ソート（sort）とは、日本語で「並べ替える、分類する、仕分けする」などの意味があります。プログラミングでソートというと、バラバラに並んだ数字のカードを小さいものから大きいものに並べ替える（昇順）、大きいものから小さいものに並べ替える（降順）、の事をいいます。プログラミングでソートをする方法（アルゴリズム）は色々あり、今回はバブルソートを取り上げます。
他のソートのアルゴリズムは以下の記事を参照ください。
バブルソートとは？
バブルソート（bubble sort）とは、隣り合った数字を比べて並べ替えていき、昇順または降順に並べ替える方法になります。
言葉だけだと分かりにくいので、図を用いて解説していきます。まず、始めに下図のように5枚の数字のカードがバラバラに並んでいるとします。
これを一番後ろ（または一番前）のカードから順に大小を比較します。今回の例では、昇順（小さいものから大きいものへ）で並べ替えていきたいと思います。
Step1：一番後ろのカードから
まず始めに、一番後ろのカードから順に隣り合うカードの大小を比較して、右側のカードの方が小さい場合はカードを入れ替えるという操作を行います。
Step1-1：3と1のカードの比較
まずStep1-1として3と1のカードを比較します。一番後ろのカード3とその左横のカード1を比較して、一番後ろの数字の方が大きければ、そのまま。小さければカードを入れ替えます。今回は一番後ろである3のカードの方が1より大きいのでそのままです。
Step1-2：1と5のカードの比較
続いて、Step1-2として、1と5のカードを比較します。右側のカード1と左側のカード5を比較して、右側のカードの方が大きければ、そのまま。小さければカードを入れ替えます。今回は右側のカードである1のカードの方が5より小さいので、入れ替えます。
Step1-3：1と2のカードの比較
続いて、Step1-3として、1と2のカードを比較します。右側のカード1と左側のカード2を比較して、右側のカードの方が大きければ、そのまま。小さければカードを入れ替えます。今回は右側のカードである1のカードの方が2より小さいので、入れ替えます。
Step1-4：1と4のカードの比較
続いて、Step1-4として、1と4のカードを比較します。右側のカード1と左側のカード4を比較して、右側のカードの方が大きければ、そのまま。小さければカードを入れ替えます。今回は右側のカードである1のカードの方が4より小さいので、入れ替えます。
ここまででStep1は終了です。Step1で一番左端（1のカード）が確定しました。
Step2：一番後ろのカードから
続いて、Step2です。Step2でもStep1と同様に、一番後ろのカードから順に隣り合うカードの大小を比較して、右側のカードの方が小さい場合はカードを入れ替えるという操作を行います。
Step2-1：3と5の比較
まずStep2-1として3と5のカードを比較します。一番後ろのカード3とその左横のカード5を比較して、一番後ろの数字の方が大きければ、そのまま。小さければカードを入れ替えます。今回は一番後ろである3のカードの方が5より小さいので入れ替えます。
Step2-2：2と3の比較
続いて、Step2-2として、2と3のカードを比較します。右側のカード2と左側のカード3を比較して、右側のカードの方が大きければ、そのまま。小さければカードを入れ替えます。今回は右側のカードである3のカードの方が2より大きいので、そのままにします。
Step2-3：4と2の比較
続いて、Step2-3として、4と2のカードを比較します。右側のカード4と左側のカード2を比較して、右側のカードの方が大きければ、そのまま。小さければカードを入れ替えます。今回は右側のカードである2のカードの方が4より小さいので、入れ替えます。
ここまででStep2は終了です。1と2の比較を行っていませんが、Step1で一番左端（1のカード）が確定している為です。また、Step2で左から2番目（2のカード）も確定しました。
Step3：一番後ろのカードから
続いて、Step3です。Step3でもStep1、2と同様に、一番後ろのカードから順に隣り合うカードの大小を比較して、右側のカードの方が小さい場合はカードを入れ替えるという操作を行います。
Step3-1：3と5の比較
まずStep3-1として3と5のカードを比較します。一番後ろのカード5とその左横のカード3を比較して、一番後ろの数字の方が大きければ、そのまま。小さければカードを入れ替えます。今回は一番後ろである5のカードの方が3のカードより大きいので、そのままにします。
Step3-2：4と3の比較
まずStep3-1として4と3のカードを比較します。後ろから2番目のカード3とその左横のカード4を比較して、後ろの数字の方が大きければ、そのまま。小さければカードを入れ替えます。今回は右側（後ろ側）である3のカードの方が4のカードより小さいので、入れ替えます。
これで昇順に並べ替えることができました。
＊
＊
＊
バブルソートの名前の由来ですが、各値が泡のようにふわふわ移動していく（本記事で言えば、1のカードがイメージしやすい？）のがバブルソートと言われるようになった由来とか由来でないとか…。
＊
＊
＊
バブルソートを実際にPythonで書いてみました。是非ご覧ください。
コメント