Міністерство освіти і науки України Вінницький національний технічний університет Факультет інтелектуальних інформаційних технологій та автоматизації Кафедра КН Лабораторна робота № 4 з дисципліни “Теорія алгоритмів ” Тема: «розробка та дослідження алгоритму сортування внутрішнього обмінного» Мета: детально проаналізувати та дослідити алгоритм сортування шляхом вибору (або внутрішнього обмінного сортування). Хід роботи: Ідея алгоритму внутрішнього обмінного сортування. Тут обмін місцями двох елементів є характерною особливістю процесу сортування. Викладений нижче алгоритм ґрунтується на порівнянні та зміні місць для пари сусідніх елементів і продовженні цього процесу доти, поки не будуть упорядковані всі елементи (тому даний алгоритм отримав ще назву „сортування прямим обміном”). І такі проходи по масиву слід повторювати, пересуваючи щоразу найменший елемент послідовності, яка залишилась, до лівого кінця масиву. Якщо розглядати масиви як вертикальні, а не горизонтальні, то елементи можна інтерпретувати як бульбашки у чані з водою, причому вага кожного відповідає його ключу [4]. Тут під час кожного проходу одна бульбашка „піднімається” до рівня, що відповідає її вазі. Власний приклад роботи алгоритму сортування методом внутрішнього обмінного на масиві з 10 чисел наведено на рисунку 1.1: Алгоритм сортування методом вставок у графічному вигляді наведено на рисунку 1.2 : Теоретична оцінка складності алгоритму для трьох випадків для найкращого випадку. Для нашого алгоритму найсприятливішим є випадок, коли масив вже є відсортований. О(n) для найгіршого випадку. Якщо ж масив відсортований у зворотному (в даному випадку, спадному) порядку – час роботи процедури буде максимальним: одержуємо, що у гіршому випадку час роботи процедури дорівнює О(n²) для середнього випадку Час роботи в середньому часто близький до часу роботи у гіршому випадку. Нехай, наприклад, ми сортуємо випадково розташовані n чисел за допомогою алгоритму бульбашки. О(n²) Сирець алгоритму сортування методом вставок наведено на рисунку 1.3: / Практична оцінка складності алгоритму в трьох випадках для масивів різного розміру. Таблиця та графік для найкращого випадку. № Кількість даних Час (c)  1 50000000 7  2 55000000 7,32  3 57000000 7,6  4 58000000 7,8  5 60000000 8,5  6 65000000 9  7 66000000 9,9   Графік: / Таблиця та графік для найгіршого випадку. № Кількість даних Час (c)  1 10000 14  2 20000 51  3 25000 79  4 30000 112  5 40000 193  6 50000 295  7 75000 696   Графік: / Таблиця та графік для середнього випадку. № Кількість даних Час (c)  1 15000 22  2 20000 48  3 25000 62  4 30000 88  5 40000 159  6 50000 260  7 75000 604   Графік: / Переваги та недоліки алгоритму сортування методом вставок Переваги: Цей алгоритм має ряд переваг. Це просто писати, легко зрозуміти, і це займе всього кілька рядків коду. Дані упорядковано на місці, так що мало пам'яті накладних витрат і, як тільки відсортовані, дані в пам'яті, готові до обробки. Недоліки: Основним недоліком є кількість часу, необхідне для сортування. Середній час збільшується майже в геометричній прогресії в міру збільшення кількості елементів таблиці. Сортування в десять разів перевищує кількість предметів майже в сто разів Висновок: детально проаналізували та дослідили алгоритм сортування внутрішнього обмінного у найкращому, середньому, найгіршому випадках. Навчились писати алгоритм сортування бульбашки. .