Deterministic median-finding

39 views
Skip to first unread message

Tom Hayes

unread,
Feb 12, 2010, 3:25:08 PM2/12/10
to CS 510 Randomized Algorithms
Hi class,

Here is a relevant article on wikipedia.

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22

The key point I was missing: Once you find the median of medians, use
that as
a PIVOT to split the list into two parts. We can argue that, by the
median of medians
property, at least a constant fraction of the list will be on each
side of the pivot, and
hence the subproblem remaining is substantially smaller.

Tom

Reply all
Reply to author
Forward
0 new messages