Algorithms/Sorting/Counting Sort

Counting Sort

計数ソート

Counting Sort

Outline

計数ソートとは、ソート対象列のすべての要素が自然数で，かつ，ある整数kより小さいと仮定して
行うソーティングアルゴリズムである.
i={0, 1, ... ,k}である各iについて
ソート対象列中のi以下の要素の数をカウントし、その情報をもとにソートする.
ただし、計数ソートは要素間の比較によるソートは行わず、
ある要素が結果としてどの位置に置かれればよいかということに基づきソートする.

具体的な例を見てみよう.
以下のようなn=8の配列Aを考える.
ここで、k=5である.

計数ソートでは一時的な記憶領域としてサイズkの配列と、
ソートの結果を格納するサイズnの配列が必要になる.
ここではそれぞれを配列B、配列Cとして、
配列Aの中で値がi以下の要素の数をそれぞれ
B[i]に格納していく.

まず、配列Bの全要素を0で初期化する.

次にj={0, 1, ... ,n}の各A[j]について、その値の個数を数える.
プログラム的には、A[j]を添え字とする配列Bの要素をインクリメントすればよい.
この作業の経過を順に見ていくことにする.

j=0
B 0 0 0 0 1

j=1
B 0 1 0 0 1

j=2
B 0 1 1 0 1

j=3
B 0 1 2 0 1

以下同様に続けていくと、配列Bは以下のようになる.

この段階で配列Bには各iに対するiの要素数(i以下の要素数ではない)が対応する添え字に格納されていることになる.
これをi以下の要素数を格納するようにするには、
各iについて&mimetex(0 \le m \le i);となるようなすべてのB[m]の要素の和を
B[i]の要素とすることになる.
プログラム的にはm={1, 2, ... ,k}として、
m=1から順にB[m]=B[m-1]+B[m]という計算を行っていく.
この作業を終えた配列Bは以下のようになる.

ここで、配列Aをソートした後の状態として配列A'を考えてみる.

配列A'と配列Bをよくみると、iがA'に現れる最後の位置の添え字が
ちょうどB[i]-1となっていることが分かる.
例えばi=2であれば、それがA'に最後に現れる添え字は5であり、
対応するB[2]の値は6となるので、6-1=5となる.
これは、上記のアルゴリズムをよく考えれば理解できるはずだ.

あとはB[i]の各要素に従って、配列Cに値を格納していく.
ここで重要なのは配列Aの要素を後ろから走査しながら、
現れた要素を添え字としたBの値を求め、さらにそのBの値を添え字としたCの要素に、
対応するAの値を代入するということだ.
単なる整数のソートなら先頭から走査しても可能であるが、
上記のような手順を踏むことでstable(安定)なソートを実現できる.
ソートが安定だというのは、重複する要素の順序関係が保たれたまま
ソートできるということである.
場合によっては安定なソートでないと正しい結果が得られないこともあり、
計数ソートの場合はそのように実装しても手間はかからないので、
常に安定なソートとして実装するようにするべきである.

Program

サイズnの配列aに対して計数ソートを行う関数.

void counting_sort(int a[], int n, int k) {
  int b[MAX];   // 要素カウント用配列
  int c[MAX];   // ソート済みデータ格納配列

  fill(b, b + k, 0);   // initialize

  for(int i = 0 ; i < n ; i++) {
    b[a[i]]++;
  }

  for(int i = 1 ; i < k ; i++) {
    b[i] += b[i - 1];
  }

  for(int i = n - 1 ; i >= 0 ; i--) {
    c[b[a[i]] - 1] = a[i];
    b[a[i]--];
  }

  copy(c, c + n, a);
}

Consideration

プログラムを見れば分かるように、計数ソートは&mimetex(O(n));で実行できる線形時間のソーティングアルゴリズムである.
何故このような実行時間が実現できるかは、以下の二つの理由に起因する.

順序の決定手段として比較を用いていない
仮定を含む

最初の理由については、比較を用いたソートの下界として
&mimetex( \Omega(n \log_{2} n) );というものが分かっている.
つまり、比較を用いたどんなソーティングアルゴリズムも
&mimetex( n \log_{2} n );という限界よりも早く実行できることはない.
従って、別の手法を用いない限り&mimetex(O(n));という実行時間は達成できないのである.

2番目の理由については、この計数ソートではソート対象列のどんな要素もある整数k以下であると仮定した.
そしてそのことがアルゴリズムの出発点になっているのだが、
例えばkがまったく予想できなければ計数ソートは実現できないし、
また以下の場合にも実現は困難である.

ソート対象列が整数以外の値で構成されている.

例えばそれが文字列であった場合、文字列を配列の添え字として用いることはできないから各文字列を整数に対応付けしないといけない.
もし実現するつもりなら手作業でインデックスと文字列との対応付けを行わなければならないが、文字列の順序関係を考えながらインデックスを割り当てるのは困難である.
その手間を考えればクイックソートで実現した方がコーディングと結果が出るまでの時間を合わせても早い(ICPCでは時間が命).

また、それが実数であれば&mimetex(10^8);程度の数との積をとって
その最大をkとすれば実行できるかもしれない.
しかしその場合は下の条件に引っかかる.

kが&mimetex(10^8);以上である.

一般的なPC、またICPCでジャッジコンピュータとして使用される計算機では
普通の整数型を&mimetex(10^8);個も確保することは難しい.

また、計数ソートがその場で(in place)ソートしていないことにも注目すべきである.
つまりソート対象列以外に余分な記憶領域が必要になる.

Algorithms/Sorting/Counting Sort

Counting Sort

Outline

Program

Consideration

Menu