考え方をひっくり返してみよう

プログラムの基礎を整理しよう

　バブルソートのアルゴリズムからプログラムを考える本連載ですが、「第3回：コンパクトなプログラムvs.直感でわかるプログラム（http://www.thinkit.co.jp/article/62/3/）」では、一見異なるアプローチながらバブルソートと同じような方法でプログラムを書きました。今回はまた少し違うアプローチをしてみましょう。

　同じことをするのにいくつも方法を考えるのは、まわりくどいと思われるかもしれませんが、プログラムの基礎になる考え方を整理する、つまり設計をすることであり、とても重要です。そして、プログラムはそれを「そのまま」表現したものであるべきです。

　前回は、カードの集まりの中から1枚を「取り出す時に」一番小さいものを選び、あとはそれを「並べるだけ」でソートを実現しました。

　これとは逆の考え方ですが、次のような方法が考えられます。

（1）カードの集まりからどれでもよいので1枚取り出す。
（2）別のところに順に並べる時に「適切な」位置に入れる。つまり、選んだカードよりも大きいものがあればその「前」に置く。
（3）（1）（2）を元のカードの集まりがなくなるまで繰り返す。

どうやって適切な置き場所を探すか

　取り出す時は楽をしますが、並べる（置く）時に少しばかり知恵を使います。

　上の（2）で「適切な」置き場所を探しますが、その方法は次のような手順になるでしょ
う。

　上の図の右側にあるカードはソートされたものですから、小さい順に並んでいるはずです。ですから、取り出したカードを、ソートされたカードの左端から順に比べていきます。

　取り出したカードよりも大きなカードに出くわしたら、その前が「適切な」場所であることがわかります。

　例えば、右側のカードが以下のように並んでいるとします。

　　2、3、6、8

　この時取り出した1枚が5だったとすれば、左から順に見ていって6が現れたところに5を「挿入」することになります。よって並びは以下のようになります。

　　2、3、5、6、8