Аналіз та дослідження алгоритму сортування методом вставок

Міністерство освіти та науки України

Вінницький національний технічний університет

Кафедра Комп’ютерних Наук

Лабораторна робота № 1

з дисципліни “Теорія алгоритмів”

Тема: “Аналіз та дослідження алгоритму

сортування методом вставок”

Виконав:

студент групи 1КН-18б

Сотула Д.Ю.

Перевірив викладач:

Арсенюк І.Р.

Вінниця-2018

Тема: “Аналіз та дослідження алгоритму сортування методом вставок”.

Мета: Проаналізувати та дослідити алгоритм сортування методом вставок.

Сортування вставками – простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям.

Сортування вставками зручне для сортування коротких послідовностей. Ідея процедури сортування вставками полягає в тому, що масив для сортування розбивається на 2 частини: ліву та праву. На початку частина , що розташована зліва містить лише один елемент, і отже є відсортованою; частина, що розташована справа містить усі інші, невідсортовані елементи. На кожному кроці з неї обирається наступний елемент і розташовується на потрібне місце у вже відсортованій послідовності. Коли останній елемент масиву займе відповідне місце сортування завершується.

Алгоритм сортування, що реалізує дану ідею наведений на рисунку 3.1.

[pic 1]

Індекс j вказує черговий елемент. Ділянку A[i ... j- 1] складають вже від-сортовані елементи, а А[j+1 … n] – ще не переглянуті. У зовнішньому циклі алгоритму (блок 1) індекс j пробігає масив зліва направо . Ми беремо елемент A[j] (блок 2) і пересуваємо елементи, що йдуть перед ним і є більшими ніж він (починаючи з (j-1) -го) справа, звільняючи місце для взятого елементу (блоки 3 – 6). У блоці 7 елемент A[j] розміщується на звільнене місце.

Таким чином, послідовність сортується „на місці”, без додаткової пам’яті, тобто крім масиву ми використовуємо лише фіксоване число елементів пам'яті. Після виконання даного алгоритму масив А впорядкований за зростанням.

[pic 2]

На рисунку 3.2 проілюстрована робота алгоритму при А=(5;2;4;6;1;3). Кружком обведено черговий елемент, що підлягає розміщенню, а стрілкою знайдене місце його розташування. Таким чином, масив з шести елементів буде відсортовано за п’ять кроків.

Для визначення складності алгоритму біля кожного блоку зліва у дужках наведена кількість разів його виконання (наприклад, блок 1 виконується n-разів, блок 2 – (n-1) разів).

Псевдокод

Отже, процедура сортування INSERTION-SORT, що відповідає нашому алгоритму, наведена на рисунку 3.3.

[pic 3]

Повернемося до нашого алгоритму і відзначимо біля кожного блоку його вартість сi (i=1, …, 7), що визначається кількістю операцій, а також число раз, яке цей блок виконується. Для кожного j від 2 до n підрахуємо, скільки разів буде виконано блок 5, і позначимо це число через tj.

Блок вартістю с, що виконується т разів, дає внесок cm у загальне число операцій. Склавши внески всіх рядків, одержимо

[pic 4]

Як ми говорили вище, час роботи алгоритму залежить не лише від n, а й від того, який, саме масив розміром n подано йому на вхід. Для нашого алгоритму найсприятливішим є випадок, коли масив вже відсортований. Тоді цикл у блоці 4 завершується після першої ж перевірки (оскільки А[i]≤key при i=j-1), тому усі tj дорівнюють 1, і загальний час

[pic 5]

Таким чином, в найсприятливішому випадку час Т(п), необхідний для сортування масиву розміром n, є лінійною функцією від n, тобто має вигляд Т(п)=an+b для деяких констант a і b. (Ці константи визначаються вибраними значеннями ci (i=1, …, 8)) Якщо ж масив відсортований у зворотному (в даному випадку, спадному) порядку – час роботи процедури буде максимальним: кожен елемент A[j] доведеться порівняти зі всіма елементами А[1], ..., A[j-1]. При цьому tj=j. Оскільки