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

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

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

Факультет інформаційних технологій та комп'ютерної інженерії

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

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

Виконав студент групи 2КН-19Б:

Любчич Н.О.

Перевірив:

Арсенюк І.Р

Вінниця-2019

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

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

Хід роботи:

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

Ідея:

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

Схема алгоритму:[pic 1]

for j = 2 to A.length do 

    key = A[j]

    i = j-1

    while (i > 0 and A[i] > key) do 

        A[i + 1] = A[i]

        i = i - 1

    end while

    A[i+1] = key

end for

Аналіз алгоритму:

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

Для кожної інструкції алгоритму введемо тимчасову вартість і кількість повторень, де
tj - кількість перевірок умови у внутрішньому циклі while.

Час роботи алгоритму сортування вставками - це сума часів роботи кожного кроку.[pic 2]

Найкращим випадком є ​​вже попередньо відсортований масив. Тоді всі внутрішні цикли складаються всього з однієї ітерації, тобто tj = 1 для всіх  j. Тоді час роботи алгоритму складе:

[pic 3]

Найгіршим випадком є ​​масив, відсортований в порядку, зворотному до потрібного. При цьому кожен новий елемент порівнюється з усіма в відсортованій послідовності. Це означає, що всі внутрішні цикли складаються з j ітерацій, тобто tj = j для всіх  j. Тоді час роботи алгоритму складе:[pic 4]