[Musikwiedergabe] 

ANDI PENG: Willkommen in Woche 3 der Sektion. Vielen Dank, Jungs, für alle kommenden auf diese frühere Startzeit heute. Wir haben einen schönen, kleinen intime Gruppe heute. Also hoffentlich werden wir zu bekommen Finish, vielleicht, früh, ein bisschen früh heute. So schnell, nur einige Ankündigungen für die Tagesordnung heute. Bevor wir beginnen, sind wir werde einfach gehen über einige kurze logistische Probleme, pset Fragen, Nachbesprechung, solche Dinge. Und dann werden wir tauchen rechts in. Wir werden einen Debugger GDB genannt zu bedienen starten Entlarvung unseren Code, der David in der Vorlesung erläutert den anderen Tag. Wir werden über die vier Arten von Arten zu gehen. Wir werden über sie ziemlich schnell gehen denn sie sind ziemlich intensiv. Aber wissen, dass alle Folien und Source-Code sind immer online. So fühlen sich frei, um Ihre Durchsicht, um gehen Sie zurück und schauen Sie sich das. 

Wir werden durchgehen asymptotische Notation, die ist nur eine andere Art zu sagen: "Laufzeiten" wo wir die große O, die David erklärte im Vortrag. Und wir haben auch Omega, die ist die untere Grenze der Laufzeit. Und wir werden ein bisschen mehr reden eingehende über, wie diese Arbeit. Und schließlich werden wir über binäre Suche zu gehen, weil viele von euch, die bereits warf einen Blick auf Ihre psets wahrscheinlich wissen, dass das ist eine Frage, die in Ihrem pset ist. So werden Sie alle glücklich sein dass wir dies heute abdecken. 

Und schließlich, nach Ihren Abschnitt Feedback, habe ich eigentlich auf der linken Seite ca. 15 Minuten das Ende, um nur übergehen Logistik pset3, Fragen, vielleicht eine gewisse Orientierungshilfe, wenn man so will, bevor wir beginnen Programmierung. Also lassen Sie uns versuchen, durchzukommen das Material ziemlich schnell. Und dann haben wir einige Zeit damit verbringen können nehmen mehr Fragen für die pset. OK. 

Schnell, so dass nur ein paar Ankündigungen, bevor wir beginnen heute. Erstens, willkommen zu machen es durch zwei Ihrer psets. Ich warf einen Blick auf your-- ja, lassen Sie uns bekommen eine Runde Applaus für diesen einen. Eigentlich war ich wirklich, wirklich beeindruckt. Ich benotet die erste pset für euch letzte Woche und du Jungs haben unglaublich. 

Stil war auf den Punkt außer ein paar Kommentare. Stellen Sie sicher, dass Sie immer Kommentieren Sie den Code. Aber Ihre psets waren auf den Punkt. Und weiter so. Und es ist gut für die Grader zu sehen, dass ihr Jungs setzen in so viel Mühe in Ihren Stil und Ihr Design in Ihrem Code dass wir gerne für Sie zu sehen. So bin ich auf meine Dankbarkeit vorbei für den Rest der TAs. 

Allerdings gibt es ein Nachbesprechung paar Fragen Ich will einfach nur hingehen, dass würde sowohl meinem Leben zu machen und eine Menge von anderen TAs 'lebt ein bisschen einfacher. Zum einen habe ich bemerkt, diese Vergangenheit week-- wie viele von euch läuft seit check50 auf Ihr Code, bevor Sie einreichen? OK. So sollte jeder check50 tun, because-- eine secret-- wir tatsächlich laufen check50 als Teil unserer Korrektheit Skripten zum Testen Ihres Codes. Also, wenn Ihr Code schlägt fehl check50, aller Wahrscheinlichkeit nach, es ist wahrscheinlich zu scheitern unsere Check als gut. Manchmal euch haben die richtigen Antworten. Wie in gierig, einige Sie haben das Recht zahlen, Sie gerade auszudrucken einige zusätzliche Sachen. Und das Extramaterial tatsächlich ausfällt das Kontroll, weil der Computer nicht wirklich, was es sucht. Und so wird es nur durchlaufen, sehen, dass Ihre Ausgabe nicht entsprechen, was wir erwarten, dass die Antwort zu sein, und markieren Sie es falsch ist. 

Und ich weiß, dass in passiert einige Ihrer Fälle dieser Woche. Also ging ich zurück und manuell herabgestuft jeden Code. In Zukunft aber, Bitte stellen Sie sicher, dass Sie laufen Check 50 auf Ihren Code. Da es sich um eine Art Schmerz für den TA zu haben, um zurück zu gehen und manuell regrade jeder einzelne pset für jeden Single, wenig verpasst Instanz. So dass ich nicht nehmen Sie keine Punkte. Ich glaube, ich nahm vielleicht ein oder zwei für Design. In der Zukunft jedoch, wenn Sie andernfalls check50 bist, Punkten genommen wird off auf Richtigkeit. 

Weiterhin sind psets aufgrund freitags am Mittag. Ich denke, es gibt eine siebenminütige Spät Nachfrist, die wir geben Ihnen. Per Harvard Zeit, sie zu dürfen 7 Minuten zu spät, alles zu sein. Also hier in Yale, werden wir sich an das auch. Aber ziemlich genau, um 12:07 Uhr, wenn Ihr pset ist nicht in, es wird so spät zu kennzeichnen. Und so, während es markiert ist so spät, ich bin der TA-- immer noch auf sein Gehalt von Ihren psets. So dass Sie immer noch ein Grad angezeigt. Jedoch wissen, dass bei das Ende des Semesters, alle späten psets wird nur sein, durch den Rechner automatisch genullt. 

Wir tun dies aus zwei Gründen. Eine, manchmal bekommen wir entschuldigt, wie Ausreden Dekans, später, dass ich nicht weiß, zu erhalten. So möchten wir sicherstellen, dass wir mit einem Gehalt alles nur für den Fall, wie ich bin fehlt ein Dekan Entschuldigung. Und zweitens, denken Geist, können Sie immer noch Drop eine pset dass hat vollen Umfang Punkten. Und so möchten wir Note alle Ihre psets gerade zu sicherzustellen, dass Ihr Handlungsspielraum dort und Sie versuchen ihnen. Also selbst wenn es spät ist, werden Sie noch Kredit für Umfang Punkte, denke ich. 

So Moral von der Geschichte ist, zu machen dass Ihr psets sind in Ein-Zeit. Und wenn sie sich nicht in Ein-Zeit, wissen, dass es nicht so toll. Ja, bevor ich weiterziehen, hat jemand Fragen in Bezug auf pset Feedback? Ja. 

ZIELGRUPPE: Haben Sie wir sagen, kann eine der psets fallen zu lassen? 

ANDI PENG: Ja. So gibt es neun psets Gesamt im Laufe des Semesters. Und wenn Sie Spielraum haben points-- so Umfang ist nur, ziemlich, werden Sie versuchen, die Problem, werden Sie setzen in der Zeit, Sie zeigen, dass Sie haben, demonstriert Ihnen die spec gelesen habe. Das ist ziemlich viel Spielraum. Und wenn Sie erfüllt sind, Geltungsbereich Punkte, die wir können die niedrigsten Drop einer von vollen Umfang. Also das ist in Ihrem Vorteil, abzuschließen und versuchen jeden pset. 

Sogar upload-- wenn keines ihnen zu arbeiten, laden Sie sie alle. Und dann werden wir hoffentlich in der Lage zu sein, geben Ihnen einige dieser Punkte zurück. Cool. Noch Fragen? Groß. 

Zweitens hours-- Büro ein paar schnelle Notizen zu Bürozeiten. So zuerst, Anfang der Woche zu kommen. Niemand ist jemals auf Bürozeiten montags. Christabel zu kam Bürozeiten gestern Abend. Ja, Christabel. Und was haben wir im Büro Stunden letzte Nacht, Christabel? 

Publikum: Wir hatten Eis. 

ANDI PENG: Also das ist richtig, wir hatten Eis in der Bürozeiten der letzten Nacht. Während ich kann Ihnen nicht versprechen, dass wir Eis an Bürozeiten haben jede Woche, was ich kann Ihnen versprechen, ist, dass es deutlich sein, eine besserer Schüler, um den TA-Verhältnis. Wie legitim, es ist wie drei zu eins. Ange Vergleichen Sie das mit Donnerstag, haben Sie bekam 150 wirklich gestresst Kinder und kein Eis. Und es ist einfach nicht produktiv für jedermann. So Moral von der Geschichte ist, früh zu kommen In den Bürozeiten und gute Dinge wird passieren. 

Außerdem kommen vorbereitet, Fragen zu stellen. Wissen Sie? Unabhängig davon, was TAS, I denken, gesagt haben, wir haben immer ein paar Studenten , die kommen am Donnerstag auf, wie, 10.50 Uhr nicht mit der Spezifikation zu lesen Wesen wie mir helfen, helfen Sie mir. Leider zu diesem Zeitpunkt gibt es nicht viel, was wir tun können, um Ihnen zu helfen. Also bitte kommen am Anfang der Woche. Kommen Sie früh, um zu Bürozeiten. Kommen Sie bereit, Fragen zu stellen. Stellen Sie sicher, dass Sie als ein Student sind, wo Sie brauchen, um, so dass das sein TAs können Sie entlang zu führen, das ist, was der Bürozeiten ist sollte für zugeteilt. 

Zweitens, so weiß ich, Professoren Lust, uns mit Tests überraschen. Ich hatte ein Professor diejenigen wie, yo, by the way, daran erinnern, dass Halbzeit Sie nächsten Montag. Ja, ich wusste nicht, über diese Halbzeit. Also werde ich zu sein, dass TA dass erinnert Sie all das Quiz 0--, weil, wissen Sie, wir sind CS. Nun, da wir getan haben, Arrays, erhalten Sie Deshalb ist es Quiz 0, nicht Quiz 1, eh? OK. Oh, ich habe einige leise Lachen auf, dass man. OK. 

So Quiz 0 wird 14. Oktober, wenn sein Sie in der Montag-Mittwoch Abschnitt sind und 15. Oktober, wenn du bist das Dienstag-Donnerstag Abschnitt. Dies gilt nicht für diejenigen von euch an der Harvard- who-- Ich denke, Sie alle werden Einnahme Ihrer Quiz am 14.. 

Also ja, nächste Woche, wenn David, in der Aula, geht, ja, so ungefähr, dass Quiz nächste Woche, können Sie alle nicht, weil schockiert sein Sie Abschnitt kam und Sie wissen, dass Ihre quiz 0 ist in zwei Wochen. Und wir schreiben müssen Sitzungen und alles. Also keine Sorgen über die für die Angst. Haben Sie Fragen before-- Fragen in allen logistischen Fragen in Bezug auf, Grading, Bürozeiten, Abschnitte? Ja. 

ZIELGRUPPE: Also das Quiz ist gehen, um während der Vorlesung sein? 

ANDI PENG: Ja. Also das Quiz, denke ich, ist 60 Minuten in diesem Zeitschlitz zugeteilt dass Sie nur nehmen im Hörsaal. So dass Sie nicht haben, um es in auf, wie, einem zufälligen 07.00. Es ist alles gut. Ja. Cool. 

Gut. So dass wir zu gehen vorstellen, ein Konzept zu Ihnen diese Woche, dass David schon Art der berührte in Vortrag in der vergangenen Woche. Es heißt GDB. Und wie viele von euch, während in der Verlauf Schreiben Ihrer psets, haben einen großen Button mit der Aufschrift aufgefallen "Debug" am oberen Rand Ihrer IDE? OK. So, jetzt werden wir tatsächlich bekommen, um auszugraben das Geheimnis, was diese Schaltfläche tatsächlich tut. Und ich garantiere Ihnen, es ist ein schön, schöne Sache. 

Also bis jetzt, denke ich, Es gab zwei Dinge, Studenten waren typischerweise tut beim Debuggen psets. One, sie entweder hinzufügen, in printf () - so alle paar Zeilen, sie in einer printf () hinzuzufügen - oh, was ist diese Variable? Oh, was ist das variable now-- und man irgendwie sehen die Progression des Codes, wie es läuft. Oder das zweite Verfahren Kindern zu tun ist dass sie nur schreiben das Ganze und dann so gehen am Ende. Hoffentlich funktioniert es. Ich garantiere Ihnen, ist GDB besser als beide dieser Methoden. Ja. So wird dies Ihr neuer bester Freund sein. Denn es ist eine schöne Sache dass visuell zeigt sowohl was Ihr Code tut an einem bestimmten Punkt als auch, was alle Ihre Variablen tragen, wie das, was ihre Werte sind, an diesem bestimmten Punkt. Und auf diese Weise können Sie wirklich Haltepunkte in Ihrem Code. Sie können durch die Zeile für Zeile ausführen. Und GDB müssen nur für die Sie, angezeigt, damit Sie, was alle Ihre Variablen sind, was tun sie, was los ist in den Code. Und in einer solchen Weise, ist es so viel einfacher zu sehen, was anstelle von printf-ing geschieht bzw. vor Aussagen. 

Also werden wir ein Beispiel dafür später. Also das scheint ein wenig abstrakt. Keine Sorge, wir werden Beispiele zu tun. Und so im wesentlichen die drei größten, am häufigsten verwendeten Funktionen finden Sie in GDB brauchen sind die nächsten, Schritt über, und Schritt in Tasten. Ich werde über Kopf es eigentlich gerade jetzt. 

So kann euch alle sehen, dass oder sollte ich in ein wenig zu vergrößern? In der Rückseite können Sie sehen, dass? Sollte ich in zu vergrößern? Nur ein bisschen? OK COOL. Da gehen wir. OK. 

So habe ich, hier, mein Implementierung für gierig. Und während eine Menge von euch schreibt gierig in while-Schleife, dass form-- ist eine völlig akzeptable Weise zu tun, es-- einen anderen Weg, es zu tun ist, einfach teilen in der Modulo. Denn dann können Sie Ihre Wert und dann haben Sie Ihren Rest. Und dann können Sie nur fügen sie alle zusammen. Hat die Logik, was ich tue hier sinnvoll, alle, bevor wir beginnen? So'ne Art? Cool. Groß. Es ist eine ziemlich sexy Stück Code, würde ich sagen. Wie ich schon sagte, David, in Vortrag, nach einer Weile, Du sehen, beginnen Code als etwas, das schön ist. Und manchmal, wenn Sie schön zu sehen Code, es ist so ein wunderbares Gefühl. 

So aber, während dieser Code ist sehr schön, funktioniert es nicht richtig. Also lassen Sie uns laufen check50 zu diesem Thema. Prüfen 50 20-- oop. 2? Ist, dass PSet2? Ja. Oh, pset1. OK. So laufen wir check50. 

Und wie Sie Jungs können hier sehen, es andernfalls ein paar Fällen. Und für einige von euch, in die Selbstverständlich tun Sie Ihr Problem-Sets, Sie wie, ah, warum funktioniert es nicht. Warum ist es für manche Arbeits Werte für andere aber nicht? Nun, GDB wird Ihnen helfen, Figur herauszufinden, warum diese Eingänge nicht in Betrieb waren. 

OK. Also mal sehen, einer der Kontrollen wurde ich in Ermangelung check50 war der Eingangswert von 0,41. So ist die richtige Antwort, Sie sollten immer ein 4. Sondern das, was ich den Ausdruck ist das 3-n, die nicht korrekt ist. Lassen Sie uns also nur manuell ausgeführt, nur stellen Sie sicher, dass check50 funktioniert. Lass uns ./greedy. Hoppla, habe ich gierig zu machen. Da gehen wir. Jetzt ./greedy. 

Wie viel ist zu verdanken? Lass uns 0,41. Und ja, wir sehen hier, dass es Ausgeben 3 wenn die richtige Antwort, in der Tat, sollten 4 sein. Also lassen Sie uns geben GDB und sehen, wie wir kann über die Festsetzung dieses Problem zu gehen. 

Also der erste Schritt bei der immer Debugging-Code ist es, einen Haltepunkt zu setzen, oder ein Punkt, an dem Sie wollen Sie den Computer oder die Debugger zu beginnen,. Also, wenn Sie nicht wirklich wissen, was dein Problem ist, in der Regel ist die typische Sache, die wir wollen, zu tun ist, um unsere Haltepunkt am Haupt gesetzt. Also, wenn euch kann dies zu sehen roten Knopf genau dort, yep, dass mich die Einstellung ein Haltepunkt für die Hauptfunktion. Ich klicke auf, dass. 

Und dann kann ich hinaufziehen zu meinem Debug-Taste. Ich traf diese Schaltfläche. Lassen Sie mich wieder zu verkleinern, wenn ich kann. Da gehen wir. So haben wir, hier ein Panel auf der rechten Seite. Es tut mir leid, Leute in den Rücken, die Sie kann nicht wirklich sehen wirklich gut. Aber im Wesentlichen alle Diese rechte Tafel tut ist die Verfolgung sowohl der hervorgehobenen Linie, die die Codezeile ist dass der Computer gerade läuft, sowie alle Ihre Variablen hier unten. 

So haben Sie Cent, Münzen, n, alles, um verschiedene Dinge erklärt an diesem Punkt. Keine Sorgen, denn wir haben nicht wirklich initialisiert sie auf alle Variablen leer. Also in Ihrem Computer, Ihrem Computer ist einfach zu sehen, oh, 32767 war die zuletzt verwendete Funktion dieser Speicherplatz in meinem Computer. Und so das ist, wo Cent derzeit. Aber nein, dass, wenn Sie den Code ausführen, sollte es sich initialisiert. 

Lassen Sie uns also durch zu gehen, Zeile Linie, was hier vor sich geht. OK. Also hier sind die drei Tasten, die ich gerade erklärt. Sie haben die Wiedergabe oder die Run-Funktion, Taste, haben Sie die Schaltfläche Step Over, und Sie haben auch den Schritt in die Taste. Und im wesentlichen alle drei sie nur durch den Code zu gehen und verschiedene Dinge tun. 

Also in der Regel, wenn Sie Debugging sind, Wir wollen nicht einfach auf Play, weil Wiedergabe wird nur laufen Ihren Code bis zum Ende des es. Und dann wirst du nicht wirklich was dein Problem kennen es sei denn, Sie mehrere Haltepunkte setzen. Wenn Sie mehrere Haltepunkte setzen, Es wird nur automatisch von einem Haltepunkt, zu der nächsten, auf die nächste. Aber in diesem Fall wir haben nur so, dass man, weil wir unsere Weise arbeiten wollen von oben nach unten nach unten. So werden wir auf diese Schaltfläche ignorieren jetzt für die Zwecke dieses Programms. 

Also der Schritt über Funktion nur Schritte über jede einzelne Zeile und sagt Ihnen, was der Computer tut. Der Schritt in die Funktion geht in die eigentliche Funktion das ist auf Ihrem Codezeile. So zum Beispiel, wie printf (), , dass eine Funktion, nicht wahr? Wenn ich wollte, um körperlich Schritt in die printf () -Funktion, Ich würde tatsächlich in das Stück gehen Code, wo printf () geschrieben wurde, und sehen, was ist da los. 

Aber in der Regel angenommen, dass der Code, den wir Ihnen funktioniert. Wir übernehmen die printf () funktioniert. Wir gehen davon aus, dass getint () funktioniert. Es gibt also keine Notwendigkeit, Schritt in diese Funktionen. Aber wenn es funktioniert , dass Sie selbst schreiben dass Sie überprüfen möchten herauszufinden, was los ist, Sie würde zu Schritt wollen in dieser Funktion. 

So jetzt sind wir gerade dabei zu Schritt über diesen Teil des Codes. Also mal sehen. Oh, drucken, "Oh hai, how viel Veränderung geschuldet ist? " Wir kümmern uns nicht. Wir wissen, dass funktioniert, so dass wir Schritt über sie. 

So n, die unsere Schwimmer ist, dass wir haben initialized-- oder declared-- an der Spitze, jetzt sind wir gleich, daß bis GetFloat (). Also lassen Sie uns Schritt über. Und wir sehen, bei der Boden hier, das Programm veranlasst mich, einen Wert eingeben. Lassen Sie uns also Eingang den Wert wollen wir hier zu testen, die 0,41 ist. Groß. 

So, jetzt n-- kann euch sehen hier am bottom-- es stored-- weil wir noch nicht abgerundet ist es in diesem wie riesige gespeichert Schwimmer, die 0,4099999996 ist, welche nahe genug, um unsere Zwecke, gerade jetzt, um 0.41. Und dann werden wir später sehen, wie wir weiter stieg über das Programm, nachdem hier hat n geworden gerundet und Cent hat sich 41. Groß. So wissen wir, dass unsere Arbeits Rundung. Wir wissen, dass wir die richtige Anzahl von Cents, so dass wir wissen, dass das ist, nicht wirklich das Problem. 

So dass wir auch weiterhin Schritt Auf im Rahmen dieses Programms. Wir gehen hier. Und so nach dieser Codezeile, die wir sollten wissen, wie vielen Seiten die wir haben. Wir treten auf. Und Sie sehen, wir haben in der Tat, haben ein Quartal, da haben wir 25 subtrahiert von unserer Anfangswert von 41. Und wir haben 16 links für unsere Cent. 

Hat jeder wissen, wie Das Programm wird durch Schritt und warum Cent hat sich zu 16 und warum, heute, Münzen hat sich 1? Jeder ist nach dieser Logik? Cool. So dass dieser Punkt, die Programmarbeits, nicht wahr? Wir wissen, es ist genau das, was wir wollen, dass es. Und wir haben nicht wirklich haben ausdrucken, oh, was ist Cent an dieser Stelle, was Münzen an dieser Stelle. 

Weiter geht es durch das Programm gehen. Schritt über. Cool. Wir gehen über Groschen. Groß. Wir sehen, dass es gemacht off 0,10 $ für einen Cent. Und jetzt haben wir zwei Münzen. Das ist richtig. 

Wir gehen über ein paar Cent und wir sehen, dass wir haben mehr als Cent gelassen. Hmm, das ist seltsam. Hier oben auf dem Programm, ich angeblich auf meine Pfennige abgezogen haben. Vielleicht war ich einfach nicht tun, dass die Linie nach rechts. Und ach, sehen Sie, hier, weil wir wissen, dass wir Schritt durch die Leitungen 32 und 33, das ist, wo unser Programm unsachgemäß hatten Variablen ausführen. So können wir schauen und sehen, oh, Ich Subtrahieren Cent hier, aber ich bin nicht wirklich Hinzufügen zu meinen Münzwert. Ich Hinzufügen Cent bin. Und ich will nicht, um hinzuzufügen, Cent, ich will, um Münzen zu fügen. Wenn wir das ändern, um Münzen, wir haben ein Arbeitsprogramm stand. Ich kann check50 laufen. Sie können einfach verlassen von GDB rechts hier und führen Sie dann check50 erneut. Ich konnte es einfach tun. Ich habe gierig zu machen. 0,41. Und hier ist es Druck Sie die richtige Antwort. 

So wie Sie sehen können, Jungs, GDB ist ein wirklich leistungsfähiges Werkzeug denn wenn wir so viel Code haben geht und so viele Variablen dass es schwer für uns, da ein Mensch, den Überblick zu behalten. Der Computer, in der GDB Debugger, die Fähigkeit hat, In den Überblick zu bewahren. Ich weiß, in Visionaire, Jungs, Sie wahrscheinlich könnte einige Segmentation Faults getroffen haben weil Sie liefen außerhalb der Grenzen des Arrays. In dem Beispiel von Caesar, das ist, genau das, was ich hier implementiert. 

So habe ich vergessen zu überprüfen, Was würde passieren, wenn ich nicht zwei Kommandozeilenargumente. Ich wusste nur nicht in dieser Kontrolle gestellt. Und so, wenn ich keine Debug-- ich meine Haltepunkt, dort rechts. Ich laufe Debug. 

OK. Ja. Also eigentlich, GDB sollte mir dort gesagt haben, war ein Segmentierungsfehler gibt. Ich weiß nicht, was los war genau dort, aber wenn ich es lief, es funktionierte. Wenn Sie Codezeilen durchlaufen und GDB könnte nur plötzlich aufhören auf dich, gehen und schauen, was die rote Fehler ist. Es werde Ihnen sagen, hey, du hatte einen Segmentation Fault, was bedeutet, dass Sie den Zugriff versucht Platz in einem Feld, das nicht existiert. Ja. 

Also das nächste Problem setzen Sie diese Woche, you guys wird wahrscheinlich eine Menge Variablen im Umlauf. Du wirst doch nicht sicher sein, was bedeutet das alles an einem bestimmten Punkt. So GDB Ihnen wirklich helfen, herauszufinden Sie heraus, was sie sind alle gleich und die Möglichkeit, dass visuell sehen. Ist jemand, wie verwirrt nichts davon funktionierte? Cool. Gut. So nach, dass sind wir werde tauchen rechts in vier verschiedene Arten von Sorten für diese Woche. Wie viele von euch, zuerst von allen, bevor wir anfangen, haben die gesamte Spezifikation für pset3 lesen? OK. Ich bin stolz auf euch. Das ist wie die Hälfte der Klasse, die ist deutlich mehr als beim letzten Mal. 

Also das ist großartig, denn wenn wir über den Inhalt sprechen in lecture-- oder sorry, in section-- Ich mag eine Menge, dass beziehen zurück, was die pset ist und wie Sie wollen umzusetzen, dass in Ihrem pset. Also, wenn Sie kommen mit lesen Sie die Spezifikation, wird es viel einfacher für Sie zu verstehen, wovon ich spreche, wenn ich sage, Oh hey, könnte dies eine wirklich sein guter Ort, um diese Art zu implementieren. Also diejenigen, die gelesen haben, die spec wissen, dass als Teil Ihres pset, Sie gehen zu haben sind schreib eine Art der Sortierung. So kann dies sehr hilfreich sein für viele von euch heute. 

Also werden wir beginnen mit, im wesentlichen, die einfachste Art der Art, die Auswahl sortieren. Die typische Algorithmus für Wie würden wir über diese gehen ist-- David ging durch diese alle in Vortrag, also werde ich schnell zusammen bewegen hier-- ist im Wesentlichen, Sie haben eine Reihe von Werten. Und dann finden sie die kleinste unsortierten Wert und Sie diesen Wert mit Swap- die erste unsortierten Wert. Und dann hast du nur immer wiederholen mit dem Rest Ihrer Liste. 

Und hier ist eine visuelle Erklärung , wie das funktionieren würde. So zum Beispiel, wenn wir starten mit einer Anordnung von fünf Elementen, index 0-4, 3, 5, 2, 6 und 4 Werte so jetzt in der array-- platziert, wir nur davon ausgehen, dass sie alle unsortierten weil wir sonst nicht getestet. 

So, wie eine Auswahl Art würde Arbeit ist, dass es erste wäre durch die Gesamtheit ausführen der unsortierten Array. Es würde herausgreifen den kleinsten Wert. In diesem Fall 3, rechte jetzt ist der kleinste. Es erhält bis 5. Nö, 5 nicht größer than-- oder sorry, nicht weniger than-- 3. So wird der Minimalwert ist immer noch 3. Und dann haben Sie, um 2 zu erhalten. Der Computer sieht, oh, 2 weniger als 3. 2 muss nun der Minimalwert sein. Und so 2-Swaps mit dem ersten Wert. 

So nach einem Durchgang, wissen wir ja sehen, dass die 2 und die 3 sind vertauscht. Und wir sind gerade dabei, auch weiterhin tun, dies wiederum mit dem Rest des Arrays. So werden wir nur durchlaufen die letzten vier Indizes des Arrays. Wir werden sehen, dass 3 der nächste Minimalwert. So werden wir, dass mit 4 zu tauschen. Und dann sind wir gerade dabei, zu halten durch Laufen, bis schließlich Sie zu erhalten, um eine sortierte Array, in dem 2, 3, 4, 5 und 6 alle sortiert. Hat jeder verstehen, die Logik wie eine Auswahl Art funktioniert? 

Sie müssen nur eine Art von einem Minimalwert. Sie sind zu verfolgen, was das ist. Und immer, wenn Sie es finden, es zu tauschen Sie mit dem ersten Wert im array-- oder, nicht das erste value-- der nächste Wert in der Anordnung. Cool. 

So wie Sie Jungs Art sah von einem kurzen Blick, wir werden diese Pseudocode aus. Also, wenn Sie Jungs in den Rücken wollen bilden eine Gruppe, jeder an einem Tisch kann ein wenig Partner bilden, werde ich Sie Jungs wie drei Minuten, um zu geben nur durch reden die Logik, in Englisch, wie wir vielleicht in der Lage zu implementieren sein Pseudocode, um eine Auswahl Art zu schreiben. Und es gibt Süßigkeiten. Bitte kommen Sie und erhalten Süßigkeiten. Wenn Sie in der Rückseite sind und Sie möchten Süßigkeiten, kann ich Süßigkeiten auf dich werfen. Eigentlich tun Sie-- cool. Oh, das tut mir leid. OK. 

Also, wenn wir möchten, wie eine Klasse, Schreibpseudo denn wie könnte man nähern Dieses Problem, sich fühlen gerade frei. Ich werde einfach gehen um und, um, fragen Sie Gruppen für die nächste Zeile von was wir tun sollten. Also, wenn Sie Jungs wollen starten off, was ist das erste, was zu tun, wenn Sie versuchen, Umsetzung einer Möglichkeit, dieses Programm zu lösen , um eine Liste wahl sortieren? Lassen Sie uns gerade gehen wir davon habe ein Array, in Ordnung? 

ZIELGRUPPE: Sie möchten einige erstellen Art [unverständlich], dass Sie läuft durch den ganzen Array. 

ANDI PENG: Richtig. So wirst du durchlaufen zu wollen, sind durch jeden Raum, oder? So großartig. Wenn Sie Jungs wollen mir die geben nächste line-- ja, in den Rücken. 

ZIELGRUPPE: Überprüfen Sie sie alle für die kleinsten. 

ANDI PENG: Dort gehen wir. So durchlaufen und überprüfen Sie, möchten wir zu sehen, was der Minimalwert ist, nicht wahr? Ich werde also abkürzen "min." Was seid ihr nach tun möchten Sie den minimalen Wert gefunden haben? 

ZIELGRUPPE: [unverständlich] ANDI PENG: So wirst du zu wollen, sind schalten Sie es mit dem ersten des Arrays, Recht? Das ist der Anfang, ich werde sagen. Gut. So, jetzt, dass Sie den ersten getauscht haben ein, was wollen Sie, um danach zu tun? So, jetzt wissen wir, dass dieser hier muss der kleinste Wert sein, oder? Dann können Sie eine zusätzliche Ruhe haben des Arrays, die unsortiert ist. Also, was Sie zu tun, wenn Sie wollen Jungs wollen mir die nächste Zeile zu geben? ZIELGRUPPE: Also Sie durchlaufen möchten durch den Rest des Arrays. ANDI PENG: Ja. Und so was durchlaufen Art implizieren wir wahrscheinlich brauchen werden? Welche Art von-- 

ZIELGRUPPE: Oh, eine zusätzliche Variable? ANDI PENG: Wahrscheinlich ein anderes für Schleife, oder? So dass wir wahrscheinlich gehen zu wollen, iterieren through-- groß. Und dann wirst du zurück bist und die Mindest wahrscheinlich noch einmal überprüfen, Recht? Und du wirst immer wiederholen sind Dies, weil die Schlaufen gerade dabei laufen zu halten, nicht wahr? 

So wie Sie Jungs, wir sehen, einfach nur einen allgemeinen Pseudo wie wir wollen dieses Programm zu schauen. Diese iterate hier, was machen wir in der Regel müssen in unserem Code zu schreiben wenn wir durch eine durchlaufen möchten Array, welche Art von Struktur? Ich denke, Christ schon gesagt, dies vor. 

Publikum: Eine for-Schleife. 

ANDI PENG: Eine for-Schleife? Genau. So ist wohl diese gehen, um eine for-Schleife ist. Was ist ein Check hier gehen, um zu verstehen? In der Regel, wenn Sie überprüfen möchten wenn etwas ist etwas else-- 

Publikum: Wenn. 

ANDI PENG: Ein, wenn, nicht wahr? Und dann die Swap Hier werden wir gehen Sie über später, denn David ging durch, dass in der Vorlesung als auch. Und dann die zweite Iteration implies-- 

ZIELGRUPPE: Another for-Schleife. 

ANDI PENG: --another for-Schleife, genau. Also, wenn wir suchen an das richtig, wir kann sehen, dass wir wahrscheinlich gehen zu müssen, eine verschachtelte for-Schleife mit einer bedingten Anweisung in es und dann wird eine tatsächliche Stück Code, das heißt gehen, um die Werte zu tauschen. Also habe ich nur allgemein geschrieben eine Pseudocode-Code hier. Und dann sind wir eigentlich vor sich geht physisch als eine Klasse, versuchen Sie dies heute umzusetzen. Gehen wir zurück in dieses IDE. 

UH Oh. Warum ist das so nicht-- da ist es. OK. Es tut uns leid, lassen Sie mich versuchen, in ein bisschen mehr zu vergrößern. Da gehen wir. Alles, was ich hier mache ist die ich angelegt habe ein Programm namens "Auswahl / sort.c." Ich habe eine Reihe von neun erstellt Werte, 4, 8, 2, 1, 6, 9, 7, 5, 3. Derzeit, wie Sie können siehe, sie sind ungeordnet. n wird sich die Zahl sein, dass sagt Ihnen, die Menge der Werte Sie haben in Ihrem Array. In diesem Fall haben wir neun Werte. Und ich habe gerade eine for-Schleife hier daß druckt die unsortierten Array. 

Und am Ende habe ich bekam auch ein für Schleife, die nur druckt er wieder heraus. Theoretisch, wenn dieses Programm korrekt arbeitet, am Ende, Sie sollten sehen, for-Schleife eine gedruckte in dem 1, 2, 3, 4, 5, 6, 7, 8, 9 sind alle richtig in Ordnung. 

So haben wir unsere Pseudo hier. Möchte jemand zu-- Ich bin einfach gehen, um zu gehen fragen Sie nach volunteers-- sagen Sie mir, was genau zu, wenn geben wir zunächst nur durchlaufen möchten durch die zu Beginn dieses Array? Was ist der Code-Zeile Ich bin Wahrscheinlich werde hier brauchen? 

ZIELGRUPPE: [unverständlich] 

ANDI PENG: Ja, das Gefühl, kostenlos zu-- sorry, Sie müssen nicht up-- Gefühl stehen frei, Ihre Stimme ein wenig zu erhöhen. 

Gruppe: für int i gleich 0-- 

ANDI PENG: Ja, gut. 

ZIELGRUPPE: i weniger als Array-Länge ist. 

ANDI PENG: So halten in dagegen hier, weil wir keine Funktion haben, dass sagt uns die Länge eines Arrays, Wir haben bereits eine Wert, dass speichert. Recht? Eine andere Sache zu halten in mind-- in einem Array von neun Werten, was sind die Indizes? Sagen wir einfach, dieses Array von 0 bis 3 ist. Sie sehen, dass der letzten Index ist eigentlich 3. Es ist nicht 4, obwohl es vier Werte im Array. 

Also hier, wir müssen sehr vorsichtig sein, von dem, was unsere Bedingung für die Länge es wird. 

ZIELGRUPPE: Wäre es nicht n minus 1? ANDI PENG: Es wird n minus 1, genau. Macht das Sinn, warum es ist n minus 1, jeder? Es ist, weil Arrays sind nullindiziert. Sie beginnen bei 0 und führen Sie bis zu n minus 1. Ja, es ist ein bisschen schwierig. OK. Und dann-- ZIELGRUPPE: Isnt'1 dass bereits um wenn genommen, nur um nicht zu sagen "kleiner oder gleich "und einfach nur sagen," weniger als? " 

ANDI Peng: Das ist eine wirklich gute Frage. Also ja. Sondern auch, die Art und Weise, dass wir Umsetzung der Überprüfung Recht, müssen Sie zwei Werte zu vergleichen. So dass Sie wirklich wollen, lassen Sie das "auf" leer. Denn wenn Sie vergleichen diese, werden Sie nicht irgendetwas, nachdem es zu vergleichen, oder? Ja. So ++ i. Fügen wir unserem Klammern. Whoops. Groß. So haben wir den Anfang unserer äußeren Schleife. So, jetzt wollen wir wahrscheinlich erstellen Sie eine Variable für die Aufbewahrung Spur der kleinste Wert, oder? Will jemand mir die geben Codezeile, die das tun würde? Was brauchen wir, wenn wir zu wollen, etwas zu speichern? 

Recht. Vielleicht ein besserer Name für die würde "temp" be-- völlig works-- vielleicht ein mehr treffend benannt würden, wenn wir wollen, die kleinste value-- 

ZIELGRUPPE: Min. ANDI PENG: min, dort gehen wir. min wäre gut. Und hier, was machen wir möchte es zu initialisieren? Das ist ein bisschen schwierig. Denn noch heute über die Anfang dieses Array, Sie nicht auf alles, was ausgesehen haben, oder? Also, was, automatisch, wenn sind wir nur auf i gleich 0 ist, was machen wir initialisieren möchten unsere erste Minimalwert zu? ZIELGRUPPE: i. ANDI Peng: Ich, genau. Christabel, warum wir wollen, um es in i zu initialisieren? 

ZIELGRUPPE: weil, na ja, wir mit 0 beginnen. So, da haben wir nichts zu vergleichen, es wird die Mindest am Ende als 0. 

ANDI PENG: Genau. Also ist sie genau richtig. Denn wir haben nicht wirklich sah nichts, wir wissen nicht, was unsere Mindestwert ist. Wir wollen einfach nur initialisieren, um i, der, gerade, ist hier richtig. Und während wir fortfahren, nach unten zu verschieben dieses Array, wir werden sehen, dass mit jedem zusätzliche Pass, erhöht i. Und so an diesem Punkt, i ist wahrscheinlich zu wollen, das Minimum sein, denn es geht um was auch immer ist der Beginn des unsortierten Array. Cool. 

So, jetzt hinzufügen möchten uns eine for-Schleife hier, das ist gehen, um durch die Iteration unsortierte oder der Rest dieses Array. Will jemand mir einen geben Codezeile, die das tun würde? Hint-- was machen wir nach unten brauchen hier? Was wird in dieser for-Schleife zu gehen? Ja. Publikum: So würden wir zu wollen haben eine andere ganze Zahl ist, weil wir durch den Rest laufen der Array statt i, vielleicht j. 

ANDI PENG: Ja, das klingt j gut zu mir. Equals? 

Publikum: So würde ich sein, plus 1, weil Sie bei der nächsten Wert angefangen haben. Und dann an den end-- so wieder, j weniger als n minus 1 und dann j ++. ANDI PENG: Great. 

Und dann hier, wir gehen zu wollen, zu überprüfen, um zu sehen, ob unsere Bedingung erfüllt ist, Recht? Weil Sie es wollen ändern Sie den Minimalwert wenn es tatsächlich kleiner als das, was Sie vergleicht sie mit, nicht wahr? Also, was sollen wir hier suchen? Überprüfen Sie,. Welche Art von Aussage werden wir wahrscheinlich ti wollen, wenn wir benutzen wollen etwas zu überprüfen? 

Publikum: Eine if-Anweisung. 

ANDI PENG: Eine if-Anweisung. So if-- und was los zu sein die Bedingung, die wir im Inneren wollen unserer if-Anweisung? 

Publikum: Ist der Wert von j ist kleiner als der Wert von i-- 

ANDI PENG: Genau. So if-- so dass diese Anordnung wird als "Array". Groß. Also, wenn array-- was war das? Sag das nochmal. 

Publikum: Wenn Array-j kleiner ist Array-i, dann würden wir die min. So würde das min j sein. 

ANDI PENG: Macht das Sinn? OK. Und jetzt hier unten, wir tatsächlich wollen die Swap umzusetzen, nicht wahr? So erinnern, in der Aula, dass David, als er versuchte, the-- was tauschen es-- Orangensaft und milk-- 

Publikum: Das war eklig. 

ANDI PENG: Ja, das war ziemlich ekelhaft. Aber es war ein ziemlich gut Konzept demonstrieren Zeit. Also denken Sie an Ihre Werte hier. Sie haben eine Reihe bekam min, eine Anordnung von i, oder was auch immer wir versuchten, hier tauschen. Und Sie wahrscheinlich nicht in gießen Sie sie miteinander zur gleichen Zeit, nicht wahr? Also was machen wir zu müssen, um hier zu erstellen um die Werte korrekt zu tauschen? 

Publikum: Eine temporäre Variable. 

ANDI PENG: Eine temporäre Variable. Lassen Sie uns so tun, int Temp. Siehe, dies wäre ein besser sein Zeit zu-- whoa, was war das? OK. So wäre dies ein besser gewesen, Zeit, um den variablen "Temp." name Lassen Sie uns so tun, int Temp. Was machen wir set temp gleich hierher? ZIELGRUPPE: Min? ANDI PENG: Es ist ein bisschen schwierig. Es ist eigentlich nicht am Ende egal. Es spielt keine Rolle, was Um Sie wählen, um in zu tauschen solange Sie darauf achten, bist du bist die Verfolgung der, was Sie tauschen sind. 

Publikum: Es könnte Array-i sein. 

ANDI PENG: Ja, lass uns Array-i. Und was ist dann die nächste Zeile Code wollen wir hier haben? ZIELGRUPPE: Array-i gleich Array-j. ANDI PENG: Und schließlich? ZIELGRUPPE: Array-j gleich Array-i. ZIELGRUPPE: oder Array-j equals Array-temp-- oder, Temp. 

ANDI PENG: OK. Also lassen Sie uns laufen diese und sehen, wenn es geht, um zu arbeiten. Wo ist das passiert? Oh, das ist ein Problem. Siehe, auf der Leitung 40, wir sind versuchen, Array-j verwenden? Aber woher kommt j nur existieren? 

Publikum: In der for-Schleife. ANDI PENG: Richtig. Also, was sollen wir tun müssen? 

ZIELGRUPPE: Definieren Sie mit raus the-- ZIELGRUPPE: Ja, ich denke, Sie haben zu einem anderen if-Anweisung, direkt zu verwenden? So wie, wenn die minimum-- Alles in Ordnung, lass mich nachdenken. 

ANDI PENG: Jungs, versuchen einen Blick werfen wir sehen, was ist etwas, was wir hier tun? 

ZIELGRUPPE: OK. Also, wenn das Minimum ist nicht gleich j-- so still ich--, wenn das Minimum dann würden wir nicht haben, um zu tauschen. 

ANDI PENG: Bedeutet das, gleich i? Was wollen Sie damit sagen? 

ZIELGRUPPE: Oder ja, wenn die Mindest nicht gleich i, yeah. ANDI PENG: OK. Nun, das löst, Art, unsere Probleme. Aber das immer noch nicht lösen, die Problem, was passiert, wenn j-- seit j nicht außerhalb von ihr existieren, was Sie wollen wir damit zu tun? Deklarieren Sie es außerhalb? Lassen Sie uns versuchen Sie diese. UH Oh. Unsere Art, funktioniert nicht. 

Wie Sie, unsere anfängliche sehen Array hatten diese Werte. Und danach es haben sollte in 1, 2, 3, 4, 5, 6, 7, 8, 9 ist. Es funktioniert nicht. Ahh. Was machen wir? ZIELGRUPPE: Debug. ANDI PENG: Okay, können wir versuchen, dass. Wir können zu debuggen. Zoom out ein wenig. Lassen Sie uns unsere Haltepunkt. Lassen Sie uns gehen like-- OK. 

Also, weil wir wissen bereits, dass diese Zeilen, 15 bis 22, sind working--, weil alles, was ich tue, ist nur durchlaufen und printing-- Ich kann gehen Sie vor und überspringen, dass. Beginnen wir in Zeile 25. Oop, lassen Sie mich loswerden, dass. 

Publikum: So ist der Haltepunkt wo das Debugging beginnt? ANDI PENG: oder stoppt. ZIELGRUPPE: oder stoppt. ANDI PENG: Ja. Sie können mehrere Haltepunkte setzen und sie kann nur direkt von einem zum anderen. Aber in diesem Fall wissen wir nicht, wo der Fehler passiert. So wollen wir nur beginnen von oben nach unten. Yep. OK. 

Also diese Linie hier, wir einspringen können. Sie können hier unten zu sehen, Wir haben eine Reihe bekam. Das sind die Werte die in dem Array. Siehst du das, wie Index 0, es entspricht der value-- oh, Ich werde versuchen, um es zu vergrößern. Sorry, es ist wirklich schwer bei Array-Index 0 see--, wir einen Wert von 4 aufweisen und dann so weiter und so fort. Wir haben unsere lokalen Variablen. Im Moment ist gleich i 0, was wir wollen, dass es sein. 

Und so wollen wir halten durch Schritt. Unser Mindest gleich 0 ist, was wir wollen auch, dass es sein. Und dann unser zweites zu treten wir Schleife, wenn Array-j weniger als Array-i ist, was es nicht war. So haben Sie gesehen, wie dass übersprungen, dass? 

Publikum: So sollte das, wenn Mindest alle dass-- nicht sollte, dass innerhalb der ersten for-Schleife sein? ANDI PENG: Nein, denn Sie wollen immer noch zu testen. Sie wollen einen Vergleich jedes tun Zeit, auch nachdem Sie durch sie auszuführen. Sie wollen nicht nur, es zu tun auf der ersten Durchgangs. Sie wollen es zu tun jede weitere Pass erneut. Können Sie dies überprüfen möchten Ihr Zustand im Inneren. Also werden wir gerade dabei, Halten Sie hier, durch läuft. Ich werde euch einen Hinweis geben. Es hat mit der Tatsache zu tun, dass, wenn Sie Überprüfung Ihrer bedingte, Sie nicht überprüft für die korrekte Index. So jetzt bist du für die Überprüfung Array-Index von j weniger als Array Index der i. Aber was werden Sie tun, um der Beginn der for-Schleife? Sind Sie nicht die Einstellung j gleich i? 

Ja, so können wir tatsächlich Verlassen des Debuggers Sie hier. Werfen wir also einen Blick auf unsere Pseudocode. For-- wir zu gehen beginnen bei i gleich 0 ist. Wir werden gehen bis zu n minus 1. Lassen Sie uns, wir haben das richtig? Yep, das war richtig. 

Also hier drinnen, wir sind gehen, um einen Mindestwert zu schaffen und stellen Sie, dass gleich i. Haben wir das? Yep, das tat. Jetzt in unserem inneren for-Schleife, wir sind werde j tun i gleich n minus 1. Haben wir das? In der Tat haben wir das. 

So aber was machen wir hier zu vergleichen? 

ZIELGRUPPE: j plus 1. ANDI PENG: Genau. Und dann wirst du einstellen möchten sind Ihre Mindest gleich j + 1 als auch. Also ging ich wirklich schnell durch, dass. Haben Sie Jungs verstehen Deshalb ist es j plus 1? OK. 

Also in Ihrem Array, in Ihren ersten Durchlauf durch, Ihre for-Schleife, für int i gleich 0 ist, lassen Sie uns einfach annehmen, dies noch nicht geändert wurde. Wir haben eine Reihe von vollständig, nur vier unsortierten Elemente, nicht wahr? Deshalb wollen wir initialisieren i gleich 0. Und ich werde gerade durch diese Schleife laufen. Und so im ersten Durchgang, werden wir um eine Variable namens "min" zu initialisieren dass auch gleich i, weil wir haben nicht einen Minimalwert. Also das ist derzeit gleich 0 als auch. Und dann werden wir zu durchlaufen. Und wir wollen noch einmal durchlaufen. Jetzt, da wir gefunden haben, was unsere Mindest ist, dass wir, um durch laufen möchten wieder, um zu sehen, ob es zu vergleichen, oder? So j, hier vor sich geht gleich i, nämlich 0. Und dann, wenn Array j plus i, die ist diejenige, die als nächstes über ist, da weniger als das, was Ihre aktuelle Mindest Wert ist, Sie austauschen möchten. 

Also lasst uns einfach sagen, dass wir haben, wie, 2, 5, 1, 8. Gerade jetzt, gleich ist i 0 und j gleich 0 ist. Und das ist unser Minimalwert. Wenn Array-J plus i-- so, wenn die eine das ist, nach dem man wir suchen größer ist als der vorherige ist, es geht um das Minimum zu werden. 

So, hier sehen wir, dass 5 nicht kleiner als die. Also, es wird nicht 5 sein. Wir sehen, dass 1 kleiner als 2, oder? So, jetzt wissen wir, dass unsere Mindest ist werde der Indexwert bei 0, 1, 2 zu sein. Ja? Und dann, wenn Sie sich hier bekommen, können Sie die richtigen Werte zu tauschen. 

Also, wenn Sie Jungs waren gerade mit der j vor, Sie waren nicht auf der Suche an der einen Danach. Sie wurden bei der Suche der gleiche Wert, der Deshalb ist es einfach nicht, etwas zu tun. Heißt das sinnvoll sein, alle zusammen, Deshalb brauchten wir, dass es plus 1? OK. Jetzt lassen Sie uns einfach laufen durch sie zu machen, dass der restliche Code korrekt ist. Warum ist das passiert? Ach, es ist der min direkt hier. Wir waren Vergleich der falschen Wert. Oh nein. 

Oh ja, hier unten waren wir Vertauschen der falsche Werte als gut. Weil wir bei i und j suchen. Das sind die, wir wurden überprüft. Wir haben tatsächlich an den Swap möchten Minimum, das aktuelle Minimum, mit dem, was der eine Außenseite ist. Und wie Sie Jungs können sich sehen Hier haben wir ein sortiertes Array. Es musste einfach mit zu tun die Tatsache, dass, wenn waren wir die Überprüfung der Werten wir den Vergleich, wir waren nicht auf der Suche in den richtigen Werten. Wir wurden an der gleichen einen Blick hier eigentlich nicht tauschen sie. Sie müssen auf der einen nächsten aussehen zu ihm und dann tauschen können. Also das ist, welche Art von war Lauschangriff unseren Code vor. Und was ich hier tat, ist alles, was der Debugger könnte für Sie getan haben, Ich habe es nur auf die Brett, weil es einfacher ist zu, anstatt zu versuchen zu sehen um auf der Debugger heranzoomen. Ist das sinnvoll, um alle? Cool. 

Gut. Wir können zu reden bewegen asymptotische Notation, die ist nur eine andere Art zu sagen die Laufzeiten aller dieser Sorten. So weiß ich, David, in der Aula, berührte Laufzeiten. Und er durch die ganze Formel ging wie man die Laufzeiten zu berechnen. Keine Sorgen darüber. Wenn Sie wirklich neugierig sind auf, wie das funktioniert, zögern Sie nicht, mich nach dem Abschnitt zu sprechen. Wir können zu Fuß durch die Formeln zusammen. Aber ihr habt doch alle, wirklich wissen ist, dass mehr als 2 n quadriert ist dasselbe wie n quadriert. Da die größte Zahl, der Exponent, wächst das Beste. Und so für unsere Zwecke, alles, was wir über Pflege ist, dass riesige Zahl, die wächst. 

Also, was ist der beste Fall, Laufzeit des Auswahl sortieren? Wenn Sie gehen zu müssen, sind um durch eine Liste durchlaufen und dann durch Iteration der Rest der Liste, wie oft sind Sie wahrscheinlich zu, im schlimmsten Fall-- in der besten Fall sorry-- durchlaufen? Vielleicht ist die bessere Frage ist, zu fragen, was ist das Worst-Case- Laufzeit des Auswahl sort. ZIELGRUPPE: n quadriert. ANDI PENG: Es ist n quadriert, rechts. So eine einfache Möglichkeit, denke das ist wie, jedes Mal, wenn zwei for-Schleifen verschachtelt sind, es wird n quadriert werden. Da sind Sie nicht nur durchlauf wieder, Sie müssen zurück um und durch sie auszuführen wieder im Inneren für jeden Wert. Also in diesem Fall, Sie laufen n sind mal n quadriert, das Leid ist--, n mal n, die n Quadrat ist gleich. 

Und Art ist auch ein bisschen einzigartig in dem Sinn dass es keine Rolle spielt, wenn diese Werte sind schon in Ordnung. Es ist immer noch gehen, um durch sowieso laufen. Sagen wir einfach, das war 1, 2, 3, 4. Unabhängig davon, ob es in war Um es noch würde durch ran und noch überprüft den minimalen Wert. Es würde gemacht haben die dieselbe Anzahl von Schecks jedes Mal, wenn auch nicht wirklich etwas zu berühren. 

Also in einem solchen Fall die besten und schlechtesten Laufzeiten sind eigentlich gleichwertig. So ist die voraussichtliche Laufzeit von Selection Sort, welche wir durch das Symbol Theta-Theta, in diesem Fall, würde auch n quadriert werden. Alle drei von diesen würde n quadriert werden. Jeder ist klar, warum die Laufzeit wird n quadriert? 

Gut. Also ich bin gerade dabei, schnell zu laufen durch den Rest der Sorten. Der Algorithmus für bubble sort-- erinnern, Dies war der erste, David ging im Vortrag. Im Wesentlichen treten Sie durch die gesamte Liste und Sie einfach swap-- Vergleichen von zwei zu einer Zeit. Und wenn man es größer ist, als Sie nur tauschen sie. Also, wenn diese höher sind, würden Sie tauschen. Ich habe offizielle rechts hier. 

Also lassen Sie uns einfach sagen, Sie hatten 8, 6, 4, 2. Sie würden die 8 und eine 6 zu vergleichen. Sie müssten, um sie auszutauschen. Sie würden die 8 und 4 zu vergleichen. Sie müssten, um sie auszutauschen. Wenn Sie die 8 tauschen müssen und die 2, ändern Sie sie als gut. Also in dem Sinne, können Sie sehen, über einen längeren Zeitraum gespielt wie die Werte Art von Blase die Enden, deshalb nennen wir Bubble-Sort. 

Wir würden gerade laufen wieder auf unserer zweiten Durchgang und unsere dritte Durchgang, und unser viertes Pass ab. Im Wesentlichen Bubble Sort gerade läuft , bis Sie nicht machen keine weiteren Swaps. In diesem Sinne ist dies nur die allgemeine Pseudocode für sie. Keine Sorge, dies wird alles online sein. Wir haben nicht wirklich über diese gehen. 

Wir haben gerade einen Zähler zu initialisieren Variable, die bei 0 beginnt. Und wir durchlaufen das gesamte Array. Und wenn ein Wert, wenn dies ist-- Wert größer als dieser Wert ist, Sie gehen, um sie auszutauschen. Und dann haben Sie gerade sind gehen, um weiterzumachen. Und du wirst zu zählen. Und Sie gerade gehen zu tun zu halten dies während der Zähler größer als 0 ist, was bedeutet, dass jedes Mal, wenn Sie zu tauschen, Sie wissen, Sie gehen wollen hin und wieder zu überprüfen. Sie wollen Kontrolle zu halten, bis Sie wissen, dass Sie nicht haben, um nicht mehr tauschen. 

Also, was sind die besten und schlechtesten Bei Laufzeiten für Bubble-Sort? Und das ist eigentlich hint-- verschiedenen von der Auswahl Art in dem Sinne, dass diese beiden Antworten nicht die gleichen sind. Überlegen Sie, was passieren würde, in ein Fall, wenn es bereits sortiert. Und darüber nachzudenken, was würde passieren, wenn es in dem Fall, in dem es nicht sortiert. Und Sie Art ausgeführt werden können durch, warum das passiert. Ich werde euch geben, wie, 30 Sekunden, um darüber nachzudenken. 

OK. Hat jemand eine Vermutung, was die haben Worst-Case-Laufzeit des Bubble-Sort ist? Ja. 

ZIELGRUPPE: Wäre es, wie, n-mal sein n minus 1 oder so ähnlich? Wie jedes Mal ausgeführt wird, es ist nur, wie man Auslagerungs weniger dass das, was es war. 

ANDI PENG: Ja, so Sie sind total richtig. Und dies ist ein Fall, in dem Ihr Antwort war eigentlich komplexere als die, die wir brauchen, um zu geben. Also, es wird run-- Ich bin gehen, um all das hier zu löschen. Jeder ist gut? Kann ich zu löschen das? OK. Sie werden durch n Run Zeiten ersten Mal, nicht wahr? Und sie gehen zu durchlaufen n minus 1 zum zweiten Mal, nicht wahr? Und dann wirst du zu halten sind gehen, n Mine 2, und so weiter. David tat dies in einem Vortrag, in dem, wenn Sie alle diese Werte addiert, Sie etwas, das es zu erhalten like-- yeah-- mehr als 2, die im Wesentlichen nur reduziert bis n quadriert. Du wirst eine bekommen seltsame Bruch drin. Und so weiß nur, dass die n quadriert immer Vorrang vor dem Bruch. Und so dass in diesem Fall der schlechtesten Laufzeit würde n quadriert werden. Wenn es in absteigender war um, denken, Sie muss eine Swap jedes Mal zu machen. 

Was wäre möglicherweise sein, die beste Tasche, Laufzeit? Sagen wir einfach, wenn die Liste bereits damit, was wäre die Laufzeit sein? 

ZIELGRUPPE: n. ANDI PENG: Es ist n, genau. Und warum ist es n? ZIELGRUPPE: Weil Sie gerade muss auf jedem einmal zu überprüfen. ANDI PENG: Genau. Also auf die bestmögliche Laufzeit Wenn diese Liste schon sorted-- sagen wir 1, 2, 3, 4-- Sie wäre nur durch zu gehen, würden Sie zu überprüfen, würden Sie sehen, oh, sie alle pan out. Ich hatte nicht zu tauschen. Ich bin fertig. Also in diesem Fall, es ist nur n oder die Anzahl der Schritte, die Sie gerade musste in der ersten Liste zu überprüfen. 

Und nachdem wir jetzt treffen Insertion Sort, wo Der Algorithmus ist im Wesentlichen zu teilen sie in einer sortierten und unsortierten Teils. Und dann einen nach dem anderen, die unsortierten Werte in ihren entsprechenden eingeführt Positionen am Anfang der Liste. 

So zum Beispiel, haben wir ein Liste von 3, 5, 2, 6, 4 wieder. Wir wissen, dass es derzeit unsortiert, weil wir gerade haben begann es zu betrachten. Wir werfen einen Blick und wir wissen, dass der erste Wert, sortiert, nicht wahr? Wenn Sie nur Blick auf eine Reihe von Größe one, wissen Sie, dass es sortiert. 

So wissen wir, dass die anderen vier sind unsortiert. Wir gehen durch, und wir sehen, dass Wert. Lass uns zurück gehen. Sehen Sie diesen Wert von 5? Wir werfen einen Blick auf sie. Wir vergleichen Sie es mit 3. Wir wissen, dass er größer als ist 3, so dass wir wissen, dass das ist, sortiert. So wissen wir jetzt, dass die ersten beiden sortiert sind und die letzten drei sind es nicht. 

Wir werfen einen Blick auf 2. Wir überprüfen sie zuerst mit 5. Ist es weniger als 5? Es ist nicht. So haben wir, auch in Zukunft nach unten. Dann schauen Sie 2 aus 3. Beträgt er weniger als? Nein. Damit Sie wissen, ein 2 muss eingelegt werden in die vorderen und 3 und 5 beide müssen herausgedrückt werden. Tun Sie dies wieder mit 6 und 4. Und wir immer mal im wesentlichen, wo wir gerade prüfen, prüfen, prüfen. Und bis es in die richtige Position, wir Art von gerade legen Sie sie in die richtige Position, Das ist, wo der Name von ihr kam. 

Also das ist nur der Algorithmus, Pseudocode per se, Art, wie wir umsetzen würde eine Insertion sort. Pseudocode ist hier. Es ist alles online. Keine Sorge, wenn Sie Jungs sind versuchen, dies zu notieren. Also noch einmal, was gleichen question-- würde die besten und schlechtesten Laufzeiten sein zum Einsetzen Art? Es ist sehr ähnlich wie die letzte Frage. Ich werde euch geben, wie, 30 Sekunden, um über diese sowie zu denken. 

OK Will jemand die schlechteste Laufzeit geben Sie mir? Ja. 

ZIELGRUPPE: n quadriert. 

ANDI PENG: Es ist n quadriert. Und warum ist es n quadriert? 

ZIELGRUPPE: Weil in umgekehrter Reihenfolge, müssen Sie durch n mal n gehen, was ist-- ANDI PENG: Ja, genau. Also dasselbe wie in der Bubble-Sort. Ist diese Liste in absteigender Reihenfolge, du bist werde zuerst einmal überprüfen zu lassen. Und dann mit jedem Mehrwert, du bist gehen zu müssen, um es gegen prüfen jeden einzelnen Wert, oder? Und so ganz, Sie gehen zu machen sind eine n Pass mal ein anderes n Pass, der ist n quadriert. Was ist mit dem besten Fall? Ja. 

ZIELGRUPPE: n minus 1, da der erste ist bereits im Quadrat. 

ANDI PENG: Also, in der Nähe. Die Antwort ist eigentlich n. Denn während die erste ist geordnet ist, kann es nicht actually-- es wir einfach Glück gehabt, in dass beispielsweise das 2 passiert die kleinste Zahl sein. Aber das wird nicht immer der Fall sein. Wenn 2 bereits in den Anfang, sortiert aber du siehst und es gibt eine 1 hier, die 1 wird ihn stoßen. Und es geht zu Ende up, die sowieso stieß. 

Also im besten Fall, es ist eigentlich gerade dabei, n sein. Wenn Sie 1, 2, 3, 4, 5, 6, 7, 8, sind Sie gehen zu durchlaufen dass ganze Liste einmal um zu überprüfen, ob alles in Ordnung zu sehen. Jeder ist klar auf Lauf Zeiten der Auswahl als auch? Ich weiß, dass ich durchmache diese wirklich schnell. Aber weiß nur, dass, wenn Sie wissen, dass die allgemeine Konzepte, sollten Sie gut sein. OK. Also werde ich nur geben euch vielleicht, wie, eine Minute, um Ihre Nachbarn zu sprechen was sind nur einige der Hauptunterschiede zwischen diesen Arten von Arten. Wir gehen über das bald. ZIELGRUPPE: Oh, OK. ANDI PENG: Ja. OK. Cool, lassen Sie uns als Klasse wieder zusammentreten. OK. Das war also eine Art von offene Frage in dem Sinne, , dass es gibt viele Antworten darauf. Und wir werden über einige von ihnen kurz. Ich wollte Ihnen nur Jungs darüber nachzudenken, was differenziert Alle drei Typen von Arten. Und ich hörte, auch, eine große question-- was Mergesort tun? Gute Frage, denn das ist, was wir abdecken nächsten. 

So verschmelzen Art ist die eine Sorte, die Funktionen sehr verschieden von den anderen Arten. Wie euch see-- können hat David zu tun, dass die Demo- wo er all die coolen hatten Geräusche zu sehen, wie verschmelzen Art lief, wie, stufenlos schneller als die beiden anderen Arten? OK. Also das ist, weil merge sort implementiert, dass die Kluft und erobern Konzept, dass wir sprachen über eine Menge in der Vorlesung. In diesem Sinne, die wir gerne arbeiten intelligenter, nicht härter, wenn Sie teilen und erobern Probleme, und brechen sie nach unten, und dann legte sie zusammen, gute Dinge immer passieren. 

Also die Art und Weise, verschmelzen sort Wesentlichen funktioniert ist, dass es teilt ein unsortierte Array in zwei Hälften. Und dann es hat zwei Hälften des Arrays. Und es ist nur sortiert diese zwei Hälften. Es hält nur Teilung in zwei Hälften, in Hälfte, in der Hälfte, bis alles sortiert und dann rekursiv bringt sie alle zusammen. 

Also das ist wirklich abstrakt. Das ist also nur ein bisschen Pseudocode. Ist das sinnvoll in die Art, wie es läuft? Also lasst uns einfach sagen, dass Sie eine haben, Array von n Elementen, nicht wahr? Wenn n kleiner als 2 ist, können Sie zurückkommen. Weil Sie wissen, dass, wenn es nur einen müssen sie sortiert werden. Else, die linke Hälfte sortieren Sie, und dann können Sie die rechte Hälfte zu sortieren, und dann können Sie verschmelzen. 

Während also das sieht einfach, in der Realität, daran zu denken ist etwas schwierig. Weil Sie wie sie sind, gut, das ist irgendwie läuft auf sich. Recht? Es ist auf sich selbst läuft. In diesem Sinne, berührte David auf Rekursion in der Klasse. Und das ist ein Konzept, wir über mehr reden. Ist es, dass diese sich diese beiden Linien hier ist eigentlich nur das Programm erzählen sie sich selbst ausführen mit unterschiedlichen Eingangs. Also anstatt mit sich führen die Gesamtheit von n Elementen, Sie können es unten in der Pause linke Hälfte und die rechte Hälfte und führen Sie es erneut. 

Und dann werden wir auf sie visuell zu suchen, denn ich bin ein visueller Lerner. Es funktioniert besser für mich. Also werden wir bei einer visuellen Beispiel hier betrachten. 

Sagen wir, wir haben eine Reihe, sechs Elemente 3, 5, 2, 6, 4, 1, nicht sortiert. Na gut, es gibt eine Menge auf dieser Seite. Also, wenn Sie Jungs können bei der Suche zunächst hier, 3, 5, 2, 6, 4, 1, Sie können sie in zwei Hälften geteilt. Sie haben 3, 5, 2, 6, 4, 1. Sie wissen, dass diese aren't-- Sie weiß nicht, ob sie sortiert oder nicht, so dass Sie zu halten und zwar getrennt nach, in der Hälfte, in der Mitte, in der Mitte, bis schließlich, Sie haben nur ein Element. Und ein Element immer sortiert, nicht wahr? 

Also wissen wir, daß 3, 5, 2, 4, 6, 1, mit sich selbst, sortiert werden. Und jetzt können wir sie wieder zusammen zu setzen. So kennen wir die 3, 5. Wir setzen diese zusammen. Wir wissen, das ist sortiert. Die 2 ist immer noch da. Wir können die 4 und die 6 zusammen. Wir wissen, dass das ist, sortiert, so stellen wir fest, dass zusammen. Und die 1 ist dort. 

Und dann muß man nur betrachten diese zwei Hälften hier richtig. Sie haben die 3, 5, 2, 2, 3, 5. Sie können einfach vergleichen die Anfang von allem. Weil Sie wissen, dass dies ist, sortiert und Sie wissen, dass das ist, sortiert. Also Sie haben nicht einmal zu haben, Vergleichen Sie die 5, die Sie gerade zu vergleichen, die 3. Und die 2 ist kleiner als 3, so Sie wissen, 2 müssen am Ende zu gehen. 

Gleiche drüben. Die 1 muss hier. Und dann, wenn du gehst zu setzen diese beiden Werte zusammen, Sie wissen, dass diese sortiert und Sie wissen, dass das ist, sortiert. So dann wird die 1 und die 2 die 1 kleiner als 2 ist. Das sagt Ihnen, dass die 1 sollte am Ende dieser gehen ohne auch nur einen Blick auf 3 oder 5. Und dann die 4, können Sie einfach zu überprüfen, geht es direkt hier. Sie müssen nicht an der 5 aussehen. Das Gleiche gilt für den 6. Sie wissen, dass es gerade die 6-- muss nicht geprüft werden. 

Und so auf diese Weise, bist du nur sparen Sie sich eine Menge von Schritten, wenn Sie den Vergleich. Sie müssen nicht um jeden vergleichen Element gegen andere Elemente. Sie vergleichen, nur gegen die, die Sie benötigen, um es gegen zu vergleichen. Also das ist Art von ein abstraktes Konzept. Keine Sorge, wenn es nicht ganz Schlagen Sie mit der rechten leer. Aber im allgemeinen ist dies wie eine Zusammenführung Art funktioniert. Fragen, kurze Fragen, bevor ich weiter? Ja. 

Publikum: So sagten Sie, dass Sie die 1 und dann der 4 und der 6 und legte sie in. So sind those-- nicht nicht Sie auf der Suche nach ihnen als separate Elemente, nicht als Ganzes? ANDI PENG: Ja. Also, was passiert, ist, dass man im Grunde schaffen ein ganz neues Array. Damit Sie wissen, dass hier, ich habe zwei Arrays der Größe 3, oder? So dass Sie wissen, dass meine sortierten Array muss sechs Elemente haben. So dass Sie nur erstellen neue Größe des Speichers. So dass Sie eine Art, wie du verschwenderisch des Gedächtnisses, aber das spielt keine Rolle, weil es so klein ist. So dass Sie an der 1 sehen und man sich das 2. Und Sie wissen, dass das 1 kleiner als 2. So dass Sie wissen, dass 1 sollte gehen in der Anfang von all denen. 

Sie brauchen noch nicht einmal zu Blick auf die 3 und der 5. Damit Sie wissen, 1 geht es. Dann im Grunde hacken Sie aus dem 1. Es ist, wie, tot zu uns. Dann müssen wir nur noch 2, 3, 5, und 4 und 6. Und dann wissen Sie, dass Sie Vergleichen Sie die 4 und die 2, oh, das 2 sollte in dorthin zu gehen. So können Sie die 2 nach unten plumpsen, hacken Sie es ab. Also müssen Sie nur noch die 3 und 5 in der 4 und der 6. Und Sie halten gerade hacken Sie sie ab , bis Sie sie in das Array. 

Publikum: So können Sie einfach immer sind Vergleichen Sie die [unverständlich]? 

ANDI PENG: Genau. In diesem Sinne, du bist nur den Vergleich im Wesentlichen wissen, eine Zahl gegen die andere Nummer. Und weil Sie wissen, dass es, Sie, sortiert haben nicht zu durchschauen alle Zahlen. Sie müssen nur bei der ersten aussehen. Und dann müssen Sie nur plop können sie nieder, weil Sie wissen, sie gehören, in denen sie angehören müssen. Ja. Gute Frage. 

Und dann, wenn einer von euch sind ein bisschen ehrgeizig, fühlen sich frei, um diesen Code zu suchen. Dies tatsächlich die physikalischen Implementierung der, wie wir merge sort schreiben. Und Sie sehen, es ist sehr kurz. Aber die Ideen hinter sie sind ziemlich komplex. Also, wenn Sie das Gefühl, Zeichnung this out in Ihre Hausaufgaben heute Abend, zögern Sie nicht. 

OK. Also ging David auch über diese in der Vorlesung. Was sind die besten Fall Laufzeiten, Worst-Case-Laufzeiten, und die erwarteten Laufzeiten der merge sort? Ein paar Sekunden, um zu denken. Das ist ziemlich hart, aber Art intuitive, wenn Sie darüber nachdenken. Gut. 

ZIELGRUPPE: Ist der schlimmsten Fall n log n? ANDI PENG: Genau. Und warum ist es n log n. 

Publikum: Ist es nicht, weil es wird exponentiell schneller, so ist es wie eine Funktion, dass statt nur einfach nur n Quadrat, oder was? ANDI PENG: Genau. So dass der Grund, warum die Laufzeit auf diese n log n because-- was bist du dabei in alle diese Schritte? Du bist nur hacken es in der Mitte, oder? Und so, wenn wir tun, die melden Sie sich, alles, was er tut spaltet ein Problem in der Hälfte, in der Mitte, in der Mitte, in mehr Hälften. Und in diesem Sinne, können Sie Art das lineare Modell des zu beseitigen dass wir habe mit. Denn wenn Sie hacken Dinge in die Hälfte, es ist ein Protokoll. Das ist nur die mathematische Weg es darstellt. 

Und dann endlich, am Ende, du bist nur machen einen letzten Durchgang durch , alle von ihnen in Ordnung zu bringen, nicht wahr? Und so, wenn Sie nur noch überprüfen Sie eine Sache, das ist n. Und damit Sie Art sind Multiplikation der beiden zusammen. So ist es wie du, dass abschließende habe Check für n hier unten mit einem log n hier oben. Und wenn Sie multiplizieren sie, das ist n log n. 

Und so die besten und schlechtesten Fall Gehäuse und erwartet, dass alle n log n. Es ist auch wie eine andere Art. Es ist wie Auswahl sort in dem Sinne, dass es Egal, was Ihr Liste ist, ist es nur geht um die gleiche Sache jedes Mal zu tun. OK. So wie Sie sehen können, Jungs, auch wenn die Sorten, die wir through-- n gegangen quadriert, dann ist es nicht sehr effizient. Und selbst diese n log n nicht die effizienteste. Wenn Sie Jungs sind neugierig, es ist eine Art Mechanismen , die so effizient, dass sie sind, fast im wesentlichen flach in der Laufzeit. 

Sie haben etwas log n ist bekam. Sie haben etwas log log n ist bekam. Wir haben nicht auf sie zu berühren in dieser Klasse jetzt. Aber wenn Sie Jungs sind neugierig, fühlen sich frei, Google, was ist die effizientesten Sortiermechanismen. Ich weiß es nicht, es gibt einige wirklich lustig sind, like-- es gibt einige wirklich funny diejenigen, die Menschen zu machen. Und Sie fragen sich, wie sie jemals daran gedacht. Also Google, wenn Sie einige Ersatz haben Zeit auf, was sind einige lustige Möglichkeiten dass people-- sowie effiziente ways-- Menschen konnten Arten umzusetzen. OK. Und hier ist nur eine handliche kleine Karte. Ich weiß, dass Sie alle, die vor diesem Quiz 0, wird in Ihrem Zimmer werden wahrscheinlich versuchen zu merken, dass. Also das ist schön dort für euch. Nur die Logik, die made-- vergessen Sie nicht, warum diese Zahlen wurden auftritt. Wenn du immer verloren, so stellen sicher, dass Sie wissen, was die Sorten sind. Und Sie können durchlaufen ihnen im Kopf um herauszufinden, warum diejenigen, Antworten sind die Antworten. 

Gut. So werden wir bewegen auf schließlich zur Suche. Weil, wie die von Ihnen, die das pset gelesen haben, Suche ist auch Teil diese Woche Problems setzt. Sie werden aufgefordert, zu implementieren zwei Arten von Suchanfragen. One ist eine lineare Suche und eine ist eine binäre Suche. 

So ist die lineare Suche ist ziemlich einfach. Sie wollen einfach nur, um zu suchen Element einer Liste zu sehen, wenn Sie es. Sie müssen nur durchlaufen. Und wenn es gleich etwas, können Sie einfach zurück, nicht wahr? Aber die, die wir am meisten sind interessiert sich für Gespräche über ist binäre Suche, rechts, die der ist Teile und herrsche Mechanismus, David wurde demonstriert in der Vorlesung. 

Denken Sie daran, das Telefonbuch Beispiel dass er immer die Erziehung, die eine, die er Art kämpfte ein bisschen auf das vergangene Jahr, wo Sie das Problem zu halbieren, in der Mitte, in der Mitte, wieder und wieder, , bis Sie finden, was Sie suchen? Und sie haben das Laufzeit das auch. Und Sie können sehen, es ist deutlich effizienter als jede andere Art der Suche. 

So ist die Art und Weise, die wir zu gehen Implementierung eines binären Such ist, wenn wir ein Array, Index 0 bis 6, sieben Elemente, können wir in der Mitte suchen, right-- sorry, wenn unsere Frage first-- wenn wir die Frage, fragen wollen, tut die Anordnung enthält das Element 7, Offensichtlich wobei Menschen, und mit so ein kleines Array, ist es einfach für uns ja zu sagen. Aber die Möglichkeit, eine binäre Umsetzung Such wäre, in der Mitte zu suchen. 

Wir wissen, dass Index 3 der Mitte, weil wir weiß, es gibt sieben Elemente. Welche 7 geteilt durch 2? Sie können abhacken, dass zusätzliche 1. Sie haben 3 in der Mitte stand. So ist Array von 3 gleich 7? Es ist nicht richtig? Aber wir können ein paar Kontrollen zu tun. Ist Array von 3 weniger als 7 oder ist Array von 3 größer als 7? 

Und wir wissen, dass es weniger als 7. So wissen wir, dass, oh, muss es nicht in der linken Hälfte. Wir wissen, dass es sein muss, in der rechten Hälfte, nicht wahr? So können wir nur abhacken Hälfte des Arrays. Wir haben nicht einmal zu Schauen Sie sich es nicht mehr. Denn wir wissen: die Hälfte unserer problem-- Wir wissen, daß die Antwort in die rechte Hälfte der unser Problem. So dass wir nur sehen, dass jetzt. 

So, jetzt schauen wir auf die Mitte, was übrig bleibt. Das Index-5. Wir tun die gleiche Prüfung erneut und wir sehen, dass es kleiner ist. Also schauen wir auf der linken Seite, dass. Und dann sehen wir, dass der Check. Ist der Array-Wert an Index 4 gleich 7? Es ist. So können wir true zurück, weil fanden wir den Wert in unserer Liste. Funktioniert, wie ich ging durch das Sinn für jedermann? OK. Ich werde euch vielleicht geben, wie, drei, vier Minuten, um herauszufinden, wie man dies in Pseudocode. 

So vorstellen, ich Sie gebeten, ein Schreiben Funktion namens search (), die zurückgegeben ein Wert, ein boolescher Wert, das war wahr oder false-- wie, wahr, wenn Sie fanden die Wert false, wenn Sie nicht. Und dann waren im Wert übergeben Sie suchten in Werte, die ist die array-- oh, ich auf jeden Fall setzen , dass an der falschen Stelle. OK. Wie auch immer, das haben sollte bereits in der richtigen Werte. Und dann int n die Zahl der Elemente in diesem Array. Wie würden Sie versuchen zu gehen dieses Problem in Pseudo? Ich werde euch geben, wie drei Minuten, um das zu tun. Nein, ich glaube, es gibt only-- ja, es gibt ein Recht hier oben. Publikum: Kann ich? ANDI PENG: Ja, ich habe Sie. Ist das Arbeits? OK COOL. 

OK. Alle richtigen Jungs, wir sind gehen, um es zu zügeln. OK. So übernehmen wir bekamen dieses schöne habe wenig Array mit n-Werte drin. Ich habe nicht ziehen die Linien. Aber wie würden wir zu gehen versuchen, dies zu schreiben? Will jemand geben Sie mir die erste Zeile? Wenn Sie mir die geben wollen erste Zeile dieser Pseudocode. 

ZIELGRUPPE: [unverständlich] ZIELGRUPPE: Sie würden wollen, iterieren through-- ZIELGRUPPE: Just another for-Schleife? AUDIENCE --for. 

ANDI PENG: Also das hier ist ein bisschen schwierig. Denken Sie about-- Sie wollen Laufen diese Schleife zu halten immer und immer wieder, bis wann? 

Publikum: Bis zum [unverständlich] Wert gleich diesem Wert. ANDI PENG: Genau. So dass Sie eigentlich nur write-- können können wir sogar zu vereinfachen es. Wir können einfach eine while-Schleife, oder? So müssen Sie nur können loop-- wir wissen, dass es eine Weile. Aber für jetzt, ich werde durch das, was - um "Schleife" zu sagen? Loop until-- was unsere Endbedingung? Ich glaube, ich hörte es. Ich hörte jemanden sagen. 

ZIELGRUPPE: Werte gleich Mitte. ANDI PENG: Sag es noch einmal. ZIELGRUPPE: Oder, bis die Wert, den Sie auf der Suche sind für die ist gleich dem mittleren Wert. 

ANDI PENG: Was wäre, wenn es nicht da drin? Was, wenn der Wert, den Sie auf der Suche sind für die ist nicht wirklich in diesem Array? Publikum: Sie kehren 1. 

ANDI PENG: Aber was wollen wir Schleife, bis, wenn wir einen Zustand haben? Ja. 

ZIELGRUPPE: Bis es gibt nur einen Wert? ANDI PENG: Sie können Loop- until-- so dass Sie wissen, dass Sie gehen, um einen Maximalwert haben, oder? Und Sie wissen, dass Sie gehen einen Minimalwert, Recht haben? Denn auch, das ist etwas, Ich habe vergessen, vor sagen, dass etwas, das ist kritisch über binäre Suche ist, dass das Array bereits sortiert ist. Da gibt es keine Möglichkeit, dies zu tun diese, wenn sie sind nur Zufallswerte. Sie wissen nicht, wenn man es größer als die andere, nicht wahr? 

So dass Sie wissen, dass Ihre max und Ihre mins sind hier, nicht wahr? Wenn Sie vorhaben, werden eingestellt sind Ihre max in Ihrem Minuten und den mid-- lassen Sie uns einfach davon ausgehen, Ihre Mitte der Wert richtig ist hier-- du gehst zu Grunde Schleife, bis Sie Ihre Mindest ist etwa die gleiche wie Ihre max, rechts oder wenn Ihr max ist nicht das gleiche wie Ihr min. Recht? Denn wenn das passiert, wissen Sie, dass Sie haben schließlich traf den gleichen Wert. So möchten Sie Schleife, bis Ihre min ist kleiner oder gleich zu-- oops, nicht weniger als oder gleich, umge herum-- max. 

Hat das Sinn? Ich nahm ein paar Versuche, dieses Recht zu bekommen. Aber Schleife, bis Sie Ihr Max-Wert ist im Wesentlichen fast weniger oder gleich Ihre minimale, nicht wahr? Das ist, wenn Sie wissen, dass Sie noch angenähert. Publikum: Wann möchten Sie Ihr Maximal Wert kleiner als der Mindest sein? ANDI PENG: Wenn Sie zu halten passt ihn, die ist das, was wir gehen zu tun, werden in diesem. Ist das sinnvoll? Mindest- und max sind nur ganzen Zahlen, die wir sind wahrscheinlich gehen zu wollen, zu erstellen, um zu halten verfolgen, wo wir suchen. Da der Array existiert unabhängig davon, was wir tun. Wie sind wir nicht tatsächlich physisch Abhacken des Arrays, oder? Wir stehen noch am Stell wo wir suchen. Ist das sinnvoll? 

ZIELGRUPPE: Ja. 

ANDI PENG: OK. Also, wenn das ist die Voraussetzung für unseren Schleife, was wollen wir innerhalb dieser Schleife? Was sollen wir sein wollen, zu tun? So jetzt, was wir haben a max und min, rechts, wohl hier oben irgendwo erstellt. Wir werden wahrscheinlich wollen um eine Mitte, rechts finden? Wie werden wir zu sein in der Lage, in der Mitte zu finden? Was ist der mathematical-- ZIELGRUPPE: Max und min dividiert durch 2. ANDI PENG: Genau. Ist das sinnvoll? Und denkt ihr, warum wir hat nicht nur use--, warum wir dies taten anstatt das zu tun gerade n geteilt durch 2? Es ist, weil n ein Wert ist das wird so bleiben. Recht? Aber wie wir unsere Mindest anzupassen und Maximalwerte, sie gehen, um zu ändern. Und als ein Ergebnis, unsere Mittel wird sich auch ändern. Also das ist, warum wir wollen, dieses Recht hier zu tun. OK. 

Und dann, jetzt, wir our-- ja gefunden. 

Publikum: Nur eine schnelle question-- wenn Sie min und max sagen, gehen wir davon aus, dass es ist bereits sortiert? 

ANDI PENG: Ja, das ist eigentlich ein Voraussetzung für eine binäre Suche, dass Sie wissen, dass es sortiert. Weshalb Art, in der Sie schreiben Problem, bevor Sie Ihre binäre Suche eingestellt. OK. So, jetzt, da wir wissen, wo unsere Mittelpunkt ist, was willst du hier? 

Publikum: Wir wollen vergleichen daß zu dem anderen. ANDI PENG: Genau. So dass Sie gehen, um zu vergleichen, sind Mitte bis Wert, nicht wahr? Und was sagt uns, wenn wir vergleichen? Was wollen wir danach tun? 

Publikum: Ist der Wert größer ist als die Mitte, wir wollen es abgeschnitten. ANDI PENG: Genau. So dass, wenn der Wert größer als die Mitte, sind wir gehen, um diese zu ändern zu wollen, Mindest- und maxes, nicht wahr? Was wollen wir ändern? Also, wenn wir wissen, dass der Wert irgendwo hier, was denkst du wir ändern? Wir wollen unseren ändern Mindest Mitte zu sein, oder? Und dann anders, wenn es in diesem Hälfte, was wollen wir ändern? 

ZIELGRUPPE: Ihr Maximal. ANDI PENG: Ja. Und dann haben Sie gerade gehen zu halten Looping, nicht wahr? Denn jetzt, nach einer Iteration durch Sie eine max hast hier. Und dann können Sie eine Mitte neu zu berechnen. Und dann kann man vergleichen. Und du gehst zu halten gehst bis die Minuten und die maxes haben im wesentlichen konvergiert. Und das ist, wenn Sie wissen, dass Sie das Ende von ihm getroffen haben. Und entweder haben Sie es gefunden oder Sie müssen nicht an diesem Punkt. 

Macht das Sinn für jedermann? OK. Das ist ziemlich wichtig, da müssen Sie , dies in Ihrem Code heute Abend schreiben. Aber euch einen ziemlich guten haben Sinn dessen, was Sie tun sollten, was gut ist. OK. So haben wir etwa sieben haben Minuten vor dem Abschnitt. Also werden wir darüber zu sprechen Diese pset, die wir tun werden. Also die pset wird in zwei Hälften geteilt. Die erste Hälfte beinhaltet Implementierung eines Fund in dem Sie eine lineare Suche zu schreiben, ein binäre Suche und ein Sortieralgorithmus. 

Das ist also der erste Zeit in einem PSET wobei Wir werden Ihnen Kerle so genannte Verteilungscode, der Code ist dass wir vor, eine schriftliche, sondern nur einige Stücke aufgehört haben damit Sie schriftlich beenden. So euch, wenn Sie dies zu betrachten Code, könnte man wirklich Angst bekommen. Wenn Sie nur wollen, ahh, ich weiß nicht, was das tut, Ich weiß nicht, wie, scheint es, dass so kompliziert, ahh, entspannen. Es ist in Ordnung. Lesen Sie das spec. Die Spezifikation wird Ihnen genau erklären, Was alle diese Programme tun. 

Beispielsweise ist ein Programm generate.c das wird mit Ihrer pset kommen. Sie eigentlich nicht haben, es zu berühren, aber Sie sollten verstehen, was es tut. Und generate.c, ist alles was man tut, entweder Erzeugung von Zufallszahlen oder Sie können es geben, einen Samen, wie ein verabredeten Zahl, die es dauert, und es erzeugt mehr Zahlen. Es gibt also eine spezifische Art und Weise, um Umsetzung generate.c in denen können Sie einfach eine Reihe von Zahlen damit Sie Ihre anderen Methoden zu testen, auf. 

Also, wenn Sie wollen, für Beispielsweise testen Sie Ihre Entdeckung, würden Sie wollen generate.c laufen, erzeugen eine Reihe von Zahlen, und führen Sie Ihre Helfer-Funktion. Ihre Helfer-Funktion ist, wo Sie sind tatsächlich physisch das Schreiben von Code. Und von Helfern denken, wie eine Bibliotheksdatei Sie schreiben, dass find ruft. Und so innerhalb helpers.c, werden Sie do Suchen und Sortieren. 

Und dann wirst du im wesentlichen nur sie alle zusammen. Die Spezifikation wird Ihnen sagen, wie man gesetzt, dass auf der Kommandozeile. Und du wirst in der Lage, ob testen oder Ihr Art und Suche arbeiten. Cool. Hat jemand bereits begonnen und auftretende Probleme oder Fragen haben sie jetzt mit diesem? OK. 

ZIELGRUPPE: Warten. Ich habe eine Frage. 

ANDI PENG: Ja. 

Publikum: So habe ich angefangen, die lineare Suche in helpers.c und es war nicht wirklich funktioniert. Aber dann später, fand ich, dass wir gerade aus haben, um es zu löschen und zu tun binäre Suche. So macht es aus, wenn es nicht funktioniert? 

ANDI PENG: Kurze Antwort ist nein. Aber da wir nicht-- ZIELGRUPPE: Aber niemand tatsächlich überprüft. ANDI PENG: Wir sind noch nie gehen, um das zu sehen. Aber wollen Sie wahrscheinlich zu machen sicher, dass Ihre Such funktioniert. Denn wenn Sie Ihre Linear Suche nicht funktioniert, dann sind die Chancen Ihrer binären Suche wird nicht so gut funktionieren. Weil Sie ähnliche haben Logik in beide. Und nein, es ist nicht wirklich wichtig. Also die einzigen, die Sie drehen in sind eine Art und binäre Suche. Ja. 

Und auch viele Kinder waren versuchen, helpers.c kompilieren. Sie sind nicht wirklich erlaubt das zu tun, weil helpers.c nicht über eine Hauptfunktion. Und damit Sie nur sollten werden tatsächlich kompilieren generieren und zu finden, denn zu finden Gespräche helpers.c und die Funktionen in sich. So dass das Debuggen ein Schmerz in den Hintern. Aber das ist, was wir zu tun haben. Publikum: Sie haben zu machen, oder? ANDI PENG: Sie können einfach machen alle als gut, ja. OK. Das ist es also in dem, was die pset bittet euch alle zu tun. Wenn Sie irgendwelche Fragen haben, fühlen frei, mit mir nach Abschnitt fragen. Ich werde hier für, wie, 20 Minuten betragen. 

Und ja, die pset ist wirklich nicht so schlimm. You guys sollte in Ordnung sein. Diese folgen nur Richtlinien. Art haben ein Gefühl der logischerweise welche sollte geschehen und alles wird gut. Seien Sie nicht zu Angst nicht. Es gibt eine Menge von Code bereits dort geschrieben. Nicht zu viel Angst, sich nicht, wenn Sie dies nicht tun zu verstehen, was das alles bedeutet. Wenn es sich um eine Menge, es ist völlig in Ordnung. Und Bürozeiten kommen. Wir helfen Ihnen, einen Blick zu nehmen. 

Publikum: Mit der zusätzlichen Funktionen Sehen wir aus jenen up? 

ANDI PENG: Ja, das sind im Code. Im Spiel von 15, die Hälfte es ist bereits für Sie geschrieben. Also diese Funktionen sind bereits im Code. Yep. Gut. Nun, viel Glück. Es ist eine ekelhafte Tag. Also hoffentlich euch nicht zu fühlen schlecht bleiben im Inneren und Codierung.