La passe qui certifie

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

É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$ .

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.