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
