概要
概要
要素の取りうる値の範囲が狭いときに強いソートです。各値が何回出たかを数え、そこから整列済み列を組み立てます。
ソート / Counting Sort（計数ソート）
要素の取りうる値の範囲が狭いときに強いソートです。各値が何回出たかを数え、そこから整列済み列を組み立てます。
目次
このページでわかること
概要
要素の取りうる値の範囲が狭いときに強いソートです。各値が何回出たかを数え、そこから整列済み列を組み立てます。
考え方
count each value
compute prefix sums
place each item into output要点
O(n + k)
O(n + k)
O(n + k)
実装次第で Yes
補足
比較を繰り返さず、値ごとの個数から位置を求めるからです。
値の範囲 k が広すぎると不利です。
Radix Sort の内部でも使われます。
動きで確認
ここでは「配列を並べ替える前に数える」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。