[racket] Looking for feedback on code style

(select 3 '(1 1 2 2 3 3 4 4 5 5 6 6 7 7))
with  <http://programmingpraxis.com/2009/12/11/selection/>
http://programmingpraxis.com/2009/12/11/selection/ runs into an infinite
loop.
I think shuffling beforehand is not enough. The pivot element must be
choosen randomly from the remaining list of numbers for each next partition.
Jos


  _____  

From: users-bounces at racket-lang.org [mailto:users-bounces at racket-lang.org]
On Behalf Of Phil Bewig
Sent: 09 September 2010 17:34
To: David Van Horn
Cc: users at racket-lang.org; Prabhakar Ragde
Subject: Re: [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/20100910/9f9eb297/attachment.html>