Bubble sort – Blasen-Sortierung in Java

Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung von Daten ist sehr wichtig für die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten benötigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus hängt von Faktoren wie der Größe und den Eigenschaften der Eingabedaten, dem verfügbaren Speicher und den Zeit- und Platzanforderungen ab. Um Ihnen die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erklären und sie in Java programmieren. Heute befassen wir uns mit Bubble Sort.

Algorithmus für Bubble sort

Bubble Sort ist ein Sortieralgorithmus, der nacheinander jeweils zwei benachbarte Elemente vergleicht und sie verwirft, bis sie in der gewünschten Reihenfolge sortiert sind. Der Algorithmus erfordert mehrere Iterationen. Der Name des Algorithmus ist von den Luftblasen abgeleitet, die im Wasser an die Oberfläche steigen. Analog dazu steigen bei diesem Algorithmus die Elemente des Arrays bei jeder Iteration bis zum Ende des unsortierten Teils des Arrays auf.

Bubble Sort Algorithmus – Funktionsprinzip

Angenommen, wir möchten die Elemente in aufsteigender Reihenfolge sortieren. Wenn ein Array nur ein Element hat, gilt es als sortiert, andernfalls müssen die Elemente sortiert werden.

Erste Iteration:

Alle zwei benachbarten Array-Elemente werden der Reihe nach vom Anfang des Arrays an verglichen. Wenn das erste Element größer ist als das zweite, tauschen sie die Reihenfolge. Dann wird das zweite Element mit dem dritten verglichen, das dritte mit dem vierten, und so weiter. Die erste Iteration endet mit dem Vergleich der letzten benachbarten Elemente. Während der ersten Iteration wird durch das Vertauschen der Elemente garantiert, dass das größte Element des Arrays an das Ende des Arrays gebracht wird.

Andere Iterationen:

Der letzte Index des Arrays wird als sortiert betrachtet, der Rest des Arrays ist noch nicht sortiert. Für den unsortierten Teil des Arrays wird das Verfahren aus der ersten Iteration wiederholt. Bei jeder Iteration wird das größte Element an das Ende des unsortierten Arrays vorgeblasen. Dies wird so lange wiederholt, bis das Array sortiert ist.

Anzahl der Iterationen: n-1
Anzahl der Vergleiche: n*(n-1)/2

Beispiel

Wir haben das folgende Array mit den Elementen [3][1][2]. Aus den Formeln berechnen wir, dass die Anzahl der benötigten Iterationen 2 und die Anzahl der Vergleiche 6 beträgt.> In der ersten Iteration finden die folgenden Operationen statt: [1][3][2] – [1][2][3]. Das größte Element 3 wird auf den letzten Index des Arrays abgebildet. Obwohl das Array bereits sortiert ist, wird eine zweite Iteration durchgeführt, bei der die ersten beiden Elemente des Arrays verglichen werden. Da das erste und das zweite Element die richtige Reihenfolge haben, wird ihre Reihenfolge nicht vertauscht.

Optimierung des Bubble Sort Algorithmus

Im obigen Beispiel haben wir gesehen, dass, wenn wir das Array bereits sortiert haben, dennoch unnötigerweise zusätzliche Iterationen und Vergleiche durchgeführt werden. Das erhöht natürlich die Laufzeit des Algorithmus. Die Lösung besteht darin, dass wir bei jeder Iteration feststellen, ob es eine Neuordnung zweier Elemente gibt. Wenn nicht, betrachten wir das Array als sortiert und führen keine weiteren Iterationen durch. Diese Optimierung reduziert die Zeitkomplexität für ein bereits sortiertes Array und gewährleistet die Anpassungsfähigkeit des Algorithmus.

Vorteile des Bubble-Sortieralgorithmus

• Es ist leicht zu verstehen und umzusetzen
• Benötigt beim Sortieren keinen zusätzlichen Speicherplatz
• Es ist stabil, d.h. zwei identische Elemente aus der Eingabe behalten ihre relative Reihenfolge im Ergebnis bei

Nachteil des Bubble-Sortieralgorithmus

• Die Zeitkomplexität ist O(n²), was ihn zu einem langsamen Algorithmus für einen großen Datensatz macht.

Zeitaufwand für Bubble sort

Bubble sort Animation, Visualisierung, gif

Die Visualisierung des Bubble-Sortieralgorithmus sieht folgendermaßen aus:

Quelle: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

Eine Animation des Algorithmus finden Sie zum Beispiel unter Toptal. Es gibt 8 Arten von Algorithmen, Sie können die Animation auch rückwärts abspielen. Auf dieser Seite können Sie die einzelnen Schritte des Algorithmus durchlaufen, so dass Sie den Zeitverbrauch des Algorithmus überprüfen können.

Bubble Sort Implementierung – Beispiel in Java

Lassen Sie uns eine optimierte Version von Bubble Sort in Java programmieren.

BubbleSort.java

package sorting;

// An optimized version of Bubble Sort
public class BubbleSort {
    private boolean change;
    private int temp;

    public void sort(int data[])
    {
        for (int i = 0; i < data.length - 1; i++) {
            System.out.println(i + 1 + ". iteration");
            change = false;
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j] > data[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    change = true;
                    printArray(data);
                }
            }
            // If no two elements swapped, then end the sort method
            if (!change)
                return;
        }
    }

    // Function to print an array
    public void printArray(int data[])
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
        System.out.println();
    }
}

Main.java

import sorting.BubbleSort;

public class Main {
    public static void main(String[] args) {
        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
        BubbleSort bubbleSort = new BubbleSort();
        System.out.print("Input: ");
        bubbleSort.printArray(dataToSort);
        bubbleSort.sort(dataToSort);
        System.out.print("Sorted: ");
        bubbleSort.printArray(dataToSort);
    }
}

Die Ausgabe dieses Beispiels ist:

Wir haben die Dateien mit dem oben genannten Beispiel in Form von Code vorbereitet, den Sie direkt in Java ausführen können. Lade den Bubble Sort-Code in Java hier herunter.

Wenn du ein Java Programmierer bist und nach Arbeit suchst, schau dir unsere Mitareiterbenefits an und reagiere auf die neuesten Stellenangebote.

Über den Autor

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.