BACK | Advanced Sorting Methods |
NEXT |
PowerPoint presentations:
Sahni's
Lecture 35
Locally maintained slide set
Koffman&Wolfgang,
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
1959, 30-32
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]
DemoShell.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
ShellGame.java
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.
MergeList.html
Merge sort for linked lists — to review the algorithm before examining an array
implementation.
MergeSort.java
Array implementation based on java.util.Arrays.sort(), with test main. [.txt]
[.pdf] [.exe]
MergeSahni.html
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
Sahni's code as accompanying the book: QuickSort.java
DemoQuick.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
Naps.html
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.
p321-hoare.pdf
Local copy of the original publication of the QuickSort algorithm in CACM of
July 1961.
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)
Three
Beautiful Quicksorts — good coders code, great reuse Web page
Three
Beautiful Quicksorts — the video itself