2.8 Sorting by Item or by Attribute

Credit: Matthew Wood

2.8.1 Problem

You need to sort a list of (x, y) coordinates by item y, or, more generally, sort a list of objects by any attribute or item.

2.8.2 Solution

You might first think of something like the following class, based on the simple but slow approach of passing a comparison function to the sort method:

class Sorter:
    # Notice how _ _compare is dependent on self._ _whichindex
    def _ _compare(self, x, y):
        return cmp(x[self._ _whichindex], y[self._ _whichindex])

    # Pass the sort function the _ _compare function defined above
    def _ _call_ _(self, data, whichindex = None):
        if whichindex is None :
            data.sort(  )
        else :
            self._ _whichindex = whichindex
            data.sort(self._ _compare)
        return data               # handy for inlining, and low-cost

The trick is to use a bound method that accesses instance state as the comparison function to determine which item (or attribute, but this version deals only with items) to fetch. Unfortunately, this makes the approach nonreentrant and not thread-safe.

Thanks to the faster, more robust, and more flexible DSU idiom, it's not hard to make a more general version that allows attributes as well as items, guarantees a stable sort, is both reentrant and thread-safe, and is speedier to boot:

class Sorter:
    def _helper(self, data, aux, inplace):
        aux.sort(  )
        result = [data[i] for junk, i in aux]
        if inplace: data[:] = result
        return result

    def byItem(self, data, itemindex=None, inplace=1):
        if itemindex is None:
            if inplace:
                data.sort(  )
                result = data
            else:
                result = data[:]
                result.sort(  )
            return result
        else:
            aux = [(d[i][itemindex], i) for i in range(len(data))]
            return self._helper(data, aux, inplace)

    # a couple of handy synonyms
    sort = byItem
    _ _call_ _ = byItem

    def byAttribute(self, data, attributename, inplace=1):
        aux = [(getattr(d[i],attributename),i) for i in range(len(data))]
        return self._helper(data, aux, inplace)

Of course, since the second version doesn't use its "classhood" in any way, making it a class is somewhat peculiar. It would be far more Pythonic, and clearer, to use a module with free-standing functions, rather than an artificial class with instances that have no state.

2.8.3 Discussion

How do you efficiently sort a list of (x, y) coordinates by y? More generally, how do you sort a list of dictionaries, lists, or class instances by a particular item or attribute? I hate not being able to sort by any item or attribute, so I wrote an auxiliary class to do it for me.

The DSU idiom is much faster than passing sort a comparison function, as discussed in other recipes. The second version of Sorter in this recipe uses DSU because of this, as well as auxiliary flexibility advantages. This second version gets no benefit from being a class rather than just a couple of functions, but casting it as a class makes it drop-in compatible with the first, inferior version, which did use some state as a trick (losing reentrancy and thread-safety in the process).

Here is some example code (note that it instantiates the Sorter class only once, another hint that it is not at all an optimal architecture to wrap this functionality as a class):

sort = Sorter(  )

if _ _name_ _ == '_ _main_ _' :
      list = [(1, 2), (4, 8), (0, 3)]
      dict = [{'a': 3, 'b': 4}, {'a': 5, 'b': 2}, {'a': 0, 'b': 0},
          {'a': 9, 'b': 9}]
      dumb = [1, 4, 6, 7, 2, 5, 9, 2, 4, 6]

      print 'list normal:', list
      sort(list, 0)
      print 'sort by [0]:', list
      sort(list, 1)
      print 'sort by [1]:', list

      print

      print "dict normal:", dict
      sort(dict, 'a')
      print "sort by 'a':",  dict
      sort(dict, 'b')
      print "sort by 'b':",  dict

      print

      print 'dumb normal:', dumb
      sort(dumb)
      print 'normal sort:', dumb

Returning the sorted list is cheap (it's just an extra reference, since Python, fortunately, never does any copying of data unless you specifically request it) and offers uniform behavior between in-place and non-in-place cases. Often, we only want to do:

for x in sort(something, inplace=0):

Returning a reference to the sorted data gives us just the right amount of flexibility for this.

2.8.4 See Also

Recipe 2.4 and Recipe 4.10.