分布数え上げソート

PHPでやってる人を見かけたので、Pythonでやってみた。

cf. 第４回 分布数え上げソート – noldor’s diary

分布数え上げソート（counting sort）ってのは、要素の最小値と最大値がわかっている場合に

1. 各要素の出現回数を数える
2. 小さい順に要素を出現回数分だけ出力する

っていうアルゴリズムだ。基本的に2回ループをまわすだけなので速い。

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]