Der Algorithmus für die Blasensortierung erfordert ein Paar verschachtelter Schleifen. Die äußere Schleife muss für jedes Element im Datensatz (der Größe n) einmal iterieren, während die innere Schleife bei der ersten Eingabe n-mal, bei der zweiten n-1-mal usw. iteriert. Betrachten Sie den Zweck jeder Schleife. Wie oben erläutert, ist die Blasensortierung so strukturiert, dass bei jedem Durchlauf durch die Liste das nächstgrößere Element der Daten an die richtige Stelle verschoben wird. Um alle n Elemente an die richtigen Stellen zu bringen, muss die äußere Schleife daher n-mal ausgeführt werden.
Die innere Schleife wird bei jeder Iteration der äußeren Schleife ausgeführt. Sein Zweck ist es, das nächstgrößere Element einzusetzen. Die innere Schleife vergleicht und vertauscht daher benachbarte Elemente. Um die Komplexität dieser Schleife zu bestimmen, berechnen wir die Anzahl der Vergleiche, die durchgeführt werden müssen. Bei der ersten Iteration der äußeren Schleife müssen beim Versuch, das größte Element zu platzieren, n – 1 Vergleiche durchgeführt werden: Der erste Vergleich wird zwischen dem ersten und dem zweiten Element durchgeführt, der zweite zwischen dem zweiten und dem dritten Element und so weiter, bis der n-1-te Vergleich zwischen dem n-1-ten und dem n-ten Element durchgeführt wird. Bei der zweiten Iteration der äußeren Schleife muss das Element nicht mit dem letzten Element der Liste verglichen werden, da es im vorherigen Durchgang an der richtigen Stelle platziert wurde. Daher erfordert die zweite Iteration nur n-2 Vergleiche. Dieses Muster wird bis zur vorletzten Iteration der äußeren Schleife fortgesetzt, wenn nur die ersten beiden Elemente der Liste unsortiert sind. In diesem Fall ist eindeutig nur ein Vergleich erforderlich. Die Gesamtzahl der Vergleiche beträgt daher (n – 1) + (n – 2) … (2) + (1) = n (n – 1) / 2 oder O (n2).
Der beste Fall für die Blasensortierung liegt vor, wenn die Liste bereits sortiert oder nahezu sortiert ist. Wenn die Liste bereits sortiert ist, wird die Blasensortierung nach der ersten Iteration beendet, da keine Swaps durchgeführt wurden. Jedes Mal, wenn ein Durchlauf durch die Liste erfolgt und keine Swaps durchgeführt wurden, ist sicher, dass die Liste sortiert ist. Die Blasensortierung ist auch dann effizient, wenn ein zufälliges Element in eine sortierte Liste sortiert werden muss, vorausgesetzt, das neue Element wird am Anfang und nicht am Ende platziert. Wenn es am Anfang platziert wird, sprudelt es einfach an die richtige Stelle und die zweite Iteration durch die Liste generiert 0 Swaps, wodurch die Sortierung beendet wird. Denken Sie daran, dass die Blasensortierung ihre Effizienz verliert, wenn das zufällige Element am Ende platziert wird, da jedes Element, das größer ist als es, ganz nach oben sprudeln muss.
Der absolut schlechteste Fall für die Blasensortierung ist, wenn die Das kleinste Element der Liste befindet sich am großen Ende. Da in jeder Iteration nur das größte unsortierte Element an die richtige Position gebracht wird, muss das kleinste Element am Ende jedes Mal durch die Liste ausgetauscht werden, und es wird erst dann an die Spitze der Liste gelangen, wenn alle n vorhanden sind Iterationen sind aufgetreten. Im schlimmsten Fall sind n Iterationen von n / 2 Swaps erforderlich, sodass die Reihenfolge wiederum n2 ist.
Bester Fall: nDurchschnittlicher Fall: n2Worst-Fall: n2