Быстрые алгоритмы сортировки
По суті цей алгоритм працює на основі алгоритму сортування обмінами, але цей алгоритм вважається швидким, оскільки перегляд послідовності відбувається у двох напрямках одночасно. Реалізовано ж цей алгоритм за допомогою оператору “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
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;
for k:=1 to n_c do c[k]:=0;
k:=1;
While ( i<= n_a ) or ( j<=n_b ) do
if i= n_a+1 then
begin
c[k]:=b[j];
k:=k+1;
j:= j+1;
end
else
if i= n_b+1 then
begin
c[k]:=a[i];
k:= k+1;
i:=i+1 ;
end
else
if a[i]= b[j] then
begin
c[k]:=b[j];
c[k+1]:= a[i];
k:=k+2;
i:=i+1;
j:=j+1
end
else
if a[i] > b[j] then
begin
c[k]:= b[j];
k:= k+1;
j:= j+1;
end
else
begin
c[k]:= a[i];
k:= k+1;
i:= i+1;