Bubble-Sort-Python

Eine Python-Blasensortierung durchläuft eine Liste und vergleicht Elemente nebeneinander. Ist ein Element rechts größer als eins links, werden die Elemente vertauscht. Dies geschieht, bis die Liste sortiert ist.

Mussen Sie eine Liste sortieren? Die Bubble-Sorte hat Ihnen den Rucken frei. Die Blasensortierung ist eine Art Standardalgorithmus, der Listen sortiert. Es ist vielleicht die einfachste Sortierung auf dem Markt, also perfekt fur Anfänger, die mit Sortieralgorithmen noch nicht vertraut sind!

In diesem Leitfaden besprechen wir, wie Bubble-Sortierungen funktionieren und wie Sie einen Python-Bubble-Sort-Algorithmus implementieren können. Wir gehen ein Beispiel durch, damit Sie verstehen, wie jeder Teil einer Blasensortierung funktioniert.

Python-Blasensortierungen

Eine Blasensortierung vergleicht Paare benachbarter Elemente und tauscht diese Elemente aus, wenn sie sind nicht in ordnung. Es wird häufig in Python implementiert, um Listen mit unsortierten Zahlen zu sortieren. Blasensortierungen sind ein Standardalgorithmus der Informatik.

Durch die Verwendung einer Blasensortierung können Sie Daten entweder in aufsteigender oder absteigender Reihenfolge sortieren. Ausgehend vom ersten Element in einer Liste vergleicht eine Blasensortierung das erste und das zweite Element. Ist das erste Element größer als das zweite, erfolgt ein Tausch.

Dieser Vorgang wird wiederholt, bis jedes Element in einer Liste uberpruft ist. Dann durchläuft eine Blasensortierung die Liste erneut. Dies geschieht, bis keine weiteren Swaps mehr durchgefuhrt werden mussen.

Wann sollten Sie eine Bubble-Sortierung in Python verwenden?

Bubble-Sorts sind eine gute Sortiermethode, wenn Sie gerade erst anfangen um mehr uber Sortieralgorithmen zu erfahren. Eine Blasensortierung ist eine einfache Möglichkeit, eine Liste von Elementen zu sortieren, die nicht in der richtigen Reihenfolge angezeigt werden.

Blasensortierungen funktionieren am besten, wenn Sie eine Liste mit nur wenigen Objekten haben. Denn wenn eine Bubble-Sortierung nur wenige Vergleiche anstellen muss, geht sie sehr schnell. Wenn Sie eine größere Liste sortieren mussen, können Sie effizientere Algorithmen verwenden. Die meisten Entwickler wurden sich fur eine Methode wie die Einfugungssortierung entscheiden, um eine längere Liste von Elementen zu sortieren.

81 % der Teilnehmer gaben an, dass sie sich nach dem Besuch eines Bootcamps hinsichtlich ihrer Aussichten auf einen technischen Job sicherer fuhlten. Lassen Sie sich noch heute in ein Bootcamp einweisen.

Der durchschnittliche Bootcamp-Absolvent verbrachte weniger als sechs Monate mit dem Karrierewechsel, vom Beginn eines Bootcamps bis zur Suche nach seinem ersten Job.

Lass uns in die Unkraut und fangen Sie an, durch die Funktionsweise einer Blasensortierung zu gehen. Wir beginnen mit der folgenden Liste, deren Elemente in der falschen Reihenfolge erscheinen:

719412

Unsere Blasensortierung beginnt mit dem Vergleich des ersten und zweiten Elements in unserer Liste das erste Element größer als das zweite ist, dann tauschen wir diese beiden Elemente aus.

In diesem Beispiel vergleichen wir 7 und 19. 7 ist nicht größer als 19, also bleibt es an der gleichen Stelle Unsere Liste sieht jetzt genauso aus wie zuvor:

7 19412

Wir werden nun das zweite und dritte Element in vergleichen unsere Liste. 19 ist größer als 4. Das bedeutet, dass wir sie austauschen mussen. Unsere Liste sieht jetzt so aus:

741912

Wir können jetzt die dritte vergleichen und vierte Elemente in unserer Liste. 19 ist größer als 12, also tauschen wir die beiden Zahlen aus:

741219

Das Ende einer Liste erreichen

Unsere Liste sieht bereits sortiert aus. Aber wir sind am Ende unserer Liste angelangt und sie ist nicht sortiert. Was ist los? Blasensortierungen durchlaufen eine Liste mehrfach, d. h. sie werden so lange ausgefuhrt, bis jedes Element in einer Liste sortiert ist.

Unsere Blasensortierung beginnt wieder von vorne, bis die Liste sortiert ist. Wir rufen jedes Mal, wenn die Liste beginnt, Werte von vorne zu sortieren, einen Durchgang auf. In diesem Beispiel vergleicht unsere Blasensortierung 7 und 4. 7 ist größer als 4, also tauschen wir die Elemente aus:

Unser Algorithmus vergleicht 7 und 12. Es ist kein Tausch erforderlich, also machen wir weiter . Wir vergleichen 12 und 19. Auch hier ist kein Tausch erforderlich. Jetzt, da wir das Ende unserer Liste erreicht haben, ist klar, dass keine weiteren Swaps mehr getätigt werden mussen.

Haben Sie bemerkt, dass unser Algorithmus auch nach dem Sortieren unserer Liste weiterlief? Das liegt daran, dass bei einer Blasensortierung weiterhin Elemente ausgetauscht werden, bis jedes Element in einer Liste mit jedem Element in der Liste verglichen wird. Unser Algorithmus wird nicht aufhören, bis jeder Tausch stattgefunden hat.

Bubble Sort Python-Programm

Bisher haben wir Zahlen in einer Tabelle getauscht. Es stimmt, dass wir es geschafft haben, unsere Liste zu sortieren, aber wir mussen dies nicht manuell tun. Bubble-Sorts sind schließlich ein Rechenalgorithmus; Lassen Sie uns den Algorithmus von einem Computer ausfuhren.

Beginnen Sie mit dem Schreiben einer Python-Funktion, die eine Liste von Zahlen in aufsteigender Reihenfolge sortiert:

Unser Algorithmus beginnt mit einer for-Schleife. Diese Schleife durchläuft jedes Element in unserem Array. Dann verwenden wir eine weitere for-Schleife, um alle Elemente in unserem Array miteinander zu vergleichen.

In unserem Code haben wir eine Python "if‚"-Anweisung definiert, die uberpruft, ob ein bestimmtes Element gr√∂√üer ist als das n√§chste Element in Diese "if‚"-Anweisung fuhrt Vergleiche durch wie:

  • Ist das erste Element in t ie Liste gr√∂√üer als das zweite?
  • Ist das zweite Element in der Liste gr√∂√üer als das dritte?

Unser Code ist noch nicht fertig. Wenn Sie versuchen, das obige Python-Programm auszufuhren, passiert nichts. Wir mussen unsere Funktion aufrufen und ihr einige Daten geben:

Unser Code gibt zuruck:

Wir haben es geschafft! Unser Python-Array ist aufsteigend sortiert! Sie k√∂nnen eine Blasensortierung verwenden, um eine Liste in absteigender Reihenfolge zu sortieren. Tauschen Sie dazu das Gr√∂√üer-als-Zeichen durch ein Kleiner-als-Zeichen in der Python-Datei "if‚" Anweisung:

Wenn wir unser Programm mit dieser uberarbeiteten Codezeile ausfuhren, wird Folgendes zuruckgegeben:

Optimierung der Blasensortierung

Fruher wir haben daruber gesprochen, wie jeder mögliche Vergleich gemacht wird, auch wenn unsere Liste sortiert ist. Dies macht unsere Bubble-Sortierung ziemlich ineffizient: Sie läuft auch nach dem Sortieren der Liste weiter.

"Karrierekarma trat in mein Leben ein, als ich es am dringendsten brauchte und half mir schnell bei einem Bootcamp. Zwei Monate nach meinem Abschluss fand ich meinen Traumjob, der meinen Werten und Lebenszielen entsprach!"

p>

Venus, Software Engineer bei Rockbot

Obwohl es in diesem Beispiel keinen großen Unterschied macht, könnte sich dies im Maßstab auf die Ausfuhrungszeit auswirken eines Programms. Hier kommt die optimierte Blasensortierung ins Spiel.

Wir können unsere Blasensortierung optimieren, indem wir eine neue Variable schreiben. Nennen wir es Swap. Diese Variable verfolgt, ob in einer Python for-Schleife. Wenn diese Variable auf false gesetzt ist, bedeutet dies, dass unsere Liste sortiert ist. Es mussen keine Iterationen mehr passieren.

√úberarbeiten wir unsere sortList-Funktion von fruher:

Wir haben eine Variable namens swap definiert, die den Standardwert True hat. Dies ist in unserer ersten for-Schleife enthalten, da sie verfolgt, ob ein Swap bei jedem Durchlauf durch die Liste aufgetreten ist. Wenn unser Array einen Vergleich durchfuhrt, wird der Wert von swap auf False gesetzt.

Wenn beim letzten Swap kein Tausch durchgefuhrt wurde, dann ist das Array bereits sortiert. Unsere Liste pruft dann, ob swap gleich True ist s, wird unser Programm nicht mehr ausgefuhrt.

Lassen Sie unseren Code erneut ausfuhren:

Unsere Daten wurden auf die gleiche Weise sortiert, aber unser Algorithmus ist jetzt schneller und effizienter. Unser Algorithmus stoppt jetzt, sobald alle Elemente in der Liste sortiert wurden.

Komplexitätsanalyse

Die durchschnittliche Zeitkomplexität der Blasensortierung beträgt O(n^2). Dies passiert, wenn die Elemente in einem Array unsortiert sind.

Im schlimmsten Fall wird eine Blasensortierung bei O(n^2) durchgefuhrt. Dies geschieht, wenn ein Array bereits in aufsteigender oder absteigender Reihenfolge vorliegt und umgekehrt sortiert werden muss. Im besten Fall wird dieser Algorithmus bei O(n) ausgefuhrt. Dies passiert, wenn ein Array bereits sortiert ist.

Weitere Informationen zur Algorithmuskomplexität finden Sie in unserem Karriere-Karma Big O Notation-Leitfaden.

Schlussfolgerung

Blasensortierungen bieten eine einfache Möglichkeit, eine Liste von Daten zu sortieren. Sie können verwendet werden, um Daten in aufsteigender oder absteigender Reihenfolge zu sortieren.

Dieser Algorithmus wird am häufigsten verwendet, wenn Sie eine kleine Liste sortieren mussen. Bubble-Sorts sind eine gute Einfuhrung in Sortieralgorithmen. Sie können sie verwenden, um sich mit Algorithmen vertraut zu machen, bevor Sie sich mit fortgeschritteneren Sortiermethoden, wie z. /how-to-learn-python/">Anleitung zum Erlernen von Python.