PHPでやってる人を見かけたので、Pythonでやってみた。
cf. 第4回 分布数え上げソート – noldor’s diary
分布数え上げソート(counting sort)ってのは、要素の最小値と最大値がわかっている場合に
- 各要素の出現回数を数える
- 小さい順に要素を出現回数分だけ出力する
っていうアルゴリズムだ。基本的に2回ループをまわすだけなので速い。
def counting_sort(lis, min, max):
counter = [0] * (max + 1)
for i in range(min, max+1):
for j in range(counter[i]):
l2 = counting_sort(l, 1, 9)
import random
def counting_sort(lis, min, max):
counter = [0] * (max + 1)
for i in lis:
counter[i] += 1
r = []
for i in range(min, max+1):
for j in range(counter[i]):
r.append(i)
return r
l = range(1,10) * 2
random.shuffle(l)
print "unsorted:", l
l2 = counting_sort(l, 1, 9)
print "sorted: ", l2
import random
def counting_sort(lis, min, max):
counter = [0] * (max + 1)
for i in lis:
counter[i] += 1
r = []
for i in range(min, max+1):
for j in range(counter[i]):
r.append(i)
return r
l = range(1,10) * 2
random.shuffle(l)
print "unsorted:", l
l2 = counting_sort(l, 1, 9)
print "sorted: ", l2
実行例:
^o^ > python counting_sort.py
unsorted: [1, 3, 7, 6, 9, 4, 7, 5, 2, 6, 9, 5, 1, 4, 8, 8, 3, 2]
sorted: [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]