Select

---

Contents

---

The Selection Problem

The selection problem seeks to select the \(k\)-th smallest (largest) element from an unsorted array of elements, and is useful for finding the median, the 25th percentile, say, from a list efficiently, or for indexing into an unsorted array as though it were sorted.

Selection problem: given an unsorted array \(A\) of \(n\) elements and a comparison operation between the elements, return the value of the \(k\)-th smallest element where \(k \lt n\).

---

Sections

• Naive Selection: \(k\)-th smallest element
• Quickselect

---

Figures

• [ w ] 1936-2001 Floyd, Robert W.

• [ w ] 1934----- Hoare, Tony

• [ w ] 1947----- Rivest, Ron

---

Terms

• [ w ] Floyd-Rivest Algorithm

  • https://www.geeksforgeeks.org/floyd-rivest-algorithm/

• [ w ] Introselect (“Introspective Selection”)

• [ w ] Median of Medians

• [ w ] Order Statistic

• [ w ] Quickselect

  • https://www.geeksforgeeks.org/quickselect-algorithm/

• [ w ] Selection Algorithm

  • https://www.geeksforgeeks.org/selection-algorithms/

---