Mise en œuvre du tri Stuge dans Python 3 (tri à bulles et tri rapide)

[Il semble y avoir une sorte appelée tri stouge. ](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) Cet algorithme de tri semble être un algorithme de tri __ très inefficace, et est moins efficace que le tri à bulles.

Dans cet article, j'essaierai d'implémenter Stuge Sort dans Python3.

#Triez la liste de manière destructive. L'algorithme est "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]

Il semble que vous puissiez trier correctement. L'idée (?) Est-ce qu'elle est implémentée de manière répétée plutôt que récursive ... Est-il significatif de l'implémenter efficacement pour des algorithmes inefficaces? (´ ・ ω ・ `)

Vient ensuite l'efficacité. [«Tri par bulles» inefficace](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82 % BD% E3% 83% BC% E3% 83% 88) et [Efficient "quick sort"](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4 Je voudrais implémenter% E3% 83% 83% E3% 82% AF% E3% 82% BD% E3% 83% BC% E3% 83% 88) et mesurer le temps pour trier une liste de 1000 éléments. Je pense.

#Triez la liste de manière destructive. L'algorithme est "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)))


#Triez la liste de manière destructive. L'algorithme est le "tri à bulles"
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]


#Triez la liste de manière destructive. L'algorithme est "tri rapide"
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

Lent ((((´ ・ ω ・ `))))