1 00:00:00,000 --> 00:00:03,332 >> [Musikwiedergabe] 2 00:00:03,332 --> 00:00:06,490 >> ANDI PENG: Willkommen in Woche 3 der Sektion. 3 00:00:06,490 --> 00:00:09,550 Vielen Dank, Jungs, für alle kommenden auf diese frühere Startzeit heute. 4 00:00:09,550 --> 00:00:11,466 Wir haben einen schönen, kleinen intime Gruppe heute. 5 00:00:11,466 --> 00:00:14,570 Also hoffentlich werden wir zu bekommen Finish, vielleicht, früh, 6 00:00:14,570 --> 00:00:15,780 ein bisschen früh heute. 7 00:00:15,780 --> 00:00:22,057 So schnell, nur einige Ankündigungen für die Tagesordnung heute. 8 00:00:22,057 --> 00:00:23,890 Bevor wir beginnen, sind wir werde einfach gehen über 9 00:00:23,890 --> 00:00:28,910 einige kurze logistische Probleme, pset Fragen, Nachbesprechung, solche Dinge. 10 00:00:28,910 --> 00:00:30,250 Und dann werden wir tauchen rechts in. 11 00:00:30,250 --> 00:00:34,710 Wir werden einen Debugger GDB genannt zu bedienen starten Entlarvung unseren Code, der David 12 00:00:34,710 --> 00:00:36,550 in der Vorlesung erläutert den anderen Tag. 13 00:00:36,550 --> 00:00:39,420 Wir werden über die vier Arten von Arten zu gehen. 14 00:00:39,420 --> 00:00:42,310 Wir werden über sie ziemlich schnell gehen denn sie sind ziemlich intensiv. 15 00:00:42,310 --> 00:00:45,710 Aber wissen, dass alle Folien und Source-Code sind immer online. 16 00:00:45,710 --> 00:00:50,810 So fühlen sich frei, um Ihre Durchsicht, um gehen Sie zurück und schauen Sie sich das. 17 00:00:50,810 --> 00:00:53,930 >> Wir werden durchgehen asymptotische Notation, die 18 00:00:53,930 --> 00:00:55,944 ist nur eine andere Art zu sagen: "Laufzeiten" 19 00:00:55,944 --> 00:00:58,360 wo wir die große O, die David erklärte im Vortrag. 20 00:00:58,360 --> 00:01:01,550 Und wir haben auch Omega, die ist die untere Grenze der Laufzeit. 21 00:01:01,550 --> 00:01:06,450 Und wir werden ein bisschen mehr reden eingehende über, wie diese Arbeit. 22 00:01:06,450 --> 00:01:10,160 Und schließlich werden wir über binäre Suche zu gehen, weil viele von euch, die bereits 23 00:01:10,160 --> 00:01:15,190 warf einen Blick auf Ihre psets wahrscheinlich wissen, dass das ist eine Frage, die in Ihrem pset ist. 24 00:01:15,190 --> 00:01:17,470 So werden Sie alle glücklich sein dass wir dies heute abdecken. 25 00:01:17,470 --> 00:01:20,610 >> Und schließlich, nach Ihren Abschnitt Feedback, habe ich eigentlich 26 00:01:20,610 --> 00:01:23,000 auf der linken Seite ca. 15 Minuten das Ende, um nur übergehen 27 00:01:23,000 --> 00:01:27,730 Logistik pset3, Fragen, vielleicht eine gewisse Orientierungshilfe, wenn man so will, 28 00:01:27,730 --> 00:01:28,990 bevor wir beginnen Programmierung. 29 00:01:28,990 --> 00:01:30,890 Also lassen Sie uns versuchen, durchzukommen das Material ziemlich schnell. 30 00:01:30,890 --> 00:01:33,880 Und dann haben wir einige Zeit damit verbringen können nehmen mehr Fragen für die pset. 31 00:01:33,880 --> 00:01:35,230 OK. 32 00:01:35,230 --> 00:01:39,570 >> Schnell, so dass nur ein paar Ankündigungen, bevor wir beginnen heute. 33 00:01:39,570 --> 00:01:45,410 Erstens, willkommen zu machen es durch zwei Ihrer psets. 34 00:01:45,410 --> 00:01:49,432 Ich warf einen Blick auf your-- ja, lassen Sie uns bekommen eine Runde Applaus für diesen einen. 35 00:01:49,432 --> 00:01:51,140 Eigentlich war ich wirklich, wirklich beeindruckt. 36 00:01:51,140 --> 00:01:55,800 Ich benotet die erste pset für euch letzte Woche und du Jungs haben unglaublich. 37 00:01:55,800 --> 00:01:58,290 >> Stil war auf den Punkt außer ein paar Kommentare. 38 00:01:58,290 --> 00:02:00,660 Stellen Sie sicher, dass Sie immer Kommentieren Sie den Code. 39 00:02:00,660 --> 00:02:03,040 Aber Ihre psets waren auf den Punkt. 40 00:02:03,040 --> 00:02:05,549 Und weiter so. 41 00:02:05,549 --> 00:02:08,090 Und es ist gut für die Grader zu sehen, dass ihr Jungs setzen 42 00:02:08,090 --> 00:02:10,704 in so viel Mühe in Ihren Stil und Ihr Design in Ihrem Code 43 00:02:10,704 --> 00:02:12,120 dass wir gerne für Sie zu sehen. 44 00:02:12,120 --> 00:02:16,450 So bin ich auf meine Dankbarkeit vorbei für den Rest der TAs. 45 00:02:16,450 --> 00:02:19,210 >> Allerdings gibt es ein Nachbesprechung paar Fragen 46 00:02:19,210 --> 00:02:22,010 Ich will einfach nur hingehen, dass würde sowohl meinem Leben zu machen 47 00:02:22,010 --> 00:02:24,900 und eine Menge von anderen TAs 'lebt ein bisschen einfacher. 48 00:02:24,900 --> 00:02:28,220 Zum einen habe ich bemerkt, diese Vergangenheit week-- wie viele von euch 49 00:02:28,220 --> 00:02:32,301 läuft seit check50 auf Ihr Code, bevor Sie einreichen? 50 00:02:32,301 --> 00:02:32,800 OK. 51 00:02:32,800 --> 00:02:36,690 So sollte jeder check50 tun, because-- eine secret-- wir tatsächlich 52 00:02:36,690 --> 00:02:41,540 laufen check50 als Teil unserer Korrektheit Skripten zum Testen Ihres Codes. 53 00:02:41,540 --> 00:02:45,480 Also, wenn Ihr Code schlägt fehl check50, aller Wahrscheinlichkeit nach, 54 00:02:45,480 --> 00:02:47,570 es ist wahrscheinlich zu scheitern unsere Check als gut. 55 00:02:47,570 --> 00:02:49,320 Manchmal euch haben die richtigen Antworten. 56 00:02:49,320 --> 00:02:52,200 Wie in gierig, einige Sie haben das Recht zahlen, 57 00:02:52,200 --> 00:02:53,960 Sie gerade auszudrucken einige zusätzliche Sachen. 58 00:02:53,960 --> 00:02:55,940 Und das Extramaterial tatsächlich ausfällt das Kontroll, 59 00:02:55,940 --> 00:02:58,440 weil der Computer nicht wirklich, was es sucht. 60 00:02:58,440 --> 00:03:00,981 Und so wird es nur durchlaufen, sehen, dass Ihre Ausgabe nicht 61 00:03:00,981 --> 00:03:03,810 entsprechen, was wir erwarten, dass die Antwort zu sein, und markieren Sie es falsch ist. 62 00:03:03,810 --> 00:03:06,560 >> Und ich weiß, dass in passiert einige Ihrer Fälle dieser Woche. 63 00:03:06,560 --> 00:03:09,870 Also ging ich zurück und manuell herabgestuft jeden Code. 64 00:03:09,870 --> 00:03:12,780 In Zukunft aber, Bitte stellen Sie sicher, 65 00:03:12,780 --> 00:03:14,570 dass Sie laufen Check 50 auf Ihren Code. 66 00:03:14,570 --> 00:03:17,970 Da es sich um eine Art Schmerz für den TA zu haben, um zurück zu gehen und manuell regrade 67 00:03:17,970 --> 00:03:21,197 jeder einzelne pset für jeden Single, wenig verpasst Instanz. 68 00:03:21,197 --> 00:03:22,530 So dass ich nicht nehmen Sie keine Punkte. 69 00:03:22,530 --> 00:03:25,210 Ich glaube, ich nahm vielleicht ein oder zwei für Design. 70 00:03:25,210 --> 00:03:27,710 In der Zukunft jedoch, wenn Sie andernfalls check50 bist, 71 00:03:27,710 --> 00:03:31,330 Punkten genommen wird off auf Richtigkeit. 72 00:03:31,330 --> 00:03:35,020 >> Weiterhin sind psets aufgrund freitags am Mittag. 73 00:03:35,020 --> 00:03:38,990 Ich denke, es gibt eine siebenminütige Spät Nachfrist, die wir geben Ihnen. 74 00:03:38,990 --> 00:03:42,434 Per Harvard Zeit, sie zu dürfen 7 Minuten zu spät, alles zu sein. 75 00:03:42,434 --> 00:03:44,350 Also hier in Yale, werden wir sich an das auch. 76 00:03:44,350 --> 00:03:47,910 Aber ziemlich genau, um 12:07 Uhr, wenn Ihr pset ist nicht in, 77 00:03:47,910 --> 00:03:49,720 es wird so spät zu kennzeichnen. 78 00:03:49,720 --> 00:03:53,160 Und so, während es markiert ist so spät, ich bin der TA-- 79 00:03:53,160 --> 00:03:54,870 immer noch auf sein Gehalt von Ihren psets. 80 00:03:54,870 --> 00:03:56,760 So dass Sie immer noch ein Grad angezeigt. 81 00:03:56,760 --> 00:03:58,820 Jedoch wissen, dass bei das Ende des Semesters, 82 00:03:58,820 --> 00:04:02,270 alle späten psets wird nur sein, durch den Rechner automatisch genullt. 83 00:04:02,270 --> 00:04:04,490 >> Wir tun dies aus zwei Gründen. 84 00:04:04,490 --> 00:04:09,220 Eine, manchmal bekommen wir entschuldigt, wie Ausreden Dekans, 85 00:04:09,220 --> 00:04:10,762 später, dass ich nicht weiß, zu erhalten. 86 00:04:10,762 --> 00:04:13,761 So möchten wir sicherstellen, dass wir mit einem Gehalt alles nur für den Fall, wie ich bin 87 00:04:13,761 --> 00:04:15,080 fehlt ein Dekan Entschuldigung. 88 00:04:15,080 --> 00:04:17,000 Und zweitens, denken Geist, können Sie immer noch 89 00:04:17,000 --> 00:04:19,370 Drop eine pset dass hat vollen Umfang Punkten. 90 00:04:19,370 --> 00:04:21,430 Und so möchten wir Note alle Ihre psets gerade 91 00:04:21,430 --> 00:04:24,730 zu sicherzustellen, dass Ihr Handlungsspielraum dort und Sie versuchen ihnen. 92 00:04:24,730 --> 00:04:29,150 Also selbst wenn es spät ist, werden Sie noch Kredit für Umfang Punkte, denke ich. 93 00:04:29,150 --> 00:04:33,730 >> So Moral von der Geschichte ist, zu machen dass Ihr psets sind in Ein-Zeit. 94 00:04:33,730 --> 00:04:38,350 Und wenn sie sich nicht in Ein-Zeit, wissen, dass es nicht so toll. 95 00:04:38,350 --> 00:04:41,678 Ja, bevor ich weiterziehen, hat jemand Fragen in Bezug auf pset Feedback? 96 00:04:41,678 --> 00:04:42,178 Ja. 97 00:04:42,178 --> 00:04:43,630 >> ZIELGRUPPE: Haben Sie wir sagen, kann eine der psets fallen zu lassen? 98 00:04:43,630 --> 00:04:44,296 >> ANDI PENG: Ja. 99 00:04:44,296 --> 00:04:47,050 So gibt es neun psets Gesamt im Laufe des Semesters. 100 00:04:47,050 --> 00:04:50,610 Und wenn Sie Spielraum haben points-- so Umfang ist nur, 101 00:04:50,610 --> 00:04:53,567 ziemlich, werden Sie versuchen, die Problem, werden Sie setzen in der Zeit, 102 00:04:53,567 --> 00:04:56,150 Sie zeigen, dass Sie haben, demonstriert Ihnen die spec gelesen habe. 103 00:04:56,150 --> 00:04:57,191 Das ist ziemlich viel Spielraum. 104 00:04:57,191 --> 00:04:59,370 Und wenn Sie erfüllt sind, Geltungsbereich Punkte, die wir 105 00:04:59,370 --> 00:05:03,360 können die niedrigsten Drop einer von vollen Umfang. 106 00:05:03,360 --> 00:05:06,790 Also das ist in Ihrem Vorteil, abzuschließen und versuchen jeden pset. 107 00:05:06,790 --> 00:05:10,320 >> Sogar upload-- wenn keines ihnen zu arbeiten, laden Sie sie alle. 108 00:05:10,320 --> 00:05:13,711 Und dann werden wir hoffentlich in der Lage zu sein, geben Ihnen einige dieser Punkte zurück. 109 00:05:13,711 --> 00:05:14,210 Cool. 110 00:05:14,210 --> 00:05:16,780 Noch Fragen? 111 00:05:16,780 --> 00:05:17,840 Groß. 112 00:05:17,840 --> 00:05:21,960 >> Zweitens hours-- Büro ein paar schnelle Notizen zu Bürozeiten. 113 00:05:21,960 --> 00:05:24,300 So zuerst, Anfang der Woche zu kommen. 114 00:05:24,300 --> 00:05:26,909 Niemand ist jemals auf Bürozeiten montags. 115 00:05:26,909 --> 00:05:28,700 Christabel zu kam Bürozeiten gestern Abend. 116 00:05:28,700 --> 00:05:29,691 Ja, Christabel. 117 00:05:29,691 --> 00:05:32,190 Und was haben wir im Büro Stunden letzte Nacht, Christabel? 118 00:05:32,190 --> 00:05:33,020 >> Publikum: Wir hatten Eis. 119 00:05:33,020 --> 00:05:36,160 >> ANDI PENG: Also das ist richtig, wir hatten Eis in der Bürozeiten der letzten Nacht. 120 00:05:36,160 --> 00:05:39,390 Während ich kann Ihnen nicht versprechen, dass wir Eis an Bürozeiten haben 121 00:05:39,390 --> 00:05:43,230 jede Woche, was ich kann Ihnen versprechen, ist, dass es deutlich sein, eine 122 00:05:43,230 --> 00:05:45,380 besserer Schüler, um den TA-Verhältnis. 123 00:05:45,380 --> 00:05:47,650 Wie legitim, es ist wie drei zu eins. 124 00:05:47,650 --> 00:05:50,350 Ange Vergleichen Sie das mit Donnerstag, haben Sie bekam 150 125 00:05:50,350 --> 00:05:52,830 wirklich gestresst Kinder und kein Eis. 126 00:05:52,830 --> 00:05:55,360 Und es ist einfach nicht produktiv für jedermann. 127 00:05:55,360 --> 00:05:58,730 So Moral von der Geschichte ist, früh zu kommen In den Bürozeiten und gute Dinge 128 00:05:58,730 --> 00:06:00,310 wird passieren. 129 00:06:00,310 --> 00:06:02,110 >> Außerdem kommen vorbereitet, Fragen zu stellen. 130 00:06:02,110 --> 00:06:03,200 Wissen Sie? 131 00:06:03,200 --> 00:06:05,420 Unabhängig davon, was TAS, I denken, gesagt haben, 132 00:06:05,420 --> 00:06:10,710 wir haben immer ein paar Studenten , die kommen am Donnerstag auf, wie, 10.50 Uhr 133 00:06:10,710 --> 00:06:15,100 nicht mit der Spezifikation zu lesen Wesen wie mir helfen, helfen Sie mir. 134 00:06:15,100 --> 00:06:18,200 Leider zu diesem Zeitpunkt gibt es nicht viel, was wir tun können, um Ihnen zu helfen. 135 00:06:18,200 --> 00:06:19,590 Also bitte kommen am Anfang der Woche. 136 00:06:19,590 --> 00:06:22,040 Kommen Sie früh, um zu Bürozeiten. 137 00:06:22,040 --> 00:06:23,350 Kommen Sie bereit, Fragen zu stellen. 138 00:06:23,350 --> 00:06:25,310 Stellen Sie sicher, dass Sie als ein Student sind, wo 139 00:06:25,310 --> 00:06:27,620 Sie brauchen, um, so dass das sein TAs können Sie entlang zu führen, 140 00:06:27,620 --> 00:06:32,850 das ist, was der Bürozeiten ist sollte für zugeteilt. 141 00:06:32,850 --> 00:06:37,380 >> Zweitens, so weiß ich, Professoren Lust, uns mit Tests überraschen. 142 00:06:37,380 --> 00:06:39,439 Ich hatte ein Professor diejenigen wie, yo, by the way, 143 00:06:39,439 --> 00:06:41,230 daran erinnern, dass Halbzeit Sie nächsten Montag. 144 00:06:41,230 --> 00:06:42,855 Ja, ich wusste nicht, über diese Halbzeit. 145 00:06:42,855 --> 00:06:45,630 Also werde ich zu sein, dass TA dass erinnert Sie all das Quiz 146 00:06:45,630 --> 00:06:47,270 0--, weil, wissen Sie, wir sind CS. 147 00:06:47,270 --> 00:06:50,730 Nun, da wir getan haben, Arrays, erhalten Sie Deshalb ist es Quiz 0, nicht Quiz 1, eh? 148 00:06:50,730 --> 00:06:51,320 OK. 149 00:06:51,320 --> 00:06:52,490 Oh, ich habe einige leise Lachen auf, dass man. 150 00:06:52,490 --> 00:06:53,120 OK. 151 00:06:53,120 --> 00:06:59,710 >> So Quiz 0 wird 14. Oktober, wenn sein Sie in der Montag-Mittwoch Abschnitt sind 152 00:06:59,710 --> 00:07:02,920 und 15. Oktober, wenn du bist das Dienstag-Donnerstag Abschnitt. 153 00:07:02,920 --> 00:07:05,630 Dies gilt nicht für diejenigen von euch an der Harvard- 154 00:07:05,630 --> 00:07:10,350 who-- Ich denke, Sie alle werden Einnahme Ihrer Quiz am 14.. 155 00:07:10,350 --> 00:07:13,560 >> Also ja, nächste Woche, wenn David, in der Aula, geht, 156 00:07:13,560 --> 00:07:15,747 ja, so ungefähr, dass Quiz nächste Woche, können Sie alle 157 00:07:15,747 --> 00:07:17,580 nicht, weil schockiert sein Sie Abschnitt kam 158 00:07:17,580 --> 00:07:19,664 und Sie wissen, dass Ihre quiz 0 ist in zwei Wochen. 159 00:07:19,664 --> 00:07:21,580 Und wir schreiben müssen Sitzungen und alles. 160 00:07:21,580 --> 00:07:26,360 Also keine Sorgen über die für die Angst. 161 00:07:26,360 --> 00:07:29,890 Haben Sie Fragen before-- Fragen in allen logistischen Fragen in Bezug auf, 162 00:07:29,890 --> 00:07:32,591 Grading, Bürozeiten, Abschnitte? 163 00:07:32,591 --> 00:07:33,090 Ja. 164 00:07:33,090 --> 00:07:35,100 >> ZIELGRUPPE: Also das Quiz ist gehen, um während der Vorlesung sein? 165 00:07:35,100 --> 00:07:35,766 >> ANDI PENG: Ja. 166 00:07:35,766 --> 00:07:39,460 Also das Quiz, denke ich, ist 60 Minuten in diesem Zeitschlitz zugeteilt 167 00:07:39,460 --> 00:07:42,240 dass Sie nur nehmen im Hörsaal. 168 00:07:42,240 --> 00:07:44,810 So dass Sie nicht haben, um es in auf, wie, einem zufälligen 07.00. 169 00:07:44,810 --> 00:07:46,140 Es ist alles gut. 170 00:07:46,140 --> 00:07:47,100 Ja. 171 00:07:47,100 --> 00:07:50,060 Cool. 172 00:07:50,060 --> 00:07:50,840 >> Gut. 173 00:07:50,840 --> 00:07:54,330 So dass wir zu gehen vorstellen, ein Konzept zu Ihnen 174 00:07:54,330 --> 00:08:00,760 diese Woche, dass David schon Art der berührte in Vortrag in der vergangenen Woche. 175 00:08:00,760 --> 00:08:02,010 Es heißt GDB. 176 00:08:02,010 --> 00:08:05,570 Und wie viele von euch, während in der Verlauf Schreiben Ihrer psets, 177 00:08:05,570 --> 00:08:09,981 haben einen großen Button mit der Aufschrift aufgefallen "Debug" am oberen Rand Ihrer IDE? 178 00:08:09,981 --> 00:08:10,480 OK. 179 00:08:10,480 --> 00:08:13,770 So, jetzt werden wir tatsächlich bekommen, um auszugraben das Geheimnis, was diese Schaltfläche tatsächlich 180 00:08:13,770 --> 00:08:14,270 tut. 181 00:08:14,270 --> 00:08:16,790 Und ich garantiere Ihnen, es ist ein schön, schöne Sache. 182 00:08:16,790 --> 00:08:20,740 >> Also bis jetzt, denke ich, Es gab zwei Dinge, 183 00:08:20,740 --> 00:08:23,320 Studenten waren typischerweise tut beim Debuggen psets. 184 00:08:23,320 --> 00:08:27,635 One, sie entweder hinzufügen, in printf () - so alle paar Zeilen, 185 00:08:27,635 --> 00:08:29,760 sie in einer printf () hinzuzufügen - oh, was ist diese Variable? 186 00:08:29,760 --> 00:08:32,551 Oh, was ist das variable now-- und man irgendwie sehen die Progression 187 00:08:32,551 --> 00:08:33,940 des Codes, wie es läuft. 188 00:08:33,940 --> 00:08:37,030 Oder das zweite Verfahren Kindern zu tun ist dass sie nur schreiben das Ganze 189 00:08:37,030 --> 00:08:38,610 und dann so gehen am Ende. 190 00:08:38,610 --> 00:08:39,970 Hoffentlich funktioniert es. 191 00:08:39,970 --> 00:08:44,851 Ich garantiere Ihnen, ist GDB besser als beide dieser Methoden. 192 00:08:44,851 --> 00:08:45,350 Ja. 193 00:08:45,350 --> 00:08:46,980 So wird dies Ihr neuer bester Freund sein. 194 00:08:46,980 --> 00:08:51,780 Denn es ist eine schöne Sache dass visuell zeigt sowohl 195 00:08:51,780 --> 00:08:54,850 was Ihr Code tut an einem bestimmten Punkt 196 00:08:54,850 --> 00:08:57,486 als auch, was alle Ihre Variablen tragen, 197 00:08:57,486 --> 00:08:59,610 wie das, was ihre Werte sind, an diesem bestimmten Punkt. 198 00:08:59,610 --> 00:09:02,670 Und auf diese Weise können Sie wirklich Haltepunkte in Ihrem Code. 199 00:09:02,670 --> 00:09:04,350 Sie können durch die Zeile für Zeile ausführen. 200 00:09:04,350 --> 00:09:07,324 Und GDB müssen nur für die Sie, angezeigt, damit Sie, 201 00:09:07,324 --> 00:09:09,490 was alle Ihre Variablen sind, was tun sie, 202 00:09:09,490 --> 00:09:10,656 was los ist in den Code. 203 00:09:10,656 --> 00:09:13,240 Und in einer solchen Weise, ist es so viel einfacher zu sehen, 204 00:09:13,240 --> 00:09:17,120 was anstelle von printf-ing geschieht bzw. vor Aussagen. 205 00:09:17,120 --> 00:09:19,160 >> Also werden wir ein Beispiel dafür später. 206 00:09:19,160 --> 00:09:20,660 Also das scheint ein wenig abstrakt. 207 00:09:20,660 --> 00:09:23,490 Keine Sorge, wir werden Beispiele zu tun. 208 00:09:23,490 --> 00:09:29,170 Und so im wesentlichen die drei größten, am häufigsten verwendeten Funktionen finden Sie in GDB brauchen 209 00:09:29,170 --> 00:09:32,500 sind die nächsten, Schritt über, und Schritt in Tasten. 210 00:09:32,500 --> 00:09:34,860 Ich werde über Kopf es eigentlich gerade jetzt. 211 00:09:34,860 --> 00:09:40,930 >> So kann euch alle sehen, dass oder sollte ich in ein wenig zu vergrößern? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 In der Rückseite können Sie sehen, dass? 214 00:09:44,470 --> 00:09:45,730 Sollte ich in zu vergrößern? 215 00:09:45,730 --> 00:09:46,480 Nur ein bisschen? 216 00:09:46,480 --> 00:09:49,390 OK COOL. 217 00:09:49,390 --> 00:09:50,280 Da gehen wir. 218 00:09:50,280 --> 00:09:50,960 OK. 219 00:09:50,960 --> 00:09:57,000 >> So habe ich, hier, mein Implementierung für gierig. 220 00:09:57,000 --> 00:10:01,430 Und während eine Menge von euch schreibt gierig in while-Schleife, dass form-- 221 00:10:01,430 --> 00:10:04,890 ist eine völlig akzeptable Weise zu tun, es-- einen anderen Weg, es zu tun ist, einfach 222 00:10:04,890 --> 00:10:06,280 teilen in der Modulo. 223 00:10:06,280 --> 00:10:09,290 Denn dann können Sie Ihre Wert und dann haben Sie Ihren Rest. 224 00:10:09,290 --> 00:10:11,150 Und dann können Sie nur fügen sie alle zusammen. 225 00:10:11,150 --> 00:10:13,390 Hat die Logik, was ich tue hier sinnvoll, alle, 226 00:10:13,390 --> 00:10:14,117 bevor wir beginnen? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 So'ne Art? 229 00:10:17,980 --> 00:10:18,710 Cool. 230 00:10:18,710 --> 00:10:19,210 Groß. 231 00:10:19,210 --> 00:10:21,290 Es ist eine ziemlich sexy Stück Code, würde ich sagen. 232 00:10:21,290 --> 00:10:23,502 Wie ich schon sagte, David, in Vortrag, nach einer Weile, 233 00:10:23,502 --> 00:10:25,960 Du sehen, beginnen Code als etwas, das schön ist. 234 00:10:25,960 --> 00:10:29,950 Und manchmal, wenn Sie schön zu sehen Code, es ist so ein wunderbares Gefühl. 235 00:10:29,950 --> 00:10:35,410 >> So aber, während dieser Code ist sehr schön, funktioniert es nicht richtig. 236 00:10:35,410 --> 00:10:37,750 Also lassen Sie uns laufen check50 zu diesem Thema. 237 00:10:37,750 --> 00:10:39,440 Prüfen 50 20-- oop. 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 Ist, dass PSet2? 241 00:10:44,990 --> 00:10:46,870 Ja. 242 00:10:46,870 --> 00:10:47,520 Oh, pset1. 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 OK. 245 00:10:52,890 --> 00:10:53,900 So laufen wir check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> Und wie Sie Jungs können hier sehen, es andernfalls ein paar Fällen. 248 00:11:07,170 --> 00:11:10,165 Und für einige von euch, in die Selbstverständlich tun Sie Ihr Problem-Sets, 249 00:11:10,165 --> 00:11:11,110 Sie wie, ah, warum funktioniert es nicht. 250 00:11:11,110 --> 00:11:13,318 Warum ist es für manche Arbeits Werte für andere aber nicht? 251 00:11:13,318 --> 00:11:17,760 Nun, GDB wird Ihnen helfen, Figur herauszufinden, warum diese Eingänge nicht in Betrieb waren. 252 00:11:17,760 --> 00:11:18,320 >> OK. 253 00:11:18,320 --> 00:11:21,640 Also mal sehen, einer der Kontrollen wurde ich in Ermangelung check50 254 00:11:21,640 --> 00:11:24,920 war der Eingangswert von 0,41. 255 00:11:24,920 --> 00:11:27,830 So ist die richtige Antwort, Sie sollten immer ein 4. 256 00:11:27,830 --> 00:11:33,090 Sondern das, was ich den Ausdruck ist das 3-n, die nicht korrekt ist. 257 00:11:33,090 --> 00:11:36,190 Lassen Sie uns also nur manuell ausgeführt, nur stellen Sie sicher, dass check50 funktioniert. 258 00:11:36,190 --> 00:11:36,940 Lass uns ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Hoppla, habe ich gierig zu machen. 261 00:11:43,340 --> 00:11:43,840 Da gehen wir. 262 00:11:43,840 --> 00:11:44,381 Jetzt ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Wie viel ist zu verdanken? 265 00:11:47,670 --> 00:11:49,550 Lass uns 0,41. 266 00:11:49,550 --> 00:11:52,590 Und ja, wir sehen hier, dass es Ausgeben 3 267 00:11:52,590 --> 00:11:55,160 wenn die richtige Antwort, in der Tat, sollten 4 sein. 268 00:11:55,160 --> 00:12:01,460 Also lassen Sie uns geben GDB und sehen, wie wir kann über die Festsetzung dieses Problem zu gehen. 269 00:12:01,460 --> 00:12:03,992 >> Also der erste Schritt bei der immer Debugging-Code 270 00:12:03,992 --> 00:12:05,950 ist es, einen Haltepunkt zu setzen, oder ein Punkt, an dem Sie 271 00:12:05,950 --> 00:12:09,079 wollen Sie den Computer oder die Debugger zu beginnen,. 272 00:12:09,079 --> 00:12:11,120 Also, wenn Sie nicht wirklich wissen, was dein Problem ist, 273 00:12:11,120 --> 00:12:14,670 in der Regel ist die typische Sache, die wir wollen, zu tun ist, um unsere Haltepunkt am Haupt gesetzt. 274 00:12:14,670 --> 00:12:18,520 Also, wenn euch kann dies zu sehen roten Knopf genau dort, 275 00:12:18,520 --> 00:12:22,860 yep, dass mich die Einstellung ein Haltepunkt für die Hauptfunktion. 276 00:12:22,860 --> 00:12:24,130 Ich klicke auf, dass. 277 00:12:24,130 --> 00:12:26,130 >> Und dann kann ich hinaufziehen zu meinem Debug-Taste. 278 00:12:26,130 --> 00:12:27,036 Ich traf diese Schaltfläche. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Lassen Sie mich wieder zu verkleinern, wenn ich kann. 281 00:12:36,555 --> 00:12:38,020 Da gehen wir. 282 00:12:38,020 --> 00:12:40,730 So haben wir, hier ein Panel auf der rechten Seite. 283 00:12:40,730 --> 00:12:43,680 Es tut mir leid, Leute in den Rücken, die Sie kann nicht wirklich sehen wirklich gut. 284 00:12:43,680 --> 00:12:49,090 Aber im Wesentlichen alle Diese rechte Tafel tut 285 00:12:49,090 --> 00:12:53,130 ist die Verfolgung sowohl der hervorgehobenen Linie, die die Codezeile ist 286 00:12:53,130 --> 00:12:56,640 dass der Computer gerade läuft, sowie alle Ihre Variablen 287 00:12:56,640 --> 00:12:57,600 hier unten. 288 00:12:57,600 --> 00:13:00,487 >> So haben Sie Cent, Münzen, n, alles, um verschiedene Dinge erklärt 289 00:13:00,487 --> 00:13:01,070 an diesem Punkt. 290 00:13:01,070 --> 00:13:04,850 Keine Sorgen, denn wir haben nicht wirklich initialisiert sie auf alle Variablen leer. 291 00:13:04,850 --> 00:13:07,200 Also in Ihrem Computer, Ihrem Computer ist einfach zu sehen, 292 00:13:07,200 --> 00:13:14,376 oh, 32767 war die zuletzt verwendete Funktion dieser Speicherplatz in meinem Computer. 293 00:13:14,376 --> 00:13:16,000 Und so das ist, wo Cent derzeit. 294 00:13:16,000 --> 00:13:19,360 Aber nein, dass, wenn Sie den Code ausführen, sollte es sich initialisiert. 295 00:13:19,360 --> 00:13:24,110 >> Lassen Sie uns also durch zu gehen, Zeile Linie, was hier vor sich geht. 296 00:13:24,110 --> 00:13:25,350 OK. 297 00:13:25,350 --> 00:13:29,400 Also hier sind die drei Tasten, die ich gerade erklärt. 298 00:13:29,400 --> 00:13:34,090 Sie haben die Wiedergabe oder die Run-Funktion, Taste, haben Sie die Schaltfläche Step Over, 299 00:13:34,090 --> 00:13:36,600 und Sie haben auch den Schritt in die Taste. 300 00:13:36,600 --> 00:13:41,260 Und im wesentlichen alle drei sie nur durch den Code zu gehen 301 00:13:41,260 --> 00:13:42,690 und verschiedene Dinge tun. 302 00:13:42,690 --> 00:13:45,680 >> Also in der Regel, wenn Sie Debugging sind, Wir wollen nicht einfach auf Play, 303 00:13:45,680 --> 00:13:47,930 weil Wiedergabe wird nur laufen Ihren Code bis zum Ende des es. 304 00:13:47,930 --> 00:13:49,070 Und dann wirst du nicht wirklich was dein Problem kennen 305 00:13:49,070 --> 00:13:51,432 es sei denn, Sie mehrere Haltepunkte setzen. 306 00:13:51,432 --> 00:13:53,890 Wenn Sie mehrere Haltepunkte setzen, Es wird nur automatisch 307 00:13:53,890 --> 00:13:56,030 von einem Haltepunkt, zu der nächsten, auf die nächste. 308 00:13:56,030 --> 00:13:58,030 Aber in diesem Fall wir haben nur so, dass man, weil wir 309 00:13:58,030 --> 00:13:59,970 unsere Weise arbeiten wollen von oben nach unten nach unten. 310 00:13:59,970 --> 00:14:04,830 So werden wir auf diese Schaltfläche ignorieren jetzt für die Zwecke dieses Programms. 311 00:14:04,830 --> 00:14:08,230 >> Also der Schritt über Funktion nur Schritte über jede einzelne Zeile 312 00:14:08,230 --> 00:14:11,510 und sagt Ihnen, was der Computer tut. 313 00:14:11,510 --> 00:14:14,630 Der Schritt in die Funktion geht in die eigentliche Funktion 314 00:14:14,630 --> 00:14:16,000 das ist auf Ihrem Codezeile. 315 00:14:16,000 --> 00:14:19,070 So zum Beispiel, wie printf (), , dass eine Funktion, nicht wahr? 316 00:14:19,070 --> 00:14:21,980 Wenn ich wollte, um körperlich Schritt in die printf () -Funktion, 317 00:14:21,980 --> 00:14:25,610 Ich würde tatsächlich in das Stück gehen Code, wo printf () geschrieben wurde, und sehen, 318 00:14:25,610 --> 00:14:26,730 was ist da los. 319 00:14:26,730 --> 00:14:29,924 >> Aber in der Regel angenommen, dass der Code, den wir Ihnen funktioniert. 320 00:14:29,924 --> 00:14:31,340 Wir übernehmen die printf () funktioniert. 321 00:14:31,340 --> 00:14:33,170 Wir gehen davon aus, dass getint () funktioniert. 322 00:14:33,170 --> 00:14:35,170 Es gibt also keine Notwendigkeit, Schritt in diese Funktionen. 323 00:14:35,170 --> 00:14:37,170 Aber wenn es funktioniert , dass Sie selbst schreiben 324 00:14:37,170 --> 00:14:39,060 dass Sie überprüfen möchten herauszufinden, was los ist, 325 00:14:39,060 --> 00:14:41,200 Sie würde zu Schritt wollen in dieser Funktion. 326 00:14:41,200 --> 00:14:43,940 >> So jetzt sind wir gerade dabei zu Schritt über diesen Teil des Codes. 327 00:14:43,940 --> 00:14:44,485 Also mal sehen. 328 00:14:44,485 --> 00:14:46,547 Oh, drucken, "Oh hai, how viel Veränderung geschuldet ist? " 329 00:14:46,547 --> 00:14:47,130 Wir kümmern uns nicht. 330 00:14:47,130 --> 00:14:49,830 Wir wissen, dass funktioniert, so dass wir Schritt über sie. 331 00:14:49,830 --> 00:14:53,290 >> So n, die unsere Schwimmer ist, dass wir haben initialized-- oder declared-- 332 00:14:53,290 --> 00:14:56,810 an der Spitze, jetzt sind wir gleich, daß bis GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Also lassen Sie uns Schritt über. 334 00:14:57,810 --> 00:14:59,580 Und wir sehen, bei der Boden hier, das Programm 335 00:14:59,580 --> 00:15:03,360 veranlasst mich, einen Wert eingeben. 336 00:15:03,360 --> 00:15:08,580 Lassen Sie uns also Eingang den Wert wollen wir hier zu testen, die 0,41 ist. 337 00:15:08,580 --> 00:15:09,160 Groß. 338 00:15:09,160 --> 00:15:12,780 >> So, jetzt n-- kann euch sehen hier am bottom-- es 339 00:15:12,780 --> 00:15:15,140 stored-- weil wir noch nicht abgerundet ist es 340 00:15:15,140 --> 00:15:19,540 in diesem wie riesige gespeichert Schwimmer, die 0,4099999996 ist, 341 00:15:19,540 --> 00:15:22,550 welche nahe genug, um unsere Zwecke, gerade jetzt, um 0.41. 342 00:15:22,550 --> 00:15:26,090 Und dann werden wir später sehen, wie wir weiter stieg über das Programm, 343 00:15:26,090 --> 00:15:29,850 nachdem hier hat n geworden gerundet und Cent hat sich 41. 344 00:15:29,850 --> 00:15:30,350 Groß. 345 00:15:30,350 --> 00:15:32,230 So wissen wir, dass unsere Arbeits Rundung. 346 00:15:32,230 --> 00:15:34,700 Wir wissen, dass wir die richtige Anzahl von Cents, 347 00:15:34,700 --> 00:15:36,990 so dass wir wissen, dass das ist, nicht wirklich das Problem. 348 00:15:36,990 --> 00:15:40,050 >> So dass wir auch weiterhin Schritt Auf im Rahmen dieses Programms. 349 00:15:40,050 --> 00:15:40,900 Wir gehen hier. 350 00:15:40,900 --> 00:15:46,139 Und so nach dieser Codezeile, die wir sollten wissen, wie vielen Seiten die wir haben. 351 00:15:46,139 --> 00:15:46,680 Wir treten auf. 352 00:15:46,680 --> 00:15:52,040 Und Sie sehen, wir haben in der Tat, haben ein Quartal, da haben wir 25 subtrahiert 353 00:15:52,040 --> 00:15:53,790 von unserer Anfangswert von 41. 354 00:15:53,790 --> 00:15:55,890 Und wir haben 16 links für unsere Cent. 355 00:15:55,890 --> 00:15:58,830 >> Hat jeder wissen, wie Das Programm wird durch Schritt 356 00:15:58,830 --> 00:16:02,980 und warum Cent hat sich zu 16 und warum, heute, Münzen hat sich 1? 357 00:16:02,980 --> 00:16:04,610 Jeder ist nach dieser Logik? 358 00:16:04,610 --> 00:16:05,110 Cool. 359 00:16:05,110 --> 00:16:07,860 So dass dieser Punkt, die Programmarbeits, nicht wahr? 360 00:16:07,860 --> 00:16:09,797 Wir wissen, es ist genau das, was wir wollen, dass es. 361 00:16:09,797 --> 00:16:11,880 Und wir haben nicht wirklich haben ausdrucken, oh, was 362 00:16:11,880 --> 00:16:14,430 ist Cent an dieser Stelle, was Münzen an dieser Stelle. 363 00:16:14,430 --> 00:16:17,170 >> Weiter geht es durch das Programm gehen. 364 00:16:17,170 --> 00:16:18,100 Schritt über. 365 00:16:18,100 --> 00:16:18,620 Cool. 366 00:16:18,620 --> 00:16:19,700 Wir gehen über Groschen. 367 00:16:19,700 --> 00:16:20,200 Groß. 368 00:16:20,200 --> 00:16:22,367 Wir sehen, dass es gemacht off 0,10 $ für einen Cent. 369 00:16:22,367 --> 00:16:23,450 Und jetzt haben wir zwei Münzen. 370 00:16:23,450 --> 00:16:25,260 Das ist richtig. 371 00:16:25,260 --> 00:16:31,555 >> Wir gehen über ein paar Cent und wir sehen, dass wir haben mehr als Cent gelassen. 372 00:16:31,555 --> 00:16:32,680 Hmm, das ist seltsam. 373 00:16:32,680 --> 00:16:37,540 Hier oben auf dem Programm, ich angeblich auf meine Pfennige abgezogen haben. 374 00:16:37,540 --> 00:16:39,400 Vielleicht war ich einfach nicht tun, dass die Linie nach rechts. 375 00:16:39,400 --> 00:16:42,190 Und ach, sehen Sie, hier, weil wir wissen, 376 00:16:42,190 --> 00:16:44,360 dass wir Schritt durch die Leitungen 32 und 33, 377 00:16:44,360 --> 00:16:50,560 das ist, wo unser Programm unsachgemäß hatten Variablen ausführen. 378 00:16:50,560 --> 00:16:55,136 So können wir schauen und sehen, oh, Ich Subtrahieren Cent hier, 379 00:16:55,136 --> 00:16:57,010 aber ich bin nicht wirklich Hinzufügen zu meinen Münzwert. 380 00:16:57,010 --> 00:16:57,860 Ich Hinzufügen Cent bin. 381 00:16:57,860 --> 00:17:00,234 Und ich will nicht, um hinzuzufügen, Cent, ich will, um Münzen zu fügen. 382 00:17:00,234 --> 00:17:05,420 Wenn wir das ändern, um Münzen, wir haben ein Arbeitsprogramm stand. 383 00:17:05,420 --> 00:17:06,730 Ich kann check50 laufen. 384 00:17:06,730 --> 00:17:11,063 Sie können einfach verlassen von GDB rechts hier und führen Sie dann check50 erneut. 385 00:17:11,063 --> 00:17:11,938 Ich konnte es einfach tun. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Ich habe gierig zu machen. 388 00:17:18,480 --> 00:17:19,940 0,41. 389 00:17:19,940 --> 00:17:22,819 Und hier ist es Druck Sie die richtige Antwort. 390 00:17:22,819 --> 00:17:26,569 >> So wie Sie sehen können, Jungs, GDB ist ein wirklich leistungsfähiges Werkzeug 391 00:17:26,569 --> 00:17:29,940 denn wenn wir so viel Code haben geht und so viele Variablen 392 00:17:29,940 --> 00:17:32,510 dass es schwer für uns, da ein Mensch, den Überblick zu behalten. 393 00:17:32,510 --> 00:17:35,360 Der Computer, in der GDB Debugger, die Fähigkeit hat, 394 00:17:35,360 --> 00:17:37,020 In den Überblick zu bewahren. 395 00:17:37,020 --> 00:17:40,480 Ich weiß, in Visionaire, Jungs, Sie wahrscheinlich könnte einige Segmentation Faults getroffen haben 396 00:17:40,480 --> 00:17:43,150 weil Sie liefen außerhalb der Grenzen des Arrays. 397 00:17:43,150 --> 00:17:46,510 In dem Beispiel von Caesar, das ist, genau das, was ich hier implementiert. 398 00:17:46,510 --> 00:17:50,060 >> So habe ich vergessen zu überprüfen, Was würde passieren, wenn ich 399 00:17:50,060 --> 00:17:52,510 nicht zwei Kommandozeilenargumente. 400 00:17:52,510 --> 00:17:53,880 Ich wusste nur nicht in dieser Kontrolle gestellt. 401 00:17:53,880 --> 00:17:57,380 Und so, wenn ich keine Debug-- ich meine Haltepunkt, dort rechts. 402 00:17:57,380 --> 00:17:58,055 Ich laufe Debug. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> OK. 405 00:18:16,550 --> 00:18:17,050 Ja. 406 00:18:17,050 --> 00:18:20,350 Also eigentlich, GDB sollte mir dort gesagt haben, 407 00:18:20,350 --> 00:18:22,300 war ein Segmentierungsfehler gibt. 408 00:18:22,300 --> 00:18:24,883 Ich weiß nicht, was los war genau dort, aber wenn ich es lief, 409 00:18:24,883 --> 00:18:25,590 es funktionierte. 410 00:18:25,590 --> 00:18:29,410 Wenn Sie Codezeilen durchlaufen und GDB könnte nur plötzlich aufhören auf dich, 411 00:18:29,410 --> 00:18:31,540 gehen und schauen, was die rote Fehler ist. 412 00:18:31,540 --> 00:18:33,930 Es werde Ihnen sagen, hey, du hatte einen Segmentation Fault, 413 00:18:33,930 --> 00:18:38,550 was bedeutet, dass Sie den Zugriff versucht Platz in einem Feld, das nicht existiert. 414 00:18:38,550 --> 00:18:39,050 Ja. 415 00:18:39,050 --> 00:18:43,280 >> Also das nächste Problem setzen Sie diese Woche, you guys 416 00:18:43,280 --> 00:18:45,600 wird wahrscheinlich eine Menge Variablen im Umlauf. 417 00:18:45,600 --> 00:18:48,560 Du wirst doch nicht sicher sein, was bedeutet das alles an einem bestimmten Punkt. 418 00:18:48,560 --> 00:18:53,560 So GDB Ihnen wirklich helfen, herauszufinden Sie heraus, was sie sind alle gleich 419 00:18:53,560 --> 00:18:55,940 und die Möglichkeit, dass visuell sehen. 420 00:18:55,940 --> 00:19:01,995 Ist jemand, wie verwirrt nichts davon funktionierte? 421 00:19:01,995 --> 00:19:02,495 Cool. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Gut. 424 00:19:10,620 --> 00:19:14,260 So nach, dass sind wir werde tauchen rechts 425 00:19:14,260 --> 00:19:17,562 in vier verschiedene Arten von Sorten für diese Woche. 426 00:19:17,562 --> 00:19:19,520 Wie viele von euch, zuerst von allen, bevor wir anfangen, 427 00:19:19,520 --> 00:19:23,020 haben die gesamte Spezifikation für pset3 lesen? 428 00:19:23,020 --> 00:19:23,824 OK. 429 00:19:23,824 --> 00:19:24,740 Ich bin stolz auf euch. 430 00:19:24,740 --> 00:19:29,110 Das ist wie die Hälfte der Klasse, die ist deutlich mehr als beim letzten Mal. 431 00:19:29,110 --> 00:19:33,950 >> Also das ist großartig, denn wenn wir über den Inhalt sprechen 432 00:19:33,950 --> 00:19:36,170 in lecture-- oder sorry, in section-- Ich mag 433 00:19:36,170 --> 00:19:38,210 eine Menge, dass beziehen zurück, was die pset ist 434 00:19:38,210 --> 00:19:40,210 und wie Sie wollen umzusetzen, dass in Ihrem pset. 435 00:19:40,210 --> 00:19:42,400 Also, wenn Sie kommen mit lesen Sie die Spezifikation, wird es 436 00:19:42,400 --> 00:19:45,510 viel einfacher für Sie zu verstehen, wovon ich spreche, wenn ich sage, 437 00:19:45,510 --> 00:19:48,720 Oh hey, könnte dies eine wirklich sein guter Ort, um diese Art zu implementieren. 438 00:19:48,720 --> 00:19:52,870 Also diejenigen, die gelesen haben, die spec wissen, dass als Teil Ihres pset, 439 00:19:52,870 --> 00:19:54,900 Sie gehen zu haben sind schreib eine Art der Sortierung. 440 00:19:54,900 --> 00:19:58,670 So kann dies sehr hilfreich sein für viele von euch heute. 441 00:19:58,670 --> 00:20:01,760 >> Also werden wir beginnen mit, im wesentlichen, die einfachste Art 442 00:20:01,760 --> 00:20:04,580 der Art, die Auswahl sortieren. 443 00:20:04,580 --> 00:20:06,800 Die typische Algorithmus für Wie würden wir über diese gehen 444 00:20:06,800 --> 00:20:10,460 ist-- David ging durch diese alle in Vortrag, also werde ich schnell zusammen bewegen 445 00:20:10,460 --> 00:20:13,900 hier-- ist im Wesentlichen, Sie haben eine Reihe von Werten. 446 00:20:13,900 --> 00:20:17,170 Und dann finden sie die kleinste unsortierten Wert 447 00:20:17,170 --> 00:20:20,200 und Sie diesen Wert mit Swap- die erste unsortierten Wert. 448 00:20:20,200 --> 00:20:22,700 Und dann hast du nur immer wiederholen mit dem Rest Ihrer Liste. 449 00:20:22,700 --> 00:20:25,740 >> Und hier ist eine visuelle Erklärung , wie das funktionieren würde. 450 00:20:25,740 --> 00:20:30,460 So zum Beispiel, wenn wir starten mit einer Anordnung von fünf Elementen, index 451 00:20:30,460 --> 00:20:35,910 0-4, 3, 5, 2, 6 und 4 Werte so jetzt in der array-- platziert, 452 00:20:35,910 --> 00:20:38,530 wir nur davon ausgehen, dass sie alle unsortierten 453 00:20:38,530 --> 00:20:41,130 weil wir sonst nicht getestet. 454 00:20:41,130 --> 00:20:44,130 >> So, wie eine Auswahl Art würde Arbeit ist, dass es erste wäre 455 00:20:44,130 --> 00:20:46,800 durch die Gesamtheit ausführen der unsortierten Array. 456 00:20:46,800 --> 00:20:49,120 Es würde herausgreifen den kleinsten Wert. 457 00:20:49,120 --> 00:20:51,750 In diesem Fall 3, rechte jetzt ist der kleinste. 458 00:20:51,750 --> 00:20:52,680 Es erhält bis 5. 459 00:20:52,680 --> 00:20:55,620 Nö, 5 nicht größer than-- oder sorry, nicht weniger than-- 3. 460 00:20:55,620 --> 00:20:57,779 So wird der Minimalwert ist immer noch 3. 461 00:20:57,779 --> 00:20:58,695 Und dann haben Sie, um 2 zu erhalten. 462 00:20:58,695 --> 00:21:00,990 Der Computer sieht, oh, 2 weniger als 3. 463 00:21:00,990 --> 00:21:02,750 2 muss nun der Minimalwert sein. 464 00:21:02,750 --> 00:21:06,630 Und so 2-Swaps mit dem ersten Wert. 465 00:21:06,630 --> 00:21:10,702 >> So nach einem Durchgang, wissen wir ja sehen, dass die 2 und die 3 sind vertauscht. 466 00:21:10,702 --> 00:21:13,910 Und wir sind gerade dabei, auch weiterhin tun, dies wiederum mit dem Rest des Arrays. 467 00:21:13,910 --> 00:21:17,660 So werden wir nur durchlaufen die letzten vier Indizes des Arrays. 468 00:21:17,660 --> 00:21:20,670 Wir werden sehen, dass 3 der nächste Minimalwert. 469 00:21:20,670 --> 00:21:23,240 So werden wir, dass mit 4 zu tauschen. 470 00:21:23,240 --> 00:21:26,900 Und dann sind wir gerade dabei, zu halten durch Laufen, bis schließlich Sie 471 00:21:26,900 --> 00:21:33,730 zu erhalten, um eine sortierte Array, in dem 2, 3, 4, 5 und 6 alle sortiert. 472 00:21:33,730 --> 00:21:37,530 Hat jeder verstehen, die Logik wie eine Auswahl Art funktioniert? 473 00:21:37,530 --> 00:21:39,669 >> Sie müssen nur eine Art von einem Minimalwert. 474 00:21:39,669 --> 00:21:41,210 Sie sind zu verfolgen, was das ist. 475 00:21:41,210 --> 00:21:45,170 Und immer, wenn Sie es finden, es zu tauschen Sie mit dem ersten Wert im array-- 476 00:21:45,170 --> 00:21:48,740 oder, nicht das erste value-- der nächste Wert in der Anordnung. 477 00:21:48,740 --> 00:21:50,150 Cool. 478 00:21:50,150 --> 00:21:55,460 >> So wie Sie Jungs Art sah von einem kurzen Blick, 479 00:21:55,460 --> 00:21:58,450 wir werden diese Pseudocode aus. 480 00:21:58,450 --> 00:22:02,510 Also, wenn Sie Jungs in den Rücken wollen bilden eine Gruppe, jeder an einem Tisch 481 00:22:02,510 --> 00:22:06,170 kann ein wenig Partner bilden, werde ich Sie Jungs wie drei Minuten, um zu geben 482 00:22:06,170 --> 00:22:08,190 nur durch reden die Logik, in Englisch, 483 00:22:08,190 --> 00:22:14,161 wie wir vielleicht in der Lage zu implementieren sein Pseudocode, um eine Auswahl Art zu schreiben. 484 00:22:14,161 --> 00:22:14,910 Und es gibt Süßigkeiten. 485 00:22:14,910 --> 00:22:16,118 Bitte kommen Sie und erhalten Süßigkeiten. 486 00:22:16,118 --> 00:22:19,520 Wenn Sie in der Rückseite sind und Sie möchten Süßigkeiten, kann ich Süßigkeiten auf dich werfen. 487 00:22:19,520 --> 00:22:22,850 Eigentlich tun Sie-- cool. 488 00:22:22,850 --> 00:22:23,552 Oh, das tut mir leid. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 OK. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Also, wenn wir möchten, wie eine Klasse, Schreibpseudo 493 00:25:27,140 --> 00:25:30,466 denn wie könnte man nähern Dieses Problem, sich fühlen gerade frei. 494 00:25:30,466 --> 00:25:32,340 Ich werde einfach gehen um und, um, fragen Sie Gruppen 495 00:25:32,340 --> 00:25:35,065 für die nächste Zeile von was wir tun sollten. 496 00:25:35,065 --> 00:25:37,840 Also, wenn Sie Jungs wollen starten off, was ist das erste, was 497 00:25:37,840 --> 00:25:40,600 zu tun, wenn Sie versuchen, Umsetzung einer Möglichkeit, dieses Programm zu lösen 498 00:25:40,600 --> 00:25:43,480 , um eine Liste wahl sortieren? 499 00:25:43,480 --> 00:25:46,349 Lassen Sie uns gerade gehen wir davon habe ein Array, in Ordnung? 500 00:25:46,349 --> 00:25:49,088 >> ZIELGRUPPE: Sie möchten einige erstellen Art [unverständlich], dass Sie 501 00:25:49,088 --> 00:25:50,420 läuft durch den ganzen Array. 502 00:25:50,420 --> 00:25:51,128 >> ANDI PENG: Richtig. 503 00:25:51,128 --> 00:25:54,100 So wirst du durchlaufen zu wollen, sind durch jeden Raum, oder? 504 00:25:54,100 --> 00:26:05,490 So großartig. 505 00:26:05,490 --> 00:26:08,600 Wenn Sie Jungs wollen mir die geben nächste line-- ja, in den Rücken. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> ZIELGRUPPE: Überprüfen Sie sie alle für die kleinsten. 508 00:26:13,290 --> 00:26:14,248 >> ANDI PENG: Dort gehen wir. 509 00:26:14,248 --> 00:26:17,438 So durchlaufen und überprüfen Sie, möchten wir zu sehen, was der Minimalwert ist, nicht wahr? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Ich werde also abkürzen "min." 512 00:26:24,840 --> 00:26:27,658 Was seid ihr nach tun möchten Sie den minimalen Wert gefunden haben? 513 00:26:27,658 --> 00:26:28,533 >> ZIELGRUPPE: [unverständlich] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI PENG: So wirst du zu wollen, sind schalten Sie es mit dem ersten des Arrays, 516 00:26:33,150 --> 00:26:33,650 Recht? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 Das ist der Anfang, ich werde sagen. 519 00:26:46,850 --> 00:26:47,220 Gut. 520 00:26:47,220 --> 00:26:50,386 So, jetzt, dass Sie den ersten getauscht haben ein, was wollen Sie, um danach zu tun? 521 00:26:50,386 --> 00:26:54,840 So, jetzt wissen wir, dass dieser hier muss der kleinste Wert sein, oder? 522 00:26:54,840 --> 00:26:58,310 Dann können Sie eine zusätzliche Ruhe haben des Arrays, die unsortiert ist. 523 00:26:58,310 --> 00:27:01,569 Also, was Sie zu tun, wenn Sie wollen Jungs wollen mir die nächste Zeile zu geben? 524 00:27:01,569 --> 00:27:04,610 ZIELGRUPPE: Also Sie durchlaufen möchten durch den Rest des Arrays. 525 00:27:04,610 --> 00:27:05,276 ANDI PENG: Ja. 526 00:27:05,276 --> 00:27:09,857 Und so was durchlaufen Art implizieren wir wahrscheinlich brauchen werden? 527 00:27:09,857 --> 00:27:10,440 Welche Art von-- 528 00:27:10,440 --> 00:27:12,057 >> ZIELGRUPPE: Oh, eine zusätzliche Variable? 529 00:27:12,057 --> 00:27:13,890 ANDI PENG: Wahrscheinlich ein anderes für Schleife, oder? 530 00:27:13,890 --> 00:27:28,914 So dass wir wahrscheinlich gehen zu wollen, iterieren through-- groß. 531 00:27:28,914 --> 00:27:31,830 Und dann wirst du zurück bist und die Mindest wahrscheinlich noch einmal überprüfen, 532 00:27:31,830 --> 00:27:32,100 Recht? 533 00:27:32,100 --> 00:27:34,975 Und du wirst immer wiederholen sind Dies, weil die Schlaufen gerade dabei 534 00:27:34,975 --> 00:27:36,010 laufen zu halten, nicht wahr? 535 00:27:36,010 --> 00:27:39,190 >> So wie Sie Jungs, wir sehen, einfach nur einen allgemeinen Pseudo 536 00:27:39,190 --> 00:27:41,480 wie wir wollen dieses Programm zu schauen. 537 00:27:41,480 --> 00:27:46,646 Diese iterate hier, was machen wir in der Regel müssen in unserem Code zu schreiben 538 00:27:46,646 --> 00:27:49,270 wenn wir durch eine durchlaufen möchten Array, welche Art von Struktur? 539 00:27:49,270 --> 00:27:51,030 Ich denke, Christ schon gesagt, dies vor. 540 00:27:51,030 --> 00:27:51,500 >> Publikum: Eine for-Schleife. 541 00:27:51,500 --> 00:27:52,160 >> ANDI PENG: Eine for-Schleife? 542 00:27:52,160 --> 00:27:52,770 Genau. 543 00:27:52,770 --> 00:27:56,060 So ist wohl diese gehen, um eine for-Schleife ist. 544 00:27:56,060 --> 00:27:59,240 Was ist ein Check hier gehen, um zu verstehen? 545 00:27:59,240 --> 00:28:02,536 In der Regel, wenn Sie überprüfen möchten wenn etwas ist etwas else-- 546 00:28:02,536 --> 00:28:03,270 >> Publikum: Wenn. 547 00:28:03,270 --> 00:28:06,790 >> ANDI PENG: Ein, wenn, nicht wahr? 548 00:28:06,790 --> 00:28:10,790 Und dann die Swap Hier werden wir gehen Sie über später, denn David 549 00:28:10,790 --> 00:28:12,770 ging durch, dass in der Vorlesung als auch. 550 00:28:12,770 --> 00:28:14,580 Und dann die zweite Iteration implies-- 551 00:28:14,580 --> 00:28:15,120 >> ZIELGRUPPE: Another for-Schleife. 552 00:28:15,120 --> 00:28:16,745 >> ANDI PENG: --another for-Schleife, genau. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Also, wenn wir suchen an das richtig, wir 555 00:28:22,000 --> 00:28:24,680 kann sehen, dass wir wahrscheinlich gehen zu müssen, eine verschachtelte for-Schleife 556 00:28:24,680 --> 00:28:28,330 mit einer bedingten Anweisung in es und dann wird eine tatsächliche Stück Code, das heißt 557 00:28:28,330 --> 00:28:31,360 gehen, um die Werte zu tauschen. 558 00:28:31,360 --> 00:28:35,980 Also habe ich nur allgemein geschrieben eine Pseudocode-Code hier. 559 00:28:35,980 --> 00:28:38,910 Und dann sind wir eigentlich vor sich geht physisch als eine Klasse, 560 00:28:38,910 --> 00:28:40,700 versuchen Sie dies heute umzusetzen. 561 00:28:40,700 --> 00:28:42,486 Gehen wir zurück in dieses IDE. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> UH Oh. 564 00:28:50,230 --> 00:28:51,754 Warum ist das so nicht-- da ist es. 565 00:28:51,754 --> 00:28:52,253 OK. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Es tut uns leid, lassen Sie mich versuchen, in ein bisschen mehr zu vergrößern. 568 00:28:57,500 --> 00:28:59,310 Da gehen wir. 569 00:28:59,310 --> 00:29:05,060 Alles, was ich hier mache ist die ich angelegt habe ein Programm namens "Auswahl / sort.c." 570 00:29:05,060 --> 00:29:10,860 Ich habe eine Reihe von neun erstellt Werte, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 Derzeit, wie Sie können siehe, sie sind ungeordnet. 572 00:29:14,370 --> 00:29:17,880 n wird sich die Zahl sein, dass sagt Ihnen, die Menge der Werte 573 00:29:17,880 --> 00:29:18,920 Sie haben in Ihrem Array. 574 00:29:18,920 --> 00:29:20,670 In diesem Fall haben wir neun Werte. 575 00:29:20,670 --> 00:29:23,760 Und ich habe gerade eine for-Schleife hier daß druckt die unsortierten Array. 576 00:29:23,760 --> 00:29:28,370 >> Und am Ende habe ich bekam auch ein für Schleife, die nur druckt er wieder heraus. 577 00:29:28,370 --> 00:29:32,070 Theoretisch, wenn dieses Programm korrekt arbeitet, am Ende, 578 00:29:32,070 --> 00:29:35,670 Sie sollten sehen, for-Schleife eine gedruckte in dem 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 sind alle richtig in Ordnung. 580 00:29:39,310 --> 00:29:43,410 >> So haben wir unsere Pseudo hier. 581 00:29:43,410 --> 00:29:46,090 Möchte jemand zu-- Ich bin einfach gehen, um zu gehen fragen Sie nach volunteers-- 582 00:29:46,090 --> 00:29:49,540 sagen Sie mir, was genau zu, wenn geben wir zunächst nur durchlaufen möchten 583 00:29:49,540 --> 00:29:52,840 durch die zu Beginn dieses Array? 584 00:29:52,840 --> 00:29:55,204 Was ist der Code-Zeile Ich bin Wahrscheinlich werde hier brauchen? 585 00:29:55,204 --> 00:29:56,990 >> ZIELGRUPPE: [unverständlich] 586 00:29:56,990 --> 00:29:59,010 >> ANDI PENG: Ja, das Gefühl, kostenlos zu-- sorry, Sie 587 00:29:59,010 --> 00:30:02,318 müssen nicht up-- Gefühl stehen frei, Ihre Stimme ein wenig zu erhöhen. 588 00:30:02,318 --> 00:30:08,190 >> Gruppe: für int i gleich 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI PENG: Ja, gut. 590 00:30:10,690 --> 00:30:15,220 >> ZIELGRUPPE: i weniger als Array-Länge ist. 591 00:30:15,220 --> 00:30:19,630 >> ANDI PENG: So halten in dagegen hier, weil wir 592 00:30:19,630 --> 00:30:23,060 keine Funktion haben, dass sagt uns die Länge eines Arrays, 593 00:30:23,060 --> 00:30:25,790 Wir haben bereits eine Wert, dass speichert. 594 00:30:25,790 --> 00:30:27,920 Recht? 595 00:30:27,920 --> 00:30:31,010 Eine andere Sache zu halten in mind-- in einem Array 596 00:30:31,010 --> 00:30:33,940 von neun Werten, was sind die Indizes? 597 00:30:33,940 --> 00:30:38,720 Sagen wir einfach, dieses Array von 0 bis 3 ist. 598 00:30:38,720 --> 00:30:41,500 Sie sehen, dass der letzten Index ist eigentlich 3. 599 00:30:41,500 --> 00:30:45,530 Es ist nicht 4, obwohl es vier Werte im Array. 600 00:30:45,530 --> 00:30:49,866 >> Also hier, wir müssen sehr vorsichtig sein, von dem, was unsere Bedingung für die Länge 601 00:30:49,866 --> 00:30:50,490 es wird. 602 00:30:50,490 --> 00:30:51,948 >> ZIELGRUPPE: Wäre es nicht n minus 1? 603 00:30:51,948 --> 00:30:54,440 ANDI PENG: Es wird n minus 1, genau. 604 00:30:54,440 --> 00:30:57,379 Macht das Sinn, warum es ist n minus 1, jeder? 605 00:30:57,379 --> 00:30:58,920 Es ist, weil Arrays sind nullindiziert. 606 00:30:58,920 --> 00:31:02,010 Sie beginnen bei 0 und führen Sie bis zu n minus 1. 607 00:31:02,010 --> 00:31:03,210 Ja, es ist ein bisschen schwierig. 608 00:31:03,210 --> 00:31:03,730 OK. 609 00:31:03,730 --> 00:31:05,929 Und dann-- 610 00:31:05,929 --> 00:31:08,054 ZIELGRUPPE: Isnt'1 dass bereits um wenn genommen, 611 00:31:08,054 --> 00:31:11,400 nur um nicht zu sagen "kleiner oder gleich "und einfach nur sagen," weniger als? " 612 00:31:11,400 --> 00:31:13,108 >> ANDI Peng: Das ist eine wirklich gute Frage. 613 00:31:13,108 --> 00:31:13,630 Also ja. 614 00:31:13,630 --> 00:31:17,410 Sondern auch, die Art und Weise, dass wir Umsetzung der Überprüfung Recht, 615 00:31:17,410 --> 00:31:19,120 müssen Sie zwei Werte zu vergleichen. 616 00:31:19,120 --> 00:31:21,009 So dass Sie wirklich wollen, lassen Sie das "auf" leer. 617 00:31:21,009 --> 00:31:23,050 Denn wenn Sie vergleichen diese, werden Sie nicht 618 00:31:23,050 --> 00:31:25,530 irgendetwas, nachdem es zu vergleichen, oder? 619 00:31:25,530 --> 00:31:27,460 Ja. 620 00:31:27,460 --> 00:31:29,297 So ++ i. 621 00:31:29,297 --> 00:31:30,380 Fügen wir unserem Klammern. 622 00:31:30,380 --> 00:31:30,880 Whoops. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Groß. 625 00:31:34,710 --> 00:31:39,117 So haben wir den Anfang unserer äußeren Schleife. 626 00:31:39,117 --> 00:31:41,450 So, jetzt wollen wir wahrscheinlich erstellen Sie eine Variable für die Aufbewahrung 627 00:31:41,450 --> 00:31:43,085 Spur der kleinste Wert, oder? 628 00:31:43,085 --> 00:31:45,751 Will jemand mir die geben Codezeile, die das tun würde? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Was brauchen wir, wenn wir zu wollen, etwas zu speichern? 631 00:31:53,570 --> 00:31:55,047 >> Recht. 632 00:31:55,047 --> 00:31:57,630 Vielleicht ein besserer Name für die würde "temp" be-- völlig works-- 633 00:31:57,630 --> 00:32:00,655 vielleicht ein mehr treffend benannt würden, wenn wir wollen, die kleinste value-- 634 00:32:00,655 --> 00:32:01,624 >> ZIELGRUPPE: Min. 635 00:32:01,624 --> 00:32:02,790 ANDI PENG: min, dort gehen wir. 636 00:32:02,790 --> 00:32:05,230 min wäre gut. 637 00:32:05,230 --> 00:32:08,340 Und hier, was machen wir möchte es zu initialisieren? 638 00:32:08,340 --> 00:32:09,620 Das ist ein bisschen schwierig. 639 00:32:09,620 --> 00:32:13,580 Denn noch heute über die Anfang dieses Array, 640 00:32:13,580 --> 00:32:15,730 Sie nicht auf alles, was ausgesehen haben, oder? 641 00:32:15,730 --> 00:32:19,200 Also, was, automatisch, wenn sind wir nur auf i gleich 0 ist, 642 00:32:19,200 --> 00:32:22,302 was machen wir initialisieren möchten unsere erste Minimalwert zu? 643 00:32:22,302 --> 00:32:22,802 ZIELGRUPPE: i. 644 00:32:22,802 --> 00:32:24,790 ANDI Peng: Ich, genau. 645 00:32:24,790 --> 00:32:27,040 Christabel, warum wir wollen, um es in i zu initialisieren? 646 00:32:27,040 --> 00:32:28,510 >> ZIELGRUPPE: weil, na ja, wir mit 0 beginnen. 647 00:32:28,510 --> 00:32:31,660 So, da haben wir nichts zu vergleichen, es wird die Mindest am Ende als 0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI PENG: Genau. 649 00:32:32,451 --> 00:32:34,400 Also ist sie genau richtig. 650 00:32:34,400 --> 00:32:36,780 Denn wir haben nicht wirklich sah nichts, 651 00:32:36,780 --> 00:32:38,680 wir wissen nicht, was unsere Mindestwert ist. 652 00:32:38,680 --> 00:32:41,960 Wir wollen einfach nur initialisieren, um i, der, gerade, ist hier richtig. 653 00:32:41,960 --> 00:32:44,750 Und während wir fortfahren, nach unten zu verschieben dieses Array, 654 00:32:44,750 --> 00:32:48,122 wir werden sehen, dass mit jedem zusätzliche Pass, erhöht i. 655 00:32:48,122 --> 00:32:49,830 Und so an diesem Punkt, i ist wahrscheinlich 656 00:32:49,830 --> 00:32:52,329 zu wollen, das Minimum sein, denn es geht um was auch immer 657 00:32:52,329 --> 00:32:54,520 ist der Beginn des unsortierten Array. 658 00:32:54,520 --> 00:32:55,270 Cool. 659 00:32:55,270 --> 00:32:58,720 >> So, jetzt hinzufügen möchten uns eine for-Schleife hier, das ist 660 00:32:58,720 --> 00:33:03,225 gehen, um durch die Iteration unsortierte oder der Rest dieses Array. 661 00:33:03,225 --> 00:33:05,808 Will jemand mir einen geben Codezeile, die das tun würde? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- was machen wir nach unten brauchen hier? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 Was wird in dieser for-Schleife zu gehen? 666 00:33:18,820 --> 00:33:19,465 Ja. 667 00:33:19,465 --> 00:33:21,590 Publikum: So würden wir zu wollen haben eine andere ganze Zahl ist, 668 00:33:21,590 --> 00:33:25,080 weil wir durch den Rest laufen der Array statt i, vielleicht 669 00:33:25,080 --> 00:33:25,760 j. 670 00:33:25,760 --> 00:33:27,301 >> ANDI PENG: Ja, das klingt j gut zu mir. 671 00:33:27,301 --> 00:33:27,850 Equals? 672 00:33:27,850 --> 00:33:33,930 >> Publikum: So würde ich sein, plus 1, weil Sie bei der nächsten Wert angefangen haben. 673 00:33:33,930 --> 00:33:40,395 Und dann an den end-- so wieder, j weniger als n minus 1 und dann j ++. 674 00:33:40,395 --> 00:33:41,103 ANDI PENG: Great. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> Und dann hier, wir gehen zu wollen, zu überprüfen, um zu sehen, ob unsere Bedingung erfüllt ist, 677 00:33:52,750 --> 00:33:53,250 Recht? 678 00:33:53,250 --> 00:33:55,740 Weil Sie es wollen ändern Sie den Minimalwert 679 00:33:55,740 --> 00:33:58,700 wenn es tatsächlich kleiner als das, was Sie vergleicht sie mit, nicht wahr? 680 00:33:58,700 --> 00:34:01,146 Also, was sollen wir hier suchen? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Überprüfen Sie,. 683 00:34:04,897 --> 00:34:06,730 Welche Art von Aussage werden wir wahrscheinlich 684 00:34:06,730 --> 00:34:08,389 ti wollen, wenn wir benutzen wollen etwas zu überprüfen? 685 00:34:08,389 --> 00:34:09,360 >> Publikum: Eine if-Anweisung. 686 00:34:09,360 --> 00:34:10,485 >> ANDI PENG: Eine if-Anweisung. 687 00:34:10,485 --> 00:34:13,155 So if-- und was los zu sein die Bedingung, die wir im Inneren wollen 688 00:34:13,155 --> 00:34:13,988 unserer if-Anweisung? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> Publikum: Ist der Wert von j ist kleiner als der Wert von i-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI PENG: Genau. 692 00:34:24,600 --> 00:34:27,480 So if-- so dass diese Anordnung wird als "Array". 693 00:34:27,480 --> 00:34:27,980 Groß. 694 00:34:27,980 --> 00:34:30,465 Also, wenn array-- was war das? 695 00:34:30,465 --> 00:34:31,090 Sag das nochmal. 696 00:34:31,090 --> 00:34:39,590 >> Publikum: Wenn Array-j kleiner ist Array-i, dann würden wir die min. 697 00:34:39,590 --> 00:34:41,590 So würde das min j sein. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI PENG: Macht das Sinn? 700 00:34:47,249 --> 00:34:48,670 OK. 701 00:34:48,670 --> 00:34:52,929 Und jetzt hier unten, wir tatsächlich wollen die Swap umzusetzen, nicht wahr? 702 00:34:52,929 --> 00:34:58,285 So erinnern, in der Aula, dass David, als er versuchte, the-- was tauschen 703 00:34:58,285 --> 00:34:59,996 es-- Orangensaft und milk-- 704 00:34:59,996 --> 00:35:01,150 >> Publikum: Das war eklig. 705 00:35:01,150 --> 00:35:02,816 >> ANDI PENG: Ja, das war ziemlich ekelhaft. 706 00:35:02,816 --> 00:35:05,310 Aber es war ein ziemlich gut Konzept demonstrieren Zeit. 707 00:35:05,310 --> 00:35:08,430 Also denken Sie an Ihre Werte hier. 708 00:35:08,430 --> 00:35:10,794 Sie haben eine Reihe bekam min, eine Anordnung von i, 709 00:35:10,794 --> 00:35:12,460 oder was auch immer wir versuchten, hier tauschen. 710 00:35:12,460 --> 00:35:15,310 Und Sie wahrscheinlich nicht in gießen Sie sie miteinander zur gleichen Zeit, nicht wahr? 711 00:35:15,310 --> 00:35:17,180 Also was machen wir zu müssen, um hier zu erstellen 712 00:35:17,180 --> 00:35:19,126 um die Werte korrekt zu tauschen? 713 00:35:19,126 --> 00:35:19,820 >> Publikum: Eine temporäre Variable. 714 00:35:19,820 --> 00:35:21,370 >> ANDI PENG: Eine temporäre Variable. 715 00:35:21,370 --> 00:35:22,570 Lassen Sie uns so tun, int Temp. 716 00:35:22,570 --> 00:35:25,681 Siehe, dies wäre ein besser sein Zeit zu-- whoa, was war das? 717 00:35:25,681 --> 00:35:26,180 OK. 718 00:35:26,180 --> 00:35:29,800 So wäre dies ein besser gewesen, Zeit, um den variablen "Temp." name 719 00:35:29,800 --> 00:35:30,730 Lassen Sie uns so tun, int Temp. 720 00:35:30,730 --> 00:35:32,563 Was machen wir set temp gleich hierher? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 ZIELGRUPPE: Min? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI PENG: Es ist ein bisschen schwierig. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 Es ist eigentlich nicht am Ende egal. 727 00:35:44,880 --> 00:35:47,690 Es spielt keine Rolle, was Um Sie wählen, um in zu tauschen 728 00:35:47,690 --> 00:35:50,862 solange Sie darauf achten, bist du bist die Verfolgung der, was Sie tauschen sind. 729 00:35:50,862 --> 00:35:52,250 >> Publikum: Es könnte Array-i sein. 730 00:35:52,250 --> 00:35:53,666 >> ANDI PENG: Ja, lass uns Array-i. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 Und was ist dann die nächste Zeile Code wollen wir hier haben? 733 00:35:59,305 --> 00:36:00,680 ZIELGRUPPE: Array-i gleich Array-j. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI PENG: Und schließlich? 736 00:36:08,070 --> 00:36:12,070 ZIELGRUPPE: Array-j gleich Array-i. 737 00:36:12,070 --> 00:36:14,525 ZIELGRUPPE: oder Array-j equals Array-temp-- oder, Temp. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> ANDI PENG: OK. 740 00:36:19,430 --> 00:36:21,510 Also lassen Sie uns laufen diese und sehen, wenn es geht, um zu arbeiten. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Wo ist das passiert? 743 00:36:39,335 --> 00:36:40,210 Oh, das ist ein Problem. 744 00:36:40,210 --> 00:36:44,320 Siehe, auf der Leitung 40, wir sind versuchen, Array-j verwenden? 745 00:36:44,320 --> 00:36:47,022 Aber woher kommt j nur existieren? 746 00:36:47,022 --> 00:36:48,402 >> Publikum: In der for-Schleife. 747 00:36:48,402 --> 00:36:49,110 ANDI PENG: Richtig. 748 00:36:49,110 --> 00:36:51,730 Also, was sollen wir tun müssen? 749 00:36:51,730 --> 00:36:53,170 >> ZIELGRUPPE: Definieren Sie mit raus the-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 ZIELGRUPPE: Ja, ich denke, Sie haben zu einem anderen if-Anweisung, direkt zu verwenden? 752 00:37:00,610 --> 00:37:05,230 So wie, wenn die minimum-- Alles in Ordnung, lass mich nachdenken. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI PENG: Jungs, versuchen einen Blick werfen wir 755 00:37:09,990 --> 00:37:11,270 sehen, was ist etwas, was wir hier tun? 756 00:37:11,270 --> 00:37:11,811 >> ZIELGRUPPE: OK. 757 00:37:11,811 --> 00:37:15,900 Also, wenn das Minimum ist nicht gleich j-- so still ich--, wenn das Minimum 758 00:37:15,900 --> 00:37:17,570 dann würden wir nicht haben, um zu tauschen. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI PENG: Bedeutet das, gleich i? 761 00:37:24,712 --> 00:37:25,920 Was wollen Sie damit sagen? 762 00:37:25,920 --> 00:37:30,494 >> ZIELGRUPPE: Oder ja, wenn die Mindest nicht gleich i, yeah. 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 ANDI PENG: OK. 765 00:37:40,210 --> 00:37:42,040 Nun, das löst, Art, unsere Probleme. 766 00:37:42,040 --> 00:37:47,265 Aber das immer noch nicht lösen, die Problem, was passiert, wenn j-- seit j 767 00:37:47,265 --> 00:37:49,890 nicht außerhalb von ihr existieren, was Sie wollen wir damit zu tun? 768 00:37:49,890 --> 00:37:50,698 Deklarieren Sie es außerhalb? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Lassen Sie uns versuchen Sie diese. 771 00:38:02,730 --> 00:38:04,435 UH Oh. 772 00:38:04,435 --> 00:38:06,200 Unsere Art, funktioniert nicht. 773 00:38:06,200 --> 00:38:10,060 >> Wie Sie, unsere anfängliche sehen Array hatten diese Werte. 774 00:38:10,060 --> 00:38:14,800 Und danach es haben sollte in 1, 2, 3, 4, 5, 6, 7, 8, 9 ist. 775 00:38:14,800 --> 00:38:15,530 Es funktioniert nicht. 776 00:38:15,530 --> 00:38:16,030 Ahh. 777 00:38:16,030 --> 00:38:17,184 Was machen wir? 778 00:38:17,184 --> 00:38:17,850 ZIELGRUPPE: Debug. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI PENG: Okay, können wir versuchen, dass. 781 00:38:23,370 --> 00:38:25,030 Wir können zu debuggen. 782 00:38:25,030 --> 00:38:26,042 Zoom out ein wenig. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Lassen Sie uns unsere Haltepunkt. 785 00:38:33,656 --> 00:38:37,280 Lassen Sie uns gehen like-- OK. 786 00:38:37,280 --> 00:38:40,444 >> Also, weil wir wissen bereits, dass diese Zeilen, 15 bis 22, 787 00:38:40,444 --> 00:38:43,610 sind working--, weil alles, was ich tue, ist nur durchlaufen und printing-- 788 00:38:43,610 --> 00:38:45,406 Ich kann gehen Sie vor und überspringen, dass. 789 00:38:45,406 --> 00:38:47,280 Beginnen wir in Zeile 25. 790 00:38:47,280 --> 00:38:48,712 Oop, lassen Sie mich loswerden, dass. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> Publikum: So ist der Haltepunkt wo das Debugging beginnt? 793 00:38:54,057 --> 00:38:54,890 ANDI PENG: oder stoppt. 794 00:38:54,890 --> 00:38:55,670 ZIELGRUPPE: oder stoppt. 795 00:38:55,670 --> 00:38:55,930 ANDI PENG: Ja. 796 00:38:55,930 --> 00:38:58,640 Sie können mehrere Haltepunkte setzen und sie kann nur direkt von einem zum anderen. 797 00:38:58,640 --> 00:39:01,590 Aber in diesem Fall wissen wir nicht, wo der Fehler passiert. 798 00:39:01,590 --> 00:39:03,780 So wollen wir nur beginnen von oben nach unten. 799 00:39:03,780 --> 00:39:05,020 Yep. 800 00:39:05,020 --> 00:39:05,550 OK. 801 00:39:05,550 --> 00:39:08,460 >> Also diese Linie hier, wir einspringen können. 802 00:39:08,460 --> 00:39:11,499 Sie können hier unten zu sehen, Wir haben eine Reihe bekam. 803 00:39:11,499 --> 00:39:13,290 Das sind die Werte die in dem Array. 804 00:39:13,290 --> 00:39:16,360 Siehst du das, wie Index 0, es entspricht der value-- oh, 805 00:39:16,360 --> 00:39:17,526 Ich werde versuchen, um es zu vergrößern. 806 00:39:17,526 --> 00:39:20,650 Sorry, es ist wirklich schwer bei Array-Index 0 see--, 807 00:39:20,650 --> 00:39:24,090 wir einen Wert von 4 aufweisen und dann so weiter und so fort. 808 00:39:24,090 --> 00:39:25,670 Wir haben unsere lokalen Variablen. 809 00:39:25,670 --> 00:39:28,570 Im Moment ist gleich i 0, was wir wollen, dass es sein. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> Und so wollen wir halten durch Schritt. 812 00:39:33,690 --> 00:39:36,850 Unser Mindest gleich 0 ist, was wir wollen auch, dass es sein. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 Und dann unser zweites zu treten wir Schleife, wenn Array-j weniger als Array-i ist, 815 00:39:45,560 --> 00:39:46,380 was es nicht war. 816 00:39:46,380 --> 00:39:48,130 So haben Sie gesehen, wie dass übersprungen, dass? 817 00:39:48,130 --> 00:39:52,430 >> Publikum: So sollte das, wenn Mindest alle dass-- nicht sollte, dass 818 00:39:52,430 --> 00:39:55,424 innerhalb der ersten for-Schleife sein? 819 00:39:55,424 --> 00:39:57,340 ANDI PENG: Nein, denn Sie wollen immer noch zu testen. 820 00:39:57,340 --> 00:40:00,329 Sie wollen einen Vergleich jedes tun Zeit, auch nachdem Sie durch sie auszuführen. 821 00:40:00,329 --> 00:40:02,620 Sie wollen nicht nur, es zu tun auf der ersten Durchgangs. 822 00:40:02,620 --> 00:40:05,240 Sie wollen es zu tun jede weitere Pass erneut. 823 00:40:05,240 --> 00:40:07,198 Können Sie dies überprüfen möchten Ihr Zustand im Inneren. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Also werden wir gerade dabei, Halten Sie hier, durch läuft. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Ich werde euch einen Hinweis geben. 828 00:40:18,420 --> 00:40:23,910 Es hat mit der Tatsache zu tun, dass, wenn Sie Überprüfung Ihrer bedingte, 829 00:40:23,910 --> 00:40:26,600 Sie nicht überprüft für die korrekte Index. 830 00:40:26,600 --> 00:40:32,510 So jetzt bist du für die Überprüfung Array-Index von j weniger als Array 831 00:40:32,510 --> 00:40:33,970 Index der i. 832 00:40:33,970 --> 00:40:36,580 Aber was werden Sie tun, um der Beginn der for-Schleife? 833 00:40:36,580 --> 00:40:38,260 Sind Sie nicht die Einstellung j gleich i? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Ja, so können wir tatsächlich Verlassen des Debuggers Sie hier. 836 00:40:45,415 --> 00:40:47,040 Werfen wir also einen Blick auf unsere Pseudocode. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- wir zu gehen beginnen bei i gleich 0 ist. 839 00:40:52,580 --> 00:40:54,760 Wir werden gehen bis zu n minus 1. 840 00:40:54,760 --> 00:40:58,040 Lassen Sie uns, wir haben das richtig? 841 00:40:58,040 --> 00:40:59,580 Yep, das war richtig. 842 00:40:59,580 --> 00:41:02,080 >> Also hier drinnen, wir sind gehen, um einen Mindestwert zu schaffen 843 00:41:02,080 --> 00:41:03,630 und stellen Sie, dass gleich i. 844 00:41:03,630 --> 00:41:04,950 Haben wir das? 845 00:41:04,950 --> 00:41:06,270 Yep, das tat. 846 00:41:06,270 --> 00:41:10,430 Jetzt in unserem inneren for-Schleife, wir sind werde j tun i gleich n minus 1. 847 00:41:10,430 --> 00:41:11,950 Haben wir das? 848 00:41:11,950 --> 00:41:15,540 In der Tat haben wir das. 849 00:41:15,540 --> 00:41:19,922 >> So aber was machen wir hier zu vergleichen? 850 00:41:19,922 --> 00:41:20,925 >> ZIELGRUPPE: j plus 1. 851 00:41:20,925 --> 00:41:21,716 ANDI PENG: Genau. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 Und dann wirst du einstellen möchten sind Ihre Mindest gleich j + 1 als auch. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Also ging ich wirklich schnell durch, dass. 856 00:41:32,640 --> 00:41:36,190 Haben Sie Jungs verstehen Deshalb ist es j plus 1? 857 00:41:36,190 --> 00:41:36,890 OK. 858 00:41:36,890 --> 00:41:40,700 >> Also in Ihrem Array, in Ihren ersten Durchlauf durch, 859 00:41:40,700 --> 00:41:44,850 Ihre for-Schleife, für int i gleich 0 ist, lassen Sie uns einfach 860 00:41:44,850 --> 00:41:46,740 annehmen, dies noch nicht geändert wurde. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 Wir haben eine Reihe von vollständig, nur vier unsortierten Elemente, nicht wahr? 863 00:41:56,760 --> 00:42:00,760 Deshalb wollen wir initialisieren i gleich 0. 864 00:42:00,760 --> 00:42:03,650 Und ich werde gerade durch diese Schleife laufen. 865 00:42:03,650 --> 00:42:08,560 Und so im ersten Durchgang, werden wir um eine Variable namens "min" zu initialisieren 866 00:42:08,560 --> 00:42:11,245 dass auch gleich i, weil wir haben nicht einen Minimalwert. 867 00:42:11,245 --> 00:42:12,870 Also das ist derzeit gleich 0 als auch. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 Und dann werden wir zu durchlaufen. 870 00:42:17,640 --> 00:42:19,270 Und wir wollen noch einmal durchlaufen. 871 00:42:19,270 --> 00:42:22,900 Jetzt, da wir gefunden haben, was unsere Mindest ist, dass wir, um durch laufen möchten 872 00:42:22,900 --> 00:42:25,190 wieder, um zu sehen, ob es zu vergleichen, oder? 873 00:42:25,190 --> 00:42:40,440 So j, hier vor sich geht gleich i, nämlich 0. 874 00:42:40,440 --> 00:42:46,320 Und dann, wenn Array j plus i, die ist diejenige, die als nächstes über ist, da weniger 875 00:42:46,320 --> 00:42:49,270 als das, was Ihre aktuelle Mindest Wert ist, Sie austauschen möchten. 876 00:42:49,270 --> 00:42:56,850 >> Also lasst uns einfach sagen, dass wir haben, wie, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Gerade jetzt, gleich ist i 0 und j gleich 0 ist. 878 00:43:01,610 --> 00:43:05,210 Und das ist unser Minimalwert. 879 00:43:05,210 --> 00:43:09,950 Wenn Array-J plus i-- so, wenn die eine das ist, nach dem man wir suchen 880 00:43:09,950 --> 00:43:13,450 größer ist als der vorherige ist, es geht um das Minimum zu werden. 881 00:43:13,450 --> 00:43:18,120 >> So, hier sehen wir, dass 5 nicht kleiner als die. 882 00:43:18,120 --> 00:43:19,730 Also, es wird nicht 5 sein. 883 00:43:19,730 --> 00:43:23,580 Wir sehen, dass 1 kleiner als 2, oder? 884 00:43:23,580 --> 00:43:32,970 So, jetzt wissen wir, dass unsere Mindest ist werde der Indexwert bei 0, 1, 2 zu sein. 885 00:43:32,970 --> 00:43:34,030 Ja? 886 00:43:34,030 --> 00:43:39,170 Und dann, wenn Sie sich hier bekommen, können Sie die richtigen Werte zu tauschen. 887 00:43:39,170 --> 00:43:42,610 >> Also, wenn Sie Jungs waren gerade mit der j vor, Sie waren nicht auf der Suche an der einen 888 00:43:42,610 --> 00:43:43,260 Danach. 889 00:43:43,260 --> 00:43:44,520 Sie wurden bei der Suche der gleiche Wert, der 890 00:43:44,520 --> 00:43:46,290 Deshalb ist es einfach nicht, etwas zu tun. 891 00:43:46,290 --> 00:43:49,721 Heißt das sinnvoll sein, alle zusammen, Deshalb brauchten wir, dass es plus 1? 892 00:43:49,721 --> 00:43:50,220 OK. 893 00:43:50,220 --> 00:43:53,345 Jetzt lassen Sie uns einfach laufen durch sie zu machen, dass der restliche Code korrekt ist. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Warum ist das passiert? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ach, es ist der min direkt hier. 898 00:44:16,364 --> 00:44:17,780 Wir waren Vergleich der falschen Wert. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 Oh nein. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> Oh ja, hier unten waren wir Vertauschen der falsche Werte als gut. 903 00:44:33,482 --> 00:44:34,940 Weil wir bei i und j suchen. 904 00:44:34,940 --> 00:44:36,440 Das sind die, wir wurden überprüft. 905 00:44:36,440 --> 00:44:39,160 Wir haben tatsächlich an den Swap möchten Minimum, das aktuelle Minimum, 906 00:44:39,160 --> 00:44:40,550 mit dem, was der eine Außenseite ist. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 Und wie Sie Jungs können sich sehen Hier haben wir ein sortiertes Array. 909 00:45:05,402 --> 00:45:07,110 Es musste einfach mit zu tun die Tatsache, dass, wenn 910 00:45:07,110 --> 00:45:09,350 waren wir die Überprüfung der Werten wir den Vergleich, 911 00:45:09,350 --> 00:45:11,226 wir waren nicht auf der Suche in den richtigen Werten. 912 00:45:11,226 --> 00:45:13,850 Wir wurden an der gleichen einen Blick hier eigentlich nicht tauschen sie. 913 00:45:13,850 --> 00:45:17,135 Sie müssen auf der einen nächsten aussehen zu ihm und dann tauschen können. 914 00:45:17,135 --> 00:45:19,260 Also das ist, welche Art von war Lauschangriff unseren Code vor. 915 00:45:19,260 --> 00:45:22,460 Und was ich hier tat, ist alles, was der Debugger könnte für Sie getan haben, 916 00:45:22,460 --> 00:45:23,810 Ich habe es nur auf die Brett, weil es einfacher ist 917 00:45:23,810 --> 00:45:26,320 zu, anstatt zu versuchen zu sehen um auf der Debugger heranzoomen. 918 00:45:26,320 --> 00:45:29,391 Ist das sinnvoll, um alle? 919 00:45:29,391 --> 00:45:29,890 Cool. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Gut. 922 00:45:35,410 --> 00:45:41,070 Wir können zu reden bewegen asymptotische Notation, die 923 00:45:41,070 --> 00:45:44,580 ist nur eine andere Art zu sagen die Laufzeiten aller dieser Sorten. 924 00:45:44,580 --> 00:45:47,650 So weiß ich, David, in der Aula, berührte Laufzeiten. 925 00:45:47,650 --> 00:45:52,124 Und er durch die ganze Formel ging wie man die Laufzeiten zu berechnen. 926 00:45:52,124 --> 00:45:53,040 Keine Sorgen darüber. 927 00:45:53,040 --> 00:45:54,660 Wenn Sie wirklich neugierig sind auf, wie das funktioniert, 928 00:45:54,660 --> 00:45:55,810 zögern Sie nicht, mich nach dem Abschnitt zu sprechen. 929 00:45:55,810 --> 00:45:57,560 Wir können zu Fuß durch die Formeln zusammen. 930 00:45:57,560 --> 00:46:00,689 Aber ihr habt doch alle, wirklich wissen ist, dass mehr als 2 n quadriert 931 00:46:00,689 --> 00:46:01,980 ist dasselbe wie n quadriert. 932 00:46:01,980 --> 00:46:04,710 Da die größte Zahl, der Exponent, wächst das Beste. 933 00:46:04,710 --> 00:46:06,590 Und so für unsere Zwecke, alles, was wir über Pflege 934 00:46:06,590 --> 00:46:09,470 ist, dass riesige Zahl, die wächst. 935 00:46:09,470 --> 00:46:13,340 >> Also, was ist der beste Fall, Laufzeit des Auswahl sortieren? 936 00:46:13,340 --> 00:46:15,830 Wenn Sie gehen zu müssen, sind um durch eine Liste durchlaufen 937 00:46:15,830 --> 00:46:18,712 und dann durch Iteration der Rest der Liste, 938 00:46:18,712 --> 00:46:20,420 wie oft sind Sie wahrscheinlich zu, 939 00:46:20,420 --> 00:46:24,612 im schlimmsten Fall-- in der besten Fall sorry-- durchlaufen? 940 00:46:24,612 --> 00:46:27,070 Vielleicht ist die bessere Frage ist, zu fragen, was ist das Worst-Case- 941 00:46:27,070 --> 00:46:28,153 Laufzeit des Auswahl sort. 942 00:46:28,153 --> 00:46:29,366 ZIELGRUPPE: n quadriert. 943 00:46:29,366 --> 00:46:30,740 ANDI PENG: Es ist n quadriert, rechts. 944 00:46:30,740 --> 00:46:36,986 So eine einfache Möglichkeit, denke das ist wie, jedes Mal, wenn zwei for-Schleifen verschachtelt sind, 945 00:46:36,986 --> 00:46:38,110 es wird n quadriert werden. 946 00:46:38,110 --> 00:46:40,386 Da sind Sie nicht nur durchlauf wieder, 947 00:46:40,386 --> 00:46:42,260 Sie müssen zurück um und durch sie auszuführen 948 00:46:42,260 --> 00:46:44,980 wieder im Inneren für jeden Wert. 949 00:46:44,980 --> 00:46:48,640 Also in diesem Fall, Sie laufen n sind mal n quadriert, das Leid ist--, 950 00:46:48,640 --> 00:46:50,505 n mal n, die n Quadrat ist gleich. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> Und Art ist auch ein bisschen einzigartig in dem Sinn 953 00:46:56,360 --> 00:46:59,774 dass es keine Rolle spielt, wenn diese Werte sind schon in Ordnung. 954 00:46:59,774 --> 00:47:01,440 Es ist immer noch gehen, um durch sowieso laufen. 955 00:47:01,440 --> 00:47:03,872 Sagen wir einfach, das war 1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Unabhängig davon, ob es in war Um es noch würde durch ran 957 00:47:07,080 --> 00:47:08,620 und noch überprüft den minimalen Wert. 958 00:47:08,620 --> 00:47:10,100 Es würde gemacht haben die dieselbe Anzahl von Schecks 959 00:47:10,100 --> 00:47:12,780 jedes Mal, wenn auch nicht wirklich etwas zu berühren. 960 00:47:12,780 --> 00:47:16,940 >> Also in einem solchen Fall die besten und schlechtesten Laufzeiten sind eigentlich gleichwertig. 961 00:47:16,940 --> 00:47:19,160 So ist die voraussichtliche Laufzeit von Selection Sort, 962 00:47:19,160 --> 00:47:23,790 welche wir durch das Symbol Theta-Theta, in diesem Fall, 963 00:47:23,790 --> 00:47:24,790 würde auch n quadriert werden. 964 00:47:24,790 --> 00:47:26,480 Alle drei von diesen würde n quadriert werden. 965 00:47:26,480 --> 00:47:29,653 Jeder ist klar, warum die Laufzeit wird n quadriert? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Gut. 968 00:47:33,980 --> 00:47:39,120 Also ich bin gerade dabei, schnell zu laufen durch den Rest der Sorten. 969 00:47:39,120 --> 00:47:41,137 Der Algorithmus für bubble sort-- erinnern, 970 00:47:41,137 --> 00:47:43,220 Dies war der erste, David ging im Vortrag. 971 00:47:43,220 --> 00:47:46,000 Im Wesentlichen treten Sie durch die gesamte Liste 972 00:47:46,000 --> 00:47:48,950 und Sie einfach swap-- Vergleichen von zwei zu einer Zeit. 973 00:47:48,950 --> 00:47:51,350 Und wenn man es größer ist, als Sie nur tauschen sie. 974 00:47:51,350 --> 00:47:53,590 Also, wenn diese höher sind, würden Sie tauschen. 975 00:47:53,590 --> 00:47:56,180 Ich habe offizielle rechts hier. 976 00:47:56,180 --> 00:47:59,100 >> Also lassen Sie uns einfach sagen, Sie hatten 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Sie würden die 8 und eine 6 zu vergleichen. 978 00:48:00,571 --> 00:48:01,570 Sie müssten, um sie auszutauschen. 979 00:48:01,570 --> 00:48:02,610 Sie würden die 8 und 4 zu vergleichen. 980 00:48:02,610 --> 00:48:03,609 Sie müssten, um sie auszutauschen. 981 00:48:03,609 --> 00:48:07,000 Wenn Sie die 8 tauschen müssen und die 2, ändern Sie sie als gut. 982 00:48:07,000 --> 00:48:10,760 Also in dem Sinne, können Sie sehen, über einen längeren Zeitraum gespielt 983 00:48:10,760 --> 00:48:13,730 wie die Werte Art von Blase die Enden, deshalb nennen wir 984 00:48:13,730 --> 00:48:15,320 Bubble-Sort. 985 00:48:15,320 --> 00:48:19,950 >> Wir würden gerade laufen wieder auf unserer zweiten Durchgang und unsere dritte Durchgang, 986 00:48:19,950 --> 00:48:21,150 und unser viertes Pass ab. 987 00:48:21,150 --> 00:48:25,820 Im Wesentlichen Bubble Sort gerade läuft , bis Sie nicht machen keine weiteren Swaps. 988 00:48:25,820 --> 00:48:31,109 In diesem Sinne ist dies nur die allgemeine Pseudocode für sie. 989 00:48:31,109 --> 00:48:32,650 Keine Sorge, dies wird alles online sein. 990 00:48:32,650 --> 00:48:34,990 Wir haben nicht wirklich über diese gehen. 991 00:48:34,990 --> 00:48:38,134 >> Wir haben gerade einen Zähler zu initialisieren Variable, die bei 0 beginnt. 992 00:48:38,134 --> 00:48:39,800 Und wir durchlaufen das gesamte Array. 993 00:48:39,800 --> 00:48:43,420 Und wenn ein Wert, wenn dies ist-- Wert größer als dieser Wert ist, 994 00:48:43,420 --> 00:48:44,610 Sie gehen, um sie auszutauschen. 995 00:48:44,610 --> 00:48:46,860 Und dann haben Sie gerade sind gehen, um weiterzumachen. 996 00:48:46,860 --> 00:48:47,970 Und du wirst zu zählen. 997 00:48:47,970 --> 00:48:50,845 Und Sie gerade gehen zu tun zu halten dies während der Zähler größer 998 00:48:50,845 --> 00:48:53,345 als 0 ist, was bedeutet, dass jedes Mal, wenn Sie zu tauschen, 999 00:48:53,345 --> 00:48:55,220 Sie wissen, Sie gehen wollen hin und wieder zu überprüfen. 1000 00:48:55,220 --> 00:48:59,510 Sie wollen Kontrolle zu halten, bis Sie wissen, dass Sie nicht haben, um nicht mehr tauschen. 1001 00:48:59,510 --> 00:49:05,570 >> Also, was sind die besten und schlechtesten Bei Laufzeiten für Bubble-Sort? 1002 00:49:05,570 --> 00:49:09,300 Und das ist eigentlich hint-- verschiedenen von der Auswahl Art in dem Sinne, 1003 00:49:09,300 --> 00:49:11,810 dass diese beiden Antworten nicht die gleichen sind. 1004 00:49:11,810 --> 00:49:14,709 Überlegen Sie, was passieren würde, in ein Fall, wenn es bereits sortiert. 1005 00:49:14,709 --> 00:49:16,500 Und darüber nachzudenken, was würde passieren, wenn es 1006 00:49:16,500 --> 00:49:18,372 in dem Fall, in dem es nicht sortiert. 1007 00:49:18,372 --> 00:49:20,580 Und Sie Art ausgeführt werden können durch, warum das passiert. 1008 00:49:20,580 --> 00:49:22,954 Ich werde euch geben, wie, 30 Sekunden, um darüber nachzudenken. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> OK. 1011 00:49:53,540 --> 00:49:57,462 Hat jemand eine Vermutung, was die haben Worst-Case-Laufzeit des Bubble-Sort ist? 1012 00:49:57,462 --> 00:49:57,962 Ja. 1013 00:49:57,962 --> 00:50:07,810 >> ZIELGRUPPE: Wäre es, wie, n-mal sein n minus 1 oder so ähnlich? 1014 00:50:07,810 --> 00:50:10,650 Wie jedes Mal ausgeführt wird, es ist nur, wie man Auslagerungs weniger 1015 00:50:10,650 --> 00:50:10,960 dass das, was es war. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI PENG: Ja, so Sie sind total richtig. 1017 00:50:12,668 --> 00:50:15,940 Und dies ist ein Fall, in dem Ihr Antwort war eigentlich komplexere 1018 00:50:15,940 --> 00:50:17,240 als die, die wir brauchen, um zu geben. 1019 00:50:17,240 --> 00:50:19,772 Also, es wird run-- Ich bin gehen, um all das hier zu löschen. 1020 00:50:19,772 --> 00:50:20,480 Jeder ist gut? 1021 00:50:20,480 --> 00:50:21,869 Kann ich zu löschen das? 1022 00:50:21,869 --> 00:50:22,368 OK. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Sie werden durch n Run Zeiten ersten Mal, nicht wahr? 1025 00:50:30,320 --> 00:50:33,200 Und sie gehen zu durchlaufen n minus 1 zum zweiten Mal, nicht wahr? 1026 00:50:33,200 --> 00:50:37,130 Und dann wirst du zu halten sind gehen, n Mine 2, und so weiter. 1027 00:50:37,130 --> 00:50:40,210 David tat dies in einem Vortrag, in dem, wenn Sie alle diese Werte addiert, 1028 00:50:40,210 --> 00:50:48,080 Sie etwas, das es zu erhalten like-- yeah-- mehr als 2, die im Wesentlichen nur reduziert 1029 00:50:48,080 --> 00:50:49,784 bis n quadriert. 1030 00:50:49,784 --> 00:50:51,700 Du wirst eine bekommen seltsame Bruch drin. 1031 00:50:51,700 --> 00:50:53,892 Und so weiß nur, dass die n quadriert immer 1032 00:50:53,892 --> 00:50:55,350 Vorrang vor dem Bruch. 1033 00:50:55,350 --> 00:50:58,450 Und so dass in diesem Fall der schlechtesten Laufzeit würde n quadriert werden. 1034 00:50:58,450 --> 00:51:00,210 Wenn es in absteigender war um, denken, Sie 1035 00:51:00,210 --> 00:51:02,530 muss eine Swap jedes Mal zu machen. 1036 00:51:02,530 --> 00:51:05,170 >> Was wäre möglicherweise sein, die beste Tasche, Laufzeit? 1037 00:51:05,170 --> 00:51:08,580 Sagen wir einfach, wenn die Liste bereits damit, was wäre die Laufzeit sein? 1038 00:51:08,580 --> 00:51:09,565 >> ZIELGRUPPE: n. 1039 00:51:09,565 --> 00:51:10,690 ANDI PENG: Es ist n, genau. 1040 00:51:10,690 --> 00:51:11,600 Und warum ist es n? 1041 00:51:11,600 --> 00:51:13,850 ZIELGRUPPE: Weil Sie gerade muss auf jedem einmal zu überprüfen. 1042 00:51:13,850 --> 00:51:14,770 ANDI PENG: Genau. 1043 00:51:14,770 --> 00:51:17,150 Also auf die bestmögliche Laufzeit Wenn diese Liste schon 1044 00:51:17,150 --> 00:51:20,270 sorted-- sagen wir 1, 2, 3, 4-- Sie wäre nur durch zu gehen, würden Sie zu überprüfen, 1045 00:51:20,270 --> 00:51:21,720 würden Sie sehen, oh, sie alle pan out. 1046 00:51:21,720 --> 00:51:22,636 Ich hatte nicht zu tauschen. 1047 00:51:22,636 --> 00:51:23,370 Ich bin fertig. 1048 00:51:23,370 --> 00:51:26,500 Also in diesem Fall, es ist nur n oder die Anzahl der Schritte, die Sie gerade 1049 00:51:26,500 --> 00:51:29,870 musste in der ersten Liste zu überprüfen. 1050 00:51:29,870 --> 00:51:33,990 >> Und nachdem wir jetzt treffen Insertion Sort, wo 1051 00:51:33,990 --> 00:51:39,260 Der Algorithmus ist im Wesentlichen zu teilen sie in einer sortierten und unsortierten Teils. 1052 00:51:39,260 --> 00:51:42,810 Und dann einen nach dem anderen, die unsortierten Werte 1053 00:51:42,810 --> 00:51:46,880 in ihren entsprechenden eingeführt Positionen am Anfang der Liste. 1054 00:51:46,880 --> 00:51:52,120 >> So zum Beispiel, haben wir ein Liste von 3, 5, 2, 6, 4 wieder. 1055 00:51:52,120 --> 00:51:54,750 Wir wissen, dass es derzeit unsortiert, weil wir gerade haben 1056 00:51:54,750 --> 00:51:57,030 begann es zu betrachten. 1057 00:51:57,030 --> 00:52:00,610 Wir werfen einen Blick und wir wissen, dass der erste Wert, sortiert, nicht wahr? 1058 00:52:00,610 --> 00:52:04,190 Wenn Sie nur Blick auf eine Reihe von Größe one, wissen Sie, dass es sortiert. 1059 00:52:04,190 --> 00:52:08,230 >> So wissen wir, dass die anderen vier sind unsortiert. 1060 00:52:08,230 --> 00:52:10,980 Wir gehen durch, und wir sehen, dass Wert. 1061 00:52:10,980 --> 00:52:11,730 Lass uns zurück gehen. 1062 00:52:11,730 --> 00:52:13,130 Sehen Sie diesen Wert von 5? 1063 00:52:13,130 --> 00:52:14,110 Wir werfen einen Blick auf sie. 1064 00:52:14,110 --> 00:52:15,204 Wir vergleichen Sie es mit 3. 1065 00:52:15,204 --> 00:52:17,870 Wir wissen, dass er größer als ist 3, so dass wir wissen, dass das ist, sortiert. 1066 00:52:17,870 --> 00:52:22,940 So wissen wir jetzt, dass die ersten beiden sortiert sind und die letzten drei sind es nicht. 1067 00:52:22,940 --> 00:52:24,270 >> Wir werfen einen Blick auf 2. 1068 00:52:24,270 --> 00:52:25,720 Wir überprüfen sie zuerst mit 5. 1069 00:52:25,720 --> 00:52:26,700 Ist es weniger als 5? 1070 00:52:26,700 --> 00:52:27,240 Es ist nicht. 1071 00:52:27,240 --> 00:52:29,510 So haben wir, auch in Zukunft nach unten. 1072 00:52:29,510 --> 00:52:30,940 Dann schauen Sie 2 aus 3. 1073 00:52:30,940 --> 00:52:31,850 Beträgt er weniger als? 1074 00:52:31,850 --> 00:52:32,350 Nein. 1075 00:52:32,350 --> 00:52:35,430 Damit Sie wissen, ein 2 muss eingelegt werden in die vorderen und 3 und 5 1076 00:52:35,430 --> 00:52:38,200 beide müssen herausgedrückt werden. 1077 00:52:38,200 --> 00:52:42,190 Tun Sie dies wieder mit 6 und 4. 1078 00:52:42,190 --> 00:52:48,962 Und wir immer mal im wesentlichen, wo wir gerade prüfen, prüfen, prüfen. 1079 00:52:48,962 --> 00:52:51,170 Und bis es in die richtige Position, wir Art von gerade 1080 00:52:51,170 --> 00:52:54,890 legen Sie sie in die richtige Position, Das ist, wo der Name von ihr kam. 1081 00:52:54,890 --> 00:52:59,830 >> Also das ist nur der Algorithmus, Pseudocode per se, Art, 1082 00:52:59,830 --> 00:53:04,990 wie wir umsetzen würde eine Insertion sort. 1083 00:53:04,990 --> 00:53:05,954 Pseudocode ist hier. 1084 00:53:05,954 --> 00:53:06,620 Es ist alles online. 1085 00:53:06,620 --> 00:53:10,720 Keine Sorge, wenn Sie Jungs sind versuchen, dies zu notieren. 1086 00:53:10,720 --> 00:53:14,500 Also noch einmal, was gleichen question-- würde die besten und schlechtesten Laufzeiten sein 1087 00:53:14,500 --> 00:53:16,120 zum Einsetzen Art? 1088 00:53:16,120 --> 00:53:17,750 Es ist sehr ähnlich wie die letzte Frage. 1089 00:53:17,750 --> 00:53:20,479 Ich werde euch geben, wie, 30 Sekunden, um über diese sowie zu denken. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> OK Will jemand die schlechteste Laufzeit geben Sie mir? 1092 00:53:50,071 --> 00:53:50,570 Ja. 1093 00:53:50,570 --> 00:53:51,490 >> ZIELGRUPPE: n quadriert. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI PENG: Es ist n quadriert. 1095 00:53:52,573 --> 00:53:53,730 Und warum ist es n quadriert? 1096 00:53:53,730 --> 00:53:57,562 >> ZIELGRUPPE: Weil in umgekehrter Reihenfolge, müssen Sie 1097 00:53:57,562 --> 00:54:02,619 durch n mal n gehen, was ist-- 1098 00:54:02,619 --> 00:54:03,660 ANDI PENG: Ja, genau. 1099 00:54:03,660 --> 00:54:06,610 Also dasselbe wie in der Bubble-Sort. 1100 00:54:06,610 --> 00:54:08,720 Ist diese Liste in absteigender Reihenfolge, du bist 1101 00:54:08,720 --> 00:54:11,240 werde zuerst einmal überprüfen zu lassen. 1102 00:54:11,240 --> 00:54:13,470 Und dann mit jedem Mehrwert, du bist 1103 00:54:13,470 --> 00:54:16,390 gehen zu müssen, um es gegen prüfen jeden einzelnen Wert, oder? 1104 00:54:16,390 --> 00:54:20,290 Und so ganz, Sie gehen zu machen sind eine n Pass mal ein anderes n Pass, der 1105 00:54:20,290 --> 00:54:21,750 ist n quadriert. 1106 00:54:21,750 --> 00:54:22,860 Was ist mit dem besten Fall? 1107 00:54:22,860 --> 00:54:24,360 Ja. 1108 00:54:24,360 --> 00:54:28,840 >> ZIELGRUPPE: n minus 1, da der erste ist bereits im Quadrat. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI PENG: Also, in der Nähe. 1110 00:54:30,270 --> 00:54:31,850 Die Antwort ist eigentlich n. 1111 00:54:31,850 --> 00:54:37,189 Denn während die erste ist geordnet ist, kann es nicht actually-- es 1112 00:54:37,189 --> 00:54:38,980 wir einfach Glück gehabt, in dass beispielsweise das 2 1113 00:54:38,980 --> 00:54:40,930 passiert die kleinste Zahl sein. 1114 00:54:40,930 --> 00:54:43,680 Aber das wird nicht immer der Fall sein. 1115 00:54:43,680 --> 00:54:48,040 Wenn 2 bereits in den Anfang, sortiert aber du siehst und es gibt eine 1 hier, 1116 00:54:48,040 --> 00:54:49,144 die 1 wird ihn stoßen. 1117 00:54:49,144 --> 00:54:51,060 Und es geht zu Ende up, die sowieso stieß. 1118 00:54:51,060 --> 00:54:56,250 >> Also im besten Fall, es ist eigentlich gerade dabei, n sein. 1119 00:54:56,250 --> 00:54:59,090 Wenn Sie 1, 2, 3, 4, 5, 6, 7, 8, sind Sie 1120 00:54:59,090 --> 00:55:00,940 gehen zu durchlaufen dass ganze Liste einmal 1121 00:55:00,940 --> 00:55:03,430 um zu überprüfen, ob alles in Ordnung zu sehen. 1122 00:55:03,430 --> 00:55:07,390 Jeder ist klar auf Lauf Zeiten der Auswahl als auch? 1123 00:55:07,390 --> 00:55:09,960 Ich weiß, dass ich durchmache diese wirklich schnell. 1124 00:55:09,960 --> 00:55:13,330 Aber weiß nur, dass, wenn Sie wissen, dass die allgemeine Konzepte, sollten Sie gut sein. 1125 00:55:13,330 --> 00:55:16,070 OK. 1126 00:55:16,070 --> 00:55:19,790 Also werde ich nur geben euch vielleicht, wie, eine Minute, um Ihre Nachbarn zu sprechen 1127 00:55:19,790 --> 00:55:21,890 was sind nur einige der Hauptunterschiede 1128 00:55:21,890 --> 00:55:23,540 zwischen diesen Arten von Arten. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Wir gehen über das bald. 1131 00:56:25,570 --> 00:56:26,444 ZIELGRUPPE: Oh, OK. 1132 00:56:26,444 --> 00:56:27,320 ANDI PENG: Ja. 1133 00:56:27,320 --> 00:56:28,380 OK. 1134 00:56:28,380 --> 00:56:33,420 Cool, lassen Sie uns als Klasse wieder zusammentreten. 1135 00:56:33,420 --> 00:56:34,330 OK. 1136 00:56:34,330 --> 00:56:37,579 Das war also eine Art von offene Frage in dem Sinne, 1137 00:56:37,579 --> 00:56:39,120 , dass es gibt viele Antworten darauf. 1138 00:56:39,120 --> 00:56:40,746 Und wir werden über einige von ihnen kurz. 1139 00:56:40,746 --> 00:56:43,411 Ich wollte Ihnen nur Jungs darüber nachzudenken, was differenziert 1140 00:56:43,411 --> 00:56:44,530 Alle drei Typen von Arten. 1141 00:56:44,530 --> 00:56:47,440 Und ich hörte, auch, eine große question-- was Mergesort tun? 1142 00:56:47,440 --> 00:56:50,110 Gute Frage, denn das ist, was wir abdecken nächsten. 1143 00:56:50,110 --> 00:56:52,850 >> So verschmelzen Art ist die eine Sorte, die Funktionen 1144 00:56:52,850 --> 00:56:56,100 sehr verschieden von den anderen Arten. 1145 00:56:56,100 --> 00:56:58,180 Wie euch see-- können hat David zu tun, dass die Demo- 1146 00:56:58,180 --> 00:57:01,130 wo er all die coolen hatten Geräusche zu sehen, wie verschmelzen 1147 00:57:01,130 --> 00:57:04,010 Art lief, wie, stufenlos schneller als die beiden anderen Arten? 1148 00:57:04,010 --> 00:57:04,510 OK. 1149 00:57:04,510 --> 00:57:07,580 Also das ist, weil merge sort implementiert, dass die Kluft 1150 00:57:07,580 --> 00:57:11,020 und erobern Konzept, dass wir sprachen über eine Menge in der Vorlesung. 1151 00:57:11,020 --> 00:57:14,550 In diesem Sinne, die wir gerne arbeiten intelligenter, nicht härter, wenn Sie teilen 1152 00:57:14,550 --> 00:57:18,120 und erobern Probleme, und brechen sie nach unten, und dann legte sie zusammen, 1153 00:57:18,120 --> 00:57:19,930 gute Dinge immer passieren. 1154 00:57:19,930 --> 00:57:21,960 >> Also die Art und Weise, verschmelzen sort Wesentlichen funktioniert 1155 00:57:21,960 --> 00:57:24,660 ist, dass es teilt ein unsortierte Array in zwei Hälften. 1156 00:57:24,660 --> 00:57:26,500 Und dann es hat zwei Hälften des Arrays. 1157 00:57:26,500 --> 00:57:28,220 Und es ist nur sortiert diese zwei Hälften. 1158 00:57:28,220 --> 00:57:31,750 Es hält nur Teilung in zwei Hälften, in Hälfte, in der Hälfte, bis alles sortiert 1159 00:57:31,750 --> 00:57:33,680 und dann rekursiv bringt sie alle zusammen. 1160 00:57:33,680 --> 00:57:36,550 >> Also das ist wirklich abstrakt. 1161 00:57:36,550 --> 00:57:38,750 Das ist also nur ein bisschen Pseudocode. 1162 00:57:38,750 --> 00:57:41,040 Ist das sinnvoll in die Art, wie es läuft? 1163 00:57:41,040 --> 00:57:43,870 Also lasst uns einfach sagen, dass Sie eine haben, Array von n Elementen, nicht wahr? 1164 00:57:43,870 --> 00:57:45,450 Wenn n kleiner als 2 ist, können Sie zurückkommen. 1165 00:57:45,450 --> 00:57:49,040 Weil Sie wissen, dass, wenn es nur einen müssen sie sortiert werden. 1166 00:57:49,040 --> 00:57:52,600 Else, die linke Hälfte sortieren Sie, und dann können Sie die rechte Hälfte zu sortieren, 1167 00:57:52,600 --> 00:57:54,140 und dann können Sie verschmelzen. 1168 00:57:54,140 --> 00:57:56,979 >> Während also das sieht einfach, in der Realität, daran zu denken ist 1169 00:57:56,979 --> 00:58:00,270 etwas schwierig. Weil Sie wie sie sind, gut, das ist irgendwie läuft auf sich. 1170 00:58:00,270 --> 00:58:00,769 Recht? 1171 00:58:00,769 --> 00:58:02,430 Es ist auf sich selbst läuft. 1172 00:58:02,430 --> 00:58:05,479 In diesem Sinne, berührte David auf Rekursion in der Klasse. 1173 00:58:05,479 --> 00:58:07,270 Und das ist ein Konzept, wir über mehr reden. 1174 00:58:07,270 --> 00:58:11,430 Ist es, dass diese sich diese beiden Linien hier ist eigentlich nur das Programm 1175 00:58:11,430 --> 00:58:13,860 erzählen sie sich selbst ausführen mit unterschiedlichen Eingangs. 1176 00:58:13,860 --> 00:58:17,230 Also anstatt mit sich führen die Gesamtheit von n Elementen, 1177 00:58:17,230 --> 00:58:20,530 Sie können es unten in der Pause linke Hälfte und die rechte Hälfte 1178 00:58:20,530 --> 00:58:22,680 und führen Sie es erneut. 1179 00:58:22,680 --> 00:58:26,050 >> Und dann werden wir auf sie visuell zu suchen, denn ich bin ein visueller Lerner. 1180 00:58:26,050 --> 00:58:27,270 Es funktioniert besser für mich. 1181 00:58:27,270 --> 00:58:29,890 Also werden wir bei einer visuellen Beispiel hier betrachten. 1182 00:58:29,890 --> 00:58:36,237 >> Sagen wir, wir haben eine Reihe, sechs Elemente 3, 5, 2, 6, 4, 1, nicht sortiert. 1183 00:58:36,237 --> 00:58:37,820 Na gut, es gibt eine Menge auf dieser Seite. 1184 00:58:37,820 --> 00:58:43,179 Also, wenn Sie Jungs können bei der Suche zunächst hier, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 Sie können sie in zwei Hälften geteilt. 1186 00:58:44,220 --> 00:58:45,976 Sie haben 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Sie wissen, dass diese aren't-- Sie weiß nicht, ob sie sortiert oder nicht, 1188 00:58:48,850 --> 00:58:52,517 so dass Sie zu halten und zwar getrennt nach, in der Hälfte, in der Mitte, in der Mitte, bis schließlich, 1189 00:58:52,517 --> 00:58:53,600 Sie haben nur ein Element. 1190 00:58:53,600 --> 00:58:56,790 Und ein Element immer sortiert, nicht wahr? 1191 00:58:56,790 --> 00:59:01,560 >> Also wissen wir, daß 3, 5, 2, 4, 6, 1, mit sich selbst, sortiert werden. 1192 00:59:01,560 --> 00:59:05,870 Und jetzt können wir sie wieder zusammen zu setzen. 1193 00:59:05,870 --> 00:59:07,510 So kennen wir die 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Wir setzen diese zusammen. 1195 00:59:08,510 --> 00:59:09,617 Wir wissen, das ist sortiert. 1196 00:59:09,617 --> 00:59:10,450 Die 2 ist immer noch da. 1197 00:59:10,450 --> 00:59:11,830 Wir können die 4 und die 6 zusammen. 1198 00:59:11,830 --> 00:59:13,996 Wir wissen, dass das ist, sortiert, so stellen wir fest, dass zusammen. 1199 00:59:13,996 --> 00:59:14,940 Und die 1 ist dort. 1200 00:59:14,940 --> 00:59:18,720 >> Und dann muß man nur betrachten diese zwei Hälften hier richtig. 1201 00:59:18,720 --> 00:59:21,300 Sie haben die 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Sie können einfach vergleichen die Anfang von allem. 1203 00:59:23,465 --> 00:59:26,340 Weil Sie wissen, dass dies ist, sortiert und Sie wissen, dass das ist, sortiert. 1204 00:59:26,340 --> 00:59:29,360 Also Sie haben nicht einmal zu haben, Vergleichen Sie die 5, die Sie gerade zu vergleichen, die 3. 1205 00:59:29,360 --> 00:59:32,070 Und die 2 ist kleiner als 3, so Sie wissen, 2 müssen am Ende zu gehen. 1206 00:59:32,070 --> 00:59:33,120 >> Gleiche drüben. 1207 00:59:33,120 --> 00:59:34,740 Die 1 muss hier. 1208 00:59:34,740 --> 00:59:37,330 Und dann, wenn du gehst zu setzen diese beiden Werte zusammen, 1209 00:59:37,330 --> 00:59:39,950 Sie wissen, dass diese sortiert und Sie wissen, dass das ist, sortiert. 1210 00:59:39,950 --> 00:59:43,240 So dann wird die 1 und die 2 die 1 kleiner als 2 ist. 1211 00:59:43,240 --> 00:59:45,570 Das sagt Ihnen, dass die 1 sollte am Ende dieser gehen 1212 00:59:45,570 --> 00:59:47,480 ohne auch nur einen Blick auf 3 oder 5. 1213 00:59:47,480 --> 00:59:50,100 Und dann die 4, können Sie einfach zu überprüfen, geht es direkt hier. 1214 00:59:50,100 --> 00:59:51,480 Sie müssen nicht an der 5 aussehen. 1215 00:59:51,480 --> 00:59:52,570 Das Gleiche gilt für den 6. 1216 00:59:52,570 --> 00:59:55,860 Sie wissen, dass es gerade die 6-- muss nicht geprüft werden. 1217 00:59:55,860 --> 00:59:57,870 >> Und so auf diese Weise, bist du nur sparen Sie sich 1218 00:59:57,870 --> 00:59:59,526 eine Menge von Schritten, wenn Sie den Vergleich. 1219 00:59:59,526 --> 01:00:02,150 Sie müssen nicht um jeden vergleichen Element gegen andere Elemente. 1220 01:00:02,150 --> 01:00:05,230 Sie vergleichen, nur gegen die, die Sie benötigen, um es gegen zu vergleichen. 1221 01:00:05,230 --> 01:00:06,870 Also das ist Art von ein abstraktes Konzept. 1222 01:00:06,870 --> 01:00:10,540 Keine Sorge, wenn es nicht ganz Schlagen Sie mit der rechten leer. 1223 01:00:10,540 --> 01:00:14,740 Aber im allgemeinen ist dies wie eine Zusammenführung Art funktioniert. 1224 01:00:14,740 --> 01:00:17,750 Fragen, kurze Fragen, bevor ich weiter? 1225 01:00:17,750 --> 01:00:18,550 Ja. 1226 01:00:18,550 --> 01:00:22,230 >> Publikum: So sagten Sie, dass Sie die 1 und dann der 4 und der 6 1227 01:00:22,230 --> 01:00:23,860 und legte sie in. 1228 01:00:23,860 --> 01:00:26,800 So sind those-- nicht nicht Sie auf der Suche nach ihnen 1229 01:00:26,800 --> 01:00:28,544 als separate Elemente, nicht als Ganzes? 1230 01:00:28,544 --> 01:00:29,210 ANDI PENG: Ja. 1231 01:00:29,210 --> 01:00:32,020 Also, was passiert, ist, dass man im Grunde 1232 01:00:32,020 --> 01:00:33,650 schaffen ein ganz neues Array. 1233 01:00:33,650 --> 01:00:36,690 Damit Sie wissen, dass hier, ich habe zwei Arrays der Größe 3, oder? 1234 01:00:36,690 --> 01:00:39,600 So dass Sie wissen, dass meine sortierten Array muss sechs Elemente haben. 1235 01:00:39,600 --> 01:00:42,270 So dass Sie nur erstellen neue Größe des Speichers. 1236 01:00:42,270 --> 01:00:44,270 So dass Sie eine Art, wie du verschwenderisch des Gedächtnisses, 1237 01:00:44,270 --> 01:00:46,186 aber das spielt keine Rolle, weil es so klein ist. 1238 01:00:46,186 --> 01:00:48,590 So dass Sie an der 1 sehen und man sich das 2. 1239 01:00:48,590 --> 01:00:50,770 Und Sie wissen, dass das 1 kleiner als 2. 1240 01:00:50,770 --> 01:00:53,840 So dass Sie wissen, dass 1 sollte gehen in der Anfang von all denen. 1241 01:00:53,840 --> 01:00:55,850 >> Sie brauchen noch nicht einmal zu Blick auf die 3 und der 5. 1242 01:00:55,850 --> 01:00:57,400 Damit Sie wissen, 1 geht es. 1243 01:00:57,400 --> 01:00:59,300 Dann im Grunde hacken Sie aus dem 1. 1244 01:00:59,300 --> 01:01:00,370 Es ist, wie, tot zu uns. 1245 01:01:00,370 --> 01:01:03,690 Dann müssen wir nur noch 2, 3, 5, und 4 und 6. 1246 01:01:03,690 --> 01:01:06,270 Und dann wissen Sie, dass Sie Vergleichen Sie die 4 und die 2, 1247 01:01:06,270 --> 01:01:07,560 oh, das 2 sollte in dorthin zu gehen. 1248 01:01:07,560 --> 01:01:09,685 So können Sie die 2 nach unten plumpsen, hacken Sie es ab. 1249 01:01:09,685 --> 01:01:12,060 Also müssen Sie nur noch die 3 und 5 in der 4 und der 6. 1250 01:01:12,060 --> 01:01:14,650 Und Sie halten gerade hacken Sie sie ab , bis Sie sie in das Array. 1251 01:01:14,650 --> 01:01:17,110 >> Publikum: So können Sie einfach immer sind Vergleichen Sie die [unverständlich]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI PENG: Genau. 1253 01:01:17,710 --> 01:01:19,590 In diesem Sinne, du bist nur den Vergleich im Wesentlichen wissen, 1254 01:01:19,590 --> 01:01:21,240 eine Zahl gegen die andere Nummer. 1255 01:01:21,240 --> 01:01:22,990 Und weil Sie wissen, dass es, Sie, sortiert 1256 01:01:22,990 --> 01:01:24,350 haben nicht zu durchschauen alle Zahlen. 1257 01:01:24,350 --> 01:01:25,870 Sie müssen nur bei der ersten aussehen. 1258 01:01:25,870 --> 01:01:27,582 Und dann müssen Sie nur plop können sie nieder, weil Sie wissen, 1259 01:01:27,582 --> 01:01:29,640 sie gehören, in denen sie angehören müssen. 1260 01:01:29,640 --> 01:01:31,030 Ja. 1261 01:01:31,030 --> 01:01:32,920 Gute Frage. 1262 01:01:32,920 --> 01:01:35,290 >> Und dann, wenn einer von euch sind ein bisschen ehrgeizig, 1263 01:01:35,290 --> 01:01:38,660 fühlen sich frei, um diesen Code zu suchen. 1264 01:01:38,660 --> 01:01:40,680 Dies tatsächlich die physikalischen Implementierung 1265 01:01:40,680 --> 01:01:42,150 der, wie wir merge sort schreiben. 1266 01:01:42,150 --> 01:01:44,070 Und Sie sehen, es ist sehr kurz. 1267 01:01:44,070 --> 01:01:46,310 Aber die Ideen hinter sie sind ziemlich komplex. 1268 01:01:46,310 --> 01:01:50,865 Also, wenn Sie das Gefühl, Zeichnung this out in Ihre Hausaufgaben heute Abend, zögern Sie nicht. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> OK. 1271 01:01:54,740 --> 01:01:58,070 Also ging David auch über diese in der Vorlesung. 1272 01:01:58,070 --> 01:02:00,660 Was sind die besten Fall Laufzeiten, Worst-Case-Laufzeiten, 1273 01:02:00,660 --> 01:02:05,680 und die erwarteten Laufzeiten der merge sort? 1274 01:02:05,680 --> 01:02:07,260 Ein paar Sekunden, um zu denken. 1275 01:02:07,260 --> 01:02:11,198 Das ist ziemlich hart, aber Art intuitive, wenn Sie darüber nachdenken. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Gut. 1278 01:02:23,054 --> 01:02:25,269 >> ZIELGRUPPE: Ist der schlimmsten Fall n log n? 1279 01:02:25,269 --> 01:02:26,060 ANDI PENG: Genau. 1280 01:02:26,060 --> 01:02:29,380 Und warum ist es n log n. 1281 01:02:29,380 --> 01:02:32,230 >> Publikum: Ist es nicht, weil es wird exponentiell schneller, 1282 01:02:32,230 --> 01:02:35,390 so ist es wie eine Funktion, dass statt nur einfach nur n 1283 01:02:35,390 --> 01:02:37,529 Quadrat, oder was? 1284 01:02:37,529 --> 01:02:38,320 ANDI PENG: Genau. 1285 01:02:38,320 --> 01:02:40,750 So dass der Grund, warum die Laufzeit auf diese n log 1286 01:02:40,750 --> 01:02:44,310 n because-- was bist du dabei in alle diese Schritte? 1287 01:02:44,310 --> 01:02:46,190 Du bist nur hacken es in der Mitte, oder? 1288 01:02:46,190 --> 01:02:48,750 Und so, wenn wir tun, die melden Sie sich, alles, was er tut 1289 01:02:48,750 --> 01:02:53,150 spaltet ein Problem in der Hälfte, in der Mitte, in der Mitte, in mehr Hälften. 1290 01:02:53,150 --> 01:02:56,430 Und in diesem Sinne, können Sie Art das lineare Modell des zu beseitigen 1291 01:02:56,430 --> 01:02:57,510 dass wir habe mit. 1292 01:02:57,510 --> 01:03:00,254 Denn wenn Sie hacken Dinge in die Hälfte, es ist ein Protokoll. 1293 01:03:00,254 --> 01:03:02,420 Das ist nur die mathematische Weg es darstellt. 1294 01:03:02,420 --> 01:03:06,310 >> Und dann endlich, am Ende, du bist nur machen einen letzten Durchgang durch 1295 01:03:06,310 --> 01:03:07,930 , alle von ihnen in Ordnung zu bringen, nicht wahr? 1296 01:03:07,930 --> 01:03:10,330 Und so, wenn Sie nur noch überprüfen Sie eine Sache, das ist n. 1297 01:03:10,330 --> 01:03:13,420 Und damit Sie Art sind Multiplikation der beiden zusammen. 1298 01:03:13,420 --> 01:03:17,660 So ist es wie du, dass abschließende habe Check für n hier unten mit einem log n 1299 01:03:17,660 --> 01:03:18,390 hier oben. 1300 01:03:18,390 --> 01:03:21,060 Und wenn Sie multiplizieren sie, das ist n log n. 1301 01:03:21,060 --> 01:03:26,100 >> Und so die besten und schlechtesten Fall Gehäuse und erwartet, dass alle n log n. 1302 01:03:26,100 --> 01:03:27,943 Es ist auch wie eine andere Art. 1303 01:03:27,943 --> 01:03:30,090 Es ist wie Auswahl sort in dem Sinne, dass es 1304 01:03:30,090 --> 01:03:32,131 Egal, was Ihr Liste ist, ist es nur geht 1305 01:03:32,131 --> 01:03:34,801 um die gleiche Sache jedes Mal zu tun. 1306 01:03:34,801 --> 01:03:35,300 OK. 1307 01:03:35,300 --> 01:03:39,950 So wie Sie sehen können, Jungs, auch wenn die Sorten, die wir through-- n gegangen 1308 01:03:39,950 --> 01:03:41,660 quadriert, dann ist es nicht sehr effizient. 1309 01:03:41,660 --> 01:03:47,060 Und selbst diese n log n nicht die effizienteste. 1310 01:03:47,060 --> 01:03:49,720 Wenn Sie Jungs sind neugierig, es ist eine Art Mechanismen 1311 01:03:49,720 --> 01:03:54,310 , die so effizient, dass sie sind, fast im wesentlichen flach in der Laufzeit. 1312 01:03:54,310 --> 01:03:55,420 >> Sie haben etwas log n ist bekam. 1313 01:03:55,420 --> 01:03:58,190 Sie haben etwas log log n ist bekam. 1314 01:03:58,190 --> 01:04:00,330 Wir haben nicht auf sie zu berühren in dieser Klasse jetzt. 1315 01:04:00,330 --> 01:04:02,663 Aber wenn Sie Jungs sind neugierig, fühlen sich frei, Google, was ist 1316 01:04:02,663 --> 01:04:04,392 die effizientesten Sortiermechanismen. 1317 01:04:04,392 --> 01:04:06,350 Ich weiß es nicht, es gibt einige wirklich lustig sind, 1318 01:04:06,350 --> 01:04:09,860 like-- es gibt einige wirklich funny diejenigen, die Menschen zu machen. 1319 01:04:09,860 --> 01:04:12,210 Und Sie fragen sich, wie sie jemals daran gedacht. 1320 01:04:12,210 --> 01:04:15,730 Also Google, wenn Sie einige Ersatz haben Zeit auf, was sind einige lustige Möglichkeiten 1321 01:04:15,730 --> 01:04:17,730 dass people-- sowie effiziente ways-- Menschen 1322 01:04:17,730 --> 01:04:20,371 konnten Arten umzusetzen. 1323 01:04:20,371 --> 01:04:20,870 OK. 1324 01:04:20,870 --> 01:04:22,880 Und hier ist nur eine handliche kleine Karte. 1325 01:04:22,880 --> 01:04:26,850 Ich weiß, dass Sie alle, die vor diesem Quiz 0, wird in Ihrem Zimmer werden wahrscheinlich versuchen 1326 01:04:26,850 --> 01:04:27,960 zu merken, dass. 1327 01:04:27,960 --> 01:04:30,940 Also das ist schön dort für euch. 1328 01:04:30,940 --> 01:04:37,120 Nur die Logik, die made-- vergessen Sie nicht, warum diese Zahlen wurden auftritt. 1329 01:04:37,120 --> 01:04:39,870 Wenn du immer verloren, so stellen sicher, dass Sie wissen, was die Sorten sind. 1330 01:04:39,870 --> 01:04:40,820 Und Sie können durchlaufen ihnen im Kopf 1331 01:04:40,820 --> 01:04:42,903 um herauszufinden, warum diejenigen, Antworten sind die Antworten. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Gut. 1334 01:04:47,600 --> 01:04:49,680 So werden wir bewegen auf schließlich zur Suche. 1335 01:04:49,680 --> 01:04:51,638 Weil, wie die von Ihnen, die das pset gelesen haben, 1336 01:04:51,638 --> 01:04:55,175 Suche ist auch Teil diese Woche Problems setzt. 1337 01:04:55,175 --> 01:04:57,300 Sie werden aufgefordert, zu implementieren zwei Arten von Suchanfragen. 1338 01:04:57,300 --> 01:05:00,070 One ist eine lineare Suche und eine ist eine binäre Suche. 1339 01:05:00,070 --> 01:05:01,760 >> So ist die lineare Suche ist ziemlich einfach. 1340 01:05:01,760 --> 01:05:04,070 Sie wollen einfach nur, um zu suchen Element einer Liste zu sehen, wenn Sie es. 1341 01:05:04,070 --> 01:05:05,444 Sie müssen nur durchlaufen. 1342 01:05:05,444 --> 01:05:08,170 Und wenn es gleich etwas, können Sie einfach zurück, nicht wahr? 1343 01:05:08,170 --> 01:05:10,890 Aber die, die wir am meisten sind interessiert sich für Gespräche über 1344 01:05:10,890 --> 01:05:14,550 ist binäre Suche, rechts, die der ist Teile und herrsche Mechanismus, 1345 01:05:14,550 --> 01:05:18,190 David wurde demonstriert in der Vorlesung. 1346 01:05:18,190 --> 01:05:20,810 >> Denken Sie daran, das Telefonbuch Beispiel dass er immer die Erziehung, 1347 01:05:20,810 --> 01:05:23,960 die eine, die er Art kämpfte ein bisschen auf das vergangene Jahr, 1348 01:05:23,960 --> 01:05:27,530 wo Sie das Problem zu halbieren, in der Mitte, in der Mitte, wieder und wieder, 1349 01:05:27,530 --> 01:05:30,730 , bis Sie finden, was Sie suchen? 1350 01:05:30,730 --> 01:05:33,727 Und sie haben das Laufzeit das auch. 1351 01:05:33,727 --> 01:05:35,810 Und Sie können sehen, es ist deutlich effizienter 1352 01:05:35,810 --> 01:05:39,080 als jede andere Art der Suche. 1353 01:05:39,080 --> 01:05:41,880 >> So ist die Art und Weise, die wir zu gehen Implementierung eines binären Such 1354 01:05:41,880 --> 01:05:46,510 ist, wenn wir ein Array, Index 0 bis 6, sieben Elemente, 1355 01:05:46,510 --> 01:05:49,790 können wir in der Mitte suchen, right-- sorry, wenn unsere Frage first-- 1356 01:05:49,790 --> 01:05:53,840 wenn wir die Frage, fragen wollen, tut die Anordnung enthält das Element 7, 1357 01:05:53,840 --> 01:05:56,840 Offensichtlich wobei Menschen, und mit so ein kleines Array, ist es einfach für uns 1358 01:05:56,840 --> 01:05:58,210 ja zu sagen. 1359 01:05:58,210 --> 01:06:05,750 Aber die Möglichkeit, eine binäre Umsetzung Such wäre, in der Mitte zu suchen. 1360 01:06:05,750 --> 01:06:08,020 >> Wir wissen, dass Index 3 der Mitte, weil wir 1361 01:06:08,020 --> 01:06:09,270 weiß, es gibt sieben Elemente. 1362 01:06:09,270 --> 01:06:10,670 Welche 7 geteilt durch 2? 1363 01:06:10,670 --> 01:06:12,850 Sie können abhacken, dass zusätzliche 1. 1364 01:06:12,850 --> 01:06:14,850 Sie haben 3 in der Mitte stand. 1365 01:06:14,850 --> 01:06:17,590 So ist Array von 3 gleich 7? 1366 01:06:17,590 --> 01:06:18,900 Es ist nicht richtig? 1367 01:06:18,900 --> 01:06:21,050 Aber wir können ein paar Kontrollen zu tun. 1368 01:06:21,050 --> 01:06:25,380 Ist Array von 3 weniger als 7 oder ist Array von 3 größer als 7? 1369 01:06:25,380 --> 01:06:27,240 >> Und wir wissen, dass es weniger als 7. 1370 01:06:27,240 --> 01:06:30,259 So wissen wir, dass, oh, muss es nicht in der linken Hälfte. 1371 01:06:30,259 --> 01:06:32,300 Wir wissen, dass es sein muss, in der rechten Hälfte, nicht wahr? 1372 01:06:32,300 --> 01:06:34,662 So können wir nur abhacken Hälfte des Arrays. 1373 01:06:34,662 --> 01:06:36,370 Wir haben nicht einmal zu Schauen Sie sich es nicht mehr. 1374 01:06:36,370 --> 01:06:38,711 Denn wir wissen: die Hälfte unserer problem-- 1375 01:06:38,711 --> 01:06:41,210 Wir wissen, daß die Antwort in die rechte Hälfte der unser Problem. 1376 01:06:41,210 --> 01:06:42,580 So dass wir nur sehen, dass jetzt. 1377 01:06:42,580 --> 01:06:44,860 >> So, jetzt schauen wir auf die Mitte, was übrig bleibt. 1378 01:06:44,860 --> 01:06:46,880 Das Index-5. 1379 01:06:46,880 --> 01:06:50,200 Wir tun die gleiche Prüfung erneut und wir sehen, dass es kleiner ist. 1380 01:06:50,200 --> 01:06:52,050 Also schauen wir auf der linken Seite, dass. 1381 01:06:52,050 --> 01:06:53,430 Und dann sehen wir, dass der Check. 1382 01:06:53,430 --> 01:06:57,600 Ist der Array-Wert an Index 4 gleich 7? 1383 01:06:57,600 --> 01:06:58,260 Es ist. 1384 01:06:58,260 --> 01:07:03,580 So können wir true zurück, weil fanden wir den Wert in unserer Liste. 1385 01:07:03,580 --> 01:07:06,738 Funktioniert, wie ich ging durch das Sinn für jedermann? 1386 01:07:06,738 --> 01:07:08,760 OK. 1387 01:07:08,760 --> 01:07:11,670 Ich werde euch vielleicht geben, wie, drei, vier Minuten, um herauszufinden, 1388 01:07:11,670 --> 01:07:13,270 wie man dies in Pseudocode. 1389 01:07:13,270 --> 01:07:18,070 >> So vorstellen, ich Sie gebeten, ein Schreiben Funktion namens search (), die zurückgegeben 1390 01:07:18,070 --> 01:07:20,640 ein Wert, ein boolescher Wert, das war wahr oder false-- wie, 1391 01:07:20,640 --> 01:07:22,970 wahr, wenn Sie fanden die Wert false, wenn Sie nicht. 1392 01:07:22,970 --> 01:07:25,230 Und dann waren im Wert übergeben Sie 1393 01:07:25,230 --> 01:07:28,410 suchten in Werte, die ist die array-- oh, ich auf jeden Fall setzen 1394 01:07:28,410 --> 01:07:29,410 , dass an der falschen Stelle. 1395 01:07:29,410 --> 01:07:29,580 OK. 1396 01:07:29,580 --> 01:07:31,829 Wie auch immer, das haben sollte bereits in der richtigen Werte. 1397 01:07:31,829 --> 01:07:36,280 Und dann int n die Zahl der Elemente in diesem Array. 1398 01:07:36,280 --> 01:07:39,430 Wie würden Sie versuchen zu gehen dieses Problem in Pseudo? 1399 01:07:39,430 --> 01:07:41,630 Ich werde euch geben, wie drei Minuten, um das zu tun. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Nein, ich glaube, es gibt only-- ja, es gibt ein Recht hier oben. 1402 01:08:02,595 --> 01:08:03,261 Publikum: Kann ich? 1403 01:08:03,261 --> 01:08:04,388 ANDI PENG: Ja, ich habe Sie. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 Ist das Arbeits? 1406 01:08:11,050 --> 01:08:12,290 OK COOL. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> OK. 1409 01:10:44,720 --> 01:10:47,630 Alle richtigen Jungs, wir sind gehen, um es zu zügeln. 1410 01:10:47,630 --> 01:10:49,730 OK. 1411 01:10:49,730 --> 01:10:54,020 So übernehmen wir bekamen dieses schöne habe wenig Array mit n-Werte drin. 1412 01:10:54,020 --> 01:10:55,170 Ich habe nicht ziehen die Linien. 1413 01:10:55,170 --> 01:10:58,649 Aber wie würden wir zu gehen versuchen, dies zu schreiben? 1414 01:10:58,649 --> 01:11:00,440 Will jemand geben Sie mir die erste Zeile? 1415 01:11:00,440 --> 01:11:02,814 Wenn Sie mir die geben wollen erste Zeile dieser Pseudocode. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> ZIELGRUPPE: [unverständlich] 1418 01:11:08,430 --> 01:11:10,138 ZIELGRUPPE: Sie würden wollen, iterieren through-- 1419 01:11:10,138 --> 01:11:11,094 ZIELGRUPPE: Just another for-Schleife? 1420 01:11:11,094 --> 01:11:11,760 AUDIENCE --for. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI PENG: Also das hier ist ein bisschen schwierig. 1423 01:11:17,780 --> 01:11:23,130 Denken Sie about-- Sie wollen Laufen diese Schleife zu halten 1424 01:11:23,130 --> 01:11:27,950 immer und immer wieder, bis wann? 1425 01:11:27,950 --> 01:11:30,819 >> Publikum: Bis zum [unverständlich] Wert gleich diesem Wert. 1426 01:11:30,819 --> 01:11:31,610 ANDI PENG: Genau. 1427 01:11:31,610 --> 01:11:33,900 So dass Sie eigentlich nur write-- können können wir sogar zu vereinfachen es. 1428 01:11:33,900 --> 01:11:35,630 Wir können einfach eine while-Schleife, oder? 1429 01:11:35,630 --> 01:11:39,380 So müssen Sie nur können loop-- wir wissen, dass es eine Weile. 1430 01:11:39,380 --> 01:11:42,850 Aber für jetzt, ich werde durch das, was - um "Schleife" zu sagen? 1431 01:11:42,850 --> 01:11:46,640 Loop until-- was unsere Endbedingung? 1432 01:11:46,640 --> 01:11:47,510 Ich glaube, ich hörte es. 1433 01:11:47,510 --> 01:11:48,530 Ich hörte jemanden sagen. 1434 01:11:48,530 --> 01:11:51,255 >> ZIELGRUPPE: Werte gleich Mitte. 1435 01:11:51,255 --> 01:11:52,255 ANDI PENG: Sag es noch einmal. 1436 01:11:52,255 --> 01:11:54,470 ZIELGRUPPE: Oder, bis die Wert, den Sie auf der Suche sind 1437 01:11:54,470 --> 01:11:58,470 für die ist gleich dem mittleren Wert. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI PENG: Was wäre, wenn es nicht da drin? 1439 01:12:00,280 --> 01:12:03,113 Was, wenn der Wert, den Sie auf der Suche sind für die ist nicht wirklich in diesem Array? 1440 01:12:03,113 --> 01:12:05,890 Publikum: Sie kehren 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI PENG: Aber was wollen wir Schleife, bis, wenn wir einen Zustand haben? 1442 01:12:08,850 --> 01:12:09,350 Ja. 1443 01:12:09,350 --> 01:12:11,239 >> ZIELGRUPPE: Bis es gibt nur einen Wert? 1444 01:12:11,239 --> 01:12:13,530 ANDI PENG: Sie können Loop- until-- so dass Sie wissen, dass Sie 1445 01:12:13,530 --> 01:12:15,714 gehen, um einen Maximalwert haben, oder? 1446 01:12:15,714 --> 01:12:18,130 Und Sie wissen, dass Sie gehen einen Minimalwert, Recht haben? 1447 01:12:18,130 --> 01:12:20,379 Denn auch, das ist etwas, Ich habe vergessen, vor sagen, 1448 01:12:20,379 --> 01:12:22,640 dass etwas, das ist kritisch über binäre Suche 1449 01:12:22,640 --> 01:12:24,182 ist, dass das Array bereits sortiert ist. 1450 01:12:24,182 --> 01:12:26,973 Da gibt es keine Möglichkeit, dies zu tun diese, wenn sie sind nur Zufallswerte. 1451 01:12:26,973 --> 01:12:29,190 Sie wissen nicht, wenn man es größer als die andere, nicht wahr? 1452 01:12:29,190 --> 01:12:32,720 >> So dass Sie wissen, dass Ihre max und Ihre mins sind hier, nicht wahr? 1453 01:12:32,720 --> 01:12:35,590 Wenn Sie vorhaben, werden eingestellt sind Ihre max in Ihrem Minuten und den mid-- 1454 01:12:35,590 --> 01:12:38,470 lassen Sie uns einfach davon ausgehen, Ihre Mitte der Wert richtig ist hier-- 1455 01:12:38,470 --> 01:12:43,910 du gehst zu Grunde Schleife, bis Sie Ihre Mindest ist 1456 01:12:43,910 --> 01:12:47,510 etwa die gleiche wie Ihre max, rechts oder wenn Ihr max ist nicht das gleiche wie Ihr min. 1457 01:12:47,510 --> 01:12:48,040 Recht? 1458 01:12:48,040 --> 01:12:51,340 Denn wenn das passiert, wissen Sie, dass Sie haben schließlich traf den gleichen Wert. 1459 01:12:51,340 --> 01:12:59,135 So möchten Sie Schleife, bis Ihre min ist kleiner oder gleich zu-- oops, 1460 01:12:59,135 --> 01:13:01,510 nicht weniger als oder gleich, umge herum-- max. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Hat das Sinn? 1463 01:13:16,160 --> 01:13:18,810 Ich nahm ein paar Versuche, dieses Recht zu bekommen. 1464 01:13:18,810 --> 01:13:21,869 Aber Schleife, bis Sie Ihr Max-Wert ist im Wesentlichen fast weniger 1465 01:13:21,869 --> 01:13:23,410 oder gleich Ihre minimale, nicht wahr? 1466 01:13:23,410 --> 01:13:25,201 Das ist, wenn Sie wissen, dass Sie noch angenähert. 1467 01:13:25,201 --> 01:13:29,290 Publikum: Wann möchten Sie Ihr Maximal Wert kleiner als der Mindest sein? 1468 01:13:29,290 --> 01:13:31,040 ANDI PENG: Wenn Sie zu halten passt ihn, die 1469 01:13:31,040 --> 01:13:32,380 ist das, was wir gehen zu tun, werden in diesem. 1470 01:13:32,380 --> 01:13:33,460 Ist das sinnvoll? 1471 01:13:33,460 --> 01:13:35,750 Mindest- und max sind nur ganzen Zahlen, die wir sind wahrscheinlich 1472 01:13:35,750 --> 01:13:39,260 gehen zu wollen, zu erstellen, um zu halten verfolgen, wo wir suchen. 1473 01:13:39,260 --> 01:13:41,790 Da der Array existiert unabhängig davon, was wir tun. 1474 01:13:41,790 --> 01:13:45,030 Wie sind wir nicht tatsächlich physisch Abhacken des Arrays, oder? 1475 01:13:45,030 --> 01:13:47,261 Wir stehen noch am Stell wo wir suchen. 1476 01:13:47,261 --> 01:13:48,136 Ist das sinnvoll? 1477 01:13:48,136 --> 01:13:48,472 >> ZIELGRUPPE: Ja. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI PENG: OK. 1479 01:13:49,110 --> 01:13:57,090 Also, wenn das ist die Voraussetzung für unseren Schleife, was wollen wir innerhalb dieser Schleife? 1480 01:13:57,090 --> 01:13:58,700 Was sollen wir sein wollen, zu tun? 1481 01:13:58,700 --> 01:14:02,390 So jetzt, was wir haben a max und min, rechts, 1482 01:14:02,390 --> 01:14:04,962 wohl hier oben irgendwo erstellt. 1483 01:14:04,962 --> 01:14:07,170 Wir werden wahrscheinlich wollen um eine Mitte, rechts finden? 1484 01:14:07,170 --> 01:14:08,450 Wie werden wir zu sein in der Lage, in der Mitte zu finden? 1485 01:14:08,450 --> 01:14:09,491 Was ist der mathematical-- 1486 01:14:09,491 --> 01:14:11,079 ZIELGRUPPE: Max und min dividiert durch 2. 1487 01:14:11,079 --> 01:14:11,870 ANDI PENG: Genau. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Ist das sinnvoll? 1490 01:14:21,620 --> 01:14:25,780 Und denkt ihr, warum wir hat nicht nur use--, warum wir dies taten 1491 01:14:25,780 --> 01:14:27,850 anstatt das zu tun gerade n geteilt durch 2? 1492 01:14:27,850 --> 01:14:30,310 Es ist, weil n ein Wert ist das wird so bleiben. 1493 01:14:30,310 --> 01:14:30,979 Recht? 1494 01:14:30,979 --> 01:14:34,020 Aber wie wir unsere Mindest anzupassen und Maximalwerte, sie gehen, um zu ändern. 1495 01:14:34,020 --> 01:14:36,040 Und als ein Ergebnis, unsere Mittel wird sich auch ändern. 1496 01:14:36,040 --> 01:14:37,873 Also das ist, warum wir wollen, dieses Recht hier zu tun. 1497 01:14:37,873 --> 01:14:38,510 OK. 1498 01:14:38,510 --> 01:14:41,600 >> Und dann, jetzt, wir our-- ja gefunden. 1499 01:14:41,600 --> 01:14:44,270 >> Publikum: Nur eine schnelle question-- wenn Sie min und max sagen, 1500 01:14:44,270 --> 01:14:46,410 gehen wir davon aus, dass es ist bereits sortiert? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI PENG: Ja, das ist eigentlich ein Voraussetzung für eine binäre Suche, 1502 01:14:48,400 --> 01:14:49,816 dass Sie wissen, dass es sortiert. 1503 01:14:49,816 --> 01:14:53,660 Weshalb Art, in der Sie schreiben Problem, bevor Sie Ihre binäre Suche eingestellt. 1504 01:14:53,660 --> 01:14:55,910 OK. 1505 01:14:55,910 --> 01:14:58,876 So, jetzt, da wir wissen, wo unsere Mittelpunkt ist, was willst du hier? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> Publikum: Wir wollen vergleichen daß zu dem anderen. 1508 01:15:04,319 --> 01:15:05,110 ANDI PENG: Genau. 1509 01:15:05,110 --> 01:15:12,280 So dass Sie gehen, um zu vergleichen, sind Mitte bis Wert, nicht wahr? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 Und was sagt uns, wenn wir vergleichen? 1512 01:15:18,670 --> 01:15:22,226 Was wollen wir danach tun? 1513 01:15:22,226 --> 01:15:25,389 >> Publikum: Ist der Wert größer ist als die Mitte, wir wollen es abgeschnitten. 1514 01:15:25,389 --> 01:15:26,180 ANDI PENG: Genau. 1515 01:15:26,180 --> 01:15:33,940 So dass, wenn der Wert größer als die Mitte, sind wir 1516 01:15:33,940 --> 01:15:36,550 gehen, um diese zu ändern zu wollen, Mindest- und maxes, nicht wahr? 1517 01:15:36,550 --> 01:15:38,980 Was wollen wir ändern? 1518 01:15:38,980 --> 01:15:42,145 Also, wenn wir wissen, dass der Wert irgendwo hier, was denkst du wir ändern? 1519 01:15:42,145 --> 01:15:44,758 Wir wollen unseren ändern Mindest Mitte zu sein, oder? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 Und dann anders, wenn es in diesem Hälfte, was wollen wir ändern? 1522 01:15:54,292 --> 01:15:55,306 >> ZIELGRUPPE: Ihr Maximal. 1523 01:15:55,306 --> 01:15:55,972 ANDI PENG: Ja. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 Und dann haben Sie gerade gehen zu halten Looping, nicht wahr? 1526 01:16:04,680 --> 01:16:08,920 Denn jetzt, nach einer Iteration durch Sie eine max hast hier. 1527 01:16:08,920 --> 01:16:10,760 Und dann können Sie eine Mitte neu zu berechnen. 1528 01:16:10,760 --> 01:16:11,990 Und dann kann man vergleichen. 1529 01:16:11,990 --> 01:16:14,766 Und du gehst zu halten gehst bis die Minuten und die maxes 1530 01:16:14,766 --> 01:16:15,890 haben im wesentlichen konvergiert. 1531 01:16:15,890 --> 01:16:17,890 Und das ist, wenn Sie wissen, dass Sie das Ende von ihm getroffen haben. 1532 01:16:17,890 --> 01:16:20,280 Und entweder haben Sie es gefunden oder Sie müssen nicht an diesem Punkt. 1533 01:16:20,280 --> 01:16:23,170 >> Macht das Sinn für jedermann? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 OK. 1536 01:16:26,770 --> 01:16:27,900 Das ist ziemlich wichtig, da müssen Sie 1537 01:16:27,900 --> 01:16:29,760 , dies in Ihrem Code heute Abend schreiben. 1538 01:16:29,760 --> 01:16:32,660 Aber euch einen ziemlich guten haben Sinn dessen, was Sie tun sollten, 1539 01:16:32,660 --> 01:16:34,051 was gut ist. 1540 01:16:34,051 --> 01:16:34,550 OK. 1541 01:16:34,550 --> 01:16:38,840 So haben wir etwa sieben haben Minuten vor dem Abschnitt. 1542 01:16:38,840 --> 01:16:43,170 Also werden wir darüber zu sprechen Diese pset, die wir tun werden. 1543 01:16:43,170 --> 01:16:46,410 Also die pset wird in zwei Hälften geteilt. 1544 01:16:46,410 --> 01:16:50,230 Die erste Hälfte beinhaltet Implementierung eines Fund 1545 01:16:50,230 --> 01:16:54,210 in dem Sie eine lineare Suche zu schreiben, ein binäre Suche und ein Sortieralgorithmus. 1546 01:16:54,210 --> 01:16:56,690 >> Das ist also der erste Zeit in einem PSET wobei 1547 01:16:56,690 --> 01:17:00,050 Wir werden Ihnen Kerle so genannte Verteilungscode, der Code ist 1548 01:17:00,050 --> 01:17:02,740 dass wir vor, eine schriftliche, sondern nur einige Stücke aufgehört haben 1549 01:17:02,740 --> 01:17:04,635 damit Sie schriftlich beenden. 1550 01:17:04,635 --> 01:17:07,510 So euch, wenn Sie dies zu betrachten Code, könnte man wirklich Angst bekommen. 1551 01:17:07,510 --> 01:17:08,630 Wenn Sie nur wollen, ahh, ich weiß nicht, was das tut, 1552 01:17:08,630 --> 01:17:11,670 Ich weiß nicht, wie, scheint es, dass so kompliziert, ahh, entspannen. 1553 01:17:11,670 --> 01:17:12,170 Es ist in Ordnung. 1554 01:17:12,170 --> 01:17:12,930 Lesen Sie das spec. 1555 01:17:12,930 --> 01:17:16,920 Die Spezifikation wird Ihnen genau erklären, Was alle diese Programme tun. 1556 01:17:16,920 --> 01:17:20,560 >> Beispielsweise ist ein Programm generate.c das wird mit Ihrer pset kommen. 1557 01:17:20,560 --> 01:17:24,060 Sie eigentlich nicht haben, es zu berühren, aber Sie sollten verstehen, was es tut. 1558 01:17:24,060 --> 01:17:28,550 Und generate.c, ist alles was man tut, entweder Erzeugung von Zufallszahlen 1559 01:17:28,550 --> 01:17:32,400 oder Sie können es geben, einen Samen, wie ein verabredeten Zahl, die es dauert, 1560 01:17:32,400 --> 01:17:34,140 und es erzeugt mehr Zahlen. 1561 01:17:34,140 --> 01:17:37,170 Es gibt also eine spezifische Art und Weise, um Umsetzung generate.c in denen 1562 01:17:37,170 --> 01:17:42,760 können Sie einfach eine Reihe von Zahlen damit Sie Ihre anderen Methoden zu testen, auf. 1563 01:17:42,760 --> 01:17:45,900 >> Also, wenn Sie wollen, für Beispielsweise testen Sie Ihre Entdeckung, 1564 01:17:45,900 --> 01:17:48,970 würden Sie wollen generate.c laufen, erzeugen eine Reihe von Zahlen, 1565 01:17:48,970 --> 01:17:50,880 und führen Sie Ihre Helfer-Funktion. 1566 01:17:50,880 --> 01:17:53,930 Ihre Helfer-Funktion ist, wo Sie sind tatsächlich physisch das Schreiben von Code. 1567 01:17:53,930 --> 01:17:59,330 Und von Helfern denken, wie eine Bibliotheksdatei Sie schreiben, dass find ruft. 1568 01:17:59,330 --> 01:18:02,950 Und so innerhalb helpers.c, werden Sie do Suchen und Sortieren. 1569 01:18:02,950 --> 01:18:06,500 >> Und dann wirst du im wesentlichen nur sie alle zusammen. 1570 01:18:06,500 --> 01:18:10,350 Die Spezifikation wird Ihnen sagen, wie man gesetzt, dass auf der Kommandozeile. 1571 01:18:10,350 --> 01:18:14,880 Und du wirst in der Lage, ob testen oder Ihr Art und Suche arbeiten. 1572 01:18:14,880 --> 01:18:15,870 Cool. 1573 01:18:15,870 --> 01:18:18,720 Hat jemand bereits begonnen und auftretende Probleme oder Fragen 1574 01:18:18,720 --> 01:18:20,520 haben sie jetzt mit diesem? 1575 01:18:20,520 --> 01:18:21,020 OK. 1576 01:18:21,020 --> 01:18:21,476 >> ZIELGRUPPE: Warten. 1577 01:18:21,476 --> 01:18:21,932 Ich habe eine Frage. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI PENG: Ja. 1579 01:18:22,844 --> 01:18:28,390 >> Publikum: So habe ich angefangen, die lineare Suche in helpers.c 1580 01:18:28,390 --> 01:18:29,670 und es war nicht wirklich funktioniert. 1581 01:18:29,670 --> 01:18:34,590 Aber dann später, fand ich, dass wir gerade aus haben, um es zu löschen und zu tun binäre Suche. 1582 01:18:34,590 --> 01:18:36,991 So macht es aus, wenn es nicht funktioniert? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI PENG: Kurze Antwort ist nein. 1585 01:18:41,510 --> 01:18:42,642 Aber da wir nicht-- 1586 01:18:42,642 --> 01:18:44,350 ZIELGRUPPE: Aber niemand tatsächlich überprüft. 1587 01:18:44,350 --> 01:18:46,058 ANDI PENG: Wir sind noch nie gehen, um das zu sehen. 1588 01:18:46,058 --> 01:18:49,590 Aber wollen Sie wahrscheinlich zu machen sicher, dass Ihre Such funktioniert. 1589 01:18:49,590 --> 01:18:51,700 Denn wenn Sie Ihre Linear Suche nicht funktioniert, 1590 01:18:51,700 --> 01:18:54,410 dann sind die Chancen Ihrer binären Suche wird nicht so gut funktionieren. 1591 01:18:54,410 --> 01:18:56,646 Weil Sie ähnliche haben Logik in beide. 1592 01:18:56,646 --> 01:18:58,020 Und nein, es ist nicht wirklich wichtig. 1593 01:18:58,020 --> 01:19:01,300 Also die einzigen, die Sie drehen in sind eine Art und binäre Suche. 1594 01:19:01,300 --> 01:19:02,490 Ja. 1595 01:19:02,490 --> 01:19:06,610 >> Und auch viele Kinder waren versuchen, helpers.c kompilieren. 1596 01:19:06,610 --> 01:19:09,550 Sie sind nicht wirklich erlaubt das zu tun, weil helpers.c 1597 01:19:09,550 --> 01:19:11,200 nicht über eine Hauptfunktion. 1598 01:19:11,200 --> 01:19:13,550 Und damit Sie nur sollten werden tatsächlich kompilieren 1599 01:19:13,550 --> 01:19:18,670 generieren und zu finden, denn zu finden Gespräche helpers.c und die Funktionen in sich. 1600 01:19:18,670 --> 01:19:20,790 So dass das Debuggen ein Schmerz in den Hintern. 1601 01:19:20,790 --> 01:19:22,422 Aber das ist, was wir zu tun haben. 1602 01:19:22,422 --> 01:19:23,880 Publikum: Sie haben zu machen, oder? 1603 01:19:23,880 --> 01:19:27,290 ANDI PENG: Sie können einfach machen alle als gut, ja. 1604 01:19:27,290 --> 01:19:28,060 OK. 1605 01:19:28,060 --> 01:19:32,570 Das ist es also in dem, was die pset bittet euch alle zu tun. 1606 01:19:32,570 --> 01:19:35,160 Wenn Sie irgendwelche Fragen haben, fühlen frei, mit mir nach Abschnitt fragen. 1607 01:19:35,160 --> 01:19:37,580 Ich werde hier für, wie, 20 Minuten betragen. 1608 01:19:37,580 --> 01:19:40,500 >> Und ja, die pset ist wirklich nicht so schlimm. 1609 01:19:40,500 --> 01:19:41,680 You guys sollte in Ordnung sein. 1610 01:19:41,680 --> 01:19:43,250 Diese folgen nur Richtlinien. 1611 01:19:43,250 --> 01:19:47,840 Art haben ein Gefühl der logischerweise welche sollte geschehen und alles wird gut. 1612 01:19:47,840 --> 01:19:48,690 Seien Sie nicht zu Angst nicht. 1613 01:19:48,690 --> 01:19:50,220 Es gibt eine Menge von Code bereits dort geschrieben. 1614 01:19:50,220 --> 01:19:53,011 Nicht zu viel Angst, sich nicht, wenn Sie dies nicht tun zu verstehen, was das alles bedeutet. 1615 01:19:53,011 --> 01:19:54,749 Wenn es sich um eine Menge, es ist völlig in Ordnung. 1616 01:19:54,749 --> 01:19:55,790 Und Bürozeiten kommen. 1617 01:19:55,790 --> 01:19:57,520 Wir helfen Ihnen, einen Blick zu nehmen. 1618 01:19:57,520 --> 01:20:00,810 >> Publikum: Mit der zusätzlichen Funktionen Sehen wir aus jenen up? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI PENG: Ja, das sind im Code. 1620 01:20:03,417 --> 01:20:05,750 Im Spiel von 15, die Hälfte es ist bereits für Sie geschrieben. 1621 01:20:05,750 --> 01:20:09,310 Also diese Funktionen sind bereits im Code. 1622 01:20:09,310 --> 01:20:12,020 Yep. 1623 01:20:12,020 --> 01:20:12,520 Gut. 1624 01:20:12,520 --> 01:20:14,000 Nun, viel Glück. 1625 01:20:14,000 --> 01:20:15,180 Es ist eine ekelhafte Tag. 1626 01:20:15,180 --> 01:20:19,370 Also hoffentlich euch nicht zu fühlen schlecht bleiben im Inneren und Codierung. 1627 01:20:19,370 --> 01:20:22,133