Les algorithmes de tri

1Le probleme du tri et les tris quadratiques

Le tri est le probleme algorithmique le mieux etudie. Il sert d'introduction a toutes les notions du cours : correction, terminaison, complexite, bornes inferieures, strategies algorithmiques (incremental, diviser pour regner). Il faut savoir ecrire, prouver et analyser les quatre tris du programme.

Tri par selection

def tri_selection(t):
    """Trie t en place par selection. Theta(n^2) comparaisons, Theta(n) echanges."""
    n = len(t)
    for i in range(n - 1):
        imin = i
        for j in range(i + 1, n):
            if t[j] < t[imin]:
                imin = j
        if imin != i:
            t[i], t[imin] = t[imin], t[i]

Invariant : au debut de l'iteration \(i\), t[0..i-1] contient les \(i\) plus petits elements de la liste initiale, tries.

Complexite : la boucle interne effectue \(n-1-i\) comparaisons, d'ou \[\sum_{i=0}^{n-2}(n-1-i) = \frac{n(n-1)}{2} = \Theta(n^2)\] comparaisons, quelle que soit l'entree : le tri par selection ne profite jamais d'une liste deja triee. En revanche il ne fait que \(n-1\) echanges au plus, ce qui le rend interessant quand les echanges sont tres couteux.

Stabilite : non, a cause de l'echange a distance. Sur [(2,'a'), (2,'b'), (1,'c')], le premier echange place (1,'c') devant et inverse les deux 2.

Tri par insertion

def tri_insertion(t):
    """Trie t en place par insertion. Theta(n) au meilleur cas, Theta(n^2) au pire."""
    for i in range(1, len(t)):
        x = t[i]                       # element a inserer
        j = i - 1
        while j >= 0 and t[j] > x:     # decalage vers la droite
            t[j + 1] = t[j]
            j -= 1
        t[j + 1] = x

Invariant : au debut de l'iteration \(i\), t[0..i-1] est triee et contient exactement les \(i\) premiers elements initiaux.

Tri a bulles

def tri_bulles(t):
    """Trie t en place par propagation. Theta(n^2), Theta(n) si deja triee."""
    n = len(t)
    for i in range(n - 1, 0, -1):
        echange = False
        for j in range(i):
            if t[j] > t[j + 1]:
                t[j], t[j + 1] = t[j + 1], t[j]
                echange = True
        if not echange:            # aucun echange : la liste est triee
            return

Le drapeau echange rend le tri adaptatif : \(\Theta(n)\) sur une liste triee. Sans lui, la complexite serait toujours \(\Theta(n^2)\). Le tri a bulles est stable (on n'echange que des voisins strictement mal ordonnes) mais reste le moins efficace des trois : il effectue autant d'echanges que d'inversions, soit jusqu'a \(n^2/2\).

2Tri fusion, diviser pour regner et borne inferieure

Tri fusion : diviser pour regner

def fusion(g, d):
    """Fusionne deux listes triees en une liste triee. Theta(len(g) + len(d))."""
    res = []
    i = j = 0
    while i < len(g) and j < len(d):
        if g[i] <= d[j]:          # <= et non < : c'est ce qui assure la STABILITE
            res.append(g[i]); i += 1
        else:
            res.append(d[j]); j += 1
    res.extend(g[i:])
    res.extend(d[j:])
    return res

def tri_fusion(t):
    """Renvoie une NOUVELLE liste triee. Theta(n log n) dans tous les cas."""
    if len(t) <= 1:
        return t[:]                # cas de base
    m = len(t) // 2
    return fusion(tri_fusion(t[:m]), tri_fusion(t[m:]))

Tri rapide (hors programme strict, mais classique)

def tri_rapide(t):
    """Tri rapide, version simple (non en place). Theta(n log n) en moyenne."""
    if len(t) <= 1:
        return t[:]
    pivot = t[len(t) // 2]
    petits  = [x for x in t if x < pivot]
    egaux   = [x for x in t if x == pivot]
    grands  = [x for x in t if x > pivot]
    return tri_rapide(petits) + egaux + tri_rapide(grands)

En moyenne \(\Theta(n\log n)\) avec une tres petite constante, mais \(\Theta(n^2)\) dans le pire cas (pivot systematiquement extremal, par exemple sur une liste deja triee si l'on prend toujours le premier element). Le choix aleatoire du pivot rend ce pire cas improbable.

Tableau comparatif

* dans sa version avec partition en place.

3Visualisation pas a pas et comparaison