BubbleSort

Bubblesort ist ein einfacher, stabiler Sortieralgorithmus, der eine Reihe von linear angeordneten Elementen (z.B. Zahlen) der Größe nach anordnet.

Prinzip

Der Algorithmus vergleicht der Reihe nach zwei benachbarte Elemente und vertauscht sie, falls sie in der falschen Reihenfolge vorliegen. Dieser Vorgang wird solange wiederholt, bis keine Vertauschungen mehr nötig sind. Hierzu sind in der Regel mehrere Durchläufe erforderlich.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die kleineren oder größeren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, d.h. an das Ende der Reihe. Auch werden immer zwei Zahlen miteinander in "Bubbles" vertauscht.

Beispiel

Eine Reihe von 5 Zahlen soll aufsteigend sortiert werden.

Die fett gedruckten Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht; das Zahlenpaar ist dann blau markiert.

55 07 78 12 42  1.Durchlauf
07 55 78 12 42
07 55 78 12 42
07 55 12 78 42
07 55 12 42 78  2.Durchlauf
07 55 12 42 78
07 12 55 42 78
07 12 42 55 78  3.Durchlauf
07 12 42 55 78
07 12 42 55 78  4.Durchlauf
07 12 42 55 78  Fertig sortiert.

Implementation

/*
 * BubbleSort
 *
 * Alle verwendeten Methoden sowie das zu sortierende Zahlenfeld
 * werden als static definiert und sind somit sofort verfügbar,
 * ohne dass man erst ein Objekt der Klasse BubbleSort erzeugen muss.
 *
 */
public class BubbleSort {
   
    // das zu sortierende Zahlenfeld
    static int[] zahlen = {45,22,20,3,2,1};
   
    // vertauschen der Zahlen an den Positionen index1 bzw. index2
    static void tausche(int index1, int index2){
        int temp = zahlen[index1];
        zahlen[index1] = zahlen[index2];
        zahlen[index2] = temp;
    }
   
    // Methode zur Ausgabe der Zahlenfolge auf der Konsole
    static void zeigeZahlenfolge(){
        for(int k=0; k<zahlen.length; k++) {
            System.out.print(" " + zahlen[k]);
        }
        System.out.println();
    }
   
    public static void main(String[] args) {

        boolean getauscht;
        int i = 0;
       
        do {
            getauscht = false;

            // innere Schleife für einen Array-Durchlauf
            // die Länge des zu durchlaufenden Arrays verkürzt
            // sich nach jedem Schleifendurchlauf um ein Element.
            for(int j=0; j<zahlen.length-1-i; j++) {
                // jede Zahl wird mit ihrem Nachfolger verglichen
                if(zahlen[j]>zahlen[j+1]) {
                    // und ggf. mit diesem vertauscht
                    tausche(j, j+1);
                    // merken, dass getauscht wurde
                    getauscht = true;
                }
            }
           
            // Zahlenfolge ausgeben
            zeigeZahlenfolge();
            // Zählvariable erhöhen
            i++;
           
        // äußere Schleife abbrechen, wenn nicht mehr getauscht wurde
        // oder wenn das unsortierte Teilarray nur noch aus einem Element besteht.
        } while(i<zahlen.length-1 && getauscht == true);

    }
       
}
 

» drucken: pdf | html