Швидкі алгоритми сортування

Програма виконує сортування послідовності за трьома алгоритмами сортування. Кожний окремий алгоритм представлений у вигляді окремої процедури.

Так, процедура Qsort виконує швидке сортування масиву, що вводиться. Під час роботи цього алгоритму відбувається аналіз даної послідовності одночасно у двох напрямках ( зліва-направо і зправа-наліво) . комп’ютер порівнює два елементи, що стоять поряд зліва. Якщо ці елементи стоять на своїх місцях, тобто перший з них є меншим за другий, то комп’ютер порівнює перший елемент з останнім. Якщо при порівнянні останній елемент виявиться меншим за перший, то комп’ютер виконає перестановку цих двох елементів. Такі дії будуть відбуватися до тих пір, поки індикатор, якій відповідає за ліву частину послідовності (в нашій процедурі це “i”) не перейде на праву частину, а індикатор, що відповідає за праву частину масиву (в нашій процедурі це “j”) не перейде на праву частину. Далі та ж сама процедура викликається рекурсивно. Тобто, якщо ліва частина вже відсортована, то ми викликаємо ту саму процедуру і комп’ютер виконує ті самі дії, але в параметрах процедури ми змінюємо ліву границю. Те саме відбувається, коли відсортована права частина масиву.

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

Procedure _Qsort (var a:mas; low, hi: byte);

Var i,j:byte;

begin

if hi> low then

begin i:= low;

j:= hi;

x:= a[i];

While i< j do

if a[i+1]<=x then

begin

a[i]:= a[i+1];

a[i+1]:=x;

i:= i+1;

end

else

begin

if a[j]<=x then