Швидке сортування є вдосконаленим метод сортування, заснований на принципі обміну. Бульбашкова сортування є найбільш неефективною з усіх алгоритмів прямої сортування. Однак вдосконалений алгоритм є найкращим з відомих методом сортування масивів. Він має настільки блискучими характеристиками, що його винахідник Ч. Хоар назвав його швидким сортуванням.
Для досягнення найбільшої ефективності бажано проводити обмін елементів на великих відстанях. У масиві вибирається певний елемент, званий що дозволяє. Потім він поміщається в те місце масиву, де йому належить бути після упорядкування всіх елементів. В процесі відшукання відповідного місця для дозволяє елемента виробляються перестановки елементів так, що зліва від них знаходяться елементи, менші дозволяє, і справа - великі (передбачається, що масив сортується за зростанням).
Тим самим масив розбивається на дві частини:
- НЕ відсортовані елементи зліва від дозволяє елемента;
- НЕ відсортовані елементи праворуч від дозволяє елемента.
Щоб впорядкувати ці два менших подмассіва, алгоритм рекурсивно викликає сам себе.
Якщо потрібно сортувати більше одного елемента, то потрібно
- вибрати в масиві дозволяє елемент;
- переупорядочить масив, поміщаючи елемент на його остаточне місце;
- впорядкувати рекурсивно елементи зліва від дозволяючого;
- впорядкувати рекурсивно елементи праворуч від дозволяючого.
Ключовим елементом швидкого сортування є алгоритм переупорядковування.
Розглянемо сортування на прикладі масиву:
Для реалізації алгоритму переупорядковування використовуємо покажчик left на крайній лівий елемент масиву. Покажчик рухається вправо, поки елементи, на які він показує, залишаються менше дозволяє. Покажчик right поставимо на крайній правий елемент масиву, і він рухається вліво, поки елементи, на які він показує, залишаються більше дозволяє.
Нехай крайній лівий елемент - дозволяє pivot. Встановимо покажчик left на наступний за ним елемент; right - на останній. Алгоритм повинен визначити правильне положення елемента 10 і по ходу справи поміняти місцями неправильно розташовані елементи.
Рух покажчиків зупиняється, як тільки зустрічаються елементи, порядок розташування яких щодо дозволить елемента неправильний.
Покажчик left переміщається до тих пір, поки не покаже елемент більше 10; right рухається, поки не покаже елемент менше 10.
Ці елементи міняються місцями і рух покажчиків поновлюється.
Процес триває до тих пір, поки right не опиниться зліва від left.
Тим самим буде визначено правильне місце дозволяє елемента.
Здійснюється перестановка дозволяє елемента з елементом, на який вказує right.
Дозволяє елемент знаходиться в потрібному місці: елементи зліва від нього мають менші значення; праворуч - великі. Алгоритм рекурсивно викликається для сортування подмассивов зліва від дозволяючого і праворуч від нього.
Реалізація алгоритму швидкого сортування на Сі
#include
#include
// Функція швидкого сортування
void quickSort (int * numbers, int left, int right)
int pivot; // дозволяє елемент
int l_hold = left; // ліва межа
int r_hold = right; // права межа
pivot = numbers [left];
while (left
if (left! = right) // якщо кордони не зімкнулися
numbers [left] = numbers [right]; // переміщаємо елемент [right] на місце дозволяє
left ++; // зрушуємо ліву кордон вправо
>
while ((numbers [left] <= pivot) && (left
if (left! = right) // якщо кордони не зімкнулися
<
numbers [right] = numbers [left]; // переміщаємо елемент [left] на місце [right]
right--; // зрушуємо праву межу вправо
>
>
numbers [left] = pivot; // ставимо дозволяє елемент на місце
pivot = left;
left = l_hold;
right = r_hold;
if (left
if (right> pivot)
quickSort (numbers, pivot + 1, right);
>
int main ()
int a [10];
// Заповнення масиву випадковими числами
for (int i = 0; i<10; i++)
a [i] = rand ()% 20 - 10;
// Висновок елементів масиву до сортування
for (int i = 0; i<10; i++)
printf ( ".". a [i]);
printf ( "\ n");
quickSort (a, 0, 9); // виклик функції сортування
// Висновок елементів масиву після сортування
for (int i = 0; i<10; i++)
printf ( ".". a [i]);
printf ( "\ n");
getchar ();
return 0;
>