Bubblesort

Gebrauch

Der Bubblesort wird gebraucht, um einen Array zu sortieren.

Während er einer der simpleren Sortierungsalgorithmen ist, ist er auch einer der weniger effizienten.

Spezifikationen

Der Bubblesort Algorithmus hat eine worst-case Performance von O(n²) Vergleiche, O(n²) Tauschungen und eine best-case Performance von O(n) Vergleiche, O(1) Tauschungen. Seine Durchschnittsperformance beträgt O(n²) Vergleiche, O(n²) Tauschungen.

Der Algorithmus braucht keine weiteren Arrays und hat somit jeweils eine Space-complexity von O(1).

Funktionsweise

Beim Bubblesort Algorithmus beginnt man am Anfang des Arrays und arbeitet sich so hoch.

Das Grundprinzip basiert darauf, dass ein Wert, welcher nie kleiner ist als ein anderer, der Grösste im Array ist. Dies kann zu nutzen gemacht werden, indem, dass man den ersten Wert des Arrays untersucht und ihn mit dem Wert vergleicht, dessen Index um eins grösser ist als sein eigener. Falls der untersuchte Wert grösser ist als der Verglichene, dann tauscht man dessen Plätze. Ansonsten fokussiert man sich neu auf den verglichenen Wert und vergleicht ihn mit dem Wert, dessen Index um eines grösser ist als der des nun neu fokussierten Wertes. Man vergleicht diese dann wieder auf die gleiche Weise, wie die ersten zwei.

Dies tut man so lange, bis man am Ende des Arrays angekommen ist. Da wir nun jeden Wert im Array miteinander verglichen und jenachdem ausgetauscht haben, wissen wir, dass der Wert am Ende des Arrays der Grösste im Array ist. Nun beginnt man wieder am Anfang des Arrays und führt das Prozedere nochmals durch, jedoch nur bis zum zweitletzten Index. Nach dem Vergleichen bis zum zweitletzten Index weiss man nun, dass der Wert am zweitletzten Index der zweitgrösste Wert im Array, beziehungsweise der Grösste ohne den letzten Wert im Array, ist. Dann wird der Algorithmus bis zum drittletzten Index weitergeführt. Dies wird alles so lange gemacht, bis der maximal zu untersuchende Index eins ist, denn dies bedeutet schlussendlich, dass der ganze Array sortiert wurde.

Beispielcode

Dies ist ein in Python geschriebener Beispielcode:

# arr ist der Array, welcher zu sortieren ist. Die Funktion gibt den sortierten Array zurück def bubbleSort(arr): # Der maximale Index, welcher der fokussierte Wert haben kann max = len(arr) - 1 # Der fokussierte Index focusedIndex = 0 # Der Index des Wertes, welcher mit dem Wert am fokussierten Index verglichen wird comparedIndex = 1 # Sobald der maximal zu fokussierende Index 1 ist, ist der Array sortiert. Falls max anfangs schon kleiner als 1 ist, hat der Array so wenig Elemente, dass er schon sortiert ist while max > 1: # Falls der fokussierte Index dem maximal zu fokussierendem Index entspricht, wird der Algorithmus wieder vom Index null weitergeführt if focusedIndex == max: # Der maximal zu fokussierende Index muss nun um eins kleiner sein max -= 1 # Man beginnt wieder am Anfang des Arrays => Der fokussierte Index ist wieder 0 focusedIndex = 0 # Der Index, mit dem verglichen wird, ist wieder 1 comparedIndex = 1 # Falls der Wert am fokussierten Index grösser ist als der am Verglichenen if arr[focusedIndex] > arr[comparedIndex]: # Die beiden Werte werden miteinander getauscht arr[focusedIndex], arr[comparedIndex] = arr[comparedIndex], arr[focusedIndex] # Nach jeder Iteration wird der fokussierte Index um eins erhöht focusedIndex += 1 # Nach jeder Iteration wird der verglichene Index um eins erhöht comparedIndex += 1 # Der sortierte Array wird zurückgegeben return arr

Dies ist ein in Java geschriebener Beispielcode:

Es können selbstverständlich auch andere Datentypen gebraucht werden.

// arr ist der Array, welcher zu sortieren ist. Die Funktion gibt den sortierten Array zurück public static int bubbleSort(int[] arr) { // Der maximale Index, welcher der fokussierte Wert haben kann int max = arr.length - 1; // Der fokussierte Index int focusedIndex = 0; // Der Index des Wertes, welcher mit dem Wert am fokussierten Index verglichen wird int comparedIndex = 1; // Sobald der maximal zu fokussierende Index 1 ist, ist der Array sortiert. Falls max anfangs schon kleiner als 1 ist, hat der Array so wenig Elemente, dass er schon sortiert ist while (max > 1) { // Falls der fokussierte Index dem maximal zu fokussierendem Index entspricht, wird der Algorithmus wieder vom Index 0 weitergeführt if (focusedIndex == max) { // Der maximal zu fokussierende Index muss nun um eins kleiner sein max--; // Man beginnt wieder am Anfang des Arrays => Der fokussierte Index ist wieder 0 focusedIndex = 0; // Der Index, mit dem verglichen wird, ist wieder 1 comparedIndex = 1; } // Falls der Wert am fokussierten Index grösser ist als der am Verglichenen, werden die beiden Werte miteinander getauscht if (arr[focusedIndex] > arr[comparedIndex]) { int temp = arr[focusedIndex]; arr[focusedIndex] = arr[comparedIndex]; arr[comparedIndex] = temp; } // Nach jeder Iteration wird der fokussierte Index um eins erhöht focusedIndex++; // Nach jeder Iteration wird der verglichene Index um eins erhöht comparedIndex++; } // Der sortierte Array wird zurückgegeben return arr; }

Animiertes Beispiel

Drücke Start, um die Animation zu starten. Ändere die Position des Sliders, um die Geschwindigkeit der Animation zu verändern.