Algorithmes de tri

Cinq tris classiques, du plus simple au plus efficace. Pour chacun : l'idée, un exemple court et le piège à éviter.

Vue d'ensemble

Un tri est stable s'il garde l'ordre relatif des éléments égaux. C'est important quand on trie des enregistrements sur plusieurs critères : trier par prénom, puis de façon stable par nom, donne une liste classée par nom puis par prénom.

Tri par insertion

La partie gauche du tableau est toujours triée. À chaque tour, on prend le premier élément de la partie non triée (la clé), on décale vers la droite les éléments triés plus grands que lui, et on insère la clé dans le trou.

Exemple : [5, 2, 8, 1]

• clé 2 : 5 se décale → [2, 5, 8, 1]
• clé 8 : 8 ≥ 5, rien à décaler
• clé 1 : 8, 5 et 2 se décalent → [1, 2, 5, 8]

Sur un tableau presque trié, il y a très peu de décalages : c'est pourquoi son meilleur cas est O(n). On s'arrête au premier élément ≤ à la clé, ce qui rend le tri stable.

Tri par sélection

Pour chaque position i, on cherche le minimum de la partie non triée A[i..n−1] et on l'échange avec A[i].

Exemple : [5, 2, 8, 1] → le minimum 1 va à l'indice 0 : [1, 2, 8, 5] → 2 est déjà en place → le minimum 5 va à l'indice 2 : [1, 2, 5, 8].

Il fait toujours O(n²) comparaisons, même si le tableau est déjà trié, mais au plus n − 1 échanges. L'échange à distance peut faire passer un élément devant un autre de même valeur : le tri n'est pas stable.

Tri par fusion

On coupe le tableau en deux moitiés, on trie chaque moitié récursivement, puis on fusionne les deux listes triées : on compare leurs têtes et on prend la plus petite, jusqu'à épuiser une liste, puis on copie le reste de l'autre.

Exemple de fusion : L = [2, 5, 8], R = [1, 3, 9]

• 2 vs 1 → 1 ; 2 vs 3 → 2 ; 5 vs 3 → 3 ; 5 vs 9 → 5 ; 8 vs 9 → 8
• L est vide : on copie 9 → [1, 2, 3, 5, 8, 9]

La récurrence T(n) = 2T(n/2) + O(n) donne O(n log n) dans tous les cas (cas 2 du théorème général). En cas d'égalité, on prend à gauche : c'est ce qui rend le tri stable. Son défaut est le tableau auxiliaire de taille n.

Tri rapide (partition de Lomuto)

On choisit un pivot (ici, le dernier élément), on place à sa gauche tout ce qui est ≤ pivot et à sa droite tout ce qui est plus grand, puis on trie récursivement les deux côtés.

partition(A, lo, hi):
    pivot = A[hi]
    i = lo - 1
    pour j de lo à hi - 1:
        si A[j] <= pivot:
            i = i + 1
            échanger A[i] et A[j]
    échanger A[i + 1] et A[hi]
    retourner i + 1

Exemple : [5, 2, 8, 1, 9, 3], pivot 3.

• j = 0 : 5 > 3, rien
• j = 1 : 2 ≤ 3 → i = 0, échange A[0] et A[1] → [2, 5, 8, 1, 9, 3]
• j = 2 : 8 > 3, rien
• j = 3 : 1 ≤ 3 → i = 1, échange A[1] et A[3] → [2, 1, 8, 5, 9, 3]
• j = 4 : 9 > 3, rien
• fin : échange A[2] et le pivot → [2, 1, 3, 5, 9, 8]. Le pivot 3 est à sa place finale.

D'autres schémas de partition existent (Hoare, par exemple) ; ils donnent des étapes différentes. Vérifie celui de ton cours.

Tri par heap

1. On transforme le tableau en max-heap en O(n) (voir heaps).
2. La racine est le maximum : on l'échange avec le dernier élément du heap. Il est maintenant à sa place finale.
3. Le heap rétrécit d'une case et on fait descendre la nouvelle racine. On recommence jusqu'à ce que le heap soit vide.

O(n log n) dans tous les cas et aucune mémoire supplémentaire. Les échanges à distance le rendent instable.

Lequel choisir ?

• Petit tableau ou presque trié : insertion.
• Besoin de stabilité et d'un pire cas garanti : fusion. TimSort, utilisé par Python et par Java pour les objets, combine fusion et insertion.
• Le plus rapide en moyenne : rapide, avec un bon choix de pivot.
• O(n log n) garanti sans mémoire supplémentaire : par heap.