Bubble Algorithme de tri dans Java: Programme de tri de tableaux et exemple
James Hartmann
⚡ Résumé intelligent
Bubble Algorithme de tri dans Java Cette fonction compare et échange les éléments adjacents d'un tableau jusqu'à obtenir l'ordre souhaité. Cet article explique son fonctionnement, son pseudocode et son implémentation complète. Java implémentation, variante optimisée, analyse de la complexité et comparaisons pratiques avec d'autres techniques de tri.
Qu'est-ce que le Bubble Trier ?
BubblL'algorithme de tri E est un algorithme simple basé sur la comparaison qui compare le premier élément du tableau au suivant. Si l'élément courant est numériquement supérieur au suivant, les éléments sont échangés. L'algorithme parcourt ainsi l'ensemble des éléments du tableau.
L'algorithme tire son nom de la manière dont la plus grande valeur de la zone non triée remonte progressivement à sa position finale, à l'image d'une bulle d'eau qui remonte à la surface. Après le premier passage complet, l'élément le plus grand occupe la dernière position. Après le deuxième passage, le deuxième plus grand élément est verrouillé à cette position, et le processus se répète jusqu'à ce que le tableau soit entièrement trié.
Dans cet article, nous allons créer un Java programme à mettre en œuvre Bubble Tri. Vérifiez le résultat du code qui vous aidera à comprendre la logique du programme, puis examinez la version optimisée et l'analyse de complexité qui suivent.
Comment le BubblL'algorithme de tri fonctionne-t-il ?
BubblLa fonction eTri fonctionne par passages successifs sur le tableau. Chaque passage parcourt le tableau du premier indice jusqu'à la fin de la zone non triée, en comparant les valeurs voisines et en les échangeant.ping Ces valeurs sont triées lorsqu'elles apparaissent dans le désordre. Comme la plus grande valeur restante se déplace toujours à l'extrême droite de la zone non triée, cette zone se rétrécit d'une position exactement après chaque passage.
Le processus complet peut être décomposé en quatre étapes répétables :
- Comparez: Examinez l'élément à l'indice j-1 par rapport à l'élément à l'indice j.
- Swap: Si l'élément de gauche est supérieur à l'élément de droite, échangez les deux valeurs à l'aide d'une variable temporaire.
- Avance: Déplacez-vous d'une position vers la droite et répétez l'opération jusqu'à atteindre la fin de la zone non triée.
- Répéter: Commencez un nouveau passage sur une région qui est plus courte d'un élément, et arrêtez-vous après n-1 passages ou lorsqu'un passage n'effectue aucun échange.
Le tableau ci-dessous tracVoici l'exemple de tableau {860, 8, 200, 9} utilisé dans le programme présenté plus loin sur cette page. Il montre précisément quelle valeur se stabilise à sa position finale à la fin de chaque itération.
| Passé | Tableau au début du passage | Comparaisons effectuées | Tableau à la fin du passage | Élément verrouillé |
|---|---|---|---|---|
| 1 | 860, 8, 200, 9 | 3 | 8, 200, 9, 860 | 860 |
| 2 | 8, 200, 9, 860 | 2 | 8, 9, 200, 860 | 200 |
| 3 | 8, 9, 200, 860 | 1 | 8, 9, 200, 860 | 9 |
| 4 | 8, 9, 200, 860 | 0 | 8, 9, 200, 860 | 8 |
Notez que le troisième passage effectue une comparaison mais aucun échange. Une implémentation optimisée détecte cette situation et s'arrête immédiatement ; il s'agit là de l'amélioration la plus précieuse que vous puissiez apporter à cet algorithme.
BubblPseudocode de l'algorithme de tri
Avant d'écrire Java La syntaxe permet d'exprimer la logique en pseudocode indépendant du langage. La version ci-dessous inclut l'indicateur de sortie anticipée, couvrant ainsi les comportements classique et optimisé.
procedure bubbleSort(array A, integer n) for i from 0 to n - 2 do swapped := false for j from 1 to n - i - 1 do // compare the adjacent pair if A[j - 1] > A[j] then swap A[j - 1] and A[j] swapped := true end if end for // no swap in a full pass means the array is sorted if swapped = false then break end if end for end procedure
La boucle externe contrôle le nombre d'itérations, et la boucle interne contrôle les comparaisons au sein d'une même itération. La limite supérieure de la boucle interne est n – i – 1 car les i dernières positions contiennent déjà leurs valeurs finales.
Java Programme de mise en œuvre Bubble Trier
Le programme suivant trie un tableau d'entiers par ordre croissant. Des instructions d'affichage supplémentaires ont été intentionnellement placées à l'intérieur des boucles, car la lecture du résultat passe par passe trace est le moyen le plus rapide pour un débutant de comprendre comment les échanges s'accumulent.
package com.guru99; public class BubbleSort { public static void main(String[] args) { int arr[] = {860, 8, 200, 9}; System.out.println("---Array BEFORE Bubble Sort---"); printArray(arr); bubbleSort(arr); //sorting array elements using bubble sort System.out.println("---Array AFTER Bubble Sort---"); printArray(arr); } static void bubbleSort(int[] array) { int n = array.length; int temp = 0; for(int i = 0; i < n; i++) // Looping through the array length { System.out.println("Sort Pass Number " + (i + 1)); for(int j = 1; j < (n - i); j++) { System.out.println("Comparing " + array[j - 1] + " and " + array[j]); if(array[j - 1] > array[j]) { //swap elements temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; System.out.println(array[j] + " is greater than " + array[j - 1]); System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } } } static void printArray(int[] array){ for(int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Sortie :
---Array BEFORE Bubble Sort--- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Swapping Elements: New Array After Swap 8 860 200 9 Comparing 860 and 200 860 is greater than 200 Swapping Elements: New Array After Swap 8 200 860 9 Comparing 860 and 9 860 is greater than 9 Swapping Elements: New Array After Swap 8 200 9 860 Sort Pass Number 2 Comparing 8 and 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 8 and 9 Sort Pass Number 4 ---Array AFTER Bubble Sort--- 8 9 200 860
Code explication: Le tri à bulles La méthode reçoit le tableau par référence, de sorte que l'appelant voit le résultat trié sans qu'aucune valeur de retour ne soit fournie. La variable Temp Elle conserve une seule valeur pendant l'échange sur trois lignes, c'est pourquoi l'algorithme ne nécessite que O(1) de mémoire supplémentaire. L'expression n – i La condition de la boucle interne garantit que les positions déjà triées à la fin ne sont jamais revisitées.
Optimisé Bubble Programme de tri dans Java
Le programme ci-dessus effectue toujours n-1 passages, même si le tableau est trié prématurément. L'ajout d'un simple indicateur booléen corrige cette inefficacité. Si un passage complet s'achève sans aucun échange, le tri du tableau est garanti et la boucle externe peut s'arrêter immédiatement.
package com.guru99; public class OptimizedBubbleSort { public static void main(String[] args) { int arr[] = {5, 12, 33, 47, 58}; bubbleSort(arr); System.out.println(java.util.Arrays.toString(arr)); } static void bubbleSort(int[] array) { int n = array.length; int passes = 0; for (int i = 0; i < n - 1; i++) { boolean swapped = false; for (int j = 1; j < n - i; j++) { if (array[j - 1] > array[j]) { int temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; swapped = true; } } passes++; // Early exit: the array is already sorted if (!swapped) { break; } } System.out.println("Passes executed: " + passes); } }
Sortie :
Passes executed: 1 [5, 12, 33, 47, 58]
Le tableau d'entrée étant déjà trié, la version optimisée s'est terminée en une seule passe au lieu de quatre. Sur des données presque triées, ce changement transforme une charge de travail quadratique en une charge de travail quasi linéaire, ce qui en est la principale raison. BubblLa fonction e Sort apparaît encore de temps à autre dans du code réel.
Complexité temporelle et complexité spatiale de Bubble Trier
La complexité décrit comment le temps d'exécution augmente avec la taille des données d'entrée. Bubble Le nombre de comparaisons dans la version non optimisée est fixé à n(n-1)/2, ce qui la place fermement dans la classe quadratique.
| Scénario | Condition d'entrée | Complexité temporelle | Complexité spatiale |
|---|---|---|---|
| Meilleur cas | Tableau déjà trié, version optimisée | O (n) | O (1) |
| Cas moyen | Éléments dans un ordre aléatoire | O(n²) | O (1) |
| Pire cas | Tableau trié en ordre inverse | O(n²) | O (1) |
Parce que chaque échange a lieu à l'intérieur du tableau d'origine et qu'une seule variable temporaire est utilisée, BubblLe tri e est un algorithme en place avec un espace auxiliaire O(1). C'est également un tri stable, ce qui signifie que deux enregistrements ayant la même clé conservent leur ordre relatif initial après le tri.
Avantages et inconvénients de Bubble Trier
Comprendre les deux aspects vous aide à décider quand l'algorithme est un choix acceptable et quand il doit être remplacé.
Avantages
- Simplicité: La logique tient en une dizaine de lignes, ce qui facilite une rédaction correcte en situation d'entretien.
- Fonctionnement sur place : Aucun tableau auxiliaire n'est alloué, la consommation de mémoire n'augmente donc pas avec la taille des données d'entrée.
- La stabilité: Les clés identiques conservent leur ordre d'origine, ce qui est important lors du tri des enregistrements par un champ secondaire.
- Détection précoce des sorties : L'indicateur d'inversion permet d'identifier un tableau déjà trié en une seule passe.
Désavantages
- Croissance quadratique : Le tri de 10 000 éléments nécessite près de 50 millions de comparaisons dans le pire des cas.
- Écritures excessives : Cet algorithme effectue beaucoup plus d'échanges que le tri par sélection, qui est coûteux en mémoire en raison de ses opérations d'écriture lentes.
- Faible évolutivité : Les charges de travail en production privilégient presque toujours Quicksort, Merge Sort ou la méthode intégrée Arrays.sort.
Astuce : En production Java code, préférez Arrays.sort () pour les primitives et Collections.sort() pour les listes. Les deux utilisent des algorithmes hautement optimisés, Dual-Pivot Quicksort et TimSort respectivement, qui surpassent un tri manuel. Bubble Trier par ordre de grandeur.
Bubble Tri par rapport à d'autres types de tri Algorithms
Le tableau ci-dessous compare Bubble Triez avec les techniques de tri que les débutants découvrent ensuite, afin que vous puissiez voir exactement où chacune l'emporte.
| Algorithme | Meilleur cas | Cas moyen | Pire cas | évenementiels | Stable |
|---|---|---|---|---|---|
| Bubble Trier | O (n) | O(n²) | O(n²) | O (1) | Oui |
| Tri de sélection | O(n²) | O(n²) | O(n²) | O (1) | Non |
| Tri par insertion | O (n) | O(n²) | O(n²) | O (1) | Oui |
| Tri rapide | O (n log n) | O (n log n) | O(n²) | O (log n) | Non |
| Tri de tas | O (n log n) | O (n log n) | O (n log n) | O (1) | Non |
BubblLe tri par insertion et le tri par sélection partagent le même meilleur cas linéaire, mais le tri par insertion effectue moins d'échanges sur des données partiellement triées. Le tri par sélection effectue toujours exactement n-1 échanges, ce qui le rend plus performant dans le meilleur des cas.tracL'algorithme Quicksort est utile lorsque les écritures sont coûteuses, même s'il sacrifie la stabilité. Pour tout tableau de plus de quelques centaines d'éléments, Quicksort ou Heap Sort est le choix approprié.
Une fois que vous maîtrisez les modèles de parcours de tableau utilisés ici, la même structure de boucle apparaît dans de nombreux exercices classiques tels que… la série de Fibonacci dans Java et la Java programme palindrome. Revregarder Java tableaux et le plus large Java tutoriel renforcera les fondements sur lesquels repose cet algorithme.
