Швидкі алгоритми сортування, Детальна інформація
Швидкі алгоритми сортування
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” головної програми і користувач зможе обирати їх і використовувати їх так само, як і ті алгоритми, що вже були розглянуті нами в нашій дослідницькій роботі.
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” головної програми і користувач зможе обирати їх і використовувати їх так само, як і ті алгоритми, що вже були розглянуті нами в нашій дослідницькій роботі.
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021