計数ソート

説明

計数ソートは，有限のアルファベット（サイズ K）からなる長さ n のリストを O(n + K) でソートする．

アルファベットサイズと同サイズの配列を用意し，リストを一回走査して各要素の出現回数を配列に記憶する．次に配列を走査して出現回数だけそのアルファベットを出力する．

もっとも簡単なバージョンならばこれでよいが，これはもとのデータを忘却する．もとのデータを保存したまま扱いたい場合（キーが有限のデータを計数ソートする場合など）は，若干巧妙なアルゴリズムが必要となる．

計算量

• O(n + K)．

ソースコード

// 0 <= a[i] < K
void countingSort(int a[], int n, int K) {
  int *b = new int[n], c[K+1];
  fill(c, c+K+1, 0);
  REP(i,n) ++c[a[i]+1];         // c[k+1] := number of occurence of k
  REP(k,K) c[k+1] += c[k];      // c[k]   := number of occurence of < k
  REP(i,n) b[c[a[i]]++] = a[i]; // copy a to b (not inplace)
  REP(i,n) a[i] = b[i];         // copy b to a
}

// Simple ver. 
void countingSort(int a[], int n, int K) {
  int c[K], j = 0;
  fill(c, c+K, 0);
  REP(i,n) ++c[a[i]];
  REP(k,K) REP(i,c[k]) a[j++] = k;
}

Verified