Sorting HOW TO¶
Python lists have a built-in list.sort() method that modifies the list in-place. There is also a sorted() built-in function that builds a new sorted list from an iterable.
In this document, we explore the various techniques for sorting data using Python.
Sorting Basics¶
A simple ascending sort is very easy: just call the sorted() function. It returns a new sorted list:
You can also use the list.sort() method. It modifies the list in-place (and returns None to avoid confusion). Usually it’s less convenient than sorted() — but if you don’t need the original list, it’s slightly more efficient.
Another difference is that the list.sort() method is only defined for lists. In contrast, the sorted() function accepts any iterable.
Key Functions¶
Both list.sort() and sorted() have a key parameter to specify a function (or other callable) to be called on each list element prior to making comparisons.
For example, here’s a case-insensitive string comparison:
The value of the key parameter should be a function (or other callable) that takes a single argument and returns a key to use for sorting purposes. This technique is fast because the key function is called exactly once for each input record.
A common pattern is to sort complex objects using some of the object’s indices as keys. For example:
The same technique works for objects with named attributes. For example:
Operator Module Functions¶
The key-function patterns shown above are very common, so Python provides convenience functions to make accessor functions easier and faster. The operator module has itemgetter() , attrgetter() , and a methodcaller() function.
Using those functions, the above examples become simpler and faster:
The operator module functions allow multiple levels of sorting. For example, to sort by grade then by age:
Ascending and Descending¶
Both list.sort() and sorted() accept a reverse parameter with a boolean value. This is used to flag descending sorts. For example, to get the student data in reverse age order:
Sort Stability and Complex Sorts¶
Sorts are guaranteed to be stable. That means that when multiple records have the same key, their original order is preserved.
Notice how the two records for blue retain their original order so that (‘blue’, 1) is guaranteed to precede (‘blue’, 2) .
This wonderful property lets you build complex sorts in a series of sorting steps. For example, to sort the student data by descending grade and then ascending age, do the age sort first and then sort again using grade:
This can be abstracted out into a wrapper function that can take a list and tuples of field and order to sort them on multiple passes.
The Timsort algorithm used in Python does multiple sorts efficiently because it can take advantage of any ordering already present in a dataset.
Decorate-Sort-Undecorate¶
This idiom is called Decorate-Sort-Undecorate after its three steps:
First, the initial list is decorated with new values that control the sort order.
Second, the decorated list is sorted.
Finally, the decorations are removed, creating a list that contains only the initial values in the new order.
For example, to sort the student data by grade using the DSU approach:
This idiom works because tuples are compared lexicographically; the first items are compared; if they are the same then the second items are compared, and so on.
It is not strictly necessary in all cases to include the index i in the decorated list, but including it gives two benefits:
The sort is stable – if two items have the same key, their order will be preserved in the sorted list.
The original items do not have to be comparable because the ordering of the decorated tuples will be determined by at most the first two items. So for example the original list could contain complex numbers which cannot be sorted directly.
Another name for this idiom is Schwartzian transform, after Randal L. Schwartz, who popularized it among Perl programmers.
Now that Python sorting provides key-functions, this technique is not often needed.
Comparison Functions¶
Unlike key functions that return an absolute value for sorting, a comparison function computes the relative ordering for two inputs.
For example, a balance scale compares two samples giving a relative ordering: lighter, equal, or heavier. Likewise, a comparison function such as cmp(a, b) will return a negative value for less-than, zero if the inputs are equal, or a positive value for greater-than.
It is common to encounter comparison functions when translating algorithms from other languages. Also, some libraries provide comparison functions as part of their API. For example, locale.strcoll() is a comparison function.
To accommodate those situations, Python provides functools.cmp_to_key to wrap the comparison function to make it usable as a key function:
Odds and Ends¶
For locale aware sorting, use locale.strxfrm() for a key function or locale.strcoll() for a comparison function. This is necessary because “alphabetical” sort orderings can vary across cultures even if the underlying alphabet is the same.
The reverse parameter still maintains sort stability (so that records with equal keys retain the original order). Interestingly, that effect can be simulated without the parameter by using the builtin reversed() function twice:
The sort routines use < when making comparisons between two objects. So, it is easy to add a standard sort order to a class by defining an __lt__() method:
However, note that < can fall back to using __gt__() if __lt__() is not implemented (see object.__lt__() ).
Key functions need not depend directly on the objects being sorted. A key function can also access external resources. For instance, if the student grades are stored in a dictionary, they can be used to sort a separate list of student names:
Sort a Tuple in Python – With Examples
Tuples, like lists, are an ordered collection of items in Python. That is, there is an order to which the elements are present inside a tuple. There might be use-cases where you’d want to sort a tuple in a particular order (for example, ascending or descending). In this tutorial, we will look at how to sort elements of a tuple in Python with the help of some examples.
How to sort a tuple in Python?
Tuples are immutable in Python and thus cannot be altered after creation. You can, however, use the Python built-in sorted() function to create a sorted copy of the original tuple. The following is the syntax.
The sorted() function returns a list of elements in a sorted order which can further be converted to a tuple using the tuple() function.
Let’s look at some examples.
Sort tuple in ascedning order
The sorted() function, by default, sorts an iterable in ascending order and returns the sorted elements as a list. Let’s use it to sort a tuple in ascending order.
Here we reassign the returned tuple to the original variable a which now contains elements sorted in ascending order.
Sort tuple in descending order
You can similarly get a tuple with elements sorted in descending order by passing reverse=True to the sorted() function. The reverse parameter is False by default.
The tuple a now contains elements sorted in descending order.
Keep in mind that tuples are immutable. Here the sorted() function returns the sorted elements in a list which we are converting to a tuple using the tuple() function.
You might also be interested in –
Subscribe to our newsletter for more informative guides and tutorials.
We do not spam and you can opt out any time.
All about sorting in Python: Numbers to Sorting Class Types
Warning: A lot of code coming in. All code snippets are images.
Please type code yourself. For reference a git link to the complete notebook is here.
Sorting a list of numbers looks as simple as this:
You have a list of numbers, just call sort method and it gets sorted in-place. Want to reverse, just say reverse = True and sorts in descending order.
If you have a list of strings, they get sorted lexicographical order (dictionary order, or alphabetic order) based on their numeric codes.
That’s Simple Enough!
What if it’s not a list, lets say tuple of something. Then what?
No problem, we have sorted() which takes an iterable and gives back a sorted list.
Lets see something else now. Lets say we have a bunch of records for some people. Each record has: name, age, salary. Each record is stored in form of a tuple. For example consider these four records
Sorting the list directly sorts on basis of the first element of each tuple. See output below.
So above code sorts by name by-default.
If we wish to sort by age, then we can use the key option in the sort method to change the key by which elements get sorted. The key option takes a lambda. This lambda should take a single argument and return one single result. Sort function will use the lambda on each object of the list, in our case on each tuple/record and use the return value of lambda to sort data. See this:
In above code lambda x: x[1] gives element at index 1 from the tuples. So sorting is done by age and not by name.
In the older versions of python, this key = callable feature was not available and hence you would have to use something called as Decorate-Sort-Undecorate approach citing from the official python.org sorting page. See below example:
Sorting Class Objects
While writing this, my intention was to focus on sorting class types. So now put all your focus here. If I were to interview someone for Python at beginner level in industry, this would have been one of the topics on my list.
Lets first create a class whose objects we will sort. Same records but as objects of class Employee .
Now we have the class and list of employees. Time to sort.
But sorting directly gives and error since python doesn’t know how to sort.
Error says ‘<’ not supported … What does that mean?
Try to understand from below example.
So if you try to compare 2 objects of a custom class, that is not supported by default and hence the error. Same error you get while calling sort() as sort will internally compare objects using <.
To fix this make our class objects comparable by the less-than operator. Doing that requires us to define the __lt__() magic method. Python calls this method when you compare two objects using < operator. Modified class looks like this:
Now the less-than comparison starts working and that’s the only thing we need. Now sorting will also work.
In __lt__() magic method comparison is done by name, so the result is sorted by name.
If you still want to change the sort key, we still have the key option in sort() . Lets sort by salary now.
Looks like the old way of sort() with key argument is a better option than defining __lt__() . But still defining the less-than magic method allows you to define a default ordering for your class objects, which can be used for things apart from sorting(putting your objects in a heap, or a bst maybe).
Some other ways to sort things
There’s a module operator which contain two functions of our interest attrgetter and itemgetter . If you didn’t understand by name have a look at example:
These functions return a function or callable(a fancy name for something that behaves like a function) that can either extract an element from an index (itemgetter) or an attribute from a class object(attrgetter).
Sort List of Tuples in Python
In Python, multiple items can be stored in a single variable using Tuples. A list of Tuples can be sorted like a list of integers.
This tutorial will discuss different methods to sort a list of tuples based on the first, second, or ith element in the tuples.
Use the list.sort() Function to Sort List of Tuples in Python
The list.sort() function sorts the elements of a list in ascending or descending order. Its key parameter specifies the value to be used in the sorting. key shall be a function or other callables that could be applied to each list element.
The following code sorts the tuples based on the second element in all the tuples.
The order can be reversed to descending by setting the reverse parameter of the sort() method to be True .
The following code sorts the list of tuples in descending order by using the reverse parameter.