Сравнение скорости работы сортировок на С++

Начнем с того, что данному вопросу уделяется мало времени и приходится гуглить данный вопрос.

Код программы используемый в данной статье, я переписывал пару раз. Всегда было интересно насколько одна сортировка будет быстрее другой. Их как бы все студенты проходят, но в основном как переписывание псевдоалгоритма на лекции в код на каком-нибудь языке. Может быть данная статья будет полезна для какого-нибудь начинающего программиста.
Рассмотрим 5 сортировок. Это пузырьковая(bubble), шейкерная(shake), пирамидальная(heap), вставками(insertion) и быстрая(quick).

Для анализа их скорости будет использоваться функция clock() до сортировки и она же после, потом берется их разность и мы узнаем время работы сортировки. Я использовал 100 итераций по 1000 значений заданных в векторах и одном листе для тестирования встроенной функции sort() из stl. Каждой сортировке даются одинаково разбросанные по массивам числа на каждой итерации. После чего время записывается в переменную mean каждой сортировки и делится по итогу на количество итераций. Так мы узнаем среднее время работы каждой сортировки и сможем в итоге их сравнить по скорости при одинаковых исходных данных. Данные вносятся в массивы функцией rand().

Файл Sorts.h:

#pragma once #include <iostream> #include <list> #include <vector>  #include <iterator> template <typename T> class Sorts { public: 	std::list<T> arrayList; 	std::vector<T> bubbleArray,insertionArray,heapArray,shakeArray; 	float BubbleSort() 	{ 		std::cout <<"Time to Bubble>" << std::endl; 		unsigned int start_time = clock(); // начальное время 		int size = bubbleArray.size(); 		for (int i = 1; i < size; i++) 			for (int j = size-1; j >=i; j--) 				if (bubbleArray[j-1] > bubbleArray[j]) 					swap(&bubbleArray, j - 1, j); 		unsigned int end_time = clock(); // конечное время 		unsigned int search_time = end_time - start_time; // искомое время 		std::cout << (float)search_time / CLOCKS_PER_SEC << std::endl; 		return (float)search_time / CLOCKS_PER_SEC; 	} 	float InsertionSort() 	{ 		std::cout << "Time to Insertion>" << std::endl; 		unsigned int start_time = clock(); // начальное время 		int size = insertionArray.size(); 		for (int i = 1; i < size; i++) 		{ 			T tmp = insertionArray[i]; 			int j = i; 			while (j > 0 && insertionArray[j - 1] > tmp) 			{ 				insertionArray[j] = insertionArray[j - 1]; 				j = j - 1; 			} 			insertionArray[j] = tmp; 		} 		unsigned int end_time = clock(); // конечное время 		unsigned int search_time = end_time - start_time; // искомое время 		std::cout << (float)search_time / CLOCKS_PER_SEC << std::endl; 		return (float)search_time / CLOCKS_PER_SEC; 	} 	void swap(std::vector<T> *v, int n, int m) 	{ 		T tmp = (*v)[n]; 		(*v)[n] = (*v)[m]; 		(*v)[m] = tmp; 	} 	float HeapSort() 	{ 		std::cout << "Time to Heap>" << std::endl; 		unsigned int start_time = clock(); // начальное время 		int size = heapArray.size(); 		for (int j = 0; j < size; j++) 		{ 			for (int i = size / 2 - 1 - j / 2; i > -1; i--) 			{ 				if (2 * i + 2 <= size - 1 - j) 				{ 					if (heapArray[2 * i + 1] > heapArray[2 * i + 2]) 					{ 						if (heapArray[i] < heapArray[2 * i + 1]) 						{ 							swap(&heapArray, i, 2 * i + 1); 						} 					} 					else 						if (heapArray[i] < heapArray[2 * i + 2]) 						{ 							swap(&heapArray, i, 2 * i + 2); 						} 				} 				else 					if (2 * i + 1 <= size - 1 - j) 						if (heapArray[i] < heapArray[2 * i + 1]) 							swap(&heapArray, i, 2 * i + 1); 			} 			swap(&heapArray, 0, size - 1 - j); 		} 		unsigned int end_time = clock(); // конечное время 		unsigned int search_time = end_time - start_time; // искомое время 		std::cout << (float)search_time / CLOCKS_PER_SEC << std::endl; 		return (float)search_time / CLOCKS_PER_SEC; 	} 	float ShakeSort() 	{ 		std::cout << "Time to Shake>" << std::endl; 		unsigned int start_time = clock(); // начальное время 		int size = shakeArray.size(); 		int left = 0; 		int right = size - 1; 		do { 			for (int i = left; i < right; i++) { 				if (shakeArray[i] > shakeArray[i + 1]) 					swap(&shakeArray,i,i+1); 			} 			right--; 			for (int i = right; i > left; i--) { 				if (shakeArray[i] < shakeArray[i - 1]) 					swap(&shakeArray, i-1, i); 			} 			left++; 		} while (left < right); 		unsigned int end_time = clock(); // конечное время 		unsigned int search_time = end_time - start_time; // искомое время 		std::cout << (float)search_time / CLOCKS_PER_SEC << std::endl; 		return (float)search_time / CLOCKS_PER_SEC; 	} 	void PrintArray(int num) 	{ 		switch (num) 		{ 		case 0: 			for (typename std::list<T>::iterator it = arrayList.begin(); it != arrayList.end(); it++) 				std::cout << (*it) << " "; 			break; 		case 1: 			for (typename std::vector<T>::iterator it = bubbleArray.begin(); it != bubbleArray.end(); it++) 				std::cout << (*it) << " "; 			break; 		case 2: 			for (typename std::vector<T>::iterator it = shakeArray.begin(); it != shakeArray.end(); it++) 				std::cout << (*it) << " "; 			break; 		case 3: 			for (typename std::vector<T>::iterator it = heapArray.begin(); it != heapArray.end(); it++) 				std::cout << (*it) << " "; 			break; 		case 4: 			for (typename std::vector<T>::iterator it = insertionArray.begin(); it != insertionArray.end(); it++) 				std::cout << (*it) << " "; 			break; 		default: 			break; 		 		} 		std::cout << std::endl; 	} }; 

Замечу что можно использовать не только целые числа, но и вещественные и символы.

Файл основной программы:

 #include "Sorts.h"   int main() { 	std::vector<float> vq, vb, vs, vh, vi; 	float meanq = 0, meanb = 0, means = 0, meanh = 0, meani = 0; 	const int N = 100; 	srand(time(0)); 	for (int i = 0; i < N; i++) 	{ 		std::cout << i+1 << " iteration" << std::endl; 		const int iSize = 1000; 		auto sort = new Sorts<int>(); 		for (int i = 0; i < iSize; i++) 		{ 			int num = rand() % iSize; 			sort->arrayList.push_back(num); 			sort->bubbleArray.push_back(num); 			sort->shakeArray.push_back(num); 			sort->heapArray.push_back(num); 			sort->insertionArray.push_back(num); 		}  		std::cout << "Time to Quick sort from stl>" << std::endl; 		unsigned int start_time = clock(); // начальное время 		sort->arrayList.sort(); 		unsigned int end_time = clock(); // конечное время 		unsigned int search_time = end_time - start_time; // искомое время 		std::cout << (float)search_time / CLOCKS_PER_SEC << std::endl; 		vq.push_back((float)search_time / CLOCKS_PER_SEC); 		vb.push_back(sort->BubbleSort()); 		vs.push_back(sort->ShakeSort()); 		vh.push_back(sort->HeapSort()); 		vi.push_back(sort->InsertionSort()); 		meanq += vq[i]; 		meanb += vb[i]; 		means += vs[i]; 		meanh += vh[i]; 		meani += vi[i]; 		//sort->PrintArray(0); 		//sort->PrintArray(1); 		//sort->PrintArray(2); 		//sort->PrintArray(3); 		//sort->PrintArray(4); 		sort->arrayList.clear(); 		sort->bubbleArray.clear(); 		sort->shakeArray.clear(); 		sort->heapArray.clear(); 		sort->insertionArray.clear(); 		std::cout << "end of "<< i + 1 <<" iteration" << std::endl; 	} 	std::cout << "Results:" << std::endl; 	std::cout << "Mean quick=" << (float)meanq / N << std::endl; 	std::cout << "Mean bubble=" << (float)meanb / N << std::endl; 	std::cout << "Mean shake=" << (float)means / N  << std::endl; 	std::cout << "Mean heap=" << (float)meanh / N  << std::endl; 	std::cout << "Mean insertion=" << (float)meani / N << std::endl; 	return 0; } 

Каковы же результаты?

С большим отрывом идет sort из stl, потом вставками, пирамидальная, шейкерная и заканчивает пузырьковая.

Quick — 0.00225 ms
Insertion — 0.04482 ms
Heap — 0.07025 ms
Shake — 0.14186 ms
Bubble — 0.14324 ms

В принципе слишком большие массивы данных долго сортируются, но quicksort справляется на порядки быстрее остальных.