[Musikwiedergabe] 

DOUG LLOYD: So Insertion Sort ist ein weiterer Algorithmus, den wir verwenden können, um ein Array zu sortieren. Die Idee hinter diesem Algorithmus ist es, Ihre sortiertes Array zu bauen an Ort und Stelle, Schaltelemente aus die Art und Weise, wie Sie gehen, Raum zu machen. Das ist etwas anders von der Auswahl sortieren oder Blase Sortieren, zum Beispiel, wo wir die Anpassung der Standorte, wo wir machen Swaps. 

In diesem Fall, was wir eigentlich Dabei ist Gleitelemente über, aus dem Weg. Wie funktioniert dieser Algorithmus arbeiten in Pseudocode? Nun lassen Sie uns einfach sagen, dass die willkürlich erste Element des Array sortiert. Wir bauen sie an Ort und Stelle. 

Wir gonna ein Element zu gehen zu einem Zeitpunkt, und bauen, und so das erste, was sehen wir, ist ein Ein-Element-Array. Und per Definition ein One Elementanordnung sortiert. 

Dann werden wir diesen Vorgang wiederholen until-- wir werden den folgenden Prozess wiederholen bis alle Elemente sortiert werden. Sehen Sie in der nächsten unsortierte Element und legen Sie sie in der sortierten Teil, indem die erforderliche Anzahl Elemente aus dem Weg. Hoffentlich Visualisierung wird Ihnen helfen, genau sehen, was ist los mit Insertion Sort. 

Also noch einmal, hier ist unsere gesamten unsortierten Array, alle Elemente in rot angezeigt. Und lassen Sie uns folgen Sie den Schritte unserer Pseudocode. Das erste, was wir tun, ist, wir als die das erste Element des Arrays, sortiert. Also sind wir nur gonna sagen fünf, du bist jetzt sortiert. 

Dann freuen wir bei der nächsten unsortierten Element des Arrays und wir möchten, dass zum Einfügen in die sortierte Abschnitt, indem Elemente über. So dass zwei der nächste unsortierten Element des Arrays. Klar ist es, bevor das angehört fünf, also was wir tun ist eine Art halten zwei beiseite für eine zweite, verlagern fünf vorbei, und dann legen Sie zwei vor fünf, wo man gehen sollte. Und jetzt können wir sagen, dass zwei sortiert ist. 

So wie Sie sehen können, bisher haben wir nur sah zwei Elemente des Arrays. Wir haben nicht die gesuchte Ruhe überhaupt, aber wir haben habe diese beiden Elemente sortiert nach Weg des Schaltmechanismus. 

So dass wir den Prozess zu wiederholen. Sehen Sie in der nächsten unsortierten Element, das ist eine. Lassen Sie uns zu halten, dass abgesehen für eine zweite, verschieben alles vorbei, und legte eine wo es gehen sollte. 

Auch noch, immer nur haben wir sah ein, zwei und fünf. Wir wissen nicht, was noch kommt, aber wir haben diese drei Elemente sortiert. 

Weiter unsortierte Element drei, so dass wir es beiseite stellen. Wir werden über verschieben, was wir müssen die, diesmal ist nicht alles wie in der vorherigen zwei Fälle, es ist nur die Fünf. Und dann werden wir drei in kleben, zwischen den beiden und der fünf. 

Six ist der nächste unsortierten Element mit dem Array. Und in der Tat sechs größer als fünf ist, so dass wir brauchen noch nicht einmal, um jede Swapping zu tun. Wir können nur tack sechs rechts auf das Ende der sortierten Abschnitt. 

Schließlich ist die vier letzten unsortierte Element. So werden wir es beiseite, verschieben über die Elemente, die wir brauchen, um zu verschieben über, und setzen Sie dann vier, wo es hingehört. Und jetzt schauen, haben wir sort aller Elemente. Beachten Sie, mit Einlege Sortieren, haben wir nicht hin und her über das Feld zu gehen. Wir waren nur über das Feld eine Zeit, und wir verschoben Dinge dass wir schon begegnet, um um Platz für die neuen Elemente bilden. 

Also, was ist der schlimmste Fall Szenario mit Insertion Sort? Im schlimmsten Fall wird die Array in umgekehrter Reihenfolge. Sie haben zu jeder der n Elemente verschieben bis n Positionen, jedes einzelne Mal, wenn wir machen eine Insertion. Das ist eine Menge der Verschiebung. 

Im besten Fall, die Array ist perfekt sortiert. Und ein bisschen wie, was passiert mit fünf und sechs im Beispiel wo wir nur tack sie auf ohne dass eine Verlagerung zu tun, wir würden im Wesentlichen tun. 

Wenn Sie sich vorstellen, dass unsere Array war eins bis sechs, wir würden durch starten erklärte man sortiert. Zwei kommt nach einer so können wir einfach sagen, OK, gut ein und zwei sortiert sind. Drei kommt nach zwei so, OK, eins und zwei und drei werden sortiert. 

Wir sind nicht irgendwelche Swaps, wir sind Mitnahme dieses willkürliche Linie zwischen sortiert und unsortiert, wie wir gehen. So wirksam wie die in dem Beispiel hat, Drehelemente blau, wie wir vorgehen. Also, was ist der schlimmste Fall der Laufzeit, dann? Denken Sie daran, wenn wir jedes verschieben die n-Elemente möglicherweise n Positionen, hoffentlich, das Ihnen eine Idee, die im schlimmsten Fall Laufzeit ist Big O n quadriert. 

Wenn das Array vollkommen sortiert, alles was wir tun müssen, wird bei jedem einzelnen Element zu suchen einmal, und dann sind wir fertig. Also im besten Fall ist es Omega der n. 

Ich bin Doug Lloyd. Dies ist CS50.