※「セキュリティ保護のため...」というメッセージが出る方・日本語が入力できない方へ
ソート手法概観

  ソートは一般に「分類」という訳語が当てられていますが、ひじょうに困
  った訳語です。これで意味の分かる人はあまりいません。もっと素直に
  「並べ替え」とでも訳した方がいいでしょう。

  ソートはソフトウェアにおける重要な基本技法のひとつで、今までに多数
  の手法が考案されてきました。

(1)王様探し

  例えば100件のデータを並べ替えるのに、最初に最も大きなデータを探し出
  して、それを取り出す。次に残ったものの中から最も大きなデータを探し
  出す。これを繰り返す。

　単純な方法で、基本プログラミングの学習者は最初にやらされるが、とっ
　ても遅い。実用性は全くない。これはこの方法では遅いということを学習
　することに意味があるのである。

(2)バブルソート

  王様探しのバリエーション。王様探しでは、１番目のデータと２番目のデ
  ータを比較したら、次には１番目と３番目、１番目と４番目、という比較
  の仕方をしていく。

　バブルの場合は、１番目と２番目、２番目と３番目、３番目と４番目、と
　いうふうに比較していく。すると大きなデータが泡となって浮かび上がる
　かのように後ろの方に集まっていく。そこで「バブル」の名前がある。

　これも遅いソートであり、実用性は全くない。しかし後述のコムソートの
　基礎になる。

(3)ヒープソート

　データを「ヒープ・トリー」という特殊な構造の中に格納し、その構造の
　特殊性を利用してソートしていく。たいへん高速なソートであり、しかも
　メモリーの消費も少ない優秀なソート。

　ヒープソートの最大のメリットは、並べ替える元のデータの品質に関係な
　く、高速にソートできることである。この後に述べる種々のソートはデー
　タの元々の並び方によっては極端に遅くなる不幸な場合もある。

　欠点は記述がやや複雑になることか。

(4)クイックソート

  昔からなぜか人気のあるソートである。データを「適当に」決めた基準値
  を元に大きい物と小さい物とに２分割し、その分割されたものを更に２分
  割する、ということを繰り返してソートする。

　コーディングが単純で実装しやすいが、比較的メモリーを消費する。また、
　データの元の並び方が悪いと（たとえば逆順に並んでいる場合）、最悪、
　王様探し並みに速度が落ちるケースもある。

(5)マージソート

  これは面白い考え方のソートである。ソート前の元データを観察すると、
  その中には、偶然、順序よく並んでいる箇所がいくつかある。

  マージソートでは、データの並びを「ソート済みのデータが幾つか集まっ
  たもの」と考える。そしてそれを全部マージして、ひとつのソート済みの
  データに変身させるのである。これもクイックソート並みに高速なソート。

  クイックソートが嫌いな人たちがよく使用していた。

(6)コムソート

　コムソート(Comb Sort)は、実は遅いことで有名なバブルソートの改良版で
　ある。ところが、この改良版が実はヒープソート並みに高速なのである。

　このソートは「髪を櫛でとく時に最初粗い櫛でといて、そのあと細かい櫛
　でとくように」データをまず大雑把に並べて、そのあと少しずつ、細かい
　部分まできれいに順序に並ぶようにしていく。

　実際のロジックについては専門的になるので省略するが、コーディングは
　バブルソートとほとんど変わらず簡単であり、メモリーも消費しないし、
　ヒープソートのような、大がかりな構造体も不要である。

　唯一の欠点は、このロジックを知らない人がこのコーディング（結構トリ
　ッキーである）を見たとき、なぜ、これでソートになるのか？というのが、
　まず理解できないことであろう。10年ほど前に発見された新しいソート。