Advanced Sorting Methods


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         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)      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.

MergeList.html        Merge sort for linked lists — to review the algorithm before examining an array implementation.       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:

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.       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:     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, 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.   [.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  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   Koffman & Wolfgang's QuickSort amplified to include Kth            Benchmark program to exercise kth versus full quick-sort  [.txt]   Required by             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 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