Exercice : tri vraiment rapide

Exercice : tri vraiment rapide#

À faire

2025-2026 Pour plus d’homogénéité, toujours utiliser l’idiom f(T+debut, fin-debut) pour passer un sous-tableau en paramètre?

L’algorithme du tri rapide est en pratique très efficace comme tri général. notre implémentation souffre toutefois de deux défauts :

Notre choix de pivot est relativement naïf et peut être nettement amélioré;
Pour les tableaux de petite taille, le tri par sélection reste plus efficace, le tri rapide ne le dépassant que lorsque la taille dépasse environ une centaine d’éléments.

Les deux questions suivantes visent à corriger ces deux problèmes.

Afin de minimiser les chances de choisir un pivot conduisant à deux sous tableaux très désequilibrés, une meilleure heuristique de choix consiste à prendre la médiane de trois éléments du tableaux. Définissez une nouvelle version de la fonction de choix de pivot qui choisi la médiane entre le premier, le dernier et l’élément du milieu du tableau à trier.

BEGIN SOLUTION

int pivot_med(int T[], int deb, int fin) {
    int med = (deb + fin) / 2;
    int a = T[deb];
    int b = T[fin];
    int c = T[med];
    if (a < b) {
        if (b < c) return fin;  // ici a < b < c
        if (a < c) return med;  // ici a < b, b >= c et a < c
        return deb;             // ici a < b, b >= c et a >= c
    } else {
        if (a < c) return deb;  // ici a >= b et a < c
        if (c < b) return fin;  // ici a >= b, a >= c et c < b
        return med;             // ici a >= b, a >= c et c >= b
    }
}

END SOLUTION

Modifiez la fonction de tri de manière à ce que les sous tableaux ne soient triés récursivement que si leur taille est supérieure à 100 éléments; sinon utilisez la fonction de tri par sélection définie dans le premier exercice.

BEGIN SOLUTION

Ici, le plus simple est de réaliser le test au début de la fonction rapide et non pas avant chaque appel récursif. Cela rend le test plus simple et permet de ne le réaliser qu’une seule fois. De plus, cela permet de tout de suite utiliser l’algorithme le plus rapide sans avoir besoin de faire au moins un niveau de tri rapide pour les petits tableaux.

Notez la manière de passer un sous-tableau en paramètre. Un tableau pouvant être assimilé ici à un pointeur vers sa première case, pour accéder à un sous tableau commençant à la position \(i\), il suffit d’ajouter \(i\) à cette adresse.
```
void tri_rapide(int T[], int deb, int fin) {
    if (fin - deb < 100) {
        tri_selection(T + deb, fin - deb + 1);
    } else {
        int idx_pivot = partitionner(T, deb, fin);
        tri_rapide(T, deb, idx_pivot - 1);
        tri_rapide(T, idx_pivot + 1, fin);
    }
}
```
END SOLUTION
Déterminez comment construire un tableau de longueur n pour lequel la complexité de ce dernier algorithme de tri rapide reste quadratique.