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

Удосконалення простих методів включеннями і вибором привело до появи значно поліпшених методів: шейкер-впорядкування, сортування Шелла, пірамідальне сортування. Ці методи  ми розглядати не будемо. Однак згодом  виявилося, що удосконалення самого гіршого методу – впорядкування простим обміном – дає взагалі кращий на сьогодні метод сортування масивів. Він має настільки блискучі характеристики, що його винахідник К. Хоор охрестив цей метод швидким сортуванням.

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

Сутність методу полягає у виконання операції часткового впорядкування масиву відносно деякого елементу. Масив називається частково впорядкованим за зростанням відносно деякого елементу. Якщо зліва від цього елементу розташовані всі , що мають менші значення, а справа – всі, що мають більші значення.

Приклад:

18 34 12 40 80 96 72

Наведений масив є частково впорядкованим відносно числа 40. для будь-якого іншого елементу часткова впорядкованість в даному масиві не виконується. Наприклад, для числа 80 зліва розташовані всі менші за нього, але справа також є елемент – 72, який має менше значення.

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

Часткове впорядкування здійснюється за таким правилом: вихідний масив розбивається на дві частини. Далі зліва від центрального елементу знаходиться елемент, більший даного, а справа – менший даного (тобто, елементи, розташовані не у своїх частинах масиву). Обрані елементи міняються місцями. Пошук і обмін продовжується, поки в кожній частині є такі елементи. Отже, відносно значення  елементу , що стоїть на центральному місці, здійснюється обмін елементів. які розташовані не у своїх частинах масиву. Після цього кожна таким чином впорядкована частина знову поділяється на дві і так до повного впорядкування масиву. Часткове впорядкування масиву розглянемо на прикладі. Елементи, що будуть обмінюватись, та центральний елемент, відносно якого здійснюється часткове впорядкування, виділимо кольором.

Вихідний масив:

44 55 12 42 18 94 06 67 32 13

Центральним є елемент 18 (з номером 5).

Знаходимо відповідні елементи для обміну: зліва – 44, справа – 13. Міняємо їх місцями:

13 55 12 42 18 94 06 67 32 44

Далі знову знаходимо елементи для обміну: зліва – 55, справа – 06

13 06 12 42 18 94 55 67 32 44

Далі знову знаходимо такі елементи: зліва – 42, справа – 18. помітимо. Що елемент. який стоїть справа, є самим числом 18 (його значення співпадає зі значенням центрального елементу). Таке може бути, оскільки часткова впорядкованість здійснюється відносно значення елементу, а не його місця в масиві. Сам елемент може міняти своє розташування в масиві, що і відбувається в даному випадку. В результаті одержимо:

13 06 12 18 42 94 55 67 32 44

Далі “зліва” буде знайдений елемент 94, а “ справа” – 12. Однак ці елементи мінятись не повинні, тому що вони насправді розташовані вірно. В даному випадку часткове впорядкування закінчилося. Після цього з масиву виділяється  дві частково невпорядковані частини: перша містить елементи 13; 06; 12 ; а друга – 94; 55; 67; 32; 44. Для кожної з них продовжується розглянута операція часткового впорядкування, але вже відносно свого центрального елементу. Помітимо, що два елементи – 18 та 42 не входять до складу жодної з частин. Це говорить про те, що ці два елементи вже впорядковані і стоять на своїх місцях. Тобто, подальший процес впорядкування здійснюється без участі цих елементів.

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

procedure quicksort (var a: massiv);

var

n1, n: integer;

procedure sort (l,r: integer);

var 

i,j: integer; {індекси}

x,w: integer; {буферні елементи}

begin

і:=l;

j:=r; {початкові значення для лівого та правого індексів}

x:=a[(l+r)div2]; {вибір середнього елемента}

repeat {пошук елементів для обміну}

{більшого злііва}

while a[і]<x do і:=і+1;

{і меншого справа}

while a[j]>x do j:=j-1;

if і<=j then 

{якщо індекси не розбіглись, то міняємо елементи місцями}

begin

w:=a[i];

a[i] :=a[j];

a[j] :=w;

i:=i+1;

j:=j-1

end;

until і>j; {завершити при розбіжності індексів}

{часткове впорядкування (розбивка)  закінчена}

{якщо ліва частина складається з більш, ніж 1 елементу, то повторити її часткове впорядкування}

if L<j then sort (L,j);

{аналогічно для правої частини}

if і<r then sort (і,r);

end;

begin

n1:=Low(a);

n:=High(a);

sort(n1,n);

end;

Очікуване число обмінів приблизно дорівнює М  n/6, а загальне число порівнянь С=nlog n. При малих n ефективність швидкого сортування невелика, тому в цих випадках краще застосовувати прості методи і, зокрема, метод простого вибору.