Реферат: Быстрые алгоритмы сортировки

end

else

begin

c[k]:= a[i];

k:= k+1;

i:= i+1;

end

End;

Третя процедура описує алгоритм швидкого сортування Хоара. Це є удосконалений метод сортування, що базується на сортуванні обмінами. Тобто, спочатку ми обираємо деякий “бар’єр” (один з елементів масиву). Потім ми переглядаємо елементи, що стоять зліва від “бар’єра” і порівнюємо їх з ним. Коли ми знаходимо елемент, який є більшим за “бар’єр”, то ми починаємо перглядати масив з кінця, порівнюючи елементи з “бар’єром”. Якщо ми знайдемо в правій частині масиву елемент менший за “бар’єр”, то ми переставимо місцями елемент зліва (той, що більше за “бар’єр”)і елемент з права ( той, що менше) і продовжимо перегляд. Потім ми рекурсивно застосовуємо цю процедуру для того, щоб відсортувати початок і кінець масиву. Реалізуємо цей алгоритм за допомогою циклів “While” та “RepeatUntil” та оператору “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;