[GO] Tri par bulles, tri par sélection, tri par insertion, tri par shell, tri par fusion, tri rapide, tri par comptage (Python)

Je vais résumer l'algorithme de tri en Python.

Tri à bulles

Montant moyen du calcul: $ O (n ^ 2) $ Pire calcul: $ O (n ^ 2) $

bubble.py

for i in range(N-1, 0, -1):
    for j in range(i):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783238

Tri par sélection

Montant moyen du calcul: $ O (n ^ 2) $ Pire calcul: $ O (n ^ 2) $

selection.py

for i in range(N):
    minj = i
    for j in range(i, N):
        if a[j] < a[minj]:
            minj = j

    a[i], a[minj] = a[minj], a[i]

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783283

Tri par insertion

Montant moyen du calcul: $ O (n ^ 2) $ Pire calcul: $ O (n ^ 2) $

insertion.py

for i in range(1, N):
    v = a[i]
    j = i - 1

    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j -= 1

    a[j+1] = v

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783260

Tri de coquille

[Article Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%AB%E3%82] en tant que colonne d'intervalle pour le tri des insertions utilisée en interne $ H = \ frac, comme dans% BD% E3% 83% BC% E3% 83% 88 #% E8% A8% 88% E7% AE% 97% E6% 99% 82% E9% 96% 93) L'entier qui satisfait {3 ^ i --1} {2} $ est adopté à partir du plus grand.

Montant moyen du calcul: si ce qui précède est adopté comme colonne d'intervalle, il devrait être $ O (n ^ {1,25}) $. Pire calcul: $ O (n ^ {1.5}) $ si ce qui précède est adopté comme colonne d'intervalle

shell.py

def insertion_sort(h):
    for i in range(h, N):
        v = a[i]
        j = i - h

        while j >= 0 and a[j] > v:
            a[j+h] = a[j]
            j -= h

        a[j+h] = v

hs = []
h = 1
while h < N+1:
    hs.append(h)
    h = 3 * h + 1

hs.reverse()

for h in hs:
    insertion_sort(h)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783355

Tri par fusion

Montant moyen du calcul: $ O (n \ log n) $ Pire calcul: $ O (n \ log n) $

merge.py

INF = 1e10  #Supérieur à la valeur maximale possible d'un élément de tableau

def merge(left, mid, right):
    l = a[left:mid]
    r = a[mid:right]

    l.append(INF)
    r.append(INF)

    i = 0
    j = 0

    for k in range(left, right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1

def merge_sort(left, right):
    if right - left >= 2:
        mid = (left + right) // 2
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)

merge_sort(0, N)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783399

Tri rapide

Montant moyen du calcul: $ O (n \ log n) $ Pire calcul: $ O (n ^ 2) $

quick.py

def partition(left, right):
    x = a[right]
    i = left-1

    for j in range(left, right):
        if a[j] <= x:
            i += 1
            a[i], a[j] = a[j], a[i]

    a[i+1], a[right] = a[right], a[i+1]
    return i+1

def quick_sort(left, right):
    if right - left >= 2:
        pivot = partition(left, right-1)
        quick_sort(left, pivot)
        quick_sort(pivot, right)

quick_sort(0, N)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783489

Tri de comptage

** C'est aussi un type de tri par seau, tri par casier **

Montant moyen du calcul: O $ (n + k) $ Pire calcul: $ O (n + k) $

counting.py

K = 100000 #Supérieur au nombre de types possibles d'éléments de tableau

b = [0 for i in range(len(a))]
c = [0 for i in range(K)]

for v in a:
    c[v] += 1

for i in range(K-1):
    c[i+1] += c[i]

for j in reversed(range(N)):
    b[c[a[j]]-1] = a[j]
    c[a[j]] -= 1

#b est un tableau trié

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783628