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

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

begin

y:=a[j];

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

a[i+1]:=y;

end;

j:=j-1

end;

-Qsort (a, low, i-1);

-Qsort (a, i+1, hi);

end;

end;

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

Procedure Mergesort;

Var i, j, k: byte;

Begin

i:=1;

j:=1;