Швидкі алгоритми сортування, Детальна інформація

end

End;

Третя процедура описує алгоритм швидкого сортування Хоара. Це є удосконалений метод сортування, що базується на сортуванні обмінами. Тобто, спочатку ми обираємо деякий “бар’єр” (один з елементів масиву). Потім ми переглядаємо елементи, що стоять зліва від “бар’єра” і порівнюємо їх з ним. Коли ми знаходимо елемент, який є більшим за “бар’єр”, то ми починаємо перглядати масив з кінця, порівнюючи елементи з “бар’єром”. Якщо ми знайдемо в правій частині масиву елемент менший за “бар’єр”, то ми переставимо місцями елемент зліва (той, що більше за “бар’єр”)і елемент з права ( той, що менше) і продовжимо перегляд. Потім ми рекурсивно застосовуємо цю процедуру для того, щоб відсортувати початок і кінець масиву. Реалізуємо цей алгоритм за допомогою циклів “While” та “Repeat Until” та оператору “if”, який відповідає за порівняння.

Procedure HoareSearch ( var a:mas; L, R: Integer);

Var left, right, b, x: Integer;

Begin

if L < R then

begin

x:= a[( L+R) div 2];

left:= L;

right:= R;

Repeat

While a[ left] < x do left:= Succ(left);

While a[right] >x do right:= Pred(right);

If left >= right then

Begin

b:= a[left];

a[left]:= a[right];

a[right]:=b;

left:= Succ( left);

right:= Pred(right);

End;

Until left > right;

HoareSearch ( L, right);

HoareSearch (left, R);

end;

End;



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

В своїй роботі ми написали програму, що сортує масив за допомогою лише трьох алгоритмів сортування. Але можна створити процедури, які б містили алгоритми сортування деревом та пірамідального сортування. Це не вплине дуже суттєво на нашу програму. Потрібно буде лише додати ці процедури оператор “Case of” головної програми і користувач зможе обирати їх і використовувати їх так само, як і ті алгоритми, що вже були розглянуті нами в нашій дослідницькій роботі.