[Powered by Google Translate] [Einfügung Sortieren] [Tommy MacWilliam] [Harvard University] [Dies ist CS50.TV] Werfen wir einen Blick auf insertion sort, ein Algorithmus für die Aufnahme einer Liste von Zahlen und sortieren. Ein Algorithmus, erinnern, ist einfach eine Schritt-für-Schritt-Verfahren für die Erfüllung einer Aufgabe. Die grundlegende Idee hinter Insertion Sort ist unsere Liste in zwei Teile zu teilen, eine sortierte Abschnitt und einen unsortierten Teil. 

Bei jedem Schritt des Algorithmus wird eine Zahl verschoben aus dem unsortierten Teil zum sortierten Teil bis schließlich die gesamte Liste sortiert ist. Hier ist die Liste von sechs unsortierten Zahlen - 23, 42, 4, 16, 8, und 15. Da diese Zahlen nicht alle in aufsteigender Reihenfolge, sie unsortiert. Da wir noch nicht begonnen haben Sortier noch, wir betrachten alle sechs Elemente unserer unsortierten Teil. 

Sobald wir Sortier starten, werden wir diese sortiert Zahlen links von ihnen setzen. Also, lasst uns mit 23, das erste Element in unserer Liste zu starten. Wir haben noch keine Elemente in unserer sortiert Teil noch also lasst uns einfach halten 23 bis Anfang und Ende unserer sortiert Teil. Jetzt hat unsere sortiert Teil eine Zahl, 23, und unsere unsortierten Teil hat diese fünf Zahlen. Lassen Sie uns jetzt legen Sie die nächste Nummer in unserem unsortierten Teil, 42, in die sortierte Teil. 

Um dies zu tun, brauchen wir, um die 42 mit der 23 zu vergleichen - das einzige Element in unserem sortiert Teil so weit. Forty-two ist größer als 23, so können wir einfach anhängen 42 bis zum Ende der sortierten Teil der Liste. Great! Jetzt unsere sortiert Abschnitt zwei Elementen, und unsere unsortierten Abschnitt weist vier Elemente. Also, lasst uns nun auf die 4 zu bewegen, das nächste Element in der unsortierten Teil. Also, sollten, wo dies in der sortierten Teil platziert werden? 

Denken Sie daran, wir wollen diese Zahl in sortierter Reihenfolge zu platzieren so dass unsere sortiert Teil bleibt jederzeit korrekt sortiert. Wenn wir die 4 auf der rechten Seite der 42 zu platzieren, dann ist unsere Liste wird aus sein, in Ordnung. Also, lasst uns weiter bewegen rechts-nach-links in unserem sort Abschnitt. Wie wir uns bewegen, wir verschieben jede Zahl auf einen Ort, um Platz für die neue Nummer. Okay, das ist 4 auch weniger als 23, so können wir nicht platzieren Sie es hier auch nicht. Gehen wir die 23 richtige Ort. 

Das heißt, wir möchten die 4 in den ersten Slot in der sortierten Teil platzieren. Beachten Sie, wie dieser Raum in der Liste schon leer, weil wir schon seit bewegen sortiert Elemente, die, wie wir sie erlebt habe. Gut. Also, wir sind auf halbem Wege. Lasst uns weiter unser Algorithmus, indem Sie die 16 in der sortierten Teil. Sechzehn weniger als 42, also lasst verschieben die 42 auf der rechten Seite. Sechzehn ist auch weniger als 23, also lasst uns auch verschieben das Element. 

Nun ist 16 größer als 4 ist. So sieht es aus, wie wir möchten, dass die 16 zwischen der 4 und der 23 einzufügen. Während der Bewegung durch die sortierte Teil der Liste von rechts nach links, 4 ist die erste Zahl die wir gesehen haben, die kleiner ist als die Zahl wir versuchen, einzufügen. So, jetzt können wir die 16 in diesem leeren Slot stecken, die, denken Sie daran, wir haben von beweglichen Elementen in der Art Teil über erstellt wie wir ihnen begegneten. 

Gut. Jetzt haben wir vier sortierte Elemente und zwei unsortierten Elementen. Also, lasst uns bewegen Sie die 8 in der sortierten Teil. Acht weniger als 42. Acht kleiner ist als 23. Und 8 ist kleiner als 16 ist. Aber 8 größer als 4 ist. So möchten wir die 8 zwischen der 4 und der 16 einzufügen. Und jetzt müssen wir nur noch ein Element links zu sortieren - die 15. Fünfzehn ist weniger als 42, Fünfzehn kleiner als 23. Und 15 ist kleiner als 16 ist. Aber 15 größer als 8 ist. 

So, hier ist, wo wir unsere letzte Einfügung machen wollen. Und wir sind fertig. Wir haben keine mehr Elemente in der unsortierten Teil, und unsere sortiert Teil in der richtigen Reihenfolge. Die Zahlen werden vom kleinsten zum größten geordnet. Also, lassen Sie uns einen Blick auf einige Pseudocode, der die Schritte, die wir soeben durchgeführten beschreibt. 

Auf der Linie 1, können wir sehen, dass wir brauchen, um durchlaufen jedes Element in der Liste mit Ausnahme der ersten, wird seit dem ersten Element in der unsortierten Abschnitt einfach geworden das erste Element in dem Abschnitt sortiert. Auf den Linien 2 und 3, sind wir die Verfolgung von unseren aktuellen Platz in der unsortierten Teil. Element stellt die Zahl, die wir gerade in Bewegung sind in der sortierten Teil, und j unserem Index in den unsortierten Teil. 

Zeile 4 sind wir durch die sortierte Teil von rechts nach links durchlaufen. Wir wollen zu stoppen Iteration einmal das Element auf der linken Seite unserer aktuellen Position ist weniger als das Element wir versuchen, einzufügen sind. In Zeile 5, wir verschieben jedes Element begegnen wir einem Raum auf der rechten Seite. So, haben wir einen klaren Raum zu legen, wenn wir das erste Element zu finden weniger als das Element wir uns bewegen. In Zeile 6, wir aktualisieren unsere Zähler weiter nach links zu bewegen, durch die sortierte Teil. Schließlich on line 7, wir Einfügen des Elements in der sortierten Teil der Liste. 

Wir wissen, dass es okay ist, in Position j einzufügen ist, weil wir bereits das Element, das da zu sein um eine Stelle nach rechts eingesetzt verschoben. Denken Sie daran, wir sind durch den sortierten Teil von rechts nach links, aber wir sind durch den unsortierten Teil von links nach rechts bewegt. Gut. Lassen Sie uns nun einen Blick auf, wie lange läuft, dass Algorithmus nahm. Wir werden zuerst die Frage stellen, wie lange dauert es, bis dieser Algorithmus im schlimmsten Fall laufen. Daran erinnern, dass wir diese Laufzeit stellen mit Big O-Notation. Um unsere Liste zu sortieren, mussten wir iterieren die Elemente in der unsortierten Teil, und für jedes dieser Elemente, potenziell über alle Elemente in der sortierten Abschnitts. Intuitiv, das klingt wie ein O (n ^ 2)-Operation. 

Mit Blick auf unsere Pseudocode, haben wir eine Schleife innerhalb einer anderen Schleife verschachtelt, die tatsächlich klingt wie ein O (n ^ 2)-Operation. Allerdings hat die sortierten Teil der Liste nicht enthalten die gesamte Liste, bis zum bitteren Ende. Dennoch konnten wir potenziell legen ein neues Element am Anfang der sortierten Teil bei jeder Iteration des Algorithmus, was bedeutet, dass wir müssten an jedem Element derzeit aussehen in der sortierten Teil. Das bedeutet also, dass wir so möglicherweise ein Vergleich für das zweite Element, zwei Vergleiche für das dritte Element und so weiter. So ist die Anzahl der Schritte die Summe der ganzen Zahlen von 1 bis zur Länge der Liste minus 1 ist. Wir können dies mit einer Summierung darstellen. 

Wir werden nicht in Summen gehen, aber es stellt sich heraus, dass diese Summe gleich ist n (n - 1) mehr als 2, was äquivalent n ^ 2/2 - n / 2. Wenn man über die asymptotische Laufzeit Diese n ^ 2 Begriff wird diesen n Begriff dominieren. So ist Insertion Sort Big O (n ^ 2). Was, wenn wir insertion sort lief auf eine bereits sortierte Liste. In diesem Fall würden wir einfach Aufbau des sortierten Teils von links nach rechts. So werden wir nur in der Größenordnung von n Schritte müssen. 

Das bedeutet, dass insertion sort ein Best-Case-Performance n hat, denen wir vertreten mit Ω (n). Und das ist es für insertion sort, nur eine der vielen Algorithmen, die wir verwenden können, um eine Liste zu sortieren. Mein Name ist Tommy, und dies ist CS50. [CS50.TV] Oh, man kann einfach nicht aufhören, dass, sobald er gestartet wird. Oh, wir haben das - >> Boom!