Module: Quicksort

Randomizing, lower bounds on comparison sorts, counting sort, radix sort, bucket sort.

Learning Outcomes

Understand quicksort

Understand the quicksort algorithm and how it differs from mergesort.

Readings

Introduction to quicksort

Basic ideas about quicksort

Screencast Suthers 24 min

Quicksort: Randomization and analysis

Randomizing and analyzing quicksort

Screencast Suthers 23 min

Bounds on sorting

Lower bounds on comparison sorts, and O(n) sorts

Screencast Suthers 20 min

CLRS 7 - Quicksort

Description and performance of quicksort, a randomized version, and analysis.

Textbook 20 pages

CLRS 8 - Sorting in linear time

Lower bounds for sorting, counting sort, radix sort, bucket sort.

Textbook 22 pages

Notes on Quicksort

Notes on quicksort

Notes

Experiential Learning

Applying your understanding of quicksort (again)

Learn about quicksort (at home).

Homework