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


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

У цій частині ми подивимося на п’ять основних алгоритмів сортування даних у масиві. Розпочнемо з найпростішого – сортування бульбашкою – і закінчимо “швидким сортуванням” (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, тому ми міняємо їх місцями, переміщуючи 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. Оскільки воно менше 7, ми повинні перенести його на правильну позицію у відсортовану частину масиву. Залишається питання: “Як її визначити?”. Це здійснюється методом 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. Ми міняємо його місцями з другим елементом, 7, після чого 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 на кожній з частин. Ключовим елементом в лівій частині стає 5. При переміщенні значень 5 змінить свій індекс. Головне – пам’ятати, що нам важливе саме ключове значення, а не його індекс.

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

І ще раз:

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

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”

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Trends: основні алгоритми сортування і пошуку

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

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