## Quicksort

This function implements the quicksort algorithm.

Quicksort works by choosing an arbitrary element in the array and then dividing the array into two parts: The first part contains all elements less than or equal to the chosen element, and the second part contains all elements greater than the chosen element. The chosen element is then swapped into the spot between the two parts (known as the pivot point), which is its proper spot in the ultimately sorted array. The function is then called recursively twice—once on each part—to complete the sort.

Assume that the stack is deep enough that recursion will not cause a stack overflow when properly processing any array that is passed to the function.

The function declares an interface `quickcompare`, which has a single
method `compare()`. This method is passed two instances of the class
`Object` (which, in Java, is the root of the class hierarchy, and thus a
superclass of any object), and returns a negative, zero, or positive number if
the first parameter is less than, equal to, or greater than the second
parameter, respectively. This is how the equivalent of function pointers can be
supported in Java. To use the `Quicksort` class, you first declare a
class that implements the `quickcompare` interface in an appropriate way
for the data you want to sort, such as this one for `String` objects

private static class StringComp implements quickcompare { public int compare(Object a, Object b) { return ((String)a).compareTo((String)b); } }

and then pass an instance of that class to `quicksort()`

public static void main(String[] args) { quicksort( args, 0, args.length-1, new StringComp()); }

(In this example, `StringComp` is declared as `static` so it
can be called from `main()`, which is also `static`.)

Note that to make recursion easier, `quicksort()` defines the
`end` parameter inclusively, thus the need to pass `args.length-1`
in the previous call.

### Source Code

1.public class QuickSort {2.3.public interface quickcompare {4.public int compare(Object a, Object b);5.}6.7.// Declare it static since it does not operate8.// on class member variables (there aren't any).9.10.public static void quicksort(11.Object[] array,12.int start,13.int end,14.quickcompare qc) {15.16.if (start < end) {17.18.Object temp;19.int pivot, low, high;20.21.//22.// Partition the array.23.//24.25.pivot = start;26.low = start+1;27.high = end;28.while (true) {29.while ((low < high) &&30.(qc.compare(array[low],31.array[pivot]) <= 0)) {32.++low;33.}34.while ((high >= low) &&35.(qc.compare(array[high],36.array[pivot]) > 0)) {37.--high;38.}39.if (low < high) {40.temp = array[low];41.array[low] = array[high];42.array[high] = temp;43.} else {44.break;45.}46.}47.temp = array[pivot];48.array[pivot] = array[high];49.array[high] = temp;50.51.// Now sort before and after the pivot.52.53.quicksort(array, start, high, qc);54.quicksort(array, high+1, end, qc);55.}56.}57.}

### Suggestions

What can you say about the relationship between

`low`and`high`during the main`while()`loop? Can`low`ever be greater than`high`?What is the goal at line 33? What is the goal at line 38?

At the end of the loop, how are

`low`and`high`related? What types of inputs would cause different situations at the end of the loop?Think of the empty, trivial, and already solved inputs for this code.

Because the code is called recursively, how can you be sure that it will ever terminate?

### Hints

Assume an implementation of `quickcompare` that compares objects of
type `Integer`. (Recall that `Integer` wraps the primitive
`int` type. The array has to be of type `Integer` because
`quickcompare` needs to compare a subclass of `Object`.) Walk
through the code with the following inputs:

- Array is unsorted, no duplicates:
array == [ Integer(3), Integer(1), Integer(4), Integer(5), Integer(2) ]; start == 0 end == 4

- Array contains only two duplicates:
array == [ Integer(4), Integer(4) ] start == 0 end == 1

- Array has the largest number in the first element (important because the
value of the first element is the pivot chosen on the first pass):
array == [ Integer(6), Integer(3), Integer(5) ] start == 0 end == 2

### Explanation of the Bug

The first of the two recursive calls, on line 53, is too expansive. It reads as follows:

quicksort(array, start, high, qc);

Recall that the pivot element was just swapped into position `high`.
Because of the way the call is written, it includes the pivot element in
the elements sorted by the recursive call. Normally, this won't cause
problems—the pivot element is less than any of the elements in the second
group (the one recursively sorted by the call on line 54), and can be equal to
elements in the first group (the one being sorted by this call), so it is
technically correct to lump it in with the first group.

The problem, however, is that for certain arrays, `high` never changes
from the initial value that's assigned to it (which was `end`), and
`start` never changes during the function, so the recursive call might be
attempting to sort the exact same range as the outer call. This means that it
continues to recurse, never shortening the array it tries to sort, and
eventually overflows the stack.

For example, the second hint causes infinite recursion. In practice, this bug
causes infinite recursion when two or more elements of the array are of equal
value (as reported by the `quickcompare` method). That's because the
bug happens when `array[high]` and `array[pivot]` have the same
value on some iteration of the loop.

The fix is to not include the pivot element in the recursive sort, because the pivot element is in its proper place in the array. Line 53 should read as follows:

quicksort(array, start, high-1, qc);

This bug's type could be debated, but I classify it as **A.logic**
because it involves a particular set of inputs that the algorithm does not
handle correctly.