1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
<span id="sortinghowto"></span><h1>Sorting HOW TO</h1> <dl class="field-list simple"> <dt class="field-odd">Author</dt> <dd class="field-odd">
<p>Andrew Dalke and Raymond Hettinger</p> </dd> <dt class="field-even">Release</dt> <dd class="field-even">
<p>0.1</p> </dd> </dl> <p>Python lists have a built-in <a class="reference internal" href="../library/stdtypes#list.sort" title="list.sort"><code>list.sort()</code></a> method that modifies the list in-place. There is also a <a class="reference internal" href="../library/functions#sorted" title="sorted"><code>sorted()</code></a> built-in function that builds a new sorted list from an iterable.</p> <p>In this document, we explore the various techniques for sorting data using Python.</p> <section id="sorting-basics"> <h2>Sorting Basics</h2> <p>A simple ascending sort is very easy: just call the <a class="reference internal" href="../library/functions#sorted" title="sorted"><code>sorted()</code></a> function. It returns a new sorted list:</p> <pre data-language="pycon3">>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]
</pre> <p>You can also use the <a class="reference internal" href="../library/stdtypes#list.sort" title="list.sort"><code>list.sort()</code></a> method. It modifies the list in-place (and returns <code>None</code> to avoid confusion). Usually it’s less convenient than <a class="reference internal" href="../library/functions#sorted" title="sorted"><code>sorted()</code></a> - but if you don’t need the original list, it’s slightly more efficient.</p> <pre data-language="pycon3">>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]
</pre> <p>Another difference is that the <a class="reference internal" href="../library/stdtypes#list.sort" title="list.sort"><code>list.sort()</code></a> method is only defined for lists. In contrast, the <a class="reference internal" href="../library/functions#sorted" title="sorted"><code>sorted()</code></a> function accepts any iterable.</p> <pre data-language="pycon3">>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]
</pre> </section> <section id="key-functions"> <h2>Key Functions</h2> <p>Both <a class="reference internal" href="../library/stdtypes#list.sort" title="list.sort"><code>list.sort()</code></a> and <a class="reference internal" href="../library/functions#sorted" title="sorted"><code>sorted()</code></a> have a <em>key</em> parameter to specify a function (or other callable) to be called on each list element prior to making comparisons.</p> <p>For example, here’s a case-insensitive string comparison:</p> <pre data-language="pycon3">>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
</pre> <p>The value of the <em>key</em> 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.</p> <p>A common pattern is to sort complex objects using some of the object’s indices as keys. For example:</p> <pre data-language="pycon3">>>> student_tuples = [
... ('john', 'A', 15),
... ('jane', 'B', 12),
... ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2]) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
</pre> <p>The same technique works for objects with named attributes. For example:</p> <pre data-language="pycon3">>>> class Student:
... def __init__(self, name, grade, age):
... self.name = name
... self.grade = grade
... self.age = age
... def __repr__(self):
... return repr((self.name, self.grade, self.age))
>>> student_objects = [
... Student('john', 'A', 15),
... Student('jane', 'B', 12),
... Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
</pre> </section> <section id="operator-module-functions"> <h2>Operator Module Functions</h2> <p>The key-function patterns shown above are very common, so Python provides convenience functions to make accessor functions easier and faster. The <a class="reference internal" href="../library/operator#module-operator" title="operator: Functions corresponding to the standard operators."><code>operator</code></a> module has <a class="reference internal" href="../library/operator#operator.itemgetter" title="operator.itemgetter"><code>itemgetter()</code></a>, <a class="reference internal" href="../library/operator#operator.attrgetter" title="operator.attrgetter"><code>attrgetter()</code></a>, and a <a class="reference internal" href="../library/operator#operator.methodcaller" title="operator.methodcaller"><code>methodcaller()</code></a> function.</p> <p>Using those functions, the above examples become simpler and faster:</p> <pre data-language="pycon3">>>> from operator import itemgetter, attrgetter
>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
</pre> <p>The operator module functions allow multiple levels of sorting. For example, to sort by <em>grade</em> then by <em>age</em>:</p> <pre data-language="pycon3">>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
</pre> </section> <section id="ascending-and-descending"> <h2>Ascending and Descending</h2> <p>Both <a class="reference internal" href="../library/stdtypes#list.sort" title="list.sort"><code>list.sort()</code></a> and <a class="reference internal" href="../library/functions#sorted" title="sorted"><code>sorted()</code></a> accept a <em>reverse</em> parameter with a boolean value. This is used to flag descending sorts. For example, to get the student data in reverse <em>age</em> order:</p> <pre data-language="pycon3">>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
</pre> </section> <section id="sort-stability-and-complex-sorts"> <h2>Sort Stability and Complex Sorts</h2> <p>Sorts are guaranteed to be <a class="reference external" href="https://en.wikipedia.org/wiki/Sorting_algorithm#Stability">stable</a>. That means that when multiple records have the same key, their original order is preserved.</p> <pre data-language="pycon3">>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]
</pre> <p>Notice how the two records for <em>blue</em> retain their original order so that <code>('blue', 1)</code> is guaranteed to precede <code>('blue', 2)</code>.</p> <p>This wonderful property lets you build complex sorts in a series of sorting steps. For example, to sort the student data by descending <em>grade</em> and then ascending <em>age</em>, do the <em>age</em> sort first and then sort again using <em>grade</em>:</p> <pre data-language="pycon3">>>> s = sorted(student_objects, key=attrgetter('age')) # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True) # now sort on primary key, descending
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
</pre> <p>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.</p> <pre data-language="pycon3">>>> def multisort(xs, specs):
... for key, reverse in reversed(specs):
... xs.sort(key=attrgetter(key), reverse=reverse)
... return xs
>>> multisort(list(student_objects), (('grade', True), ('age', False)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
</pre> <p>The <a class="reference external" href="https://en.wikipedia.org/wiki/Timsort">Timsort</a> algorithm used in Python does multiple sorts efficiently because it can take advantage of any ordering already present in a dataset.</p> </section> <section id="decorate-sort-undecorate"> <h2>Decorate-Sort-Undecorate</h2> <p>This idiom is called Decorate-Sort-Undecorate after its three steps:</p> <ul class="simple"> <li>First, the initial list is decorated with new values that control the sort order.</li> <li>Second, the decorated list is sorted.</li> <li>Finally, the decorations are removed, creating a list that contains only the initial values in the new order.</li> </ul> <p>For example, to sort the student data by <em>grade</em> using the DSU approach:</p> <pre data-language="python">>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated] # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
</pre> <p>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.</p> <p>It is not strictly necessary in all cases to include the index <em>i</em> in the decorated list, but including it gives two benefits:</p> <ul class="simple"> <li>The sort is stable – if two items have the same key, their order will be preserved in the sorted list.</li> <li>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.</li> </ul> <p>Another name for this idiom is <a class="reference external" href="https://en.wikipedia.org/wiki/Schwartzian_transform">Schwartzian transform</a>, after Randal L. Schwartz, who popularized it among Perl programmers.</p> <p>Now that Python sorting provides key-functions, this technique is not often needed.</p> </section> <section id="comparison-functions"> <h2>Comparison Functions</h2> <p>Unlike key functions that return an absolute value for sorting, a comparison function computes the relative ordering for two inputs.</p> <p>For example, a <a class="reference external" href="#">balance scale</a> compares two samples giving a relative ordering: lighter, equal, or heavier. Likewise, a comparison function such as <code>cmp(a, b)</code> will return a negative value for less-than, zero if the inputs are equal, or a positive value for greater-than.</p> <p>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, <a class="reference internal" href="../library/locale#locale.strcoll" title="locale.strcoll"><code>locale.strcoll()</code></a> is a comparison function.</p> <p>To accommodate those situations, Python provides <a class="reference internal" href="../library/functools#functools.cmp_to_key" title="functools.cmp_to_key"><code>functools.cmp_to_key</code></a> to wrap the comparison function to make it usable as a key function:</p> <pre data-language="python">sorted(words, key=cmp_to_key(strcoll)) # locale-aware sort order
</pre> </section> <section id="odds-and-ends"> <h2>Odds and Ends</h2> <ul> <li>For locale aware sorting, use <a class="reference internal" href="../library/locale#locale.strxfrm" title="locale.strxfrm"><code>locale.strxfrm()</code></a> for a key function or <a class="reference internal" href="../library/locale#locale.strcoll" title="locale.strcoll"><code>locale.strcoll()</code></a> for a comparison function. This is necessary because “alphabetical” sort orderings can vary across cultures even if the underlying alphabet is the same.</li> <li>
<p>The <em>reverse</em> 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 <a class="reference internal" href="../library/functions#reversed" title="reversed"><code>reversed()</code></a> function twice:</p> <pre data-language="pycon3">>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> standard_way = sorted(data, key=itemgetter(0), reverse=True)
>>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))
>>> assert standard_way == double_reversed
>>> standard_way
[('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]
</pre> </li> <li>
<p>The sort routines use <code><</code> when making comparisons between two objects. So, it is easy to add a standard sort order to a class by defining an <a class="reference internal" href="../reference/datamodel#object.__lt__" title="object.__lt__"><code>__lt__()</code></a> method:</p> <pre data-language="pycon3">>>> Student.__lt__ = lambda self, other: self.age < other.age
>>> sorted(student_objects)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
</pre> <p>However, note that <code><</code> can fall back to using <a class="reference internal" href="../reference/datamodel#object.__gt__" title="object.__gt__"><code>__gt__()</code></a> if <a class="reference internal" href="../reference/datamodel#object.__lt__" title="object.__lt__"><code>__lt__()</code></a> is not implemented (see <a class="reference internal" href="../reference/datamodel#object.__lt__" title="object.__lt__"><code>object.__lt__()</code></a>).</p> </li> <li>
<p>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:</p> <pre data-language="pycon3">>>> students = ['dave', 'john', 'jane']
>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
>>> sorted(students, key=newgrades.__getitem__)
['jane', 'dave', 'john']
</pre> </li> </ul> </section> <div class="_attribution">
<p class="_attribution-p">
© 2001–2023 Python Software Foundation<br>Licensed under the PSF License.<br>
<a href="https://docs.python.org/3.12/howto/sorting.html" class="_attribution-link">https://docs.python.org/3.12/howto/sorting.html</a>
</p>
</div>
|
