Implémentation du tri à bulles en Java

Il existe un assez grand nombre d'algorithmes de tri, dont beaucoup sont très spécifiques et ont été développés pour résoudre un éventail restreint de problèmes et travailler avec des types de données spécifiques. Mais parmi toute cette diversité, l’algorithme le plus simple est à juste titre le tri à bulles, qui peut être implémenté dans n’importe quel langage de programmation. Malgré sa simplicité, il sous-tend de nombreux algorithmes plutôt complexes. Un autre avantage tout aussi important est sa simplicité et, par conséquent, il peut être mémorisé et mis en œuvre immédiatement, sans avoir de documentation supplémentaire sous les yeux.

Introduction

L'ensemble de l'Internet moderne se compose d'un grand nombre de types différents de structures de données collectées dans des bases de données. Ils stockent toutes sortes d'informations, depuis les données personnelles des utilisateurs jusqu'au noyau sémantique des systèmes automatisés hautement intelligents. Il va sans dire que le tri des données joue un rôle extrêmement important dans cette énorme quantité d’informations structurées. Le tri peut être une étape obligatoire avant de rechercher une information dans la base de données, et la connaissance des algorithmes de tri joue un rôle très important en programmation.

Trier les yeux des machines et les yeux humains

Imaginons que vous deviez trier 5 colonnes de hauteurs différentes par ordre croissant. Ces colonnes peuvent contenir tout type d'informations (cours des actions, bande passante du canal de communication, etc.) ; vous pouvez présenter certaines de vos propres versions de cette tâche pour la rendre plus claire. Eh bien, à titre d'exemple, nous allons trier les Avengers par hauteur : Contrairement à un programme informatique, le tri ne sera pas difficile pour vous, car vous êtes capable de voir l'ensemble du tableau et de déterminer immédiatement quel héros doit être déplacé où pour que le tri par hauteur soit effectué avec succès. Vous avez probablement déjà deviné que pour trier cette structure de données par ordre croissant, il suffit d'intervertir les places de Hulk et d'Iron Man :

Fait!

Et cela terminera le tri avec succès. Cependant, l'ordinateur, contrairement à vous, est quelque peu stupide et ne voit pas l'ensemble de la structure des données dans son ensemble. Son programme de contrôle ne peut comparer que deux valeurs à la fois. Pour résoudre ce problème, elle devra placer deux nombres dans sa mémoire et effectuer une opération de comparaison sur ceux-ci, puis passer à une autre paire de nombres, et ainsi de suite jusqu'à ce que toutes les données aient été analysées. Ainsi, tout algorithme de tri peut être très simplifié sous la forme de trois étapes :

• Comparez deux éléments ;
• Échangez ou copiez l'un d'entre eux ;
• Passez à l'élément suivant ;

Différents algorithmes peuvent effectuer ces opérations de différentes manières, mais nous allons maintenant examiner le fonctionnement du tri à bulles.

Algorithme de tri à bulles

Le tri des bulles est considéré comme le plus simple, mais avant de décrire cet algorithme, imaginons comment vous trieriez les Avengers par hauteur si vous pouviez, comme une machine, comparer seulement deux héros entre eux sur une période de temps. Très probablement, vous feriez ce qui suit (de la manière la plus optimale) :

• Vous passez à l'élément zéro de notre tableau (Black Widow) ;
• Comparez l'élément zéro (Black Widow) avec le premier (Hulk) ;
• Si l'élément en position zéro est plus haut, vous les échangez ;
• Sinon, si l'élément en position zéro est plus petit, vous les laissez à leur place ;
• Déplacez-vous vers la droite et répétez la comparaison (comparez Hulk avec le capitaine)

Après avoir parcouru toute la liste en un seul passage avec un tel algorithme, le tri ne sera pas complètement terminé. Mais d’un autre côté, l’élément le plus grand de la liste sera déplacé à l’extrême droite. Cela se produira toujours, car dès que vous trouverez le plus grand élément, vous changerez constamment de place jusqu'à ce que vous le déplaciez jusqu'au bout. Autrement dit, dès que le programme « trouvera » Hulk dans le tableau, il le déplacera plus loin à la toute fin de la liste : C'est pourquoi cet algorithme est appelé tri à bulles, car à la suite de son fonctionnement, le plus grand élément de la liste sera tout en haut du tableau et tous les éléments plus petits seront décalés d'une position vers la gauche : Pour terminer le tri, vous devrez revenir au début du tableau et répéter à nouveau les cinq étapes décrites ci-dessus, en vous déplaçant à nouveau de gauche à droite, en comparant et en déplaçant les éléments si nécessaire. Mais cette fois, vous devez arrêter l'algorithme un élément avant la fin du tableau, car nous savons déjà que le plus grand élément (Hulk) est absolument à l'extrême droite : Le programme doit donc avoir deux boucles. Pour plus de clarté, avant de passer à la révision du code du programme, vous pouvez voir une visualisation du fonctionnement du tri à bulles sur ce lien : Visualisation du fonctionnement du tri à bulles

Implémentation du tri à bulles en Java

Pour démontrer comment fonctionne le tri en Java, voici le code du programme :

• crée un tableau de 5 éléments ;
• y télécharge la montée des vengeurs ;
• affiche le contenu du tableau ;
• implémente le tri à bulles ;
• réaffiche le tableau trié.

Vous pouvez consulter le code ci-dessous et même le télécharger dans votre IDE IntelliJ préféré . Il sera analysé ci-dessous :

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

Malgré les commentaires détaillés dans le code, nous fournissons une description de certaines des méthodes présentées dans le programme. Les méthodes clés qui effectuent le travail principal du programme sont écrites dans la classe ArrayBubble. La classe contient un constructeur et plusieurs méthodes :

• into– méthode d'insertion d'éléments dans un tableau ;
• printer– affiche le contenu du tableau ligne par ligne ;

• toSwap– réorganise les éléments si nécessaire. Pour ce faire, une variable temporaire est utilisée dummydans laquelle la valeur du premier nombre est écrite, et à la place du premier nombre la valeur du deuxième nombre est écrite. Le contenu de la variable temporaire est ensuite écrit dans le deuxième nombre. Il s'agit d'une technique standard pour échanger deux éléments ;

  et enfin la méthode principale :

• bubbleSorter– qui fait le travail principal et trie les données stockées dans le tableau, nous le présenterons à nouveau séparément :

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

Ici, vous devez faire attention à deux compteurs : externe outet interne in. Le compteur externeout commence à énumérer les valeurs à partir de la fin du tableau et diminue progressivement de un à chaque nouveau passage. outA chaque nouveau passage, la variable est décalée davantage vers la gauche afin de ne pas affecter les valeurs déjà triées sur le côté droit du tableau. Le compteur internein commence à énumérer les valeurs depuis le début du tableau et augmente progressivement de un à chaque nouveau passage. L'augmentation inse produit jusqu'à ce qu'elle atteigne out(le dernier élément analysé dans la passe en cours). La boucle interne incompare deux cellules adjacentes inet in+1. Si inun nombre supérieur à in+1, alors la méthode est appelée toSwap, qui échange les places de ces deux nombres.

Conclusion

L'algorithme de tri à bulles est l'un des plus lents. Si le tableau est constitué de N éléments, alors N-1 comparaisons seront effectuées au premier passage, N-2 au second, puis N-3, etc. C'est-à-dire que le nombre total de passes sera effectué : (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Ainsi, lors du tri, l'algorithme effectue environ 0,5x(N ^2) comparaisons. Pour N = 5, le nombre de comparaisons sera d'environ 10, pour N = 10 le nombre de comparaisons passera à 45. Ainsi, à mesure que le nombre d'éléments augmente, la complexité du tri augmente considérablement : La vitesse de l’algorithme dépend non seulement du nombre de passes, mais également du nombre de permutations à effectuer. Pour les données aléatoires, le nombre de permutations est en moyenne de (N ^ 2) / 4, soit environ la moitié du nombre de passes. Cependant, dans le pire des cas, le nombre de permutations peut également être N^2/2 - c'est le cas si les données sont initialement triées dans l'ordre inverse. Bien qu'il s'agisse d'un algorithme de tri plutôt lent, il est très important de connaître et de comprendre son fonctionnement et, comme mentionné précédemment, il constitue la base d'algorithmes plus complexes. Bon Dieu !