[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