Алгоритм

Швидке сортування використовує метод програмування який називають поділяй і владарюй. Масив ділять на дві частини, так, щоб кожен елемент лівої частини був менший за будь-який з правої. Потім беруть ліву частину і рекурсивно повторюють такі дії для неї. Так само і для правої. Коли розмір частини досягне одного елемента, то масив очевидно буде відсортованим. Запишемо це в мові C.

void qsort(int *a, int l, int r)

{

if(l>=r) return;

int c=partition(int *a, int l, int r);

qsort(a,l,c);

qsort(a,c+1,r);

}

Тут параметри l і r показують межі сортування.

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

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

int partition(int *a, int l, int r)

{

int x=a[l];

int i=l-1;

int j=r+1;

while(1)

{

do{ j--; } while(a[j]>x);

do{ i++; } while(a[i]<x);

if(i<j) swap(a+i,a+j);

else return j;

}

}

Швидкість

Очевидно, що функція partition працює за O(n). Спочатку вона раз викликається для всього масиву. Потім два рази для половинок (O(n/2) + O(n/2)). Потім чотири рази для четвертинок. А в самому кінці n разів для частин, розмір яких дорівнює 1. Тому бачимо що на кожному рівні рекурсії сумарний час роботи рівний O(n).

Глибина ж рекурсії дорівнює ln(n), якщо масив ділиться на частини рівномірно. Складність алгоритму буде O(n ln(n)) Якщо ж щоразу одна частина має один елемент, а інша всі решту, то таких поділів буде n. Тоді складність буде O(n²).

Модифіковані методи сортування

Головний недолік простих методів - обмін ведеться в основному між сусідними елементами. Тому бажано робити якомога ширші обміни.