1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] TOMMY: Werfen wir einen Blick auf Auswahl sortieren, ein Algorithmus 2 00:00:09,980 --> 00:00:12,800 für die Aufnahme einer Liste von Zahlen und sortieren. 3 00:00:12,800 --> 00:00:15,750 Ein Algorithmus, erinnern, ist einfach eine Schritt-für-Schritt 4 00:00:15,750 --> 00:00:18,370 Verfahren zur Durchführung einer Aufgabe. 5 00:00:18,370 --> 00:00:21,470 Die Grundidee Auswahl Art ist zu teilen 6 00:00:21,470 --> 00:00:23,390 unserer Liste in zwei Teile - 7 00:00:23,390 --> 00:00:26,810 eine sortierte Abschnitt und einen unsortierten Teil. 8 00:00:26,810 --> 00:00:30,200 Bei jedem Schritt des Algorithmus wird eine Rufnummer aus dem bewegten 9 00:00:30,200 --> 00:00:33,800 unsortierten Abschnitt zu dem Abschnitt sortiert bis schließlich die 10 00:00:33,800 --> 00:00:35,880 gesamte Liste sortiert ist. 11 00:00:35,880 --> 00:00:38,510 Also hier ist eine Liste von sechs Nummern - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8 und 15. 13 00:00:44,010 --> 00:00:47,680 Gerade jetzt die gesamte Liste wird als unsortiert. 14 00:00:47,680 --> 00:00:51,770 Auch wenn eine Reihe wie 16 bereits in seiner korrekten sein 15 00:00:51,770 --> 00:00:56,040 Lage hat unser Algorithmus nicht wissen, dass bis zum 16 00:00:56,040 --> 00:00:57,980 gesamte Liste sortiert ist. 17 00:00:57,980 --> 00:01:01,355 So wir betrachten jede Zahl zu unsortiert bis wir sortieren 18 00:01:01,355 --> 00:01:03,800 es selbst gemacht. 19 00:01:03,800 --> 00:01:06,890 Wir wissen, dass wir die Liste in aufsteigender Reihenfolge sein wollen. 20 00:01:06,890 --> 00:01:10,200 Also werden wir aufbauen wollen die sortierte Teil unserer Liste 21 00:01:10,200 --> 00:01:13,280 von links nach rechts, vom kleinsten zum größten. 22 00:01:13,280 --> 00:01:17,970 Um dies zu tun, brauchen wir, um die minimale unsortierten Element zu finden 23 00:01:17,970 --> 00:01:21,350 und ihn am Ende der sortierten Abschnitts. 24 00:01:21,350 --> 00:01:25,370 Da diese Liste nicht sortiert ist, ist der einzige Weg, das zu tun, um 25 00:01:25,370 --> 00:01:29,330 Blick auf jedes Element in der unsortierten Teil, erinnern 26 00:01:29,330 --> 00:01:32,010 welches Element ist die niedrigste und Vergleichen 27 00:01:32,010 --> 00:01:33,770 jedes Element dazu. 28 00:01:33,770 --> 00:01:36,150 Also werden wir zunächst an der 23 aussehen. 29 00:01:36,150 --> 00:01:38,650 Dies ist das erste Element, das wir gesehen haben, so dass wir daran erinnern, 30 00:01:38,650 --> 00:01:40,050 es als das Minimum. 31 00:01:40,050 --> 00:01:42,320 Als nächstes werden wir bei 42 aussehen. 32 00:01:42,320 --> 00:01:46,720 42 ist größer als 23, so ist immer noch die 23 Minimum. 33 00:01:46,720 --> 00:01:51,210 Weiter ist die 4, die weniger als 23 ist, so dass wir 4 erinnern 34 00:01:51,210 --> 00:01:52,880 als neue Minimum. 35 00:01:52,880 --> 00:01:56,380 Weiter ist 16, die größer als 4 ist, also 4 36 00:01:56,380 --> 00:01:57,980 noch das Minimum. 37 00:01:57,980 --> 00:02:03,670 8 ist größer als 4 und 15 ist größer als 4, so muß 4 38 00:02:03,670 --> 00:02:05,980 der kleinste unsortierten Element. 39 00:02:05,980 --> 00:02:09,350 Also auch wenn wir als Menschen können sofort sehen, dass 4 ist 40 00:02:09,350 --> 00:02:12,300 das kleinste Element, muss unser Algorithmus zu betrachten 41 00:02:12,300 --> 00:02:15,710 jeden unsortierten Element, selbst nachdem wir die 4 gefunden - die 42 00:02:15,710 --> 00:02:16,860 kleinste Element. 43 00:02:16,860 --> 00:02:19,900 So, jetzt haben wir das kleinste Element, 4 gefunden, wir möchten 44 00:02:19,900 --> 00:02:23,410 um es in der sortierten Teil der Liste zu verschieben. 45 00:02:23,410 --> 00:02:27,320 Da dies der erste Schritt, bedeutet dies, wir wollen 4 bei setzen 46 00:02:27,320 --> 00:02:29,680 der Anfang der Liste. 47 00:02:29,680 --> 00:02:33,040 Gerade jetzt 23 steht am Anfang der Liste, so 48 00:02:33,040 --> 00:02:36,080 wir tauschen die 4 und die 23. 49 00:02:36,080 --> 00:02:38,870 So, jetzt unsere Liste sieht wie folgt aus. 50 00:02:38,870 --> 00:02:42,710 Wir wissen, dass 4 muss an seinem endgültigen Standort sein, denn es ist 51 00:02:42,710 --> 00:02:45,890 sowohl das kleinste Element und das Element am Anfang 52 00:02:45,890 --> 00:02:46,960 der Liste. 53 00:02:46,960 --> 00:02:50,650 Dies bedeutet also, dass wir nicht immer müssen es wieder zu bewegen. 54 00:02:50,650 --> 00:02:53,910 Also lasst uns diesen Vorgang wiederholen, um ein weiteres Element, um das Add 55 00:02:53,910 --> 00:02:55,910 sortierten Teil der Liste. 56 00:02:55,910 --> 00:02:58,950 Wir wissen, dass wir nicht brauchen, um an der 4 aussehen, weil es 57 00:02:58,950 --> 00:03:00,000 bereits sortiert. 58 00:03:00,000 --> 00:03:03,540 So können wir auf die 42 zu starten, was wir als die erinnern 59 00:03:03,540 --> 00:03:05,290 kleinste Element. 60 00:03:05,290 --> 00:03:08,700 Also das nächste wir an der 23, die weniger als 42 ist zu sehen, so dass wir 61 00:03:08,700 --> 00:03:11,620 Speichern 23 ist das neue Minimum. 62 00:03:11,620 --> 00:03:14,870 Weiter sehen wir die 16, die weniger als 23 ist, so 63 00:03:14,870 --> 00:03:16,800 16 ist das neue Minimum. 64 00:03:16,800 --> 00:03:19,720 Nun auf 8, die weniger als 16 ist zu sehen, so dass 65 00:03:19,720 --> 00:03:21,130 8 ist das neue Minimum. 66 00:03:21,130 --> 00:03:25,900 Und schließlich 8 weniger als 15, so wissen wir, dass 8 ein Minimum ist 67 00:03:25,900 --> 00:03:27,780 unsortierten Element. 68 00:03:27,780 --> 00:03:30,660 Das heißt also, wir sollten 8 bis sortierten anhängen 69 00:03:30,660 --> 00:03:32,450 Teil der Liste. 70 00:03:32,450 --> 00:03:35,990 Gerade jetzt 4 ist die einzige sortiert Element, so wollen wir platzieren 71 00:03:35,990 --> 00:03:38,410 die 8 neben dem 4. 72 00:03:38,410 --> 00:03:41,920 Da 42 ist das erste Element in dem Teil des unsortierten 73 00:03:41,920 --> 00:03:47,260 Liste, wir wollen die 42 und die 8 tauschen. 74 00:03:47,260 --> 00:03:49,680 So, jetzt unsere Liste sieht wie folgt aus. 75 00:03:49,680 --> 00:03:53,830 4 und 8 stellen die sortierte Teils der Liste, und das 76 00:03:53,830 --> 00:03:56,440 restlichen Zahlen stellen den unsortierten 77 00:03:56,440 --> 00:03:58,260 Teil der Liste. 78 00:03:58,260 --> 00:04:00,630 Lassen Sie uns also mit einer anderen Iteration fortsetzen. 79 00:04:00,630 --> 00:04:03,850 Wir beginnen mit 23 dieses Mal, da brauchen wir nicht zu sehen 80 00:04:03,850 --> 00:04:05,770 die 4 und die 8 nicht mehr, weil sie haben 81 00:04:05,770 --> 00:04:07,660 bereits sortiert. 82 00:04:07,660 --> 00:04:10,270 16 ist kleiner als 23, so dass wir daran erinnern, 83 00:04:10,270 --> 00:04:12,070 16 als neue Minimum. 84 00:04:12,070 --> 00:04:18,149 16 ist kleiner als 42, aber weniger als 15 16, 15 muß so 85 00:04:18,149 --> 00:04:20,480 die minimale unsortierten Element. 86 00:04:20,480 --> 00:04:24,580 So, jetzt wollen wir die 15 und die 23 zu tauschen 87 00:04:24,580 --> 00:04:26,310 uns diese Liste. 88 00:04:26,310 --> 00:04:30,500 Die sortierte Teil der Liste besteht aus 4, 8 und 15, und 89 00:04:30,500 --> 00:04:33,210 diese Elemente sind immer noch unsortiert. 90 00:04:33,210 --> 00:04:36,900 Aber es passiert einfach so, dass die nächste unsortierten Element 16, 91 00:04:36,900 --> 00:04:38,480 bereits sortiert. 92 00:04:38,480 --> 00:04:42,060 Allerdings gibt es keine Möglichkeit für unser Algorithmus zu wissen, dass 16 93 00:04:42,060 --> 00:04:45,230 ist bereits in die richtige Position, so müssen wir noch 94 00:04:45,230 --> 00:04:47,870 wiederholen exakt den gleichen Prozess. 95 00:04:47,870 --> 00:04:53,750 Wir sehen, dass weniger als 16 42 ist, und 16 ist kleiner als 23, so 96 00:04:53,750 --> 00:04:56,230 16 muss das kleinste Element sein. 97 00:04:56,230 --> 00:04:59,010 Es ist unmöglich, dieses Element mit sich selbst tauschen, so können wir 98 00:04:59,010 --> 00:05:01,780 lassen Sie es einfach in dieser Lage. 99 00:05:01,780 --> 00:05:04,660 Also brauchen wir noch ein Pass von unserem Algorithmus. 100 00:05:04,660 --> 00:05:09,370 42 ist größer als 23, so 23 muss das sein 101 00:05:09,370 --> 00:05:10,970 minimale unsortierten Element. 102 00:05:10,970 --> 00:05:17,410 Sobald wir tauschen die 23 und die 42, haben wir am Ende mit unserem letzten 103 00:05:17,410 --> 00:05:18,530 sortierte Liste - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Wir wissen, 42 muss an der richtigen Stelle zu sein, da es das ist 106 00:05:26,830 --> 00:05:30,210 einzige Element links, und das ist Auswahl sort. 107 00:05:30,210 --> 00:05:32,100 Lassen Sie uns nun zu formalisieren unser Algorithmus mit einigen 108 00:05:32,100 --> 00:05:34,540 Pseudocode. 109 00:05:34,540 --> 00:05:37,760 On line ein, können wir sehen, dass wir die Integration über brauchen 110 00:05:37,760 --> 00:05:39,530 jedes Element der Liste. 111 00:05:39,530 --> 00:05:42,150 Außer dem letzten Element, da die 1-Element 112 00:05:42,150 --> 00:05:44,230 Liste bereits sortiert. 113 00:05:44,230 --> 00:05:48,100 Auf Leitung zwei, betrachten wir das erste Element des unsortierten 114 00:05:48,100 --> 00:05:51,080 Teil der Liste, um das Minimum sein, wie wir mit unseren getan 115 00:05:51,080 --> 00:05:53,750 Beispielsweise, so haben wir etwas zu vergleichen. 116 00:05:53,750 --> 00:05:57,260 Zeile drei beginnt eine zweite Schleife, in denen wir iterieren 117 00:05:57,260 --> 00:05:59,170 Jede unsortierten Element. 118 00:05:59,170 --> 00:06:02,150 Wir wissen, dass, nachdem ich Iterationen, die sortierte Teil 119 00:06:02,150 --> 00:06:05,330 unserer Liste muss i Elemente in ihr, da jeder Schritt 120 00:06:05,330 --> 00:06:06,890 Arten aus einem Element. 121 00:06:06,890 --> 00:06:11,770 Also der erste unsortierten Element muss in der Position i plus 1 sein. 122 00:06:11,770 --> 00:06:15,440 On line vier, vergleichen wir das aktuelle Element auf das Minimum 123 00:06:15,440 --> 00:06:17,750 Element, das wir bisher gesehen haben. 124 00:06:17,750 --> 00:06:20,560 Wenn das aktuelle Element kleiner ist als die minimale 125 00:06:20,560 --> 00:06:23,870 Element, dann erinnern wir uns das aktuelle Element als neue 126 00:06:23,870 --> 00:06:26,250 minimale on line fünf. 127 00:06:26,250 --> 00:06:29,900 Schließlich auf Leitungen sechs und sieben, tauschen wir die minimale 128 00:06:29,900 --> 00:06:33,080 Element mit dem ersten Element unsortierter, wodurch 129 00:06:33,080 --> 00:06:36,990 Zugabe zu dem sortierten Teil der Liste. 130 00:06:36,990 --> 00:06:40,030 Sobald wir einen Algorithmus haben, eine wichtige Frage stellen 131 00:06:40,030 --> 00:06:43,370 uns als Programmierer ist, wie lange hat das gedauert? 132 00:06:43,370 --> 00:06:46,970 Wir werden zuerst die Frage stellen, wie lange dauert es, bis dieser Vorgang 133 00:06:46,970 --> 00:06:50,070 Algorithmus im schlimmsten Fall laufen? 134 00:06:50,070 --> 00:06:51,640 Erinnern wir uns stellen diese Lauf 135 00:06:51,640 --> 00:06:55,060 Zeit mit O-Notation. 136 00:06:55,060 --> 00:06:58,650 Um die minimale unsortierten Elementes zu bestimmen, haben wir 137 00:06:58,650 --> 00:07:01,880 hatte im Wesentlichen um jedes Element in der Liste zu vergleichen 138 00:07:01,880 --> 00:07:04,040 jedes andere Element in der Liste. 139 00:07:04,040 --> 00:07:08,430 Intuitiv, das klingt wie ein O n squared Betrieb. 140 00:07:08,430 --> 00:07:12,050 Mit Blick auf unsere Pseudocode, haben wir auch eine Schleife verschachtelt Inneren 141 00:07:12,050 --> 00:07:14,420 eine weitere Schleife, die tatsächlich klingt wie ein O 142 00:07:14,420 --> 00:07:16,480 von n quadrierten Betrieb. 143 00:07:16,480 --> 00:07:19,250 Beachten Sie jedoch, dass wir nicht brauchen, um über die aussehen 144 00:07:19,250 --> 00:07:23,460 gesamte Liste bei der Bestimmung der minimalen unsortierten Element? 145 00:07:23,460 --> 00:07:26,600 Sobald wir wussten, dass die 4 sortiert wurde, zum Beispiel, haben wir nicht 146 00:07:26,600 --> 00:07:28,170 müssen noch einmal anschauen. 147 00:07:28,170 --> 00:07:31,020 So funktioniert das untere die Laufzeit? 148 00:07:31,020 --> 00:07:34,510 Für unsere Liste der Länge 6, mussten wir fünf machen 149 00:07:34,510 --> 00:07:37,990 Vergleiche für das erste Element, vier Vergleiche für 150 00:07:37,990 --> 00:07:40,750 das zweite Element, und so weiter. 151 00:07:40,750 --> 00:07:44,690 Das bedeutet, dass die Gesamtzahl der Schritte ist die Summe von 152 00:07:44,690 --> 00:07:49,160 die ganzen Zahlen von 1 bis zur Länge der Liste minus 1 ist. 153 00:07:49,160 --> 00:07:51,005 Wir können dies mit einer Summierung darstellen. 154 00:07:57,980 --> 00:07:59,910 Wir werden nicht in Summen hier. 155 00:07:59,910 --> 00:08:04,900 Es zeigt sich aber, dass diese Summierung gleich n mal ist 156 00:08:04,900 --> 00:08:07,540 n minus 1 über 2. 157 00:08:07,540 --> 00:08:14,220 Oder äquivalent, n quadriert über 2 minus n über 2. 158 00:08:14,220 --> 00:08:18,860 Wenn man über die asymptotische Laufzeit dieses n quadrierten Terms 159 00:08:18,860 --> 00:08:22,070 wird dieses n Begriff dominieren. 160 00:08:22,070 --> 00:08:27,850 So Auswahl Art ist O n Quadrat. 161 00:08:27,850 --> 00:08:31,460 Daran erinnern, dass in unserem Beispiel, Auswahl sort noch erforderlich, um 162 00:08:31,460 --> 00:08:33,850 prüfen, ob eine Zahl, die bereits sortiert wurde 163 00:08:33,850 --> 00:08:35,450 benötigt, um bewegt werden. 164 00:08:35,450 --> 00:08:38,929 Das heißt also, dass, wenn wir liefen Auswahl sort über eine bereits 165 00:08:38,929 --> 00:08:43,070 sortierten Liste, würde es erfordern die gleiche Anzahl von Schritten, wie sie 166 00:08:43,070 --> 00:08:46,340 wäre beim Lauf über eine völlig unsortierte Liste. 167 00:08:46,340 --> 00:08:51,470 So Auswahl Art hat eine best case Leistung von n squared, 168 00:08:51,470 --> 00:08:56,820 denen wir vertreten mit Omega n Quadrat. 169 00:08:56,820 --> 00:08:58,600 Und das ist es für die Auswahl sort. 170 00:08:58,600 --> 00:09:00,630 Nur eine der vielen Algorithmen können wir 171 00:09:00,630 --> 00:09:02,390 verwenden, um eine Liste zu sortieren. 172 00:09:02,390 --> 00:09:05,910 Mein Name ist Tommy, und dies ist CS50.