日: 2013年2月11日

分布数え上げソートをやったついでに、クイックソート（quick sort）もやってみた。

import random

def quick_sort(lis):
    if len(lis) == 0:
        return []
    p = lis.pop(0)
    left = [x for x in lis if cmp(x, p) < 0]
    right = [x for x in lis if cmp(x, p) >= 0]
    return quick_sort(left) + [p] + quick_sort(right)


l = range(1,10) * 2
random.shuffle(l)
print "unsorted:", l

l2 = quick_sort(l)
print "sorted: ", l2

実行例：

^o^ > python quick_sort.py
unsorted: [2, 7, 9, 1, 8, 6, 3, 5, 1, 5, 2, 4, 8, 7, 3, 9, 4, 6]
sorted:   [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]

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]