Dérouler le tri à bulles

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 3 — Boucles imbriquées et complexité quadratique

Énoncé

Simuler le tri à bulles à la main sur la liste $t = [5, 1, 4, 2]$ . Donner l'état de la liste après chaque passe externe, vérifier l'invariant et compter le nombre de comparaisons et d'échanges.

Corrigé

Passe $k = 0$ (Zone non triée $t [0..3]$ , 3 comparaisons) :
Compare 5 et 1 $\to$ échange $\to [1, 5, 4, 2]$
Compare 5 et 4 $\to$ échange $\to [1, 4, 5, 2]$
Compare 5 et 2 $\to$ échange $\to [1, 4, 2, 5]$
Bilan : Le plus grand élément 5 est à sa place définitive. L'invariant $t [3..3] = [5]$ est validé.
Passe $k = 1$ (Zone non triée $t [0..2]$ , 2 comparaisons) :
Compare 1 et 4 $\to$ pas d'échange $\to [1, 4, 2, 5]$
Compare 4 et 2 $\to$ échange $\to [1, 2, 4, 5]$
Bilan : L'invariant $t [2..3] = [4, 5]$ est validé.
Passe $k = 2$ (Zone non triée $t [0..1]$ , 1 comparaison) :
Compare 1 et 2 $\to$ pas d'échange $\to [1, 2, 4, 5]$
Bilan : L'invariant $t [1..3] = [2, 4, 5]$ est validé. Au total, l'algorithme a réalisé $3 + 2 + 1 = 6$ comparaisons et $4$ échanges.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.