Selection Algorithms

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 k^th smallest or largest element from the list. So given a list of data elements and a number (k), the aim is to find the k^th smallest or largest element. The simplest case of selection algorithms is to find the minimum or maximum data element from the list. However, sometimes, we may need to find the k^th smallest or largest element in the list. The simplest way is to first sort the list using any sorting algorithm, and then we can easily obtain the k^th smallest (or largest) element. However, when the list is very large, then it is not efficient to sort the list to get the k^th smallest or largest element. In that case, we can use different selection algorithms that can efficiently produce the k^th smallest or largest element.

In this chapter, we will cover the following topics...