Doc/howto/sorting.rst

   1 .. _sortinghowto:
   2
   3 Sorting HOW TO
   4 **************
   5
   6 :Author: Andrew Dalke and Raymond Hettinger
   7 :Release: 0.1
   8
   9
  10 Python lists have a built-in :meth:`list.sort` method that modifies the list
  11 in-place.  There is also a :func:`sorted` built-in function that builds a new
  12 sorted list from an iterable.
  13
  14 In this document, we explore the various techniques for sorting data using Python.
  15
  16
  17 Sorting Basics
  18 ==============
  19
  20 A simple ascending sort is very easy: just call the :func:`sorted` function. It
  21 returns a new sorted list::
  22
  23     >>> sorted([5, 2, 3, 1, 4])
  24     [1, 2, 3, 4, 5]
  25
  26 You can also use the :meth:`list.sort` method of a list. It modifies the list
  27 in-place (and returns *None* to avoid confusion). Usually it's less convenient
  28 than :func:`sorted` - but if you don't need the original list, it's slightly
  29 more efficient.
  30
  31     >>> a = [5, 2, 3, 1, 4]
  32     >>> a.sort()
  33     >>> a
  34     [1, 2, 3, 4, 5]
  35
  36 Another difference is that the :meth:`list.sort` method is only defined for
  37 lists. In contrast, the :func:`sorted` function accepts any iterable.
  38
  39     >>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
  40     [1, 2, 3, 4, 5]
  41
  42 Key Functions
  43 =============
  44
  45 Starting with Python 2.4, both :meth:`list.sort` and :func:`sorted` added a
  46 *key* parameter to specify a function to be called on each list element prior to
  47 making comparisons.
  48
  49 For example, here's a case-insensitive string comparison:
  50
  51     >>> sorted("This is a test string from Andrew".split(), key=str.lower)
  52     ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
  53
  54 The value of the *key* parameter should be a function that takes a single argument
  55 and returns a key to use for sorting purposes. This technique is fast because
  56 the key function is called exactly once for each input record.
  57
  58 A common pattern is to sort complex objects using some of the object's indices
  59 as keys. For example:
  60
  61     >>> student_tuples = [
  62         ('john', 'A', 15),
  63         ('jane', 'B', 12),
  64         ('dave', 'B', 10),
  65     ]
  66     >>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
  67     [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
  68
  69 The same technique works for objects with named attributes. For example:
  70
  71     >>> class Student:
  72             def __init__(self, name, grade, age):
  73                 self.name = name
  74                 self.grade = grade
  75                 self.age = age
  76             def __repr__(self):
  77                 return repr((self.name, self.grade, self.age))
  78
  79     >>> student_objects = [
  80         Student('john', 'A', 15),
  81         Student('jane', 'B', 12),
  82         Student('dave', 'B', 10),
  83     ]
  84     >>> sorted(student_objects, key=lambda student: student.age)   # sort by age
  85     [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
  86
  87 Operator Module Functions
  88 =========================
  89
  90 The key-function patterns shown above are very common, so Python provides
  91 convenience functions to make accessor functions easier and faster. The operator
  92 module has :func:`operator.itemgetter`, :func:`operator.attrgetter`, and
  93 starting in Python 2.5 a :func:`operator.methodcaller` function.
  94
  95 Using those functions, the above examples become simpler and faster:
  96
  97     >>> from operator import itemgetter, attrgetter
  98
  99     >>> sorted(student_tuples, key=itemgetter(2))
 100     [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
 101
 102     >>> sorted(student_objects, key=attrgetter('age'))
 103     [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
 104
 105 The operator module functions allow multiple levels of sorting. For example, to
 106 sort by *grade* then by *age*:
 107
 108     >>> sorted(student_tuples, key=itemgetter(1,2))
 109     [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
 110
 111     >>> sorted(student_objects, key=attrgetter('grade', 'age'))
 112     [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
 113
 114 The :func:`operator.methodcaller` function makes method calls with fixed
 115 parameters for each object being sorted.  For example, the :meth:`str.count`
 116 method could be used to compute message priority by counting the
 117 number of exclamation marks in a message:
 118
 119     >>> messages = ['critical!!!', 'hurry!', 'standby', 'immediate!!']
 120     >>> sorted(messages, key=methodcaller('count', '!'))
 121     ['standby', 'hurry!', 'immediate!!', 'critical!!!']
 122
 123 Ascending and Descending
 124 ========================
 125
 126 Both :meth:`list.sort` and :func:`sorted` accept a *reverse* parameter with a
 127 boolean value. This is using to flag descending sorts. For example, to get the
 128 student data in reverse *age* order:
 129
 130     >>> sorted(student_tuples, key=itemgetter(2), reverse=True)
 131     [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
 132
 133     >>> sorted(student_objects, key=attrgetter('age'), reverse=True)
 134     [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
 135
 136 Sort Stability and Complex Sorts
 137 ================================
 138
 139 Starting with Python 2.2, sorts are guaranteed to be `stable
 140 <http://en.wikipedia.org/wiki/Sorting_algorithm#Stability>`_\. That means that
 141 when multiple records have the same key, their original order is preserved.
 142
 143     >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
 144     >>> sorted(data, key=itemgetter(0))
 145     [('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]
 146
 147 Notice how the two records for *blue* retain their original order so that
 148 ``('blue', 1)`` is guaranteed to precede ``('blue', 2)``.
 149
 150 This wonderful property lets you build complex sorts in a series of sorting
 151 steps. For example, to sort the student data by descending *grade* and then
 152 ascending *age*, do the *age* sort first and then sort again using *grade*:
 153
 154     >>> s = sorted(student_objects, key=attrgetter('age'))     # sort on secondary key
 155     >>> sorted(s, key=attrgetter('grade'), reverse=True)       # now sort on primary key, descending
 156     [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
 157
 158 The `Timsort <http://en.wikipedia.org/wiki/Timsort>`_ algorithm used in Python
 159 does multiple sorts efficiently because it can take advantage of any ordering
 160 already present in a dataset.
 161
 162 The Old Way Using Decorate-Sort-Undecorate
 163 ==========================================
 164
 165 This idiom is called Decorate-Sort-Undecorate after its three steps:
 166
 167 * First, the initial list is decorated with new values that control the sort order.
 168
 169 * Second, the decorated list is sorted.
 170
 171 * Finally, the decorations are removed, creating a list that contains only the
 172   initial values in the new order.
 173
 174 For example, to sort the student data by *grade* using the DSU approach:
 175
 176     >>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
 177     >>> decorated.sort()
 178     >>> [student for grade, i, student in decorated]               # undecorate
 179     [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
 180
 181 This idiom works because tuples are compared lexicographically; the first items
 182 are compared; if they are the same then the second items are compared, and so
 183 on.
 184
 185 It is not strictly necessary in all cases to include the index *i* in the
 186 decorated list, but including it gives two benefits:
 187
 188 * The sort is stable -- if two items have the same key, their order will be
 189   preserved in the sorted list.
 190
 191 * The original items do not have to be comparable because the ordering of the
 192   decorated tuples will be determined by at most the first two items. So for
 193   example the original list could contain complex numbers which cannot be sorted
 194   directly.
 195
 196 Another name for this idiom is
 197 `Schwartzian transform <http://en.wikipedia.org/wiki/Schwartzian_transform>`_\,
 198 after Randal L. Schwartz, who popularized it among Perl programmers.
 199
 200 For large lists and lists where the comparison information is expensive to
 201 calculate, and Python versions before 2.4, DSU is likely to be the fastest way
 202 to sort the list. For 2.4 and later, key functions provide the same
 203 functionality.
 204
 205 The Old Way Using the *cmp* Parameter
 206 =====================================
 207
 208 Many constructs given in this HOWTO assume Python 2.4 or later. Before that,
 209 there was no :func:`sorted` builtin and :meth:`list.sort` took no keyword
 210 arguments. Instead, all of the Py2.x versions supported a *cmp* parameter to
 211 handle user specified comparison functions.
 212
 213 In Py3.0, the *cmp* parameter was removed entirely (as part of a larger effort to
 214 simplify and unify the language, eliminating the conflict between rich
 215 comparisons and the :meth:`__cmp__` magic method).
 216
 217 In Py2.x, sort allowed an optional function which can be called for doing the
 218 comparisons. That function should take two arguments to be compared and then
 219 return a negative value for less-than, return zero if they are equal, or return
 220 a positive value for greater-than. For example, we can do:
 221
 222     >>> def numeric_compare(x, y):
 223             return x - y
 224     >>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare)
 225     [1, 2, 3, 4, 5]
 226
 227 Or you can reverse the order of comparison with:
 228
 229     >>> def reverse_numeric(x, y):
 230             return y - x
 231     >>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric)
 232     [5, 4, 3, 2, 1]
 233
 234 When porting code from Python 2.x to 3.x, the situation can arise when you have
 235 the user supplying a comparison function and you need to convert that to a key
 236 function. The following wrapper makes that easy to do::
 237
 238     def cmp_to_key(mycmp):
 239         'Convert a cmp= function into a key= function'
 240         class K(object):
 241             def __init__(self, obj, *args):
 242                 self.obj = obj
 243             def __lt__(self, other):
 244                 return mycmp(self.obj, other.obj) < 0
 245             def __gt__(self, other):
 246                 return mycmp(self.obj, other.obj) > 0
 247             def __eq__(self, other):
 248                 return mycmp(self.obj, other.obj) == 0
 249             def __le__(self, other):
 250                 return mycmp(self.obj, other.obj) <= 0
 251             def __ge__(self, other):
 252                 return mycmp(self.obj, other.obj) >= 0
 253             def __ne__(self, other):
 254                 return mycmp(self.obj, other.obj) != 0
 255         return K
 256
 257 To convert to a key function, just wrap the old comparison function:
 258
 259     >>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
 260     [5, 4, 3, 2, 1]
 261
 262 In Python 2.7, the :func:`functools.cmp_to_key` function was added to the
 263 functools module.
 264
 265 Odd and Ends
 266 ============
 267
 268 * For locale aware sorting, use :func:`locale.strxfrm` for a key function or
 269   :func:`locale.strcoll` for a comparison function.
 270
 271 * The *reverse* parameter still maintains sort stability (so that records with
 272   equal keys retain their original order). Interestingly, that effect can be
 273   simulated without the parameter by using the builtin :func:`reversed` function
 274   twice:
 275
 276     >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
 277     >>> assert sorted(data, reverse=True) == list(reversed(sorted(reversed(data))))
 278
 279 * To create a standard sort order for a class, just add the appropriate rich
 280   comparison methods:
 281
 282     >>> Student.__eq__ = lambda self, other: self.age == other.age
 283     >>> Student.__ne__ = lambda self, other: self.age != other.age
 284     >>> Student.__lt__ = lambda self, other: self.age < other.age
 285     >>> Student.__le__ = lambda self, other: self.age <= other.age
 286     >>> Student.__gt__ = lambda self, other: self.age > other.age
 287     >>> Student.__ge__ = lambda self, other: self.age >= other.age
 288     >>> sorted(student_objects)
 289     [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
 290
 291   For general purpose comparisons, the recommended approach is to define all six
 292   rich comparison operators.  The :func:`functools.total_ordering` class
 293   decorator makes this easy to implement.
 294
 295 * Key functions need not depend directly on the objects being sorted. A key
 296   function can also access external resources. For instance, if the student grades
 297   are stored in a dictionary, they can be used to sort a separate list of student
 298   names:
 299
 300     >>> students = ['dave', 'john', 'jane']
 301     >>> grades = {'john': 'F', 'jane':'A', 'dave': 'C'}
 302     >>> sorted(students, key=grades.__getitem__)
 303     ['jane', 'dave', 'john']