Namaran

Code daily. Without assist.

2026-10-21

counting_sort.rs

fn counting_sort(a: &[usize]) -> Vec<usize> {
    let max = a.iter().copied().max().unwrap_or(0);
    let mut count = vec![0; max + 1];
    for &x in a {
        count[x] += 1;
    }
    (0..max).flat_map(|v| std::iter::repeat_n(v, count[v])).collect()
}

fn main() {
    println!("{:?}", counting_sort(&[4, 1, 2, 1, 4]));
}

counting_sort は、値ごとの個数を数えてから小さい値の順に個数分だけ並べ、昇順に並べ替えた Vec を返すつもりの関数です。[4, 1, 2, 1, 4] を渡すと、いまは [1, 1, 2] と出力されます。本来の出力は [1, 1, 2, 4, 4] です。

Answer

Wrong

    (0..max).flat_map(|v| std::iter::repeat_n(v, count[v])).collect()

count は0から max までの max + 1 個の値を数えられる長さで作られ、数える段階では4も2個と正しく数えています。誤っているのは取り出す側です。0..max は終わりの値を含まない範囲なので、v は0から3までしか動かず、count[4] は一度も読まれません。最大値の4が2個とも落ち、panic もせずに [1, 1, 2] が返ります。

Right

    (0..=max).flat_map(|v| std::iter::repeat_n(v, count[v])).collect()

0..=max は終わりの値を含む範囲なので、v は count の添字と同じ0から max までを動き、count[4] の2個も並びます。配列の長さを max + 1 にした時点で、取り出す範囲も max を含める必要があります。0..count.len() と書けば、長さと範囲が食い違うことはありません。