One interesting set of algorithms related to finding elements in an unordered list of items is selection algorithms. Given a list of elements, selection algorithms are used to find the ith smallest element from the list. In doing so, we shall be answering questions that have to do with selecting the median of a set of numbers and selecting the ith smallest or largest element in a list.
In this chapter, we will cover the following topics:
- Selection by sorting
- Randomized selection
- Deterministic selection