Jetzt anmelden...

Login
Passwort
Registrieren

JAVA Blog

Der Bubblesort-Algorithmus in Java

Der Bubblesort ist der einfachste Sortier-Algorithmus. Er vergleicht mehrfach alle benachbarten Elemente in einem Array und tauscht sie sukzessive in die richtige Reihenfolge. Lernen Sie heute, wie genau das funktioniert. Am Ende haben Sie sich eine kleine Abkürzung verdient.

Kommentare [0] 115 Views

Stefan 10.08.2020

Infos zum Artikel

Kategorie Java
Autor Stefan
Datum 10.08.2020

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

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 durchlaugen, bis alle Elemente des Arrays vollständig in der richtigen Reihenfolge sind.

Ein Beispiel für den Bubblesort

Sehen wir uns ein konkreten 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:

Java Variablen Infografik

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. Welchen 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 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.

Falconbyte unterstützen

Kommentar schreiben

Nur angemeldete und aktivierte Benutzer können kommentieren.

Alle Kommentare

Es gibt bislang noch keine Kommentare zu diesem Thema.

Verzweigungen in Java

Eine zentrale Notwendigkeit der Programmierung sind Verzweigungen.

Primitive Datentypen

Am Ende des Kapitels werden Sie wissen, wie Primitive Datentypen korrekt eingesetzt werden.

Arrays in Java

Arrays ermöglichen das Speichern von Daten in einer übergeordneten Datenstruktur

FALCONBYTE.NET

Handmade with 🖤️

© 2018-2020 Stefan E. Heller

Impressum | Datenschutz

facebook programmieren lernen twitter programmieren lernen youtube programmieren lernen