Exercice 1 — Tri naïf

Sujet

Prérequis : Soit \(n\) un entier strictement positif. On admet que \(0+1+2+\cdots+(n-2)+(n-1)=\frac{n(n-1)}{2}\).
En informatique, il est courant d'avoir besoin de trier des données. Nous nous intéressons au tri de données numériques entières, c'est-à-dire au fait de trier des listes données de nombres entiers. Une liste est une suite finie de nombres. Une liste de n éléments est appelée une \(n\)-liste.
Par exemple, \(L=(5 ;-2 ; 0 ; 5)\) est une 4-liste. Sa version « ordonnée» serait \(L=(-2 ; 0 ; 5 ; 5)\).

Voici un algorithme qui permet, à partir d'une liste \(L\) de nombres donnée, d'obtenir son minimum min .
Remarque : l'instruction \(a \leftarrow b\) signifie que la valeur de \(b\) est stockée dans la variable a.

Pour la suite de l'exercice, on notera \(\min (L)\) le minimum d'une liste \(L\), ainsi obtenu dans la variable min à la fin de l'algorithme.

Saisir \(L\)
\(x \leftarrow\) premier élément de \(L\)
\(\min \leftarrow x\)
Tant que \(x \mathrm{n}^{\prime}\) est pas le dernier élément de \(L\) Faire
    \(x \leftarrow\) élément suivant de \(L\)
    Si \(x<\min\) alors
        \(\min \leftarrow x\)
    Fin Si
Fin Tant que

1. Faire tourner cet algorithme avec la 8 -liste \(L=(5 ; 9 ;-10 ; 2 ; 3 ;-15 ; 120 ; 1)\).

Pour cela, recopier le tableau ci-contre, et le compléter au fur et à mesure de l'exécution de l'algorithme. Vous munirez le tableau du nombre de lignes nécessaires. Préciser quelle est la valeur contenue dans la variable min lorsque l'exécution de l'algorithme se termine.
2. Le fait de se demander lequel de deux nombres donnés est le plus petit

ou le plus grand est appelé une comparaison.
a. Combien opère-t-on de comparaisons sur une 8 -liste pour la recherche de son minimum ?
b. Combien opère-t-on de comparaisons sur une \(n\)-liste, avec \(n\) entier strictement positif quelconque, pour la recherche de son minimum ?
3. Les créateurs d'un jeu vidéo en ligne cherchent à classer rapidement les joueurs, en fonction de leur nombre d'erreurs ; ces joueurs sont classés dans l'ordre croissant de leur nombre d'erreurs.
Les nombres d'erreurs par joueur constituent une liste d'entiers qu'il faut donc ordonner (on admet que le nom du joueur reste associé à son nombre d'erreurs). On suppose que l'on dispose de l'instruction « supprimer un élément de la liste », qui supprime la première occurrence de l'élément donné, dans la liste donnée et de l'instruction « ajouter un élément à la liste », qui vient ajouter l'élément donné à la fin de la liste (à droite).
Les créateurs élaborent l'algorithme ci-contre, où \(L_{1}\) est une liste donnée de nombres :
a. Faire tourner cet algorithme avec la 4-liste \(L_{1}=(3 ; 6 ; 6 ;-10)\), puis une autre fois avec la 8 -liste \(L_{1}{ }^{\prime}=\)
( \(5 ; 9 ;-10 ; 2 ; 3 ;-15 ; 120 ; 1\) )
b. Quel est le rôle de cet algorithme ?
4. a.Justifier que l'exécution de l'algorithme nécessite 6 comparaisons pour la liste \(L_{1}\).

Saisir \(L_{1}\)
\(L_{2}\) ← Liste vide
Tant que \(L_{1}\) n'est pas vide
Faire
    \(m \leftarrow \min \left(L_{1}\right)\)
    Ajouter \(m\) à \(L_{2}\)
    Supprimer \(m\) de \(L_{1}\).
Fin Tant que

b. Déterminer le nombre de comparaisons opérées par l'algorithme pour la liste \(L_{1}{ }^{\prime}\).
5. On considère une \(n\)-liste pour \(n\) entier strictement positif. On note \(T(n)\) le nombre de comparaisons utilisées pour trier une \(n\)-liste. Justifier que \(T(n)=\frac{n^{2}}{2}-\frac{n}{2}\).
6. Quelques propriétés...