カウントソートとは何ですか？

各値の出現回数を数えて並べ替えるソートアルゴリズム。比較を行わずにO(n+k)の時間で整列でき、値の範囲が限られた整数データのソートに適する。

カウントソートのポイントは？

各値の出現回数をカウントして並び順を決めるソートアルゴリズム。要素同士の比較を行わないため、比較ソートのO(n log n)の壁を破れる。時間計算量はO(n+k)で、kは値の最大値（範囲が狭いほど高速）。安定ソートであり、基数ソートの内部処理としても使われる

【かうんとそーと】

💡 比べずに数えるだけ、選挙の開票みたいなソート法

📌 このページのポイント

カウントソートのイメージ

ひよこ

カウントソートってどうやって並べ替えるの？

ペンギン先生

まず各値が何回出てくるか数えて、その回数表をもとに正しい位置に配置するんだ。選挙の開票で票数を数えて当選者を決めるのに似ているね。

ひよこ

比較しないってすごいね！なんで速いの？

ペンギン先生

通常のソートは2つの要素を比較するから最低でもO(n log n)かかるんだけど、カウントソートは数えるだけだからO(n+k)で済むんだよ。kは値の最大値ね。

ひよこ

じゃあいつでもカウントソートを使えばいいのかな？

ペンギン先生

値の範囲が狭い整数データなら最強だけど、値の範囲が広いとカウント用の配列が巨大になってメモリを食うんだ。小数や文字列には直接使えないのも弱点だよ。

ひよこ

どんなところで使われてるの？

ペンギン先生

テストの点数集計、年齢順の並べ替え、画像のヒストグラム計算とか、値の範囲が限られた場面で活躍するよ。あと基数ソートの中でカウントソートが内部的に使われていて、この組み合わせがめちゃくちゃ高速なんだ。

まとめ：ざっくりこれだけ覚えればOK！

「カウントソート」って出てきたら「値の出現回数を数えて並べる高速ソート」と思えればだいたいOK！

📖 おまけ：英語の意味

「Counting Sort」＝計数ソート

💬 Counting（数える）で並べ替えるから、そのままの名前だよ