Debian Codegraph @

Doc/howto/sorting.rst

raw
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.