SPEAKER 1: Hej alle! Velkommen tilbage til afsnittet. Så glad for at se så mange af jer både her, og alle, der er at se online. Så som sædvanlig velkommen tilbage. Jeg håber, at alle havde en dejlig weekend, fuld af hvile, afslapning. Det var smukt ud i går. Så jeg håber du har nydt udendørs. 

Så først et par meddelelser. Censur. Så de fleste af jer bør har fået en e-mail fra mig om din Scratch Pset, samt Vurdering af Pset 1. Så bare et par ting. Vær sikker på at bruge check50 i style50. Disse er beregnet til at være ressourcer til jer, at sikre, at du får så mange point som du kan uden unødigt at miste dem. Så ting som stil er meget vigtige. Vi kommer til at tage ud for det. Nogle af jer har måske allerede bemærket, at fra din Pset. Og check50 er bare en rigtig nem måde at sikre, at vi faktisk er returnering hvad skal returneres til brugeren, og at alt virker korrekt. 

På den anden note, så sørg for din uploade ting til den rigtige mappe. Det gør mit liv bare en lidt sværere hvis du uploader Pset 2 ind Pset 1 fordi når jeg downloader ting, de ikke downloader korrekt. Og jeg ved, det er lidt wonky i et system til at vænne sig til, men blot være super forsigtig, hvis det kun for mig, så når du får e-mails på ligesom 2:00 og jeg er sortering. Hvis ikke forårsage jeg nødt til at se hele vejen rundt for din Pset. Cool. 

Jeg ved det er tidligt, men jeg helt fik taget off guard af et essay, der er på grund af denne fredag, at mine professorer var ligesom, oh yeah. Husk, du har en essay forfalder på fredag. Så jeg kender ingen kan lide at tænke midterms, men din første quiz er den 15. oktober som oktober starter i denne uge. Så kan det være hurtigere end du regnede med, er alt. Så du er ikke smidt ud vagt, når Jeg nævner næste uges afsnit, der åh, din quiz i næste uge, tænkte jeg Jeg ville give dig en lille smule mere af en hoveder op nu. 

Så dit problem sæt, nummer tre. Hvordan folk har læst spec ud af nysgerrighed? OK. Vi fik et par. Slags ned fra sidste uge, men det er OK. Jeg ved, det var smukt ud. Så Break Out. Bestemt efter du få gjort i dag læse din spec mindst prøv gerne downloade fordeling kode og drift ligesom den første indledende ting, de beder dig til. Fordi vi bruger fordeling kode og et bibliotek at vi kun har været using-- --Det er kun anden gang vi har gjort dette Pset, skøre ting kan ske med dit apparat, og du ønsker at finde, ud nu versus senere. 

For hvis det er torsdag aften, eller det er Onsdag nat og nogle grunde apparatet bare ikke ønsker at køre med biblioteket eller med fordelingen kode, som midler du kan ikke engang begynde at gøre kodningen. Fordi du ikke kan kontrollere for at se, om det virker. Din ikke gonna være i stand at se, om det kompilerer. Du ønsker at tage sig af dem, tidligt i uge, når man stadig kan e-maile mig eller en af ​​de andre TF'er, og vi kan få dem rettet. Fordi disse er spørgsmål der kommer til at stoppe dig fra at gøre reelle fremskridt. Det er ikke ligesom en bug, at du kan bare slags springe over. Hvis du har problemer med din apparat eller distribution kode, du virkelig ønsker at få det taget pleje af hellere før end senere. Så selvom du ikke gonna faktisk starte kodning, hente distributionen kode, kan du læse spec, sørg alt arbejder der. OK? Hvis du bare kan gøre det, jeg lover jeres liv vil blive lettere. Og så er du sandsynligvis vil at gøre det lige nu rigtigt? OK. Så eventuelle spørgsmål der? Eventuelle logistiske ting? Alle er godt? OK. 

Ansvarsfraskrivelse for dem af du i værelset og online. Jeg har tænkt mig at forsøge at skifte mellem PowerPoint i apparatet fordi vi kommer at være at gøre nogle kodning dag ved populære efterspørgsel af den anonyme forslag meningsmåling jeg sendte ud i sidste uge. Så vil vi gøre nogle kodning. Så hvis du fyre vil også at fyre op dine apparater, og du bør have fået en e-mail fra mig, med en prøve-fil. Du er velkommen til at gøre det. 

Så vi kommer til at tale om GDB, som er en debugger. Det kommer til at hjælpe dig slags regne ud, hvor tingene går galt i din kode. Det er egentlig bare en måde for dig at træde gennem din kode som det sker, og være i stand til at udskrive variabler eller se, hvad der faktisk sker under kølerhjelmen vers dit program bare kører, det er ligesom forkastning, og du er ligesom, ingen idé hvad der lige skete her. Jeg ved ikke, hvilken linje det mislykkedes på. Jeg ved ikke, hvor det gik galt. Så er GDB vil hjælpe dig med det. Også, hvis du beslutter dig for at fortsætte ja, og tage 61, det vil virkelig, virkelig være din bedste ven, fordi jeg kan fortælle dig fordi jeg går igennem denne klasse. 

Vi kommer til at se på binær søg, som, hvis du fyre huske den store telefonbog eksempel skue fra klassen. Vi vil gennemførelsen af ​​denne, og walking gennem at en lille smule mere, og så vil vi gennem fire forskellige slags, der er Bubble, Udvælgelse, indsættelse og sammenfletning. Cool. Så GDB som jeg nævnte, er en debugger. Og disse er slags af de store ting, de store funktioner eller kommandoer at du bruger i GDB, og jeg vil gå dig gennem en demo af det i en anden. 

Så det er ikke bare vil bo abstrakt. Jeg vil prøve og gøre det så konkret som muligt for jer. Så bryde. Det vil enten være pause lignende, et tal, som repræsenterer en linje i dit program, eller du kan navngive en funktion. Så hvis du siger bryde main, det vil stoppe ved main, og lade dig gå gennem denne funktion. 

Ligeledes, hvis du har nogle eksterne fungerer som Swap eller Cube, at vi kiggede på i sidste uge. Hvis du siger bryder en af ​​dem, når dit program rammer, at det vil vente på dig til fortælle det, hvad de skal gøre. Før det bare vil køre, så du faktisk kunne trin inde i funktion og se, hvad der foregår. Så næste, bare springer over næste linje, går over funktioner. Step. Disse er alle lidt abstrakt. Så vil jeg bare at køre gennem dem, men du vil se dem i brug i en anden. 

Træd ind i en funktion. Så som jeg sagde, gerne med Swap, ville det giver dig mulighed for rent faktisk som hvis du er ligesom fysisk stepping inde, du kan rod med de variabler, print ud af, hvad de er, se, hvad der foregår. Listen vil bogstaveligt talt bare udskrive den omgivende kode. Så hvis du slags glemmer hvor du er i dit program, eller du spekulerer hvad der foregår omkring det, dette vil bare udskrive et segment af lide fem eller seks linjer omkring det. Så kan du få orienteret om, hvor du er. 

Udskriv nogle variabel. Så hvis du har nøglen ligesom i Cæsar, at vi vil se på. Du kan sige Print Key på noget tidspunkt. Det vil fortælle dig, hvad værdien er så at, måske et eller andet sted langs vejen, du har overskrevet din nøgle. Man kan faktisk sige at fordi du rent faktisk kan se, at værdien. 

I de lokale, bare udskrifter din lokale variabler. Så når du er inden for en løkke, og du blot ønsker at se ud, oh. Hvad er min jeg? Hvad er denne nøgle værdi at jeg initialisere her? Hvad er budskabet på dette punkt? Det vil bare udskrive alle af dem, så man behøver ikke at individuelt sige, Print I. Print Message. Print Key. Og derefter vise. Hvad det gør, er, som du trin gennem programmet, det vil bare sørge for, at det er vise nogle bestemte variable på hvert punkt. Så du also-- --Det er slags en genvej, hvor du behøver ikke at holde ud ligesom, oh. Print Key eller Udskriv I. Det bare vil automatisk gøre det for dig. 

Så med dette, vil vi at se, hvordan det går. Jeg har tænkt mig at prøve og skifte over til mit apparat. Se om jeg kan gøre dette. Alle. Vi bare at spejle det. Der er ikke noget vanvittigt på min bærbare computer anyways. OK. Dette skal være denne. Det er så lille. Lad os se om vi kan gøre dette. 

OK. Alice er naturligvis kæmper her bare en lille smule, men vi får det i en momento. OK. Vi er bare nødt til at øge dette. OK. Kan alle slags se det? Måske en lille smule? Jeg ved det er lidt lille. Du kan ikke helt finde ud af hvordan man kan gøre denne større. Hvis nogen kender. Er der nogen vide, hvordan man kan gøre det større? OK. Vi kommer til at rulle med det. Betyder ikke noget anyways fordi det er bare det er den kode, som du fyre bør har. 

Hvad er mere vigtigt er terminalen her. Og vi har her Hvorfor er det så lille? Indstillinger. Oh. Ægte Ike. Hvordan er det? Ud derfra. Er det bedre for alle? OK ,. Cool. 

Du ved, når du er i en CS klasse tekniske vanskeligheder er form af en del af til-- Så lad os klare dette. OK. Så, lige her i afsnittet, som vi havde her. Cæsar er en eksekverbar fil. Så jeg gjorde det. Så én ting at indse med GDB er at det kun virker på eksekverbare filer. Så kan du ikke køre det på en Dotsy. Du er nødt til rent faktisk at gøre sikker på, at din kode kompilerer, og at det faktisk kan køres. 

Så sørg for, at hvis det ikke gør kompilere, få det til at kompilere, så man kan slags løbe igennem den. Så for at starte GDB, alt hvad du gør, Gloria typen GDB, og så bare det fil, du ønsker. Jeg altid staver Cæsar. Men du vil være sikker da det er en eksekverbar fil, TI dot flash, så betyder, at du går at køre CSI du kommer til at eksekvere dette filer enten med debugger. OK. Så behøver du det, får du denne slags volapyk. Det er bare alle ting om debugger. Du behøver ikke virkelig nødt til at bekymre dig om det lige nu. Og som du kan se, har vi denne åbne Parens, BNP, tæt parens, og bare slags ligner vores kommandolinjen, right? 

Så, hvad vi ønsker at do-- --So, Den første ting er vi ønsker at vælge et sted at bryde den. Så der er en bug i dette Caesar program at jeg præsentere, at vi kommer til at finde ud af. Det, hvad det gør, er det tager input Barfoo i alle kasketter, og en eller anden grund det ændrer ikke A. Det bare efterlader det alene, er alt andet korrekt, men det andet bogstav A forbliver uændret. Så vi vil forsøge at regne ud, hvorfor det er. Så den første ting du typisk ønsker at gøre, når du starter på GDB er at finde ud af, hvor at bryde den. 

Så Cæsar er en temmelig korte program. Vi skal bare have én funktion, right? Hvad var vores funktion i Cæsar? Der er kun én funktion, Main right? Main er en funktion for alle dine programmer. Hvis du ikke har Main, jeg måske være lidt bekymret lige nu, men jeg håber du alle havde Main derinde. Så, hvad vi kan gøre, er at vi kan bare bryde Main, ligesom det. Så det siger OK. Vi sætter vores breakpoint der. 

Så, nu de ting at huske er Cæsar tager én kommandolinje argument højre og vi har ikke gjort at overalt endnu. Så hvad du skal gøre er, når du rent faktisk går til at køre programmet, ethvert program, du er kører i GDB, der skal kommandolinjen argumenter, er du nødt til at indtaste når du først begynder at køre det. Så i dette tilfælde, gør vi Kør med en nøgle på tre. Og det vil faktisk begynde. 

Så hvis du ser her, har vi Hvis RC ikke er lig med 2. Så hvis du fyre har alle denne fil, som jeg sendte ud op du vil se, at det er ligesom første linje vores vigtigste funktion, right? Det er kontrol for at se, om vi har det korrekte antal argumenter. Så hvis du spekulerer hvis RC er korrekt, du kan gøre noget ligesom Print RC. RC er to, som er hvad vi forventede, ikke? 

Så kan vi gå næste, og fortsætter igennem. Så vi har nogle nøgle der. Og vi kan udskrive vores nøgle at sørge for, det er korrekt. Interessant. Ikke helt hvad vi forventede. Så én ting indse med GDB også er at det ikke er indtil du faktisk ramt Dernæst at den linje, som du lige har set faktisk udføres. Så i dette tilfælde Key er ikke blevet tildelt endnu. Så Key er nogle skrald værdi som du kan se på bunden der. Negativ $ 120-- --Det er en milliard og noget mærkeligt ting rigtigt? Det er ikke den nøgle, som vi forventede. Men hvis vi ramt Næste og derefter vi prøv og Print-tast, det er tre. 

Alle se det? Så hvis du får noget at du er ligesom, vent. Dette er helt forkert, og jeg kender ikke hvordan dette vil ske, fordi alt, hvad jeg ønsker at gøre, er at tildele et nummer, en variabel, forsøge at ramme Dernæst prøv at udskrive det igen, og se om det virker. Fordi det kun kommer til at udføre og faktisk tildele noget efter dig hit Næste. Mening for alle? Uh huh? 

SPEAKER 2: Når du tilfældig numre hvad betyder det? 

SPEAKER 1: Det er bare tilfældigt. Det er bare skrald. Det er bare noget, som din Computeren vil tilfældigt tildele. Cool. Så nu kan vi bevæger os igennem, og så nu har vi denne klartekst getString. Så lad mig blot introducere hvad vil ske, når vi ramt Næste her. Vores GDB slags forsvinder, right? Det er fordi getString nu udfører, right? Så når vi så almindelig tekst lig GetString, åbne parens og Parens, og vi ramt Dernæst der har faktisk udføres nu. Så det venter os til input noget. 

Så vi kommer til at indtaste vores fødevarer, som er, hvad det er ikke, som jeg fortalte dig og der bare siger, at det er færdig udførelse, at den er lukket beslag betyder det er afslutter ud af denne løkke. Så kan vi ramt på Næste, og nu, da jeg er sikker på at du kender alle fra Cæsar, dette er, hvad er denne linje vil gøre. Det er for Int Jeg er lig med 0, N er lig StrLen, almindelig tekst, og derefter I er mindre end n, I, plus, plus. Hvad er denne løkke gøre? Åbn din besked. Cool. Så lad os begynde at gøre det. 

Så bør denne betingelse matche, for vores første? Hvis det er en B, det er almindelig tekst I. Vi kan få information om vores lokale. Så I er nul, og hvis seks, hvilket vi forventer, og vores nøgle er tre. Alle, der giver mening, right? Disse tal er alle præcis, hvad de burde være. Så nynne? SPEAKER 3: Jeg har tilfældige tal til mine. SPEAKER 1: Nå, kan vi check-- --Vi kan chatte om det i en anden. Men du skal være at få dette. Så hvis vi har en kapital B til vores første, denne betingelse bør fange det, right? Så hvis vi ramte Dernæst ser vi at denne Hvis faktisk udfører. Fordi hvis du følger sammen i din kode, denne linje her, hvor almindelig tekst jeg erstattes med denne aritmetiske, kun udfører hvis If betingelse er korrekt ret? 

GDB er kun vil vise dig ting, der rent faktisk udfører. Så hvis denne Hvis betingelsen ikke er opfyldt, er det bare at springe til den næste linje. OK? Så vi har der. Dette beslag betyder det er lukket ud af den løkke nu. Så det kommer til at starte igen. Ligesom det. Så at vi kan få info om vores lokale her, og vi kan se, at vores første brev har ændret sig, right? Det er nu en E, som det burde være. Så kan vi fortsætte på. 

Og vi har denne kontrol. Og denne kontrol bør arbejde, right? Det er A. Det bør ændres tre bogstaver fremad. Men hvis du bemærker, at vi få noget andet. Så i dette tilfælde op her, det er fanget det, og så denne linje udføres, som ændret vores B. Men i dette tilfælde her, har vi at det bare sprunget over det, og gik til [? L Siff. ?] Så noget der foregår dér. Hvad der er at fortælle dig er, at, vi ved, at det skal fange her, men det er ikke. Kan nogen se, hvad vores problemet er i denne linje? Det er en meget lille ting. Og du kan også se på din kode. Det er også line-- glemme, hvilken linje det er i there-- men det er i [uhørligt]. Ja? 

SPEAKER 4: Det er på mere end side, hvis man læser det i bogen. SPEAKER 1: Præcis. Så kunne debugger ikke fortælle Dem, men debugger kunne få dig ned til en linje at du ved, fungerer ikke. Og nogle gange, når især senere i semestret, når du beskæftiger sig med en hundrede, en hundrede par linjer kode, og du ved ikke, hvor det er ikke, dette er en fantastisk måde at gøre det. Så fandt vi vores fejl. Du kan ordne det i din fil, og så kunne du køre det igen, og alt ville fungere perfekt. Og den største ting er dette kan synes som, OK. Ja. Cool. Du vidste, hvad du leder efter. Så du vidste, hvad de skal gøre. 

GDB kan være super nyttige, fordi du kan udskrive alle disse ting, som du ville ikke. Det er meget mere nyttigt end printf. Hvor mange af jer bruger ligesom printf udsagn at regne ud, hvor en fejl var, right? Så med dette, behøver du ikke nødt til at holde tilbage, og gerne kommentere på Printf, eller kommentere ud, og regne ud, hvad du skal udskrive. Dette faktisk bare giver dig mulighed for at gå gennem udskrive ting som du går igennem, så kan du observere, hvordan de ændrer i realtid, som dit program kører. 

Og det tager lidt lidt getting bruges til. Jeg vil meget anbefale bare lidt af at være lidt frustreret over det for lige nu. Hvis du tilbringe en time i løbet af næste uge at lære at bruge GDB, du vil spare dig selv så meget tid senere. Og bogstaveligt. vi fortæller dette mennesker hvert år, og jeg kan huske, da jeg tog klasse, jeg var ligesom, jeg vil være fint. Nej. Pset 6 kom, og jeg var ligesom, Jeg skal lære hvordan man bruger GDB fordi jeg ikke vide, hvad der foregår her. 

Så hvis du tager dig tid så bruge det på mindre programmer at du kommer til at være arbejder på, at arbejde gennem noget lignende Visionare, som denne. Eller hvis du ønsker ekstra praksis, er jeg sikker Jeg kunne komme op med buggy programmer for dig at fejlsøge, hvis du gerne vil. 

Men hvis du bare tage lidt tid at få vant til det, bare lege med det, det virkelig vil tjene dig godt. Og det er virkelig en af de ting, som du bare nødt til at prøve, og få dine hænder beskidte med, før du virkelig forstår det. Jeg har egentlig kun forstod det engang Jeg havde til at fejlrette ting med det, og det er meget pænere at have en idé om hvordan man debug hellere før end senere. OK. Cool. Jeg ved, det er lidt ligesom et lynkursus i GDB, og jeg vil helt sikkert arbejde på at få disse til at se større næste gang. Cool. 

Så hvis vi går tilbage til vores PowerPoint. Er det at gå på arbejde? AWH. Ja. OK. Så hvis du nogensinde brug for nogen af dem igen, der er på listen. Så binær søgning, som alle husker den store forestilling af David ripping telefonbøger i halve. Jeg kan ikke rigtig få den telefonbøger længere, fordi ligesom hvor vil du få telefonbøger i disse dage? Jeg virkelig ikke kender. Binary Search. Er der nogen der kan huske hvordan binær søgning Works? Nogen overhovedet? Ja? SPEAKER 5: Du ved, når man ser på, hvor halvdelen det ville være i, på grundlag af denne, og slippe af med den anden halvdel. 

SPEAKER 1 Præcis. Så binær søgning, det er lidt en-- --Vi lide at kalde det splitte og erobre. Så, hvad du skal gøre, er du vil se i midten, og du vil se, om det passer hvad du leder efter. Og hvis det ikke gør, så du forsøger at regne ud, er det vil blive overladt halvdelen eller den højre halvdel. Så kan det være, hvis du søger på noget, der er ordnet alfabetisk, du ser, oh. Er Allison kommer før M? Ja. Så vi kommer til at se på den første halvdel. 

Eller det kan være ligesom med tal. Alt, hvad du kan sammenligne det kan sorteres. Du kan bruge binær søgning på. Så nogen huske denne graf eller hvad det er? Det er Asymptotisk kompleksitet. Så denne graf bare beskriver hvor lang tid det tager dig med at løse et problem, som du øge antallet af ting at du bruger. 

Så vi har N, hvilket er lineær tid. Hvis N over to, hvilket er lidt bedre, stadig vokser super hurtigt. Og så har vi login, hvilket er hvad vi anser binær søgning. Hvis vi opdager, da dit problem får langt og meget større, den tid det tager dig at løse det egentlig ikke stige så meget. Det er ligesom sammenlignelige her i begyndelsen. Du er ligesom, OK. Noget her egentlig ikke uanset hvilken en vi bruger, men du får ud til en million, en milliard. Du forsøger at finde some-- --you're forsøger at finde en nål i en høstak. 

Jeg tror, ​​du ønsker dette problem. Du ønsker denne kompleksitet, ikke lineær fordi til alle jer kender din gonna være at søge gennem hver enkelt nål, ting af hø, forsøger at lede efter nålen. Og det er ikke alt for sjovt i min udtalelse. Jeg kan lide hurtig. Jeg kan lide effektiv. Og som hårdtarbejdende studerende dig fyre er, du ved arbejde smartere, ikke hårdere type ting, hvordan du kan gøre op disse algoritmer. 

Så vi kommer til at gå gennem blot et hurtigt eksempel. Jeg tror du fyre bør have en hånd på binær søgning, men hvis nogen er lidt fuzzy, ønsker at styrke det, vi kommer til at bare gå gennem et eksempel her. Så er vi på udkig efter hvis arrayet indeholder syv. 

Så første ting, vi gør, er ser i midten, højre? Og også du vil være kodning Binary Søg på bare et sekund. Så det kommer til at være sjovt. Så vi ser i den midterste små arrays 3. Er 3 lig 7? Ikke gør. Det er seks. Så er det mindre end eller større end syv? Mindre end. Ja. Nice job fyre. Jeg føler, jeg kan lide, jeg skulle have slik, fordi jeg ønsker at smide det ud i værfterne. Det er, hvad jeg vil gøre i næste uge. Det vil holde jer skarpe. 

Så vi smider væk, første halvdel, right? det var mindre end. Vi ved, at alt på den venstre side vil være mindre end hvad vi faktisk på udkig efter. Så der er ingen grund til at opmærksomme på det. Bare glem det. Så nu ser vi på vores højre side, og vi ser på midten derovre, og nu er det ni. Så 9 is-- --Everyone? Større end hvad vi er leder efter, right? Så vi kommer til at kaste alt væk til højre. Ligesom det. Nu er alt vi tilbage med er en. Så vi kontrollere, er denne ene hvad vi leder efter? det er. Vi fandt hvad vi ønskede. Så vi er færdig. Bilineær Search. 

Og hvis du bemærker, at vi havde syv indgange der. Det tog os kun som tre gange, men hvis du laver ligesom en milliard, du fyre ved, hvor mange skridt det ville tage, hvis vi havde fire milliarder ting? Nogen gæt? Det er 32. 32 trin til at finde noget i en fire milliarder elementopstillingen grund af beføjelser to. Så to er til 32, er til fire milliarder. 

Så temmelig vanvittigt, hvordan du er stadig inden for som et forholdsvis lille antal trin at finde noget i fire milliarder elementer. Så på dette notat, er vi kommer til at kode dette så du fyre kan faktisk slags se, hvordan det virker. Okay, så du fyre kan kode. Jeg har tænkt mig at lade dig fyre tale om en lille smule. Få at vide folk omkring dig, som er hvad nogen ønskede fra sidste afsnit. 

Så få at vide de mennesker omkring dig. Tal for en lille smule. Og alt, hvad jeg ønsker fra dig fyre lige nu er bare forsøge at skabe et omrids af pseudokode. OK? Whoa. Alt hvad jeg ønsker fra jer er, du er bare kommer til at fylde i denne case. Så jeg har sat disse øvre og nedre grænser, som repræsenterer begyndelsen og slutningen af ​​vores array. Og du kommer til at faktisk loop igennem og finde ud af hvad vi laver i denne while-løkke. 

Så hvis du kan regne out-- jeg har en antydning there-- hvad er de tilfælde, at vi her? Så hvis du ønsker at finde ud af tilfælde vil vi pseudokode dem og så vil vi faktisk kode dem. Og det kommer til at være, jeg tror, ​​forhåbentlig det vil være lidt nemmere, end du forventer. Fordi det er ikke så meget kode, faktisk, som er virkelig cool. 

Mm-hm? 

STUDENT: [uhørligt]? Instruktør: Ja. Der var noget at finde i midten. 

STUDENT: Så vi kan bruge det. OK. 

Instruktør: Perfect. Så det er det første, vi skal gøre. Så find midten. Great. Så har du en idé om, hvordan vi kan faktisk finde midten med koden? 

STUDENT: Ja. n over 2? Instruktør: Så n over 2. Så én ting at huske er, at din øvre og nedre grænser ændres. Vi holder snærende den del af array, vi leder til. Så n over 2 vil kun arbejde for det første, vi gør. Så tager øvre og nedre højde, hvordan kan vi få det midterste element? Fordi vi ønsker den midterste mellem øvre og nedre, højre? Mm-hm? 

STUDENT: [uhørligt]. 

Instruktør: Så har vi nogle midten. Og det vil være øvre plus lavere over 2. Awesome. Der vi går. En linje ned. Du fyre er på vej. Så nu, at vi har vores midten, hvad ønsker vi at gøre? Bare i almindelighed. Du behøver ikke at kode det. Ja. STUDENT: [uhørligt]? Instruktør: Så det er plus, fordi du er finde gennemsnittet mellem de to af dem. Så hvis du tænker på dem som en slags af stigende fra siderne, tænker over det, når du nærmer midten, du ønsker sådan. Så hvis du var på hver side af midten, og vi har ligesom 5 og 7. Når du tilføjer dem sammen du få 12, du dividere med 2, er 6. 

Nogle gange er det svært at forklare, hvorfor det virker, men hvis du arbejder gennem et eksempel undertiden, det vil hjælpe dig med at finde ud af, om det bør være plus eller minus. Ja. 

STUDENT: [uhørligt] præcis i midten hvis de havde en sag, hvor der er en masse mindre tal og ligesom et stort antal? 

Instruktør: Så alt hvad du har brug for er midten af ​​arrayet. Så hvis du havde en masse små tal og derefter en virkelig stort antal i slutningen, er det ligegyldigt. Alt, der betyder noget, er, at de er sorteret, du bare ønsker at se på midten af array fordi du stadig udskæring dit problem i halve. Cool. Så nu, at vi har den midten, hvad gør vi nu? 

STUDENT: Compare. Instruktør: The sammenligne. Så sammenligne midten til value_wanted. Cool. Så du ser op her har vi denne værdi, vi ønsker her. Husk dette er et array. Så midten refererer til indekset. Så vi ønsker at gøre værdier for midten. Glem ikke, hvis du ønsker at sammenligne, dobbelt ligemænd. Du gør enkelt lig du er bare at overflytte det, og så selvfølgelig, det er vil være den værdi, du ønsker. Så du skal ikke gøre det. 

Så vi kommer til at se, om værdierne ved midten er lig med den værdi, vi ønsker. Glem ikke dine seler. Dropbox skal gå væk. Så hvad gør vi i dette tilfælde? Hvis det er, hvad vi ønsker at vende tilbage? Vi prøver at sige. 

STUDENT: Print slukket. 

Instruktør: Godt, vi ikke ønsker at udskrive fra. Så dette er en bool her, så vi ønsker at vende tilbage sande eller falske. Vi siger, er dette tal en [? RRA? ?] Så hvis det er vi bare returnere det sandt. Hvis jeg kan stave rigtigt. 

STUDENT: Hvorfor ville du ikke returnere nul? Instruktør: Så du kunne returnere nul, hvis du ville. Men i dette tilfælde, fordi vores funktion returnerer en bool, vi nødt til at vende tilbage til enten sande eller falske. STUDENT: Når du er siger boolean udtryk, kan du indstille det lig med falsk? Ligesom hvis jeg ønsker at sige, at hvis denne betingelse ikke er opfyldt, ligesom er øverste lig falsk. Vil det forstå, hvis du bare sætte falsk på den anden side? Instruktør: Ja. Så rent faktisk, hvis du er nogensinde at gøre noget som er øvre eller lavere, som returnerer sandt eller falsk og det er faktisk dårlig stil til sige lig lig sandt eller ligestillede lig med falsk. Du ønsker at bruge dette resultat da selv som din check. Ikke hvad jeg ønskede. Det er, hvad jeg ønskede. Så i tilfælde af du spørger om noget lignende gemme denne i c. 

Så hvis vi har int main (void) og noget som dette. Og du har, hvis er øvre af nogle input, og du er spørger, om du kan gøre noget som dette? Right? STUDENT: Jeg prøvede at gøre det [uhørligt]. Fordi hvis it's-- Instruktør: Right. Så du ønsker dette at være falsk, right? STUDENT: Ja. Instruktør: Så i dette tilfælde dig ønsker det til at udføre, hvis det ikke er sandt. Så cool ting du gør der er dette. Så husk udråbstegn punkt negerer ting? Den siger [uhørligt] betyder ikke. Så hvis vi ser på bare denne del her, ville du sige, der evalueres til falsk som du ønsker det. Ikke falsk er sandt som betyder dette ville udføre. Giver det mening? STUDENT: Ja. Instruktør: Awesome. OK. Så kunne vi bare tilbage sand i dette tilfælde. Så nu har vi to andre tilfælde i denne sag. Hvad er vores to andre sager? Lad os bare gøre det på denne måde. Så lad os starte med andet hvis værdier i midten er mindre end den værdi, vi ønsker. Så vores værdi i midten er mindre end den værdi, som vi leder efter. 

Så som bundet gør du tror, ​​at vi ønsker at opdatere? Øvre eller lavere? Upper? Så hvilken side af opstillingen vil vi se på? 

STUDENT: Jo lavere. 

Instruktør: Vi skal vi at se til venstre. Så ellers hvis ringe værdi er mindre. Så din midterste værdi her er mindre end hvad vi ønsker. Så vi ønsker at tage højre side af vores array. Så vi kommer til at opdatere vores nedre grænse. Så vi vil overflytte vores lavere. Og hvad tror du lavere bør være? STUDENT: Den midterste værdi? Instruktør: Så den midterste value-- STUDENT: Plus 1. Instruktør: --plus 1. Kan nogen fortælle mig, hvorfor vi har den plus 1? 

STUDENT: [? Ingen værdi?] er mere lig det. 

Instruktør: Right. Fordi vi allerede ved, at vores midterste værdi ikke er lig med det, og vi ønsker at udelukke det fra alle efterfølgende søgninger. Hvis du glemmer at plus 1, dette vil gerne loop på ubestemt tid. Og du vil bare blive fanget i en uendelig løkke og så vil du segfault og tingene går dårligt. Så altid sørge for at du ikke er herunder den værdi, du bare kiggede på. Så tager vi os af det med et plus 1. 

Så nu har vi vores sidste betingelse som jeg altid for en sikkerheds skyld du kan tjekke her, ellers hvis værdi på midten er større end værdien vi ønsker. Det betyder, at vi ønsker den venstre halvdel hånd. Så hvilken en skal vi til at opdatere? Øvre. Og hvad er denne ene kommer til at svare? Midten minus 1, fordi selvfølgelig, vi ønsker at sikre, at vi ikke er ser på det midterste værdi igen. Og så har vi det. Det er det. Det er alt binær søgning er. Det er ikke så slemt, right? Det er ligesom 10 linier kode med hvide rum. Så meget kraftfuld, meget nyttigt, vil du være at bruge det i en af ​​dine senere psets. Måske ikke denne ene, men senere. Så lære det. Elsker det. Det vil behandle dig godt. Så nogen der har nogen spørgsmål om binær søgning? Ja. 

STUDENT: Betyder det noget, om din n er lige eller ulige? 

Instruktør: Nej. Fordi vi kastede det til midten som en int, vil det bare afkorte det. Så det vil forblive et heltal, og det vil sidst sortere gennem alt. Så du behøver ikke at bekymre dig om det. Alle godt? Awesome. Cool. Så du fyre fik dette. Slideshow. Så som vi talte om, jeg kender David nævnte kompleksitet runtime. 

Så i bedste fald, det er bare én, som vi kalder konstant tid. Kan nogen fortælle mig, hvorfor det kunne være? Hvilken type scenarie ville det indebære? Mm-hm. 

STUDENT: [uhørligt] first-- Instruktør: Så midten er den første element, som vi kommer til, ikke? Så enten et array af en eller uanset hvad vi leder efter bare sker for at være smack dab i midten. Så det er vores bedste tilfælde. Du får ind i reelle problemer, sandsynligvis ikke kommer til at nå [uhørligt] så ofte. Hvad med vores værste fald? Vores værste fald er log n. Og der har at gøre med det hele beføjelser to ting, som jeg talte om. 

Så i værste fald ville det betyde at vi måtte hugge array ned indtil det var et element af en. Så vi var nødt til at hugge den ned i halve så mange gange som vi overhovedet kunne. Det er derfor det er log n fordi du bare holde dividere med to. Så antagelser, ting du har brug for at vide, hvis du nogensinde vil bruge en binær søgning. Dine elementer skal sorteres. De skal sorteres, fordi det er den eneste måde, du kan vide, hvis du er i stand at smide halvdelen af ​​det. 

Hvis du havde denne rodet taske af numre og du siger, OK, jeg har tænkt mig at kontrollere den midterste og nummeret jeg leder efter er mindre end det, vil jeg bare til vilkårligt at smide den ene halvdel. Du ville ikke vide, om din numre i den anden halvdel. Din liste skal sorteres. Samt, kan dette være går videre en lille smule, men du skal have random access. Du skal være i stand til bare gå til denne midterste element. Hvis du har til at krydse gennem noget eller det tager dig ekstra trin for at komme til det midterste element, det er ikke log n længere, fordi du tilføjer mere arbejde i det. Og det vil gøre en lille mere mening om to uger, men jeg bare slags ønskede at indlede, giver jer en idé om, hvad der er at komme. Men det er de to vigtige forudsætninger at du har brug for en binær listen. Sørg for, at det er sorteret. Det er den store én for jer lige nu. Og der kan vi gå ind i resten af ​​vores slags. Så fire sorts-- boble, indsættelse, udvælgelse, og smelter sammen. De er alle slags cool. Hvis du fyre beslutter at tage CS 124, vil du lære om alle mulige slags. Og hvis du er en xkcd fan, der er en virkelig cool tegneserie om ligesom virkelig ineffektive slags, som jeg anbefales du vil se på. En af dem er som panik slags, som er ligesom, åh nej, tilbage tilfældig array. Shutdown system. Efterlad. Så nørdede humor er altid godt. 

Så er der nogen huske slags ligesom bare en generel idé hvordan boble slags fungerer. Kan du huske? 

STUDENT: Ja. 

Instruktør: Go for it. 

STUDENT: Så du går igennem, og hvis det er større, så bytte dig de to. 

Instruktør: Mm-hm. Præcis. Så du bare gentage gennem. Du tjekker to numre. Hvis en før er større end den bagefter, du bare bytte dem, så i denne måde alle de højere tal boble op mod slutningen af ​​listen og alle lavere numre boble ned. 

Har han vise dig fyre den kølige lydeffekt sortering video? Det er lidt cool. Så som Robert sagde bare, algoritmen at du bare gå gennem listen, swapping tilstødende værdier hvis de ikke er i orden. Og så bare med at gentage indtil du ikke gør nogen swaps. Så ikke dårligt, right? Så vi bare have en hurtig eksempel her. Så dette kommer til at sortere dem i stigende rækkefølge. Så når vi går gennem den første tid, vi ser gennem otte og seks er naturligvis ikke i orden, vi bytte dem. 

Så kig på den næste. Otte og fire ikke i orden. Bytte dem. Og så otte og to, bytte dem. Der vi går. Så efter dit første pass, du vide, at din største antal vil være hele vejen i toppen, fordi det er bare kommer til at være konstant større end alt andet og det bare at gå til boble op hele vejen til enden der. Er der giver mening for alle? Cool. 

Så ser vi på vores andet gennemløb. Switch seks og fire. Switch seks og to. Og nu har vi et par ting i orden. Så for hver pass, som vi gøre gennem hele vores liste, vi ved, at ligesom at mange numre ved udgangen vil være blevet sorteret. Så vi gør en tredje aflevering, som er en swap. Og derefter på vores fjerde passere, vi har nul slots. Og så ved vi, at vores array er blevet sorteret. 

Og det er den store ting med boble slags. Vi ved, at når vi have nul swaps, at betyder, at alt er i fuldstændig orden. Det er lidt, hvordan vi kontrollere. Så vi vil også kode boble sortere som også er ikke så slemt. Ingen af ​​disse er så slemt. Jeg ved, at de kan virke lidt skræmmende. Jeg ved, når jeg tog klassen, selv når jeg underviste klassen for første gang sidste år, Jeg var ligesom, hvordan gør jeg det? Det giver mening i teorien, men hvordan gør vi egentlig det? Hvilket er grunden til jeg ønsker også at gå gennem kode med jer her. Så jeg har en pseudokode til jer denne gang. Så bare holde dette i tankerne, som vi er ved at skifte i løbet. Så vi har nogle tæller, holder styr på vores swaps, fordi vi er nødt til at sørge for, at vi tjekker det. Og vi gentage hele systemet som vi lige gjorde med dette eksempel. Hvis elementet før er større end elementet efter hvor vi er på, vi bytte dem, og vi tilvækst vores tæller fordi så snart vi bytte, Vi ønsker at lade vores tæller vide. Eventuelle spørgsmål dér? Noget virker sjovt herovre. STUDENT: Mener du indstille tælleren til nul hver gang du går gennem løkken? Må ikke du holde ud tilbage til nul hver gang? Instruktør: Ikke nødvendigvis. Så hvad sker der, er vi går igennem her. Så gør samtidig, husk, dette vil køre en gang uden at fejle. Så det kommer til at indstille tæller lig med nul, så det kommer til at gentage gennem. Som det gennemløber, det vil opdatere tæller. Som den opdaterer tæller, når det er gjort, når det er nået til slutningen af ​​arrayet, hvis vores liste ikke er sorteret, Tælleren er blevet opdateret. 

Så kontrollerer det tilstanden og det siger, OK, er tælleren større end nul. Hvis det er, gøre det igen. Du ønsker at nulstille, så når du gå igennem, tælleren er lig med nul. Hvis du går gennem en sorteret array, ændrer intet, dette mislykkes, og du returnere sorteret liste. Giver det mening? STUDENT: Det kunne i en lille smule. Instruktør: OK. Hvis der er en anden spørgsmål, der kommer op. Ja. 

STUDENT: Hvad ville den funktion være for at bytte de elementer? 

Instruktør: Så vi kan faktisk skrive at hvis vi kommer til lige nu. Cool. Så på dette notat, er Alison går at skifte tilbage til apparatet. Det kommer til at være sjovt. Og vi har vores dejlige Boblesortering ting her. Så jeg gjorde allerede cykling gennem array. Vi har vores swaps, som er lig med nul. Så vi ønsker at bytte tilstødende elementer, hvis de er ude af drift. Så den første ting, vi er nødt til at gør, er gentage gennem vores array. 

Så hvordan tror du, vi måske gentage gennem vores array? Vi har for, og jeg er lig med 0. Vi ønsker jeg at være mindre end n minus 1 minus k. Og jeg vil forklare, at i en anden. Så dette er en optimering her, hvor huske, hvordan jeg sagde efter hver pass gennem array vi vide, at uanset hvad er on-- 

Så efter en pass vi ved, at dette er sorteret. Efter to gennemløb ved vi at alt dette er sorteret. Efter tre passerer vi ved, at der sorteres. Så den måde jeg iteration gennem array her, er det at sikre, at kun gå gennem hvad vi ved er usorteret. OK? Det er bare en optimering. Du kunne skrive det naivt bare iteration gennem alt, det ville bare tage længere tid. Med denne fire loop er det bare en dejlig optimering fordi vi ved, at efter hver hele iteration gennem array her, ligesom hver fuld løkke her, vi kender at en flere af disse elementer vil blive sorteret i slutningen. 

Så vi behøver ikke at bekymre sig om dem. Er der giver mening for alle? Denne cool lille trick? Så i dette tilfælde, hvis vi iteration igennem, vi ved, at vi ønsker at kontrollere, om matrix n og n plus 1 er i orden. OK. Så her er pseudokode. Vi ønsker at kontrollere, om opstilling n og n plus 1 er i orden. Så hvad kunne vi have der? Det kommer til at være nogle betingede. Det vil være en hvis. 

STUDENT: Hvis matrix n er mindre end matrix n plus 1. Instruktør: Mm-hm. Nå, mindre end eller større end. STUDENT: Større end. Så vi ønsker at bytte dem. Præcis. Så nu vi kommer ind, hvad der er den mekanisme til at bytte dem? Så vi gik gennem dette kort, en type swap funktion i sidste uge. Er der nogen der kan huske, hvordan det fungerede? Så vi kan ikke bare forflytte dem, right? Fordi en af ​​dem vil gå tabt. Hvis vi sagde A er lig med B, og derefter B er lig med A, alle pludselig begge er blot lig med B. 

Så hvad vi skal gøre, er vi have en midlertidig variabel, der er kommer til at holde en af ​​vores mens vi er i færd med at bytte. Så hvad vi har, er vi får nogle int temp er lig at-- du kan tildele det til den, du vil, bare Sørg for at holde styr på it-- så i dette tilfælde, vil jeg tildele den til matrix n plus 1. Så det kommer til at holde, hvad værdi i denne anden blok at vi kigger på. 

Og så vi kan gøre, er at vi kan gå fremad, og tildel matrix n plus 1, fordi vi ved, at vi har denne værdi lagres. Dette er også en af ​​de store things-- Jeg ved ikke, om nogen af ​​jer havde spørgsmål, hvor, hvis du skifter to kodelinjer pludselig tingene fungerede. For er meget vigtigt i CS. Så sørg for at diagram ting ud hvis det er muligt om, hvad der faktisk sker. Så nu vil vi overflytte matrix n plus 1, fordi vi ved, at vi har denne værdi lagres. 

Og vi kan tildele den pågældende til opstilling n eller i dette tilfælde matrix i. Alt for mange variabler. OK. Så nu har vi omplaceret opstilling i plus 1 til lige hvad der er i matrix i. Og nu kan vi gå tilbage og tildele matrix i hvad? Anyone? 

STUDENT: 10. 

Instruktør: 10. Præcis. Og en sidste ting. Hvis vi har byttet det nu, hvad skal vi gøre? Hvad er den ene ting der kommer til at fortælle os hvis vi nogensinde afslutte dette program? Hvad fortæller os, at vi har en sorteret liste? Hvis vi ikke udfører nogen swaps, right? Hvis swaps er lig med nul ved udgangen af ​​dette. Så når du udfører en swap, da vi bare gjorde her, vi ønsker at opdatere swaps. Og jeg ved, at der var en spørgsmål tidligere om du kan bruge nul eller én i stedet af sande eller falske. Og det er, hvad dette betyder her. Så det siger hvis ikke swaps. Så hvis swaps er nul, hvilket is-- jeg altid få mine sandheder og mine falses blandet op. Vi vil have os til at vurdere til sand, og det er det ikke. Så hvis det er nul, så er det falsk. Hvis du negere det med en [? bang?] bliver det sandt. Så denne linje udfører. 

Sandheder og falske og nuller og ettaller får vanvittigt. Bare hvis du langsomt gå gennem det det vil give mening. Men det er, hvad denne lille bit kode her gør. Så det kontrollerer, har vi gjort nogen swaps. Så hvis det er noget udover nul, går det at være falsk og det hele er kommer til at udføre igen. Cool? 

STUDENT: Hvad betyder break gøre? 

Instruktør: Break bare bryder dig ud af løkken. Så i dette tilfælde ville det bare gerne afslutte programmet og du ville bare har din sorteret liste. STUDENT: Amazing. Instruktør: Jeg er ked af? STUDENT: Da vi tidligere anvendte skrevet 1 overskrevet nul at præsentere, at hvis der vil arbejde eller ej. 

Instruktør: Ja. Så du kan returnere nul eller 1. I dette tilfælde, fordi vi er faktisk ikke gør noget med den funktion, vi bare vil have det til at knække. Vi har ikke virkelig bekymrer sig om det. Bremse er også godt, hvis det bruges til at bryde ud af fire løkker eller tilstande, du ikke ønsker at beholde udførelse. Det bare tager dig ud af dem. Det er lidt af en nuance ting. Jeg føler som om der er en masse af hånd viftende, ligesom du vil lære om dette snart. 

Men du vil lære om dette snart. Jeg lover. OK. Så gør alle komme Boblesortering? Ikke alt for dårlig. Kør igennem, swap ting ved hjælp af en temp variabel, og vi er alle indstillet der? Cool. Awesome. OK. Tilbage til PowerPoint. Eventuelle spørgsmål i almindelighed om disse hidtil? Cool. Mm-hm. 

STUDENT: [uhørligt] int main normalt. Har du nødt til at have, at for denne? 

Instruktør: Så blev vi bare at kigge netop på det faktiske sortering algoritme. Hvis du havde det inden for ligesom et større program, du ville have en int main eller andet sted. Afhængig af hvor du bruge denne algoritme, det ville bestemme, hvad der er bliver returneret af den. Men for vores sag, vi er strengt se på, hvordan gør dette faktisk gentage gennem et array. Så vi behøver ikke bekymre dig om det. 

Så vi talte om bedste fald og værst tænkelige scenarier for binær søgning. Så det er også vigtigt at gøre at for hver af vores slags. Så hvad tror du er den værste tilfælde runtime af boble slags? Du fyre huske? 

STUDENT: N minus 1. Instruktør: N minus 1. Så det betyder, at der er n minus 1 sammenligninger. Så én ting at indse, er at den første iteration, vi går igennem, vi sammenligner disse to-- så det er 1. Disse to, tre, fire. Så efter en iteration vi allerede har fire sammenligninger. Når jeg taler om runtime og n. N repræsenterer antallet af sammenligninger som en funktion af, hvor mange elementer vi har. OK? 

Så vi går igennem, har vi fire. Næste gang du ved, at vi ikke gør det nødt til at tage sig af dette. Vi sammenligner disse to, disse to, disse to, og hvis vi ikke havde denne optimering med fire løkke, som jeg skrev, du ville være at sammenligne med her anyways. Så du ville have til løber gennem arrayet og foretage sammenligninger n n gange, fordi hver gang vi løber gennem det vi slags én ting. 

Og hver gang vi kører gennem array, gør vi n sammenligninger. Så vores runtime til dette er faktisk n kvadreret, som er langt værre i vores log ende, fordi der betyder, at hvis vi havde fire milliard elementer, det er kommer til at tage os fire milliarder kvadreret i stedet for 32. Så ikke den bedste runtime, men for nogle ting, du ved, hvis du er inden for et bestemt interval af elementer Boblesortering kan være fint at bruge. 

OK. Så nu, hvad er den bedste fald runtime? STUDENT: Zero? Eller 1? 

Instruktør: So 1 ville være en sammenligning. Højre. 

STUDENT: N minus 1? 

Instruktør: Så, ja. Så n minus 1. Når du har et begreb som n minus 1, er vi tilbøjelige til bare aflevere den og vi bare sige n fordi du har at sammenligne hver af these-- hvert par. Så det ville være n minus 1, som vi vi ville bare sige er ca n. Når du har at gøre med runtime, alt er i tilnærmede. Så længe eksponenten er korrekt, er du temmelig godt. 

Det er, hvordan vi skal håndtere det. Således at bedste fald er n, som betyder, at listen allerede er sorteret, og alle vi gøre er at køre igennem og kontrollér, at det er sorteret. Cool. Ok. Så som du kan se her, vi bare have nogle flere grafer. Så n potens. Fun. Meget værre end n, som vi ser, og meget, meget værre end log 2n. Og så skal du også komme ind log logs. Og du tager 124, få dig ind ligesom log stjerne, som er som en sindssyg. Så hvis du er interesseret, opslag log stjerne. Det er lidt sjov. Så vi har denne store diagram. Bare en hoveder op, dette en vidunderlige diagram til at have for din midtvejs, fordi vi lang tid at spørge dig disse tynd. Så bare en heads up, har dette på din midtvejs på din pæne snyde ark der. Så vi kiggede bare på boble slags. Worst case, n kvadreret, bedste fald, n. Og vi kommer til at se på de andre. 

Og som du kan se, er den eneste en, der virkelig gør godt er Mergesort, som vi vil komme ind på hvorfor. Så vi kommer til at gå til næste her-- udvælgelse slags. Er der nogen der kan huske, hvordan udvælgelse sortere arbejdet? Gå efter det. 

STUDENT: Dybest set gå gennem en ordre og oprette en ny liste. Og lige som du lægger elementer i, læg dem på rette sted i den nye liste. 

Instruktør: Så at lyde mere ligesom insertion slags. Men du er virkelig tæt. De er meget ens. Selv jeg får dem blandet op nogle gange. Før dette afsnit vil jeg var ligesom, vent. OK. Så hvad du vil gøre, er udvælgelse sortere, den måde, du kan tænke om det, og den måde, Jeg sørge for jeg forsøger ikke at få dem blandet op, er det går gennem og vælger den mindste antal og det sætter det i begyndelsen af ​​din liste. Det bytter den med den første plet. De har faktisk et eksempel for mig. Awesome. Så bare en måde at tænke på it-- udvælgelse sortere, vælge den mindste værdi. Og vi vil løber gennem et eksempel at jeg tror vil hjælpe, fordi Jeg tror visuals altid hjælpe. Så vi starter ud med noget der er helt usorteret. Red vil være usorteret, grøn vil blive sorteret. Det vil alle give mening i en anden. 

Så vi går igennem, og vi gentage fra begyndelsen til slutningen. Og vi siger, OK, 2 er vores mindste antal. Så vi kommer til at tage 2, og vi vil at flytte det til den forreste del af vores matrix fordi det er den mindste antal vi har. Så det er, hvad dette gør her. Det er bare at bytte de to. Så nu har vi en ordnet del og en usorteret del. Og hvad der er godt at huske om udvælgelse slags er vi kun vælge fra usorteret del. 

Den sorterede del du blot lade alene. Mm-hm? 

STUDENT: Hvordan fungerer det ved, hvad er den mindste uden at sammenligne det til hver anden værdi i array. Instruktør: Det gør sammenligne det. Vi gerne sprunget over det. Det er bare helt overordnet. Ja. Når vi skriver koden jeg sikker på, du vil være mere tilfredse. Men du gemme denne første element som den mindste. Du sammenligner og du sige, OK, er det mindre? Ja. Hold det. Her er det mindre? Nej? 

Dette er din mindste, overflytte det til din værdi. Og du vil blive meget lykkeligere når vi går igennem koden. Så vi går igennem, vi bytte den, ja så vi ser på dette usorteret portion. Så vi kommer til at vælge tre ud. Vi kommer til at sætte det på i slutningen af ​​vores sorterede portion. Og vi bare at holde gør at gøre det, og gør det. Så dette er vores slags pseudokode her. Vi vil kode det op her i en anden. Men bare noget at gå igennem på et højt niveau. Du kommer til at gå fra i er lig 0 til n minus 2. Det er en anden optimering. Må ikke bekymre dig for meget om det. Så som du sagde. Som Jakob sagde, hvordan gør vi holde styr på, hvad vores minimum er? Hvordan kan vi vide? Vi nødt til at sammenligne alt i vores liste. 

Så minimum lig i. Det er bare at sige i denne sag indekset for vores minimumsværdi. Så det kommer til at gentage gennem og det går fra j lig i plus 1. Så vi ved allerede, at det er vores første element. Vi behøver ikke at sammenligne det med sig selv. Så begynder vi sammenligne det med det næste en, der er grunden til det er jeg plus 1 til n minus 1, som er ende af formationen der. Og vi sagde, at hvis arrayet på j er mindre end matrix min, så vi overflytte hvor vores minimumskrav indeks er. 

Og hvis min ikke er lig med I, som i hvor vi var tilbage herovre. Så gerne, når vi først gjorde dette ene. I dette tilfælde vil det starte ved nul, vil det ende med at blive to. Så min ville ikke lige jeg i sidste ende. Der lader os vide, at vi er nødt til at bytte dem. Jeg føler mig som et konkret eksempel vil bidrage meget mere end dette. Så jeg vil kode det op med jer lige nu, og jeg tror, ​​det vil være bedre. 

Sorterer tendens til at arbejde på den måde i det Det er ofte bedre bare at se dem. Så hvad vi ønsker at gøre, er vi først vil have den mindste element i sin position i opstillingen. Præcis hvad Jacob sagde. Du er nødt til at gemme, på en måde. Så vi kommer til at starte her iteration over array. Vi kommer til at sige, det er vores første blot til at begynde med. Så vi er nødt til int mindste er lig med matrix ved jeg. 

Så én ting at bemærke, hver gang denne løkke udfører, vi starter et skridt længere henne. Når vi starter vi ser på denne ene. Næste gang vi gentage gennem, vi starter på denne ene og tildele det vores mindste værdi. Så det er meget lig Boblesortering hvor vi ved, at efter en aflevering, Dette sidste element er sorteret. Med udvælgelse sortere, det er lige det modsatte. 

Ved hver pass, vi ved, at den første er sorteret. Efter den anden passage, den anden vil blive sorteret. Og som du så med slide eksempler vores sorteres portion bare vokser. Så ved at sætte vores mindste til arrays i, alt det gør er snærende hvad vi kigger på, så at minimere antallet sammenligninger vi laver. Giver det mening for alle? Har du brug for mig til at løbe gennem det igen langsommere eller i forskellige ord? Jeg er glad for. OK. 

Så vi opbevare værdi på dette punkt, men vi ønsker også at gemme indekset. Så vi kommer til at gemme position af de mindste én, der bare kommer til at være i. Så nu Jacob er tilfreds. Vi har ting, der er gemt. Og nu er vi nødt til at se igennem den usorterede del af array. Så i dette tilfælde ville være vores usorteret. Det er jeg. OK. 

Så hvad vi skal gøre kommer til at være for en løkke. Når du skal gentage gennem et array, dit sind kan gå til for en løkke. Så for nogle int k equals-- hvad tror vi k vil lig at starte med? Dette er, hvad vi har sat som vores mindste værdi, og vi ønsker at sammenligne det. Hvad ønsker vi at sammenligne det til? Det kommer til at være den næste ene, right? Så vi ønsker k skal initialiseres til i plus 1 for at starte. 

Og vi vil k vi i dette tilfælde allerede har størrelse gemt op her, så vi kan bare bruge størrelse. Størrelse er størrelsen af ​​array. Og vi ønsker blot at opdatere k med en hver gang. Cool. Så nu er vi nødt til at finde det mindste element her. Så hvis vi gennemløber, vi ønsker at sige, hvis matrix ved k er mindre end vores mindste value-- dette er, hvor vi er faktisk holde styr på, hvad der er den mindste her-- så vi ønsker at overflytte hvad vores mindste værdi. 

Det betyder, at, åh, vi er iteration igennem her. Uanset værdien her er ikke vores mindste ting. Vi vil ikke have det. Vi ønsker at overflytte det. Så hvis vi omfordeling det, hvad gør du tror kunne være i denne kode? Vi ønsker at overflytte mindste og position. Så hvad er mindste nu? STUDENT: Array k. Instruktør: Array k. Og hvad er position nu? Hvad er indekserne for vores mindste værdi? Det er bare k. Så matrix k, k, de passer sammen. Så vi ønskede at tilknytte den. Og så efter vi fandt vores mindste, så i slutningen af ​​denne for-løkke her har vi fundet, hvad vores mindste værdi, så vi bare bytte det. I dette tilfælde, ligesom sige vores mindste værdi er herude. Dette er vores mindste værdi. 

Vi ønsker blot at bytte det her, som er hvad det swap funktion nederst gjorde, som vi lige har skrevet op sammen et par minutter siden. Så det burde virke bekendt. Og så vil det bare gentage igennem, indtil den når hele vejen til enden, hvilket betyder at man har nul elementer, usorterede og alt andet er blevet sorteret. Mening? Lidt mere konkret? Koden hjælp? 

STUDENT: For en størrelse, du aldrig virkelig definere det eller ændre det, hvordan ser det vide? 

Instruktør: Så én ting at mærke op her er int størrelse. Så vi siger i denne sort-- slags er en funktion i denne case-- det udvælgelse slags, er det gået i med funktionen. Så hvis det ikke blev passeret i, ville du gøre noget ligesom med længden af ​​array eller du ville gentage gennem at finde længden. Men fordi det er bestået i, kan vi bare bruge det. Du skal bare antage, at brugeren gav dig en gyldig størrelse, faktisk repræsenterer en størrelse på dit array. Cool? 

Hvis du fyre har nogen problemer med disse eller ønsker mere praksis kodning sorterer på egen hånd, bør du gå til study.cs50. Det er et værktøj. De har en brik, der du kan faktisk skrive. De gør pseudokode. De har flere videoer og dias herunder dem, jeg bruger her. Så hvis du stadig føler en lidt fuzzy, prøv det ud. Som altid, kommer tale med mig, også. Spørgsmål? 

STUDENT: Siger du, at det størrelse er tidligere defineret? Instruktør: Ja. Størrelsen tidligere defineret op her i funktionen erklæring. Så du antager, at det er blevet vedtaget i af brugeren, og for nemheds skyld, vi kommer til at antage, at den bruger gav os den rigtige størrelse. Cool. Så det er udvælgelse slags. Gutter, jeg ved, at vi er ved at lære en masse i dag. Det er en tæt data for afsnit. Så med dette, vil vi at gå til indsættelse slags. 

OK. Så før at vi har at gøre vores runtime analyse her. Så i bedste fald, ydet siden jeg viste dig tabellen jeg allerede slags gav det væk. Men bedste fald runtime, hvad mener vi? Alt sorteres. N potens. Nogen der har en forklaring for hvorfor du tror? 

STUDENT: du sammenligner through-- Instruktør: Right. Du sammenligner igennem. Ved hver iteration, selvom vi decrementing dette ved en, du stadig søge gennem alt for at finde den mindste. Så selvom din mindste værdi er her i begyndelsen, du stadig sammenligne det mod alt andet at sikre, at det er den mindste ting. Så du ender med at løbe igennem ca n kvadreret gange. Ok. Og hvad er det værste tilfælde? Også n kvadreret fordi du vil at gøre det samme procedure. Så i dette tilfælde, udvælgelse slags har noget at vi også kalder forventet runtime. Så i de andre, vi bare vide de øvre og nedre grænser. Afhængigt af, hvordan crazy vores listen er eller hvor usorteret det er, de varierer mellem n eller n potens. Vi ved det ikke. 

Men fordi valg Sorter har samme værste og bedste fald, der fortæller os, at uanset hvilken type af input, vi have, uanset om det er helt sorteret eller helt omvendt sorteret, er det kommer til at tage den samme mængde tid. Så i dette tilfælde, hvis du husker fra vores bord, det faktisk havde en værdi, disse to former ikke har, som forventes runtime. Så vi ved, at når vi kører udvælgelse sortere, det er garanteret til køre en n kvadrerede tid. Der er ingen variation der. Det er bare forventet. Og igen, hvis du ønsker at lære mere, tage CS 124 i foråret. Ok. Vi har set denne ene. Cool. Så insertion slags. Og jeg sandsynligvis vil at blaze gennem dette. Jeg vil ikke have jer kode det. Vi vil bare gå igennem det. Så Indsættelsessortering er venlig af tilsvarende selektion slags i, at vi har både en usorteret og sorteret del af array'et. 

Men hvad der er anderledes, er, at som vi går igennem én efter én, vi bare tage, hvad nummer er næste i vores usorteret, og korrekt sortere det ind i vores sorterede array. Det vil give mere mening med et eksempel. Så alt starter som usorteret, ligesom med udvælgelse slags. Og vi kommer til at sortere dette i stigende rækkefølge, som vi har været. Så på vores første pass vi tager den første værdi og vi siger, OK, du er nu på en liste ved dig selv. 

Fordi du er på en liste ved dig selv, du er sorteret. Tillykke til at være den første element i denne matrix. Du er allerede ordnet alt på egen hånd. Så nu har vi en ordnet og en usorteret array. Så nu tager vi det første. Hvad sker der mellem her og her er, at vi siger, OK, vi kommer til at se på første værdi af vores usorteret matrix og vi kommer til at indtaste det i sin korrekte sted i den sorterede array. 

Så det, vi gør, er vi tager 5 og vi siger, OK, 5 er større end 3, så vi bare indsætte det rigtige til højre for denne. Vi er gode. Så går vi videre til vores næste. Og vi tager 2. Vi siger, OK, 2 er mindre end 3, så vi ved, at det skal være på foran vores liste nu. Så hvad vi gør, er vi skubber 3 og 5 ned og vi bevæger 2 ind i den første spalte. Så vi bare at indsætte den i det rigtige sted, det bør være. 

Så ser vi på vores næste, og vi siger 6. OK, 6 er større end alt i vores sorterede array, så vi bare mærke det på enden. Og så ser vi på 4. 4 er mindre end 6, er det mindre end 5, men det er større end 3. Så vi bare indsætte den helt ud midt mellem 3 og 5. Så for at gøre det lidt lidt mere konkret, Her er lidt af det idé om, hvad der skete. Så for hver usorteret element, vi bestemme, hvor i den sorterede portion det er. 

Så under hensyntagen til den sorteret og usorteret, Vi er nødt til at krydse gennem og figur ud af, hvor det passer ind i den sorterede array. Og vi indsætter det ved at flytte elementer til højre for det ned. Og så har vi bare holde iteration igennem, indtil vi har en helt sorteret liste hvor usorteret er nu nul og sorterede fylder helhed af vores liste. Så igen, for at gøre tingene selv mere konkret, har vi pseudokode. 

Så dybest set, for jeg er lig med 0 til n minus 1, det er bare længden af ​​vores array. Vi har et element, der er lig med den første matrix eller de første indeks. Vi satte j svarende til det. Så mens j er større end nul, og array, j minus 1 er større end element, så alt det der gør er at sikre, at Deres j virkelig repræsenterer usorteret del af array. 

Så mens der er stadig ting at sortere og j minus én is-- hvad er det element hende? J blev aldrig defineret her. Det er lidt irriterende. OK. Alligevel. Så j minus 1, er du tjekker elementet før det. Du siger, OK, er det element, før hvor jeg am-- lad os faktisk trække det ud. Så lad os sige det er ligesom på vores andet gennemløb. Så jeg kommer til at være lig 1, som er her. 

Så jeg kommer til at være lig med 1. Dette ville være 2, 4, 5, 6, 7. Ok. Så vores element i denne sag vil være lig 4. Og vi har nogle j, der er vil være lig med 1. Åh, er j decrementing. Det er, hvad det er. Så j er lig med i, så hvad det er siger er, at når vi bevæger os fremad, vi bare sørge for at vi er ikke ovre indeksere denne måde, når vi prøver at indsætte ting ind i vores sorteret liste. 

Så når j er lig med 1 i denne sag, og matrix j minus en-- så matrix j minus 1 er 2 i denne case-- hvis det er større end det element, så alt dette gør er ved at flytte tingene ned. Så i dette tilfælde, matrix j minus én ville være opstilling nul, hvilket er 2. 2 ikke er større end 4, så det betyder ikke udføre. Så skiftet ikke bevæger sig ned. Hvad dette betyder her er bare flytte din sorterede række ned. I dette tilfælde faktisk, vi kunne do-- lad os gøre dette 3. Så hvis vi skal gå igennem med dette eksempel, er vi nu her. Dette er sorteret. Dette er usorteret. Cool? Så jeg er lig med 2, så vores element er lig med 3. Og vores j er lig med 2. Så vi ser igennem, og vi sige, OK, er matrix j minus én større end elementet at vi kigger på? Og svaret er ja, right? 4 er større end 3 og j er 2, så denne kode udfører. 

Så nu, hvad vi gør et array på 2, så lige her, vi bytte dem. Så vi bare sige, OK, matrix ved 2 er der nu kommer til at være 3. Og j vil være lig j minus 1, som er 1. Det er forfærdeligt, men jer får den idé. J er nu lig med 1. Og array j er bare at være svarende til vores element, som var 4. Jeg slettet noget skulle jeg ikke har eller miswrote noget, men du fyre får den idé. 

Det bevæger sig n. Og derefter, hvis dette var, ville det loop igen, og det vil sige, OK, j er 1 nu. Og array j minus 1 er nu 2. Er 2 mindre end vores element? Nej? Det betyder, at vi har indsat dette element i det rigtige sted i vores sorterede array. Så kan vi tage dette, og vi siger, OK, vores sorterede array er her. Og det ville tage dette nummer 6 og være ligesom, OK, er 6 mindre end dette antal? Nej? Cool. Vi er fine. 

Gøre det igen. Vi siger 7. Er 7 mindre end i slutningen vores sorterede array? Nej. Så vi er fint. Så det ville blive sorteret. Dybest set alt dette gør Det siger take det første element i usorteret array, regne ud, hvor det går i dit sorterede array. Og dette blot tager sig af swaps til at gøre det. Du er dybest set bare bytte indtil det er på det rigtige sted. Den visuelle billede er, at du er bevæger sig alt ned ved at gøre det. 

Så det er ligesom halv Boblesortering-esque. Tjek undersøgelse 50. Jeg anbefaler stærkt, forsøger at kode dette på egen hånd. Hvis du har nogen spørgsmål eller du ønsker at se prøve kode for en Indsættelsessortering, så lad mig det vide. Jeg er altid rundt. Så worst case runtime og bedste fald runtime. Som du guy så fra bordet jeg allerede viste dig, er det både n kvadreret og n. 

Så venlig at gå ud over, hvad vi talte omkring med vores tidligere sorterer, værst tilfælde runtime er, at hvis Det er helt usorterede, vi nødt til at sammenligne alle disse n gange. Vi gør en hel masse sammenligninger fordi hvis det er i omvendt rækkefølge, vi kommer til at sige, OK, dette er den samme, det er godt, og dette skal sammenlignes mod den første til at blive flyttet tilbage. Og da vi kommer hen enden, har vi at sammenligne, sammenligne og sammenligne mod alt. 

Så det ender med at blive ca n potens. Hvis det er korrekt, så du sige, OK, 2, du er god. 3, du er i forhold til 2. Du er god. 4, skal du blot sammenligne med halen. Du er god. 6, sammenligne med halen, er du fint. Så for hver plet, hvis det allerede er sorteres, du gør en sammenligning. Så det er bare n. Og fordi vi har et best case runtime n og en worst case runtime n kvadreret, har vi ingen forventede runtime. 

Det bare afhænger af kaos på vores liste der. Og igen, en anden graf og en anden tabel. Så forskelle mellem slags. Jeg skal bare til at brise gennem, jeg føle, at vi har talt udførligt om, hvordan de alle slags af variere og linke sammen. Så Mergesort er den sidste Jeg skal kede jer med. Vi har en temmelig farverigt billede. Så Mergesort er en rekursiv algoritme. Så tror du fyre vide, hvad en rekursiv funktion er? 

Enhver, der ønsker at sige? Du ønsker at prøve? Så en rekursiv funktion er kun en funktion, der kalder sig selv. Så hvis du fyre kender med Fibonacci-sekvens, der er anses for rekursiv fordi du tager de to foregående og tilføje dem sammen at få din næste. Så rekursive, jeg tror altid rekursion som som en spiral så du er ligesom en spiral ned i den. Men det er bare en funktion der kalder sig. 

Og faktisk, virkelig hurtigt jeg kan vise dig, hvad der ligner. Så rekursive her, hvis vi ser, det er rekursive måde at opsummere over en array. Så alt, hvad vi gør, er vi har funktion sum sum, der tager en størrelse og et array. Og hvis du bemærker, størrelse formindskelser af en hver gang. Og alt det gør er, hvis x er lig med zero-- så hvis størrelsen af ​​array er lig med zero-- det returnerer nul. 

Ellers summerer dette sidste element i arrayet, og derefter tager en sum af resten af ​​arrayet. Så det er bare at bryde det ned i mindre og mindre problemer. Lang historie kort, rekursion, funktion, der kalder sig selv. Hvis det er alt, hvad du fik ud af dette, det er, hvad en rekursiv funktion er. Hvis du tager 51, vil du få meget, meget komfortabel med rekursion. Det er virkelig cool. Det gav mening på ligesom 03:00 en nat ud. Og jeg var ligesom, hvorfor har jeg aldrig bruge dette? 

Så for Mergesort, dybest set hvad det kommer til at gøre, er at det er kommer til at bryde det ned og bryde det ned, indtil det er bare enkelte elementer. De enkelte elementer er let at sortere. Vi ser, at. Hvis du har et element, det er allerede overvejet sorteres. Så på en indgang af n elementer, hvis n er mindre end 2, bare vende tilbage, fordi det betyder det er enten 0 eller 1, som vi har set. De anses sorterede elementer. 

Ellers bryde det i halve. Sorter første halvdel, sortere det andet halve, og derefter flette dem sammen. Hvorfor det hedder Mergesort. Så vi har her vi skal sortere disse. Så vi holder have dem indtil array-størrelse er 1. Så når det er 1, vi bare tilbage fordi dette er en sorterede array, og dette er en sorterede array, og det er en sorteret array, vi alle sorteret. Så hvad vi gør, er vi begynde at sammenlægge dem sammen. 

Så den måde, du kan tænke sammenlægning er du bare fjerne den mindre antal af hver af de sub arrays og bare tilføje det til opstået array. Så hvis du ser her, når vi har disse sæt har vi 4, 6 og 1. Når vi ønsker at fusionere disse, vi ser på disse to første og vi siger, OK, 1 er mindre, det går til fronten. 4 og 6, der er intet at sammenligne det til, bare tag det på til enden. 

Når vi kombinerer disse to, vi bare tage den mindste af disse to, så det er 1. Og nu tager vi mindste af disse to, så 2. Mindste af disse to, 3. Mindste af disse to, 4, 5, 6. Så du bare trække ud disse. Og fordi de har blevet sorteret tidligere, du bare har én sammenligning, hver gang der. Så mere kode her, bare repræsentation. Så du starter på midten og du sortere venstre og højre og så skal du bare flette dem. 

Og vi har ikke kode for fusionere lige her. Men igen, hvis du går på studere 50, vil det være der. Ellers kommer tale med mig hvis du stadig forvirret. Så cool ting her er, at bedste fald worst case, og forventede driftstid er alle i log n, som er langt bedre, end vi har ses for resten af ​​vores slags. Vi har set n kvadreret og hvad vi rent faktisk får her er n log n, som er fantastisk. 

Se på, hvor meget bedre det er. Sådan en nice kurve. Så meget mere effektiv. Hvis du nogensinde kan, brug Mergesort. Det vil spare dig tid. Så igen, da vi sagde, hvis du ned i denne lavere region, det gør ikke, at meget af en forskel. Du får op til flere tusinde og tusindvis af input, du helt sikkert vil have en mere effektiv algoritme. Og igen, vores dejlige tabel over alle slags, der du fyre lært i dag. 

Så jeg ved, det har været en tæt dag. Dette er ikke nødvendigvis vil at hjælpe dig med din pset. Men jeg vil bare gøre en erklæring om ansvarsfraskrivelse dette afsnit handler ikke kun om psets. Alt dette materiale er fair spil til dine midterms. Og også hvis du fortsætte med CS, disse er virkelig vigtige nøgletal at du behøver at vide. Så nogle dage vil være en lidt mere pset hjælp, men nogle uger vil være meget mere faktiske indhold der måske ikke synes super nyttige for dig lige nu, men jeg lover, hvis du fortsætter på vil være meget, meget nyttig. 

Så det er det for sektionen. Ned til ledningen. Jeg gjorde det inden for et minut. Men der du går. Og jeg vil have donuts eller slik. Er der nogen allergisk over for noget, ved den måde? Æg og mælk. Så donuts er et nej? OK. Ok. Chokolade nej? Starburst. Starbursts er god. OK. Vi bliver nødt til Starburst næste uge derefter. Det er, hvad jeg får. Du fyre har en stor uge. Læs din spec. 

Lad mig vide, hvis du har spørgsmål. Pset to karakterer skal være ud til dig af torsdag. Hvis du har spørgsmål om hvordan jeg sorterede noget eller hvorfor jeg sorterede noget den måde, jeg gjorde, så skriv til mig, kom tale med mig. Jeg er lidt crazy dette uge, men jeg lover Jeg vil stadig svare inden for 24 timer. Så har en stor uge, alle. Held og lykke på din pset.