---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
kernelspec:
  display_name: C++17
  language: C++17
  name: xcpp17
---

+++ {"tags": ["solution"]}

# Exercice : tri vraiment rapide

:::{todo} 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.

1.  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

    ```cpp
    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

2.  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.

    ```cpp
    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

3.  Déterminez comment construire un tableau de longueur n pour lequel
    la complexité de ce dernier algorithme de tri rapide reste
    quadratique.