Методи сортування. Звіт до лабораторної роботи з Програмування складних алгоритмів. Робота № 100388

Методи сортування

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

ВУЗ:

Національний технічний університет України Київський політехнічний інститут

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

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

Рік:

2023

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Програмування складних алгоритмів

Завантажити

Частина тексту файла (без зображень, графіків і формул):

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №3 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Методи сортування» Варіант № 20 Дата «16» травня 2022 Мета роботи: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Завдання до лабораторної роботи: Розробити програму з алгоритмом згідно варіанту з використанням методів сортування. Оцінити час виконання та складність алгоритму. 1. Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням). 2. Самостійно обрати додатковий метод та провести сортування того ж масиву. 3. Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел. Завдання для варіанту 20: Метод сортування вставками / Теоретичні відомості Алгоритми сортування - це методи реорганізації великої кількості елементів у певний порядок, наприклад, від найвищого до найнижчого, або навпаки, або навіть в якомусь алфавітному порядку. Ці алгоритми беруть вхідний список, обробляють його (тобто виконують над ним деякі операції) і створюють відсортований список. Найпоширеніший приклад, з яким ми стикаємось щодня - це сортування одягу чи інших предметів на веб-сайті електронної комерції або за найнижчою ціною, або за списком за популярністю, або за іншим замовленням. Типи сортувальних алгоритмів: Quick Sort Bubble Sort Merge Sort Insertion Sort Selection Sort Heap Sort Radix Sort Bucket Sort Порівняння алгоритмів: Algorithm Best Average Worst Quick Sort Ω(n log(n)) Θ(n log(n)) O(n^2) Bubble Sort Ω(n) Θ(n^2) O(n^2) Merge Sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) Insertion Sort Ω(n) Θ(n^2) O(n^2) Selection Sort Ω(n^2) Θ(n^2) O(n^2) Heap Sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) Radix Sort Ω(nk) Θ(nk) O(nk) Bucket Sort Ω(n+k) Θ(n+k) O(n^2) Виконання роботи Порівняння часу виконання в залежності від розміру масиву Розмір масиву Кількість ітерацій Час виконання Insertion sort Bubble sort 10x10 110 0.149ms 0.248ms 26x26 1118 0.465ms 1.207ms / Результати Для масиву розмірністю 10 на 10: / Для масиву розмірністю 26 на 26: / / Висновки: У ході виконання даної лабораторної роботи було отримано практичні навички з використання простих методів сортування. Порівняно час роботи та кількість ітерацій програми з різною розмірністю масиву використовуючи різні методи сортування. Код програми у вигляді скріншотів Метод сортування вставками / Бульбашкове сортування / Час виконання /

Звіт до лабораторної роботи Програмування складних алгоритмів

22.05.2023 11:52

Коментарі

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

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись