Sprecher 1: Hey everyone! Willkommen zurück in Abschnitt. So froh, dass so viele von euch beiden hier zu sehen, und jeder, der ist online beobachten. Also, wie üblich willkommen zurück. Ich hoffe, dass Sie alle einen schönen hatten Wochenende voller Ruhe, Entspannung. Es war schön gestern. So, ich hoffe Sie die Natur genossen. Also erstmal ein paar Ankündigungen. Grading. Also, die meisten von euch sollte bekommen haben ein E-Mail von mir über Ihre Scratch Pset, sowie Bewertung für Pset 1. Also, nur ein paar Dinge. Achten Sie darauf, check50 in style50 verwenden. Diese sollen zu sein Ressourcen für euch, um sicherzustellen, dass Sie bekommen so viele Punkte wie möglich ohne sie unnötig zu verlieren. Also Dinge wie Stil sind sehr wichtig. Wir werden für sie ab zu nehmen. Einige von euch haben vielleicht schon aufgefallen, dass von Ihrem Pset. Und check50 ist nur eine wirklich einfache Möglichkeit, um sicherzustellen, dass wir tatsächlich zurückkehren, was braucht, um an den Benutzer zurückgegeben werden, und dass alles ordnungsgemäß funktioniert. Auf der zweiten Note, sicherzustellen, dass Ihre Hochladen Dinge in den richtigen Ordner. Es macht mein Leben nur eine etwas schwieriger wenn Sie Pset 2 in Pset 1 laden denn wenn ich Dinge herunterzuladen, sie nicht richtig downloaden weiß. Und ich weiß, es ist ein wenig wackelig in einem System zu gewöhnen, aber einfach super sein Vorsicht, wenn auch nur für mich, so dass, wenn Sie immer E-Mails an wie 02.00 und ich bin Grading. Wenn nicht dazu führen, muss ich schauen rundum für Ihre Pset. Cool. Ich weiß, es ist früh, aber ich völlig unvorbereitet getroffen habe durch einen Aufsatz, der aufgrund dieser Freitag, dass Meine Professoren waren wie, oh yeah. Denken Sie daran, ein müssen Sie Essay am Freitag fällig. Also, ich weiß, niemand mag über Mittelklausuren denke, aber Ihre erste Quiz ist am 15. Oktober, was Oktober wird ab dieser Woche. So könnte es früher sein als Sie erwartet haben ist alles. Also, dass man nicht unvorbereitet, wenn sie geworfen Ich erwähne Abschnitt der nächsten Woche, die oh, Ihr Quiz nächste Woche, ich dachte, Ich würde Ihnen ein wenig mehr zu geben der ein Heads-up jetzt. Also, Ihr Problem zu setzen, die Nummer drei. Wie die Leute gelesen haben die spec aus Neugier? Ok. Wir bekamen ein Paar. Art von unten von den letzten Woche, aber das ist OK. Ich weiß, es war wunderschön aus. Also Break Out. Definitiv, nachdem Sie erledigen lesen Sie noch heute Ihr spec mindestens versuchen wie das Herunterladen von Verteilungscode und Lauf wie der erste Anfangs Sache, die sie Sie bitten,. Weil wir mit Verteilungscode und eine Bibliothek dass wir erst seit using-- --Es nur das zweite Mal, dass wir dieses Pset getan, verrückte Dinge passieren können mit Ihrem Gerät, und Sie möchten, dass finden wollen out now gegenüber später. Denn wenn es am Donnerstagabend ist, oder es ist Mittwochabend und aus irgendeinem Grund Ihr Gerät funktioniert einfach nicht will mit der Bibliothek laufen oder mit der Verteilung Code, das bedeutet Sie können nicht einmal angefangen zu Codierung. Weil Sie nicht überprüfen können um zu sehen, ob es funktioniert. Ihr nicht gonna zu können zu sehen, wenn es kompiliert. Sie möchten die kümmern, früh zu nehmen in der Woche, wenn Sie mich noch eine E-Mail oder einer der anderen TFs, und wir bekommen können diejenigen fixiert. Denn das sind Fragen die gehen, Sie zu stoppen sind von dem jede echte Fortschritte. Es ist nicht wie ein Bug, dass Sie können nur irgendwie überspringen. Wenn Sie Probleme mit Ihrer bist Appliance oder Vertriebscode, Sie wirklich wollen, zu bekommen, dass getroffen Pflege eher früher als später. Also selbst wenn du nicht wirklich Gonna Programmieren beginnen, laden Sie die Verteilung Code, lesen Sie die spec, stellen Sie sicher, Alles ist dort arbeiten. OK? Wenn Sie können einfach tun, ich versprechen euer Leben wird leichter. Und so sind Sie wahrscheinlich um es jetzt richtig machen? Ok. Also, irgendwelche Fragen gibt? Alle logistischen Dinge? Jeder ist gut? Ok. Disclaimer für die von Sie in den Raum und online. Ich werde versuchen, zu wechseln zwischen Powerpoint in der Appliance denn wir werden zu sein, wenn Sie einige Codierung heute aufgrund der großen Nachfrage des anonymen Vorschlag Umfrage schickte ich letzte Woche. Also, wir werden tun, einige Codierung. Also, wenn Sie nie wieder ausziehen wollen auch zu feuern Ihre Geräte, und Sie sollten eine E-Mail bekommen haben von mir, mit einer Beispieldatei. Bitte zögern Sie nicht, das zu tun. Also, wir gehen, darüber zu sprechen GDB, die ein Debugger ist. Es wird Ihnen helfen Art herauszufinden, wo etwas falsch läuft in Ihrem Code. Es ist wirklich nur eine Möglichkeit für Sie zu Schritt durch den Code, wie es geschieht, und in der Lage zu drucken Variablen oder sehen, was wirklich passiert Unter der Haube Verse Ihr Programm nur läuft, ist es wie Verwerfungen, und du, keine Ahnung bist was gerade hier passiert ist. Ich weiß nicht, welche Zeile es gescheitert. Ich weiß nicht, wo es schief ging. Also, GDB wird Ihnen dabei helfen. Auch, wenn Sie sich entscheiden, weiterhin ja, und nehmen Sie 61, es wird wirklich, wirklich dein bester Freund, denn ich kann Ihnen sagen, weil ich durch diese Klasse gehen. Wir werden bei binären aussehen Suche, die, wenn euch erinnern das große Telefonbuch beispiels Schauspiel von Klasse. Wir werden die Umsetzung das, und zu Fuß durch, dass ein bisschen mehr, und dann sind wir durch vier gehen verschiedene Sorten, die Blase sind, Auswahl, Insertion und Zusammenführen. Cool. Also, GDB wie ich bereits erwähnt, ist ein Debugger. Und das sind Art des großen Dinge, die großen Funktionen oder Befehle dass Sie innerhalb GDB verwenden, und ich werde gehen Sie durch eine Demo davon in einer Sekunde. So ist dies nicht nur werde abstrakt bleiben. Ich werde versuchen, es so konkret als für euch möglich. Also, zu brechen. Es wird entweder Pause wie einige Nummer, die stellt eine Zeile in Ihrem Programm, oder Sie können eine Funktion zu nennen. Also, wenn Sie sagen, brechen Haupt, es wird am Haupt zu stoppen, und lassen Sie sich durch diese Funktion zu gehen. Ebenso, wenn Sie einige externe haben funktionieren wie Tausch oder Würfel, dass wir sah letzte Woche. Wenn Sie sagen, brechen einer von denen, wenn Ihr Programm geht, dass, es werde auf dich warten, um sagen, was zu tun ist. Bevor es nur ausführen, so dass Sie könnte tatsächlich innerhalb der Funktion Schritt und sehen, was los ist. Also, das nächste, überspringt gerade über die nächste Zeile, geht über Funktionen. Step. Diese sind alle wenig abstrakt. Also, ich bin gerade dabei, durch sie laufen, aber du wirst sie in den Einsatz in einem zweiten zu sehen. Treten Sie ein in einer Funktion. So als wollte ich sagen, wie bei Swap, wäre es können Sie eigentlich, wenn Sie in wie physisch innerhalb Schritt, Sie verwirren kann mit dieser Variablen, drucken herauszufinden, was sie sind, zu sehen, was los ist. Liste wird buchstäblich nur drucken aus dem umgebenden Code. Also, wenn Sie Art von Vergessen wo Sie in Ihrem Programm haben, oder Sie sich fragen, was los ist um ihn herum, dies nur Ausdruck eines Segments der gerne fünf oder sechs Zeilen um ihn herum. Also, Sie orientieren können darüber, wo Sie sind. Gibt einige Variablen. Also, wenn Sie den Schlüssel wie haben Cäsar, die wir zu betrachten. Man kann sagen, Print-Taste an einem beliebigen Punkt. Es wird Ihnen sagen, was der Wert ist, so dass, vielleicht irgendwo auf dem Weg, Sie Ihren Schlüssel überschrieb. Sie können tatsächlich sagen, dass, weil kann man tatsächlich beobachten diesen Wert. In den Einheimischen, nur Drucke Ihre lokalen Variablen. Also, wenn Sie innerhalb einer Schleife sind, und Sie wollen einfach nur wie zu sehen, oh. Was ist mein Ich? Was ist das Schlüsselwert dass ich zu initialisieren hier? Was ist die Botschaft an dieser Stelle? Es wird einfach alles ausdrucken von denen, so dass Sie nicht einzeln müssen sagen, Print I. Meldung drucken. Print Key. Und dann auf Anzeige. Was das bedeutet ist, wie Sie Schritt durch das Programm, es wird einfach nur sicherstellen, dass es Anzeige einige bestimmte variable an jedem Punkt. Damit Sie also-- --IT ist Art der Verknüpfung, wo Sie müssen nicht, um weiterzumachen wie, oh. Druck Tasten oder Print I. Es ist einfach wird automatisch für Sie erledigen. Also, mit, dass, wir gehen zu sehen, wie das geht. Ich werde versuchen und Schalter zu meinem Gerät. Sehen Sie, wenn ich das tun kann. Alle. Wir sind noch dabei, es zu spiegeln. Es gibt nichts verrückt auf meinem Laptop sowieso. Ok. Dies muss diese sein. Es ist so winzig. Mal sehen, ob wir dies tun können. Ok. Alice ist offensichtlich kämpfen hier nur ein wenig, aber wir werden es in einem momento bekommen. Ok. Wir sind gerade dabei, diese zu erhöhen. Ok. Kann jeder Art sehen, dass? Vielleicht ein bisschen? Ich weiß, es ist ein wenig klein. Man kann nicht ganz herausfinden wie man diese größer. Wenn jemand weiß. Weiß jemand, wie man es größer zu machen? Ok. Wir werden mit ihm rollen. Nicht sowieso egal, denn es ist nur das ist der Code, den Sie Jungs sollten haben. Was ist wichtiger ist der Anschluss hier. Und wir haben hier Warum ist es so klein? Einstellungen. Oh. Wahre Ike. Wie ist das? Von dort. Ist das besser für alle? Ok ,. Cool. Sie wissen, wenn Sie in einer CS sind Klasse technische Schwierigkeiten sind so eine Art Teil the-- Also, lasst uns klar, dass dies. Ok. Also, hier im Schnitt, was wir hier hatten. Caesar ist eine ausführbare Datei. Also machte ich es. Also, das ist eine Sache, mit GDB realisieren dass es funktioniert nur auf ausführbare Dateien. So können Sie nicht führen Sie es auf einer Dotsy. Sie müssen tatsächlich machen sicher, dass Ihr Code kompiliert, und dass sie tatsächlich ausgeführt werden. Also, stellen Sie sicher, dass, wenn es nicht kompilieren, bekommen es zu kompilieren, so dass Sie Art von durch sie laufen. Also, um GDB starten, alles, was Sie tun, Gloria Typ GDB, und dann erst der Datei, die Sie wollen. Ich falsch schreiben immer Caesar. Aber Sie sicherstellen möchten, da es eine ausführbare, TI dot Flash, so dass bedeutet du gehst zu laufen CSI wirst du auszuführen sind diese Dateien entweder mit dem Debugger. Ok. Also, Sie das tun, erhalten Sie diese Art von Kauderwelsch. Es ist nur alles über Debugger. Sie haben nicht wirklich zu Sorgen über es jetzt. Und wie Sie sehen, dieses haben wir offene Pars, BIP, in der Nähe Pars, und nur irgendwie aussieht unsere Befehlszeile, oder? Also, was wir wollen do-- SO, das erste, was ist, dass wir wählen möchten ein Ort, um sie zu brechen. So gibt es eine Fehler in diesem Caesar Programm dass ich vorstellen, dass wir werden es herausfinden. Was es tut, ist es die Eingabe erfolgt Barfoo in Großbuchstaben, und aus irgendeinem Grund es nicht A. ändern Er lässt nur sie allein, alles andere ist richtig, aber der zweite Buchstabe A bleibt unverändert. Also, wir werden versuchen, herauszufinden, warum das so ist. Also, das erste, was Sie in der Regel tun wollen, wann immer Sie auf GDB starten ist herauszufinden, wo es zu brechen. So Caesar ist ein ziemlich kurzes Programm. Wir haben nur eine Funktion, nicht wahr? Was war unsere Funktion in Caesar? Es gibt nur eine Funktion, Main oder? Main ist eine Funktion für alle Programme. Wenn Sie nicht über Haupt, könnte ich Seien Sie ein wenig besorgt gerade jetzt, aber ich hoffe, Sie alle Haupt drin hatte. Also, was wir tun können, ist, dass wir nur brechen Main, einfach so. So heißt es, OK. Wir setzen unsere Haltepunkt dort. So, jetzt ist die Sache zu erinnern Caesar nimmt ein Kommandozeilenparameter rechts und wir haben nicht das in der noch nicht fertig. Also, was Sie tun, ist, wenn Sie tatsächlich gehen zu laufen das Programm, jedes Programm, das Sie in GDB läuft, die Befehlszeile muss Argumente, du bist zur Eingabe gehen beim ersten Ausführen starten. Also, in diesem Fall, wir tun Führen Sie mit einem Schlüssel von drei. Und es wird tatsächlich beginnen. Also, wenn Sie hier sehen, haben wir Wenn RC nicht gleich 2 ist. Also, wenn euch alle die Datei, die ich schickte up Sie sehen, dass das ist, wie die erste Zeile unserer Hauptfunktion, oder? Es ist zu überprüfen, ob wir die richtige Anzahl von Argumenten. Also, wenn Sie sich fragen, wenn RC korrekt ist, Sie können etwas wie Print RC tun. RC zwei ist, das ist was wir erwartet hatten, nicht wahr? Also, können wir gehen nächstes und weiter durch. So haben wir einige Schlüssel dort. Und wir können Sie ausdrucken unser Schlüssel um sicherzustellen, dass ist richtig. Interessant. Nicht ganz das, was wir erwartet hatten. Also, eine Sache zu erkennen, mit GDB Auch ist dass es nicht, bis Sie wirklich getroffen Als nächstes, dass die Linie, die Sie gerade gesehen tatsächlich ausgeführt wird. So, in diesem Fall Key wurde noch nicht zugeordnet. Also, ist Key einige Müll Wert dass Sie sehen auf der Unterseite befindet. Negative $ 120-- --Es eine Milliarde und etwas seltsame Dinge richtig? Es ist nicht der Schlüssel, der uns erwartet. Aber wenn wir getroffen Weiter, und dann werden wir versuchen und Print-Taste, es ist drei. Alle sehen, dass? Also, wenn Sie etwas zu bekommen dass Sie wie sie sind, zu warten. Dies ist völlig falsch, und ich weiß nicht, wie dies geschehen würde, weil alles was ich will tun müssen, ist eine Nummer, eine Variable, versuchen schlagen nächstes versuchen Druck es wieder, und sehen, ob das funktioniert. Weil es nur geht, um auszuführen und etwas, nachdem Sie tatsächlich zuweisen Treffer nächster. Sinnvoll, alle? Uh huh? Sprecher 2: Wenn Sie zufällig Zahlen, was bedeutet das? Sprecher 1: Es ist nur zufällig. Es ist nur Müll. Es ist nur etwas, das Ihre Computer nach dem Zufallsprinzip vergeben. Cool. So, jetzt können wir durch bewegen, und so Jetzt haben wir diese Klartext GetString. Also, lassen Sie mich nur vorstellen, was wird passieren, wenn wir getroffen Next hier. Unsere GDB Art verschwindet, oder? Das ist, weil GetString wird nun die Ausführung, nicht wahr? Also, als wir sahen, Klartext ist gleich GetString, offene Pars und Pars, und wir schlagen nächstes hat, dass eigentlich jetzt ausgeführt. Also, es wartet uns zur Eingabe etwas. Also, wir fahren nach Eingang geht unsere Nahrung, die ist, was es in Ermangelung wie gesagt und sagt nur, dass es beendet die Ausführung, dass der geschlossene Klammer bedeutet, es ist Verlassen entlastet wird. So können wir Treffer nächster, und jetzt, wie ich bin sicher, Sie alle sind von Caesar vertraut, das ist, was ist diese Linie tun. Es ist für Int I gleich 0, N gleich Strlen, Klartext, und dann I kleiner als n, I, und, und. Was ist diese Schleife tun? Öffnen Sie Ihre Nachricht. Cool. Also, lassen Sie uns beginnen zu tun. Also, sollten diese Bedingung entsprechen, für unsere erste? Wenn es ein B, es ist Klartext I. Wir erhalten Sie Informationen über unsere Einheimischen. Also, ich Null, und wenn sechs, die wir erwarten, und unsere wichtigsten ist drei. Alle, die Sinn machen, oder? Diese Zahlen sind alle genau, was sie sein sollte. Also, summen? SPEAKER 3: Ich habe Zufallszahlen für meine. Sprecher 1: Nun, wir können --wir check-- kann etwa, dass in einem zweiten chatten. Aber man sollte immer diese. Also, wenn wir eine Kapital B für unsere erste, Dieser Zustand sollte es zu fangen, oder? Also, wenn wir getroffen nächstes sehen wir dass dieses Falls tatsächlich ausführt. Denn wenn Sie mitlesen entlang in Ihrem Code, diese Linie hier, wo Klartext I Mit diesem Rechen ersetzt, nur ausgeführt, wenn die If Bedingung ist richtig oder? GDB ist nur zu zeigen, Dinge, die tatsächlich ausgeführt werden. Also, wenn dies Wenn Bedingung nicht erfüllt wurde, ist es gerade dabei, in die nächste Zeile springen. OK? So haben wir das. Diese Halterung bedeutet, es ist entlastet wird jetzt geschlossen. Also, es geht wieder von vorne anfangen. Einfach so. So, dass wir Informationen zu erhalten über unsere Einheimischen hier, und wir sehen, dass unsere erste Brief, rechts geändert? Es ist jetzt ein E, wie es sein sollte. So können wir weiter auf. Und wir haben dieses Kontroll. Und diese Prüfung sollte funktionieren, oder? Es ist A. Es sollte geändert werden drei Buchstaben nach vorn. Aber wenn Sie, wir merken bekommen etwas anderes. Also in diesem Fall hier, fing es , und so diese Zeile ausgeführt wird, die unsere B. modifiziert Aber im hier vorliegenden Fall wir, dass es einfach übersprungen es, und ging auf die [? L Siff. ?] So etwas ist da los. Was das erzählt, ist, dass, wir wissen, dass es hier zu fangen, aber es ist nicht. Kann jemand sehen, was unsere Problem ist in dieser Zeile? Es ist eine sehr kleine Sache. Und man konnte auch auf den Code schauen. Es ist auch line-- vergessen, was Linie ist es in sind-- aber es ist in der [unverständlich]. Ja? Lautsprecher 4: Es ist an der mehr als Seite, wenn Sie es in dem Buch zu lesen. Sprecher 1: Genau. Also, der Debugger nicht sagen Sie das, aber der Debugger könnten Sie auf eine Linie zu bekommen dass Sie wissen, funktioniert nicht. Und manchmal, wenn vor allem später im Semester, wenn Sie mit einem hundert, Umgang hundert paar Zeilen Code, und Sie weiß nicht, wo es andernfalls, dies ist eine gute Möglichkeit, es zu tun. So fanden wir unsere Fehler. Sie können es in Ihrer Datei zu beheben, und dann könnte man es erneut ausführen, und alles wäre perfekt. Und die größte Sache ist dies kann scheinen, wie, OK. Ja. Cool. Sie wussten, was Sie suchen. So wusste man, was zu tun ist. GDB kann super hilfsbereit, weil Sie sein ausdrucken können all diese Dinge, die Sie wollte nicht. Es ist viel nützlicher als printf. Wie viele von euch nutzen wie printf-Anweisungen um herauszufinden, wo ein Fehler war, nicht wahr? Also, mit diesem können Sie nicht tun müssen immer wieder zurück, und gerne kommentieren in Printf oder auskommentieren, und herauszufinden, was sollten Sie den Druck. Diese eigentlich nur ermöglicht es Ihnen, Schritt durch, ausdrucken Dinge wie du durchmachst, so können Sie beobachten, wie sie in Echtzeit zu ändern, wie Ihr Programm ausgeführt wird. Und es sieht ein wenig dauern etwas gewöhnungsbedürftig. Ich würde empfehlen, nur irgendwie des Seins ein wenig frustriert mit ihr für jetzt. Wenn Sie eine Stunde über die verbringen nächste Woche lernen, wie man GDB verwenden, Sie sparen sich so viel Zeit später. Und wörtlich. wir sagen dies Menschen jedes Jahr, und ich erinnere mich, als ich die Klasse, ich war wie, ich werde in Ordnung sein. Nein. Pset 6 kam auf und ich war wie, Ich werde lernen wie GDB verwenden, weil ich nicht wissen, was hier vor sich geht. Also, wenn Sie die Zeit so nehmen verwenden Sie es auf kleinere Programme dass Sie sein wirst Arbeiten an, wie die Arbeit durch so etwas wie Visionäre, wie diese. Oder wenn Sie zusätzliche Übung wollen, bin ich sicher Ich könnte mit fehlerhafte Programme, für Sie debuggen, wenn Sie möchten. Aber wenn man nur etwas Zeit nehmen, um daran gewöhnt, nur spielen, um mit ihm, es wird wirklich gute Dienste leisten. Und es ist wirklich eine der die Dinge, die Sie gerade müssen versuchen, und sich die Hände schmutzig mit, bevor Sie wirklich verstehen. Ich wirklich nur verstanden es einmal Ich musste Debug Dinge mit ihm, und es ist viel schöner, eine Vorstellung davon haben, wie man eher früher als später zu debuggen. Ok. Cool. Ich weiß, das ist eine Art, wie ein Crash-Kurs in GDB, und ich werde auf jeden Fall funktionieren auf immer diese zu größeren nächste Mal freuen. Cool. Also, wenn wir gehen zurück zu unseren Powerpoint. Wird das funktionieren? Awh. Ja. Ok. Also, wenn Sie jemals brauchen einem diese wiederum gibt es die Liste. So Binary Search, die jeder erinnert sich an den großen Schauspiel David Ripping Telefon-Bücher in zwei Hälften. Ich glaube nicht wirklich das Telefon-Bücher mehr, denn wie, wo wollen Sie bekommen Telefon-Bücher in diesen Tagen? Ich weiß wirklich nicht,. Die binäre Suche. Erinnert sich noch jemand wie Binäre Suche funktioniert? Wer überhaupt? Ja? Lautsprecher 5: Sie wissen, wann Sie bei der die Hälfte aussehen es würde, basierend auf dem, und der anderen Hälfte loszuwerden. SPEAKER1 Genau. Also, Binäre Suche, es ist irgendwie A-- --wir gerne nennen es teilen und zu erobern. Also, was du tun wirst ist Sie in der Mitte zu suchen, und Sie werden sehen, ob es passt was Sie suchen. Und wenn es das nicht tut, dann Sie versuchen, herauszufinden, ist es werde gelassen werden die Hälfte oder die rechte Hälfte. Also, das könnte sein, wenn Sie suchen auf etwas, das alphabetisiert ist, Sie sehen, oh. Hat Allison vor M gekommen? Ja. Also, wir sind zu gehen Blick auf die erste Hälfte. Oder es könnte, wie mit Zahlen. Alles, was du kannst vergleichen kann sortiert werden. Sie können binäre Suche weiter verwenden. Also, jemand erinnern diese Grafik oder was das ist? Es ist Asymptotische Komplexität. Also, dieser Graph nur beschreibt, wie lange es Sie gelangen auf ein Problem zu lösen, wie Sie die Anzahl der Dinge, zu erhöhen dass Sie verwenden. Also, wir haben N, die lineare Zeit ist. Wenn N als zwei, die leicht ist besser, wächst noch super schnell. Und dann haben wir Einloggen, was ist was wir als Binary Search. Wenn wir feststellen, wie Ihr Problem wird viel und viel größer, die Zeit, die Sie, es zu lösen nicht wirklich so viel zu erhöhen. Es ist wie vergleichbare hier am Anfang. Du bist wie, OK. Alles hier ist nicht wirklich Gleichgültig, welches wir verwenden, aber Sie bekommen bis zu einer Million, eine Milliarde. Du versuchst, some-- --you're finden versucht, eine Nadel im Heuhaufen zu finden. Ich denke, dieses Problem soll. Sie möchten diese Komplexität nicht linear, da für alles, was Sie wissen Ihre gonna werden durch die Suche jede einzelne Nadel, was von Heu, versucht, für Ihre Nadel aussehen. Und das ist nicht zu Spaß meiner Meinung nach. Ich mag schnell. Ich mag effizient. Und als fleißige Studenten Sie Jungs sind, weißt du intelligenter zu arbeiten, nicht härter Typ Sache, wie Sie können bis diese Algorithmen. Also, wir gehen zu Fuß durch nur ein kleines Beispiel. Ich glaube, Sie Jungs haben sollte eine Hand auf Binäre Suche, aber falls jemand ein wenig ist Fuzzy, möchte es zu verstärken, wir werden einfach gehen durch ein Beispiel hier. Also suchen wir nach, wenn auf der Suche das Array enthält sieben. Also, erste, was wir tun, ist schauen Sie in der Mitte, oder? Und auch du gehst zu codierenden bist Binäre Suche in nur einer Sekunde. Also, es wird Spaß machen. Also haben wir in der Suche Mitte kleine Arrays 3. Enthält 3 gleich 7? Nicht. Es ist sechs. So ist es weniger als oder mehr als sieben? Weniger als. Ja. Nice job Jungs. Ich fühle Ich mag ich sollte haben Süßigkeiten, weil ich wollen, um es in den Werften werfen. Es ist, was ich in der nächsten Woche zu tun. Es wird euch scharf zu halten. Also, wir wegwerfen, dass ersten Hälfte, nicht wahr? es war weniger als. wir wissen, dass alles, was auf dieser linken Seite wird kleiner sein als das, was wir eigentlich suchen. Also, es gibt keine Notwendigkeit, achten Sie darauf. Vergiss es einfach. So, jetzt schauen wir auf unserer rechten Seite, und wir freuen in der Mitte dort, und jetzt ist es neun. So, 9 ist-- --Everyone? Größer als das, was wir sind auf der Suche nach, oder? Also, wir gehen zu werfen alles weg nach rechts. So. Nun sind alle verließen wir mit einer ist. So prüfen wir, das ist man sich, was wir suchen? es ist. Wir fanden, was wir wollten. Also wir sind fertig. Bilineare suchen. Und wenn Sie, wir bemerken, hatte sieben Eingänge gibt. Es dauerte nur wie drei Mal, aber wenn Sie wie ein Milliarden tut, Sie Jungs wissen, wie viele Schritte es würde nehmen, wenn wir hatten vier Milliarden Dinge? Irgendwelche Vermutungen? Es ist 32. 32 Schritte, um etwas zu finden in vier Milliarden Elementanordnung, weil von Zweierpotenzen. Also zwei ist bis 32, ist zu vier Milliarden Euro. So ziemlich verrückt, wie du bist immer noch in wie eine ziemlich kleine Anzahl von Schritten etwas in finden vier Milliarden Elementen. Also in diesem Sinne, wir sind werde diesen Code so euch kann eigentlich Art sehen, wie das funktioniert. Alles klar, so euch kann codieren. Ich werde euch lassen sprechen für ein wenig. Lernen Sie Menschen um Sie wissen, das ist, was jemand wollte von den letzten Abschnitt. So lernen Sie die Menschen um Sie herum wissen. Sprechen Sie für ein wenig. Und alles, was ich von dir will Jungs ist jetzt nur versuchen, einen Umriss eines Pseudocodes zu erstellen. OK? Whoa. Alles was ich will von euch ist du bist gerade dabei, in diesem Fall, während zu füllen. So habe ich diese oberen gesetzt und die untere Grenze der stellen den Anfang und Ende unserer Array. Und Sie gehen, um tatsächlich Schleife durch und herauszufinden, was wir in dieser while-Schleife zu tun. Also, wenn Sie heraus out-- kann ich ein Hauch sind-- was sind die Fälle dass wir hier? Also, wenn Sie herausfinden, die wollen Fällen werden wir solche Pseudo und dann werden wir tatsächlich codieren. Und es geht um sein, ich denke, hoffentlich ist das dann ein wenig leichter, als Sie erwarten. Denn es ist nicht so viel Code, tatsächlich, das ist wirklich cool. Mm-hm? STUDENT: [unverständlich]? LEHRER: Ja. Es war etwas in der Mitte zu finden. STUDENT: So können wir dafür verwenden. Ok. LEHRER: Perfect. Also das ist das erste, was wir tun müssen. So finden Sie die Mitte. Großartig. So haben Sie eine Vorstellung davon haben, wie wir tatsächlich in der Mitte mit dem Code finden? STUDENT: Ja. n mehr als 2? LEHRER: Also n über 2. So eine Sache zu erinnern ist, dass Ihre oberen und unteren Grenzen ändern. Wir halten gende den Teil des Arrays wir uns auf. So n über 2 funktioniert nur, für das erste, was wir tun. So nehmen oberen und unteren berücksichtigt, wie könnten wir diese mittlere Element zu bekommen? Weil wir wollen, dass die Mitte zwischen oberen und unteren, nicht wahr? Mm-hm? STUDENT: [unverständlich]. LEHRER: Also müssen wir einen Mittelweg. Und es wird oberen zzgl unteren als 2 sein. Genial. Dort gehen wir. Eine Zeile nach unten. Ihr seid auf dem Weg. So, jetzt, da wir unsere Mitte, was wollen wir tun? Nur im Allgemeinen. Sie müssen nicht, um es zu codieren. Ja. STUDENT: [unverständlich]? LEHRER: So ist es und weil Sie Ermitteln des Durchschnitts zwischen den beiden von ihnen. Also, wenn Sie von ihnen denken, als eine Art der von den Seiten zunimmt, denken Sie darüber nach, wie Sie nähern der mittlere, möchten Sie so. Also, wenn Sie auf beiden Seiten die waren Mitte, und wir haben wie 5 und 7. Wenn Sie sie Sie addieren erhalten 12, um 2 dividieren Sie ist 6. Manchmal ist es schwer, erklären, warum das funktioniert, aber wenn Sie durcharbeiten ein Beispiel manchmal, es wird Ihnen helfen, herauszufinden, ob es sollte plus oder minus ist. Ja. STUDENT: [unverständlich] genau in der Mitte wenn sie einen Fall, wo hatten es gibt eine Menge von kleineren Zahlen und wie einer großen Zahl? LEHRER: Also alles was Sie brauchen ist die Mitte des Arrays. Also, wenn Sie ein paar kleine Zahlen hatten und dann ein wirklich große Anzahl am Ende, spielt es keine Rolle. Alles was zählt ist, dass sie, die Sie gerade sortiert möchte in der Mitte aussehen das Array, weil du bist immer noch Schneiden Sie Ihr Problem in der Hälfte. Cool. So, jetzt, dass wir die Mitte, was machen wir als nächstes? STUDENT: Vergleichen. LEHRER: Die zu vergleichen. So vergleichen mittleren bis value_wanted. Cool. So können Sie bis hier sehen wir dieser Wert wollen wir hier oben. Vergessen, das ist ein Array. Also Mitte bezieht sich auf den Index. So wollen wir Werte von Mitte zu tun. Vergessen Sie nicht, wenn Sie wollen zu, Doppel equals vergleichen. Sie tun einzigen gleich du bist gerade dabei, es neu zuzuweisen, und natürlich ist es gehen, um den Wert Sie wollen. Also tun Sie das nicht. Also, wir werden sehen, ob die Werte in der Mitte ist gleich dem Wert, den wir wollen. Vergessen Sie nicht Ihre Zahnspange. Dropbox sollten weggehen. Also, was tun wir in diesem Fall tun? Wenn es was wollen wir zurückkehren wollen? Wir versuchen zu sagen. STUDENT: Drucken aus. LEHRER: Nun, wir wollen nicht ausdrucken. Das ist also ein bool hier, so dass wir want true oder false zurück. Wir sagen, ist diese Nummer ein [? RRA? ?] Also, wenn es heißt, wir bringen Sie ihn einfach wahr. Wenn ich kann wahr buchstabieren. STUDENT: Warum würden Sie nicht Null zurück? LEHRER: so konnte man Null zurück, wenn man wollte. Aber in diesem Fall, weil unsere Funktion gibt einen bool, wir brauchen, um zurückzukehren entweder wahr oder falsch. STUDENT: Wenn man sagen Booleschen Ausdruck, können Sie es gleich falsch gesetzt? Wie, wenn ich sagen will, wenn diese Bedingung nicht erfüllt ist, wie ist Ober gleich falsch. Wird es, wenn Sie nur zu verstehen legte falsche auf der anderen Seite? LEHRER: Yeah. Also eigentlich, wenn Sie immer etwas zu tun wie ist oberen oder niedriger ist, die wahr oder falsch zurück und es ist eigentlich schlechter Stil, sagen wir gleich gleich wahr oder equals gleich falsch. Sie wollen dieses Ergebnis nutzen als sich als Ihr Scheck. Nicht das, was ich wollte. Das ist, was ich wollte. So im Fall der du fragst über so etwas wie speichern Sie diese in c. Wenn wir also int main (void) und so etwas wie dieses. Und Sie haben, wenn obere ist einiger Eingangs und du bist gefragt, ob Sie tun können so etwas? Richtig? Student: Ich habe versucht es zu tun [unverständlich]. Denn wenn it's-- LEHRER: Richtig. Sie wollen dies falsch sein, oder? STUDENT: Ja. LEHRER: Also in diesem Fall, dass Sie wollen, dass es ausgeführt wird, wenn es nicht wahr ist. Also die coole Sache, die Sie tun, gibt es diese. Also denken Sie daran Ausrufe Punkt negiert Dinge? Er sagt, [unverständlich] bedeutet nicht. Also, wenn wir uns nur dieser Teil hier, würden Sie sagen, dass ausgewertet wird falsch, wie Sie es wollen. Nicht falsch ist wahr was bedeutet dies auszuführen. Ist das sinnvoll? STUDENT: Ja. LEHRER: Awesome. Ok. So dass wir nur zurückkehren konnte in diesem Fall wahr. So, jetzt haben wir zwei andere haben Fälle, in diesem Fall. Was sind unsere beiden anderen Fällen? Lassen Sie uns gerade tun es auf diese Weise. Lassen Sie uns also mit anderen starten wenn Werte in der Mitte kleiner als der Wert, den wir wollen. Also unsere Wert in der Mitte weniger ist als der Wert, den wir suchen. Also die verpflichtet Sie tun denke, wir aktualisieren möchten? Obere oder untere? Ober? Also die Seite des Arrays werden wir auf der Suche an? STUDENT: Je niedriger. LEHRER: Wir werden wir auf der Suche auf der linken Seite. So else if wenig Wert geringer ist. Also Ihr Mittelwert hier weniger als das, was wir wollen. Also, um das nehmen wir wollen rechten Seite unser Angebot. Also sind wir zu gehen aktualisieren unsere untere Schranke. Also werden wir unsere Unter zuweisen. Und was denken Sie, niedriger sein sollte? STUDENT: Der mittlere Wert? LEHRER: Also das mittlere value-- STUDENT: Plus 1. LEHRER: --plus 1. Kann mir jemand sagen, warum wir haben, dass plus 1? STUDENT: [? Kein Wert?] ist gleich zu ihm. LEHRER: Richtig. Weil wir wissen bereits, dass unsere mittlere Wert ist ungleich es und wir wollen es ausschließen möchten von allen nachfolgenden Such. Wenn Sie vergessen, dass plus 1, dieses auf unbestimmte Zeit gefallen Schleife. Und Sie werden nur in ein gefangen werden Endlosschleife und dann wirst du segfault und die Dinge schlecht. Also immer darauf achten, dass Sie nicht einschließlich dem Wert, den Sie gerade sah. Also kümmern wir uns, dass mit einem plus 1. So, jetzt haben wir unsere letzte Bedingung die ich immer für die Sicherheit willen Sie können hier überprüfen, sonst, wenn der Wert bei der mittlere größer als der Wert ist wir wollen. Das heißt, wir wollen die linke Hälfte. So das man werden wir aktualisieren? Ober. Und was ist dies einer werde gleich? Naher minus 1, da, natürlich wollen wir um sicherzustellen, dass wir nicht Suche in diesem mittleren Wert wieder. Und dann haben wir es. Das ist es. Das ist alles, binäre Suche ist. Es ist nicht so schlecht, oder? Es ist wie 10 Zeilen Code mit weißen Raum. So sehr mächtig, sehr nützlich, werden Sie verwenden es in einem Ihrer späteren psets. Vielleicht nicht dieses, aber später. So lernen. Liebe es. Es wird Ihnen gut zu behandeln. Also weiß jemand welche haben Fragen über binäre Suche? Ja. STUDENT: Spielt es eine Rolle ob Ihr n gerade oder ungerade? LEHRER: No. Weil wir es gegossen, um die Mitte als ein int, wird es nur abzuschneiden. So wird es eine ganze Zahl zu bleiben und es wird schließlich durch alles zu sortieren. So müssen Sie nicht zu befürchten, dass. Jeder gut? Genial. Cool. So bekam diese euch. Slideshow. So wie wir redeten, ich weiß David erwähnt Komplexität Laufzeiten. Also im besten Fall ist es nur ein, die wir konstante Zeit nennen. Kann mir jemand sagen, warum das so sein könnte? Welche Art von Szenario würde das zur Folge haben? Mm-hm. STUDENT: [unverständlich] first-- LEHRER: Also das mittlere wobei der erste Element, das wir kommen, oder? Also entweder eine Anordnung von einer oder was auch immer wir für nur suchen passiert genau in der Mitte sein. Also das ist unsere beste Fall. Sie erhalten in echte Probleme, wahrscheinlich nicht werde, dass oft zu erreichen [unverständlich]. Was ist mit unseren schlimmsten Fall? Unsere schlimmsten Fall ist log n. Und daß, um mit der gesamten zu tun Potenzen von zwei, was ich darüber gesprochen. Also im schlimmsten Fall würde es bedeuten, dass wir, um das Array zu fällen bis es ein Element von einem. Also mussten wir es in der Hälfte fällen so oft wie wir nur konnte. Das ist, warum es ist log n, weil Sie halten gerade durch zwei geteilt. Also Annahmen, Dinge, die Sie müssen wissen, ob Sie überhaupt werde eine binäre Suche verwenden. Ihre Elemente müssen sortiert werden. Sie müssen sortiert werden, weil das ist der einzige Weg, kann wissen, ob Sie in der Lage sind daran zu werfen Hälfte. Wenn Sie diese wirre Tasche hatte von Zahlen und du sagst, OK, ich werde die Mitte zu überprüfen Nummer und die Nummer Ich suche nach ist geringer als die, ich bin gerade dabei willkürlich werfen die Hälfte. Sie würden nicht wissen, ob Ihre Zahlen in dieser anderen Hälfte. Ihre Liste muss sortiert werden. Wie gut, dies auch sein mag gehen voran ein wenig, aber Sie müssen mit wahlfreiem Zugriff haben. Sie müssen in der Lage zu sein, nur gehen Sie zu diesem mittleren Element. Wenn Sie durchlaufen haben durch etwas oder es dauert zusätzliche Schritte um zu diesem mittleren Element zu bekommen, es ist nicht log n mehr, weil Sie hinzufügen mehr Arbeit hinein. Und das wird ein wenig zu machen mehr Sinn in zwei Wochen, aber ich nur irgendwie wollte Vorwort geben euch eine Vorstellung von dem, was zu kommen. Aber diejenigen, die beiden sind Wichtige Annahmen dass Sie für eine binäre Liste. Stellen Sie sicher, es ist sortiert. Das ist die große für euch jetzt. Und dass wir in zu gehen der Rest unserer Sorten. Also vier sorts-- Blase, Insertion, Auswahl und Zusammenführen. Sie sind alle ziemlich cool. Wenn euch entscheiden, CS 124 zu nehmen, Sie über alle möglichen Arten zu lernen. Und wenn Sie ein XKCD Fan bist, gibt ist eine wirklich coole Comic über wie wirklich unwirksam Sorten, die ich empfehlen Sie gehen, zu betrachten. Einer von ihnen ist wie Panik Art, die ist wie, oh nein, zurück zufälligen Anordnung. Shutdown-System. Zu verlassen. So geeky Humor ist immer gut. Also hat jemand erinnern Art der wie nur eine allgemeine Vorstellung wie Bubble-Sort arbeitet. Sie erinnern sich? STUDENT: Ja. LEHRER: Go for it. Student: Sie durchmachen und wenn es größer ist, dann haben Sie die beiden tauschen. LEHRER: Mm-hm. Genau. Sie haben also nur durch Iteration. Sie überprüfen zwei Zahlen. Wenn die davor ist größer als die danach einfach tauschen sie damit in auf diese Weise alle höheren Nummern Blase gegen Ende der Liste und all die niedrigeren Zahlen Blase nach unten. Hat er euch die kühle Sound-Effekt Sortier Video? Es ist irgendwie cool. So wie Robert sagte nur, den Algorithmus dass Sie nur Schritt durch die Liste, Vertauschen der benachbarten Werten wenn sie nicht in Ordnung. Und dann nur immer wiederholen bis Sie nicht machen keine Swaps. Also nicht schlecht, oder? Also müssen wir nur ein kleines Beispiel hier. Es wird also zu sortieren sie in aufsteigender Reihenfolge. Wenn wir also über den ersten zu gehen Zeit, durch acht freuen wir und sechs sind offensichtlich nicht in Ordnung ist, tauschen wir sie. So sehen Sie die nächste. Acht und vier nicht in Ordnung. Tauschen sie. Und dann acht und zwei, tauschen sie. Dort gehen wir. Also nach dem ersten Durchgang, die Sie wissen, dass Ihre größte Zahl wird sich den ganzen Weg sein an der Spitze, weil es einfach werde ständig größer als alles andere und es nur geht zu brodeln bis hin zu dem Ende gibt. Macht das Sinn macht, alle? Cool. Also schauen wir auf unserer zweiten Durchgang. Sechs und vier, Schalter. Sechs und zwei, Schalter. Und jetzt haben wir ein paar Dinge in Ordnung. So wird für jeden Pass, dass wir machen durch unsere gesamte Liste, wir wissen, dass wie so vielen Zahlen am Ende wird sortiert worden sind. Also machen wir einen dritten Durchgang, Das ist ein Swap. Und dann auf unserer vierten passieren, wir haben null Slots. Und so wissen wir, dass unsere Array sortiert wurde. Und das ist die große Sache mit Bubble-Sort. Wir wissen, dass, wenn wir null Swaps, dass bedeutet, dass alles steht in völligem Ordnung. Es ist eine Art, wie wir zu überprüfen. Also wir gehen aber auch auf Blasen codieren Art, die auch nicht so schlimm. Keiner von ihnen sind so schlecht. Ich weiß, sie ein wenig beängstigend erscheinen kann. Ich weiß, als ich die Klasse, auch wenn ich wurde die Klasse für den Unterricht das erste Mal im letzten Jahr, Ich war wie, wie mache ich das? Es macht Sinn, in der Theorie, sondern wie wollen wir eigentlich tun? Deshalb möchte ich auch zu Fuß gehen durch Code mit euch hier. So habe ich eine Pseudocode für euch dieses Mal. Also einfach bedenken Sie dies als Wir sind dabei, den Übergang über. Also haben wir etwas Zähler, verfolgt die Spuren unserer Swaps, denn wir müssen sicherstellen, dass dass wir prüfen, ob. Und wir durchlaufen das gesamte Array wie wir gerade getan mit diesem Beispiel. Wenn das Element vor größer als das Element nach dem, wo wir sind, wir tauschen sie und wir erhöhen unsere Zähler, denn sobald wir tauschen, wollen wir lassen unsere Gegen wissen. Haben Sie noch Fragen gibt? Etwas scheint lustig hier. STUDENT: Haben Sie die Zähler auf Null gesetzt jedes Mal, wenn Sie durch die Schleife zu gehen? Weißt du nicht weitermachen zurück, jedes Mal Null? LEHRER: Nicht unbedingt. Also, was passiert ist, dass wir hier durch zu gehen. So zu tun, während, denken Sie daran, diese wird einmal ohne fehler auszuführen. Also es geht um den Satz Zähler gleich Null ist, dann, es wird durch Iteration. Wie es durch läuft, es wird Gegen aktualisieren. Da es Zähler aktualisiert, wenn es fertig ist, wenn es das Ende der Anordnung erreicht hat, wenn unsere Liste noch nicht sortiert, Zähler wird aktualisiert wurden. So dann prüft er den Zustand und sagt, OK, ist Zähler größer als Null ist. Wenn es ist, es wieder tun. Sie wollen, so dass, wenn Sie zurückgesetzt durchlaufen, ist Zähler gleich Null. Wenn Sie über einen sortierten gehen Array, ändert sich nichts, dies fehlschlägt, und Sie Rückkehr der sortierten Liste. Macht das Sinn macht? STUDENT: Es könnte in ein wenig. LEHRER: OK. Wenn es irgendwelche anderen Frage, die aufkommt. Ja. STUDENT: Was würde die Funktion für das Vertauschen der Elemente? LEHRER: So können wir eigentlich schreiben dass, wenn wir gehen, um nun mit der rechten. Cool. Also in diesem Sinne, ist Alison gehen zurück zum Gerät einzuschalten. Es wird Spaß machen. Und wir haben unsere schöne Bubble-Sort Sache hier. So habe ich schon Radfahren durch die Anordnung. Wir haben unsere Swaps gleich Null sind. So zum Tauschen benachbarter wollen wir Elemente, wenn sie nicht in Ordnung. Das erste, was wir brauchen, um Sie wird durch unsere Arrays durchlaufen. So wie Sie denken, wir könnten durchlaufen unser Angebot? Wir haben für und i gleich 0. Wir wollen i kleiner sein als n minus 1 minus k. Und das werde ich in einem zweiten zu erklären. Das ist also eine Optimierung hier, wo, erinnere mich, wie ich sagte, nach jedem Durchlauf durch das Array wir wissen, dass was auch immer on-- ist So nach einem Durchgang wir wissen, dass diese sortiert. Nach zwei Durchgängen wir wissen dass dies alles sortiert. Nach drei Durchgängen wir weiß, das ist sortiert. So, wie ich bin Iteration durch hier das Array, wird es macht Sie nur gehen durch das, was wir wissen, ist unsortiert. OK? Das ist nur eine Optimierung. Man könnte es naiv einfach schreiben Iteration durch alles, es nur länger dauern würde. Mit diesem Vier-Schleife ist es nur eine nette Optimierung weil wir wissen, dass nach jeder vollen Iteration hier durch die Anordnung, wie jedes volle Schleife hier, wir wissen, daß man mehrere dieser Elemente wird am Ende sortiert werden. Also haben wir nicht haben, um über diejenigen zu kümmern. Macht das Sinn macht, alle? Das kühle kleine Trick? So dass in diesem Fall, wenn wir durchlaufen, wir wissen, dass wir, wenn überprüfen möchten Array n und n + 1 sind in Ordnung. Ok. Also hier ist der Pseudocode. Wir wollen, wenn überprüfen Array n und n plus 1 sind in Ordnung. Also, was können wir denn da? Es wird etwas bedingter sein. Es wird eine, wenn. STUDENT: Wenn Array n weniger als Array n plus 1. LEHRER: Mm-hm. Nun, kleiner oder größer als. STUDENT: Größer als. Dann wollen wir sie zu tauschen. Genau. So, jetzt zu dem, was ist das bekommen wir Mechanismus für den Tausch? Also gingen wir durch diese kurz, eine Art von Swap-Funktion in der vergangenen Woche. Erinnert sich noch jemand, wie es funktioniert? So können wir nicht nur neu zuweisen ihnen, nicht wahr? Weil einer von ihnen verloren geht. Wenn wir die A gleich B und dann B ist gleich A, die alle eine plötzliche beide sind nur gleich B. Also, was wir tun müssen, ist, dass wir haben eine temporäre Variable, die ist werde einer von uns, während halten wir sind in den Prozess der Swapping. Also, was wir haben, ist wir einige int haben Temp gleich zu-- können Sie es zuordnen zu welcher sie benutzen möchten, gerade stellen Sie sicher, Sie verfolgen es-- halten so in diesem Fall, ich bin zu gehen weisen Sie ihn Array n plus 1. Also, das wird halten unabhängig Wert in diesem zweiten Block ist dass wir auf der Suche. Und dann wir tun können ist, dass wir gehen können vor und weisen Array n plus 1, weil wir wissen, dass wir haben diese gespeicherten Wert. Dies ist auch einer der großen things-- Ich weiß nicht, ob jemand von euch hatte Probleme, wo, wenn Sie zwei Schalter Codezeilen plötzlich Dinge funktionierten. Sortieren ist in CS sehr wichtig. So stellen Sie sicher Diagramm Dinge aus, wenn möglich darüber, was tatsächlich passiert. So, jetzt sind wir zu gehen neu zuweisen Array n plus 1, weil wir wissen, dass wir haben diese gespeicherten Wert. Und wir können das zu Array zuweisen n oder in diesem Fall Array i. Zu viele Variablen. Ok. So, jetzt haben wir neu zugewiesen habe Array i plus 1 auf gleichen, was in Array i. Und jetzt können wir zurückgehen und zuweisen Array i zu was? Anyone? STUDENT: 10. LEHRER: 10. Genau. Und eine letzte Sache. Wenn wir sie jetzt ausgelagert, was müssen wir tun? Was ist die eine Sache, das wird uns sagen wenn wir jemals dieses Programm zu beenden? Was sagt uns, dass wir eine sortierte Liste? Wenn wir keine Swaps, die nicht durchführen, oder? Wenn Swaps gleich ist Null am Ende von diesem. Also, wenn Sie eine Swap durchführen, wie wir gerade hier getan hat, wollen wir Swaps aktualisieren. Und ich weiß, gab es eine Frage früher über können Sie verwenden Null oder Eins statt von wahr oder falsch. Und das ist, was dieser tut hier. Also das sagt, wenn nicht Swaps. Also, wenn Swaps null ist, was ich immer ist-- meine Wahrheiten und meine Falschen durcheinander. Wir wollen uns zu bewerten auf true und es ist nicht. Also, wenn es Null ist, dann ist es falsch. Wenn Sie es mit einem negieren [? Knall?] wird es wahr. Also dann ist diese Linie führt. Wahrheiten und falsche und Nullen und Einsen verrückt. Nur, wenn Sie langsam gehen durch sie wird es Sinn machen. Aber das ist, was dieses kleine Stück Code hier tut. Also das überprüft, haben wir getan, keine Swaps. Also, wenn es etwas anderes Null, es geht um falsch zu sein und die ganze Sache ist werde erneut ausführen. Cool? STUDENT: Was bedeutet Pause machen? LEHRER: gerade Pause bricht man aus der Schleife. So dass in diesem Fall wäre es genau wie das Programm beenden und Sie nur würde Ihre sortierte Liste. STUDENT: Amazing. LEHRER: Es tut mir leid? STUDENT: Weil wir vorher Gebraucht geschrieben 1 überschrieben Null zu präsentieren, wenn das funktionieren wird oder nicht. LEHRER: Yeah. So können Sie Null oder 1 zurück. In diesem Fall, weil wir nicht wirklich etwas zu tun mit der Funktion, wir wollen nur, dass es zu brechen. Wir wissen nicht wirklich darum. Brake ist auch gut, wenn es ist für Ausbrechen verwendet von vier Schleifen oder Bedingungen, Sie wollen nicht zu halten Ausführen. Es dauert einfach aus ihnen heraus. Es ist ein bisschen wie ein Nuance Sache. Ich fühle mich, als gäbe es eine Menge von Hand einwirken, wie du darüber bald lernen. Aber Sie werden darüber bald lernen. Ich verspreche. Ok. So kann jeder bekommen hat Bubble Sort? Nicht schlecht. Durch eine Iteration, Swap Dinge mit ein TEMP-Variable, und wir sind alle dort eingestellt? Cool. Genial. Ok. Zurück zu den Powerpoint. Alle Fragen im Allgemeinen über diese so weit? Cool. Mm-hm. STUDENT: [unverständlich] int main Regel. Haben Sie zu haben, dass für diese? LEHRER: So waren wir gerade auf der Suche gerade bei der aktuellen Sortieralgorithmus. Wenn Sie hatte es innerhalb wie ein größeres Programm, Sie würde einen int main irgendwo. Je nachdem wo Sie verwenden diesen Algorithmus, es wäre festzustellen, was ist von ihr zurück. Aber für unseren Fall, wir sind strikt schauen, wie funktioniert das eigentlich durchlaufen ein Array. So wissen wir nicht darum kümmern. So waren wir über die besten Fall reden und Worst-Case-Szenarien für binäre Suche. So ist es auch wichtig, zu tun daß für jede der Arten. Also, was denken Sie, ist das Schlimmste Bei Laufzeit von Bubble Sort? Ihr Jungs erinnern? STUDENT: N minus 1. LEHRER: N minus 1. Das heißt also, es gibt n minus 1 Vergleiche. So eine Sache zu realisieren ist, dass bei der ersten Iteration, wir durchmachen, vergleichen wir diese two-- damit ist 1. Diese zwei, drei, vier. So nach einer Iteration wir bereits vier Vergleiche. Wenn ich über Laufzeit und n reden. N repräsentiert die Anzahl der Vergleiche in Abhängigkeit davon, wie viele Elemente wir haben. OK? So durchlaufen wir, haben wir vier. Das nächste Mal, wenn Sie wissen, dass wir nicht muss sich darum kümmern. Wir vergleichen diese beiden, diese beiden, diese beiden, und wenn wir nicht haben, dass die Optimierung mit den vier Schleife, die ich schrieb, Sie würden hier werden sowieso vergleichen. Also Sie müssten durch das Array laufen und machen n Vergleiche n Zeiten, da jedes Mal, wenn wir laufen wir durch sie sort eine Sache. Und jedes Mal, wenn wir durchlaufen das Array, wir machen n Vergleiche. Also unsere Laufzeit dafür ist tatsächlich n quadriert, die ist in viel schlechterem unserer log Ende, denn das bedeutet, wenn wir vier Milliarden-Elemente, ist es wird uns nehmen vier Milliarden statt 32 quadriert. Also nicht die beste Laufzeit, aber für einige Dinge, Sie wissen, wenn Sie innerhalb bist ein bestimmter Bereich von Elementen Bubble-Sort kann gut zu nutzen. Ok. So jetzt, was ist der beste Fall, Laufzeit? STUDENT: Zero? Oder 1? LEHRER: Also eins würde sein ein Vergleich. Richtig. STUDENT: N minus 1? LEHRER: Also, ja. So n minus 1. Wann immer Sie ein Konzept, wie n minus 1, neigen wir dazu, nur fallen sie ab und wir einfach sagen, n, weil Sie zu jedem der these-- jedem Paar zu vergleichen. Es wäre also n minus 1, die wir wir würden einfach sagen, etwa n. Wenn Sie mit der Laufzeit zu tun haben, alles in nahekommt. Solange der Exponent richtig, du bist ziemlich gut. Das ist, wie wir damit umgehen. So, dass der beste Fall ist N, die bedeutet, dass die Liste bereits sortiert ist, und alles, was wir tun müssen, ist durchlaufen und überprüfen Sie, dass es sortiert. Cool. In Ordnung. So wie Sie hier sehen, haben wir müssen nur noch ein paar Grafiken. So n quadriert. Fun. Viel schlimmer als n wie wir sehen, und viel, viel schlimmer als log 2n. Und dann auch noch in protokoll protokolle erhalten Sie. Und Sie nehmen 124, in erhalten Sie wie Protokoll Stern, der wie verrückt ist. Also, wenn Sie interessiert sind, Lookup Protokoll star. Es ist eine Art Spaß. So haben wir diese große Diagramm. Nur ein Heads-up, das ein wunderbaren Chart zu haben für Ihre mittelfristige, weil wir lange, Sie zu bitten, diese verdünnt. Also nur ein Heads-up, habe dieses auf Ihrem Halbzeit auf Ihrem schönen Spickzettel da. So dass wir nur sah Bubble Sort. Schlimmsten Fall n quadriert, best case, n. Und wir werden auf die anderen schauen. Und wie Sie sehen, die nur können eine, die wirklich gut tut ist Mergesort, die wir, warum bekommen. So werden wir auf dem Sprung nächste hier-- Auswahl sortieren. Erinnert sich noch jemand, wie Auswahl Art gearbeitet? Go for it. STUDENT: Grundsätzlich durchlaufen eine Ordnung und eine neue Liste. Und so, wie Sie setzen Elemente sind in, legte sie an der richtigen Stelle in der neuen Liste. LEHRER: Also das klingt mehr wie Insertion Sort. Aber du bist wirklich in der Nähe. Sie sind sehr ähnlich. Sogar ich sie manchmal gemischt. Vor diesem Abschnitt Ich war wie, warten. Ok. Also, was Sie wollen tun, ist Selection Sort, die Art, wie Sie denken können darüber und die Art und Weise Ich achte darauf, ich versuche nicht zu bekommen sie auf, vermischt ist es durchgeht und es wählt die kleinste Zahl, und es legt, dass am Anfang der Liste. Es tauscht sie mit diesem ersten Punkt. Sie haben tatsächlich ein Beispiel für mich. Genial. Also nur ein Weg, um von es-- Auswahl denken sortieren, wählen Sie den kleinsten Wert. Und wir sind zu gehen durch ein Beispiel ausführen dass ich denke, wird da helfen Ich denke, Visuals immer helfen. Also wir beginnen mit etwas das ist völlig unsortiert. Rot werden unsortiert sein, grün sortiert werden. Es wird alles Sinn machen in einer Sekunde. So gehen wir durch, und wir durchlaufen vom Anfang bis zum Ende. Und wir sagen, OK, 2 unsere kleinste Zahl. So werden wir 2 nehmen und wir werden um es in den Vordergrund unserer Array bewegen weil es das kleinste Zahl, die wir haben. Also das ist, was dies hier tun. Es ist gerade dabei, diese beiden zu tauschen. So, jetzt haben wir eine sortierte haben Teil und einem unsortierten Teil. Und was ist gut daran zu erinnern, über Selection Sort ist, dass wir nur die Auswahl aus dem unsortierten Teil. Die sortierten Teil einfach in Ruhe lassen. Mm-hm? STUDENT: Woher weiß er, was ist die kleinste ohne Vergleich zu jedem anderen Wert in dem Array. LEHRER: Es tut vergleichen. Wir mögen es übersprungen. Dies ist nur allgemeine insgesamt. Ja. Wenn wir den Code Ich bin zu schreiben sicher, du wirst mehr zufrieden sein. Aber Sie diese zunächst speichern Element als kleinste. Sie vergleichen und Sie sagen, OK, es ist kleiner? Ja. Halten Sie es. Hier ist es kleiner? Nein? Das ist Ihre kleinsten, neu zuweisen, um sie Ihren Wert. Und Sie werden viel glücklicher sein wenn wir gehen durch den Code. So gehen wir durch, tauschen wir sie, so ist, dann wir uns diese unsortierten Teil. So werden wir drei auswählen. Wir werden es an zu setzen bei das Ende unserer sortierten Teils. Und wir sind gerade dabei, weiterhin tun, dass, das tun, und tun. Also das ist unsere Art von Pseudo hier. Wir werden es hier in einem zweiten Code oben. Aber nur etwas zu Fuß durch auf einem hohen Niveau. Du wirst aus gehen i gleich 0 bis n minus 2. Das ist ein weiterer Optimierung. Sie nicht zu viel Sorgen. So sagten Sie. Als Jacob sagte, wie gehen wir zu verfolgen, was unsere Mindest ist? Wie können wir wissen? Wir haben zum Vergleich alles in unserer Liste. Also mindestens gleich i. Es ist einfach zu sagen in diesem Fall der Index unserer Minimalwert. Also, es wird durch Iteration und es geht von j gleich i plus 1. So wissen wir bereits, dass das ist unser erstes Element. Wir brauchen nicht, um es sich zu vergleichen. So beginnen wir den Vergleich mit dem nächsten eine, die ist, warum es i plus 1 bis n minus 1, die ist Ende des Arrays gibt. Und wir, wenn Array an dem j kleiner als Array min, dann werden wir neu zuzuweisen, wo unsere Mindestindizes ist. Und wenn min nicht gleich i, wie in denen wir waren hier zurück. So gerne, wenn wir zuerst tat dieses. In diesem Fall wäre es am Start Null, wäre es am Ende als zwei. Also min würde nicht gleich i am Ende. Das lässt uns wissen, dass wir brauchen, um sie zu tauschen. Ich fühle mich wie ein konkretes Beispiel wird viel mehr als dieses zu helfen. Also werde ich dieses oben Code mit euch schon jetzt und ich denke, es wird besser sein. Art in der Regel so, dass Arbeit es ist oft besser, nur um sie zu sehen. Also, was wir tun wollen, ist wollen wir zuerst die kleinste Element in seiner Position in der Anordnung. Genau das, was Jacob sagte. Sie müssen das irgendwie zu speichern. Also werden wir hier starten Iteration über das Array. Wir werden sagen, es ist unsere erste nur für den Anfang. So werden wir int haben kleinste gleich Array bei i. So eine Sache zu bemerken, jede Mal in dieser Schleife führt, wir beginnen einen Schritt weiter entlang. Wenn wir beginnen wir auf dieser. Das nächste Mal, wenn wir durch Iteration, wir an diesem einen Start zugeordnet wird unsere kleinsten Wert. So ist es sehr ähnlich zu Bubble-Sort wenn wir wissen, daß nach einem Durchgang, Dieses letzte Element wird sortiert. Mit Selection Sort, es ist genau das Gegenteil. Bei jedem Durchgang, wissen wir, dass Der erste wird sortiert. Nach dem zweiten Durchlauf, der zweite sortiert werden. Und wie Sie mit den Schiebe Beispielen sahen, unsere sortiert Teil wächst und wächst. Also, indem Sie unsere kleinsten Arrays i, alles was man tut schränkt das, was Wir sind am so suchen um die Anzahl zu minimieren Vergleiche die wir machen. Ist das sinnvoll, um alle? Haben Sie mich brauchen, um durch die ausgeführt wieder langsamer oder mit anderen Worten? Ich bin glücklich,. Ok. Also sind wir die Speicherung der Wert an dieser Stelle, aber wir wollen auch, um den Index zu speichern. Also wir gehen in den Laden Position des kleinsten eine, die gerade dabei ist, um i sein. Jetzt so Jacob ist zufrieden. Wir haben Dinge gespeichert. Und jetzt müssen wir schauen durch die unsortierten Teil des Arrays. Also in diesem Fall diese wäre unsere unsortiert. Dies ist i. Ok. Also, was wir tun werden wird zu einer Schleife. Wann immer Sie wollen durchlaufen ein Array, Ihre Meinung könnte für eine Schleife gehen. Also für einige int k equals-- was wir denken k wird sich gleich mit zu beginnen? Dies ist, was wir als unsere kleinste gesetzt Wert, und wir wollen es zu vergleichen. Was wollen wir, um es zu vergleichen? Es wird diese nächste sein, richtig? So wollen wir k initialisiert werden i plus 1 zu starten. Und wir wollen, k wir in diesem Fall bereits Größe bis hier abgelegt, so können wir nur nutzen Größe. Größe durch die die Größe des Arrays. Und wir wollen einfach nur Aktualisieren k jedesmal um eins. Cool. So, jetzt müssen wir herausfinden das kleinste Element. Also, wenn wir durch laufen, wir will sagen, wenn Array bei k weniger als unsere kleinste value-- das ist, wo wir sind eigentlich Verfolgung, was die kleinste hier-- dann neu zuweisen möchten wir was unsere kleinste Wert ist. Dies bedeutet, dass, oh, wir sind Iteration durch hier. Was auch immer Wert ist hier nicht unsere kleinste Sache. Wir wollen es nicht. Wir wollen es neu zuweisen. Also, wenn wir die Neuzuweisung von ihm, was zu tun Sie vielleicht denken in diesem Code hier sein? Wir wollen neu zuweisen kleinste und Position. Also, was ist kleinste jetzt? STUDENT: Array k. LEHRER: Array k. Und was ist die Position jetzt? Was ist die Indizes unsere kleinsten Wert? Es ist nur k. So Array k, k, passen sie auf. Also wollten wir, dass neu zuweisen. Und dann, nachdem wir fanden unsere kleinste, so dass am Ende dieses für Schleifen hier haben wir festgestellt, was unsere kleinsten Wert ist, so dass wir tauschen es einfach. In diesem Fall sagen wie unsere kleinste Wert ist hier draußen. Dies ist unsere kleinste Wert. Wir wollen einfach nur, um es hier zu tauschen, das ist was das Swap-Funktion am unteren Rand tat, was wir gerade schrieb zusammen vor ein paar Minuten. So sollte es bekannt vorkommen. Und dann wird es nur durchlaufen durch, bis er den ganzen Weg erreicht an dem Ende, das bedeutet, dass man null Elemente, die unsortiert sind und alles andere wurde sortiert. Sinnvoll? Ein wenig konkreter? Der Code Hilfe? STUDENT: Für eine Größe, die Sie nie wirklich definieren oder zu ändern, wie funktioniert es schon? LEHRER: Also eine Sache, bemerken hier oben ist int size. So dass wir in diesem sort-- Art sagen ist eine Funktion in dieser case-- es Auswahl sortieren, es bestanden in der Funktion. Also, wenn es nicht übergeben wurde in, würden Sie etwas tun wie mit der Länge der Anordnung oder Sie würden durch laufen um die Länge zu finden. Sondern weil es bestanden in, können wir es einfach verwenden. Sie übernehmen nur, dass der Benutzer gaben Sie eine gültige Größe, dass tatsächlich stellt Größe Ihres Arrays. Cool? Wenn Sie Jungs haben keine Probleme mit diesen oder wollen mehr Praxis Codierungsarten auf eigene Faust, sollten Sie gehen Sie zu study.cs50. Es ist ein Werkzeug. Sie haben ein Checker, Sie tatsächlich schreiben. Sie tun Pseudocode. Sie haben mehr Videos und Dias einschließlich die, die ich hier verwenden. Also, wenn Sie immer noch das Gefühl bist ein wenig unscharf, versuchen, dass aus. Wie immer kommen mit mir reden, auch. Question? STUDENT: Wollen Sie sagen, die Größe wird vorher festgelegt? LEHRER: Ja. Die Größe wird zuvor festgelegt hier in der Funktionsdeklaration. So können Sie davon ausgehen, dass es in übergeben worden durch den Benutzer, und der Einfachheit halber, wir gehen davon aus, dass die Benutzer gab uns die richtige Größe. Cool. Also das ist Selection Sort. Leute, ich weiß, dass wir eine Menge lernen heute. Es ist eine dichte Daten für Abschnitt. Also mit diesem werden wir auf Insertion Sort gehen. Ok. Also, bevor wir zu tun haben, unsere Laufzeitanalyse hier. Also im besten Fall, gewährt, da ich Ihnen gezeigt, Die Tabelle habe ich bereits Art gab es weg. Aber bestenfalls Laufzeit, was denken wir? Alles sortiert. N zum Quadrat. Wer noch eine Erklärung für Sie, warum? STUDENT: Du vergleichst through-- LEHRER: Richtig. Du vergleichst durch. Bei jeder Iteration, obwohl wir Dekrementieren dies durch eine, du bist immer noch durch die Suche alles, das kleinste finden. Also selbst wenn Sie Ihre kleinsten Wert ist hier zu Beginn, du bist immer noch den Vergleich gegen alles andere um sicherzustellen, dass es die kleinste Sache. So werden Sie am Ende durchlauf etwa n Quadrat mal. In Ordnung. Und was ist der schlimmste Fall? Auch n quadriert, weil du gehst zu tun, dass die gleiche Prozedur. So dass in diesem Fall Auswahl hat Art etwas dass wir auch anrufen erwartete Laufzeit. Also in den anderen, wir wissen nur, die oberen und unteren Grenzen. Je nachdem, wie verrückt unsere Liste ist oder wie unsortierte es, sie variieren zwischen n oder n quadriert. Wir wissen es nicht. Aber weil Selection Sort hat die gleiche schlimmsten und besten Fall erzählt, dass uns, dass Egal, welche Art von Eingangs wir haben, sei es vollständig sortiert oder komplett Reverse sortiert, es ist würde die gleiche Menge an Zeit in Anspruch nehmen. Also in diesem Fall, wenn Sie erinnern von unserem Tisch, sie einen Wert tatsächlich hatte, diese beiden Arten nicht haben, was erwartet der Laufzeit. So wissen wir, dass, wann immer wir laufen Selection Sort, es ist gewährleistet laufen eine n quadriert Zeit. Es gibt keine Variabilität gibt. Es ist nur zu erwarten. Und wieder, wenn Sie lernen wollen mehr nehmen CS 124 im Frühjahr. In Ordnung. Wir haben diesen einen gesehen. Cool. So Insertion Sort. Und ich bin wahrscheinlich um durch diese lodern. Ich will nicht, euch es zu codieren. Wir werden einfach durch sie hindurchgehen. So Insertion Sort ist eine Art der ähnlich wie Selection Sort in, dass wir sowohl eine unsortierte und sortiert Teil des Arrays. Aber was ist anders ist, dass als wir durch einen Streich nach dem anderen, wir nehmen nur was Nummer ist als nächstes in unserem unsortiert, und richtig sortieren sie in unsere sortierten Array. Es wird mehr Sinn mit einem Beispiel zu machen. So beginnt alles mit dem unsortierten, Genau wie bei Selection Sort. Und wir werden dies in sortieren aufsteigender Reihenfolge, wie wir waren. So auf den ersten Pass nehmen wir den ersten Wert und wir sagen, OK, du bist jetzt in einer Liste selbst. Weil Sie in einer Liste sind selbst, Sie sind sortiert. Herzlichen Glückwunsch für Sein der das erste Element in dieser Anordnung. Sie sind bereits sortiert alle auf eigene Faust. So, jetzt haben wir eine sortierte haben und eine unsortierte Array. So, jetzt haben wir die erste nehmen. Was passiert zwischen hier und hier ist, dass wir sagen, OK, wir gehen auf der Suche erste Wert unserer unsortierten Array und wir den Eingang geht es in seinem richtigen Stelle im sortierten Array. Also, was wir tun, ist nehmen wir 5 und wir sagen, OK, 5 größer als 3, so fügen wir es genau richtig auf der rechten Seite davon. Wir sind gut. Also wir gehen auf unsere nächste. Und wir nehmen 2. Wir sagen, OK, 2 weniger als 3, so dass wir wissen, dass es muss bei der sein vor unserer Liste jetzt. Also, was wir tun, ist schieben wir 3 und 5 nach unten und wir bewegen 2 in diesem ersten Steckplatz. Also sind wir nur Einsetzen in der richtige Ort, es sein sollte. Dann schauen wir auf unsere nächste, und wir sagen, 6. OK, 6 ist größer als alles in unserer sortierten Array, so dass wir Tag setzen nur bis zum Ende. Und dann schauen wir auf 4. 4 ist kleiner als 6, dann ist es weniger als 5, aber es ist mehr als 3. Also fügen wir es genau richtig in der Mitte zwischen 3 und 5. So zu machen, dass ein wenig etwas mehr Beton, hier ist eine Art der Vorstellung davon, was passiert ist. Also für jeden unsortierte Element, wir festzustellen, wo in der sortierten Teil es ist. Also wenn man bedenkt, das sortiert und unsortiert, wir durchqueren und Figur aus, wo es in der sortierten Array passt. Und wir setzen Sie sie durch Verschieben des Elemente auf der rechten Seite nach unten. Und dann haben wir einfach weiter durch Iteration, bis wir haben eine völlig sortierte Liste wo unsortiert ist jetzt Null und sortierten nimmt die Gesamtheit unserer Liste. Also, noch einmal, um die Dinge noch zu machen konkretere, haben wir Pseudocode. Also im Grunde für i gleich 0 bis n minus 1, das ist nur die Länge unseres Arrays. Wir haben einige Element, das gleich ist die erste Anordnung oder die ersten Indizes. Wir setzen j gleich. So, während j größer ist Null, und die Anordnung, j minus 1 ist größer als die Element, so alles, was zu tun sorgt dafür, dass Ihre j wirklich repräsentiert die unsortierten Teil des Arrays. So, während es immer noch Dinge, zu sortieren und j minus eins ist-- was ist das Element mit ihr? J wurde hier nie definiert. Es ist irgendwie nervig. Ok. Sowieso. So j minus 1, Sie überprüfen sind das Element, bevor es. Sie sagen, OK, ist das Element vor, wo immer ich am-- uns gelassen tatsächlich ziehen dies. Also lassen Sie uns sagen, das ist wie auf unserem zweiten Durchgang. Also i wird gleich sein 1, welches hier. Also i wird gleich 1 zu sein. Dies würde 2, 4, 5, 6, 7 sein. In Ordnung. Also unser Element in diesem Fall wird gleich 4 ist. Und wir haben einige j, das ist geht gleich 1 zu sein. Oh, ist j Dekrementieren. Das ist, was es ist. So j gleich i, so was das ist Sprichwort ist, dass wie wir vorankommen, wir nur dafür, dass dass wir nicht über Indizierung auf diese Weise, wenn wir versuchen, die Dinge in unsere sortierte Liste einfügen. So dass, wenn j gleich 1 ist, und in diesem Fall Array j minus one-- so Array j minus 1 ist 2 in diesem case-- wenn das größer als das Element, dann all dies tut verlagert sich die Dinge nach unten. Also in diesem Fall, array j minus eins würde Array Null, was 2 sein. 2 nicht größer als 4 ist, so dass diese nicht ausgeführt. So ist die Verschiebung nicht nach unten zu verschieben. Was das bedeutet ist hier nur Bewegen sortierten Array nach unten. In diesem Fall tatsächlich wir könnte do-- wir machen diese 3. Also, wenn wir durch mit zu gehen Dieses Beispiel können wir jetzt hier. Dies wird sortiert. Dies ist unsortiert. Cool? So ist i gleich 2, so unser Element ist gleich 3. Und unsere j gleich 2 ist. Also durch und wir freuen uns sagen, OK, ist Array j minus eins größer ist als die Element dass wir bei der Suche? Und die Antwort ist ja, nicht wahr? 4 größer als 3 ist und j 2 ist, sodass dieser Code ausführt. So jetzt, was wir tun ein Array an 2, so genau hier, tauschen wir sie. Also haben wir einfach sagen, OK, Array bei 2 wird jetzt auf 3 sein. Und j wird sich gleich j minus 1, 1. Das ist schrecklich, aber you guys get the idea. J ist nun gleich 1 ist. Und Array j gerade dabei zu sein gleich unser Element, die 4 war. Ich löschte etwas, was ich nicht sollte haben oder miswrote etwas, aber ihr Jungs bekommen die Idee. Es bewegen sich n. Und dann, wenn dies, wäre es Schleife wieder und es würde sagen, OK, j 1 jetzt. Und Array j minus 1 ist jetzt 2. Ist 2 weniger als unser Element? Nein? Das bedeutet, dass wir eingefügt dieses Element an der richtigen Stelle in unserem sortierten Array. Dann können wir diese übernehmen und wir sagen, OK, ist unsere sortierten Array hier. Und es würde diese Nummer 6 zu nehmen und wie, OK, 6 weniger als diese Zahl? Nein? Cool. Uns geht es gut. Tun Sie es erneut. Wir sagen 7. Ist 7 weniger als zum Ende unserer sortierten Array? Nein. Wir sind also in Ordnung. So wäre sortiert werden. Grundsätzlich alles tut wird es sagen Take das erste Element Ihre unsortierten Array herauszufinden, wo es geht in Ihrem sortierten Array. Und das dauert nur Pflege von Swaps zu tun. Sie sind im Grunde nur Swapping bis es an der richtigen Stelle. Das visuelle Bild ist, dass Sie Bewegen alles auf diese Weise vor. So ist es wie ein halb Bubble-Sort-esque. Check out Studie 50. Ich kann empfehlen, um dies an Ihrem eigenen Code. Wenn Sie irgendwelche Fragen haben oder Sie wollen siehe Beispielcode für eine Insertion Sort, lass es mich wissen, bitte. Ich bin immer in der Nähe. Also worst case-Laufzeit und best case-Laufzeit. Wie Sie Kerl sah aus der Tabelle habe ich bereits Ihnen gezeigt, es ist sowohl n quadriert und n. So Art abgehend von dem, was wir sprachen mit unseren früheren Sorten, am schlechtesten Bei Laufzeit ist, dass wenn es ist völlig unsortiert, wir müssen alle diese n-mal zu vergleichen. Wir tun eine ganze Menge von Vergleichen denn wenn es in umgekehrter Reihenfolge, wir gehen zu sagen, OK, diese die gleiche ist, ist gut, und diese müssen verglichen werden gegen die erste, zurückbewegt werden. Und wie wir in Richtung bekommen das Schwanzende, haben wir Vergleichen, vergleichen und Vergleichen gegen alles. Also es endet als etwa n quadriert. Wenn es richtig ist, dann sagen, OK, 2, du bist gut. 3, Sie 2 verglichen sind. Du bist gut. 4, einfach zu vergleichen, um den Schwanz. Du bist gut. 6, zu vergleichen, um den Schwanz, es dir gut geht. So wird für jeden Ort, wenn es schon sortiert, du machst einen Vergleich. So ist es nur n. Und weil wir eine best case-Laufzeit von n und einem Worst-Case-Laufzeit von n quadriert, haben wir keine erwartete Laufzeit. Es hängt nur von der Chaos unserer Liste gibt. Und wieder ein anderer Grafik und eine andere Tabelle. Also Unterschiede zwischen Arten. Ich werde einfach Brise durch, ich das Gefühl, wir haben ausgiebig gesprochen darüber, wie sie aller Art von variieren und miteinander zu verknüpfen. So Mergesort ist die letzte Ich werde mit der Bohrung euch. Wir haben ein ziemlich buntes Bild. So Mergesort ist ein rekursiver Algorithmus. Also euch wissen, was eine rekursive Funktion ist? Wer möchte sagen? Sie wollen versuchen? Also eine rekursive Funktion ist nur eine Funktion, die sich selbst aufruft. Also, wenn euch vertraut sind mit der Fibonacci-Folge, das ist als rekursive weil Sie die vorherigen beiden nehmen und addieren sie um Ihren nächsten zu gelangen. So rekursive, denke ich immer der Rekursion als wie eine Spirale so dass Sie wie Spirale nach unten hinein. Aber es ist nur eine Funktion dass nennt sich. Und, tatsächlich, wirklich schnell ich kann Ihnen zeigen, wie das aussieht. So rekursiven hier, wenn wir betrachten, ist dieses die rekursive Weg zur Summe über ein Array. Also alles, was wir tun, ist wir Summenfunktion haben Summe, die eine Größe und ein Array nimmt. Und wenn Sie feststellen, Größe dekrementiert jedesmal um eins. Und alle es tut, ist, wenn x gleich ist zero-- so dass, wenn die Größe des Arrays gleich zero-- wird Null zurückgegeben. Ansonsten fasst diese letzte Element des Arrays, und nimmt dann eine Summe von der Rest des Arrays. So ist es nur die Zerlegung in immer kleinere Probleme. Lange Rede kurzer Sinn, Rekursion, Funktion, die sich selbst aufruft. Wenn es das ist alles, was Sie von diesem bekam, das ist, was eine rekursive Funktion ist. Wenn Sie eine 51, werden Sie sehr zu bekommen, sehr komfortabel mit Rekursion. Es ist wirklich cool. Es machte Sinn, wie 3.00 eine Nacht aus. Und ich war wie, warum habe ich nie verwenden das? Also für Merge-Sort, im Grunde was es zu tun ist, es ist werde es brechen und brechen nach unten, bis es nur einzelne Elemente. Die einzelnen Elemente sind einfach zu sortieren. Wir sehen, dass. Wenn Sie ein Element haben, ist es bereits als sortierte. Usw. mit einem Eingang des n Elemente, Wenn n kleiner als 2 ist, nur zurück, weil das bedeutet es ist entweder 0 oder 1, wie wir gesehen haben. Diese werden als sortierte Elemente. In Halb Sonst brechen. Sortieren Sie die erste Hälfte, sortieren Sie die zweite Hälfte, und dann verschmelzen sie zusammen. Warum es heißt merge sort. So haben wir hier wir diese zu sortieren. So halten wir mit ihnen bis der Array-Größe ist 1. Also, wenn es ein, wir zurückkehren denn dies ist ein sortiertes Array, und dies ist ein sortiertes Array, und das ist ein sortiertes Array, wir sind alle sortiert. Also dann, was wir tun ist, dass wir starten gemeinsam ihre Zusammenlegung. Also die Art und Weise können Sie denke über Verschmelzung ist Sie entfernen Sie einfach das kleinere Anzahl der jedem der Subarrays und hängen Sie einfach an die entstanden Array. Also, wenn Sie hier sehen, wenn wir Diese Sätze haben wir 4, 6 und 1. Wenn wir diese zusammenführen möchten, wir diese ersten zwei und wir sagen, OK, ein kleiner, es geht nach vorne. 4 und 6, es gibt nichts zu vergleichen es, nur Tag setzen bis zum Ende. Wenn wir diese beiden zu kombinieren, wir haben nur nehmen Sie die kleinere von diesen beiden, so ist es ein. Und jetzt nehmen wir die kleinere der beiden, also 2. Kleinere von beiden ist, 3. Kleinere der beiden, 4, 5, 6. Sie sind also nur Abziehen diesen. Und weil sie zuvor sortiert, Sie müssen nur ein Vergleich jedes Mal dort. Also mehr Code hier, nur die Vertretung. So können Sie in der Mitte beginnen und Sie sortieren links und rechts und dann muß man nur zusammenführen denen. Und wir wissen nicht Code für verschmelzen hier richtig. Aber noch einmal, wenn Sie weitermachen studieren 50, wird es da sein. Ansonsten kommen talk to me wenn Sie immer noch verwirrt. So cool daran ist, dass bestenfalls schlimmsten Fall und erwartete Laufzeit sind alle in log n, die ist weit besser als wir haben für den Rest der Art gesehen. Wir haben gesehen, n quadriert und was wir tatsächlich bekommen hier n log n, das ist toll. Schauen Sie, wie viel besser das ist. So ein netter Kurve. So viel effizienter. Wenn Sie überhaupt möglich, die Verwendung Mergesort. Es erspart Ihnen Zeit. Dann wieder, wie gesagt, wenn du unten bist in diesem unteren Bereich, es macht keinen, dass einen großen Unterschied. Sie erhalten bis zu Tausenden und Tausende von Eingängen, Sie wollen auf jeden Fall ein effizienter Algorithmus. Und wieder unsere schöne Tabelle aller Sorten, die euch heute gelernt. Also ich weiß, es ist schon eine dichte Tag. Dies ist nicht notwendigerweise um Sie bei Ihrer pset helfen. Aber ich will nur einen Haftungsausschluss zu machen dieser Abschnitt ist nicht nur über psets. All dieses Material Messe ist Spiel für Ihr Mittelklausuren. Und auch, wenn Sie weiter mit CS zu tun, diese sind wirklich wichtige Grundlagen dass Sie müssten es wissen. So ein paar Tage wird ein wenig mehr pset Hilfe aber einige Wochen sein wird viel mehr tatsächliche Inhalt das kann nicht scheinen Super nützlich für Sie gerade jetzt, aber ich verspreche, wenn Sie weiterhin auf wird sehr, sehr nützlich. Das ist es also für den Abschnitt. Auf Draht. Ich habe es innerhalb einer Minute. Aber dort gehen Sie. Und ich muss Donuts oder Süßigkeiten. Ist jemand allergisch auf überhaupt, durch die Art und Weise? Eier und Milch. Also Donuts sind ein nein? Ok. In Ordnung. Schokolade nein? Starburst. Starbursts sind gut. Ok. Wir gehen zu müssen Starburst nächste Woche dann. Das ist, was ich erhalte. Ihr habt eine tolle Woche. Lesen Sie Ihre spec. Lassen Sie mich wissen, wenn Sie irgendwelche Fragen haben. Pset zwei Grade sein sollte zu Ihnen bis Donnerstag. Wenn Sie irgendwelche Fragen haben, darüber, wie ich benotet etwas oder warum ich benotet etwas so, wie ich haben, mailen Sie mich bitte, komm mit mir reden. Ich bin ein wenig verrückt diese Woche, aber ich verspreche, Werde ich noch antworten innerhalb von 24 Stunden. So haben eine tolle Woche, jeder. Viel Glück auf Ihrer pset.