【１】バブル・ソート

　いま、ここに０から９までの数字が書かれた１０枚のカードがシャッフルされで並んでいるとします。でたらめに切り混ぜられたカードが１０枚程度ならば、それを大きさの順に並べ換える場合、多くの人は無意識のうちに単純選択法・単純挿入法・単純交換法のいずれかの手順でカードを並べ換えていきます。

　これらの方法はだれでも思いつく単純素朴な方法であって人間の思考にもっとも近く、いずれもプログラム・リストがたった数行で書けるシンプルなアルゴリズムになっています。

　プログラムの設計はおぼろげな概念を具体的な形に表してゆく仕事であって、この形はすべて設計者の意識の働きから生まれてきます。つまり、コーディングの第一歩は無意識の下に行なった並べ換え手順を意識的に分析してプログラムに組みあげていくことから始まるわけですが、これらのソート法のうち単純交換法に相当するのが以下に述べるバブル・ソートです。バブル・ソートについては多くの本で取り上げられている割りにはこれといった長所のないソートであるとする見方もありますが、ここでは次節で取り上げるコム・ソートへの導入をはかるためにバブル・ソートを紹介します。

　バブル・ソートでは隣接する２つのデータを順次比較して、２つのデータの大小関係が正しければそのまま、逆であれば交換するという方法で並べ替えを行ないます。先頭から末尾へ順番に比較して必要に応じて交換すると、１回目の走査で１番大きなデータが末尾の位置に、２回目の走査で２番目に大きなデータが末尾から２番目の位置にきます（末尾から先頭へ走査するときは小さなデータが先頭の位置にきます）。データが移動するとき、水中で重い石が沈み軽い泡が浮き上がる様を連想させることから泡立ち法ともいわれ、データ数が少ないときによく利用されます。

　Ｎ個のデータならＮ−１回の走査が必要ですが、途中でソーティングが終っていることがあるかもしれません。そこで無駄な走査を防ぐために交換スイッチＳＷを設けます。各回の走査の度ごとにスイッチを交換しない（ＳＷ＝０）にセットしておき、もし走査の間にデータの入れ替えがあれば交換スイッチを交換した（ＳＷ＝１）に切り換えます。走査の間に一度でも交換があればさらに走査を繰り返しますが、なければソーティングを終了します（停止条件付きバブル・ソート）。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】コム・ソート

　バブル・ソートの欠点は実行速度が遅いことですが、バブル・ソートに２〜３行プログラムを追加する簡単な手直しだけで劇的に速度を向上させることのできる画期的なソート・アルゴリズムがLacey とBox によって発想考案されたコム・ソートです。コム・ソートでは最高速だといわれているクイック・ソート並みかそれ以上の速度が出ます。しかも、プログラムが長くなるクイック・ソートに比べ、コム・ソートのコーディングは至って簡単です。

　バブル・ソートではデータを比較する回数が多く、かつ、１回の交換につき１コマずつしかデータが位置移動しないため実行速度が遅くなります。そのため、コム・ソートでは隣接するデータを連続的に比較するのではなく、ある距離を隔てたデータを比較するようにします。比較するデータの間隔をギャップと呼びますが、コム・ソートではギャップ系列を［Ｎ／１．３］，［［Ｎ／１．３］／１．３］，・・・，１　（［　］はガウス記号、Ｎはデータ数）として前回のギャップを１．３で割って次第に狭めていきます。ここで、１．３はベンチマーク・テストの結果から得られた最適条件を備えた収縮率になっています。このようにすると比較する回数が減少し、データは大きくジャンプするのでソートをスピード・アップさせることができます。

　つまり、この方法ではまずおおざっぱにデータの並べ替えを行ない、ギャップが１となり、かつ、走査中にデータの位置変更が起こらなくなるまで比較・交換を繰り返していきます。この方法は、まず歯の粗い櫛で、次に細かい歯の櫛で髪をとかしていくのに似ていることから、comb sort と名付けられました。

　コム・ソートの基本型となるバブル・ソートはある程度データが並んでいるときに有効ですので、コム・ソートではその特長を活かしながらソート効率の改良を行なっています。　ギャップが９または１０ならそれを１１に変更すると、さらにソートが高速化されます。

　途方もなく遅いという欠点のため誰からも注目されることのなかったバブル・ソートの改良型がコム・ソートですが、現在ではその高速性とコーディングの容易さを兼ね備えた卓越したデータ整列法としての地位を築くまでに至っています。　コム・ソートにおけるLacey とBox の着眼と隘路打開の話はいろいろな示唆（教訓・寓意）に富んでいます。　

　『ソートできるデータ数に実際上制約があり扱いにくいというバブル・ソートの性質は最初は重大な弱点であった。しかし、高速化の方法が確立してしまうとその弱点は大きな長所に転化するのである。』　確かに驚異的なアルゴリズムですが、だからといって「こんな画期的なアルゴリズムを考える人がいるんだよなあ・・・」と感心してばかりではいられません。コム・ソート自体は古典的なバブル・ソートに少し手を加えただけですが、ソートを遅くする原因（ノロノロ這い回るカメ）を追及し分析できたからこそ速くする改良（ピョンピョン跳ね回るウサギ）が可能となったのです。

参考文献：Ｌａｃｅｙ，Ｂｏｘ「バブル・ソートが簡単な手直しで劇的に速く

なる」，日経バイト，９１年１１月号，３０５〜３１２ページ

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝