Data & Algorithm 今回のお題：
『ソート (3)- クィックソート、コムソート、数えソート』

●概要

最後となるソートの 3 回目は、「高速なソート」であるクィックソート、 一寸変わり種のコムソート、用途は限定されてるけど高速な数えソートです。

1. クィックソート

プログラムの中でも「不朽の名作」といわれるアルゴリズムの一つです。 一つのアルゴリズムのみを使う場合では、ほぼ最速と言われています。

このソート法も、基本は divide and conquer です。 さらに、再帰を使ったコードにするとよりエレガントに書けるため、 再帰呼び出しの練習用アルゴリズムとして用いられることがあります。手順は以下の通りです。

  1. しきい値 (基準となる値) を、データ中から選ぶ。
  2. 配列の片方にしきい値より大きい値を、反対側に小さい値を集める。 しきい値自身はどちらかのグループに入れても構わないが、 2 つのグループの真ん中に置いておけば、それがソート済みの位置になる。
  3. 「大きい側」「小さい側」の両方のグループに対して、1. 〜 3. を実行。 データ数が 1 になるまで実行し続ける。(データ数が 1 になったらそこはソート済み)

最後の「1. 〜 3.」の「3.」ってのが再帰呼び出しがある事を意味するんですが、解りますか？

31415926 -> 11234569
クィックソートの動作の様子

図にすると図 (a) のようになります。 下から 2 番目は、分割しているように見えませんが、 2 分割できているときと同じように操作するとこのようになります。

「２つのグループに分けている様子」が分かると、 もっと解りやすいんですが……。

しきい値の採り方としては以下のようなものがあります。

・データの真ん中の値を使う
特に意味は無いのですが、よく使われます。アルゴリズムの説明の時に 「2 分割する」という雰囲気を出すためだと思いますが……。
・データの先頭の値を使う
「しきい値を他の場所に保存しないやり方」でも、コードが分かりやすく書けます。 今回はこれを採用しました。
・データの一部分を持ってきて、その平均値を使う
クイックソートは、グループ分けの時に偏りが出ると効率が落ちます。この方法を使えば、その偏りが減り、 高速にソートできます。ただ、「平均値はグループ分けせずにそのまま」という方法が使えず、 平均値を求めるのにも多少時間が掛かるので、工夫しないと逆に遅くなる可能性もあります。

ちなみに、このクイックソートにも弱点があって、その中でも有名なのが「逆順に並んだデータ」でしょう。 クイックソートのオーダは平均で O(n*log2n) なんですが、この場合だと O(n2) 程度になってしまい、場合によってはバブルソートより遅くなることもあるそうです。

2. コムソート

バブルソートの変種ですが、親のバブルソートとはえらい違いで、クイックソートの半分くらいの速度が出るそうです。 「コム」とは "comb"、すなわち「櫛 (クシ)」のことです。 また、割と新しいアルゴリズムらしいです。詳しくは知りませんが。

バブルソートは隣接した (1 だけ離れた) 要素間で比較・交換を行うが、 コムソートは n だけ離れた要素間で比較・交換を行う。
n は 要素数より小さい任意の数から始まって、i = ∞ で ni = 1 となる。 実際には n1 = 要素数 - 1、ni+1 = ni / 1.3 あたりが良いらしい。
実装では n = ( n * 10 + 3 ) / 13 として、小数点演算を避けると共に、 +3 して n = 0 となるのを完全に防ぐ方法が用いられる。

ということが参照した文献に載ってましたので、これをそのまま実装しました。 バブルソートを少し弄るだけで良いので、実装は簡単です。

3. 数えソート

たぶん正式な名前があると思うんですが、私は数えソートと呼んでいます。これは、今まで出てきたソートとは違い、

という、いろんな意味でとんでもないソートです。

ソースも短いので、以下にそのまま載せてしまいます。出てきた回数をカウントして、 小さい方から回数分出力する、というのがアルゴリズムの仕組みです。 

/* 数えソート。こればっかりはプロトタイプも仕方ない  *
 * 0〜255 の値のみに有効。汎用性はもう少し上げられる */
#define TBLSIZE 256
void  countsort( int *value, size_t nel )
{
  size_t  cnttbl[TBLSIZE];
  int     i, j;

  /* 初期化 */
  memset( cnttbl, 0, TBLSIZE * sizeof( int ) );

  /* カウント */
  for( i = 0 ; i < nel ; i++ )
    if( 0 <= value[i] && value[i] < TBLSIZE )
      cnttbl[value[i]]++;

  /* 出力 */
  j = 0;
  for( i = 0 ; i < TBLSIZE ; i++  )
    for( ; cnttbl[i] > 0 ; cnttbl[i]-- )
    {
      value[j] = i;
      j++;
    }
}

●サンプル

Cで書いてみたサンプル (download)
クイックソートにちょっと気になる部分が有るんですが、「それっぽく直ってる」し 「十分なサンプルを用いたテストでも誤動作はなかった」ので、まぁこれで良しとします。御免。

●備考

残った３つは、また暫くしたら掲載ということにしておきます。とりあえず、

ヒープソート
「ふるい落とし」の動作がよく分かんない。
二分木ソート
全く目を通してない。
馬鹿ソート
数列の生成の仕方をどうしようか模索中。

これらの問題が解決されれば組める……と、思います。

戻る