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²)
