Blasensortieralgorithmus mit Python anhand eines Listenbeispiels

Was ist eine Blasensortierung?

Blasensortierung 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 dieser Blase wird sortiert Python-Tutorial Du wirst es lernen:

Implementierung des 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 Folgendeswing 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.

Optimierter Blasensortierungsalgorithmus

Standardmäßig ist der Algorithmus für die Blasensortierung in Python compares 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 Zeit- und Ressourcenverschwendung.

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 wird eingeleitet, bis der Prozess abgeschlossen ist, wie im folgenden Beispiel für die Blasensortierung gezeigt.

Die Optimierung erfolgt mit folgendem Befehlwing Schritte

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

Angesichts einer Liste von fünf Elementen folgt das Folgendewing Bilder veranschaulichen, wie die Blasensortierung die Werte beim Sortieren durchläuft

Die folgendenwing Das Bild zeigt die unsortierte Liste

Visuelle Darstellung

Erste Iteration

Schritt 1)

Visuelle Darstellung

Die Werte 21 und 6 werden verglichen, um zu prüfen, welcher Wert größer als der andere ist.

Visuelle Darstellung

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

Visuelle Darstellung

Unsere geänderte Liste sieht jetzt wie oben aus.

Schritt 2)

Visuelle Darstellung

Die Werte 21 und 9 werden verglichen.

Visuelle Darstellung

21 ist größer als 9, daher vertauschen wir die Positionen von 21 und 9

Visuelle Darstellung

Die neue Liste ist nun wie oben

Schritt 3)

Visuelle Darstellung

Die Werte 21 und 33 werden verglichen, um den größeren Wert zu ermitteln.

Visuelle Darstellung

Der Wert 33 ist größer als 21, daher findet kein Austausch statt.

Schritt 4)

Visuelle Darstellung

Die Werte 33 und 3 werden verglichen, um den größeren Wert zu ermitteln.

Visuelle Darstellung

Der Wert 33 ist größer als 3, daher tauschen wir ihre Positionen.

Visuelle Darstellung

Die sortierte Liste am Ende der ersten Iteration ähnelt der obigen

Zweite Iteration

Die neue Liste nach der zweiten Iteration lautet wie folgt

Visuelle Darstellung

Dritte Iteration

Die neue Liste nach der dritten Iteration lautet wie folgt

Visuelle Darstellung

Vierte Iteration

Die neue Liste nach der vierten Iteration lautet wie folgt

Visuelle Darstellung

Python-Beispiele

Die folgendenwing Code zeigt, wie der Bubble Sort-Algorithmus in Python implementiert wird.

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)

Das Ausführen des obigen Blasensortierprogramms in Python führt zu folgendem Ergebniswing Ergebnisse

[6, 9, 21, 3, 33]

Code Erklärung

Die Erklärung für den Python Bubble Sort-Programmcode lautet wie folgt

Code Erklärung

HIER,

  1. Definiert eine Funktion bubbleSort, die einen Parameter theSeq akzeptiert. Der Code gibt nichts aus.
  2. Ruft die Länge des Arrays ab und weist den Wert einer Variablen n zu. Der Code gibt nichts aus
  3. Startet eine for-Schleife, die den Blasensortierungsalgorithmus (n – 1) Mal ausführt. Dies ist die äußere Schleife. Der Code gibt nichts aus
  4. 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
  5. Startet die innere Schleife, die compares alle Werte in der Liste vom ersten bis zum letzten. Der Code gibt nichts aus.
  6. 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.
  7. Weist den Wert von theSeq[j] einer zeitlichen Variablen tmp zu, wenn die Bedingung „true“ ergibt. Der Code gibt nichts aus
  8. Der Wert von theSeq[j + 1] wird der Position von theSeq[j] zugewiesen. Der Code gibt nichts aus
  9. Der Wert der Variablen tmp wird der Position theSeq[j + 1] zugewiesen. Der Code gibt nichts aus
  10. Der Flag-Variable wird der Wert 1 zugewiesen, um anzuzeigen, dass ein Austausch stattgefunden hat. Der Code gibt nichts aus
  11. Verwendet eine if-Anweisung, um zu prüfen, ob der Wert des Variablenflags 0 ist. Der Code gibt nichts aus
  12. Wenn der Wert 0 ist, rufen wir die Break-Anweisung auf, die die innere Schleife verlässt.
  13. Gibt den Wert von theSeq zurück, nachdem es sortiert wurde. Der Code gibt die sortierte Liste aus.
  14. Definiert eine Variable el, die eine Liste von Zufallszahlen enthält. Der Code gibt nichts aus.
  15. Weist den Wert der Funktion bubbleSort einer Variablen result zu.
  16. Gibt den Wert der Variablen result aus.

Vorteile der Blasensortierung

Die folgendenwing sind einige der Vorteile des Bubble-Sort-Algorithmus

  • 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.

Nachteile der Blasensortierung

Die folgendenwing sind einige der Nachteile des Blasensortierungsalgorithmus

  • 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

Mitplexity-Analyse der Blasensortierung

Es gibt drei Arten von Complexität sind:

1) Sortieren Sie complexity

Die Sorte complexity wird verwendet, um die Menge an Ausführungszeiten und den Platz auszudrücken, die zum Sortieren der Liste benötigt werden. Die Blasensortierung führt (n – 1) Iterationen durch, um die Liste zu sortieren, wobei n die Gesamtzahl der Elemente in der Liste ist.

2) Zeitkomplexity

Die Zeit complexDie Größe der Blasensorte ist O(n2)

Die Zeit complexitä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)
  • I'm besten fall – Dies geschieht, wenn die bereitgestellte Liste bereits sortiert ist. Der Algorithmus führt die minimale Anzahl von Ausführungen durch, die als [Big-Omega] Ω(n)
  • Durchschnittlicher Fall – Dies geschieht, wenn die Liste in zufälliger Reihenfolge vorliegt. Der durchschnittliche ComplexDie Einheit wird als [Big-Theta] ⊝(n) dargestellt2)

3) Weltraumkommunikationplexity

Die Weltraumkommunikationplexity misst den zusätzlichen Platz, der zum Sortieren der Liste benötigt wird. Die Blasensortierung erfordert nur einen (1) zusätzlichen Platz für die zeitliche Variable, die zum Austauschen von Werten verwendet wird. Daher verfügt es über eine Raumkommunikationplexitä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 Blasensortierungsalgorithmus ist mit Python relativ einfach. 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.
  • Die Bubbler-Sorte hat ein Zeitlimitplexität von O (n2) und ein Weltraumkommunikationsgerätplexitä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.