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