Der Algorithmus
Beim „Bubble Sort“ markiert die äußere Schleife das letzte Element des noch unsortierten Bereichs, während die innere Schleife anfangs das erste Element markiert und bei jeder Iteration bis zu dem Element, was die äußere Schleife markiert, läuft. Jedes Element der aktuellen Iteration der inneren Schleife wird mit dem Nachfolgeelement der aktuellen Iteration verglichen. Ist ein Element kleiner/größer (je nachdem wie der Vergleichsoperator „gedreht“ ist) wird getauscht. Auf diese Weise „blubbert“ die größte Zahl immer bis zum Anfang des sortierten Bereichs, welchen die äußere Schleife markiert, nach oben.
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 Rechts nach links durch,
// damit der bereits sortierte Bereich rechts wächst
for (int i = myArray.length; i > 1 ; i--)
{
System.out.println("Iteration " + i);
// Innere Schleife: Laufe das Array bis zum bereits sortierten Bereich der
// äußeren Schleife durch
for (int j = 0; j < i - 1; j++)
{
// Tausche die Array-Inhalte
if (myArray[j] > myArray[j + 1])
{
this.vertausche(myArray, j, j + 1);
System.out.print("Tausche: ");
this.OutputOfIntArray(myArray);
}
}
}
System.out.print("Nachher: ");
this.OutputOfIntArray(myArray);
}
public void vertausche(int[] arrayToSwap, int idx1, int idx2)
{
int swapVar = arrayToSwap[idx1];
arrayToSwap[idx1] = arrayToSwap[idx2];
arrayToSwap[idx2] = swapVar;
}
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
Iteration 11
Tausche: 6;22;2;4;10;3;9;7;5;8;1
Tausche: 6;2;22;4;10;3;9;7;5;8;1
Tausche: 6;2;4;22;10;3;9;7;5;8;1
Tausche: 6;2;4;10;22;3;9;7;5;8;1
Tausche: 6;2;4;10;3;22;9;7;5;8;1
Tausche: 6;2;4;10;3;9;22;7;5;8;1
Tausche: 6;2;4;10;3;9;7;22;5;8;1
Tausche: 6;2;4;10;3;9;7;5;22;8;1
Tausche: 6;2;4;10;3;9;7;5;8;22;1
Tausche: 6;2;4;10;3;9;7;5;8;1;22
Iteration 10
Tausche: 2;6;4;10;3;9;7;5;8;1;22
Tausche: 2;4;6;10;3;9;7;5;8;1;22
Tausche: 2;4;6;3;10;9;7;5;8;1;22
Tausche: 2;4;6;3;9;10;7;5;8;1;22
Tausche: 2;4;6;3;9;7;10;5;8;1;22
Tausche: 2;4;6;3;9;7;5;10;8;1;22
Tausche: 2;4;6;3;9;7;5;8;10;1;22
Tausche: 2;4;6;3;9;7;5;8;1;10;22
Iteration 9
Tausche: 2;4;3;6;9;7;5;8;1;10;22
Tausche: 2;4;3;6;7;9;5;8;1;10;22
Tausche: 2;4;3;6;7;5;9;8;1;10;22
Tausche: 2;4;3;6;7;5;8;9;1;10;22
Tausche: 2;4;3;6;7;5;8;1;9;10;22
Iteration 8
Tausche: 2;3;4;6;7;5;8;1;9;10;22
Tausche: 2;3;4;6;5;7;8;1;9;10;22
Tausche: 2;3;4;6;5;7;1;8;9;10;22
Iteration 7
Tausche: 2;3;4;5;6;7;1;8;9;10;22
Tausche: 2;3;4;5;6;1;7;8;9;10;22
Iteration 6
Tausche: 2;3;4;5;1;6;7;8;9;10;22
Iteration 5
Tausche: 2;3;4;1;5;6;7;8;9;10;22
Iteration 4
Tausche: 2;3;1;4;5;6;7;8;9;10;22
Iteration 3
Tausche: 2;1;3;4;5;6;7;8;9;10;22
Iteration 2
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)
Diese Version des Bubble Sort-Algorithmus hat im Worst-, Average- und Best-Case eine Laufzeitkomplexität von O(n²)
Es gibt eine optimierte Version des Bubble Sort Algorithmus, der hier im Blog im Artikel „Der optimierte Bubble Sort in Java“ vorgestellt wird.
