c++ - HeapSort vs QuickSort performance -

c++ - HeapSort vs QuickSort performance -

i have 2 implementations of sort, 1 beingness heapsort , sec 1 quicksort. heard, quicksort should have improve average case performance, tests, performs 4 times worse heapsort array of random integers. if integers in interval smaller size of array, performance slower (20 times worse).

do see major flaws in quicksort algorithm?

is there method choosing pivot works type t? tried choosing middle element of array, time performance went ever worse.

template <typename t> void indexedsequence<t>::sort(quicksorttag, comparator<t> comparator, signed long from, signed long to) { adjustsubsequence(from,to); if(to-from < 2) { return; } if(to-from == 2) { if(comparator(operator[](from),operator[](to-1)) == greater_than) { swap(operator[](from),operator[](to-1)); } return; } type pivot = operator[](to-1); signed long left = from, right = to-2; while(true) { while(comparator(operator[](left),pivot) == smaller_than) { ++left; } while((comparator(operator[](right),pivot) != smaller_than) && right > 0) { --right; } if(left >= right--) { swap(operator[](to-1),operator[](left)); break; } else { swap(operator[](left),operator[](right)); } } sort(quicksorttag(),comparator,from,left); sort(quicksorttag(),comparator,left+1,to); }

here test code:

buffer<signed long> buf1; buffer<signed long> buf2; srand(14225); for(signed long = 0; < 100000l; ++i) { buf1.addback(rand()%500000000l); } buf2 = buf1; clock_t t1, t2; t1 = clock(); buf1.sort(heapsorttag(),ascendingcompare); t2 = clock(); std::cout << "time of heap sort: " << (double)(t2-t1)/clocks_per_sec << std::endl; t1 = clock(); buf2.sort(quicksorttag(),ascendingcompare); t2 = clock(); std::cout << "time of quick sort: " << (double)(t2-t1)/clocks_per_sec << std::endl;

output:

time of heap sort: 0.047 time of quick sort: 0.243

c++ algorithm quicksort