Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №3
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
Методи сортування
Мета роботи: метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування.
Теоретична частина.
Сортування – процес переставлення об’єктів множини у визначеному порядку з метою полегшення наступного пошуку елементів у відсортованій множині. Елементи сортування є практично в усіх задачах(телефонні книги, відомості, звіти). Найчастіше сортування використовують для подальшого пошуку даних.
1. Сортування вибором: Один з найпростіших методів сортування працює в такий спосіб: знаходимо найменший елемент у масиві й обмінюємо його з елементом, якій знаходиться на першому місці, потім повторюємо процес із другої позиції у файлі і знайдений елемент обмінюємо з другим елементом і так далі поки весь масив не буде відсортований. Цей метод називається сортування вибором оскільки він працює циклічно вибираючи найменший з елементів, що залишилися.
/
2. Сортування вставками: Алгоритм можна описати так:
Запам'ятати в тимчасову змінну значення поточного елемента масиву;
Поки елементи ліворуч від запам'ятованого значення більше ніж запам'ятовується – переміщуємо їх на позицію праворуч. Виходить, що попередній елемент займе осередок запам'ятованого. А той, що стоїть перед попереднім, – переміститься своєю чергою на місце попереднього. І так елементи рухатимуться один за одним.
Рух елементів закінчується, якщо черговий елемент, який потрібно зрушити, виявляється за значенням меншим, ніж той, що запам'ятали в тимчасову змінну на початку циклу.
Цикл бере наступний елемент, і знову зрушує всі, що розташовані перед ним і великі за значенням.
/
Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням методів сортування. Оцінити час виконання та складність алгоритму.1. Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів відсортувати масив (10х10 або більше).2. Самостійно обрати додатковий метод та провести сортування того ж масиву.3. Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час сортування с масивом більшого розміру, який створити за допомогою генератора випадкових чисел.
/
Опис алгоритму
Після заповнення масиву 10х10 випадковими числами від 0 до 9 за допомогою двох циклів for так виведення його на екран, за допомогою методу вибором відсортуємо початковий масив, використавши перебір елементів через два цикли. Виводимо відсортований масив і час сортування на екран. Як додатковий метод сортування я обрав метод вставками: два цикли for для перебору чисел та ще один for з вмістом для реалізування сортування. Вивід на екран масиву та час виконання. Потім ініціалізація масиву 20х20 та заповнення, знову ж таки, випадковими числами від 0 до 9 та його виведення. Далі, так само, як і з масивом 10х10, сортування методом вибору, виведення відсортованого масиву та час сортування на екран.
Складність алгоритму
Масив
Метод
10х10
20x20
Вибором
Time=2.7ns
Time=8.6ns
Вставкою
Time=2ns
-
Результати роботи програми
Масив 10х10 методом вибору:
/
Масив 10х10 методом вставки:
/
Масив 20х20 методом вибору (зліва-початковий, справа-відсортований):
//
Програмний код
https://replit.com/join/jpaugfkmtf-ironfire2535
Висновок:
В результаті виконання лабораторної роботи було проведено 3 сортування: масиву 10х10 двома методами (вибору та вставкою) та масиву 20х20 одним методом (вибору). В результаті аналізу швидкодії, була виявлена різниця в швидкості сортування методом вибору и методом вставки: метод вставки працює швидше.
Ви не можете залишити коментар. Для цього, будь ласка, увійдіть
або зареєструйтесь.
Ділись своїми роботами та отримуй миттєві бонуси!
Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!