Quicksort: Samuel's tutorial
Samuel's tutorial for quicksort covering Lomuto and Hoare partitioning, worst-case analysis and engineering improvements.
Timestamps:
00:00 - Quicksort
01:54 - Quicksort Overview
04:34 - Lomuto Partition
07:11 - Hoare Partition
10:27 - Worst-Case Analysis
12:59 - Balanced Partition Analysis
15:19 - Engineering Improvements
Detailed description:
This video describes the quicksort sorting algorithm, devised by Tony Hoare in 1959. Following a brief history of the algorithm, we describe its runtime complexity: O(n log n) on average, bug O(n^2) in the worst case. We also cover its storage complexity (linear in the worst case, unless tail call elimination is available) and applications.
We then give an overview of the algorithm, explaining how it uses a recursive, divide-and-conquer strategy to partition an array into subarrays around a pivot element.
Next, we describe Python implementations of the Lomuto and Hoare partitioning schemes and illustrate them visually with examples, noting how it's easy to make mistakes when implementing the Hoare partition scheme!
We then analyse the worst-case behaviour of the algorithm by drawing out the unbalanced recursion tree that arises when the pivot falls too close to the end of the array.
Next, we describe how quicksort produces O(n log n) behaviour when the pivot rank is proportional to the length of the array, even for relatively extreme cases.
Lastly, we discuss some engineering improvements to address the poor behaviour of navie quicksort on common cases such as already sorted inputs. These include the "median-of-three" heuristic to select the pivot and using random pivot selection. We also discuss the "killer adversary for quicksort" of McIlroy that induces quadratic behaviour on many quicksort implementations. We close by mentioning the fact that it is possible to ensure that quicksort exhibits O(n log n) complexity, but that the cost of achieving this is prohibitively expensive, so it is rarely done in practice.
Corrections:
10:49 - This formula assumes r is 1-indexed. To compute the runtime recursion cost with r as a 0-indexed variable, the recursion formula is given by: T(n) = T(r) + T(n - r - 1) + Theta(n)
16:23 - This should say "swap with the element at index n-1 (if using Lomuto partition), and swap with the element at index 0 (if using Hoare partition)."
Topics: #quicksort #sorting #algorithms
Python code for lightweight implementations of quicksort can be found here: https://github.com/albanie/algorithms...
Slides (pdf): https://samuelalbanie.com/files/diges...
References for papers mentioned in the video can be found at
http://samuelalbanie.com/digests/2023...
Recommended further reading on this topic:
J. Erickson, "Algorithms", Chap. 2, http://algorithms.wtf/
Cormen et al., "Introduction to algorithms", Chap. 7, MIT press, https://mitpress.mit.edu/978026204630... (2022)
L. Xinyu, "Elementary Algorithms", Chap. 13, https://github.com/liuxinyu95/AlgoXY (2022)
For related content:
YouTube: / @samuelalbanie1
Twitter: / samuelalbanie
Research lab: https://caml-lab.com/