Manuell verknüpfte Liste mit Bubble-Sort-Algorithmus in Java sortieren

1. Blasensortierung in Java
2. Bubble Sort Manual Linked List in Java
3. Klassensortierte verkettete Liste in Java

Bubble Sort ist der gebräuchlichste Datenstrukturalgorithmus, der zum Sortieren der Datensammlung verwendet wird. Es funktioniert durch Iterieren und Vertauschen der benachbarten Elemente in der falschen Reihenfolge, bis sie korrekt sind.

Wir zeigen Ihnen zunächst die grundlegende Sortierdemo. Dann werden wir zwei Bubble-Sort-Algorithmen implementieren, um verknüpfte Listen in Java zu sortieren.

Blasensortierung in Java

Lassen Sie uns die Dinge wesentlich halten, ohne in den arithmetischen Aspekt des Sortierens einzusteigen. Wir werden ein Array vom Anfang bis zum letzten Index in der Blasensortierung durchlaufen.

Nur dann kann es den aktuellen Index mit dem folgenden Index vergleichen. Das Kernkonzept dieser Formel ist, wenn die vorhandenen Elemente größer werden als das nächste Element.

Syntax:

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;
    }

Lassen Sie uns nun einen einfachen Bubble-Sort-Algorithmus in Java ausführen. Aber schauen Sie sich zuerst den Anfangszustand der unsortierten Indizes des Arrays an.

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

Der folgende Codeblock führt eine Blasensortierung für diesen Array-Index durch, indem er diesen grundlegenden Sortieralgorithmus anwendet.

Es ist erwähnenswert, dass wir diese Formel je nach unseren Anforderungen jederzeit ändern können. Der Kern sollte jedoch grundlegend bleiben, um in diesem Moment Klarheit zu schaffen.

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);
  }
}

Nachdem wir dieses Array in aufsteigender Reihenfolge sortiert haben, erhalten wir die Ausgabe von Java.

Ausgabe:

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

Bubble Sort Manual Linked List in Java

Die manuelle Sortierung mit verknüpften Listen ist auch eine einfache Methode in Bubble Sort.

Haben wir zuvor über das Durchlaufen von Daten gesprochen? Jetzt werden wir es üben.

Knoten ermöglichen es uns, Daten von einem Knoten zum nächsten zu übertragen.

Sehen Sie sich unten unser Demomodell an. Da wir im vorherigen Beispiel eine Sortierung durchgeführt haben, ist es wichtig, hier Knoten hervorzuheben.

Klassensortierte verkettete Liste in Java

Wie wir verstanden haben, wenden wir diese Klasse an, um Knoten in Java zu bilden.

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;
    }
  }

Sie können diese Klassen separat verwenden und ihre Objekte aufrufen, aber das ist ein langwieriger und komplizierter Weg. Daher haben wir alle Klassen in einer Datei gespeichert.

Ebenso verwenden wir die Funktion .getNextNode(), sie ruft das nächste Klassenelement ohne Argumente ab. Sie müssen mit dem Konzept vertraut sein, also führen wir den manuellen Bubble-Sort-Algorithmus ohne weiteres aus.

1. Verkettete Liste vor dem Sortieren:

   

   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. Nach Durchführung der manuellen Blasensortierung:

   

   Ausgabe:

   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
   

Sie können dieses Programm Ihren Anforderungen entsprechend modifizieren. Dies ist jedoch die praktischste Methode für Anfänger, um das manuelle Sortieren von verknüpften Listen mit Bubble Sort zu verstehen.

Angenommen, Sie sind immer noch verwirrt über dieses Thema. Auch den Code haben wir im Dateiverzeichnis für Sie bereitgestellt.