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.

About these ads

Pages: 1 2

4 Responses to “Quick Sort”

  1. Quicky python solution:

    def qsort(A):
    if (len(A) < 2):
    return A
    else:
    return qsort(filter(lambda x: x A[0], A[1:]))
    [/sourcecode]

  2. Whoops messed up the formatting.
    Quicky python solution:

    def qsort(A):
    	if (len(A) < 2):
    		return A
    	else:
    		return qsort(filter(lambda x: x <= A[0], A[1:])) + [A[0]] + qsort(filter(lambda x: x > A[0], A[1:]))
    
  3. Jebb said

    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;
    }
  4. Vikas Tandi said

    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;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 645 other followers

%d bloggers like this: