sorting list of complex numbers

[Gabriel Genellina]

En Tue, 18 Nov 2008 08:41:58 -0200, Paul Rubin  
<"http://phr.cx"@nospam.invalid> escribió:

> skip at pobox.com writes:
>> but how do I then do a secondary sort by the imaginary part,...
>> Is there a way to do this using just the key arg, no extra data  
>> structures?
>
> Clever solutions involving multiple sorts aside, I think what they
> really want you to do is something like (untested):
>
>     class mkKey(complex):
>        def __lt__(self, other):
>            a = cmp(self.real, other.real)
>            return a if a else cmp(self.imag, other.imag)
>
> then:
>
>     yourlist.sort(key=mkKey)
>
> for fancier structures you'd need a full blown class implementation
> with an init method.  Either way you end up temporarily allocating a
> lot of extra structures, but at least they're not all in memory
> simultaneously like in the DSU pattern.

Yes, the keys for all items in the list are all created when the sort  
begins, and live until the sort finishes. list.sort(key=...) is actually  
implemented using the DSU pattern, something like this:

for i in range(len(alist)):
   alist[i] = (key(alist[i]), alist[i])
# ...sort items...
for i in range(len(alist)):
   alist[i] = alist[i][1]

except a custom `sortwrapper` object is used instead of a 2-item tuple.

-- 
Gabriel Genellina