рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Порівняння алгоритмів сортування масивів

Реферат Курсовая Конспект

Выберите учебное заведение

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

Порівняння алгоритмів сортування масивів - раздел Образование, ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ Закінчуючи Огляд Методів Сортування, Порівняємо Їх Ефективність. В Таблиці 5....

Закінчуючи огляд методів сортування, порівняємо їх ефективність. В таблиці 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

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

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ

ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ... НАД СТАТИЧНИМИ І СТРУКТУРАМИ R...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Порівняння алгоритмів сортування масивів

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Послідовний або лінійний пошук
Найпростішим методом пошуку елемента, що знаходиться в неупорядкованому наборі даних, за значенням його ключа є послідовний перегляд кожного елемента набору, що продовжується доти,

Пошук у таблиці
Пошук у масиві іноді називають пошуком у таблиці, якщо ключ сам є інтегрованим об'єктом, таким як масив чисел чи символів. Часто зустрічається саме останній випадок, коли масиви сим

Прямий пошук рядка в тексті
Часто доводиться зіштовхуватися зі специфічним пошуком, так названим пошуком рядка в тексті. Його можна визначити таким способом. Нехай заданий масив s з

КМП-алгоритм пошуку рядка в тексті
У 1970 р. Д. Кнут, Дж. Морріс і В. Пратт запропонували алгоритм пошуку рядка в тексті, так званий КМП-алгоритм або КМП-пошук, фактично потребуючий тільки N порівнян

БМ-алгоритм пошуку рядка в тексті
Схема КМП-пошуку дає справжній виграш тільки тоді, коли при порівнянні символів до розбіжності було деяке число збігів (>1). Лише в цьому випадку образ зміщується більш ніж на одиницю. На жаль,

Таблиці прямого доступу
Найпростішою організацією таблиці, що забезпечує ідеально швидкий пошук, є таблиця прямого доступу. У такій таблиці ключ є адресою запису в таблиці або може бути перетворений на адр

Таблиці з довідниками
Одним із способів усунення недоліку, властивого таблицям прямого доступу, який полягає в тому, що вони вимагають пам'ять значних розмірів, є метод довідників. Основна табли

Хешовані таблиці та функції хешування
Як відзначалося вище, у кожній реальній таблиці фактична множина ключів є лише невеликою підмножиною множини всіх теоретично можливих ключів. З міркувань економії пам'яті доцільно призначати роз

Проблема колізій у хешованих таблицях
Колізії (друга назва - конфлікт) – основна проблема для хешованих таблиць. Вдало підібрана функція хешування може мінімізувати число колізій, але не може гарантувати їхньої повної в

Сортування
Для самого загального випадку задача сортування може формулюватися так: мається деяка неупорядкована вхідна множина ключів, необхідно одержати вихідну множину тих же ключів, упорядк

Сортування вибіркою
Сортування простою вибіркою. Даний метод реалізує практично "дослівно" сформульовану вище стратегію вибірки. Порядок алгоритму простої вибірки – O(N2

Сортування включенням
Сортування простими вставками. Цей метод – "дослівна" реалізація стратегії включення. У програмному прикладі 5.19 наведена підпрограма сортування простими вставками.

Сортування розподілом
Порозрядне цифрове сортування. Алгоритм вимагає представлення ключів сортованої послідовності у вигляді чисел у деякій системі обчислення P. Число

Сортування злиттям
Алгоритми сортувань злиттям, як правило, мають порядок O(N*log(N)), але відрізняються від інших алгоритмів більшою складністю і вимагають великого числа пересилань. Алгоритми злиття