選択ソートの仕組み・コード・計算量をわかりやすく解説

考え方を平易に説明

リスト全体を走査して最小の要素を見つけ、インデックス 0 の要素と交換します。これでインデックス 0 は確定です。次にインデックス 1 からリストの残りを走査して最小の要素を見つけ、インデックス 1 と交換します。要素が1つだけ残るまで続けると、その1つは必然的に最大の要素です。

バブルソートや挿入ソートと違い、選択ソートは入力がすでにソート済みでも得をしません。最小値を見つけたと確信するために、残りの要素をすべて走査しなければならないからです。

具体例をステップごとに見る

[64, 25, 12, 22, 11] をソートします。バーより前の部分はソート済みで確定です。

5要素に対して4ステップ、比較は 4 + 3 + 2 + 1 = 10 回、実際の交換は3回です。

Pythonでの実装

def selection_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]
    return items
print(selection_sort([64, 25, 12, 22, 11]))   # [11, 12, 22, 25, 64]
print(selection_sort([2, 1]))                 # [1, 2]

最後に残った要素は自動的に所定の位置にあるため、外側のループは n − 1 回実行されます。内側のループはインデックスを記録するだけで、交換は外側のステップごとに1回だけ行われます。

時間計算量と空間計算量

書き込み回数が少ないことが、選択ソート唯一の本当の強みです。一部のフラッシュメモリや大きなレコードの移動のように、メモリへの書き込みが読み取りよりずっと高コストな場合、書き込みが少ないことが効いてきます。サイクルソートはこれをさらに進め、各要素を最大1回だけ書き込みます。

安定性：選択ソートが安定でない理由

安定ソートは、等しい要素の元の相対的な順序を保ちます。選択ソートの離れた位置との交換は、要素を、それと等しい別の要素の向こう側へ飛び越えさせてしまうことがあります。

def selection_sort_by_key(items, key):
    n = len(items)
    for i in range(n - 1):
        m = min(range(i, n), key=lambda j: key(items[j]))
        items[i], items[m] = items[m], items[i]
    return items
cards = [("4", "hearts"), ("4", "spades"), ("2", "clubs")]
print(selection_sort_by_key(cards, key=lambda c: c[0]))
# [('2', 'clubs'), ('4', 'spades'), ('4', 'hearts')]  order of the 4s changed

2 はハートの 4 と交換され、その結果ハートの 4 がスペードの 4 の後ろに移動しました。安定版も存在します。交換する代わりに、最小値を取り除いて位置 i に挿入し、他の要素を右にずらすのです。これで順序は保たれますが、ステップごとに O(n) 回の書き込みが必要になります。

選択ソートと他のソートの比較

ヒープソートは、より良いデータ構造を使った選択ソートです。やはり残りの要素から最大のものを繰り返し選びますが、O(n) の走査ではなく二分ヒープを使って O(log n) で見つけるため、全体で O(n log n) になります。

選択ソートを使う場面

実際のPythonコードでは、組み込みの sorted() か list.sort() を使います。選択ソートを知っておく価値があるのは、教育用の例として、制約のある環境での非常に小さな固定サイズの配列に対して、そして書き込み回数を最小にしなければならない場合です。試験や面接の定番問題でもあり、たいていは、手順を追跡し、比較と交換の回数を数え、安定でない理由を説明する、という形で出題されます。