🗺️ アルゴリズムクエスト
STAGE 4 ― バブルソート ―
クリア 0 / 9
🧭 地図
STAGE 4

バブルソート

隣どうしを比べて N²
🎯 ミッション
バブルソートの手順と、比べる回数が N(N−1)/2(O(N²))になる理由を説明できるようになろう。8個の荷物を並べ終え、確認クイズに全問正解すれば合格。
未達成
ねこ博士
二分探索には「並んでいる」ことが必要だった。今日は、ばらばらのものを並べる並べ替え(ソート)を考える。王国の倉庫に、重さのばらばらな荷物が一列に置かれている。軽い順に左から並べたい。ただし、一度に比べられるのは2つの荷物だけ、とする。
うさ美
全体を見渡して一番軽いものを探せれば楽ですけど、2つずつしか比べられないと、それも比べ方を決めないといけないですね。
ねこ博士
一番素朴なやり方から始めよう。左端から、隣どうしを比べて、左のほうが重ければ入れ替える。これを右端まで1周やる。この手順をバブルソートと呼ぶ。1周やると、何が起きるかな。
うさ美
重い荷物は、比べるたびに右へ送られていく。一番重い荷物は、どこにあっても、そこから先は毎回勝って右へ送られるので、1周すると必ず右端に来ます。
ねこ博士
そう。泡(バブル)が水面へ上がっていくように、大きいものが端へ浮かんでいくので、この名前がある。1周で右端が1つ確定する。次の周は、右端を除いた残りで同じことをすればいい。
1周目:N 個のうち隣どうしを N−1 回比べる → 一番重いものが右端で確定 2周目:残り N−1 個で N−2 回比べる → 2番目に重いものが確定 …… 最後の周:残り2個で1回比べる
ねこ博士
比べる回数の合計を、N 個の場合で式にしてごらん。足し算は、同じ式を逆の順番でもう1つ書いて、上下に足すと楽になるよ。
うさ美
(N−1) + (N−2) + … + 1。逆順に書いた 1 + 2 + … + (N−1) と上下に足すと、どの組も N で、それが N−1 組。2つ分の合計が N(N−1) なので、1つ分はその半分です。
1 + 2 + … + (N−1) = N(N−1) ÷ 2 N = 8 なら 8×7÷2 = 28 回 / N = 1000 なら 約50万回 / N = 100万 なら 約5000億回 N(N−1)/2 = (N² − N)/2 → いちばん大きく効くのは N² の項 → 計算量 O(N²)
うさ美
N が10倍になると、比べる回数は約100倍。100万個を並べるのに5000億回……。二分探索で20回で探せても、その前の並べ替えでこれでは意味がないですね。
ねこ博士
そうなんだ。O(N²) は、N が大きくなるととても重い。バブルソートは、どんな並びでも同じ回数だけ比べる(入れ替えの回数は並びによる)。わかりやすい代わりに遅い。
うさ美
もっと速く並べる方法はあるんですか?
ねこ博士
ある。鍵は、1回の比較で分かったことを、もっと有効に使うことだ。バブルソートは、隣どうしの比較の結果を、その2つの順番にしか使っていない。次のステージでは、1つの基準と比べて全体を2つのグループに分けてしまう方法を見よう。

確認クイズ

Q1. バブルソートで1周(左端から右端まで)比べ終わると、必ず何が起きる?

Q2. 10個の荷物をバブルソートで並べるとき、比べる回数は?

Q3. バブルソートの計算量は?