バブルソートと比べてみよう

バブルソートと比べてみよう

　2ページ目で作った「mysort1()」と第2回目で紹介したバブルソートを比べてみましょう。今回は「一番小さなものを順に取り出して、取り出した順に並べた」だけでした。

　さて、最初のバブルソートをもう一度考えてみましょう。隣り合ったものを比較して、小さいものがあればそれを左側に置く、という作業を繰り返しました。それを何度も繰り返すのですが、一度右端からはじめて左へ見ていった結果、何が行われるのでしょう？

　はじめのバブルソートプログラムにちょっと手を加えてデバッグ文をいれて、ループごとに元の配列がどのように変わるかを見てみました。

本質的には同じこと！

　最初のループの結果、左端には一番小さなもの（1）が出てきます。

　再度、右側から見ていきますが、その結果、その次に小さなもの（2）が出てきます。何度か繰り返しをしますが、一度右から左へ走査（スキャンといいますが）をするのは、その中で一番小さなものを見つけることをしていたのです！

　上で作ったmysort1()も、本質的にはバブルソートをしているのです！

　bubble_sort()とmysort1()とを見比べてどうでしょうか？いかにもbubble_sort()はコンパクトです。一見、何をしているかわかりませんが、効率良く動きそうです。それに比べてmysort1()は行数も多いです。しかし、直感的にわかりやすくはないでしょうか？

　プログラムには技巧的なところがあります。最終的には一見して何をしているかわからないプログラムになることもあります。けれど、設計する際は、自然に直感的にわかるところからはじめたいものです。