ストゥージソートをPython3で実装(バブルソート&クイックソート)

ストゥージソート(stooge sort)というソートがあるそうです。このソートアルゴリズムはとても__効率の悪い__ソートアルゴリズムらしく、バブルソートより効率が悪いとか。

この記事ではストゥージソートをPython3で実装してみます。

# リストを破壊的にソートする。アルゴリズムは「ストゥージソート」
def stooge_sort(ls):
    stack = [(0, len(ls) - 1)]
    
    while stack:
        i, j = stack.pop()
        if ls[i] > ls[j]: ls[i], ls[j] = ls[j], ls[i]
        
        if j - i + 1 >= 3:
            t = (j - i + 1) // 3
            stack.extend(((i, j - t), (i + t, j), (i, j - t)))

if __name__ == '__main__':
    import random

    ls = list(range(30))
    random.shuffle(ls)

    print(ls)
    stooge_sort(ls)
    print(ls)

# [20, 4, 13, 28, 12, 0, 17, 19, 22, 21, 5, 23, 3, 27, 14, 2, 29, 11, 24, 7, 15, 9, 25, 6, 26, 18, 8, 1, 10, 16]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

確かにちゃんとソートできているようですね。 工夫(?)としては再帰ではなく、繰り返しで実装している点ですが……効率のわるいアルゴリズムに対して、効率よく実装する意味はあるのか(´・ω・`)

次に効率ですが、効率の悪い「バブルソート」と効率のいい「クイックソート」をそれぞれ実装し、1000個の要素を持つリストをソートする時間を計測してみたいと思います。

# リストを破壊的にソートする。アルゴリズムは「ストゥージソート」
def stooge_sort(ls):
    stack = [(0, len(ls) - 1)]
    
    while stack:
        i, j = stack.pop()
        if ls[i] > ls[j]: ls[i], ls[j] = ls[j], ls[i]
        
        if j - i + 1 >= 3:
            t = (j - i + 1) // 3
            stack.extend(((i, j - t), (i + t, j), (i, j - t)))


# リストを破壊的にソートする。アルゴリズムは「バブルソート」
def bubble_sort(ls):
    t = len(ls)

    for i in range(t - 1):
        for j in range(i + 1, t):
            if ls[i] > ls[j]: ls[i], ls[j] = ls[j], ls[i]


# リストを破壊的にソートする。アルゴリズムは「クイックソート」
def quick_sort(ls):
    stack = [(0, len(ls) - 1)]

    while stack:
        left, right = stack.pop()
        if left >= right: continue

        pivot = ls[left + (right - left) // 2]
        i, j = left, right
        while True:
            while ls[i] < pivot: i += 1
            while ls[j] > pivot: j -= 1

            if i >= j: break
            
            ls[i], ls[j] = ls[j], ls[i]
            i, j = i + 1, j - 1

        stack.extend(((j + 1, right), (left, i - 1)))

if __name__ == '__main__':
    import random, copy, time

    ls = list(range(1000))
    random.shuffle(ls)
    
    bubble_ls = copy.deepcopy(ls)
    bubble_start = time.time()
    bubble_sort(bubble_ls)
    bubble_time = time.time() - bubble_start

    quick_ls = copy.deepcopy(ls)
    quick_start = time.time()
    quick_sort(quick_ls)
    quick_time = time.time() - quick_start

    stooge_ls = copy.deepcopy(ls)
    stooge_start = time.time()
    stooge_sort(stooge_ls)
    stooge_time = time.time() - stooge_start

    print("bubble : {}".format(bubble_time))
    print("quick  : {}".format(quick_time))
    print("stooge : {}".format(stooge_time))

    # bubble : 0.0938718318939209
    # quick  : 0.0
    # stooge : 33.47836709022522

遅い ((((´・ω・`))))