Introduction au Bubble Sort en Java

Le tri à bulles est l'un des algorithmes les plus couramment utilisés pour trier les données en Java. Le tri ici se fait en comparant récursivement les nombres adjacents et en les décalant dans l'ordre croissant ou décroissant selon les besoins. Ce déplacement des éléments se fait jusqu'à ce que tous les chiffres soient complètement triés dans l'ordre requis.

Le nom «tri à bulles» de cet algorithme est dû au fait que les éléments d'un tableau se frayent un chemin jusqu'au début de celui-ci. 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 organisés dans l'ordre croissant.

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

Itérations

Voici les itérations effectuées dans Bubble Sort en Java, qui est la suivante:

Première itération

(6 1 8 5 3) - Il commence par comparer les deux premiers nombres et décale le plus petit des deux vers la droite. Par conséquent, parmi 6 et 1, 1 est le plus petit nombre est décalé vers la gauche et 6 vers la droite.

(1 6 8 5 3) - Ensuite, il compare les deux nombres adjacents en décalant 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, la 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 a lieu entre les numéros 8 et 3. Le numéro 3 est décalé vers la gauche car il est inférieur à 8.

(1 6 5 3 8) - Il s'agit du résultat final de la commande après la 1ère itération.

Deuxième itération

Étant donné que les nombres ne sont pas encore complètement dans leur ordre croissant, 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 car 1 est inférieur à 6.

(1 6 5 3 8) - Ici, les numéros 5 et 6 sont comparés. Le même ordre est conservé car il est déjà dans l'ordre croissant requis.

(1 5 6 3 8) - Ici, la comparaison a lieu entre les chiffres 6 et 3. Le numéro 3 est décalé vers la gauche car il est plus petit que 6.

(1 5 3 6 8) - Les numéros 6 et 8 suivants sont comparés l'un à l'autre. Le même ordre est conservé car il est dans un ordre attendu.

(1 5 3 6 8) - Il s'agit du résultat final après la deuxième itération. Cependant, nous pouvons remarquer que les chiffres ne sont pas complètement disposés dans leur ordre croissant. Nous devons encore échanger les numéros 5 et 3 pour obtenir le résultat final. Par conséquent, le programme va pour la troisième itération.

Troisième itération

(1 5 3 6 8) - la troisième itération commence en comparant les deux premiers chiffres 1 et 5. Puisque l'ordre est comme prévu, il est conservé de la même manière.

(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 continue pour comparer 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 la comparaison de chaque élément adjacent et constate que tous les chiffres sont dans l'ordre croissant.

Puisqu'il n'y avait ici que 5 éléments d'un tableau qui devaient être triés, cela n'a pris que 3 itérations au total. À mesure que les éléments du tableau augmentent, le nombre d'itérations augmente également.

Implémentation du tri à bulles utilisant Java

Ci-dessous se trouve le code Java qui est l'implémentation de l'algorithme de tri Bubble. (Notez que la première position d'un tableau en Java commence à 0 et se poursuit par incréments de 1, c'est-à-dire tableau (0), tableau (1), tableau (2) et 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 < (ni); 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
)
)
)

Production:

Avantages et inconvénients du Bubble Sort en Java

Voici les différents avantages et inconvénients du tri à bulles en Java:

Les avantages

  1. Le code est très facile à é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, ce qui permet d'économiser beaucoup de mémoire.

Désavantages

  1. Cet algorithme n'est pas adapté aux grands ensembles de données car la comparaison prend beaucoup de temps. Le temps nécessaire pour trier les numéros d'entrée augmente de façon exponentielle.
  2. O (n 2) est la complexité moyenne du tri à bulles et O (n) est la complexité du meilleur 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

Étant donné que le tri à bulles est capable de détecter des erreurs infimes dans le tri, il est utilisé en infographie. Il est également utilisé dans l'algorithme de remplissage de polygone où la doublure des sommets du polygone doit être triée.

Conclusion

Dans cet article, nous avons vu comment fonctionne l'algorithme de tri Bubble 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 algorithme de comparaison et est utilisé par les novices en raison de sa simplicité.

Articles recommandés

Ceci est un guide de Bubble Sort en Java. Ici, nous discutons de plusieurs itérations pour effectuer le tri à bulles en Java et son implémentation de code ainsi que des avantages et des inconvénients. Vous pouvez également consulter les articles suivants pour en savoir plus -

  1. Tri des bulles en JavaScript
  2. Tri en R
  3. Tableaux 3D en Java
  4. Tableaux en C #
  5. Tri des bulles en Python

Catégorie:

Développement de logiciels