Quick Sort
November 3, 2009
Quick sort was invented by Sir Charles Antony Richard “Tony” Hoare, a British computer scientist and winner of the 1980 Turing Award, in 1960, while he was a visiting student at Moscow State University. Though it has an annoying quadratic worst-case performance, quick sort has expected O(n log n) performance and is significantly faster in practice than most other O(n log n) sorting algorithms, and it is possible to arrange that the worst-case performance almost never happens for real-world data.
Quick sort works as follows: First, an element, called the pivot, is chosen from the array. Then the array is partitioned around the pivot by reordering the array so that all elements less than the pivot come before it and all items greater than the pivot come after it; this puts the pivot element in its final position in the array. Finally, quick sort is called recursively on the less-than and greater-than partitions; the base of the recursion is arrays of zero or one element.
There are many ways to choose the pivot element. Some algorithms choose the first element of the array, or the last; others choose the median of three elements (first, middle, last). Our preference is to choose an element at random, since that virtually eliminates the possibility of quadratic performance (unless there is collusion between the random-number generator and the data).
Likewise, there are many ways to perform the partitioning. One approach, due to Nick Lomuto, uses a single pointer to run through the sub-array, swapping the current element for the last element of the sub-array, which is then decremented, if it is greater than the pivot. Another approach uses two pointers that approach each other, swapping elements when the two pointers cross over the pivot element. Lomuto’s partition is simpler; dual pointers is quicker, but the details are hard to get right.
Your task is to write a function that sorts an array using the quick sort algorithm, using the conventions of a previous exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Quicky python solution:
def qsort(A):
if (len(A) < 2):
return A
else:
return qsort(filter(lambda x: x A[0], A[1:]))
[/sourcecode]
Whoops messed up the formatting.
Quicky python solution:
Ongoing experimentations in C. I’d implemented an integer version of this a few months ago, and I just went back and generalized it now I’ve learned how function pointers and (void *) passing works.
static int swap(void *el1, void *el2, int elemSize) { void *buffer; buffer = (void *)malloc(elemSize * sizeof(char)); assert(buffer); memcpy(buffer, el1, elemSize); memcpy(el1, el2, elemSize); memcpy(el2, buffer, elemSize); free(buffer); } static int partition(void *base, int length, int elemSize, void *pivot, int (*cmpFunc)(void *, void *)) { int i, newIndex; void *elt1, *elt2, *lastElt; lastElt = (char *)base + (length - 1) * elemSize; swap(pivot, lastElt, elemSize); //Move the pivot out of the way newIndex = 0; elt1 = base; for (i = 0; i < length - 1; i++) { //We're storing the pivot at the end!!! elt2 = (char *)base + i * elemSize; if (cmpFunc(lastElt, elt2) < 0) { swap(elt1, elt2, elemSize); newIndex++; elt1 = (char*)base + newIndex * elemSize; } } /*Now we only need to re-insert the pivot (which we've stored at lastElt) *in the array at the proper index *With the numbering used, newIndex is now the index of the first element *"larger" than the pivot *elt1 is still the array element of index newIndex*/ swap(lastElt, elt1, elemSize); return newIndex; } int quisort(void *base, int length, int elemSize, int (*cmpFunc)(void *, void *)) { int pivotNewIndex; void *pivot, *base2; if (length > 1) { srand(time(0)); pivot = (char *)base + (rand() % length) * elemSize; pivotNewIndex = partition(base, length, elemSize, pivot, cmpFunc); base2 = (char *)base + (pivotNewIndex + 1) * elemSize; quisort(base, pivotNewIndex, elemSize, cmpFunc); quisort(base2, length - pivotNewIndex - 1, elemSize, cmpFunc); } return 0; }generating random every is very costly and slows down the algorithm considerably.
I have used the median of three elements instead.
Here is my c implementation
#include <stdlib.h> #include <time.h> #define M 10 void insertion_sort(int arr[], int left, int right); static void swap(int arr[], int i, int j); static int partition(int arr[], int left, int right); static void quicksort_imp(int arr[], int left, int right); /* assume presence of two artificial keys arr[0] = -ve infinity and arr[n+1] = +ve infinity such that arr[0] <= arr[i] <= arr[n+1] for 1 <= i <= n */ void quicksort(int arr[], int left, int right) { /* if array size is small or equal to M than sort it directly by straight insertion sort */ if((right-left-1) > M) quicksort_imp(arr, left+1, right-1); if(M > 1) insertion_sort(arr, left+1, right-1); } static void quicksort_imp(int arr[], int left, int right) { int pivot, mid; /* select pivot element */ mid = (left + right)/2; pivot = (left + mid + right)/3; /* swap pivot element with the first element */ swap(arr, left, pivot); /* partition the array */ pivot = partition(arr, left, right); /* right subfile is greater than or equal to left subfile and both subfiles are greater than M */ if((right - pivot) >= (pivot - left) && (right - pivot) > M && (pivot - left) > M) { /* sort the smaller subfile first to ensure that the stack size doesn't grow more than log N */ quicksort_imp(arr, left, pivot-1); quicksort_imp(arr, pivot+1, right); } /* left subfile is greater than right subfile and also both subfiles are greater than M */ if((pivot - left) > (right - pivot) && (right - pivot) > M && (pivot - left) > M) { /* sort the smaller subfile first to ensure that the stack size doesn't grow more than log N */ quicksort_imp(arr, pivot+1, right); quicksort_imp(arr, left, pivot-1); } /* right subfile is greater than left subfile, right subfile is greater than M and left subfiles is less than or equal to M */ if((right - pivot) > (pivot - left) && (right - pivot) > M && (pivot - left) <= M) { quicksort_imp(arr, pivot+1, right); } /* left subfile is greater than right subfile, left subfile is greater than M and right subfiles is less than or equal to M */ if((pivot - left) > (right - pivot) && (pivot - left) > M && (right - pivot) <= M) { quicksort_imp(arr, left, pivot-1); } /* if both subfile are smaller than M, unwind the stack */ } static int partition(int arr[], int left, int right) { int i, j, key; /* partition the element */ for(i = left, j = right+1, key = arr[left]; ;) { /* compare key with arr[i] */ for(i = i+1; arr[i] < key; i++); /* the loop must terminate with i <= j as arr[j] >= key */ /* compare key with arr[j] */ for(j = j-1; arr[j] > key; j--); /* the loop must terminate with j >= (i-1) as arr[i-1] <= key */ if(j <= i) /* end of partition */ { swap(arr, left, j); break; } swap(arr, i, j); } return j; } void insertion_sort(int arr[], int left, int right) { int i, min; /* move smallest key to left end */ for(i = left+1, min = left; i <= right; i++) if(arr[min] > arr[i]) min = i; swap(arr, left, min); for(i = left+1; i <= right; i++) { int j, key; for(j = i-1, key = arr[i]; arr[j] > key; j--) arr[j+1] = arr[j]; arr[j+1] = key; } } static void swap(int arr[], int i, int j) { int t; t = arr[i]; arr[i] = arr[j]; arr[j] = t; }