Quick Sort
November 3, 2009
We will provide four quick sorts of increasing sophistication, beginning with this simple quicksort based on Lomuto’s partition:
function swap(A,i,j, t) {
t = A[i]; A[i] = A[j]; A[j] = t }
function qsort(A,lo,hi, i,last) {
if (lo >= hi)
return
swap(A, lo, lo + int((hi-lo+1) * rand()))
last = lo
for (i=lo+1; i<=hi; i++)
if (A[i] < A[lo])
swap(A, ++last, i)
swap(A, lo, last)
qsort(A, lo, last-1)
qsort(A, last+1, hi) }
function sort(A,n) { qsort(A, 1, n) }
Our second version moves swaps inline and eliminates recursion; lo and hi are the endpoints of the current sort range, i and j are pointers to elements of the array, t is a temporary value, s is the recursion stack that stores the previous lo and hi values in each frame, and p is a pointer to the stack:
function sort(A,n, lo,hi,i,j,t,s,p) {
lo = 1; hi = n; p = 2
do {
if (hi > lo) {
j = lo + int((hi - lo + 1) * rand())
t = A[lo]; A[lo] = A[j]; A[j] = t
j = lo
for (i=lo+1; i<=hi; i++)
if (A[i] < A[lo]) {
j++; t = A[j]; A[j] = A[i]; A[i] = t }
t = A[lo]; A[lo] = A[j]; A[j] = t
if ((j - lo) < (hi - j)) {
s[p] = lo; s[p+1] = j - 1; lo = j + 1 }
else { s[p] = j + 1; s[p+1] = hi; hi = j - 1 }
p += 2 }
else { p -= 2; lo = s[p]; hi = s[p+1] }
} while (p > 0) }
Much of the time spent in quick sort is wasted in the recursive calls for small sub-arrays, which involve more pushing and popping the stack than comparing and exchanging array elements. A common fix is to almost-sort the array, leaving small sub-arrays unsorted, then finish the sort by calling insert sort, which is very fast on arrays that are nearly sorted:
function sort(A,n, lo,hi,i,j,t,s,p) {
lo = 1; hi = n; p = 2
do {
if (hi - lo > 10) {
j = lo + int((hi - lo + 1) * rand())
t = A[lo]; A[lo] = A[j]; A[j] = t
j = lo
for (i=lo+1; i<=hi; i++)
if (A[i] < A[lo]) {
j++; t = A[j]; A[j] = A[i]; A[i] = t }
t = A[lo]; A[lo] = A[j]; A[j] = t
if ((j - lo) < (hi - j)) {
s[p] = lo; s[p+1] = j - 1; lo = j + 1 }
else { s[p] = j + 1; s[p+1] = hi; hi = j - 1 }
p += 2 }
else { p -= 2; lo = s[p]; hi = s[p+1] }
} while (p > 0)
for (i=2; i<=n; i++) {
t = A[i]
for (j=i; j>1 && A[j-1] > t; j--)
A[j] = A[j-1]
A[j] = t } }
Our final version of quick sort uses the very fast approaching-pointers partition; beware the details:
function sort(A,n, lo,hi,i,j,t,v,s,p) {
lo = 1; hi = n; p = 2
do {
if (hi - lo > 10) {
i = lo + int((hi - lo + 1) * rand())
t = A[lo]; A[lo] = A[i]; A[i] = t
j = lo + int((hi - lo + 1) * rand())
t = A[hi]; A[hi] = A[j]; A[j] = t
if (A[hi] < A[lo]) {
t = A[lo]; A[lo] = A[hi]; A[hi] = t }
v = A[hi]; i = lo; j = hi
do {
do { i++ } while (A[i] < v)
do { j-- } while (v < A[j])
t = A[i]; A[i] = A[j]; A[j] = t
} while (i < j)
t = A[i]; A[i] = A[hi]; A[hi] = t
if ((i - lo) > (hi - i)) {
s[p] = lo; s[p+1] = i - 1; lo = i + 1 }
else { s[p] = i + 1; s[p+1] = hi; hi = i - 1 }
p += 2 }
else { p -= 2; lo = s[p]; hi = s[p+1] }
} while (p > 0)
for (i=2; i<=n; i++) {
t = A[i]
for (j=i; j>1 && A[j-1] > t; j--)
A[j] = A[j-1]
A[j] = t } }
Quick sort has time complexity O(n log n) unless the data is such that the random choice of pivot is near the ends of the sub-array at each partitioning step. If you are worried about the quadratic worst-case performance, Jon L. Bentley and M. Douglas McIlroy give a solution in their classic 1993 Software—Practice and Experience paper “Engineering a Sort Function” (Volume 23, Number 11, pages 1249–1265).
The code, including the test suite of the previous exercise, is collected at http://programmingpraxis.codepad.org/wTUyljFX, but you can’t run it, since codepad doesn’t provide an Awk interpreter.
Pages: 1 2
Quicky python solution:
[/source]
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; }