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

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

Є два вказівники і та j, причому на початку i = 1, j = n., де n кількість елементів масиву. Довільним чином вибирається за базовий будь-який елемент з масиву (перший, середній або останній). Нехай, наприклад, це буде перший елемент X= R₁. Встановлюємо і=1 (від першого), j =n (від останнього), якщо знайдено R_i>=X та R_j < X, то потрібно провести обмін R_i <-> R_j при умові що i<j. Після першого обміну збільшуємо і на одиницю та шукаємо R_i >=X. Якщо такий елемент знайдено то j зменшуємо на одиницю і шукаємо R_j < X. Проводимо наступний обмін. Якщо R_i >=X не знайдено, а i>=j, то перша ітерація закінчена. Отже,алгоритм працює за принципом "спалюванню свічки з обох кінців". Масив буде розділений наступним чином: R₁,R₂,…,R_i-1, R_i,R_i+1,…,R_n причому R_l < X, l=1,…,i-1; R_m <= X, m=i+1,…,n. В лівій частині масиву будуть стояти всі елементи, що є меншими від базового, а в правій – що є більшими та сам базовий елемент. Потім до кожної з цих підмножин рекурсивно застосовується даний метод. Рекурсія закінчується, коли всі підмножини будуть складатися з одного елементу, або весь масив буде впорядкований.

Розглянемо приклад:

Нехай масив включає наступні елементи:

5 3 2 6 4 1 3 7

Встановлюємо i=1, j=8, X=5.

Для i=1 виконується умова 5>=5, для j=7 виконується умова 3<5. Оскільки i<j, то проводимо обмін місцями знайдених елементів 5<->3. Повторюємо кроки для новоутвореного масиву 3 3 2 6 4 1 5 7:для i=4, 6>5, для j=6, 1<5, i<j, проводимо обмін місцями елементів 6<->1. При наступній ітерації умова i<j не виконається

3 3 2 1 4 6 5 7, i=8, j=5 i>j, отже перший прохід розділить масив на дві частини. Рекурсивно відсортовуємо по черзі обидві частини.

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

· Найгірше розбиття. Найгірша поведінка має місце у тому випадку, коли процедура, що виконує розбиття, породжує одну підзадачу з (n – 1) елементом, а другу - з 0 елементами. Нехай таке незбалансоване розбиття виникає при кожному рекурсивному виклику. Для самого розбиття потрібен час Θ (n). Тоді рекурентне співвідношення для часу роботи, можна записати наступним чином:

T (n) = T (n – 1) + T (0) + Θ (n) = T (n – 1) + Θ (n).

Розв’язком такого співвідношення є: T (n) = Θ (n ²).

· Найкраще розбиття. В найкращому випадку процедура поділу ділить задачу на дві підзадачі, розмір кожної з яких не перевищує (n / 2). Час роботи описується нерівністю: T (n) ≤ 2∙ T (n / 2) + Θ (n). Тоді: T (n) = O (n ∙log(n)) — асимптотично найкращий час.

· Середній випадок. Математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах є O (n ∙log(n)), тобто середній випадок ближчий до найкращого.