Ressources mathématiques > Base de données d'exercices > Exercices de théorie des graphes et d'algorithmique >
Exercices corrigés - Algorithmique : tris
Enoncé
La fonction tri_bulle ci-dessous prend en argument une liste L de nombres flottants et en effectue un tri en ordre croissant.
def tri_bulle(L):
n=len(L)
for i in range(n):
for j in range(n-1,i,-1):
if L[j]<L[j-1]:
L[j],L[j-1]=L[j-1],L[j] # échange d'éléments
def tri_bulle(L):
n=len(L)
for i in range(n):
for j in range(n-1,i,-1):
if L[j]<L[j-1]:
L[j],L[j-1]=L[j-1],L[j] # échange d'éléments
- Lors de l'appel tri_bulle(L) où L est la liste [5,2,3,1,4], donner le contenu de la liste L à la fin de chaque itération de la boucle for i in range(n):.
- On suppose que L est une liste non vide de nombres réels. Montrer que, pour tout $k\in\{0,\dots,n\}$, la propriété $\mathcal P(k)$ suivante est vraie :
"après $k$ itérations de la première boucle, les $k$ premiers éléments de la liste sont triés par ordre croissant et sont tous inférieurs aux $n-k$ éléments restants".
En déduire que tri_bulle(L) trie bien la liste L en ordre croissant. - Donner la complexité dans le meilleur des cas et dans le pire des cas de la fonction tri_bulle.