Tri à bulles

Le tri à bulle ou tri par propagation est un algorithme de tri très critiqué à cause de sa lenteur d'exécution. Il consiste à faire remonter le plus grand élément du tableau (comme une bulle d'air remonte à la surface) en comparant les éléments successifs. C'est-à-dire qu'on va comparer le 1er et le 2e élément du tableau, conserver le plus grand et puis les échanger s'ils sont désordonnés les uns par rapport aux autres. On recommence cette opération jusqu'à la fin du tableau. Ensuite, il ne reste plus qu'à renouveler cela jusqu'à l'avant-dernière place et ainsi de suite… On arrête quand le tableau à trier est de taille 1 ou qu'on n'a pas fait d'échanges au dernier passage.

 

Complexité

Pour un tableau de taille n, la boucle for sera exécutée n-1 fois et while sera exécutée une fois si permut == faux, c'est-à-dire le tableau est trié n-1 fois si permut est vrai.
Meilleur cas : O(n) le tableau est trié : n * 1 = o(n)
Pire cas: o(n²) le tableau est trié en ordre inverse (n -1)*(n-1) = o(n²)