[Musik spiller] 

ANDI Peng: Velkommen til uge 3 i afsnit. Tak, gutter, for alle der kommer til dette tidligste starttidspunkt dag. Vi har fået en dejlig, lille intime gruppe i dag. Så forhåbentlig vil vi komme til slut, måske tidligt, en lille smule tidligt i dag. Så hurtigt, blot nogle meddelelser for dagsordenen i dag. Før vi begynder, er vi kommer til at bare gå over nogle korte logistiske problemer, pset spørgsmål, debriefing, ting som. Og så vil vi dykke ret i. Vi vil bruge en debugger kaldet GDB til begynde Debunking vores kode, som David forklaret i foredrag forleden. Vi vil gå over de fire typer af slags. Vi vil gå over dem ret hurtigt da de er temmelig intensiv. Men ved, at alle dias og kildekoden er altid online. Så velkommen på din orientering, til gå tilbage og tage et kig på det. 

Vi vil gå igennem asymptotisk notation, som er bare en fancy måde at sige "runtime" hvor vi har den store O, som David forklaret i forelæsning. Og vi har også Omega, som er den nedre grænse runtime. Og vi vil tale lidt mere dybdegående om, hvordan de arbejder. Og endelig vil vi gå over binær søgning, fordi en masse af jer, der allerede har kiggede på dine psets sikkert, at det er et spørgsmål, som er i din pset. Så du alle være glade at vi dækker denne dag. 

Og endelig, pr din sektion feedback, jeg faktisk venstre omkring 15 minutter ved enden til bare gå over logistik pset3, spørgsmål, måske en smule vejledning, hvis du vil, før vi begynder programmering. Så lad os prøve at komme igennem materialet temmelig hurtigt. Og så kan vi bruge lidt tid tager flere spørgsmål til pset. OK. 

Hurtigt, så blot et par meddelelser før vi begynder i dag. For det første, velkommen til at gøre det gennem to af dine psets. Jeg tog et kig på your-- yeah, lad os få en runde af bifald for at en. Faktisk, jeg var virkelig, virkelig imponeret. Jeg sorterede den første pset for jer sidste uge, og du fyre gjorde utroligt. 

Stil var på punkt ud over et par kommentarer. Sørg for, at du altid er kommentere din kode. Men dine psets var på punkt. Og holde det op. Og det er godt for grader til se, at du fyre lægger i så stor en indsats i din stil og dit design i din kode at vi gerne for dig at se. Så jeg passerer langs min taknemmelighed for resten af ​​TAS. 

Men der er en få debriefing spørgsmål Jeg ønsker blot at gå over, at ville gøre både mit liv og en masse af den anden AT'er liv lidt nemmere. For det første har jeg bemærket dette fortid week-- hvor mange af jer har kørt check50 på din kode, før du sender? OK. Så alle bør gøre check50, because-- en secret-- vi faktisk køre check50 som en del af vores korrekthed scripts til at teste din kode. Så hvis din kode er ikke check50, efter al sandsynlighed, Det er nok at gå til svigte vores kontrol så godt. Nogle gange er du fyre har de rigtige svar. Ligesom i grådige, nogle af du har de rigtige tal, du bare udskrive nogle ekstra ting. Og det ekstra ting faktisk ikke checken, fordi computeren ikke virkelig ved, hvad det er på udkig efter. Og så vil det bare løbe igennem, se, at dit output ikke matche, hvad vi forventer svaret at være, og markere det er forkert. 

Og jeg ved, at der skete i nogle af dine sager i denne uge. Så jeg gik tilbage og manuelt nedklassificeret alles kode. I fremtiden selv, please, skal du sørge for at du kører tjek 50 på din kode. Fordi det er sådan en smerte for TA nødt til at gå tilbage og manuelt nedklassificering hver eneste pset for hver enkelt, lille savnet instans. Så jeg ikke tage nogen point. Jeg tror, ​​jeg tog måske en eller to for design. I fremtiden, selv hvis du ikke check50, punkter vil blive taget off for korrekthed. 

Endvidere er psets grund fredagen ved middagstid. Jeg tror, ​​der er en syv minutters sene afdragsfri periode, at vi giver dig. Per Harvard tid, er de lov til at være syv minutter for sent til alt. Så her på Yale, vi får holde sig til, at så godt. Men temmelig meget på 00:07, hvis din pset ikke er i, det vil blive markeret som sent. Og så mens det er mærket så sent, at TA-- jeg er stadig vil være klassificering dine psets. Så du stadig se en karakter vises. Dog ved, at ved I slutningen af ​​semestret, alle sene psets vil bare være automatisk nulstilles af computeren. 

Det gør vi af to grunde. Én, nogle gange får vi undskyldt, ligesom Dean undskyldninger, senere, at jeg ikke ved om endnu. Så vi vil gerne sikre, at vi er klassificering alt bare i tilfælde, ligesom, jeg er mangler et dekanens undskyldning. Og for det andet, skal du sind, kan du stadig drop én pset der har fulde omfang point. Og så vi gerne til lønklasse alle dine psets bare at sikre, at din rækkevidde s der, og du forsøger dem. Så selv om det er sent, vil du stadig få kredit for rækkevidde punkter, tror jeg. 

Så moralske af historien er, at gøre at dine psets er i on-tiden. Og hvis de ikke er i den tid, vide, at det ikke er stor. Ja, inden jeg går videre, nogen der har spørgsmål vedrørende pset feedback? Ja. 

PUBLIKUM: Sagde du, vi kan falde en af ​​psets? 

ANDI Peng: Ja. Så der er ni psets samlet i løbet af semestret. Og hvis du har rækkevidde points-- så omfanget er bare, temmelig meget, er du forsøger at problem, er du sætte i gang, viser du, at du har demonstreret du har læst spec. Det er temmelig meget rækkevidde. Og hvis du opfylder Anvendelsesområde punkter, vi kan droppe laveste en ud af fulde omfang. Så det er i din fordel at udfylde og prøve hver pset. 

Selv upload-- hvis ingen af dem arbejde, uploade dem alle. Og så vil vi forhåbentlig kunne give dig nogle af disse punkter tilbage. Cool. Andre spørgsmål? Great. 

For det andet kontor hours-- et par hurtige noter om kontortid. Så først, kommer tidligt på ugen. Ingen er nogensinde på kontortid om mandagen. Christabel kom til kontortid aftes. Ja, Christabel. Og hvad gjorde vi har på kontoret timer i aftes, Christabel? 

PUBLIKUM: Vi havde is. 

ANDI Peng: Så det er rigtigt, vi havde is på kontortid aftes. Mens jeg ikke kan love dig, at vi får is på kontortid hver uge, hvad jeg kan love dig er, at der vil være en betydelig bedre studerende til TA-forholdet. Ligesom legit, det er ligesom 3-1. Betragtninger, kontrast, at med Torsdag du har omkring 150 virkelig stressede børn og ingen is. Og det er bare ikke produktive for nogen. Så moralske af historien er, kommer tidligt til kontortid og gode ting vil ske. 

Også, kommer parat til at stille spørgsmål. Du ved? Uanset hvad TAS, I tror, ​​har sagt, Vi har været at få et par studerende der kommer ind på torsdag på, ligesom, 10:50 ikke have læst spec være som hjælp mig, hjælp mig. Desværre på det tidspunkt, der er ikke meget vi kan gøre for at hjælpe dig. Så kan du komme tidligt på ugen. Kom tidligt at kontortid. Kommer parat til at stille spørgsmål. Sørg for at du, som en studerende, er der, hvor du skal være således, at AT'er kan vejlede dig sammen, Hvilket er, hvad kontortid bør tildeles efter. 

For det andet, så jeg ved professorer gerne overraske os med tests. Jeg havde en professor dem lignende, slå om, ved den måde, husk at midterm du har næste mandag. Ja, jeg vidste ikke, om det midterm. Så jeg har tænkt mig at være, at TA der minder dig alt, quiz 0-- fordi, du ved, vi er CS. Nu, hvor vi har gjort arrays, får du hvorfor det er quiz 0, ikke quiz 1, eh? OK. Åh, jeg fik nogle chuckles på at en. OK. 

Så quiz 0 vil være 14 oktober, hvis du er i mandag onsdag sektion og oktober 15, hvis du er i tirsdag-torsdag sektionen. Dette gælder ikke for dem af jer på Harvard who-- jeg tror du vil alle være tage dine quizzer på 14.. 

Så yeah, i næste uge, hvis David i foredrag, går, yeah, så om det Quizzen næste uge, jer alle vil ikke blive chokeret, fordi du kom til afsnit og du ved, at din quiz 0 er i to uger. Og vi vil have bedømmelse sessioner og alt. Så ingen bekymringer om være bange for det. Eventuelle spørgsmål before-- spørgsmål på alle logistiske problemer med hensyn til, sortering, kontortid, sektioner? Ja. 

PUBLIKUM: Så quizzen er kommer til at være under forelæsning? 

ANDI Peng: Ja. Så quizzen, tror jeg, er 60 minut tildelt i denne tid slot at du bare vil tage i auditoriet. Så du behøver ikke at komme i på, ligesom, en tilfældig 07:00. Det er alle gode. Ja. Cool. 

Okay. Så vi kommer til at indføre et koncept for dig denne uge, at David har allerede slags af berørt i forelæsning i sidste uge. Det hedder GDB. Og hvor mange af jer, mens der i forløbet af at skrive dine psets, har bemærket en stor knap, der hedder "Debug" på toppen af ​​dit IDE? OK. Så nu får vi faktisk komme til at grave mysteriet om, hvad der knap faktisk gør. Og jeg garanterer dig, er det en smukke, smukke ting. 

Så indtil nu, tror jeg der har været to ting studerende har været typisk gør, når debugging psets. Én, de enten tilføje printf () - så hvert par linjer, de tilføje i en printf () - Åh, hvad er denne variabel? Åh, hvad er denne variabel nu-- og du slags se progression af din kode, som det kører. Eller den anden metode kids gøre, er at de bare skrive det hele og derefter gå ligesom dette i slutningen. Forhåbentlig det fungerer. Jeg garanterer dig, GDB er bedre end begge disse metoder. Ja. Så dette vil være din nye bedste ven. Fordi det er en smuk ting der visuelt viser både hvad din kode gør på et bestemt punkt samt hvad alle dine variabler bærer, ligesom hvad deres værdier er, på det specifikke punkt. Og på denne måde, kan du virkelig sætte breakpoints i din kode. Du kan køre igennem linje for linje. Og GDB vil bare have for Dem, der vises for dig, hvad alle dine variabler er, hvad laver de, hvad der foregår i koden. Og på en sådan måde, er det så meget lettere at se hvad der sker i stedet for printf-ing eller skrive ned dine udtalelser. 

Så vi vil gøre et eksempel på dette senere. Så det synes lidt abstrakt. Ingen bekymringer, vil vi gøre eksempler. Og så væsentlige, de tre største, mest anvendte funktioner, du har brug for i GDB er de næste, trin over, og Træd ind knapper. Jeg har tænkt mig at gå over der, faktisk, lige nu. 

Så kan du fyre alle se, at eller skal jeg zoome ind lidt? I ryggen, kan du se det? Skal jeg zoome ind? Bare en lille smule? OK, cool. Der vi går. OK. 

Så jeg har, her, min implementering for grådige. Og mens en masse af jer skrev grådige i while-løkke form-- at er en helt acceptabel måde at gøre det-- en anden måde at gøre det på er simpelthen at opdele i modulo. Fordi så kan du få din værdi og så har din resten. Og så kan du bare føje det hele sammen. Er logikken i, hvad jeg gør her giver mening for alle, før vi begynder? Slags? Cool. Great. Det er en temmelig sexet stykke kode, vil jeg sige. Ligesom jeg sagde, David, i foredrag, efter et stykke tid, du vil alle begynde at se kode som noget, der er smukt. Og nogle gange, når du ser smuk kode, det er sådan en vidunderlig følelse. 

Så dog mens denne kode er meget smuk, betyder det ikke korrekt. Så lad os køre check50 på dette. Tjek 50 20-- oop. 2? Er det pset2? Ja. Åh, pset1. OK. Så vi kører check50. 

Og som du fyre kan se her, det er ikke et par tilfælde. Og for nogle af jer, i løbet af at gøre dit problem sæt, du er ligesom, ah, hvorfor er det ikke fungerer. Hvorfor er det at arbejde for nogle værdier, men ikke for andre? Nå, er GDB vil hjælpe dig tal ud af, hvorfor disse input ikke fungerede. 

OK. Så lad os se, en af ​​de checks Jeg tabte check50 var input værdi på 0,41. Så det korrekte svar, der du skal få er et 4. Men i stedet hvad jeg udskrivning ud er 3-n, som er ukorrekt. Så lad os bare køre det manuelt, bare sørge for, at check50 virker. Lad os gøre ./greedy. Ups, jeg er nødt til at gøre grådige. Der vi går. Nu ./greedy. 

Hvor meget skylder? Lad os gøre 0,41. Og jep, vi ser her at det er udsende 3 når det korrekte svar, Faktisk bør være 4. Så lad os komme ind GDB og se, hvordan vi kan gå om fastsættelse af dette problem. 

Så det første skridt i altid debugging din kode er at sætte et breakpoint, eller et punkt, hvor du vil have computeren eller debugger til at begynde at kigge på. Så hvis du ikke virkelig vide, hvad dit problem er, normalt, den typiske ting, vi ønsker at gøre, er at sætte vores breakpoint på main. Så hvis du fyre kan se dette røde knap lige der, jep, det var mig at sætte en -grænseværdien for den vigtigste funktion. Jeg klikker det. 

Og så kan jeg gå op til min Debug-knappen. Jeg ramte den knap. Lad mig ind igen, hvis jeg kan. Der vi går. Så vi har, her, et panel til højre. Jeg er ked af, fyre i ryggen, du kan ikke rigtig se rigtig godt. Men det væsentlige alle denne ret panel gør holder styr på både den fremhævede line, som er kodelinje at computeren kører i øjeblikket, såvel som alle dine variabler hernede. 

Så du har fået cents, mønter, n, alle erklæret forskellige ting på dette tidspunkt. Ingen bekymringer, fordi vi har faktisk ikke initialiseret dem til eventuelle variable endnu. Så i din computer, din computer er bare at se, Åh, 32767 var den sidst brugte funktion af denne hukommelsesplads i min computer. Og så det er hvor cent i øjeblikket er. Men nej, at når du kører koden, Det bør blive initialiseret. 

Så lad os gå igennem, linje linje, hvad der foregår her. OK. Så heroppe er tre knapper, jeg forklarede bare. Du har Play, eller Kør-funktion, knap, har du Step-knappen igen, og du har også Træd ind knappen. Og i det væsentlige, alle tre dem bare gå gennem din kode og gøre forskellige ting. 

Så typisk, når du debugging, Vi ønsker ikke at bare trykke Play, fordi Play vil bare køre din kode til slutningen af ​​det. Og derefter vil du faktisk ikke vide, hvad dit problem er medmindre du indstille flere breakpoints. Hvis du indstille flere breakpoints, Det vil bare automatisk løbe fra den ene breakpoint, til den næste, til den næste. Men i dette tilfælde vi har bare, at man, fordi vi ønsker at arbejde os fra top ned til bunden. Så vi kommer til at ignorere, at knap lige nu med henblik på dette program. 

Så trin over funktion bare trin over hver enkelt linje og fortæller dig, hvad computeren gør. Den Træd ind funktionen går i den aktuelle funktion der er på din linje kode. Så for eksempel, som printf (), der er en funktion, ikke? Hvis jeg ønskede at fysisk trin i printf () funktion, Jeg vil faktisk gå ind i stykke kode, hvor printf () blev skrevet og se hvad der foregår der. 

Men typisk antager vi, at den kode, vi giver dig fungerer. Vi antager printf () arbejder. Vi antager, at GetInt () arbejder. Så der er ingen grund til at træde ind i disse funktioner. Men hvis der er funktioner at du skriver dig selv at du ønsker at kontrollere ud af, hvad der foregår, du ønsker at træde ind i denne funktion. 

Så lige nu er vi bare at træde over dette stykke kode. Så lad os se. Åh, print, "Oh hai, hvordan meget forandring skylder? " Vi er ligeglade. Vi ved, at arbejder, så vi træder over det. 

Så n, som er vores float, at vi har initialized-- eller declared-- op i toppen, er vi nu svarende til at GetFloat (). Så lad os træde over det. Og vi ser på bunden her, programmet er at spørge mig for at indtaste en værdi. Så lad os input den værdi, vi ønsker at teste her, som er 0,41. Great. 

Så nu n- gør du fyre se Her ved bottom-- det er stored-- fordi vi ikke har rundet endnu, det er gemmes i denne lignende gigant float, der er ,4099999996, som er tæt nok til vores formål, lige nu, til 0,41. Og så vil vi se senere, da vi fortsætte med at træde over programmet, efter her, er n blevet afrundede og cents er blevet 41. Great. Så vi ved, at vores afrunding arbejdstid. Vi ved, at vi har den korrekte antal cents, så vi ved, at det er egentlig ikke problemet. 

Så vi fortsætter med at træde indenfor dette program. Vi går her. Og så efter denne linje kode, vi bør vide, hvor mange kvartaler vi har. Vi trin over. Og du ser vi, i virkeligheden, har en kvartal fordi vi har trukket 25 fra vores oprindelige værdi på 41. Og vi har 16 til venstre for vores cents. 

Er alle forstå, hvordan programmet er at træde igennem og hvorfor cents er nu blevet 16 og hvorfor, nu, mønter er blevet 1? Alle er efter denne logik? Cool. Så i dette punkt, at programmets arbejde, ikke? Vi ved, det gør præcis hvad vi ønsker det. Og det gjorde vi faktisk ikke nødt til at udskrive, åh, hvad er cents på dette punkt, hvad der er mønter på dette punkt. 

Vi fortsætte med at gå gennem programmet. Træd over. Cool. Vi gå over Dimes. Great. Vi ser, at det er taget off $ 0,10 for en skilling. Og nu har vi to mønter. Det er korrekt. 

Vi gå over øre, og vi ser at vi har tilovers cents. Hmm, det er mærkeligt. Heroppe på programmet, skulle jeg at have trukket mine øre. Måske var jeg bare ikke at gøre det linje lige. Og desværre, kan du se her, fordi vi ved at vi er ved at styrke gennem ledninger 32 og 33, det er, hvor vores program uretmæssigt havde variabler køre. Så vi kan se og se, åh, Jeg fratrække cents her, men jeg er faktisk ikke tilføje til min møntværdi. Jeg tilføje til cents. Og jeg ønsker ikke at føje til cent, jeg ønsker at tilføje til mønter. Så hvis vi ændrer det til mønter, vi har fået et arbejdsprogram. Jeg kan køre check50. Du kan bare gå ud fra GDB højre her og derefter køre check50 igen. Jeg kunne bare gøre det. Jeg er nødt til at gøre grådige. 0,41. Og her, det er udskrivning ud det rigtige svar. 

Så som du fyre kan se, GDB er en virkelig kraftfuldt værktøj for når vi har så meget kode foregår og så mange variabler at det er svært for os, som et menneske, til at holde styr på. Computeren, i GDB debugger, har evnen at holde styr på alt. Jeg ved, i Visionaire, du fyre sandsynligvis kunne have ramt nogle segmentering fejl fordi du kørte out of bounds i dit array. I eksemplet med Cæsar, det er præcis, hvad jeg har implementeret her. 

Så jeg glemte at kontrollere for hvad der ville ske, hvis jeg havde ikke to kommandolinjeargumenter. Jeg vidste bare ikke sætte i denne kontrol. Og så hvis jeg kører Debug-- jeg indstille min breakpoint til højre der. Jeg løber Debug. 

OK. Ja. Så faktisk blev GDB meningen at have fortalt mig der var en segmentering fejl der. Jeg ved ikke, hvad der foregik lige der, men da jeg kørte det, det fungerede. Når du kører linjer kode igennem og GDB måske bare pludselig holde op på dig, gå op og se hvad den røde fejlen er. Det vil fortælle dig, hey, du havde en segmentering fejl, hvilket betyder, at du har forsøgt at få adgang plads i et array, der ikke eksisterede. Ja. 

Så i det næste problem fastsat i denne uge, du fyre vil sandsynligvis have en masse variabler flyder rundt. Du kommer ikke til at være sikker på, hvad de alle betyder på et bestemt tidspunkt. Så GDB vil virkelig hjælpe dig med at regne ud af, hvad de alle er svarende og at kunne se, at visuelt. Er der nogen forvirret om, hvordan noget af det var i orden? Cool. Okay. Så efter det, vi er kommer til at dykke ret i er fire forskellige typer af slags til denne uge. Hvor mange af jer, først af alt, inden vi begynder, har læst hele spec for pset3? OK. Jeg er stolt af jer. Det er ligesom halvdelen af ​​klassen, som er betydeligt mere end sidste gang. 

Så det er godt, fordi når vi taler om indholdet i lecture-- eller ked af det, i section-- Jeg kan lide at relatere en masse, der tilbage til, hvad det pset er og hvordan du vil implementere det i din pset. Så hvis du kommer med læse spec, det vil være meget nemmere for dig at forstå hvad jeg taler om, når jeg siger, åh hey, kan dette være en rigtig godt sted at gennemføre denne slags. Så dem af jer der har læst den spec vide, at som en del af din pset, du nødt til at skrive en type slags. Så det kan være meget nyttigt for en masse af jer i dag. 

Så vi vil starte med, væsentlige den mest simple form af sortering, udvælgelse slags. Den typiske algoritme til hvordan vi ville gå om dette is-- David gik gennem disse alle i foredrag, så jeg vil hurtigt bevæger sig langs her-- er hovedsagelig, du har en bred vifte af værdier. Og derefter finde dig mindste usorteret værdi og du bytte den værdi med den første usorteret værdi. Og så skal du bare holde gentage med resten af ​​din liste. 

Og her er en visuel forklaring på, hvordan det ville fungere. Så for eksempel, hvis vi skulle starte med et array af fem elementer, indeks 0 til 4, med 3, 5, 2, 6 og 4 værdier placeret i array-- så lige nu, vi bare kommer til at påtage sig at de er alle usorteret fordi vi har ikke testet på anden måde. 

Så hvordan et valg slags ville arbejde er, at det ville først løber gennem hele af usorteret array. Det ville udvælge den mindste værdi. I dette tilfælde, 3, højre nu, er den mindste. Det bliver til 5. Nope, 5 er ikke større than-- eller ked af det, ikke er mindre than-- 3. Så den mindste værdi er stadig 3. Og så får du til 2. Computeren ser, åh, 2 er mindre end 3. 2 må nu være den mindste værdi. Og så 2 swaps med det første værdi. 

Så efter en aflevering, kan vi faktisk se at de 2 og 3 er byttet. Og vi bare kommer til at fortsætte med at gøre dette igen med resten af ​​arrayet. Så vi kommer til at bare køre igennem de sidste fire indekser af matrixen. Vi vil se, at 3 er næste minimumsværdi. Så vi kommer til at bytte det med 4. Og så er vi bare kommer til at holde løber gennem indtil i sidste ende, du komme til en sorterede matrix, hvor 2, 3, 4, 5 og 6 er alle sorter. Har alle forstå logikken af, hvordan et valg slags virker? 

Du skal bare have en vis form af en mindsteværdi. Du holder styr på, hvad det er. Og når du finder det, du bytte det med den første værdi i array-- eller, ikke den første value-- den næste værdi i arrayet. Cool. 

Så som du fyre slags så fra en kort glimt, vi kommer til at pseudokode det ud. Så hvis du fyre i ryggen vil danne en gruppe, alle på et bord kan danne en lille partner, vil jeg at give dig fyre som tre minutter at bare tale gennem logikken, på engelsk, af, hvordan vi kan være i stand til at implementere pseudokode til at skrive et valg slags. Og der er slik. Kom op og få slik. Hvis du er i ryggen, og du ønsker slik, kan jeg kaster slik på dig. Faktisk gør du-- cool. Åh undskyld. OK. 

Så hvis vi gerne vil, som en klasse, skrive pseudokode for, hvordan man kunne nærme sig dette problem, bare du velkommen. Jeg vil bare gå rundt og, i orden, spørg grupper for den næste linje med hvad vi skal gøre. Så hvis du fyre ønsker at starte off, hvad er den første ting at gøre, når du forsøger at gennemføre en måde at løse dette program til selektivt at sortere en liste? Lad os bare antage, vi har et array, okay? 

PUBLIKUM: Du ønsker at skabe nogle slags [uhørligt], at du er løber gennem hele din array. 

ANDI Peng: Right. Så du vil ønsker at gentage gennem hver plads, ikke? Så stor. Hvis du fyre ønsker at give mig næste line-- yeah, i ryggen. 

PUBLIKUM: Tjek dem alle for de mindste. 

ANDI Peng: Der går vi. Så vi ønsker at gå igennem og kontrollere, se, hvad den mindste værdi, ikke? Jeg har tænkt mig at forkorte det til "min." Hvad tror du fyre ønsker at gøre efter du har fundet den mindste værdi? 

PUBLIKUM: [uhørligt] ANDI Peng: Så du vil ønsker at skifte det med det første af denne array, højre? Det er begyndelsen, jeg har tænkt mig at sige. Okay. Så nu, at du har byttet den første en, hvad vil du gøre efter det? Så nu ved vi, at denne ene her skal være den mindste værdi, ikke? Så har du en ekstra hvile af arrayet, der er usorteret. Så hvad du ønsker at gøre her, hvis du fyre ønsker at give mig den næste linie? PUBLIKUM: Så du ønsker at gentage gennem resten af ​​arrayet. ANDI Peng: Ja. Og så hvad betyder iteration gennem slags antyde, vi skal nok bruge? Hvilken type of-- 

PUBLIKUM: Åh, en ekstra variabel? ANDI Peng: Sandsynligvis anden for-løkke, ikke? Så vi sandsynligvis vil ønsker at gentage through-- stor. Og så er du kommer til at gå tilbage og sandsynligvis kontrollere mindst en gang, højre? Og du kommer til at holde gentage dette, fordi løkkerne bare at holde kørende, ikke? 

Så som du fyre kan se, vi bare har en generel pseudokode af, hvordan vi ønsker, at dette program til at se ud. Denne ITERATE- her, hvad gør vi typisk brug for at skrive i vores kode hvis vi ønsker at gentage gennem en array, hvilken type struktur? Jeg tror Christabel allerede sagt det før. 

PUBLIKUM: en for-løkke. 

ANDI Peng: en for-løkke? Præcis. Så det er nok vil være en for-løkke. Hvad er en check her kommer til at betyde? Typisk hvis du ønsker at kontrollere hvis noget er noget else-- 

PUBLIKUM: Hvis. 

ANDI Peng: An hvis, ikke? Og så swap her, vi får gå over senere, fordi David gik gennem det i forelæsning så godt. Og så den anden ITERATE- implies-- 

PUBLIKUM: Endnu for-løkke. 

ANDI Peng: --another for-løkke, nøjagtigt. Så hvis vi ser på dette korrekt, vi kan se, at vi er nok vil få brug for en indlejret for løkke med en betinget erklæring derinde og derefter en faktiske stykke kode, der er kommer til at bytte de værdier. Så jeg har bare generelt skrevet en pseudokode kode. Og så er vi faktisk går fysisk, som en klasse, forsøge at gennemføre denne dag. Lad os gå tilbage til denne IDE. 

Uh-oh. Hvorfor er det not-- der er det. OK. Beklager, lad mig prøve at zoome ind lidt mere. Der vi går. Alt jeg gør her, er jeg har oprettet et program kaldet "udvælgelse / sort.c." Jeg har oprettet en vifte af ni værdier, 4, 8, 2, 1, 6, 9, 7, 5, 3. I øjeblikket, som du kan se, de er uordnet. n vil være det nummer, fortæller dig mængden af ​​værdier du har i dit array. I dette tilfælde har vi ni værdier. Og jeg har lige fået en for-løkke her der udskriver det usorterede array. 

Og i slutningen, har jeg også fået en for løkke, der bare udskriver det ud igen. Så teoretisk, hvis dette program fungerer korrekt, i slutningen, bør du se en trykt for løkke hvor 1, 2, 3, 4, 5, 6, 7, 8, 9 er alle korrekt i orden. 

Så vi har fået vores pseudokode her. Er der nogen der ønsker at-- jeg er bare kommer til at gå bede om volunteers-- fortælle mig præcis, hvad de skal skrive om vi ønsker at det første, bare gentage gennem begyndelsen af ​​dette array? Hvad er linje kode jeg sandsynligvis vil få brug for her? 

PUBLIKUM: [uhørligt] 

ANDI Peng: Ja, føler gratis at-- ked af det, du behøver ikke at stå up-- føler fri til at hæve stemmen lidt. 

PUBLIKUM: Til int i lig 0-- 

ANDI Peng: Ja, godt. 

PUBLIKUM: Jeg er mindre end vifte længde. 

ANDI Peng: Så hold i tankerne her, fordi vi ikke har en funktion, fortæller os længden af ​​en matrix, Vi har allerede en værdi, der lagrer det. Højre? En anden ting at huske i mind-- i et array ni værdier, hvad er indekser? Lad os bare sige dette array var 0 til 3. Du ser, at den sidste indeks er faktisk 3. Det er ikke 4, selvom der er fire værdier i arrayet. 

Så her er vi nødt til at være meget forsigtige af, hvad vores betingelse for længden kommer til at være. 

PUBLIKUM: Ville det ikke være n minus 1? ANDI Peng: Det kommer n minus 1, nøjagtigt. Giver det mening, hvorfor det er n minus 1, alle? Det er fordi arrays er nul-indekseret. De starter ved 0 og køre op til n minus 1. Ja, det er lidt tricky. OK. Og så-- PUBLIKUM: Isnt'1 at allerede taget sig af selv, ved bare ikke at sige "mindre end eller lig med "og bare sige" mindre end? " 

ANDI Peng: Det er en rigtig godt spørgsmål. Så, ja. Men også, den måde, at vi er gennemførelsen af ​​retten kontrol, du nødt til at sammenligne to værdier. Så du rent faktisk ønsker at forlade "til" tom. Fordi hvis du sammenligner denne ene, du ikke vil har noget, efter at den at sammenligne med, ikke? Ja. Så jeg ++. Lad os tilføje vores beslag på. Hovsa. Great. Så vi har begyndelsen vores ydre loop. Så nu er vi sikkert gerne oprette en variabel til at holde styr på den mindste værdi, ikke? Er der nogen ønsker at give mig linje kode, der ville gøre det? Hvad har vi brug for, hvis vi skal at ønsker at gemme noget? 

Højre. Måske et bedre navn for det ville være-- "temp" helt works-- måske en mere passende navn ville være, hvis vi ønsker den mindste value-- 

PUBLIKUM: Min. ANDI Peng: min, der vi gå. min ville være godt. Og så her, hvad gør vi vil initialisere det til? Dette er en smule tricky. Fordi lige nu på begyndelsen af ​​dette array, du ikke har kigget på noget, ikke? Så hvad, automatisk, hvis vi er bare på jeg er lig med 0, hvad ønsker vi at initialisere vores første minimumsværdi til? PUBLIKUM: i. ANDI Peng: i, nøjagtigt. Christabel, hvorfor vi ønsker at initialisere den til jeg? 

PUBLIKUM: Fordi, ja, vi starter med 0. SÃ¥ fordi vi har noget at sammenligne det vil minimum ende med at blive 0. 

ANDI Peng: Præcis. Så hun er helt rigtigt. Fordi vi har faktisk ikke så på noget endnu, Vi ved ikke, hvad vores minimum værdi. Vi ønsker at bare initialisere den til I, som for tiden er lige her. Og som vi fortsætter med at flytte ned dette array, vi vil se, at med hver ekstra aflevering, jeg intervaller. Og så på det tidspunkt, Jeg er sandsynligvis vil at ville være det mindste, fordi det vil være, hvad er begyndelsen af ​​usorteret array. Cool. 

Så nu er vi ønsker at tilføje en for-løkke her, der er kommer til at gentage gennem usorteret, eller resten af ​​dette array. Er der nogen ønsker at give mig en linje kode, der ville gøre det? Hint-- hvad skal vi hernede? Hvad kommer til at gå i denne for-løkke? Ja. PUBLIKUM: Så vi gerne vil har en anden heltal, fordi vi kører gennem resten af arrayet i stedet for I, så måske j. 

ANDI Peng: Ja, j lyder godt for mig. Lig? 

PUBLIKUM: Så ville være i plus 1, fordi du starter på den næste værdi. Og derefter til end-- det igen, j er mindre end n minus 1, og derefter j ++. ANDI Peng: Great. 

Og derefter i her, vi kommer til at have at kontrollere, om vores betingelse er opfyldt, højre? Fordi du ønsker at ændre minimumsværdi hvis det er faktisk mindre end hvad du sammenligne det med, ikke? Så hvad skal vi have i her? Kontroller at se. Hvilken type erklæring vi sandsynligvis vil ti ønsker at bruge, hvis vi ønsker at kontrollere noget? 

PUBLIKUM: en if-sætning. 

ANDI Peng: en if-sætning. Så if-- og hvad der vil være den betingelse, at vi ønsker inde af vores hvis erklæring? 

PUBLIKUM: Hvis værdien af ​​j er mindre end værdien af ​​jeg-- 

ANDI Peng: Præcis. Så if-- så dette array kaldes "array." Great. Så hvis array-- hvad var det? Sig det igen. 

PUBLIKUM: Hvis vifte-j er mindre end matrix-i, så ville vi ændre min. Så min ville være j. 

ANDI Peng: Giver det mening? OK. Og nu hernede, vi faktisk ønsker at gennemføre swap, ikke? Så husker, i foredrag, at David, når han prøvede at bytte til--, hvad der var det-- appelsinsaft og milk-- 

PUBLIKUM: Det var brutto. 

ANDI Peng: Ja, det var slags brutto. Men det var en temmelig god koncept demonstrerer tid. Så tænk på dine værdier her. Du har fået en matrix på min, en opstilling af i, eller hvad vi forsøgte at bytte her. Og du sandsynligvis ikke kan hælde dem ind hinanden på samme tid, ikke? Så hvad skal vi at brug for at skabe her for at bytte de værdier korrekt? 

PUBLIKUM: En midlertidig variabel. 

ANDI Peng: En midlertidig variabel. Så lad os gøre int temp. Se, det ville være et bedre tid at-- whoa, hvad var det? OK. Så det ville have været en bedre tid til at navngive variablen "temp". Så lad os gøre int temp. Hvad skal vi indstillet temp lig med her? PUBLIKUM: Min? ANDI Peng: Det er lidt tricky. Det faktisk betyder ikke noget i sidste ende. Det er ligegyldigt, hvad rækkefølge, du vælger at bytte i så længe du gør, at du er holde styr på, hvad du bytte. 

PUBLIKUM: Det kunne være matrix-i. 

ANDI Peng: Ja, lad os gøre vifte-i. Og hvad er den næste linje kode vi ønsker at have her? PUBLIKUM: matrix-i lig vifte-j. ANDI Peng: Og endelig? PUBLIKUM: matrix-j lig vifte-i. Publikum: Eller vifte-j ligemænd matrix-temp-- eller temp. 

ANDI Peng: OK. Så lad os køre dette og se hvis det kommer til at fungere. Hvor er det der sker? Åh, det er et problem. Se, om linje 40, er vi forsøger at bruge matrix-j? Men hvor kommer j kun eksisterer i? 

PUBLIKUM: I for-løkken. ANDI Peng: Right. Så hvad skal vi gøre? 

PUBLIKUM: Definer det uden til-- PUBLIKUM: Ja, jeg tror, ​​du har at bruge en anden if-sætning, ikke? Så ligesom, hvis minimum-- okay, lad mig tænke. 

ANDI peng: Guys, prøv at tage et kig Lad os se, hvad der er noget, vi kan gøre her? 

PUBLIKUM: OK. Så hvis den mindste ikke er lig j-- så hvis minimum er stadig jeg-- så ville vi ikke have at bytte. 

ANDI Peng: Betyder, at lige jeg? Hvad vil du sige her? 

PUBLIKUM: Eller yeah, hvis minimum ikke er lig i, ja. ANDI Peng: OK. Nå det løser, slags, vores problemer. Men det stadig ikke løser problemet med, hvad der sker, hvis j-- da j eksisterer ikke uden for det, hvad vil du ønsker vi at gøre med det? Erklære den udenfor? Lad os prøve at køre dette. Uh-oh. Vores slags virker ikke. 

Som du kan se, vores indledende matrix havde disse værdier. Og bagefter det burde have været i 1, 2, 3, 4, 5, 6, 7, 8, 9. Det virker ikke. Ahh. Hvad gør vi? PUBLIKUM: Debug. ANDI Peng: Okay, kan vi prøve det. Vi kan debug. Zoom ud lidt. Lad os sætte vores breakpoint. Lad os gå like-- OK. 

Så fordi vi allerede ved, at disse linjer, 15 til 22, er working-- fordi alle jeg gør er bare iteration gennem og printing-- Jeg kan gå videre og springe det. Lad os starte ved linje 25. Oop, lad mig slippe af med det. 

PUBLIKUM: Så breakpoint s hvor debugging starter? ANDI Peng: Eller stopper. PUBLIKUM: Eller stopper. ANDI Peng: Ja. Du kan indstille flere breakpoints og det kan lige springe fra den ene til den anden. Men i dette tilfælde ved vi ikke hvor fejlen sker. Så vi ønsker blot at starte fra toppen og ned. Yep. OK. 

Så denne linje her, kan vi træde til. Du kan se hernede, vi har et array. Det er de værdier som er i array'et. Kan du se, at, hvordan indeks 0, det svarer til value-- oh, Jeg har tænkt mig at forsøge at zoome ind. Beklager, det er virkelig svært at see-- på matrix-indeks 0, Vi har en værdi på 4, og derefter så videre og så videre. Vi har vores lokale variabler. Lige nu i er lig med 0, som vi ønsker det skal være. 

Og så lad os holde træde igennem. Vores minimum er lig med 0, som vi også ønsker det skal være. Og så skal vi ind vores anden for loop, hvis matrix-j er mindre end matrix-I, som var det ikke. Så kunne du se, hvordan der springes over det? 

PUBLIKUM: Så skulle det hvis minimum alle at-- bør ikke, at være inde den første til loop? ANDI Peng: Nej, fordi du stadig ønsker at teste. Du ønsker at gøre en sammenligning hver tid, selv efter du har kørt igennem den. Du behøver ikke bare ønsker at gøre det den første gennemslag. Du ønsker at gøre det med hver ekstra pass igen. Så du ønsker at kontrollere for din tilstand indeni. Så vi bare gå til holde kører igennem her. Jeg vil give jer et tip. Det har at gøre med det faktum, at når du tjekker din betingede, du ikke kontrol for den korrekte indeks. Så lige nu er du kontrollere for vifte indeks j er mindre end matrix indeks i. Men hvad laver du op på begyndelsen af ​​for-løkken? Er du ikke sætte j lig med jeg? 

Ja, så kan vi faktisk forlade debugger her. Så lad os tage et kig på vores pseudokode. For-- vi vil starter ved i er lig med 0. Vi kommer til at gå op til n minus 1. Lad os tjekke, vi har denne ret? Jep, det var rigtigt. 

Så inde her, vi er vil skabe en minimumsværdi og sæt, lig med i. Gjorde vi det? Jep, gjorde det. Nu i vores indre for-løkke, er vi vil gøre j lig I n 1 minus. Gjorde vi det? Faktisk gjorde vi det. 

SÃ¥ dog hvad skal vi sammenligner her? 

PUBLIKUM: j plus 1. ANDI Peng: Præcis. Og så er du vil ønsker at indstille din minimum svarende til j plus 1 så godt. Så jeg gik igennem, der virkelig hurtigt. Har du fyre forstår hvorfor det er j plus 1? OK. 

Så i dit array, i dit første passage gennem, din for-løkke, til int Jeg er lig 0, lad os bare påtage sig dette er ikke blevet ændret endnu. Vi har en bred vifte af helt, blot fire usorterede elementer, ikke? Så vi vil initialisere jeg lig med 0. Og jeg vil bare løbe gennem denne løkke. Og så i den første aflevering, vil vi at initialisere en variabel kaldet "min" der også er lig med I, fordi vi ikke har en minimumsværdi. Så det er i øjeblikket lig med 0 så godt. Og så vi vil gå igennem. Og vi ønsker at gentage igen. Nu da vi har fundet, hvad vores minimum er, vi ønsker at gentage gennem igen for at se, om det er at sammenligne, ikke? Så j, her, vil til lige I, som er 0. Og derefter, hvis matrix j plus jeg, som er den, der er næste forbi, som mindre end hvad din nuværende minimum værdi, du ønsker at bytte. 

Så lad os bare sige, at vi har fik, ligesom, 2, 5, 1, 8. Lige nu, i er lig med 0 og j er lig 0. Og det er vores mindste værdi. Hvis vifte-j plus jeg-- så hvis den ene det er efter det vi kigger på er større end den, før den, det kommer til at blive et minimum. 

Så her ser vi, at 5 ikke er mindre end det. Så det kommer til at være 5. Vi ser, at 1 er mindre end 2, ikke? Så nu ved vi, at vores minimum er vil være den indeksværdien ved 0, 1, 2. Ja? Og så når du kommer herned, du kan bytte de korrekte værdier. 

Så når du fyre bare have den j før, var du ikke ser på den ene efter det. Du ledte på den samme værdi, som Derfor er det bare ikke gør noget. Giver det mening for alle, hvorfor vi havde brug for, at plus 1 er der? OK. Lad os nu bare køre igennem det for at gøre sikker på resten af ​​koden er korrekt. Hvorfor er det der sker? Ah, det er min lige her. Vi sammenlignede den forkerte værdi. Åh nej. 

Oh yeah, hernede var vi bytte de forkerte værdier. Fordi vi ser på i og j. Det er dem, vi kontrol. Vi faktisk ønsker at bytte den minimum det nuværende minimum, med hvad den ene udenfor er. Og som du fyre kan se ned her har vi en sorterede array. Det havde bare at gøre med det faktum, at når vi kontrol af værdier, vi sammenligner, vi ikke leder på de rigtige værdier. Vi ledte på den samme her, faktisk ikke bytte det. Du er nødt til at se på en næste til det, og så kan du bytte. Så det er det, der var slags aflytning vores kode før. Og hvad jeg gjorde her er alt debugger kunne have gjort for dig Jeg gjorde det bare på bord, fordi det er nemmere at se snarere end at forsøge at zoome ind på debugger. Giver det mening for alle? Cool. 

Okay. Vi kan gå videre til at tale om asymptotisk notation, som er bare en fancy måde at sige det runtime af alle disse former. Så jeg ved David, i foredrag, berørt runtime. Og han gik igennem hele formel af hvordan man beregner de runtime. Ingen bekymringer om der. Hvis du er virkelig nysgerrig om, hvordan det fungerer, velkommen til at tale med mig efter sektion. Vi kan gå igennem formlerne sammen. Men alle du fyre har virkelig ved er, at n kvadreret over 2 er det samme som n potens. Fordi det største antal, eksponenten, vokser mest. Og så til vores formål, alt, hvad vi interesserer os er, at kæmpe nummer, der vokser. 

Så hvad er den bedste fald runtime af valg Sorter? Hvis du vil have at gentage gennem en liste og derefter gentage gennem resten af ​​denne liste, hvor mange gange er vil du sandsynligvis, i værste case-- i bedste fald sorry-- løbe igennem? Måske bedre spørgsmål er at spørge, hvad er det værste tilfælde runtime af markering slags. PUBLIKUM: n potens. ANDI Peng: Det er n kvadreret, højre. Så en nem måde at tænke på det er ligesom, helst du har to indlejret efter sløjfer, det kommer til at blive n potens. Fordi ikke kun er du løber gennem endnu en gang, du nødt til at gå tilbage rundt og kørt gennem det endnu en gang inden for hver værdi. Så i dette tilfælde, er du kører n gange n kvadreret, hvilket is-- undskyld, n gange n, hvilket svarer til n potens. 

Og sortere er også lidt unikke i den forstand, at det ikke betyder noget, hvis disse værdier er allerede i orden. Det er stadig kommer til at køre igennem anyways. Lad os bare sige det var 1, 2, 3, 4. Uanset om det var i orden, er det stadig ville have løb gennem og stadig kontrolleres minimumsværdien. Det ville have gjort samme antal kontroller hver eneste gang, selv om det faktisk ikke ved noget. 

Så i dette tilfælde, det bedste og værste runtime faktisk ækvivalente. Så den forventede runtime udvælgelse sortere, som vi betegner med symbolet af theta, theta, i dette tilfælde, ville også n potens. Alle tre af disse ville blive n potens. Er alle klar på, hvorfor runtime er n kvadreret? 

Okay. Så jeg vil blot hurtigt løbe gennem resten af ​​den slags. Algoritmen for boble sort-- huske, dette var den første David gik over i forelæsning. Væsentlige, du trin gennem hele listen og du swap-- du bare sammenligne to ad gangen. Og hvis man er større, end du bare bytte dem. Så hvis disse er større, ville du bytte. Jeg har fået officiel lige her. 

Så lad os bare sige, at du havde 8, 6, 4, 2. Du vil sammenligne 8 og en 6. Du behøver at bytte dem. Du ville sammenligne 8 og en 4. Du behøver at bytte dem. Hvis du er nødt til at skifte 8 og 2, ændre dem så godt. Så i sådan en følelse, kan du se, udspiller sig over en lang periode, hvordan værdier slags boblen til enderne, hvilket er derfor, vi kalder det boble slags. 

Vi vil blot løbe igennem igen på vores anden aflevering, og vores tredje aflevering, og vores fjerde pass. Væsentlige, boble sortere bare kører indtil du ikke foretager nogen flere swaps. Så i den forstand, det er bare den generelle pseudokode for det. Ingen bekymringer, vil disse alle være online. Vi har ikke til rent faktisk at gå over dette. 

Vi har lige initialisere en tæller variabel, der starter ved 0. Og vi gentage gennem hele systemet. Og hvis én værdi is-- hvis det værdien er større end denne værdi, du kommer til at bytte dem. Og så er du bare kommer til at holde ud. Og du kommer til at tælle. Og du bare kommer til at holde gør dette, mens tælleren er større end 0, hvilket betyder, at hver gang du har til at bytte, du ved, du ønsker at gå tilbage og tjek igen. Du ønsker at holde kontrol, indtil du kender at du ikke behøver at bytte længere. 

Så hvad er de bedste og værste tilfælde Runtimes til boble slags? Og hint-- det er faktisk anderledes fra valg Sorter i den forstand, at disse to svar ikke er de samme. Tænk over, hvad der ville ske i en sag, hvis den allerede blev sorteret. Og tænke over, hvad ville ske, hvis det var i det tilfælde, hvor det ikke blev sorteret. Og du kan slags køre gennem hvorfor det sker. Jeg vil give jer, ligesom, 30 sekunder til at tænke over det. 

OK. Er der nogen der har et gæt på, hvad værste tilfælde runtime af boble slags er? Ja. 

PUBLIKUM: Ville det være, ligesom, n gange n minus 1 eller sådan noget? Ligesom, hver gang det kører, det er bare, ligesom, en swap mindre at uanset hvad det var. 

ANDI Peng: Ja, så du er helt rigtigt. Og det er en sag, hvor din Svaret var faktisk mere kompliceret end den, vi nødt til at give. Så det kommer til at run-- jeg er kommer til at slette alt det her. Er alle godt? Kan jeg slette det? OK. Du kommer til at løbe gennem n gange den første gang, ikke? Og de kommer til at løbe gennem n minus 1 anden gang, ikke? Og så er du kommer til at holde gå, n minen 2, et cetera. David gjorde det i et foredrag, hvor, hvis du har tilføjet op alle disse værdier, du får noget, der er like-- yeah-- over 2, som i det væsentlige blot reducerer ned til n potens. Du kommer til at få en underlige fraktion derinde. Og så bare vide, at n kvadreret altid forrang for fraktionen. Og så i dette tilfælde, det værste runtime ville blive n potens. Hvis det var i faldende orden, tror, ​​du nødt til at gøre en swap hver eneste gang. 

Hvad ville være potentielt bedste fald runtime? Lad os bare sige, hvis listen var allerede i orden, hvad ville runtime være? 

PUBLIKUM: n. ANDI Peng: Det er n, nøjagtigt. Og hvorfor er det n? PUBLIKUM: Fordi du bare nødt til at tjekke på hver gang. ANDI Peng: Præcis. Så på den bedst mulige runtime, Hvis denne liste allerede var sorted-- lad os sige 1, 2, 3, 4-- du ville bare gå igennem, vil du tjekke, du ville se, åh, de alle panorere. Jeg behøvede ikke at bytte. Jeg er færdig. Så i dette tilfælde, det er bare n eller antallet af trin, du bare havde til at kontrollere den første liste. 

Og efter vi nu ramt indsættelse sortere, hvor algoritmen er væsentlige kløft den i en sorteret og usorteret del. Og derefter en efter en, de usorterede værdier er indsat i deres passende positioner i begyndelsen af ​​listen. 

Så for eksempel, har vi en Liste over 3, 5, 2, 6, 4 igen. Vi ved, at det er i øjeblikket usorteret fordi vi har bare begyndte at se på det. Vi tager et kig og vi ved, at den første værdi sorteres, ikke? Hvis du kun kigger på en vifte af størrelse en, du ved, at det er ordnet. 

Så vi ved, at andre fire er usorteret. Vi går igennem, og vi kan se, at værdi. Lad os gå tilbage. Se, at værdi af 5? Vi tager et kig på det. Vi sammenligner det til 3. Vi ved, at det er større end 3, så vi ved, at der er sorteret. Så vi ved nu, at de to første sorteres og de sidste tre er ikke. 

Vi tager et kig på 2. Vi først tjekke det med 5. Er det mindre end 5? Det er ikke. Så vi er nødt til at holde kigger ned. Så du tjekke 2 off 3. Er det mindre end? Nej. Så du ved en 2 skal indsættes i den forreste og 3 og 5 begge at blive skubbet ud. Gør dette igen med 6 og 4. Og vi bare holde kontrol væsentlige, hvor vi lige tjekke, check, check. Og indtil det er i den rigtige position, vi slags blot indsætte det i den rigtige position, som er, hvor navnet på det kom fra. 

Så det er bare den algoritme, pseudokode per se, slags, om, hvordan vi ville gennemføre en insertion slags. Pseudokode er her. Det er alt sammen online. Ingen bekymringer, hvis du fyre er forsøger at kopiere det ned. Så endnu en gang, samme question-- hvad ville være den bedste og værste runtime til indføring slags? Det er meget lig det sidste spørgsmål. Jeg vil give jer, ligesom, 30 sekunder til at tænke over det så godt. 

OK Er der nogen ønsker at give mig den værste runtime? Ja. 

PUBLIKUM: n potens. 

ANDI Peng: Det er n potens. Og hvorfor er det n kvadreret? 

PUBLIKUM: Fordi i omvendt rækkefølge, du har at gå gennem n gange n, som is-- ANDI Peng: Ja, præcis. Så samme som i boblen slags. Hvis denne liste er i faldende rækkefølge, du er nødt til at tjekke først én gang. Og derefter med hver ekstra værdi, du er nødt til at tjekke det mod hver enkelt værdi, ikke? Og så helt, er du nødt til at gøre en n pass gange en anden n passere, som er n potens. Hvad med den bedste sag? Ja. 

PUBLIKUM: n minus 1, fordi første er allerede potens. 

ANDI Peng: Så tæt på. Svaret er faktisk n. Fordi mens den første er sorteret, kan det ikke actually-- det vi bare lucked, i dette eksempel, at 2 tilfældigvis det mindste tal. Men det vil ikke altid være tilfældet. Hvis 2 allerede er sorteret i begyndelsen men du ser og der er en 1 her, 1 kommer til at støde det. Og det kommer til at ende med at blive rumlede anyways. 

Så i bedste fald, Det er faktisk bare kommer til at være n. Hvis du har 1, 2, 3, 4, 5, 6, 7, 8, er du kommer til at løbe gennem at hele listen gang at kontrollere, om alt er fint. Er alle klar på at køre tider med udvælgelsen så godt? Jeg ved, jeg har tænkt mig igennem disse virkelig hurtig. Men bare vide, at hvis du kender generelle begreber, skal du være god. OK. Så jeg vil bare give jer måske, ligesom, et minut til at tale med dine naboer på hvilke er blot nogle af de væsentligste forskelle mellem disse typer af former. Vi vil gå over at snart. PUBLIKUM: Åh, OK. ANDI Peng: Ja. OK. Cool, lad os træde sammen som en klasse. OK. Så dette var form for en åbent spørgsmål i den forstand, at der er masser af svar på dem. Og vi vil gå over nogle af dem kort. Jeg ville bare få jer tænke over, hvad differentieret alle tre typer af mulige. Og jeg hørte også en stor question-- hvad betyder mergesort gøre? Store spørgsmål, fordi det er hvad vi dækker næste. 

Så mergesort er den en slags, der fungerer meget forskelligt fra de andre former. Som du fyre kan see-- gjorde David gør det demo hvor han havde alle de seje lyde af at se, hvordan fusionere sortere løb, ligesom, uendeligt hurtigere end de to andre typer? OK. Så det er fordi fusionere sortere implementerer at kløft og erobre koncept, som vi har talte om en masse i forelæsning. I den forstand, at vi kan lide at arbejde smartere, ikke hårdere, når du deler og erobre problemer og bryde dem ned, og derefter sætte dem sammen, gode ting altid sker. 

Så den måde, at fusionere sortere væsentlige værker er, at det skiller en usorteret array i halve. Og så det har fået to halvdele af arrays. Og det bare sorterer de to halvdele. Det bare holder dividere i halve, i halvdelen, i halve indtil alt er sorteret og derefter rekursivt sætter det hele sammen. 

Så det er virkelig abstrakt. Så dette er bare en smule af pseudokode. Giver det mening i den måde, det kører? Så lad os bare sige, at du har en vifte af n elementer, ikke? Hvis n er mindre end 2, kan du vende tilbage. Fordi du ved, at hvis der er kun én ting, skal det sorteres. Else, du sortere venstre halvdel, og så du sortere højre halvdel, og så skal du flette. 

Så mens der ser virkelig let, i virkeligheden tænker om det er slags vanskelig. Fordi du er ligesom, godt, der er slags kører på sig selv. Højre? Det kører på sig selv. Så i den forstand, David rørt ved rekursion i klassen. Og det er et koncept Vi vil tale om mere. Det er, at dette, disse to linjer her, er faktisk lige programmet fortæller det til at køre sig selv med forskellige input. Så i stedet for at køre sig i sin helhed n elementer, du kan bryde det ned i venstre halvdel og højre halvdel og derefter køre den igen. 

Og så vil vi se på det visuelt, fordi jeg er en visuel lærende. Det virker bedre for mig. Så vil vi se på et visuelt eksempel her. 

Lad os sige, at vi har et array, seks elementer, 3, 5, 2, 6, 4, 1, ikke er sorteret. Okay, der er en masse på denne side. Så hvis du fyre kan se på første skridt her, 3, 5, 2, 6, 4, 1, du kan opdele det i halve. Du har 3, 5, 2, 6, 4, 1. Du ved, at disse aren't-- du ved ikke, om de er ordnet eller ej, så du holder bryde dem ned, i halve, i halve, i halve, indtil til sidst, du kun har et element. Og et element altid sorteres, ikke? 

Så vi ved, 3, 5, 2, 4, 6, 1, i sig selv, er sorteret. Og nu kan vi sætte dem sammen igen. Så vi kender den 3, 5. Vi sætter dem sammen. Vi ved, det er sorterede. De 2 er der stadig. Vi kan sætte 4 og 6 sammen. Vi ved, at der er sorteret, så vi sætte det sammen. Og 1 er der. 

Og så skal du bare se på disse to halvdele lige her. Du har 3, 5, 2, 2, 3, 5. Du kan bare sammenligne begyndelsen af ​​alting. Fordi du ved, at dette er sorteret og du ved, at der er sorteret. Så du behøver ikke engang at sammenligne de 5, skal du blot sammenligne de 3. Og 2 er mindre end 3, så du ved 2 skal gå i sidste ende. 

Samme ting derovre. Den 1 skal gå her. Og så når du går til at sætte disse to værdier sammen, du ved, at dette sorteres og du ved, at der er sorteret. Så den 1 og den 2, 1 er mindre end 2. Det fortæller dig, at 1 skal gå på enden af ​​denne uden selv ser på 3 eller 5. Og så 4, kan du bare check, det går lige i her. Du behøver ikke at se på 5. Samme ting med 6. Du ved, at det 6-- det bare behøver ikke at blive kigget. 

Og så på den måde, du er bare spare dig selv en masse af trin, når du sammenligner. Du behøver ikke at sammenligne hver element mod andre elementer. Du skal bare sammenligne med dem at du skal sammenligne det mod. Så det er sådan et abstrakt begreb. Ingen bekymringer, hvis det ikke helt at ramme dig lige endnu. Men generelt er dette hvordan en mergesort fungerer. Spørgsmål, hurtige spørgsmål, inden jeg går videre? Ja. 

PUBLIKUM: Så du siger, at du tager 1, og derefter 4 og 6 og sætte dem i. Så er those-- ikke ikke du kigger på dem som separate elementer, ikke som helhed? ANDI Peng: Ja. Så hvad der sker er, at du dybest set skaber en helt ny array. Så du ved, at her, jeg har to arrays af størrelse 3, ikke? Så du ved, at min sorterede vifte skal have seks elementer. Så du bare oprette en nye mængde hukommelse. Så du er lidt ligesom være spild af hukommelse, men det betyder ikke noget fordi det er så lille. Så du ser på 1 og du ser på de 2. Og du ved, at 1 er mindre end 2. Så du ved, at 1 skulle gå i begyndelsen af ​​alle dem. 

Du behøver ikke engang at se på 3 og 5. Så du ved 1 går der. Så du dybest set hugge 1. Det er, ligesom, døde for os. Så vi bare have 2, 3, 5, og derefter 4 og 6. Og så ved du at, du sammenligne 4 og 2, Åh, de 2 skulle gå derind. Så du plop de 2 ned, du hugge det ud. Så du skal bare have den 3 og 5 i 4 og 6. Og du bare holde hakke det ud indtil du lægger dem i array. 

PUBLIKUM: Så du er bare altid sammenligne den [uhørligt]? 

ANDI Peng: Præcis. Så i den forstand, er du bare sammenligne det væsentlige, ét nummer mod den anden nummer. Og fordi du ved, at det er sorteret, du behøver ikke at se gennem alle numrene. Du skal bare nødt til at se på den første. Og så kan du bare plop dem ned, fordi du ved, de tilhører, hvor de skal tilhøre. Ja. Godt spørgsmål. 

Og så hvis nogen af ​​jer er lidt ambitiøst, velkommen til at se på denne kode. Dette er faktisk den fysiske gennemførelse af, hvordan vi ville skrive mergesort. Og du kan se, det er meget kort. Men ideerne bag det er temmelig kompliceret. Så hvis du har lyst til at trække det ud i dit hjemmearbejde i aften, er du velkommen til. 

OK. Så David også gik over dette i foredrag. Hvad er de bedste fald runtime, worst case runtime, og de forventede runtime af mergesort? Et par sekunder til at tænke. Dette er temmelig hårdt, men slags intuitiv, hvis du tænker over det. Okay. 

PUBLIKUM: Er værste fald n log n? ANDI Peng: Præcis. Og hvorfor er det n log n. 

PUBLIKUM: Er det ikke, fordi det bliver eksponentielt hurtigere, så det er ligesom en funktion af det i stedet for bare blot at være n kvadreret eller noget? ANDI Peng: Præcis. Så grunden runtime på dette er n log n er because-- hvad er du gør i alle disse trin? Du bare hakke det på midten, højre? Og så når vi laver den log, alt, det gør er dividere et problem i halve, i halve, i halve, i flere halvdele. Og i den forstand, kan du slags af fjerne den lineære model at vi har brugt. Fordi når du hugger ting i halve, det er en log. Det er bare den matematiske måde at repræsentere det. 

Og så til sidst, i slutningen, er du bare at gøre en sidste passage gennem at sætte dem alle i orden, ikke? Og så hvis du bare nødt til at kontrollere en ting, det er n. Og så er du sådan multiplicere de to sammen. Så det er ligesom du har fået, at den endelige kontrollere for n hernede med en log over n heroppe. Og hvis du ganger dem, der er n log n. 

Og så det bedste tilfælde og værste tilfælde og forventet er alle n log n. Det er også ligesom en anden slags. Det er ligesom valg Sorter i den forstand, at det er ligegyldigt, hvad din Listen er, det bare at gå til at gøre det samme hver eneste gang. OK. Så som du fyre kan se, selvom den slags, som vi har gået through-- n kvadreret, det er ikke meget effektiv. Og selv denne n log n er ikke den mest effektive. Hvis du fyre er nysgerrige, der er sortere mekanismer der er så effektive, at de er næsten væsentlige fladt i runtime. 

Du har fået nogle log n s. Du har fået nogle log log n s. Vi ikke røre dem i denne klasse lige nu. Men hvis du fyre er nysgerrige, velkommen til at google, hvad er de mest effektive sorteringsmekanismerne. Jeg ved det ikke, er der nogle virkelig sjove dem, like-- der er nogle virkelig sjove dem, folk gør. Og du spekulerer på, hvordan de nogensinde tænkt på det. Så google, hvis du har nogle fritid tid, om, hvad er nogle sjove måder at people-- samt effektive ways-- mennesker har kunnet gennemføre mulige. OK. Og her er bare en handy lille diagram. Jeg kender alle jer, før det quiz 0, vil være i dit værelse sandsynligvis forsøger at huske det. Så det er rart i der for jer. Bare glem ikke logik, der made-- hvorfor disse numre foregik. Hvis du altid er faret vild, bare gøre du vide, hvad den slags er. Og du kan køre igennem dem i dit sind at finde ud af, hvorfor de, svar er disse svar. 

Okay. Så vi kommer til at bevæge sig på endelig at søge. Fordi som dem af jer der har læst pset, søgning er også en del af denne uges problem sætter. Du vil blive bedt om at gennemføre to typer af søgninger. Den ene er en lineær søgning og den ene er en binær søgning. 

Så den lineære søgning er forholdsvis let. Du ønsker bare at søge element af en liste for at se, om du får det. Du skal bare nødt til at gentage gennem. Og hvis det er lig med noget, du kan bare returnere den, ikke? Men den, som vi er mest interesseret i at tale om er binær søgning, højre, som er den opdele og erobre mekanisme, som David demonstrerer i forelæsning. 

Husk telefonbog eksempel at han bliver ved med at bringe op, den, han slags kæmpet en smule på det seneste år, hvor man opdele problemet i halve, i halve, i halve, igen og igen, indtil du finder det, du leder efter? Og du har fået den runtime af, at så godt. Og du kan se, er det betydeligt mere effektiv end nogen anden type søgning. 

Så den måde, at vi ville gå om gennemføre en binær søgning er, hvis vi havde en matrix, indeks 0 til 6, syv elementer, vi kan se i midten, right-- beklager, hvis vores spørgsmål first-- hvis vi ønsker at stille spørgsmålet om, gør arrayet indeholder det element af 7, naturligvis være mennesker, og som har sådan en lille matrix, er det nemt for os at sige ja. Men den måde at gennemføre en binær søgning ville være at se i midten. 

Vi ved, at indekset 3 er midten, fordi vi ved, at der er syv elementer. Hvad 7 divideret med 2? Du kan hugge det ekstra 1. Du har 3 i midten. Så er vifte af 3 lig med 7? Det er ikke, vel? Men vi kan gøre et par checks. Er array af 3 mindre end 7 eller er array af 3 større end 7? 

Og vi ved, at det er mindre end 7. Så vi ved, at, åh, den skal ikke ligge i venstre halvdel. Vi ved, at det skal være i den højre halvdel, ikke? Så kan vi bare hugge halvdelen array. Vi behøver ikke engang at se på det længere. Fordi vi ved, at halvdelen af ​​vores problem-- vi ved, at svaret er i højre halvdel af vores problem. Så vi bare se på det nu. 

Så nu ser vi på det midten af ​​hvad der er tilbage. Det indeks 5. Vi gør det samme kontrol igen og vi kan se, at det er mindre. Så vi ser til venstre for det. Og så ser vi, at check. Er array værdi på indeks 4 lig med 7? Det er. Så vi kan vende tilbage sandt, fordi vi fandt værdien i vores liste. Er den måde, jeg gik igennem det mening for alle? OK. Jeg vil give jer måske, ligesom, tre, fire minutter til at finde ud af hvordan man pseudokode dette. 

Så forestille Jeg bad dig om at skrive en funktion kaldet søgning (), der vendte tilbage en værdi, en boolesk værdi, det var sandt eller false-- lignende, tilfældet, hvis du har fundet den værdi, falsk, hvis du ikke. Og så var bestået i værdi, du søgte i værdier, som er den array-- åh, jeg helt sikkert sætte at på det forkerte sted. OK. Anyways, der skal have været til højre for værdier. Og derefter int n er antallet af elementer i den opstilling. Hvordan ville du gå om at forsøge at pseudokode dette problem i? Jeg vil give dig fyre som tre minutter til at gøre det. Nej, jeg tror, ​​der er only-- Ja, der er en lige heroppe. PUBLIKUM: Kan jeg? ANDI Peng: Ja, jeg har dig. Er det i orden? OK, cool. 

OK. Alle rigtige gutter, vi er kommer til at tøjle det i. OK. Så antager vi har fået denne dejlige lille array med n værdier i det. Jeg har ikke tegne linjerne. Men hvordan ville vi gå om forsøger at skrive dette? Er der nogen ønsker at give mig den første linje? Hvis du vil give mig første linje i denne pseudokode. 

PUBLIKUM: [uhørligt] PUBLIKUM: Du ville have at gentage through-- PUBLIKUM: Bare en anden for løkke? PUBLIKUM: --for. 

ANDI Peng: Så denne ene er lidt tricky. Tænk om-- du ønsker at holde kører denne løkke igen og igen, indtil hvornår? 

PUBLIKUM: Indtil [uhørligt] er lig med denne værdi. ANDI Peng: Præcis. Så kan du faktisk bare write-- Vi kan endda forenkle det mere. Vi kan bare gøre en while-løkke, ikke? Så du kan bare have loop-- vi ved, at det er et stykke tid. Men for lige nu, jeg skal at sige "loop" - gennem hvad? Loop until-- hvad der er vores slutter tilstand? Jeg tror, ​​jeg hørte det. Jeg hørte nogen sige det. 

Publikum: Værdier lig midten. ANDI Peng: Sig det igen. PUBLIKUM: Eller, indtil værdi, du søger for er lig med den midterste værdi. 

ANDI Peng: Hvad hvis det ikke er der? Hvad hvis den værdi, du søger for er faktisk ikke i dette array? PUBLIKUM: Du vender tilbage 1. 

ANDI Peng: Men hvad ønsker vi at loop indtil hvis vi har en tilstand? Ja. 

PUBLIKUM: Indtil der er kun én værdi? ANDI Peng: Du kan loop until-- så du ved, at du er vil have en max værdi, ikke? Og du ved, at du vil at have en min værdi, ikke? Fordi også, det er noget Jeg glemte at sige før, at noget, der er kritisk om binær søgning er, at dit array allerede er sorteret. Fordi der er ingen måde at gøre dette, hvis de er bare tilfældige værdier. Du ved ikke, hvis man er større end den anden, ikke? 

Så du ved, at din max og dine mins er her, ikke? Hvis du kommer til at justere din max i dine minutter og mid-- lad os bare antage din mid-værdi er rigtige her-- du vil stort set loop indtil din minimum er om det samme som dit max, til højre, eller hvis dit max er ikke det samme som din min. Højre? For når det sker, du ved, at du i sidste ende har ramt den samme værdi. Så du ønsker at sløjfe indtil din min er mindre end eller lig at-- UPS, ikke mindre end eller lig med den anden vej around-- max er. 

Fik at give mening? Jeg tog et par forsøger at få denne ret. Men loop indtil din max værdi er i det væsentlige næsten mindre end eller lig med din minimum, ikke? Det er, når du ved at du har konvergeret. PUBLIKUM: Hvornår vil din maksimale værdi være mindre end den mindste? ANDI Peng: Hvis du holder justere den, hvilket er det, vi går at gøre i dette. Giver det mening? Minimum og max er blot heltal, at vi er nok vil ønsker at skabe for at holde styr på, hvor vi leder efter. Fordi array eksisterer uanset hvad vi laver. Ligesom, vi er ikke rent fysisk hugge array, ikke? Vi er bare justere hvor vi leder efter. Giver det mening? 

Publikum: Ja. 

ANDI Peng: OK. Så hvis det er betingelsen for vores løkke, hvad vil vi inde i denne løkke? Hvad skal vi være der ønsker at gøre? Så lige nu, har vi fået en max og en min, til højre, formentlig skabt op her et sted. Vi kommer til at sikkert gerne at finde en mellemvej, ikke? Hvordan skal vi være stand til at finde midten? Hvad er mathematical-- PUBLIKUM: Max plus min divideret med 2. ANDI Peng: Præcis. Giver det mening? Og tror du fyre se, hvorfor vi ikke bare use-- hvorfor vi gjorde dette i stedet for at gøre netop n divideret med 2? Det er fordi n er en værdi der kommer til at forblive den samme. Højre? Men som vi justerer vores minimum og maksimale værdier, de kommer til at ændre. Og som et resultat, vores midten vil også ændre sig. Så det er derfor, vi ønsker at gøre dette her. OK. 

Og så, nu, vi har fundet our-- ja. 

PUBLIKUM: Bare en hurtig question-- når du siger min og max, vi antager, at det er allerede ordnet? 

ANDI Peng: Ja, det er faktisk en forudsætning for en binær søgning, at du er nødt til at vide det er sorteret. Hvilket er grunden til sortering, du skriver i dit problem indstillet før din binær søgning. OK. Så nu, at vi ved, hvor vores midtpunkt er, hvad vil du gøre her? 

PUBLIKUM: Vi ønsker at sammenligne at til den anden. ANDI Peng: Præcis. Så du kommer til at sammenligne midten til værdi, ikke? Og hvad siger det os, når vi sammenligner? Hvad ønsker vi at gøre bagefter? 

PUBLIKUM: Hvis værdien er større end midten, ønsker vi at skære det ud. ANDI Peng: Præcis. Så hvis værdien er større end midten, vi er vil ønsker at ændre disse minimum og Maxes, ikke? Hvad ønsker vi at ændre? Så hvis vi kender værdien er et sted herinde, hvad gør du vi ændre? Vi ønsker at ændre vores minimum at være midt, højre? Og så ellers, hvis det er i denne halvdelen, hvad gør vi ønsker at ændre? 

PUBLIKUM: Din maksimum. ANDI Peng: Ja. Og så er du bare at holde looping, ikke? Fordi nu, efter en iteration igennem, du har fået en max her. Og så kan du genberegne en mid. Og så kan du sammenligne. Og du kommer til at holde i gang indtil minutter og Maxes har væsentlige konvergeret. Og det er, når du ved, at du har ramt i slutningen af ​​det. Og enten du har fundet det eller du ikke på dette punkt. 

Betyder det mening at alle? OK. Det er temmelig vigtigt, fordi du har at skrive dette i din kode i aften. Men du fyre har en temmelig god fornemmelse af, hvad du skal gøre, hvilket er godt. OK. Så vi har fået omkring syv minutter tilbage sektion. Så vi kommer til at tale om denne pset at vi vil gøre. Så pset er opdelt i to halvdele. Den første halvdel involverer gennemføre et fund hvor du skriver en lineær søgning, en binær søgning og en sorteringsalgoritme. 

Så dette er den første tid i en pset hvor vi vil være at give jer, hvad der kaldes fordeling kode, som er kode at vi har pre-skrevet, men netop forladt nogle stykker off for dig at afslutte skrive. Så jer, når man ser på dette kode, kan du få virkelig bange. Hvis du lige er lyst, ahh, jeg ved ikke, hvad der er at gøre, Jeg ved det ikke, ligesom, der synes så kompliceret, ahh, slappe af. Det er ok. Læs spec. Den spec vil præcist forklare dig hvad alle disse programmer gør. 

For eksempel generate.c er et program der vil komme med din pset. Du behøver faktisk ikke at røre ved det, men bør du forstå, hvad det gør. Og generate.c, alt det gør, er enten at generere tilfældige tal eller du kan give det et frø, som en indtegnet nummer, det tager, og det genererer flere numre. Så der er en bestemt måde at gennemføre generate.c hvor kan du bare lave en masse numre for dig at teste dine andre metoder på. 

Så hvis du ville, for eksempel teste din fund, du ønsker at køre generate.c, generere en masse tal, og derefter køre din hjælpere funktion. Din hjælpere funktion er, hvor du er rent fysisk at skrive kode. Og tænk på hjælpere som et bibliotek fil du skriver, at fund der ringer. Og så inden helpers.c, vil du gør søgning og sortering. 

Og så er du kommer til at væsentlige bare sætte dem alle sammen. Den spec vil fortælle dig, hvordan du sætte det på kommandolinjen. Og du vil være i stand til at teste, om ikke din sortere og søge fungerer. Cool. Har nogen allerede begyndt, og stødt problemer eller spørgsmål de har lige nu med dette? OK. 

PUBLIKUM: Vent. Jeg har et spørgsmål. 

ANDI Peng: Ja. 

PUBLIKUM: Så jeg begyndte at gøre den lineære søgning i helpers.c og det var ikke rigtig fungerer. Men senere fandt jeg ud af vi bare nødt til at slette det og gøre binær søgning. Så betyder det noget, hvis det ikke virker? 

ANDI Peng: korte svar er nej. Men da vi er not-- PUBLIKUM: Men ingen er faktisk kontrol. ANDI Peng: Vi er aldrig kommer til at se det. Men du sandsynligvis ønsker at gøre sikker på din søgning virker. Fordi hvis din lineære søgning ikke virker, så chancerne er din binære søgningen er ikke til at arbejde så godt. Fordi du har lignende logik i dem begge. Og nej, det er faktisk ligegyldigt. Så de eneste, du vil vise i er sortering og binær søgning. Ja. 

Og også, en masse børn var forsøger at kompilere helpers.c. Du er faktisk ikke tilladt at gøre det, fordi helpers.c ikke har en hovedfunktion. Og så bør du kun være faktisk kompilering generere og find, fordi find opkald helpers.c og funktionerne i den. Så det gør debugging en smerte i butt. Men det er, hvad vi skal gøre. PUBLIKUM: Du skal bare gøre alle, ikke? ANDI Peng: Du kan bare gøre alle så godt, ja. OK. Så det er det i form af, hvad den pset beder jer alle at gøre. Hvis du har spørgsmål, er du velkommen velkommen til at spørge mig efter sektion. Jeg vil være her for, ligesom, 20 minutter. 

Og yeah, pset s virkelig ikke så slemt. Du fyre burde være OK. Disse, blot følge retningslinjer. Slags har en følelse af, logisk, hvad bør ske, og du vil være fint. Må ikke være alt for bange. Der er en masse kode allerede skrevet der. Må ikke være alt for bange, hvis du ikke gør forstå, hvad alt dette betyder. Hvis det er en masse, det er helt fint. Og kommer til kontortid. Vi hjælper dig med at tage et kig. 

PUBLIKUM: Med den ekstra funktioner, vi ser dem op? 

ANDI Peng: Ja, de er i koden. I spillet af 15, halvdelen af det er allerede skrevet til dig. Så disse funktioner er allerede i koden. Yep. Okay. Nå, held og lykke. Det er en modbydelig dag. Så forhåbentlig jer ikke føler sig alt for dårligt om opholder sig inde og kodning.