Sorting without transitivity

[Frank Niessink]

On Fri May 02 00:35:15 2003, Anton Vredegoor wrote:

> However, now that the else clause is visible, the implementation below
> seems more natural.
> 
> class TopList(list):
>     ''' Topological list class. This class uses topological sort to
>         sort its contents. List items should provide __lt__ and 
>         __eq__ methods. '''
>         
>     def topSort(self):
>         self[:] = [self.popMin() for i in range(len(self))]
> 
>     def popMin(self):
>         return self.pop(self.findMin())
> 
>     def findMin(self):
>         R = range(len(self))
>         i = R.pop(0)
>         while True:
>             for j,k in enumerate(R):
>                 if self[k] < self[i]:
>                     i = R.pop(j)
>                     break
>             else:
>                 return i

Maybe it's just me, but I'm utterly confused by findMin(). I think
it's partly because of the i, j and k variable names that don't convey
any intention, but also because of the things you do with R: enumerate 
a list of indeces??

It does pass my tests though, I'll have to give you that :-)

Cheers, Frank

-- 
Very few things actually get manufactured these days, because in an infinitely
large Universe such as, for instance, the one in which we live, most things
one could possibly imagine, and a lot of things one would rather not, grow
somewhere.
	-- Douglas Adams, 'Life, the Universe, and Everything'