6. Quicksort

Question 1

Quicksort is popular because it is

Answer 1

not difficult to implement, works well for a variety of different kinds of input data, and is substantially faster than any other sorting method in typical applications. It is in-place (uses only a small auxiliary stack), requires time proportional to N log N on the average to sort N items, and has an extremely short inner loop.

Question 2

The basic algorithm

Answer 2

Quicksort is a divide-and-conquer method for sorting. It works by partitioning an array into two parts, then sorting the parts independently.

Question 3

The crux of the method is the partitioning process, which rearranges the array to make the following three conditions hold:

Answer 3

The entry a[j] is in its final place in the array, for some j.
No entry in a[lo] through a[j-1] is greater than a[j].
No entry in a[j+1] through a[hi] is less than a[j].

Question 4

We achieve a complete sort by partitioning, then recursively applying the method to the subarrays. It is a randomized algorithm, because

Answer 4

it randomly shuffles the array before sorting it.

Question 5

Partitioning

Answer 5

First, we arbitrarily choose a[lo] to be the partitioning item—the one that will go into its final position. Next, we scan from the left end of the array until we find an entry that is greater than (or equal to) the partitioning item, and we scan from the right end of the array until we find an entry less than (or equal to) the partitioning item.
The two items that stopped the scans are out of place in the final partitioned array, so we exchange them. When the scan indices cross, all that we need to do to complete the partitioning process is to exchange the partitioning item a[lo] with the rightmost entry of the left subarray (a[j]) and return its index j.

Question 6

Quick.java

Answer 6

is an implementation of quicksort, using the partitioning method described above.

Question 7

//Quick.java
/**
* The {@code Quick} class provides static methods for sorting an
* array and selecting the ith smallest element in an array using quicksort.
*/
public class Quick {

Answer 7

// This class should not be instantiated.
private Quick() { }

Question 8

//Quick.java
/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {

Answer 8

StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
assert isSorted(a);
}

Question 9

//Quick.java
// quicksort the subarray from a[lo] to a[hi]
private static void sort(Comparable[] a, int lo, int hi) {

Answer 9

if (hi <= lo) return;
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
assert isSorted(a, lo, hi);
}

Question 10

//Quick.java
// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {

Answer 10

int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while (true) {

        // find item on lo to swap
        while (less(a[++i], v)) {
            if (i == hi) break;
        }

        // find item on hi to swap
        while (less(v, a[--j])) {
            if (j == lo) break;      // redundant since a[lo] acts as sentinel
        }

        // check if pointers cross
        if (i >= j) break;

        exch(a, i, j);
    }

Question 11

//Quick.java
// put partitioning item v at a[j]
exch(a, lo, j);

Answer 11

// now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
return j;
}

Question 12

//Quick.java
/**
* Rearranges the array so that {@code a[k]} contains the kth smallest key;
*/
public static Comparable select(Comparable[] a, int k) {

Answer 12

if (k < 0 || k >= a.length) {
throw new IllegalArgumentException(“index is not between 0 and “ + a.length + “: “ + k);
}
StdRandom.shuffle(a);
int lo = 0, hi = a.length - 1;
while (hi > lo) {
int i = partition(a, lo, hi);
if (i > k) hi = i - 1;
else if (i < k) lo = i + 1;
else return a[i];
}
return a[lo];
}

Question 13

//Quick.java
// is v < w ?
private static boolean less(Comparable v, Comparable w) {

Answer 13

if (v == w) return false; // optimization when reference equals
return v.compareTo(w) < 0;
}

Question 14

//Quick.java
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {

Answer 14

Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}

Question 15

//Quick.java
private static boolean isSorted(Comparable[] a) {

Answer 15

return isSorted(a, 0, a.length - 1);
}

Question 16

//Quick.java
private static boolean isSorted(Comparable[] a, int lo, int hi) {

Answer 16

for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}

Question 17

//Quick.java
// print array to standard output
private static void show(Comparable[] a) {

Answer 17

for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}

Question 18

//Quick.java
/**
* Reads in a sequence of strings from standard input; quicksorts them;
* and prints them to standard output in ascending order.
* Shuffles the array and then prints the strings again to
* standard output, but this time, using the select method.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {

Answer 18

String[] a = StdIn.readAllStrings();
Quick.sort(a);
show(a);
assert isSorted(a);

    // shuffle
    StdRandom.shuffle(a);

    // display results again using select
    StdOut.println();
    for (int i = 0; i < a.length; i++) {
        String ith = (String) Quick.select(a, i);
        StdOut.println(ith);
    }
}

}

Question 19

Implementation details:
Partitioning inplace.

Answer 19

If we use an extra array, partitioning is easy to implement, but not so much easier that it is worth the extra cost of copying the partitioned version back into the original.

Question 20

Implementation details:
Staying in bounds.

Answer 20

If the smallest item or the largest item in the array is the partitioning item, we have to take care that the pointers do not run off the left or right ends of the array, respectively.

Question 21

Implementation details:
Preserving randomness.

Answer 21

The random shuffle puts the array in random order. Since it treats all items in the subarrays uniformly, Quick.java has the property that its two subarrays are also in random order. This fact is crucial to the algorithm’s predictability. An alternate way to preserve randomness is to choose a random item for partitioning within partition().

Question 22

Implementation details:
Terminating the loop.

Answer 22

Properly testing whether the pointers have crossed is a bit trickier than it might seem at first glance. A common error is to fail to take into account that the array might contain other keys with the same value as the partitioning item.

Question 23

Implementation details:
Handling items with keys equal to the partitioning item’s key.

Answer 23

It is best to stop the left scan for items with keys greater than or equal to the partitioning item’s key and the right scan for items less than or equal to the partitioning item’s key. Even though this policy might seem to create unnecessary exchanges involving items with keys equal to the partitioning item’s key, it is crucial to avoiding quadratic running time in certain typical applications.

Question 24

Implementation details:
Terminating the recursion.

Answer 24

A common mistake in implementing quicksort involves not ensuring that one item is always put into position, then falling into an infinite recursive loop when the partitioning item happens to be the largest or smallest item in the array.

Question 25

Quicksort uses ~___ compares (and one-sixth that many exchanges) on the average to sort an array of length N with distinct keys.

Answer 25

Quicksort uses ~2 N ln N compares (and one-sixth that many exchanges) on the average to sort an array of length N with distinct keys.

Question 26

Quicksort uses ~___ compares in the worst case, but random shuffling protects against this case.

Answer 26

Quicksort uses ~N2/2 compares in the worst case, but random shuffling protects against this case.

Question 27

Improvements :
Cutoff to insertion sort.

Answer 27

As with mergesort, it pays to switch to insertion sort for tiny arrays. The optimum value of the cutoff is system-dependent, but any value between 5 and 15 is likely to work well in most situations.

Question 28

Improvements :
Median-of-three partitioning.

Answer 28

A second easy way to improve the performance of quicksort is to use the median of a small sample of items taken from the array as the partitioning item. Doing so will give a slightly better partition, but at the cost of computing the median. It turns out that most of the available improvement comes from choosing a sample of size 3 (and then partitioning on the middle item).