Les algorithmes de tri, en images

Trier : le problème préféré des informaticiens

Trier des données (par prix, par date, par nom) est une opération omniprésente, et la rendre rapide est un problème étudié depuis les années 1950. Il existe des dizaines d’algorithmes ; ils illustrent à merveille le lien entre idée et efficacité.

Choisis un algorithme, mélange, puis lance l’animation. Le compteur affiche les comparaisons effectuées.

Tri à bulles : simple, mais lent

On parcourt la liste en comparant les voisins deux à deux ; s’ils sont dans le mauvais ordre, on les échange. Le plus grand élément « remonte » comme une bulle jusqu’au bout. On recommence jusqu’à ce qu’aucun échange ne soit nécessaire. Complexité : O(n²).

def tri_bulles(a):
    a = a[:]                      # on travaille sur une copie
    n = len(a)
    for fin in range(n - 1, 0, -1):
        echange = False
        for i in range(fin):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                echange = True
        if not echange:           # déjà trié : on s'arrête
            break
    return a

print(tri_bulles([5, 2, 9, 1, 7]))

Tri par insertion : comme trier ses cartes

Tu prends les cartes une à une et tu glisses chacune à sa bonne place parmi celles déjà triées. Très efficace sur de petites listes ou des listes presque triées (O(n) dans le meilleur cas, O(n²) dans le pire).

def tri_insertion(a):
    a = a[:]
    for i in range(1, len(a)):
        valeur = a[i]
        j = i - 1
        while j >= 0 and a[j] > valeur:
            a[j + 1] = a[j]      # on décale vers la droite
            j -= 1
        a[j + 1] = valeur
    return a

print(tri_insertion([5, 2, 9, 1, 7]))

Tri rapide : diviser pour régner

On choisit un pivot, puis on sépare les éléments en deux groupes : ceux plus petits, ceux plus grands. On trie chaque groupe de la même façon (récursivité), puis on assemble. En moyenne : O(n log n).

def tri_rapide(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    petits  = [x for x in a if x < pivot]
    egaux   = [x for x in a if x == pivot]
    grands  = [x for x in a if x > pivot]
    return tri_rapide(petits) + egaux + tri_rapide(grands)

print(tri_rapide([5, 2, 9, 1, 7, 2]))