クイックソート

リハビリ第2弾(ref. スランプ脱出法, フィボナッチ数列)

from random import shuffle
data = range(100)
shuffle(data)

# recursion
def qsort(data):
    if not data: return data
    pivot = data[0]
    rest = data[1:]
    greater = [x for x in rest if x > pivot]
    lesser = [x for x in rest if x <= pivot]
    return qsort(lesser) + [pivot] + qsort(greater)

print qsort(data)

ループ版難しい。これじゃ1回しかpivotで振り分けてないしな…

# loop
def qsort_loop(data):
    """
    ... pivot a b c ... last done ... のとき
    if a < pivot:
        ... a pivot b c ...
    else:
        ... pivor b c ... last a done ...
        が素朴だけどどこれはコピーがたくさんあるので
        ... pivor last b c ... a done ...

    """
    if not data: return data
    pivot = data[0]
    cur = 1
    done = len(data)
    while cur != done:
        v = data[cur]
        if v < pivot:
            data[cur - 1] = v
            data[cur] = pivot
            cur += 1
        else:
            data[cur] = data[done - 1]
            data[done - 1] = v
            done -= 1
    
    return data

print qsort_loop(data)

---

できた。

# loop
def qsort_loop(data):
    """
    ... pivot a b c ... last done ... のとき
    if a < pivot:
        ... a pivot b c ...
    else:
        ... pivor b c ... last a done ...
        が素朴だけどどこれはコピーがたくさんあるので
        ... pivor last b c ... a done ...

    """
    stack = [(0, len(data))]
    while stack:
        start, end = stack.pop()
        print (start, end)
        if end - start <= 1: continue
        pivot = data[start]
        cur = start + 1
        done = end
        while cur != done:
            v = data[cur]
            #print data
            #print cur, done, pivot, v
            if v < pivot:
                data[cur - 1] = v
                data[cur] = pivot
                cur += 1
            else:
                data[cur] = data[done - 1]
                data[done - 1] = v
                done -= 1

            #print data
            #print
        stack.append((start, cur - 1))
        stack.append((cur, end))
    
    return data

print qsort_loop(data)

最初

-        stack.append((start, cur - 1))
-        stack.append((cur, end))
+        stack.append((start, cur))
+        stack.append((cur + 1, end))

ってなっていて大体ソートし終わった最後にぐちゃぐちゃになっていた。コメントアウトしてあるprint文を補ってrange(5)にして流れを追ってみた。

---

速度の比較

from time import clock

def profile(n):
    print n,
    original_data = range(n)
    shuffle(original_data)
    data = original_data[:]

    t = clock()
    qsort(data)
    print clock() - t,

    data = original_data[:]
    t = clock()
    qsort_loop(data)
    print clock() - t

for i in range(13):
    profile(100 * (2 ** i))

100 0.000448 0.000429
200 0.000967 0.001027
400 0.002129 0.002277
800 0.004327 0.005072
1600 0.00907 0.011751
3200 0.018466 0.022997
6400 0.039396 0.050003
12800 0.085261 0.112591
25600 0.171988 0.224489
51200 0.362911 0.484281
102400 0.767855 1.092627
204800 1.677372 2.279966
409600 3.564921 4.905796

あれあれ。意外と再起呼び出しが健闘するなぁ。再起版の方がメモリを無駄遣いするはずなのだけども、ループ版のポインタ演算のコストが高いせいで見えてこないのかな。