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() と書けば、長さと範囲が食い違うことはありません。