Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
розробка та дослідження алгоритму сортування внутрішнього обмінного
Інформація про навчальний заклад
ВУЗ:
Вінницькій національний технічний університет
Інститут:
О
Факультет:
СІ
Кафедра:
КН
Інформація про роботу
Рік:
2022
Тип роботи:
Лабораторна робота
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Вінницький національний технічний університет
Факультет інтелектуальних інформаційних технологій та автоматизації
Кафедра КН
Лабораторна робота № 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
Графік:
/
Переваги та недоліки алгоритму сортування методом вставок
Переваги:
Цей алгоритм має ряд переваг. Це просто писати, легко зрозуміти, і це займе всього кілька рядків коду. Дані упорядковано на місці, так що мало пам'яті накладних витрат і, як тільки відсортовані, дані в пам'яті, готові до обробки.
Недоліки:
Основним недоліком є кількість часу, необхідне для сортування. Середній час збільшується майже в геометричній прогресії в міру збільшення кількості елементів таблиці. Сортування в десять разів перевищує кількість предметів майже в сто разів
Висновок: детально проаналізували та дослідили алгоритм сортування внутрішнього обмінного у найкращому, середньому, найгіршому випадках. Навчились писати алгоритм сортування бульбашки. .
23.05.2022 20:36
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора