[MUSIK SPELA] 

ANDI PENG: Välkommen till vecka 3 i avsnitt. Tack, ni, för alla kommande till detta tidigare starttid idag. Vi har en fin, lite intim grupp idag. Så förhoppningsvis kommer vi till finish, kanske, tidigt, lite tidigt idag. Så snabbt, bara några meddelanden till dagordning i dag. Innan vi börjar, vi är kommer att bara gå över några korta logistiska frågor, pset frågor, utfråga, sånt. Och sedan ska vi dyka rätt i. Vi kommer att använda en avlusare kallas GDB till börja avslöja vår kod, som David förklaras i föreläsning häromdagen. Vi kommer att gå igenom de fyra typer av slag. Vi kommer att gå igenom dem ganska snabbt eftersom de är ganska intensiv. Men vet att alla bilder och källkod är alltid online. Så känn dig fri på din läsning, till gå tillbaka och ta en titt på det. 

Vi ska gå igenom asymptotisk notation, som är bara ett fint sätt att säga "drifttider" där vi har den stora O, som David förklaras i föreläsning. Och vi har också Omega, som är den nedre gränsen körning. Och vi kommer att prata lite mer djupgående om hur de arbete. Och slutligen, kommer vi att gå över binär sökning, eftersom en hel del av er som redan har sneglade på dina psets vet förmodligen att det är en fråga som är i pset. Så du kommer alla vara glad som vi täcker denna dag. 

Och slutligen, per din avsnitt feedback, jag faktiskt vänster ca 15 minuter vid slutet för att bara gå över logistiken för pset3, frågor, kanske lite vägledning, om ni så vill, innan vi börja programmera. Så låt oss försöka få igenom materialet ganska snabbt. Och då kan vi tillbringa lite tid ta fler frågor för pset. OK. 

Snabbt, så det är bara ett fåtal meddelanden innan vi börjar idag. För det första, välkommen att göra det genom två av dina psets. Jag tog en titt på your-- ja, låt oss få en applåd för att en. Faktiskt, jag var riktigt, verkligen imponerad. Jag graderade första pset för er förra veckan och ni gjorde otroligt. 

Style var på punkt förutom några kommentarer. Se till att du alltid kommentera din kod. Men dina psets var på punkt. Och hålla den. Och det är bra för grader till se att ni sätter i så mycket ansträngning i din stil och din design i din kod att vi skulle vilja för dig att se. Så jag passerar längs min tacksamhet för resten av TAS. 

Men det finns en några utfråga frågor Jag vill bara gå över den skulle göra både mitt liv och en hel del av den andra Resebyråerna liv lite lättare. För det första har jag märkt detta Tidigare week-- hur många av er har varit igång check50 på din kod innan du skickar? OK. Så alla borde göra check50, because-- en secret-- vi faktiskt köra check50 som en del av vår riktighet skript för att testa din kod. Så om din kod misslyckas check50, med all sannolikhet, det förmodligen kommer att misslyckas vår kontroll samt. Ibland ni har de rätta svaren. Liksom i girig, en del av du har rätt nummer, du bara skriva ut lite extra grejer. Och det extra grejer faktiskt misslyckas kontrollen, eftersom datorn inte riktigt vet vad det är du letar efter. Och så kommer det att bara köra igenom, se till att utskrifterna inte matchar vad vi förväntar oss svaret att vara, och markera det är fel. 

Och jag vet som hände i några av dina ärenden denna vecka. Så jag gick tillbaka och manuellt omklassificerade allas kod. I framtiden om, snälla, vänligen se att du kör kontrollera 50 på din kod. Eftersom det är lite av en smärta för TA att behöva gå tillbaka och manuellt omklassificering varenda pset för varje singel, lite missade exempel. Så jag tog bort några poäng. Jag tror att jag tog fart kanske en eller två för design. I framtiden men om du inte check50, punkter kommer att tas off för korrekthet. 

Vidare psets är på grund fredagar kl. Jag tror att det finns en sju minuters sen grace period som vi ger dig. Per Harvard tid, de är tillåtet att sju minuter sent till allt. Så här vid Yale, vi ska ansluta sig till det också. Men ganska mycket, på 0:07, Om din pset inte är i, det kommer att märkas så sent. Och så även om det är märkt så sent, det TA-- jag fortfarande kommer att klassificera dina psets. Så du fortfarande se en klass visas. Men vet att vid I slutet av terminen, alla sena psets kommer bara vara automatiskt nollställs av datorn. 

Vi gör detta av två skäl. En, ibland får vi ursäktas, liksom prostens ursäkter, senare att jag inte vet om ännu. Så vi vill se till att vi ska klassificera allt bara i fall som jag är saknade en dekanus ursäkt. Och för det andra, kom sinne, kan du fortfarande släppa en pset som har full omfattning poäng. Och så vi vilja klass alla dina psets bara att se till att din oscilloskops där och du försöker dem. Så även om det är sent, kommer du fortfarande få kredit för räckvidd punkter, tror jag. 

Så Sensmoralen i historien är, gör att dina psets är i tid. Och om de inte är i på-tid, vet att det inte är bra. Ja, innan jag går vidare, någon som har frågor om pset synpunkter? Yeah. 

PUBLIK: Sa du att vi kan släppa en av de psets? 

ANDI PENG: Ja. Så det finns nio psets övergripande under loppet av terminen. Och om du har räckvidd points-- så räckvidd är bara, ganska mycket, är du försöker den problem, du sätter i tid, visar du att du har visade du har läst spec. Det är ganska mycket utrymme. Och om du uppfyller scope punkter, vi kan släppa lägsta en av fritt spelrum. Så det är i din fördel att fylla i och prova varje pset. 

Även upload-- om ingen av dem att fungera, ladda upp dem alla. Och sedan kommer vi förhoppningsvis att kunna ge er några av dessa punkter tillbaka. Häftigt. Alla andra frågor? Bra. 

För det andra hours-- några kontor snabba anteckningar om kontorstid. Så först, kom i början av veckan. Ingen är någonsin på kontorstid på måndagar. Christabel kom till kontorstid i natt. Ja, Christabel. Och vad gjorde vi har på kontoret timmar i natt, Christabel? 

PUBLIK: Vi hade Glass. 

ANDI PENG: Så det är rätt, vi hade Glass på kontorstid i går kväll. Även om jag inte kan lova er att Vi kommer att ha glass på kontorstid varje vecka, vad jag kan lova dig är att det kommer att finnas en signifikant bättre elev TA förhållande. Liksom legit, det är som 3-1. Medan kontrast som med Torsdag, har du ca 150 verkligen stressade barn och ingen Glass. Och det är inte produktivt för någon. Så Sensmoralen i historien är, kom tidigt till kontorstid och bra saker kommer att hända. 

Dessutom kommer beredd att ställa frågor. Du vet? Oavsett vad resebyråerna, jag tror, ​​har sagt, Vi har fått ett par studenter som kommer på torsdag på, liksom, 10:50 inte ha läst spec vara som hjälp mig, hjälp mig. Tyvärr vid denna tidpunkt, det finns inte mycket vi kan göra för att hjälpa dig. Så kom gärna i början av veckan. Kom tidigt till kontorstid. Kom beredd att ställa frågor. Se till att du, som en student, är där du måste vara så att Resebyråerna kan guida dig längs, vilket är vad kontorstid bör tilldelas för. 

För det andra, så jag vet professorer gillar att överraska oss med tester. Jag hade en professor som som, omslag, förresten, kom ihåg att halva tiden du har nästa måndag. Ja, jag visste inte om det midterm. Så jag kommer att vara att TA som påminner dig allt frågesport 0-- eftersom du vet, vi är CS. Nu när vi har gjort uppsättningar, får du varför det är quiz 0, inte quiz 1, va? OK. Åh, jag fick några skratt på att en. OK. 

Så quiz 0 blir 14 oktober om du är i måndag-onsdag sektionen och 15 oktober om du är i tisdag-torsdag avsnitt. Detta gäller inte för de av er vid Harvard who-- Jag tror att du kommer alla vara ta dina frågesporter på den 14: e. 

Så ja, nästa vecka, om David, i föreläsning, går, Ja, så om det quiz nästa vecka, ni alla kommer inte bli chockad eftersom du kom till avsnitt och du vet att din quiz 0 i två veckor. Och vi ska ha recension sessioner och allt. Så ingen oro vara rädd för det. Eventuella frågor before-- frågor på alla som rör logistiska problem, betygs, kontorstid, avsnitt? Yeah. 

PUBLIK: Så testet är kommer att vara under föreläsning? 

ANDI PENG: Ja. Så frågesport, tror jag, är 60 minuter tilldelade i denna tidslucka att du bara tar i föreläsningssalen. Så du behöver inte komma in på, som en slumpmässig 07:00. Allt är bra. Yeah. Häftigt. 

Okej. Så vi kommer att införa ett koncept för dig den här veckan att David har redan slag av berörs i föreläsning i förra veckan. Det kallas GDB. Och hur många av er, medan Under skriva dina psets, har märkt en stor knapp som säger "Debug" på toppen av din IDE? OK. Så nu ska vi faktiskt får gräva mysterium vad den knappen faktiskt gör. Och jag garanterar dig, det är en vacker, vacker sak. 

Så fram till nu, tror jag Det har varit två saker studenter har varit typiskt gör när felsökning psets. En, de antingen lägga in printf () - så var några rader, de lägger i en printf () - åh, vad är denna variabel? Åh, vad är denna variabel now-- och du typ av se progressionen av din kod som körs. Eller den andra metoden barn gör är att de bara skriver det hela och sedan gå så här i slutet. Förhoppningsvis fungerar det. Jag garanterar dig, är bättre GDB än båda dessa metoder. Yeah. Så det här kommer att vara din nya bästa vän. Eftersom det är en vacker sak som visuellt visar både vad din kod gör vid en specifik punkt liksom vad alla dina variabler bärande, precis vad deras värderingar är, vid denna punkt. Och på det här sättet, kan du verkligen ange brytpunkter i koden. Du kan gå igenom rad för rad. Och GDB kommer bara för dig, visas för dig, vad alla dina variabler är, vad de gör, vad som händer i koden. Och på ett sådant sätt, är det så mycket lättare att se vad som händer i stället för printf-ing eller skriva ner dina uttalanden. 

Så vi kommer att göra ett exempel på detta senare. Så detta verkar lite abstrakt. Inga bekymmer, ska vi göra exempel. Och så i huvudsak, de tre största, mest använda funktioner som du behöver i GDB är nästa, steg över, och Kliv in knapparna. Jag kommer att gå över där, faktiskt, just nu. 

Så kan ni alla se att eller ska jag in i en bit? I ryggen, kan du se det? Ska jag zooma in? Bara lite? OK bra. Det går vi. OK. 

Så jag har här, min genomförande för giriga. Och medan en hel del av er skrev giriga i while-slinga form-- att är ett fullt godtagbart sätt att göra det-- ett annat sätt att göra det är att helt enkelt dela i modulo. För då kan du ha din värde och sedan har din resten. Och då kan du bara lägga ihop allt. Har logiken i det jag gör här vettigt för alla, innan vi börjar? Ungefär? Häftigt. Bra. Det är en ganska sexig pjäs kod, skulle jag säga. Som jag sa, David, i föreläsning, efter en stund, ni kommer att börja se kod som något som är vackert. Och ibland när du ser vackra kod, är det en underbar känsla. 

Så dock medan denna kod är mycket vacker, det fungerar inte på rätt sätt. Så låt oss köra check50 på detta. Kontrollera 50 20-- oop. 2? Är det pset2? Yeah. Åh, pset1. OK. Så vi kör check50. 

Och som ni kan se här, det är inte ett par fall. Och för vissa av er, i kurs för att göra dina problem uppsättningar, du är som, ah, varför det inte fungerar. Varför det fungerar för vissa värden men inte för andra? Tja, GDB kommer att hjälpa dig att räkna varför dessa ingångar inte fungerade. 

OK. Så låt oss se, en av de checkar jag misslyckas i check50 var ingångsvärdet på 0,41. Så det rätta svaret att Du bör få en fyra. Men i stället vad jag skriva ut Detta är ett 3-n, som är felaktig. Så låt oss bara köra manuellt, bara se till att check50 fungerar. Låt oss göra ./greedy. Oops, jag måste göra giriga. Det går vi. Nu ./greedy. 

Hur mycket är skyldig? Låt oss göra 0,41. Och japp, ser vi här att det är utmatning 3 När det rätta svaret, i själva verket borde vara fyra. Så låt oss gå in GDB och se hur vi kan gå om fastställande av det här problemet. 

Så det första steget i alltid felsökning din kod är att sätta en brytpunkt, eller en punkt där du vill att datorn eller debugger för att börja titta på. Så om du inte riktigt vet vad ditt problem är, vanligtvis, den typiska sak som vi vill göra är att ställa vår brytpunkt vid huvud. Så om ni kan se här röda knappen just där, Japp, det var inställningen mig brytpunkt för huvudfunktionen. Jag klickar på den. 

Och då kan jag gå upp till min Debug knappen. Jag slog den knappen. Låt mig in igen om jag kan. Det går vi. Så vi har här, en panel till höger. Jag är ledsen, killar i ryggen, du kan inte riktigt se riktigt bra. Men i huvudsak alla denna högra panelen gör är att hålla reda på både den markerade linje, som är den kodrad att datorn är igång, liksom alla dina variabler här nere. 

Så du har fått cent, mynt, n, alla förklarats olika saker vid denna punkt. Inga problem, eftersom vi inte har faktiskt initieras dem till några variabler än. Så i datorn, dator är bara att se, åh, 32767 var den senast använda funktionen av det minnesutrymme i min dator. Och så det är där cent för närvarande är. Men ingen att när du kör koden, Det bör bli initierad. 

Så låt oss gå igenom, rad för linje, vad som händer här. OK. Så här uppe är de tre knappar som jag förklarade bara. Du har Play eller Kör funktionen, knappen, har du steg över knappen, och du har också steget in knappen. Och i huvudsak, alla tre dem bara gå igenom din kod och göra olika saker. 

Så typiskt, när du felsökning, Vi vill inte bara trycka Play, eftersom Play kommer bara köra koden till slutet av det. Och då kommer du faktiskt inte vet vad ditt problem är om du ställer in flera brytpunkter. Om du ställer in flera brytpunkter, Det kommer bara automatiskt löpa från en brytpunkt, till nästa, till nästa. Men i detta fall vi har bara att man, eftersom vi vill arbeta vårt sätt uppifrån ned till botten. Så vi kommer att ignorera den knappen just nu för detta program. 

Så Step over funktion bara steg över varje enda rad och talar om för dig vad datorn gör. Step in funktionen går i själva funktionen det är på din kodrad. Så till exempel, som printf (), som är en funktion, eller hur? Om jag ville fysiskt steg in printf () -funktionen, Jag skulle faktiskt gå in i bit koden där printf () skrevs och se vad som händer där. 

Men typiskt, antar vi att den kod som vi ger dig fungerar. Vi antar printf () fungerar. Vi antar att getInt () fungerar. Så det finns ingen anledning att kliva in i dessa funktioner. Men om det finns funktioner att du skriver själv som du vill kontrollera reda på vad som händer, du skulle vilja steg i denna funktion. 

Så just nu vi ska bara att kliva över denna del av koden. Så låt oss se. Åh, skriva ut, "Oh hai, hur mycket förändring är skyldig? " Vi bryr oss inte. Vi vet att det fungerar, så vi kliver över den. 

Så n, som är vår flottör som vi har initialized-- eller declared-- upp på toppen, vi är nu equaling att till getFloat (). Så låt oss kliva över det. Och vi ser på botten här, programmet är vilket fick mig att mata in ett värde. Så låt oss mata in värde som vi vill till testet här, vilket är 0,41. Bra. 

Så nu n-- gör ni se här, vid bottom-- det är stored-- eftersom vi har inte rundade ännu, är det lagras i detta som jätte flottör som är 0,4099999996, som är tillräckligt nära vår ändamål, just nu, till 0,41. Och sedan får vi se senare, när vi fortsätta kliva över programmet, efter här, har n blivit rundade och cent har blivit 41. Bra. Så vi vet att vår avrundning fungerar. Vi vet att vi har rätt antal cent, så vi vet att det är inte riktigt problemet. 

Så vi fortsätter att kliva om i det här programmet. Vi går här. Och så efter den här kodraden, vi bör veta hur många kvartal vi har. Vi kliver över. Och ni ser vi, i själva verket har en kvartal eftersom vi har subtraheras 25 från vår initiala värdet av 41. Och vi har 16 kvar för våra cent. 

Förstår alla hur programmet stega igenom och varför cent har nu blivit 16 och varför nu, mynt har blivit en? Är alla som följer logiken? Häftigt. Så från och med denna punkt, programmets arbete, rätt? Vi vet att det gör exakt vad vi vill. Och det gjorde vi faktiskt inte måste skriva ut, åh, vad är cent på denna punkt, Vad är mynt på denna punkt. 

Vi fortsätter att gå igenom programmet. Kliva över. Häftigt. Vi går över Dimes. Bra. Vi ser att det har tagit rabatt $ 0,10 för en krona. Och nu har vi två mynt. Det stämmer. 

Vi går över pennies och vi ser att vi har kvar över cent. Hmm, det är konstigt. Här uppe på programmet, skulle jag ha dras mina slantar. Kanske jag var bara inte gör den linjen till höger. Och tyvärr, kan du se här, eftersom vi vet att vi trappar genom ledningarna 32 och 33, det är där vårt program felaktigt hade variabler springa. Så vi kan se och se, oh, Jag subtrahera cent här, men jag är faktiskt inte lägga till min myntvärde. Jag lägger till cent. Och jag vill inte lägga till cent, jag vill lägga till mynt. Så om vi ändrar det till mynt, Vi har ett arbetsprogram. Jag kan köra check50. Du kan bara stänga av GDB rätt här och kör sedan check50 igen. Jag kan bara göra detta. Jag måste göra giriga. 0,41. Och här är det utskrift ut det rätta svaret. 

Så när ni kan se, GDB är ett riktigt kraftfullt verktyg för när vi har så mycket kod pågår och så många variabler att det är svårt för oss, som en människa, för att hålla reda på. Datorn, i GDB debugger, har förmågan att hålla reda på allt. Jag vet, i Visionaire, ni förmodligen kanske har drabbat vissa segmente fel eftersom du kör out of bounds på din array. I exemplet på Caesar, det är exakt vad jag har implementerat här. 

Så jag glömde att kontrollera vad som skulle hända om jag behövde två kommandoradsargumenten. Jag bara inte sätta i denna kontroll. Och så om jag kör Debug-- jag in min brytpunkt till höger där. Jag kör Debug. 

OK. Yeah. Så egentligen var GDB tänkt ha sagt mig det var en segmentering fel där. Jag vet inte vad som pågår just där, men när jag körde det, Det fungerade. När du kör rader kod genom och GDB kanske bara plötsligt sluta på dig, gå upp och se vad den röda felet är. Det kommer att berätta för er, hej, du hade en segmentering fel, vilket innebär att du försökte komma åt utrymme i en matris som inte existerade. Yeah. 

Så i nästa problem som denna vecka, ni kommer troligen att ha en hel del variabler som flyter runt. Du kommer inte att vara säker på vad de alla betyder vid en viss punkt. Så GDB kommer verkligen att hjälpa dig att räkna reda på vad de är alla lika och att kunna se att visuellt. Är det någon förvirrad om hur något av det fungerade? Häftigt. Okej. Så efter att vi kommer att dyka rätt i är fyra olika typer av slag för den här veckan. Hur många av er, första av allt, innan vi börjar, har läst hela spec för pset3? OK. Jag är stolt över er. Det är som att hälften av klassen, som är betydligt mer än förra gången. 

Så det är bra, för när vi talar om innehållet i lecture-- eller ledsen, i section-- Jag gillar att relatera en hel del som tillbaka till vad pset är och hur du vill genomföra detta i din pset. Så om du kommer att ha läs spec, det ska vara mycket lättare för dig att förstå vad jag talar om när jag säger, oh hey, kan detta vara en riktigt bra ställe för att genomföra den här typen. Så de av er som har läst spec vet att som en del av pset, du kommer att behöva skriva ett typ av sortering. Så detta kan vara till stor hjälp för många av er idag. 

Så vi ska börja med, huvudsak den mest enkel typ av sortering, val slag. Den typiska algoritm för hur vi skulle gå om detta är-- David gick igenom alla dessa i föreläsning, så jag ska snabbt röra sig längs här-- är i huvudsak, du har en matris av värden. Och sedan hittar minsta osorterade värde och du byta detta värde med den första osorterade värde. Och då du bara fortsätta att upprepa med resten av din lista. 

Och här är en visuell förklaring av hur det skulle fungera. Så till exempel, om vi skulle börja med en uppsättning av fem element, index 0 till 4, med 3, 5, 2, 6, och 4 värden placeras i array-- så just nu, Vi kommer bara att anta att de är alla osorterade eftersom vi har inte testat något annat. 

Så hur ett urval sortera skulle arbete är att det skulle först gå igenom helheten av osorterade array. Det skulle plocka ut det minsta värdet. I detta fall 3, höger nu, är den minsta. Det blir till 5. Nix, 5 inte är större than-- eller ledsen, inte mindre than-- 3. Så det minsta värdet är fortfarande 3. Och sedan får du 2. Datorn ser, oh, två är mindre än 3. 2 måste nu vara det minsta värdet. Och så 2 swappar med det första värdet. 

Så efter ett pass, vi verkligen ser att 2 och 3 byts. Och vi ska bara fortsätta att göra detta igen med resten av matrisen. Så vi kommer att bara köra igenom de sista fyra index i uppsättningen. Vi ser att 3 är nästa minimivärdet. Så vi kommer att byta det med fyra. Och då vi bara kommer att hålla löper genom tills slutligen du komma till en sorterad array där 2, 3, 4, 5, och 6 är alla sorterade. Har alla förstå logiken om hur ett val Sortera fungerar? 

Du har bara någon sorts av ett minimivärde. Du hålla reda på vad det är. Och när du hittar det, byta du det med det första värdet i array-- eller inte första value-- nästa värde i arrayen. Häftigt. 

Så när ni slags såg från en kort glimt, vi kommer att pseudokod detta. Så om ni i ryggen vill bilda en grupp, alla vid ett bord kan bilda en liten partner, jag kommer för att ge dig killar som tre minuter att bara prata igenom logiken, på engelska, hur vi skulle kunna genomföra pseudokod att skriva ett urval slag. Och det finns godis. Kom upp och få godis. Om du är i ryggen och du vill godis, kan jag kasta godis på dig. Egentligen gör du-- cool. Åh förlåt. OK. 

Så om vi vill, som en klass, skriv pseudokod hur man kan närma sig detta problem, bara välkommen. Jag ska bara gå runt och, i ordning, frågar grupper för nästa rad av vad vi borde göra. Så om ni vill starta off, vad är det första att göra när du försöker implementera ett sätt att lösa det här programmet att selektivt sortera en lista? Låt oss bara antar vi har en matris, okej? 

PUBLIK: Du vill skapa några sorts [OHÖRBAR] att du är som löper genom hela din samling. 

ANDI PENG: Rätt. Så du kommer att vilja upprepa genom varje utrymme, eller hur? Så bra. Om ni vill ge mig Nästa line-- ja, i ryggen. 

PUBLIK: Kontrollera dem allt för de minsta. 

ANDI PENG: Det gå vi. Så vi vill gå igenom och kontrollera se vad det minsta värdet är, eller hur? Jag kommer att förkorta det till "min." Vad vill ni göra efter du har hittat det lägsta värdet? 

PUBLIK: [OHÖRBAR] ANDI PENG: Så du kommer att vilja slå på den med den första i nämnda matris, höger? Det är början, jag kommer att säga. Okej. Så nu när du har bytt den första en, vad vill du göra efter det? Så nu vet vi att detta här måste vara det minsta värdet, eller hur? Då har du en ytterligare vila av matrisen som är osorterade. Så vad du vill göra här, om du killar vill ge mig nästa rad? PUBLIK: Så då du vill iterera genom återstoden av uppsättningen. ANDI PENG: Ja. Och så vad iterera genom sorts innebära att vi kommer förmodligen att behöva? Vilken typ of-- 

Målgrupp: Åh, en ytterligare rörlig? ANDI PENG: Förmodligen en annan för loop, eller hur? Så vi förmodligen kommer att vilja att iterera through-- stor. Och då du kommer att gå tillbaka och förmodligen kontrollera minsta igen, höger? Och du kommer att fortsätta att upprepa detta, eftersom slingorna bara gå att hålla igång, eller hur? 

Så när ni kan se, vi bara ha en allmän pseudokod om hur vi vill att det här programmet ska se ut. Denna iterate här, vad gör vi vanligtvis måste skriva i vår kod Om vi ​​vill att iterera genom ett matris, vilken typ av struktur? Jag tror Christabel redan sagt det förut. 

PUBLIK: A för loop. 

ANDI PENG: A för loop? Exakt. Så det här är förmodligen kommer att vara en for-loop. Vad är en check här kommer att innebära? Normalt, om du vill kontrollera om något är något else-- 

PUBLIK: If. 

ANDI PENG: An om, eller hur? Och sedan swap här, vi ska gå över senare, eftersom David gick igenom det i föreläsning också. Och sedan den andra iterate implies-- 

PUBLIK: Another for-loop. 

ANDI PENG: --another for-loop, exakt. Så om vi letar på detta på rätt sätt, vi kan se att vi är förmodligen kommer att behöva en kapslad för loop med en villkorlig uppgift i det och sedan en verklig bit kod som är kommer att byta värden. Så jag har bara allmänt skrivit en pseudokoden här. Och sedan vi faktiskt kommer fysiskt, som klass, försöka genomföra detta i dag. Låt oss gå tillbaka till denna IDE. 

Hoppsan. Varför är det inte-- det är det. OK. Tyvärr, låt mig försöka zooma in lite mer. Det går vi. Allt jag gör här är att jag har skapat ett program som heter "urval / sort.c." Jag har skapat en rad nio värden, 4, 8, 2, 1, 6, 9, 7, 5, 3. För närvarande, som du kan se, de är oordnad. n kommer att vara det antal som säger mängden av värden du har i din samling. I det här fallet har vi nio värden. Och jag har precis fått en for-loop här som skriver ut osorterade array. 

Och i slutet, har jag också fått en för loop som bara skriver ut den igen. Så teoretiskt, om programmet fungerar korrekt, i slutet, bör du se en tryckt for-loop i vilken en, två, tre, fyra, fem, sex, 7, 8, 9 är alla korrekt i ordning. 

Så vi har fått vår pseudokod här. Finns det någon som vill att-- jag bara kommer att gå be om volunteers-- berätta exakt vad jag ska skriva om Vi vill i första hand bara iterera genom början av denna samling? Vad är kodraden jag förmodligen kommer att behöva här? 

PUBLIK: [OHÖRBAR] 

ANDI PENG: Ja, känner gratis att-- ledsen, du behöver inte stå up-- känsla fri att höja rösten lite. 

PUBLIK: För int i lika 0-- 

ANDI PENG: Ja, bra. 

PUBLIK: i är mindre än array längd. 

ANDI PENG: Så kom sinne här, eftersom vi inte har en funktion som berättar längden på en array, vi redan har en värde som lagrar det. Höger? En annan sak att hålla i mind-- i en gruppering nio värden, vilka är index? Låt oss bara säga denna uppsättning var 0-3. Du ser att den sista index är faktiskt tre. Det är inte 4, även om det finns fyra värdena i gruppen. 

Så här måste vi vara mycket försiktiga av vad vårt villkor för längden det kommer bli. 

PUBLIK: Skulle det inte vara n minus 1? ANDI PENG: Det kommer n minus 1, exakt. Låter det vettigt, varför Det är n minus 1, alla? Det beror på arrayer är noll indexeras. De börjar på 0 och köra upp till n minus 1. Ja, det är lite knepigt. OK. Och då-- PUBLIK: Isnt'1 som redan tagit hand om men, genom att bara inte säga "mindre än eller lika med "och bara säga" mindre än? " 

ANDI PENG: Det är en riktigt bra fråga. Så ja. Men också, det sätt som vi är genomförandet av kontroll höger, du behöver för att jämföra två värden. Så du verkligen vill lämna "till" tom. För om du jämför här, du kommer inte har något efter det att jämföra med, eller hur? Yeah. Så jag ++. Låt oss lägga våra parentes. Hoppsan. Bra. Så vi har början av vår yttre slinga. Så nu vill vi förmodligen skapa en variabel för att hålla reda på det minsta värdet, eller hur? Finns det någon som vill ge mig kodrad som skulle göra det? Vad behöver vi om vi ska att vilja lagra något? 

Höger. Kanske ett bättre namn för att skulle be-- "temp" helt works-- kanske en mer passande namnet skulle vara, om vi vill att minsta value-- 

PUBLIKEN: Min. ANDI PENG: min, det går vi. min skulle vara bra. Och så här, vad gör vi vill initiera den till? Detta är lite knepigt. Eftersom just nu på i början av denna array, du inte har tittat på något, eller hur? Så vad, automatiskt, om vi är bara på i lika med 0, Vad vill vi initiera vår första minimivärde till? PUBLIK: i. ANDI Peng: Jag, precis. Christabel, varför vill vi att initiera det i? 

Målgrupp: Jo, ja, Vi börjar med 0. Så eftersom vi har inget att jämföra det kommer minst hamna 0. 

ANDI PENG: Exakt. Så hon är exakt rätt. Eftersom vi har faktiskt inte tittat på något ännu, vi vet inte vad vår minimivärde är. Vi vill bara initiera den till i, som för närvarande är just här. Och när vi fortsätter att flytta ner denna uppsättning, vi får se att med varje extra pass, jag ökar. Och så på den punkten, Jag är förmodligen kommer att vilja vara det minsta, eftersom det kommer att bli allt är början av osorterade array. Häftigt. 

Så nu vill vi att lägga en for-loop här som är kommer att iterera igenom osorterade, eller resten av denna samling. Finns det någon som vill ge mig en kodrad som skulle göra det? Hint-- vad behöver vi här nere? Vad kommer att gå i detta för loop? Yeah. PUBLIK: Så vi skulle vilja har en annan heltal, eftersom vi kör igenom resten av matris i stället för den i:, så kanske j. 

ANDI PENG: Ja, låter j bra för mig. Lika? 

PUBLIK: Så skulle vara i plus 1, eftersom du börjar på nästa värde. Och sedan till end-- så igen, j mindre än n minus 1, och sedan j ++. ANDI PENG: Great. 

Och sedan i här, vi kommer att vilja att kontrollera om våra villkor är uppfyllt, höger? Eftersom du vill ändra det minsta värdet om det är faktiskt mindre än vad du jämför det till, eller hur? Så vad ska vi ha här? Kontrollera att se. Vilken typ av uttalande vi förmodligen kommer ti vill använda om vi vill kontrollera något? 

PUBLIK: En if-sats. 

ANDI PENG: En if-sats. Så if-- och vad som kommer att bli under förutsättning att vi vill ha inne av vår if? 

PUBLIK: Om värdet på j är mindre än värdet av I-- 

ANDI PENG: Exakt. Så if-- så denna array kallas "array." Bra. Så om array-- vad var det? Säga det igen. 

Publik: Om matris-j är mindre än array-i, då skulle vi ändra min. Så min skulle vara j. 

ANDI PENG: Låter det vettigt? OK. Och nu här nere, vi faktiskt vill genomföra swap, eller hur? Så minns i föreläsning, att David, när han försökte byta the-- vad var det-- apelsinjuice och milk-- 

PUBLIK: Det var brutto. 

ANDI PENG: Ja, det var typ av brutto. Men det var en ganska bra koncept som visar tiden. Så tänk på dina värden här. Du har en array av min, en matris av i, eller vad vi försökte byta här. Och du förmodligen inte kan hälla dem i varandra på samma gång, eller hur? Så vad ska vi att behöva skapa här För att byta värden på rätt sätt? 

PUBLIK: En temporär variabel. 

ANDI Peng: En temporär variabel. Så låt oss göra int temp. Se detta skulle vara en bättre tid att-- whoa, vad var det? OK. Så detta skulle ha varit en bättre tid att namnge variabeln "temp." Så låt oss göra int temp. Vad ska vi inställd temp lika med här? PUBLIK: Min? ANDI PENG: Det är lite knepigt. Det faktiskt ingen roll i slutändan. Det spelar ingen roll vad ordning du väljer att byta in så länge du gör att du är hålla reda på vad du byta. 

Publik: Det kan vara matris-i. 

ANDI PENG: Ja, låt oss göra array-i. Och vad är nästa rad kod vi vill ha här? PUBLIK: array-i lika array-j. ANDI PENG: Och slutligen? PUBLIK: array-j är lika med array-i. Målgrupp: Eller array-j jämlikar matris-temp-- eller, temp. 

ANDI PENG: OK. Så låt oss köra det här och se om det kommer att fungera. Var är det som händer? Åh, det är ett problem. Se på rad 40, vi är försöker använda array-j? Men varifrån kommer j finns bara i? 

PUBLIK: I for-slingan. ANDI PENG: Rätt. Så vad ska vi göra? 

PUBLIK: Definiera det utanför the-- Målgrupp: Ja, jag antar att du har att använda en annan if-sats, eller hur? Så liknande, om minimum-- okej, låt mig tänka. 

ANDI Peng: Killar, försök att ta en titt Låt oss se, vad är något som vi kan göra här? 

PUBLIK: OK. Så om minimi inte är lika j-- så om den minsta är fortfarande jag-- då skulle vi inte behöva byta. 

ANDI PENG: Betyder det lika i? Vad vill du säga här? 

PUBLIK: Eller ja, om minimi inte är lika i, ja. ANDI PENG: OK. Tja det löser, typ av våra problem. Men som fortfarande inte löser problemet med vad som händer om j-- sedan j existerar inte utanför den, vad vill du att vi vill göra med det? Förklara det utanför? Låt oss försöka köra detta. Hoppsan. Vår typ fungerar inte. 

Som ni kan se, vår första array hade dessa värden. Och efteråt borde ha varit i en, två, tre, fyra, fem, sex, 7, 8, 9. Dess inte fungerar. Ahh. Vad gör vi? PUBLIK: Debug. ANDI PENG: Okej, kan vi prova det. Vi kan felsöka. Zooma ut en bit. Låt oss ställa vår brytpunkt. Låt oss gå like-- OK. 

Så eftersom vi redan vet att dessa rader, 15 till 22, är working-- eftersom allt jag gör är bara iteration genom och printing-- Jag kan gå vidare och hoppa över det. Låt oss börja på linje 25. Oop, låt mig få bli av med det. 

PUBLIK: Så brytpunkten är där felsökning börjar? ANDI PENG: Eller stannar. PUBLIK: Eller stannar. ANDI PENG: Ja. Du kan ställa in flera brytpunkter och den kan bara hoppa från en till den andra. Men i detta fall vi inte vet där felet händer. Så vi vill bara börja från toppen och nedåt. Japp. OK. 

Så här linjen här, kan vi kliva in. Du kan se här nere, vi har en matris. De är de värden som är i gruppen. Ser du det, hur index 0, det motsvarar value-- oh, Jag ska försöka att zooma in. Tyvärr, det är verkligen svårt att see-- vid fältindex 0, vi har ett värde av 4 och då så vidare och så vidare. Vi har våra lokala variabler. Just nu jag är lika med 0, som vi vill att det ska vara. 

Och så låt oss hålla stega igenom. Vår minsta är lika med 0, som vi vill också att det ska vara. Och sedan går vi vår andra för slinga, om matris-j är mindre än matris-i, vilket det inte var. Så såg du hur som hoppade över det? 

PUBLIK: Så bör if minimum, allt that-- bör inte det vara inne den första för loop? ANDI PENG: Nej, eftersom du fortfarande vill testa. Du vill göra en jämförelse varje tid, även efter att du kör igenom den. Du vill inte bara göra det på den första genomslaget. Du vill göra det med varje extra pass igen. Så du vill söka efter ditt tillstånd inuti. Så vi ska bara hålla igång igenom här. Jag ska ge er en ledtråd. Det har att göra med det faktum att när du kontrollera din villkorligt, du inte kontrollera för rätt index. Så just nu är du kontroll av array index för j är mindre än array index på i. Men vad gör du uppe på början av for-slingan? Är du inte ställa j lika med i? 

Ja, så kan vi faktiskt avsluta debugger här. Så låt oss ta en titt på vår pseudokod. For-- vi ska börjar på i lika med 0. Vi kommer att gå upp till n minus 1. Låt oss kolla, vi har det rätt? Japp, det var rätt. 

Så då inne här, vi är kommer att skapa ett minimivärde och uppsättning som är lika med i. Gjorde vi göra det? Japp, gjorde det. Nu i vår inre for-loop, vi är kommer att göra j lika i till n minus 1. Gjorde vi göra det? I själva verket gjorde vi det. 

Så dock vad vi jämföra här? 

PUBLIK: j plus 1. ANDI PENG: Exakt. Och då du kommer att vilja ställa din minsta lika med j plus 1 också. Så jag gick igenom det riktigt snabbt. Gör ni förstå varför det är j plus 1? OK. 

Så i din samling, i din första passera, din för loop, för int Jag är lika med 0, låt oss bara antar att det har inte ändrats ännu. Vi har en matris med, helt, bara fyra osorterade element, eller hur? Så vi vill initiera jag lika med 0. Och jag kommer att bara köra igenom detta slinga. Och så i det första passet, kommer vi att initiera en variabel som heter "min" som också är lika med i, eftersom vi har inte ett minimivärde. Så det är för närvarande lika med 0 också. Och då kommer vi att gå igenom. Och vi vill iterera igen. Nu när vi har hittat vad vår lägsta vill säga, vi vill iterera genom igen för att se om det är en jämförelse, eller hur? Så j, här, kommer till lika i, som är 0. Och sedan om array j plus i, som är den som är nästa över, som mindre än vad din nuvarande minimi värde är, du vill byta. 

Så låt oss bara säga att vi har fick, liksom, 2, 5, 1, 8. Just nu är jag lika med 0 och j är lika med 0. Och det är vår minimivärde. Om matris-j plus jag-- så om en det är efter den vi tittar på är större än den föregående, det kommer att bli ett minimum. 

Så här ser vi att 5 inte mindre än så. Så det kommer att vara 5. Vi ser att en är mindre än 2, eller hur? Så nu vet vi att vår minsta är kommer att vara indexvärdet vid 0, 1, 2. Yeah? Och sedan när du kommer ner hit, du kan byta korrekta värden. 

Så när ni var bara med j innan, var du inte tittar på en efter det. Du tittar på samma värde, vilket Därför bara inte gjorde någonting. Innebär det vettigt att alla, varför vi behövde det plus en där? OK. Nu ska vi bara gå igenom den för att göra Se till att resten av koden är korrekt. Varför är det som händer? Ah, det är min rätt här. Vi jämförde fel värde. Å nej. 

Oh ja, här nere var vi byta fel värden. Eftersom vi tittar på i och j. De är de som vi checkar. Vi vill faktiskt att byta minimum, den nuvarande lägsta, med vad det utanför är. Och som ni kan se ner Här har vi en sorterad array. Det hade bara att göra med det faktum att när vi kontrollera värderingar vi jämföra, Vi var inte ute på de rätta värderingarna. Vi letade på samma en här, faktiskt inte byta det. Du måste titta på en nästa till det och sedan kan du byta. Så det är vad som var typ av buggning vår kod innan. Och vad jag gjorde här är allt debugger kunde ha gjort för dig Jag gjorde bara det på ombord, eftersom det är lättare att se stället för att försöka för att zooma in på debugger. Innebär det vettigt att alla? Häftigt. 

Okej. Vi kan gå vidare till att tala om asymptotisk notation, som är bara ett finare sätt att säga drifttider av alla dessa typer. Så jag vet David, i föreläsning, berört drifttider. Och han gick igenom hela formeln av hur man beräknar drifttider. Inga bekymmer om det. Om du är riktigt nyfiken om hur det fungerar, gärna prata med mig efter avsnitt. Vi kan gå igenom formlerna tillsammans. Men alla ni måste verkligen vet är att n kvadrat över 2 är samma sak som n kvadrat. Eftersom det största antalet, exponenten, växer mest. Och så för våra syften, allt vi bryr oss om är det jätte siffra som växer. 

Så vad är det bästa fall runtime urvals sort? Om du ska ha att iterera igenom en lista och sedan iterera genom resten av denna förteckning, hur många gånger är ni förmodligen, i värsta case-- i bästa fall sorry-- gå igenom? Kanske bättre fråga är att fråga, vad är det värsta fallet runtime selektions slag. PUBLIK: n kvadrat. ANDI PENG: Det n kvadrat, höger. Så ett enkelt sätt att tänka på detta är, varje gång du har två kapslade loopar, det kommer att bli n kvadrat. Eftersom inte bara är du löper genom ytterligare en gång, du måste gå tillbaka runt och köra igenom det återigen insidan för varje värde. Så i detta fall, du kör n gånger n kvadrat, som är-- ledsen, n gånger n, vilket är lika med n kvadrat. 

Och sortera är också lite unikt i den meningen att det spelar ingen roll om dessa värden är redan i sin ordning. Det är fortfarande kommer att köra igenom ändå. Låt oss bara säga att detta var en, två, tre, fyra. Oavsett huruvida det var i ordning, det fortfarande skulle ha gick igenom och fortfarande kontrolleras minimivärdet. Det skulle ha gjort samma antal kontroller varje gång, även om det faktiskt inte röra någonting. 

Så i ett sådant fall, det bästa och sämsta drifttider är faktiskt likvärdiga. Så förväntade runtime selektions sortera, som vi betecknar med symbolen theta, theta, i detta fall, skulle också vara n kvadrat. Alla tre av dessa skulle vara n kvadrat. Är alla klara över varför runtime är n kvadrat? 

Okej. Så jag ska bara snabbt köra genom resten av slag. Algoritmen för bubbla sort-- ihåg, Detta var den första David gick över i föreläsning. I huvudsak, steg du igenom hela listan och du swap-- du just jämföra två åt gången. Och om man är större, än du bara byta dem. Så om dessa är större, skulle du byta. Jag har officiellt här. 

Så låt oss bara säga att du hade 8, 6, 4, 2. Du skulle jämföra 8 och 6. Du skulle behöva byta dem. Du skulle jämföra 8 och 4. Du skulle behöva byta dem. Om du måste byta 8 och 2, ändra dem också. Så i en sådan känsla, kan du se, spelas ut under en lång tidsperiod, hur värden typ av bubbla till ändarna, som är därför vi kallar det bubbelsortering. 

Vi skulle bara köra igenom igen på vår andra pass, och vår tredje passet, och vår fjärde cykeln. I huvudsak, bubbelsortering bara körs tills du inte göra några fler swappar. Så i den meningen är det bara den allmänna pseudokod för den. Inga bekymmer, kommer alla dessa vara online. Vi behöver inte faktiskt gå över detta. 

Vi initiera bara en räknare variabel som börjar på 0. Och vi iterera igenom hela uppsättningen. Och om ett värde är-- om detta värdet är större än detta värde, du kommer att byta dem. Och då är du bara kommer att fortsätta. Och du kommer att räkna. Och du ska bara fortsätta göra detta medan räknaren är större än 0, vilket innebär att varje gång du måste byta, du vet att du vill gå tillbaka och kontrollera igen. Du vill behålla kontrollen tills du vet att du inte behöver byta längre. 

Så vad är det bästa och sämsta fall runtimes för bubbelsortering? Och hint-- detta är faktiskt annorlunda från val slag i den mening att dessa två svar är inte samma sak. Tänk på vad som skulle hända i ett ärende om det var redan för sortering. Och tänk på vad skulle hända om det var i det fall där det inte var sorteras. Och du kan slags kör genom varför det händer. Jag ska ge er, som, 30 sekunder för att tänka på det. 

OK. Har någon en gissning på vad värsta fall runtime av bubbelsortering är? Yeah. 

PUBLIK: Skulle det vara, något liknande, n gånger n minus 1 eller nåt sånt? Liksom varje gång det körs, det är bara, som en swap mindre att vad det var. 

ANDI PENG: Ja, så du är helt rätt. Och detta är ett fall där din Svaret var faktiskt mer komplex än den vi måste ge. Så det kommer att run-- jag kommer att radera allt det här. Är alla bra? Kan jag ta bort det? OK. Du kommer att gå igenom n gånger den första gången, eller hur? Och de kommer att gå igenom n minus 1 andra gången, eller hur? Och då du kommer att hålla gå, n gruvan 2, et cetera. David gjorde detta i en föreläsning, där, Om du har lagt upp alla dessa värden, du får något som är like-- yeah-- över 2, som i huvudsak bara minskar ned till n kvadrat. Du kommer att få en konstig fraktion där. Och så vet bara att n kvadrat alltid företräde framför fraktionen. Och så i detta fall, det värsta runtime skulle n kvadrat. Om det var i fallande ordning, tror du måste göra en swap varenda gång. 

Vad skulle vara potentiellt bästa fall runtime? Låt oss bara säga, om listan var redan i ordning, vad skulle runtime vara? 

PUBLIK: n. ANDI PENG: Det är n, precis. Och varför är det n? PUBLIK: Eftersom du bara måste kolla på varje gång. ANDI PENG: Exakt. Så i bästa möjliga runtime, Om denna lista var redan sorted-- låt oss säga 1, 2, 3, 4-- du skulle bara gå igenom, vill du kolla, du skulle se, oh, alla panorera. Jag behövde inte byta. Jag är färdig. Så i så fall är det bara n eller antalet steg du bara hade att checka in den första listan. 

Och efter vi nu hit insättningssortering, där algoritmen är i huvudsak att dividera det i en sorterad och osorterade delen. Och sedan en efter en, de osorterade värden är insatt i deras fall positioner i början av listan. 

Så till exempel, vi har en lista över 3, 5, 2, 6, 4 igen. Vi vet att det är för närvarande osorterade eftersom vi har bara började titta på det. Vi tar en titt och vi vet att det första värdet sorteras, eller hur? Om du bara tittar på en rad storlek en, vet du att det är för sortering. 

Så då vet vi att övriga fyra är osorterade. Vi går igenom och vi ser detta värde. Låt oss gå tillbaka. Se till att värdet på 5? Vi tar en titt på det. Vi jämför det med tre. Vi vet att det är större än 3, så vi vet att det är för sortering. Så vi vet nu att de två första sorteras och de tre sista är det inte. 

Vi tar en titt på 2. Vi kollar först den med 5. Är det mindre än 5? Jag är inte. Så vi måste hålla tittar ner. Då kan du kontrollera 2 st 3. Är det mindre än? Nej. Så du vet en 2 måste införas in i den främre och 3 och 5 båda måste skjutas ut. Gör detta igen med 6 och 4. Och vi håller bara kontrollera i huvudsak där vi checkar bara, check, check. Och tills det är i rätt läge, vi slags bara in den i rätt position, som är där namnet på det kom från. 

Så det är bara algoritmen, pseudokod per se, typ av, om hur vi skulle genomföra ett insättningssortering. Pseudokod är här. Det handlar på nätet. Inga bekymmer om ni är försöker kopiera ner det. Så återigen, samma question-- vad skulle vara det bästa och sämsta drifttider för insättningssortering? Det är mycket lik den sista frågan. Jag ska ge er, som, 30 sekunder att tänka på detta också. 

OK Finns det någon som vill ge mig det värsta runtime? Yeah. 

PUBLIK: n kvadrat. 

ANDI PENG: Det n kvadrat. Och varför är det n kvadrat? 

PUBLIK: För i omvänd ordning, har du att gå igenom n gånger n, som är-- ANDI PENG: Ja, exakt. Så samma sak som i bubbelsortering. Om denna lista är i fallande ordning, du är kommer att behöva kontrollera först en gång. Och sedan med varje mervärde, du är kommer att behöva kontrollera den mot varenda värde, eller hur? Och så helt och hållet, du kommer att göra En N passtider annan n passera, som är N i kvadrat. Hur är det bästa fall? Yeah. 

Publik: n minus 1, eftersom första är redan i kvadrat. 

ANDI PENG: Så nära. Svaret är faktiskt n. Eftersom medan den första är sorteras, kan det inte actually-- det vi bara lucked i det exemplet, att 2 råkade vara det minsta antalet. Men det kommer inte alltid att vara fallet. Om två redan sorterats i början men du ser ut och det finns en 1 här, 1 kommer att stöta den. Och det kommer att sluta ändan stötte ändå. 

Så i bästa fall, det är faktiskt bara kommer att bli n. Om du har en, två, tre, 4, 5, 6, 7, 8, är du kommer att gå igenom att hela listan så snart att kontrollera att se om allt är bra. Är alla klara för löpning tider val samt? Jag vet att jag går igenom Dessa riktigt snabbt. Men bara vet att om du vet allmänna begrepp, bör du vara bra. OK. Så jag ska bara ge er kanske, liksom, en minut att prata med dina grannar om vad som är bara några av de viktigaste skillnaderna mellan dessa typer av slag. Vi kommer att gå igenom det snart. Målgrupp: Åh, OK. ANDI PENG: Ja. OK. Cool, låt oss träffas igen som en klass. OK. Så det här var typ av en öppen fråga i den meningen att det finns massor av svar på dem. Och vi kommer att gå igenom några av dem kortfattat. Jag ville bara få er tänka på vad differentierade alla tre typer av slag. Och jag hörde också en stor question-- vad merge sort göra? Bra fråga, eftersom det är vad vi täcker nästa. 

Så merge sort är den en sort som fungerar mycket annorlunda än de andra sorter. Som ni kan see-- gjorde David göra det demo där han hade alla coola tongångar se hur samman sortera sprang, liksom, oändligt snabbare än de andra två typerna? OK. Så det beror på sammanslagning sortera implementerar att klyftan och erövra koncept som vi har talade om en hel del i föreläsning. I den meningen att vi tycker om att arbeta smartare, inte hårdare, när du dela och erövra problem, och bryta dem ner, och sedan sätta ihop dem, bra saker alltid hända. 

Så det sätt som går samman sortera väsentligen fungerar är att den delar ett osorterade array i hälften. Och sedan har fått två halvor av matriser. Och det bara sorterar dessa två halvor. Det håller bara dela på mitten, i hälften i hälften tills allt sorteras och sedan rekursivt sätter ihop allt. 

Så det är egentligen abstrakt. Så det här är bara en bit av pseudokod. Betyder det vettigt i så det är igång? Så låt oss bara säga att du har en uppsättning av n element, eller hur? Om n är mindre än 2, kan du återvända. Eftersom du vet att om det finns bara en sak, måste det sorteras. Annars, du sortera den vänstra halvan, och sedan sortera högra halvan, och sedan samman. 

Så medan det ser riktigt enkelt, i verkligheten, att tänka på det är typ av svårt. Eftersom du är som, ja, det är typ att köra på sig själv. Höger? Det körs på sig själv. Så i den meningen, David rörde vid rekursion i klassen. Och det är ett koncept Vi ska tala om mer. Det är att detta, dessa två linjer här är faktiskt bara programmet säga till den att köra själv med olika indata. Så i stället för att köra själv med helheten av n element, Du kan dela upp det i den vänstra halvan och den högra halvan och sedan köra den igen. 

Och då kommer vi att titta på det visuellt, eftersom jag är en visuell inlärare. Det fungerar bättre för mig. Så ska vi titta på ett visuellt exempel här. 

Låt oss säga att vi har en matris, sex delar, 3, 5, 2, 6, 4, 1, inte sortering. Okej, det finns en hel del på den här sidan. Så om ni kan titta på första steget här, 3, 5, 2, 6, 4, 1, du kan dela den på mitten. Du har 3, 5, 2, 6, 4, 1. Du vet att dessa aren't-- dig vet inte om de är sorterade eller inte, så du håller bryta ner dem i hälften, på mitten, på mitten, tills slutligen, du bara har ett element. Och en del är alltid sorteras, eller hur? 

Så vi vet att 3, 5, 2, 4, 6, 1, av sig själva, sorteras. Och nu kan vi sätta tillbaka dem tillsammans. Så vi vet 3, 5. Vi sätter dem tillsammans. Vi vet att det är sorteras. De 2 är fortfarande där. Vi kan sätta 4 och 6 tillsammans. Vi vet att det är sorteras, så vi satte det tillsammans. Och ett är där. 

Och sedan bara titta på Dessa två halvor här. Du har 3, 5, 2, 2, 3, 5. Du kan bara jämföra i början av allt. Eftersom du vet att detta är sorterad och du vet att det är för sortering. Så då du inte ens jämföra 5, du bara jämföra tre. Och 2 är mindre än 3, så du vet två måste gå i slutändan. 

Samma sak om det. 1 måste gå här. Och sedan när du går att sätta dessa två värden tillsammans, du vet att detta sorteras och du vet att det sorteras. Så då 1 och 2, den 1 är mindre än två. Som talar om att 1 bör gå på slutet av denna utan att ens titta på 3 eller 5. Och sedan 4, kan du bara kontrollera, det går rätt här. Du behöver inte titta på 5. Samma sak med 6. Du vet att det 6-- det bara behöver inte ses. 

Och så på det sättet, är du bara spara dig en hel del steg när du jämför. Du behöver inte jämföra alla elementet mot andra element. Du jämför bara mot de att du måste jämföra den mot. Så det är typ av ett abstrakt begrepp. Inga bekymmer om det inte är helt träffa dig rätt ännu. Men generellt är detta hur en sammanslagning sort fungerar. Frågor, snabba frågor, innan jag går vidare? Yeah. 

PUBLIK: Så du sa att du tar den 1, och sedan 4 och 6 och sätta dem i. Så är inte those-- inte du tittar på dem som separata delar, inte som helhet? ANDI PENG: Ja. Så vad som händer är att du i princip skapar en helt ny uppsättning. Så du vet att här har jag två uppsättningar av storlek 3, eller hur? Så du vet att min sorterade arrayen måste ha sex element. Så du bara skapa en ny mängd minne. Så du är ungefär som är slöseri med minne, men det spelar ingen roll eftersom det är så liten. Så du tittar på en och du tittar på 2. Och du vet att en är mindre än 2. Så du vet att en bör gå i början av alla dem. 

Du behöver inte ens behöver titta på 3 och 5. Så du vet en går där. Då du i princip hugga bort en. Det är, som, död för oss. Sedan har vi bara två, 3, 5 och sedan 4 och 6. Och då vet du att du jämföra 4 och 2, åh, två bör gå in där. Så du plopp 2 ner, du hackar den. Så då du bara har 3 och 5 i 4 och 6. Och du bara hålla hugga bort tills du lägger dem i gruppen. 

PUBLIK: Så du är bara alltid jämföra [OHÖRBAR]? 

ANDI PENG: Exakt. Så i den meningen, du är bara jämföra, i huvudsak, ett antal mot den andra nummer. Och eftersom du vet att det är sorteras, du behöver inte titta igenom alla nummer. Du behöver bara titta på den första. Och då kan du bara plopp ner dem, eftersom du vet de tillhör där de behöver tillhöra. Yeah. Bra fråga. 

Och sedan om någon av er är lite ambitiöst, gärna att titta på denna kod. Detta är faktiskt den fysiska genomförandet om hur vi skulle skriva merge sort. Och du kan se, det är mycket kort. Men idéerna bakom det är ganska komplex. Så om du känner för att dra ut detta i dina läxor ikväll, gärna. 

OK. Och David gick också över detta i föreläsning. Vilka är de bästa fall drifttider, värsta fall drifttider, och de förväntade drifttider för merge sort? Ett par sekunder att tänka. Detta är ganska svårt, men typ av intuitiv om man tänker på det. Okej. 

PUBLIK: Är det värsta fallet n log n? ANDI PENG: Exakt. Och varför är det n log n. 

PUBLIK: Är inte det eftersom det blir exponentiellt snabbare, så det är som en funktion av den i stället för att bara helt enkelt vara n kvadrat eller något? ANDI PENG: Exakt. Så anledningen till att runtime på detta är n log n är because-- vad är du gör i alla dessa steg? Du är bara hugga den på mitten, eller hur? Och så när vi gör det logga, allt som det gör splittrar ett problem i halv, på mitten, på mitten, i fler halvor. Och i det avseendet, kan du snäll av eliminera den linjära modellen att vi har använt. För när du hugger saker i hälften, det är en logg. Det är bara den matematiska sätt att representera det. 

Och slutligen, i slutet, du är bara göra en sista passage genom att sätta dem alla i ordning, eller hur? Och så om du bara behöver kolla en sak, det är n. Och så du är typ av multiplicera de två tillsammans. Så det är som du har fått den slutliga kontrollera n här nere med en logg över n Här uppe. Och om du multiplicera dem, som är n log n. 

Och så det bästa fallet och sämsta fallet och förväntat är alla n log n. Det är också som en annan sort. Det är som val Sortera i den meningen att den spelar ingen roll vad din listan är, det är bara att gå att göra samma sak varje gång. OK. Så när ni kan se, även om den typ som vi har gått through-- n kvadrat, det är inte mycket effektiv. Och även denna n log n är inte det mest effektiva. Om ni är nyfikna, det finns sorteringsmekanismer som är så effektiva att de är nästan i huvudsak plana när runtime. 

Du har några log n-talet. Du har lite log log n-talet. Vi rör inte på dem i denna klass just nu. Men om ni är nyfikna, gärna google, vad är de mest effektiva sorteringsmekanismer. Jag vet inte, det finns några riktigt roliga sådana, like-- det finns några riktigt roliga sådana som människor gör. Och du undrar hur de någonsin tänkt på det. Så google, om du har några extra tid, på, vad är några roliga sätt som people-- samt effektiva ways-- människor har kunnat genomföra slag. OK. Och här är bara en behändig liten diagram. Jag vet allt om dig, innan det frågesport 0, kommer att vara i ditt rum förmodligen försöker att memorera det. Så det är trevligt där för er. Glöm bara inte logiken som made-- varför dessa siffror var inträffar. Om du alltid förlorat, bara göra att du vet vad slag är. Och du kan köra igenom dem i ditt sinne ta reda på varför de Svaren är dessa svar. 

Okej. Så vi kommer att flytta på, slutligen sökning. På grund som de av er som har läst pset, sökning är också en del av veckans problem sätter. Du kommer att bli ombedd att genomföra två typer av sökningar. Den ena är en linjär sökning och en är en binär sökning. 

Så den linjära sökningen är ganska lätt. Du vill bara att söka elementet en lista för att se om du får det. Du behöver bara iterera igenom. Och om det är lika med något, du kan bara lämna tillbaka den, eller hur? Men det som vi är mest intresserade av att prata om är binär sökning, höger, som är den söndra och härska mekanism som David demonstrerade i föreläsning. 

Kom ihåg telefonboken exempel att han håller föra upp, den som han slags kämpade lite på det senaste året, där du dela upp problemet i en halv, i halv, i halv, om och om igen, tills du hittar vad du letar efter? Och du har fått runtime av det också. Och du kan se, är det betydligt effektivare än någon annan typ av sökning. 

Så det sätt som vi skulle gå om implementering av en binär sökning är, om vi hade en matris, index 0-6, sju element, vi kan se i mitten, right-- ledsen, om vår fråga first-- om vi vill ställa frågan om, gör arrayen innehåller beståndsdelen av 7, naturligtvis, att vara människor, och som har en så liten samling, är det lätt för oss att säga ja. Men sättet att implementera ett binärt sökningen skulle vara att titta i mitten. 

Vi vet att index 3 är i mitten, eftersom vi vet att det finns sju element. Vad 7 delat med 2? Du kan hugga av den extra 1. Du har tre i mitten. Så är uppsättning av 3 lika med 7? Det är inte, eller hur? Men vi kan göra ett par av kontroller. Är uppsättning av tre mindre än 7 eller är samling av tre större än 7? 

Och vi vet att det är mindre än 7. Så vi vet att, åh, måste det inte vara i den vänstra halvan. Vi vet att det måste vara i den högra halvan, eller hur? Så vi kan bara hugga av halva uppsättningen. Vi behöver inte ens till titta på det längre. Eftersom vi vet att halv av vår problem-- vi vet att svaret är den högra halvan av vårt problem. Så vi bara tittar på det nu. 

Så nu tittar vi på mitten av vad som finns kvar. Det index 5. Vi gör samma kontroll igen och vi ser att det är mindre. Så vi se till vänster av det. Och sedan ser vi att check. Är arrayen värdet vid index 4 är lika med 7? Det är. Så vi kan återkomma sant, eftersom vi hittade värdet i vår lista. Har det sätt som jag gick igenom det vettigt för alla? OK. Jag ska ge er kanske, liksom, tre, fyra minuter att räkna ut hur pseudo detta. 

Så tänk jag bad dig att skriva en funktion som kallas sökning () som återvände ett värde, ett booleskt värde, det var sant eller false-- liknande, true om du hittat värde, falskt om så inte är fallet. Och så var antogs i det värde som du letade efter i värden, som är array-- åh, jag definitivt sätta att på fel plats. OK. Iaf, bör den ha varit till höger om värden. Och sedan int n är antalet element i den arrayen. Hur skulle du gå om att försöka att pseudo det problemet in? Jag ska ge er killar som tre minuter att göra det. Nej, jag tror att det finns only-- Ja, det finns en rätt upp här. PUBLIK: Kan jag? ANDI PENG: Ja, jag har dig. Är det fungerar? OK bra. 

OK. Okej killar, vi är kommer att tygla den. OK. Så antar vi har denna härliga liten samling med n värden i det. Jag ville inte dra linjerna. Men hur skulle vi gå om försöker att skriva detta? Finns det någon som vill ge mig den första raden? Om du vill ge mig första raden i denna pseudokod. 

PUBLIK: [OHÖRBAR] PUBLIK: Du skulle vilja att iterera through-- PUBLIK: Just another för loop? PUBLIK: --Barnspel. 

ANDI PENG: Så här är lite knepigt. Tänk about-- du vill att hålla igång denna loop om och om igen tills när? 

PUBLIK: Tills [OHÖRBAR] värde är lika med detta värde. ANDI PENG: Exakt. Så du kan faktiskt bara write-- Vi kan även förenkla den mer. Vi kan bara göra en while-slinga, eller hur? Så du kan bara ha loop-- Vi vet att det är ett tag. Men just nu, jag kommer att säga "loop" - genom vad? Loop until-- vad som är vår sinande tillstånd? Jag tror att jag hörde det. Jag hörde någon säga det. 

Målgrupp: Värden lika mitten. ANDI PENG: Säg det igen. Målgrupp: Eller tills värde du söker för är lika med det mittersta värdet. 

ANDI PENG: Vad händer om det inte är i det? Vad händer om det värde du söker finns inte faktiskt i denna samling? PUBLIK: Du kommer tillbaka 1. 

ANDI PENG: Men vad vi vill slinga tills om vi har ett tillstånd? Yeah. 

PUBLIK: Tills det finns bara ett värde? ANDI PENG: Du kan loop until-- så att du vet att du är kommer att ha en maxvärde, eller hur? Och du vet att du kommer att ha en min värde, eller hur? Eftersom också, det är något Jag glömde att säga innan, att något som är kritiska binär sökning är att din samling redan sorteras. Eftersom det finns inget sätt att göra detta om de är bara slumpmässiga värden. Du vet inte om man är större än den andra, eller hur? 

Så du vet att din max och dina mins är här, eller hur? Om du kommer att justera ditt max i dina minuter och mid-- låt oss bara anta din mitten värde är rätt här-- du kommer att i grund och botten slinga tills din minsta är ungefär samma som ditt max, höger, eller Om din max är inte detsamma som din min. Höger? För när det händer, vet du att du har så småningom träffa samma värde. Så du vill loop tills min är mindre än eller lika att-- oops, inte är mindre än eller lika med, åt andra hållet around-- max är. 

Gjorde det vettigt? Jag tog några försök att få det rätt. Men slinga tills maxvärdet är i huvudsak nästan mindre än eller lika med din minsta, eller hur? Det är när du vet att du har närmat sig varandra. PUBLIK: När skulle din högsta värde vara mindre än den minsta? ANDI PENG: Om du håller anpassa den som är vad vi kommer att göra detta. Betyder det vettigt? Minsta och max är bara heltal som vi förmodligen kommer att vilja skapa för att hålla reda på var vi letar. Eftersom arrayen existerar oavsett vad vi gör. Precis, vi är inte rent fysiskt hugga av arrayen, eller hur? Vi har precis justering där vi letar. Betyder det vettigt? 

PUBLIK: Ja. 

ANDI PENG: OK. Så om det är en förutsättning för vår slinga, Vad vill vi insidan av denna loop? Vad ska vi kommer att vilja göra? Så just nu har vi max och min, höger, förmodligen skapat här uppe någonstans. Vi ska förmodligen vill att hitta en medelväg, eller hur? Hur ska vi vara kunna hitta mitten? Vad är mathematical-- PUBLIK: Max plus min dividerat med två. ANDI PENG: Exakt. Betyder det vettigt? Och ni se varför vi inte bara use-- varför vi gjorde detta istället för att göra just n delat med 2? Det beror på n är ett värde det kommer att förbli densamma. Höger? Men när vi anpassar vår minsta och maxvärden, kommer de att förändras. Och som ett resultat, våra middle kommer att förändras. Så det är därför vi vill att göra denna rätt här. OK. 

Och sedan, nu när vi har hittat our-- ja. 

PUBLIK: Bara en snabb question-- när du säger min och max, Vi antar att det är redan sorteras? 

ANDI PENG: Ja, det är faktiskt en förutsättning för en binär sökning, att du måste veta det sorteras. Vilket är varför sort, du skriver i ditt problem in innan din binär sökning. OK. Så nu när vi vet var vår mittpunkt är, vad vill du göra här? 

PUBLIK: Vi vill jämföra att till den andra en. ANDI PENG: Exakt. Så du kommer att jämföra mitten till värde, eller hur? Och vad säger det oss när vi jämför? Vad vill vi göra efteråt? 

PUBLIK: Om värdet är större än mitten, vi vill skära bort det. ANDI PENG: Exakt. Så om värdet är större än mitten, vi är kommer att vilja ändra dessa minimum och maxar, eller hur? Vad vill vi förändra? Så om vi vet värdet är någonstans här, vad gör du vi ändra? Vi vill förändra vår minimum för att vara i mitten, eller hur? Och sedan andra, om det är i detta halvt, vad vi vill förändra? 

PUBLIK: Din maximum. ANDI PENG: Ja. Och då du bara gå att hålla looping, eller hur? För nu, efter en iteration igenom, har du en max här. Och då kan du räkna en mitten. Och då kan du jämföra. Och du kommer att fortsätta tills minuter och de maxes i allt väsentligt konvergerat. Och det är när du vet att du har drabbats i slutet av den. Och antingen du har hittat den eller om du har inte på den punkten. 

Innebär detta vettigt för alla? OK. Detta är ganska viktigt, eftersom du har att skriva detta i din kod i kväll. Men ni har en ganska bra känsla för vad du ska göra, vilket är bra. OK. Så vi har omkring sju minuter kvar avsnitt. Så vi kommer att tala om detta pset att vi ska göra. Så pset är uppdelad i två halvor. Den första halvan involverar genomföra en Sök där du skriver en linjär sökning, en binär sökning och en sorteringsalgoritm. 

Så det här är den första tid i en pset där vi kommer att ge er vad som kallas distributions kod, som är koden att vi har redan skrivna, men bara lämnat vissa delar av för dig att avsluta skriva. Så ni, när man tittar på det här koden, kan du bli riktigt rädd. Om du bara vill, ahh, jag vet inte vad det gör, Jag vet inte, som verkar som så komplicerat, ahh, slappna av. Det är ok. Läs spec. Spec kommer att förklara för dig exakt vad alla dessa program gör. 

Exempelvis är generate.c ett program som kommer med din pset. Du behöver faktiskt inte röra det, men bör du förstå vad det gör. Och generate.c, är allt den gör antingen generera slumptal eller så kan du ge det ett frö, som en uppgjort nummer som det tar, och det genererar fler nummer. Så det finns ett särskilt sätt att genomföra generate.c där Du kan bara göra en massa siffror för dig att testa dina andra metoder på. 

Så om du ville, för exempel testa din hitta, du skulle vilja köra generate.c, generera en massa siffror, och sedan köra din hjälpare funktion. Din medhjälpare funktion är där du är faktiskt fysiskt skriva kod. Och tänk på medhjälpare som ett bibliotek fil du skriver att fyndet ringer. Och det inom helpers.c, kommer du gör sökning och sortering. 

Och då du kommer att väsentligen bara sätta dem alla tillsammans. Spec kommer att berätta hur man lägga det på kommandoraden. Och du kommer att kunna testa om inte din typ och söka fungerar. Häftigt. Har någon redan börjat och stött på problem eller frågor De har just nu med detta? OK. 

PUBLIK: Vänta. Jag har en fråga. 

ANDI PENG: Ja. 

PUBLIK: Så jag började göra den linjära sökning i helpers.c och det var inte riktigt fungerar. Men senare, fick jag veta att vi bara måste ta bort det och göra binär sökning. Så spelar det någon roll om det inte fungerar? 

ANDI PENG: korta svaret är nej. Men eftersom vi är inte-- PUBLIK: Men ingen är faktiskt kontroll. ANDI PENG: Vi är aldrig kommer att se det. Men du förmodligen vill göra Kontrollera din sökning fungerar. För om din linjära sökning inte fungerar, då är chansen din binära sökning kommer inte att fungera lika bra. Eftersom du har liknande logik i dem båda. Och nej, det spelar egentligen ingen roll. Så de enda du ska vända i är typ och binär sökning. Yeah. 

Och även en hel del barn var försöker kompilera helpers.c. Du faktiskt inte tillåtet att göra det, eftersom helpers.c inte har en huvudfunktion. Och så du bör endast vara faktiskt sammanställa generera och hitta, eftersom hitta samtal helpers.c och funktioner inom det. Så det gör felsökning en smärta i baken. Men det är vad vi måste göra. PUBLIK: Du gör precis allt, eller hur? ANDI PENG: Du kan bara göra allt också, ja. OK. Så det är det i termer av vad den pset ber er alla att göra. Om du har några frågor är du välkommen fri att fråga mig efter avsnitt. Jag kommer att vara här i ungefär 20 minuter. 

Och Ja, PSET s verkligen inte så illa. Ni borde vara OK. Dessa, följ bara riktlinjer. Typ av har en känsla av, logiskt, vad bör hända och du kommer att bli bra. Inte vara alltför rädd. Det finns en hel del kod redan skrivit där. Inte vara alltför rädd om du inte förstå vad allt detta betyder. Om det är en hel del, det är helt bra. Och komma till kontorstid. Vi hjälper dig att ta en titt. 

PUBLIK: Med extra funktioner, ser vi de upp? 

ANDI PENG: Ja, de är i koden. I spelet 15, halv av Det är redan skriven för dig. Så dessa funktioner är redan i koden. Japp. Okej. Tja, lycka till. Det är en motbjudande dag. Så förhoppningsvis ni inte känner sig alltför illa om vistas inne och kodning.