GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing cpython-previews--146482.org.readthedocs.build — Sorting Techniques
This is a deploy preview created from a pull request.
For authoritative documentation, see
the current stable release.
Sorting Techniques¶
Python lists have a built-in 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([5, 2, 3, 1, 4]) [1, 2, 3, 4, 5] You can also use the >>> a = [5, 2, 3, 1, 4] >>> a.sort() >>> a [1, 2, 3, 4, 5] Another difference is that the >>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'}) [1, 2, 3, 4, 5] Key Functions¶The For example, here’s a case-insensitive string comparison using
>>> sorted("This is a test string from Andrew".split(), key=str.casefold) ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This'] 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: >>> 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)] The same technique works for objects with named attributes. For example: >>> 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)] Objects with named attributes can be made by a regular class as shown
above, or they can be instances of Operator Module Functions and Partial Function Evaluation¶The key function patterns shown above are very common, so Python provides
convenience functions to make accessor functions easier and faster. The
Using those functions, the above examples become simpler and faster: >>> 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)] The operator module functions allow multiple levels of sorting. For example, to sort by grade then by age: >>> 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)] The >>> from functools import partial >>> from unicodedata import normalize >>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split() >>> sorted(names, key=partial(normalize, 'NFD')) ['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë'] >>> sorted(names, key=partial(normalize, 'NFC')) ['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana'] Ascending and Descending¶Both >>> 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)] 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. >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] >>> sorted(data, key=itemgetter(0)) [('blue', 1), ('blue', 2), ('red', 1), ('red', 2)] Notice how the two records for blue retain their original order so that
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: >>> 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)] 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. >>> 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)] 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:
For example, to sort the student data by grade using the DSU approach: >>> 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)] 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:
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 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, To accommodate those situations, Python provides
sorted(words, key=cmp_to_key(strcoll)) # locale-aware sort order Strategies For Unorderable Types and Values¶A number of type and value issues can arise when sorting. Here are some strategies that can help:
>>> data = ['twelve', '11', 10] >>> sorted(map(str, data)) ['10', '11', 'twelve'] This is needed because most cross-type comparisons raise a
>>> from math import isnan >>> from itertools import filterfalse >>> data = [3.3, float('nan'), 1.1, 2.2] >>> sorted(filterfalse(isnan, data)) [1.1, 2.2, 3.3] This is needed because the IEEE-754 standard specifies that, “Every NaN shall compare unordered with everything, including itself.” Likewise, >>> data = [3.3, None, 1.1, 2.2] >>> sorted(x for x in data if x is not None) [1.1, 2.2, 3.3] This is needed because
>>> data = [{'a': 1}, {'b': 2}] >>> sorted(data, key=lambda d: sorted(d.items())) [{'a': 1}, {'b': 2}] This is needed because dict-to-dict comparisons raise a
>>> data = [{'a', 'b', 'c'}, {'b', 'c', 'd'}] >>> sorted(map(sorted, data)) [['a', 'b', 'c'], ['b', 'c', 'd']] This is needed because the elements contained in set types do not have a
deterministic order. For example, Odds and Ends¶
Partial Sorts¶Some applications require only some of the data to be ordered. The standard library provides several tools that do less work than a full sort:
© Copyright 2001 Python Software Foundation.
This page is licensed under the Python Software Foundation License Version 2. Examples, recipes, and other code in the documentation are additionally licensed under the Zero Clause BSD License. See History and License for more information. Hosted on Read the Docs. The Python Software Foundation is a non-profit corporation. Please donate. Last updated on Jun 17, 2026 (23:49 UTC). Found a bug? Created using Sphinx 8.2.3. |
| You are visitor 01402639 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |