From mboxrd@z Thu Jan  1 00:00:00 1970
Message-ID: <e12b9977fbd25026b38c9729cc44cc49@quanstro.net>
From: erik quanstrom <quanstro@quanstro.net>
Date: Sat, 18 Mar 2006 13:01:26 -0600
To: 9fans@cse.psu.edu
Subject: Re: [9fans] ports from GPL
MIME-Version: 1.0
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit
Topicbox-Message-UUID: 18be79a8-ead1-11e9-9d60-3106f5b1d025

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)
>