Namaran

Code daily. Without assist.

2026-09-22

count_sort.c

#include <stddef.h>

void count_sort(int *a, size_t n, size_t k) {
}

配列aの要素はすべて0以上k未満の整数です。比較ではなく、この範囲kを利用した計数ソートでaを昇順に並べ替えてください(呼び出し側はkが1以上であることを保証します)。要素数nが0のときは何もしません。a={3,1,2,3,0}, n=5, k=4 → a={0,1,2,3,3}、a={0}, n=1, k=1 → a={0}、a={}, n=0, k=4 → a={}(変化なし)

Reference
void count_sort(int *a, size_t n, size_t k) {
    int count[k];
    for (size_t v = 0; v < k; v++) count[v] = 0;
    for (size_t i = 0; i < n; i++) count[a[i]]++;

    size_t pos = 0;
    for (size_t v = 0; v < k; v++) {
        for (int c = 0; c < count[v]; c++) a[pos++] = (int)v;
    }
}

比較ソートなら最善でもO(n log n)ですが、値が[0, k)に収まっていると分かっているなら、値そのものを添字として使えるcountという長さkの配列(ここではサイズが実行時に決まる可変長配列)を用意するだけでO(n + k)で並べ替えられます。まずcount[v]に値vの出現回数を数え、次にvを昇順に見ながら、その出現回数ぶんだけvをaに書き戻します。要素の比較は1度も行いません。これは参考実装であり、唯一の正解ではありません(例えば累積和を使って安定ソートにする書き方もあります)。