交換法(バブルソート)

隣どうしを比べて入れ替える

前回までの探索は、並んでいるデータを速く探す話でした。ここからは、その「並んでいる状態」を自分で作る整列の話に移ります。最初は交換法です。バブルソートとも呼ばれ、軽い泡が水面に浮かぶように大きい値が端へ動いていく様子からこの名が付いています。

やることは驚くほど単純で、隣り合う2つを比べて順序が逆なら入れ替える、これを配列の端から端まで繰り返すだけです。1回の走査を終えると、いちばん大きい値が必ず末尾に到達します。そこから先は動かないので、次の走査では末尾を除いた範囲だけを見ればよくなります。

擬似言語で書くとこうなります

○整数型の配列: koukanhou(整数型の配列: data) 整数型: i, j, tmp for (i を 1 から dataの要素数 - 1 まで 1 ずつ増やす) for (j を 1 から dataの要素数 - i まで 1 ずつ増やす) if (data[j] > data[j + 1]) tmp ← data[j] data[j] ← data[j + 1] data[j + 1] ← tmp endif endfor endfor return data

二重の for が出てきました。外側の i は「何回目の走査か」、内側の j は「その走査で今どこを見ているか」を表します。内側の終わりが要素数 - i になっているのは、走査を1回終えるごとに末尾から1つずつ確定していくからです。ここを要素数 - 1 のままにしても答えは合いますが、確定済みの部分をむだに見ることになります。

3行の交換を分けて書く理由

交換の部分が3行になっている点に注目してください。data[j] ← data[j + 1] を先にやってしまうと、もとの data[j] の値が上書きされて消えます。だから tmp に一度どかしてから入れ替えます。この tmp のような一時的な置き場を、退避用の変数と呼びます。擬似言語の穴埋めでは、この3行のうち1行が空欄になる出題がよくあります。順番を入れ替えると値が壊れる、という理由から答えを決められるようにしてください。

何回比べるか

要素数が n のとき、1回目の走査は n - 1 回、2回目は n - 2 回と減っていきます。合計は n(n - 1) ÷ 2 回です。n が 5 なら 10 回、n が 100 なら 4950 回で、要素数が10倍になると比較回数はおよそ100倍になります。この増え方を後の回で O(n の2乗) として扱います。データが少ないうちは気になりませんが、件数が増えると急に苦しくなる方法だと覚えておいてください。

それでは、5個の配列で1回目の走査を追い、最大値が末尾へ動く様子を確かめましょう。

課題

  1. 各行を実行したあとの値を入れる
  2. 値が変わらない変数はそのままの値を入れる
  3. 配列は {5, 3, 4, 1, 2} の形で全体を書く

ヒント

1 / 12 行目のトレース

1○整数型の配列: koukanhou(整数型の配列: data)
2 整数型: i, j, tmp
3 for (i を 1 から dataの要素数 - 1 まで 1 ずつ増やす)
4   for (j を 1 から dataの要素数 - i まで 1 ずつ増やす)
5     if (data[j] > data[j + 1])
6       tmp ← data[j]
7       data[j] ← data[j + 1]
8       data[j + 1] ← tmp
9     endif
10   endfor
11 endfor
12 return data
実行した行ijtmpdata
実行前———{5, 3, 4, 1, 2}
3 行目

3 行目を実行したあとの値を入れてください。変わらない変数は、 そのままの値を入れます。まだ値が入っていない変数は「—」と入れます。