Thread: Algorithm to find the median number

This is an algorithm to find the median number of a sequence of numbers, it works in linear time in average case: Quickselect. (It can even find the n:th smallest element)

But I think this algorithm works in linear time in all cases: BFPRT. But that depends on the Median of Medians algorithm. If the Median of Medians algorithm does find a number that is guaranteed to be greater than or equal to at least X % of the numbers and smaller than or equal to at least X % of the numbers, where X is a constant, then the BFPRT algorithm does work in linear time in worst case, I believe. But what is X and how can you show that? (Then it even works in liear time in worst case when it is going to find the n:th smallest element)

Originally Posted by TriKri

This is an algorithm to find the median number of a sequence of numbers, it works in linear time in average case: Quickselect. (It can even find the n:th smallest element)

But I think this algorithm works in linear time in all cases: BFPRT. But that depends on the Median of Medians algorithm. If the Median of Medians algorithm does find a number that is guaranteed to be greater than or equal to at least X % of the numbers and smaller than or equal to at least X % of the numbers, where X is a constant, then the BFPRT algorithm does work in linear time in worst case, I believe. But what is X and how can you show that? (Then it even works in liear time in worst case when it is going to find the n:th smallest element)

Maybe I should add where X is a constant > 0. By the way, here is some wikipedia links if someone wants to read about the algorithms:
Quickselect, based onm the Quicksort algorithm
BFPRT, uses the Median of Medians algorithm (I believe)