Hoare FIND algorithm (``quickselect'')
The partitioning idea of Quicksort can also be used to find the $j$-th element of a file. It can be generalized to find a given set of elements. Finding all of the elements is equivalent to sorting. We find explicit expressions for the average number of passes (recursive steps) and comparisons. As a corollary, we get the results of Mahmoud and Lent. A median-of-three partitioning strategy can also be used in the find algorithm. In this case, we also find (complicated) explicit expressions for the average passes and comparisons.