Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

分布数え上げソートとは

ソートする配列の値範囲が既知の場合,分布数え上げソート (カウンティングソート)
が最速となる。
具体的な仕組みは以下参照
分布数え上げソート [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; //小さい順に格納
    ...
}
derodero24
主に画像認識/言語処理AIの研究・開発に従事 Python,JS,Julia,FLutter
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away