ALDS1_6_A Counting sortを解く話

計数ソート（Counting sort）を実装する．

特徴

• 配列の要素をキーとするソートアルゴリズム
• キーを要素とする別の配列を用意して出現頻度と累積和を計算
• 累積和から任意のキー以下の要素数がわかり，正しい位置に要素を代入

アルゴリズム

A: ソートする配列，B:ソート済みの配列，n: Aの要素数，k: キー(Aの要素）の最大値

1. Countingsort(A, B, n, k)
2.     C[K]
3. 　// 初期化
4.     for i = 0 to k
5.         C[i] = 0
6.     // Aの要素の出現頻度を計算
7.     for i = 0 to n
8.         C[A[i]]++
9. 　// 累積和を計算
10.     for i = 1 to k
11.         C[i] = C[i] + C[i - 1]
12.     // 累積和をもとにAの要素をBの正しい位置に代入
13.     for i = n - 1 downto 0
14.         B[C[A[i]]] = A[i]
15.         C[A[i]]--

計算量

サイズ 配列の走査とサイズ 配列の走査をするので計算量は．

実装

gist26c42254b7044f831a5cac19840a2d07

感想

累積和をなぜ計算しているか理解するのに時間がかかった．自分の値以下の要素がいくつあるのかを知るのがポイント．それが分かると自分の位置がわかるのでソートできる．

色々調べてると計数ソートは基数ソートとかなり関係あるみたい．

www.opendatastructures.org

ただAOJには基数ソートないんだよなぁ．