Алгоритм швидкого сортування

Зараз ми розглянемо оптимальний за часом роботи алгоритм, який називається алгоритмом швидкого сортування. Цей алгоритм був розроблений Ентоні Хоаром в 1960 році. Покажемо, як він реалізується через рекурсивну процедуру.

В алгоритмі швидкого сортування використовуються три ідеї:

1) поділ сортованого масиву на дві частини: ліву і праву;

2) взаємне упорядкування двох частин (подмассивов) так, щоб всі значення елементів лівій частині не перевищували значень елементів правій частині;

3) рекурсія, при якій подмассів упорядковується точно таким же способом, як і весь масив.

Для початкового поділу масиву на дві частини потрібно вибрати деякий “бар’єрне” значення. Це значення має задовольняти єдиному умові: лежати в діапазоні значень для даного масиву (т. Е. Між мінімальною і максимальною величинами). У якості “бар’єру” можна вибрати значення будь-якого елемента масиву, наприклад першого або останнього, або перебуває в середині.

Далі потрібно зробити так, щоб в лівому подмассіви опинилися всі елементи зі значеннями, меншими або рівними бар’єра, а в правому – великими або рівними. Для цього, переглядаючи масив зліва направо, потрібно знайти позицію першого елемента зі значенням, більшим або рівним бар’єра, а переглядаючи справа наліво, знайти перший елемент зі значенням, меншим або рівним бар’єра. Поміняти місцями ці значення. Потім продовжити зустрічний рух до наступної пари елементів, призначених для обміну. Так продовжувати до тих пір, поки індекс лівого перегляду не стане більше індексу правого перегляду. Ці індекси будуть роздільниками двох взаємно впорядкованих під-масивів. Далі алгоритм рекурсивно застосовується до кожного з подмассивов (лівому і правому). У кінцевому рахунку приходимо до сукупності з п взаємно впорядкованих одноелементних масивів, які ділити далі неможливо. Ця сукупність утворює один повністю впорядкований масив. Сортування завершена!


1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Алгоритм швидкого сортування