Сортування включеннями

Сортування включеннями

2 Аналіз алгоритмів сортування

Література

Глибовець М. М. Основи комп’ютерних алгоритмів. – К.: Видавничий дім „КМ Академія”, 2003. с 83-96.

Припустимо, що на певному етапі роботи алгоритму ліва частина масиву з 1-го по (i-1)-й елемент включно є відсортованою, а права частина з i-го по n-й елемент залишається такою, якою вона була в первісному, невідсортованому масиві. Черговий крок алгоритму полягає в розширенні лівої частини на один елемент і, відповідно, скорочення правої частини. Для цього береться перший елемент правої частини (з індексом i) і вставляється на відповідне йому місце в ліву частину так, щоб впорядкованість лівої частини збереглася.

Процес починається з лівої частини, що складається з одного елемента А[1], а закінчується, коли права частина стає порожньою.

2 Аналіз алгоритмів сортування

Оцінимо складність алгоритму сортування простим включенням. Очевидно, що часова складність залежить як від розміру сортованого масиву, так і від його вихідного стану в сенсі упорядкованості елементів. Часова складність буде мінімальною, якщо вихідний масив вже відсортований в потрібному порядку значень ключа (в даному випадку - за зростанням). Максимальне значення складності буде відповідати протилежної впорядкованості вихідного масиву, тобто впорядкованості вихідного масиву за спаданням значень ключа. Зазвичай для алгоритмів сортування часова складність оцінюється кількістю пересилань елементів.

Оцінимо величину мінімальної часової складності алгоритму. Якщо масив вже відсортований, то тіло циклу while не буде виконуватися жодного разу. Виконання процедури зведеться до роботи наступного циклу:

Оскільки тіло циклу for виконується n-1 раз, то число пересилань елементів масиву

М_min = 2*(n – 1),

а число порівнянь ключів дорівнює

С_min = n – 1.

Складність алгоритму буде максимальною, якщо вихідний масив впорядкований за спаданням. Тоді кожен елемент А[i] буде «проганятися» до початку масиву, тобто встановлюватися в першу позицію. Цикл while виконається 1 раз при i=2, 2 рази при i=3 і т. д., n-1 раз при i=n. Таким чином, загальне число пересилань записів дорівнює:

Більш підходящою для реальної ситуації є середня оцінка складності. Для її обчислення треба припустити, що всі елементи вихідного масиву – випадкові числа та їх значення ніяк не пов'язані з їх номерами. У такому разі результат чергової перевірки умови x.key <A [j].key в циклі While також є випадковим.

Розумно припустити, що середня кількість виконань циклу While для кожного конкретного значення i дорівнює i/2, тобто в середньому кожен раз доводиться переглядати половину послідовності до тих пір, поки не знайдеться підходяще місце для чергового елемента.

Тоді формула для середнього числа пересилань (середня оцінка складності) буде наступною:

Як максимальна, так і середня оцінка складності алгоритму квадратична (є поліномом другого ступеня) за параметром n – розміром сортованого масиву.

Контрольні завдання

1. Опишіть словесний алгоритм сортування методом простого включення.

2. Складіть схему алгоритму сортування методом простого включення.

3. Проаналізуйте алгоритм сортування методом простого включення для мінімальної, максимальної та середньої часової складності.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Питання	\|	ЕНЕРГЕТИЧНІ ХАРАКТЕРИСТИКИ МЕХАНІЧНИХ ПЕРЕТВОРЮВАЧІВ В СТАТИЧНИХ РЕЖИМАХ

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.029 сек.