バブルソート
バブルソートは最も説明しやすいソートアルゴリズムです。隣り合う2つの値を比較し、順序が逆なら交換し、これを繰り返します。長いリストでは遅いものの、どの手順も追いやすいため、最初に見るアルゴリズムの定番です。
考え方
リストを左から右へたどり、隣り合う値のペアを順に見ます。左の値が右より大きければ交換します。最後まで来ると、泡が水面に浮かぶように、最大の値が最後の位置まで運ばれています。このひと通りの走査をパスと呼びます。リストが整列するまでパスを繰り返します。
例
5, 1, 4, 2, 8 を例にします。最初のパスでは5と1を比較して交換し、続いて5と4(交換)、5と2(交換)、5と8(交換なし)を比較します:1, 4, 2, 5, 8。8は最終位置に確定しました。2回目のパスでは1と4(交換なし)、4と2(交換)、4と5(交換なし)を比較します:1, 2, 4, 5, 8。3回目のパスでは交換が一度もないので、リストは整列済みです。比較9回、交換4回です。
パスごとに確定する値が1つ増える理由
パスの途中では、それまでに見た最大の値が常に運ばれていきます。パスがその値に達すると、以後の比較のたびに1つずつ右へ動きます。そのため最初のパスで最大の値が最後に、2回目のパスで2番目に大きい値がその直前に置かれ、以下同様です。k回目のパスの後、最後のk個の位置は確定し、次のパスは1つ手前で終われます。だからパスはだんだん短くなります。
交換回数は転倒数と等しい
転倒とは、順序が逆になっている値のペア、つまり大きい値が小さい値より前にあるペアのことです。順序が逆の隣り合う2つを交換すると、転倒がちょうど1つ消え、新しい転倒は生まれません。そのため比較の順番にかかわらず、バブルソートの交換回数は初期リストの転倒数とちょうど同じになります。整列済みのリストには転倒がなく、n個の値の逆順リストには考えられる最大のn(n − 1)/2個があります。
早期終了とコスト
1回のパス全体で交換がなければ、隣り合う値はすべて正しい順序で、リストは整列済みです。これを判定すれば、バブルソートは整列済みのリストをn − 1回の比較、1パスで終えられます。最悪の場合はやはりn − 1回のパスとn(n − 1)/2回の比較が必要で、交換回数の平均はn(n − 1)/4回です。どちらもn²に比例して増えるので、リストの長さが2倍になると並べ替えの時間は約4倍になります。
バブルソートは安定です。等しい値は交換されないので、元の順序が保たれます。追加のメモリなしでその場で並べ替えます。挿入ソートも同じ性質を持ち、たいていより少ない手順で済みます。マージソートやクイックソートはn log nに比例する時間で済み、長いリストではずっと短くなります。
試してみよう
アプリを開いて「再生」を押すか、「ステップ」で比較を1回ずつ進めます。比較中の2つの値は強調表示され、交換は専用の色で示され、確定した値は緑色になります。逆順のリストで最悪の場合を、ほぼ整列済みのリストで早期終了により数回のパスで終わる様子を確かめたり、上の例の数値を入力したりしてみましょう。
よくある質問
バブルソートの時間計算量は?
最悪と平均の場合はO(n²)で、n個の値に対して最大n(n − 1)/2回比較します。早期終了があれば、整列済みのリストはO(n)、つまり1パスで終わります。追加メモリはO(1)だけです。
バブルソートは安定ですか?
はい。左の値が真に大きいときだけ隣り合う2つを交換するので、等しい値が互いを追い越すことはなく、元の順序が保たれます。
バブルソートと挿入ソートの違いは?
どちらも隣り合う値を交換し、交換回数はどちらも転倒数と同じです。バブルソートは未整列の部分全体をパスで走査しますが、挿入ソートは新しい値を必要な分だけ前へずらすので、たいてい比較回数が少なく、ほぼ整列済みのリストでは特にそうです。
バブルソートが向いているのはどんなとき?
主に教育用と、速度より単純さが大事なごく短いリストです。それより大きなデータには、プログラミング言語に組み込まれたソートの方がはるかに高速です。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
バブルソートを試す