Tri à bulles en Java

Le tri à bulles est l'un des algorithmes les plus couramment utilisés pour trier les données en Java. Le tri est effectué de manière récursive en comparant les nombres adjacents et en les décalant dans l'ordre croissant ou décroissant. Ce déplacement des éléments est effectué jusqu'à ce que tous les chiffres soient complètement triés dans l'ordre requis. Le tri à bulles est le nom car les éléments d'une bulle de tableau sont leur façon de commencer. Comprenons l'algorithme de tri à bulles en prenant un exemple.

Exemple : Considérons un tableau de nombres [6 1 8 5 3] qui doivent être classés par ordre croissant.

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

L'algorithme de tri à bulles fonctionne en plusieurs itérations jusqu'à ce qu'il constate que tous les nombres sont triés.

Itérations

Vous trouverez ci-dessous les itérations effectuées dans Bubble Sort en Java qui sont les suivantes :

Première itération

[6 1 8 5 3] – Il commence par comparer les deux premiers nombres et décale le plus petit nombre des deux vers sa droite. Ainsi parmi 6 et 1, 1 est le plus petit nombre qui est décalé vers la gauche et 6 vers la droite. [1 6 8 5 3] – Ensuite, il compare les deux nombres adjacents en les décalant d'une position vers la droite. Ici, le nombre 6 est inférieur à 8, et donc le même ordre est conservé. [1 6 8 5 3] – Encore une fois, en décalant une position vers la droite, une comparaison a lieu entre 8 et 5. Le numéro 5 est décalé vers la gauche car il est plus petit que 8. [1 6 5 8 3] – Ici, la comparaison s'effectue entre les nombres 8 et 3. Le chiffre 3 est décalé vers la gauche puisqu'il est plus petit que 8. [1 6 5 3 8] – Ceci est le résultat final de la commande après la 1ère itération.

Deuxième itération

Comme les chiffres n'augmentent pas encore complètement, le programme passe à la deuxième itération.

[1 6 5 3 8] – Ici, la comparaison recommence à partir des deux premiers chiffres du résultat de la première itération. Il compare les nombres 1 et 6 et conserve le même ordre puisque 1 est inférieur à 6. [1 6 5 3 8] – Ici, les nombres 5 et 6 sont comparés. Le même ordre est conservé tel qu'il est déjà dans l'ordre croissant requis. [1 5 6 3 8] – Une comparaison se produit entre les nombres 6 et 3. Le chiffre 3 est décalé vers la gauche car il est plus petit que 6. [1 5 3 6 8] – Ensuite, les nombres 6 et 8 sont comparés les uns aux autres. Le même ordre est conservé tel quel dans un ordre attendu. [1 5 3 6 8] – C'est le résultat final après la deuxième itération. On remarque néanmoins que les chiffres ne sont pas complètement classés dans leur ordre croissant. Pourtant, nous devons échanger les numéros 5 et 3 pour obtenir le résultat final. Le programme passe donc à la troisième itération.

Troisième itération

[1 5 3 6 8] – la troisième itération commence par comparer les deux premiers chiffres, 1 et 5. Puisque l'ordre est comme prévu, il est conservé le même. [1 5 3 6 8]- Ensuite, les nombres adjacents 3 et 5 sont comparés. Puisque 5 est supérieur à 3, il est décalé vers la droite. [1 3 5 6 8] – L'itération compare ensuite les nombres 5 et 6, 6 et 8. Puisqu'il est dans l'ordre requis, il conserve l'ordre. [1 3 5 6 8] – Enfin, l'itération est arrêtée lorsque le programme parcourt en comparant chaque élément adjacent et constate que tous les chiffres sont dans l'ordre croissant.

Comme seuls 5 éléments d'un tableau devaient être triés, cela n'a pris que 3 itérations. À mesure que les éléments du tableau augmentent, le nombre d'itérations augmente également.

Implémentation du tri à bulles à l'aide de Java

Vous trouverez ci-dessous le code Java, qui implémente l'algorithme de tri Bubble. (Notez que la première position d'un tableau en Java commence à 0 et continue par incréments de 1, c'est-à-dire array[0], array[1], array[2], et cela continue.)

Code :

import java.util.Scanner;
public class BubbleSort {
static void bubbleSort(int[] arraytest) {
int n = arraytest.length; //length of the array is initialized to the integer n
int temp = 0; //A temporary variable called temp is declared as an integer and initialized to 0
for(int i=0; i < n; i++){ // first for loop performs multiple iterations
for(int j=1; j < (n-i); j++){
if(arraytest[j-1] > arraytest[j]){ // if loop compares the adjacent numbers
// swaps the numbers
temp = arraytest[j-1]; // assigns the greater number to temp variable
arraytest[j-1] = arraytest[j]; // shifts the lesser number to the previous position
arraytest[j] = temp; // bigger number is then assigned to the right hand side
}
}
}
}
public static void main(String[] args) {
int arraytest[] ={23,16,3,42,75,536,61}; // defining the values of array
System.out.println("Array Before Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++){ // for loop used to print the values of array
System.out.print(arraytest[i] + " ");
}
System.out.println();
bubbleSort(arraytest); // array elements are sorted using bubble sort function
System.out.println("Array After Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++){
System.out.print(arraytest[i] + " "); // for loop to print output values from array
}
}
}

Sortie :

Avantages et inconvénients du tri à bulles en Java

Vous trouverez ci-dessous les différents avantages et inconvénients du tri à bulles en Java :

Avantages

1. Le code est très simple à écrire et à comprendre. Cela ne prend généralement que quelques minutes.
2. La mise en œuvre est également très simple.
3. Le tri à bulles trie les nombres et les conserve en mémoire, économisant ainsi beaucoup de mémoire.

Inconvénients

1. Cet algorithme ne convient pas aux grands ensembles de données car la comparaison prend beaucoup de temps. Le temps nécessaire pour trier les nombres saisis augmente de façon exponentielle.
2. O(n^2) est la complexité moyenne du tri à bulles, et O(n) est la complexité dans le meilleur des cas (le meilleur cas est lorsque les éléments sont triés en premier lieu), où n est le nombre d'éléments.

Applications en temps réel

Le tri à bulles étant capable de détecter d'infimes erreurs de tri, il est utilisé en infographie. Il est également utilisé dans l’algorithme de remplissage des polygones, où les sommets du polygone doivent être triés.

Conclusion

Cet article a vu comment fonctionne l'algorithme de tri à bulles et comment il peut être implémenté à l'aide de la programmation Java. Le tri à bulles est un algorithme très stable qui peut être facilement implémenté pour des ensembles de données relativement petits. Il s'agit d'un cas d'algorithme de comparaison et est utilisé par les novices en raison de sa simplicité.

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!