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;
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” головної програми і користувач зможе обирати їх і використовувати їх так само, як і ті алгоритми, що вже були розглянуті нами в нашій дослідницькій роботі.
Висновки
Отже, ми розглянули як працюють швидкі алгоритми сортування і спробували визначити їх складність.
Застосування того чи іншого алгоритму сортування для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.
Звичайно, необхідність застосування саме швидких алгоритмів сортування очевидна. Адже прості алгоритми сортування не дають бажаної ефективності в роботі програми. Але завжди треба пам’ятати й про те, що кожний швидкий алгоритм сортування поряд із своїми перевагами може містити і деякі недоліки.
Так, алгоритм сортування деревом, хоча й працює однаково на всіх входах (так, що його складність в гіршому випадку співпадає зі складністю в середньому), але цей алгоритм має і досить суттєвий недолік: для нього потрібна додаткова пам’ять розміром 2n-1.
Розглядаючи такий швидкий алгоритм сортування, як пірамідальне сортування, можна зазначити, що цей алгоритм ефективніший ніж попередній, адже він сортує “на місці” , тобто він не потребує додаткових масивів. Крім того, цей алгоритм (“ з точністю до мультиплікативної константи” (4, 74)) оптимальний: його складність співпадає з нижньою оцінкою задачі, тобто за критеріями C(n) та M(n) він має складність O(n log2 n), але містить складний елемент в умові. Тобто, в умові A[left] має бути строго менше ніж x , а A[right] - строго більше за x. Якщо ж замість “строго більше” та “строго менше” поставити знаки, що позначають “більше, або дорівнює” та “менше, або дорівнює”, то індекси left і right пробіжать увесь масив і побіжать далі. Вийти з цієї ситуації можна було б шляхом ускладнення умов продовження перегляду, але це б погіршило ефективність програми.
В нашій роботі ми розглянули деякі швидкі алгоритми сортування та їх реалізацію мовою Pascal, дослідили не лише переваги таких алгоритмів, ефективність їх використання, але й визначили деякі недоліки окремих алгоритмів, що заважають вживати їх для вирішення першої ліпшої задачі сортування.
Отже, головною задачею, яку має вирішити людина, яка повинна розв’язати задачу сортування – це визначення як позитивних, так і усіх негативних характеристик різних алгоритмів сортування, передбачення кінцевого результату. До того ж , треба враховувати головне – чи , можливо, цю задачу задовольнить один з класичних простих алгоритмів сортування.
Список використаних джерел
1. Абрамов С. А., Зима Е. В. Начала программирования на языке Pascal. - М.: Наука, 1987.
Завантажити реферат