Carrano.java
Carrano's implementation of partition and quickSort, slightly altered for
benchmarking purposes
Naps.java
Implementation by Thomas Naps (with parition based on single moves, not swaps — mentioned
in Hoare[1962])
Koffman.java
Implementation from Elliot Koffman
Hoare.java
Tony Hoare's original algorithm as published in CACM (July 1961), translated to Java
MergeSort.java For
comparison, a MergeSort implementation by Elliot Koffman
BenchQuick.java Main program to
exercise all five above implementations plus Arrays.sort(), generating a spreadsheet file (CSV format)
Traces.txt Traces of Naps.quickSort comparable with Powerpoint traces of Carrano.quickSort
BenchQuick.xls
Result of a benchmark run (run on wyoming.ewu.edu, a 2 GHz Linux computer)
Compare1.gif
Average number of compareTo calls (range 2 through 128)
Compare2.gif
Average number of compareTo calls (range 32 through 4096)
Time1.gif
Average time (microseconds) (range 2 through 128)
Time2.gif
Average time (microseconds) (range 32 through 4096)
BenchQuick_1.html Slide set with about four figures graphical results
CkPivot.html Examination of some "void choosePivot()" strategies
p321-hoare.pdf
Local copy of Hoare's original publication in CACM (July 1961)
Hoare_Cmpr_J.pdf Local copy of Hoare's
original discussion of the algorithm in the Computer Journal of 1962.
Hoare's home page
As a senior researcher with Microsoft Research in Cambridge (England) — dated 11 October 1999.
Note: as of 26 May 2005, http://research.microsoft.com/aboutmsr/visitmsr/cambridge/ still lists him as a member of the Programming Principles and Tools group.
