| 1 |
.. _sortinghowto: |
| 2 |
|
| 3 |
Sorting Techniques |
| 4 |
****************** |
| 5 |
|
| 6 |
:Author: Andrew Dalke and Raymond Hettinger |
| 7 |
|
| 8 |
|
| 9 |
Python lists have a built-in :meth:`list.sort` method that modifies the list |
| 10 |
in-place. There is also a :func:`sorted` built-in function that builds a new |
| 11 |
sorted list from an iterable. |
| 12 |
|
| 13 |
In this document, we explore the various techniques for sorting data using Python. |
| 14 |
|
| 15 |
|
| 16 |
Sorting Basics |
| 17 |
============== |
| 18 |
|
| 19 |
A simple ascending sort is very easy: just call the :func:`sorted` function. It |
| 20 |
returns a new sorted list: |
| 21 |
|
| 22 |
.. doctest:: |
| 23 |
|
| 24 |
>>> sorted([5, 2, 3, 1, 4]) |
| 25 |
[1, 2, 3, 4, 5] |
| 26 |
|
| 27 |
You can also use the :meth:`list.sort` method. It modifies the list |
| 28 |
in-place (and returns ``None`` to avoid confusion). Usually it's less convenient |
| 29 |
than :func:`sorted` - but if you don't need the original list, it's slightly |
| 30 |
more efficient. |
| 31 |
|
| 32 |
.. doctest:: |
| 33 |
|
| 34 |
>>> a = [5, 2, 3, 1, 4] |
| 35 |
>>> a.sort() |
| 36 |
>>> a |
| 37 |
[1, 2, 3, 4, 5] |
| 38 |
|
| 39 |
Another difference is that the :meth:`list.sort` method is only defined for |
| 40 |
lists. In contrast, the :func:`sorted` function accepts any iterable. |
| 41 |
|
| 42 |
.. doctest:: |
| 43 |
|
| 44 |
>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'}) |
| 45 |
[1, 2, 3, 4, 5] |
| 46 |
|
| 47 |
Key Functions |
| 48 |
============= |
| 49 |
|
| 50 |
The :meth:`list.sort` method and the functions :func:`sorted`, |
| 51 |
:func:`min`, :func:`max`, :func:`heapq.nsmallest`, and |
| 52 |
:func:`heapq.nlargest` have a *key* parameter to specify a function (or |
| 53 |
other callable) to be called on each list element prior to making |
| 54 |
comparisons. |
| 55 |
|
| 56 |
For example, here's a case-insensitive string comparison using |
| 57 |
:meth:`str.casefold`: |
| 58 |
|
| 59 |
.. doctest:: |
| 60 |
|
| 61 |
>>> sorted("This is a test string from Andrew".split(), key=str.casefold) |
| 62 |
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This'] |
| 63 |
|
| 64 |
The value of the *key* parameter should be a function (or other callable) that |
| 65 |
takes a single argument and returns a key to use for sorting purposes. This |
| 66 |
technique is fast because the key function is called exactly once for each |
| 67 |
input record. |
| 68 |
|
| 69 |
A common pattern is to sort complex objects using some of the object's indices |
| 70 |
as keys. For example: |
| 71 |
|
| 72 |
.. doctest:: |
| 73 |
|
| 74 |
>>> student_tuples = [ |
| 75 |
... ('john', 'A', 15), |
| 76 |
... ('jane', 'B', 12), |
| 77 |
... ('dave', 'B', 10), |
| 78 |
... ] |
| 79 |
>>> sorted(student_tuples, key=lambda student: student[2]) # sort by age |
| 80 |
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
| 81 |
|
| 82 |
The same technique works for objects with named attributes. For example: |
| 83 |
|
| 84 |
.. doctest:: |
| 85 |
|
| 86 |
>>> class Student: |
| 87 |
... def __init__(self, name, grade, age): |
| 88 |
... self.name = name |
| 89 |
... self.grade = grade |
| 90 |
... self.age = age |
| 91 |
... def __repr__(self): |
| 92 |
... return repr((self.name, self.grade, self.age)) |
| 93 |
|
| 94 |
>>> student_objects = [ |
| 95 |
... Student('john', 'A', 15), |
| 96 |
... Student('jane', 'B', 12), |
| 97 |
... Student('dave', 'B', 10), |
| 98 |
... ] |
| 99 |
>>> sorted(student_objects, key=lambda student: student.age) # sort by age |
| 100 |
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
| 101 |
|
| 102 |
Objects with named attributes can be made by a regular class as shown |
| 103 |
above, or they can be instances of :class:`~dataclasses.dataclass` or |
| 104 |
a :term:`named tuple`. |
| 105 |
|
| 106 |
Operator Module Functions and Partial Function Evaluation |
| 107 |
========================================================= |
| 108 |
|
| 109 |
The :term:`key function` patterns shown above are very common, so Python provides |
| 110 |
convenience functions to make accessor functions easier and faster. The |
| 111 |
:mod:`operator` module has :func:`~operator.itemgetter`, |
| 112 |
:func:`~operator.attrgetter`, and a :func:`~operator.methodcaller` function. |
| 113 |
|
| 114 |
Using those functions, the above examples become simpler and faster: |
| 115 |
|
| 116 |
.. doctest:: |
| 117 |
|
| 118 |
>>> from operator import itemgetter, attrgetter |
| 119 |
|
| 120 |
>>> sorted(student_tuples, key=itemgetter(2)) |
| 121 |
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
| 122 |
|
| 123 |
>>> sorted(student_objects, key=attrgetter('age')) |
| 124 |
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
| 125 |
|
| 126 |
The operator module functions allow multiple levels of sorting. For example, to |
| 127 |
sort by *grade* then by *age*: |
| 128 |
|
| 129 |
.. doctest:: |
| 130 |
|
| 131 |
>>> sorted(student_tuples, key=itemgetter(1,2)) |
| 132 |
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)] |
| 133 |
|
| 134 |
>>> sorted(student_objects, key=attrgetter('grade', 'age')) |
| 135 |
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)] |
| 136 |
|
| 137 |
The :mod:`functools` module provides another helpful tool for making |
| 138 |
key-functions. The :func:`~functools.partial` function can reduce the |
| 139 |
`arity <https://en.wikipedia.org/wiki/Arity>`_ of a multi-argument |
| 140 |
function making it suitable for use as a key-function. |
| 141 |
|
| 142 |
.. doctest:: |
| 143 |
|
| 144 |
>>> from functools import partial |
| 145 |
>>> from unicodedata import normalize |
| 146 |
|
| 147 |
>>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split() |
| 148 |
|
| 149 |
>>> sorted(names, key=partial(normalize, 'NFD')) |
| 150 |
['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë'] |
| 151 |
|
| 152 |
>>> sorted(names, key=partial(normalize, 'NFC')) |
| 153 |
['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana'] |
| 154 |
|
| 155 |
Ascending and Descending |
| 156 |
======================== |
| 157 |
|
| 158 |
Both :meth:`list.sort` and :func:`sorted` accept a *reverse* parameter with a |
| 159 |
boolean value. This is used to flag descending sorts. For example, to get the |
| 160 |
student data in reverse *age* order: |
| 161 |
|
| 162 |
.. doctest:: |
| 163 |
|
| 164 |
>>> sorted(student_tuples, key=itemgetter(2), reverse=True) |
| 165 |
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)] |
| 166 |
|
| 167 |
>>> sorted(student_objects, key=attrgetter('age'), reverse=True) |
| 168 |
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)] |
| 169 |
|
| 170 |
Sort Stability and Complex Sorts |
| 171 |
================================ |
| 172 |
|
| 173 |
Sorts are guaranteed to be `stable |
| 174 |
<https://en.wikipedia.org/wiki/Sorting_algorithm#Stability>`_\. That means that |
| 175 |
when multiple records have the same key, their original order is preserved. |
| 176 |
|
| 177 |
.. doctest:: |
| 178 |
|
| 179 |
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] |
| 180 |
>>> sorted(data, key=itemgetter(0)) |
| 181 |
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)] |
| 182 |
|
| 183 |
Notice how the two records for *blue* retain their original order so that |
| 184 |
``('blue', 1)`` is guaranteed to precede ``('blue', 2)``. |
| 185 |
|
| 186 |
This wonderful property lets you build complex sorts in a series of sorting |
| 187 |
steps. For example, to sort the student data by descending *grade* and then |
| 188 |
ascending *age*, do the *age* sort first and then sort again using *grade*: |
| 189 |
|
| 190 |
.. doctest:: |
| 191 |
|
| 192 |
>>> s = sorted(student_objects, key=attrgetter('age')) # sort on secondary key |
| 193 |
>>> sorted(s, key=attrgetter('grade'), reverse=True) # now sort on primary key, descending |
| 194 |
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
| 195 |
|
| 196 |
This can be abstracted out into a wrapper function that can take a list and |
| 197 |
tuples of field and order to sort them on multiple passes. |
| 198 |
|
| 199 |
.. doctest:: |
| 200 |
|
| 201 |
>>> def multisort(xs, specs): |
| 202 |
... for key, reverse in reversed(specs): |
| 203 |
... xs.sort(key=attrgetter(key), reverse=reverse) |
| 204 |
... return xs |
| 205 |
|
| 206 |
>>> multisort(list(student_objects), (('grade', True), ('age', False))) |
| 207 |
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
| 208 |
|
| 209 |
The `Timsort <https://en.wikipedia.org/wiki/Timsort>`_ algorithm used in Python |
| 210 |
does multiple sorts efficiently because it can take advantage of any ordering |
| 211 |
already present in a dataset. |
| 212 |
|
| 213 |
Decorate-Sort-Undecorate |
| 214 |
======================== |
| 215 |
|
| 216 |
This idiom is called Decorate-Sort-Undecorate after its three steps: |
| 217 |
|
| 218 |
* First, the initial list is decorated with new values that control the sort order. |
| 219 |
|
| 220 |
* Second, the decorated list is sorted. |
| 221 |
|
| 222 |
* Finally, the decorations are removed, creating a list that contains only the |
| 223 |
initial values in the new order. |
| 224 |
|
| 225 |
For example, to sort the student data by *grade* using the DSU approach: |
| 226 |
|
| 227 |
.. doctest:: |
| 228 |
|
| 229 |
>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)] |
| 230 |
>>> decorated.sort() |
| 231 |
>>> [student for grade, i, student in decorated] # undecorate |
| 232 |
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)] |
| 233 |
|
| 234 |
This idiom works because tuples are compared lexicographically; the first items |
| 235 |
are compared; if they are the same then the second items are compared, and so |
| 236 |
on. |
| 237 |
|
| 238 |
It is not strictly necessary in all cases to include the index *i* in the |
| 239 |
decorated list, but including it gives two benefits: |
| 240 |
|
| 241 |
* The sort is stable -- if two items have the same key, their order will be |
| 242 |
preserved in the sorted list. |
| 243 |
|
| 244 |
* The original items do not have to be comparable because the ordering of the |
| 245 |
decorated tuples will be determined by at most the first two items. So for |
| 246 |
example the original list could contain complex numbers which cannot be sorted |
| 247 |
directly. |
| 248 |
|
| 249 |
Another name for this idiom is |
| 250 |
`Schwartzian transform <https://en.wikipedia.org/wiki/Schwartzian_transform>`_\, |
| 251 |
after Randal L. Schwartz, who popularized it among Perl programmers. |
| 252 |
|
| 253 |
Now that Python sorting provides key-functions, this technique is not often needed. |
| 254 |
|
| 255 |
Comparison Functions |
| 256 |
==================== |
| 257 |
|
| 258 |
Unlike key functions that return an absolute value for sorting, a comparison |
| 259 |
function computes the relative ordering for two inputs. |
| 260 |
|
| 261 |
For example, a `balance scale |
| 262 |
<https://upload.wikimedia.org/wikipedia/commons/1/17/Balance_à_tabac_1850.JPG>`_ |
| 263 |
compares two samples giving a relative ordering: lighter, equal, or heavier. |
| 264 |
Likewise, a comparison function such as ``cmp(a, b)`` will return a negative |
| 265 |
value for less-than, zero if the inputs are equal, or a positive value for |
| 266 |
greater-than. |
| 267 |
|
| 268 |
It is common to encounter comparison functions when translating algorithms from |
| 269 |
other languages. Also, some libraries provide comparison functions as part of |
| 270 |
their API. For example, :func:`locale.strcoll` is a comparison function. |
| 271 |
|
| 272 |
To accommodate those situations, Python provides |
| 273 |
:class:`functools.cmp_to_key` to wrap the comparison function |
| 274 |
to make it usable as a key function:: |
| 275 |
|
| 276 |
sorted(words, key=cmp_to_key(strcoll)) # locale-aware sort order |
| 277 |
|
| 278 |
Strategies For Unorderable Types and Values |
| 279 |
=========================================== |
| 280 |
|
| 281 |
A number of type and value issues can arise when sorting. |
| 282 |
Here are some strategies that can help: |
| 283 |
|
| 284 |
* Convert non-comparable input types to strings prior to sorting: |
| 285 |
|
| 286 |
.. doctest:: |
| 287 |
|
| 288 |
>>> data = ['twelve', '11', 10] |
| 289 |
>>> sorted(map(str, data)) |
| 290 |
['10', '11', 'twelve'] |
| 291 |
|
| 292 |
This is needed because most cross-type comparisons raise a |
| 293 |
:exc:`TypeError`. |
| 294 |
|
| 295 |
* Remove special values prior to sorting: |
| 296 |
|
| 297 |
.. doctest:: |
| 298 |
|
| 299 |
>>> from math import isnan |
| 300 |
>>> from itertools import filterfalse |
| 301 |
>>> data = [3.3, float('nan'), 1.1, 2.2] |
| 302 |
>>> sorted(filterfalse(isnan, data)) |
| 303 |
[1.1, 2.2, 3.3] |
| 304 |
|
| 305 |
This is needed because the `IEEE-754 standard |
| 306 |
<https://en.wikipedia.org/wiki/IEEE_754>`_ specifies that, "Every NaN |
| 307 |
shall compare unordered with everything, including itself." |
| 308 |
|
| 309 |
Likewise, ``None`` can be stripped from datasets as well: |
| 310 |
|
| 311 |
.. doctest:: |
| 312 |
|
| 313 |
>>> data = [3.3, None, 1.1, 2.2] |
| 314 |
>>> sorted(x for x in data if x is not None) |
| 315 |
[1.1, 2.2, 3.3] |
| 316 |
|
| 317 |
This is needed because ``None`` is not comparable to other types. |
| 318 |
|
| 319 |
* Convert mapping types into sorted item lists before sorting: |
| 320 |
|
| 321 |
.. doctest:: |
| 322 |
|
| 323 |
>>> data = [{'a': 1}, {'b': 2}] |
| 324 |
>>> sorted(data, key=lambda d: sorted(d.items())) |
| 325 |
[{'a': 1}, {'b': 2}] |
| 326 |
|
| 327 |
This is needed because dict-to-dict comparisons raise a |
| 328 |
:exc:`TypeError`. |
| 329 |
|
| 330 |
* Convert set types into sorted lists before sorting: |
| 331 |
|
| 332 |
.. doctest:: |
| 333 |
|
| 334 |
>>> data = [{'a', 'b', 'c'}, {'b', 'c', 'd'}] |
| 335 |
>>> sorted(map(sorted, data)) |
| 336 |
[['a', 'b', 'c'], ['b', 'c', 'd']] |
| 337 |
|
| 338 |
This is needed because the elements contained in set types do not have a |
| 339 |
deterministic order. For example, ``list({'a', 'b'})`` may produce |
| 340 |
either ``['a', 'b']`` or ``['b', 'a']``. |
| 341 |
|
| 342 |
Odds and Ends |
| 343 |
============= |
| 344 |
|
| 345 |
* For locale aware sorting, use :func:`locale.strxfrm` for a key function or |
| 346 |
:func:`locale.strcoll` for a comparison function. This is necessary |
| 347 |
because "alphabetical" sort orderings can vary across cultures even |
| 348 |
if the underlying alphabet is the same. |
| 349 |
|
| 350 |
* The *reverse* parameter still maintains sort stability (so that records with |
| 351 |
equal keys retain the original order). Interestingly, that effect can be |
| 352 |
simulated without the parameter by using the builtin :func:`reversed` function |
| 353 |
twice: |
| 354 |
|
| 355 |
.. doctest:: |
| 356 |
|
| 357 |
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] |
| 358 |
>>> standard_way = sorted(data, key=itemgetter(0), reverse=True) |
| 359 |
>>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0)))) |
| 360 |
>>> assert standard_way == double_reversed |
| 361 |
>>> standard_way |
| 362 |
[('red', 1), ('red', 2), ('blue', 1), ('blue', 2)] |
| 363 |
|
| 364 |
* The sort routines use ``<`` when making comparisons |
| 365 |
between two objects. So, it is easy to add a standard sort order to a class by |
| 366 |
defining an :meth:`~object.__lt__` method: |
| 367 |
|
| 368 |
.. doctest:: |
| 369 |
|
| 370 |
>>> Student.__lt__ = lambda self, other: self.age < other.age |
| 371 |
>>> sorted(student_objects) |
| 372 |
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
| 373 |
|
| 374 |
However, note that ``<`` can fall back to using :meth:`~object.__gt__` if |
| 375 |
:meth:`~object.__lt__` is not implemented (see :func:`object.__lt__` |
| 376 |
for details on the mechanics). To avoid surprises, :pep:`8` |
| 377 |
recommends that all six comparison methods be implemented. |
| 378 |
The :func:`~functools.total_ordering` decorator is provided to make that |
| 379 |
task easier. |
| 380 |
|
| 381 |
* Key functions need not depend directly on the objects being sorted. A key |
| 382 |
function can also access external resources. For instance, if the student grades |
| 383 |
are stored in a dictionary, they can be used to sort a separate list of student |
| 384 |
names: |
| 385 |
|
| 386 |
.. doctest:: |
| 387 |
|
| 388 |
>>> students = ['dave', 'john', 'jane'] |
| 389 |
>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'} |
| 390 |
>>> sorted(students, key=newgrades.__getitem__) |
| 391 |
['jane', 'dave', 'john'] |
| 392 |
|
| 393 |
Partial Sorts |
| 394 |
============= |
| 395 |
|
| 396 |
Some applications require only some of the data to be ordered. The standard |
| 397 |
library provides several tools that do less work than a full sort: |
| 398 |
|
| 399 |
* :func:`min` and :func:`max` return the smallest and largest values, |
| 400 |
respectively. These functions make a single pass over the input data and |
| 401 |
require almost no auxiliary memory. |
| 402 |
|
| 403 |
* :func:`heapq.nsmallest` and :func:`heapq.nlargest` return |
| 404 |
the *n* smallest and largest values, respectively. These functions |
| 405 |
make a single pass over the data keeping only *n* elements in memory |
| 406 |
at a time. For values of *n* that are small relative to the number of |
| 407 |
inputs, these functions make far fewer comparisons than a full sort. |
| 408 |
|
| 409 |
* :func:`heapq.heappush` and :func:`heapq.heappop` create and maintain a |
| 410 |
partially sorted arrangement of data that keeps the smallest element |
| 411 |
at position ``0``. These functions are suitable for implementing |
| 412 |
priority queues which are commonly used for task scheduling. |