選択ソート｜コードで実践

選択ソート

このレッスンで分かること

内側ループは「最小値とその位置を記録する」だけ

発想がストレートで、紙の上でも追いかけやすいので、ソートの導入として人気があります

選択ソート (selection sort) は、配列を左から順に「ここから右の最小値」を選んで持ってくる、という発想のソートです

選択ソートとは

残り部分から最小値を選んで先頭から順に確定させる選択ソートを実装し、バブルソートとの違いを理解する。本レッスンでは、選択ソートの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

選択ソート (selection sort) は、配列を左から順に「ここから右の最小値」を選んで持ってくる、という発想のソートです。バブルソートが「隣同士の交換を繰り返す」のに対し、選択ソートは「最小値の場所だけ覚えておいて、1 ラウンドに 1 回だけスワップする」ので、スワップ回数が少ないのが特徴です。

発想がストレートで、紙の上でも追いかけやすいので、ソートの導入として人気があります。計算量は O(n^2) でバブルソートと同じですが、メモリへの書き込み回数が O(n) と少なく、書き込みコストが高い環境では選択ソートのほうが速いこともあります。

選択ソートは「未確定領域の最小を選ぶ」を n - 1 回繰り返す。スワップ回数は最大でも n - 1 回。

アルゴリズムの動き

[4, 2, 7, 1, 3] をソートする例を追います。

1 周目: [4, 2, 7, 1, 3] の最小は 1 (index 3)。先頭の 4 と入れ替えて [1, 2, 7, 4, 3]。
2 周目: 残り [2, 7, 4, 3] の最小は 2。すでに位置にあるのでそのまま [1, 2, 7, 4, 3]。
3 周目: 残り [7, 4, 3] の最小は 3。7 と入れ替えて [1, 2, 3, 4, 7]。
4 周目: 残り [4, 7] の最小は 4。そのまま [1, 2, 3, 4, 7]。

4 ラウンドで完了です。

diagram (will load when visible)

図のポイント (テキスト併記)

内側ループは「最小値とその位置を記録する」だけ

内側ループは「最小値とその位置を記録する」だけ。実際の交換は外側ループの 1 回ごとに 1 回。

Python での実装

Python

def selectionSort(arr):
    a = list(arr)
    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]
    return a

min_idx で「現在の最小値の位置」を追います。内側ループでは要素を入れ替えず、位置 だけ更新するのがポイント。

JavaScript での実装

JavaScript

function selectionSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[minIdx]) minIdx = j;
    }
    if (minIdx !== i) {
      const tmp = a[i];
      a[i] = a[minIdx];
      a[minIdx] = tmp;
    }
  }
  return a;
}

バブルソートとの比較

観点	バブルソート	選択ソート
比較回数	`O(n^2)`	`O(n^2)`
スワップ回数	最悪 `O(n^2)`	最大 `n - 1`
安定ソートか	`安定`	一般実装は `不安定`
早期終了	可能 (フラグで)	不可

選択ソートはスワップが少ない一方、不安定 (同じ値の相対順序が崩れる) のが弱点。

よくある間違い

1 つ目は 内側ループの開始位置。j = i + 1 ではなく j = 0 にすると、毎回全体を見てしまい計算量は同じでも余計な比較が増えます。2 つ目は min_idx の初期化を忘れる。min_idx = i を毎ラウンド最初にリセットしないと、前ラウンドの値が残ります。3 つ目は 交換条件の省略。min_idx != i のチェックを入れないと、変化がないときも書き込みが発生してパフォーマンスが落ちます。

やってみよう

[3, 1, 4, 1, 5, 9, 2, 6] を入れて結果が [1, 1, 2, 3, 4, 5, 6, 9] になるか確認する。
降順にしたいときはどこを直せばよいか考える。ヒント: < を > に変える。
スワップ回数をカウントする変数を追加して、バブルソートと比較してみる。

安定性を壊す例

選択ソートが 不安定 と言われる理由を、レコード型のデータで確認します。[(5, "a"), (5, "b"), (3, "c")] を 数値 でソートすると、選択ソートは 1 周目で先頭の (5, "a") と最小値 (3, "c") を入れ替えて [(3, "c"), (5, "b"), (5, "a")] になります。

入力時の (5, "a") と (5, "b") の順序は a -> b でしたが、結果は b -> a と逆転しています。一般的な選択ソートは「最小値を末尾までスキャンして 1 度のスワップで持ってくる」ため、同値要素を跨いだスワップが起き相対順序が崩れます。安定性を保ちたいときは挿入ソートかマージソートを選んでください。

Python

# 不安定の例
records = [(5, "a"), (3, "b"), (5, "c")]
# 選択ソートだと (5, "a") -> (5, "b") の順が (5, "b") -> (5, "a") に逆転する

不安定 ソートは要素自体の値が同じなら問題ないが、レコードの 副次的なフィールド を保ちたいときは要注意。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は 挿入ソート で、残り部分から最小値を選んで先頭から順に確定させる選択ソートを実装し、バブルソートとの違いを理解するを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

選択ソートの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 選択ソートとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

選択ソート