V VIDYALAYA · Soutien scolaire
Mathématiques2ndeAlgorithmique et programmationExercices + corrigé

Algorithmes de recherche et tri — Exercices

Tracer, compléter, écrire. Corrigé en fin de fiche.
⏱ ~30 min✎ Calculatrice inutile
1Recherche du maximum — trace/ 4 pts
On applique l'algorithme de recherche du maximum à la liste $L = [7, 2, 9, 4, 6, 1]$.
  1. Recopier et compléter le tableau de trace : pour chaque indice $i$ de 2 à 6, indiquer si max est mis à jour et donner la valeur courante de max.
  2. Quelle valeur l'algorithme renvoie-t-il ?
  3. Pour une liste de $n$ éléments, combien de comparaisons cet algorithme effectue-t-il ?
2Recherche d'un élément/ 3 pts
On utilise l'algorithme de recherche d'un élément sur la liste $L = [3, 8, 5, 1, 7]$.
  1. Chercher la valeur $5$ : combien de comparaisons sont effectuées ? Que renvoie l'algorithme ?
  2. Chercher la valeur $4$ : combien de comparaisons ? Que renvoie l'algorithme ?
  3. Dans quel cas le nombre de comparaisons est-il maximal ?
3Tri par sélection — trace complète/ 6 pts
On trie la liste $L = [5, 2, 8, 1, 4]$ par sélection (indices 1 à 5).
  1. Donner l'état de la liste après chacune des 4 étapes du tri.
  2. Combien d'échanges effectifs ont eu lieu (échanges entre deux éléments de valeurs distinctes) ?
  3. Calculer le nombre total de comparaisons, puis vérifier avec la formule $\displaystyle\sum_{k=1}^{n-1} k = \dfrac{(n-1)n}{2}$.
4Compléter un algorithme/ 4 pts

L'algorithme ci-dessous doit renvoyer l'indice du minimum d'une liste $L$ de $n$ éléments (indices 1 à $n$). Trois cases sont manquantes (notées ___).

i_min ← ___
Pour j allant de 2 à n :
    Si L[j] < ___ alors i_min ← ___
Retourner i_min

  1. Recopier l'algorithme en complétant les trois cases.
  2. Appliquer l'algorithme complété à $L = [6, 3, 9, 1, 5]$. Quelle valeur est renvoyée et que représente-t-elle ?
5Problème — notes d'une classe/ 3 pts
Les notes de six élèves sont : $L = [12, 17, 8, 14, 11, 19]$.
  1. Appliquer l'algorithme de recherche du maximum pour déterminer la meilleure note.
  2. Appliquer le tri par sélection et donner l'état de la liste après chaque étape.
  3. Quelle unique modification faut-il apporter à l'algorithme pour trier dans l'ordre décroissant ?
Corrigé détaillé
1Recherche du maximum — trace
Trace \(\text{max}=7.\; i{=}2: 2\lt7\to\text{max}=7.\; i{=}3: 9\gt7\Rightarrow\text{max}=9.\; i{=}4: 4\lt9.\; i{=}5: 6\lt9.\; i{=}6: 1\lt9.\) \(\text{max} = 9\)
Nb de comparaisons \(\text{Une comparaison pour chaque }i\in\{2,3,\ldots,n\}.\) \(n-1\text{ comparaisons}\)
2Recherche d'un élément
Chercher 5 \(i{=}1: 3\neq5.\; i{=}2: 8\neq5.\; i{=}3: 5=5\Rightarrow\text{trouve}=\text{Vrai}.\) \(3\text{ comparaisons ; renvoie Vrai.}\)
Chercher 4 \(i{=}1: 3\neq4.\; i{=}2: 8\neq4.\; i{=}3: 5\neq4.\; i{=}4: 1\neq4.\; i{=}5: 7\neq4.\) \(5\text{ comparaisons ; renvoie Faux.}\)
Cas maximal \(\text{L'element est absent ou en derniere position.}\) \(n\text{ comparaisons.}\)
3Tri par sélection — trace complète
Étape 1 \([5,2,8,1,4]:\;\min=1\text{ (indice 4). Echange L[1]}\leftrightarrow\text{L[4].}\) \([1,\;2,\;8,\;5,\;4]\)
Étape 2 \([1,2,8,5,4]:\;\min=2\text{ (indice 2). Deja en place.}\) \([1,\;2,\;8,\;5,\;4]\)
Étape 3 \([1,2,8,5,4]:\;\min=4\text{ (indice 5). Echange L[3]}\leftrightarrow\text{L[5].}\) \([1,\;2,\;4,\;5,\;8]\)
Étape 4 \([1,2,4,5,8]:\;\min=5\text{ (indice 4). Deja en place.}\) \([1,\;2,\;4,\;5,\;8]\)
Bilan \(\text{Echanges effectifs : etapes 1 et 3.}\quad 4+3+2+1=\dfrac{4\times5}{2}\) \(2\text{ echanges}.\quad 10\text{ comparaisons.}\)
4Compléter un algorithme
Complétion \(i_{\min}\leftarrow1.\quad\text{Si }L[j]\lt L[i_{\min}]\text{ alors }i_{\min}\leftarrow j.\) \(\text{Retourner }i_{\min}\)
Application \(j{=}2: 3\lt6\Rightarrow i_{\min}{=}2.\; j{=}3: 9\gt3.\; j{=}4: 1\lt3\Rightarrow i_{\min}{=}4.\; j{=}5: 5\gt1.\) \(\text{Retourne 4 : le minimum (valeur 1) est a l'indice 4.}\)
5Problème — notes d'une classe
Maximum \(\text{max}=12\to17\gt12\Rightarrow\text{max}=17\to8,14,11\lt17\to19\gt17\Rightarrow\text{max}=19.\) \(\text{Meilleure note : }19\)
Tri \(\text{Et.1}: \min=8,\;1\leftrightarrow3\to[8,17,12,14,11,19].\;\text{Et.2}: \min=11,\;2\leftrightarrow5\to[8,11,12,14,17,19].\;\text{Et.3-5 : en place.}\) \([8,\;11,\;12,\;14,\;17,\;19]\)
Ordre décroissant \(\text{Remplacer }L[j]\lt L[i_{\min}]\text{ par }L[j]\gt L[i_{\max}].\) \(\text{On cherche le maximum a chaque etape (tri par selection du maximum).}\)