ALDS1_6_A Counting sortを解く話
計数ソート(Counting sort)を実装する.
特徴
アルゴリズム
A: ソートする配列,B:ソート済みの配列,n: Aの要素数,k: キー(Aの要素)の最大値
- Countingsort(A, B, n, k)
- C[K]
- // 初期化
- for i = 0 to k
- C[i] = 0
- // Aの要素の出現頻度を計算
- for i = 0 to n
- C[A[i]]++
- // 累積和を計算
- for i = 1 to k
- C[i] = C[i] + C[i - 1]
- // 累積和をもとにAの要素をBの正しい位置に代入
- for i = n - 1 downto 0
- B[C[A[i]]] = A[i]
- C[A[i]]--
計算量
サイズ 配列の走査とサイズ 配列の走査をするので計算量は.
実装
gist26c42254b7044f831a5cac19840a2d07
感想
累積和をなぜ計算しているか理解するのに時間がかかった.自分の値以下の要素がいくつあるのかを知るのがポイント.それが分かると自分の位置がわかるのでソートできる.
色々調べてると計数ソートは基数ソートとかなり関係あるみたい.
ただAOJには基数ソートないんだよなぁ.