CS 411 Fall 2012
Outline & Supplementary Notes for Friday, September 28, 2012

Outline

Variable size decrease algorithms [L 4.5; 5.6 in 2nd ed]

• Idea
• Quickselect
  • How it works.
  • Partitioning algorithms: Lomuto, Hoare.
  • Write code.
  • Analyze.

Example code: quickselect.cpp.

Supplementary Notes

Quickselect & Introselect

Hoare’s Quickselect is a fine algorithm. It is easy to implement, uses constant additonal space, and has linear-time average performance. However, it is a quadratic-time algorithm; this worst-case behavior can make it a poor choice in many circumstances.

There are linear-time selection algorithms known. In particular, an algorithm known as the Blum-Floyd-Pratt-Rivest-Tarjan Algorithm (catchy name, eh?) does selection in linear time. However, its average-case performance—while still linear—is significantly worse than Quickselect.

David Musser suggested a hybrid algorithm, known as Introselect: we run Quickselect, keeping track of the recursion depth. If this gets too large, then switch to Blum-Floyd-Pratt-Rivest-Tajan. This has essentially the same average-case performance as Quickselect, with a linear-time worst case.