Stuge Sort in Python 3 implementiert (Bubble Sort & Quick Sort)

[Es scheint eine Sorte namens Stouge-Sorte zu geben. ](Https://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%88%E3%82%A5%E3%83%BC%E3%82%B8%E3%82%BD % E3% 83% BC% E3% 83% 88) Dieser Sortieralgorithmus scheint ein sehr __ ineffizienter __ Sortieralgorithmus zu sein und ist weniger effizient als die Blasensortierung.

In diesem Artikel werde ich versuchen, Stuge Sort in Python3 zu implementieren.

#Sortieren Sie die Liste destruktiv. Der Algorithmus ist "stuge sort"
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]

Es scheint, dass Sie richtig sortieren können. Die Idee (?) Ist, dass es wiederholt und nicht rekursiv implementiert wird ... Ist es sinnvoll, es für ineffiziente Algorithmen effizient zu implementieren? (´ ・ ω ・ `)

Als nächstes kommt die Effizienz. [Ineffiziente "Blasensortierung"](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82 % BD% E3% 83% BC% E3% 83% 88) und [Effiziente "schnelle Sortierung"](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4 Ich möchte% E3% 83% 83% E3% 82% AF% E3% 82% BD% E3% 83% BC% E3% 83% 88) implementieren und die Zeit zum Sortieren einer Liste mit 1000 Elementen messen. Ich denke.

#Sortieren Sie die Liste destruktiv. Der Algorithmus ist "stuge sort"
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)))


#Sortieren Sie die Liste destruktiv. Der Algorithmus ist "Blasensortierung"
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]


#Sortieren Sie die Liste destruktiv. Der Algorithmus ist "schnelle Sortierung"
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

Langsam ((((´ ・ ω ・ `))))