QuickSort (A, scanDown 1,
high);
)
Обчислювальна складність «швидкої» сортування
Загальний аналіз ефективності «швидкої» сортування
досить важкий. Буде краще показати її обчислювальну складність, підрахувавши
число порівнянь при деяких ідеальних припущеннях. Припустимо, що n - ступінь
двійки, n = 2k (k = log2n), а центральний елемент розташовується точно
посередині кожного списку і розбиває його на два підсписки приблизно однаковою
довжини.
При першому скануванні проводиться n-1 порівнянь. У
результаті створюються два підсписки розміром n/2. На наступній фазі обробка
кожного підсписки вимагає приблизно n/2 порівнянь. Загальне число порівнянь на цій
фазі дорівнює 2 (n/2) = n. На наступній фазі обробляються чотири підсписки, що
вимагає 4 (n/4) порівнянь, і т.д. Врешті-решт процес розбиття припиняється
після k проходів, коли вийшли підсписки містять по одному елементу.
Загальне число порівнянь приблизно дорівнює
n +
2 (n/2) + 4 (n/4) + ... + N (n/n) = n + n + ... + N = n * k = n * log2n
Для списку загального вигляду обчислювальна складність
«Швидкої» сортування дорівнює O (n log2 n). Ідеальний випадок, який ми тільки що
розглянули, фактично виникає тоді, коли масив вже відсортований за
зростанням. Тоді центральний елемент потрапляє точно в середину кожного
підсписки.
Якщо масив відсортований за спаданням, то на перший
проході центральний елемент виявляється на середині списку і змінюється
місцями з кожним елементом як у першому, так і в другому підсписки.
Результуючий список майже відсортований, алгоритм має складність порядку O (n
log2n).
Рис.6
Найгіршим сценарієм для «швидкої» сортування буде
той, при якому центральний елемент весь час потрапляє в одноелементні
подспісок, а всі інші елементи залишаються в другому підсписки. Це відбувається
тоді, коли центральним завжди є найменший елемент. Розглянемо
послідовність 3, 8, 1, 5, 9.
На першому проході проводиться n порівнянь, а більший
подспісок містить n-1 елементів. На наступному проході цей подспісок вимагає
n-1 порівнянь і дає подспісок з n-2 елементів і т.д. Загальне число порівнянь
одно:
n + n-1 + n-2 + ... + 2 = n (n +1)/2 - 1
Складність найгіршого випадку дорівнює O (n2), тобто не краще,
ніж для сортувань вставками і вибором. Проте цей випадок є
патологічним і малоймовірний на практиці. Загалом, середня продуктивність
«Швидкої» сортування вище, ніж у всіх розглянутих нами сортувань.
Алгоритм QuickSort вибирається за основу в більшості
універсальних сортують утиліт. Якщо ви не можете змиритися з
продуктивністю найгіршого випадку, використовуйте пірамідальну сортування --
більш стійкий алгоритм, складність якого дорівнює O (n log2n) і залежить тільки
від розміру списку.
Порівняння алгоритмів сортування масивів
Ми порівняли алгоритми сортування, випробувавши їх на
масивах, що містять 4000, 8000, 10000, 15000 і 20000 цілих чисел,
відповідно. Час виконання виміряна в тіках (1/60 частка секунди). Серед
всіхалгоритмів порядку O (n2) час сортування вставками відображає той факт, що
на i-му проході потрібно лише i/2 порівнянь. Цей алгоритм явно перевершує
всі інші сортування порядку O (n2). Зауважте, що найгіршу загальну
продуктивність демонструє сортування методом бульбашки. Результати
випробувань показані в таблиці 1 і на малюнку 7.
Для ілюстрації ефективності алгоритмів сортування в
екстремальних випадках використовуються масиви з 20000 елементів, впорядкованих
по зростанню і за спаданням. При сортування методом бульбашки і сортування
вставками виконується тільки один прохід масиву, впорядкованого за
зростанням, у той час як сортування за допомогою вибору залежить тільки від
розміру списку і виробляє 19999 проходів. Упорядкованість даних за спаданням
є найгіршим випадком для бульбашкової, обмінної та сортування вставками,
зате сортування вибором виконується, як звичайно.
n
Обмінна сортування
Сортування вибором
Бульбашкова сортування
Сортування вставками
4 000
12.23
17.30
15.78
5.67
8 000
49.95
29.43
64.03
23.15
10 000
77.47
46.02
99.10
35.43
15 000
173.97
103.00
223.28
80.23
20 000
313.33
185.05
399.47
143.67
Рис.7 Порівняння сортувань порядку O (n2)
n
Обмінна сортування
Сортування вибором
Бульбашкова сортування
Сортування вставками
8 000 (впорядкований по
зростанням)
185.27
185.78
0.03
0.05
8 000 (впорядкований по
спаданню)
526.17
199.00
584.67
286.92
У загальному випадку QuickSort є найшвидшим алгоритмом.
Завдяки своїй ефективності, що дорівнює O (n log2n), він явно перевершує будь-який
алгоритм порядку O (n2). Судячи з результатів випробувань, наведених в наступній
таблиці, він також швидше будь-який з сортувань порядку O (n log2n), розглянутих
нами в попередньому номері. Зверніть увагу, що ефективність «швидкої»
сортування становить O (n log2n) навіть в екстремальних випадках. Зате сортування
за допомогою пошукового дерева стає в цих випадках O (n2) складною, тому що
сформоване дерево є виродженим.
n
Турнірна сортування
Сортування за допомогою
дерева
Пірамідальна сортування
"Швидка"
сортування
4 000
0.28
0.32
0.13
0.07
8 000
0.63
0.68
0.28
0.17
10 000
0.90
0.92
0.35
0.22
15 000
1.30
1.40
0.58
0.33
20 000
1.95
1.88
0.77
0.47
8 000 (впорядкований по
зростанням)
1.77
262.27
0.75
0.23
8 000 (впорядкований по
спаданню)
1.65
275.70
0.80
0.28
Рис.8 Порівняння сортувань порядку O (n log2n)
Порівняння сортувань
Ця програма здійснює порівняння алгоритмів
сортування даних, представлених на рисунках 7 і 8. Тут ми наводимо тільки
базову структуру програми. Хронометраж проводиться за допомогою функції
TickCount, що повертає число 1/60 часток секунди, що минули з моменту старту
програми.
# include
# include "arrsort.h"
// Перечіслімий тип,
що описує початковий стан масиву даних.
enum Ordering (randomorder, ascending, descending);
// Перечіслімий тип,
ідентифікує алгоритм сортування.
enum SortType
(
SortTypeBegin,
exchange = SortTypeBegin,
selection,
bubble,
insertion,
tournament,
tree,
heap,
quick,
SortTypeEnd = quick
);
// копіювати n-елементний масив y в масив x
void Copy (int * x, int * y, int n)
(
for (int i = 0; i
* x + + = * y ++;
)
// Загальна сортуються
функція, яка приймає вихідний масив
// із заданою
упорядкованістю елементів і застосовує вказаний
// алгоритм сортування.
void Sort (int a [], int n, SortType type, Ordering order)
(
long time;
cout << "Сортування" <
// Вивести тип впорядкованості.
switch (order)
(
case random:
cout << "елементів.";
break;
case ascending:
cout << "елементів,
упорядкованих за зростанням. ";
break;
case descending:
cout << "елементів,
упорядкованих за спаданням. ";
break;
)
// засікти час
time = TickCount ();
// Виконати сортування і вивести її тип ...
switch (type)
(
case exchange:
ExchangeSort (a, n);
cout << "Сортування обміном:";
break;
case selection:
SelectionSort (a, n);
cout << "Сортування вибором:";
break;
case bubble:. . . . . . .
case insertion:. . . . . . .
case tournament:. . . . . . .
case tree:. . . . . . .
case heap:. . . . . . .
case quick:. . . . . . .
)
// Підрахувати час виконання у секундах.
time = TickCount () - time;
cout <
)
// Виконує сортування
масиву з n елементами,
// розташованих в порядку,
що визначається параметром order.
void RunTest (int n, Ordering order)
(
int i;
int * a, * b;
SortType stype;
RandomNumber rnd;
// Виділити пам'ять для двох n-елементних
масивів a і b.
a = new int [n];
b = new int [n];
// Визначити тип впорядкованості даних.
if (order == randomorder)
(
// Заповнити масив b випадковими числами.
for (i = 0; i
b [i] = rnd.Random (n);
)
else
(
// Дані, відсортовані за
зростанням.
for (i = 0; i
b [i] = i;
)
else
(
// дані, відсортовані за спаданням.
for (i = 0; i
b [i] = n - 1 - i;
)
else
(
// Копіювати дані в масив a.
По черзі виконати сортування для
// кожного типу.
for (stype = SortTypeBegin;
stype <= SortTypeEnd; stype = SortType (stype +1))
(
Copy (a, b, n);
Sort (a, n, stype, order);
)
)
// Видалити обидва динамічних масиву.
delete [] a;
delete [] b;
)
// Відсортувати 4 000 -, 8
000 -, 10 000 -, 15 000 - і 20 000-елементний масиви,
// заповнені випадковими
числами.
// Потім спочатку
відсортувати 20 000-елементний масив, упорядкований
// за зростанням, а потім
за спаданням.
void main (void)
(
int nelts [5] = (4000, 8000,
10000, 15000, 20000);
int = i;
cout.precision (3);
cout.setf (ios:: fixed |
ios:: showpoint);
for (i = 0; i <5; i ++)
RunTest (nelts [i],
randomorder);
RunTest (20000, ascending);
RunTest (20000, descending);
Список літератури
Для підготовки даної роботи були використані
матеріали з сайту http://www.rsdn.ru/
