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.

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 598 other followers

%d bloggers like this: