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

Щоб розуміти, як і навіщо цей алгоритм покращують, потрібно розібратися, як він працює у своєму первісному вигляді. Варто зазначити, що, як на свою обчислювальну ефективність, цей алгоритм досить простий для розуміння та реалізації.

Алгоритм працює за принципом «розділяй і володарюй» — ми будемо ділити масив і застосовувати один і той самий алгоритм до його частин, які будуть поступово зменшуватися. Загальна схема алгоритму виглядає так:

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

Після виконання цих дій ми отримаємо повністю відсортований масив.

Розглянемо другий пункт детальніше: що ж там відбувається? Для цього візьмемо несортований масив елементів [7, 2, 1, 8, 6, 3, 5, 4] і пройдемо його покроково.

Крок 1

Для початку оберемо опорний елемент — візьмемо останній елемент масиву, він дорівнює 4. Також вводимо два лічильники — i та j. Будемо вважати, що індексація в масиві починається з 0. Тоді i = -1, а j = 0.

Порівнюємо j-й елемент масиву [7] з опорним елементом [4]. Якщо j-й елемент більший за опорний, то просто інкрементуємо лічильник j. У нашому випадку на першому кроці ми так і зробимо.

Тепер j = 1, порівнюємо j-й елемент масиву [2] з опорним елементом [4]. Якщо він менший за опорний, то інкрементуємо лічильник i. Тепер i = 0, міняємо місцями i-й та j-й елементи масиву. У нашому випадку міняємо місцями нульовий і перший елементи масиву, отримуємо масив [2, 7, 1, 8, 6, 3, 5], опорний елемент [4] та інкрементуємо лічильник j.

Далі крок за кроком рухаємося масивом.

Крок 2

Лічильник j = 2, порівнюємо [1] і [4]. В цьому випадку інкрементуємо i, i = 1, далі міняємо місцями i-й та j-й елементи масиву [7] і [1], отримуємо масив [2, 1, 7, 8, 6, 3, 5], опорний елемент [4] і збільшуємо лічильник j.

Крок 3

Лічильник j = 3, порівнюємо [8] і [4]. У цьому випадку інкрементуємо тільки лічильник j.

Крок 4

Лічильник j = 4, порівнюємо [6] і [4]. У цьому випадку інкрементуємо тільки лічильник j.

Крок 5

Лічильник j = 5, порівнюємо [3] і [4]. У цьому випадку інкрементуємо i, i = 2 і міняємо місцями i-й та j-й елементи масиву [7] і [3], отримуємо масив [2, 1, 3, 8, 6, 7, 5], опорний елемент [4] і збільшіємо лічильник j.

Крок 6

Лічильник j = 6, порівнюємо [5] і [4]. Лічильник j можна не збільшувати, оскільки ми досягли кінця масиву.

Тепер залишилося знайти місцинку в масиві для нашого опорного елемента. Вона знаходиться на i+1 позиції в масиві. Отримуємо [2, 1, 3] ≤ [4] < [8, 6, 7, 5]. Але так як у підмасивах знаходиться більше двох елементів, необхідно виконати аналогічне сортування для підмасиву елементів, які менше або дорівнюють опорному [2, 1, 3], та елементів, які більші за опорний [8, 6, 7, 5].

Надалі описані вище дії повторюються для кожного з підмасивів доки масив не буде повністю відсортовано.

За цими кроками нескладно реалізувати алгоритм в коді.

Особливості алгоритму

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

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

Переваги і недоліки алгоритму

Що стосується складності швидкого сортування, то в найкращому випадку ми отримаємо складність Ω (n log n), а в найгіршому — O(n²). Окрім низької обчислювальної складності цьому алгоритму притаманні й інші переваги:

на практиці це один з найбільш швидкодіючих алгоритмів внутрішнього сортування;
алгоритм доволі простий як для розуміння, так і для реалізації;
потребує лише O(n) пам’яті, для покращеної версії — O(1);
дозволяє розпаралелювання для сортування підмасивів;
працює на пов’язаних списках;
є найефективнішим для сортування великої кількості даних.

Недоліками можна вважати:

нестійкість;
обчислювальна складність сильно деградує за умови невдалих вхідних даних.

Цей алгоритм, нехай і з модифікаціями, використовується в різних мовах програмування. Наприклад, в Java його реалізацію можна зустріти в бібліотеці java.util.Arrays, в методі sort(). А ось що написано в документації Oracle: “Реалізація: в якості алгоритму використовується Dual-Pivot Quick Sort, розроблений Володимиром Ярославським, Джоном Бентлі та Джошуа Блохом”. Саме тому цей алгоритм заслуговує вашої уваги.

Ще більше сортувань ви знайдете тут: