SPEAKER 1: Hey iedereen! Welkom terug bij sectie. Zo blij om hier zo velen van jullie beiden te zien, en iedereen wie let online. Dus, zoals gebruikelijk welkom terug. Ik hoop dat jullie allemaal een mooie weekend, vol rust, ontspanning. Het was prachtig gisteren. Dus, ik hoop dat je genoten hebt van het buitenleven. 

Dus eerst een paar mededelingen. Grading. Dus, de meeste van jullie moeten hebben gekregen van een e-mail van mij over uw Scratch Pset, evenals Beoordeling voor Pset 1. Dus, gewoon een paar dingen. Zorg ervoor dat u check50 gebruiken in style50. Deze zijn bedoeld om te worden middelen voor jullie, om ervoor te zorgen dat je krijgt zo veel punten als je kunt zonder ze onnodig verlies. Dus, dingen als stijl zijn zeer belangrijk. We gaan af te nemen voor het. Sommigen van u misschien al gemerkt dat uit je Pset. En check50 is slechts een heel gemakkelijke manier om ervoor te zorgen dat we eigenlijk zijn terug wat moet worden teruggegeven aan de gebruiker, en dat alles naar behoren werkt. 

Op de tweede nota, zorg ervoor dat uw het uploaden van dingen naar de juiste map. Het maakt mijn leven net een beetje moeilijker als je Pset 2 uploaden naar Pset 1 want als ik dingen downloaden ze niet goed te downloaden. En ik weet dat het een beetje wankel in een systeem te wennen, maar gewoon super zijn voorzichtig, al was het maar voor mij, zodat wanneer je krijgt e-mails op als 02:00 en ik ben het sorteren. Zo niet veroorzaken ik moet kijken rondom voor uw Pset. Cool. 

Ik weet dat het vroeg, maar ik totaal werd overrompeld door een essay dat is vanwege deze vrijdag, dat Mijn docenten waren net als, oh ja. Vergeet niet, je hebt een essay verschuldigd op vrijdag. Dus, ik weet niemand houdt na te denken over tentamens, maar uw eerste quiz is op 15 oktober, die oktober wordt vanaf deze week. Dus, zou het eerder zijn dan je verwacht is alles. Dus dat je niet gegooid off guard wanneer Ik noem sectie van volgende week dat oh, je test volgende week, dacht ik Ik zou je een beetje meer te geven van een heads up nu. 

Dus, uw probleem te stellen, nummer drie. Hoe mensen hebben gelezen de spec uit nieuwsgierigheid? OK. We kregen een paar. Soort lager dan vorig week, maar dat is OK. Ik weet dat het was prachtig uit. Dus Break Out. Zeker nadat je gedaan te krijgen vandaag lees je spec tenminste proberen, zoals het downloaden verdeelsleutel en hardlopen net als de eerste voorletter ding dat ze je vragen om. Omdat we gebruik maken verdeelsleutel en een bibliotheek dat we alleen using-- --Het is slechts de tweede keer dat we dit Pset gedaan, gekke dingen kunnen gebeuren met uw apparaat, en je wilt weten dat out nu versus later. 

Want als het is donderdagavond of het is Woensdagavond en om wat voor reden uw apparaat doet gewoon niet wilt uitvoeren met de bibliotheek of de verdeling code, dat betekent kun je niet eens beginnen met het doen van de codering. Want je kunt niet controleren om te zien of het werkt. Je niet gaat kunnen te zien of het compileert. U wilt de zorg van hen vroeg in te nemen de week, wanneer je nog steeds kunt e-mail me of één van de andere TF, en we kunnen krijgen die vast. Want dat zijn zaken die gaan om je te stoppen van het maken van een echte vooruitgang. Het is niet als een bug, dat kun je gewoon een soort van overslaan. Als u problemen met uw apparaat of de verdeelsleutel, je echt wilt krijgen dat genomen zorg van eerder vroeger dan later. Dus zelfs als je niet echt Gaat begin te coderen, te downloaden van de distributie code, lees de spec, zorg ervoor dat Alles is er werken. OK? Als je dat kan doen, ik beloof jullie levens zal het makkelijker zijn. En dus ben je waarschijnlijk gaat om het nu goed te doen? OK. Dus, vragen daar? Elke logistieke dingen? Iedereen is goed? OK. 

Disclaimer voor die van u in de kamer en online. Ik ga proberen om te schakelen tussen PowerPoint in het toestel want we gaan te doen van wat codering vandaag op veler verzoek van de anonieme suggestie poll Ik stuurde vorige week. Dus, zullen we doen wat codering. Dus, als jullie ook willen om vuur van uw apparatuur, en je moet een e-mail hebben gekregen van mij, met een voorbeeld bestand. Aarzel dan niet om dat te doen. 

Dus, we gaan om te praten over GDB, een debugger. Het gaat om u te helpen soort uitzoeken waar dingen mis gaan in de code. Het is eigenlijk gewoon een manier voor u om stap door je code als het gebeurt, en in staat zijn om uit te printen variabelen of zien wat er daadwerkelijk gebeurt onder de motorkap verzen uw programma alleen rennen, het is net vastgelopen, en je bent zoals, geen idee wat hier gebeurde gewoon. Ik weet niet welke lijn is fout. Ik weet niet waar het mis ging. Dus, GDB gaat om u te helpen met dat. Ook, als u besluit om verder ja, en neem 61, het zal echt, echt uw beste vriend, want ik kan u vertellen want ik ga door die klasse. 

We gaan kijken naar binaire zoeken, die als jullie herinneren het grote telefoonboek voorbeeld spektakel van klasse. We zullen de uitvoering van die, en wandelen door dat een klein beetje meer, en dan gaan we door middel van vier verschillende soorten, die Bubble zijn, Selectie, Insertion, en samenvoegen. Cool. Dus, GDB zoals ik al zei, is een debugger. En dit zijn soort van de grote dingen, de grote functies of opdrachten dat u binnen GDB gebruiken, en ik zal lopen u door middel van een demo van het in een tweede. 

Dit is dus niet alleen ga abstract blijven. Ik zal proberen en maak het zo concreet mogelijk te maken voor jullie. Dus, breken. Het zal ofwel pauze zoals, een getal, dat vertegenwoordigt een lijn in uw programma, of u kunt een functie noemen. Dus, als je zegt breken belangrijkste, het zal stoppen bij de belangrijkste, en laat je door die functie te lopen. 

Evenzo, als je een aantal externe functioneren zoals Swap of Cube, dat hebben we gekeken naar de afgelopen week. Als je zegt dat breekt een van die, wanneer uw programma raakt dat, het zal wachten tot je vertellen wat ze moeten doen. Voordat het net zal uitvoeren, zodat u eigenlijk kon stappen binnen de functie en zie wat er gebeurt. Dus, de volgende, net slaat over de volgende regel, gaat over functies. Step. Dit zijn allemaal kleine abstract. Dus, ik ben gewoon gaan lopen via hen, maar zie je ze in gebruik in een tweede. 

Stap in een functie. Dus zoals ik al zei, zoals met Swap, het zou kunt u eigenlijk alsof je als fysiek binnenstappen, je kan knoeien met die variabelen, afdrukken wat ze zijn, zien wat er gaande is. Lijst zal letterlijk gewoon uitprinten uit de omliggende code. Dus, als je soort vergeten waar je bent in je programma, of je je afvraagt wat er omheen, dit zal alleen maar afdrukken van een segment van willen vijf of zes lijnen omheen. Dus, kun je gericht te krijgen over waar je bent. 

Print enkele variabele. Dus, als je de sleutel als in Caesar, dat zullen we kijken naar. U kunt afdrukken Key op elk punt te zeggen. Het zal u vertellen wat de waarde is zo dat, misschien ergens langs de weg, u uw sleutel overschreven. Je kunt eigenlijk zeggen dat, omdat je kunt eigenlijk zien dat waarde. 

In de lokale bevolking, net prints uw lokale variabelen. Dus, wanneer je binnen een lus, en je wil gewoon om te zien, zoals, oh. Wat is mijn ik? Wat is deze kernwaarde dat ik hier te initialiseren? Wat is de boodschap op dit punt? Het zal gewoon allemaal af te drukken van hen, zodat u niet individueel hoeft te zeggen, Print I. Print Message. Print Key. En vervolgens op Beeldscherm. Wat dat doet is als je stap voor stap door het programma, het zal alleen maar ervoor te zorgen dat het het weergeven van sommige bepaalde variabele op elk punt. Zodat u also-- --Het is soort van een snelkoppeling waar je hoeft niet te blijven gaan zoals, oh. Print Key of Print I. Het net zal automatisch het voor je doen. 

Dus, met dat, we gaan om te zien hoe dit gaat. Ik ga proberen en switch naar mijn toestel. Kijken of ik dit kan doen. All. We gaan gewoon om het te spiegelen. Er is niets gek op mijn laptop anyways. OK. Dit moet deze. Het is zo klein. Laten we eens kijken of we dit kunnen doen. 

OK. Alice is uiteraard worstelen hier maar een klein beetje, maar we zullen het krijgen in een momento. OK. We gaan enkel deze te verhogen. OK. Kan iedereen soort dat gezien? Misschien een klein beetje? Ik weet dat het een beetje klein. Je kan niet helemaal achterhalen hoe deze groter te maken. Als iemand weet. Weet iemand hoe je het groter te maken? OK. We gaan om te rollen met het. Heeft anyways niet uit want het is gewoon dat is de code die jullie moeten hebben. 

Wat is belangrijker is de terminal hier. En we hebben hier Waarom is het zo klein? Instellingen. Oh. True Ike. Hoe is dit? Daar weg. Is dat beter voor iedereen? OK ,. Cool. 

Je weet dat wanneer je in een CS class technische problemen zijn een soort van een deel van the-- Dus, laten we dit te wissen. OK. Dus, hier in doorsnede, die we hier hadden. Caesar is een uitvoerbaar bestand. Dus ik maakte het. Dus, een ding om te beseffen met GDB is dat het werkt alleen uitvoerbare bestanden. Dus, kun je niet draaien op een Dotsy. Je moet eigenlijk maken zeker van zijn dat je code compileert, en dat daadwerkelijk kan worden uitgevoerd. 

Dus, zorg ervoor dat als het niet compileren, krijgen om te compileren, zodat u kunt soort er doorheen lopen. Dus, om GDB beginnen, alles wat je doet, Gloria soort GDB, en dan gewoon de bestand dat u wilt. Ik misspell altijd Caesar. Maar je wilt er zeker van want het is een uitvoerbaar, dot flash ti's zodat betekent dat je gaat te lopen CSI je gaat om uit te voeren deze bestanden ofwel met de debugger. OK. Dus, heb je dat, dan krijg je dit soort onzin. Het is gewoon allemaal dingen over debugger. Je hoeft niet echt te zorgen te maken over het nu. En zoals je ziet, hebben we dit geopend parens, BBP, dicht parens, en gewoon een soort eruit ziet onze command line, toch? 

Dus, wat we willen doen-- -SO, Het eerste wat is dat we willen kiezen een plek om het te breken. Er is dus een bug in deze Caesar programma dat ik te introduceren, dat we gaan om uit te vinden. Het Wat het wel is duurt de input Barfoo in hoofdletters, en om wat voor reden het niet A. veranderen Het laat gewoon het alleen, Klopt alles anders, maar de tweede letter Een ongewijzigd. Dus, we gaan proberen erachter te komen waarom dat zo is. Dus, het eerste wat je meestal wilt doen wanneer je begint op GDB is erachter te komen waar het te breken. 

Dus Caesar is een vrij kort programma. We hebben slechts één functie, toch? Wat was onze functie in Caesar? Er is maar één functie, Main toch? Belangrijkste is een functie voor al uw programma's. Als je niet hoefde Main, zou ik zijn een beetje ongerust nu, maar ik hoop dat jullie allemaal Hoofd gehad daar. Dus, wat we kunnen doen is dat we kunnen gewoon breken Main, net als dat. Dus, zegt het, OK. We zetten onze breekpunt één daar. 

Zo, nu het ding om te onthouden is Caesar duurt een command line argument rechts en we hebben nog ergens dat niet gedaan. Dus, wat je doet is wanneer u ook daadwerkelijk te gaan uitvoeren het programma, een programma dat je bent lopen in GDB dat opdrachtregel nodig argumenten, je gaat om input wanneer u voor het eerst begint te lopen is. Dus, in dit geval, doen wij Draaien met een sleutel van de drie. En het zal daadwerkelijk beginnen. 

Dus, als je hier ziet, hebben wij Als RC niet gelijk is aan 2. Dus als jullie nog allemaal dat bestand dat ik stuurde up je zult zien dat dat is net als de eerste regel van onze belangrijkste functie, toch? Het is te controleren om te zien of we hebben het juiste aantal argumenten. Dus, als je je afvraagt Als RC juist is, kun je iets net zoals Print RC doen. RC is twee, wat wat we hadden verwacht, toch? 

Dus, kunnen we gaan Next, en verder door. Dus, we hebben een aantal belangrijke daar. En we kunnen onze key uitprinten om ervoor te zorgen dat klopt. Interessant. Niet helemaal wat we verwacht hadden. Dus, een ding om te beseffen met GDB ook is dat het niet tot u eigenlijk hit Vervolgens, dat de lijn die je net zag wordt daadwerkelijk uitgevoerd. Dus, in dit geval Key is nog niet toegewezen. Dus, Key is garbage waarde dat zie je op de bodem daar. Negatieve $ 120-- --Het's een miljard en iets wat vreemde dingen toch? Het is niet de sleutel die we verwacht hadden. Maar als we hit Volgende en we proberen en Print-toets, het is drie. 

Iedereen ziet dat? Dus, als je iets te krijgen dat je net als, wacht. Dit is volkomen verkeerd, en ik weet het niet hoe dit zou gebeuren, want alles wat ik wil te doen is een nummer, een variabele, proberen te raken Vervolgens probeer af te drukken het weer, en kijk of dat werkt. Want het gaat alleen om uit te voeren en eigenlijk na je iets toe te wijzen hit Volgende. Zinvol zijn voor iedereen? Uh huh? 

SPEAKER 2: Wanneer u willekeurig nummers wat betekent dat? 

SPEAKER 1: Het is gewoon willekeurig. Het is gewoon afval. Het is gewoon iets dat je computer zal willekeurig toe te wijzen. Cool. Zo, nu kunnen we door middel van bewegen, en dus nu hebben we deze platte tekst GetString. Dus, laat me introduceren wat zal gebeuren wanneer we hit Volgende hier. Onze GDB soort verdwijnt, toch? Dat komt omdat GetString wordt nu uitvoeren, toch? Dus, toen we zagen platte tekst is gelijk aan GetString open parens en parens, en we raken Next, dat heeft nu daadwerkelijk zijn uitgevoerd. Dus, het is het wachten op ons invoer iets. 

Dus, we gaan om input ons eten die is wat het is niet zoals ik het u gezegd en dat alleen maar zegt dat het afgewerkt uitvoeren, dat de gesloten beugel betekent dat het verlaten uit die lus. Dus, kunnen we hit Volgende, en nu, zoals ik ben ervoor dat je zijn allemaal bekend van Caesar, Dit is, wat is deze lijn gaan doen. Het is voor Int I gelijk is aan 0, N gelijk Strlen, platte tekst, en dan I is kleiner dan n, I, plus, plus. Wat is deze lus gaat doen? Open uw bericht. Cool. Dus, laten we beginnen met dat te doen. 

Dus, moet deze voorwaarde overeenkomen, voor onze eerste? Als het een B, het is platte tekst I. We u informatie over onze lokale bevolking te krijgen. Dus, I nul en indien zes die we verwachten, en onze sleutel is drie. Al die zin te maken, toch? Die alle cijfers precies wat ze moeten zijn. Dus, neuriën? SPEAKER 3: Ik heb willekeurige getallen voor de mijne. SPEAKER 1: Nou, we kunnen --we check-- kunnen chatten over dat in een tweede. Maar je moet het krijgen van deze. Dus, als we een hoofdstad B onze eerste, deze voorwaarde moet vangen, toch? Dus, als we geraakt Vervolgens zien we dat dit Als daadwerkelijk uitvoert. Want als je na langs in de code, deze lijn hier, waar platte tekst I wordt vervangen door deze rekenkundige, alleen uitgevoerd wanneer de If Voorwaarde is juist toch? 

GDB is alleen maar om te laten zien dingen die daadwerkelijk worden uitgevoerd. Dus als dit Als voorwaarde niet is voldaan, is het gewoon om naar de volgende regel. OK? Dus, we hebben dat. Deze beugel betekent dat het gesloten uit die lus nu. Dus, het gaat om opnieuw te beginnen. Net als dat. Dus, dat we informatie kunnen krijgen over onze locals hier, en we zien dat onze eerste brief is veranderd, toch? Het is nu een E, zoals het hoort. Dus, kunnen we verder. 

En we hebben deze controle. En deze controle zou moeten werken, toch? Het is A. Er wordt gewijzigd drie brieven naar voren. Maar als je merkt, we krijg je iets anders. Dus in dit geval hier, het gevangen het, en dus is deze lijn uitgevoerd, die onze B. gemodificeerd Maar hier casu we hebben dat het gewoon overgeslagen, en ging naar de [? L siff. ?] Dus iets aan de hand is daar. Wat dat vertelt je dat, we weten dat het hier zou moeten vangen, maar het is niet. Kan iedereen zien wat onze probleem is in die lijn? Het is een zeer minute ding. En je zou ook kunnen kijken naar uw code. Het is ook line-- vergeten welke lijn het is in er-- maar het is in de [onverstaanbaar]. Ja? 

SPEAKER 4: Het is op de meer dan pagina als je het gelezen in het boek. SPEAKER 1: Precies. Ja, kan de debugger niet vertellen je dat, maar de debugger kon u neer op een lijn waarvan u weet dat niet functioneert. En soms, als bijzonder later in het semester, toen je te maken hebt met een honderdtal, een honderd paar regels code, en je weet niet waar het is niet, dit is een geweldige manier om het te doen. Dus vonden we onze bug. U kunt het probleem te verhelpen in uw bestand, en dan kon je weer lopen, en alles zou perfect werken. En het grootste ding is Dit kan lijken, OK. Yeah. Cool. Je wist wat je zoekt. Dus, je wist wat te doen. 

GDB kan zijn super handig omdat je kunnen al deze dingen uit te printen die je zou niet. Het is veel nuttiger dan printf. Hoeveel van jullie gebruiken zoals printf statements om erachter te komen waar een bug was, toch? Dus, met dit, je doet niet moeten terug gaan houden, en graag commentaar in Printf, of commentaar uit, en erachter te komen wat moet u het afdrukken. Dit eigenlijk alleen maar kunt u stap door een afdruk van de dingen als je gaat door, zo kunt u observeren hoe ze veranderen in real-time, als je programma draait. 

En het vergt wel een beetje beetje wennen. Ik zou gewoon een soort bevelen van het zijn een beetje gefrustreerd met het voor nu. Als je een uurtje over de volgende week leren hoe te GDB gebruiken, je bespaart jezelf zoveel tijd later. En letterlijk. we vertellen Dit om mensen per jaar, en ik herinner me toen ik de klasse, was ik net, ik zal wel goed zijn. Nee Pset 6 kwam op en ik was als, ik ga leren hoe GDB gebruiken omdat ik niet weten wat er aan de hand hier. 

Dus als je de tijd dus neem gebruik het op kleinere programma's dat je gaat om te zijn werken aan, zoals het werken door iets als Visionare, zoals deze. Of als u extra oefening wilt, ik ben er zeker van Ik kon komen met buggy's, voor u om te debuggen als je wilt. 

Maar als je gewoon wat tijd nemen om te krijgen aan gewend, net om te spelen met het, het zal je echt goed van dienst zijn. En het is echt een van die dingen die je gewoon moeten proberen, en krijg je handen vuil met, voordat je echt begrijpen. Ik begreep het pas een keer Ik moest debug dingen mee, en het is veel leuker om een ​​idee te hebben hoe eerder vroeger dan later te debuggen. OK. Cool. Ik weet dat is een soort van een spoedcursus in GDB, en ik zal zeker werken aan het verkrijgen van deze groter volgende keer kijken. Cool. 

Dus, als we terug gaan naar onze PowerPoint. Gaat dit werken? AWH. Ja. OK. Dus, als je ooit een van nodig die weer is er de lijst. Dus Binary Search, waarbij iedereen herinnert zich de grote spektakel van David rippen telefoonboeken doormidden. Ik heb niet echt het telefoon boeken meer, want zoals waar moet je krijgen de telefoon boeken deze dagen? Ik weet het echt niet. De Binary Search. Herinnert iemand zich hoe Binary Search werkt? Wie dan ook? Yeah? SPEAKER 5: Je weet wanneer je kijkt naar waar de helft het in zou zijn, op basis van dat, en zich te ontdoen van de andere helft. 

SPEAKER 1 Precies. Dus, Binary Search, het is een soort van a-- --we graag noemen het verdeel en heers. Dus, wat je zult doen is je kijkt in het midden, en je zult zien of het overeenkomt wat u zoekt. En als dat niet het geval, dan probeer je erachter te komen, het gaat om te worden overgelaten de helft of de rechter helft. Dus, zou dit zijn als u op zoek bent naar iets dat is gealfabetiseerd, zie je, oh. Heeft Allison komt voor M? Ja. Dus, we gaan kijk naar de eerste helft. 

Of het kan worden als met getallen. Alles wat je kunt vergelijken, kan worden gesorteerd. U kunt binaire zoekopdracht op te gebruiken. Dus, iedereen die dit niet vergeten grafiek of wat dit is? Het is Asymptotische Complexiteit. Dus, deze grafiek net beschrijft hoe lang het neemt je mee naar een probleem op te lossen als u het aantal dingen te verhogen dat u gebruikt. 

We hebben dus N is lineaire tijd. Als N over twee, die enigszins is beter, nog steeds groeit super snel. En dan hebben we inloggen, dat is wat wij als Binary Search. Als we merken, als je probleem krijgt veel en veel groter, de tijd die het u kost om het op te lossen niet echt te verhogen dat veel. Het is net als vergelijkbare hier in het begin. Je bent net, OK. Alles wat hier niet echt uit welke we gebruiken, maar je uit tot een miljoen, een miljard. Je probeert some-- --you're vinden proberen om een ​​naald in een hooiberg te vinden. 

Ik denk dat je dit probleem wilt. U wilt deze complexiteit niet lineair, want voor alles wat je weet je gaat wel op zoek door middel van elke individuele naald, ding van hooi, proberen te kijken voor je naald. En dat is niet zo leuk in mijn mening. Ik hou van snel. Ik hou van efficiënt. En als hardwerkende studenten je jongens zijn, weet je slimmer werken, niet harder soort ding, hoe je kunnen maken van deze algoritmen. 

Dus, we gaan wandelen door slechts een snel voorbeeld. Ik denk dat jullie moeten hebben een hand op Binary Search, maar in het geval iemand is een beetje fuzzy, willen versterken, we gaan gewoon gaan door middel van een voorbeeld hier. Dus zijn we op zoek naar als de array bevat zeven. 

Dus, het eerste wat we doen is kijk in het midden, toch? En ook dat je gaat worden codering Binary Zoek in slechts een seconde. Dus het gaat leuk worden. Dus we kijken in de midden kleine arrays 3. Heeft 3 gelijk 7? Doet dat niet. Het is zes. Dus, is het minder dan of meer dan zeven? Minder dan. Ja. Nice job guys. Ik voel Graag zou hebben snoep omdat ik willen het uit te gooien in de werven. Het is wat ik ga volgende week doen. Het houdt je jongens scherp. 

Dus, gooien we weg, dat eerste helft, toch? het was minder dan. we weten dat alles op die linkerkant zal minder zijn dan wat we zijn eigenlijk op zoek naar. Dus, er is geen noodzaak om aandacht aan te besteden. Vergeet het dan maar. Zo, nu kijken we naar onze rechterhand, en we kijken naar het midden daar, en nu is het negen. Dus, 9 is-- --Everyone? Groter dan wat we op zoek naar, toch? Dus, we gaan gooien alles weg naar rechts. Als dat. Nu, zijn allemaal vertrokken we met één. Dus we controleren, is dit een wat we zoeken? is. We vonden wat we wilden. Dus we zijn klaar. Bilineaire Search. 

En als u merkt, we had zeven ingangen daar. Het kostte ons slechts als drie keer, maar als je aan het doen bent als een miljard, jullie weten hoeveel stappen het zou nemen als we hadden 4000000000 dingen? Elke gissingen? Het is 32. 32 stappen om iets te vinden in een 4000000000 element scala vanwege machten van twee. Dus twee om 32 is vier miljard dollar. 

Dus behoorlijk gek hoe je bent nog steeds binnen als een vrij klein aantal stappen iets in te 4000000000 elementen. Dus op die opmerking, we zijn gaat deze code dus jullie kunnen eigenlijk soort te zien hoe dit werkt. Oké, dus jullie kunnen coderen. Ik ga jullie laten praten voor een klein beetje. Krijgen om mensen om je heen weet, dat is wat iemand wilde van vorige paragraaf. 

Dus maak je de mensen om je heen te leren kennen. Praat voor een klein beetje. En alles wat ik van je wil jongens is nu net proberen om een ​​overzicht van pseudocode creëren. OK? Whoa. Alles wat ik wil van jullie is dat je gewoon gaan in dit geval, terwijl in te vullen. Dus ik heb deze bovenste set en ondergrenzen die vertegenwoordigen het begin en het einde van ons aanbod. En je gaat eigenlijk lus door en uitzoeken wat we doen binnen deze while lus. 

Dus als je kunt achterhalen out-- Ik heb een hint er-- wat zijn de gevallen dat we hier? Dus als je wilt achterhalen van de gevallen zullen wij pseudocode die en dan gaan we daadwerkelijk coderen hen. En het gaat worden, ik denken, hopelijk het zal een beetje makkelijker dan je verwacht. Want het is niet zo veel code, eigenlijk, dat is echt cool. 

Mm-hm? 

STUDENT: [onverstaanbaar]? INSTRUCTEUR: Ja. Er was iets te vinden in het midden. 

STUDENT: Dus kunnen we dat gebruiken. OK. 

INSTRUCTEUR: Perfect. Dus dat is het eerste wat we moeten doen. Dus vind het midden. Grote. Dus heb je een idee van hoe we zouden kunnen het midden met code eigenlijk vinden? 

STUDENT: Ja. n meer dan 2? INSTRUCTEUR: Zo n meer dan 2. Dus een ding om te onthouden is dat je bovenste en onderste grenzen veranderen. We blijven vernauwen de kant van de array zijn we op zoek naar. Dus n meer dan 2 zal alleen werken voor het eerste wat we doen. Zodat het nemen van de bovenste en onderste in aanmerking, hoe kunnen we dat midden element? Omdat we willen dat het midden tussen de bovenste en onderste, toch? Mm-hm? 

STUDENT: [onverstaanbaar]. 

INSTRUCTEUR: Dus we hebben een aantal midden. En het zal de bovenste plus lager dan 2 zijn. Awesome. Daar gaan we. Eén regel omlaag. Jullie zijn op weg. Dus nu hebben we onze midden, wat willen we doen? Gewoon in het algemeen. Je hoeft het niet te coderen. Ja. STUDENT: [onverstaanbaar]? INSTRUCTEUR: Dus het is plus omdat je het vinden van het gemiddelde tussen de twee daarvan. Dus als je denkt dat ze als soort verhogen vanaf de zijkanten, over nadenkt als je aanpak het midden, je wilt als dat. Als je aan beide zijden van de midden, en we hebben net 5 en 7. Als je ze bij elkaar optelt u krijg 12, je delen door 2, is 6. 

Soms is het moeilijk om uitleggen waarom dat werkt, maar als je door te werken Een voorbeeld soms het zal u helpen erachter te komen of Moet plus of min zijn. Ja. 

STUDENT: [onverstaanbaar] precies in het midden als ze een geval waarin er is een hoop kleinere aantallen en als een groot aantal? 

INSTRUCTEUR: Dus alles wat je nodig hebt is het midden van de array. Dus als je een bos van kleine aantallen hadden en dan een heel groot aantal op het einde, het maakt niet uit. Het enige dat telt is dat ze gesorteerd zijn, je gewoon willen kijken naar het midden van de array, omdat je nog steeds het snijden van uw probleem in de helft. Cool. Dus nu hebben we de midden, wat moeten we nu doen? 

STUDENT: Vergelijk. INSTRUCTEUR: Het vergelijken. Dus vergelijken midden om value_wanted. Cool. Zo zie je hier boven hebben wij deze waarde willen we hier. Vergeet niet dat dit een array. Dus midden verwijst naar de index. Dus we willen de waarden van de middenklasse te doen. Vergeet niet als je wilt te vergelijken, dubbel is. Je doet enkel gelijk je bent gewoon gaan om het opnieuw toewijzen, en dan, natuurlijk, het is gaat om de waarde die u wilt zijn. Dus doe dat niet. 

Dus we gaan om te zien of de waarden in het midden is gelijk aan de waarde die we willen. Vergeet je bretels. Dropbox zou weggaan. Dus wat doen we in dit geval? Als het is wat we willen terugkeren? We proberen te zeggen. 

STUDENT: Print uit. 

INSTRUCTEUR: Nou, we wil niet af te drukken. Dus dit is een bool hier, dus we willen waar of onwaar terug. We zeggen, is dit aantal een [? RRA? ?] Dus als het, we hebben net weer het waar. Als ik kan spellen waar. 

STUDENT: Waarom zou je niet nul terug te keren? INSTRUCTEUR: Dus je kon nul terug te keren als je wilde. Maar in dit geval, omdat onze functie retourneert een bool, we nodig hebben om waar of onwaar terug. STUDENT: Wanneer je bent zeggen boolean expressie, kan je het gelijk instellen op false? Net als ik wil zeggen, als deze voorwaarde niet is voldaan, zoals is bovenste gelijk vals. Zal het te begrijpen als je gewoon zet vals aan de andere kant? INSTRUCTEUR: Yeah. Dus eigenlijk als je ooit iets te doen zoals is boven- of lager is, dat waar of onwaar retourneert en het is eigenlijk slecht stijl aan zeg gelijk gelijk waar of gelijken gelijk aan vals. U wilt dat resultaat gebruiken zo zelf als uw cheque. Niet wat ik wilde. Dat is wat ik wilde. Dus in het geval van je vraagt over iets als sla dit in c. 

Dus als we int main (void) en iets als dit. En je hebt als is boven- van wat input en je bent de vraag of u kunt doen zoiets als dit? Right? STUDENT: Ik probeerde om het te doen [onverstaanbaar]. Want als it's-- INSTRUCTEUR: Right. Dus je wilt deze vals te zijn, toch? STUDENT: Ja. INSTRUCTEUR: Dus in dit geval je wil dat het uit te voeren als het niet waar is. Dus de koele ding je doet er dit. Dus onthoud uitroepteken punt ontkent dingen? Het zegt [onverstaanbaar] betekent niet. Dus als we kijken naar slechts dit deel hier, zou je zeggen dat evalueert naar valse zoals u dat wilt. Niet vals is waar die betekent dit zou uitvoeren. Heeft dat zin? STUDENT: Ja. INSTRUCTEUR: Awesome. OK. Dus we konden gewoon terug geldt in dit geval. Dus nu hebben we twee andere gevallen in dit geval. Wat zijn onze twee andere gevallen? Laten we het gewoon doen het op deze manier. Dus laten we beginnen met het andere als waarden in het midden kleiner is dan de waarde die we willen. Dus onze waarde in het midden is minder dan de waarde die we zoeken. 

Dus die gebonden je doet denk dat we willen updaten? Bovenste of onderste? Upper? Dus welke kant van de matrix gaan we op zoek naar? 

STUDENT: De onderste. 

INSTRUCTEUR: We gaan we te kijken naar de linkerkant. Dus anders als weinig waarde is minder. Dus je middelste waarde hier is minder dan wat we willen. Dus we willen het nemen rechterzijde van onze array. Dus we gaan werken onze ondergrens. Dus we onze lagere toewijzen. En wat denk je dat lager zou moeten zijn? STUDENT: De middelste waarde? INSTRUCTEUR: Dus het midden value-- STUDENT: Plus 1. INSTRUCTEUR: --plus 1. Kan iemand mij vertellen waarom we hebben dat plus 1? 

STUDENT: [? Geen waarde?] is gelijk aan. 

INSTRUCTEUR: Right. Omdat we weten al dat onze middelste waarde niet gelijk is aan het en we willen het uitsluiten Uit latere zoekopdrachten. Als je dat plus 1, dit vergeet zal voor onbepaalde tijd willen lus. En je zult gewoon in een gevangen worden oneindige lus en dan zul je segfault en dingen slecht gaan. Dus altijd voor zorgen dat je niet inbegrip van de waarde die u zojuist gekeken. Dus we zorgen dat met een plus 1. 

Dus nu hebben we onze laatste voorwaarde die ik altijd voor de zekerheid U kunt hier controleren, anders als waarde op het midden groter is dan de waarde we willen. Dat betekent dat we willen de linker helft. Dus die ene gaan we updaten? Upper. En wat is dit één gaan evenaren? Midden minus 1 omdat, natuurlijk, we willen om ervoor te zorgen dat we niet kijken naar dat middelste waarde weer. En dan hebben we het. Dat is het. Dat is alles binair zoeken is. Het is niet zo slecht, toch? Het is als 10 regels van code met witte ruimte. Dus zeer krachtig, zeer nuttig, je wil worden met behulp van het in een van je later psets. Misschien niet deze, maar later. Dus leer het. Love it. Het zal je goed behandelen. Dus heeft iemand enig hebben vragen over binary search? Ja. 

STUDENT: Maakt het uit of je n even of oneven? 

INSTRUCTEUR: No. Omdat we wierp het naar het midden als een int, zal het alleen maar afgekapt. Dus het een integer zal blijven en het zal uiteindelijk sorteren door alles. U hoeft zich dus geen zorgen te maken over dat. Iedereen goed? Awesome. Cool. Dus, jullie hebben dit. Slideshow. Dus als we het over hadden, weet ik David genoemde complexiteit looptijden. 

Dus in het beste geval, het is gewoon , waar we constante tijd noemen. Kan iemand mij vertellen waarom dat zou kunnen zijn? Wat voor soort scenario zou dat inhouden? Mm-hm. 

STUDENT: [onverstaanbaar] first-- INSTRUCTEUR: Dus het midden zijn de eerste element dat we komen om, toch? Dus ofwel een array van één of wat we ook op zoek bent naar net gebeurt er precies in het midden zijn. Dus dat is onze best case. U krijgt in de echte problemen, waarschijnlijk niet zal bereiken [onverstaanbaar] dat vaak. Hoe zit het met onze ergste geval? Onze slechtste geval is log n. En dat heeft te maken met de hele machten van twee ding dat ik over sprak. 

Dus in het slechtste geval zou betekenen dat we moesten de array omhakken totdat het een element van één. Dus moesten we het neer te hakken in de helft zo vaak als we maar konden. Dat is waarom het log n omdat je gewoon blijven delen door twee. Dus aannames, dingen die je moet weten als je ooit ga een binary search gebruiken. Uw elementen moeten worden gesorteerd. Ze moeten gesorteerd worden, omdat dat is de enige manier waarop je kan weten als je in staat bent te gooien de helft van het. 

Als je dit door elkaar gegooid zak had van nummers en je zegt, OK, ik ga naar het midden te controleren nummer en het nummer Ik ben op zoek naar is minder dan dat, ik ben gewoon gaan om willekeurig gooien de helft. Je zou het niet weten of uw getallen in de andere helft. Uw lijst gesorteerd moet worden. Als goed, kan dit verder te gaan een beetje, maar je moet random access hebben. Je moet in staat zijn om gewoon naar die tussenstuk. Als je moet doorkruisen door iets of kost het je extra stappen dat tussenstuk te krijgen, het is niet meer, omdat log n je bent meer werk toe te voegen in. En dit zal een beetje te maken meer zin in twee weken, maar ik gewoon een soort van wilde inleiden, geven jullie een idee van wat er komen. Maar dat zijn de twee belangrijke aannames die je nodig hebt voor een binaire lijst. Zorg ervoor dat het is opgelost. Dat is de grote voor jullie nu. En op dat we kunnen gaan in de rest van onze soort. Dus vier sorts-- bubble, inbrengen, selectie, en merge. Ze zijn allemaal wel cool. Als jullie besluiten om CS 124 te nemen, leer je over allerlei soorten. En als je een XKCD fan, er is een echt cool strip over hou echt ineffectief soorten, die ik raden u gaan kijken. Eén van hen is als paniek soort, die is als, oh nee, terug willekeurige array. Shutdown systeem. Verlaat. Dus geeky humor is altijd goed. 

Dus heeft iemand herinneren soort van als slechts een algemeen idee hoe bubble sort werkt. Herinnert u zich? 

STUDENT: Ja. 

INSTRUCTEUR: Go for it. 

STUDENT: Dus je gaat door en als het is groter, dan wisselen de twee. 

INSTRUCTEUR: Mm-hm. Precies. Dus je gewoon doorlopen. Je controleert twee nummers. Als de vorige groter dan die daarna, je ze gewoon verwisselen, zodat in Zo alle hogere nummers bubble tegen het einde van de lijst en al de lagere aantallen bubble naar beneden. 

Heeft hij laten zien dat jullie de koele geluidseffect sorteren video? Het is wel cool. Dus zoals Robert al zei, het algoritme dat je gewoon door de lijst, omwisselen van de aangrenzende waarden als ze niet in orde is. En dan gewoon blijven herhalen totdat je geen swaps maken. Dus niet slecht, toch? Dus we hebben gewoon een snelle voorbeeld hier. Dus dit gaat te sorteren ze in oplopende volgorde. Dus toen we door de eerste tijd, we kijken door middel van acht en zes zijn uiteraard niet in orde is, wisselen we ze. 

Dus kijk naar de volgende. Acht en vier niet in orde. Ze te verwisselen. En dan acht en twee, ruil ze. Daar gaan we. Dus na je eerste pas, je weten dat uw grootste aantal zal de manier aan de top, want het is gewoon zal voortdurend groter dan al het andere en het is gewoon te borrelen up helemaal tot het einde daar. Is dat zinvol is voor iedereen? Cool. 

Dus dan kijken we naar onze tweede pass. Zes en vier, switch. Zes en twee, switch. En nu hebben we een paar dingen in orde. Dus voor iedere pas die we maken door middel van onze hele lijst, we weten dat als dat veel nummers eind zal zijn gesorteerd. Dus we doen een derde pas, dat is een swap. En dan op onze vierde passeren, we hebben nul slots. En zo weten we dat onze serie is gesorteerd. 

En dat is het grote ding met bubble sort. We weten dat wanneer we hebben nul swaps, dat betekent dat alles is volledig in orde. Het is een soort van hoe we controleren. Dus we gaan ook bubble coderen soort die ook niet zo slecht. Geen van deze zijn zo slecht. Ik weet dat ze kan lijken een beetje eng. Ik weet dat toen ik de klas, zelfs wanneer ik onderwees de klasse voor de eerste keer vorig jaar, Ik was als, hoe kan ik dit doen? Het is zinvol in theorie, maar hoe kunnen we eigenlijk doen? Dat is waarom ik wil ook lopen door middel van code met jullie hier. Dus ik heb een pseudocode voor jullie deze keer. Dus gewoon dit in gedachten te houden als we gaan dan de overgang. Dus we hebben een aantal teller die houdt onze swaps, want we moeten ervoor zorgen dat we controleren dat. En we herhalen het hele array zoals we net hebben gedaan met dit voorbeeld. Indien het element vóór groter is dan het element na waar we aan, we ze te verwisselen en we verhogen ons teller want zodra we ruilen, willen we laten onze balie weten dat. Heeft u vragen daar? Iets lijkt grappig hier. STUDENT: Heeft u de teller op nul te zetten elke keer als je door de lus? Hoef je niet te gaan terug naar elke keer nul? INSTRUCTEUR: Niet per se. Dus wat er gebeurt is dat we hier gaan door. Dus doen terwijl, denk eraan, dit zal een keer uit te voeren zonder falen. Dus het gaat om het stellen teller gelijk aan nul, dan dat het gaat om door te herhalen. Als het doorloopt, het zal teller updaten. Zoals het een bijwerking teller, wanneer het klaar is, wanneer het aan het einde van de array, als onze lijst niet zijn gesorteerd, teller zal zijn bijgewerkt. 

Dus dan wordt de toestand en het zegt, OK, is teller groter dan nul. Als het is, doe het opnieuw. U wilt dus dat wanneer je reset doorlopen, teller gelijk aan nul. Als je door een gesorteerde array, niets verandert, dit niet lukt, en je de terugkeer van de gesorteerde lijst. Is dat zinvol? STUDENT: Het zou in een klein beetje. INSTRUCTEUR: OK. Als er een andere vraag die omhoog komt. Ja. 

STUDENT: Wat zou de functie zijn voor het omwisselen van de elementen? 

INSTRUCTEUR: Dus we kunnen eigenlijk schrijven dat als we gaan nu rechts. Cool. Dus op deze nota, is Alison gaat terug naar het apparaat schakelen. Het zal leuk zijn. En we hebben onze mooie bubble sort ding hier. Dus ik al fietsen deed door de matrix. We hebben onze swaps die gelijk aan nul. Dus we willen ruilen aangrenzende elementen als ze niet in orde. Dus het eerste wat we moeten do wordt doorlopen ons aanbod. 

Dus hoe denk je dat we misschien doorlopen van ons aanbod? We hebben voor en i gelijk is aan 0. We willen dat ik minder te zijn dan n min 1 min k. En ik zal uitleggen dat in een tweede. Dus dit is een optimalisatie hier, waar, herinneren hoe ik zei na elke pas door de array we weten dat wat er ook on-- 

Dus na één pas we weten dat dit wordt gesorteerd. Na twee passen we weten dit alles wordt gesorteerd. Na drie passen we weten dat er gesorteerd worden. Dus de manier waarop ik ben itereren hier door de matrix, wordt het is en zorg ervoor dat alleen gaan door wat we weten is ongesorteerd. OK? Dat is gewoon een optimalisatie. Je zou het naïef te schrijven gewoon itereren door alles heen, het zou alleen maar langer duren. Met deze vier lus is het gewoon een leuke optimalisatie omdat we weten dat er na elke volle iteratie door de array hier, zoals elke volle loop hier, we weten dat één van deze elementen wordt gesorteerd eind. 

We hoeven dus geen zorgen te maken over die. Is dat zinvol is voor iedereen? Die koele trucje? Dus in dat geval, als we iteratie, we weten dat we willen controleren of array-n en n + 1 in orde zijn. OK. Dus hier is de pseudocode. We willen om te controleren of serie n en n plus 1 in orde zijn. Dus wat kunnen we daar? Het zal een aantal voorwaarden worden gekoppeld. Het zal een if. 

STUDENT: Als scala n minder dan scala n plus 1. INSTRUCTEUR: Mm-hm. Wel, kleiner of groter dan. STUDENT: Groter dan. Dan willen we ze te verwisselen. Precies. Dus nu komen we in wat is het mechanisme voor swapping hen? Dus gingen we door middel van dit kort, een soort swap functie vorige week. Heeft iemand nog hoe het werkte? Dus we kunnen niet zomaar opnieuw toewijzen hen, toch? Omdat één van hen zal verdwalen. Als we zeiden A is gelijk aan B en vervolgens B gelijk is aan A, alle ineens beiden zijn gelijk aan B. 

Dus wat we moeten doen is dat we een tijdelijke variabele die gaat een van ons, terwijl houden we zijn in het proces van swappen. Dus wat we hebben is dat we u een aantal int hebben temp is gelijk to-- je het kan toewijzen aan welke u wilt, gewoon zorg ervoor dat u spoor van het-- houden dus in dit geval, ik ga toewijzen aan array-n plus 1. Dus dat gaat houden wat waarde in die tweede blok dat we naar kijken. 

En dan kunnen we doen is dat we kunnen gaan vooruit en ken scala n plus 1, omdat we weten dat we hebben dat opgeslagen waarde. Dit is een van de grote things-- Ik weet niet of iemand van jullie had problemen waar als je twee schakelen regels code plotseling dingen werkten. Volgorde is zeer belangrijk in CS. Dus zorg ervoor dat je diagram dingen uit, indien mogelijk als om wat er daadwerkelijk gebeurt. Dus nu gaan we naar toewijzen scala n plus 1, omdat we weten dat we hebben dat opgeslagen waarde. 

En we kunnen toewijzen die array n of in dit geval serie i. Te veel variabelen. OK. Dus nu hebben we opnieuw toegewezen reeks i plus 1 te evenaren wat er in reeks i. En nu kunnen we terug te gaan en toewijzen scala ik aan wat? Anyone? 

STUDENT: 10. 

INSTRUCTEUR: 10. Precies. En een laatste ding. Als we het nu hebben verwisseld, wat hebben we nodig om te doen? Wat is het een ding dat gaat ons vertellen als we ooit dit programma te beëindigen? Wat vertelt ons dat we hebben een gesorteerde lijst? Als we geen swaps uit te voeren, toch? Als swaps is gelijk aan nul aan het einde van deze. Dus wanneer je een swap uit te voeren, zoals we gewoon hier deden, we willen swaps updaten. En ik weet dat er een vraag eerder over dan kunt u Gebruik nul of één plaats van waar of onwaar. En dat is wat dit hier doet. Dus dit zegt als niet swaps. Dus als swaps is nul, wat ik altijd is-- krijg mijn waarheden en mijn falses door elkaar. We willen ons om te evalueren om waar en het is niet. Dus als het nul is, dan is het vals. Als je het ontkennen met een [? bang?] het waar wordt. Dus dan is deze lijn voert. 

Waarheden en valse en nullen en enen gek. Net als je langzaam lopen doorheen het zal zinvol. Maar dat is wat deze kleine stukje code hier doet. Dus dit controleert hebben we gedaan elke swaps. Dus als het even wat naast nul, het gaat vals te zijn en de hele zaak is gaat opnieuw uit. Cool? 

STUDENT: Wat doet break doen? 

INSTRUCTEUR: Break net breekt u uit de lus. Dus in dit geval zou net als het einde van het programma en je zou gewoon hebben uw gesorteerde lijst. STUDENT: Amazing. INSTRUCTEUR: Het spijt me? STUDENT: Omdat we eerder gebruikte geschreven 1 overschreven nul presenteren dat als dat zal niet werken of niet. 

INSTRUCTEUR: Yeah. Dus u kunt nul of 1 terug te keren. In dit geval, omdat we niet echt iets te doen met de functie, we willen gewoon het te breken. We niet echt zorgen over. Rem is ook goed als het wordt gebruikt voor het breken uit vier lussen of condities die u niet wilt behouden uitvoeren. Het kost je gewoon van hen. Het is een beetje een nuance ding. Ik heb het gevoel alsof er veel wuivende hand, als je leert over dit binnenkort. 

Maar leer je over dit binnenkort. Ik beloof het. OK. Dus doet iedereen krijgt bubble sort? Niet al te slecht. Doorloopt, swap dingen met behulp van een temp variabele, en we zijn er allemaal ingesteld? Cool. Awesome. OK. Terug naar de PowerPoint. Heeft u vragen in het algemeen over deze tot nu toe? Cool. Mm-hm. 

STUDENT: [onverstaanbaar] int main meestal. Heeft u te hebben dat voor dit? 

INSTRUCTEUR: Dus we waren gewoon op zoek alleen op de eigenlijke sorteren algoritme. Als je het had binnen als een groter programma, zou je een int main ergens hebben. Afhankelijk van waar u Gebruik algoritme, het zou bepalen wat er wordt geretourneerd door het. Maar voor ons geval, we zijn strikt kijken naar hoe werkt dit eigenlijk doorlopen van een array. Dus we hebben geen zorgen over te maken. 

Dus hadden we het over het beste geval en worst-case scenario's voor binary search. Dus het is ook belangrijk om te doen dat voor elk van onze soorten. Dus wat denk je dat is het ergste Bij runtime van bubble sort? Jullie herinneren? 

STUDENT: N min 1. INSTRUCTEUR: N min 1. Dus dat betekent dat er n minus 1 vergelijkingen. Dus een ding om te beseffen is dat op de eerste iteratie, we gaan door, we vergelijken deze two-- dus dat is 1. Deze twee, drie, vier. Dus na een iteratie we al vier vergelijkingen. Toen ik het over runtime en n. N het aantal vergelijkingen als functie van het aantal elementen we hebben. OK? 

Dus doorlopen we, hebben we vier. De volgende keer dat je weet dat we dat niet doen moeten zorgen voor dit. We vergelijken deze twee, beide deze twee, en als we niet hebben dat optimalisatie met de vier lus die ik heb geschreven, je zou hier een vergelijking in anyways. Dus je zou moeten lopen door de array en maak n vergelijkingen n tijden, want elke keer als we er doorheen lopen we eigenlijk een ding. 

En elke keer als we lopen door de array, maken we n vergelijkingen. Dus onze runtime hiervoor is eigenlijk n kwadraat, die is veel erger in onze inloggen end want dat betekent dat als we hadden vier miljard elementen, het gaat ons 4000000000 kwadraat ipv 32. Dus niet de beste runtime, maar voor sommige dingen, weet je, als je binnen een bepaald bereik van elementen bubble sort kan zijn prima te gebruiken. 

OK. Dus nu wat is de beste case runtime? STUDENT: Zero? Of 1? 

INSTRUCTEUR: Dus 1 zou één vergelijking. Right. 

STUDENT: N min 1? 

INSTRUCTEUR: Dus, ja. Zo n minus 1. Wanneer heb je een concept als n minus 1, hebben we de neiging om gewoon deze inleveren en we gewoon zeggen n omdat je elk van these-- elk paar vergelijken. Zo zou n minus 1, welke we we gewoon zou zeggen dat is ongeveer n. Wanneer je te maken hebt met runtime, alles is in bij benadering. Zolang de exponent correct, je bent behoorlijk goed. 

Dat is hoe we omgaan met het. Zodat het beste geval is n, dat betekent dat de lijst al is gesorteerd, en alles wat we doen wordt gerund door en controleer of het is opgelost. Cool. Prima. Dus zoals je hier ziet, we gewoon wat meer grafieken. Zo n kwadraat. Fun. Veel slechter dan n zoals we zien, en veel, veel erger dan log 2n. En dan krijg je ook in logboek logboeken. En je 124 nemen, krijg je in als log ster, die is als een gek. Dus als je geïnteresseerd bent, lookup log ster. Het is wel leuk. Dus we hebben deze grote grafiek. Gewoon een heads up, dit een prachtige grafiek om te hebben voor de middellange termijn, omdat we lang om u te vragen deze dunner. Dus gewoon een heads up, heb dit op uw tussenbalans op uw mooie spiekbriefje daar. Dus we keken naar bubble sort. Worst case, n kwadraat, best case, n. En we gaan kijken naar de anderen. 

En zoals je kunt zien, de enige een die echt goed doet is merge soort, die we zullen krijgen in waarom. Dus we gaan naar de volgende hier-- selectie sorteren. Heeft iemand nog hoe selectie sorteren gewerkt? Ga ervoor. 

STUDENT: In principe gaan door een bestelling en maak een nieuwe lijst. En net als je het aantrekken elementen in, leg ze op de juiste plaats in de nieuwe lijst. 

INSTRUCTEUR: Dus dat geluiden meer als insertion sort. Maar je bent echt dichtbij. Ze zijn zeer vergelijkbaar. Zelfs ik ze door elkaar soms. Voordat deze sectie Ik was als, wacht. OK. Dus wat je wilt doen is selectie sorteren, de manier waarop je kunt bedenken over en de weg Ik zorg ervoor dat ik probeer niet te krijgen ze door elkaar, is gaat het door en selecteert de kleinste getal en het zet dat aan het begin van uw lijst. Hij ruilt het met die eerste plek. Ze hebben eigenlijk een voorbeeld voor mij. Awesome. Dus gewoon een manier om te denken van het-- selectie sorteren, selecteert u de kleinste waarde. En we gaan Onderstaand voorbeeld van dat ik denk dat zal helpen, want Ik denk visuals altijd helpen. Dus we beginnen met iets dat is volkomen ongesorteerd. Red zal ongesorteerd zijn, groen worden gesorteerd. Het zal allemaal zin in een tweede. 

Dus gaan we door en we herhalen van het begin tot het einde. En we zeggen, OK, 2 is onze kleinste getal. Dus we gaan nemen 2 en we gaan om het te verplaatsen naar de voorkant van ons aanbod want het is de kleinste getal hebben we. Dus dat is wat dit hier doet. Het gaat gewoon om te wisselen die twee. Dus nu hebben we een gesorteerde deel en een ongesorteerd deel. En wat is goed om te onthouden over selectie sorteren is dat we alleen selecteren uit het ongesorteerde deel. 

De gesorteerde deel je gewoon laat staan. Mm-hm? 

STUDENT: Hoe weet het wat is de kleinste zonder het te vergelijken elke andere waarde in de array. INSTRUCTEUR: Het doet vergelijken. Wij willen overgeslagen. Dit is gewoon algemeen algemeen. Yeah. Wanneer we de code schrijven ben ik zeker dat je meer tevreden. Maar je deze eerst op te slaan element als kleinste. U vergelijkt en je zeggen, OK, is het kleiner? Ja. Keep it. Hier is het kleiner? Nee? 

Dit is uw kleinste, toewijzen aan uw waarde. En je zult veel gelukkiger zijn toen we door de code. Dus we gaan door, ruilen we het, dus dan we kijken naar deze ongesorteerd deel. Dus we gaan naar drie te selecteren. We gaan om het aan te zetten op het einde van onze gesorteerde gedeelte. En we gaan gewoon blijven doen dat, om dat te doen, en dat doen. Dus dit is onze soort pseudocode hier. We zullen het coderen hier in een tweede. Maar gewoon iets om te lopen door op een hoog niveau. Je gaat om te gaan van i gelijk is aan 0 tot n minus 2. Dat is een andere optimalisatie. Niet te veel zorgen over te maken. Dus zoals je zei. Zoals Jacob zei, hoe doen we bijhouden wat onze minimum is? Hoe weten we dat? We moeten vergelijken alles in onze lijst. 

Dus minimum is gelijk aan i. Het is gewoon te zeggen in dit geval de index van onze minimale waarde. Dus dan is dat het gaat om door te herhalen en het gaat van j i gelijk plus 1. Dus we weten al dat dat is onze eerste element. We hoeven niet te vergelijken met zichzelf. Dus beginnen te vergelijken met de volgende een die is waarom het i plus 1 tot n minus 1, die de einde van de array zijn. En we zeiden dat als array j is dan matrix min, vervolgens toewijzen we waar onze minimale indices is. 

Als min niet gelijk i, zoals in waar waren we terug over hier. Dus als toen we voor het eerst deed dit één. In dit geval zou het beginnen nul, het zou uiteindelijk op twee. Zo min zou niet gelijk ik in het einde. Dat laat ons weten dat we nodig hebben om ze te verwisselen. Ik voel me als een concreet voorbeeld zal veel meer dan dit te helpen. Dus ik zal deze code met jullie op dit moment en ik denk dat het zal beter zijn. 

Soorten hebben de neiging om op die manier in die werken is het vaak beter gewoon om ze te zien. Dus wat we willen doen is we willen eerst de kleinste element in zijn positie in de array. Precies wat Jacob zei. Je moet een of andere manier op te slaan dat. Dus we gaan hier beginnen itereren over de array. We gaan om te zeggen dat het onze eerste net beginnen. Dus we gaan int hebben kleinste is gelijk aan scala aan i. 

Dus een ding om op te merken, elke tijd deze lus wordt uitgevoerd, starten we een stap verder mee. Wanneer we beginnen we kijken naar deze. De volgende keer dat we doorlopen, we beginnen bij deze ene en toe te wijzen onze kleinste waarde. Dus het is zeer vergelijkbaar met bubble sort waarvan we weten dat na één passage, dit laatste element wordt gesorteerd. Met selectie sorteren, het is juist het tegenovergestelde. 

Bij elke pas, weten we dat de eerste wordt gesorteerd. Na de tweede pas, de zal tweede gesorteerd worden. En als je zag met de glijbaan voorbeelden, onze naargelang deel maar door blijft groeien. Dus door het instellen van onze kleinste arrays ik, alles wat het aan het doen is beperkt het wat we kijken naar zo het nummer minimaliseren van vergelijkingen die we maken. Is dat zinvol voor iedereen? Hou je me nodig hebt om te draaien door die weer langzamer of in andere woorden? Ik ben blij om. OK. 

Dus we zijn het opslaan van de waarde op dit punt, maar we willen ook de index op te slaan. Dus we gaan naar de winkel positie van de kleinste één, die net gaat i zijn. Dus nu Jacob is tevreden. We hebben dingen opgeslagen. En nu moeten we kijken door het ongesorteerde deel van de array. Dus in dit geval is dit zou onze ongesorteerd zijn. Dit is i. OK. 

Dus wat we gaan doen zal voor een lus. Wanneer u maar wilt doorloopt een array, je geest kon gaan voor een lus. Dus voor sommige int k equals-- wat vinden we k zal gelijk beginnen? Dit is wat we als onze kleinste waarde en we willen om het te vergelijken. Wat willen we te vergelijken met? Het gaat om deze volgende, toch? Dus we willen k te worden geïnitialiseerd i plus 1 beginnen. 

En we willen dat k in dit geval hebben we al hebben de grootte hier opgeslagen up, dus we kunnen gewoon gebruik maken van de grootte. Maat zijnde de grootte van de matrix. En we willen gewoon bijwerken k telkens met één. Cool. Dus nu moeten we vinden het kleinste element hier. Dus als we doorlopen, we willen zeggen, als array k is minder dan onze kleinste value-- dit is waar we eigenlijk het bijhouden van wat er de kleinste hier-- dan willen we toewijzen wat onze kleinste waarde is. 

Dit betekent dat, oh, we zijn iteratie hier. Wat waarde hier niet onze kleinste ding. We willen het niet. We willen deze grond. Dus als we het opnieuw toewijzen van het, wat doen je denkt misschien in deze code hier? We willen toewijzen kleinste en positie. Dus wat is het kleinste nu? STUDENT: Array k. INSTRUCTEUR: Array k. En wat is de positie nu? Wat is de indices van onze kleinste waarde? Het is gewoon k. Dus scala k, k, ze met elkaar overeenkomen. Dus wilden we opnieuw toekennen. En dan na vonden we onze kleinste, zodat aan het einde van deze lus hier hebben we gevonden wat onze kleinste waarde is, dus we wisselen het gewoon. In dit geval, net als zeggen dat onze kleinste waarde is hier. Dit is onze kleinste waarde. 

We willen alleen maar om het hier te ruilen, dat is wat dat swap-functie op de bodem deed, die we zojuist schreef samen een paar minuten geleden. Dus het zal geen groot probleem. En dan zal het alleen maar herhalen door tot het helemaal bereikt aan het einde, waardoor u hebben nul elementen die ongesorteerde en alles is gesorteerd. Zinvol? Een beetje meer concreet? De code helpen? 

STUDENT: Voor een grootte, die u nooit echt het definiëren of wijzigen, hoe weet het? 

INSTRUCTEUR: Dus een ding om merken hier is int size. Dus we zeggen in dit sort-- soort is een functie in deze case-- het selectie soort, het is voorbij met de functie. Dus als het niet is overgegaan in, zou je iets doen zoals de lengte van de array of zou je via herhalen de lengte vinden. Maar omdat het is voorbij in, kunnen we gewoon gebruiken. U aanvaardt alleen dat de gebruiker gaf je een geldig formaat dat vertegenwoordigt eigenlijk een grootte van uw array. Cool? 

Als jullie problemen hebt met deze of wilt u meer praktijk codering soorten op uw eigen, moet u ga naar study.cs50. Het is een hulpmiddel. Ze hebben een checker dat kan je eigenlijk schrijven. Ze doen pseudocode. Zij hebben meer video's en dia's inclusief degenen die ik hier gebruik. Dus als je nog steeds het gevoel een beetje wazig, probeer dat uit. Zoals altijd, kom met me praten, ook. Vraag? 

STUDENT: Bedoel je dat de maat is eerder gedefinieerd? INSTRUCTEUR: Ja. Grootte is eerder gedefinieerde up hier in de functie declaratie. Zodat u ervan uitgaan dat het is aangenomen in door de gebruiker, en voor het gemak, we gaan ervan uit dat de gebruiker gaf ons de juiste maat. Cool. Dus dat is selectie sorteren. Jongens, ik weet dat we veel leren vandaag. Het is een dichte gegevens voor sectie. Dus met dat gaan we naar insertion sort. 

OK. Dus voordat dat we moeten doen onze runtime analyse hier. Dus in het beste geval, verleend, omdat ik je liet zien de tafel heb ik al soort gaf het weg. Maar het beste geval runtime, wat vinden we? Alles gesorteerd worden. N kwadraat. Iedereen heeft een verklaring waarom je denkt? 

STUDENT: je vergelijkt through-- INSTRUCTEUR: Right. Je vergelijkt door. Bij elke iteratie, hoewel we decrementing dit door één, je bent nog steeds op zoek door middel van alles tot in de kleinste een te vinden. Dus zelfs als uw kleinste waarde is hier aan het begin, je bent het nog steeds te vergelijken tegen al het andere om ervoor te zorgen dat het de kleinste ding. Dus zul je uiteindelijk doorheen ongeveer n kwadraat tijden. Prima. En wat is het ergste geval? Ook n kwadraat want je gaat te doen, dat dezelfde procedure. Dus in dit geval, selectie heeft een soort iets dat we ook bellen verwachte runtime. Dus in de anderen, we weten gewoon de bovenste en onderste grenzen. Afhankelijk van hoe gek onze lijst is of hoe ongesorteerd het is, ze variëren tussen n en n kwadraat. We weten het niet. 

Maar omdat selectie soort heeft dezelfde slechtste en het beste geval, dat ons vertelt dat het maakt niet uit wat voor soort input die we hebben, of het nu helemaal gesorteerde of volledig achteruit naargelang, het is naar dezelfde hoeveelheid tijd. Dus in dat geval, als je herinneren uit onze tafel, het eigenlijk had een waarde deze twee soorten niet hebben, die verwacht runtime. Zodat we weten dat wanneer we lopen selectie sorteren, het is gegarandeerd om uitvoeren van een n kwadraat tijd. Er is geen variatie zijn. Het is gewoon te verwachten. En, nogmaals, als je wilt leren meer, neem CS 124 in het voorjaar. Prima. We hebben dit gezien. Cool. Dus insertion sort. En ik ga waarschijnlijk ontbrandde nu doorheen. Ik wil niet dat jullie het coderen. We zullen gewoon doorheen lopen. Dus insertion sort is een soort van vergelijkbaar selectie sorteren dat we zowel ongesorteerd en gesorteerd deel van de array. 

Maar wat is er anders is dat als we door een voor een, we gewoon nemen wat het aantal is de volgende in onze ongesorteerd, en correct sorteren van het in onze gesorteerde array. Het zal meer zin te maken met een voorbeeld. Dus alles begint als ongesorteerd, net als met de selectie sorteren. En we gaan deze te sorteren oplopende volgorde, zoals we zijn geweest. Dus op onze eerste pas We nemen de eerste waarde en wij zeggen, OK, je bent nu in een lijst door uzelf. 

Omdat je in een lijst door jezelf, je gesorteerd worden. Proficiat voor het zijn de eerste element in de array. Je bent al al naargelang op uw eigen. Dus nu hebben we een gesorteerde en een ongesorteerde array. Dus nu nemen we de eerste. Wat gebeurt er tussen hier en hier is dat we zeggen, OK, we gaan kijken naar de eerste waarde van onze ongesorteerde reeks en we gaan invoeren in zijn juiste plaats in de gesorteerde array. 

Dus wat we doen is nemen we 5 en we zeggen, OK, 5 groter is dan 3, dus voegen we het precies goed naar rechts daarvan. We zijn goed. Dus dan gaan we op naar onze volgende. En we nemen 2. Wij zeggen, OK, 2 minder dan 3, dus we weten dat het moet op de voorkant van onze lijst nu. Dus wat we doen is dat we duwen 3 en 5 naar beneden en we bewegen 2 in die eerste sleuf. Dus we zijn gewoon deze in de juiste plaats het zou moeten zijn. 

Dan kijken we naar onze volgende, en we zeggen 6. OK, 6 is groter dan alles in ons gesorteerde array, dus we taggen het op tot het einde. En dan kijken we naar 4. 4 kleiner dan 6, is het minder dan 5 maar het is groter dan 3. Dus we steken het gewoon recht in het midden tussen 3 en 5. Zo te maken dat een beetje beetje meer concreet, hier is een soort van de idee van wat er gebeurd is. Dus voor elk ongesorteerd element, we bepalen waar in de gesorteerde gedeelte is. 

Dus rekening houdend met de gesorteerd en ongesorteerd, we moeten doorkruisen door en figuur waar het in de gesorteerde array past. En we voegen er door het verschuiven van de elementen rechts van beneden. En dan houden we gewoon itereren door tot we hebben een volledig gesorteerde lijst waar ongesorteerd is nu nul en gesorteerde neemt de totaliteit van onze lijst. Dus, nogmaals, om dingen nog te maken meer concreet, we hebben pseudocode. 

Dus eigenlijk voor i is gelijk aan 0 tot n minus 1, dat is gewoon de lengte van ons aanbod. We hebben een element dat gelijk is de eerste array of de eerste indices. We j gelijk aan die. Dus terwijl j groter is dan nul en de array, j minus 1 groter is dan de element, dus alles wat het doen is ervoor te zorgen dat je j echt vertegenwoordigt het ongesorteerde deel van de array. 

Dus terwijl er nog steeds dingen te sorteren en j min één is-- wat is het element van haar? J werd hier nooit gedefinieerd. Het is een beetje vervelend. OK. Anyways. Dus j minus 1, u controleren bent het element voordat het. Je zegt, OK, is het element voordat waar ik am-- laten eigenlijk trekken dit uit. Dus laten we zeggen dat dit zoals op onze tweede pass. Dus ik zal gelijk zijn 1, welke hier. 

Dus ik zal gelijk aan 1 zijn. Dit zou 2, 4, 5, 6, 7. Prima. Dus onze element in dit geval gaat gelijk aan 4 is. En we hebben een aantal j dat is gaan gelijk aan 1 zijn. Oh, j wordt decrementing. Dat is wat het is. Dus j is gelijk aan i, dus wat is dit gezegde is dat als we vooruit, we zijn gewoon om ervoor te zorgen dat we niet meer dan indexeren op deze manier wanneer we proberen om dingen in te voegen in onze gesorteerde lijst. 

Dus wanneer j gelijk is aan 1 in dit geval array-j minus een-- zo scala j minus 1 2 is in dit case-- als dat is groter dan het element, dan dit alles doet verschuift dingen naar beneden. Dus in dit geval, array j min één zou scala nul, dat is 2 te zijn. 2 niet groter is dan 4, zodat deze niet wordt uitgevoerd. Dus de verschuiving niet beweegt naar beneden. Wat dit doet is vaak precies het verplaatsen van uw gesorteerde array naar beneden. In dit geval, eigenlijk, we kon doen-- laten we deze 3. Dus als we om door te lopen met dit voorbeeld zijn we nu hier. Dit wordt gesorteerd. Dit is ongesorteerd. Cool? Dus ik gelijk aan 2, dus onze element gelijk aan 3. En onze j gelijk is aan 2. Dus we kijken door en wij zeggen, OK, is het scala j min één groter dan het element dat we naar kijken? En het antwoord is ja, toch? 4 is groter dan 3 en j is 2, dus deze code wordt uitgevoerd. 

Dus nu doen we een scala aan 2, dus hier, ruilen we ze. Dus we gewoon zeggen, OK, array 2 is zal meer 3. En j gaat evenaren j minus 1, die 1. Dat is verschrikkelijk, maar jullie krijgen het idee. J is nu gelijk aan 1. En de vele j is gewoon gaat worden gelijk aan ons element, waarvan 4 was. Ik gewist iets wat ik niet zou moeten hebben of miswrote iets, maar jullie krijgen het idee. 

Het bewegen op n. En dan als dit, het zou lus weer en het zou zeggen, OK, j is 1 nu. En de vele j minus 1 is nu 2. Is 2 minder dan onze element? Nee? Dat betekent dat we hebben ingevoegd dit element in de juiste plaats in onze gesorteerde array. Dan kunnen we hier rekening en wij zeggen, OK, onze gesorteerde array is hier. En het zou dit nummer 6 te nemen en als, OK, is 6 minder dan dit aantal? Nee? Cool. We zijn prima. 

Doe het opnieuw. We zeggen 7. 7 minder dan het einde van onze gesorteerde array? Nee Dus we zijn prima. Dus dit zou worden geregeld. In principe al dit doet wordt het zegt take het eerste element van uw ongesorteerde array, erachter te komen waar het gaat in uw gesorteerde array. En dit duurt slechts zorg van swaps om dat te doen. Je bent eigenlijk gewoon omwisselen totdat het op de juiste plek. Het visuele beeld is dat je bent verplaatsen alles naar beneden door dat te doen. 

Dus het is net half bubble sort-esque. Check out studie 50. Ik beveel het proberen Om deze code op uw eigen. Als u problemen hebt of u wilt zie voorbeeldcode voor een insertion sort, laat het me weten. Ik ben altijd in de buurt. Dus ergste geval runtime en best case runtime. Zoals je man zag van de tafel heb ik al liet u, het is zowel n kwadraat en n. 

Dus soort afgaan van wat we gesproken over met onze vorige soorten, slechtste Bij runtime is dat als het is volkomen ongesorteerd, we al deze n maal vergelijken. We doen een heleboel vergelijkingen want als het in omgekeerde volgorde, we gaan zeggen, OK, dit hetzelfde is dit goed, en deze zal moeten worden vergeleken tegen de eerste worden terugbewogen. En als we in de richting van de staart, hebben we te vergelijken, vergelijken en vergelijk tegen alles. 

Het eindigt zo omhoog het zijn ongeveer n kwadraat. Als het correct is dan moet je zeggen, OK, 2, je bent goed. 3, je bent in vergelijking met 2. Je bent goed. 4, je gewoon vergelijken met de staart. Je bent goed. 6, te vergelijken met de staart, je boete. Dus voor elke plek als het al naargelang, je maakt een vergelijking. Dus het is gewoon n. En omdat we een best case runtime n en een worst case batterijduur van n kwadraat, we hebben geen verwachte runtime. 

Het is maar net de chaos van onze lijst daar. En nogmaals, een andere grafiek en een andere tafel. Dat verschillen tussen soorten. Ik ga gewoon door wind, I het gevoel dat we uitvoerig hebben gesproken over hoe ze allerlei van verschillen en het aan elkaar koppelen. Dus samenvoegen soort is de laatste Ik zal vervelen jullie met. We hebben een mooi kleurrijk beeld. Dus samenvoegen soort is een recursief algoritme. Dus doen jullie weten wat een recursieve functie is? 

Iedereen willen zeggen? Je wilt proberen? Dus een recursieve functie is enkel een functie die zichzelf aanroept. Dus als jullie zijn vertrouwd met de Fibonacci-reeks, dat is recursieve omdat geacht neemt u de vorige twee en voeg ze samen naar uw volgende te krijgen. Dus recursieve, denk ik altijd van recursie als als een spiraal dus je bent zoals neerwaartse spiraal erin. Maar het is gewoon een functie dat noemt zichzelf. 

En, eigenlijk, heel snel ik kan je laten zien hoe dat eruit ziet. Hier dus recursieve, als we kijken, is dit de recursieve manier om samen te vatten over een array. Dus alles wat we doen is we hebben som functie bedrag dat een omvang en een array neemt. En als u merkt, de grootte verlaagt telkens met één. En alles wat het doet is als x gelijk aan zero-- dus als de grootte van de matrix is gelijk aan zero-- het nul terugkeert. 

Anders is dit vat laatste element van de array, en neemt vervolgens een bedrag van de rest van de matrix. Dus het is gewoon het af te breken in steeds kleinere problemen. Lang verhaal kort, recursie, functie die zichzelf aanroept. Als dat is alles wat je hebt uit deze, dat is wat een recursieve functie is. Als u 51 nemen, zul je zeer te krijgen, zeer comfortabel met recursie. Het is echt cool. Het was logisch om als 03:00 een avondje uit. En ik was als, waarom heb ik dit nooit gebruiken? 

Dus voor merge sort, in principe wat het gaat doen, is het om dat af te breken en breken naar beneden totdat het is gewoon losse elementen. De afzonderlijke elementen zijn gemakkelijk te sorteren. We zien dat. Als je er een element, het is al beschouwd gesorteerde. Zo op een ingang van n elementen, Als n kleiner is dan 2, gewoon terug omdat die middelen het is ofwel 0 of 1 zoals we hebben gezien. Die worden beschouwd als gesorteerde elementen. 

Anders breekt het in tweeën. Sorteer de eerste helft, sorteert de tweede de helft, en dan ze samenvoegen. Daarom heet het merge sort. We hebben hier dus we zullen deze afstand. Dus houden we het hebben van hen totdat de array size is 1. Dus als het 1, we hebben net weer omdat dit een gesorteerde array, en dit is een gesorteerde array en dat is een gesorteerde array, we zijn allemaal opgelost. Dus dan wat we doen is dat we beginnen ze te groeperen. 

Dus de manier waarop u kunt denken over samenvoeging is je gewoon verwijderen van de kleinere van elk van de sub-arrays en gewoon voeg deze toe aan het ontstaan ​​array. Dus als je hier kijkt, als we deze sets wij 4, 6, en 1. Als we willen deze samenvoegen, we kijken naar deze eerste twee en wij zeggen, OK, 1 is kleiner, het naar voren. 4 en 6, er is niets om te vergelijken het aan, gewoon een label met het hoofd tot het einde. 

Toen we combineren deze twee, we hebben net neem de kleinere van de twee, dus het is 1. En nu nemen we de kleinste van deze twee, dus 2. Kleinste van deze twee, 3. Kleinste van deze twee, 4, 5, 6. Dus je bent gewoon te trekken uit deze. En omdat ze hebben eerder gesorteerd, je hoeft alleen één vergelijking elke keer daar. Dus meer code hier, net vertegenwoordiging. Dus je begint in het midden en u sorteert links en rechts en dan moet je gewoon samen te voegen die. 

En we hebben geen code hebben voor het samenvoegen hier. Maar, nogmaals, als je verder gaat studeren 50, het zal er zijn. Anders kom met me praten als je nog steeds in de war. Zo gaaf ding hier is dat het beste geval, slechtste geval, en verwachte runtime zijn allemaal in log n, die is veel beter dan we hebben gezien de rest van onze soorten. We hebben gezien n kwadraat en wat we eigenlijk krijgen hier is n log n, wat geweldig is. 

Kijk eens hoeveel beter dat is. Zo'n mooie curve. Zo veel efficiënter. Als je ooit kunt, gebruik samenvoegen soort. Het bespaart u tijd. Dan weer, zoals we al zeiden, als je naar beneden bent in deze lagere regio, het niet maken dat veel van een verschil. U krijgt tot duizenden en duizenden ingangen, u zeker wilt een efficiënter algoritme. En, nogmaals, onze mooie tafel van alle soorten die jullie vandaag geleerd. 

Dus ik weet dat het een dichte dag. Dit is niet per se te gaan om u te helpen met uw pset. Maar ik wil gewoon een disclaimer maken die sectie is niet alleen over psets. Al dit materiaal is eerlijk spel voor je tentamens. En ook als je verder met CS, deze zijn echt belangrijke fundamenten die je zou moeten weten. Dus een paar dagen zal er een weinig meer PSET hulp, maar een paar weken zal zijn veel meer daadwerkelijke inhoud dat lijkt misschien niet super nuttig voor u op dit moment, maar ik beloof als u doorgaat op zal zeer, zeer nuttig. 

Dus dat is het voor sectie. Down to the wire. Ik deed het binnen een minuut. Maar daar ga je. En ik zal donuts of snoep hebben. Is er iemand allergisch voor wat dan ook, door de manier waarop? Eieren en melk. Dus donuts zijn een no? OK. Prima. Chocolade no? Starburst. Starbursts zijn goed. OK. We gaan te hebben Starburst volgende week dan. Dat is wat ik krijg. Jullie hebben een geweldige week. Lees je spec. 

Laat me weten als je vragen hebt. Pset twee kwaliteiten moeten zijn aan u door donderdag. Als u vragen heeft over hoe ik graded iets of waarom ik graded iets de manier waarop ik heeft, stuur een email naar mij, kom met me praten. Ik ben een beetje gek dit week, maar ik beloof Ik zal nog steeds antwoorden binnen 24 uur. Dus hebben een geweldige week, iedereen. Veel succes op je pset.