選択法（選択ソート）シミュレーター

ALGORITHM

選択法とは何をしているか

選択法（選択ソート）は、まだ整列していない部分の中からいちばん小さい値を選び、その部分の先頭と交換するという操作を繰り返す整列です。 1回のパスで先頭から1個ずつ確定していくため、交換法（右端から確定）とは確定していく向きが逆になります。

トランプを並べ替えるとき、「残りの中でいちばん小さいカードを探して、左端に置く」という作業を繰り返すのと同じです。 シミュレーターでは、探している範囲を j（青）が動き、現在の最小値の候補が黄色で示されます。

min_pos は「値」ではなく「位置」を覚える

このアルゴリズムの中心にあるのが min_pos です。名前のとおり最小値の位置（添字）を覚えます。 なぜ値ではなく位置なのかというと、最後に交換するときに「どこにあるか」が分からなければ入れ替えられないからです。 「いちばん小さいのは 1 だ」と分かっても、それが配列のどこにあるか分からなければ Nums[i] と交換できません。

内側の繰り返しは i + 1 から

内側の j は i + 1 から始まります。i 自身はすでに min_pos = i として候補になっているので、 自分と自分を比べる必要がないからです。また i より前は確定済みなので、調べる範囲は自然と後ろへ狭まっていきます。

1パスで交換は1回だけ

交換法との最大の違いがここです。交換法は条件が成り立つたびに入れ替えるので交換が何度も起きますが、 選択法は探し終わってから1回だけ交換します。そのため交換回数は多くても n - 1 回で済みます。

要素数5の逆順で比べると、交換法は10回交換しますが、選択法は2回で済みます。 交換法のシミュレーターと見比べてみてください。

すでに整列済みでも交換は起きる

基本の書き方では、min_pos が i と同じでも交換の3行を実行します。これは同じ位置どうしの交換なので値は変わりませんが、 交換回数としては数えられます。無駄を省きたい場合は もし min_pos != i ならば という条件を足します。 条件の切り替えで、整列済みの配列の交換回数が 4回 → 0回（要素数5のとき）に変わることを確認できます。

CODE

3つの書き方で見る選択法

Nums = [5, 2, 4, 1]

i を 0 から 要素数(Nums) - 2 まで 1 ずつ増やしながら繰り返す:
｜min_pos = i
｜j を i + 1 から 要素数(Nums) - 1 まで 1 ずつ増やしながら繰り返す:
｜｜もし Nums[j] < Nums[min_pos] ならば:
｜⎿⎿ min_pos = j
｜temp = Nums[i]
｜Nums[i] = Nums[min_pos]
⎿ Nums[min_pos] = temp

表示する(Nums)

nums = [5, 2, 4, 1]

for i in range(len(nums) - 1):
    min_pos = i
    for j in range(i + 1, len(nums)):
        if nums[j] < nums[min_pos]:
            min_pos = j
    temp = nums[i]
    nums[i] = nums[min_pos]
    nums[min_pos] = temp

print(nums)

const nums = [5, 2, 4, 1];

for (let i = 0; i < nums.length - 1; i++) {
  let minPos = i;
  for (let j = i + 1; j < nums.length; j++) {
    if (nums[j] < nums[minPos]) {
      minPos = j;
    }
  }
  const temp = nums[i];
  nums[i] = nums[minPos];
  nums[minPos] = temp;
}

console.log(nums);

COST

比較回数と計算量

比較回数は交換法とまったく同じで、並び方に関係なく一定です。 違うのは交換回数だけで、こちらは要素数に比例する程度（n - 1 回）に抑えられます。 ただし処理全体の重さは比較回数が決めるため、計算量はどちらも O(n²) です。 「交換が少ない＝速い」と単純に言えない点に注意してください。

EXAM POINT

共通テスト「情報Ⅰ」での出題ポイント

1. min_pos の更新：min_pos = j の行が空欄になる形。値ではなく位置を代入する点が要点です。
2. 内側の開始値：j を i + 1 から の i + 1 の部分。なぜ i からではないのかを問われます。
3. 比較の向き：Nums[j] < Nums[min_pos] の不等号。> にすると最大値を探すことになり、大きい順に並びます。
4. 1パス後の配列：「1回目のパスが終わった時点の配列」を答える問題。先頭が確定する点が交換法との違いです。
5. 交換回数の比較：「交換法と選択法で交換回数が少ないのはどちらか」という比較問題。選択法は最大 n - 1 回です。

MISTAKES

よくある間違い

CHECK

理解度チェック