Trier la liste chaînée manuelle avec l'algorithme de tri à bulles en Java

1. Tri à bulles en Java
2. Liste chaînée manuelle de tri à bulles en Java
3. Liste chaînée de tri de classe en Java

Le tri à bulles est l’algorithme de structure de données le plus couramment utilisé pour trier la collecte de données. Il fonctionne en itérant et en échangeant les éléments adjacents dans le mauvais ordre jusqu’à ce qu’ils soient corrects.

Nous allons d’abord vous montrer la démo de tri de base. Ensuite, nous implémenterons deux algorithmes de tri à bulles pour trier les listes chaînées en Java.

Tri à bulles en Java

Gardons l’essentiel sans entrer dans l’aspect arithmétique du tri. Nous parcourrons un tableau du début à l’index final dans le tri à bulles.

Alors seulement, il peut comparer l’index actuel à l’index suivant. Le concept de base de cette formule est lorsque les éléments actuels deviennent plus grands en taille que l’élément suivant.

Syntaxe:

for (int A = 0; A < sort - 1; A++)
  for (int B = 0; B < sort - A - 1; B++)
    if (DEMO[B] > DEMO[B + 1]) {
      // Swapping of array
      int temp = DEMO[B];
      DEMO[B] = DEMO[B + 1];
      DEMO[B + 1] = temp;
    }

Exécutons maintenant un simple algorithme de tri à bulles en Java. Mais d’abord, regardez l’état initial des index non triés du tableau.

Tableau : {43, 65, 21, 64, 12, 6, 1}

Le bloc de code suivant effectuera un tri à bulles sur cet index de tableau en appliquant cet algorithme de tri de base.

Il est à noter que nous pouvons toujours modifier cette formule en fonction de nos besoins. Cependant, le noyau doit rester basique pour former la clarté en ce moment.

Code:

// In this program, we will sort an array DEMO using the bubble sort algorithm
// Main class
public class BubbleSortLinkListExample1 {
  // Main function
  private void bubbleSort(int DEMO[]) {
    // Using .length to determine entire length of array's index
    int sort = DEMO.length;
    // If array's length is less than int sort, increase it by 1
    for (int A = 0; A < sort - 1; A++)
      // Formula 1
      for (int B = 0; B < sort - A - 1; B++)
        if (DEMO[B] > DEMO[B + 1]) {
          // Swapping of array
          int temp = DEMO[B];
          DEMO[B] = DEMO[B + 1];
          DEMO[B + 1] = temp;
        }
  }
  /* Now we are going to print DEMO array*/
  void printArray(int DEMO[]) {
    int sort = DEMO.length;
    for (int A = 0; A < sort; ++A) System.out.print(DEMO[A] + " ");
    System.out.println();
  }
  // We are going to implement a driver algorithm for sorting our DEMO array
  public static void main(String args[]) {
    BubbleSortLinkListExample1 ob = new BubbleSortLinkListExample1();
    int DEMO[] = {43, 65, 21, 64, 12, 6, 1};
    ob.bubbleSort(DEMO);
    System.out.println("After the array has been sorted!");
    ob.printArray(DEMO);
  }
}

Après avoir trié ce tableau par ordre croissant, nous obtenons la sortie de Java.

Production:

After the array has been sorted!
1 6 12 21 43 64 65

Liste chaînée manuelle de tri à bulles en Java

Le tri manuel de la liste chaînée est également une méthode simple dans le tri à bulles.

Avons-nous déjà discuté des données de traversée ? Maintenant, nous allons le pratiquer.

Les nœuds nous permettent de parcourir les données d’un nœud à l’autre.

Regardez notre modèle de démonstration ci-dessous. Puisque nous avons effectué un tri dans l’exemple précédent, il est important de mettre l’accent sur les nœuds ici.

Liste chaînée de tri de classe en Java

Comme nous l’avons compris, nous appliquons cette classe pour former des nœuds en Java.

Code:

class SortLL {
  public static class Mynode {
    int indx;
    Mynode fwdMynode;

    public Mynode(int indx) {
      this.indx = indx;
      this.fwdMynode = null;
    }
    public int getindx() {
      return this.indx;
    }
  }

Vous pouvez utiliser ces classes séparément et appeler leurs objets, mais c’est une méthode longue et compliquée. Par conséquent, nous avons conservé toutes les classes dans un seul fichier.

De même, nous utiliserons la fonction .getNextNode(), elle récupère l’élément de classe suivant sans arguments. Vous devez être familiarisé avec le concept, alors exécutons l’algorithme de tri manuel des bulles sans plus tarder.

1. Liste chaînée avant tri :

   

   Code:

   class SortLL {
     public static class Mynode {
       int indx;
       Mynode fwdMynode;
   
       public Mynode(int indx) {
         this.indx = indx;
         this.fwdMynode = null;
       }
       public int getindx() {
         return this.indx;
       }
     }
     // My node class
     private Mynode head;
     private int size;
     public SortLL() {
       this.head = null;
       this.size = 0;
     }
     public void add(int indx) {
       Mynode Mynode = new Mynode(indx);
       if (head == null) {
         head = Mynode;
       } else {
         Mynode CN = head;
         while (CN.fwdMynode != null) {
           CN = CN.fwdMynode;
         }
         CN.fwdMynode = Mynode;
       }
       size++;
     }
     public void sort() {
       if (size > 1) {
         boolean dtr;
         do {
           Mynode thisMynode = head;
           Mynode ladtMynode = null;
           Mynode fwd = head.fwdMynode;
           dtr = false;
   
           while (fwd != null) {
             if (thisMynode.indx > fwd.indx) {
               dtr = true;
               if (ladtMynode != null) {
                 Mynode sig = fwd.fwdMynode;
   
                 ladtMynode.fwdMynode = fwd;
                 fwd.fwdMynode = thisMynode;
                 thisMynode.fwdMynode = sig;
               } else {
                 Mynode sig = fwd.fwdMynode;
                 head = fwd;
                 fwd.fwdMynode = thisMynode;
                 thisMynode.fwdMynode = sig;
               }
               ladtMynode = fwd;
               fwd = thisMynode.fwdMynode;
             } else {
               ladtMynode = thisMynode;
               thisMynode = fwd;
               fwd = fwd.fwdMynode;
             }
           }
         } while (dtr);
       }
     }
     public int listSize() {
       return size;
     }
     public void printindx() {
       Mynode CN = head;
   
       while (CN != null) {
         int indx = CN.getindx();
         System.out.print(indx + " ");
         CN = CN.fwdMynode;
       }
       System.out.println();
     }
     public boolean isEmpty() {
       return size == 0;
     }
   }
   // indxInterface class
   class SrtBubb {
     public static void main(String[] args) {
       SortLL s = new SortLL();
       s.add(12);
       s.add(2);
       s.add(7);
       s.add(19);
       s.add(23);
       s.add(9);
       System.out.println("Before Performing Bubble Sort");
       s.printindx();
       s.sort();
       System.out.println("After Performing Bubble Sort");
       s.printindx();
       System.out.println("Size of the linked list is: " + s.listSize());
     }
   }
   

2. Après avoir effectué le tri à bulles manuel :

   

   Production:

   Before Performing Bubble Sort
   12 2 7 19 23 9
   After Performing Bubble Sort
   2 7 9 12 19 23
   Size of the linked list is: 6
   

Vous pouvez modifier ce programme en fonction de vos besoins. Mais c’est la méthode la plus pratique pour les débutants pour comprendre le tri manuel des listes chaînées à l’aide du tri à bulles.

Supposons que vous soyez toujours confus à propos de ce sujet. Nous avons également fourni le code dans le répertoire de fichiers pour vous.