Algorithmen und Datenstrukturen: Der Bubble Sort in Java

Der Algorithmus

Beim „Bubble Sort“ markiert die äußere Schleife das erste Element des noch unsortierten Bereichs, während die innere Schleife ab diesem Element immer bis zum Ende des Arrays ein Element zum Vergleich rauspickt. Ist ein Element kleiner/größer (je nachdem wie der Vergleichsoperator „gedreht“ ist) wird getauscht.

Dies führt am Ende zu der Sortierung des Arrays. Im Gegesatz zum Selection Sort, wo nur das Minimum getauscht wird, wird beim Bubble Sort immer getauscht.

package AlgoDat;

public class BubbleSort {
    // Zu sortierendes Array
    private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};

    // Hält die Klasse als instanziertes Objekt
    @SuppressWarnings("unused")
    private static BubbleSort program;

    // Hilfsfunktion für das Ausgeben des Arrays
    public void OutputOfIntArray(int myArray[])
    {
        if (myArray != null)
        {
            for (int i = 0; i < myArray.length; i++) {
                if (i > 0) System.out.print(";");
                System.out.print(myArray[i]);
            }

            System.out.println();
        }
    }

    // Konstruktor
    public BubbleSort()
    {
        System.out.print("Vorher: ");
        this.OutputOfIntArray(myArray);

        // Äußere Schleife: Laufe das zu sortierende Array von Anfang bis Ende durch (Komplexität: n)
        for (int idxSortierterBereich = 0; idxSortierterBereich < myArray.length - 1 ; idxSortierterBereich++)
        {
            // Innere Schleife: Laufe das Array ab dem Index der äußeren Schleife bis Ende durch (Komplexität: n / 2)
            for (int idxUnsortierterBereich = idxSortierterBereich + 1; idxUnsortierterBereich < myArray.length; idxUnsortierterBereich++)
            {
                // Tausche die Array-Inhalte an den Indizes der inneren und äußeren Schleife
                // wenn diese kleiner/größer sind. Anmerkung: Ein Drehen von < zu > ändert die Sortierreihenfolge
                if (myArray[idxUnsortierterBereich] < myArray[idxSortierterBereich])
                {
                    // Beim Bubble Sort wird im Gegensatz zum Selection Sort immer getauscht.
                    // Beim Selection Sort wird nur das gefundene Minimum getauscht. 
                    // Dieser Code tauscht das Element am Index der äußeren Schleife                
                    // mit dem Element am Index der inneren Schleife
                    int swapVar = myArray[idxUnsortierterBereich];
                    myArray[idxUnsortierterBereich] = myArray[idxSortierterBereich];
                    myArray[idxSortierterBereich] = swapVar;

                    System.out.print("Tausche: ");
                    this.OutputOfIntArray(myArray);
                }
            }
        }

        System.out.print("Nachher: ");
        this.OutputOfIntArray(myArray);
    }

    public static void main(String[] args) 
    {
        // Instanziere aus den statischem Programm ein echtes Objekt
        // damit nicht alle Methoden und Variablen static sein müssen.
        program = new BubbleSort();
    }
}

Ausgabe

Vorher: 22;6;2;4;10;3;9;7;5;8;1
Tausche: 6;22;2;4;10;3;9;7;5;8;1
Tausche: 2;22;6;4;10;3;9;7;5;8;1
Tausche: 1;22;6;4;10;3;9;7;5;8;2
Tausche: 1;6;22;4;10;3;9;7;5;8;2
Tausche: 1;4;22;6;10;3;9;7;5;8;2
Tausche: 1;3;22;6;10;4;9;7;5;8;2
Tausche: 1;2;22;6;10;4;9;7;5;8;3
Tausche: 1;2;6;22;10;4;9;7;5;8;3
Tausche: 1;2;4;22;10;6;9;7;5;8;3
Tausche: 1;2;3;22;10;6;9;7;5;8;4
Tausche: 1;2;3;10;22;6;9;7;5;8;4
Tausche: 1;2;3;6;22;10;9;7;5;8;4
Tausche: 1;2;3;5;22;10;9;7;6;8;4
Tausche: 1;2;3;4;22;10;9;7;6;8;5
Tausche: 1;2;3;4;10;22;9;7;6;8;5
Tausche: 1;2;3;4;9;22;10;7;6;8;5
Tausche: 1;2;3;4;7;22;10;9;6;8;5
Tausche: 1;2;3;4;6;22;10;9;7;8;5
Tausche: 1;2;3;4;5;22;10;9;7;8;6
Tausche: 1;2;3;4;5;10;22;9;7;8;6
Tausche: 1;2;3;4;5;9;22;10;7;8;6
Tausche: 1;2;3;4;5;7;22;10;9;8;6
Tausche: 1;2;3;4;5;6;22;10;9;8;7
Tausche: 1;2;3;4;5;6;10;22;9;8;7
Tausche: 1;2;3;4;5;6;9;22;10;8;7
Tausche: 1;2;3;4;5;6;8;22;10;9;7
Tausche: 1;2;3;4;5;6;7;22;10;9;8
Tausche: 1;2;3;4;5;6;7;10;22;9;8
Tausche: 1;2;3;4;5;6;7;9;22;10;8
Tausche: 1;2;3;4;5;6;7;8;22;10;9
Tausche: 1;2;3;4;5;6;7;8;10;22;9
Tausche: 1;2;3;4;5;6;7;8;9;22;10
Tausche: 1;2;3;4;5;6;7;8;9;10;22
Nachher: 1;2;3;4;5;6;7;8;9;10;22

Komplexität: O-Notation (Ordnung)

O(T(n)) = O(n²)

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.