Tri à bulles Java

Si vous avez déjà entendu parler des méthodes de tri en programmation, il s'agit très probablement de l'algorithme de tri à bulles. C'est un célèbre. Chaque programmeur connaît le tri à bulles (ou du moins en a entendu parler en apprenant) non pas parce que c'est le meilleur algorithme de tri au monde, mais le plus simple. Cet algorithme est généralement utilisé à des fins d'apprentissage ou vous pouvez l'obtenir en tant que tâche dans votre entretien Java Junior. L'algorithme de tri Java Bubble est très facile à comprendre, mais il n'est pas efficace. Quoi qu'il en soit, découvrons-le.

Qu'est-ce que le tri

Tout d'abord, vous devez comprendre ce qu'est le tri en général et ce que nous pouvons trier dans les programmes Java. Si nous pouvons comparer deux ou plusieurs éléments ou objets par l'un de leurs attributs, cela signifie qu'ils peuvent être triés par cet attribut. Par exemple, des nombres dans l'ordre croissant ou décroissant ou des mots dans l'ordre alphabétique. Par conséquent, les éléments doivent être comparables entre eux. Au fait, les éléments de quoi ? En Java, nous pouvons comparer les éléments de Collections. Par exemple, nous pouvons trier Array ou ArrayList d'entiers, de chaînes, etc.

Comment fonctionne le tri à bulles

Disons que nous devons trier un tableau d'entiers par ordre croissant, c'est-à-dire du plus petit au plus grand nombre. Tout d'abord, nous parcourons tout le tableau et comparons tous les 2 éléments voisins. S'ils sont dans le mauvais ordre (le voisin de gauche est plus gros que celui de droite), on les échange. Au premier passage à la fin, il apparaîtra le plus grand élément (si nous trions par ordre croissant). Vous pouvez dire que le plus gros élément "apparaît". C'est la raison du nom de l'algorithme de tri Bubble. Nous répétons la première étape du premier à l'avant-dernier élément. Nous avons le deuxième élément le plus important à l'avant-dernière place. Et ainsi de suite. Nous pouvons améliorer un peu un algorithme en vérifiant si au moins un échange à l'étape précédente a été effectué. Si ce n'est pas le cas, nous arrêtons de courir le long du tableau.

Exemple de tri à bulles

Trions le tableau d'entiers, celui que vous pouvez voir ci-dessous sur une image. Étape 1 : nous parcourons le tableau. L'algorithme commence par les deux premiers éléments (avec les indices 0 et 1), 8 et 7, et vérifie s'ils sont dans le bon ordre. Evidemment, 8 > 7, donc on les échange. Ensuite, nous regardons les deuxième et troisième éléments (indices 1 et 2), maintenant ce sont 8 et 1. Pour les mêmes raisons, nous les intervertissons. Pour la troisième fois nous comparons 8 et 2 et, au moins 8 et 5. Nous avons fait quatre échanges au total : (8, 7), (8, 1), (8, 2) et (8, 5). Une valeur de 8, la plus grande de ce tableau, est apparue à la fin de la liste à la bonne position. Le résultat de la première étape du fonctionnement de l'algorithme de tri à bulles est le tableau suivant : Étape 2. Faites de même avec (7,1), (7,2) et (7,5). 7 est maintenant en avant-dernière position, et nous n'avons pas besoin de le comparer avec la "queue" de la liste, il est déjà trié. Le résultat de la deuxième étape du fonctionnement de l'algorithme de tri à bulles est le tableau suivant : comme vous pouvez le voir, ce tableau est déjà trié. Quoi qu'il en soit, l'algorithme Bubble Sort devrait fonctionner au moins une fois de plus. Étape 3. Nous parcourons le tableau une fois de plus. Rien à échanger ici, donc si nous utilisons l'algorithme "amélioré" de Bubble Sort (avec vérification si au moins un échange à l'étape précédente a été effectué), cette étape est la dernière.

Code Java de tri à bulles

Réalisation Java du tri à bulles

Créons deux méthodes pour le tri à bulles. Le premier, bubbleSort(int[] myArray) est un plan. Il parcourt le tableau à chaque fois. Le second, optimiséBubbleSort(int myArray[]) est optimisé en arrêtant l'algorithme si la boucle interne n'a pas provoqué d'échange. Le compteur vous indique le nombre d'étapes que vous avez effectuées lors du tri. Ici, nous avons la réalisation Java du tri Bubble :

import java.util.Arrays;

public class BubbleSortExample {

   //  Plane Bubble sort example

   public static int[] bubbleSort(int[] myArray) {

       int temp = 0;  //  temporary element for swapping
       int counter = 0;  //  element to count quantity of steps

       for (int i = 0; i < myArray.length; i++) {
           counter = i + 1;
           for (int j = 1; j < (myArray.length - i); j++) {

               if (myArray[j - 1] > myArray[j]) {
                   //  swap array’s elements using temporary element
                   temp = myArray[j - 1];
                   myArray[j - 1] = myArray[j];
                   myArray[j] = temp;
               }
           }
       }
       System.out.println("Steps quantity, non optimized = " + counter);
       return myArray;
   }
   //  An optimized version of Java Bubble Sorting

   static int[] optimizedBubbleSort(int myArray[]) {
       int temp;
       boolean swapped;
       int counter = 0;  //  element to count quantity of steps
       for (int i = 0; i < myArray.length - 1; i++) {
           counter = i + 1;
           swapped = false;
           for (int j = 0; j < myArray.length - i - 1; j++) {
               //  counter++;
               if (myArray[j] > myArray[j + 1]) {
                   //  swap arr[j] and arr[j+1]
                   temp = myArray[j];
                   myArray[j] = myArray[j + 1];
                   myArray[j + 1] = temp;
                   swapped = true;

               }
           }  //  counter = i;
           //  If there weren't elements to swap in inner loop, then break
           if (swapped == false) {

               break;

           }
       }
       System.out.println("steps quantity, optimized = " + counter);
       return myArray;
   }


   public static void main(String[] args) {
       int arr[] = {8, 7, 1, 2, 5};
       int arr1[] = {8, 7, 1, 2, 5};

       System.out.println("Array arr Before Bubble Sort");
       //  we use java.util.Arrays toString method to print the array
 System.out.println(Arrays.toString(arr));

       System.out.println("Array arr After Bubble Sort");
       System.out.println(Arrays.toString(bubbleSort(arr)));

       System.out.println("Array arr1 Before Bubble Sort");
       System.out.println(Arrays.toString(arr1));

       System.out.println("Array arr1 After Optimized Bubble Sort");
       System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
   }
}

Le résultat du travail de l'algorithme Java Bubble sort:

Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]

Quelle est l'efficacité du tri à bulles ?

Le tri à bulles est l'un des algorithmes les plus faciles à implémenter mais il n'est pas efficace. Il nécessite une paire de boucles imbriquées. Même dans une version optimisée de l'algorithme dans le pire des cas (chaque élément de l'ensemble de données est dans l'ordre inverse de celui souhaité), la boucle externe itère une fois pour chacun des n éléments de l'ensemble de données. La boucle interne itère n fois pour la première fois, ( n-1 ) pour la seconde, et ainsi de suite. Par conséquent, pour obtenir tous les n , éléments triés, les boucles doivent être exécutées n*(n-1)/2 fois. Il s'appelle O(n ² )complexité temporelle et signifie que l'algorithme effectue environ 500 000 comparaisons pour 1000 éléments d'un tableau. Cependant, l'algorithme de tri à bulles est assez efficace dans l'utilisation de la mémoire (la complexité de la mémoire est O(n) ) et est vraiment bon pour les petits ensembles de données presque triés.