Module: Quicksort

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

Prerequisite Modules

Complex Sorting Algorithms

Heapsort, Quicksort, Mergesort.

Learning Outcomes

Define and characterize behavior of the quicksort algorithm, including:

Writing applications using quicksort.
Graphically representing the behavior of quicksort on various data sets.

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