C++Talk.NET

BuG · Guest

Voici l'algorithme du Tri Bulle :

Tri_bulle (t[1....n]) :

1: i <- 1
2: tant que i <- n-1 faire
3: j <- n
4: tant que j -> i+1 faire
5: si t[j] < t[j -1] alors
6: valeur <- t[j]
7: t[j] <- t[j -1]
8: t[j -1] <- valeur
9: j <- j-1
10:i <- i+1

La question etant :
Soit n la taille du tableau à trier et k la valeur de la variable i à
l'entrée dans la deuxième boucle "tant que". Soit C(n,k) le nombre de fois
où la comparaison de la ligne 5 est effectuée. Exprimez C(n,k) en fonction
de n et k.

La réponse etant;

"C(n,k) = n - (k +1) +1"
"C(n,k) = n-1 "

*********************

Ma question :
En regardant des exemples de tri bulle, on s'aperçoit facilement que si n
reprénsente la taille du tableau, alors le nombre de comparaison est égal à
n- 1 à chaque passage dans le tableau. On compare un element avec les autres
element.... excepté lui même . Mais mon problème etant que je ne comprends
pas ce raisonnement.

Qqun peut m'aider ?

Merci

Gib
----
[email]bug (AT) asrun (DOT) org[/email]