Pythonでアルゴリズム「バブルソート」：”景気のいい”ソート、ではありませんでした。

はい、「Pythonでアルゴリズム・シリーズ」ですよ😄！今回から、アルゴリズムの「本丸」である「並べ替え（ソート）」に切り込んでまいります！ソートは、小さい順あるいは大きい順に並べることです。

返り打ちに合わないように丁寧に見ていきましょう。今回取り上げるのは、数ある並べ替えアルゴリズムの中で、「バブルソート」です！だいたい、どんなテキストでも、「バブルソート」から始まりますね～🙂。

ご多分に漏れず、このブログも「バブルソート」から取り組みましょう！カメみたいに口から泡を吹かないよう、まずは「バブルソートって何だろう？」というところから確認しましょう！

「バブルソート」って何？

バブルソートは、並べ替えアルゴリズムの一つです。で、「バブル」って何ですかね！？

「ジュリアナ…トウキョー！！！😆」

それは、ちょっと味わってみたい「バブル景気」というやつですね！って違うわ（打ち合わせどおりですね🧡）。ここでは、バブルは、まさに「泡」です。泡は、軽いので浮かび上がります。この「浮かび上がる」という特徴があるので、「バブルソート」と呼ばれます。数値が小さい順（or大きい順）に浮かんでくるアルゴリズム何です。

ただ、アルゴリズムが分かりやすくて学びやすいのはいいのですが、端から端まで計算するので計算量は多め（処理速度は遅め）であることに注意が必要になります。

浮かびあがるといってもイメージが湧かない？ですか…。では、例によって図解をしてみますよ😄。

ループは、外側と内側の２つある

では、5個の数字を左から小さい順に並べるソートを例にとって、バブルソートの核心に迫ります😆！

バブルソートを行うには、ループが必要になります。しかも、2つのループを「入れ子」にします。

ループの「入れ子」とは、「ループの中にループがある」状態を指します。ここでは、「外側のループ」「内側のループ」という表現を使って解説していきますよ！

外側のループ：左から右へ、「小さい順」に値を決めていく

「外側のループ」の目標は、なんといっても「左から右の順に、小さい順に値を決めていく」ことです。1回目の外側のループの目標は、「0番の値」を決めることです。外側のループが4回転して、「3番の値」まで決まれば目標達成です（4番の値は自動的に決まります）。

上の図は、「外側1回目のループ」で、この中にある「内側のループ」が4回転します。ループ終了後、一番左（0番）の値が確定しました😆！

内側のループ：右から左へ、隣り合う値を比較して、小さい値を浮かびあがらせる。

内側のループは、「右から左へ、となりある値を比較して、右の値が小さければ交換」を繰り返します。外側のループにより決定したい値と、その右側を比較したら、内側のループは終了します。

この内側のループを右端から繰り返していくと、ループ範囲の中でもっとも小さい値が左側に「浮かび上がって」きます。この様子が、「バブル」なわけですね～。

内側のループ範囲は、どんどん狭まる

0番目の値が確定して、2回目のループに突入します。内側のループが、やはり一番右側の値から始まります。2回目のループの目標は、「1番の値」を決めることです。

外側1回目のループと同様に、「となりあう２値を比べて、右側が小さいなら交換する、右側が大きいなら何もしない」を繰り返します。すると、どんどん小さい値が浮かびあがりますが、決定したい番合（1番）を最後に比較したら、内側のループ終了です。外側1回目より、内側のループ回数が1回減ったことに気づきましたか～🙂？

このように、外側のループの回数が進むにつれ、小さい側の値の順番がどんどん決まっていき、内側のループの範囲は縮んでいくのです～😉。

外側最後のループ：内側のループは1回しか回らない

外側3回目のループは、外側2回目と同じ処理なので省略して、最後の外側のループ（4回目）を見てみましょう！

左側から３つ並びが決まってしまいました。3番目の値を決めることが、4回目のループの目標ですが、、、、もう比較する値が２つしか残っていないようです。

となれば、内側のループは、1回行うだけでよいわけです。内側のループは、最終的に1回転するのみとなとなりました😄。

これで、3番の値が決まりました。これにより、自動的に4番、すなわち、一番右の値も決まったので、並べ替え完了となります🎉！

やったね～！これが、バブルソートの処理の流れです。

「左から順に小さい値を確定していくため、右から順に値を比較しては交換するを繰り返す」ようすが見て取れましたか？このイメージをしっかりもちつつ、次回以降、実際にPythonのコードを書いてみることにしましょう。

本日は、ここまで～！

では、ビーダゼーン！

※私のやる気アップとブログの品質向上につながりますので、記事が気に入られた方は、「ポチっ」と好きボタンを押してくださったり、フォローいただけますと幸いです🙇。