This week the heavy lifting in terms of presenting material is going to be done by a historical set of videos instead of screencasts by me. The video was originally a single production called Sorting out Sorting. It was created by Ronald Baecker at the University of Toronto in 1981. This was early days for both computer animation and algorithm visualization. The video's animation (and sound) techniques were quickly superceded by Hollywood, but the visualizations are still very helpful in understanding how the algorithms work and indeed "set the stage for much of what has followed in the evolution of algorithm visualization (AV)."*
The video describes the operation and performance of nine classic sorting algortihms, 3 each in 3 families.
| Families | ||
|---|---|---|
| Insertion Sorts | Selection Sorts | Exchange Sorts |
| Linear insertion | Straight selection | Bubble sort |
| Binary Insertion | Tree sort | Shaker sort |
| Shell sort | Heap sort | Quicksort |
I have italicized the names of the ones we will implement and compare. This week we will do the first four. In two weeks we will return to the topic of sorting and implement the Quicksort and Heap Sort algorithms.
You can view the video in segments on You Tube: part 1, part 2, part 3, part 4.
Happy viewing!
* http://portal.acm.org/citation.cfm?id=1384319