Bubblesort-Algorithmus in Java erklärt!

Der Bubblesort ist eine sehr simpler Sortieralgorithmus, gerade in Lehranstalten wie Uni und Berufsschule wird dieser immer wieder gerne als Beispiel genommen um zu demonstrieren, wie Suchalgorithmen funktionieren.

Der Bubblesort-Algorithmus erwartet eine Liste von Zahlen, diese Zahlen werden dann aufsteigende sortiert. Die Sortierung basiert immer auf einem Wertepaar, wobei man von einem Linken und einem Rechten Wert spricht. Dabei werden kleine Werte nach links zum Anfang verschoben und große Werte nach rechts, also zum Ende hin.

In der nachfolgenden Infografik kannst du das ganze einmal sehen – wie sich das in einem Durchlauf verhält, dieser Durchlauf passiert so lange, bis alle Zahlen an ihrer richtigen Stelle stehen. Dabei fällt auf, dass in der zweiten Reihe eine 8 mit einer 10 verglichen wird, hier passiert nichts weiter, weil 8 kleiner als 10 ist und somit steht die Zahl für diesen Moment an ihrer richtigen Stelle. Alle anderen Zahlen werden entsprechende getauscht, da die Rechte kleiner als die Linke ist. Nachdem eine Iteration durchgelaufen ist, folgt direkt die nächste – bis wir die Zahlenreihe 3, 5, 7, 8, 10 erhalten.

Was dir hier anhand der Grafik schon auffallen sollte, ist die Performance eines Bubblesort-Algorithmus ist nicht besonders berauschende. Weshalb er in Programmiersprachen auch selten Anwendung findet. Deutlich schnellere Algorithmen wären unter anderem der Quicksort, Heapsort oder der Mergesort.

Implementierung des Bubblesort-Algorithmus in Java

Nachdem wir nun verstanden haben, wie der Bubblesort-Algorithmus funktioniert. Können wir diesen in Programmiersprachen wie Java implementieren. Dazu habe ich mich entschieden, eine Klasse BubbleSort anzulegen.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {

        int[] numbers = {3, 8, 7, 5, 10};

        var bubbleSort = new BubbleSort(numbers);

        var sortedArray = bubbleSort.sort();

        System.out.println(Arrays.toString(sortedArray));

    }
}

Diese nimmt einen Array von Zahlen entgegen – zusätzlich gibt es noch eine Methode sort() diese sortiert unseren Array nach dem Bubblesort-Algorithmus.

Bedeutet, wir müssen uns jede Zahl einmal anschauen, um das zu tun, verwenden wir eine For-Schleife. Dieser prüft als Erstes, ob die Linke Zahl kleiner ist als die Rechte, falls ja, soll mit der nächsten Iteration fortgefahren werden. Da wie in der Infografik auch in diesem Fall nichts zu tun ist, da die Zahlen schon an der richtigen Position stehen.

Falls unsere Linke Zahl jedoch größer als unsere Rechte Zahl ist, müssen wir die Positionen von diesen tauschen. Anders als unter anderem Python hat Java keine Möglichkeit ohne eine temporäre Variable zu arbeiten – unsere temporäre Variable ist n dort speichern wir unsere linke Zahl zwischen. Anschließende weisen wir der linken Stelle die rechte Zahl zu. Nachdem das getan wurde, rufen wir die Methode noch einmal auf, um den nächsten Sortierdurchlauf zu starten.

public class BubbleSort {
    public static int[] numbers;

    BubbleSort(int[] array){
        numbers = array;
    }

    public int[] sort(){
        int n;

        for (int i = 0; i < numbers.length - 1; i++) {
            if(numbers[i] < numbers[i + 1]){
                continue;
            }

            n = numbers[i];
            numbers[i] = numbers[i + 1];
            numbers[i + 1] = n;
            sort();
        }

        return numbers;
    }

}

Die Umsetzung mit der Methode sort(), die sich selbst aufruft, bis nichts mehr zu sortieren ist – nennt man einen rekursiven Funktionsaufruf. Dabei ruf die auslösende Funktion sich selbst auf. Wichtig ist, dass man hier eine Abbruchbedingung hat, um keine Endlosschleife zu erzeugen. In unserem Fall passiert das durch die if Abfrage, die prüft, ob der rechte Wert größer als der linke Wert ist.

Exkurs: Methode zum Sortieren von Arrays in Java

In Java gibt es bereits implementierte Methoden, um einen Array von Zahlen zu sortieren. So brauchst du nicht jedes Mal die Sortierung selbst zu implementieren. Eine der einfachsten zu verwendenden Varianten wäre etwa Arrays.sort(numbers). Der Sortieralgorithmus, der sich hinter dieser Methode verbirgt, ist ein Quicksort Algorithmus von Vladimir Yaroslavskiy, Jon Bentley und Josh Bloch.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {

        int[] numbers = {10,20,30,5,500,6,70,600};

        Arrays.sort(numbers);

        System.out.println(Arrays.toString(numbers));

    }
}

Der verwendete Algorithmus ist etwa deutlich schneller als der Bubblesort-Algorithmus.

Fazit

Der Bubblesort-Algorithmus ist gerade zur Veranschaulichung von einfachen Sortieralgorithmen sehr interessant zu betrachten und auch leicht zu implementieren.

Als kleine Übungsaufgabe kannst du ja einmal versuchen den Bubblesort-Algorithmus, ohne eine Rekursion in Java zu implementieren.