Швидкі алгоритми сортування

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

Begin

Inp; Hoare(1, n); Out

End.

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

C(n) = O(n log2 n), M(n) = O(n log2 n)

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

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

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

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

12..........n-1n

J1j2...........jn-1jnу якому 2-ий рядок містить всі елементи відрізка 1..n. Підстановка B називається зворотньою до підстановки A, якщо B виходить з A сортуванням стовпчиків A у порядку зростання елементів 2-го рядка з наступною перестановкою рядків. Потрібно побудувати алгоритм обчислення зворотньої підстановки. З визначення випливає, що стовпчик [i, ji] підстановки A потрібно перетворити в стовпчик [ji , i] і поставити на ji-те місце в підстановці 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 програми, яка б виконувала сортування будь-якої послідовності елементів. Для того, щоб продемонструвати роботу різних швидких алгоритмів сортування, ми залишили вибір конкретного алгоритму на розсуд користувача програми. Тобто, ми створили основну програму – меню, яка пропонує користувачеві три можливі варіанти швидких алгоритмів сортування: швидке сортування, сортування Хоара та сортування “злиттям”. Вибір певного алгоритму здійснюється за допомогою оператору “case of”, тобто натисканням клавіш клавіатури 1, 2 або 3. Також ми передбачили варіант, коли користувач програми натискає будь-яку іншу клавішу: в цьому випадку на екрані з’явиться повідомлення про помилку. Також, після проведення сортування за вибраним алгоритмом, користувач зможе продовжити роботу й випробувати інший алгоритм. Для цього потрібно натиснути клавіші клавіатури “у” або “д” або набрати слово “yes” чи “да” коли після завершення роботи одного з обраних алгоритмів сортування на екрані з’явиться запитання “Хотите ли вы продолжить работу с данной программой?”. Якщо ж користувач уже випробував усі алгоритми або за браком часу (або бажання) хоче завершити роботу з програмою, то йому достатньо буде лише натиснути на клавіатурі клавіші “n” або “н” чи набрати слова “no” або “нет” після того, як на екрані з’явиться зазначене вище запитання.