バブルソートと選択ソートの違い｜比較回数と交換回数を図解

パソコンは、バラバラのデータをどうやって小さい順に並べるのでしょう？ 最小のものを一度に見抜いているのでしょうか？

整列（ソート）とは、決めた基準に従ってデータを並べ替えることです。

小さい順を昇順、大きい順を降順といいます。今回は 5・3・8・1 を使い、2つの手順を比べましょう。

先に結論：「隣と交換」と「最小を探して交換」が違う

今回の基本形では、4個の比較はどちらも6回ですが、実際の交換は交換法が4回、選択法が2回です。比べた回数と、入れ替えた回数は別と押さえましょう。

交換法は左から右へ比較し、途中で並んでも予定の周を最後まで行う方式で説明します。手順を変えると回数も変わるため、以下では条件をそろえて追います。

50人の名簿、どう並べ替える？

部誌の締め切り前夜。ユウキは、50人ぶんの名簿を五十音順にする係になりました。

ユウキ「手でやると、30分くらいですかね……」
テッパン先輩「手順にできれば、コンピュータにも任せられるよ」
Sandy「『ええ感じに並べて』では通じへんで。何と何を比べるか、決めよか」

先輩は名簿を一瞬で並べます。これは物語の場面で、処理時間を測定したものではありません。速さを比べる前に、まず並べ替える手順を見てみましょう。

まずは4枚の数字カードで、動きを見える大きさにしましょう。

名簿なら名前や読み仮名、得点表なら得点のように、並べる基準となる項目を決めます。ここからは数字の値を基準に、昇順で考えます。

交換法は、隣どうしを比べて入れ替える

交換法では、隣り合う2つの値を比べ、左の値が右の値より大きければ交換します。今回は左から右へ進み、確定した右端を次の周から外す方式です。

最初の並びは 5・3・8・1。1周目を細かく追ってみます。

ここで最大の8が右端に来ました。隣との比較で大きい値が右へ進み続けるため、1周が終わると、その範囲の最大が右端に確定します。

Sandy「一発で全部は並ばん。でも、いちばん右は決まったやろ」
ユウキ「じゃあ、次は8まで見に行かなくていいんだ！」

2周目は残り3枚だけ。3と5はそのまま、5と1を交換し、3・1・5・8 になります。3周目に3と1を交換すると完成です。

比較は3＋2＋1＝6回、実際の交換は2＋1＋1＝4回でした。比較しても、必ず交換するわけではありません。

なお、右から左へ比較を進める方式なら、左端に最小を確定させる説明になります。「交換法ならいつでも最大が右端」と方向を外して覚えないことが大切です。

選択法は、残りから最小を探して置く

選択法は、まだ並びが確定していない範囲から最小を探し、その範囲の先頭と交換します。こちらは左側から順に確定する方法です。

同じ 5・3・8・1 で、各周を追いましょう。

ここでいう「先頭」は、配列全体の先頭とは限りません。2周目なら2番目、3周目なら3番目が、残りの範囲の先頭です。

最小を探すときは、残りの先頭を仮の最小にします。1周目なら候補は5。次の3を見て候補を3へ変え、8では変えず、最後の1で候補を1へ変えます。

ここまでは候補の位置を覚え直すだけで、カードは動かしません。 残りをすべて見終わってから、最小の1と先頭の5を交換します。

ユウキ「候補を更新するたびに、カードも交換するの？」
Sandy「そこは別や。探してる間は『いま最小なんは何番目か』を覚える。置くんは、探し終わってからやで」

この例では比較が3＋2＋1＝6回、実際の交換が1＋0＋1＝2回。3周したことと、3回交換したことを混同しないようにしましょう。

比較回数は、なぜ n×(n−1)÷2 なのか

ここでは次の条件で回数を数えます。

• 交換法は確定した右端を外し、途中で並んでも予定の周を最後まで行う。
• 選択法は残りの先頭を候補とし、残りの他の値と比べて最小を探す。
• 「比較」はデータの値どうしの比較。「繰り返しを続けるか」の判定は含めない。
• 「交換」は異なる位置の2つのデータを実際に入れ替える操作。自分自身との交換は省く。

この基本形では、n個のデータの比較回数は、どちらも次の合計になります。

(n−1)＋(n−2)＋…＋1＝n×(n−1)÷2

外側の繰り返しが「何周目か」を進め、内側の繰り返しが「その周の比較」を進めます。比較する範囲が1つずつ短くなるため、n×n回ではありません。

式を丸暗記する前に、4個なら3回＋2回＋1回と数えましょう。この合計を逆順の1＋2＋3と足すと、各組が4になり、3組で12。元の合計はその半分なので6です。同じ考え方で、n個ならn×(n−1)÷2になります。

10個なら45回、100個なら4,950回。データは10倍ですが、比較回数は110倍です。件数が増えると、必要な比較が急に多くなることが分かります。

50人の名簿なら50×49÷2＝1,225回。ただし、この回数も今説明した基本形の値で、あらゆるソートや実際の名簿アプリが1,225回比較するわけではありません。

比較が同じなら、速さも同じ？

比較回数が同じでも、実行時間が同じとは限りません。 交換にかかる作業や、プログラムの書き方なども影響します。

逆順のデータでは、交換法の交換回数は多くなります。選択法は1周に多くても1回なので、データを入れ替える作業が重ければ、その少なさが役立ちます。

一方、交換法には「1周して一度も交換しなければ終了する」という改良もあります。すでに昇順の4個なら、最初の3比較・交換0回で終了できます。今回の途中終了なしの方式なら、同じ入力でも6比較です。

Sandy「『比較回数はいつでも同じ』まで広げたらあかん。どの手順の話か、そろえよな」
ユウキ「方法の名前だけで、回数が全部決まるわけじゃないんですね」

また、大量のデータには、マージソートなど、より比較の手数を抑えられる方法もあります。交換法と選択法は、手順を追い、方法を比べるためのよい入口です。

それでも並べる理由は、探しやすくなるから

並べ替えると、一覧を見やすくしたり、順位を付けたりできます。同じ基準で整列したデータに二分探索を使えるのも利点です。

では、最初に並べ替える手間は、どのくらい探せば回収できるのでしょう。固定された100個のデータを何度も探す、単純なモデルを考えます。

毎回線形探索をするなら、1回につき最大100個を確認。先に今回の選択法で並べるなら4,950比較が必要ですが、その後の二分探索は1回につき最大7個の中央要素を確認します。

探索回数をqとすると、目安は 100q と 4950＋7q です。

• 53回探す場合： 毎回線形探索なら5,300、先に並べるなら5,321。
• 54回探す場合： 毎回線形探索なら5,400、先に並べるなら5,328。

このモデルでは、54回目から先に並べる側の合計が小さくなります。 最初にかかる整列の手間を、その後の探索の少なさで回収する考え方です。

ただし、これは各探索の最悪回数を足した目安です。二分探索は「中央要素を1つ確認」を1回とし、細かい演算子の数までは数えていません。交換や実行時間も含めていないので、実際のソフトの損益分岐点ではありません。

一度しか探さない場合や、途中でデータが追加・変更される場合は、準備の負担も考える必要があります。「並べれば必ず得」ではなく、どう使うかまで含めて手順を選ぶわけです。

オリジナル例題：周回数と交換回数を分けよう

次は本記事のオリジナル学習例です。実際の共通テスト問題ではありません。

4・1・3・2 を今回の選択法で昇順にします。比較回数と、実際の交換回数はそれぞれ何回でしょう。最小がすでに範囲の先頭なら、交換は省きます。

解答：比較6回、交換2回です。

1周目は最小の1と4を交換し、1・4・3・2。2周目は残りの最小2と4を交換し、1・2・3・4。3周目は3と4を比べますが、最小3が範囲の先頭なので交換しません。

比較は3＋2＋1＝6回。交換は1＋1＋0＝2回です。見た目では2周目で並んでいても、今回の選択法は3周目の比較も行います。

覚えたいのは、何を数えたか

• 交換法は隣どうしを比べ、逆順なら交換する。今回の方向では右から確定する。
• 選択法は残りから最小を探し、残りの先頭と交換する。左から確定する。
• 今回の基本形の比較回数は、両方ともn×(n−1)÷2。途中終了などの条件が変われば回数も変わる。
• 比較回数・交換回数・周回数・実行時間は区別する。

テッパン先輩「回数が分かれば、方法を比べられるね」
Sandy「並んだ、で終わらんと、『どんな手順で、何回やったか』まで追えたらええな」

関連する学習テーマは、情報Ⅰサバイバルの記事一覧から確認できます。手順を実際のプログラムや作品にして試したい方は、プログラミングスクールSandboxもご覧ください。

参考資料

• NIST：bubble sort — 隣接比較と交換、交換がなくなったら終了する方式、比較範囲を縮める改良。
• NIST：selection sort — 残りの最小を最終位置に置く方法と、交換による実装。
• NIST：binary search — 整列済みデータから範囲を狭めて探索する方法。