【かうんとそーと】
カウントソート とは？
最終更新:
💡 値ごとの整理棚に、何個あるかを数えて並べる
各値の出現回数を利用して並べ替えるソートアルゴリズム。整数キーの範囲が限られる場合に適し、要素数n、数える値の範囲の大きさkに対してO(n+k)時間で整列する。
📌 このページのポイント
ひよこ カウントソートってどうやって並べ替えるの？
ペンギン先生 たとえば3・1・4・1・2・3なら、1は2個、2は1個、3は2個、4は1個と数えるよ。数字だけなら、この回数どおりに小さい値から出力して1・1・2・3・3・4にできるね。
ひよこ どれくらい時間がかかるの？
ペンギン先生 要素数をn、数える値の範囲の大きさをkとしてO(n+k)だよ。たとえば0〜100を数えるならkは101。最大値そのものとは区別するんだ。
ひよこ じゃあ、どんなデータでも速いの？
ペンギン先生 値の範囲が広いと、個数を置く配列の用意に時間とメモリがかかるよ。限られた範囲の整数キーに向いていて、いつでも最速というわけではないんだ。
ひよこ 名前の付いたデータも並べられる？
ペンギン先生 点数と名前の組なら点数をキーにできるよ。同点の人の元の順序を保つには、累積した個数で位置を決めて要素ごと移す安定な実装を使うんだ。この性質は基数ソートにも役立つよ。
もっと詳しく知りたい人へ
同じ値の元の順序を、どうやって保つの？
キー以外の情報を持つ要素では、個数だけから値を作り直すと元の情報を失います。代表的な安定実装は、個数の累積和で出力位置を求め、入力を後ろから走査して要素全体を出力配列へ置きます。同じキーの要素の相対順序を保つこの性質は、基数ソートでも役立ちます。
まとめ：ざっくりこれだけ覚えればOK！
「カウントソート」って出てきたら「値ごとの個数を使って並べるソート」と思えばだいたいOK！
📖 おまけ：英語の意味
「Counting Sort」 ＝ 計数ソート
💬 Counting（数える）で並べ替えるから、そのままの名前だよ