Blasensortierung
Ein Beispiel für die Blasensortierung. Vergleichen Sie ab dem Anfang der Liste jedes benachbarte Paar und tauschen Sie seine Position aus, wenn sie nicht in der richtigen Reihenfolge sind (das letztere ist kleiner als das erstere). Nach jeder Iteration muss ein Element weniger (das letzte) verglichen werden, bis keine Elemente mehr verglichen werden müssen.
PerformanceEdit
Die Blasensortierung hat eine Worst-Case- und durchschnittliche Komplexität von О (n2), wobei n die Anzahl der zu sortierenden Elemente ist. Die meisten praktischen Sortieralgorithmen weisen eine wesentlich bessere Worst-Case- oder durchschnittliche Komplexität auf, häufig O (n log n). Selbst andere О (n2) -Sortieralgorithmen wie die Einfügungssortierung laufen im Allgemeinen schneller als die Blasensortierung und sind nicht komplexer. Daher ist die Blasensortierung kein praktischer Sortieralgorithmus.
Der einzige wesentliche Vorteil, den die Blasensortierung gegenüber den meisten anderen Algorithmen hat, selbst die Quicksortierung, jedoch nicht die Einfügungssortierung, besteht darin, dass erkannt werden kann, dass die Liste sortiert ist effizient ist in den Algorithmus eingebaut. Wenn die Liste bereits sortiert ist (Best-Case), beträgt die Komplexität der Blasensortierung nur O (n). Im Gegensatz dazu führen die meisten anderen Algorithmen, selbst diejenigen mit einer besseren durchschnittlichen Fallkomplexität, ihren gesamten Sortierprozess am Satz durch und sind daher komplexer. Die Einfügesortierung teilt jedoch nicht nur diesen Vorteil, sondern bietet auch eine bessere Leistung bei einer Liste, die im Wesentlichen sortiert ist (mit einer geringen Anzahl von Inversionen). Wenn dieses Verhalten gewünscht wird, kann es außerdem trivial zu jedem anderen Algorithmus hinzugefügt werden, indem die Liste überprüft wird, bevor der Algorithmus ausgeführt wird.
Die Blasensortierung sollte bei großen Sammlungen vermieden werden. Bei einer Sammlung in umgekehrter Reihenfolge ist dies nicht effizient.
Kaninchen und SchildkrötenEdit
Die Entfernung und Richtung, in die sich Elemente während der Sortierung bewegen müssen, bestimmen die Leistung der Blasensortierung, weil Elemente bewegen sich mit unterschiedlichen Geschwindigkeiten in verschiedene Richtungen. Ein Element, das sich gegen Ende der Liste bewegen muss, kann sich schnell bewegen, da es an aufeinanderfolgenden Swaps teilnehmen kann. Beispielsweise gewinnt das größte Element in der Liste jeden Swap, also bewegt es sich zu Die sortierte Position beim ersten Durchgang, auch wenn sie am Anfang beginnt. Andererseits kann sich ein Element, das sich zum Anfang der Liste bewegen muss, nicht schneller als einen Schritt pro Durchgang bewegen, sodass sich die Elemente sehr langsam zum Anfang bewegen Das kleinste Element befindet sich am Ende der Liste. Es dauert n – 1 Durchgänge, um es an den Anfang zu verschieben. Dies hat dazu geführt, dass diese Elementtypen nach den Zeichen in Aesops Fabel von Kaninchen bzw. Schildkröten genannt werden Die Schildkröte und der Hase.
Verschiedene Es wurden Anstrengungen unternommen, um Schildkröten zu eliminieren, um die Geschwindigkeit der Blasensortierung zu verbessern. Die Cocktailsorte ist eine bidirektionale Blasensorte, die von Anfang bis Ende verläuft und sich dann umkehrt und von Ende zu Anfang geht. Es kann Schildkröten ziemlich gut bewegen, behält aber die Komplexität von O (n2) im schlimmsten Fall bei. Die Kammsortierung vergleicht Elemente, die durch große Lücken getrennt sind, und kann Schildkröten extrem schnell bewegen, bevor zu immer kleineren Lücken übergegangen wird, um die Liste zu glätten. Die Durchschnittsgeschwindigkeit ist vergleichbar mit schnelleren Algorithmen wie Quicksort.
Schritt-für-Schritt-Beispiel Bearbeiten
Nehmen Sie ein Array mit Zahlen „5 1 4 2 8“ und sortieren Sie das Array vom niedrigsten Zahl zur größten Zahl mit Blasensortierung. In jedem Schritt werden fett geschriebene Elemente verglichen. Es sind drei Durchgänge erforderlich:
Erster Durchgang (5 1 4 2 8) → (1 5 4 2 8). Hier vergleicht der Algorithmus die ersten beiden Elemente und tauscht seit 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), Swap seit 5 > 4 (1 4 5 2 8) → (1 4 2 5 8), Swap seit 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Nun, da diese Elemente bereits in Ordnung sind (8 > 5), der Algorithmus tauscht sie nicht aus. Zweiter Durchgang (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Tauschen seit 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)
Jetzt ist das Array bereits sortiert, aber der Algorithmus weiß nicht, ob es abgeschlossen ist . Der Algorithmus benötigt einen ganzen Durchgang ohne Austausch, um zu wissen, dass er sortiert ist.