Закінчуючи огляд методів сортування, порівняємо їх ефективність. В таблиці 5.3 подано дані (у секундах) для упорядкування довільного, упорядкованого й упорядкованого в зворотному порядку масивів з n=2000.
Таблиця 5.3
Порівняння методів сортувань
| Метод сортування | Масив | ||
| Упорядко-ваний | Довiльний | В зворотному порядку | |
| Сортування вставками з бар¢єром Сортування методом двiйкових вставок Обмiнне сортування простою вибiркою Бульбашкове сортування класичне Шейкер-сортування Сортування Шелла Пiрамiдальне сортування Сортування Хоара (швидке) – рекурсивне Сортування Хоара нерекурсивне Сортування прямим злиттям | 0.22 1.16 58.18 80.18 0.16 0.80 2.32 0.72 0.72 1.98 | 50.74 37.66 58.34 128.84 104.44 7.08 2.22 1.22 1.32 2.06 | 103.80 76.06 73.46 178.66 187.36 12.34 2.12 0.76 0.80 1.98 |
Видно, що бульбашкове сортування найгірше з усіх порівнюваних, сортування Хоара – найкраще.
В таблиці 5.4 наведено результати тестування алгоритмів сортування порядку O(n2) за часом в залежності від розміру масивів (n= 4000, 8000, 10000, 15000 і 20000). Час виконання вимірюваний у секундах. Серед всіх алгоритмів порядку O(n2) час сортування вставками відбиває той факт, що на і-му проході потрібно лише і/2 порівнянь. Цей алгоритм явно перевищує всі інші сортування порядку O(n2). Зверніть увагу, що саму гіршу загальну продуктивність демонструє сортування методом бульбашки.
Таблиця 5.4
| Сортування вибором | Бульбашкове сортування з признаком | Сортування вставками | |
| n = 4 000 | 17.30 | 15.78 | 5.67 |
| n = 8 000 | 29.43 | 64.03 | 23.15 |
| n = 10 000 | 46.02 | 99.10 | 35.43 |
| n = 15 000 | 103.00 | 223.28 | 80.23 |
| n = 20 000 | 185.05 | 399.47 | 143.67 |
Порівняння алгоритмів сортувань порядку O(n2)
В таблиці 5.5 наведено результати тестування алгоритмів сортування порядку O(n2) в екстремальних умовах, коли в якості вхідних даних використовувалися масиви, що вже були відсортовані за зростанням і за спаданням. При сортуванні методом бульбашки і сортуванні вставками виконується тільки один прохід масиву, упорядкованого за зростанням, у той час як сортування за допомогою вибору залежить тільки від розміру набору даних. Упорядкованість даних за спаданням є найгіршим випадком для бульбашкового, обмінного сортування і сортування вставками, проте сортування вибором виконується, як звичайно.
Таблиця 5.5
Сортування упорядкованих масивів алгоритмами складності O(n2)
| Упорядкова-ність масиву | Обмінне сортування | Сортування вибором | Бульбашкове сортування | Сортування вставками |
| n = 8000 (за зростанням ) | 185.27 | 185.78 | 0.03 | 0.05 |
| n = 8000 (за спаданням ) | 526.17 | 199.00 | 584.67 | 286.92 |
У загальному випадку сортування Хоара є найбільш швидким алгоритмом. Завдяки своїй ефективності, рівній O(n*log(n)), він явно перевищує будь-який алгоритм порядку O(n2). Судячи з результатів тестувань, наведених у таблиці 5.6, він також швидше кожного із сортувань порядку O(n*log(n)). Зверніть увагу, що ефективність "швидкого сортування" (сортування Хоара) складає O(n log(n)) навіть в екстремальних випадках. Проте сортування за допомогою пошукового дерева стає в цих випадках O(n2) складним, тому що формоване дерево є виродженим.
Таблиця 5.6
Результати тестування алгоритмів сортування порядку O(n log(n))
| Масив | Турнірне сортування | Сортування за допомогою дерева | Пірамідальне сортування | Сортування Хоара |
| n = 4 000 | 0.28 | 0.32 | 0.13 | 0.07 |
| n = 8 000 | 0.63 | 0.68 | 0.28 | 0.17 |
| n = 10000 | 0.90 | 0.92 | 0.35 | 0.22 |
| n = 15000 | 1.30 | 1.40 | 0.58 | 0.33 |
| n = 20000 | 1.95 | 1.88 | 0.77 | 0.47 |
| n = 8000 (упорядкований за зростанням ) | 1.77 | 262.27 | 0.75 | 0.23 |
| n = 8 000 (упорядкований за убуванням ) | 1.65 | 275.70 | 0.80 | 0.28 |
Останнє зауваження. При аналізі алгоритмів сортувань говорять про кількість порівнянь (вона визначає порядок алгоритму) і кількість перестановок. Для машин з конвеєрним виконанням команд значення має в основному кількість порівнянь, тому що порівняння пов'язане з припиненням "конвеєра" процесора до ухвалення рішення за результатами команди порівняння. Перестановки цей процес не порушують і тому виконуються швидко. Для повільних машин кількість перестановок істотно впливає на час сортування.