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

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

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


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


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

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

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

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

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