Tri à bulles 3049 31782218 2008-07-22T08:26:59Z 193.252.28.206 /* Implémentations */ Erreur dans le script, il faut mettre j-- pour la décrémentatin 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 1{{er}} et le 2{{e}} é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. Pour trier un tableau A de taille N, le nombre de comparaisons entre paires d'éléments est donc au plus <math>N(N-1) \over 2</math>. Le nombre d'échanges de paires d'éléments successifs est égal au nombre de couples (i,j) tels que i < j et A(i) > A(j). Ce nombre d'échanges est indépendant de la manière d'organiser les échanges. Pour un tableau aléatoire, il est en moyenne égal à <math>N(N-1) \over 4</math>. Le tri à bulle utilisera donc sur un ordinateur un temps proportionnel à N<sup>2</sup>, ce qui est lent par comparaison avec les algorithmes en <math>n \log n</math>. [[Image:Bubble sort animation.gif|frame|right|Exemple du tri à bulle utilisant une liste de nombres aléatoires]] Un dérivé du tri à bulle est le ''shakersort'' ou ''tri cocktail''. Cette méthode de tri est basée sur une simple observation du comportement du tri à bulle : quand on fait un passage pour trier le maximum du tableau, on a tendance à déplacer les éléments les plus petits du tableau vers le début de celui-ci. Donc l'astuce consiste à alterner les sens de passage de notre bulle. Bien que le nombre d'échanges à effectuer soit identique (voir ci-dessus), on obtient un tri un peu plus rapide que la bulle. En effet, lors des changements de sens, cet algorithme relit les données les plus récentes et qui sont donc encore dans le tampon (cache) de la mémoire. Mais le temps d'exécution est toujours proportionnel à N<sup>2</sup> donc médiocre. ===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.<br> *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²) === Implémentations === Une mise en œuvre simple du tri à bulle sur un tableau d'entiers en [[C (langage)|C]] : <source lang=cpp> #define TRUE 1 #define FALSE 0 typedef int tab_entiers[MAX]; void tri_a_bulle(tab_entiers t) { int i = 0; /* Indice de répétition du tri */ int j = 0; /* Variable de boucle */ int tmp = 0; /* Variable de stockage temporaire */ /* Booléen marquant l'arrêt du tri si le tableau est ordonné */ int en_desordre = TRUE; /* Boucle de répétition du tri et le test qui arrête le tri dès que le tableau est ordonné */ for(i = 0 ; (i < MAX) && en_desordre; i++) { /* Supposons le tableau ordonné */ en_desordre = FALSE; /* Vérification des éléments des places j et j-1 */ for(j = 1 ; j < MAX - i ; j++) { /* Si les 2 éléments sont mal triés */ if(t[j] < t[j-1]) { /* Inversion des 2 éléments */ tmp = t[j-1]; t[j-1] = t[j]; t[j] = tmp; /* Le tableau n'est toujours pas trié */ en_desordre = TRUE; } } } } </source> Une amélioration en [[C (langage)|C++]] : <source lang=cpp> void tri_a_bulle(int *t, int size) { bool en_desordre=true; for (int i=0; i<size && en_desordre; ++i) { en_desordre=false; for (int j=1; j<size-i; ++j) if (t[j]<t[j-1]) { int tmp=t[j-1]; t[j-1]=t[j]; t[j]=tmp; en_desordre=true; } } } </source> Une implémentation en [[Pascal (langage)|Pascal]] (en ordre croissant) : <source lang=pascal> const MAX = 100; (* MAX = 100 est donné en exemple seulement *) type tab = array [1..MAX] of integer; procedure TriBulle(n: integer ; var t: tab); var i, j, tmp: integer; begin (* On va trier les n-1 premiers éléments du tableau *) for i := 1 to n - 1 do begin j := i; (* L'éléments d'indice i doit reculer *) (* Jusqu'à prendre sa place *) while (j >= 1) and (t[j + 1] < t[j]) do begin tmp := t[j]; t[j] := t[j + 1]; t[j+1] := tmp; j := j - 1; end; end; end; </source> Une implémentation en [[Java (langage)|Java]] : <source lang=java> public static void triBulle(int tableau[]) { int longueur=tableau.length; boolean permut; do { //hypothése : le tableau est trié permut=false; for(int i=0;i<longueur-1;i++) { //Teste si 2 éléments successifs sont dans le bon ordre ou non if(tableau[i]>tableau[i+1]) { //s'ils ne le sont pas on échange leurs positions echanger(tableau,i,i+1); permut=true; } } } while(permut); } </source> *Une implémentation en PHP : <source lang="PHP"> function bubble_sort($array){ $count = count($array); if ($count <= 0) return false; for($i=0; $i<$count; $i++){ for($j=$count-1; $j>$i; $j–-){ if ($array[$j] < $array[$j-1]){ $tmp = $array[$j]; $array[$j] = $array[$j-1]; $array[$j-1] = $tmp; } } } return $array; } </source> == Liens externes == *[http://www.algorithm-code.com/wiki/Bubble_sort Implémentation en PHP,C,C++,C#,Java] {{Algorithme_de_tri}} {{Portail Informatique}} [[Catégorie:Algorithme de tri|Bulles]] [[ar:ترتيب الفقاعات]] [[bg:Метод на мехурчето]] [[cs:Bubble sort]] [[da:Boblesortering]] [[de:Bubblesort]] [[el:Ταξινόμηση φυσαλίδας]] [[en:Bubble sort]] [[es:Ordenamiento de burbuja]] [[et:Mullisortimine]] [[fa:مرتب‌سازی حبابی]] [[fi:Kuplalajittelu]] [[he:מיון בועות]] [[hu:Buborékrendezés]] [[is:Bóluröðun]] [[it:Bubble sort]] [[ja:バブルソート]] [[ko:거품 정렬]] [[lt:Burbulo rikiavimo algoritmas]] [[nl:Bubblesort]] [[no:Boblesortering]] [[pl:Sortowanie bąbelkowe]] [[pt:Bubble sort]] [[ru:Сортировка пузырьком]] [[sk:Bublinkové triedenie]] [[sl:Mehurčno urejanje]] [[sv:Bubble sort]] [[tr:Kabarcık sıralaması]] [[uk:Сортування стандартним обміном]] [[vi:Sắp xếp nổi bọt]] [[zh:冒泡排序]]