Var A : array[1..n] of Integer;

{ процедури Swap, Hoare, введення і висновку }

Begin

Inp; Hoare(1, n); Out

End.

Аналіз складності алгоритму в середньому, що використовує гіпотезу про рівну імовірність усіх входів, показує, що:

C(n) = O(n log₂ n), M(n) = O(n log₂ n)

У гіршому випадку, коли в якості бар'єрного вибирається, наприклад, максимальний елемент підмассиву, складність алгоритму квадратична.

1.4 Метод цифрового сортування

Іноді при розв’язанні задач типу задачі сортування можна використовувати особливості типу перетворюваних даних для одержання ефективного алгоритму. Розглянемо одну з таких задач - задачу про звертання підстановки.

Підстановкою безлічі 1..n назвемо двовимірний масив A[1..2, 1..n] виду

1	2	..........	n-1	n
J1	j2	...........	jn-1	jn

у якому 2-ий рядок містить всі елементи відрізка 1..n. Підстановка B називається зворотньою до підстановки A, якщо B виходить з A сортуванням стовпчиків A у порядку зростання елементів 2-го рядка з наступною перестановкою рядків. Потрібно побудувати алгоритм обчислення зворотньої підстановки. З визначення випливає, що стовпчик [i, j_i ] підстановки A потрібно перетворити в стовпчик [j_i , i] і поставити на j_i -те місце в підстановці B.

{Type NumSet = 1..n;

Substitution = array[ 1..2, NumSet] of NumSet; }

Procedure Reverse ( Var A, B : Substitution);

Begin

For i := 1 to n do begin

B[A[2, i], 2] := i; B[A[2, i], 1] := A[2, i]

end

End;

Складність процедури Reverse лінійна, оскільки тіло арифметичного циклу складається з двох операторів присвоювання, в той час як стовпчики підстановки відсортовані.

2. Практична реалізація мовою Паскаль швидких алгоритмів сортування

Практичною метою нашої дослідницької роботи було написання мовою Pascal програми, яка б виконувала сортування будь-якої послідовності елементів. Для того, щоб продемонструвати роботу різних швидких алгоритмів сортування, ми залишили вибір конкретного алгоритму на розсуд користувача програми. Тобто, ми створили основну програму – меню, яка пропонує користувачеві три можливі варіанти швидких алгоритмів сортування: швидке сортування, сортування Хоара та сортування “злиттям”. Вибір певного алгоритму здійснюється за допомогою оператору “caseof”, тобто натисканням клавіш клавіатури 1, 2 або 3. Також ми передбачили варіант, коли користувач програми натискає будь-яку іншу клавішу: в цьому випадку на екрані з’явиться повідомлення про помилку. Також, після проведення сортування за вибраним алгоритмом, користувач зможе продовжити роботу й випробувати інший алгоритм. Для цього потрібно натиснути клавіші клавіатури “у” або “д” або набрати слово “yes” чи “да” коли після завершення роботи одного з обраних алгоритмів сортування на екрані з’явиться запитання “Хотите ли вы продолжить работу с данной программой?”. Якщо ж користувач уже випробував усі алгоритми або за браком часу (або бажання) хоче завершити роботу з програмою, то йому достатньо буде лише натиснути на клавіатурі клавіші “n” або “н” чи набрати слова “no” або “нет” після того, як на екрані з’явиться зазначене вище запитання.

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

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

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

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

Var i,j:byte;

begin

if hi> low then