Exercice : Tri rapide

Dans cet exercice vous allez implémenter une version basique du tri rapide vu en cours. Attention de bien tester toutes vos fonctions au fur et à mesure en pensant bien à tous les cas limites.

À faire

2025-2026

• Commencer par prendre un pivot non aléatoire (par exemple le premier); d’abord pour faciliter les tests avec un code déterministe. Mais aussi pour leur faire toucher du doigt sur des exemples que la complexité est quadratique.

• Exprimer explicitement les invariants et spécifications. Et les faire écrire dans la doc et/ou le code; en langue naturelle ou sous forme de tests

• Leur faire compter le nombre d’opérations?

• Extraire la solution code dans un fichier séparé pour pouvoir le tester. Ou bien le mettre dans des cellules.

1. La première fonction à écrire pour implémenter le tri rapide est la fonction de choix du pivot. Une première implémentation simple et relativement efficace est de choisir le pivot de manière aléatoire.

   Cette fonction comme les suivantes prend en paramètre le tableau à trier ainsi que les indices du premier et du dernier élément à trier. Elle renvoie l’indice du pivot choisit.

   int pivot(int T[], int debut, int fin);
   

   BEGIN SOLUTION

   int pivot(int T[], int debut, int fin) {
       int cnt = fin - debut + 1;  // nb d'éléments de la zone à trier
       return rand() % cnt + debut;
   }
   

   END SOLUTION

2. Le cœur de l’algorithme est dans la fonction de partitionnement qui va permuter les éléments du tableau entre les index debut et fin inclus, de manière à ce que tous les éléments inférieurs ou égaux au pivot soient placés avant celui-ci et que tous les éléments strictement supérieurs au pivot soient placés après.

   Cette fonction doit renvoyer l’index de la case du tableau qui contient le pivot après permutation.

   int partitionner(int T[], int debut, int fin);
   

   BEGIN SOLUTION

   int partitionner(int T[], int debut, int fin) {
       int idx_pivot = pivot(T, debut, fin);
       echanger(T, idx_pivot, fin); // à présent le pivot est T[fin]
       int limite = debut;
       for (int i = debut; i < fin; i++) {
           if (T[i] <= T[fin]) {
               echanger(T, i, limite);
               limite++;
           }
       }
       echanger(T, limite, fin);    // mettre le pivot à sa place
       return limite;
   }
   

   END SOLUTION

3. Il est maintenant possible d’implémenter le tri rapide. Cette fonction doit partitionner le sous tableau entre debut et fin inclus autour d’un pivot et ensuite trier récursivement les deux sous tableaux à gauche et à droite du pivot.

   void trirapide(int T[], int debut, int fin);
   

   BEGIN SOLUTION

   void tri_rapide(int T[], int debut, int fin) {
       if (debut < fin) {
           int idx_pivot = partitionner(T, debut, fin);
           tri_rapide(T, debut, idx_pivot - 1);
           tri_rapide(T, idx_pivot + 1, fin);
       }
   }
   

   END SOLUTION