   Quick Sort vs Heapsort
  I have written a program out of boredom and I was wondering if I can get some feedback.When I ran it on my computer heapsort seems to be beating quicksort which is weird so I am thinking there is either a mistake in my sorting or timing code.This is a small project consisting two files one of them is the class that I use to get timings the other one holds all the sorting code. I also use 3 threads, each thread uses a different sort(bubble,heap,quick).main.cpp#include <iostream>#include <sstream>#include <vector>#include <iomanip>#include <windows.h>#include "Profiler.h"using std::cout;template<class T>void swap(T& a,T& b){T c = a;a = b;b = c;}// Bubble Sorttemplate<class T>void bubbleSort(std::vector<T>& data,int (*compare)(T,T)){// number of swaps made in each passint swapCount = 0;for(unsigned int i=1; i<data.size(); ++i){swapCount = 0;for(unsigned int k=0; k<data.size() - i; ++k){if( compare(data[k],data[k+1]) > 0 ){swap(data[k],data[k+1]);++swapCount;}}//if there are no swaps in a pass the array is sortedif (swapCount == 0)return;}}// Heap Sort// converts an array into a heaptemplate<class T>void heapify(std::vector<T>& data,unsigned int current,unsigned int size,int (*compare)(T,T)){while(current < size){unsigned int left = current * 2 + 1;unsigned int right = left + 1;if(left < size){unsigned int index = current;if(compare( data, data[index] ) > 0)index = left;if( right < size ){if(compare( data, data[index] ) > 0)index = right;}if(index!=current){swap(data[current],data[index]);current = index;}elsebreak;}else break;}}template<class T>void heapSort(std::vector<T>& data,int (*compare)(T,T)){int start = data.size()/2 - 1;for(int i=start; i>=0; --i){heapify(data,i,data.size(),compare);}for(unsigned int i=0; i < data.size() -1 ; ++i){swap(data[0],data[data.size()-i-1]);heapify(data,0,data.size()- i -1,compare);}}// Quick Sorttemplate<class T> int findMedianOfThree(std::vector<T>& data,int first,int size,int (*compare)(T,T)){int mid = first + (size / 2);int last = first + size - 1;T pivot = data[first];if(compare(pivot,data[mid]) >0 && compare(pivot,data[last]) < 0){return first;}pivot = data[mid];if(compare(pivot,data[first]) >0 && compare(pivot,data[last]) < 0){return mid;}return last;}template<class T>void quickSortRecurse(std::vector<T>& data,int first,int size,int (*compare)(T,T)){int pivot = 0;int last = first + size - 1;int mid = 0;int lower = first;int higher = last;if(size > 1){mid = findMedianOfThree(data,first,size,compare);pivot = data[mid];data[mid] = data[first];while(lower<higher){while(compare(pivot,data[higher]) < 0 && lower < higher)higher--;if(higher!=lower){data[lower] = data[higher];lower++;}while(compare(pivot,data[lower]) > 0 && lower < higher)lower++;if(higher!=lower){data[higher] = data[lower];higher--;}}data[lower] = pivot;quickSortRecurse(data,first,lower-first,compare);quickSortRecurse(data,lower+1,last-lower,compare);}}template<class T>void quickSort(std::vector<T>& data,int (*compare)(T,T)){quickSortRecurse(data,0,data.size(),compare);}// comparison methodsint ascending(int a,int b){return a-b;}int descending(int a,int b){return b-a;}// for printing the datatemplate<class T>void printData(std::vector<T>& data){HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);std::wostringstream oss;DWORD dwChars;for(unsigned int i=0; i<data.size(); ++i){oss<<data<<" ";}oss<<"\n";std::wstring text = oss.str();WriteConsole(hStdout,text.c_str(), (DWORD)text.length(), &dwChars, NULL);}DWORD WINAPI thread1(LPVOID args){DWORD dwChars;// Make sure there is a console to receive output results. HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);if( hStdout == INVALID_HANDLE_VALUE )return 1;std::vector<int>* data = reinterpret_cast<std::vector<int>*>(args);//make copy of datastd::vector<int> bubbleData = *data;Profiler profiler;profiler.beginProfile("bubbleSort");bubbleSort<int>(bubbleData,ascending);profiler.endProfile("bubbleSort");std::wostringstream oss;oss<<"Bubble sort : "<<std::fixed<<std::showpoint<<std::setprecision(10)<<profiler.getData("bubbleSort")<<" seconds\n";std::wstring text  = oss.str();WriteConsole(hStdout,text.c_str(), (DWORD)text.length(), &dwChars, NULL);return 0;}DWORD WINAPI thread2(LPVOID args){DWORD dwChars;// Make sure there is a console to receive output results. HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);if( hStdout == INVALID_HANDLE_VALUE )return 1;std::vector<int>* data = reinterpret_cast<std::vector<int>*>(args);//make copy of datastd::vector<int> heapData = *data;Profiler profiler;profiler.beginProfile("heapSort");heapSort<int>(heapData,ascending);profiler.endProfile("heapSort");std::wostringstream oss;oss<<"Heap sort   : "<<std::fixed<<std::showpoint<<std::setprecision(10)<<profiler.getData("heapSort")<<" seconds\n";std::wstring text  = oss.str();WriteConsole(hStdout,text.c_str(), (DWORD)text.length(), &dwChars, NULL);return 0;}DWORD WINAPI thread3(LPVOID args){DWORD dwChars;// Make sure there is a console to receive output results. HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);if( hStdout == INVALID_HANDLE_VALUE )return 1;std::vector<int>* data = reinterpret_cast<std::vector<int>*>(args);//make copy of datastd::vector<int> quickSortData = *data;Profiler profiler;profiler.beginProfile("quickSort");quickSort<int>(quickSortData,ascending);profiler.endProfile("quickSort");std::wostringstream oss;oss<<"Quick sort  : "<<std::fixed<<std::showpoint<<std::setprecision(10)<<profiler.getData("quickSort")<<" seconds\n";std::wstring text  = oss.str();WriteConsole(hStdout,text.c_str(), (DWORD)text.length(), &dwChars, NULL);return 0;}int main(int argc, char* argv[]){// create array and fill with random valuesint arraysStartingSize = 100;unsigned int runs = 4;HANDLE threads[3];DWORD threadIds[3];for(unsigned int n=0; n<runs; ++n){cout<<"Sorting "<<arraysStartingSize<<" elements\n";std::vector<int> data;for(int i=0; i<arraysStartingSize; ++i){data.push_back(rand()%1000);}threads[0] = CreateThread( NULL, 0, thread1, &data, 0, &threadIds[0]);threads[1] = CreateThread( NULL, 0, thread2, &data, 0, &threadIds[1]);threads[2] = CreateThread( NULL, 0, thread3, &data, 0, &threadIds[2]);WaitForMultipleObjects(3, threads, TRUE, INFINITE);// enlarge the array sizearraysStartingSize = arraysStartingSize * 10;cout<<"\n\n";for(int i=0; i<3; i++){CloseHandle(threads);}}return 0;}Profiler.h#ifndef INC_PROFILER_H#define INC_PROFILER_H#include <string>#include <map>#include <windows.h>#include<exception>class Profiler{public:struct TimeData{TimeData():elapsedTime(0.0f){}LARGE_INTEGER begin;LARGE_INTEGER end;float elapsedTime;};Profiler(){if(!QueryPerformanceFrequency(&m_TicksPerSecond)){throw std::runtime_error("Can't initialize timer.");}}void beginProfile(const std::string& name){std::map<std::string,TimeData>::iterator it;if((it = m_Data.find(name)) != m_Data.end()){TimeData& time = it->second;QueryPerformanceCounter(&time.begin);}else{TimeData time;QueryPerformanceCounter(&time.begin);m_Data[name] = time;}}void endProfile(const std::string& name){std::map<std::string,TimeData>::iterator it;if((it = m_Data.find(name)) != m_Data.end()){TimeData& time = it->second;QueryPerformanceCounter(&time.end);time.elapsedTime = ( (float) time.end.QuadPart - (float) time.begin.QuadPart) / (float) m_TicksPerSecond.QuadPart;}}float getData(const std::string& name)const{std::map<std::string,TimeData>::const_iterator it = m_Data.find(name);if(it!=m_Data.end())return it->second.elapsedTime;return 0.0f;}std::map<std::string,TimeData> m_Data;LARGE_INTEGER m_TicksPerSecond;};#endif // INC_PROFILER_HAny feedback is welcome.   
Quote:Original post by Black KnightWhen I ran it on my computer heapsort seems to be beating quicksort which is weird so I am thinking there is either a mistake in my sorting or timing code.It isn't. Heap sort has worst case nlogn, QS has n^2.For some sequences, HS will perform better. QS inevitably depends on split heuristics.Also, for small number of elements, QS is quite sub-optimal, and if number of elements falls under N, different sorts are often used.It's been a while, and I don't have the charts handy, but IIRC, bubblesort is optimal for < 5 or so elements, followed by heap sort < 30, followed by QS. Despite this, amortized complexity remains nlogn.   ;  My code starts with an array of 100 elements and then increases size by ten times and does four passes.So it does sorting for 100,1000,10000,100000 elements, here are the results : Sorting 100 elementsBS: 0.0000210543 secondsHS: 0.0000084217 secondsQS: 0.0000091873 secondsSorting 1000 elementsBS: 0.0023450654 secondsHS: 0.0001006778 secondsQS: 0.0001098651 secondsSorting 10000 elementsBS: 0.2190228254 secondsHS: 0.0012192349 secondsQS: 0.0012758900 secondsSorting 100000 elementsBS: 21.6917514801 secondsHS: 0.0142614115 secondsQS: 0.0129457098 secondsLooks like I need to go over 100k for QS to beat heapsort.   ;Quote:Original post by Black KnightLooks like I need to go over 100k for QS to beat heapsort.QS is divide and conquer. On each division you can check if new interval is smaller than X.The sizes for which HeapSort behaves consistently better are small, in low double digits. Anything above that will depend on actual value distribution.   ;  HeapSort has nlogn runtime, while quicksort has "expected" nlogn. That meansquicksort may be better or worse than nlogn, depending on the input. But from what I have read, quicksort does better in practice for large inputs.   ;Sorting 100 elementsBubble sort : 0.0000197462 secondsHeap sort   : 0.0000084104 secondsQuick sort  : 0.0000098731 secondsstd::sort   : 0.0000054850 secondsSorting 1000 elementsBubble sort : 0.0019731547 secondsHeap sort   : 0.0000903205 secondsQuick sort  : 0.0001118950 secondsstd::sort   : 0.0000566788 secondsSorting 10000 elementsBubble sort : 0.1955748796 secondsHeap sort   : 0.0011003007 secondsQuick sort  : 0.0013262847 secondsstd::sort   : 0.0005616689 secondsSorting 100000 elementsBubble sort : 19.8348808289 secondsHeap sort   : 0.0140658580 secondsQuick sort  : 0.0150707187 secondsstd::sort   : 0.0050616027 secondsMind you, most std::sort implementations use introsort, which switches from quicksort to heapsort if the recursion depth exceeds a certain level   ;  Holy cow! That is 3x faster. Is that speed gain only from intro sort or other tricks and optimizations?template<class _RanIt,class _Diff,class _Pr> inlinevoid _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred){// order [_First, _Last), using _Pred_Diff _Count;for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; ){// divide and conquer by quicksort_STD pair<_RanIt, _RanIt> _Mid =_Unguarded_partition(_First, _Last, _Pred);_Ideal /= 2, _Ideal += _Ideal / 2;// allow 1.5 log2(N) divisionsif (_Mid.first - _First < _Last - _Mid.second){// loop on second half_Sort(_First, _Mid.first, _Ideal, _Pred);_First = _Mid.second;}else{// loop on first half_Sort(_Mid.second, _Last, _Ideal, _Pred);_Last = _Mid.first;}}if (_ISORT_MAX < _Count){// heap sort if too many divisions_STD make_heap(_First, _Last, _Pred);_STD sort_heap(_First, _Last, _Pred);}else if (1 < _Count)_Insertion_sort(_First, _Last, _Pred);// small}It looks so cryptic :). I went and tried understanding make_heap,sort_heap etc but even trying to read those code makes me dizzy.;Quote:Original post by Black KnightHoly cow! That is 3x faster. Is that speed gain only from intro sort or other tricks and optimizations?*** Source Snippet Removed ***It looks so cryptic :). I went and tried understanding make_heap,sort_heap etc but even trying to read those code makes me dizzy.Looks pretty simple to me.   ;  Washu's addition of std::sort is probably showing that your code is less optimal than it could be.Try adding rde::quick_sort and rde::heap_sort to the test and see how fast they perform. Their code should be a lot more readable than std::sort's as well ;)   ;  Well once you get past the pre-underscore madness I'm sure it is simple.