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

Алгоритм сортування обмінами, хоча і завершує свою роботу (оскільки він використовує лише цикли з параметром і в тілі циклів параметри примусово не змінюються) і не використовує допоміжної пам’яті, але займає багато часу. Навіть, якщо внутрішній цикл не містить жодної перестановки, то дії будуть повторюватись до тих пір, поки не завершиться зовнішній цикл.

Алгоритм сортування вибором ефективніше сортування обмінами за критерієм М(n), тобто за кількістю пересилань, але також є не дуже ефективним. З цих причин було розроблено деякі нові алгоритми сортування, що отримали назву швидких алгоритмів сортування. Це такі алгоритми, як сортування деревом, пірамідальне сортування, швидке сортування Хоара та метод цифрового сортування.

Метою нашої дослідницької роботи є ознайомлення з цими швидкими алгоритмами сортування, спроба проаналізувати їх і висвітлити кожен з них і написати програму, яка б виконувала сортування деякої послідовності за допомогою різних швидких алгоритмів сортування.

1. Аналіз швидких алгоритмів сортування

1.1. Сортування деревом

Алгоритм сортування деревом ТreeSort власне кажучи є поліпшенням алгоритму сортування вибором. Процедура вибору найменшого елемента удосконалена як процедура побудови т.зв. сортуючого дерева. Сортуюче дерево - це структура даних, у якій представлений процес пошуку найменшого елемента методом попарного порівняння елементів, що стоять поруч. Алгоритм сортує масив у два етапи.

•I етап : побудова сортуючого дерева;

•II етап : просівання елементів по сортуючому дереву.Розглянемо приклад: Нехай масив A складається з 8 елементів (мал. 1, 1-а рядок). Другий рядок складається з мінімумів елементів першого рядка, які стоять поруч. Кожний наступний рядок складений з мінімумів елементів, що стоять поруч, попереднього рядка.

Ця структура даних називається сортуючим деревом. У корені сортуючого дерева розташований найменший елемент. Крім того, у дереві побудовані шляхи елементів масиву від листів до відповідного величині елемента вузла - розгалуження. (На мал.1 шлях мінімального елемента a5 - від листа a5 до кореня відзначений товстою лінією.)

Коли дерево побудоване, починається етап просівання елементів масиву по дереву. Мінімальний елемент пересилається у вихідний масив B і усі входження цього елемента в дереві заміняються на спеціальний символ M.

Потім здійснюється просівання елемента уздовж шляху, відзначеного символом M, починаючи з листка, сусіднього з M (На мал 2. униз) і до кореня. Крок просівання - це вибір найменшого з двох елементів, що зустрілися на шляху до кореня дерева і його пересилання у вузол, відзначений M. Просівання 2-го елемента показано на мал 3. (Символ М більше, ніж будь-який елемент масиву).

a6 = min(M, a6)

a6 = min(a6, a8)

a3 = min(a3, a6)

b2 := a3

Просівання елементів відбувається доти, поки весь вихідний масив не буде заповнений символами M, тобто n раз:

For I := 1 to n do begin

Відзначити шлях від кореня до листка символом M;