(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-boun...@racket-lang.org [mailto:users-boun...@racket-lang.org] On Behalf Of Phil Bewig Sent: 09 September 2010 17:34 To: David Van Horn Cc: users@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 <dvanh...@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
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
