1 00:00:00,000 --> 00:00:02,290 [Powered by Google Translate] [Einfügung Sortieren] 2 00:00:02,290 --> 00:00:04,240 [Tommy MacWilliam] [Harvard University] 3 00:00:04,240 --> 00:00:07,290 [Dies ist CS50.TV] 4 00:00:07,290 --> 00:00:13,060 Werfen wir einen Blick auf insertion sort, ein Algorithmus für die Aufnahme einer Liste von Zahlen und sortieren. 5 00:00:13,060 --> 00:00:18,300 Ein Algorithmus, erinnern, ist einfach eine Schritt-für-Schritt-Verfahren für die Erfüllung einer Aufgabe. 6 00:00:18,300 --> 00:00:23,640 Die grundlegende Idee hinter Insertion Sort ist unsere Liste in zwei Teile zu teilen, 7 00:00:23,640 --> 00:00:26,580 eine sortierte Abschnitt und einen unsortierten Teil. 8 00:00:26,580 --> 00:00:29,290 >> Bei jedem Schritt des Algorithmus wird eine Zahl verschoben 9 00:00:29,290 --> 00:00:32,439 aus dem unsortierten Teil zum sortierten Teil 10 00:00:32,439 --> 00:00:35,680 bis schließlich die gesamte Liste sortiert ist. 11 00:00:35,680 --> 00:00:43,340 Hier ist die Liste von sechs unsortierten Zahlen - 23, 42, 4, 16, 8, und 15. 12 00:00:43,340 --> 00:00:47,680 Da diese Zahlen nicht alle in aufsteigender Reihenfolge, sie unsortiert. 13 00:00:47,680 --> 00:00:53,890 Da wir noch nicht begonnen haben Sortier noch, wir betrachten alle sechs Elemente unserer unsortierten Teil. 14 00:00:53,890 --> 00:00:59,270 >> Sobald wir Sortier starten, werden wir diese sortiert Zahlen links von ihnen setzen. 15 00:00:59,270 --> 00:01:03,600 Also, lasst uns mit 23, das erste Element in unserer Liste zu starten. 16 00:01:03,600 --> 00:01:06,930 Wir haben noch keine Elemente in unserer sortiert Teil noch 17 00:01:06,930 --> 00:01:12,460 also lasst uns einfach halten 23 bis Anfang und Ende unserer sortiert Teil. 18 00:01:12,460 --> 00:01:16,510 Jetzt hat unsere sortiert Teil eine Zahl, 23, 19 00:01:16,510 --> 00:01:20,260 und unsere unsortierten Teil hat diese fünf Zahlen. 20 00:01:20,260 --> 00:01:27,320 Lassen Sie uns jetzt legen Sie die nächste Nummer in unserem unsortierten Teil, 42, in die sortierte Teil. 21 00:01:27,320 --> 00:01:35,930 >> Um dies zu tun, brauchen wir, um die 42 mit der 23 zu vergleichen - das einzige Element in unserem sortiert Teil so weit. 22 00:01:35,930 --> 00:01:41,980 Forty-two ist größer als 23, so können wir einfach anhängen 42 bis zum Ende 23 00:01:41,980 --> 00:01:45,420 der sortierten Teil der Liste. Great! 24 00:01:45,420 --> 00:01:51,850 Jetzt unsere sortiert Abschnitt zwei Elementen, und unsere unsortierten Abschnitt weist vier Elemente. 25 00:01:51,850 --> 00:01:57,200 Also, lasst uns nun auf die 4 zu bewegen, das nächste Element in der unsortierten Teil. 26 00:01:57,200 --> 00:02:00,230 Also, sollten, wo dies in der sortierten Teil platziert werden? 27 00:02:00,230 --> 00:02:04,220 >> Denken Sie daran, wir wollen diese Zahl in sortierter Reihenfolge zu platzieren 28 00:02:04,220 --> 00:02:08,680 so dass unsere sortiert Teil bleibt jederzeit korrekt sortiert. 29 00:02:08,680 --> 00:02:14,380 Wenn wir die 4 auf der rechten Seite der 42 zu platzieren, dann ist unsere Liste wird aus sein, in Ordnung. 30 00:02:14,380 --> 00:02:18,380 Also, lasst uns weiter bewegen rechts-nach-links in unserem sort Abschnitt. 31 00:02:18,380 --> 00:02:23,260 Wie wir uns bewegen, wir verschieben jede Zahl auf einen Ort, um Platz für die neue Nummer. 32 00:02:25,440 --> 00:02:31,740 Okay, das ist 4 auch weniger als 23, so können wir nicht platzieren Sie es hier auch nicht. 33 00:02:31,740 --> 00:02:34,480 Gehen wir die 23 richtige Ort. 34 00:02:36,500 --> 00:02:43,120 >> Das heißt, wir möchten die 4 in den ersten Slot in der sortierten Teil platzieren. 35 00:02:43,120 --> 00:02:46,300 Beachten Sie, wie dieser Raum in der Liste schon leer, 36 00:02:46,300 --> 00:02:51,120 weil wir schon seit bewegen sortiert Elemente, die, wie wir sie erlebt habe. 37 00:02:51,120 --> 00:02:52,740 Gut. Also, wir sind auf halbem Wege. 38 00:02:52,740 --> 00:02:57,990 Lasst uns weiter unser Algorithmus, indem Sie die 16 in der sortierten Teil. 39 00:02:59,260 --> 00:03:03,820 Sechzehn weniger als 42, also lasst verschieben die 42 auf der rechten Seite. 40 00:03:05,700 --> 00:03:10,190 Sechzehn ist auch weniger als 23, also lasst uns auch verschieben das Element. 41 00:03:11,790 --> 00:03:20,820 >> 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. 42 00:03:20,820 --> 00:03:24,620 Während der Bewegung durch die sortierte Teil der Liste von rechts nach links, 43 00:03:24,620 --> 00:03:29,160 4 ist die erste Zahl die wir gesehen haben, die kleiner ist als die Zahl 44 00:03:29,160 --> 00:03:31,540 wir versuchen, einzufügen. 45 00:03:31,540 --> 00:03:35,820 So, jetzt können wir die 16 in diesem leeren Slot stecken, 46 00:03:35,820 --> 00:03:40,520 die, denken Sie daran, wir haben von beweglichen Elementen in der Art Teil über erstellt 47 00:03:40,520 --> 00:03:43,340 wie wir ihnen begegneten. 48 00:03:43,340 --> 00:03:47,900 >> Gut. Jetzt haben wir vier sortierte Elemente und zwei unsortierten Elementen. 49 00:03:47,900 --> 00:03:51,600 Also, lasst uns bewegen Sie die 8 in der sortierten Teil. 50 00:03:51,600 --> 00:03:55,010 Acht weniger als 42. 51 00:03:55,010 --> 00:03:56,940 Acht kleiner ist als 23. 52 00:03:56,940 --> 00:04:00,230 Und 8 ist kleiner als 16 ist. 53 00:04:00,230 --> 00:04:03,110 Aber 8 größer als 4 ist. 54 00:04:03,110 --> 00:04:07,280 So möchten wir die 8 zwischen der 4 und der 16 einzufügen. 55 00:04:09,070 --> 00:04:13,650 Und jetzt müssen wir nur noch ein Element links zu sortieren - die 15. 56 00:04:13,950 --> 00:04:16,589 Fünfzehn ist weniger als 42, 57 00:04:16,589 --> 00:04:19,130 Fünfzehn kleiner als 23. 58 00:04:19,130 --> 00:04:21,750 Und 15 ist kleiner als 16 ist. 59 00:04:21,750 --> 00:04:24,810 Aber 15 größer als 8 ist. 60 00:04:24,810 --> 00:04:27,440 >> So, hier ist, wo wir unsere letzte Einfügung machen wollen. 61 00:04:28,770 --> 00:04:30,330 Und wir sind fertig. 62 00:04:30,330 --> 00:04:33,540 Wir haben keine mehr Elemente in der unsortierten Teil, 63 00:04:33,540 --> 00:04:36,670 und unsere sortiert Teil in der richtigen Reihenfolge. 64 00:04:36,670 --> 00:04:40,270 Die Zahlen werden vom kleinsten zum größten geordnet. 65 00:04:40,270 --> 00:04:44,330 Also, lassen Sie uns einen Blick auf einige Pseudocode, der die Schritte, die wir soeben durchgeführten beschreibt. 66 00:04:46,760 --> 00:04:51,740 >> Auf der Linie 1, können wir sehen, dass wir brauchen, um durchlaufen jedes Element in der Liste 67 00:04:51,740 --> 00:04:57,060 mit Ausnahme der ersten, wird seit dem ersten Element in der unsortierten Abschnitt einfach geworden 68 00:04:57,060 --> 00:05:00,220 das erste Element in dem Abschnitt sortiert. 69 00:05:00,220 --> 00:05:06,320 Auf den Linien 2 und 3, sind wir die Verfolgung von unseren aktuellen Platz in der unsortierten Teil. 70 00:05:06,320 --> 00:05:10,450 Element stellt die Zahl, die wir gerade in Bewegung sind in der sortierten Teil, 71 00:05:10,450 --> 00:05:15,600 und j unserem Index in den unsortierten Teil. 72 00:05:15,600 --> 00:05:20,980 >> Zeile 4 sind wir durch die sortierte Teil von rechts nach links durchlaufen. 73 00:05:20,980 --> 00:05:26,010 Wir wollen zu stoppen Iteration einmal das Element auf der linken Seite unserer aktuellen Position 74 00:05:26,010 --> 00:05:30,050 ist weniger als das Element wir versuchen, einzufügen sind. 75 00:05:30,050 --> 00:05:35,600 In Zeile 5, wir verschieben jedes Element begegnen wir einem Raum auf der rechten Seite. 76 00:05:35,600 --> 00:05:40,950 So, haben wir einen klaren Raum zu legen, wenn wir das erste Element zu finden 77 00:05:40,950 --> 00:05:44,080 weniger als das Element wir uns bewegen. 78 00:05:44,080 --> 00:05:50,800 In Zeile 6, wir aktualisieren unsere Zähler weiter nach links zu bewegen, durch die sortierte Teil. 79 00:05:50,800 --> 00:05:56,860 Schließlich on line 7, wir Einfügen des Elements in der sortierten Teil der Liste. 80 00:05:56,860 --> 00:06:00,020 >> Wir wissen, dass es okay ist, in Position j einzufügen ist, 81 00:06:00,020 --> 00:06:05,360 weil wir bereits das Element, das da zu sein um eine Stelle nach rechts eingesetzt verschoben. 82 00:06:05,360 --> 00:06:09,460 Denken Sie daran, wir sind durch den sortierten Teil von rechts nach links, 83 00:06:09,460 --> 00:06:13,960 aber wir sind durch den unsortierten Teil von links nach rechts bewegt. 84 00:06:13,960 --> 00:06:19,090 Gut. Lassen Sie uns nun einen Blick auf, wie lange läuft, dass Algorithmus nahm. 85 00:06:19,090 --> 00:06:25,300 Wir werden zuerst die Frage stellen, wie lange dauert es, bis dieser Algorithmus im schlimmsten Fall laufen. 86 00:06:25,300 --> 00:06:29,040 Daran erinnern, dass wir diese Laufzeit stellen mit Big O-Notation. 87 00:06:32,530 --> 00:06:38,500 Um unsere Liste zu sortieren, mussten wir iterieren die Elemente in der unsortierten Teil, 88 00:06:38,500 --> 00:06:43,430 und für jedes dieser Elemente, potenziell über alle Elemente in der sortierten Abschnitts. 89 00:06:43,430 --> 00:06:47,950 Intuitiv, das klingt wie ein O (n ^ 2)-Operation. 90 00:06:47,950 --> 00:06:51,840 >> Mit Blick auf unsere Pseudocode, haben wir eine Schleife innerhalb einer anderen Schleife verschachtelt, 91 00:06:51,840 --> 00:06:55,290 die tatsächlich klingt wie ein O (n ^ 2)-Operation. 92 00:06:55,290 --> 00:07:01,590 Allerdings hat die sortierten Teil der Liste nicht enthalten die gesamte Liste, bis zum bitteren Ende. 93 00:07:01,590 --> 00:07:06,920 Dennoch konnten wir potenziell legen ein neues Element am Anfang der sortierten Teil 94 00:07:06,920 --> 00:07:09,320 bei jeder Iteration des Algorithmus, 95 00:07:09,320 --> 00:07:14,500 was bedeutet, dass wir müssten an jedem Element derzeit aussehen in der sortierten Teil. 96 00:07:14,500 --> 00:07:20,090 Das bedeutet also, dass wir so möglicherweise ein Vergleich für das zweite Element, 97 00:07:20,090 --> 00:07:24,660 zwei Vergleiche für das dritte Element und so weiter. 98 00:07:24,660 --> 00:07:32,480 So ist die Anzahl der Schritte die Summe der ganzen Zahlen von 1 bis zur Länge der Liste minus 1 ist. 99 00:07:32,480 --> 00:07:35,240 Wir können dies mit einer Summierung darstellen. 100 00:07:41,170 --> 00:07:47,270 >> Wir werden nicht in Summen gehen, aber es stellt sich heraus, dass diese Summe gleich ist 101 00:07:47,270 --> 00:07:57,900 n (n - 1) mehr als 2, was äquivalent n ^ 2/2 - n / 2. 102 00:07:57,900 --> 00:08:00,800 Wenn man über die asymptotische Laufzeit 103 00:08:00,800 --> 00:08:05,170 Diese n ^ 2 Begriff wird diesen n Begriff dominieren. 104 00:08:05,170 --> 00:08:11,430 So ist Insertion Sort Big O (n ^ 2). 105 00:08:11,430 --> 00:08:16,150 Was, wenn wir insertion sort lief auf eine bereits sortierte Liste. 106 00:08:16,150 --> 00:08:20,960 In diesem Fall würden wir einfach Aufbau des sortierten Teils von links nach rechts. 107 00:08:20,960 --> 00:08:25,050 So werden wir nur in der Größenordnung von n Schritte müssen. 108 00:08:25,050 --> 00:08:29,740 >> Das bedeutet, dass insertion sort ein Best-Case-Performance n hat, 109 00:08:29,740 --> 00:08:34,130 denen wir vertreten mit Ω (n). 110 00:08:34,130 --> 00:08:36,190 Und das ist es für insertion sort, 111 00:08:36,190 --> 00:08:40,429 nur eine der vielen Algorithmen, die wir verwenden können, um eine Liste zu sortieren. 112 00:08:40,429 --> 00:08:43,210 Mein Name ist Tommy, und dies ist CS50. 113 00:08:43,210 --> 00:08:44,880 [CS50.TV] 114 00:08:46,110 --> 00:08:49,230 Oh, man kann einfach nicht aufhören, dass, sobald er gestartet wird. 115 00:09:01,620 --> 00:09:04,760 Oh, wir haben das - >> Boom!