розробка та дослідження алгоритму сортування внутрішнього обмінного

Інформація про навчальний заклад

ВУЗ:
Вінницькій національний технічний університет
Інститут:
О
Факультет:
СІ
Кафедра:
КН

Інформація про роботу

Рік:
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 Графік: /
Переваги та недоліки алгоритму сортування методом вставок
Переваги: Цей алгоритм має ряд переваг. Це просто писати, легко зрозуміти, і це займе всього кілька рядків коду. Дані упорядковано на місці, так що мало пам'яті накладних витрат і, як тільки відсортовані, дані в пам'яті, готові до обробки. Недоліки: Основним недоліком є кількість часу, необхідне для сортування. Середній час збільшується майже в геометричній прогресії в міру збільшення кількості елементів таблиці. Сортування в десять разів перевищує кількість предметів майже в сто разів Висновок: детально проаналізували та дослідили алгоритм сортування внутрішнього обмінного у найкращому, середньому, найгіршому випадках. Навчились писати алгоритм сортування бульбашки.
.
Антиботан аватар за замовчуванням

01.01.1970 00:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Новини