Java Reference
In-Depth Information
public static void quicksort3(int[] A, int lo, int hi) {
Stack S = new Stack();
S.push(new NodeData(lo, hi));
int stackItems = 1, maxStackItems = 1;
while (!S.empty()) {
--stackItems;
NodeData d = S.pop();
if (d.left < d.right) { //if the sublist is > 1 element
int dp = partition2(A, d.left, d.right);
if (dp - d.left + 1 < d.right - dp) { //compare lengths of sublists
S.push(new NodeData(dp+1, d.right));
S.push(new NodeData(d.left, dp));
}
else {
S.push(new NodeData(d.left, dp));
S.push(new NodeData(dp+1, d.right));
}
stackItems += 2; //two items added to stack
} //end if
if (stackItems > maxStackItems) maxStackItems = stackItems;
} //end while
System.out.printf("Max stack items: %d\n\n", maxStackItems);
} //end quicksort3
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
public static void swap(int[] list, int i, int j) {
//swap list[i] and list[j]
int hold = list[i];
list[i] = list[j];
list[j] = hold;
} //end swap
} //end class Quicksort3Test
class NodeData {
int left, right;
Search WWH ::




Custom Search