В даній статті ми розглянемо алгоритм швидкого сортування. Цей алгоритм, Ніклаус Вірт, у своїй книзі "Алгоритми і структури даних", назвав найшвидшим з відомих алгоритмів сортування масивів. І він дещо відрізняється від описаних раніше алгоритмів сортування (бульбашковий, вставками і вибором).
Розглянемо масив Array, який необхідно відсортувати. Для даного алгоритму, нам знадобляться наші звичайні ітератори iter і jter, N - кількість елементів масиву, L і R - ліва і права межі сортування відповідно, і дві змінні для зберігання значень масиву - x і w. Реалізація даного алгоритму на C++ виглядає наступним чином:
/* Функція швидкого сортування */
void QuickSort (int Array[], /* масив для сортування */
unsigned int N, /* розмір масиву */
int L, /* ліва межа сортування */
int R) /* права межа сортування */
{
int iter = L ,
jter = R ;
int middle = (R+L)/2 ;
int x = Array [middle] ;
int w ;
do
{
while (Array[iter]<x)
{ iter ++ ; }
while (x<Array[jter])
{ jter -- ; }
if (iter<=jter)
{
w = Array [iter];
Array [iter] = Array [jter] ;
Array [jter] = w ;
iter ++ ;
jter -- ;
}
}
while (iter<jter) ;
if (L<jter)
{ QuickSort (Array, N, L, jter) ; }
if (iter<R)
{ QuickSort (Array, N, iter, R) ; }
}
Проста програма, яка використовує дану реалізацію алгоритму, виглядає наступним чином:
#include <iostream>
using namespace std ;
/* Функція швидкого сортування */
void QuickSort (int Array[], /* масив для сортування */
unsigned int N, /* розмір масиву */
int L, /* ліва межа сортування */
int R) /* права межа сортування */
{
int iter = L ,
jter = R ;
int middle = (R+L)/2 ;
int x = Array [middle] ;
int w ;
do
{
while (Array[iter]<x)
{ iter ++ ; }
while (x<Array[jter])
{ jter -- ; }
if (iter<=jter)
{
w = Array [iter];
Array [iter] = Array [jter] ;
Array [jter] = w ;
iter ++ ;
jter -- ;
}
}
while (iter<jter) ;
if (L<jter)
{ QuickSort (Array, N, L, jter) ; }
if (iter<R)
{ QuickSort (Array, N, iter, R) ; }
}
int main (int argc, char** argv) /* головна функція програрми */
{
/* масив даних */
int Array [] = {11, 5, 7, 8, 3, 4, 2, 9, 0, 1, 6, 10, 13, 12} ;
int N = sizeof (Array) / sizeof (Array[0]) ; /* дізнаємося довжину масиву */
int iter ; /* бігунки-ітератори для перебору масиву */
/* виводимо масив на екран для наглядності */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
QuickSort (Array, N, 0, N-1) ;
/* виводимо масив на екран для наглядності */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
return 0 ; /* Вихід з програми */
}
Після виконання її на комп'ютері ви отримаєте наступне:
Даний алгоритм, хоча і являється, як сказав Ніклаус, найшвидшим з відомих, однак не є легким для аналізу і розуміння, на відміну від простіших алгоритмів на подобі алгоритму простих вставок або алгоритму вибору - його буде важче реалізувати по пам'яті ніж інші. Окрім того, що у нас є два цикла з оператором вибору всередині іншого циклу, так ще й функція рекурсивно сама себе викликає.
Отже при першому виклику функції QuickSort, ітератори iter і jter ініціалізовуються у значення лівої і правої меж відповідно, тобто рівні індексам початку і кінця масиву. Далі ми обераємо середній з усіх елементів масиву, який ми і будемо порівнювати з усіма іншими елементами. При входженні у зовнішній цикл, ми одночасно входимо і в перший внутрішній цикл, який зупиняється при найпершому більшому елементі від обраного серединного (лінійний пошук з інваріантою). Після виходу з даного циклу, ітератор iter, буде містити в собі індекс найпершого більшого елементу від серединного починаючи зліва. Далі ми входимо у другий внутрішній цикл (також лінійний пошук з інваріантою), який шукає більший елемент від серединного починаючи з правої межі, і після закінчення виконання циклу в ітераторі jter буде міститись індекс даного елементу. Далі ми натрапляємо на оператор вибору, який перевіряє чи значення ітератора iter менше від значення ітератора jter. Основна ціль виконання перевірки даної умови полягає у тому, щоб перевірити, чи вони не розминулися. Якщо вони все таки розминулись - не виконується обмін значеннями і ітерації зовнішнього циклу зупиняються. Після чого функція може сама себе викликати, якщо сортування ще не закінчено. Сортування закінчується, якщо ліва межа (тобто L) більша за значення ітератора jter і права межа менша за ітератор iter.
Тобто алгоритм просто ділить масив на половину, і перекидає усі менші елементи вліво від центрального, а усі більші - вправо. І це відбувається доти, доки межі не зіллються.
Щоб отримати масив в порядку спадання, необхідно замінити оператори порівняння на протилежні в умовах двох внутрішніх циклів:
#include <iostream>
using namespace std ;
/* Функція швидкого сортування */
void QuickSort (int Array[], /* масив для сортування */
unsigned int N, /* розмір масиву */
int L, /* ліва межа сортування */
int R) /* права межа сортування */
{
int iter = L ,
jter = R ;
int middle = (R+L)/2 ;
int x = Array [middle] ;
int w ;
do
{
while (Array[iter]>x)
{ iter ++ ; }
while (x>Array[jter])
{ jter -- ; }
if (iter<=jter)
{
w = Array [iter];
Array [iter] = Array [jter] ;
Array [jter] = w ;
iter ++ ;
jter -- ;
}
}
while (iter<jter) ;
if (L<jter)
{ QuickSort (Array, N, L, jter) ; }
if (iter<R)
{ QuickSort (Array, N, iter, R) ; }
}
int main (int argc, char** argv) /* головна функція програми */
{
/* масив даних */
int Array [] = {11, 5, 7, 8, 3, 4, 2, 9, 0, 1, 6, 10, 13, 12} ;
int N = sizeof (Array) / sizeof (Array[0]) ; /* дізнаємося довжину масиву */
int iter ; /* бігунки-ітератори для перебору масиву */
/* виводимо масив на екран для наглядності */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
QuickSort (Array, N, 0, N-1) ;
/* виводимо масив на екран для наглядності */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
return 0 ; /* Вихід з програми */
}
Результат виконання:
