Cadre général

On distingue deux grandes familles :

1. Tri par comparaisons : l’algorithme ne connaît les éléments qu’au travers d’un prédicat de comparaison < ou <=.
2. Tri non basé sur les comparaisons : exploite la structure des clés (entiers bornés, chaînes de longueur bornée, etc.) pour atteindre une complexité linéaire. En dehors de ce cours (counting sort, radix sort).

Cadre théorique simplifié. Dans la sutie de ce cours, nous considérerons le cadre théorique plus simple où toute opération élémentaire (comparaison, affectation, accès mémoire) est en $O(1)$, sans considération de la localité du cache, des latences mémoire ni de la hiérarchie de caches. Ce modèle permet de raisonner plus facilement sur la complexité algorithmique. Les aspects pratiques (cache, branches, etc.) seront mentionnés en remarques ponctuelles.

Tout algorithme de tri qui ne s’appuie que sur des comparaisons peut être modélisé par un arbre de décision binaire :

• Chaque nœud interne est une comparaison entre deux éléments.
• Chaque feuille correspond à une permutation possible des $n$ éléments.

Il existe exactement $n!$ permutations possibles de $n$ éléments distincts. Pour que l’algorithme fonctionne correctement dans tous les cas, son arbre de décision doit donc comporter au minimum $n!$ feuilles, chacune correspondant à une permutation possible. Or, un arbre binaire de hauteur $h$ possède au plus $2^h$ feuilles.

• On doit donc satisfaire : $2^h \ge n!$
• En prenant le logarithme en base 2, on obtient : $h \ge \log_2(n!)$
• En utilisant l’approximation de Stirling : $n! = \sqrt{2 \pi n}(\frac{n}{e})^ n$
• Cela donne : $\log_2(n!) \approx n \log_2 n - O(n)$

Ainsi, la hauteur minimale de l’arbre et donc la complexité dans le pire cas est en $O(n \log n)$. Cela implique que toute méthode de tri par comparaisons nécessite au moins $\Omega(n \log n)$ comparaisons dans le pire cas.

Remarque. Ce résultat justifie pourquoi les tris « classiques » (quicksort, mergesort, heapsort) tournent tous autour de $O(n \log n)$ : ils sont asymptotiquement optimaux dans ce modèle de calcul. Pour faire « mieux », il faut changer de modèle (exploiter la structure des clés).

Bubble sort

Le tri à bulles (bubble sort) est l’algorithme de tri le plus intuitif. Il consiste à parcourir le tableau de gauche à droite, en comparant chaque paire d’éléments consécutifs et en les échangeant s’ils sont dans le mauvais ordre. On répète ces passes jusqu’à ce qu’aucun échange ne soit nécessaire.

void bubble_sort(int *arr, int n) {
    for (int i = 0; i < n - 1; ++i) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break; // optimisation : arrêt si aucun échange
    }
}

Analyse de complexité :

• La boucle externe s’exécute au plus $n - 1$ fois.
• À la passe $i$, la boucle interne effectue $n - 1 - i$ comparaisons.
• Nombre total de comparaisons dans le pire cas : $\sum_{i=0}^{n-2}(n-1-i) = \frac{n(n-1)}{2} = O(n^2)$.
• Meilleur cas (tableau déjà trié) : une seule passe sans échange → $O(n)$.
• Pire cas (tableau trié à l’envers) : $O(n^2)$.
• Stable, en place ($O(1)$ mémoire supplémentaire).

Remarque. Le bubble sort est principalement utilisé à des fins pédagogiques. Il est strictement inférieur à l’insertion sort en pratique (plus de swaps, moins d’optimisations possibles). Son intérêt est de servir de premier exemple d’analyse de complexité quadratique.

Tri boustrophédon

Le tri boustrophédon (aussi appelé cocktail sort, shaker sort ou tri à bulles bidirectionnel) est une variante du bubble sort qui alterne les parcours de gauche à droite et de droite à gauche. Le terme « boustrophédon » vient d’un mode d’écriture antique où les lignes alternent de gauche à droite et de droite à gauche.

Le problème du bubble sort classique est que les petits éléments situés en fin de tableau (les « tortues ») migrent très lentement vers le début, tandis que les grands éléments (les « lièvres ») atteignent rapidement leur position finale. Le parcours bidirectionnel accélère les tortues.

void cocktail_shaker_sort(int *arr, int n) {
    int start = 0, end = n - 1;
    int swapped = 1;
    while (swapped) {
        swapped = 0;
        // Passe gauche → droite
        for (int i = start; i < end; ++i) {
            if (arr[i] > arr[i + 1]) {
                int tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                swapped = 1;
            }
        }
        --end;
        if (!swapped) break;
        swapped = 0;
        // Passe droite → gauche
        for (int i = end; i > start; --i) {
            if (arr[i] < arr[i - 1]) {
                int tmp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = tmp;
                swapped = 1;
            }
        }
        ++start;
    }
}

Analyse de complexité :

• Pire cas : $O(n^2)$, identique au bubble sort.
• Meilleur cas (déjà trié) : $O(n)$.
• Stable, en place.

Le gain pratique par rapport au bubble sort est marginal. L’algorithme reste $O(n^2)$ dans le pire cas et n’est pas utilisé en production. Son intérêt est de montrer qu’on peut optimiser un algorithme existant sans changer sa classe de complexité.

Insertion sort

Le tri par insertion construit progressivement un sous-tableau trié en insérant chaque élément à sa place correcte. C’est l’analogue de la manière dont on trie des cartes en main.

void insertion_sort(int *arr, int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

Analyse de complexité :

• À l’itération $i$, on insère arr[i] dans le sous-tableau trié arr[0..i-1].
• Au pire (tableau décroissant), chaque insertion parcourt tout le préfixe : $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = O(n^2)$.
• Meilleur cas (déjà trié) : chaque insertion se fait en $O(1)$ → temps total $O(n)$.
• Stable, en place.

Pourquoi l’insertion sort bat le bubble sort. L’insertion sort effectue des décalages (une seule affectation par élément déplacé) au lieu d’échanges (trois affectations par swap). Sur un tableau presque trié, il est très efficace car la boucle interne s’arrête dès que l’élément est en place.

Remarque pratique. Sur des petits tableaux ($n \lesssim 16$–32), l’insertion sort est souvent plus rapide que les tris sophistiqués, grâce à un nombre très faible de branches et à une excellente localité cache. C’est pourquoi les implémentations industrielles de quicksort basculent vers l’insertion sort sur des petits segments.

Shell sort

Le Shell sort (Donald Shell, 1959) est une généralisation de l’insertion sort. L’idée est de comparer et trier des éléments éloignés les uns des autres avant de réduire progressivement la distance (le gap), jusqu’à un tri par insertion final avec gap = 1.

Un tableau est dit $h$-trié si, pour tout $i$, les éléments aux positions $i, i+h, i+2h, \dots$ sont triés entre eux. Le Shell sort effectue des $h$-tris successifs pour une séquence décroissante de gaps se terminant par 1.

void shell_sort(int *arr, int n) {
    // Séquence de Knuth : h = (3^k - 1) / 2
    int h = 1;
    while (h < n / 3)
        h = 3 * h + 1; // 1, 4, 13, 40, 121, ...

    while (h >= 1) {
        // h-insertion sort
        for (int i = h; i < n; ++i) {
            int key = arr[i];
            int j = i;
            while (j >= h && arr[j - h] > key) {
                arr[j] = arr[j - h];
                j -= h;
            }
            arr[j] = key;
        }
        h /= 3;
    }
}

Analyse de complexité :

La complexité du Shell sort dépend fortement de la séquence de gaps choisie :

Avec la séquence originale de Shell ($n/2, n/4, \dots, 1$), le pire cas est $O(n^2)$ (par exemple quand $n$ est une puissance de 2 et que les grands/petits éléments alternent entre positions paires et impaires). La séquence de Knuth $(3^k - 1)/2$ donne un pire cas en $O(n^{3/2})$, ce qui est un gain significatif.

Propriétés :

• En place : $O(1)$ mémoire supplémentaire.
• Non stable : les tris avec gap > 1 peuvent transporter des éléments égaux au-delà l’un de l’autre.
• Bien que la complexité exacte du Shell sort reste un problème ouvert pour la plupart des séquences de gaps, il constitue un intermédiaire intéressant entre les tris $O(n^2)$ et les tris $O(n \log n)$.

Remarque. Le Shell sort est utilisé dans certaines implémentations embarquées (uClibc, bzip2) car il nécessite très peu de code, pas de pile d’appels récursifs, et offre de bonnes performances sur des tableaux de taille modérée.

Quicksort

Le quicksort repose sur un schéma de partitionnement (divide-and-conquer) :

1. Choisir un pivot $p$.
2. Réorganiser le tableau pour que tous les éléments $< p$ soient à gauche, et tous les éléments $\ge p$ soient à droite.
3. Appliquer récursivement le tri aux deux sous-tableaux.

int partition(int *arr, int low, int high) {
    int pivot = arr[high]; // choix simple : dernier élément
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    int tmp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = tmp;
    return i + 1;
}

void quicksort_rec(int *arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quicksort_rec(arr, low, pi - 1);
        quicksort_rec(arr, pi + 1, high);
    }
}

void quicksort(int *arr, int n) {
    quicksort_rec(arr, 0, n - 1);
}

Analyse de complexité :

Cas moyen. Si le pivot coupe le tableau « à peu près au milieu » à chaque appel, la relation de récurrence est :

$$ T(n) = 2\,T(n/2) + O(n) $$

Par le théorème maître (ou par déroulement de la récurrence), on obtient $T(n) = O(n \log n)$. Chaque niveau de récursion (profondeur $O(\log n)$) traite $O(n)$ éléments au total dans la phase de partitionnement.

Pire cas. Si le pivot est systématiquement le minimum ou le maximum, les partitions sont de taille $n-1$ et 1 :

$$ T(n) = T(n-1) + O(n) \implies T(n) = O(n^2) $$

Cela survient typiquement lorsqu’on choisit un pivot naïf (premier ou dernier élément) sur un tableau déjà trié ou presque trié.

Stratégies de pivot. Pour éviter le pire cas : pivot aléatoire (en espérance $O(n \log n)$), médiane de trois (premier, milieu, dernier). L’analyse probabiliste du quicksort aléatoire montre un nombre moyen de comparaisons de $2n \ln n \approx 1.39\, n \log_2 n$.

Propriétés :

• En place (pile récursive en $O(\log n)$ en moyenne).
• Non stable dans sa version classique.
• Malgré son pire cas $O(n^2)$, le quicksort est souvent le plus rapide en pratique grâce à ses accès séquentiels lors du partitionnement et à son faible overhead mémoire.

Heapsort

Le heapsort utilise la structure de tas binaire (max-heap), vue au cours précédent. Rappel : un max-heap est un arbre binaire complet stocké dans un tableau où chaque nœud est $\ge$ ses enfants.

L’algorithme :

1. Construire un max-heap à partir du tableau → build_heap en $O(n)$.
2. Répéter $n - 1$ fois :
   - Échanger la racine (max) avec le dernier élément du tas.
   - Réduire la taille logique du tas de 1.
   - Restaurer la propriété de tas via sift_down en $O(\log n)$.

void sift_down(int *arr, int n, int i) {
    while (1) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest])
            largest = left;
        if (right < n && arr[right] > arr[largest])
            largest = right;
        if (largest == i) break;
        int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
        i = largest;
    }
}

void build_heap(int *arr, int n) {
    for (int i = n / 2 - 1; i >= 0; --i)
        sift_down(arr, n, i);
}

void heapsort(int *arr, int n) {
    build_heap(arr, n);
    for (int i = n - 1; i > 0; --i) {
        int tmp = arr; arr = arr[i]; arr[i] = tmp;
        sift_down(arr, i, 0);
    }
}

Analyse de complexité :

Construction du tas en $O(n)$. Rappel du cours précédent : en appliquant sift_down du dernier nœud interne vers la racine, le coût total est :

$$ \sum_{k=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{k+1}} \right\rceil \cdot O(k) = O\!\left(n \sum_{k=0}^{\infty} \frac{k}{2^k}\right) = O(n \cdot 2) = O(n) $$

Boucle principale. On effectue $n - 1$ extractions du maximum, chacune suivie d’un sift_down en $O(\log n)$ donc coût total $O(n \log n)$.

Complexité totale : $O(n) + O(n \log n) = O(n \log n)$ dans tous les cas (pire, moyen, meilleur).

Propriétés :

• En place : $O(1)$ mémoire supplémentaire.
• Non stable.
• Complexité $O(n \log n)$ garantie, contrairement au quicksort.

Remarque pratique. Le heapsort a d’excellentes garanties théoriques, mais est souvent plus lent que le quicksort en pratique : les accès au tas suivent un motif « arbre binaire » qui produit plus de cache misses que le partitionnement séquentiel du quicksort.

Mergesort

Le tri fusion (mergesort) applique systématiquement une stratégie divide-and-conquer :

1. Diviser le tableau en deux moitiés.
2. Trier récursivement chaque moitié.
3. Fusionner les deux sous-tableaux triés en un seul.

void merge(int *arr, int left, int mid, int right, int *tmp) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else                  tmp[k++] = arr[j++];
    }
    while (i <= mid)  tmp[k++] = arr[i++];
    while (j <= right) tmp[k++] = arr[j++];
    for (int t = left; t <= right; ++t)
        arr[t] = tmp[t];
}

void mergesort_rec(int *arr, int left, int right, int *tmp) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergesort_rec(arr, left, mid, tmp);
    mergesort_rec(arr, mid + 1, right, tmp);
    merge(arr, left, mid, right, tmp);
}

void mergesort(int *arr, int n) {
    int *tmp = (int*)malloc(sizeof(int) * n);
    mergesort_rec(arr, 0, n - 1, tmp);
    free(tmp);
}

Analyse de complexité :

La relation de récurrence est :

$$ T(n) = 2\,T(n/2) + O(n) $$

• La division produit une profondeur de récursion de $\log_2 n$.
• À chaque niveau, la phase de fusion parcourt tous les éléments donc $O(n)$.
• Temps (tous cas) : $O(n \log n)$.
• Espace : $O(n)$ (tableau temporaire).

Propriétés :

• Stable (conserve l’ordre relatif des éléments égaux).
• Complexité garantie en $O(n \log n)$ même dans le pire cas.
• Non in-place dans sa version classique (nécessite $O(n)$ mémoire supplémentaire).

Remarque. Sur des architectures où la mémoire est limitée (systèmes embarqués) ou où les allocations sont coûteuses, l’overhead mémoire de mergesort peut être problématique. Des variantes in-place existent mais sont beaucoup plus complexes et perdent une partie de leurs garanties pratiques.

Synthèse

* Avec la séquence de Knuth. Dépend de la séquence de gaps choisie.

Implémentations industrielles. Les implémentations réelles (glibc qsort, C++ std::sort, Rust sort_unstable) combinent généralement plusieurs idées : quicksort introspectif (qui bascule en heapsort si la profondeur de récursion devient excessive), insertion sort pour les petits segments, et parfois mergesort pour garantir la stabilité (std::stable_sort).