Tri à bulles

Un tri à bulles trie le tableau en plusieurs phases. Chaque passe permute successivement les éléments voisins si les éléments ne sont pas en ordre. L'algorithme de tri à bulles effectue plusieurs passages dans le tableau. A chaque passage, des paires voisines successives sont comparées. Si une paire est en ordre décroissant, ses valeurs sont inversées ; sinon, les valeurs restent inchangées. La technique est appelée tri à bulles ou tri par descente, car les valeurs les plus petites « bouillonnent » progressivement vers le haut et les valeurs les plus grandes coulent vers le bas. Après le premier passage, le dernier élément devient le plus grand du tableau. Après le deuxième passage, l’avant-dernier élément devient le deuxième plus grand du tableau. Ce processus se poursuit jusqu'à ce que tous les éléments soient triés.

La figure ci-dessous (a) montre la première passe d'un tri à bulles sur un tableau de six éléments (2 9 5 4 8 1). Comparez les éléments de la première paire (2 et 9), et aucun échange n'est nécessaire car ils sont déjà dans l'ordre. Comparez les éléments de la deuxième paire (9 et 5) et échangez 9 avec 5 car 9 est supérieur à 5. Comparez les éléments de la troisième paire (9 et 4) et échangez 9 avec 4. Comparez les éléments de la quatrième paire (9 et 8) et échangez 9 avec 8. Comparez les éléments de la cinquième paire (9 et 1) et échangez 9 avec 1. Les paires comparées sont mises en surbrillance et les nombres déjà triés sont en italique dans la figure ci-dessous. 🎜>

La première passe place le plus grand nombre (9) comme dernier du tableau. Lors de la deuxième passe, comme le montre la figure ci-dessous (b), vous comparez et commandez des paires d'éléments de manière séquentielle. Il n’est pas nécessaire de considérer la dernière paire, car le dernier élément du tableau est déjà le plus grand. Lors de la troisième passe, comme le montre la figure ci-dessous (c), vous comparez et commandez des paires d'éléments séquentiellement, à l'exception des deux derniers éléments, car ils sont déjà dans l'ordre. Ainsi, dans la kième passe, vous n'avez pas besoin de considérer les k - 1 derniers éléments, car ils sont déjà ordonnés.

L'algorithme de tri à bulles est décrit dans le code ci-dessous.

pour (int k = 1; k < list.length; k++) {

// Effectuer la kième passe
pour (int i = 0; i < list.length - k; i++) {
si (liste[i] > liste[i + 1])
échanger la liste[i] avec la liste[i + 1];
>
>
Notez que si aucun échange n'a lieu dans une passe, il n'est pas nécessaire d'effectuer la passe suivante, car tous les éléments sont déjà triés. Vous pouvez utiliser cette propriété pour améliorer l'algorithme dans le code ci-dessus comme dans le code ci-dessous.

booléen needNextPass = true;

pour (int k = 1; k < list.length && needNextPass; k++) {
// Le tableau peut être trié et le prochain passage n'est pas nécessaire
needNextPass = false;
// Effectuer la kième passe
pour (int i = 0; i < list.length – k; i++) {
if (liste[i] > liste[i + 1]) {
échanger la liste[i] avec la liste[i + 1];
needNextPass = vrai ; // Le prochain passage est encore nécessaire
>
>
>

L'algorithme peut être implémenté dans le code ci-dessous

Dans le meilleur des cas, l'algorithme de tri à bulles n'a besoin que du premier passage pour constater que le tableau est déjà trié ; aucun passage suivant n'est nécessaire. Puisque le nombre de comparaisons est n - 1 lors du premier passage, le meilleur moment pour un tri à bulles est O(n).

Dans le pire des cas, l'algorithme de tri à bulles nécessite n - 1 passes. La première passe effectue n - 1 comparaisons ; le deuxième passage effectue n - 2 comparaisons ; et ainsi de suite; la dernière passe fait 1 comparaison. Ainsi, le nombre total de comparaisons est :

Par conséquent, le pire moment pour un tri à bulles est O(n^2).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!