Bubble Sort Algorithmus mit Python Beispiel mit Listenverwendung

Non-Profit Bubble Sortieren?

Bubble Sortieren Der Algorithmus ordnet Listenelemente aufsteigend, indem er zwei benachbarte Werte vergleicht. Ist der erste Wert größer als der zweite, rückt der erste Wert an die Stelle des zweiten und umgekehrt. Ist der erste Wert kleiner als der zweite, findet kein Tausch statt.ping erledigt.

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 Bubble Sortieren in Python Lernprogramm Sie lernen das Problem kennen, das es löst, seine optimierte Form, eine schrittweise visuelle Anleitung und ein funktionierendes Beispiel. Python Programm und seine Leistungsmerkmale.

Implementierung der Bubble-Sort-Algorithmus

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

Das Problem

Eine Liste von Gegenständen ist in zufälliger Reihenfolge gegeben, und wir möchten die Gegenstände in eine geordnete Reihenfolge bringen.

Betrachten Sie die folgende Liste:

[21, 6, 9, 33, 3]

Die Lösung

Iteriere durch die Liste, vergleiche zwei benachbarte Elemente und tausche sie aus.ping sie, wenn der erste Wert höher ist als der zweite Wert.

Das Ergebnis sollte wie folgt aussehen:

[3, 6, 9, 21, 33]

Algorithmus

Der Bubble-Sort-Algorithmus funktioniert wie folgt:

Schritt 1) Ermitteln Sie die Gesamtanzahl der Elemente. Ermitteln Sie die Gesamtanzahl der Einträge in der gegebenen Liste.

Schritt 2) Bestimme die Anzahl der äußeren Durchläufe (n – 1). Ihre Länge ist die Liste minus eins.

Schritt 3) Führe den inneren Durchlauf (n – 1) Mal für den ersten äußeren Durchlauf aus. Ermittle den Wert des ersten Elements und vergleiche ihn mit dem Wert des zweiten Elements. Ist der zweite Wert kleiner als der erste, vertausche die Positionen.

Schritt 4) Wiederhole Schritt 3, bis du den äußersten Durchlauf (n – 1) erreicht hast. Nimm das nächste Element der Liste und wiederhole dann den Vorgang aus Schritt 3, bis alle Werte in der korrekten aufsteigenden Reihenfolge angeordnet sind.

Schritt 5) Gib das Ergebnis zurück, sobald alle Durchläufe abgeschlossen sind. Gib 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 in folgenden Schritten:

Schritt 1) Erstelle eine Flag-Variable, die überwacht, ob ein Tauschvorgang stattfindet.ping ist in der inneren Schleife aufgetreten.

Schritt 2) Wenn die Werte ihre Positionen getauscht haben, fahre mit der nächsten Iteration fort.

Schritt 3) Falls die Werte ihre Positionen nicht getauscht 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 veranschaulichen, wie der Bubble-Sort-Algorithmus die Werte einer Liste von fünf Elementen durchläuft, um sie zu sortieren.

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.

Da 21 größer als 6 ist, nimmt 21 die Position ein, die zuvor von 6 besetzt war, während 6 die Position einnimmt, die zuvor 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 sieht nun wie oben aus.

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 kein Tausch.ping stattfindet.

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 sieht aus wie die obige.

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:

[3, 6, 9, 21, 33]

Code Erläuterung

Die Erklärung für die Python BubblDer Programmcode für e Sort lautet wie folgt:

HIER,

1. Definiert eine Funktion bubbleSort, die einen Parameter theSeq akzeptiert. Der Code gibt nichts aus.
2. Ermittelt die Länge des Arrays und weist den Wert einer Variablen n zu. Der Code gibt nichts aus.
3. Es wird eine for-Schleife gestartet, die den Bubble-Sort-Algorithmus (n – 1) Mal ausführt. Dies ist die äußere Schleife. Der Code gibt keine Ausgabe aus.
4. Definiert eine Flag-Variable, die angibt, ob ein Tausch stattgefunden hat oder nicht. Dies dient der Optimierung. Der Code gibt keine Ausgabe 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 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 der temporären Variable tmp den Wert von theSeq[j] zu, falls die Bedingung als wahr ausgewertet wird. Der Code gibt keine Ausgabe aus.
8. Der Wert von theSeq[j + 1] wird der Position theSeq[j] zugewiesen. Der Code gibt keine Ausgabe aus.
9. Der Wert der Variablen tmp wird der Position theSeq[j + 1] zugewiesen. Der Code gibt nichts aus.
10. Der Flag-Variablen wird der Wert 1 zugewiesen, um anzuzeigen, dass ein Tausch stattgefunden hat. Der Code gibt keine Ausgabe aus.
11. Verwendet eine if-Anweisung, um zu prüfen, ob der Wert der Variablen flag 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.

BubblVorteile von e sort

Im Folgenden werden einige Vorteile des Bubble-Sort-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 werden einige Nachteile des Bubble-Sort-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 Anwendungen in der realen Welt verwendet.
• Die Anzahl der zum Sortieren der Liste erforderlichen Schritte liegt in der Größenordnung n².

Komplexitätsanalyse von Bubble Sortieren

Es gibt drei Arten von Komplexität:

1) Komplexität sortieren

Die Sortierkomplexität gibt an, wie viel Zeit und Speicherplatz zum Sortieren einer Liste benötigt werden. Der Bubblesort-Algorithmus benötigt (n – 1) Iterationen, um die Liste zu sortieren, wobei n die Gesamtzahl der Elemente in der Liste ist.

2) Zeitliche Komplexität

Die Zeitkomplexität des Bubblesort beträgt O(n²).

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 wird²).
• bester Fall Dies tritt auf, wenn die bereitgestellte Liste bereits sortiert ist. Der Algorithmus führt die minimale Anzahl an 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) dargestellt.²).

3) Raumkomplexität

Die Speicherkomplexität misst den zusätzlichen Speicherplatz, der zum Sortieren der Liste benötigt wird. Der Bubblesort benötigt lediglich einen (1) zusätzlichen Speicherplatz für die temporäre Variable, die zum Vertauschen verwendet wird.ping Daher hat es eine Speicherkomplexität von O(1).

Häufig gestellte Fragen