Part III · Searching, Sorting and Selection
19. Selection, Order Statistics and Ranking
6 lessons•25 topics•Beginner / Intermediate
6 of 6 lessons published
19.01Lesson
Order statistics
- Minimum/maximum
- Median
- Kth smallest/largest
- Percentiles
- Rank and select
19.021 animated
Quickselect
- Partition-based selection
- Randomized pivots
- Expected linear time
- Worst-case behavior
- Duplicate keys
19.03Lesson
Deterministic selection
- Median-of-medians
- Grouping of five
- Linear worst-case selection
- Correctness intuition
19.043 animated
Heap selection
- Top K largest/smallest
- K-way merge
- Kth in sorted streams
- Running median with two heaps
19.05Lesson
Partial sorting
- Nth element concept
- Partial heap sort
- Sorting only top K
- K closest points
19.061 animated
Inversions and counts
- Count inversions via merge sort
- Reverse pairs
- Count smaller elements after self