Java Bubble Sort

Bubble Sort

Der am einfachsten zu implementierende Algorithmus zum Sortieren von Daten ist vermutlich der BubbleSort-Algorithmus.
Zu beachten ist, dass er insbesondere im Vergleich zum wesentlich komplexer zu implementierenden Quick-Sort-Algorithmus ein wesentlich schlechteres Laufzeitverhalten zeigt.
Dies wird insbesondere bei großen Datenmengen relevant.

Beim bubble sort wird immer wieder ein Element im Array mit seinem Nachbarelement verglichen und die beiden Elemente ggf. vertauscht, falls sie vorher in der falschen Reihenfolge standen.
Somit wird mit jedem einzelnen Tausch die Sortierung der gesamten Liste "ein wenig besser". Dies wird so lange wiederholt, bis die gesamte Liste vollständig korrekt sortiert ist.
Die Schleifen sind hierzu verschachtelt: im ersten Durchgang der äußeren Schleife wird von Beginn an jedes Element mit seinem Nachfolger in der Liste verglichen: sind die beiden Elemente in der falschen Reihenfolge, so werden sie vertauscht.
Dadurch steht am Ende des ersten Durchlaufs der äußeren Schleife zwangsweise das letzte Element an der letzten Stelle (es ist also korrekt (am Ende) einsortiert).
Nun wird dieser Vorgang mit der um eins verkürzten Liste wiederholt (das letzte Element muss ja nicht mehr betrachtet werden, denn es ist ja schon korrekt einsortiert).
Der Algorithmus ist beendet, wenn dieser Vorgang mit der letzten, kürzesten Liste (bestehend aus zwei Elementen) abgeschlossen ist.

Das folgende Beispiel zeigt diesen Algorithmus am Beispiel eines String-Arrays:

Einfache Bubble Sort Implementierung

Zum Test binden wir de Methode "sort" in eine einfache Testklasse ein:

public class BubbleSort {
    public static void sort(final String[] data) {
        final int len = data.length;
        String buffer;
        for (int i = len - 2; i >= 0; i--) {
            for (int k = 0; k <= i; k++) {
                if (data[k].compareTo(data[k+1]) > 0) {
                    buffer = data[k+1];
                    data[k+1] = data[k];
                    data[k] = buffer;
                }
            }
        }
    }
    public static void main(final String[] args) {
        sort(args);
        for (String current: args) {
            System.out.println(current);
        }
    }
}

Wir testen die Sortierfunktion z. B. wie folgt:

java BubbleSort Chris Anton Emil Franz Gustav Dora Berta

... und sehen als Ergebnis die Namen in sortierter Reihenfolge.

Performance

Die Zeit, die zum Sortieren benötigt wird, wächst Proportional mit dem Quadrat der Anzahl der zu sortierenden Elemente.
Deutlich performanter wäre ein Quicksort, welcher allerdings komplexer zu implementieren ist. Beim Quicksort ist die benötigte Zeit proportional zum Logarithmus des Quadrats der Anzahl der zu sortierenden Elemente.



Nach oben, Inhaltsverzeichnis, Impressum Admin: Artikel editieren