[Musikwiedergabe] DOUG LLOYD: Okay, so Bubble-Sort ist ein Algorithmus, Sie verwenden, um eine Reihe von Elementen sortieren. Werfen wir einen Blick darauf, wie es funktioniert. 

So ist die Grundidee Bubble-Sort ist dies. Wir wollen in der Regel zu höheren bewegen geschätztes Elemente allgemein auf der rechten Seite, und senken Sie Wert Elemente allgemein nach links, wie man erwarten würde. Wir wollen, dass die unteren Dinge zu sein, der Anfang, und die höheren Dinge am Ende ist. 

Wie machen wir das? Nun in Pseudocode, könnten wir sagen, lasst uns Set eine Swap-Zähler auf einen Wert ungleich Null. Wir werden sehen, warum wir das tun, in einer Sekunde. Und dann haben wir Wiederholen Sie die folgenden Prozess, bis die Swap-Gegen 0, oder bis wir machen keine Swaps überhaupt. 

Setzen Sie den Swap-Zähler auf 0, wenn es nicht bereits 0. Schauen Sie sich jeden benachbarten Elementpaar. Wenn diese beiden Elemente sind nicht in Ordnung, tauschen sie, und fügen Sie 1 auf die Swap-Gegen. Wenn du denkst diese, bevor Sie es zu visualisieren, bemerken, dass dies zu bewegen unteren geschätztes Elemente links und höherwertigen Elemente rechts, effektiv zu tun, was wir tun wollen, die bewegen diese Gruppen ist von Elementen auf diese Weise. Lassen Sie uns zu vergegenwärtigen, wie diese aussehen könnte, mit unser Angebot , dass wir zum Testen verwendet werden, aus dieser Algorithmen. Wir haben eine unsortierte Array wieder hier, von allen der Elemente angegeben wobei in rot. Und ich meine Swap-Gegen um einen Wert ungleich Null. Ich willkürlich gewählt negativen 1-- es ist nicht 0. Wir wollen diesen Vorgang wiederholen bis der Swap-Gegen 0. Das ist, warum ich meine Swap- Zähler bis zu einem gewissen Wert ungleich Null, weil sonst die Swap-Gegen würde 0 sein. Wir würden nicht einmal ansatzweise die Prozess des Algorithmus. Also noch einmal, die Schritte sind-- setzen Sie die Swap-Gegen auf 0, dann auf jeder benachbarten suchen Paar, und wenn sie nicht in Ordnung sind, tauschen sie, und fügen Sie 1 auf die Swap-Gegen. Lassen Sie uns also beginnen diesen Prozess. Das erste, was wir tun, ist setzen wir die Swap-Zähler auf 0, und dann werden wir beginnen, an jedem benachbarten Paar. 

So dass wir zuerst beginnen, 5 und 2. Wir sehen, dass sie aus sind bestellen und so tauschen wir sie. Und wir 1 hinzufügen, um die Swap-Gegen. So, jetzt unseren Swap-Zähler 1, und 2 und 5 umgeschaltet worden sind. Jetzt haben wir den Prozess zu wiederholen. 

Wir schauen uns den nächsten benachbarten Paar, 5 und 1-- sie sind auch nicht in Ordnung, so dass wir tauschen sie und fügen Sie 1 auf die Swap-Gegen. Dann schauen wir uns 5 und 3. Sie sind nicht in Ordnung, so dass wir tauschen sie und wir 1 hinzufügen, um die Swap-Gegen. Dann schauen wir uns 5 und 6. Sie sind in Ordnung, so dass wir nicht wirklich müssen Sie nichts dieses Mal tauschen. Dann schauen wir uns 6 und 4. Sie sind auch nicht in Ordnung, so dass wir tauschen sie und wir 1 hinzufügen, um die Swap-Gegen. 

Jetzt bemerken, was passiert ist. Wir haben 6 bewegt den ganzen Weg bis zum Ende. So bei der Auswahl zu sortieren, wenn Sie schon gesehen, dass Videos, was wir taten, war Wir sind dann schließlich die kleinsten Elemente im Gebäude sortierten Array im Wesentlichen aus von links nach rechts, vom kleinsten zum größten. Im Falle von Bubble Sort, wenn wir nach diesem speziellen Algorithmus, wir tatsächlich zu bauen sortierten Array von rechts zu, der größten zur kleinsten verlassen. Wir haben effektiv sprudelte 6, die größten Wert, den ganzen Weg bis zum Ende. 

Und so können wir nun erklären, dass diese sortiert, und in Zukunft iterations-- Durchlaufen des Arrays again-- wir haben nicht mehr zu berücksichtigen 6. Wir haben nur zu prüfen, die unsortierten Elemente wenn wir bei benachbarten Paaren suchen. Also haben wir einen fertig sind passieren Bubble-Sort. So, jetzt gehen wir zurück zu der Frage, wiederholen, bis die Swap-Gegen 0. Nun, die Swap-Gegen 4 ist, also werden wir zum Wiederholen Sie diesen Vorgang erneut. 

Wir werden die Swap-Zähler zurückzusetzen auf 0, und schauen Sie sich jedem benachbarten Paar. So beginnen wir mit 2 und 1-- sie nicht in Ordnung, so tauschen wir sie und wir 1 hinzufügen, um die Swap-Gegen. 2 und 3, sind sie in Ordnung. Wir brauchen nicht, etwas zu tun. 3 und 5 sind in Ordnung. Wir brauchen nicht, etwas zu tun gibt. 

5 und 4 aus sind sie der Ordnung, und so haben wir brauchen, um sie zu tauschen, und fügen Sie 1 auf die Swap-Gegen. Und jetzt haben wir 5 bewegt wird, der nächstgrößte Element, bis zum Ende des unsortierten Abschnitt. So können wir heute sagen, dass Teil des sortiert Teil. 

Jetzt können Sie auf die gesuchte Bildschirm und wahrscheinlich kann sagen, wie kann ich, daß das Array wird jetzt sortiert. Aber wir können nicht beweisen, dass noch kann. Wir haben nicht eine Garantie dass es sortiert. Aber das ist, wo das Swap- Gegen geht um ins Spiel kommen. 

Also haben wir einen Pass abgeschlossen. Die Swap-Zähler 2. So werden wir wiederholen dieser Prozess wieder, wiederholen, bis die Swap-Gegen 0. Setzen Sie den Swap-Zähler auf 0. Also werden wir es zurückzusetzen. 

Nun ein Blick auf jedem benachbarten Paar. Das ist in Ordnung, 1 und 2. 2 und 3 sind in Ordnung. 3 und 4 sind in Ordnung. Also an dieser Stelle bemerken wir abgeschlossen haben Suche in jedem benachbarten Paar, aber die Swap-Gegen ist immer noch 0. 

Wenn wir nicht haben, um umzuschalten alle Elemente, dann muss in Ordnung sein, durch Aufgrund dieses Prozesses. Und so eine Effizienz von Art, dass wir Informatiker lieben, ist können wir nun erklären, die gesamte Anordnung muss sortiert werden, weil wir nicht müssen alle Elemente zu vertauschen. Das ist ziemlich nett. 

Also, was ist der schlimmste Fall Szenario mit Bubble-Sort? Im schlimmsten Fall ist das Array in völlig umgekehrter Reihenfolge, und so müssen wir jede Blase der großen Elemente alle die Art und Weise über das Array. Und wir effektiv auch haben bubble alle kleinen Elementen zurück den ganzen Weg über die Anordnung, zu. So dass jedes der n Elemente zu bewegen in all den anderen n-Elemente. Also das ist der schlimmste Fall. Im besten Fall Szenario ist dies jedoch geringfügig von Selection Sort. Das Array ist bereits sortiert, wenn wir gehen. Wir haben nicht zu einem zu machen Swaps im ersten Durchgang. So haben wir vielleicht zu schauen bei weniger Elemente, nicht wahr? Wir haben nicht, dies zu wiederholen, Verarbeiten einer Anzahl von Faches. 

Also, was bedeutet das? Also, was ist das schlimmste Szenario für Bubble-Sort, und was das beste Szenario für Bubble-Sort? Haben Sie denke, dies? Im schlimmsten Fall, dass Sie durchlaufen haben über alle n Elemente n-fach. So der schlimmste Fall ist n quadriert. 

Wenn das Array vollkommen obwohl sortierten, nur du muss bei jedem Blick der Elemente gleichzeitig. Und wenn die Swap-Gegen ist immer noch 0, Sie sagen, dass dieses Array sortiert. Und so im besten Fall, ist dies sogar besser als Auswahl sort-- es Omega der n. 

Ich bin Doug Lloyd. Dies ist CS50.