Die Blasensortierung ist ein einfacher Algorithmus, mit dem eine bestimmte Menge von Elemente in Form eines Arrays mit n Anzahl der Elemente. Die Blasensortierung vergleicht alle Elemente einzeln und sortiert sie nach ihren Werten.
Wenn das angegebene Array in aufsteigender Reihenfolge sortiert werden muss, beginnt die Blasensortierung mit dem Vergleich des ersten Elements des Arrays mit Das zweite Element, wenn das erste Element größer als das zweite Element ist, tauscht beide Elemente aus und fährt dann fort, um das zweite und das dritte Element usw. zu vergleichen.
Wenn wir total haben n Elemente, dann müssen wir diesen Vorgang für n-1 Mal wiederholen.
Es wird als Blasensortierung bezeichnet. Denn bei jeder vollständigen Iteration sprudelt das größte Element im angegebenen Array zur letzten Stelle oder zum höchsten Index, genau wie eine Wasserblase zur Wasseroberfläche aufsteigt.
Die Sortierung erfolgt durch Schritt durch alle die Elemente einzeln und vergleichen Sie sie mit dem benachbarten Element und tauschen Sie sie bei Bedarf aus.
HINWEIS: Wenn Sie mit dem Sortieren in der Datenstruktur nicht vertraut sind, sollten Sie fi Erfahren Sie zunächst, was Sortieren bedeutet, um die Grundlagen des Sortierens zu kennen.
Implementieren des Blasensortierungsalgorithmus
Im Folgenden werden die Schritte zum Sortieren von Blasen aufgeführt (zum Sortieren eines bestimmten Arrays in aufsteigender Reihenfolge):
- Beginnen Sie mit dem ersten Element (Index = 0) und vergleichen Sie das aktuelle Element mit dem nächsten Element des Arrays.
- Wenn das aktuelle Element größer als das nächste Element ist Tauschen Sie sie im Array aus.
- Wenn das aktuelle Element kleiner als das nächste Element ist, wechseln Sie zum nächsten Element. Wiederholen Sie Schritt 1.
Betrachten wir ein Array mit den Werten {5, 1, 6, 2, 4, 3}
Nachfolgend haben wir eine Bildliche Darstellung, wie die Blasensortierung das angegebene Array sortiert.
Wie wir in der obigen Darstellung nach dem sehen können Die erste Iteration 6 wird am letzten Index platziert, der die richtige Position dafür darstellt.
Ähnlich nach der zweiten Iteration 5 befindet sich am vorletzten Index usw.
Zeit zum Schreiben des Codes für die Blasensortierung:
Obwohl die obige Logik ein unsortiertes Array sortiert, ist der obige Algorithmus immer noch nicht effizient, da gemäß der obigen Logik die äußere for -Schleife wird 6 Iterationen lang ausgeführt, auch wenn das Array nach der zweiten Iteration sortiert wird.
Wir können also unseren Algorithmus klar optimieren.
Optimierter Blasensortierungsalgorithmus
Um unsere Blase zu optimieren Mit dem Sortieralgorithmus können wir eine flag einführen, um zu überwachen, ob Elemente innerhalb der inneren for -Schleife ausgetauscht werden.
Daher prüfen wir in der inneren for -Schleife jedes Mal, ob ein Austausch von Elementen stattfindet oder nicht.
Wenn für eine bestimmte Iteration kein Austausch erforderlich war Ort bedeutet, dass das Array sortiert wurde und wir aus der for -Schleife springen können, anstatt alle Iterationen auszuführen.
Betrachten wir ein Array mit Werten {11, 17, 18, 26, 23}
Nachfolgend sehen Sie eine bildliche Darstellung, wie die optimierte Blasensortierung das angegebene Array sortiert.
Wie wir sehen können, fand in der ersten Iteration ein Austausch statt, daher haben wir unseren flag -Wert auf 1 Als Ergebnis tritt die Ausführung erneut in die for -Schleife ein. In der zweiten Iteration findet jedoch kein Austausch statt, daher bleibt der Wert von flag 0 und die Ausführung bricht aus der Schleife aus.
Im obigen Code in der Funktion bubbleSort, wenn für a Einzelner vollständiger Zyklus der j -Iteration (innere for -Schleife), es findet kein Austausch statt, dann flag bleibt 0 und dann brechen wir aus den for -Schleifen aus, da das Array bereits sortiert wurde.
Komplexitätsanalyse der Blasensortierung
Bei der Blasensortierung werden im ersten Durchgang n-1 Vergleiche durchgeführt, n-2 im 2. Durchgang, n-3 im 3. Durchgang und so weiter. Die Gesamtzahl der Vergleiche beträgt also
(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1Summe = n (n- 1) /2i.e O (n2)
Daher ist die zeitliche Komplexität der Blasensortierung O (n2).
Der Hauptvorteil der Blasensortierung ist die Einfachheit des Algorithmus.
Die Speicherplatzkomplexität für die Blasensortierung ist O (1), da nur ein einziger zusätzlicher Speicherplatz erforderlich ist, dh für die Variable temp.
Die beste zeitliche Komplexität ist O (n), wenn die Liste bereits sortiert ist.
Nachfolgend sind die zeitliche und räumliche Komplexität für den Blasensortierungsalgorithmus aufgeführt.
Nachdem wir den Blasensortierungsalgorithmus gelernt haben, können Sie auch diese Sortieralgorithmen und ihre Anwendungen überprüfen:
- Einfügesortierung
- Auswahlsortierung
- Schnellsortierung
- Zusammenführungssortierung
- Heap-Sortierung
- Zählsortierung
