We all know that Quicksort is one of the fastest algorithms for sorting. It's not often, however, that we get a chance to see exactly how fast Quicksort really is. The following applets chart the progress of several common sorting algorthms while sorting an array of data. (This is inspired by the algorithm animation work at Brown University and the video Sorting out Sorting from the University of Toronto (circa 1970!).)
| Bi-Directional
Bubble Sort (implemented by James Gosling) Bi-Directional BubbleSort is like BubbleSort except that it alternates between "bubbling" large elements to the right and small elements to the left. |
|
| Shaker Sort (implemented by Jason Harrison) ShakerSort is like SelectionSort in that it passes over the unsorted part of the array to select the next element(s) to add to the sorted part. It differs in that with each pass it looks for the smallest and the largest remaining element. It then moves the smallest element into its position at the left end of the array and the largest element into position at the right end. Thus the sorted part of the array grows from each end. |
|
| In-Place Merge Sort (implemented by Jason Harrison) This version of MergeSort does not use an extra array for the merging step. This slows it down dramatically. |
|
| Comb Sort 11 (implemented by Jason Harrison) CombSort performs a BubbleSort, but with large gaps between the elements it compares. This has the effect of moving the exchanged elements larger distances towards its ultimate destination. During successive passes the gap between elements it compares is reduced. During the last pass, the gap is 1 -- the same as BubbleSort. |
|
| Quick Sort with
Bubblesort (implemented by Jim Boritz) This version of QuickSort uses BubbleSort to sort small regions of the array. |
|
| Enhanced Quick Sort (implemented by Jim Boritz) Enhanced QuickSort is the same as QuickSort, but when the region to be sorted is 4 or less it uses a sorting algorithm which has no loops (and only works for arrays of size 4 or less). |
|
| Fast Quick Sort (implemented by Denis Ahrens) This version of QuickSort chooses its pivot as the median of the first, middle, and last elements. This helps give good performance on sorted or nearly sorted data. It also leaves small subarrays unsorted until the very end when it runs InsertionSort over the entire array to move elements to their final place. |
|
If you're going to make a copy of this demo, you'll need to also copy the the SortAlgorithm class and the SortItem class.
Sorting routines to be added:
Change History:
| James Gosling, jag@firstperson.com | Original demonstration. |
| Jason Harrison, harrison@cs.ubc.ca Jim Boritz, boritz@cs.ubc.ca | Further modifications, additional sorts. Hosted at http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html. |
| Guido Bunsen | |
| Jean-Luc Duprat | Rebuilt this page for Netscape 2.0 and recompiled the applets with the JDK. |
| Byron Weber Becker, bwbecker@uwaterloo.ca |
|