How to sort a list of strings in reverse order without using reverse=True parameter?

Question

I want to sort a list of strings in reverse order, e.g.:

my_list = ['aaa', 'bbb', 'ccc']

expected result:

['ccc', 'bbb', 'aaa']

I don't want to use sorted(my_list, reverse=True), because in more complex case when filtering by two values it would not work. For example:

my_list2 = [('aaa', 'bbb'), ('aaa', 'ccc'), ('bbb', 'aaa'), ('bbb', 'ccc')]

expected result would be:

[('bbb', 'aaa'), ('bbb', 'ccc'), ('aaa', 'bbb'), ('aaa', 'ccc')]

sorted(my_list2, reverse=True) returns:

[('bbb', 'ccc'), ('bbb', 'aaa'), ('aaa', 'ccc'), ('aaa', 'bbb')]

It is simple with numbers, you can negate the value:

>>> my_list3 = [(1, 2), (1, 3), (2, 1), (2, 3)]
>>> sorted(my_list3, key=lambda x: (-x[0], x[1]))
... [(2, 1), (2, 3), (1, 2), (1, 3)]

But how to do it with strings?

Answer 1

You'll have to sort twice. Python's sort algorithm is stable, which means that elements that are equal keep their relative order. Use this to first sort on the second element (sorting in ascending order), then sort that output again, on only the first element and in reverse order:

sorted(sorted(my_list2, key=lambda t: t[1]), key=lambda t: t[0], reverse=True)

Using operator.itemgetter() instead of lambdas can make this little bit faster (avoiding stepping back in to the Python interpreter for each element):

from operator import itemgetter

sorted(sorted(my_list2, key=itemgetter(1)), key=itemgetter(0), reverse=True)

Demo:

>>> from operator import itemgetter
>>> my_list2 = [('aaa', 'bbb'), ('aaa', 'ccc'), ('bbb', 'aaa'), ('bbb', 'ccc')]
>>> sorted(sorted(my_list2, key=lambda t: t[1]), key=lambda t: t[0], reverse=True)
[('bbb', 'aaa'), ('bbb', 'ccc'), ('aaa', 'bbb'), ('aaa', 'ccc')]
>>> sorted(sorted(my_list2, key=itemgetter(1)), key=itemgetter(0), reverse=True)
[('bbb', 'aaa'), ('bbb', 'ccc'), ('aaa', 'bbb'), ('aaa', 'ccc')]

The general rule is to sort from the innermost element to the outermost element. So for an arbitrary-element-count sort, with a key and a reverse boolean each, you can use the functools.reduce() function to apply these:

from functools import reduce
from operator import itemgetter

def sort_multiple(sequence, *sort_order):
    """Sort a sequence by multiple criteria.

    Accepts a sequence and 0 or more (key, reverse) tuples, where
    the key is a callable used to extract the value to sort on
    from the input sequence, and reverse is a boolean dictating if
    this value is sorted in ascending or descending order.

    """
    return reduce(
        lambda s, order: sorted(s, key=order[0], reverse=order[1]),
        reversed(sort_order),
        sequence
    )

sort_multiple(my_list2, (itemgetter(0), True), (itemgetter(1), False))

Answer 2

If 'my_list2' contains only ASCII, you can try:

sorted(my_list2, key=lambda t: (t[0],[255-ord(c) for c in list(t[1])]), reverse=True)                                
[('bbb', 'aaa'), ('bbb', 'ccc'), ('aaa', 'bbb'), ('aaa', 'ccc')]

Answer 3

Another solution is to create a class with a comparison function to use as key. You only need to define __lt__ used by sort/sorted.

def reverse_key(reverse):
    class C:
        def __init__(self, obj):
            self.obj = obj
        def __lt__(self, other):
            for a, b, r in zip(self.obj, other.obj, reverse):
                if a < b:
                    return not r
                elif a > b:
                    return r
            return False
    return C

This can be used with sort/sorted by

my_list2 = [('aaa', 'bbb'), ('aaa', 'ccc'), ('bbb', 'aaa'), ('bbb', 'ccc')]
sorted(my_list2, key=reverse_key([True, False]))

As seen this allows to call sort/sorted only once. In terms of performance I this could be faster than the accepted answer if each tuple in your list to sort contains a ton of items.

Answer 4

You can do a negative ord on the value and that would work for an ascii string:

>>> sorted(my_list2, key=lambda x: ([-ord(l) for l in x[0]], x[1]))
[('bbb', 'aaa'), ('bbb', 'ccc'), ('aaa', 'bbb'), ('aaa', 'ccc')]

For non-ascii though you'd have choices in how you'd want to sort though:

>>> sorted(my_list2, key=lambda x: ([-ord(l) for l in x[0]], x[1]))
[('ébb', 'écc'), ('bbb', 'aaa'), ('aaa', 'bbb'), ('aaa', 'ccc')]