<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META content="text/html; charset=us-ascii" http-equiv=Content-Type> <META name=GENERATOR content="MSHTML 8.00.7600.16625"></HEAD> <BODY> <DIV dir=ltr align=left><FONT color=#0000ff size=2 face=Arial>(select 3 '(1 1 2 2 3 3 4 4 5 5 6 6 7 7))</FONT></DIV> <DIV dir=ltr align=left><SPAN class=108311721-10092010><FONT color=#0000ff size=2 face=Arial>with <A href="http://programmingpraxis.com/2009/12/11/selection/"><FONT size=3 face="Times New Roman">http://programmingpraxis.com/2009/12/11/selection/</FONT></A> runs into an infinite loop.</FONT></SPAN></DIV> <DIV dir=ltr align=left><SPAN class=108311721-10092010><FONT color=#0000ff size=2 face=Arial>I think shuffling beforehand is not enough. The pivot element must be choosen randomly from the remaining list of numbers for each next partition.</FONT></SPAN></DIV> <DIV dir=ltr align=left><SPAN class=108311721-10092010><FONT color=#0000ff size=2 face=Arial>Jos</FONT></SPAN></DIV><BR> <BLOCKQUOTE style="BORDER-LEFT: #0000ff 2px solid; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; MARGIN-RIGHT: 0px"> <DIV dir=ltr lang=en-us class=OutlookMessageHeader align=left> <HR tabIndex=-1> <FONT size=2 face=Tahoma><B>From:</B> users-bounces@racket-lang.org [mailto:users-bounces@racket-lang.org] <B>On Behalf Of </B>Phil Bewig<BR><B>Sent:</B> 09 September 2010 17:34<BR><B>To:</B> David Van Horn<BR><B>Cc:</B> users@racket-lang.org; Prabhakar Ragde<BR><B>Subject:</B> Re: [racket] Looking for feedback on code style<BR></FONT><BR></DIV> <DIV></DIV><A href="http://programmingpraxis.com/2009/12/11/selection/">http://programmingpraxis.com/2009/12/11/selection/</A><BR><BR> <DIV class=gmail_quote>On Thu, Sep 9, 2010 at 10:26 AM, David Van Horn <SPAN dir=ltr><<A href="mailto:dvanhorn@ccs.neu.edu">dvanhorn@ccs.neu.edu</A>></SPAN> wrote:<BR> <BLOCKQUOTE style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class=gmail_quote> <DIV class=im>On 9/9/10 10:04 AM, Prabhakar Ragde wrote:<BR> <BLOCKQUOTE style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class=gmail_quote>I don't think vectors help very much in this case (median-finding). For<BR>the given code, the O(n) access to the middle of the list is dominated<BR>by the cost of the sorting, which is at least O(n log n) [*].<BR><BR>It is theoretically possible to compute the median in O(n) time, but the<BR>method is complicated and not very practical. But sorting definitely<BR>does too much work. If only the median (or the kth largest, a problem<BR>called "selection") is needed, a method which is both practical and of<BR>pedagogical interest stems from adapting Quicksort, which is a good<BR>exercise after section 25.2 of HtDP. This has expected cost O(n) on<BR>random data, and vectors offer no asymptotic advantage over lists. --PR<BR><BR>[*] Technically, "at least Omega(n log n)".<BR></BLOCKQUOTE><BR></DIV>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.<BR><BR>Thanks!<BR><FONT color=#888888><BR>David</FONT> <DIV> <DIV></DIV> <DIV class=h5><BR>_________________________________________________<BR> For list-related administrative tasks:<BR> <A href="http://lists.racket-lang.org/listinfo/users" target=_blank>http://lists.racket-lang.org/listinfo/users</A><BR></DIV></DIV></BLOCKQUOTE></DIV><BR></BLOCKQUOTE></BODY></HTML>