sort by last then by first

[Andrew Henshaw]

<posted & mailed>

Alex Martelli wrote:

> Jørgen Cederberg wrote:
>    ...
>> When sorting a list by several fields, I use this method:
>> 
>>  >>> names=[['Flintstone', 'Fred'],['Flintstone', 'Wilma'],['Rubble',
>> ... 'Barney'],['Rubble', 'Betty'],['Flintstone', 'Pebbles']]
>>  >>> snames = [ (x[1], x[0], x) for x in names]
>>  >>> snames.sort()
>>  >>> sortednames = [x[-1] for x in snames]
>>  >>> sortednames
>> [['Rubble', 'Barney'], ['Rubble', 'Betty'], ['Flintstone', 'Fred'],
>> ['Flintstone
>> ', 'Pebbles'], ['Flintstone', 'Wilma']]
>>  >>>
>> 
>> I create a list of tuples, where the tuple is ordered in the way I want
>> to sort, i.e. "sort by last then by first". The last element is the
>> original item to be sorted. Sort them, and then extract the original
>> item.
>> 
>> Maybe there are faster and easier ways, but I understand this one.
> 
> There is no substantially faster way than this approach (the "Decorate,
> Sort, Undecorate" idiom, aka DSU) for long-enough lists.  There _are_
> several slight variants that can come in handy sometimes, e.g. inserting
> in each item of sortednames the index into names of the corresponding
> item, in order to make the sort "stable" (items that compare equal on
> all compared fields are then guaranteed to stay in the same order as
> they were originally -- the sort method, per se, is not stable up to
> Python 2.2, and is not guaranteed to remain stable in the future even
> though it is in 2.3).
> 
> I entirely agree that, almost always, DSU is simpler as well as faster
> (when it counts, i.e., for large lists) than the alternatives.  The
> main exceptions come when the sort needs to be ascending on certain
> fields but descending on others -- _then_ DSU gets a bit hairier.
> 
> 
> Alex

The following is an approach that I sometimes use for complicated sorting.  
While certainly slower than DSU, it is very convenient.  This is a modified 
version of the code that I submitted to the Python Cookbook.

Andy

#################

class Sortable:
    sortorder = []
    def __init__(self, **args):
        self.__dict__.update(args)

    def __cmp__(self, other):
        s=[]
        o=[]
        for attr in Sortable.sortorder:
            if attr[0] == '-':
                attr = attr[1:]
                s.append(getattr(other, attr))
                o.append(getattr(self, attr))
            else:
                s.append(getattr(self, attr))
                o.append(getattr(other, attr))
        return cmp(s,o)

    def __str__(self):
        return '\t'.join(['%s: %s' % x for x in self.__dict__.items()])
    

def test():
    print
    p1=Sortable(dob='900420', gender='f', experience=1)
    p2=Sortable(dob='900410', gender='f', experience=1)
    p3=Sortable(dob='900425', gender='m', experience=1)
    p4=Sortable(dob='900425', gender='m', experience=0)
    l=[p1,p2,p3,p4]

    for order in [('-gender', 'dob'),
                  ('dob', 'experience'),
                  ('-experience', 'dob')]:
        print order
        Sortable.sortorder = order
        l.sort()
        for i in l:  
            print i


if __name__ == '__main__':
    test()

>>> 
('-gender', 'dob')
dob: 900425     gender: m       experience: 1
dob: 900425     gender: m       experience: 0
dob: 900410     gender: f       experience: 1
dob: 900420     gender: f       experience: 1
('dob', 'experience')
dob: 900410     gender: f       experience: 1
dob: 900420     gender: f       experience: 1
dob: 900425     gender: m       experience: 0
dob: 900425     gender: m       experience: 1
('-experience', 'dob')
dob: 900410     gender: f       experience: 1
dob: 900420     gender: f       experience: 1
dob: 900425     gender: m       experience: 1
dob: 900425     gender: m       experience: 0