This chapter is from the book
This chapter is from the book
This chapter is from the book
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 operate
8. // 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.