Трехпутевая порозрядне швидка сортування

Всім привіт!

Сьогодні мова піде про не самому відомому алгоритмі сортування трехпутевая порозрядне швидка сортування.

Цей алгоритм є гібридом широко відомих швидкого сортування і порозрядної сортування.

Подробиці під катом.

Але для початку, згадаємо старе.

Швидке сортування (QSort)
Її знає більшість. Якщо коротко — беремо опорний елемент, обмінами робимо так, щоб з одного боку від нього в масиві залишилися менші елементи, з іншого — більші або рівні. Далі запускаємо рекурсивно ту ж процедуру на одержані частинах. Сам опорний елемент при цьому вже опинився на тому місці, на якому він буде у відсортованому масиві.

При цьому часто говорять про оптимізацію швидкого сортування.
Найвідоміша оптимізація — вибирати опорний елемент випадковим чином. Таким чином суттєво зменшується ймовірність потрапляння в випадок, коли швидка сортування показує найгіршу продуктивність ( Про(n^2), як ми всі пам'ятають).
Друга за популярністю ідея — розділяти масив не на дві, а на три частини. Елементи менше опорного, рівні йому і елементи більше опорного. Ця оптимізація помітно прискорює час виконання у випадках, коли у вихідному масиві багато однакових елементів — адже рівні опорного елементи також, як і опорний, вже «потрапили» на своє місце у відсортованому масиві, і ніяких додаткових процедур для їх сортування вже не потрібно. Зменшується і кількість виконуваних операцій і глибина рекурсивних викликів. Загалом, непоганий спосіб трохи заощадити.

Складність O(nlogn) в середньому O(n^2) в гіршому, доп. пам'ять — O(1)

Якщо що, ось тут непогано і коротко написано.

Порозрядне сортування (Radix Sort)
Трохи менш популярний алгоритм, але досить добре відомий.
Логіка його роботи проста. Припустимо, у нас є масив чисел.
Спочатку відсортуємо їх по першому(старшого) розряду. Сортування в такому разі виконується з допомогою сортування підрахунком (count sort). Складність o(n). Ми отримали 10 «кошиків» — у яких старший розряд 0, 1, 2 і т. д. Далі в кожній з кошиків запускаємо ту ж процедуру, але тільки розглядаємо вже не старший розряд, а наступний за ним, і т. д.

Кроків стільки, скільки розрядів у числах. Відповідно, складність алгоритму — O(n*k), k — число розрядів.

Є два види такої сортування — MSD(most significant digit — спочатку старший розряд) і LSD(least significant digit — спочатку молодший розряд).
LSD кілька зручніше для сортування чисел, т. к. не доводиться «приписувати» до чисел зліва незначущі 0 для вирівнювання числа розрядів.
MSD ж зручніше для сортування рядків.

Алгоритмом у такій реалізації потрібна додаткова пам'ять — O(n).

Прочитати детальніше можна, наприклад, тут.

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

Використовувати qsort, який активно порівнює елементи, виглядає занадто накладним — порівняння рядків операція довга. Так, ми можемо написати свій компаратор, який буде кілька ефективніше. Але все ж.

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

А що якщо як-небудь чином скомбінувати ці алгоритми?

Логіка роботи отриманого алгоритму така:

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

Складність сортування — O(nlogn). Додаткова пам'ять — O(1).

Мінус цього алгоритму в тому, що на відміну від порозрядної сортування, вона розбиває масив лише на три частини, що, наприклад, обмежує можливості многопоточной реалізації.
Перевага над швидкої сортуванням в тому, що нам не потрібно порівнювати елементи «цілком».
Перевага над порозрядної сортуванням — нам не потрібна додаткова пам'ять.

Окремо варто відзначити, що такий сортуванням зручно користуватися, коли елементом вихідного масиву є інший масив.
Тоді, якщо вихідний масив input, то, наприклад, старший розряд — input[i][0], наступний — input[i][1] і т. д.
Таке сортування називається багатовимірної швидкої сортуванням, або ж multikey quicksort.

Детальніше і більш розгорнуто — Р. Седжвік, Фундаментальні алгоритми на С++, ч. 3, гол. 10, 10.4 «Трехпутевая порозрядне швидка сортування»

Схема роботи алгоритму:
image

Ще раз про трехпутевое поділ
Відзначимо, що найбільш простий спосіб реалізувати поділ масиву на три частини відносного опорного — використовувати алгоритм Бентлі і Макилроя.
Він полягає в тому, що в стандартну процедуру поділу qsort вноситься наступне доповнення (безпосередньо після обміну елементів).
Якщо оброблений елемент влучив у ліву частину масиву (тобто він не більше опорного) і він дорівнює опорного, то він поміщається в ліву частину масиву шляхом обміну з відповідним елементом (який вже був повністю оброблений і відповідно, менше опорного).
Аналогічно, якщо оброблений елемент потрапив у праву частину масиву і дорівнює опорного, то він поміщається в праву частину масиву.
Після завершення процедури поділу, коли кількість елементів менше опорного вже точно відомо, виконується перенесення рівних елементів в середину масиву (відразу після елементів, менших опорного).

Детальніше про нього можна прочитати в Р. Седжвік — Фундаментальні алгоритми на С++, ч. 3, гол. 7, п. 7.6 «Дубльовані ключі».
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.