Performance and Test, Spring 2008: Episode 2.2

Lecture Friday, February 8, 10—12, room 3A14

Subject : Performance Characteristics of Sorting

Text : 6.6, 6.10, 7.1, 7.2, 7.3, 7.4, 10.0, 10.1, 10.2, 10.3, 10.6. This is an abridged list. See the explanation below [this abridged reading is approx 45 pages, 5 hours]

Downloads: Lecture slides. Demos of Quicksort and of Quicksort partitioning.

Comments: In this lecture we will try to do the impossible: discuss all interesting sorting methods within two hours. We will not cover all the details in the lecture. On the contrary, we will try to extract the information that is most essential from the user perspective. The lecture should give you a good guide to sorting techniques.

The broad coverage of the lecture implies that the reading list spans a huge material. You may find it particularly daunting if you have not studied sorting before. In any case remember that gory details of the sorting algorithms are not the most important for us in this lecture. What you should focus on is the performance characteristics of each of the algorithms and the essential concepts related to sorting algorithms. So the most important sections are 6.6, 7.2, 7.3, 8.6, 10.6.

You should focus on general concepts and properties like stability, in-place, worst-case running time, average running time, space complexity, external sorting, sequential memory access, random memory access, linear sorting, sensitivity to input sequence, etc.

You should read entire chapters 6—10 during the semester (not necessarily before this lecture). Students without algorithmic background should use this opportunity to learn the basic computer science vocabulary and idioms. Sorting is really a fundamental piece of knowledge in this field that exemplifies techniques going way beyond sorting. Students with prior algorithmic training and with programming experience will likely find Sedgewick's presentation non-standard, discussing a lot of practical issues normally ignored in algorithms text. In particular chapters 7 and 8 are two very nice studies of improving the implementation, with a lot of good programming insight.