[racket] Looking for feedback on code style

http://programmingpraxis.com/2009/12/11/selection/

On Thu, Sep 9, 2010 at 10:26 AM, David Van Horn <dvanhorn at ccs.neu.edu>wrote:

> On 9/9/10 10:04 AM, Prabhakar Ragde wrote:
>
>> I don't think vectors help very much in this case (median-finding). For
>> the given code, the O(n) access to the middle of the list is dominated
>> by the cost of the sorting, which is at least O(n log n) [*].
>>
>> It is theoretically possible to compute the median in O(n) time, but the
>> method is complicated and not very practical. But sorting definitely
>> does too much work. If only the median (or the kth largest, a problem
>> called "selection") is needed, a method which is both practical and of
>> pedagogical interest stems from adapting Quicksort, which is a good
>> exercise after section 25.2 of HtDP. This has expected cost O(n) on
>> random data, and vectors offer no asymptotic advantage over lists. --PR
>>
>> [*] Technically, "at least Omega(n log n)".
>>
>
> 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.
>
> Thanks!
>
> David
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20100909/64c5f0b7/attachment-0001.html>