Re: [9fans] ports from GPL

[erik quanstrom <quanstro@quanstro.net>]

interesting.  off the top of my head i saw two similar sorts on
the tiac.net (below). there was one that picked a random i, j
to compare.  but you have the added advantage of computing each
full solution in advance.  there was at least one O(N^3) algorithm
that used an auxillary bit array to keep track of itself.

- erik

On Sat Mar 18 12:48:23 CST 2006, 9nut@9netics.com wrote:
> has anyone done a lotterysort? something like:
>
> array lotterysort(array a) {
> 	forever {
> 		array b = randomize(a)
> 		int i = 1
> 		while (b[i] > b[i-1] && i < size(b))
> 			i++
>
> 		if (i >= size(b)) return b
> 	}
> }
>
> > references:
> > 	http://home.tiac.net/~cri/2001/badsort.html
> > 	http://www.iq0.com/duffgram/silly.c
> >
> > - erik
> >
> > On Sat Mar 18 08:05:10 CST 2006, quanstro@quanstro.net wrote:
> >
> >> actually i think rtl ends up doing this: (quoted from tom duff's
> >> sillysort)
>