[MUSIC SPILLE] ANDI PENG: Velkommen til uke tre av seksjonen. Takk, dere, for alle kommende til dette tidligere starttid i dag. Vi har fått en fin, liten intim gruppe i dag. Så forhåpentligvis vil vi få til finish, kanskje, tidlig, litt tidlig i dag. Så fort, bare noen kunngjøringer for agendaen i dag. Før vi begynner, er vi kommer til å bare gå over noen korte logistiske problemer, PSet spørsmål, debrief, sånne ting. Og så skal vi stupe rett i. Vi vil bruke en debugger kalt GDB til starte avslørte vår kode, som David forklart i forelesning her om dagen. Vi vil gå over fire typer former. Vi vil gå over dem ganske raskt siden de er ganske intensiv. Men vet at alle skinnene og Kildekoden er alltid online. Så gjerne, ved gjennomlesing, til gå tilbake og ta en titt på det. Vi vil gå gjennom asymptotisk notasjon, som er bare en fancy måte si "kjøretidsfiler," hvor vi har den store O, som David forklart i forelesningen. Og vi har også Omega, som er den nedre grense kjøring. Og vi skal snakke litt mer inngående om hvordan de arbeidet. Og til slutt, vil vi gå over binære søk, fordi mange av dere som allerede har kikket på dine psets vet sikkert at det er et spørsmål som er i din PSet. Så du vil alle være fornøyd at vi dette i dag dekker. Og til slutt, per din § tilbakemeldinger, jeg faktisk forlot ca 15 minutter ved slutt å bare gå over logistikken pset3, spørsmål, kanskje litt veiledning, om du vil, før vi begynner programmering. Så la oss prøve å komme gjennom materialet ganske raskt. Og så kan vi bruke litt tid tar flere spørsmål for PSet. OK. Raskt, slik at bare noen få kunngjøringer før vi starter i dag. For det første, velkommen til å gjøre det gjennom to av dine psets. Jeg tok en titt på your-- yeah, la oss få en runde med applaus for at ett. Egentlig var jeg virkelig, virkelig imponert. Jeg gradert første PSet for dere forrige uke, og dere gjorde utrolig. Stilen var på punktet foruten noen kommentarer. Sørg for at du alltid er kommenterer koden din. Men dine psets var på punktet. Og holde det opp. Og det er bra for grader til se at dere setter i så mye innsats i din stil og design i koden at vi ønsker for deg å se. Så jeg passerer langs min takknemlighet for resten av TAS. Men det er en Noen utspørrings spørsmål Jeg vil bare gå over at ville gjøre både livet mitt og mange av de andre TAs liv litt lettere. For det første, jeg har lagt merke til dette forbi week-- hvor mange av dere har kjørt check50 på koden din før du sender inn? OK. Så alle bør gjøre check50, because-- en secret-- vi faktisk kjøre check50 som en del av vår korrekthet skript for å teste koden din. Så hvis koden er sviktende check50, i all sannsynlighet, det er trolig kommer til å mislykkes vår sjekk også. Noen ganger dere har de riktige svarene. Som, i grådige, noen av du har de riktige tallene, du bare skrive ut noen ekstra ting. Og som ekstra ting faktisk svikter sjekk, fordi datamaskinen ikke egentlig vet hva det er på jakt etter. Og så det vil bare kjøre gjennom, ser at utskriftene ikke samsvarer med hva vi forventer svaret å være, og merk det er galt. Og jeg vet at har skjedd i noen av sakene denne uken. Så jeg gikk tilbake og manuelt regraded alles kode. I fremtiden skjønt, please, please sørge at du kjører sjekke 50 på koden din. Fordi det er litt vondt for TA å måtte gå tilbake og manuelt regrade hver eneste PSet for hver enkelt, lite savnet eksempel. Så jeg fikk ikke ta av noen poeng. Jeg tror jeg tok av kanskje én eller to for design. I fremtiden om, hvis du er sviktende check50, punktene vil bli tatt off for korrekthet. Videre psets er skyldes fredager på formiddagen. Jeg tror det er en syv minutters sent gyldighetsperiode som vi gir deg. Per Harvard tid, er de lov til å være sju minutter for sent til alt. Så her ved Yale, vil vi holder seg til det også. Men ganske mye, på 12:07, hvis PSet ikke er i, det kommer til å merkes så sent. Og så lenge det er merket så sent, den TA-- jeg er fortsatt kommer til å bli gradering dine psets. Så vil du fortsatt se en karakter vises. Men vet at på slutten av semesteret, alle sent psets vil bare være automatisk nullet av datamaskinen. Vi gjør dette av to grunner. En, noen ganger får vi unnskyldt, som Deans unnskyldninger, senere at jeg ikke vet om ennå. Så vi ønsker å sørge for at vi gradering alt bare i tilfelle, som jeg er mangler en dekan unnskyldning. Og for det andre, holde i sinn, kan du fortsatt droppe en PSet som har full omfang poeng. Og så liker vi å gradere alle dine psets bare å sørge for at omfanget er der og du prøver dem. Så selv om det er sent, vil du likevel få kreditt for omfang poeng, tror jeg. Så moralen i historien er, gjøre for at psets er på gang. Og hvis de ikke er i på-tiden, vet at det er ikke bra. Ja, før jeg går videre, er det noen som har spørsmål om PSet tilbakemeldinger? Yeah. PUBLIKUM: Visste du si vi kan slippe en av de psets? ANDI PENG: Yeah. Så det er ni psets generelle i løpet av semesteret. Og hvis du har omfanget points-- så omfanget er bare, ganske mye, er du forsøker problem, er du setter i gang, er du viser at du har demonstrert du har lest spec. Det er ganske mye omfang. Og hvis du oppfyller omfang poeng, vi kan slippe den laveste en ut av full omfang. Så det er i din fordel å fullføre og prøve hver PSet. Selv upload-- hvis ingen av dem arbeid, laste dem alle. Og da vil vi forhåpentligvis kunne gi deg noen av disse punktene tilbake. Kjølig. Eventuelle andre spørsmål? Flott. Dernest kontor timer-- noen raske notater om kontortiden. Så først, kom tidlig i uken. Ingen er noensinne på kontortid på mandager. Christ kom til kontortid i går kveld. Ja, Christ. Og hva gjorde vi har på kontoret timer i går kveld, Christ? PUBLIKUM: Vi hadde iskrem. ANDI PENG: Så det er riktig, hadde vi iskrem på kontortiden i går kveld. Selv om jeg ikke kan love deg at vi vil ha iskrem på kontortid hver uke, det kan jeg love deg er at det vil være en betydelig bedre student til TA ratio. Som legit, er det som 12:57. Mens, kontrast at med Torsdag, har du ca 150 veldig stresset barn og ingen iskrem. Og det er bare ikke produktivt for alle. Så moralen i historien er, kom tidlig til arbeidstid og gode ting vil skje. Også kommer forberedt til å stille spørsmål. Du vet? Uansett hva TAs, jeg tror, ​​har vært å si, Vi har fått et par studenter som kommer inn på torsdag på, som, 10:50 ikke å ha lest spec være som å hjelpe meg, hjelpe meg. Dessverre på det punktet, det er ikke mye vi kan gjøre for å hjelpe deg. Så kan du komme tidlig i uken. Kom tidlig for å kontortid. Kom forberedt på å stille spørsmål. Sørg for at du som en student, er der du må være slik at TAs kan veilede deg langs, Som er hva kontortid burde bli tildelt for. For det andre, så jeg vet professorer liker å overraske oss med tester. Jeg hadde en professor dem liker, yo, forresten, husk at deleksamen du har neste mandag. Ja, jeg visste ikke om at deleksamen. Så jeg kommer til å være at TA som minner deg alt som quiz 0-- fordi, du vet, vi er CS. Nå som vi har gjort arrays, får du hvorfor det er quiz 0, ikke quiz en, eh? OK. Åh, jeg fikk noen humrer på den. OK. Så quiz 0 vil være 14 oktober hvis du er i mandag-onsdag seksjon og oktober 15 Hvis du er i tirsdag-torsdag delen. Dette gjelder ikke for de av dere ved Harvard who-- Jeg tror du vil alle være ta dine quizer på den 14. Så ja, neste uke, hvis David, i foredrag, går, yeah, så om det quiz neste uke, dere alle vil ikke bli sjokkert fordi du kom til seksjon og du vet at din quiz 0 er i to uker. Og vi vil ha en vurdering økter og alt. Så ingen bekymringer om å være redd for det. Eventuelle spørsmål before-- spørsmål på alle om logistiske problemer, gradering, kontortid, seksjoner? Yeah. PUBLIKUM: Så quiz er kommer til å være under forelesning? ANDI PENG: Yeah. Så quiz, tror jeg, er 60 minutt tildelt i den tidsluke at du bare ta i forelesningssalen. Så du trenger ikke å komme i på, som en tilfeldig 07:00. Det er alt bra. Yeah. Kjølig. Greit. Så vi kommer til å introdusere et konsept for deg denne uken at David har allerede slag av berørt i foredraget denne siste uken. Det kalles GDB. Og hvor mange av dere, mens i I løpet av å skrive dine psets, har lagt merke til en stor knapp som sier "Debug" på toppen av din IDE? OK. Så nå skal vi faktisk får til å grave opp mysterium hva den knappen faktisk gjør. Og jeg kan garantere deg, det er en vakker, vakker ting. Så frem til nå, tror jeg det har vært to ting studenter har vært typisk gjør når debugging psets. En, de enten legge i printf () - så noen få linjer, de legger i en printf () - oh, hva er denne variabelen? Oh, hva er denne variabelen now-- og du slags se progresjon av koden din som det går. Eller den andre metoden barna gjør er at de bare skrive hele greia og deretter gå slik på slutten. Forhåpentligvis fungerer det. Jeg kan garantere deg, er GDB bedre enn begge disse metoder. Yeah. Så dette blir din nye bestevenn. Fordi det er en vakker ting som visuelt viser både hva koden gjør på et bestemt punkt samt hva alle dine variabler er bærer, som hva deres verdier er, på det bestemt punkt. Og på denne måten, kan du virkelig sette stoppunkter i koden din. Du kan kjøre gjennom linje for linje. Og GDB vil bare ha for du, som vises for deg, hva alle variabler er, hva de gjør, hva som skjer i koden. Og på en slik måte, er det så mye lettere å se hva som skjer i stedet for printf-ing eller skrive ned dine uttalelser. Så vi vil gjøre et eksempel på dette senere. Så dette virker litt abstrakt. Ingen grunn til bekymring, vil vi gjøre eksempler. Og så egentlig, de tre største, mest brukte funksjonene du trenger i GDB er den neste, Step over, og skrittet inn knapper. Jeg kommer til å gå over der, faktisk, akkurat nå. Så kan dere alle se at eller skal jeg zoome inn litt? I ryggen, kan du se det? Bør jeg zoome inn? Bare en liten bit? Ok kult. Det vi går. OK. Så jeg har, her, min implementering for grådig. Og mens mange av dere skrev grådig i mens loop form-- at er en helt akseptabel måte å gjøre det-- en annen måte å gjøre det på er å rett og slett dele i modulo. Fordi da kan du ha din verdi og deretter ha resten. Og da kan du bare legger det hele sammen. Har logikken i hva jeg gjør her være fornuftig for alle, før vi begynner? På en måte? Kjølig. Flott. Det er en ganske sexy stykke kode, vil jeg si. Som jeg sa, David, i forelesning, etter en stund, du vil alle begynne å se koden som noe som er vakkert. Og noen ganger når du ser vakker kode, det er slik en fantastisk følelse. Så imidlertid mens denne koden er veldig vakkert, det fungerer ikke som den skal. Så la oss kjøre check50 på dette. Sjekk 50 20-- oop. 2? Er det pset2? Yeah. Oh, pset1. OK. Så vi kjører check50. Og som dere kan se her, det er sviktende et par tilfeller. Og for noen av dere, i løpet av å gjøre dine oppgavesett, du er som, ah, hvorfor er det ikke fungerer. Hvorfor er det å jobbe for noen verdier, men ikke for andre? Vel, GDB kommer til å hjelpe deg figuren ut hvorfor disse inngangene ikke fungerer. OK. Så la oss se, en av de sjekker jeg mislykkes i check50 var inngangsverdien på 0,41. Så det riktige svaret som du bør få er en 4. Men i stedet hva jeg skriver ut er 3-n, som er feil. Så la oss bare kjøre dette manuelt, bare sørge for at check50 fungerer. La oss gjøre ./greedy. Oops, jeg må gjøre grådig. Det vi går. Nå ./greedy. Hvor mye er skyldte? La oss gjøre 0,41. Og ja, vi ser her at det å gi ut tre når det riktige svaret, faktisk, bør være fire. Så la oss gå inn GDB og se hvordan vi kan gå om å fikse dette problemet. Så det første trinnet i alltid debugging koden er å sette et stoppunkt, eller et punkt der du vil datamaskinen eller debugger for å begynne å se på. Så hvis du ikke virkelig vet hva problemet er, vanligvis, den typiske ting vi ønsker å gjøre er å sette vår stoppunkt på hoved. Så hvis dere kan se dette røde knappen til høyre der, Jepp, det var meg å sette en bruddpunkt for den viktigste funksjonen. Jeg klikker det. Og så kan jeg gå opp til min Debug-knappen. Jeg traff den knappen. La meg zoome ut igjen hvis jeg kan. Det vi går. Så vi har, her, et panel på høyre side. Jeg beklager, gutta i ryggen, du kan egentlig ikke se veldig bra. Men i hovedsak, alt denne retten panel gjør er å holde styr på både uthevet linje, som er den linje med kode at datamaskinen kjører for øyeblikket, samt alle dine variabler her nede. Så du har fått cent, mynter, n, alle erklærte til forskjellige ting På dette punktet. Ingen grunn til bekymring, fordi vi har faktisk ikke initialisert dem til noen variabler ennå. Så i datamaskinen, din Datamaskinen er bare å se, oh, 32767 var det sist brukte funksjonen av at minne i datamaskinen min. Og så det er der cent i dag. Men no at når du kjører koden, Det bør bli initialisert. Så la oss gå gjennom, linje for linje, hva som skjer her. OK. Så her oppe er de tre knapper som jeg nettopp forklart. Du har Play, eller Run-funksjonen, knappen, har du gå over knappen, og du har også steget inn knappen. Og egentlig, alle tre dem bare gå gjennom koden din og gjøre forskjellige ting. Så typisk, når du er feilsøking, vi ønsker ikke å bare trykke Play, fordi Play vil bare kjøre koden til slutten av den. Og da vil du faktisk ikke vet hva problemet er mindre du stille inn flere stoppunkter. Hvis du angir flere stoppunkter, det vil bare automatisk løpe fra en stoppunkt, til den neste, til den neste. Men i dette tilfellet har vi bare at en, fordi vi ønsker å jobbe oss fra toppen og ned til bunnen. Så vi kommer til å ignorere den knappen akkurat nå for anvendelsen av dette programmet. Så Step over funksjonen bare skritter over hver enkelt linje og forteller deg hva datamaskinen gjør. Step inn funksjon går inn i selve funksjonen som er på linje med kode. Så for eksempel, som printf (), som er en funksjon, ikke sant? Hvis jeg ønsket å fysisk trinn inn i printf () -funksjonen, Jeg vil faktisk gå inn i stykke koden der printf () ble skrevet og se hva som skjer der. Men typisk, antar vi at koden som vi gi deg fungerer. Vi antar at printf () fungerer. Vi antar at GetInt () fungerer. Så det er ingen grunn til å gå inn i disse funksjonene. Men hvis det er funksjoner som du skriver selv som du ønsker å sjekke ut hva som skjer, du ønsker å gå inn i denne funksjonen. Så akkurat nå er vi bare nødt å gå over denne del av koden. Så la oss se. Oh, print, "Oh hai, hvordan mye endring er skyldte? " Vi bryr oss ikke. Vi vet at fungerer, så vi gå over det. Så n, som er vår flåte som vi har initialized-- eller declared-- opp på toppen, er vi nå tilsvarende som i GetFloat (). Så la oss gå over det. Og vi ser på bunn her, programmet tilskynder meg for å legge inn en verdi. Så la oss innspill verdien vi ønsker for å teste her, som er 0,41. Flott. Så nå N- gjør dere se her, på bottom-- det er stored-- fordi vi har ikke rundet ennå, er det som er lagret i dette som gigant flåte som er ,4099999996, som er nær nok til vår formål, akkurat nå, til 0,41. Og så får vi se senere, som vi fortsette å tråkke over programmet, etter her, har n blitt avrundet og øre har blitt 41. Flott. Så vi vet at vår avrunding arbeidsgruppe. Vi vet at vi har riktig antall cent, så vi vet at det er egentlig ikke problemet. Så vi fortsetter å tråkke på i dette programmet. Vi går her. Og så etter denne linjen med kode, vi bør vite hvor mange kvartalene vi har. Vi går over. Og du ser vi, faktisk, har en kvartal fordi vi har trukket 25 fra vår opprinnelige verdi av 41. Og vi har 16 venstre for våre cent. Har alle forstår hvordan programmet er å tråkke gjennom og hvorfor cent har nå blitt 16 og hvorfor, nå, mynter har blitt en? Er alle etter den logikken? Kjølig. Slik som i dette punkt, Programmets arbeids, ikke sant? Vi vet at det gjør akkurat hva vi vil. Og vi gjorde faktisk ikke må skrive ut, oh, hva er cents på dette punktet, hva er mynter på dette punktet. Vi fortsetter å gå gjennom programmet. Tråkke over. Kjølig. Vi går over dimes. Flott. Vi ser at det er tatt off $ 0,10 for en krone. Og nå har vi to mynter. Det er riktig. Vi går over pennies og vi ser at vi har fått til overs cent. Hmm, det er rart. Her oppe på programmet, skulle jeg å ha trukket mine pennies. Kanskje jeg var bare ikke gjør at linjen rett. Og akk, kan du se her, fordi vi vet at vi er stepping gjennom linjene 32 og 33, det er der vårt program feilaktig hadde variabler kjøre. Så vi kan se og se, oh, Jeg trekke cents her, men jeg er faktisk ikke legge til min myntverdi. Jeg legger til cent. Og jeg ønsker ikke å legge til cents, jeg vil legge til mynter. Så hvis vi endre det til mynter, vi har et arbeidsprogram. Jeg kan kjøre check50. Du kan bare gå ut av GDB rett her og deretter kjøre check50 igjen. Jeg kunne bare gjøre dette. Jeg må gjøre grådig. 0,41. Og her er det utskrift ut det rette svaret. Så som dere kan se, GDB er et veldig kraftig verktøy for når vi har så mye kode skjer og så mange variabler at det er vanskelig for oss, som et menneske, for å holde styr på. Datamaskinen, i GDB debugger, har evnen å holde styr på alt. Jeg vet, i Visionaire, dere sannsynligvis kan ha truffet noen segmentering feil fordi du kjører utenfor banen for ditt array. I eksempelet med Cæsar, det er akkurat det jeg har implementert her. Så jeg glemte å se etter hva som ville skje hvis jeg hadde ikke to kommandolinjeargumenter. Jeg hadde ikke bare sette i at innsjekking. Og så hvis jeg kjører Debug-- satt jeg min stoppunkt til høyre der. Jeg kjører Debug. OK. Yeah. Så egentlig, GDB skulle å ha fortalt meg det var en segmentering feil der. Jeg vet ikke hva som skjedde rett der, men når jeg kjørte den, det var i arbeid. Når du kjører linjer med kode gjennom og GDB kanskje bare plutselig slutte på deg, gå opp og se hva den røde feilen er. Det skal fortelle deg, hei, du hadde en segmentering feil, noe som betyr at du prøvde å få tilgang plass i en matrise som ikke eksisterte. Yeah. Så i det neste problemet satt denne uken, dere vil trolig ha mye variabler som flyter rundt. Du kommer ikke til å være sikker på hva de betyr på et visst punkt. Så GDB vil virkelig hjelpe deg i å finne ut hva de er alle tilsvar og å være i stand til å se at visuelt. Er noen forvirret på hvordan noe av det arbeidet? Kjølig. Greit. Så etter det, er vi kommer til å stupe rett inn er fire forskjellige typer former for denne uken. Hvor mange av dere, først av alt, før vi begynner, har lest hele spec for pset3? OK. Jeg er stolt av dere. Det er som halvparten av klassen, som er betydelig mer enn forrige gang. Så det er flott, fordi når vi snakker om innholdet i lecture-- eller sorry, i section-- Jeg liker å forholde seg mye av det tilbake til hva PSet er og hvordan du vil implementere det i din PSet. Så hvis du kommer med lese spec, det vil være mye lettere for deg å forstå hva jeg snakker om når jeg sier, oh hei, dette kan være en virkelig godt sted å implementere denne typen. Så de av dere som har lest spec vet det, som en del av PSet, du er nødt til å skrive en type slag. Så dette kan være svært nyttig for mange av dere i dag. Så vi vil begynne med, hovedsak, den mest enkel type sortering, valg liksom. Den typiske algoritme for hvordan vi skulle gå om dette er-- David gikk gjennom alle disse i forelesning, så jeg vil raskt flytte sammen her-- er egentlig, du har en rekke verdier. Og så finner du den minste usortert verdi og du bytte denne verdien med den første usortert verdi. Og så du bare terpe med resten av listen. Og her er en visuell forklaring av hvordan det ville fungere. Så for eksempel, hvis vi skulle starte med en rekke av fem elementer, index 0 til 4, med 3, 5, 2, 6, 4 og verdiene plasseres i array-- så akkurat nå, vi bare kommer til å anta at de er alle usortert fordi vi har ikke testet noe annet. Så hvordan et utvalg slags ville arbeid er at det ville først kjøre gjennom helheten av usortert array. Det ville plukke ut den minste verdien. I dette tilfellet, 3, høyre nå, er den minste. Det blir til fem. Nope, fem er ikke større than-- eller beklager, er ikke mindre than-- tre. Så minimumsverdien er fortsatt tre. Og så får du til to. Datamaskinen ser, oh, to er mindre enn tre. 2, må nå være minimumsverdi. Og så 2 swaps med at første verdien. Så etter ett pass, trenger vi faktisk se at 2 og 3 er byttet. Og vi bare kommer til å fortsette å gjøre dette igjen med resten av matrisen. Så vi kommer til å bare kjøre gjennom de siste fire indekser i rekken. Vi får se at tre er neste minimumsverdi. Så vi kommer til å bytte det med fire. Og da er vi bare kommer til å fortsette kjører gjennom til slutt, du få til en sortert array i hvilken 2, 3, 4, 5, og 6 er sortert. Har alle forstå logikken av hvordan et utvalg slags jobber? Du har bare en slags fra en minimumsverdi. Du holder styr på hva det er. Og når du finner den, bytte du det med den første verdien i array-- eller, ikke den første value-- neste verdi i matrisen. Kjølig. Så som dere slags så fra et kort glimt, vi kommer til å pseudo ut dette. Så hvis dere i ryggen vil danne en gruppe, alle på et bord kan danne en liten partner, jeg kommer å gi dere som tre minutter å bare snakke gjennom logikken, på engelsk, om hvordan vi kan være i stand til å gjennomføre pseudokode for å skrive et utvalg sort. Og det er godteri. Kom opp og få godteri. Hvis du er i ryggen, og du vil godteri, kan jeg kaste godteri på deg. Egentlig gjør you-- kult. Åh unnskyld. OK. Så hvis vi har lyst til, som en klasse, skrive pseudo for hvordan en kan nærme seg dette problemet, bare du gjerne. Jeg vil bare gå rundt og, i orden, spør grupper for den neste linje hva vi bør gjøre. Så hvis dere ønsker å starte off, hva er det første å gjøre når du prøver å implementere en måte å løse dette programmet selektivt sortere en liste? La oss bare anta at vi har en rekke, ok? PUBLIKUM: Du ønsker å lage noen liksom [uhørbart] at du er kjører gjennom hele klyngen. ANDI PENG: Høyre. Så du kommer til å ønske å reagere gjennom hver plass, ikke sant? Så stor. Hvis dere ønsker å gi meg neste line-- yeah, i ryggen. PUBLIKUM: Sjekk dem alt etter de minste. ANDI PENG: Det vi går. Så vi ønsker å gå gjennom og kontrollere se hva minimumsverdien er, ikke sant? Jeg kommer til å forkorte det til "min." Hva gjør dere vil gjøre etter du har funnet den laveste verdien? PUBLIKUM: [uhørbart] ANDI PENG: Så du kommer til å ønske å slår den med den første av den oppstillingen, ikke sant? Det er begynnelsen, jeg kommer til å si. Greit. Så nå som du har byttet den første en, hva vil du gjøre etter det? Så nå vet vi at denne her må være den minste verdien, ikke sant? Da har du en ekstra hvile i matrisen som er usortert. Så hva du ønsker å gjøre her, hvis du Gutta ønsker å gi meg neste linje? PUBLIKUM: Så da du ønsker å reagere gjennom resten av matrisen. ANDI PENG: Yeah. Og så hva betyr gjentakelse gjennom en slags innebære vi må sikkert? Hvilken type of-- PUBLIKUM: Oh, en ekstra variabel? ANDI PENG: Sannsynligvis en annen for loop, ikke sant? Så vi sannsynligvis kommer til å ønske å veksle through-- stor. Og så kommer du til å gå tilbake og sannsynligvis kontrollere minimum igjen, ikke sant? Og du kommer til å terpe dette, fordi sløyfene bare kommer å holde i gang, ikke sant? Så som dere kan se, vi bare har en generell pseudo av hvordan vi vil at dette programmet skal se ut. Dette iterere her, hva gjør vi vanligvis trenger å skrive i vårt kode hvis vi ønsker å iterere gjennom en array, hva slags struktur? Jeg tror Christ allerede har sagt dette før. PUBLIKUM: En for loop. ANDI PENG: A for loop? Nettopp. Så dette er trolig kommer til å være en for loop. Hva er en sjekk her kommer til å innebære? Vanligvis, hvis du ønsker å sjekke hvis noe er noe else-- PUBLIKUM: If. ANDI PENG: An om, ikke sant? Og så swap her, vil vi gå over senere, fordi David gikk gjennom det i foredraget også. Og deretter den andre itera implies-- PUBLIKUM: Another for loop. ANDI PENG: --another for loop, akkurat. Så hvis vi ser på dette riktig, vi kan se at vi er trolig kommer til å trenge en nestet for loop med et betinget utsagn der og deretter en faktisk stykke kode som er kommer til å bytte verdier. Så jeg har bare generelt skrevet en pseudokode her. Og da er vi faktisk kommer til fysisk, som en klasse, prøve å gjennomføre dette i dag. La oss gå tilbake til denne IDE. UH oh. Hvorfor er det not-- det det er. OK. Sorry, la meg prøve å zoome inn litt mer. Det vi går. Alt jeg gjør her er at jeg har opprettet et program som heter "valg / sort.c." Jeg har opprettet en rekke av ni verdier, 4, 8, 2, 1, 6, 9, 7, 5, 3. Tiden, som du kan se, de er uordnet. n kommer til å være nummer som forteller deg hvor mye verdier du har i array. I dette tilfellet har vi ni verdier. Og jeg har nettopp fått en for loop her som skriver ut usortert array. Og på slutten, jeg har også fått en for loop som bare skriver den ut igjen. Så teoretisk, dersom dette programmet fungerer som den skal, på slutten, du burde se en trykt for loop hvori 1, 2, 3, 4, 5, 6, 7, 8, 9 er alle på riktig måte for. Så vi har fått vår pseudo her. Ønsker noen to-- jeg bare kommer til å gå be om volunteers-- fortelle meg nøyaktig hva du skal skrive om vi vil, først, bare iterere ved begynnelsen av denne array? Hva er kodelinje jeg er sannsynligvis kommer til å trenge her? PUBLIKUM: [uhørbart] ANDI PENG: Ja, føler gratis to-- beklager, du trenger ikke å stå opp-- følelse fritt til å heve stemmen litt. PUBLIKUM: For int i lik 0-- ANDI PENG: Ja, bra. PUBLIKUM: Jeg er mindre enn utvalg lengde. ANDI PENG: Så holde i tankene her, fordi vi ikke har en funksjon som forteller oss hvor lang en matrise, vi allerede har en verdi som lagrer det. Høyre? En annen ting å huske i mind-- i en matrise av ni verdier, hva er indekser? La oss bare si denne matrisen var 0 til 3. Du ser at den siste Indeksen er faktisk tre. Det er ikke fire, selv om det er fire verdier i matrisen. Så her må vi være veldig forsiktig av det vår tilstand for lengden kommer til å være. PUBLIKUM: Ville det ikke være n minus 1? ANDI PENG: Det kommer n minus en, akkurat. Gjør det fornuftig, hvorfor det er n minus en, alle? Det er fordi arrays er null-indeksert. De starter på 0 og kjøre opp til n minus en. Ja, det er litt vanskelig. OK. Og så-- PUBLIKUM: Isnt'1 at allerede tatt vare på selv, ved å bare ikke si "mindre enn eller lik "og bare si" mindre enn? " ANDI PENG: Det er en veldig godt spørsmål. Så, ja. Men også, slik at vi er implementere sjekker høyre, må du sammenligne to verdier. Slik at du faktisk ønsker å la "til" tom. Fordi hvis du sammenligner denne, er du ikke kommer har noe etter det å sammenligne med, ikke sant? Yeah. Så i ++. La oss legge våre parentes i. Uff da. Flott. Så vi har i begynnelsen av vår ytre loop. Så nå er vi sannsynligvis vil opprette en variabel for å holde spor av den minste verdien, ikke sant? Ønsker noen å gi meg kodelinje som ville gjøre det? Hva trenger vi hvis vi skal å ønske å lagre noe? Høyre. Kanskje et bedre navn for det ville be-- "temp" helt works-- kanskje en mer treffende navnet ville bli, hvis vi ønsker den minste value-- PUBLIKUM: Min. ANDI PENG: min, der vi går. min ville være bra. Og så her, hva gjør vi ønsker å initialisere den til? Dette er litt vanskelig. Fordi akkurat nå på begynnelsen av denne matrisen, du ikke har sett på noe, ikke sant? Så hva, automatisk, hvis vi er bare på i lik 0, hva ønsker vi å initial vår første minimumsverdi til? PUBLIKUM: i. ANDI PENG: i, akkurat. Christ, hvorfor vi ønsker initialisere det til jeg? PUBLIKUM: Fordi, vel, vi begynner med 0. Så fordi vi har ingenting å sammenligne det til, vil minimum ende opp som 0. ANDI PENG: Nettopp. Så hun er helt riktig. Fordi vi har faktisk ikke sett på noe ennå, vi vet ikke hva vår minimumsverdi er. Vi ønsker å bare initialisere den til Jeg, som i dag, er rett her. Og som vi fortsetter å flytte ned denne matrisen, vi vil se at med hver ekstra pass, intervaller i. Og så på det punktet, Jeg er trolig kommer å ønske å være minimum, fordi det kommer til å bli hva er i begynnelsen av usortert array. Kjølig. Så nå ønsker vi å legge til en for loop her som er kommer til å iterere gjennom usorterte, eller resten av denne matrisen. Ønsker noen å gi meg en kodelinje som ville gjøre det? Hint-- hva trenger vi her nede? Hva kommer til å gå i dette for loop? Yeah. PUBLIKUM: Så vi ønsker å har et annet heltall, fordi vi kjører gjennom resten i matrisen i stedet for den i, så kanskje j. ANDI PENG: Ja, høres j bra for meg. Er lik? PUBLIKUM: Så vil være i pluss 1, fordi du starter på neste verdi. Og deretter til den end-- så igjen, er j mindre enn n minus en, og deretter j ++. ANDI PENG: Great. Og så i her, vi kommer til å ønske å sjekke for å se om vår vilkåret er oppfylt, ikke sant? Fordi du ønsker å endre den laveste verdien hvis det er faktisk mindre enn hva du sammenligner det til, ikke sant? Så hva skal vi ønsker her inne? Sjekk for å se. Hva slags statement vi sannsynligvis kommer ti vil bruke hvis vi ønsker å sjekke noe? PUBLIKUM: En hvis setningen. ANDI PENG: An hvis setningen. Så if-- og hva som kommer til å være betingelse av at vi ønsker inne av vår hvis setningen? PUBLIKUM: Hvis verdien av j er mindre enn verdien av I-- ANDI PENG: Nettopp. Så if-- så denne matrisen kalles "array". Flott. Så hvis array-- hva var det? Si det igjen. PUBLIKUM: Hvis matrise-j er mindre enn matrise-i, så vi ville endre min. Så min ville være j. ANDI PENG: Betyr det fornuftig? OK. Og nå her nede, vi faktisk ønsker å gjennomføre swap, ikke sant? Så husker, i foredrag, som David, når han prøvde å bytte the-- hva som var it-- appelsinjuice og milk-- PUBLIKUM: Det var ekkelt. ANDI PENG: Ja, det var litt ekkelt. Men det var en ganske god konsept demonstrere tid. Så tenk på dine verdier her. Du har fått en rekke av min, en rekke i, eller hva vi prøvde å bytte her. Og har du sannsynligvis ikke kan helle dem inn hverandre samtidig, til høyre? Så hva skal vi til å trenge for å lage her for å bytte verdiene riktig? PUBLIKUM: En midlertidig variabel. ANDI PENG: En midlertidig variabel. Så la oss gjøre int temp. Se, dette ville være en bedre tid to-- Jøss, hva var det? OK. Så dette ville ha vært en bedre tid for å nevne variabelen "temp." Så la oss gjøre int temp. Hva skal vi satt temp lik her? PUBLIKUM: Min? ANDI PENG: Det er litt vanskelig. Det faktisk ikke saken i slutten. Det spiller ingen rolle hva For du velger å bytte i så lenge du gjør at du er holde styr på hva du bytte. PUBLIKUM: Det kan være matrise-i. ANDI PENG: Ja, la oss gjøre matrise-i. Og så hva er neste linje av koden vi ønsker å ha her? PUBLIKUM: array-i er lik matrise-j. ANDI PENG: Og til slutt? PUBLIKUM: array-j matrise-i er lik. Målgruppe: Eller matrise-j equals matrise-temp-- eller temp. ANDI PENG: OK. Så la oss kjøre dette og se hvis det kommer til å fungere. Hvor er det som skjer? Å, det er et problem. Se, på linje 40, vi er prøver å bruke matrise-j? Men hvor kommer j bare eksistere i? PUBLIKUM: I for loop. ANDI PENG: Høyre. Så hva skal vi gjøre? PUBLIKUM: Definer det utenfor the-- PUBLIKUM: Ja, jeg tror du har å bruke en annen hvis setningen, ikke sant? Så som, hvis minimum-- all right, la meg tenke. ANDI Peng: Guys, prøv å ta en titt La oss se, hva er det noe vi kan gjøre her? PUBLIKUM: OK. Så hvis minimum er ikke lik j-- så hvis minimum er fortsatt I-- da vi ikke ville ha til å bytte. ANDI PENG: Betyr det like jeg? Hva ønsker du å si her? PUBLIKUM: Eller ja, hvis minimum er ikke lik i, ja. ANDI PENG: OK. Vel det løser, type, våre problemer. Men som fortsatt ikke løser problemet med hva som skjer hvis j-- siden j ikke eksisterer utenfor det, hva du vi ønsker å gjøre med det? Erklære den utenfor? La oss prøve å kjøre dette. UH oh. Vår liksom ikke fungerer. Som du kan se, vår første matrise hadde disse verdiene. Og etterpå det skal ha vært i en, to, tre, fire, fem, seks, syv, åtte, ni. Den funker ikke. Ahh. Hva skal vi gjøre? PUBLIKUM: Debug. ANDI PENG: Greit, kan vi prøve det. Vi kan feilsøke. Zoome ut litt. La oss sette vår stoppunkt. La oss gå like-- OK. Så fordi vi allerede vet at disse linjene, 15 gjennom 22, er working-- fordi alt jeg gjør er bare itera gjennom og printing-- Jeg kan gå videre og hoppe over dette. La oss starte på linje 25. Oop, la meg bli kvitt det. PUBLIKUM: Så stoppunkt er hvor debugging starter? ANDI PENG: Eller stopper. PUBLIKUM: Eller stopper. ANDI PENG: Yeah. Du kan sette flere stoppunkt og Det kan bare hoppe fra den ene til den andre. Men i dette tilfellet vet vi ikke der skjer det feil. Så vi bare ønsker å starte fra toppen og ned. Jepp. OK. Så denne linjen her, kan vi gå inn. Du kan se her nede, vi har en matrise. De er de verdier som befinner seg på matrisen. Ser du det, hvordan indeksen 0, det tilsvarer value-- oh, Jeg kommer til å prøve å zoome inn. Beklager, det er virkelig vanskelig til see-- på tabellindekser 0, vi har en verdi på 4 og da så videre og så videre. Vi har våre lokale variabler. Akkurat nå jeg er lik 0, som vi ønsker den skal være. Og så la oss holde tråkke gjennom. Våre minimum er lik 0, som vi også ønsker den skal være. Og så går vi inn vår andre for loop, hvis matrise-j er mindre enn matrise-i, som ikke var det. Så fikk du se hvordan som hoppet over det? PUBLIKUM: Så skal den hvis minimum, alt at-- bør ikke at være inne i den første for loop? ANDI PENG: Nei, fordi du fortsatt ønsker å teste. Du ønsker å gjøre en sammenligning hver tid, selv etter at du har kjørt gjennom den. Du trenger ikke bare ønsker å gjøre det på første pass-through. Du ønsker å gjøre det med hver ekstra pass igjen. Så du ønsker å se etter din tilstand inne. Så vi skal bare fortsette å kjøre gjennom her. Jeg skal gi dere et hint. Det har å gjøre med det faktum at når du sjekker din betinget, du ikke sjekker for riktig indeksen. Så akkurat nå er du sjekker for rekke indeks over j er mindre enn utvalg indeks over i. Men hva gjør du opp på begynnelsen av for loop? Er du ikke sette j lik jeg? Ja, så vi kan faktisk avslutte debugger her. Så la oss ta en titt på vår pseudokode. For-- vi kommer til å starter på jeg er lik 0. Vi kommer til å gå opp til n minus en. La oss sjekke, vi har det riktig? Jepp, det var rett. Så da inne her, vi er kommer til å lage en minimumsverdi og sette det lik i. Gjorde vi det? Jepp, gjorde det. Nå i vårt indre for loop, vi er kommer til å gjøre j lik jeg til n minus en. Gjorde vi det? Ja, vi gjorde det. Så imidlertid hva vi sammenligner her? PUBLIKUM: j pluss 1. ANDI PENG: Nettopp. Og så kommer du til å ønske å sette minst en lik j + 1 tillegg. Så jeg gikk gjennom som virkelig raskt. Har dere forstår hvorfor det er j pluss en? OK. Så i arrayet, i din første går gjennom, din for loop, for int jeg er lik 0, la oss bare anta at dette har ikke blitt endret ennå. Vi har en rekke, helt, bare fire usorterte elementer, ikke sant? Så vi ønsker å initial jeg lik 0. Og jeg kommer til å like kjøre gjennom denne sløyfen. Og så i den første pass, skal vi å klargjøre en variabel kalt "min" som også er lik i, fordi vi ikke har en minimumsverdi. Så det er for tiden lik 0 i tillegg. Og så kommer vi til å gå gjennom. Og vi ønsker å reagere igjen. Nå som vi har funnet hva vår minimum er, vi ønsker å iterere gjennom på nytt for å se om det er å sammenligne, ikke sant? Så j, her kommer til lik i, som er 0. Og så hvis matrisen j pluss jeg, som er den som er neste over, som mindre enn hva din nåværende minste verdien er, du ønsker å bytte. Så la oss bare si at vi har fikk, som, 2, 5, 1, 8. Akkurat nå er jeg lik 0 og j er lik 0. Og det er vår minimumsverdien. Hvis matrise-j pluss I-- så hvis den ene det er etter det vi ser på er større enn den før det, det kommer til å bli minimum. Så her ser vi at 5 ikke er mindre enn det. Så det kommer til å være fem. Vi ser at en er mindre enn to, ikke sant? Så nå vet vi at vår minste er kommer til å være indeksverdien på 0, 1, 2. Yeah? Og så når du kommer ned hit, du kan bytte de riktige verdiene. Så når dere var bare å ha det j før, ble du ikke ser på den ene etter den. Du var ute på den samme verdi, som er grunnen til at det rett og slett ikke å gjøre noe. Betyr det fornuftig for alle, hvorfor vi trengte som pluss en det? OK. La oss nå bare kjøre gjennom det å gjøre at resten av koden er korrekt. Hvorfor er det som skjer? Ah, det er min rett her. Vi var sammenligne feil verdi. Å nei. Oh yeah, her nede var vi bytte feil verdier også. Fordi vi var ute på i og j. De er de vi sjekker. Vi har faktisk ønsker å bytte minimum, den nåværende minimum, med hva den ene utenfor er. Og som dere kan se ned her har vi en sortert array. Det hadde bare å gjøre med det faktum at når vi sjekket den verdier vi sammenligne, Vi var ikke ute på de rette verdiene. Vi var ute på den samme her, faktisk ikke bytte den. Du må se på den ene siden til det og deretter kan du bytte. Så det er det var slags avlytting vår kode før. Og hva jeg gjorde her er alt debugger kunne ha gjort for deg Jeg bare gjorde det på bord, fordi det er enklere å se heller enn å prøve for å zoome inn på debugger. Betyr det fornuftig for alle? Kjølig. Greit. Vi kan gå videre til å snakke om asymptotisk notasjon, som er bare en fancy måte å si det runtimes av alle disse former. Så jeg vet David, i foredrag, berørt runtimes. Og han gikk gjennom hele formel hvordan å beregne kjøretider. Ingen bekymringer om at. Hvis du er virkelig nysgjerrig på hvordan det fungerer, gjerne snakke med meg etter pkt. Vi kan gå gjennom formlene sammen. Men alle dere må virkelig vet er at n squared vel 2 er det samme som n squared. Fordi det største antallet, eksponenten, vokser mest. Og så for vårt formål, alt vi bryr oss om er det gigantiske tall som er økende. Så hva er den beste saken runtime av utvalget slag? Hvis du kommer til å ha å iterere gjennom en liste og deretter iterere gjennom resten av den listen, hvor mange ganger er Skal du sannsynligvis, i verste case-- i beste fall sorry-- kjøre gjennom? Kanskje bedre spørsmål er å spørre, hva er det verste tilfellet runtime av utvalget slag. PUBLIKUM: n squared. ANDI PENG: Det er n squared, ikke sant. Så en enkel måte å tenke på dette er like, helst du har to nestet for løkker, det kommer til å bli n squared. Fordi ikke bare er du går gjennom nok en gang, du må gå tilbake rundt og kjøre gjennom det nok en gang inne for hver verdi. Så i så fall kjører du n ganger n squared, som er-- beklager, n ganger n, noe som tilsvarer n squared. Og sort er også litt unik i den forstand at det ikke spiller noen rolle om disse Verdiene er allerede i orden. Det er fortsatt kommer til å kjøre gjennom anyways. La oss bare si at dette var en, to, tre, fire. Uavhengig av hvorvidt det var i rekkefølge, ville det fortsatt ha løp gjennom og likevel kontrollert minimumsverdien. Det ville ha gjort samme antall kontroller hver gang, selv om det faktisk ikke røre noe. Slik at i et slikt tilfelle, det beste og verste runtimes er faktisk tilsvarende. Så den forventede runtime av utvalget sortere, som vi utpeke med symbolet av theta, theta, i dette tilfellet vil også bli n squared. Alle tre av disse ville bli n squared. Er alle klare på hvorfor runtime er n squared? Greit. Så jeg skal bare raskt kjøre gjennom resten av den slags. Algoritmen for boble sort-- huske, Dette var den første David gikk over i forelesning. Hovedsak, du går gjennom hele listen og du swap-- du bare sammenligne to om gangen. Og hvis man er større, enn du bare bytte dem. Så hvis disse er større, vil du bytte. Jeg har offisielt her. Så la oss bare si at du hadde 8, 6, 4, 2. Du vil sammenligne åtte og en 6. Du trenger for å bytte dem. Du vil sammenligne åtte og en 4. Du trenger for å bytte dem. Hvis du må bytte den 8 og 2, endre dem også. Så i en slik følelse, kan du se, spilles ut over en lang tidsperiode, hvordan verdiene slags boble til endene, noe som er grunnen til at vi kaller det boble slag. Vi ville bare kjøre gjennom på nytt på vår andre pass, og vår tredje pass, og vår fjerde runden. Hovedsak, boble liksom bare renner til du ikke gjør noen flere bytteavtaler. Så i den forstand, dette er bare den generelle pseudokode for det. Ingen grunn til bekymring, disse vil alle være online. Vi trenger ikke å faktisk gå over dette. Vi bare initial en teller variabel som starter på 0. Og vi iterere gjennom hele array. Og hvis en verdi er-- om dette verdien er større enn denne verdien, du kommer til å bytte dem. Og da er du bare kommer til å holde det gående. Og du kommer til å telle. Og du bare kommer til å fortsette å gjøre dette mens telleren er større enn 0, hvilket betyr at hver gang du må bytte, du vet at du vil gå tilbake og sjekke igjen. Du ønsker å holde kontroll før du vet at du ikke trenger å bytte lenger. Så hva er det beste og verste case tider for boble liksom? Og hint-- dette er faktisk annerledes fra utvalget slag i den forstand at disse to svarene er ikke det samme. Tenk på hva som ville skje i en sak dersom det var allerede sortert. Og tenke på hva ville skje hvis det var i det tilfelle hvor det ikke ble sortert. Og du kan slags kjøre gjennom hvorfor det skjer. Jeg skal gi dere, liker, 30 sekunder på å tenke på det. OK. Har noen en gjetning på hva worst case runtime av boble typen er? Yeah. PUBLIKUM: Ville det være, som, n ganger n minus 1 eller noe sånt? Liker, hver gang det kjøres, det er bare, som, en swap mindre at uansett hva det var. ANDI PENG: Ja, så du er helt rett. Og dette er en sak der din Svaret var faktisk mer komplisert enn det vi trenger for å gi. Så det kommer til å run-- jeg er kommer til å slette alt dette her. Er alle gode? Kan jeg slette denne? OK. Du kommer til å kjøre gjennom n ganger den første gangen, ikke sant? Og de kommer til å kjøre gjennom n minus en annen gang, ikke sant? Og så kommer dere til å holde kommer, n min 2, et cetera. David gjorde dette i et foredrag, hvor, hvis du har lagt opp alle disse verdiene, du får noe som er like-- yeah-- over 2, som i det vesentlige bare reduserer ned til n squared. Du kommer til å få en rare brøkdel der inne. Og så bare vet at n squared alltid forrang brøkdel. Og så i dette tilfellet, det verste runtime ville bli n squared. Hvis det var i synkende rekkefølge, tror du har å gjøre en swap hver eneste gang. Hva ville være, potensielt, beste fall runtime? La oss bare si, hvis listen var allerede i orden, hva ville runtime være? PUBLIKUM: n. ANDI PENG: Det er n, akkurat. Og hvorfor er det n? PUBLIKUM: Fordi du bare må sjekke på hver gang. ANDI PENG: Nettopp. Så på best mulig runtime, Hvis denne listen var allerede sorted-- la oss si 1, 2, 3, 4-- deg ville bare gå gjennom, ville du sjekker, du ville se, oh, de alle panorere. Jeg trengte ikke å bytte. Jeg er ferdig. Så i dette tilfellet, er det bare n eller antall skritt du bare måtte sjekke inn den første listen. Og etter vi nå treffer innsetting sortere, der algoritmen er vesentlig å skille det inn i en sortert og usortert del. Og så en etter en, de usorterte verdiene er satt inn i deres aktuelle posisjoner i begynnelsen av listen. Så for eksempel, har vi en listen 3, 5, 2, 6, 4 på nytt. Vi vet at det er i dag usortert fordi vi har bare begynte å se på det. Vi tar en titt og vi vet at den første verdien er sortert, ikke sant? Hvis du bare ser på en rekke størrelse ett, vet du at det er sortert. Så da vet vi at andre fire er usortert. Vi går gjennom, og vi ser at verdien. La oss gå tilbake. Se at verdien av 5? Vi tar en titt på den. Vi sammenligne det med tre. Vi vet at det er større enn 3, så vi vet at det er sortert. Så nå vet vi at de to første sorteres og de tre siste er det ikke. Vi tar en titt på to. Vi først sjekke det med fem. Det er mindre enn 5? Det er ikke. Så vi må holde utkikk ned. Så du sjekke to av tre. Er det mindre enn? Nei. Så du vet en 2 må settes inn i den fremre og 3 og 5 begge må bli skjøvet ut. Gjøre dette igjen med 6 og 4. Og vi bare fortsette å se hovedsak, der vi bare sjekke, sjekk, sjekk. Og før det er i riktig posisjon, vi slags bare sett det inn i riktig posisjon, som er der navnet på den kom fra. Så det er bare algoritmen, pseudokode per se, type, om hvordan vi skulle gjennomføre et innførings sort. Pseudokode er her. Det handler online. Ingen grunn til bekymring hvis dere er prøver å kopiere dette ned. Så igjen, samme question-- hva ville være den beste og verste runtimes for innsetting slag? Det er svært lik den siste spørsmålet. Jeg skal gi dere, liker, 30 sekunder på å tenke på dette også. OK Er det noen som ønsker å gi meg det verste runtime? Yeah. PUBLIKUM: n squared. ANDI PENG: Det er n squared. Og hvorfor er det n squared? PUBLIKUM: Fordi i omvendt rekkefølge, har du for å gå gjennom n ganger n, som er-- ANDI PENG: Ja, akkurat. Så samme som i boblen slag. Hvis denne listen er i synkende rekkefølge, er du nødt til å sjekke første gang. Og deretter med hver tilleggsverdi, er du nødt til å sjekke det mot hver enkelt verdi, ikke sant? Og så helt, du kommer til å gjøre En N pass ganger en annen n pass, som er n squared. Hva om den beste saken? Yeah. PUBLIKUM: n minus en, fordi første er allerede squared. ANDI PENG: Så nær. Svaret er faktisk n. Fordi mens den første er sorteres, kan det ikke det actually-- vi bare lucked ut, i som eksempel at to tilfeldigvis var det minste tallet. Men det vil ikke alltid være tilfelle. Hvis to allerede er sortert i begynnelsen men du ser, og det er en en her, 1 kommer til å støte den. Og det kommer til å ende opp med å bli dunket anyways. Så i beste fall det er faktisk bare skal være n. Hvis du har en, to, tre, 4, 5, 6, 7, 8, er du kommer til å kjøre gjennom at hele listen en gang for å sjekke om alt er i orden. Er alle klare på løping tider utvalg så vel? Jeg vet at jeg kommer gjennom disse virkelig fort. Men bare vet at hvis du kjenner generelle konsepter, bør du være god. OK. Så jeg vil bare gi dere kanskje, som, et minutt til å snakke med dine naboer på hva som er bare noen av de viktigste forskjellene mellom disse typer slag. Vi vil gå over det snart. PUBLIKUM: Oh, OK. ANDI PENG: Yeah. OK. Cool, la oss reconvene som klasse. OK. Så dette var litt av en åpent spørsmål i den forstand at det er mange svar på dem. Og vi vil gå over noen av dem kort. Jeg ville bare komme dere tenke på hva differensiert alle tre typer slag. Og jeg har hørt, også, en stor question-- hva betyr fusjonere slags gjøre? Stort spørsmål, fordi det er hva vi dekker neste. Så fusjonere typen er en sort som fungerer veldig forskjellig fra de andre former. Som dere kan see-- gjorde David som demo hvor han hadde alle de kule lyder av å se hvordan flette slags løp, som, uendelig raskere enn de to andre typer? OK. Så det er fordi flettingen sorter implementerer at skillet og erobre konsept som vi har snakket om mye i forelesning. I den forstand at vi liker å jobbe smartere, ikke hardere, når du deler og erobre problemer, og bryte dem ned, og deretter sette dem sammen, gode ting alltid skje. Så måten fusjonere sorter hovedsak fungerer er at det skiller en usortert array i halvparten. Og så er det nødt to halvdeler av arrays. Og det bare sorterer de to halvdelene. Det holder bare å dele i to, i halvparten, i to før alt er sortert og deretter rekursivt setter det hele sammen. Så det er egentlig abstrakte. Så dette er bare litt av pseudokode. Betyr det fornuftig i måten den kjører? Så la oss bare si at du har en utvalg av n elementer, ikke sant? Hvis n er mindre enn 2, kan du gå tilbake. Fordi du vet at hvis det er bare én ting, må det være sortert. Else, du sortere venstre halvdel, og deretter sortere høyre halvdel, og deretter flette. Så mens det ser veldig lett, i virkeligheten, tenker det er slags vanskelig. Fordi du er som, vel, det er slags kjører på seg selv. Høyre? Det kjører på seg selv. Så i den forstand, rørte David ved rekursjon i klassen. Og det er et konsept vi skal snakke om mer. Det er som dette, disse to linjene her, er faktisk akkurat det programmet fortelle den til å kjøre seg selv med forskjellig inngang. Så i stedet for å kjøre selv med helheten av n elementer, du kan bryte det ned i venstre halvdel og høyre halvdel og deretter kjøre den på nytt. Og så får vi se på det visuelt, fordi jeg er en visuell elev. Det fungerer bedre for meg. Så skal vi se på et visuelt eksempel her. La oss si at vi har en matrise, seks elementer, 3, 5, 2, 6, 4, 1, ikke sortert. Greit, det er mye på denne siden. Så hvis dere kan se på første trinn her, 3, 5, 2, 6, 4, 1, du kan dele den i to. Du har 3, 5, 2, 6, 4, 1. Du vet at disse aren't-- deg vet ikke om de er sortert eller ikke, så du holder bryte dem ned, i to, i to, i to, til slutt, du bare har ett element. Og ett element er alltid sortert, ikke sant? Så vi vet at 3, 5, 2, 4, 6, 1, av seg selv, er sortert. Og nå kan vi sette dem sammen igjen. Så vi vet at 3, 5. Vi setter dem sammen. Vi vet at det er sortert. De 2 er fortsatt der. Vi kan sette 4 og 6 sammen. Vi vet at det er sortert, så vi sette det sammen. Og en er der. Og så kan du bare se på disse to halvdeler her. Du har 3, 5, 2, 2, 3, 5. Du kan bare sammenligne begynnelsen av alt. Fordi du vet at dette er sortert og du vet at det er sortert. Så da kan du ikke engang å sammenligne 5, du bare sammenligne 3. Og 2 er mindre enn 3, så Kjenner du to må gå til slutt. Samme om det. Den en må gå her. Og så når du går for å sette disse to verdier sammen, du vet at dette er sortert og du vet at det er sortert. Så da en og 2, at en er mindre enn 2. Som forteller deg at en skal gå på slutten av denne uten å se på tre eller fem. Og så fire, kan du bare sjekk, det går rett inn her. Du trenger ikke å se på fem. Samme med den 6. Du vet at 6-- det bare trenger ikke å bli sett. Og så på den måten, er du bare spare deg mange skritt når du sammenligner. Du trenger ikke å sammenligne hver elementet mot andre elementer. Du bare sammenligne mot de at du trenger å sammenligne den mot. Så det er på en måte et abstrakt begrep. Ingen grunn til bekymring hvis det ikke er ganske treffer deg rett ennå. Men generelt, er dette hvordan et flette slags jobber. Spørsmål, raske spørsmål, før jeg går videre? Yeah. PUBLIKUM: Så du sier at du tar 1, og deretter 4, og 6 og sette dem i. Så er those-- ikke er ikke du ser på dem som separate elementer, ikke som helhet? ANDI PENG: Yeah. Så hva som skjer er at du i utgangspunktet oppretter en helt ny rekke. Så du vet det, her har jeg to matriser av størrelse 3, ikke sant? Så du vet at min sorterte utvalg må ha seks elementer. Så du bare lage en ny mengde minne. Så du er typen som være sløsing av hukommelse, men det spiller ingen rolle fordi det er så liten. Så du ser på en og du ser på to. Og du vet at en er mindre enn to. Så du vet at en bør gå i I begynnelsen av alle disse. Du trenger ikke engang å se på 3 og 5. Så du vet en går der. Da har du i utgangspunktet hogge av en. Det er, som døde for oss. Så vi må bare 2, 3, 5, og deretter 4 og 6. Og da vet du at du sammenligne 4 og 2, oh, to bør gå inn der. Så du slenger den to ned, du hogge det av. Så da er det bare 3 og 5 i fire og seks. Og du bare holde hakking den av før du setter dem i rekken. PUBLIKUM: Så du er bare alltid sammenligne [uhørbart]? ANDI PENG: Nettopp. Så i den forstand, er du bare sammenligne, i hovedsak, en rekke mot den andre nummer. Og fordi du vet at det er sortert, du trenger ikke å se gjennom alle tallene. Du må bare se på den første. Og så kan du bare slenger dem ned, fordi du vet de hører hvor de trenger å tilhøre. Yeah. Godt spørsmål. Og så hvis noen av dere er litt ambisiøst, gjerne se på denne koden. Dette er faktisk fysisk implementering av hvordan vi skulle skrive merge sort. Og du kan se, det er svært kort. Men ideene bak det er ganske komplisert. Så hvis du har lyst til å trekke ut dette i lekser i kveld, gjerne. OK. Så David også gikk over dette i foredraget. Hva er den beste saken runtimes, verst tenkelige kjøretider, og de forventede driftstider av merge sort? Et par sekunder til å tenke. Dette er ganske vanskelig, men slags intuitive hvis du tenker på det. Greit. PUBLIKUM: Er det verste tilfellet n log n? ANDI PENG: Nettopp. Og hvorfor er det n log n. PUBLIKUM: Er ikke det fordi det blir eksponentielt raskere, så det er som en funksjon av at i stedet for bare bare å være n squared eller noe? ANDI PENG: Nettopp. Så grunnen til at runtime på dette er n log n er because-- hva er du gjør i alle disse trinnene? Du bare hakke den i to, ikke sant? Og så når vi gjør det logg, alt som det gjør er å dele et problem i to, i to, i to, i flere omganger. Og i den forstand, kan du snill av eliminere den lineære modellen at vi har brukt. Fordi når du hogge ting i halvparten, er det en logg. Det er bare den matematiske måte å representere det. Og så til slutt, på slutten, er du bare å lage en siste pasning gjennom å sette dem alle i orden, ikke sant? Og så hvis du bare nødt til å sjekke en ting, er at n. Og så er du slags å multiplisere de to sammen. Så det er som du har fått det endelige sjekk for n ned her med en logg over n opp her. Og hvis du multiplisere dem, som er n log n. Og så den best case og worst saken og forventet er alle n log n. Det er også som en annen sort. Det er som utvalget sort i den forstand at den spiller ingen rolle hva din Listen er, det bare kommer å gjøre det samme hver eneste gang. OK. Så som dere kan se, selv om den slags som vi har gått through-- n squared, det er ikke veldig effektivt. Og selv dette n log n er ikke den mest effektive. Hvis dere er nysgjerrige, det er liksom mekanismer som er så effektive at de er nesten tilnærmet flat i runtime. Du har fått noen log n-tallet. Du har fått noen log log n-tallet. Vi vil ikke berøre dem i denne klassen akkurat nå. Men hvis dere er nysgjerrige, gjerne google, hva er den mest effektive sorteringsmekanismer. Jeg vet ikke, det er noen virkelig morsomme seg, like-- det er noen virkelig morsomme seg som folk gjør. Og du lurer på hvordan de noen gang tenkt på det. Så google, hvis du har litt fritid tid, på, hva er noen morsomme måter at people-- samt effektive ways-- mennesker har vært i stand til å gjennomføre sorterer. OK. Og her er bare en hendig liten diagram. Jeg vet alt om deg, før det quiz 0, vil være i rommet ditt sannsynligvis prøver å huske det. Så det er hyggelig der for dere. Bare ikke glem den logikken som made-- hvorfor disse tallene ble forekommende. Hvis du alltid er tapt, bare sørg at du vet hva slags er. Og du kan kjøre gjennom dem i tankene dine å finne ut hvorfor de Svarene er disse svarene. Greit. Så vi kommer til å flytte på, til slutt, for å søke. Fordi som de av dere som har lest den PSet, søking er også en del av denne ukens problem setter. Du vil bli bedt om å gjennomføre to typer søk. Den ene er en lineær søk og en er en binær søk. Så den lineære søk er ganske enkelt. Du bare vil søke element av en liste for å se om du får det. Du trenger bare å iterere gjennom. Og hvis det er lik noe, du kan bare returnere det, ikke sant? Men det som vi er mest interessert i å snakke om er binært søk, til høyre, som er den splitt og hersk mekanisme som David ble demonstrere i forelesningen. Husk telefonboken eksempel at han holder å bringe opp, den som han slags slet litt på det siste året, hvor du dele problemet i to, i to, i to, igjen og igjen, til du finner det du leter etter? Og du har fått runtime av det også. Og du kan se, er det betydelig mer effektiv enn noen annen type søk. Så den måten at vi skulle gå om implementere en binær søk er, hvis vi hadde en matrise, indeks 0-6, syv elementer vi kan se i midten, right-- sorry, hvis våre spørsmål first-- hvis vi ønsker å stille spørsmålet om, gjør matrisen inneholde element av 7, selvsagt, som mennesker, og som har et så lite utvalg, er det lett for oss å si ja. Men den måten å implementere en binær søk ville være å se i midten. Vi vet at indeksen 3 er midten, fordi vi vet er det syv elementer. Hva syv delt på 2? Du kan hogge av den ekstra en. Du har tre i midten. Derfor er utvalget av 3 lik 7? Det er ikke, ikke sant? Men vi kan gjøre et par sjekker. Er utvalg av tre mindre enn 7 eller er matrise av tre som er større enn 7? Og vi vet at det er mindre enn syv. Så vi vet at, oh, må det ikke være i venstre halvdel. Vi vet at det må være i høyre halvdel, ikke sant? Så vi kan bare hogge av halve array. Vi trenger ikke engang å se på det lenger. Fordi vi vet at halvparten av vår problem-- vi vet at svaret er i høyre halvdel av vårt problem. Så vi bare se på det nå. Så nå ser vi på midten av det som er igjen. At indeksen 5. Vi gjør det samme sjekken på nytt og vi ser at det er mindre. Så vi ser til venstre for det. Og så ser vi at sjekken. Er array verdi på indeks 4 lik 7? Det er. Så vi kan returnere sant, fordi vi fant verdien i vår liste. Har den måten jeg gikk gjennom det fornuftig for alle? OK. Jeg skal gi dere kanskje, som, tre, fire minutter på å finne ut hvordan pseudokode dette i. Så tenk jeg ba deg om å skrive en funksjon kalt søk () som returneres en verdi, en boolsk verdi, det var sant eller false-- lignende, sant hvis du fant den verdi, usann hvis du ikke gjorde det. Og da du var vedtatt i verdien du var ute etter i verdier, som er array-- oh, jeg definitivt sette som på feil sted. OK. Anyways, som bør ha vært til høyre av verdier. Og deretter int n er antallet av elementene i den oppstillingen. Hvordan vil du gå om å prøve til pseudo det problemet i? Jeg skal gi dere liker tre minutter å gjøre det. Nei, jeg tror det er only-- Ja, det er en rett opp her. PUBLIKUM: Kan jeg? ANDI PENG: Ja, jeg har deg. Er at arbeiderklassen? Ok kult. OK. Greit folkens, vi er kommer til å tøyle den i. OK. Så antar vi har fått denne herlige lite utvalg med n verdier i den. Jeg visste ikke trekke linjene. Men hvordan skulle vi gå om prøver å skrive dette? Er det noen som ønsker å gi meg den første linjen? Hvis du ønsker å gi meg første linje av denne pseudokode. PUBLIKUM: [uhørbart] PUBLIKUM: Du ønsker å veksle through-- PUBLIKUM: Bare en annen for loop? PUBLIKUM: --Barnespill. ANDI PENG: Så dette er litt vanskelig. Tenk om-- du ønsker å holde kjører denne sløyfen om og om igjen til da? PUBLIKUM: Inntil [uhørbart] verdi er lik denne verdien. ANDI PENG: Nettopp. Så du kan faktisk bare write-- Vi kan også forenkle det mer. Vi kan bare gjøre en stund loop, ikke sant? Så du kan bare ha loop-- vi vet at det er en stund. Men for akkurat nå, jeg skal å si "loop" - gjennom hva? Loop until-- hva er vår slutter tilstand? Jeg tror jeg hørte det. Jeg hørte noen si det. Målgruppe: Verdier tilsvarer midten. ANDI PENG: Si det igjen. PUBLIKUM: Eller, inntil verdien du søker for er lik middelverdien. ANDI PENG: Hva om det ikke er der? Hva hvis verdien du søker for er faktisk ikke i denne matrisen? PUBLIKUM: Du går tilbake 1. ANDI PENG: Men hva gjør vi ønsker å løkke til hvis vi har en tilstand? Yeah. PUBLIKUM: Inntil det er bare én verdi? ANDI PENG: Du kan sløyfe until-- slik at du vet at du er kommer til å ha en maks verdi, ikke sant? Og du vet at du kommer å ha en min verdi, ikke sant? Fordi også, det er noe Jeg glemte å si før, som noe som er kritisk om binære søk er at klyngen er allerede sortert. Fordi det er ingen måte å gjøre dette hvis de er bare tilfeldige verdier. Du vet ikke om man er større enn den andre, ikke sant? Så du vet at din max og dine min er her, ikke sant? Hvis du kommer til å være å justere din max i dine minutter og mid-- la oss bare anta din mid verdi er riktig her-- du kommer til utgangspunktet løkke til minimum din er omtrent det samme som max, høyre eller hvis max er ikke det samme som min. Høyre? Fordi når det skjer, vet du at du har til slutt treffer den samme verdien. Så du ønsker å sløyfe inntil min er mindre enn eller lik to-- oops, ikke er mindre enn eller lik den andre veien around-- max er. Visste at fornuftig? Jeg tok et par prøver å få det riktig. Men løkke til din max verdi er egentlig nesten mindre enn eller lik minimum din, ikke sant? Det er da du vet at du har konvergert. PUBLIKUM: Når ville ditt maksimale verdien være mindre enn den minste? ANDI PENG: Hvis du holder å justere det, som er hva vi skal til å gjøre i dette. Gir det mening? Minimum og max er bare heltall som vi er trolig kommer til å ønske å lage for å holde styr på hvor vi leter. Fordi matrisen eksisterer uansett hva vi gjør. Liker, vi er faktisk ikke fysisk hakking av tabellen, ikke sant? Vi er bare å justere hvor vi ser. Gir det mening? PUBLIKUM: Yeah. ANDI PENG: OK. Så hvis det er en forutsetning for vår loop, hva gjør vi ønsker innsiden av denne loop? Hva skal vi være som ønsker å gjøre? Så akkurat nå, har vi en max og en min, høyre, trolig skapt her oppe et sted. Vi skal sannsynligvis ha å finne en middelvei, ikke sant? Hvordan skal vi være i stand til å finne midten? Hva er mathematical-- PUBLIKUM: Max pluss min delt på to. ANDI PENG: Nettopp. Gir det mening? Og gjør dere se hvorfor vi ikke bare use-- hvorfor vi gjorde dette i stedet for å gjøre nettopp n delt på 2? Det er fordi n er en verdi som kommer til å bli det samme. Høyre? Men som vi justere vår minimum og maksimumsverdier, de kommer til å endre seg. Og som et resultat, våre middel kommer til å endre også. Så det er derfor vi ønsker å gjøre dette her. OK. Og så, nå som Vi har funnet our-- ja. PUBLIKUM: Bare en rask question-- når du sier min og max, er vi antar at det er allerede sortert? ANDI PENG: Ja, det er faktisk en Forutsetningen for en binær søk, at du må vite det er sortert. Som er grunnen sortere, skrive deg i din oppgavesettet før binære søk. OK. Så nå som vi vet hvor våre midtpunkt er, hva ønsker du å gjøre her? PUBLIKUM: Vi ønsker å sammenligne som til den andre. ANDI PENG: Nettopp. Så du kommer til å sammenligne midten til verdi, ikke sant? Og hva som forteller oss når vi sammenligner? Hva ønsker vi å gjøre etterpå? PUBLIKUM: Hvis verdien er større enn på midten, vi ønsker å kutte den av. ANDI PENG: Nettopp. Så hvis verdien er større enn på midten, er vi kommer til å ønske å endre disse minimum og maxes, ikke sant? Hva ønsker vi å endre? Så hvis vi kjenner verdien er et sted her inne, hva gjør du vi å endre? Vi ønsker å endre vår minimum for å være midten, ikke sant? Og så annet, hvis det er i denne halvparten, hva vi ønsker å endre? PUBLIKUM: Din maksimale. ANDI PENG: Yeah. Og da er du bare kommer å holde looping, ikke sant? Fordi nå, etter en iterasjon gjennom, har du en maks her. Og så kan du beregne en mid. Og så kan du sammenligne. Og du kommer til å holde det gående inntil min og maxes har i hovedsak sammenfallende. Og det er da du vet at du har truffet på slutten av den. Og enten du har funnet det eller du ikke har på det tidspunktet. Betyr dette fornuftig for alle? OK. Dette er ganske viktig, fordi du vil ha å skrive dette i koden din i kveld. Men dere har en ganske god følelse av hva du bør gjøre, noe som er bra. OK. Så vi har fått om lag sju minutter igjen delen. Så vi kommer til å snakke om dette PSet at vi skal gjøre. Så PSet er delt inn i to halvdeler. Den første halvdelen innebærer implementere et funn der du skriver en lineær søk, en binære søk, og en sorteringsalgoritme. Så dette er den første tid i en PSet der vi vil være å gi dere det som kalles fordeling kode, som er kode at vi har pre-skrevet, men bare igjen noen stykker av for deg å fullføre skriftlig. Så dere, når du ser på dette kode, kan du bli virkelig redd. Hvis du bare vil, ahh, jeg vet ikke hva det gjør, Jeg vet ikke, liker, virker det som så komplisert, ahh, slappe av. Det er greit. Les spec. Spesifikasjonen vil forklare deg nøyaktig hva alle disse programmene gjør. For eksempel, er generate.c et program som vil komme med din PSet. Du trenger faktisk ikke å røre det, men du bør forstå hva det gjør. Og generate.c, er alt den gjør enten å generere slumptall eller du kan gi den et frø, som en avtalt antall at det tar, og det genererer flere tall. Så det er en bestemt måte å implementere generate.c der du kan bare gjøre en haug med tall Her kan du teste dine andre metoder på. Så hvis du ville, for eksempel teste funn, du ønsker å kjøre generate.c, generere en haug med tall, og deretter kjøre hjelpere funksjon. Din hjelpere funksjonen er der du er faktisk fysisk å skrive kode. Og tenk på hjelpere som en bibliotekfilen du skriver at funn som ringer. Og så innen helpers.c, vil du gjør søking og sortering. Og så kommer dere til hovedsak bare sette dem alle sammen. Spec vil fortelle deg hvordan du sette det på kommandolinjen. Og du vil være i stand til å teste hvorvidt ikke din sortere og søke jobber. Kjølig. Har noen allerede startet og oppstått problemer eller spørsmål de har akkurat nå med dette? OK. PUBLIKUM: Vent. Jeg har et spørsmål. ANDI PENG: Yeah. PUBLIKUM: Så jeg begynte å gjøre den lineære søk i helpers.c og det var egentlig ikke fungerer. Men så senere, jeg fant ut at vi bare måtte slette det og gjøre binære søk. Så gjør det noe hvis det ikke fungerer? ANDI PENG: korte svaret er nei. Men siden vi er not-- PUBLIKUM: Men ingen er faktisk sjekker. ANDI PENG: Vi er aldri kommer til å se det. Men du sannsynligvis ønske å gjøre at søket fungerer. Fordi hvis din lineær søk fungerer ikke, så sjansene er din binære søket er ikke til å fungere så bra. Fordi du har lignende Logikken i begge. Og nei, det spiller egentlig ingen rolle. Så de eneste som vil slå i er liksom og binært søk. Yeah. Og også, mange av barna var prøver å kompilere helpers.c. Du er faktisk ikke tillatt å gjøre det, fordi helpers.c ikke har en hovedfunksjon. Og så du bør bare være faktisk kompilering generere og finne, fordi finne samtaler helpers.c og funksjonene i den. Så det gjør debugging en smerte i baken. Men det er det vi må gjøre. PUBLIKUM: Du bare gjøre alt, ikke sant? ANDI PENG: Du kan bare gjøre alt så vel, ja. OK. Så det er det i forhold til hva den PSet ber dere alle til å gjøre. Hvis du har spørsmål, føler fri til å spørre meg etter pkt. Jeg vil være her for, liker, 20 minutter. Og ja, de PSet s egentlig ikke så ille. Dere bør være OK. Disse, bare følg retningslinjer. Type har en følelse av, logisk, hva bør skje, og du blir fin. Ikke vær for redd. Det er mye kode allerede skrevet der. Ikke vær for redd hvis du ikke forstå hva alt dette betyr. Hvis det er mye, det er helt greit. Og kommer til kontortid. Vi hjelper deg å ta en titt. PUBLIKUM: Med den ekstra funksjoner, ser vi dem opp? ANDI PENG: Ja, de er i koden. I spillet 15, halvparten av det er allerede skrevet for deg. Så disse funksjonene er allerede i koden. Jepp. Greit. Vel, lykke til. Det er en motbydelig dag. Så forhåpentligvis dere ikke føler for dårlig om bor inne og koding.