Blasensortierungsalgorithmus mit Python unter Verwendung des Listenbeispiels

Inhaltsverzeichnis:

Anonim

Was ist eine Blasensorte?

Bubble Sort ist ein Sortieralgorithmus, mit dem Listenelemente in aufsteigender Reihenfolge sortiert werden, indem zwei benachbarte Werte verglichen werden. 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, wird kein Austausch durchgeführt.

Dieser Vorgang wird wiederholt, bis alle Werte in einer Liste verglichen und gegebenenfalls ausgetauscht wurden. Jede Iteration wird normalerweise als Pass bezeichnet. Die Anzahl der Durchgänge in einer Blasensortierung entspricht der Anzahl der Elemente in einer Liste minus eins.

In diesem Tutorial zum Sortieren von Blasen in Python lernen Sie:

  • Was ist eine Blasensorte?
  • Implementierung des Blasensortierungsalgorithmus
  • Optimierter Blasensortierungsalgorithmus
  • Visuelle Darstellung
  • Python-Beispiele
  • Code Erklärung
  • Vorteile der Blasensortierung
  • Blasensortierung Nachteile
  • Komplexitätsanalyse der Blasensortierung

Implementierung des Blasensortierungsalgorithmus

Wir werden die Implementierung in drei (3) Schritte aufteilen, nämlich das Problem, die Lösung und den Algorithmus, mit dem wir Code für jede Sprache schreiben können.

Das Problem

Eine Liste der Artikel wird in zufälliger Reihenfolge angegeben, und wir möchten die Artikel in einer geordneten Reihenfolge anordnen

Betrachten Sie die folgende Liste:

[21,6,9,33,3]

Die Lösung

Durchlaufen Sie die Liste, indem Sie zwei benachbarte Elemente vergleichen und austauschen, wenn der erste Wert höher als der zweite Wert ist.

Das Ergebnis sollte wie folgt sein:

[3,6,9,21,33]

Algorithmus

Der Blasensortierungsalgorithmus funktioniert wie folgt

Schritt 1) Ermitteln Sie die Gesamtzahl der Elemente. Holen Sie sich die Gesamtzahl der Elemente in der angegebenen Liste

Schritt 2) Bestimmen Sie die Anzahl der durchzuführenden äußeren Durchgänge (n - 1). Seine Länge ist Liste minus eins

Schritt 3) Führen Sie die inneren Durchgänge (n - 1) für den ä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 aus

Schritt 4) Wiederholen Sie Schritt 3, bis Sie den äußeren Durchgang (n - 1) erreichen. Holen Sie sich das nächste Element in die Liste und wiederholen Sie 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 benachbarte Werte bereits sortiert sind. Wenn die bereitgestellte Liste beispielsweise bereits Elemente enthält, die in aufsteigender Reihenfolge sortiert wurden, können wir die Schleife frühzeitig unterbrechen.

Optimierter Blasensortierungsalgorithmus

Standardmäßig vergleicht der Algorithmus für die Blasensortierung in Python 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.

Durch die Optimierung der Blasensortierung können wir unnötige Iterationen vermeiden und Zeit und Ressourcen sparen.

Wenn beispielsweise das erste und das zweite Element bereits sortiert sind, müssen die restlichen Werte nicht durchlaufen werden. Die Iteration wird beendet und die nächste wird gestartet, bis der Vorgang abgeschlossen ist, wie im folgenden Beispiel für die Blasensortierung gezeigt.

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 Positionen 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 erforderlichen Schritte ausführt und diejenigen überspringt, die nicht erforderlich sind.

Visuelle Darstellung

Bei einer Liste von fünf Elementen veranschaulichen die folgenden Bilder, wie die Blasensortierung beim Sortieren durch die Werte iteriert

Das folgende Bild zeigt die unsortierte Liste

Erste Iteration

Schritt 1)

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

21 ist größer als 6, also nimmt 21 die Position ein, die von 6 besetzt ist, während 6 die Position einnimmt, die von 21 besetzt war

Unsere geänderte Liste sieht jetzt wie oben aus.

Schritt 2)

Die Werte 21 und 9 werden verglichen.

21 ist größer als 9, also tauschen wir die Positionen von 21 und 9

Die neue Liste ist jetzt wie oben

Schritt 3)

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

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 zu finden.

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

Die sortierte Liste am Ende der ersten Iteration entspricht 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 der Bubble Sort-Algorithmus in Python implementiert wird.

def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)

Das Ausführen des obigen Blasensortierprogramms in Python führt zu den folgenden Ergebnissen

[6, 9, 21, 3, 33]

Code Erklärung

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

HIER,

  1. Definiert eine Funktion bubleSort, 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, mit der bestimmt wird, ob ein Swap stattgefunden hat oder nicht. Dies dient Optimierungszwecken. Der Code gibt nichts aus
  5. Startet die innere Schleife, die alle Werte in der Liste vom ersten bis zum letzten vergleicht. Der Code gibt nichts aus.
  6. Verwendet die if-Anweisung, um zu überprüfen, ob der Wert auf der linken Seite größer ist als der auf der unmittelbaren rechten Seite. Der Code gibt nichts aus.
  7. Weist den Wert von theSeq [j] einer zeitlichen Variablen tmp zu, wenn die Bedingung als wahr ausgewertet wird. 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 zugewiesen, um die Sequenz [j + 1] zu positionieren. Der Code gibt nichts aus
  10. Der Flag-Variablen wird der Wert 1 zugewiesen, um anzuzeigen, dass ein Swap stattgefunden hat. Der Code gibt nichts aus
  11. Verwendet eine if-Anweisung, um zu überprü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 aus der inneren Schleife austritt.
  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 einem variablen Ergebnis den Wert der Funktion bubleSort zu.
  16. Druckt den Wert des variablen Ergebnisses.

Vorteile der Blasensortierung

Im Folgenden sind einige der Vorteile des Blasensortierungsalgorithmus aufgeführt

  • Es ist leicht zu verstehen
  • Es funktioniert sehr gut, wenn die Liste bereits oder fast sortiert ist
  • Es benötigt keinen umfangreichen Speicher.
  • Es ist einfach, den Code für den Algorithmus zu schreiben
  • Der Platzbedarf ist im Vergleich zu anderen Sortieralgorithmen minimal.

Blasensortierung Nachteile

Das Folgende sind einige der Nachteile des Blasensortierungsalgorithmus

  • Es funktioniert nicht gut beim Sortieren großer Listen. Es kostet zu viel Zeit und Ressourcen.
  • Es wird hauptsächlich für akademische Zwecke verwendet und nicht für die reale Anwendung.
  • Die Anzahl der zum Sortieren der Liste erforderlichen Schritte liegt in der Reihenfolge n 2

Komplexitätsanalyse der Blasensortierung

Es gibt drei Arten von Komplexität:

1) Komplexität sortieren

Die Sortierkomplexität wird verwendet, um die Anzahl der Ausführungszeiten und den Speicherplatz auszudrücken, die zum Sortieren der Liste erforderlich sind. Die Blasensortierung führt (n - 1) Iterationen durch, um die Liste zu sortieren, wobei n die Gesamtzahl der Elemente in der Liste ist.

2) Zeitliche Komplexität

Die zeitliche Komplexität der Blasensortierung beträgt O (n 2 )

Die zeitlichen Komplexitäten können wie folgt eingeteilt werden:

  • Schlimmster Fall - hier ist die Liste in absteigender Reihenfolge. Der Algorithmus führt die maximale Anzahl von Ausführungen aus, die als [Big-O] O (n 2 ) ausgedrückt wird.
  • Bester Fall - Dies tritt auf, wenn die bereitgestellte Liste bereits sortiert ist. Der Algorithmus führt die minimale Anzahl von Ausführungen durch, die als [Big-Omega] Ω (n) ausgedrückt wird.
  • Durchschnittlicher Fall - Dies tritt auf, wenn die Liste in zufälliger Reihenfolge vorliegt. Die durchschnittliche Komplexität wird als [Big-Theta] ⊝ (n 2 ) dargestellt.

3) Raumkomplexität

Die Speicherplatzkomplexität misst die Menge an zusätzlichem Speicherplatz, der zum Sortieren der Liste benötigt wird. Die Blasensortierung benötigt nur einen (1) zusätzlichen Platz für die zeitliche Variable, die zum Austauschen von Werten verwendet wird. Daher hat es eine Raumkomplexität von O (1).

Zusammenfassung

  • Der Blasensortierungsalgorithmus vergleicht zwei benachbarte Werte und tauscht sie aus, 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 Blasensortieralgorithmus löst, besteht darin, eine zufällige Liste von Elementen in eine geordnete Liste umzuwandeln.
  • Der Blasensortierungsalgorithmus in der Datenstruktur funktioniert am besten, wenn die Liste bereits sortiert ist, da er eine minimale Anzahl von Iterationen ausführt.
  • Der Blasensortierungsalgorithmus funktioniert nicht gut, wenn die Liste in umgekehrter Reihenfolge ist.
  • Die Bubbler-Sortierung hat eine zeitliche Komplexität von O (n 2 ) und eine räumliche Komplexitä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 übersprungen werden, wenn bereits sortierte Werte überprüft werden.