Advanced Sorting Methods
Locally maintained slide set
Ch. 10, beginning with slide 15
Link to an animation demonstrating numerous sorting algorithms.
Wikipedia discussion of Shellsort — Applet with simulation at this location referenced in the article
Donald Shell's Original Paper CACM 2, July
Sahni's treatment of Shell's Algorithm Includes a full implementation based on the strategy to reduce the increment by a factor of 2.2
PowerPoint presentation on Shell's Sorting Algorithm. Developed by Bill Clark, revised by Tom Capaul and Tim Rolfe
ShellSort.java Sedgewick's code accompanying the text, amplified. [.txt] [.exe]
Program to show the interleaved arrays of Shell's algorithm under Windows
DemoShell.c Source code (the formatting code does not easily translate)
DemoShell.java Translation into Java (based on Java 1.5.x method printf) [.txt]
DemoShellJ.exe Java jar in an exe wrapper
Experimenting with gap sequences. [.txt]
ShellGame.xls Experimental results (2 through 300, stepping by 1)
ShellTime.gif Plot of time required
ShellCmp.gif Plot of comparisons required
Wikipedia discussion of Mergesort — which has an applet with simulation at the top of the page.
Merge sort for linked lists — to review the algorithm before examining an array
MergeSort.java Array implementation based on java.util.Arrays.sort(), with test main. [.txt] [.pdf] [.exe]
Array merge sort — Link to the .java file
Sahni's code as accompanying the book: MergeSort.java
DemoMerge.exe Drill program to show steps in Mergesort. (C source code)
Reminder: the code from java.util.Arrays.sort() was discussed on the algorithm analysis page.
Wikipedia discussion of Quicksort — which has an applet with simulation at the top of the page.
QuickSort.java Sedgewick's code accompanying the text, with test main. [.txt] [.exe]
QuickSahni.html Quick Sort based on Sahni's DSAAJ, Section 19.2.3 Link to the .java file
youtube video of quicksort
Sahni's code as accompanying the book: QuickSort.java
Java program for tracing Quick Sort [.txt]
DemoQuickRun.txt Specimen execution for n=16
DemoQuick.exe Java jar in an exe wrapper thanks to JSmooth
DRILLSEQ.EXE Program giving random digits for drill purposes
Alternative partitioning algorithm with somewhat better performance — about a 5% speed-up for arrays of size 10000.
Sorting.ppt This PowerPoint presentation from earlier offerings of this course represents yet another version
LinkedList Linked list implementation flowing from Wikipedia pseudocode with explicit lists lesser and greater
Tony Hoare's home page
Note: as of 9 Nov 2009, http://research.microsoft.com/en-us/labs/cambridge/default.aspx still lists him as a member of the Programming Principles and Tools group, though his home page is time-stamped 11 October, 1999. Inevitable Wikipedia page.
Local copy of the original publication of the QuickSort algorithm in CACM of
HoareCACM.jpg Local copy extracting just algorithms 63 through 65. Same embedded in Word.
Hoare.java [.txt] Hoare's original algorithm translated into Java (without goto statements)
Hoare_Cmpr_J.pdf Local copy of the original discussion, published in the Computer Journal in 1962.
Optimizations Robert Sedgewick's article "Implementing Quicksort Programs", CACM October 1978
TunedQuickSort.java Collecting together several optimizations into one implementation. [.txt] [.exe]
Enrichment Material (not subject to examination)
Non-comparison-based Sorting Algorithm: Radix Sort
Partition to Solve Another Problem
In Tony Hoare's original publication of the QUICKSORT algorithm (as Algorithm 64 within the Collected Algorithms of the ACM, following Algorithm 63, PARTITION), he also included Algorithm 65, "FIND". This has been more recently called the "Kth element" algorithm: within an array of unsorted data, determine the value that would occur in position K if the array were sorted.
The obvious solution (operating in O(n log n) time) is to sort the array and then actually do the subscripting. One can, however, use the partition algorithm to partially reorder the array, so that only segments of the array that contain the subscript in question undergoing finer and finer reordering. If the data are well-behaved (in other words, would be sorted by QuickSort in (n log n) time) the item can be found in linear time. A common occurrence of this problem is determining the median of a set of values, something that occurs in image processing.
Sahni's Lecture 36: Selection and closest pair of points.
Kth.txt Algorithm by itself in a text file
QuickSortAmpl.java Koffman & Wolfgang's QuickSort amplified to include Kth
BenchKth.java Benchmark program to exercise kth versus full quick-sort [.txt]
MyComparable.java Required by BenchKth.java
DemoKth.java Program to animate the Kth element (like DemoQuick above) [.txt]
DemoKth.exe Java jar in an exe wrapper
Kth.xls Excel workbook with experimental results
AvgCmp.gif Plot of average comparisons required
10Ktime.gif Plot of time required on idaho.ewu.edu to do 10,000 runs per size
Bad Idea Example What if we used "Kth element" to force partitioning on the median all the time?
Merge Sort Options Variations on the merge sort algorithm touched on earlier (Algorithm Analysis, Recursion)
Beautiful Quicksorts — good coders code, great reuse Web page
Three Beautiful Quicksorts — the video itself