Fixed. See the comment at http://programmingpraxis.com/2009/12/11/selection/.
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: http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/24270db01f684439/e54c99564028efec. The list-vector-list method is O(n); any functional method appears to be O(n log n). On Fri, Sep 10, 2010 at 5:22 PM, Jos Koot <jos.k...@telefonica.net> wrote: > The bug is clear, I think. When a chosen pivot element results into two > partitions of which one is empty and the other other one contains all > elements left so far, it is obvious that another pivot element must be > chosen, or else we obtain the same two partitions, one being empty, the > other one containing all numbers left so far, resulting in an infinite > loop. > Jos > > > -----Original Message----- > > From: Prabhakar Ragde [mailto:plra...@uwaterloo.ca] > > Sent: 10 September 2010 23:38 > > To: Jos Koot > > Subject: Re: [racket] Looking for feedback on code style > > > > On 9/10/10 5:21 PM, Jos Koot wrote: > > > (select 3 '(1 1 2 2 3 3 4 4 5 5 6 6 7 7)) with > > > 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. > > > > Shuffling beforehand should be fine, probabilistically > > speaking (though the method -- converting to a vector, using > > mutation, converting back -- is painful). The code style is > > sufficiently alien to me that I don't want to try to find the > > bug. --PR > > > _________________________________________________ > For list-related administrative tasks: > http://lists.racket-lang.org/listinfo/users >
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
