並べ替え(整列)

Python には小さい順に並べ替える関数が二つあります。sort()sorted() です。この違いを,例で体験してみましょう。

In [ ]: a = [3, 5, 2, 4, 1]   # 適当なリストを作る

In [ ]: sorted(a)             # 並べ替えたリストを返す
Out[ ]: [1, 2, 3, 4, 5]       # 並べ変わっている

In [ ]: a                     # 元のリスト a は
Out[ ]: [3, 5, 2, 4, 1]       # 並べ変わっていない

In [ ]: a.sort()              # リストをその場で並べ替える

In [ ]: a                     # 元のリスト a が
Out[ ]: [1, 2, 3, 4, 5]       # 並べ変わっている

In [ ]: sorted("I have an apple".lower().split())
Out[ ]: ['an', 'apple', 'have', 'i']  # 文字列は辞書順に

デフォルトでは昇順になります。降順にするには reverse=True というオプションを与えます。

並べ替えをする簡単な関数を作ってみましょう。いろいろなアルゴリズムがありますが,次のものは選択ソート(selection sort)というものです:

def selectsort(a):
    n = len(a)
    for i in range(n):
        k = i
        for j in range(i + 1, n):
            if a[j] < a[k]:
                k = j
        a[i], a[k] = a[k], a[i]

最後の行は a[i]a[k] の値を交換しています。Python ならこのように簡単に書けます。

うまくいくか試してみましょう:

In [ ]: a = [3, 5, 2, 4, 1]   # 適当なリストを作る

In [ ]: selectsort(a)         # うまくいくかな?

In [ ]: a                     # 元のリスト a は
Out[ ]: [1, 2, 3, 4, 5]       # 並べ変わっている

もっと速いアルゴリズムとしてクイックソート(quicksort)が知られています:

def quicksort(a, first=0, last=None):
    if last is None:
        last = len(a) - 1
    x = a[(first + last) // 2]
    i = first
    j = last
    while True:
        while a[i] < x:
            i += 1
        while x < a[j]:
            j -= 1
        if i >= j:
            break
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    if first < i - 1:
        quicksort(a, first, i - 1)
    if j + 1 < last:
        quicksort(a, j + 1, last)

def quicksort(a, first=0, last=len(a)-1): としたいかもしれませんが,Python の引数のデフォルトの値は関数定義を評価したときに決まってしまうので,期待した動作になりません。ここでは,何もないことを表すオブジェクト None をデフォルトの値として,関数の実行時にもし None であれば len(a) - 1 に置き換えています。if last is None:if last == None: と似ていますが == は値の比較,is はオブジェクトのアドレスの比較です。後者の方が速く,しかも == のようにオーバーライド(上書き)できないので確実な比較ができます。

時間を比べてみましょう。Wall time が実時間(壁にかかっている時計で計った時間)です:

In [ ]: import numpy as np

In [ ]: rng = np.random.default_rng()

In [ ]: a = rng.random(10000)

In [ ]: %time selectsort(a)
CPU times: user 19.1 s, sys: 10.3 ms, total: 19.1 s
Wall time: 19.1 s

In [ ]: a = rng.random(10000)

In [ ]: %time quicksort(a)
CPU times: user 82.3 ms, sys: 3.79 ms, total: 86.1 ms
Wall time: 84.8 ms

Python の sort()sorted()Timsort というアルゴリズムを使っています。

NumPy にも整列の関数があります。

In [ ]: a = rng.random(10000)

In [ ]: %time a.sort() # aを上書きする
CPU times: user 702 µs, sys: 452 µs, total: 1.15 ms
Wall time: 593 µs

In [ ]: a = rng.random(10000)

In [ ]: %time b = np.sort(a) # aを上書きしない
CPU times: user 811 µs, sys: 647 µs, total: 1.46 ms
Wall time: 817 µs

こちらは降順に並べ替えるオプションはありませんが,a[::-1] で逆順にできます。あるいは実際には並べ替えをせず並べ替えた順序だけを返す np.argsort() を使えば逆順もできます。

In [ ]: a = np.array([3, 5, 2, 4, 1])

In [ ]: o = np.argsort(a)

In [ ]: a[o]

Out[ ]: array([1, 2, 3, 4, 5])

In [ ]: o = np.argsort(-a)

In [ ]: a[o]

Out[ ]: array([5, 4, 3, 2, 1])

Last modified: