# [racket] Looking for feedback on code style

On 9/9/10 11:26 AM, David Van Horn wrote:
>* The original post got me interested in median algorithms and I started
*>* to read up on the selection problem. Wikipedia (I know, I know) says the
*>* same thing as you: medians can be computed in O(n) time and points to
*>* selection as the way to do it. But I don't see how to use selection to
*>* achieve a O(n)-time median algorithm -- selection (of the kth
*>* largest/smallest element) is O(n), but that's were k is some fixed
*>* constant. To compute the median, you let k=n/2 (right?), so it's no
*>* longer constant. Can you point me to (or sketch) a O(n) method? Or just
*>* correct me if my reasoning is going astray.
*
Selection can be done in O(n) time regardless of the value of k. It's
not at all obvious, and is a classic result from 1975 or so.
The idea is to split the n elements into sets of 5, find the median of
each set by an ad-hoc method, recursively find the median of the
medians, and use that to partition the n elements as in the Quicksort
method. That is guaranteed to remove about 3n/10 elements (every median
smaller than the median of the medians, and two elements from each
associated set). So you get a recurrence like
T(n) = T(n/5) + T(7n/10) + O(n)
which has a solution that is O(n). The constant is pretty high, though.
It occurred to me while writing my earlier response that, while I have
taught this in a third-year algorithms course (eliciting mostly blank
stares), Racket makes it possible for the average student to actually
implement it. Not that there's any point in doing that, besides being a
nice programming exercise. --PR