読者です 読者をやめる 読者になる 読者になる

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]]--

 

計算量

サイズ n 配列の走査とサイズk 配列の走査をするので計算量はO(n + k)

実装

gist26c42254b7044f831a5cac19840a2d07

 

感想

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

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

www.opendatastructures.org

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