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

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

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

ЗІ

Кафедра:

Не вказано

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

Рік:

2023

Тип роботи:

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

Предмет:

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

Завантажити

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

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

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

17.05.2023 18:07

Коментарі

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

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

поділитись