Reading material

Pages 209-213, 215-221.

Additional material

Proposition 6.5 PostScript PDF
Priority Queue Sort PostScript PDF

Running time of selection sort
Phase 1
n removals from sequence: O(n)
n insertions into priority queue: O(n)
Phase 2
n removals from priority queue: O(n2)
n insertions into sequence: O(n)

USPriorityQueue.java
SSPriorityQueue.java
Item.java
Comparator.java
IntegerComparator.java
PairOfInt.java
Lexicographic.java