Bubble Sort Algorithmus mit Python Beispiel mit Listenverwendung
Non-Profit Bubble Sortieren?
Bubble Sortieren ist ein Sortieralgorithmus, der zum Sortieren von Listenelementen in aufsteigender Reihenfolge durch den Vergleich zweier benachbarter Werte verwendet wird. Wenn der erste Wert höher als der zweite Wert ist, nimmt der erste Wert die zweite Wertposition ein, während der zweite Wert die erste Wertposition einnimmt. Wenn der erste Wert niedriger als der zweite Wert ist, erfolgt kein Austausch.
Dieser Vorgang wird wiederholt, bis alle Werte einer Liste verglichen und gegebenenfalls ausgetauscht wurden. Jede Iteration wird normalerweise als Durchgang bezeichnet. Die Anzahl der Durchgänge bei einer Blasensortierung entspricht der Anzahl der Elemente in einer Liste minus eins.
In diesem Bubble Sortieren in Python Lernprogramm Du wirst es lernen:
Implementierung der Bubble-Sort-Algorithmus
Wir werden die Implementierung in drei (3) Schritte unterteilen, nämlich das Problem, die Lösung und den Algorithmus, den wir zum Schreiben von Code für jede Sprache verwenden können.
Das Problem
Eine Liste der Artikel wird in zufälliger Reihenfolge bereitgestellt, und wir möchten die Artikel in einer geordneten Art und Weise anordnen
Betrachten Sie die folgende Liste:
[21,6,9,33,3]
Die Lösung
Durchlaufen Sie die Liste, vergleichen Sie zwei benachbarte Elemente und tauschen Sie sie aus, wenn der erste Wert höher als der zweite Wert ist.
Das Ergebnis sollte wie folgt aussehen:
[3,6,9,21,33]
Algorithmus
Der Blasensortierungsalgorithmus funktioniert wie folgt
Schritt 1) Ermitteln Sie die Gesamtzahl der Elemente. Ermitteln Sie die Gesamtzahl der Elemente in der angegebenen Liste
Schritt 2) Bestimmen Sie die Anzahl der durchzuführenden Außendurchgänge (n – 1). Seine Länge beträgt Liste minus eins
Schritt 3) Führen Sie innere Durchgänge (n – 1) Mal für äußeren Durchgang 1 durch. Ermitteln Sie den ersten Elementwert und vergleichen Sie ihn mit dem zweiten Wert. Wenn der zweite Wert kleiner als der erste Wert ist, tauschen Sie die Positionen
Schritt 4) Wiederholen Sie Schritt 3 Durchgänge, bis Sie den äußeren Durchgang erreichen (n – 1). Holen Sie sich das nächste Element in der Liste und wiederholen Sie dann den in Schritt 3 durchgeführten Vorgang, bis alle Werte in der richtigen aufsteigenden Reihenfolge platziert wurden.
Schritt 5) Geben Sie das Ergebnis zurück, wenn alle Durchgänge abgeschlossen sind. Gibt die Ergebnisse der sortierten Liste zurück
Schritt 6) Algorithmus optimieren
Vermeiden Sie unnötige innere Durchgänge, wenn die Liste oder angrenzende Werte bereits sortiert sind. Wenn die bereitgestellte Liste beispielsweise bereits Elemente enthält, die in aufsteigender Reihenfolge sortiert wurden, können wir die Schleife vorzeitig unterbrechen.
Optimiert Bubble-Sort-Algorithmus
Standardmäßig ist der Algorithmus für Bubblesort in Python vergleicht alle Elemente in der Liste, unabhängig davon, ob die Liste bereits sortiert ist oder nicht. Wenn die angegebene Liste bereits sortiert ist, ist der Vergleich aller Werte eine Verschwendung von Zeit und Ressourcen.
Die Optimierung der Blasensortierung hilft uns, unnötige Iterationen zu vermeiden und Zeit und Ressourcen zu sparen.
Wenn beispielsweise das erste und das zweite Element bereits sortiert sind, ist es nicht erforderlich, die restlichen Werte zu durchlaufen. Die Iteration wird beendet und die nächste gestartet, bis der Prozess wie unten gezeigt abgeschlossen ist. Bubble Sortierbeispiel.
Die Optimierung erfolgt mit den folgenden Schritten
Schritt 1) Erstellen Sie eine Flag-Variable, die überwacht, ob in der inneren Schleife ein Austausch stattgefunden hat
Schritt 2) Wenn die Werte die Positionen vertauscht haben, fahren Sie mit der nächsten Iteration fort
Schritt 3) Wenn die Vorteile die Position nicht vertauscht haben, beenden Sie die innere Schleife und fahren Sie mit der äußeren Schleife fort.
Eine optimierte Blasensortierung ist effizienter, da sie nur die notwendigen Schritte ausführt und diejenigen überspringt, die nicht erforderlich sind.
Visuelle Darstellung
Die folgenden Bilder zeigen, wie die Bubblesort-Methode bei der Sortierung der Werte eine Liste mit fünf Elementen durchläuft.
Das folgende Bild zeigt die unsortierte Liste
Erste Iteration
Schritt 1)
Die Werte 21 und 6 werden verglichen, um zu prüfen, welcher Wert größer als der andere ist.
21 ist größer als 6, also nimmt 21 die Position ein, die von 6 eingenommen wurde, während 6 die Position einnimmt, die von 21 eingenommen wurde
Unsere geänderte Liste sieht jetzt wie oben aus.
Schritt 2)
Die Werte 21 und 9 werden verglichen.
21 ist größer als 9, daher vertauschen wir die Positionen von 21 und 9
Die neue Liste ist nun wie oben
Schritt 3)
Die Werte 21 und 33 werden verglichen, um den größeren Wert zu ermitteln.
Der Wert 33 ist größer als 21, daher findet kein Austausch statt.
Schritt 4)
Die Werte 33 und 3 werden verglichen, um den größeren Wert zu ermitteln.
Der Wert 33 ist größer als 3, daher tauschen wir ihre Positionen.
Die sortierte Liste am Ende der ersten Iteration ähnelt der obigen
Zweite Iteration
Die neue Liste nach der zweiten Iteration lautet wie folgt
Dritte Iteration
Die neue Liste nach der dritten Iteration lautet wie folgt
Vierte Iteration
Die neue Liste nach der vierten Iteration lautet wie folgt
Python Beispiele
Der folgende Code zeigt, wie die implementiert wird Bubble Sortieralgorithmus in Python.
def bubbleSort( theSeq ): n = len( theSeq ) for i in range( n - 1 ) : flag = 0 for j in range(n - 1) : if theSeq[j] > theSeq[j + 1] : tmp = theSeq[j] theSeq[j] = theSeq[j + 1] theSeq[j + 1] = tmp flag = 1 if flag == 0: break return theSeq el = [21,6,9,33,3] result = bubbleSort(el) print (result)
Ausführen des obigen Bubblesort-Programms in Python führt zu folgenden Ergebnissen
[6, 9, 21, 3, 33]
Code Erklärung
Die Erklärung für die Python BubblDer Programmcode von e Sort lautet wie folgt
HIER,
- Definiert eine Funktion bubbleSort, die einen Parameter theSeq akzeptiert. Der Code gibt nichts aus.
- Ruft die Länge des Arrays ab und weist den Wert einer Variablen n zu. Der Code gibt nichts aus
- Startet eine for-Schleife, die den Blasensortierungsalgorithmus (n – 1) Mal ausführt. Dies ist die äußere Schleife. Der Code gibt nichts aus
- Definiert eine Flag-Variable, die verwendet wird, um zu bestimmen, ob ein Austausch stattgefunden hat oder nicht. Dies dient Optimierungszwecken. Der Code gibt nichts aus
- Startet die innere Schleife, die alle Werte in der Liste vom ersten bis zum letzten vergleicht. Der Code gibt nichts aus.
- Verwendet die if-Anweisung, um zu prüfen, ob der Wert auf der linken Seite größer ist als der Wert auf der unmittelbar rechten Seite. Der Code gibt nichts aus.
- Weist den Wert von theSeq[j] einer zeitlichen Variablen tmp zu, wenn die Bedingung „true“ ergibt. Der Code gibt nichts aus
- Der Wert von theSeq[j + 1] wird der Position von theSeq[j] zugewiesen. Der Code gibt nichts aus
- Der Wert der Variablen tmp wird der Position theSeq[j + 1] zugewiesen. Der Code gibt nichts aus
- Der Flag-Variable wird der Wert 1 zugewiesen, um anzuzeigen, dass ein Austausch stattgefunden hat. Der Code gibt nichts aus
- Verwendet eine if-Anweisung, um zu prüfen, ob der Wert des Variablenflags 0 ist. Der Code gibt nichts aus
- Wenn der Wert 0 ist, rufen wir die Break-Anweisung auf, die die innere Schleife verlässt.
- Gibt den Wert von theSeq zurück, nachdem es sortiert wurde. Der Code gibt die sortierte Liste aus.
- Definiert eine Variable el, die eine Liste von Zufallszahlen enthält. Der Code gibt nichts aus.
- Weist den Wert der Funktion bubbleSort einer Variablen result zu.
- Gibt den Wert der Variablen result aus.
BubblVorteile von e sort
Im Folgenden sind einige der Vorteile des Bubblesort-Algorithmus aufgeführt
- Es ist leicht zu verstehen
- Es funktioniert sehr gut, wenn die Liste bereits oder fast sortiert ist
- Es ist kein umfangreicher Speicher erforderlich.
- Es ist einfach, den Code für den Algorithmus zu schreiben
- Der Platzbedarf ist im Vergleich zu anderen Sortieralgorithmen minimal.
BubblNachteile der E-Sortierung
Im Folgenden sind einige der Nachteile des Bubblesort-Algorithmus aufgeführt
- Beim Sortieren großer Listen ist die Leistung nicht gut. Es kostet zu viel Zeit und Ressourcen.
- Es wird hauptsächlich für akademische Zwecke und nicht für die reale Anwendung verwendet.
- Die Anzahl der zum Sortieren der Liste erforderlichen Schritte liegt in der Größenordnung n2
Komplexitätsanalyse von Bubble Sortieren
Es gibt drei Arten von Komplexität:
1) Komplexität sortieren
Die Sortierkomplexität wird verwendet, um die Ausführungszeit und den Speicherplatz auszudrücken, die zum Sortieren der Liste erforderlich sind. Beim Bubblesort werden (n – 1) Iterationen zum Sortieren der Liste durchgeführt, wobei n die Gesamtzahl der Elemente in der Liste ist.
2) Zeitliche Komplexität
Die Zeitkomplexität des Bubblesort beträgt O(n2)
Die zeitlichen Komplexitäten können wie folgt kategorisiert werden:
- Schlimmsten Fall – hier erfolgt die Auflistung in absteigender Reihenfolge. Der Algorithmus führt die maximale Anzahl von Ausführungen durch, die als [Big-O] O(n) ausgedrückt wird2)
- bester Fall – dies tritt auf, wenn die bereitgestellte Liste bereits sortiert ist. Der Algorithmus führt die Mindestanzahl von Ausführungen durch, die als [Big-Omega] Ω(n) ausgedrückt wird.
- Durchschnittlicher Fall – dies tritt auf, wenn die Liste in zufälliger Reihenfolge ist. Die durchschnittliche Komplexität wird dargestellt als [Big-theta] ⊝(n2)
3) Raumkomplexität
Die Speicherkomplexität misst die Menge an zusätzlichem Speicherplatz, die zum Sortieren der Liste benötigt wird. Der Bubblesort benötigt nur einen (1) zusätzlichen Speicherplatz für die Zeitvariable, die zum Austauschen von Werten verwendet wird. Daher hat er eine Speicherkomplexität von O (1).
Zusammenfassung
- Der Blasensortierungsalgorithmus funktioniert, indem er zwei benachbarte Werte vergleicht und sie vertauscht, wenn der Wert links kleiner als der Wert rechts ist.
- Die Implementierung eines Bubblesort-Algorithmus ist relativ einfach mit Python. Sie müssen lediglich for-Schleifen und if-Anweisungen verwenden.
- Das Problem, das der Blasensortierungsalgorithmus löst, besteht darin, eine zufällige Liste von Elementen in eine geordnete Liste umzuwandeln.
- Der Blasensortierungsalgorithmus in der Datenstruktur erzielt die beste Leistung, wenn die Liste bereits sortiert ist, da er nur eine minimale Anzahl von Iterationen durchführt.
- Der Blasensortierungsalgorithmus funktioniert nicht gut, wenn die Liste in umgekehrter Reihenfolge vorliegt.
- Der Bubblersort hat eine Zeitkomplexität von O (n2) und einer Raumkomplexität von O (1)
- Der Bubbler-Sortieralgorithmus eignet sich am besten für akademische Zwecke und nicht für reale Anwendungen.
- Die optimierte Blasensortierung macht den Algorithmus effizienter, indem unnötige Iterationen bei der Überprüfung bereits sortierter Werte übersprungen werden.