Advanced Sorting - Advanced Topics in Java: Core Concepts in Data Structures - page 270

The value of hi is such that the values in num[1..hi] are smaller than those in num[hi+1..n] . Here, the values in
num[1..5] are smaller than those in num[6..10] . Note that 53 is not in its final sorted position. However, this is not a
problem since, to sort the array, all we need to do is sort num[1..hi] and num[hi+1..n] .
We can express the procedure just described as partition2 :
public static int partition2(int[] A, int lo, int hi) {
//return dp such that A[lo..dp] <= A[dp+1..hi]
int pivot = A[lo];
--lo; ++hi;
while (lo < hi) {
do --hi; while (A[hi] > pivot);
do ++lo; while (A[lo] < pivot);
if (lo < hi) swap(A, lo, hi);
}
return hi;
} //end partition2
With this version of partition, we can write quicksort2 as follows:
public static void quicksort2(int[] A, int lo, int hi) {
//sorts A[lo] to A[hi] in ascending order
if (lo < hi) {
int dp = partition2(A, lo, hi);
quicksort2(A, lo, dp);
quicksort2(A, dp+1, hi);
}
}
In partition2 , we choose the first element as the pivot. However, as discussed, choosing a random element will
give better results. We can do this with the following code:
swap(A, lo, random(lo, hi));
int pivot = A[lo];
Here, random can be written like this:
public static int random(int m, int n) {
//returns a random integer from m to n, inclusive
return (int) (Math.random() * (n - m + 1)) + m;
}
9.5.2 Nonrecursive Quicksort
In the versions of quicksort shown earlier, after a sublist is partitioned, we call quicksort with the left part followed
by the right part. For most cases, this will work fine. However, it is possible that, for large n , the number of pending
recursive calls can get so large so as to generate a “recursive stack overflow” error.
In our experiments, this occurred with n = 7000 if the given data was already sorted and the first element was
chosen as the pivot. However, there was no problem even for n = 100000 if a random element was chosen as the pivot.
Another approach is to write quicksort nonrecursively. This would require us to stack the pieces of the list
that remain to be sorted. It can be shown that when a sublist is subdivided, if we process the smaller sublist first, the
number of stack elements will be restricted to at most log 2 n .