Швидке сортування як метод програмування
У 1960 році К. А. Хоар розробив метод швидкого сортування інформації, що став найвідомішим. На сьогоднішній день він широко застосовується в програмуванні, так як має масу позитивних властивостей: може використовуватися для загальних випадків, вимагає невеликого збільшення додаткової пам`яті, сумісний з різними типами списків і зручний для реалізації. Але є і недоліки, які має швидке сортування: при використанні в роботі допускається багато помилок і вона кілька нестійка.
Однак це найбільш вивчена версія. Після появи перших розрахунків Хоара, багато зайнялися її щільним вивченням. Була створена велика база з теоретичних питань перебування витраченого на роботу часу, яку підкріпили емпіричними даними. З`явилися реальні пропозиції щодо поліпшення основного алгоритму і збільшення швидкості роботи.
Швидке сортування дуже поширена, її можна зустріти всюди. На її основі реалізований метод TList.Sort, яка є в усіх версіях (за винятком 1) Delphi, функція бібліотеки часу, витраченого на виконання, qsort в C ++.
Основний принцип роботи можна сформулювати як "розділяй і володарюй". Відбувається розбиття списку на дві групи і сортування виконується для кожної частини сама по собі. Звідси випливає, що більша увага потрібна приділяти процесу поділу, під час якого відбувається наступне: визначається базовий елемент і вже щодо нього переставляється весь список. Лівіше вибудовується група кандидатів, значення яких менше, правіше переносяться всі інші. Виходить, що основний елемент в відсортованому списку розташований на своєму законному місці. Подальший етап - це виклик рекурсивної функції сортування для обох сторін елементів щодо базового. Закінчується процес роботи тільки тоді, коли список буде містити тільки один елемент, тобто буде відсортованим. Таким чином, щоб освоїти таку функцію програмування, як швидке сортування, треба знати роботу алгоритмів нижчого рівня: а) вибір базового елемента-б) найбільш ефективна перестановка списку для отримання двох наборів з меншими і більшими значеннями.
Ознайомимося з принципами першого. При виборі базового елементу, в ідеалі повинен вибиратися середній зі списку. Тоді при розбитті він розділиться на дві рівні половини. тільки обчислити середнє значення в списку дуже складно, тому навіть найшвидша сортування обходить це обчислення стороною. Але і вибір основного елемента з максимальним або мінімальним значенням - також не найкращий варіант. У разі такого визначення один зі створених списків буде гарантовано порожній, а другий переповнений. Звідси висновок, що в якості базового елементу слід вибирати той, який знаходиться ближче до середнього, але далі від максимального і мінімального.
Після того, як з вибором визначилися, можна переходити до роботи алгоритму розбиття. Це так звані внутрішні цикли швидкого сортування. Все будується на двох бистроработающіх індексах: перший піде за елементами зліва направо, другий, навпаки, справа наліво. Починається операція виконання справа: індекс йде за списком і порівнює все значення з основним. Цикл вважається завершеним, якщо присутній елемент менший або рівний базовому. Тобто відбувається порівняння і зменшується значення індексу. З лівого боку робота закінчена при знаходженні більшого або рівного значення. І тут значення при порівнянні збільшується.
На даному етапі роботи алгоритму розбиття, який містить швидке сортування, можуть виникнути дві ситуації. Перша полягає в тому, що індекс зліва буде менше ніж справа. Це вказує на помилку, то є елементи, на які було вказано, знаходяться в списку в неправильному порядку. Вихід - зміна їх місцями. Друга ситуація, коли обидва стовпчика рівні або перетнулися. Це вказує на успішне поділ списку, тобто роботу можна вважати закінченою.
