Bubble-Sort-Python
Python-Funktionen und -Methoden
Michael Zippo
31.10.2021
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:
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:
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:
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:
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.
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.
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:
Wenn wir unser Programm mit dieser uberarbeiteten Codezeile ausfuhren, wird Folgendes zuruckgegeben:
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!"
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.
