PythonでCounting Sortした
たまには真面目に記事を書きます．
今大学でやっているアルゴリズムの授業で書いたものです．
実行速度で差をつけろ！というときは，CやC++などで書くのがメジャーで，Pythonはスクリプト言語で，逐次実行というところからすると，やはり遅くなってしまいます．
僕も大体の部分ではCを使って書いていたのですが，今回始めてPythonでじっくり書きました．
この大学のアルゴリズムの講義では会津大学のAOJというサイトを使用し，そこに用意されている問題をACさせることが，授業の課題という感じです．
今回の問題はこちら．
問題を要約すると，入力された数字を計数ソートにより昇順に並べ換えるという問題です．
これをするためには Counting sort という手法で数字を並べ換える必要があります．
やり方としては以下の通り
- キー(配列Aのデータ)を数え上げるための配列Cとソートのための作業用配列Bを用意する
- 配列Cを利用して，配列Aのデータの出現頻度を数える
- 配列Cが保持したキーの累積度数分布を求める
- (配列Cの)累積度数分布に従って配列Aから配列Bにデータをコピーする
- 必要な場合，配列Bから元の配列Aにデータをコピーする
累積度数分布って何ですか？
累積度数分布とは，その値がいくつあるか？という分布です． 例として，以下のような数列が与えられたとき．
1 5 2 3 1 1 3 3
この場合，要素数は8，分布が均等であれば，1~8がそれぞれ１つずつ存在することになります．
実際は重複がいくつかあり，この場合の累積度数分布は
こうなる，あとはこのリストを分布に沿ってコピーすればいいという感じです．
実際のコードはこんな感じ，sort内のmはカウントをする配列の数になる．count = [0]*(m)の表記は，これだけで要素を0で初期化が出来ます．
ここまで言って何なんですが，このコードの中では累積度数分布を使用していません．
count[a] += 1 の部分で出現回数の計算をし，
for c in range(count[a]):
array[i] = a
i += 1
で値の出現回数だけ繰り返して元のリストに値をコピーしています．
サンプルにするとこんな感じ，print部分でごちゃごちゃしているのは出力に制限があり，それに当てはめた結果がこのようになりました．
ただただ出力したい場合は print(li)で出力が可能です．
def counting_sort(array, maxval):
m = maxval+100
count = [0] * (m)
for a in array:
count[a] += 1
i = 0
for a in range(m):
for c in range(count[a]):
array[i] = a
i += 1
return array
if __name__ == '__main__':
N = int(input())
l = list(map(int, input().split()))
a = 0
li = counting_sort(l, N)
for a in range(N-1):
print(li[a], end=" ")
print(li[N-1])
実行例
入力1
6 1 1 4 5 1 4
出力1
1 1 1 4 4 5
入力2
10 2 2 2 1 1 5 5 9 1 1
出力2
1 1 1 1 2 2 2 5 5 9
入力3
100 0 33 43 62 29 0 8 52 56 56 19 11 51 43 5 8 93 30 66 69 32 17 47 72 68 80 23 49 92 64 69 51 27 90 24 35 20 44 10 62 84 63 1 10 36 76 31 29 97 75 91 90 44 34 25 29 30 27 26 43 34 4 60 49 20 56 32 72 13 90 9 19 5 95 49 27 19 97 24 96 49 56 84 93 45 7 6 9 54 52 65 83 38 1 90 30 37 95 56 63
出力3
0 0 1 1 4 5 5 6 7 8 8 9 9 10 10 11 13 17 19 19 19 20 20 23 24 24 25 26 27 27 27 29 29 29 30 30 30 31 32 32 33 34 34 35 36 37 38 43 43 43 44 44 45 47 49 49 49 49 51 51 52 52 54 56 56 56 56 56 60 62 62 63 63 64 65 66 68 69 69 72 72 75 76 80 83 84 84 90 90 90 90 91 92 93 93 95 95 96 97 97
このように間違いはなく，実際にソートがされているということが分かる．
