[Powered by Google Translate] [BUBBLE SORT]
[JACKSON STEINKAMP HARVARD UNIVERSITY]
[DIESES IST CS50. CS50TV]
Blase Sortieren eines Beispiels eines Sortier-Algorithmus -
das heißt, ein Verfahren zum Sortieren einer Gruppe von Elementen in
aufsteigender oder absteigender Reihenfolge.
Zum Beispiel, wenn Sie ein Array sortieren wollte bestehend aus den Zahlen
[3, 5, 2, 9], würde eine korrekte Umsetzung der Bubble Sort wieder die
sortierte Array [2, 3, 5, 9] in aufsteigender Reihenfolge.
Nun, ich werde in Pseudocode erklären, wie der Algorithmus funktioniert.
>> Lassen Sie uns sagen, dass wir eine Liste sortieren von 5 Zahlen - 3, 2, 9, 6 und 5.
Der Algorithmus beginnt, indem man die beiden ersten Elemente, 3 und 2,
und Prüfen, ob sie außer Betrieb relativ zueinander sind.
Sie sind - 3 größer als 2 ist.
In aufsteigender Reihenfolge, sollten sie anders herum sein.
So, tauschen wir sie.
Nun ist die Liste sieht wie folgt aus: [2, 3, 9, 6, 5].
>> Als nächstes betrachten wir die zweite und dritte Element, 3 und 9.
Sie sind in der richtigen Reihenfolge relativ zueinander.
Das heißt, 3 weniger als 9 so der Algorithmus nicht funktioniert tauschen sie.
Als nächstes schauen wir auf 9 und 6. Sie sind nicht in Ordnung.
>> Also brauchen wir, um sie auszutauschen, weil 9 ist größer als 6.
Schließlich betrachten wir die letzten zwei Zahlen, 9 und 5.
Sie sind nicht in Ordnung, so müssen sie ausgetauscht werden.
Nach dem ersten Durchgang durch die vollständige Liste,
es sieht wie folgt aus: [2, 3, 6, 5, 9].
Nicht schlecht. Es ist fast sortiert.
Aber wir müssen in der Liste erneut ausführen, um es vollständig sortiert.
Zwei weniger als 3, so dass wir nicht tauschen.
>> Drei weniger als 6, so dass wir nicht tauschen.
Sechs größer als 5 ist. Wir tauschten.
Sechs von weniger als 9. Wir wissen nicht tauschen.
Nach dem zweiten Durchgang, sieht es wie folgt aus: [2, 3, 5, 6, 9]. Perfect.
Nun schreiben wir es in Pseudocode.
Grundsätzlich für jedes Element in der Liste, müssen wir es betrachten
und das Element direkt an ihrer rechten Seite.
Wenn sie außerhalb der Reihenfolge zueinander - das heißt, wenn das Element auf der linken
ist größer als die auf der rechten Seite -, wir sollten die beiden Elemente auszutauschen.
>> Wir tun dies für jedes Element in der Liste, und wir haben ein Durchlauf gemacht.
Jetzt müssen wir nur noch die Pass-Through oft genug tun, um die Liste zu sichern
vollständig, richtig sortiert.
Aber wie oft haben wir, um die Liste zu passieren
garantieren, dass wir fertig sind?
Nun, das ist das Worst-Case-Szenario, wenn wir eine vollständig rückwärts Liste haben.
Dann dauert es eine Reihe von Durchreichen gleich der Anzahl
der Elemente n-1.
Wenn dies keinen Sinn macht intuitiv, von einem einfachen Fall zu denken - die Liste [2, 1].
>> Das wird ein Pass-Through zu ergreifen, um korrekt zu sortieren.
[3, 2, 1] - Der schlimmste Fall ist, dass mit drei Elementen sortiert rückwärts,
es geht um 2 Iterationen zu sortieren nehmen.
Nach einer Iteration, es ist [2, 1, 3].
Die zweite ergibt das sortierte Array [1, 2, 3].
Damit Sie wissen, Sie müssen nie durch das Array zu gehen, in der Regel
mehr als n-1 mal, wobei n die Anzahl der Elemente in dem Array.
Es heißt Bubble Sort, weil die größten Elemente zu "bubble-up" eher
auf der rechten Seite ziemlich schnell.
In der Tat hat dieser Algorithmus sehr interessantes Verhalten.
>> Nach m Iterationen durch das gesamte Array,
die rechten m Elemente sind garantiert
in ihren richtigen Platz sortiert werden.
Wenn Sie diese für sich selbst zu sehen,
wir können es auf einem völlig rückwärts list [9, 6, 5, 3, 2] versuchen.
Nach einem Durchgang durch die gesamte Liste,
[Sound des Schreibens]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
die rechte 9 ist an der richtigen Stelle.
Nach dem zweiten Pass-Through wird der 6 haben 'gesprudelt-up' der
Sekunden rechten Ort.
Die zwei Elemente auf der rechten Seite - 6 und 9 - wird in ihrer richtigen Orten sein
nach den ersten beiden Durchführungen.
>> Also, wie können wir nutzen, um den Algorithmus zu optimieren?
Nun, nach einer Iteration durch das Array
wir nicht wirklich brauchen, um die am weitesten rechts Element überprüfen
weil wir wissen, dass es sortiert.
Nach zwei Iterationen, wissen wir, dass die beiden rechten Elemente sind vorhanden.
So im allgemeinen nach k Iterationen durch die vollständige Anordnung,
Überprüfung der letzten k Elemente ist überflüssig, da wir wissen,
sie sind an der richtigen Stelle schon.
>> Also, wenn Sie das Sortieren eines Arrays von n Elementen,
bei der ersten Iteration - Sie werden müssen alle Elemente sortiert werden - die erste n-0.
Bei der zweiten Iteration, haben Sie auf alle Elemente, aber die letzte aussehen -
die erste n-1.
Eine weitere Optimierung könnte zu überprüfen, ob die Liste bereits sortiert ist
nach jeder Iteration.
Wenn es bereits sortiert ist, brauchen wir nicht zu einem mehr Iterationen machen
durch die Liste.
Wie können wir das tun?
Nun, wenn wir machen keine Swaps auf einer Pass-Through auf der Liste,
es ist klar, dass die Liste bereits sortiert wurde, weil wir nicht tauschen nichts.
Also haben wir definitiv nicht noch einmal zu sortieren.
>> Vielleicht könnten Sie initialisieren eine Flag-Variable namens "nicht sortiert", um
false und ändern Sie ihn auf true, wenn Sie keine Elemente auf Auslagerung von
eine Iteration durch das Array.
Oder ähnlich, einen Zähler zu zählen, wie viele Swaps Sie
an einem bestimmten Iteration.
Am Ende einer Iteration, wenn Sie nicht tauschen eines der Elemente,
Sie wissen, die Liste bereits sortiert ist und du bist fertig.
Bubble Sort, wie andere Sortieralgorithmen, kann
optimiert, um für alle Elemente, die eine Bestellung Verfahren haben zu arbeiten.
>> Das ist, da zwei Elemente haben Sie eine Möglichkeit zu sagen, wenn das erste ein
größer als, gleich oder kleiner als die zweite.
Zum Beispiel könnten Sie die Buchstaben des Alphabets mit den Worten sortieren
dass a <b, b <c usw.
Oder Sie könnten sortieren Tag der Woche, wobei Sonntag weniger als Montag
das ist weniger als Dienstag.
>> Bubble Sort ist keineswegs eine sehr effiziente und schnelle Sortier-Algorithmus.
Sein Worst-Case-Laufzeit ist Big O von n ²
da muss man n Iterationen durch eine Liste zu machen
Überprüfung aller n Elemente jeweils pass-through, nxn = n ².
Diese Laufzeit bedeutet, dass die Anzahl der Elemente Sie Sortier steigt,
die Laufzeit steigt quadratisch.
>> Aber wenn Effizienz ist nicht ein wichtiges Anliegen des Programms
oder wenn Sie nur Sortieren einer kleinen Anzahl von Elementen,
finden Sie vielleicht Bubble Sort nützlich, weil
Es ist eine der einfachsten Sortieralgorithmen zu verstehen
und codieren.
Es ist auch ein guter Weg, um Erfahrungen mit der Übersetzung eine theoretische bekommen
Algorithmus in tatsächliche Funktionieren Code.
Nun, das ist Bubble Sort für Sie. Danke fürs Zuschauen.
CS50.TV