Randomized selection

In the previous chapter, we discussed the quicksort algorithm. The quicksort algorithm allows us to sort an unordered list of items, but has a way of preserving the index of elements as the sorting algorithm runs. Generally speaking, the quicksort algorithm does the following:

1. Selects a pivot
2. Partitions the unsorted list around the pivot
3. Recursively sorts the two halves of the partitioned list using steps 1 and 2

One interesting and important fact is that after every partitioning step the index of the pivot will not change, even after the list has become sorted. This means that after each iteration the selected pivot value will be placed at its correct position in the list. It is this property that enables us to be able to work with a not-so-fully sorted list to obtain the i^th smallest number. Because randomized selection is based on the quicksort algorithm...