Перелік рекомендованих джерел. 1. Brian W. KernighanandDennis M

1. Brian W. KernighanandDennis M. Ritchie «The C ProgrammingLanguage» (SecondEdition). — 1988. [ISBN 0–13–110362–8]

2. Donald E. Knuth «TheArtofComputerProgramming»: «Volume 3: SortingandSearching» (SecondEdition). — 1998. [ISBN 0–201–89685–0]

Лабораторна робота № 5

Лабораторна робота № 5

Тема роботи: Метод швидкого сортування.

Мета роботи: Вивчити алгоритм швидкого сортування. Здійснити програмну реалізацію алгоритму швидкого сортування. Дослідити швидкодію алгоритму швидкого сортування.

Короткі теоретичні відомості

Швидке сортування (англійською «QuickSort») — алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Хоаром, який не потребує додаткової пам’яті і виконує у середньому O (n ∙log(n)) операцій, однак, у найгіршому випадку робить O (n ²) порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності.

В основі алгоритму лежить принцип «розділяй та володарюй» (англійською «DivideandConquer»). Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин вудбуваєтьсярекурсивно. Алгоритм швидкого сортування може бути реалізований як на масиві, так і на двобічнму списку.

Швидке сортування є алгоритмом на основі порівнянь, і не є стабільним.

Алгоритм швидкого сортування було розроблено Чарльзом Хоаром у 1962 році під час роботи у маленькій британській компанії ElliottBrothers.

В класичному варіанті, запропонованому Хоаром, з масиву обирався один елемент, і весь масив розбивався на дві частини по принципу: в першій частині — ті що не більші даного елементу, в другій частині — ті що не менші даного елемента.

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

· Найгірше розбиття. Найгірша поведінка має місце у тому випадку, коли процедура, що виконує розбиття, породжує одну підзадачу з (n – 1) елементом, а другу — з 0 елементами. Нехай таке незбалансоване розбиття виникає при кожному рекурсивному виклику. Для самого розбиття потрібен час Θ (n). Тоді рекурентне співвідношення для часу роботи, можна записати наступним чином: T (n) = T (n – 1) + T (0) + Θ (n) = T (n ­– 1) + Θ (n). Розв’язком такого співвідношення є: T (n) = Θ (n ²).

· Найкраще розбиття. В найкращому випадку процедура поділу ділить задачу на дві підзадачі, розмір кожної з яких не перевищує (n / 2). Час роботи, описується нерівністю: T (n) ≤ 2∙ T (n / 2) + Θ (n). Тоді: T (n) = O (n ∙log(n)) — асимптотично найкращий час.

· Середній випадок. Математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах є O (n ∙log(n)), тобто середній випадок ближчий до найкращого.

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