SPEAKER 1: Hei alle sammen! Velkommen tilbake til del. Så glad for å se så mange av dere begge her, og alle som ser på nettet. Så, som vanlig velkommen tilbake. Jeg håper at dere alle har hatt en fin helg, full av ro, avslapning. Det var vakkert ut i går. Så, jeg håper du likte utendørs. Så først et par kunngjøringer. Gradering. Så, de fleste av dere burde ha fått en e-post fra meg om din Scratch PSet, samt for gradering PSet 1. Så, bare et par ting. Pass på å bruke check50 i style50. Disse er ment å være ressurser til dere, å sørge for at du får så mange poeng som du kan uten unødvendig å miste dem. Så, ting som stil er svært viktig. Vi kommer til å ta av for det. Noen av dere har kanskje allerede lagt merke til at fra PSet. Og check50 er bare en veldig enkel måte å sørge for at at vi faktisk tilbake hva må returneres til brukeren, og at alt er i brukbar stand. På den andre notatet, sørg for at laste opp ting til riktig mappe. Det gjør livet mitt bare en litt vanskeligere hvis du laster opp PSet 2 inn PSet 1 fordi når jeg laster ned ting, de ikke laste riktig. Og jeg vet det er litt wonky i et system for å venne seg til, men bare være super forsiktig, hvis bare for meg, slik at når du får e-post på som to A.M. og jeg er gradering. Hvis ikke føre jeg må se alle rundt for din PSet. Cool. Jeg vet det er tidlig, men jeg helt fikk tatt av vakt av et essay som er grunn denne fredagen, som mine professorer var bare liker, oh yeah. Husk, du har en essay grunn på fredag. Så, jeg vet ingen liker å tenke på midterms, men din første quiz er 15. oktober, som oktober starter denne uken. Så, kan det være raskere enn du forventet er alt. Slik at du ikke kastet av vakt når Jeg nevner neste ukes delen som oh, din quiz neste uke, tenkte jeg Jeg vil gi deg litt mer av en heads up nå. Så, problemet satt, nummer tre. Hvordan folk har lest spec ut av nysgjerrighet? OK. Vi fikk et par. Slags ned fra fjor uke, men det er OK. Jeg vet det var vakkert ut. Så Break Out. Definitivt etter at du får gjort i dag lese spec minst prøve som laster ned distribusjon kode og kjører som den første innledende ting som de ber deg om det. Fordi vi bruker distribusjon kode og bibliotek at vi har bare vært using-- --det er bare andre gang vi har gjort dette PSet, gale ting kan skje med apparatet, og du vil finne at ute nå versus senere. Fordi hvis det er torsdag kveld, eller det er Onsdag kveld og for noen grunn apparatet gjør bare ikke ønsker å kjøre med biblioteket eller med distribusjonen kode, at midler du kan ikke engang begynne å gjøre kodingen. Fordi du kan ikke sjekke for å se om det fungerer. Ikke skal kunne å se om det kompilerer. Du ønsker å ta vare på de som tidlig uken, når du fortsatt kan sende meg eller en av de andre TFS, og vi kan få de fikset. Fordi de er problemer som kommer til å stoppe deg fra å gjøre noen reell fremgang. Det er ikke som en bug, som du kan bare slags hoppe over. Hvis du har problemer med din apparatet eller distribusjon kode, du virkelig ønsker å få det tatt vare på før heller enn senere. Så selv om du ikke skal faktisk starte koding, laste ned distribusjon koden, leser spec, sørg alt fungerer der. OK? Hvis du kan bare gjøre det, jeg lover deres liv vil bli lettere. Og så er du sannsynligvis kommer å gjøre det akkurat nå ikke sant? OK. Så, noen spørsmål der? Eventuelle logistikk ting? Alle er bra? OK. Ansvar for de av deg på rommet og på nettet. Jeg kommer til å være å prøve å slå mellom PowerPoint i apparatet fordi vi kommer å være å gjøre noen koding i dag etter stor etterspørsel av den anonyme forslag meningsmåling jeg sendte ut i forrige uke. Så vil vi gjøre noen koding. Så, hvis dere også vil ha å fyre opp dine hvitevarer, og du skal ha fått en e-post fra meg, med en prøve-fil. Ta gjerne gjøre det. Så vi kommer til å snakke om GDB, som er en debugger. Det kommer til å hjelpe deg slags finne ut hvor ting går galt i koden. Det er egentlig bare en måte for deg å gå gjennom koden din så det skjer, og være i stand til å skrive ut variabler eller se hva som faktisk skjer under panseret vers programmet bare å kjøre, det er som forkastninger, og du er like, ingen anelse hva skjedde her. Jeg vet ikke hvilken linje det sviktet på. Jeg vet ikke hvor det gikk galt. Så, er GDB kommer til å hjelpe deg med det. Også, hvis du bestemmer deg for å fortsette ja, og ta 61, det vil virkelig, virkelig være din beste venn, fordi jeg kan fortelle deg fordi jeg går gjennom den klassen. Vi kommer til å se på binær søk, som hvis dere husker den store telefonboken eksempel opptog fra klassen. Vi kommer til å gjennomføre det, og vandre gjennom det litt mer, og så skal vi gjennom fire forskjellige slags, som er boble, Utvalg, Innsetting, og flett. Cool. Så, GDB som jeg nevnte, er en debugger. Og dette er slags stor ting, de store funksjoner eller kommandoer som du bruker i løpet av GDB, og jeg vil gå deg gjennom en demo av det i et sekund. Så, dette er ikke bare kommer til å bli abstrakt. Jeg skal prøve og gjøre det så konkret som mulig for dere. Så, bryte. Det vil enten være pause lignende, noe nummer, som representerer en linje i programmet, eller du kan navngi en funksjon. Så, hvis du sier bryte hoved, det vil stoppe på hoved, og la deg gå gjennom den funksjonen. Likeledes, hvis du har noen ekstern fungere som Swap eller Cube, som vi så på i forrige uke. Hvis du sier bryte en av dem, når programmet treffer det, det vil vente på deg til fortelle den hva du skal gjøre. Før det vil bare kjøre slik at du faktisk kunne gå innenfor funksjonen og se hva som skjer. Så, neste, hopper bare over neste linje, går over funksjoner. Trinn. Disse er alle litt abstrakt. Så, jeg bare kommer til å kjøre gjennom dem, men du vil se dem i bruk i en annen. Gå inn i en funksjon. Så som jeg sa, som med Swap, det ville tillate deg å faktisk som om du er som fysisk stepping inni, du kan rote med disse variablene, print ut hva de er, se hva som skjer. Listen vil bokstavelig talt bare skrive ut rundt koden. Så, hvis du slags glemmer hvor du er i programmet, eller kanskje du lurer hva som skjer rundt det, dette vil bare skrive ut et segment av liker fem eller seks linjer rundt det. Så kan du få orientert om hvor du er. Skriv ut noen variable. Så, hvis du har nøkkelen som i Cæsar, som vi skal se på. Du kan si Print Key på noe punkt. Det vil fortelle deg hva verdien er så det, kanskje et sted på veien, du overskrev din nøkkel. Du kan faktisk fortelle at fordi du kan faktisk observere at verdi. I lokalbefolkningen, bare utskrifter ut din lokale variabler. Så, når du er innenfor en løkke, og du bare ønsker å se ut som, oh. Hva er mitt jeg? Hva er dette nøkkelverdi at jeg initial her? Hva er budskapet på dette punktet? Det vil bare skrive ut alle av dem, slik at man trenger ikke å individuelt si, Print I. Skriv Message. Print Key. Og så Skjerm. Hva det gjør er som du gå gjennom programmet, det vil bare være sikker på at det er viser noen bestemt variabel på hvert punkt. Slik at du also-- --det er slag av en snarvei der du trenger ikke å holde det gående like, oh. Print Nøkkel eller Print I. Det bare vil automatisk gjøre det for deg. Så med det, vi skal for å se hvordan dette går. Jeg kommer til å prøve og bytte over til min apparatet. Se om jeg kan gjøre dette. Alle. Vi kommer bare til å speile det. Det er ingenting gale på min laptop anyways. OK. Dette må være denne. Det er så liten. La oss se om vi kan gjøre dette. OK. Alice er åpenbart sliter her bare en liten bit, men vi vil få det i en momento. OK. Vi er bare kommer til å øke dette. OK. Kan alle slags se det? Kanskje litt? Jeg vet det er litt for liten. Du kan ikke helt finne ut hvordan å gjøre dette større. Hvis noen vet. Er det noen som vet hvordan å gjøre det større? OK. Vi kommer til å rulle med den. Spiller ingen rolle anyways fordi det er bare det er koden som dere bør ha. Hva er mer viktig er terminalen her. Og vi har her Hvorfor er det så lite? Innstillinger. Oh. Sann Ike. Hvordan er dette? Ut av det. Er det bedre for alle? OK ,. Cool. Du vet når du er i en CS klasse tekniske problemer er slags del av the-- Så, la oss fjerne dette. OK. Så, her i seksjonen, som vi hadde her. Caesar er en kjørbar fil. Så jeg gjorde det. Så, er én ting å realisere med GDB at det fungerer bare på kjørbare filer. Så, kan du ikke kjøre den på en dotsy. Du må faktisk gjøre sikker på at koden kompilerer, og at det faktisk kan kjøres. Så, sørg for at hvis det ikke kompilere, få det til å kompilere, slik at du kan slags kjøre gjennom den. Så, for å starte GDB, alt du gjør, Gloria typen GDB, og så bare den -fil du vil. Jeg har alltid feilstaver Cæsar. Men du vil være sikker siden det er en kjørbar, TIS dot flash slik at betyr at du kommer å kjøre CSI du kommer til å kjøre dette filer enten med debugger. OK. Så du det, får du denne typen vrøvl. Det er bare alt om debugger. Du trenger egentlig ikke å bekymre deg for det akkurat nå. Og som du ser, har vi denne åpne parentesar, BNP, nære parentesar, og bare slags ser ut som vår kommandolinjen, ikke sant? Så, hva vi ønsker å do-- --So, Det første er vi ønsker å velge et sted å bryte den. Så, det er en bug i dette Caesar program at jeg presentere, at vi kommer til å finne ut. Det Hva det betyr er at det tar inngangs Barfoo i store bokstaver, og for noen grunn det endrer ikke A. Det etterlater bare det alene, alt annet er riktig, men den andre bokstaven En forblir uendret. Så vi kommer til å prøve og finne ut hvorfor det er. Så, det første du vanligvis ønsker å gjøre når du starter på GDB er å finne ut hvor du skal bryte den. Så Cæsar er en ganske kort program. Vi har bare én funksjon, ikke sant? Hva var vår funksjon i Cæsar? Det er bare én funksjon, Main sant? Hoved er en funksjon for alle programmene dine. Hvis du ikke har Main, kanskje jeg være litt bekymret akkurat nå, men jeg håper dere alle har hatt Hoved der inne. Så, hva vi kan gjøre er at vi kan bare bryte Main, bare sånn. Så sier det, OK. Vi setter vår stoppunkt der. Så, nå er det ting å huske Caesar tar en kommandolinje argument retten og vi har ikke gjort det noe sted ennå. Så, hva du gjør er når du faktisk går til å kjøre programmet, et program som du er kjører i GDB som trenger kommandolinje argumenter, du kommer til innspill når du først begynner å kjøre den. Så, i dette tilfelle, gjør vi Kjør med en nøkkel på tre. Og det vil faktisk begynne. Så, hvis du ser her, har vi Hvis RC ikke er lik 2. Så hvis dere har all den filen som jeg sendte ut opp vil du se at det er som det første linjen vår viktigste funksjon, ikke sant? Det er å sjekke for å se om vi har riktig antall argumenter. Så, hvis du lurer på hvis RC er riktig, du kan gjøre noe akkurat som Print RC. RC er to, som er hva vi forventet, ikke sant? Så kan vi gå neste, og fortsetter gjennom. Så har vi noen viktige der. Og vi kan skrive ut vår nøkkel å sørge for at det er riktig. Interessant. Ikke helt hva vi forventet. Så, en ting å realisere med GDB også, er at det er ikke før du faktisk treffer Neste, at linjen som du nettopp så faktisk er utført. Så, i dette tilfellet Key har ikke blitt tildelt ennå. Så, er Key noen søppel verdi som du ser på bunnen der. Negativ $ 120-- --det er en milliard og noe rare ting riktig? Det er ikke nøkkelen som vi forventet. Men hvis vi treffer på Neste, og da er vi prøv og trykk nøkkel, er det tre. Alle se det? Så, hvis du får noe at du er som, vent. Dette er helt galt, og jeg vet ikke hvordan dette ville skje fordi alt jeg ønsker å gjøre er å tilordne et tall, en variabel, prøv å treffe Deretter kan du prøve å skrive ut det igjen, og se om det fungerer. Fordi det er bare kommer til å utføre og faktisk tildele noe etter at du har rammet Neste. Fornuftig for alle? Uh huh? SPEAKER 2: Når du tilfeldig tall hva betyr det? SPEAKER 1: Det er bare tilfeldig. Det er bare søppel. Det er bare noe som din Datamaskinen vil tilfeldig tildele. Cool. Så, nå kan vi gå gjennom, og så nå har vi dette ren tekst GetString. Så, la meg bare presentere hva vil skje når vi treffer Neste her. Vår GDB slags forsvinner, ikke sant? Det er fordi GetString er nå å gjennomføre, ikke sant? Så, når vi så ren tekst lik GetString, åpne parentesar og parentesar, og vi slo Deretter har det faktisk henrettet nå. Så er det å vente på oss å legge inn noe. Så, skal vi innspill maten som er hva det er sviktende som jeg fortalte deg og som bare sier at det er ferdig utføring, at den lukkes brakett betyr at det er som kommer ut av denne sløyfe. Så kan vi treffer Neste, og nå som jeg er at du er alle kjent fra keiser, dette er, hva er denne linjen kommer til å gjøre. Det er for Int jeg er lik 0, er lik N Strlen, ren tekst, og deretter Jeg er mindre enn n, jeg, pluss, pluss. Hva er denne sløyfen kommer til å gjøre? Åpne meldingen. Cool. Så, la oss begynne å gjøre det. Så, bør denne tilstanden matche, for vår første? Hvis det er en B, det er ren tekst I. Vi kan få informasjon om våre lokalbefolkningen. Så, er jeg null, og hvis seks, som vi forventer, og vårt viktigste er tre. Alt som gir mening, ikke sant? Disse tallene er alle nøyaktig hva de skal være. Så, nynne? SPEAKER 3: Jeg har tilfeldige tall for meg. SPEAKER 1: Vel, vi kan check-- --vi kan prate om det i et sekund. Men du bør være å få dette. Så, hvis vi har en kapital B for vår første, denne tilstanden bør ta det, ikke sant? Så, hvis vi treffer Deretter ser vi at dette Dersom faktisk utfører. Fordi hvis du følger sammen i koden, denne linjen her, hvor ren tekst jeg er erstattet med denne aritmetikk, bare utfører dersom Dersom betingelsen er riktig rett? GDB er bare kommer til å vise deg ting som faktisk utfører. Så hvis dette Dersom tilstanden ikke ble oppfylt, er det bare kommer til å hoppe til neste linje. OK? Så har vi det. Denne braketten betyr at det er lukket ut av at sløyfen nå. Så det kommer til å starte på nytt. Bare sånn. Så, at vi kan få info om våre lokalbefolkningen her, og vi ser at vår første brev har endret seg, ikke sant? Det er nå en E, som det skal være. Så kan vi fortsette på. Og vi har denne sjekken. Og denne kontrollen skal fungere, ikke sant? Det er A. Det bør endres tre bokstaver fremover. Men hvis du legger merke til, vi få noe annet. Så i dette tilfellet her opp, det fanget den, og slik at denne linjen utført, som endret vår B. Men i dette tilfellet er her, vi har at det bare hoppet over den, og gikk til [? L SIFF. ?] Så noe skjer der. Hva som er å fortelle deg er at, vi vet at det skal fange her, men det er ikke. Kan noen se hva våre Problemet ligger i at linjen? Det er en veldig liten ting. Og du kan også se på koden din. Det er også line-- glemme hvilken linje det er i det-- men det er i [uhørbart]. Ja? SPEAKER 4: Det er på større enn siden hvis du leser det i boken. SPEAKER 1: Nettopp. Så, debugger kunne ikke fortelle du det, men debugger kan få deg ned til en linje som du vet ikke fungerer. Og noen ganger, når spesielt senere i semesteret, da du arbeider med hundre, en hundre få linjer med kode, og du vet ikke hvor det er sviktende, dette er en fin måte å gjøre det. Så, har vi funnet vår bug. Du kan fikse det i filen, og deretter kan du kjøre den på nytt, og alt skulle fungere perfekt. Og den største tingen er Dette kan virke som, OK. Yeah. Cool. Du visste det du leter etter. Så, visste du hva du skal gjøre. GDB kan være super nyttig fordi du kan skrive ut alle disse tingene som du ville ikke. Det er mye mer nyttig enn printf. Hvor mange av dere bruker som printf uttalelser å finne ut hvor en bug var, ikke sant? Så, med dette, gjør du ikke nødt til å holde tilbake, og liker kommenterer i Printf, eller kommentere ut, og finne ut hva du skal skrive ut. Dette faktisk bare lar deg bla gjennom, skrive ut ting som du kommer gjennom, så kan du observere hvordan de endrer i sanntid, som programmet kjører. Og det tar litt bit av å bli vant til. Jeg vil sterkt anbefale bare slags for å være litt frustrert med det for akkurat nå. Hvis du tilbringer en time over neste uke lære å bruke GDB, du vil spare deg selv så mye tid senere. Og bokstavelig talt. vi forteller dette til folk hvert år, og jeg husker da jeg tok klasse, var jeg liker, jeg vil bli bra. Nei. PSet 6 kom på, og jeg var liker, jeg skal lære hvordan du bruker GDB fordi jeg ikke vet hva som skjer her. Så hvis du tar deg tid så bruke den på mindre programmer at du kommer til å være jobber på, liker å jobbe gjennom noe sånt Visionäre, som dette. Eller hvis du vil ha ekstra praksis, er jeg sikker Jeg kunne komme opp med buggy programmer, for deg å feilsøke hvis du ønsker. Men hvis du bare tar litt tid å komme vant til det, bare spille rundt med den, det vil virkelig tjene deg godt. Og det er virkelig en av de tingene som du bare må prøve og få hendene skitne med, før du virkelig forstår det. Jeg egentlig bare forstått det en gang Jeg måtte feilsøke ting med det, og det er mye hyggeligere å ha en idé om hvordan å feilsøke før heller enn senere. OK. Cool. Jeg vet det er litt som et lynkurs i GDB, og jeg vil definitivt jobbe med å få disse for å se større neste gang. Cool. Så, hvis vi går tilbake til vår PowerPoint. Dette kommer til å fungere? Awh. Ja. OK. Så, hvis du skulle trenge noen av de igjen, det er på listen. Så Binary Search, som alle husker den store opptog av David ripping telefonkataloger i to. Jeg vet egentlig ikke får telefonen bøker lenger, fordi som der gjør du få telefonen bøker i disse dager? Jeg vet virkelig ikke. The Binary Search. Er det noen som husker hvordan Binary Search fungerer? Noen i det hele tatt? Yeah? SPEAKER 5: Du vet når du ser på hvilken halvdel det ville være i, Basert på det, og bli kvitt den andre halvparten. SPEAKER en Nettopp. Så, Binary Search, er det slags a-- --Vi liker å kalle det splitt og hersk. Så, hva du skal gjøre er du vil se i midten, og du vil se om det samsvarer det du leter etter. Og hvis det ikke skjer, så du prøver å finne ut, det kommer til å stå halvparten eller høyre halvdel. Så, dette kan være hvis du leter på noe som er alfabetisert, du ser, oh. Betyr Allison kommer før M? Ja. Så, skal vi se på den første halvdelen. Eller det kan være som med tall. Alt som du kan null, kan det bli sortert. Du kan bruke binære søk på. Så, noen som husker dette graf eller hva dette er? Det er Asymptotisk Complexity. Så, denne grafen bare beskriver hvor lang tid det tar deg til å løse et problem som du øke antall ting som du bruker. Så har vi N, som er lineær tid. Hvis N over to, som er litt bedre, vokser fortsatt super rask. Og da har vi Logg inn, noe som er det vi anser Binary Search. Hvis vi legger merke til, så problemet ditt blir mye og mye større, den tiden det tar deg å løse det egentlig ikke øke så mye. Det er som sammenlign her i begynnelsen. Du er som, OK. Noe her gjør virkelig ikke Uansett hvilken vi bruker, men du får ut til en million, en milliard. Du prøver å finne some-- --you're prøver å finne en nål i en høystakk. Jeg tror du vil ha dette problemet. Du ønsker denne kompleksiteten, ikke lineær fordi for alt du kjenner din skal være å søke gjennom hver enkelt nål, ting av høy, prøver å lete etter nålen. Og det er ikke så gøy etter min mening. Jeg liker rask. Jeg liker effektiv. Og så hardtarbeidende studenter deg gutta er, vet du jobbe smartere, ikke hardere type ting, hvordan du kan gjøre opp disse algoritmene. Så vi kommer til å gå gjennom bare en rask eksempel. Jeg tror dere bør ha en hånd på Binary Search, men i tilfelle noen er litt fuzzy, ønsker å forsterke det, vi skal bare gå gjennom et eksempel her. Så vi leter etter hvis matrisen inneholder syv. Så, er det første vi gjør ser i midten, ikke sant? Og også du kommer til å bli koding Binary Søk på bare et sekund. Så det kommer til å bli gøy. Så vi ser i midterste små arrays tre. Har tre lik 7? Ikke. Det er seks. Så, er det mindre enn eller større enn syv? Mindre enn. Ja. Nice jobb folkens. Jeg føler jeg at jeg burde ha godteri fordi jeg ønsker å kaste den ut i verftene. Det er hva jeg skal gjøre neste uke. Det vil holde dere skarpe. Så kaster vi bort at første halvår, ikke sant? det var mindre enn. vi vet at alt på den venstre side kommer til å være mindre enn hva vi faktisk leter etter. Så det er ingen grunn til å ta hensyn til det. Bare glem det. Så nå ser vi på vår høyre side, og vi ser på midten der borte, og nå er det ni. Så, 9 er-- --Everyone? Større enn hva vi er på jakt etter, ikke sant? Så vi kommer til å kaste bort alt til høyre. Sånn. Nå er alt vi igjen med er en. Så vi sjekke, er dette en hva vi leter etter? det er. Vi fant det vi ønsket. Så vi er ferdige. Bilinear søk. Og hvis du legger merke til, vi hadde sju innganger der. Det tok oss bare som tre ganger, men hvis du gjør som en milliard, dere vet hvor mange skritt det ville ta hvis vi hadde for fire milliarder ting? Eventuelle gjetninger? Det er 32. 32 skritt for å finne noe i en fire milliarder elementsatsen på grunn av krefter to. Så to er til 32, er til fire milliarder kroner. Så ganske sprøtt hvordan du er fortsatt innenfor som et relativt lite antall skritt å finne noe i fire milliarder elementer. Så på dette notatet, er vi kommer til å kode dette så dere kan faktisk slags se hvordan dette fungerer. All right, så dere kan kode. Jeg kommer til å fortelle dere snakke litt. Bli kjent med folk rundt deg, som er hva noen ønsket fra forrige avsnitt. Så bli kjent med menneskene rundt deg. Snakk for en liten bit. Og alt jeg ønsker fra deg Gutta er akkurat nå bare prøve å lage en skisse av pseudokode. OK? Whoa. Alt jeg ønsker fra dere er at du er bare kommer til å fylle ut dette mens saken. Så jeg har satt disse øvre og nedre grenser som representerer begynnelsen og slutten av matrisen. Og du kommer til å faktisk sløyfe gjennom og finne ut hva vi gjør innenfor dette mens loop. Så hvis du kan finne out-- jeg har et hint det-- hva er de tilfeller som vi har her? Så hvis du ønsker å finne ut av tilfeller vil vi pseudo de og så får vi faktisk kode dem. Og det kommer til å være, jeg tror, ​​forhåpentligvis det vil være litt enklere enn du forventer. Fordi det er ikke så mye kode, faktisk, som er virkelig kult. Mm-hm? STUDENT: [uhørbart]? INSTRUKTØR: Ja. Det var noe å finne i midten. STUDENT: Så vi kan bruke det. OK. INSTRUKTØR: Perfect. Så det er det første vi må gjøre. Så finn midten. Stor. Så har du en idé om hvordan vi kan faktisk finne midten med koden? STUDENT: Yeah. n enn 2? INSTRUKTØR: Så n på over 2. Så én ting å huske er at øvre og nedre grenser endres. Vi holder constricting delen av tabellen vi er ute etter å. Så n løpet av to vil bare fungere for det første vi gjør. Så tar øvre og nedre hensyn, hvordan kan vi få den midterste element? Fordi vi ønsker midten mellom store og små, ikke sant? Mm-hm? STUDENT: [uhørbart]. INSTRUKTØR: Så vi har noen midten. Og det vil være øvre pluss lavere over to. Awesome. Det vi går. En linje ned. Dere er på vei. Så nå som vi har vår midten, hva vi ønsker å gjøre? Bare generelt. Du trenger ikke å kode det. Ja. STUDENT: [uhørbart]? INSTRUKTØR: Så det er pluss fordi du er finne gjennomsnittet mellom de to av dem. Så hvis du tenker på dem som slag for å øke inn fra sidene, tenker på det som du nærmer deg midten, vil du liker det. Så hvis du var på hver side av midten, og vi har som 5 og 7. Når du legger dem sammen du får 12, deler du med 2, er 6. Noen ganger er det vanskelig å forklare hvorfor det fungerer, men hvis du jobber gjennom et eksempel noen ganger, det vil hjelpe deg å finne ut om det bør være pluss eller minus. Ja. STUDENT: [uhørbart] nøyaktig i midten hvis de hadde en sak der det er mye mindre tall og som en stort antall? INSTRUKTØR: Så alt du trenger er den midterste av rekken. Så hvis du hadde en haug med små tall og deretter en virkelig stort antall på slutten, spiller det ingen rolle. Alt som teller er at de er sortert, du bare ønsker å se på midten av matrisen fordi du er fortsatt slicing problemet i to. Cool. Så nå som vi har midten, hva skal vi gjøre nå? STUDENT: sammenligne. INSTRUKTØR: Den sammenligne. Så sammenligne midten value_wanted. Cool. Så du ser her oppe har vi denne verdien vi ønsker her oppe. Husk dette er en matrise. Så midt refererer til indeksen. Så vi ønsker å gjøre verdier av midten. Ikke glem om du vil å sammenligne, dobbel likeverdige. Du gjør enkelt lik du er bare kommer til å overføre den, og da, selvfølgelig, det er kommer til å være den verdien du vil. Så ikke gjør det. Så vi kommer til å se om verdiene ved midten er lik verdien vi ønsker. Ikke glem tannregulering. Dropbox bør gå unna. Så hva skal vi gjøre i dette tilfellet? Hvis det er hva vi ønsker å komme tilbake? Vi prøver å si. STUDENT: Print av. INSTRUKTØR: Vel, vi ikke ønsker å skrive ut. Så dette er en bool her, så vi ønsker å returnere sant eller usant. Vi sier, er dette nummeret en [? RRA? ?] Så hvis det er, vi bare returnere det sant. Hvis jeg kan stave sant. STUDENT: Hvorfor ville du ikke returnere null? INSTRUKTØR: Så du kunne returnere null hvis du ville. Men i dette tilfellet fordi vår funksjon returnerer en bool, vi trenger å returnere enten sant eller usant. STUDENT: Når du er sier boolsk uttrykk, kan du sette den lik falsk? Som hvis jeg ønsker å si, hvis denne tilstanden ikke er oppfylt, som er øvre lik falsk. Vil det å forstå hvis du bare sette falsk på den andre siden? INSTRUKTØR: Yeah. Så egentlig hvis du er noen gang å gjøre noe som er øvre eller er lavere, som returnerer sant eller usant og det er faktisk dårlig stil til si lik lik sant eller equals lik falsk. Du ønsker å bruke dette resultatet så seg selv som sjekken. Ikke hva jeg ønsket. Det var det jeg ønsket. Så i tilfelle du spør om noe sånt lagre dette i c. Så hvis vi har int main (void) og noe sånt som dette. Og du har hvis er øvre av noen innspill, og du er spør om du kan gjøre noe sånt som dette? Høyre? STUDENT: Jeg prøvde å gjøre det [uhørbart]. Fordi hvis it's-- INSTRUKTØR: Høyre. Så du vil at dette skal være falske, ikke sant? STUDENT: Yeah. INSTRUKTØR: Så i dette tilfellet deg vil den skal kjøre hvis det ikke er sant. Så kule ting du gjør det er dette. Så husk utrops punkt benekter ting? Det står [uhørbart] betyr ikke. Så hvis vi ser på bare denne delen her, ville du si at evalueres til falsk som du vil ha det til. Ikke falske er sant som betyr dette ville utføre. Betyr det fornuftig? STUDENT: Yeah. INSTRUKTØR: Awesome. OK. Så vi kunne bare gå tilbake sant i dette tilfellet. Så nå har vi to andre tilfeller i dette tilfellet. Hva er våre to andre saker? La oss bare gjøre det på denne måten. Så la oss starte med annet hvis verdier ved midten er mindre enn verdien vi ønsker. Så vår verdi i midten er mindre enn verdien som vi leter etter. Så hvilke bundet gjør du tror vi vil oppdatere? Øvre eller nedre? Øvre? Så hvilken side av matrisen skal vi se på? STUDENT: Den nedre. INSTRUKTØR: Vi skal vi å være ute på venstre. Så annet hvis liten verdi er mindre. Så din midterste verdien her er mindre enn det vi ønsker. Så vi ønsker å ta høyre side av vår array. Så vi kommer til å oppdatere vår nedre grense. Så vi vil tildele våre lavere. Og hva tror du lavere bør være? STUDENT: Den midterste verdien? INSTRUKTØR: Så midt value-- STUDENT: Pluss en. INSTRUKTØR: --plus en. Kan noen fortelle meg hvorfor har vi at pluss 1? STUDENT: [? Ingen verdi?] er mer lik det. INSTRUKTØR: Høyre. Fordi vi allerede vet at vår midterste verdien er ikke lik det, og vi ønsker å utelukke det fra alle senere søk. Hvis du glemmer at pluss 1, dette vil gjerne sløyfe på ubestemt tid. Og du vil bare bli fanget i en uendelig løkke, og da vil du segfault og ting går dårlig. Så alltid sørge for at du ikke er inkludert verdien som du bare sett på. Så vi tar vare på det med en pluss en. Så nå har vi vår siste vilkåret som jeg alltid for sikkerhets skyld du kan sjekke her, annet hvis verdien på midten er større enn verdien vi ønsker. Det betyr at vi ønsker den venstre halvdel. Så hvilken skal vi oppdatere? Øvre. Og hva er dette som kommer til å like? Middle minus en grunn, selvfølgelig, vi ønsker å sørge for at vi ikke er ser på det midterste verdien på nytt. Og så har vi det. Det var det. Det er alt binære søk er. Det er ikke så ille, ikke sant? Det er som 10 linjer kode med hvite felt. Så veldig kraftig, veldig nyttig, vil du være å bruke det i en av dine senere psets. Kanskje ikke denne, men senere. Så lære det. Elsker det. Det vil behandle deg godt. Så er det noen som har noen spørsmål om binære søk? Ja. STUDENT: Spiller det noen rolle om din n er partall eller oddetall? INSTRUKTØR: Nei. Fordi vi kastet den til midten som en int, vil det bare avkorter det. Så det vil bli et heltall og det vil slutt sortere gjennom alt. Så du trenger ikke å bekymre deg for det. Alle gode? Awesome. Cool. Så, fikk dere dette. Lysbildefremvisning. Så som vi snakket om, jeg vet David nevnte kompleksitet runtimes. Så i beste fall, det er bare en, som vi kaller konstant tid. Kan noen fortelle meg hvorfor det kan være? Hvilken type scenario ville det innebære? Mm-hm. STUDENT: [uhørbart] first-- INSTRUKTØR: Så midten blir første elementet som vi kommer til, ikke sant? Slik at enten en oppstilling av ett eller uansett hva vi leter etter akkurat skjer for å være smellkyss dab i midten. Så det er vårt beste fall. Du kommer inn i reelle problemer, sannsynligvis ikke kommer til å nå [uhørbart] som ofte. Hva om vår verste fall? Vår verste fall er log n. Og det har å gjøre med hele krefter på to ting som jeg snakket om. Så i verste fall ville det bety at vi måtte hogge array ned inntil det var et element av en. Så vi måtte hogge det ned i halvparten så mange ganger som vi muligens kunne. Det er derfor det er log n fordi du bare holde dividere med to. Så forutsetninger, ting dere trenger å vite hvis du noen gang kommer til å bruke et binært søk. Dine elementene skal sorteres. De må sorteres fordi det er den eneste måten du kan vite om du er i stand å kaste ut halvparten av det. Hvis du hadde denne jumbled bag av tall og du sier, OK, jeg kommer til å sjekke midten tall og antall jeg leter etter er mindre enn det, jeg bare går å vilkårlig kaste ut den ene halvdelen. Du ville ikke vite om din Tallene i den annen halvdel. Din liste som skal sorteres. I tillegg, kan dette være går videre litt, men du må ha random access. Du må være i stand til å bare gå til det midterste element. Hvis du har å traversere gjennom noe eller det tar deg ekstra trinn å komme til det midterste element, det er ikke log n lenger fordi du legger mer arbeid i det. Og dette vil gjøre litt mer fornuftig i to uker, men jeg bare slags ønsket å forord, gi dere en idé om hva som er å komme. Men de er de to viktige forutsetninger at du trenger for en binær liste. Sørg for at det er sortert. Det er den store en for dere akkurat nå. Og på at vi kan gå inn resten av våre former. Så fire sorts-- boble, innsetting, utvelgelse, og flette. De er alle slags kule. Hvis dere velger å ta CS 124, du vil lære om alle slags former. Og hvis du er en XKCD fan, det er en veldig kul tegneserie om som virkelig ineffektive slag, som jeg anbefaler deg å gå å se på. En av dem er som panikk slag, som er like, oh no, tilbake tilfeldig utvalg. Shutdown system. Forlate. Så nerdete humor er alltid bra. Så er det noen som husker slag av som bare en generell idé av hvordan boble slags fungerer. Husker du? STUDENT: Yeah. INSTRUKTØR: Gå for det. STUDENT: Så du kommer gjennom og hvis det er større, så du bytte de to. INSTRUKTØR: Mm-hm. Nettopp. Så du bare iterere gjennom. Du sjekker to tall. Dersom en før er større enn den etterpå, du bare bytte dem slik at i denne måten alle de høyere tall boble opp mot slutten av listen og alle lavere tall boble ned. Har han vise dere den kule lydeffekt sortering video? Det er litt kult. Så som Robert sa, algoritmen at du bare gå gjennom listen, bytte tilstøtende verdier hvis de ikke er i orden. Og så bare terpe til du ikke gjør noen bytteavtaler. Så ikke dårlig, ikke sant? Så vi har bare en rask eksempel her. Så dette kommer til å sortere dem i stigende rekkefølge. Så når vi går gjennom det første tid, ser vi gjennom åtte og seks er åpenbart ikke i orden, bytte vi dem. Så se på den neste. Åtte og fire ikke i orden. Bytte dem. Og da åtte og to, bytte dem. Det vi går. Så etter din første pass, du vet at din største antall kommer til å være hele veien på toppen fordi det er bare kommer til å være konstant større enn alt annet og det er bare kommer til å boble opp hele veien til enden der. Betyr det er fornuftig for alle? Cool. Så da vi ser på vår andre pass. Seks og fire, bryter. Seks og to, bryter. Og nå har vi noen få ting i orden. Så for hver pass som vi gjør gjennom hele vår liste, vi vet at sånn mange tall på slutten vil ha blitt sortert. Så vi gjør en tredje pass, som er en swap. Og så på vår fjerde pass, vi har null spor. Og så vet vi at vår matrise er blitt sortert. Og det er den store ting med boble slag. Vi vet at når vi har null bytteavtaler, som betyr at alt er i fullstendig orden. Det er slags hvordan vi sjekke. Så skal vi også å kode boble sorter som også er ikke så ille. Ingen av disse er så ille. Jeg vet at de kan virke litt skremmende. Jeg vet når jeg tok klassen, selv når jeg underviste klassen for første gang i fjor, Jeg var ut, hvordan gjør jeg dette? Det er fornuftig i teorien, men hvordan gjør vi faktisk gjøre dette? Det er derfor jeg ønsker også å gå gjennom koden med dere her. Så jeg har en pseudokode for dere denne gangen. Så bare ha dette i bakhodet når vi er i ferd med å overgang over. Så vi har noen teller som holder orden på våre bytteavtaler, fordi vi må sørge for at vi sjekker det. Og vi iterere hele matrisen som vi nettopp gjorde med dette eksempelet. Hvis elementet er større enn før elementet etter hvor vi er, vi bytte dem, og vi øke vår teller fordi så snart vi bytte, vi ønsker å la vår teller vet det. Eventuelle spørsmål der ute? Noe virker morsomt her borte. STUDENT: du setter Må telleren til null hver gang du går gjennom løkken? Tror ikke du holde det gående tilbake til null hver gang? INSTRUKTØR: Ikke nødvendigvis. Så hva skjer er at vi går gjennom her. Så gjør stund, husk, dette vil kjøre en gang uten å lykkes. Så det kommer til å sette telleren er lik null, så det kommer til å iterere gjennom. Som det gjentas gjennom, det vil oppdatere telleren. Som den oppdaterer teller, når det er gjort, når den er kommet til slutten av tabellen, hvis vår liste ikke er sortert, telleren vil ha blitt oppdatert. Så da er det kontrollerer tilstanden og det sier, OK, er telleren større enn null. Hvis det er, gjør det igjen. Du ønsker å tilbakestille slik at når du går gjennom, er telleren er lik null. Hvis du går gjennom en sortert array, endrer ingenting, dette mislykkes, og du returnere sortert liste. Betyr det fornuftig? STUDENT: Det er kanskje i en liten bit. INSTRUKTØR: OK. Hvis det er noen andre spørsmål som kommer opp. Ja. STUDENT: Hva ville funksjonen være for å bytte elementene? INSTRUKTØR: Så vi kan faktisk skrive at hvis vi kommer til akkurat nå. Cool. Så på dette notatet, er Alison kommer å bytte tilbake til apparatet. Det kommer til å bli gøy. Og vi har våre fint boble slags ting her. Så jeg allerede gjorde sykling gjennom matrisen. Vi har våre bytteavtaler som er lik null. Så vi ønsker å bytte tilstøtende elementer hvis de er ute av drift. Så det første vi må gjør er iterere gjennom vårt utvalg. Så hvordan tror du vi kan iterere gjennom vårt utvalg? Vi har for og jeg er lik 0. Vi ønsker jeg å være mindre enn n minus 1 minus k. Og jeg skal forklare det i et sekund. Så dette er en optimalisering her hvor, husker hvordan jeg sa etter hvert pass gjennom rekke vi vet at uansett hva som er on-- Så etter en pasning vi vet at dette er sortert. Etter to passerer vi vet at alt dette er sortert. Etter tre passerer vi vet det er sortert. Så måten jeg itera gjennom rekke her, er det å sørge for å bare gå gjennom det vi vet er usortert. OK? Det er bare en optimalisering. Du kan skrive det naivt bare itera gjennom alt, det ville bare ta lengre tid. Med denne fire sløyfe er det bare en fin optimalisering fordi vi vet at etter hver hele iterasjon gjennom rekke her, som hver hele sløyfe her, vi vet at ett eller flere av disse elementene blir sortert ved enden. Så vi ikke trenger å bekymre deg om dem. Betyr det er fornuftig for alle? Den kule lille trikset? Så i så fall, hvis vi gjentar gjennom, vi vet at vi ønsker å sjekke om matrise n og n + 1 er i orden. OK. Så her er pseudokode. Vi ønsker å sjekke om matrise n og n pluss en er i orden. Så hva kan vi ha det? Det kommer til å være noen betinget. Det vil være en if. STUDENT: Hvis matrise n er mindre enn matrise n pluss 1. INSTRUKTØR: Mm-hm. Vel, mindre enn eller større enn. STUDENT: Større enn. Så vi ønsker å bytte dem. Nettopp. Så nå får vi inn hva som er den mekanisme for å bytte dem? Så vi gikk gjennom dette kort, en type swap-funksjonen i forrige uke. Er det noen som husker hvordan det fungerte? Så vi kan ikke bare overføre dem, ikke sant? Fordi en av dem vil gå tapt. Hvis vi nevnte A er lik B og deretter B er lik A, alle en plutselig begge er bare lik B. Så det vi trenger å gjøre er vi har en midlertidig variabel som er kommer til å holde en av våre mens vi er i ferd med å bytte. Så det vi har er vi vil ha noen int temp er lik to-- du kan tilordne den til hvilken du vil ha, bare Sørg for å holde styr på it-- så i dette tilfellet, kommer jeg til å tilordne den til matrise n pluss 1. Så det kommer til å holde uansett verdien er i den andre blokken at vi ser på. Og da kan vi gjøre er at vi kan gå videre og Ny tilordning matrise n pluss 1, fordi vi vet at vi har denne verdien lagret. Dette er også en av de store things-- Jeg vet ikke om noen av dere hadde problemer der hvis du slår to linjer med kode plutselig ting fungerte. Rekkefølgen er svært viktig i CS. Så sørg for at du diagram ting ut hvis mulig med hensyn til hva som faktisk skjer. Så nå skal vi tilordne matrise n pluss 1, fordi vi vet at vi har denne verdien lagret. Og vi kan tildele det til matrise n eller i dette tilfellet i matrisen. For mange variabler. OK. Så nå har vi overført matrise i pluss en til lik hva som er i matrisen i. Og nå kan vi gå tilbake og tildele utvalg i til hva? Anyone? STUDENT: 10. INSTRUKTØR: 10. Nettopp. Og en siste ting. Hvis vi har byttet den nå, hva trenger vi å gjøre? Hva er den ene tingen som kommer til å fortelle oss hvis vi noen gang avslutte dette programmet? Hva forteller oss at vi ha en sortert liste? Hvis vi ikke utfører noen bytteavtaler, ikke sant? Hvis swaps er lik null ved slutten av denne. Så når du utfører en swap, som vi nettopp gjorde her, vi ønsker å oppdatere bytteavtaler. Og jeg vet at det var en spørsmålet tidligere om kan du bruke null eller ett i stedet av sant eller usant. Og det er hva dette gjør her. Så dette sier om ikke bytteavtaler. Så hvis swaps er null, som er-- jeg alltid få mine sannheter og mine misoppfatter blandet sammen. Vi ønsker oss å evaluere til sann, og det er det ikke. Så hvis det er null, så er det usant. Hvis du benekter det med en [? bang?] blir det sant. Så da denne linjen utfører. Sannheter og falske og nuller og enere bli gal. Bare hvis du sakte gå gjennom det vil det være fornuftig. Men det er hva denne lille bit av koden her gjør. Så dette sjekker for å se har vi gjort noen bytteavtaler. Så hvis det er noe i tillegg null, kommer det til å være falsk og det hele er kommer til å kjøre igjen. Cool? STUDENT: Hva gjør pause? INSTRUKTØR: bryte bare bryter deg ut av loopen. Så i dette tilfellet ville det akkurat som avslutter programmet og du ville bare har din sortert liste. STUDENT: Amazing. INSTRUKTØR: Jeg beklager? STUDENT: Fordi vi tidligere brukt skrevet 1 over skrevet null å presentere at hvis som vil fungere eller ikke. INSTRUKTØR: Yeah. Så du kan returnere null eller 1. I dette tilfellet, fordi vi er faktisk ikke gjør noe med funksjonen, vi ønsker bare det å bryte. Vi har egentlig ikke bryr seg om det. Bremsen er også bra hvis det er brukt for å bryte ut av fire sløyfer eller tilstander som trenger du ikke ønsker å beholde utføring. Det tar deg bare ut av dem. Det er litt av en nyanse ting. Jeg føler at det er mye hand waving, som du vil lære om dette snart. Men du vil lære mer om dette snart. Jeg lover. OK. Så gjør alle får boble liksom? Ikke så ille. Iterere gjennom, bytte ting ved hjelp av en temp variabel, og vi er alle satt der? Cool. Awesome. OK. Tilbake til PowerPoint. Eventuelle spørsmål generelt om disse så langt? Cool. Mm-hm. STUDENT: [uhørbart] int main vanligvis. Må du ha det for dette? INSTRUKTØR: Så vi var bare ute bare på selve sorteringsalgoritmen. Hvis du hadde det i løpet av som et større program, du ville ha en int main et sted. Avhengig av hvor du bruker denne algoritmen, det ville bestemme hva som er blir returnert av den. Men for vår sak, vi er strengt å se på hvordan dette faktisk iterere gjennom en matrise. Så vi trenger ikke bekymre deg om det. Så vi snakket om best case og worst case scenarier for binære søk. Så det er også viktig å gjøre at for hver av våre former. Så hva tror du er den verste case runtime boble liksom? Husker dere? STUDENT: N minus 1. INSTRUKTØR: N minus 1. Så det betyr at det er n minus 1 sammenligninger. Så en ting å innse er at på den første iterasjon, vi går gjennom, sammenligner vi disse two-- så det er en. Disse to, tre, fire. Så etter en iterasjon vi allerede har fire sammenligninger. Når jeg snakker om runtime og n. N representerer antallet sammenligninger som en funksjon av hvor mange elementer vi har. OK? Så vi går gjennom, har vi fire. Neste gang du vet at vi ikke gjør det nødt til å ta vare på dette. Vi sammenligner disse to, disse to, disse to, og hvis vi ikke har den optimalisering med de fire loop som jeg skrev, du ville være å sammenligne her anyways. Så du ville ha til å kjøres gjennom matrisen og gjøre n sammenligninger n ganger, fordi hver gang vi kjøre gjennom det vi liksom en ting. Og hver gang vi kjører gjennom rekken, gjør vi n sammenligninger. Så vår runtime for dette er faktisk n squared, som er mye verre i vår logge slutten fordi at betyr at hvis vi hadde fire milliarder elementer, er det kommer til å ta oss fire milliarder squared i stedet for 32. Så ikke den beste runtime, men for noen ting, du vet, hvis du er innenfor et visst utvalg av elementer boble slags kan være greit å bruke. OK. Så nå hva som er den beste fall runtime? STUDENT: Zero? Eller 1? INSTRUKTØR: Så en ville være en sammenligning. Høyre. STUDENT: N minus 1? INSTRUKTØR: Så, ja. Så n minus 1. Når du har et konsept som n minus 1, har vi en tendens til å bare slippe den av og vi bare si n fordi du har å sammenligne hver av these-- hvert par. Derfor ville det være n minus en, som vi Vi ville bare si er omtrent n. Når du arbeider med runtime, alt er i tilnærmet. Så lenge eksponenten er riktig, er du ganske bra. Det er hvordan vi forholder oss til det. Slik at den beste fall er n, som betyr at listen er allerede sorteres, og alt vi gjør er å kjøre gjennom og sjekk at det er sortert. Cool. OK. Så som du ser her, vi bare ha noen flere grafer. Så n squared. Fun. Mye verre enn n som vi ser, og mye, mye verre enn log 2n. Og da får du også inn logg logger. Og du tar 124, få deg inn som log stjernen, som er like crazy. Så hvis du er interessert, lookup log stjerne. Det er litt moro. Så har vi dette flotte diagrammet. Bare en heads up, dette er en fantastisk diagrammet for å ha for mid-term fordi vi lang tid å spørre deg disse tynner. Så bare en heads up, har dette på din mid-term på fin jukselapp der. Så vi bare så på boble slag. Verste tilfelle, n kvadrert, beste fall, n. Og vi kommer til å se på de andre. Og som du kan se, den eneste en som virkelig gjør det bra er merge sort, som vi skal komme inn på hvorfor. Så vi kommer til å gå til neste her-- utvalg slag. Er det noen som husker hvordan utvalget slags jobbet? Gå for det. STUDENT: I ​​utgangspunktet gå gjennom en ordre og opprette en ny liste. Og akkurat som du setter elementer inn, sette dem på rett sted i den nye liste. INSTRUKTØR: Slik at lydene mer som innsetting slag. Men du er veldig nære. De er svært like. Selv jeg får dem blandet opp noen ganger. Før denne delen jeg var som, vent. OK. Så hva du vil gjøre er utvalget sortere, måten du kan tenke om det og hvordan Jeg sørge for at jeg prøver ikke å få dem blandet opp, er den går gjennom og det velges minste tallet og det setter at i begynnelsen av listen. Den bytter den med det første spot. De har faktisk et forbilde for meg. Awesome. Så bare en måte å tenke på it-- utvalg sortere, velge den minste verdien. Og vi kommer til å kjøres gjennom et eksempel som jeg tror vil hjelpe fordi Jeg tror visuelle alltid hjelpe. Så vi starter ut med noe som er helt usortert. Red vil være usortert, green vil bli sortert. Det vil alle være fornuftig i et sekund. Så vi går gjennom, og vi iterere fra begynnelsen til slutten. Og vi sier, OK, er to vår minste tallet. Så vi kommer til å ta to og vi kommer å flytte den til forsiden av vår matrise fordi det er den minste tallet vi har. Så det er hva dette gjør her. Det er bare kommer til å bytte de to. Så nå har vi en sortert del og en usortert del. Og hva som er bra å huske om valg liksom er vi bare velge fra usortert del. Den sorterte delen du bare la alene. Mm-hm? STUDENT: Hvordan vet den hva er den minste uten å sammenligne det til alle andre verdier i matrisen. INSTRUKTØR: Det gjør sammenligne det. Vi liker hoppet over det. Dette er bare generell overordnet. Yeah. Når vi skriver inn koden jeg er sikker på at du vil være mer fornøyd. Men du lagrer denne første element som den minste. Du sammenligne og du si, OK, er det mindre? Ja. Beholde den. Her er det mindre? Nei? Dette er din minste, overføre den til din verdi. Og du vil bli mye lykkeligere når vi går gjennom koden. Så vi går gjennom, vi bytte det, så da vi ser på dette usortert del. Så vi kommer til å velge tre. Vi kommer til å sette den på ved slutten av sorterte parti. Og vi bare kommer til å fortsette å gjøre det, gjør det, og gjør det. Så dette er vår form for pseudo her. Vi vil kode det opp her i et sekund. Men bare noe å gå gjennom på et høyt nivå. Du kommer til å gå fra Jeg er lik 0 til n minus 2. Det er en annen optimalisering. Ikke bekymre deg for mye om det. Så som du sa. Som Jakob sa, hvordan gjør vi holde oversikt over hva vår minimum er? Hvordan vet vi det? Vi må sammenligne alt i vår liste. Så minimum lik i. Det er bare å si i dette tilfellet indeksen av minimumsverdien. Så da kommer det til å iterere gjennom og det går fra j i pluss en er lik. Så vi vet allerede at det er vår første elementet. Vi trenger ikke å sammenligne det med seg selv. Så vi begynner å sammenligne den med neste en som er grunnen til at det er i pluss 1 til n minus en, som er enden av rekken der. Og vi sa at hvis matrise på j er mindre enn matrise min, Da vi overføre der våre minimums indekser er. Og hvis min ikke er lik I, som i hvor var vi tilbake over her. Så liker når vi først gjorde dette. I dette tilfelle, ville det begynne på null, vil det ende opp med å være to. Så min ville ikke lik i i ende. Som lar oss få vite at vi trenger å bytte dem. Jeg føler meg som et konkret eksempel vil hjelpe mye mer enn dette. Så jeg skal kode dette opp med dere akkurat nå, og jeg tror det vil bli bedre. Sorterer en tendens til å fungere på den måten at det er ofte bedre bare for å se dem. Så det vi ønsker å gjøre er vi først ønsker de minste elementet i dens posisjon i matrisen. Nøyaktig hva Jakob sa. Du trenger å lagre som liksom. Så vi kommer til å begynne her iterere over matrisen. Vi kommer til å si at det er vår først en bare for å begynne med. Så vi kommer til å ha int minste er lik matrise på i. Så en ting å legge merke til, hver gang denne sløyfen utfører, vi starter ett skritt videre sammen. Når vi starter ser vi på dette. Neste gang vi iterere gjennom, vi starter på denne ene og tildele det vår minste verdi. Så det er svært lik boble slags der vi vet at etter ett pass, Dette siste elementet er sortert. Med utvalg sortere, det er akkurat det motsatte. På hvert pass, vet vi at den første er sortert. Etter den andre pass, andre vil bli sortert. Og som du så med glide eksempler, vår sortert del bare fortsetter å vokse. Så ved å sette vår minste en til arrays i, alt det gjør er sammentrekkende hva vi ser på slik å minimere antall sammenligninger vi gjør. Betyr det fornuftig for alle? Har du behov for meg å kjøre gjennom det igjen saktere eller i forskjellige ord? Jeg er glad for å. OK. Så vi oppbevarer Verdien på dette punktet, men vi ønsker også å lagre indeksen. Så vi kommer til å lagre posisjonen til den minste en, som bare kommer til å være i. Så nå Jacob er fornøyd. Vi har ting lagret. Og nå trenger vi å se gjennom usortert del av tabellen. Så i dette tilfellet er dette ville være vår usortert. Dette er i. OK. Så hva vi skal gjøre kommer til å være for en loop. Når du trenger å iterere gjennom en matrise, tankene dine kan gå til for en loop. Så for noen int k equals-- hva vi mener k kommer til å like å starte med? Dette er hva vi satt som vår minste verdi, og vi ønsker å sammenligne det. Hva ønsker vi å sammenligne det med? Det kommer til å bli denne neste, ikke sant? Så vi ønsker k å bli initialisert å jeg pluss 1 for å starte. Og vi ønsker k i dette tilfellet vi allerede har størrelsen lagret opp her, så vi kan bare bruke størrelse. Størrelse blir størrelsen av rekken. Og vi vil bare oppdaterer k med én hver gang. Cool. Så nå må vi finne det minste elementet her. Så hvis vi iterere gjennom, vi ønsker å si, hvis utvalg på k er mindre enn vår minste value-- det er her vi er faktisk holde styr på hva som er den minste her-- Da vi ønsker å tilordne hva våre minste verdien er. Dette betyr at, åh, vi er itera gjennom her. Uansett hva verdien er her er ikke vår minste ting. Vi vil ikke ha det. Vi ønsker å overføre den. Så hvis vi reassigning det, hva gjør du tror kan være i denne koden her? Vi ønsker å tilordne minste og posisjon. Så hva er minste nå? STUDENT: Array k. INSTRUKTØR: Array k. Og hva er stillingen nå? Hva er indeksene for vår minste verdi? Det er bare k. Så rekke k, k, matche de opp. Så vi ønsket å overføre det. Og så etter at vi fant vår minste, slik at ved slutten av dette for sløyfen her har vi funnet det vår minste verdien er, slik at vi bare bytte det. I dette tilfellet, i likhet si vår minste verdien er her ute. Dette er vår minste verdi. Vi ønsker bare å bytte det her, som er hva som swap-funksjonen nederst gjorde, som vi nettopp skrev opp sammen et par minutter siden. Så det bør være kjent. Og så vil det bare iterere gjennom inntil den når hele veien til slutten, noe som betyr at du har null elementer som usortert og alt annet er blitt sortert. Fornuftig? Litt mer konkret? Koden hjelp? STUDENT: For en størrelse, du aldri egentlig definere det eller endre det, hvordan virker det vet? INSTRUKTØR: Så en ting til merke seg her er int størrelse. Så vi sier i denne sort-- slags er en funksjon i dette er det case-- utvalg sortere, er det vedtatt i med funksjonen. Så hvis det ikke ble vedtatt i, ville du gjøre noe som med lengden av rekken eller du vil iterere gjennom for å finne lengden. Men fordi det er gått i, kan vi bare bruke den. Du bare anta at brukeren ga deg en gyldig størrelse som faktisk representerer en størrelse på array. Cool? Hvis dere har noen problemer med disse eller ønsker mer praksis koding sorterer på egen hånd, bør du gå til study.cs50. Det er et verktøy. De har en brikke som du faktisk kan skrive. De gjør pseudokode. De har flere videoer og lysbilder inkludert de jeg bruker her. Så hvis du fortsatt føler en litt uklar, prøve det ut. Som alltid, kom snakke med meg, også. Spørsmål? STUDENT: Sier du det Størrelsen er tidligere definert? INSTRUKTØR: Ja. Størrelse er tidligere definert opp her i funksjonen erklæringen. Så du antar at det er blitt vedtatt i av brukeren, og for enkelhets skyld, vi kommer til å anta at bruker ga oss riktig størrelse. Cool. Så det er valg slag. Folkens, jeg vet at vi lærer mye i dag. Det er en tett data for seksjonen. Så med det, skal vi å gå til innsetting slag. OK. Så før at vi har å gjøre vår runtime analysen her. Så i beste fall innvilget siden jeg viste deg bordet jeg allerede slags ga den bort. Men best case runtime, hva tror vi? Alt sortert. N squared. Alle som har en forklaring for hvorfor du tror? STUDENT: Du sammenligner through-- INSTRUKTØR: Høyre. Du sammenligner gjennom. Ved hver iterasjon, til tross vi minske dette etter en, du fortsatt søker gjennom alt for å finne den minste. Så selv om din minste verdien er her i begynnelsen, du fortsatt sammenligner det mot alt annet å sørge for at det er den minste ting. Så du vil ende opp med å løpe gjennom ca n squared ganger. OK. Og hva er det verste tilfellet? Også n squared fordi du kommer som skal gjøre det samme prosedyre. Slik at i dette tilfellet, utvelgelse liksom har noe at vi også ringe forventet runtime. Så i de andre, vi bare vet øvre og nedre grense. Avhengig av hvor gal vår Listen er eller hvordan usortert det er, de varierer mellom n eller n squared. Vi vet ikke. Men fordi utvalget liksom har samme verste og beste fall forteller at oss at uansett hva slags innspill vi har, enten det er helt sortert eller helt reversere sortert, det er kommer til å ta den samme tidsperiode. Så i så fall, hvis du husker fra bordet vårt, det faktisk hadde en verdi som disse to slags ikke har, som er forventet runtime. Så vi vet at når vi kjører valg slag, det er garantert å kjøre en n squared tid. Det er ingen variasjon der. Det er bare forventet. Og, igjen, hvis du ønsker å lære mer, ta CS 124 i løpet av våren. OK. Vi har sett denne ene. Cool. Så innsetting slag. Og jeg sannsynligvis kommer å fyke gjennom dette. Jeg vil ikke ha dere kode det. Vi må bare gå gjennom den. Så innsetting liksom er snill av lik valg liksom ved at vi har både en usortert og sortert del av tabellen. Men hva er annerledes er at når vi går gjennom en etter en, vi bare ta uansett hvor mange er neste i vår usortert, og riktig sortere det inn i vårt sortert array. Det vil være mer fornuftig med et eksempel. Så alt starter som usortert, akkurat som med valg slag. Og vi kommer til å sortere dette i stigende rekkefølge som vi har vært. Så på vår første pass vi tar den første verdien og vi sier, OK, du er nå i en liste selv. Fordi du er i en liste av deg selv, du er sortert. Gratulerer med å være den første element i denne matrise. Du er allerede sortert alt på egen hånd. Så nå har vi en sortert og en usortert array. Så nå tar vi det første. Hva skjer mellom her og her er at vi sier, OK, vi kommer til å se på første verdien av vår usortert utvalg og vi kommer til å legge den i sin riktig plass i den sorterte array. Så det vi gjør er tar vi fem og vi sier, OK, 5 er større enn 3, så vi bare sette det riktig til høyre for den. Vi er bra. Så da går vi videre til vår neste. Og vi tar to. Vi sier, OK, to er mindre enn 3, så vi vet at det må være på foran vår liste nå. Så det vi gjør er å presse vi 3 og 5 ned og vi beveger oss to inn i det første sporet. Så vi bare å sette den inn riktig sted det skal være. Så ser vi på vår neste, og vi sier seks. OK, 6 er større enn alt i vår sorterte array, så vi bare merke det på til slutt. Og så ser vi på fire. 4 er mindre enn 6, er det mindre enn 5, men det er større enn 3. Så vi bare sette ballen opp midt mellom 3 og 5. Så for å gjøre det litt litt mer konkret, her er litt av det ide om hva som skjedde. Så for hver usortert element, vi bestemme hvor i den sorterte parti det er. Så med tanke på sortert og usortert, vi må traversere gjennom og figur ut hvor det passer i den sorterte array. Og vi setter den ved å forskyve elementer til høyre for det ned. Og da har vi bare fortsette itera gjennom før vi har en helt sortert liste hvor usortert er nå null og sorterte tar opp helheten av vår liste. Så, igjen, for å gjøre ting enda mer konkret, har vi pseudokode. Så i utgangspunktet for jeg er lik 0 til minus 1 n, det er bare lengden på array. Vi har noen element som er lik den første matrise eller de første indeksene. Vi satt j lik. Så mens j er større enn null og matrisen, j minus 1 er større enn den element, så alt som gjør er å sørge for at din j virkelig representerer usortert parti av matrisen. Så mens det er fortsatt ting å sortere og j minus én er-- hva er element henne? J ble aldri definert her. Det er litt irriterende. OK. Anyways. Så j minus 1, du sjekker elementet før det. Du sier, OK, er element før uansett hvor jeg am-- la oss faktisk trekke dette ut. Så la oss si dette er som på våre andre pass. Så jeg kommer til å være lik til 1, som er her. Så jeg kommer til å være lik 1. Dette ville være 2, 4, 5, 6, 7. OK. Så vår element i dette tilfellet kommer til å være lik 4. Og vi har noen j som er kommer til å være lik 1. Oh, er j dekrementering. Det er hva det er. Så j er lik i, så hva dette er sier er at når vi beveger oss fremover, vi er bare å sørge for at vi er ikke over indeksere denne måten når vi prøver å sette ting inn i vårt sortert liste. Slik at når j er lik 1, og i dette tilfellet matrise j minus one-- slik matrise j minus 1 er to i denne case-- hvis det er større enn elementet, så alt dette gjør er skiftende ting ned. Så i dette tilfellet, array j minus én ville være matrise null, noe som er 2. 2 ikke er større enn 4, slik at dette ikke utføres. Så skiftet rører seg ikke ned. Hva dette her er bare bevege sortert rekke ned. I dette tilfellet faktisk, vi kunne do-- la oss gjøre dette til tre. Så hvis vi skal gå gjennom med dette eksempelet, vi er nå her. Dette er sortert. Dette er usortert. Cool? Så i er lik 2, så vår element er lik 3. Og vårt j er lik 2. Så vi ser gjennom, og vi si, OK, er matrise j minus én større enn elementets at vi ser på? Og svaret er ja, ikke sant? 4 er større enn 3, og j er 2, slik at denne utfører koden. Så nå hva vi gjør en matrise på 2, så akkurat her, bytter vi dem. Så vi bare si, OK, array 2 er nå kommer til å bli tre. Og j kommer til å like j minus 1, som er 1. Det er fryktelig, men dere skjønner poenget. J er nå lik 1. Og rekke j er bare kommer til å være lik våre elementet, som var 4. Jeg slettet noe jeg ikke burde har eller miswrote noe, men dere skjønner poenget. Det flytter på n. Og så om dette var, ville det sløyfe igjen, og det vil si, OK, er j en nå. Og rekke j minus 1 er nå to. Er to mindre enn vår element? Nei? Det betyr at vi har satt inn dette elementet på riktig sted i vårt sortert array. Da kan vi ta dette og vi sier, OK, er vår sorterte utvalg her. Og det ville ta dette nummer 6 og vær lignende, OK, er 6 færre enn dette nummeret? Nei? Cool. Vi er fine. Gjøre det igjen. Vi sier 7. 7 er mindre enn enden av vår sorterte array? Nei. Så vi er fine. Så dette ville være sortert. I utgangspunktet alt dette gjør det er å si take det første elementet din usortert array, finne ut hvor det går i sortert array. Og dette tar bare vare av bytteavtaler for å gjøre det. Du er i utgangspunktet bare bytte før det er på rett sted. Det visuelle bildet er at du er flytte alt ned ved å gjøre det. Så det er som en halv boble sort-esque. Sjekk ut studie 50. Jeg anbefaler å prøve å kode dette på egen hånd. Hvis du har noen spørsmål eller ønsker å se eksempelkode for en innsetting sortere, vennligst gi meg beskjed. Jeg er alltid rundt. Så worst case runtime og best case runtime. Som du fyren så fra bordet jeg allerede viste deg, det er både n squared og n. Så snill å gå ut av hva vi snakket om med våre tidligere former, verste case runtime er at hvis det er helt usortert, vi har å sammenligne alle disse n ganger. Vi gjør en hel masse sammenligninger fordi hvis det er i motsatt rekkefølge, vi kommer til å si, OK, dette er den samme, er dette bra, og dette vil måtte bli sammenlignet mot den første til å bli beveget tilbake. Og som vi får mot halen slutten, har vi å sammenligne, sammenligne, og sammenligne mot alt. Så det ender opp med å bli ca n squared. Hvis det er riktig så du si, OK, to, du er flink. 3, du er sammenlignet med 2. Du er flink. 4, du bare sammenligne med halen. Du er flink. 6, sammenlignet med halen, du er fine. Så for hvert sted hvis det er allerede sortert, du gjør en sammenligning. Så det er bare n. Og fordi vi har et best case runtime n og en worst case runtime av n squared, har vi ingen forventet runtime. Det avhenger bare av den kaos av vår liste der. Og igjen, en annen graf og en annen tabell. Så forskjellene mellom sorterer. Jeg skal bare bris gjennom, jeg føler at vi har snakket mye om hvordan de alle slags av variere og koble sammen. Så Flettesortering er den siste Jeg skal kjede dere med. Vi har et ganske fargerikt bilde. Så flette sort er en rekursiv algoritme. Så vet dere hva en rekursiv funksjon er? Alle som ønsker å si? Du ønsker å prøve? Så en rekursiv funksjon er bare en funksjon som kaller seg. Så hvis dere er kjent med Fibonacci-sekvensen, som er ansett rekursiv fordi du tar de to foregående og legge dem sammen å få din neste. Så rekursive, jeg tenker alltid av rekursjon som som en spiral så du er som spiral ned i den. Men det er bare en funksjon som kaller seg. Og, faktisk, veldig raskt jeg kan vise deg hva som ser ut som. Så rekursive her, hvis vi ser, er dette den rekursive måte å oppsummere over en tabell. Så alt vi gjør er vi har sum funksjon sum som tar en størrelse og en matrise. Og hvis du legger merke til, størrelse svekkelser av en hver tid. Og alt det gjør er hvis x er lik zero-- slik at hvis størrelsen av rekken er lik zero-- den returnerer null. Ellers oppsummerer dette siste element i matrisen, og deretter tar en sum av resten av matrisen. Så det er bare å bryte det ned i mindre og mindre problemer. Lang historie kort, rekursjon, funksjon som kaller seg selv. Hvis det er alt du fikk ut av dette, det er hva en rekursiv funksjon er. Hvis du tar 51, vil du få veldig, veldig komfortabel med rekursjon. Det er virkelig kult. Det var fornuftig på som 3 AM en natt ute. Og jeg var som, hvorfor har jeg aldri bruke dette? Så for merge sort, i utgangspunktet hva det kommer til å gjøre, er det kommer til å bryte det ned, og bryte det ned før det er bare enkeltelementer. Enkeltelementene er enkelt å sortere. Vi ser at. Hvis du har ett element, er det allerede vurdert sortert. Så på en inngang på n elementer, hvis n er mindre enn 2, bare tilbake fordi det betyr det er enten 0 eller 1 som vi har sett. De anses sorterte elementer. Ellers bryte den i to. Sortere første halvår, sortere den andre halvparten, og deretter flette dem sammen. Hvorfor det heter merge sort. Så vi har her vi vil sortere disse. Så vi holder å ha dem inntil gitterstørrelse er 1. Så når det er en, vi bare tilbake fordi dette er en sortert matrise, og dette er en sortert matrise, og det er en sortert array, er vi alle sortert. Så det vi gjør er vi begynne å flette dem sammen. Så på den måten du kan tenker om sammenslåing er du bare fjerne mindre antallet av hver av de sub-arrayer og bare føye det til fremkom array. Så hvis du ser her, når vi har disse settene har vi 4, 6, og en. Når vi ønsker å slå sammen disse, vi ser på disse to først og vi sier, OK, en er mindre, det går til fronten. 4 og 6, det er ingenting å sammenligne det til, bare merke det på til slutt. Når vi kombinerer disse to, vi bare ta den mindre av disse to, så det er en. Og nå tar vi minste av disse to, så to. Minste av disse to, tre. Minste av disse to, 4, 5, 6. Så du bare å trekke av disse. Og fordi de har blitt sortert tidligere, du bare har én sammenlikning hver gang der. Så mer kode her, bare representasjon. Så du begynner på midten og du liksom venstre og høyre og så du bare flette dem. Og vi ikke har kode for flette akkurat her. Men, igjen, hvis du går på studere 50, vil det være der. Ellers komme å snakke med meg Hvis du fortsatt er forvirret. Så kult her er at beste fall verste fall, og forventet runtime er alle i log n, der er langt bedre enn vi har sett for resten av våre former. Vi har sett n squared og hva vi faktisk får her er n log n, som er flott. Se på hvor mye bedre det er. Slik en fin kurve. Så mye mer effektiv. Hvis du noen gang kan, bruk flette slag. Det vil spare deg for tid. Så igjen, som vi sa, hvis du er nede i denne nedre regionen, det gjør ikke det mye av en forskjell. Du får opp til tusenvis og tusenvis av innganger, du definitivt vil ha en mer effektiv algoritme. Og, igjen, vår nydelig bord av alt former som dere har lært i dag. Så jeg vet det har vært en tett dag. Dette er ikke nødvendigvis kommer å hjelpe deg med din PSet. Men jeg vil bare gjøre en ansvarsfraskrivelse den delen er ikke bare om psets. Alt dette materialet er rettferdig spill for dine midterms. Og også hvis du fortsetter med CS, disse er veldig viktige grunnprinsipper som du trenger å vite. Så noen dager vil være en litt mer PSet hjelp, men noen uker vil være mye mer faktiske innholdet som kanskje ikke synes super nyttig for deg akkurat nå, men jeg lover hvis du fortsetter på vil være veldig, veldig nyttig. Så det er det for seksjonen. Ned til ledningen. Jeg gjorde det i løpet av ett minutt. Men det du går. Og jeg vil ha donuts eller godteri. Er noen allergisk mot noe, forresten? Egg og melk. Så donuts er et nei? OK. OK. Sjokolade nei? Starburst. Starbursts er gode. OK. Vi kommer til å ha Starburst neste uke da. Det er det jeg får. Dere har en flott uke. Les spec. La meg vite om du har noen spørsmål. PSet to karakterer bør være ut til deg innen torsdag. Hvis du har noen spørsmål om hvordan jeg gradert noe eller hvorfor jeg gradert noe slik jeg gjorde, vennligst send meg, kom snakke med meg. Jeg er litt gal denne uke, men jeg lover Jeg vil fortsatt svare innen 24 timer. Så ha en flott uke, alle sammen. Lykke til på din PSet.