Algorithmes de tri

Algorithmes de tri

I. Tri par sélection

def tri_selection(L):
    for i in range(len(L)):
        m = i
        for j in range(i+1, len(L)):
            if L[j] < L[m]: m = j
        L[i], L[m] = L[m], L[i]

Complexité : $O(n^2)$ (toujours).

II. Tri par insertion

def tri_insertion(L):
    for i in range(1, len(L)):
        x = L[i]
        j = i
        while j > 0 and L[j-1] > x:
            L[j] = L[j-1]
            j -= 1
        L[j] = x

Complexité : $O(n^2)$ pire cas, $O(n)$ si déjà trié.

III. Tri fusion

Approche diviser pour régner :

def fusion(L):
    if len(L) <= 1: return L
    m = len(L)//2
    G = fusion(L[:m]); D = fusion(L[m:])
    res = []; i = j = 0
    while i < len(G) and j < len(D):
        if G[i] <= D[j]:
            res.append(G[i]); i += 1
        else:
            res.append(D[j]); j += 1
    return res + G[i:] + D[j:]

Complexité : $O(n \log n)$ garantie.

IV. Tri rapide (Quicksort)

def quicksort(L):
    if len(L) <= 1: return L
    pivot = L[0]
    petits = [x for x in L[1:] if x < pivot]
    grands = [x for x in L[1:] if x >= pivot]
    return quicksort(petits) + [pivot] + quicksort(grands)

Moyenne $O(n \log n)$, pire $O(n^2)$.

V. Comparaison

Tri	Pire	Moyen	Stable	Sur place
Sélection	$n^2$	$n^2$	non	oui
Insertion	$n^2$	$n^2$	oui	oui
Fusion	$n\log n$	$n\log n$	oui	non
Rapide	$n^2$	$n\log n$	non	oui
Tas	$n\log n$	$n\log n$	non	oui