Der Bubblesort-Algorithmus in Java

Sofort-Code

int[] array = {2, 1, 5, 4, 6, 3};

int smaller;
int bigger;
boolean run = true;


for (int i = 0; i < array.length && run == true; i++) {
    run = false;

   for (int y = 0; y < array.length-1; y++) {
        if(array[y] > array[y + 1]) {
            bigger = array[y];
            smaller = array[y + 1];
            array[y] = smaller;
            array[y + 1] = bigger;
            run = true;
          }
    }
}

Inhaltsverzeichnis

1. Wie funktioniert der Bubblesort?
2. Ein Beispiel für den Bubblesort
3. Der Bubblesort im Java-Code
4. Die Methode Arrays.sort()

Wie funktioniert der Bubblesort?

Der Bubblesort-Algorithmus sortiert eine Liste von Elementen in einem Array. Dies geschieht dadurch, dass die einzelnen Elemente immer paarweise von links nach rechts miteinander verglichen werden.

Ist das rechte Element größer als das direkt benachbarte linke, werden beide Elemente miteinander getauscht. So ist die richtige Reihenfolge des Vergleich-Paares hergestellt. Danach wird das nächste Paar miteinander verglichen. Dieser Vorgang läuft solange, bis das gesamte Array einmal durchlaufen wurde.

Ist das Ende des Arrays erreicht und wurden alle Paare miteinander verglichen und die erste "Tausch-Runde" damit abgeschlosen, startet der nächste Array-Durchlauf und das Prozedere beginnt von vorn.

Das Array wird solange von vorne bis hinten durchlaufen, bis alle Elemente des Arrays vollständig in der richtigen Reihenfolge sind.

Ein Beispiel für den Bubblesort

Sehen wir uns ein konkretes Beispiel an:

Wir erzeugen jetzt ein kleines Array aus Ganzzahlen. Die einzelnen Elemente sind nicht sortiert:

int[] array = {2, 1, 5, 4, 6, 3};

Der Bubblesort, den wir auf diesem Array anwenden, soll die einzelnen Elemente in aufsteigender Reihenfolge sortieren.

Insgesamt werden dafür drei Durchgänge benötigt, damit alle Elemente entsprechend unseres Sortierkriteriums geordnet sind:

Soweit zur Theorie. Sehen wir uns nun den spannenden Teil an: Den Code.

Der Bubblesort im Java-Code

Der vollständige Code zum Bubblesort-Algorithmus sehen wir hier:

int[] array = {2, 1, 5, 4, 6, 3};

int smaller;
int bigger;
boolean run = true;


for (int i = 0; i < array.length && run == true; i++) {
    run = false;

   for (int y = 0; y < array.length-1; y++) {
        if(array[y] > array[y + 1]) {
            bigger = array[y];
            smaller = array[y + 1];
            array[y] = smaller;
            array[y + 1] = bigger;
            run = true;
          }
    }
}

Unser Algorithmus arbeitet mit einer äußeren und inneren Schleife. Bevor der Code aber in die Schleifenkonstruktion geht, werden drei notwendige Variablen deklariert. Welchem Zweck sie dienen, zeigt sich gleich.

Unser Sortier-Algorithmus benötigt maximal die Anzahl an Durchläufen der Größe des Arrays -1. Dies wird durch die äußere Schleife festgelegt.

In der inneren Schleife findet nun der eigentliche Sortierprozess statt, indem die einzelnen (benachbarten) Array-Positionen miteinander verglichen werden. Ist ein linker Wert (array[y]) größer als ein rechter (array[y]+1) werden die beiden Elemente miteinander getauscht. Die beiden Variablen smaller und bigger dienen zur Zwischenspeicherung.

Ein guter Algorithmus endet, sobald seine Aufgabe erfüllt ist. Wir brauchen keine unnötigen Schleifendurchläufe! Wenn die if-Prüfung mit array[y] > array[y + 1] einmal nicht mehr erfüllt ist, gibt es folglich nichts mehr zu tauschen und alle Elemente sind sortiert. Damit wird die Variable run nicht mehr auf true gesetzt. Die Laufbedingung der übergeordneten Schleife ist damit nicht mehr erfüllt und wir sind fertig.

Ein Test bestätigt den Erfolg unseres Vorhabens:

for(int i = 0; i < array.length; i++){
    System.out.print(array[i] + " "); // 1 2 3 4 5 6
}

Die Methode Arrays.sort()

Um das Ganze für unsere zukünftigten Programmierprojekte abzukürzen, können wir auch auf die fertige Sortier-Methode der Klasse Arrays zurückgreifen. 😎

Man nehme einfach die statische Methode sort() aus der Bibliotheksklasse java.util.Arrays (import-Anweisung nicht vergessen!):

int[] array = {2, 1, 5, 4, 6, 3};

Arrays.sort(array);
System.out.println(Arrays.toString(array)); // 1 2 3 4 5 6

Allerdings läuft diese Methode nicht mit dem Bubble-Sort, sondern Quicksort-Verfahren.