Sorting In Python

Oct 1st, 2021 - written by Kimserey with .

Sorting lists in Python is very easy provided that we know how to use the sorting functionalities. Python comes with list.sort() and sorted() function, both behaving somewhat in the same way with the only different that the first one sorts in place whereas the later returns a new sorted list without altering the existing list. In today’s post we will look at different sorting scenarios and how we can achieve them using Python sort functionalities.

Sorting Lists
Sorting Using Custom Key
Sorting By Multiple Values

Sorting Lists

We can sort lists by just using sorted.

In [1]: sorted([10,4,9,1,3])
Out[1]: [1, 3, 4, 9, 10]

It produces another sorted list. The sorting algorith is of time complexity O(nlogn).

We can sort numbers and strings:

In [4]: sorted(["gold", "dollar", "doge"])
Out[4]: ['doge', 'dollar', 'gold']

or sort classes which have an equality implementation:

In [19]: @total_ordering
    ...: class Pet:
    ...:     def __init__(self, name, age):
    ...:         self.name = name
    ...:         self.age = age
    ...: 
    ...:     def __eq__(self, other):
    ...:         return (self.name, self.age) == (other.name, other.age)
    ...: 
    ...:     def __lt__(self, other):
    ...:         return (self.name, self.age) < (other.name, other.age)
    ...: 
    ...:     def __repr__(self):
    ...:         return "{} {}".format(self.name, self.age)

In [20]: p1 = Pet("bento", 1)

In [21]: p2 = Pet("philou", 13)

In [22]: sorted([Pet("philou", 13), Pet("bento", 1)])
Out[22]: [bento 1, philou 13]

One interesting aspect of tuples is that they can be compared with equality checks and Python by default will apply a comparison on each value of the tuples to determine ordering.

In [23]: (1, "hello") == (1, "hello")
Out[23]: True

In [24]: (1, "hello") < (9, "bye")
Out[24]: True

In [25]: (1, "hello") < (1, "bye")
Out[25]: False

So this allows us to sort tuples just by passing them to sorted which would result in the list sorted by the first value, then the second value, and so on until the last value of the tuple.

In [26]: sorted([(1, "hello"), (1, "bye")])
Out[26]: [(1, 'bye'), (1, 'hello')]

As we can see, this mimics an order by then by sorting strategy algorithm.

All sorts we have done earlier were ascending order. sorted also supports descending order with the argument reverse=True.

In [27]: sorted([(1, "hello"), (1, "bye")], reverse=True)
Out[27]: [(1, 'hello'), (1, 'bye')]

In [28]: sorted([1, 5, 3, 10], reverse=True)
Out[28]: [10, 5, 3, 1]

Sorting Using Custom Key

When we do not want to consider the whole item but instead select part of it, for example sorting by the second value of a tuple, we can provide a function or a lambda to the argument key=....

In [31]: sorted([(0, "hello"), (1, "bye")], key=lambda k: k[1])
Out[31]: [(1, 'bye'), (0, 'hello')]

Because this is a function, we can also use it to apply some transformation, for example if the value we want to sort is a string and we want to lower case it, we can provide key=str.lower or if we have integer and want to sort by absolute value we can provide key=abs.

In [34]: sorted(["Hello", "bye"], key=str.lower)
Out[34]: ['bye', 'Hello']

In [37]: sorted([0, -10, -2], key=abs)
Out[37]: [0, -2, -10]

Another trick that can be used to sort descending integers is to multiply the keys by -1 which would put them in descending order.

In [38]: sorted([0, 30, 2, 24, 15], key=lambda k: -k)
Out[38]: [30, 24, 15, 2, 0]

Selecting out of tuple or from attributes also have convenience functions provided by Python under operator module; itemgetter and attrgetter:

In [39]: from operator import itemgetter

In [40]: sorted([(0, "hello"), (1, "bye")], key=itemgetter(1))
Out[40]: [(1, 'bye'), (0, 'hello')]

Similarly we can use attrgetter to avoid having to define a lambda:

In [41]: from operator import attrgetter

In [43]: sorted([Pet("philou", 13), Pet("bento", 1)], key=attrgetter("name"))
Out[43]: [bento 1, philou 13]

Sorting By Multiple Values

We looked at how we could sort with tuple which allow us to execute an order by then by but for more complex filtering, for example if we need to order a list descding then ascending on a second property, it isn’t something that can be done with tuples as the reverse option is applied across the whole ordering with tuples.

For multiple values sorting, we can leverage the fact that sorting is stable in Python which means that the order of the items is preserved if they have the same key. By leveraging that we can then do multiple filtering from the center to the outer filtering.

For example if we want to sort our pets by the name ascending, then age descending:

In [44]: pets = [Pet("philou", 13), Pet("bento", 1), Pet("lili", 2), Pet("lili", 10)]

In [47]: sorted(pets, key=attrgetter("age"), reverse=True)
Out[47]: [philou 13, lili 10, lili 2, bento 1]

In [48]: p = sorted(pets, key=attrgetter("age"), reverse=True)

In [49]: sorted(p, key=attrgetter("name"))
Out[49]: [bento 1, lili 10, lili 2, philou 13]

We start first by the inner sort, which is the sort by age descending. This allows us to place the pets within the correct order by age. Then we sort by the name ascending which provides us what we wanted. And that concludes today’s post!

Conclusion

In today’s post we looked at Python sorting. We first started by looking at the most common usage of sorting with numbers, objects and tuples. We then moved on to sorting by selecting a custom key with a lambda or using one of the operators provided by Python so select a key out of a data structure. And lastly we saw how we could do multi sorting by using repeatedly sorted leveraging the stable aspect of Python sort. I hope you liked this post and I’ll see you on the next one!