Алгоритми і структури даних для початківців: сортування


У цій частині ми подивимося на п’ять основних алгоритмів сортування даних в масиві. Розпочнемо з найпростішого – сортування бульбашкою – і закінчимо “швидким сортуванням” (quicksort).

Для кожного алгоритму, окрім пояснення його роботи, ми також вкажемо його складність по пам’яті і часу в найгіршому, найкращому і середньому випадку.


Також дивитеся інші матеріали цієї серії: бінарне дерево, стеки і черги, динамічний масив, зв’язний список, оцінка складності алгоритму і множини.

Метод Swap

Для спрощення коду і поліпшення читаності ми введемо метод Swap, який мінятиме місцями значення в масиві по індексу.

void Swap (T[] items, int left, int right){ if (left != right) { T temp = items[left]; items[left] = items[right]; items[right] = temp; }}

Бульбашкове сортування

Складність Найкращий випадок В середньому Найгірший випадок
Час O (n) O (n2) O (n2)
Пам’ять O (1) O (1) O (1)

Сортування бульбашкою – це найпростіший алгоритм сортування. Він проходить по масиву кілька разів, на кожному етапі переміщаючи найбільше значення з невідсортованих в кінець масиву.

Наприклад, у нас є масив цілих чисел :

При першому проході по масиву ми порівнюємо значення 3 і 7. Оскільки 7 більше 3, ми залишаємо їх як є. Після чого порівнюємо 7 і 4. 4 менше 7, тому ми міняємо їх місцями, переміщаючи сімку на одну позицію ближче до кінця масиву. Тепер він виглядає так:

Цей процес повторюється до тих пір, поки сімка не дійде майже до кінця масиву. У кінці вона порівнюється з елементом 8, яке більше, тобто обміну не відбувається. Після того, як ми обійшли масив один раз, він виглядає так:

Оскільки був здійснений принаймні один обмін значень, нам треба пройти по масиву ще раз. В результаті цього проходу ми переміщаємо на місце число 6.

І знову був зроблений як мінімум один обмін, тобто проходимо по масиву ще раз.

При наступному проході обміну не робиться, що означає, що наш масив відсортований, і алгоритм закінчив свою роботу.

public void Sort (T[] items){ bool swapped; do { swapped = false; for (int i = 1; i < items.Length; i++) { if (items[i - 1].CompareTo (items[i])  > 0) { Swap (items, i - 1, i); swapped = true; } } } while (swapped != false);}

Сортування вставками

Складність Найкращий випадок В середньому Найгірший випадок
Час O (n) O (n2) O (n2)
Пам’ять O (1) O (1) O (1)

Сортування вставками працює, проходячи по масиву і переміщаючи потрібне значення в початок масиву. Після того, як оброблена чергова позиція, ми знаємо, що усі позиції до неї відсортовані, а після неї – ні.

Важливий момент: сортування вставками обробляє елементи масиву по порядку. Оскільки алгоритм проходить по елементах зліва направо, ми знаємо, що все, що зліва від поточного індексу – вже відсортовано. На цьому малюнку показано, як збільшується відсортована частина масиву з кожним проходом:

Поступово відсортована частина масиву росте, і, врешті-решт, масив виявиться впорядкованим.

Давайте поглянемо на конкретний приклад. Ось наш невідсортований масив, який ми використовуватимемо :

Алгоритм розпочинає роботу з індексу 0 і значення 3. Оскільки це перший індекс, масив до нього включно вважається відсортованим.

Далі ми переходимо до числа 7. Оскільки 7 більше, ніж будь-яке значення у відсортованій частині, ми переходимо до наступного елементу.

На цьому етапі елементи з індексами 0.1 відсортовані, а про елементи з індексами 2.n нічого не відомо.

Наступним перевіряється значення 4. Оскільки воно менше семи, ми повинні перенести його на правильну позицію у відсортовану частину масиву. Залишається питання: як її визначити? Це здійснюється методом FindInsertionIndex. Він порівнює передане йому значення (4) з кожним значенням у відсортованій частині, поки не знайде місце для вставки.

Отже, ми знайшли індекс 1 (між значеннями 3 і 7). Метод Insert здійснює вставку, видаляючи значення, що вставляється, з масиву і зрушуючи усі значення, починаючи з індексу для вставки, управо. Тепер масив виглядає так:

Тепер частина масиву, починаючи від нульового елементу і закінчуючи елементом з індексом 2, відсортована. Наступний прохід розпочинається з індексу 3 і значення 4. У міру роботи алгоритму ми продовжуємо робити такі вставки.

Коли більше немає можливостей для вставок, масив вважається повністю відсортованим, і робота алгоритму закінчена.

public void Sort (T[] items){ int sortedRangeEndIndex = 1; while (sortedRangeEndIndex < items.Length) { if (items[sortedRangeEndIndex].CompareTo (items[sortedRangeEndIndex - 1])  < 0) { int insertIndex = FindInsertionIndex (items, items[sortedRangeEndIndex]); Insert (items, insertIndex, sortedRangeEndIndex); } sortedRangeEndIndex++; }}
private int FindInsertionIndex (T[] items, T valueToInsert){ for (int index = 0; index < items.Length; index++) { if (items[index].CompareTo (valueToInsert)  > 0) { return index; } } throw new InvalidOperationException ("The insertion index was not found");} private void Insert (T[] itemArray, int indexInsertingAt, int indexInsertingFrom){ // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // // Дій: // 1: Зберегти поточний індекс в temp // 2: Замінити indexInsertingAt на indexInsertingFrom // 3: Замінити indexInsertingAt на indexInsertingFrom у позиції +1 // Зрушити елементи вліво на один. // 4: Записати temp на позицію в масиві + 1. // Крок 1. T temp = itemArray[indexInsertingAt]; // Крок 2.
itemArray[indexInsertingAt] = itemArray[indexInsertingFrom]; // Крок 3. for (int current = indexInsertingFrom; current > indexInsertingAt; current--) { itemArray[current] = itemArray[current - 1]; } // Крок 4. itemArray[indexInsertingAt + 1] = temp;}

Сортування вибором

Складність Найкращий випадок В середньому Найгірший випадок
Час O (n) O (n2) O (n2)
Пам’ять O (1) O (1) O (1)

Сортування вибором – це деякий гібрид між бульбашковою і сортуванням вставками. Як і сортування бульбашкою, цей алгоритм проходить по масиву раз по раз, переміщаючи одно значення на правильну позицію. Проте, на відміну від бульбашкового сортування, він вибирає найменше невідсортоване значення замість найбільшого. Як і при сортуванні вставками, впорядкована частина масиву розташована на початку, тоді як у бульбашковому сортуванні вона знаходиться у кінці.

Давайте подивимося на роботу сортування вибором на нашому невідсортованому масиві.

При першому проході алгоритм за допомогою методу FindIndexOfSmallestFromIndex намагається знайти найменше значення в масиві і перемістити його в початок.

Маючи такий маленький масив, ми відразу можемо сказати, що найменше значення – 3, і воно вже знаходиться на правильній позиції. На цьому етапі ми знаємо, що на першій позиції в масиві (індекс 0) знаходиться найменше значення, отже, початок масиву вже відсортований. Тому ми починаємо другий прохід – цього разу по індексах від 1 до n – 1.

На другому проході ми визначаємо, що найменше значення – 4. Ми міняємо його місцями з другим елементом, сімкою, після чого 4 встає на свою правильну позицію.

Тепер невідсортована частина масиву розпочинається з індексу 2. Вона росте на один елемент при кожному проході алгоритму. Якщо на якому-небудь проході ми не зробили жодного обміну, це означає, що масив відсортований.

Після ще двох проходів алгоритм завершує свою роботу:

public void Sort (T[] items){ int sortedRangeEnd = 0; while (sortedRangeEnd < items.Length) { int nextIndex = FindIndexOfSmallestFromIndex (items, sortedRangeEnd); Swap (items, sortedRangeEnd, nextIndex); sortedRangeEnd++; }} private int FindIndexOfSmallestFromIndex (T[] items, int sortedRangeEnd){ T currentSmallest = items[sortedRangeEnd]; int currentSmallestIndex = sortedRangeEnd; for (int i = sortedRangeEnd + 1; i < items.Length; i++) { if (currentSmallest.CompareTo (items[i])  > 0) { currentSmallest = items[i]; currentSmallestIndex = i; } } return currentSmallestIndex;
}

Сортування злиттям

Складність Найкращий випадок В середньому Найгірший випадок
Час O (n·log n) O (n·log n) O (n·log n)
Пам’ять O (n) O (n) O (n)

Розділяй і володарюй

Досі ми розглядали лінійні алгоритми. Вони використовують мало додаткової пам’яті, але мають квадратичну складність. На прикладі сортування злиттям ми подивимося на алгоритм типу “розділяй і володарюй” (divide and conquer).

Алгоритми цього типу працюють, розділяючи велике завдання на дрібніші, вирішувані простіше. Ми користуємося ними щодня. Приміром, пошук в телефонній книзі – один з прикладів такого алгоритму.

Якщо ви хочете знайти людину по прізвищу Петров, ви не станете шукати, починаючи з букви А і перевертаючи по одній сторінці. Ви, швидше за все, відкриєте книгу десь посередині. Якщо потрапите на букву Т, перелистнете декілька сторінок назад, можливо, надто багато – до букви О. Тоді ви підете вперед. Таким чином, перегортаючи туди і назад все меншу кількість сторінок, ви, врешті-решт, знайдете потрібну.

Наскільки ефективні ці алгоритми?

Припустимо, що в телефонній книзі 1000 сторінок. Якщо ви відкриваєте її на середині, ви відкидаєте 500 сторінок, в яких немає шуканої людини. Якщо ви не потрапили на потрібну сторінку, ви вибираєте праву або ліву сторону і знову залишаєте половину доступних варіантів. Тепер вам потрібно проглянути 250 сторінок. Таким чином ми ділимо наше завдання навпіл знову і знову і можемо знайти людину в телефонній книзі всього за 10 переглядів. Це складає 1% від усієї кількості сторінок, які нам довелося б проглянути при лінійному пошуку.

Сортування злиттям

При сортуванні злиттям ми розділяємо масив навпіл до тих пір, поки кожна ділянка не стане завдовжки в один елемент. Потім ці ділянки повертаються на місце (зливаються) в правильному порядку.

Давайте подивимося на такий масив:

Розділимо його навпіл:

І ділитимемо кожну частину навпіл, поки не залишаться частини з одним елементом:

Тепер, коли ми розділили масив на максимально короткі ділянки, ми зливаємо їх в правильному порядку.

Спочатку ми отримуємо групи по два відсортовані елементи, потім ” збираємо” їх в групи по чотири елементи і у кінці збираємо всі разом у відсортований масив.

Для роботи алгоритму ми повинні реалізувати наступні операції:

  1. Операцію для рекурсивного розділення масиву на групи (метод Sort).
  2. Злиття в правильному порядку (метод Merge).

Варто відмітити, що на відміну від лінійних алгоритмів сортування, сортування злиттям ділитиме і склеюватиме масив незалежно від того, був він відсортований спочатку або ні. Тому, попри те, що у гіршому разі він відпрацює швидше, ніж лінійний, у кращому разі його продуктивність буде нижча, ніж у лінійного. Тому сортування злиттям – не саме краще рішення, коли потрібно відсортувати частково упорядченный масив.

public void Sort (T[] items){ if (items.Length <= 1) { return; } int leftSize = items.Length / 2;
int rightSize = items.Length - leftSize; T[] left = new T[leftSize]; T[] right = new T[rightSize]; Array.Copy (items, 0, left, 0, leftSize); Array.Copy (items, leftSize, right, 0, rightSize); Sort (left); Sort (right); Merge (items, left, right);} private void Merge (T[] items, T[] left, T[] right){ int leftIndex = 0; int rightIndex = 0; int targetIndex = 0; int remaining = left.Length + right.Length; while (remaining > 0) { if (leftIndex >= left.Length) { items[targetIndex] = right[rightIndex++]; } else if (rightIndex >= right.Length) { items[targetIndex] = left[leftIndex++]; } else if (left[leftIndex].CompareTo (right[rightIndex])  < 0) { items[targetIndex] = left[leftIndex++]; } else {
items[targetIndex] = right[rightIndex++]; } targetIndex++; remaining--; }}

Швидке сортування

Складність Найкращий випадок В середньому Найгірший випадок
Час O (n·log n) O (n·log n) O (n2)
Пам'ять O (1) O (1) O (1)

Швидке сортування - це ще один алгоритм типу "розділяй і володарюй". Він працює, рекурсивно повторюючи наступні кроки:

  1. Вибрати ключовий індекс і розділити по ньому масив на дві частини. Це можна робити різними способами, але в цій статті ми використовуємо випадкове число.
  2. Перемістити усі елементи більше ключового в праву частину масиву, а усі елементи менші за ключовий - в ліву. Тепер ключовий елемент знаходиться в правильній позиції - він більше будь-якого елементу ліворуч і менше будь-якого елементу справа.
  3. Повторюємо перші два кроки, поки масив не буде повністю відсортований.

Давайте подивимося на роботу алгоритму на наступному масиві:

Спочатку ми випадковим чином вибираємо ключовий елемент:

int pivotIndex =_pivotRng.Next (left, right);

Тепер, коли ми знаємо ключовий індекс (4), ми беремо значення, що знаходиться по цьому індексу (6), і переносимо значення в масиві так, щоб усі числа більше або рівні ключовому були в правій частині, а усі числа менші за ключовий - в лівій. Зверніть увагу, що в процесі перенесення значень індекс ключового елементу може змінитися (ми побачимо це незабаром).

Переміщення значень здійснюється методом partition.

На цьому етапі ми знаємо, що значення 6 знаходиться на правильній позиції. Тепер ми повторюємо цей процес для правої і лівої частин масиву.

Ми рекурсивно викликаємо метод quicksort на кожній з частин. Ключовим елементом в лівій частині стає п'ятірка. При переміщенні значень вона змінить свій індекс. Головне - пам'ятати, що нам важливе саме ключове значення, а не його індекс.

Знову застосовуємо швидке сортування:

І ще раз:

У нас залишилося одно невідсортоване значення, а, оскільки ми знаємо, що усе інше вже відсортоване, алгоритм завершує роботу.

Random_pivotRng = new Random (); public void Sort (T[] items){ quicksort (items, 0, items.Length - 1);}
private void quicksort (T[] items, int left, int right){ if (left < right) { int pivotIndex =_pivotRng.Next (left, right); int newPivot = partition (items, left, right, pivotIndex); quicksort (items, left, newPivot - 1); quicksort (items, newPivot + 1, right); }} private int partition (T[] items, int left, int right, int pivotIndex){ T pivotValue = items[pivotIndex]; Swap (items, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) { if (items[i].CompareTo (pivotValue)  < 0) { Swap (items, i, storeIndex); storeIndex += 1; } } Swap (items, storeIndex, right); return storeIndex;}

Висновок

На цьому ми закінчуємо наш цикл статей по алгоритмах і структурах даних для початківців. За цей час ми розглянули зв'язні списки, динамічні масиви, двійкове дерево пошуку і множини з прикладами коду на C#.

Переклад статті "Sorting Algorithms"

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *