Кількість переміщень елементів

Масив 100х500х500

Табл. 4. 3 - Кількість переміщень елементів для масиву 100х500х500

	Невпорядкований	Впорядкований	Зворотно впорядкований
Дані по сортуванню вставкою	649500000	0	1287000000
Сортування вибором	1806000000	0	3712500000
Шейкерне сортування	1806000000	0	3712500000

Порівняння часу сортування для різних геометричних розмірів одного й тогож масиву

Масив 100х250х1000

Табл. 4.4 - Час сортування для масиву 100х250х1000

	Невпорядкований	Впорядкований	Зворотно впорядкований
Дані по сортуванню вставкою	5453	0	11485
Сортування вибором	0094	0	0094
Шейкерне сортування	6922	0	14187

 

Масив 100х500х2000

Табл. 4.5 - Час сортування для масиву 100х1000х250

	Невпорядкований	Впорядкований	Зворотно впорядкований
Дані по сортуванню вставкою	6672	0	14250
Сортування вибором	0109	0	0093
Шейкерне сортування	7000	0	14110

4.
Висновки за отриманим результатами

Порівняння результатів сортування для різних станів масивів

 

1. Сортування відбувається найшвидше коли стан масиву впорядкований.

. Сортування відбувається найдовше коли масив впорядкований у зворотньому порядку (ніж задано за варіантом).

 

Порівняння методів сортування на невпорядкованому масиві

 

1. Найшвидше, масив був відсортований методом «Вибру».

. На другому та третьому місці - «сортування вставкою» та «сортування шейкером» відповідно. Хоча відмінність у часі між «сортування вставкою» та «сортування шейкером» порівняно невелике.

 

Порівняння методів сортування на впорядкованому масиві

 

Результати тестів свідчать, що на впорядкованому масиві алгоритми спрацьовують практично миттєво. Це пов’язано з тим, що переміщень елементів не відбувається, а отже основні затрати часу, які є в наявності для інших станів масиву (невпорядкований та зворотно впорядкований) тут відсутні.

Теоретично кількість порівнянь у методу обміну та шейкерного є меншою, ніж у алгоритму сортування вставкою із лінійним пошуком місця вставки зліва, оскільки для перших двох алгоритмів достатньо одного проходу по масиву, та для кожного з елементів порівняти його з наступним, тобто здійснити (n-1) порівнянь, для алгоритму вставки із пошуком місця вставки від кінця відсортованої частини, тобто з правого боку, для кожного і-того елементу ми порівнювали б його з попереднім елементом і одразу бачимо, що і-тий елемент вже стоїть на своєму місці, а отже кількість порівнянь також (n-1)).

 

Порівняння методів сортування на зворотно впорядкованому масиві

 

Результати тестів свідчать, що найшвидше відсортовує алгоритм сортування «вибором». Потім ідуть «сортування вставкою» та «сортування шейкером» з відносно невеликою різницею (результати наведені в табл. 4.1 та 4.2).

 

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

 

Результати тестів свідчать, що для різних геометричних розмірів масиву тривалість сортування суттєво не відрізняється. Основний час при сортуванні витрачається на переміщення перерізів, що відбувається через одну змінну, отже при однаковій кількості елементів у перерізі переміщення перерізу буде займати приблизно однаково часу.

Отже, геометричні розміри перерізу масиву суттєво не впливають на тривалість сортування для даної задачі.

 

Кількість переміщень елементів

 

Як і у попередніх тестах, найкращій результат показав алгоритм «сорування вибором» - кількість його переміщень найменша. «сортування вставкою» та «сортування шейкером» майже не відрізняються.

вибір лінійний шейкерний програма

Список використаної літератури

 

1. Вирт Н. Алгоритмы и структуры данных: Пер с англ. - М.: Мир, 1989.

2. <http://www.cyberguru.ru/>

3. МЕТОДИЧЕСКИЕ УКАЗАНИЯ к лабораторному практикуму и самостоятельной работе по дисциплине «Программирование» для студентов направления подготовки 0915 -“Компьютерная инженерия”