[Powered by Google Translate] [Merge Sort] [Rob Bowden - Harvard University] [Dies ist CS50. - CS50.TV] Reden wir über merge sort. Bisher haben Sie bubble sort, insertion sort und Auswahl Art gesehen. Obwohl ich werde Art von Welle meiner Hand, was ich damit meine, besser, Mergesort führt in der Regel besser als eine dieser 3 Sorten. 

Aber bevor wir über Mergesort, lassen Sie uns über die Verschmelzung von 2 sortierte Listen zu sprechen. Wir rufen den Prozess der Übernahme 2 sortierte Listen, wie diese, und macht einen einzigen sortierten Liste von ihnen - die Zusammenführung der Listen. Wie können wir das tun? Nun, das ist eine Idee, um nur Stick eine Liste an das Ende der anderen Liste und dann sortieren Sie die Liste aus. 

Während dies funktioniert, ist es eine Menge unnötiger Arbeit. Wir können es schneller tun als nur sorting. Beachten Sie, dass eine falsche Idee, nur nehmen abwechselnd Becher aus jeder Liste ist. Während das mag das funktioniert auf den ersten Blick, tun, dass wir am Ende mit 4, 8, 15, 23, 16 - Ankündigung, dass 16 und 23 fehl am Platze sind. Dies liegt daran, 2 Elemente, die angezeigt Folge sollte in der zusammengeführte Liste sind in der gleichen ursprünglichen Liste. Beide 15 und 16 sind in der Liste auf der linken Seite. Der Trick ist, den Vorteil der Tatsache, dass beide Listen bereits sortiert sind zu nehmen. Dies bedeutet, dass, wenn wir nur auf die ersten Elemente der beiden Listen aussehen - Hier, 4 und 8 - muß eine von ihnen auch das erste Element der vereinigten Liste sein. Nun, warum ist das so? Beide Listen sind bereits sortiert, und so entweder 4 oder 8 muss das kleinste Element sein, wenn wir die 2 Listen zu kombinieren. In diesem Fall ist die kleinste 4, so können wir nehmen 4 und machen es das erste Element unserer zusammengeführten Liste. Jetzt haben wir weiterhin die Zusammenlegung der verbleibenden 3 Elemente der ersten Liste und 4 Elemente der zweiten Liste. 

Wieder einmal müssen wir nur auf das erste Element der beiden Listen zu suchen. Je kleiner der 2 ist der zweite Bestandteil unserer vereinigten Liste sein. Dieses Mal zwischen 8 und 15 die kleinste ist 8, und so fügen wir, dass als zweites Element der sortierten Liste. Wir können weiterhin das Vergleichen der ersten Elemente der beiden Listen und Entfernen des kleineren der zwei. Vergleichens 15 und 23, 15 ist kleiner und so daß die das dritte Element. Nun Vergleichens 16 und 23, 16 ist kleiner. Damit ist das vierte Element. 

Beachten Sie, dass 2 Elemente aus der gleichen Liste in einer Reihe kam. Deshalb ist das zusammengeführte Liste kann nicht einfach alternativen Elementen aus den 2 Listen. Vergleicht man 50 und 23, 23 ist kleiner, so wählen wir, dass. Zwischen 50 und 42, 42 ist kleiner. Zwischen 50 und 108, beträgt 50 kleiner. Und schließlich müssen wir nur noch 108, so muss es am Ende unserer Liste. Beachten Sie, dass wir eine schöne, sortierte Liste haben. Jedes Mal, verglichen wir die ersten 2 Elemente der 2 Listen konnten wir das nächste Element des fusionierten Liste zu bestimmen. Das heißt, wenn die endgültige Liste n Zahlen, wobei n hier 8 enthält, dann brauchen wir höchstens n Vergleiche alle diese Zahlen in den richtigen Ort gelangen. Ein solcher Algorithmus ist in der linearen Zeit ausführen, aber nicht über das hier machen. 

Mit unserem Algorithmus zur verschmelzen, können wir eine schnelle Mergesort-Algorithmus. Also, lasst uns setzen unseren Listen. Es gibt 2 große Schritte in den Prozess der Zusammenführung sort. Zunächst kontinuierlich spaltete die Liste der Becher in zwei Hälften bis wir eine Reihe von Listen mit nur 1 Tasse in ihnen. Mach dir keine Sorgen, wenn eine Liste eine ungerade Anzahl und man kann nicht einen perfekt sauberen Schnitt zwischen ihnen. Einfach willkürlich auswählen, welche Liste, um die zusätzliche Tasse in. gehören Also, lasst uns aufgeteilt diese Listen. Jetzt haben wir 2 Listen. Jetzt haben wir 4 Listen. 

Und jetzt haben wir 8 Listen mit einer einzigen Tasse in jeder Liste. Das ist es also für Schritt 1. Für Schritt 2 wir immer wieder verschmelze Paare von Listen mit der Merge-Algorithmus haben wir zuvor gelernt. Zusammenführen 108 und 15, landen wir mit der Liste 15, 108. Zusammenführen 50 und 4, landen wir mit 4, 50. Zusammenführen 8 und 42, landen wir mit 8, 42. Und Zusammenführen 23 und 16, landen wir mit 16, 23. Nun sind alle unsere Listen sind der Größe 2. Feststellen, dass jedes der vier Listen sortiert ist. 

So können wir beginnen Verschmelzung Paar von Listen wieder. Zusammenführen 15 und 108 und 4 und 50 - zuerst den 4, dann die 15, dann die 50, dann die 108. Zusammenführen 8, 42 und 16, 23, wir zunächst die 8, dann die 16, dann die 23, dann die 42. So jetzt haben wir nur 2 Listen der Größe 4 haben, von denen jeder sortiert. So jetzt haben wir verschmelzen diese 2 Listen. Zuerst nehmen wir die 4. Dann nehmen wir die 8. Dann nehmen wir den 15 und 16, dann 23, dann 42, dann 50, dann 108. Und wir sind fertig. Wir haben jetzt eine sortierte Liste. So wie schnell war das genau? In technischer Hinsicht ist Mergesort O (n log n), während alle bubble sort, insertion sort und Auswahl sort O sind (n ²). In der Tat, wie Sie bald lernen, werden Sie nicht in der Lage zu kommen mit einer Art das funktioniert besser als O (n log n) im allgemeinen Fall. Auch nicht über diesen großen O-Notation Sorgen, wenn Sie es noch nicht gesehen. 

Genau wissen, dass dies bedeutet, wenn wir eine wirklich große Liste sortieren wollte bubble sort, insertion sort und Auswahl sort könnte dauern deutlich länger als Mergesort. Es bedeutet nicht, dass Mergesort schneller für alle Listen werden oder sogar für jede einzelne Liste unter einer bestimmten Größe. Zum Beispiel könnte insertion sort die schnellste Art für alle Listen kleiner als 5 Elemente. In der Praxis ist Mergesort in der Regel schneller für Listen so klein wie 50 Elemente. 

Aber diese zusätzliche Geschwindigkeit nicht ohne einen Preis zu kommen. Im Gegensatz zu unseren anderen Sorten nehmen, deren Liste und ändern Sie die Liste an Ort und Stelle bis wir eine sortierte Liste zu erhalten, muss Mergesort zusätzlichen Speicherplatz bis 2 Listen miteinander verschmelzen. Wir können nicht sofort verwenden Listen, die zusammengeführt werden, um die zusammengeführte Liste speichern da wir überschreiben können Elemente, die müssen noch zusammengeführt werden. Dieser Raum ist ein bisschen wie ein Preis, aber es ist in der Regel nicht unvernünftig. Und das ist es für merge sort. 

Mein Name ist Rob Bowden, und dies ist CS50. [CS50.TV] - Und die Auswahl sort. [Lacht] Oh, ich muss, dass nehmen Sie auch, weil ich, wie ich mich präsentieren sie eingeschaltet. Liste auf der linken Seite. Das war ein Tippfehler. [Misspoke] Ich habe es vermasselt - [Lacht] Ich weiß nicht, was -