交換法（バブルソート）シミュレーター

ALGORITHM

交換法とは何をしているか

交換法（バブルソート）は、隣り合う2つの値を比べ、順序が逆なら入れ替えるという操作を繰り返す整列です。 左から順に隣どうしを比べていくと、大きい値が次々と後ろへ押し出され、 1回のパスが終わるたびに、未確定部分でいちばん大きい値が右端に確定します。

水中の泡（bubble）が少しずつ上へ浮かんでいく様子に似ているため、バブルソートと呼ばれます。 シミュレーターでは、確定したマスが緑になり、右から順に緑が増えていく様子が確認できます。

temp がなければ値が消える

入れ替えは3行で書きます。この temp は一時的に値を置いておく変数で、これがないと入れ替えは成り立ちません。

temp = Nums[j]          ← 左の値を退避
Nums[j] = Nums[j + 1]   ← 左に右の値を入れる
Nums[j + 1] = temp      ← 右に退避した値を入れる

もし1行目を書かずに Nums[j] = Nums[j + 1] から始めると、その瞬間に Nums[j] の値が上書きされて消えます。 すると3行目で戻すべき値がもう手元にありません。結果として同じ値が2つ並ぶことになります。 「なぜ temp が必要か」は説明を求められることがあるので、この流れで覚えておくと確実です。

比べる範囲がだんだん狭くなる

内側の繰り返しは 要素数 - 2 - i までです。- i があるのは、 すでに確定した右側をもう一度比べる必要がないからです。 1回目のパスでは右端の1個が確定し、2回目のパスでは右端の2個が確定しているので、その分だけ範囲を狭められます。

比較回数は一定、交換回数はデータ次第

基本の書き方では、比較回数は並び方に関係なく一定です。要素数 n のとき (n-1) + (n-2) + … + 1 = n(n-1)/2 回になります。 一方、交換回数はデータによって変わります。すでに整列済みなら0回、逆順なら比較のたびに交換が起きて最大になります。

表の3つは、シミュレーターの「整列済み」「ばらばら」「逆順」でそのまま確認できます。 比較回数はどれも10回で同じなのに、交換回数だけが変わることを目で確かめてください。

早期終了という工夫

整列済みのデータでも最後まで比べ続けるのは無駄です。そこで「このパスで交換が1回も起きなかったら、すでに整列済みだから抜ける」という判定を足すことがあります。 条件で「交換がなければ抜ける（早期終了）」を選ぶと、整列済みのデータが1パスだけで終わる様子が確認できます。 ただし逆順のような最悪の場合は最後まで回るので、最悪の計算量は O(n²) のままです。

CODE

3つの書き方で見る交換法

擬似言語（DNCL風）・Python・JavaScript で並べました。変数名と処理の順番はすべて揃えてあります。

Nums = [5, 2, 4, 1]
swap = 0

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

表示する(Nums, swap)

nums = [5, 2, 4, 1]
swap = 0

for i in range(len(nums) - 1):
    for j in range(len(nums) - 1 - i):
        if nums[j] > nums[j + 1]:
            temp = nums[j]
            nums[j] = nums[j + 1]
            nums[j + 1] = temp
            swap = swap + 1

print(nums, swap)

const nums = [5, 2, 4, 1];
let swap = 0;

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

console.log(nums, swap);

COST

比較回数と計算量

要素数が2倍になると、手間はおよそ4倍になります。これが O(n²)（要素数の2乗に比例）の意味です。 探索の 二分探索 が O(log n) だったのと比べると、整列はずっと重い処理だと分かります。 だからこそ「1回探すだけなら整列せずに 線形探索」という判断が成り立ちます。

なお、要素数10個で「逆順」を選ぶと45回の交換が起きるため、ステップ数もかなり多くなります。 全体の流れをつかみたいときは「自動再生」＋「はやい」で通して見るのがおすすめです。

EXAM POINT

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

1. 入れ替えの3行：temp を使った入れ替えの順番。3行のうち1行が空欄になる形が定番です。
2. 内側の範囲：要素数 - 2 - i の - i の部分。「なぜ範囲が狭くなるのか」を説明させる問題もあります。
3. 1パス後の配列：「1回目のパスが終わった時点の配列を答えよ」という問題。途中の状態を書けることが大切です。
4. 交換回数：与えられた配列で交換が何回起きるかを数える問題。比較回数と混同しないよう注意します。
5. 比較演算子の向き：> を < にすると大きい順（降順）に並びます。「降順にするにはどこを変えるか」という形で問われます。

MISTAKES

よくある間違い

CHECK

理解度チェック

まず自分で考え、答えを開く前に上のシミュレーターで確かめてみてください。