© Oselote/Shutterstock.com
Der Bubble-Sort-Algorithmus ist ein Beispiel für einen einfachen Sortieralgorithmus. Diese Art von Algorithmus ordnet Zeichen, Zeichenfolgen oder Zahlen in einer bestimmten Reihenfolge an, die durch das Problem bestimmt wird, das Sie mit Ihrem Code lösen.
Eine Sortierung ist oft nützlich, wenn Sie Elemente alphabetisch oder in numerischer Reihenfolge anordnen möchten. Sortieralgorithmen sind ein entscheidender Teil des Programmierens, und die Blasensortierung ist aufgrund ihrer Einfachheit bei Schülern beliebt. Es ist jedoch nicht die beste Wahl, wenn Sie eine schnelle Leistung benötigen.
Wenn Sie mehr über den Bubble-Sort-Algorithmus und seine Funktionsweise erfahren möchten, sind Sie hier genau richtig. Der heutige Artikel wird aufschlüsseln, wie der Bubble-Sort-Algorithmus funktioniert, und Ihnen zeigen, wie Sie ihn implementieren. Fangen wir an!
Was ist der Bubble Sort-Algorithmus?
Sortieralgorithmen geben Ihnen eine Möglichkeit, Daten logisch darzustellen, wenn Sie Ihren Code ausführen. Wenn Sie das Programmieren lernen, ist Bubble Sort einer der ersten Algorithmen, die Sie lernen werden, da Sie damit visualisieren können, wie ein Sortieralgorithmus auf grundlegender Ebene funktioniert.
Der Bubble-Sort-Algorithmus ist einzigartig, da er nur zwei benachbarte Datensätze vergleichen kann. Es bewegt sich durch das gesamte Array, Wörterbuch, Liste oder String und vergleicht jedes Element und sortiert alles nach Ihren Anforderungen.
Der Algorithmus
Bevor wir untersuchen, wie man eine Blasensortierung erstellt Schauen wir uns in Ihrem Code Schritt für Schritt an, wie es funktioniert:
Zuerst würden wir eine Sammlung von Daten identifizieren, die sortiert werden müssen. Dies kann eine Sammlung von Zahlen, Wörtern oder Buchstaben sein, die Sie auf eine bestimmte Weise anordnen möchten. Eine übliche Funktion einer Blasensortierung wäre, eine Liste von Zahlen zu nehmen und sie nach ihrem Wert zu ordnen, entweder vom niedrigsten zum höchsten oder vom höchsten zum niedrigsten. Der Algorithmus beginnt beim ersten Element in einer Liste, das wären die Daten bei Index 0 Es vergleicht diese Daten mit den Daten bei Index 1, um festzustellen, ob ein Wechsel erforderlich ist.Wenn ein Wechsel vorgenommen wird, haben wir ein Flag, das wir setzen, das es uns ermöglicht, den Algorithmus zu verlassen, um ihn effizienter zu machen Index 1 bis Index 2, und er fährt durch die Liste fort, bis er das Ende erreicht. Sobald der Algorithmus einmal durchlaufen wurde, muss er den Prozess erneut durchlaufen, da er nicht abgeschlossen ist, bis keine Änderungen mehr vorgenommen werden müssen. Dies wird normalerweise mit verschachtelten Schleifen erreicht, die eine Blasensortierung durch die gesamte Liste ausführen, bis eine Bedingung, die auf dem Flag operiert, beendet wird, sobald wir eine vollständige Iteration ohne Änderungen durchlaufen haben. Sobald diese verschachtelten Schleifen ausgeführt wurden, wird die sortierte Liste ausgeführt in der vorgesehenen Reihenfolge sein, damit Sie es auf dem Bildschirm anzeigen oder für weitere Operationen in Ihrem Code verwenden können. 
Der Bubblesort-Algorithmus wird mit einem Diagramm veranschaulicht.
©Von Stefano furin – Eigene Arbeit, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=37141358
Funktionsweise des Bubble-Sort-Algorithmus
Nun, da wir die Logik des Bubble-Sort-Algorithmus behandelt haben, lassen Sie uns tiefer in ein Beispiel eintauchen. Wir nehmen eine Liste mit Zahlen, die nicht in der richtigen Reihenfolge sind, und lassen sie vom Bubble Sort in aufsteigender Reihenfolge anordnen.
Um es einfach zu machen, verwenden wir eine Liste mit vier Zahlen:
29, 15, 0,-5
Die erste Berechnung, die die Blasensortierung durchführen würde, wäre die Überprüfung der Werte von Index 0 und Index 1, wie wir oben besprochen haben. Da 29 größer als 15 ist, tauschen sich ihre Positionen und geben uns diese Zahlenfolge:
15, 29, 0,-5
Als Nächstes vergleicht der Algorithmus 29 und 0. Hier ist die resultierende Liste:
15, 0, 29,-5
Beim letzten Mal durch diese erste Iteration vergleicht der Algorithmus 29 mit-5 und gibt uns diese Liste:
15, 0,-5, 29
Unsere Liste ist nicht ganz dort, wo wir sie brauchen, und die nächste Iteration wird uns helfen, das zu sortieren. Wir werden sehen, dass sich die Liste wie folgt ändert:
0, 15,-5, 29
0,-5, 15, 29
0,-5, 15, 29
0,-5, 15, 29
Dann würde uns die dritte Iteration dieses Ergebnis liefern:
-5, 0, 15 , 29
-5, 0, 15, 29
-5, 0, 15, 29
-5, 0, 15, 29
Da die Liste nun vollständig sortiert ist, brauchen wir eine Möglichkeit, der Schleife mitzuteilen, dass sie die Ausführung beenden soll. Dies soll es effizienter machen. Dazu verwenden wir normalerweise eine boolesche Variable zusammen mit einigen bedingten Anweisungen, damit der Algorithmus aus der Schleife ausbrechen kann, sobald keine Änderungen vorgenommen wurden.
Implementierung des Bubble Sort-Algorithmus mit einer For-Schleife
Lassen Sie uns nun etwas Code für den Bubble-Sort-Algorithmus in Python werfen, um ein gutes Verständnis dafür zu bekommen, wie er als Sortiermethode funktioniert. So würden wir es mit einer for-Schleife implementieren:
def bubbleSort (numArray, z): for a in range(z-1): swap=False for b in range (0, z-a-1): if numArray[b] > numArray[b+1]: swap=True numArray[b], numArray[b+1]=numArray[b+1], numArray[b] wenn nicht swap: return numArray numberArray=[82, 67 , 0,-500,-80, 99, 2] x=len(numberArray) print (“Sorted Array:”) print (bubbleSort(numberArray, x))
Erklärung des Codes
Lassen Sie uns diesen Code Schritt für Schritt aufschlüsseln, damit wir verstehen können, was vor sich geht.
Initialisieren des Arrays
Zuerst müssen wir unser Array mit einer Reihe von Zahlen initialisieren, die wir möchte sortieren (numberArray). Diese werden absichtlich in zufälliger Reihenfolge initialisiert, um zu demonstrieren, wie der Bubble-Sort-Algorithmus funktioniert. Als Nächstes initialisieren wir eine Variable, die die Anzahl der Elemente enthält, die wir im Array (x) haben. Wir werden diese Variable später verwenden, um zu steuern, wie oft wir die Schleife durchlaufen.
Den Bubble Sort-Algorithmus definieren
Zwei Werte werden an den Algorithmus übergeben, der als bubbleSort definiert ist. Der erste Wert ist das Array selbst. Dann übergeben wir auch die Länge des Arrays. Innerhalb des Algorithmus werden diese als numArray bzw. z neu zugewiesen.
Die Schleife, die wir verwenden, um die Blasensortierung auszuführen, wird eine bestimmte Anzahl von Malen durchlaufen, aber es ist nicht immer notwendig, dass sie ihren Lauf nimmt. Also müssen wir zuerst eine boolesche Variable am Anfang der äußeren for-Schleife einrichten, die sich in der inneren Schleife von False zu True ändert, wenn während unseres Sortieralgorithmus ein Austausch vorgenommen wird.
Wie wir besprochen haben Früher vergleicht ein Bubble-Sort-Algorithmus zwei benachbarte Werte, um festzustellen, ob das Array geändert werden muss. Also richten wir eine Bedingung ein, um zu bestimmen, welcher Wert der höchste ist. Wenn der Wert der ersten Variablen höher ist, tauscht sie die Plätze mit dem benachbarten Element im Array. Und da ein Austausch vorgenommen wurde, setzen wir auch den booleschen Wert (swap) auf True, damit wir die Schleife noch nicht verlassen.
Sobald die innere Schleife das Array durchlaufen hat Beim ersten Mal wird der boolesche Wert auf True gesetzt, also gehen wir beim zweiten Mal in die externe Schleife und setzen den booleschen Wert (Swap) wieder auf False, um den Vorgang von vorne zu beginnen. Dieser boolesche Wert muss jedes Mal neu initialisiert werden, da unser Algorithmus in der Lage sein soll, das erste Mal, wenn wir die innere Schleife einmal ohne Austausch durchlaufen, zu beenden. Sie können den gesamten Prozess ohne eine Beendigungsbedingung durchlaufen, aber Ihr Programm wird schneller ausgeführt, wenn sie implementiert ist.
Besuch der Bereiche
Der Bubble-Sort-Algorithmus wird diesen Prozess fortsetzen, bis wir’Ich habe eine vollständige Iteration der internen Schleife durchlaufen, ohne einen Austausch vorzunehmen. In der for-Schleifensyntax teilt der Bereich der Schleife mit, wann sie starten, stoppen und um wie viele Schritte sie inkrementieren soll. Sie kann drei Parameter annehmen, benötigt aber nur einen – an welcher Stelle die for-Schleife enden soll.
In unserer externen for-Schleife müssen wir ihr nur sagen, wo sie enden soll, und zwar am allerletzten Index des Arrays. Wir müssen dort z-1 als Bereich verwenden, da der Index mit der Nummerierung bei 0 und nicht bei 1 beginnt. Wenn wir also bei z aufhören, würde es noch einmal gehen, als wir brauchten.
In unserem internen for-Schleife haben wir zwei Parameter, weil wir ihr sagen wollen, wo sie beginnen soll – beim ersten Index, 0 – und wo sie aufhören soll. Wir hören etwas früher auf als die externe for-Schleife, weil wir diese verbleibenden Elemente im Array nicht überprüfen müssen.
Aktualisieren des Arrays
Die if-Anweisung erstellt eine zu bestimmende Bedingung wenn die zwei benachbarten Elemente im Array ihre Position tauschen müssen. Da wir die Zahlen in aufsteigender Reihenfolge sortieren, muss, wenn die erste Zahl größer als die zweite verglichene Zahl ist, diese erste Zahl um eine Stelle nach rechts verschoben werden, was bedeutet, dass die zweite Zahl seitdem um eine Stelle nach links verschoben werden muss es ist kleiner.
Dieser Wechsel kann auf verschiedene Arten erfolgen, aber der schnellste und einfachste Weg, dies zu tun, besteht darin, die Werte gleichzeitig den angrenzenden Elementen zuzuweisen. Dies wird mit der folgenden Anweisung erreicht: numArray[b], numArray[b+1]=numArray[b+1], numArray[b]. Eine alternative Methode wäre, eine temporäre Variable zu erstellen, die einen der Werte enthält, die verschoben werden müssen, während der andere mit einer einfachen Zuweisung verschoben wird. Da dies jedoch mehr Code erfordert, ist es viel effizienter zu bewerkstelligen, wenn wir beide gleichzeitig zuweisen.
Ausgabe der Ergebnisse
Wenn die Methode bubbleSort aus der Verschachtelung ausbricht for-Schleifen und kehrt zum Hauptprogramm zurück, es sendet das resultierende Array an die print-Anweisung, von der wir die Methode aufgerufen haben, und zeigt die Ergebnisse auf dem Bildschirm an, wodurch wir ein Array mit sieben Elementen erhalten, die in aufsteigender Reihenfolge nach Zahlenwert sortiert sind.
Das sortierte Array, das wir aus unserem Beispiel erhalten würden:
[-500,-80, 0, 2, 67, 82, 99]
Beste und schlechteste Anwendungsfälle der Bubble Sort Algorithmus
Der Bubble-Sort-Algorithmus arbeitet effizient, wenn wir eine begrenzte Anzahl von Datenelementen haben, die wir in einer bestimmten Reihenfolge anordnen müssen. Wenn Sie skalieren oder zu viele Datenpunkte hinzufügen, beginnt die Blasensortierung zu kämpfen. Wenn Sie einen effizienteren Algorithmus benötigen, gibt es viele Optionen. Sie können versuchen, Sortierung und Schnellsortierung zusammenzuführen, die beide erheblich schneller sind.
Sehen wir uns die Zeit-und Raumkomplexität an, um eine Vorstellung von der Leistung zu bekommen.
Zeitkomplexität des Bubble-Sort-Algorithmus
(N steht für die Anzahl der Elemente im Datensatz.)
Der beste Fall liegt vor, wenn das Array bereits sortiert ist und keine Änderungen vorgenommen werden müssen. Bevor der Sortieralgorithmus beginnt, weiß das Programm dies jedoch nicht, daher muss es die Schritte zum Sortieren des Arrays mindestens einmal durchlaufen.
Dies ist nicht typisch, wenn es um Daten geht, die Sie sortieren müssen. Oft arbeiten wir mit Daten, die von einem Benutzer eingegeben oder aus einer anderen vom Programm ausgeführten Methode abgerufen werden. Und es ist nicht der effizienteste Weg, ein Programm zu entwerfen, das vom Benutzer verlangt, Daten alphabetisch oder numerisch einzugeben.
Raumkomplexität des Bubble-Sort-Algorithmus
Der Bubble-Sort-Algorithmus hat keinen großen Platzbedarf. Weil wir höchstens einen booleschen Wert hinzufügen, um nach Swaps zu suchen, und temporäre Variablen, um Daten zu speichern, während wir bei Bedarf tauschen. Aus diesem Grund ändert sich die Raumkomplexität nicht, wenn wir größere Datensätze verwenden.
Zusammenfassung
Der Bubble-Sort-Algorithmus kann effizient sein, wenn Sie nur sortieren möchten kleine Datenmengen. Aber es ist wirklich nicht das effizienteste und es ist aufgrund seiner Leistung nicht ideal. Stattdessen ist es als Lernwerkzeug für Programmieranfänger am nützlichsten, um zu lernen, wie der Computer Algorithmen ausführt. Wenn Sie einen Kurs über Datenstrukturen und Algorithmen belegen, müssen Sie diesen beherrschen. Sobald Sie die Grundlagen der Sortieralgorithmen verstanden haben, können Sie zu effizienteren übergehen.
Was ist der Bubble-Sort-Algorithmus und wie funktioniert er? (Mit Beispielen) FAQs (Häufig gestellte Fragen)
Was ist der Bubble-Sort-Algorithmus?
Ein Bubble-Sort-Algorithmus ist ein einfacher Sortieralgorithmus, der zwei vergleicht benachbarte Werte und macht einen Wechsel basierend auf einer in unserem Code festgelegten Bedingung. Normalerweise wird entweder eine While-Schleife oder eine For-Schleife verwendet, um jeden Satz benachbarter Elemente zu durchlaufen, bis das Ende des Datensatzes erreicht ist. Es erfordert jedoch mehr als eine Iteration des vollständigen Datensatzes, um die Daten in aufsteigender oder absteigender Reihenfolge zu sortieren.
Welche Einschränkungen hat der Bubble-Sort-Algorithmus?
Bei großen Datensätzen ist der Bubble-Sort-Algorithmus nicht die beste Nutzung unserer Computerleistung. Andere Sortieralgorithmen wären die bessere Wahl, da sie wahrscheinlich nicht so viel Zeit für die Ausführung des Algorithmus benötigen.
Wie hoch ist die zeitliche Komplexität des Bubble-Sort-Algorithmus?
Die Zeitkomplexität reicht von 0 (N) bis 0 (N^2), wobei das günstigste Szenario besteht, wenn der Datensatz bereits sortiert ist. N stellt die Anzahl der Elemente im Datensatz dar, sodass die zeitliche Komplexität stark ansteigen kann, wenn mit großen Datensammlungen gearbeitet wird.
Wie groß ist die räumliche Komplexität des Bubble-Sort-Algorithmus?
Die Raumkomplexität, egal wie groß unser Datensatz ist, ist O(1), was bedeutet, dass sie gleich bleibt. Theoretisch würde ein Datensatz mit 200 Elementen genauso viel Platz beanspruchen wie einer mit 100.
Wann sollte der Bubble-Sort-Algorithmus verwendet werden?
Da er bei kleinen Datensätzen am effektivsten ist, ist der Bubble-Sort-Algorithmus am nützlichsten in Bildungseinrichtungen, wenn Programmieranfänger zum ersten Mal lernen, Sortieralgorithmen zu codieren.
Was Gibt es verschiedene Möglichkeiten, den Bubble-Sort-Algorithmus zu implementieren?
Da wir den gesamten Datensatz durchlaufen müssen, um einen Bubble-Sort-Algorithmus auszuführen, wird er normalerweise mit Schleifen implementiert – entweder einer for-Schleife oder eine While-Schleife.
Was sind die Alternativen zum Bubble-Sort-Algorithmus?
Es gibt mehrere Algorithmen, die wir verwenden können, um eine Sortierung durchzuführen. Im Folgenden sind einige der am häufigsten verwendeten Sortiermethoden aufgeführt: Auswahlsortierung, Einfügesortierung, Bucket-Sortierung, Heap-Sortierung und Zusammenführungssortierung.