Звiт про виконання розрахункового графічного завдання за «Основи програмування»

Міністерство освіти і науки України

Національний технічний університет

«Харківський політехнічний інститут»

Факультет комп’ютерних наук і програмної інженерії

Кафедра інформатики та інтелектуальної власності (ІІВ)

ЗВІТ

про виконання розрахункового графічного завдання

за дисципліною

«Основи програмування»

Виконав

студент групи КН-322Б        Георгій ЖОВТОБРЮХ

Перевірив

ст. викладач кафедри ІІВ        Максим СОБОЛЬ

Харків 2022

1. ЗАВДАННЯ

Програмно реалізувати та порівняти час виконання 2 алгоритмів сортування для упорядкованих, неупорядкованих, та упорядкованих в зворотному порядку масивів даних розміром від 5 до 45 елементів з кроком 5. Побудувати відповідні графіки.

 Відповідно до індивідуального завдання необхідно порівняти наступні алгоритми сортування:

Сортування гнома ― один із найпростіших алгоритмів сортування. Ім'я походить від голландського садового гнома, якого ставлять між квітковими горщиками. Алгоритм знаходить перше місце, де два сусідні елементи стоять у неправильному порядку та змінює їх місцями. Враховуючи, що обмін може породити нову пару, яка стоїть у неправильному порядку, лише до або після переставлених елементів, то потрібно лише перевірити позицію до переставлених елементів. Якщо два сусідні елементи йдуть у правильному порядку, алгоритм йде на одну позицію вперед. Якщо ж вони у неправильному порядку - міняє ці два елементи місцями і йде на одну позицію назад.

Алгоритм концептуально простий, і не потребує вкладених циклів. Його середня швидкодія дорівнює  O(n2), а найкраща швидкодія ― O(n).

Пірамідальне сортування ― це популярний і ефективний алгоритм сортування в комп’ютерному програмуванні. Алгоритм працює шляхом візуалізації елементів масиву як особливого виду повного бінарного дерева, що називається купою.  

 Купа — це спеціальна структура даних на основі дерева.  Бінарне дерево є купою, якщо усі вузли в дереві більші за своїх дочірніх елементів, тобто найбільший елемент знаходиться в корені та обидва його дочірні елементи менші за корінь.

Оскільки дерево задовольняє властивості Max-Heap, то найбільший елемент зберігається в кореневому вузлі. Алгоритм міняє місцями елемент в корені та останній елемент масиву, зменшуючи розмір купи на 1. Знову будує купу, щоб мати найбільший елемент у корені.

 Процес повторюється, доки не будуть відсортовані всі елементи списку.

Середня швидкодія алгоритму ― О(n*log n).

1. ВИКОНАННЯ

Результати вимірювання часу виконання 2 алгоритмів сортування для упорядкованих, неупорядкованих, та упорядкованих в зворотньому порядку масивів даних на прикладі масиву з 5 елементів подано на рис. 2.1.

[pic 1]

Рисунок 2.1 – Приклад результату обчислення

Результати всіх обчислень для упорядкованого масиву подано у табл. 2.1.

Результати всіх обчислень для масиву впорядкованого в зворотному порядку подано у табл. 2.2.

Результати всіх обчислень для невпорядкованого масиву подано у табл. 2.3.

Таблиця 2.1 – Результати обчислень для упорядкованого масиву

У секундах