Namaran

Code daily. Without assist.

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;