In computer science it is often desirable to return the i-th smallest element. This obviously can be done with sorting the items and returning the i-th element in the sorted list; however, if the list requires a comparison based sort algorithm, we would need a better way to accomplish this in linear time. The procedure select, returns the i-th smallest element in linear time, O(n). - Divide
the n elements of the input array into partitions of 5 elements, which
would yield ⌊n/5⌋ partitions of 5 elements and at most one partition of
the remaining n mod 5 elements.
- Find the median of each partition by sorting each, utilizing Insertion sort.
- Use Select recursively on these medians to find the median-of-medians.
- Partition
the input around the median-of-medians using a modified version of
partition subroutine of Quicksort that would take the pivot as an input.
- If
i = median-of-medians then return the median-of-medians.Otherwise, use
Select recursively using the low side if i < median-of-medians,
otherwise the high side.
| 