I have been doing my homework which is to compare a bunch of sorting algorithms, and I have came across a strange phenomenon. Things have been as expected: insertionsort winning for something like table of 20 ints, otherwise quicksort outperforming heapsort and mergesort. Up to a table of 500,000 ints (stored in memory). For 5,000,000 ints (still stored in memory) quicksort becomes suddenly worse then heapsort and mergesort. Numbers are always uniformly distributed random, windows virtual memory turned off. Anyone has an idea what could be the cause of that?
void quicksortit(T *tab,int s) {
if (s==0 || s==1) return;
T tmp;
if (s==2) {
if (tab[0]>tab[1]) {
tmp=tab[0];
tab[0]=tab[1];
tab[1]=tmp;
}
return;
}
T pivot=tab[s-1];
T *f1,*f2;
f1=f2=tab;
for(int i=0;i<s;i++)
if (*f2>pivot)
f2++;
else {
tmp=*f1;
*f1=*f2;
*f2=tmp;
f1++; f2++;
}
quicksortit(tab,(f1-1)-tab);
quicksortit(f1,f2-f1);
};
You algorithm starts failing when there are many duplicates in the array. You only noticed this at large values because you have been feeding the algorithm random values which have a large span
( I'm assuming you used rand() with: 0 - RAND_MAX ), and that problem only appears with large arrays.
When you try to sort an array of identical numbers( try sorting 100000 identical numbers, the program will crash ) you will first walk through the entire array superfluously swapping elements. Then you split the array into two, but the large array has only been reduced by 1:
v
quicksortit(tab,(f1-1)-tab);
Thus your algorithm becomes O(n^2), and you also consume a very large amount of stack. Searching for a better pivot, will not help you in this case, rather choose a version of quicksort() that doesn't exhibit this flaw.
For example:
function quicksort(array)
if length(array) > 1
pivot := select middle, or a median of first, last and middle
left := first index of array
right := last index of array
while left <= right
while array[left] < pivot
left := left + 1
while array[right] > pivot
right := right - 1
if left <= right
swap array[left] with array[right]
left := left + 1
right := right - 1
quicksort(array from first index to right)
quicksort(array from left to last index)
Which is a modified version of: http://rosettacode.org/wiki/Sorting_algorithms/Quicksort