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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
3 Comments »

3 Responses to “Quick Sort”

  1. Joe Doliner said
    November 10, 2009 at 8:05 AM

    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]

  2. Joe Doliner said
    November 10, 2009 at 8:06 AM

    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
    February 18, 2010 at 11:52 PM

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

Leave a Reply