【C言語】分布数え上げソートの簡単な実装方法

分布数え上げソートとは

ソートする配列の値範囲が既知の場合，分布数え上げソート (カウンティングソート)
が最速となる。
具体的な仕組みは以下参照
・分布数え上げソート [Counting Sort]
・C言語アルゴリズム-分布数え上げソート

単純な実装方法

・配列data[n]を昇順でソート
・配列data[]の値範囲は0~max
のとき

main.c

#define REP(i,n) for(int i=0;i<n;i++)

int main() {
    ...
    int tmp[max+1], arg = 0; //ソート用の配列と変数
    REP(i,max+1) tmp[i] = 0; //配列tmp[]を0で初期化
    REP(i,n) tmp[data[i]]++; //数え上げ
    REP(i,max+1) REP(j,tmp[i]) data[arg++] = i; //小さい順に格納
    ...
}

少し複雑に

・配列data[]のtop~end番目の要素だけを昇順でソート
・top~end番目の要素値の範囲はmin~max
のとき

main.c

#define FOR(i,a,b) for(int i=a;i<b;i++)

int main() {
    ...
    int arg = top, tmp[max-min+1]; //ソート用の配列と変数
    FOR(i,0,max-min+1) tmp[i] = 0; //配列tmp[]を0で初期化
    FOR(i,top,end+1) tmp[data[i] - min]++; //数え上げ
    FOR(i,0,max-min+1) FOR(j,0,tmp[i]) data[arg++] = i + min; //小さい順に格納
    ...
}