実際にバブルソートをやってみよう

実際にバブルソートをやってみよう

　図3の（1）のようにカードが並んでいるところを想像してください。

　ここでは7枚のカードが並んでいます。それぞれの位置を0からはじめて6まで番号を付けました。

　これを右端から順に、左隣と見比べます。左から始めてもかまいませんが、バブルソートはなぜか右から始めるのがお約束のようですのでこのようにします。その意味は次回以降で説明します。

　右端から見始めて、視点を1つ1つずらしながら、もし左側が右側よりも大きければコロコロと入れ替えていきましょう。

　はじめに、6番目と5番目のものを比べます。左の4の方が右の2よりも大きいので、図3の（2）のように入れ替えます。

　次に、5番目と4番目を比べます。図3の（3）のようにここでも入れ替わります。

考え方を押さえておこう

同様のことを左端に達するまで繰り返します。その結果どうなるかというと、図3の（4）のようになります。

　これで一巡目の入れ替えはおしまいです。右端にあった2が左から3番の位置まで「上がって」きました。また、1が一番左に来ました。

　続いてここまでと同様の手順を繰り返しますが、2回目は左端の0番目まで見る必要はありません。見ても構いませんが左端のものと交換する可能性はないからです。その理由は2回目以降で詳しくで説明します。

　よって2回目は1番目のところまでを見ます。3回目は2番目まで・・・と繰り返します。そして最後には図3の（5）のようになるはずです。ぜひ皆さんも実際に試してみてください。

　次回は、このバブルソートをプログラムにしていきます。この考え方をよく理解しておいてください。