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

public NodeData(int a, int b) {
left = a;
right = b;
}
public static NodeData getRogueValue() {return new NodeData(-1, -1);}
} //end class NodeData
class Node {
NodeData data;
Node next;
public Node(NodeData d) {
data = d;
next = null;
}
} //end class Node
class Stack {
Node top = null;
public boolean empty() {
return top == null;
}
public void push(NodeData nd) {
Node p = new Node(nd);
p.next = top;
top = p;
} //end push
public NodeData pop() {
if (this.empty())return NodeData.getRogueValue();
NodeData hold = top.data;
top = top.next;
return hold;
} //end pop
} //end class Stack
In quicksort3 , when partition2 returns, the lengths of the two sublists are compared, and the longer one
is placed on the stack first followed by the shorter one. This ensures that the shorter one will be taken off first and
processed before the longer one.
We also added statements to quicksort3 to keep track of the maximum number of items on the stack at any given
time. When used to sort 100000 integers, the maximum number of stack items was 13. This is less than the theoretical
maximum, log 2 100000 = 17, rounded up.
Suppose quick.in contains the following numbers:
43 25 66 37 65 48 84 73 60 79 56 69 32 87 23 99 85 28 14 78 39 51 44 35
46 90 26 96 88 31 17 81 42 54 93 38 22 63 40 68 50 86 75 21 77 58 72 19