Namaran

Code daily. Without assist.

2026-10-21

counting_sort_by.rs

fn counting_sort_by<T: Clone>(items: &[T], max_key: usize, key: impl Fn(&T) -> usize) -> Vec<T> {
}

items の要素を、key が返す整数の小さい順に並べた新しい Vec を返す counting_sort_by を書いてください。key はどの要素にも0以上 max_key 以下の値を返します。要素どうしは比べず、キーの値の範囲が小さいことを使って並べます。キーが同じ要素は、items での順序のまま並べます。items が空なら空の Vec を返します。

入力例 1

counting_sort_by(&[("ann", 3), ("bob", 1), ("cid", 3), ("dan", 0)], 3, |p| p.1)

出力例 1

[("dan", 0), ("bob", 1), ("ann", 3), ("cid", 3)]

入力例 2

counting_sort_by(&[5, 2, 5], 5, |&x| x)

出力例 2

[2, 5, 5]

入力例 3

counting_sort_by(&[] as &[u8], 9, |&x| x.into())

出力例 3

[]
Reference
fn counting_sort_by<T: Clone>(items: &[T], max_key: usize, key: impl Fn(&T) -> usize) -> Vec<T> {
    let mut buckets = vec![Vec::new(); max_key + 1];
    for item in items {
        buckets[key(item)].push(item.clone());
    }
    buckets.concat()
}

キーの値ごとに1つずつ、要素を入れる Vec を用意し、キーの値を添字にしてそこへ入れていきます。キーは max_key 以下なので、Vec は max_key + 1 個要ります。max_key 個にすると、最大のキーを持つ要素で添字が範囲を外れて panic します。最後に concat で添字の小さい順につなげば、キーの小さい順に並びます。要素どうしを一度も比べないので、手間は要素数とキーの範囲の和に比例します。

同じキーの要素は、items を先頭から読んだ順に同じ Vec の末尾へ足されるので、つないだあとも元の順序が残ります。入力例 1 の "ann" と "cid" がその例です。このように同じキーの要素の順序を変えない並べ替えを安定(stable)であるといいます。

T: Clone の境界は、借りた &[T] から新しい Vec<T> を作るために、要素を複製する必要があることから来ています。vec![Vec::new(); n] も Vec<T> を複製して並べるので同じ境界を使います。

掲載したのは参考実装で、唯一の正解ではありません。キーごとの個数を数えて累積和を取り、各要素を置く位置を決めてから1つの Vec に書き込む書き方もあります。そちらは要素ごとの小さな Vec を作らずに済みます。