10.2. Алгоритм швидкого сортування

У р. 5 ми розглянули кілька розповсюджених алгоритмів упоряд­кування послідовності чисел. Опишемо ще один такий алгоритм. Його побудовано з використанням рекурсії.

Розглянемо таке перетворення масиву: нехай дано масив а1, а2,…, аn. Необхідно переставити його елементи так, щоб спочатку в масиві розташувати групу елементів, менших за початкове значення а1, потім - власне це значення, а потім - групу більших елементів. Для цього неодхідно виконати не більше, ніж n-1 порівнянь і n-1 переміщень.

Використовуючи описане перетворення, можна побудувати рекур­сивний алгоритм упорядкування масиву - швидке впорядкування. Якщо масив містить один елемент, то він впорядкований. У протилежному випадку застосовуємо до нього описане перетворення і визначаємо результат упорядкування так: спочатку в масиві розташовано першу групу елементів, упорядкованих за допомогою алгоритму швидкого сортування; потім без змін той елемент, який відокремлював першу і другу групи елементів; далі - другу групу елементів, упорядкованих за допомогою алгоритму швидкого сортування. Цей алгоритм не використовує додаткового масиву і потребує в середньому приблизно п log2n порівнянь і стільки ж переміщень елементів. Проте це лише середнє значення: у найгіршому випадку кількість порівнянь досягатиме n (n-1)/2.

З метою складення процедури швидкого сортування нам доведеться спочатку відповісти на кілька запитань. Перше з них: як виконати однократне перетворення масиву? Щоб відокремити дві групи елементів масиву - менших і більших за значення першого елемента - необхідно один раз перебрати елементи масиву, порівняти їх з цим значенням і виконати необхідні переміщення. Зауважимо, що у цьому випадку індекс елемента, в якому зберігатиметься перше значення, завжди буде меншим за індекс елемента, зі значенням якого його порівнюють. Для зберігання цих індексів використаємо змінні відповідно і та j. Отже, якщо черговий елемент більший за перше значення, то переходимо до наступного. У протилежному випадку групу елементів від i-го до j-1-го необхідно перемістити на одну позицію вперед, а j-й елемент — на місце, що звільнилося. Схожі зміни відбуваються з масивом під час сортування методом бульбашки. Тільки тут «підіймається» не один (перший) елемент, а ціла група елементів, значення яких не менші за значення першого.

Сортування частин масиву можна виконати за допомогою рекурсивних викликів процедури сортування, однак у цьому випадку виникає друге запитання: як передавати цій процедурі частини масиву? Адже в мові Pascal діють правила строгої типізації, і відповідні формальні та фактичні параметри мусять мати еквівалентні типи. Щоб не виникало суперечностей під час звертання до процедури швидкого сортування для передавання їй масиву (чи довільної його частини), використаємо безтиповий параметр, який в тілі процедури наділятимемо типом « масив _дійсних_чисел». Відповідним йому фактичним парамет­ром може бути довільний елемент масиву, що є першим у тій частині, яка підлягає впорядкуванню. Другий параметр процедури повинен задавати кількість елементів цієї частини.

Нижче наведено текст програми з оголошеною процедурою quicksort і двома викликами її для впорядкування масивів х та у. Ці масиви оголошено як типізовані константи:

program quick;

type vl=array[1..10]of real;

v2=array[1..17]of real;

const X:vl=(5,3,9,2,l,8,5,6,2,l);

y:v2=(10,9,8,7,6,5,4,3,2,1,0, -1,-2,-3,-4, -5,-6);

procedure writeRealMas(var a; n:integer);

{процедура виведення масиву а дійсних чисел розміру п<=2000)

type mas=array [1. .2000] of real;

var і:integer;

begin for i:=l to n do write(mas(a) [i];8:3);

writeln

end; {writeRealMas}

procedure quicksort(var a; n:integer);

{процедура швидкого сортування масиву а дійсних чисел розміру n<=2000}

type mas=array[1..2000]of real;

var c:real; і, j , k : integer;

begin i:=l; j:=2; {перетворення масиву}

while j<=n do

if mas(a) [i]<=mas(a) [j] then inc(j) else

begin c:=mas(a)[j]; {переміщаємо групу більших}

for k:=j-l downto і do mas(a) [k+1] :=mas(a) [k];

mas(a) [i] :=c; inc(i) ; inc (j)

end; {if & while}

if i>2 then quicksort(а,і - 1) ; {впорядковуємо менші}

if n-i>2 then quicksort(mas(a) [i+l],n-i) {та більші}

end;{quіckSort}

Begin writeln ('Масив х'); writeRealMas (x, 10) ;

quicksort(x,10); writeln('Після впорядкування');

writeRealMas(x,10) ; readln;

writeln (' Масив у'); writeRealMas (у, 17);

quicksort(у,17); writeln('Після впорядкування');

writeRealMas(у,17)

End.

Результати роботи програми:

Масин х

5.000 3.000 9.000 2.000 1.000 8.000 5.000 6.000 2.000 1.000

Після впорядкування

1.000 1.000 2.000 2.000 3.000 5.000 5.000 6.000 8.000 9.000

Масив у

10.000 9.000 8.000 7.000 6.000 5.000 4.000 3.000 2.000 1.000

0.000 -1.000 -2.000 -3.000 -4.000 -5.000 -6.000 Після впорядкування

-6.000 5.0 00 -4.000 -3.000 -2.000 -1.000 0.000 1.000 2.000 3.000

4.000 5.000 6.000 7.000 8.000 9.000 10.000

Упорядкування частини масиву за алгоритмом швидкого сортуван­ня подібне до сортування цілого масиву. Цю особливість алгоритму природно визначати у термінах рекурсії, що ми і продемонстрували на прикладі останньої програми.