2026-09-22
range_sort.c
#include <stdio.h>
int main(void) {
int a[] = {7, 3, 5, 3, 7};
int n = 5;
int min = 3, max = 7;
int count[max - min];
for (int i = 0; i < max - min; i++) count[i] = 0;
for (int i = 0; i < n; i++) count[a[i] - min]++;
int pos = 0;
for (int v = min; v <= max; v++) {
for (int c = 0; c < count[v - min]; c++) a[pos++] = v;
}
for (int i = 0; i < n; i++) printf(i ? ",%d" : "%d", a[i]);
printf("\n");
}
minからmaxまでの範囲を利用した計数ソートでaを昇順に並べ替えるつもりのコードです。入力はa = {7, 3, 5, 3, 7}(min=3, max=7)。配列の境界を超えて書き込むため、いまの出力は保証されません(このコードは実際にクラッシュします)。本来の出力は3,3,5,7,7です。何が問題で、どう直せばよいでしょうか?
Answer
値はminからmaxまでmax - min + 1通りありますが、countはmax - min個分しか確保していません。a[i] - minが最大になるのはa[i] == maxのときで、添字はmax - minになりますが、これは確保した範囲(添字0〜max - min - 1)の1つ外です。この例ではmax - min = 4なので、値7(添字4)へのカウントも、後半のfor (int v = min; v <= max; v++)ループがv = max = 7まで読みに行くcount[4]も、どちらも配列の外を指します。off-by-oneで境界を1つ書き損なう典型例で、直し方は範囲の個数max - minをmax - min + 1に直すだけです:
int count[max - min + 1];
for (int i = 0; i < max - min + 1; i++) count[i] = 0;