Главная | Обратная связь | Поможем написать вашу работу!

Порівняння алгоритмів сортування масивів

Закінчуючи огляд методів сортування, порівняємо їх ефективність. В таблиці 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(n²) за часом в залежності від розміру масивів (n= 4000, 8000, 10000, 15000 і 20000). Час виконання вимірюваний у секундах. Серед всіх алгоритмів порядку O(n²) час сортування вставками відбиває той факт, що на і-му проході потрібно лише і/2 порівнянь. Цей алгоритм явно перевищує всі інші сортування порядку O(n²). Зверніть увагу, що саму гіршу загальну продуктивність демонструє сортування методом бульбашки.

Таблиця 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(n²) в екстремальних умовах, коли в якості вхідних даних використовувалися масиви, що вже були відсортовані за зростанням і за спаданням. При сортуванні методом бульбашки і сортуванні вставками виконується тільки один прохід масиву, упорядкованого за зростанням, у той час як сортування за допомогою вибору залежить тільки від розміру набору даних. Упорядкованість даних за спаданням є найгіршим випадком для бульбашкового, обмінного сортування і сортування вставками, проте сортування вибором виконується, як звичайно.

Таблиця 5.5

Сортування упорядкованих масивів алгоритмами складності O(n²)

Упорядкова-ність масиву	Обмінне сортування	Сортування вибором	Бульбашкове сортування	Сортування вставками
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(n²). Судячи з результатів тестувань, наведених у таблиці 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

Останнє зауваження. При аналізі алгоритмів сортувань говорять про кількість порівнянь (вона визначає порядок алгоритму) і кількість перестановок. Для машин з конвеєрним виконанням команд значення має в основному кількість порівнянь, тому що порівняння пов'язане з припиненням "конвеєра" процесора до ухвалення рішення за результатами команди порівняння. Перестановки цей процес не порушують і тому виконуються швидко. Для повільних машин кількість перестановок істотно впливає на час сортування.

ВПРАВИ

1. Чим КМП - пошук відрізняється від БМ – пошуку?

2. В чому головна ідея хешування?

3. Поясніть, чому виникають колізії?

4. Поясніть, чому кількість колізій залежить від порядку ключів, що подаються?

5. Назвіть всі алгоритми сортування порядку O(n²), O(n), O(log(n)).

6. Назвіть всі алгоритми сортувань, що відносяться до групи бульбашкових. Чим характеризуються ці алгоритми?

7. Вкажіть всі можливі модифікації алгоритму сортування Шейкера. Напишіть одну з вказаних процедур Шейкер – сортування.

8. В алгоритмі сортування Шелла шаг d визначається як N dіv 2. А чи можна визначати d інакше, чому запропоновано саме такий алгоритм?

9. В чому основна ідея алгоритму сортування Хоара?

10. Чим ви поясните наявність такої кількості алгоритмів сортування?

11. Поясніть, чому алгоритми сортувань на деревах характеризуються порядком log₂(N)?

12. Назвіть відомі вам алгоритми сортувань, час виконання яких не залежить від стану впорядкованості вхідного масиву.

___________

⇐ Предыдущая 1 2 3 4 56