Quick Sort

Description

This algorithm makes multiple passes through the data set. In the first pass, it uses the first item in the list as a "pivot", and then it separates all the items into two groups on either side of the pivot: all the items that are less than the pivot (in no particular order), then the pivot item, then all the items that are greater than the pivot (again, in no particular order). The two groups might be the same size, as in the diagram below, but they might not be.

pivot 0

group 1: less than pivot 0

group 2: greater than pivot 0

In the next pass, it applies the same algorithm to each of the groups created in the previous pass, so we now have 4 groups and 3 pivots. Again, the groups are not guaranteed to be equal in size, and often aren't.

pivot 0

pivot 1

group 1a

group 1b

pivot 2

group 2c

group 2d

This process continues, creating more but smaller groups, until the groups contain just a single item and do not have to be processed further.

Animation
The Visual Sort section of this page contains small-scale, step-by-step animations of several sorting algorithms.

Choose Quick Sort in the first drop-down menu.

Repeatedly click on Step until you have a sense of how the algorithm works. Then click Run and check whether its continued behavior is what you expect.

You can click on the New Sort button to get a new set of random data if you want to repeat the process to understand the algorithm better.

Performance

In each pass, this algorithm parcels all items to one side or another of its current pivot, comparing and swapping roughly N items in each pass. (N is the number of data items to sort. For example, N would be 1000 if the data set contains 1000 items.) How many passes does it need? Well, if the data start out sufficiently random, each group is cut roughly in half in each pass. Ideally, the group sizes go from 1000 to 500, to 250, to 125, to 63, to 32, to 16, to 8, to 4, to 2, to 1, so the number of passes would be log₂(N), also known as lg(N). The actual performance is likely to be somewhat worse because the groups do not divide exactly equally. (The worst case is if the data are sorted before the process begins; the group sizes go from 1000 to 999, to 998, to 997, etc., requiring N passes.)

Code

    // Quick Sort: choose a pivot value and put
    // everything smaller than the pivot to the left and everything bigger than
    // the pivot to the right.  Then do recursive quick sorts on the left
    // half and the right half.
    void sort(int[] data, int numItems)
    {
        // Call a recursive version of the quick sort method, giving the
        // first and last indices of the range of data to sort.
        recSortQ(data, 0, numItems - 1);
    }

    // Recursive Quick Sort: Find a pivot point, separate the data into two
    // chunks (smaller data to the left of the pivot and larger data to the
    // right), and then recursively sort the two chunks.
    void recSortQ(int data[], int startRange, int endRange)
    {
        // If there's only 1 value in the range, then it's sorted wrt itself.
        if ( ( endRange - startRange ) < 1 )
            return;

        // Split the data into two chunks around a pivot point.
        int pivotLoc = pivot(data, startRange, endRange);

        // Now sort the left and right chunks on either side of the pivot.
        recSortQ(data, startRange, pivotLoc - 1);
        recSortQ(data, pivotLoc + 1, endRange);
    }

    // Rearrange the data to have a pivot point
    // somewhere in the middle oof the range, with smaller items to the left
    // and larger items to the right.
    int pivot(int data[], int startRange, int endRange)
    {
        // Find a pivot point.  We'll just choose the first item in the range,
        // but we could choose the last item, a middle item, or the middle
        // value of the first, middle, and last items.
        int pivot = data[startRange];

        // Set up indices to work from the left and the right.
        int leftIndex = startRange + 1;   // Skip the pivot
        int rightIndex = endRange;

        // Rearrange the values around the pivot; smaller values to the left
        // and larger values to the right.  Keep going until the left and right
        // indices meet or cross over.
        while ( leftIndex <= rightIndex )
        {
            // Moving left-to-right, skip over items smaller than the pivot.
            while ( data[leftIndex] <= pivot && leftIndex <= rightIndex)
            {
                leftIndex++;
            }

            // Moving right-to-left, skip over items larger than the pivot.
            while ( data[rightIndex] >= pivot && rightIndex >= leftIndex )
            {
                rightIndex--;
            }

            // If we have a too-big item in leftIndex and a too-small item in
            // rightIndex, swap them.
            if ( leftIndex < rightIndex )
            {
                int temp = data[leftIndex];
                data[leftIndex] = data[rightIndex];
                data[rightIndex] = temp;
                leftIndex++;
                rightIndex--;
            }
        }

        // The two indices have met or crossed over.  We have swapped
        // everything we can, now put the pivot in place.
        if ( rightIndex > startRange )
        {
            data[startRange] = data[rightIndex];
            data[rightIndex] = pivot;
        }

        // Return the pivot location.
        return rightIndex;
    }