ENNONCÉ :

La médiane est un élément fondamental en statistiques. Dans un tableau T[1 \ldots n] contenant des entiers, la médiane est définie comme suit :

• Si n est impair, la médiane est le \lceil n/2 \rceil-ième plus petit élément.
• Si n est pair, la médiane est l'un des deux éléments au centre après tri.

Trouver la médiane peut sembler simple lorsqu'on trie le tableau, mais il existe des algorithmes plus efficaces qui n'impliquent pas de trier tout le tableau. L'objectif de cet exercice est d'explorer ces méthodes.

Partie 1 : Compréhension de l'algorithme

1. Définir la notion de k-ième plus petit élément :

   Expliquez ce qu'on entend par le k-ième plus petit élément dans un tableau T[1 \ldots n]. Utilisez un exemple pour illustrer.

2. Analyse naïve :

   Supposons que vous deviez trouver la médiane d'un tableau en triant tous ses éléments. Quel est le coût en temps de cet algorithme si vous utilisez un tri rapide ou un tri fusion ? Justifiez.

Partie 2 : Implémentation de l'algorithme de sélection

1. L'algorithme de sélection :

   Implémentez un algorithme pour trouver le k-ième plus petit élément dans un tableau T[1 \ldots n] en utilisant la méthode suivante :

   • Choisir un pivot p.
   • Répartir les éléments du tableau en trois groupes : ceux plus petits que p, égaux à p, et plus grands que p.
   • Décider, en fonction de k, dans quel groupe chercher.

   Exemple d'entrée :

   Tableau : [7, 10, 4, 3, 20, 15]
   k = 3
                   

   Sortie attendue :

   7, car c'est le 3ème plus petit élément du tableau.

2. Optimisation avec sélection rapide :

   Adaptez l'algorithme pour qu'il fonctionne en O(n) dans le cas moyen, en utilisant une approche similaire à QuickSort. Justifiez comment le pivot est choisi et pourquoi cet algorithme est efficace.

Partie 3 : Problèmes avancés

1. Extension - Médiane :

   Utilisez l'algorithme de sélection pour trouver la médiane d'un tableau T[1 \ldots n]. Vérifiez que votre solution est correcte pour :

   • n impair.
   • n pair.

2. Partitionnement en trois groupes :

   Modifiez votre algorithme pour qu'il divise le tableau T en trois parties :

   • T_1 : éléments < pivot,
   • T_2 : éléments = pivot,
   • T_3 : éléments > pivot.

   Assurez-vous que le partitionnement est réalisé en une seule passe.

Données d'exemple :

1. Jeu de test 1 :
   • Tableau : [10, 4, 5, 8, 6, 11, 26]
   • Trouver la médiane.
2. Jeu de test 2 :
   • Tableau : [1, 3, 5, 2, 2]
   • Trouver le k = 4-ième plus petit élément.

Critères d'évaluation :

• Respect des concepts de partitionnement et de sélection rapide.
• Complexité de votre solution.
• Justification des choix algorithmiques.