Міністерство освіти і науки України
Вінницький національний технічний університет
Факультет інформаційних технологій та комп’ютерної та комп’ютерної
інженерії
Кафедра Комп’ютерних Наук
Лабораторна робота № 2
з дисципліни “Теорія алгоритмів”
Виконав ст. гр. 1КН-22б Світельський А. І.
Перевірив: Денисюк В. О.
Вінниця 2023
Тема: програмування, дослідження алгоритму внутрішнього сортування
шляхом вставок.
Мета: детально проаналізувати та дослідити алгоритм сортування шляхом вставок.
Хід роботи
Code (Python)
def insertion_sort(lst):
for i in range (1, len(lst)):
j = i
while j > 0 and lst[j-1] > lst[j]:
lst[j-1], lst[j] = lst[j], lst[j-1]
j -= 1
return lst
print (insertion_sort ([15, 103, 7, 68, 1, 19, 43, 175, 19, 8]))
Output
[1, 7, 8, 15, 19, 19, 43, 68, 103, 175]
Алгоритм сортування методом вставок у графічному вигляді
Теоретична оцінка складності алгоритму для трьох випадків
Для найкращого випадку, коли масив вже відсортований, складність алгоритму методу вставки становить O(n), де n - кількість елементів у масиві. Це означає, що кожен елемент масиву порівнюється з попереднім, і оскільки вони вже відсортовані, то не відбувається жодних перестановок.
Для найгіршого випадку, коли масив відсортований в зворотному порядку, складність алгоритму становить O(n^2), де n - кількість елементів у масиві. У цьому випадку кожен новий елемент масиву потребує порівнянь з усіма попередніми елементами, щоб знайти його місце в відсортованому масиві, тому кількість порівнянь збільшується квадратично.
Для середнього випадку, коли масив містить випадкову послідовність елементів, теоретична складність алгоритму також становить O(n^2), де n - кількість елементів у масиві. Це означає, що в середньому, кожен новий елемент масиву потребує порівнянь з половиною попередніх елементів, щоб знайти його місце в відсортованому масиві.
Практична оцінка складності алгоритму
Найгірший випадок:
| Розмір масиву | Час виконання |
| 1000 | 0.03s |
| 5000 | 0.7s |
| 10000 | 2.83s |
| 15000 | 6.4s |
| 20000 | 12.13s |
| 25000 | 17.56s |
| 30000 | 26.86s |
| 40000 | 45.72s |
Найкращий випадок:
| Розмір масиву | Час виконання |
| 1000 | 0.0s |
| 10000 | 0.001s |
| 100000 | 0.008s |
| 1000000 | 0.0822s |
| 10000000 | 0.8583s |
| 100000000 | 8.4817s |
Середній випадок:
| Розмір масиву | Час виконання |
| 1000 | 0.01s |
| 5000 | 0.35s |
| 10000 | 1.42s |
| 15000 | 3.33s |
| 20000 | 6.08s |
| 25000 | 9.69s |
| 30000 | 14.03s |
| 40000 | 25.92s |
З отриманих даних можна зробити наступні висновки:
В найкращому випадку (відсортований масив) алгоритм методу вставки має лінійну складність. Практично це підтверджується тим, що час виконання зростає приблизно лінійно зі збільшенням розміру вхідних даних.
В середньому випадку алгоритм методу вставки має квадратичну складність. Це видно з того, що час виконання зростає квадратично зі збільшенням розміру масиву. Але цей алгоритм має певні переваги порівняно з іншими алгоритмами сортування, зокрема він простий у реалізації та ефективний для відносно невеликих масивів.
У найгіршому випадку (масив відсортований в зворотньому порядку) алгоритм методу вставки має квадратичну складність, а саме його час виконання зростає квадратично зі збільшенням розміру масиву.
Переваги та недоліки алгоритму сортування методом вставок
Незважаючи на те, що метод вставки має кілька переваг, наприклад, його простота та ефективність для невеликих масивів, він має й деякі недоліки:
Інваріантність: Інваріантність - це властивість сортувального алгоритму, яка означає, що порядок елементів не змінюється, якщо два елементи мають однакове значення. Метод вставки не є інваріантним, тому що коли до масиву додається декілька елементів з однаковим значенням, порядок цих елементів може змінюватись.
Ефективність: Метод вставки має складність O (n^2), що робить його неефективним для великих масивів. Крім того, його ефективність залежить від початкового розташування елементів в масиві. Якщо масив вже відсортований або майже відсортований, метод вставки буде ефективним. Однак, якщо масив випадковий або відсортований у зворотному порядку, метод вставки буде менш ефективним.
Пам'ять: Метод вставки потребує додаткової пам'яті для тимчасового зберігання елементів масиву. Це може бути проблемою для дуже великих масивів, які можуть не вміщатись у пам'ять комп'ютера.
Практичне застосування: Метод вставки не є популярним алгоритмом сортування в практичних застосуваннях, тому що існують більш швидкі та ефективні алгоритми, такі як швидке сортування (QuickSort) та сортування злиттям (MergeSort). Ці алгоритми мають складність O (n log n), що робить їх значно швидшими за метод вставки для великих масивів.
Чутливість до вхідних даних: Метод вставки є чутливим до вхідних даних, оскільки швидкість його виконання залежить від початкового розташування елементів в масиві. Якщо масив містить багато дублікатів, то метод вставки може бути повільним. Крім того, якщо вхідні дані вже відсортовані, метод вставки може бути зайвим, оскільки масив вже відсортований.
Сортування за спаданням: Метод вставки є натуральним для сортування за зростанням, проте він не так просто реалізується для сортування за спаданням. Для сортування за спаданням метод вставки потребує додаткових операцій, що робить його менш ефективним.
Сортування більш складних даних: Метод вставки може бути використаний для сортування простих даних, таких як числа або рядки. Однак, для сортування більш складних даних, таких як об'єкти, структури або класи, потрібно визначити порядок їх порівняння, що може бути складним і вимагати додаткової роботи.
Висновок
У ході виконання лабораторної роботи було продемонстровано роботу алгоритму методом вставок та проаналізовано його ефективність.