選択ソート（Selection Sort）完全ガイド：仕組み・計算量・安定化とPython実装

選択ソートとは — 概要

選択ソート（Selection Sort）は、最も単純で古典的なソートアルゴリズムの一つです。配列から順に「最小（または最大）の要素を選んで」先頭から順に確定させていく方式で並べ替えを行います。概念が単純で理解しやすいため教育用途やアルゴリズム入門で頻繁に紹介されますが、計算量は二乗時間であるため大きなデータセット向けには実用的ではありません。

基本的な動作原理

長さ n の配列 A を昇順に並べる選択ソートの基本的な手順は次のとおりです。

• 未ソート領域の先頭位置 i を 0 から n−2 まで進める。
• 位置 i 以降の要素の中から最小要素のインデックス minIndex を探す（探索は線形スキャン）。
• 見つかった最小要素 A[minIndex] を A[i] と交換する（minIndex = i の場合は交換を省略できる）。
• 以上を繰り返し、配列全体をソートする。

疑似コード（典型実装）

for i = 0 to n-2:
    minIndex = i
    for j = i+1 to n-1:
        if A[j] < A[minIndex]:
            minIndex = j
    if minIndex != i:
        swap A[i], A[minIndex]

具体例（手順の追跡）

配列 [64, 25, 12, 22, 11] の場合（昇順にソート）:

1. i=0: 最小は 11（index 4）。swap 64 と 11 → [11,25,12,22,64]
2. i=1: 残りの最小は 12（index 2）。swap 25 と 12 → [11,12,25,22,64]
3. i=2: 残りの最小は 22（index 3）。swap 25 と 22 → [11,12,22,25,64]
4. i=3: 残りの最小は 25（index 3）。交換不要 → [11,12,22,25,64]

計算量の解析

• 比較回数：内側ループで要素を走査するため、比較回数は常に (n−1) + (n−2) + ... + 1 = n(n−1)/2。入力の並びに依らず一定です。
• 交換（swap）回数：典型実装（minIndex≠i のときのみswap）では最大で n−1 回、最小で 0 回（既にソート済みの場合）です。したがって交換回数は入力に依存しますが、最大でも O(n) に抑えられます。
• 時間計算量：比較回数が支配的なため、最良・平均・最悪いずれも Θ(n^2)。大きな n に対しては実用的でない。
• 空間計算量：in-place に動作し、補助記憶は定数 O(1)。

性質（安定性・適合性など）

• 安定性：標準的な選択ソートは安定ではありません。等しいキーを持つ要素の相対順序が入れ替わる可能性があります（交換によって後ろの等値要素が前に移動することがあるため）。
• インプレース：はい。追加の配列や大きな補助メモリを必要とせず、O(1) の補助領域で動作します。
• 適応性（入力の既ソート性への適応）：非適応的です。比較回数は入力に依らず一定なので、既にほぼソート済みの入力でも高速化されません。
• 書き込み回数の少なさ：比較ベースの単純ソートの中では“書き込み（swap）回数が少ない”という利点があります。swap の回数は最大でも n−1 に抑えられるため、書き込みが高コストとなる環境（フラッシュメモリなど）で選択されることがあります。ただし、書き込み最小化を厳密に目的とするなら Cycle Sort のような別アルゴリズムがより優れます。

安定化する方法（工夫）

選択ソートを安定にするには、単純な swap を使わずに、見つけた最小要素を位置 i に「挿入」する（つまり最小要素より前にある要素を右にシフトする）実装にすれば良いです。これにより等しいキーの相対順序を保てますが、シフト操作が増えるため書き込み回数は増え、実行コストは高くなります（実装によっては移動回数が O(n^2) になる）。

バリエーション・最適化

• 両方向選択（双方向選択ソート、cocktail-selection）：同時に最小と最大を見つけて両端から詰めていくことでパス回数を半分にできますが、依然として O(n^2) の比較は必要です。
• 再帰的選択ソート：再帰を用いて同じ処理を行うだけで、アルゴリズム的性質は変わりません。
• 安定化の工夫：前述の挿入（シフト）を用いることで安定化可能。ただしコストは増加。

いつ使うべきか（実用的な観点）

• 教育目的：アルゴリズムの基礎概念（選択・交換・インプレース）の理解には最適です。
• 小規模データ：n が非常に小さい場面（例えば数十要素以下）では実装が簡単で十分なことがあります。
• 書き込みコストが高い場面：書き込み（swap）をできるだけ減らしたい場合に選択ソートは有用です（ただし、さらに良い選択肢も存在します）。
• それ以外：大量データや高速化が必要な場面ではクイックソート、マージソート、ヒープソートなど O(n log n) のアルゴリズムを使うべきです。

他アルゴリズムとの比較（簡潔に）

• 挿入ソート（Insertion Sort）と比べると：挿入ソートは既にほぼソートされた入力に対して非常に高速（最良時 O(n)）になりますが、選択ソートは非適応で常に O(n^2)。ただし挿入ソートはデータの移動（書き込み）が多く、選択ソートは交換回数が少ない傾向にあります。
• バブルソート（Bubble Sort）と比べると：どちらも O(n^2) だが、バブルソートは安定であり、ある種の最良ケース（既ソート）で早く終わることがある。
• 快速／安定なソート（Quicksort/Mergesort）と比べると：大規模データでは選択ソートは非実用的。メモリや書き込み制約が特別に厳しい場合に限り検討される。

実装例（Python）

def selection_sort(a):
    n = len(a)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        if min_idx != i:
            a[i], a[min_idx] = a[min_idx], a[i]

安定化実装（挿入でのシフト）例：

def stable_selection_sort(a):
    n = len(a)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        # 最小要素を取り出して i に挿入（右にシフト）
        key = a[min_idx]
        while min_idx > i:
            a[min_idx] = a[min_idx-1]
            min_idx -= 1
        a[i] = key

まとめ

選択ソートは理解・実装が容易で、補助メモリが小さい場合や書き込みを抑えたい特殊なケースで役立つことがあります。しかし、比較回数が常に n(n−1)/2 と多く、大規模データには不向きです。安定性が必要な場合は実装上の工夫が必要で、その場合は移動コストが増える点に注意してください。実務では一般に O(n log n) のソートが標準で使われますが、アルゴリズム学習や特殊用途のために選択ソートの特徴（単純さ・最小スワップ特性）を理解しておくことは有用です。

参考文献

• 選択ソート - Wikipedia（日本語）
• Selection Sort — GeeksforGeeks（英語）
• Sorting algorithm — Comparison sorts（Wikipedia, 英語）
• MIT OpenCourseWare — 講義資料（選択・挿入・マージソートの解説）