バブルソート

バブルソート。

隣接するものと比較し、想定する順序と逆であれば入れ替える。

そんな作業を行い、最終的に想定した順に数字が並ぶ、というものです。


たとえば、こういう問題。

1～100までの番号のついた箱と、1～100までの番号がついたボールがある。それら100個の箱すべてにまず適当にボールをひとつずつ入れる。その後、箱1と箱2を比べ、（箱1のボールの数字）＜（箱2のボールの数字）の場合、ボールの入れ替えを行い、逆ならば入れ替えをしないものとする。そのような作業を箱2・箱3、箱3・箱4・・・と行い、最後には箱99と箱100の比較をし、それにて作業を終了する。この一連の作業を一回と数える。このとき、箱50の数字は最低何回以上の作業で確定するか？

結構ややこしい問題ですが、実はこれ中学受験レベルの問題。

簡単に解法を記しておきましょう。


まず、一回の作業を行ったとき。①のボールはどこに入っているかどうかわからないが、どのボールよりも小さいので、必ず箱100まで移動してくる。

また、二回目の作業では、先ほどの作業で①が確定したので、今度は②が他のボールより小さいため、箱99まで移動してくる。

これらのことより、作業を繰り返すごとに箱100、箱99、箱98・・・と順に入っているボールが確定していくことがわかる。

つまり、早ければ、箱100は１回、箱99は２回、箱98は３回で確定するわけです。

この調子でいくと、箱50は51回で確定することがわかります。

※この51回とは、交換回数自体ではない。また、作業が最も少ない場合を聞かれているのとも違う。もしそうならば、もともと箱1に100箱2に99・・・箱100に1が入っていれば良いことになり、問題として成立しない。あくまで、何回作業すれば、確実に定まるか、という問題である。


バブルソート自体はメジャーなアルゴリズムにあたるわけですが、これを小学６年生に解かせるとはなかなか面白いですね。

もし、交換回数を絡めた問題を出しても、小学生には解けるでしょう。この分野は、これから応用されて出題されるやもしれません。

ちなみに、バブルソートという語ですが、どうやら大きい順or小さい順に並ぶ様子が泡のようであるため、と聞いたことがあります。

参考までに。


☆生徒さん募集中！

詳しくはこちら↓
http://leo-edu.blog.so-net.ne.jp/2010-04-15