Швидке сортування. 
Загальні характеристики роботи різних методів сортування

Опис алгоритму:

• 1. вибрати елемент, званий опорним.
• 2. порівняти всі інші елементи з опорним, на підставі порівняння розбити безліч на три — «менші опорного», «рівні» та «великі», розташувати їх у порядку менші-рівні-великі.
• 3. повторити рекурсивно для «менших» і «великих».

Примітка: на практиці звичайно поділяють сортовані безліч не на три, а на дві частини: наприклад, «менші опорного» і «рівні і великі». Такий підхід в загальному випадку виявляється ефективніше, тому що для здійснення такого поділу достатньо одного проходу по сортованому безлічі і однократного обміну лише деяких обраних елементів.

Алгоритм швидкого сортування використовує стратегію «розділяй і володарюй». Кроки алгоритму наступні:

• 1. Вибираємо в масиві деякий елемент, який будемо називати опорним елементом. З точки зору коректності алгоритму вибір опорного елемента байдужий. З точки зору підвищення ефективності алгоритму вибиратися повинна медіана, але без додаткових відомостей про сортованих даних її зазвичай неможливо отримати. Відомі стратегії: вибирати постійно один і той же елемент, наприклад, середній або останній по положенню; вибирати елемент з випадково вибраним індексом.
• 2. Операція поділу масиву: реорганізуємо масив таким чином, щоб всі елементи, менші або рівні опорному елементу, виявилися зліва від нього, а всі елементи, великі опорного — праворуч від нього. Звичайний алгоритм операції:
• 3. Два індексу — l і r, прирівнюються до мінімального і максимального індексу розділяється масиву відповідно.
• 4. Обчислюється індекс опорного елемента m.
• 5. Індекс l послідовно збільшується до тих пір, поки l-й елемент не перевищить опорний.
• 6. Індекс r послідовно зменшується до тих пір, поки r-й елемент не виявиться менше або дорівнює опорному.
• 7. Якщо r = l — знайдена середина масиву — операція поділу закінчена, обидва індекси вказують на опорний елемент.
• 8. Якщо l
• 9. Рекурсивно упорядковуємо подмассіва, що лежать ліворуч і праворуч від опорного елемента.

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

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

QuickSort є істотно поліпшеним варіантом алгоритму сортування за допомогою прямого обміну (його варіанти відомі як «Бульбашкова сортування» та «Шейкерная сортування»), відомого, зокрема, своєї низькою ефективністю. Принципова відмінність полягає в тому, що після кожного проходу елементи діляться на дві незалежні групи. Цікавий факт: поліпшення самого неефективного прямого методу сортування дало в результаті ефективний покращений метод.

Кращий випадок. Для цього алгоритму найкращий випадок — якщо в кожній ітерації кожен з підмасивів ділився б на два рівних по величині масиву. В результаті кількість порівнянь, які робить швидкої сортуванням, було б дорівнює значенню рекурсивного вираження CN = 2CN / 2 + N, що в явному вираженні дає приблизно N lg N порівнянь. Це дало б найменший час сортування.

Середнє. Дає в середньому O (n log n) обмінів при упорядкуванні n елементів. В реальності саме така ситуація зазвичай має місце при випадковому порядку елементів і виборі опорного елемента з середини масиву або випадково.

На практиці (у випадку, коли обміни є більш витратною операцією, ніж порівняння) швидке сортування значно швидше, ніж інші алгоритми з оцінкою O (n lg n), через те, що внутрішній цикл алгоритму може бути ефективно реалізований майже на будь-архітектурі. 2CN / 2 покриває витрати по сортуванню двох отриманих підмасива; N — це вартість обробки кожного елемента, використовуючи один або інший вказівник. Відомо також, що приблизне значення цього виразу одно CN = N lg N.

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

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