過去問クラブ 学ぶ、わかる、つづく。
ログイン
用語解説

選択ソート

残りの最小値を選ぶ

選択ソートは、未整列の部分から最小値などを選び、順に確定位置へ移す整列方法です。昇順なら、最初に全体の最小値を先頭へ、次に残りの最小値を二番目へ置きます。毎回、未処理の範囲から一つの値を選ぶ点が特徴です。隣同士を繰り返し交換するバブルソートとは動作が異なります。

Pythonによる例

def selection_sort(values):
    result = list(values)
    for start in range(len(result) - 1):
        minimum = start
        for index in range(start + 1, len(result)):
            if result[index] < result[minimum]:
                minimum = index
        result[start], result[minimum] = (
            result[minimum], result[start]
        )
    return result

内側のループでは最小値の位置を覚え、調べ終えてから交換します。

手順の例

5、2、4、1なら、最初に1を見つけて5と交換し、1、2、4、5になります。次は先頭の1を除く範囲で最小値を選びます。一回の選択で一つの確定位置が増えますが、途中の未整列部分が偶然整って見えることもあります。手順を省略せず、問題が指定する回数を確認します。

比較回数と交換回数

未処理の範囲を毎回調べるため、標準的な比較回数はn(n-1)/2程度で、時間計算量はO(n²)です。一方、交換は各段階で多くても一回なのでO(n)です。比較と交換の費用が異なる場面では、この違いが評価に関係します。既に整列済みでも、同じように最小値を調べる実装なら比較は減りません。

安定性と試験

離れた位置の要素を交換すると、同じキーを持つ要素の相対順序が変わる場合があります。したがって典型的な交換方式は安定とは限りません。試験では「最小値を探してから交換」という段階を区別し、内側の比較のたびに交換する別の実装と混同しないようにします。要素の値だけでなく同じ値の識別番号も付けると、安定性を確認しやすくなります。

参考資料

内容確認日:2026-11-13

この言葉を含む問題を探す

この用語に関連する問題

1問

用語一覧

6件