Національний технічний університет України «КПІ ім. Ігоря Сікорського» Кафедра АПЕПС Алгоритмізація та програмування 1: Базові концепції програмування ЗВІТ Лабораторна робота (Комп’ютерний практикум) № 7+8: « Методи сортування масивів» Дата «10» Грудня 2021 Завдання Ознайомитись з алгоритмами сортування масивів та способами їхньої реалізації. У якості індивідуального завдання необхідно написати програмний код, у якому реалізується сортування масивів методами бульбашки, вставок, вибору, сортуванням Шелла, Хоора та швидкого сортування. Звернення до елементів масиву реалізувати за допомогою вказівника на масив. Вихідні дані по варіантах у Додатку В. РЕЗУЛЬТАТ РОБОТИ ПОТРІБНО: 1. Роздрукувати (вивести на екран) початковий масив та масиви після виконання сортування різними методами. Показати кількість операцій для виконання сортування різними методами. 2. Відкритий для редагування програмний код розмістити на сайті https://replit.com/ (посилання через кнопку «+ Share»). 3. Звіт до комп’ютерного практикуму № 8 додати в свій Клас на ресурсі https://classroom.google.com/. Теоретичні відомості Метод бульбашки (Bubble Sort) Сутність методу полягає в багаторазовому проході по масиву. На кожному кроці послідовно порівнюються пари сусідніх елементів, і якщо порядок в такій парі невірний, то елементи в парі міняються місцями. При проході алгоритму, елемент, що стоїть не на своїй позиції, «спливає» до потрібної позиції як бульбашка, звідки і назва алгоритму. Сортування зі вставками (Insertion Sort) Сортований масив переглядається в порядку зростання номерів і кожен елемент вставляється в уже переглянуту частина масиву так, щоб зберегти порядок. Сортування вибором Спочатку відшукується найменший елемент масиву, потім він міняється місцями з елементом, що стоїть першим у сортованому масиві. Далі, знаходиться другий найменший елемент і міняється місцями з елементом, що стоїть другим у вихідному масиві. Цей процес триває до тих пір, поки весь масив не буде відсортований. Метод Шелла Цей метод полягає в порівнянні елементів масиву, розділених однаковою відстанню таким чином, щоб елементи на цій відстані були впорядковані. Потім ця відстань ділиться навпіл і процес триває. В кінці відстань рівна 1 і якщо змін немає, то масив відсортований. Швидке сортування Цей метод розглядає масив, як список значень. Спочатку виділяється середнє значення як сепаратор (фактор розбиття) списку. Список розбивається на два: в одному з них значення менше сепаратора, а в іншому - більше або рівні. Далі процедура сортування рекурсивно викликає саму себе для кожного з двох списків. Кожен раз при виклику сортування список елементів розбивається на два менших. Швидке сортування Хоара Цей метод ґрунтується на послідовному поділі набору даних на блоки меншого розміру таким чином, що між значеннями різних блоків забезпечується відношення впорядкованості (для будь-якої пари блоків всі значення одного з цих блоків не перевищують значень іншого блоку ). Блок-схема / 25 Варіант завдання / / Результати програми Вивід на екран монітора результату // Висновок: Під час виконання цієї лабораторної робити було ознайомлено з методами можлтвістю перестановки елементів масиву. Також вивчено метод сортування масиву, який дозволив виконати завдання відповідно до варіанту. Результати були виведені на екран. Силка на repl.it: https://replit.com/join/jlpmevgmko-tr-15shiepietko