La passe qui certifie

Boucles imbriquées et complexité quadratique · niveau 2

Énoncé

Démontrer rigoureusement que si une passe complète du tri à bulles n'effectue aucun échange, alors le tableau est trié. Donner le variant de la boucle externe du tri à bulles amélioré.

Corrigé

Preuve : Si aucun échange n'a été fait, alors pour chaque indice $i \in {0, \dots, n - 2 - k}$ , le test de condition a donné $t [i] \leq t [i + 1]$ . Par transitivité de la relation d'ordre $\leq$ , on en déduit que pour tout couple d'indices $a < b$ , $t [a] \leq t [b]$ , ce qui prouve la croissance globale de la liste.
Variant de la boucle externe : La quantité $v = (n - 1) - k$ convient. Tant que la boucle tourne, $k \leq n - 1$ . De plus, $k$ augmente strictement de 1 à chaque tour de boucle, ce qui fait décroître strictement $v$ .

Énoncé

Corrigé

Exercices semblables