About this document
QuickSelect and Deterministic Selection Algorithms by Andrew Lee is a document available to read on EtoBox.
The document summarizes algorithms for selection - finding the ith smallest element in a list. It describes QuickSelect, a randomized selection algorithm that adapts the partition step from quicksort. By randomly picking a pivot and recursively searching only half the list, QuickSelect runs in average case linear time Θ(n). It also describes a deterministic selection algorithm using a median-of-medians technique that guarantees linear worst-case time Θ(n) but has slower constants, making it less efficient t
- Author
- Andrew Lee
- Language
- EN