tpop(2.2): Sorting

2.2 Sorting

2011-03-03 Thu

• One of the best all-round sorting algorithms is quicksort, which was invented in 1960 by C. A. R. Hoare. Quicksort is a fine example of how to avoid extra computing. It works by partitioning an array into little and big elements:

• pick one element of the array(the "pivot").
  partition the other elements into two groups:
        "little ones" that are less than the pivot value, and
        "big ones" that are greater than or equal to the pivot value.
  recursively sort each group.

• When this process is finished, the array is in order.

• Quicksort is fast because once an element is known to be less than the pivot value, we don't have to compare it to any of the big ones; similarly, big ones are not compared to little ones. This makes it much faster than the simple sorting methods such as insertion sort and bubble sort that compare each element directly to all the others.

• This quicksort

/* quicksort: sort v[0]..v[n-1] into increasing order */
void quicksort(int v[], int n)
{
        int i, last;
        if (n <= 1) /* nothing to do */
                return;
        swap (v, 0, rand() % n); /* move pivot elem to v[0] */
        last = 0;
        for (i = 1; i < n; i++) /* partition */
                if (v[i] < v[0])
                        swap(v, ++last, i);
        swap(v, 0, last); /* restore pivot */
        quicksort(v, last); /* recursively sort */
        quicksort(v+last+1, n-last-1); /* each part */
}

The swap operation, which interchanges two elements, appears three times in quicksoft, so it is best made into a separate function:

/* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
        int temp;
        temp = v[i];
        v[i] = v[j];
        v[j] = temp;
}

(1) Partitioning selects a random element as the pivot, swaps it temporarily to the front, then sweeps through the remaining elements, exchanging those smaller than the pivot ("little ones") towards the beginning (at location last) and big ones towards the end (at location i) At the beginning of the process, just after the pivot has been swapped to the front, last=0 and elements i=1 through n-1 are unexamined.

(2) At the top of the for loop, element 1 through last are strictly less than the pivot, elements last+1 through i-1 are greater than or equal to the pivot, and element i through n-1 have not been examined yet. Until v[i]>=v[0], the algorithm may swap v[i] with itself; this wastes some time but not enough to worry about.

(3) After all elements have been partitioned, element 0 is swapped with the last element to put the pivot element in its final position; this maintains the correct ordering.

(4) The same process is applied to the left and right sub-arrays; when this has finished, the whole array has been sorted.

How fast is quicksort? In the best possible case,

• the first pass partitions n elements into two groups of about n/2 each.
• the second level partitions two groups, each of about n/2 elements, into four groups each of about n/4.
• the next level partitions four groups of about n/4 into eight of about n/8.
• and so on.

This goes on for about log2 n levels, so the total amount of work in the best case is proportional to n+2× n/2+4× n/4+8× n/8 … (log2 n terms), which is nlog2 n. On the average, it does only little more work. It is customary to use base 2 logarithms; thus we say that quicksort takes time proportional to nlog n.

• This implementation of quicksort is the clearest for exposition, but it has a weakness. If each choice of pivot splits the element values into two nearly equal groups, our analysis is correct, but if the split is uneven too often, the run-time can grow more like n².
• Our implementation uses a random element as the pivot to reduce the chance that unusual input data will cause too many uneven splits. But if all the input values are the same, our implementation splits off only one element each time and will thus run in time proportional to n².