outline-style sorting algorithm

[Delaney, Timothy C (Timothy)]

Thorsten Kampe wrote:

>>>>> foo
>> ['1.0', '1.0.1', '1.1.1', '1.2', '1.9', '1.10', '1.11', '1.20',
>> '1.20.1', '1.30']
>>>>> foo.sort()
>>>>> foo
>> ['1.0', '1.0.1', '1.1.1', '1.10', '1.11', '1.2', '1.20', '1.20.1',
>> '1.30', '1.9'] 
>> 
>> Obviously 1.20.1 should be after 1.9 if we look at this as
>> dot-delimited integers, not as decimal numbers.
> 
> You need some general approach to avoid the DSU thing:
> 
> def funcsort(seq, func):
>     """ sort seq by func(item) """
>     seq = seq[:]
>     seq.sort(lambda x, y: cmp(func(x), func(y)))
>     return seq
> 
> funcsort(foo, lambda x: map(int, x.split('.')))

I've seen you give this advice several times, today, and IMO it's
completely wrong.

DSU is *exactly* what you want to do. If you want to wrap it inside a
general function, that's fine, but DSU is in almost all cases preferred
to passing a comparison function - it's much faster.

    def sorted (seq, cmp=None, key=None):
        """ sort seq by func(item) """
        if key is None:
            seq = seq[:]
        else:
            seq = [(key(e), i, e) for i, e in enumerate(seq)]

        seq.sort(cmp)

        if key is None:
            return seq
        else:
            return [i[-1] for i in seq]

    foo = ['1.0', '1.0.1', '1.1.1', '1.2', '1.9', '1.10', '1.11',
'1.20', '1.20.1', '1.30']

    foo = sorted(foo, key=lambda x: map(int, x.split('.')))
    print foo

Note that Python 2.4 will have DSU as a built-in idiom to `list.sort`
i.e. `list.sort(key=func)` but will be somewhat more efficient than the
above. Likewise there will be a new builtin `sorted` which has exactly
the same semantics as the above - it is stable, and it does not ever
compare the actual value if a key function is supplied - only the key
value (the above also compares the position, but that's an
implementation detail and has no visible effect).

Tim Delaney