The biggest improvement to Quicksort that I know of, is to add Insertion sort (and calls to it), when the sub arrays are small (say 15 to 60 or so, depending on your own system).
imo, no sorter is faster with a small array that is almost already sorted, than Insertion sort. Oddly, Bubble sort is also quick at this specialty.
This is the optimized Quicksort, I have found best (but still clear), so far. I know iMalc (a forum regular) has an optimized one as well, but I haven't tested his version yet.
Code:
//Optimzed Quicksort
void quicksortOpt(int A[], int lo, int hi) {
int i, j, pivot, temp;
if(lo == hi) return;
if((hi - lo) < InsertNum) {
insertionSort(A, lo, hi+1);
return;
}
i=lo;
j=hi;
pivot= A[(lo+hi)/2];
/* Split the array into two parts */
do {
while (A[i] < pivot) i++;
while (A[j] > pivot) j--;
if (i<=j) {
/* using a swap() function gives the same time, as
using the swap code below */
temp= A[i];
A[i]= A[j];
A[j]=temp;
i++;
j--;
}
} while(i<=j);
if (lo < j) quicksortOpt(A, lo, j);
if (i < hi) quicksortOpt(A, i, hi);
}
I have read all kinds of misleading posts regarding fast sorters. They were misleading in the sense that they optimized a particular algorithm, to perform exceptionally well on a particular PC system, (and there are many such optimizations you can make), or their IDEA of a fast sorting algorithm, was untested, and just wasn't that fast.
Those algorithms and optimizations for specific data, or a specific type of computer system, don't interest me. I want to use it on any PC and, I need it to be clear enough that it can be optimized for the specific type of data that will be sorted, if necessary.
To use it, you need to also have an Insertion sort function, and some of those are funky, as well. The one's that don't "shuffle" are hardly different from Bubble sort, imo. Unfortunately, the Bible of C ("The C Programming Language by K&R), has an example of a funky Insertion sort, so it's become fairly commonplace.
Code:
/* a clearer version */
void insertionSort(int A[], int lo, int hi) {
int i, j, val;
j=hi;
for(i=lo+1;i<hi;i++) {
val = A[i];
j = i-1;
while(A[j] > val) {
A[j + 1] = A[j];
--j;
if(j<0) break;
}
A[j+1] = val;
}
/*
puts("\nAfter Insertion Sort:\n");
for(i=lo;i<hi;i++)
printf(" %2d ",A[i]);
getchar();
*/
}