Швидке сортування як метод програмування

У 1960 році К. А. Хоар розробив метод швидкого сортування інформації, що став найвідомішим. На сьогоднішній день він широко застосовується в програмуванні, так як має масу позитивних властивостей: може використовуватися для загальних випадків, вимагає невеликого збільшення додаткової пам`яті, сумісний з різними типами списків і зручний для реалізації. Але є й недоліки, якими володіє швидке сортування: при використанні в роботі допускається багато помилок і вона кілька нестійка.

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

Швидке сортування дуже поширена, її можна зустріти скрізь. На її основі реалізований метод TList.Sort, існуючий у всіх версіях (за винятком 1) Delphi, функція бібліотеки часу, витраченого на виконання, qsort в C ++.

Основний принцип роботи можна сформулювати як "розділяй і володарюй". Відбувається розбиття списку на дві групи і сортування виконується для кожної частини сама по собі. Звідси випливає, що більшу увагу потрібно приділяти процесу поділу, під час якого відбувається наступне: визначається базовий елемент і вже відносно нього переставляється весь список. Лівіше вибудовується група кандидатів, значення яких менше, правіше переносяться всі інші. Виходить, що основний елемент в відсортованому списку розташований на своєму законному місці. Подальший етап - це виклик рекурсивної функції сортування для обох сторін елементів відносно базового. Закінчується процес роботи тільки тоді, коли список буде містити тільки один елемент, тобто буде відсортованим. Таким чином, щоб освоїти таку функцію програмування, як швидке сортування, треба знати роботу алгоритмів нижчого рівня: а) вибір базового елемента-б) найбільш ефективна перестановка списку для отримання двох наборів з меншими і більшими значеннями.

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

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

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