Аналіз та дослідження алгоритму сортування методом вставок
Автор: optimist_2001 • Февраль 15, 2019 • Лабораторная работа • 1,002 Слов (5 Страниц) • 701 Просмотры
Міністерство освіти та науки України
Вінницький національний технічний університет
Кафедра Комп’ютерних Наук
Лабораторна робота № 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. Оскільки
...