2026-09-22
stable_tags.c
#include <stdio.h>
int main(void) {
int value[] = {2, 1, 2, 0, 1};
char label[] = "ABCDE";
int n = 5;
int count[3] = {0};
for (int i = 0; i < n; i++) count[value[i]]++;
for (int i = 1; i < 3; i++) count[i] += count[i - 1];
char out[6] = {0};
for (int i = n - 1; i >= 0; i--) {
out[--count[value[i]]] = label[i];
}
printf("%s\n", out);
}
このプログラムを実行すると、何が出力されるでしょうか?
Answer
DBEAC(その後に改行)。valueは0〜2の範囲に収まっているので、比較ではなくvalue[i]自身をcountの添字として使う計数ソートです。まずcountに各値の出現回数を数え、次に累積和を取ることで「その値のブロックがoutのどこから始まるか」の1つ先の位置(終端の1つ後ろ)をcountに持たせます。配置はi = n - 1から0へ、つまり元の配列を後ろから辿りながら--count[value[i]]で1つ手前の位置に書き込みます。この「後ろから辿り、書き込む前に添字を1つ減らす」やり方が、同じ値どうしの元の順序を保つ(安定ソートになる)理由です。前から辿ると同じ値の中で順序が逆転してしまいます。value = [2,1,2,0,1]・label = "ABCDE"で実際に手を動かすと、countの累積和は[1,3,5]になり、i=4(値1・'E')からi=0(値2・'A')まで順にout[2]='E'・out[0]='D'・out[4]='C'・out[1]='B'・out[3]='A'と埋まっていき、結果はvalue昇順・同値内は元の順序(1については'B'が'E'より先、2については'A'が'C'より先)を保った"DBEAC"になります。