НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №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-[ім’я автора приховано] Висновок: В результаті виконання лабораторної роботи було проведено 3 сортування: масиву 10х10 двома методами (вибору та вставкою) та масиву 20х20 одним методом (вибору). В результаті аналізу швидкодії, була виявлена різниця в швидкості сортування методом вибору и методом вставки: метод вставки працює швидше.