Implementierung der Blasensortierung in Java

Es gibt eine ganze Reihe von Sortieralgorithmen, viele davon sind sehr spezifisch und wurden entwickelt, um eine begrenzte Anzahl von Problemen zu lösen und mit bestimmten Datentypen zu arbeiten. Aber bei all dieser Vielfalt ist der einfachste Algorithmus zu Recht die Blasensortierung, die in jeder Programmiersprache implementiert werden kann. Trotz seiner Einfachheit liegt es vielen recht komplexen Algorithmen zugrunde. Ein weiterer ebenso wichtiger Vorteil ist seine Einfachheit und kann daher sofort im Gedächtnis behalten und umgesetzt werden, ohne dass Sie zusätzliche Literatur vor sich haben.

Einführung

Das gesamte moderne Internet besteht aus einer Vielzahl unterschiedlicher Datenstrukturen, die in Datenbanken gesammelt werden. Sie speichern alle Arten von Informationen, von persönlichen Daten der Benutzer bis hin zum semantischen Kern hochintelligenter automatisierter Systeme. Es versteht sich von selbst, dass die Datensortierung bei dieser riesigen Menge an strukturierten Informationen eine äußerst wichtige Rolle spielt. Das Sortieren kann ein obligatorischer Schritt vor der Suche nach Informationen in der Datenbank sein, und Kenntnisse über Sortieralgorithmen spielen bei der Programmierung eine sehr wichtige Rolle.

Sortieren durch Maschinenaugen und menschliche Augen

Stellen wir uns vor, Sie müssen 5 Spalten unterschiedlicher Höhe in aufsteigender Reihenfolge sortieren. Diese Spalten können jede Art von Information bedeuten (Aktienkurse, Bandbreite des Kommunikationskanals usw.); Sie können einige Ihrer eigenen Versionen dieser Aufgabe präsentieren, um sie klarer zu machen. Als Beispiel sortieren wir die Avengers nach Größe: Im Gegensatz zu einem Computerprogramm wird Ihnen das Sortieren nicht schwer fallen, da Sie das Gesamtbild sehen und sofort erkennen können, welcher Held wohin verschoben werden muss, damit die Sortierung nach Höhe erfolgreich abgeschlossen werden kann. Sie haben wahrscheinlich schon vermutet, dass es ausreicht, die Plätze von Hulk und Iron Man zu tauschen, um diese Datenstruktur in aufsteigender Reihenfolge zu sortieren:

Erledigt!

Damit ist die Sortierung erfolgreich abgeschlossen. Allerdings ist der Computer im Gegensatz zu Ihnen etwas dumm und sieht nicht die gesamte Datenstruktur als Ganzes. Sein Steuerprogramm kann jeweils nur zwei Werte vergleichen. Um dieses Problem zu lösen, muss sie zwei Zahlen in ihrem Gedächtnis ablegen und einen Vergleichsvorgang mit ihnen durchführen, dann zu einem anderen Zahlenpaar übergehen und so weiter, bis alle Daten analysiert sind. Daher kann jeder Sortieralgorithmus in Form von drei Schritten stark vereinfacht werden:

• Vergleichen Sie zwei Elemente;
• Tauschen oder kopieren Sie einen davon;
• Gehe zum nächsten Element;

Verschiedene Algorithmen können diese Operationen auf unterschiedliche Weise ausführen, aber wir werden uns nun mit der Funktionsweise der Blasensortierung befassen.

Blasensortierungsalgorithmus

Die Blasensortierung gilt als die einfachste, aber bevor wir diesen Algorithmus beschreiben, stellen wir uns vor, wie Sie die Avengers nach Größe sortieren würden, wenn Sie wie eine Maschine nur zwei Helden in einem Zeitraum miteinander vergleichen könnten. Höchstwahrscheinlich würden Sie Folgendes tun (am optimalsten):

• Sie bewegen sich zum Element Null unseres Arrays (Black Widow);
• Vergleichen Sie das Nullelement (Black Widow) mit dem ersten (Hulk);
• Wenn das Element an Position Null höher ist, tauschen Sie es aus;
• Andernfalls, wenn das Element an der Position Null kleiner ist, belassen Sie sie an ihrer Stelle;
• Gehen Sie zu einer Position nach rechts und wiederholen Sie den Vergleich (vergleichen Sie den Hulk mit dem Captain).

Nachdem Sie mit einem solchen Algorithmus die gesamte Liste in einem Durchgang durchgegangen sind, ist die Sortierung nicht vollständig abgeschlossen. Andererseits wird das größte Element in der Liste ganz nach rechts verschoben. Dies wird immer passieren, denn sobald Sie das größte Element gefunden haben, wechseln Sie ständig die Plätze, bis Sie es ganz ans Ende verschieben. Das heißt, sobald das Programm den Hulk im Array „findet“, verschiebt es ihn weiter ans Ende der Liste: Aus diesem Grund wird dieser Algorithmus als Blasensortierung bezeichnet, da aufgrund seiner Operation das größte Element in der Liste ganz oben im Array steht und alle kleineren Elemente um eine Position nach links verschoben werden: Um die Sortierung abzuschließen, müssen Sie zum Anfang des Arrays zurückkehren und die oben beschriebenen fünf Schritte noch einmal wiederholen, wobei Sie sich erneut von links nach rechts bewegen und die Elemente nach Bedarf vergleichen und verschieben. Dieses Mal müssen Sie den Algorithmus jedoch ein Element vor dem Ende des Arrays stoppen, da wir bereits wissen, dass sich das größte Element (Hulk) absolut an der äußersten rechten Position befindet: Das Programm muss also zwei Schleifen haben. Zur besseren Übersicht können Sie, bevor wir mit der Überprüfung des Programmcodes fortfahren, unter diesem Link eine Visualisierung der Funktionsweise der Blasensortierung sehen: Visualisierung der Funktionsweise der Blasensortierung

Implementierung der Blasensortierung in Java

Um zu demonstrieren, wie das Sortieren in Java funktioniert, hier der Programmcode:

• erstellt ein Array aus 5 Elementen;
• lädt den Aufstieg der Rächer hinein;
• zeigt den Inhalt des Arrays an;
• implementiert Blasensortierung;
• Zeigt das sortierte Array erneut an.

Sie können den Code unten ansehen und ihn sogar in Ihre bevorzugte IntelliJ- IDE herunterladen. Es wird im Folgenden analysiert:

class ArrayBubble{
    private long[] a;   // Array-Referenz
    private int elems;  //Anzahl der Elemente im Array

    public ArrayBubble(int max){    //Klassenkonstruktor
        a = new long[max];          //Erstelle ein Array mit der Größe max
        elems = 0;                  //Beim Erstellen enthält das Array 0 Elemente
    }

    public void into(long value){   // Methode zum Einfügen eines Elements in ein Array
        a[elems] = value;           //Wert in Array a einfügen
        elems++;                    //Arraygröße erhöht sich
    }

    public void printer(){          // Methode zur Ausgabe eines Arrays an die Konsole
        for (int i = 0; i < elems; i++){    //für jedes Element im Array
            System.out.print(a[i] + " ");   // Ausgabe an die Konsole
            System.out.println("");         //eine neue Zeile
        }
        System.out.println(„----Array-Ausgabe beenden----“);
    }

    private void toSwap(int first, int second){ //Methode vertauscht ein Array-Nummernpaar
        long dummy = a[first];      // das erste Element in eine temporäre Variable einfügen
        a[first] = a[second];       // das zweite Element anstelle des ersten einfügen
        a[second] = dummy;          //anstelle des zweiten Elements das erste aus dem temporären Speicher schreiben
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Äußere Schleife
            for (int in = 0; in < out; in++){       //Innere Schleife
                if(a[in] > a[in + 1])               //Wenn die Reihenfolge der Elemente falsch ist
                    toSwap(in, in + 1);             // die Swapping-Methode aufrufen
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Array mit 5 Elementen erstellen

        array.into(163);       //Füllen Sie das Array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //Elemente vor dem Sortieren anzeigen
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // die sortierte Liste erneut drucken
    }
}

Trotz der detaillierten Kommentare im Code bieten wir eine Beschreibung einiger der im Programm vorgestellten Methoden. Die Schlüsselmethoden, die die Hauptarbeit im Programm ausführen, sind in der Klasse ArrayBubble geschrieben. Die Klasse enthält einen Konstruktor und mehrere Methoden:

• into– Methode zum Einfügen von Elementen in ein Array;
• printer– zeigt den Inhalt des Arrays Zeile für Zeile an;

• toSwap– Ordnet Elemente bei Bedarf neu an. Dazu wird eine temporäre Variable verwendet dummy, in die der Wert der ersten Zahl geschrieben wird und anstelle der ersten Zahl der Wert der zweiten Zahl geschrieben wird. Der Inhalt der temporären Variablen wird dann in die zweite Zahl geschrieben. Dies ist eine Standardtechnik zum Austauschen zweier Elemente.

  und schließlich die Hauptmethode:

• bubbleSorter– welches die Hauptarbeit erledigt und die im Array gespeicherten Daten sortiert, wir stellen es noch einmal separat vor:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Äußere Schleife
          for (int in = 0; in < out; in++){       //Innere Schleife
              if(a[in] > a[in + 1])               //Wenn die Reihenfolge der Elemente falsch ist
                  toSwap(in, in + 1);             // die Swapping-Methode aufrufen
          }
      }
  }

Hier sollten Sie auf zwei Zähler achten: extern outund intern in. Der externe Zählerout beginnt mit der Aufzählung der Werte am Ende des Arrays und verringert sich bei jedem neuen Durchgang schrittweise um eins. outBei jedem neuen Durchlauf wird die Variable weiter nach links verschoben, um die bereits auf der rechten Seite des Arrays sortierten Werte nicht zu beeinträchtigen. Der interne Zählerin beginnt mit der Aufzählung der Werte vom Anfang des Arrays und erhöht sich bei jedem neuen Durchgang schrittweise um eins. Die Erhöhung erfolgt, bis sie (das letzte analysierte Element im aktuellen Durchgang) inerreicht . outDie innere Schleife invergleicht zwei benachbarte Zellen inund in+1. Wenn ineine größere Zahl gespeichert ist als in+1, dann wird die Methode aufgerufen toSwap, die die Stellen dieser beiden Zahlen vertauscht.

Abschluss

Der Blasensortierungsalgorithmus ist einer der langsamsten. Wenn das Array aus N Elementen besteht, werden beim ersten Durchgang N-1 Vergleiche durchgeführt, beim zweiten N-2, dann N-3 usw. Das heißt, die Gesamtzahl der Durchgänge wird wie folgt durchgeführt: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Somit gilt beim Sortieren der Algorithmus führt etwa 0,5x(N ^2)-Vergleiche durch. Für N = 5 beträgt die Anzahl der Vergleiche etwa 10, für N = 10 erhöht sich die Anzahl der Vergleiche auf 45. Mit zunehmender Anzahl der Elemente nimmt also die Komplexität der Sortierung deutlich zu: Die Geschwindigkeit des Algorithmus wird nicht nur von der Anzahl der Durchläufe beeinflusst, sondern auch von der Anzahl der durchzuführenden Permutationen. Bei Zufallsdaten beträgt die durchschnittliche Anzahl der Permutationen (N^2) / 4, was etwa halb so viel ist wie die Anzahl der Durchgänge. Im schlimmsten Fall kann die Anzahl der Permutationen jedoch auch N^2 / 2 betragen – dies ist dann der Fall, wenn die Daten zunächst in umgekehrter Reihenfolge sortiert werden. Obwohl es sich um einen eher langsamen Sortieralgorithmus handelt, ist es sehr wichtig, seine Funktionsweise zu kennen und zu verstehen, und wie bereits erwähnt, ist er die Grundlage für komplexere Algorithmen. Jgd!