Python Data Structures and Algorithms

Randomized selection

In the previous chapter, we examined the quick sort algorithm. The quick sort 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 quick sort 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 step 1 and step 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. It is this property that enables us to be able to work with a not-so-fully sorted list to obtain the ith-smallest number. Because randomized selection ...