5.4. Практические аспекты сравнения

Для практического сравнения быстродействия работы алгоритмов сортировки, была написана программа, которая реализовывала все вышеназванные алгоритмы. Сортировались следующие массивы данных:

• массив, состоящий из 10 элементов, численные значения элементов которого лежат в диапазоне 0..774 и случайно сгенерированных, а также этот же массивов, но с упорядоченными по возрастанию и по убыванию значениями;

• массив, состоящий из 50 элементов, численные значения элементов которого лежат в диапазоне 0..749 и случайно сгенерированных, а также этот же массивов, но с упорядоченными по возрастанию и по убыванию значениями;

• массив, состоящий из 100 элементов, численные значения элементов которого лежат в диапазоне 0..197 и случайно сгенерированных, а также этот же массивов, но с упорядоченными по возрастанию и по убыванию значениями;

• массив, состоящий из 1000 элементов, численные значения элементов которого лежат в диапазоне 0..143 и случайно сгенерированных, а также этот же массивов, но с упорядоченными по возрастанию и по убыванию значениями;

• массив, состоящий из 10000 элементов, численные значения элементов которого лежат в диапазоне 0..143 и случайно сгенерированных, а также этот же массивов, но с упорядоченными по возрастанию и по убыванию значениями;

После этого составлялась сравнительная таблица тестирования:

Обьем массива	Критерий сравнения	Алгоритм сортировки	Вид массива
			обычный	возраст.	убывающий
10	Время	QuickSort	0,00000072	0,00000185	0,00000072
		InsertionSort	0,00000036	0,00000019	0,00000036
		MergeSort	0,00000109	0,00000174	0,00000127
		HeapSort	0,00000127	0,00000185	0,00000127
	Присвоения	QuickSort	102	90	110
		InsertionSort	50	30	102
		MergeSort	148	148	172
		HeapSort	191	206	161
	Сравнения	QuickSort	96	90	105
		InsertionSort	26	20	76
		MergeSort	92	85	73
		HeapSort	117	127	98
50	Время	QuickSort	0,00000544	0,00000903	0,00000903
		InsertionSort	0,00000325	0,00000091	0,00000487
		MergeSort	0,00001088	0,00000718	0,00000903
		HeapSort	0,00001273	0,00001447	0,00001088
	Присвоения	QuickSort	865	1469	1515
		InsertionSort	1506	150	2496
		MergeSort	1308	1308	1340
		HeapSort	1792	1977	1563
	Сравнения	QuickSort	798	1467	1488
		InsertionSort	1364	100	2350
		MergeSort	873	774	610
		HeapSort	1249	1376	1098
100	Время	QuickSort	0,00001447	0,00002894	0,00002894
		InsertionSort	0,00001088	0,00000145	0,00001806
		MergeSort	0,00002350	0,00001991	0,00002176
		HeapSort	0,00002894	0,00003252	0,00002535
	Присвоения	QuickSort	1817	5362	5195
		InsertionSort	5004	300	9962
		MergeSort	3048	3048	3084
		HeapSort	4392	4805	3868
	Сравнения	QuickSort	1662	5344	5125
		InsertionSort	4716	200	9666
		MergeSort	2104	1818	1448
		HeapSort	3145	3449	2772
Обьем массива	Критерий сравнения	Алгоритм сортировки	Вид массива
			обычный	возраст.	убывающий
1000	Время	QuickSort	0,00018519	0,00126157	0,00072917
		InsertionSort	0,00083218	0,00001447	0,00166435
		MergeSort	0,00017361	0,00037037	0,00017361
		HeapSort	0,00035880	0,00054398	0,00035880
	Присвоения	QuickSort	27717	244366	159485
		InsertionSort	503700	3000	992944
		MergeSort	43852	43852	43900
		HeapSort	69083	72123	63146
	Сравнения	QuickSort	24755	243017	157673
		InsertionSort	500728	2000	989960
		MergeSort	32771	26086	23807
		HeapSort	51603	53495	47340
10000	Время	QuickSort	0,00199074	0,02459491	0,01446759
		InsertionSort	0,11410880	0,00023611	0,25046296
		MergeSort	0,00416667	0,00361111	0,00379630
		HeapSort	0,00614583	0,00578704	0,00561343
	Присвоения	QuickSort	357053	4989888	2951278
		InsertionSort	49618138	30000	99300942
		MergeSort	574396	574396	574460
		HeapSort	938751	888865	878717
	Сравнения	QuickSort	311549	4960528	2917767
		InsertionSort	49588276	20000	99271064
		MergeSort	445822	350602	335870
		HeapSort	713997	669752	670762