Fixed. See the comment at <span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; "><a href="http://programmingpraxis.com/2009/12/11/selection/" target="_blank" style="color: rgb(0, 0, 204); ">http://programmingpraxis.com/2009/12/11/selection/</a>.</span><div>
<font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br></span></font></div><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;">Prabhakar: You are correct that shuffling once at the beginning is sufficient. But I am interested in your critique of shuffling. Do you know a better way to shuffle a list than to convert it to a vector, shuffle in place, then convert back to a list? You might look at this discussion: <a href="http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/24270db01f684439/e54c99564028efec">http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/24270db01f684439/e54c99564028efec</a>. The list-vector-list method is O(n); any functional method appears to be O(n log n).<br>
</span></font><br><div class="gmail_quote">On Fri, Sep 10, 2010 at 5:22 PM, Jos Koot <span dir="ltr"><<a href="mailto:jos.koot@telefonica.net">jos.koot@telefonica.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
The bug is clear, I think. When a chosen pivot element results into two<br>
partitions of which one is empty and the other other one contains all<br>
elements left so far, it is obvious that another pivot element must be<br>
chosen, or else we obtain the same two partitions, one being empty, the<br>
other one containing all numbers left so far, resulting in an infinite loop.<br>
Jos<br>
<div class="im"><br>
> -----Original Message-----<br>
> From: Prabhakar Ragde [mailto:<a href="mailto:plragde@uwaterloo.ca">plragde@uwaterloo.ca</a>]<br>
> Sent: 10 September 2010 23:38<br>
> To: Jos Koot<br>
> Subject: Re: [racket] Looking for feedback on code style<br>
><br>
</div><div class="im">> On 9/10/10 5:21 PM, Jos Koot wrote:<br>
> > (select 3 '(1 1 2 2 3 3 4 4 5 5 6 6 7 7)) with<br>
> > <a href="http://programmingpraxis.com/2009/12/11/selection/" target="_blank">http://programmingpraxis.com/2009/12/11/selection/</a> runs into an<br>
> > infinite loop.<br>
> > I think shuffling beforehand is not enough. The pivot<br>
> element must be<br>
> > choosen randomly from the remaining list of numbers for<br>
> each next partition.<br>
><br>
</div>> Shuffling beforehand should be fine, probabilistically<br>
> speaking (though the method -- converting to a vector, using<br>
> mutation, converting back -- is painful). The code style is<br>
> sufficiently alien to me that I don't want to try to find the<br>
> bug. --PR<br>
<div><div></div><div class="h5"><br>
<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></div>