並べ替え方法

著者: アンドリュー・ダルケとレイモンド・ヘッティンガー
リリース: 0.1

Pythonリストには、リストをインプレースで変更する組み込みの list.sort（）メソッドがあります。反復可能オブジェクトから新しいソート済みリストを作成する sorted（）組み込み関数もあります。

このドキュメントでは、Pythonを使用してデータを並べ替えるためのさまざまな手法について説明します。

並べ替えの基本

単純な昇順ソートは非常に簡単です。 sorted（）関数を呼び出すだけです。新しいソート済みリストを返します。

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

list.sort（）メソッドを使用することもできます。リストをインプレースで変更します（混乱を避けるためにNoneを返します）。通常は sorted（）よりも便利ではありませんが、元のリストが必要ない場合は、少し効率的です。

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

もう1つの違いは、 list.sort（）メソッドがリストに対してのみ定義されていることです。対照的に、 sorted（）関数は任意の反復可能関数を受け入れます。

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

主な機能

list.sort（）と sorted（）の両方に、比較を行う前に各リスト要素で呼び出される関数を指定する key パラメーターがあります。

たとえば、大文字と小文字を区別しない文字列の比較を次に示します。

>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

key パラメーターの値は、単一の引数を取り、ソートの目的で使用するキーを返す関数である必要があります。キー関数は入力レコードごとに1回だけ呼び出されるため、この手法は高速です。

一般的なパターンは、オブジェクトのインデックスの一部をキーとして使用して、複雑なオブジェクトを並べ替えることです。例えば：

>>> 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)]

同じ手法が、名前付き属性を持つオブジェクトに対しても機能します。例えば：

>>> 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)]

オペレータモジュールの機能

上記のキー関数パターンは非常に一般的であるため、Pythonには、アクセサー関数をより簡単かつ高速にする便利な関数が用意されています。 operator モジュールには、 itemgetter（）、 attrgetter（）、および methodcaller（）関数があります。

これらの関数を使用すると、上記の例はより単純で高速になります。

>>> 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)]

オペレータモジュール機能により、複数レベルのソートが可能です。たとえば、 grade で並べ替えてから、 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)]

上昇と下降

list.sort（）と sorted（）はどちらも、ブール値を持つ reverse パラメーターを受け入れます。これは、降順のソートにフラグを立てるために使用されます。たとえば、学生データを年齢の逆の順序で取得するには、次のようにします。

>>> 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)]

ソートの安定性と複雑なソート

ソートは安定であることが保証されています。つまり、複数のレコードが同じキーを持っている場合、元の順序が保持されます。

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

blue の2つのレコードが元の順序を保持しているため、('blue', 1)が('blue', 2)に先行することが保証されていることに注意してください。

この素晴らしいプロパティを使用すると、一連の並べ替え手順で複雑な並べ替えを作成できます。たとえば、 grade を降順で age を昇順で並べ替えるには、最初に age 並べ替えを実行してから、 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)]

Pythonで使用される Timsort アルゴリズムは、データセットにすでに存在する任意の順序を利用できるため、複数の並べ替えを効率的に実行します。

デコレート-ソート-アンデコレートを使用した古い方法

このイディオムは、次の3つのステップの後で、Decorate-Sort-Undecorateと呼ばれます。

まず、初期リストは、ソート順を制御する新しい値で装飾されます。
次に、装飾されたリストがソートされます。
最後に、装飾が削除され、新しい順序の初期値のみを含むリストが作成されます。

たとえば、DSUアプローチを使用して、学生データを grade で並べ替えるには次のようにします。

>>> 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)]

タプルは辞書式に比較されるため、このイディオムは機能します。最初の項目が比較されます。それらが同じである場合、2番目の項目が比較されます。

すべての場合に、装飾リストにインデックス i を含める必要はありませんが、含めると2つの利点があります。

並べ替えは安定しています– 2つのアイテムが同じキーを持っている場合、それらの順序は並べ替えられたリストに保持されます。
装飾されたタプルの順序は最大で最初の2つのアイテムによって決定されるため、元のアイテムは比較可能である必要はありません。したがって、たとえば、元のリストには、直接ソートできない複素数が含まれている可能性があります。

このイディオムの別名は、RandalLにちなんでシュワルツ変換です。 Perlプログラマーの間でそれを普及させたSchwartz。

Pythonの並べ替えでキー機能が提供されるようになったため、この手法はあまり必要ありません。

cmp パラメータを使用した古い方法

このHOWTOに記載されている多くの構成は、Python2.4以降を想定しています。それ以前は、 sorted（）が組み込まれておらず、 list.sort（）はキーワード引数を取りませんでした。代わりに、すべてのPy2.xバージョンは、ユーザー指定の比較関数を処理するために cmp パラメーターをサポートしていました。

Py3.0では、 cmp パラメーターが完全に削除されました（言語を単純化および統一するためのより大きな努力の一環として、豊富な比較と__cmp__()マジックメソッドの間の競合を排除しました）。

Py2.xでは、sortは、比較を行うために呼び出すことができるオプションの関数を許可していました。この関数は、比較する2つの引数を取り、より小さい場合は負の値を返すか、等しい場合はゼロを返すか、より大きい場合は正の値を返す必要があります。たとえば、次のことができます。

>>> def numeric_compare(x, y):
...     return x - y
>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare) 
[1, 2, 3, 4, 5]

または、次の方法で比較の順序を逆にすることもできます。

>>> def reverse_numeric(x, y):
...     return y - x
>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric) 
[5, 4, 3, 2, 1]

Python 2.xから3.xにコードを移植する場合、ユーザーが比較関数を提供し、それをキー関数に変換する必要がある場合に状況が発生する可能性があります。次のラッパーを使用すると、これを簡単に実行できます。

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K:
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K

キー関数に変換するには、古い比較関数をラップするだけです。

>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
[5, 4, 3, 2, 1]

Python 3.2では、 functools.cmp_to_key（）関数が標準ライブラリの functools モジュールに追加されました。

奇数と終わり

ロケール対応の並べ替えの場合、キー関数には locale.strxfrm（）を使用し、比較関数には locale.strcoll（）を使用します。

reverse パラメーターは、ソートの安定性を維持します（したがって、同じキーを持つレコードは元の順序を保持します）。興味深いことに、その効果は、組み込みの reverse（）関数を2回使用することにより、パラメーターなしでシミュレートできます。

>>> 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)]

ソートルーチンは、2つのオブジェクトを比較するときに__lt__()を使用することが保証されています。したがって、__lt__()メソッドを定義することで、クラスに標準の並べ替え順序を簡単に追加できます。
```
>>> Student.__lt__ = lambda self, other: self.age < other.age
>>> sorted(student_objects)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
```
主要な機能は、ソートされるオブジェクトに直接依存する必要はありません。キー機能は外部リソースにもアクセスできます。たとえば、学生の成績が辞書に保存されている場合、それらを使用して、学生名の個別のリストを並べ替えることができます。
```
>>> students = ['dave', 'john', 'jane']
>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
>>> sorted(students, key=newgrades.__getitem__)
['jane', 'dave', 'john']
```

並べ替え方法—Pythonドキュメント