Blase sortieren

Definition - Was bedeutet Blasensortierung?

Die Blasensortierung ist ein Sortieralgorithmus, bei dem wiederholt zu sortierende Listen durchlaufen, jedes Paar benachbarter Elemente verglichen und ausgetauscht werden, wenn sie in der falschen Reihenfolge vorliegen. Dieser Übergabevorgang wird wiederholt, bis keine Swaps mehr erforderlich sind, was darauf hinweist, dass die Liste sortiert ist. Die Blasensortierung erhält ihren Namen, weil kleinere Elemente ganz oben auf der Liste stehen.

Die Blasensortierung wird auch als sinkende Sortierung oder Vergleichssortierung bezeichnet.

Technische.me erklärt Bubble Sort

Die Blasensortierung hat eine Worst-Case- und durchschnittliche Komplexität von O (n2), wobei n die Anzahl der sortierten Elemente ist. Im Gegensatz zu den anderen Sortieralgorithmen erkennt die Blasensortierung, ob die sortierte Liste effizient in den Algorithmus integriert ist. Die Blasensortierleistung über eine bereits sortierte Liste beträgt O (n).

Die Position von Elementen bei der Blasensortierung spielt eine wichtige Rolle bei der Bestimmung der Leistung. Große Elemente am Anfang stellen kein Problem dar, da sie leicht ausgetauscht werden können. Die kleinen Elemente gegen Ende bewegen sich langsam zum Anfang. Als solche werden diese Elemente Kaninchen und Schildkröten genannt.

Der Blasensortierungsalgorithmus kann optimiert werden, indem größere Elemente an der endgültigen Position platziert werden. Nach jedem Durchgang werden alle Elemente nach dem letzten Austausch sortiert und müssen nicht erneut überprüft werden, wodurch die Verfolgung der ausgetauschten Variablen übersprungen wird.