СР 6 Швидке сортування

Швидке сортування Хоара

Автор цього метода Ч. Хоар назвав його швидким сортуванням. Метод функціонує за принципом «розділяй та володарюй»: елементи масиву діляться на дві частини, і кожна з них потім сортується окремо. Для цього обирають деякий елемент x, назвемо його розділовим. Мета полягає у розташуванні всіх менших за х елементів зліва від х, а всіх більших за х елементів — справа від х. Поділивши масив, слід повторити процедуру сортування для кожної частини, потім — для частин цих частин і т. д., доки кожна з частин масиву не міститиме лише один елемент.

Отже, алгоритм методу Хоара є рекурсивним і для його реалізації зручно застосувати рекурсивну процедуру.

Швидке сортування (Хоара) є найширше вживаним і одним їх найефективніших алгоритмів.

Загальна схема алгоритму така:

  1. з масиву вибирається деякий опорний елемент а,

  2. запускається процедура розділення масиву, яка переміщає всі ключі, менші, або рівні а[i], ліворуч від нього, а всі ключі, більші, або рівні а[i] — вправо

  3. тепер масив складається з двох підмножин, причому ліва менша, або рівна правої, 

  4. для обох підмасивів: якщо в підмасиві більше двох елементів, рекурсивно запускаємо для нього ту ж процедуру.

В кінці вийде повністю відсортована послідовність.

Розглянемо алгоритм детальніше.

На вході масив а[0]…a[N] і опорний елемент p, по якому буде робитися розділення.

  1. Введемо два покажчики: i та j. На початку алгоритму вони вказують, відповідно, на лівий і правий кінець послідовності.

  2. Рухатимемо покажчик i з кроком в 1 елемент у напрямку до кінця масиву, поки не буде знайдений елемент а[i] >= р. Потім аналогічним чином почнемо рухати покажчик j від кінця масиву до початку, поки не буде знайдений a[j] <= p.

  3. Далі, якщо i <= j, міняємо а[i] і а[j] місцями і продовжуємо рухати i,j по тих же правилах…

  4. Повторюємо крок 3, поки i <= j.

Розглянемо роботу процедури для масиву а[0]…a[6] і опорного елементу p = а[3].

Тепер масив роздільний на дві частини: всі елементи лівої менше або рівні p, всі елементи правої — більше, або дорівнюють р. Розділення завершене.

Псевдокод.

quickSort ( масив a, верхня границя N ) {

Вибрати опорний елемент p — середину масиву

Розділити масив по цьому елементу

Якщо підмасив зліва від p містить більше як один елемент,

викликати quickSort для нього.

Якщо підмасив праворуч від p містить більше як один елемент

викликати quickSort для нього.

}