TALARE 1: Hej alla! Välkommen tillbaka till avsnitt. Så glad att se så många av er både här, och alla som tittar på nätet. Så, som vanligt välkommen tillbaka. Jag hoppas att ni alla haft en härlig helg, full av vila, avkoppling. Det var vackert ute igår. Så, jag hoppas du haft utomhus. 

Så först ett par meddelanden. Betygs. Så, de flesta av er bör ha fått en maila mig om din Scratch Pset, liksom omdöme för Pset 1. Så, bara ett par saker. Var noga med att använda check50 i style50. Dessa är tänkta att vara resurser för er killar, att se till att du får så många poäng som du kan utan att i onödan förlora dem. Så saker som stil är mycket viktiga. Vi kommer att ta bort det. Några av er kanske redan har märkt att från din Pset. Och check50 är bara en riktigt enkelt sätt att se till att vi faktiskt är åter vad måste returneras till användaren, och att allt fungerar korrekt. 

På den andra anteckningen, se till att din ladda upp saker till rätt mapp. Det gör mitt liv bara en Lite svårare Om du laddar upp Pset 2 i Pset 1 för när jag hämta saker, de inte hämtas. Och jag vet att det är lite wonky i ett system för att vänja sig, men bara vara super försiktig, om så bara för mig, så att när du får e-post på liknande 02:00 och jag är betygssättning. Om inte orsaka jag måste titta runt för din Pset. Cool. 

Jag vet att det är tidigt, men jag helt fick tas på sängen av en uppsats som är på grund denna fredag, som mina professorer var precis som, oh yeah. Kom ihåg, du har en uppsats beror på fredagen. Så, jag vet ingen gillar att tänka midterms, men din första frågesport är den 15 oktober, vilket Oktober börjar denna vecka. Så kan det vara förr än vad du förväntat är allt. Så att du inte kastat på sängen när Jag nämner nästa veckas avsnitt som åh, din quiz nästa vecka, tänkte jag Jag skulle ge dig lite mer av en huvuden upp nu. 

Så ditt problem inställd, nummer tre. Hur människor har läst spec av nyfikenhet? OK. Vi fick ett par. Typ av minskning från förra vecka men det är OK. Jag vet att det var vackert ute. Så Break Out. Definitivt när du får gjort idag läsa din spec minst Försök som laddar ner distributions kod och kör liksom den första initiala sak som de ber dig att. Eftersom vi använder distributions kod och ett bibliotek att vi bara har using-- --Det är bara andra gången vi har gjort detta Pset, galna saker kan hända med apparaten, och du vill finna att ute nu kontra senare. 

För om det är torsdag kväll eller är det Onsdag natt och av någon anledning apparaten bara inte vill köra med biblioteket eller med fördelningen kod, det betyder du kan inte ens börja göra kodningen. Eftersom du inte kan kontrollera för att se om det fungerar. Din kommer inte att kunna att se om det sammanställer. Du vill ta hand om dem som i början av veckan, när man fortfarande kan maila mig eller någon av de andra TF, och vi kan få dem fast. Eftersom dessa är frågor som kommer att stoppa dig från att göra några verkliga framsteg. Det är inte som en bugg, som du kan liksom bara hoppa över. Om du har problem med din apparaten eller distributionskoden, du verkligen vill att sett hand om förr snarare än senare. Så även om du inte tänker faktiskt börja koda, ladda ner distributionen kod, läs spec, se till att allt fungerar där. OK? Om du bara kan göra det, jag lovar ditt liv kommer att bli lättare. Och så du förmodligen kommer att göra det just nu rätt? OK. Så, några frågor där? Any logistiska saker? Alla är bra? OK. 

Disclaimer för de av dig i rummet och på nätet. Jag kommer att försöka byta mellan PowerPoint i apparaten eftersom vi kommer att göra lite kodning idag på allmän begäran av anonyma förslag enkät jag skickade ut förra veckan. Så kommer vi att göra lite kodning. Så, om ni också vill att brand upp dina apparater, och du bör ha fått ett e-postmeddelande från mig, med en exempelfil. Du får gärna göra det. 

Så vi kommer att prata om GDB, vilket är en debugger. Det kommer att hjälpa dig sorts räkna ut var det går fel i din kod. Det är egentligen bara ett sätt för dig att kliva genom din kod eftersom det händer, och kunna skriva ut variabler eller se vad som egentligen händer under huven verserna ditt program bara kör, det är som faulting, och du är som, ingen aning vad som just hände här. Jag vet inte vilken linje det misslyckades på. Jag vet inte var det gick fel. Så, GDB kommer att hjälpa dig med det. Dessutom, om du bestämmer dig för att fortsätter ja, och ta 61, Det kommer verkligen, verkligen vara din bästa vän, för jag kan berätta för dig eftersom jag går igenom den klassen. 

Vi kommer att titta på digital sök, som om ni kommer ihåg den stora telefonboken exempel skådespel från klass. Vi kommer att genomföra det, och promenader genom att lite mer, och sedan ska vi gå igenom fyra olika slag, som är Bubble, Urval, Insättning, och sammanfoga. Cool. Så, GDB som jag nämnde, är en debugger. Och dessa är typ av de stora saker, de stora funktioner eller kommandon som du använder i GDB, och jag kommer att gå dig genom en demo av den i en sekund. 

Så detta är inte bara kommer att bo abstrakta. Jag ska försöka göra det så konkret som möjligt för er. Så, bryta. Det ska antingen vara break liknande, några nummer, vilket representerar en rad i programmet, eller så kan du namnge en funktion. Så, om du säger break, det kommer att stanna vid huvud, och låta dig gå igenom den funktionen. 

Likaså om du har någon extern fungerar som Swap eller Cube, att vi tittade på i förra veckan. Om du säger att bryta en av dem, när ditt program slår det, Det väntar på dig att tala om vad de ska göra. Innan det kommer bara köra så att du kunde faktiskt steg inuti funktionen och se vad som händer. Så hoppar Nästa strax över nästa rad, går över funktioner. Step. Dessa är alla lite abstrakt. Så, jag ska bara köra igenom dem, men du kommer att se dem i bruk i en sekund. 

Kliv in i en funktion. Så när jag sa, som med Swap, skulle det kan du faktiskt som om du är som fysiskt kliva inne, du kan bråka med dessa variabler, print reda på vad de är, se vad som händer. Lista kommer bokstavligen bara ut ut det omgivande kod. Så, om du slags glömmer var du är i ditt program, eller du undrar vad som händer runt omkring, Detta kommer bara skriva ut ett segment av vilja fem eller sex rader runt den. Så kan du få orienterad om var du befinner dig. 

Skriv några variabel. Så, om du har nyckeln som i Caesar, som vi ska titta på. Du kan säga Print Key på någon punkt. Den ska berätta vad värdet är så att, kanske någonstans på vägen, Du har skrivit över din nyckel. Du kan faktiskt säga att eftersom Du kan faktiskt konstatera att värdet. 

I lokalbefolkningen, bara utskrifter ut dina lokala variabler. Så, när du är i en slinga, och du bara vill se ut som, oh. Vad är mitt jag? Vad är detta nyckelvärde att jag initiera här? Vad är budskapet i detta läge? Det kommer bara att skriva ut alla av dem, så att du behöver inte individuellt säga, Print I. ut meddelande. Skriv Key. Och sedan Display. Vad det gör är som ni stega igenom programmet, det ska bara se till att det är visar några viss variabel vid varje punkt. Så att du also-- --den är typ av en genväg där du behöver inte hålla på som, oh. Skriv Key eller Skriv I. Det bara kommer automatiskt att göra det åt dig. 

Så med det, vi kommer för att se hur det går. Jag ska försöka och switch över till min apparat. Se om jag kan göra det här. Alla. Vi kommer bara att spegla den. Det finns inget galet på min laptop ändå. OK. Detta måste vara den här. Den är så liten. Låt oss se om vi kan göra det här. 

OK. Alice är uppenbarligen kämpar här bara en liten bit, men vi kommer att få det i en momento. OK. Vi kommer bara att öka denna. OK. Kan alla sorts ser det? Kanske lite? Jag vet att det är lite små. Du kan inte riktigt räkna ut hur man gör det här större. Om någon vet. Finns det någon som vet hur man gör det större? OK. Vi kommer att rulla med det. Spelar ingen roll ändå eftersom det är bara det är den kod som ni bör har. 

Vad är viktigare är terminalen här. Och vi har här Varför är det så liten? Inställningar. Oh. Sann Ike. Hur är det? Av det. Är det bättre för alla? OK ,. Cool. 

Du vet när du är i en CS klass tekniska svårigheter är typ av en del av the-- Så, låt oss klara detta. OK. Så här i avsnittet, som vi hade här. Caesar är en körbar fil. Så jag gjorde det. Så, är en sak att inse med GDB att det fungerar bara på körbara filer. Så kan du inte köra det på en dotsy. Du måste faktiskt göra Se till att din kod sammanställer, och att det faktiskt kan köras. 

Så, se till att om det inte gör det sammanställa, få den att kompilera, så att du kan slags kör igenom den. Så, för att starta GDB, allt du gör, Gloria typ GDB, och sedan bara den fil som du vill. Jag stavar alltid Caesar. Men du vill vara säker på eftersom det är en körbar, ti s dot blixt så att innebär att du kommer att köra CSI du kommer att köra Detta filer antingen med debugger. OK. Så, du gör det, får du denna typ av rotvälska. Det är bara allt om debugger. Du behöver verkligen inte till oroa sig för det just nu. Och som ni ser har vi denna öppna parens, BNP, nära parens, och bara typ av ser ut vår kommandorad, eller hur? 

Så, vad vi vill do-- --So, Det första är att vi vill välja en plats för att bryta den. Så det finns ett programfel i detta Caesar programmet att jag presentera, att vi kommer att ta reda på. Det Vad det är det tar ingången Barfoo med stora bokstäver, och av någon anledning Det ändrar inte A. Det lämnar bara det ensam, är allt annat rätt, men den andra bokstaven A är oförändrad. Så vi ska försöka räkna ut varför det är. Så, det första du normalt vill göra när du börjar på GDB är räkna ut var att bryta den. 

Så Caesar är en ganska kort program. Vi har bara en funktion, eller hur? Vad var vår funktion i Caesar? Det finns bara en funktion, Main rätt? Main är en funktion för alla dina program. Om du inte har Main, kanske jag vara lite orolig just nu, men jag hoppas att ni alla hade huvud där. Så, vad vi kan göra är att vi kan bara bryta Main, bara så där. Så står det, OK. Vi sätter vår brytpunkt där. 

Så, nu är det sak att komma ihåg Caesar tar en Kommandoradsargumentet rätt och vi har inte gjort det någonstans än. Så, vad du gör är när du faktiskt går att köra programmet, alla program som du är körs i GDB som behöver kommandoraden argument, du kommer att mata när du börjar köra den. Så i det här fallet, vi gör Kör med en nyckel av tre. Och det kommer faktiskt börja. 

Så, om ni ser här, vi har Om RC inte är lika med två. Så om ni har alla den fil som jag skickade ut upp ser du att det är som första raden våran funktion, eller hur? Det är kontroll för att se om vi har rätt antal argument. Så, om du undrar om RC är korrekt, du kan göra något precis som Print RC. RC är två, vilket är vad vi förväntat oss, eller hur? 

Så kan vi gå på Nästa, och fortsätter genom. Så, har vi några viktiga där. Och vi kan skriva ut vår nyckel att se till att det är korrekt. Intressant. Inte riktigt vad vi förväntat oss. Så, för en sak att inse med GDB också är att det inte är förrän du faktiskt hit Därefter att den linje som du just såg faktiskt exekveras. Så i det här fallet Key har inte tilldelats ännu. Så, är nyckeln vissa skräp värde som du ser på botten där. Negativ $ 120-- --Det är en miljard och något udda saker rätt? Det är inte nyckeln som vi förväntade oss. Men om vi träffade på Nästa och sedan vi försök och tryckknapp, det är tre. 

Alla se det? Så, om du får något att du är som, vänta. Detta är helt fel, och jag vet inte Hur detta skulle hända eftersom allt jag vill ha göra är att tilldela ett nummer, en variabel, försöka slå Därefter försöker skriva ut det igen, och se om det fungerar. Eftersom det är bara att köra och faktiskt tilldela något efter dig hit Nästa. Vettigt att alla? Uh huh? 

TALARE 2: När du random siffror vad betyder det? 

TALARE 1: Det är bara slumpmässigt. Det är bara skräp. Det är bara något som din Datorn kommer att slumpmässigt tilldela. Cool. Så, nu kan vi gå igenom, och så Nu har vi denna klartext getString. Så, låt mig bara presentera vad kommer att hända när vi träffar Next här. Vår GDB slags försvinner, eller hur? Det beror getString Nu utför, eller hur? Så när vi såg klartext lika GetString, öppna parens och parens, och vi drabbades Därefter har det faktiskt utförs nu. Så är det att vänta på oss att mata in något. 

Så vi kommer att mata våra livsmedel som är vad det inte som jag sa och som bara säger att det är körts, att den slutna Fästet gör att det är att komma ut i nämnda slinga. Så kan vi träffa på Nästa, och nu, när jag är att du är alla bekanta från Caesar, Detta är, vad är denna linje kommer att göra. Det är för Int I är lika med 0, lika med N Strlen, vanlig text, och sedan Jag är mindre än n, jag, plus, plus. Vad är denna slinga ska göra? Öppna ditt meddelande. Cool. Så, låt oss börja göra det. 

Så, bör detta tillstånd matcha, för vår första? Om det är ett B, det är ren text I. Vi kan få information om våra lokalbefolkningen. Så, är jag noll, och om sex, vilket Vi förväntar oss, och vår nyckel är tre. Allt som vettigt, eller hur? Dessa siffror är alla exakt vad de borde vara. Så, hum? TALARE 3: Jag har slumptal för gruvan. SPEAKER 1: Tja, kan vi check-- --Vi kan prata om det på en sekund. Men du bör vara att få detta. Så, om vi har ett kapital B för vår första, detta villkor ska fånga den, eller hur? Så om vi slog Därefter ser vi att denna Om faktiskt utför. För om du följer tillsammans i din kod, denna linje här, där klartext I skall ersättas med denna aritmetik, endast körs om Om tillståndet är korrekt rätt? 

GDB kommer bara att visa dig saker som faktiskt utför. Så om detta Om villkoret inte uppfylldes, det bara att hoppa till nästa rad. OK? Så har vi det. Detta fäste betyder att det är stängd ur denna loop nu. Så det kommer att börja igen. Bara så där. Så att vi kan få info om våra lokalbefolkningen här, och vi ser att vår första brev har förändrats, eller hur? Det är nu ett E, som det ska vara. Så kan vi fortsätta på. 

Och vi har denna kontroll. Och denna kontroll bör fungera, eller hur? Det är A. Det bör ändras tre bokstäver framåt. Men om du märker, vi få något annat. Så i detta fall här uppe, fångade den det, och så denna linje avrättades, som modifierats vår B. Men, i detta fallet här, Vi har att det bara hoppade över det, och gick till [? L SIFF. ?] Så något händer där. Vad som är att berätta är att, Vi vet att den ska hinna hit, men det är det inte. Kan någon se vad vår Problemet ligger i den linjen? Det är en mycket liten sak. Och du kan även titta på din kod. Det är också line-- glömma vad linjen är det i there-- men det är i [OHÖRBAR]. Ja? 

TALARE 4: Det är på mer än sida om du läser det i boken. TALARE 1: Exakt. Så, debugger kunde inte berätta du det, men det debugger kan få dig ner till en linje som du vet fungerar inte. Och ibland, när speciellt senare på terminen, när du arbetar med ett hundratal, en hundra några rader kod, och du vet inte var det är inte, Detta är ett bra sätt att göra det. Så hittade vi vår bugg. Du kan fixa det i filen, och då kan du köra den igen, och allt skulle fungera perfekt. Och det största är Detta kan tyckas, OK. Yeah. Cool. Du visste vad du letar efter. Så, du visste vad du ska göra. 

GDB kan vara super bra eftersom du kan skriva ut alla dessa saker som du skulle inte. Det är mycket mer användbar än printf. Hur många av er använder liknande printf Information att räkna ut var en bugg var, eller hur? Så med detta, behöver du inte måste hålla gå tillbaka, och gillar kommentera i Printf eller kommentera bort, och räkna ut vad du ska skriva ut. Detta egentligen bara ger dig möjlighet att gå igenom, skriva ut saker när du går igenom, så kan du observera hur de förändras i realtid, som ditt program körs. 

Och det tar lite lite tid att vänja sig. Jag rekommenderar starkt bara typ av att vara lite frustrerad med det för just nu. Om du tillbringar en timme över nästa vecka att lära sig använda GDB, du kommer att rädda dig själv så mycket tid längre fram. Och bokstavligt. Vi berättar detta till människor varje år, och jag minns när jag tog klass, var jag vill, jag kommer att bli bra. Nej. Pset 6 kom och jag var liksom, jag ska lära hur man använder GDB eftersom jag inte veta vad som händer här. 

Så om du tar dig tid så använda den på mindre program att du kommer att vara arbetar med, som att jobba igenom något liknande Visionäre, som den här. Eller om du vill ha extra praxis, jag är säker på Jag kunde komma på buggiga program, för dig att felsöka om du vill. 

Men om du bara tar lite tid att komma van vid det, bara leka med den, Det kommer verkligen att tjäna dig väl. Och det är verkligen en av de saker som du bara måste försöka, och få händerna smutsiga med, innan man verkligen förstår det. Jag verkligen bara förstod det en gång Jag var tvungen att felsöka saker med den, och det är mycket trevligare att ha en uppfattning om hur man felsöka förr snarare än senare. OK. Cool. Jag vet att det är ungefär som en snabbkurs i GDB, och jag kommer definitivt att arbeta på att få dessa för att se större nästa gång. Cool. 

Så om vi går tillbaka till vår PowerPoint. Kommer detta att fungera? AWH. Ja. OK. Så, om du någonsin behöver någon av dem igen, det finns i listan. Så Binary Search, som alla minns den stora skådespel av David rippning telefonböcker i hälften. Jag vet inte riktigt får telefonböcker längre, eftersom som var gör du få telefonböcker nuförtiden? Jag vet faktiskt inte. Binary Search. Kommer någon ihåg hur Binary Search fungerar? Någon alls? Yeah? SPEAKER 5: Du vet när man tittar på vilken halvlek det skulle vara i, Baserat på detta, och bli av med den andra hälften. 

SPEAKER 1 Exakt. Så, Binary Search, är det slags en-- --Vi vill kalla det söndra och härska. Så, vad du ska göra är du ser i mitten, och du får se om det matchar vad du letar efter. Och om det inte gör det, då du försöker räkna ut, kommer det att vara kvar hälften eller den högra halvan. Så kan det vara om du letar på något som är alfabetiskt, du ser, oh. Har Allison kommer före M? Ja. Så, ska vi titta på den första halvleken. 

Eller det kan vara som med siffror. Allt som du kan jämföra, kan det sorteras. Du kan använda binär sökning på. Så, någon som minns detta graf eller vad det här är? Det är Asymptotic komplexitet. Så, detta diagram bara beskriver hur lång tid det tar dig att lösa ett problem som du ökar antalet saker som du använder. 

Så vi har N, som är linjär tid. Om N över två, som är något bättre, växer fortfarande supersnabb. Och sedan har vi Login, vilket är vad vi anser Binary Search. Om vi ​​märker, eftersom ditt problem blir mycket och mycket större, den tid det tar att lösa det egentligen inte ökar så mycket. Det är som jämförbara här i början. Du är som, OK. Allt här egentligen inte Oavsett vilken som vi använder, men du får ut till en miljon, en miljard. Du försöker hitta some-- --you're att försöka hitta en nål i en höstack. 

Jag tror att du vill ha det här problemet. Du vill ha denna komplexitet, inte linjär grund för allt du vet din gonna söka igenom varje enskild nål, ting av hö, försöker leta efter din nål. Och det är inte alltför roligt i min mening. Jag gillar snabbt. Jag gillar effektiv. Och så hårt arbetande studenter Er killar är, vet du arbeta smartare, inte hårdare typ sak, hur man kan kompensera dessa algoritmer. 

Så vi kommer att gå genom bara ett snabbt exempel. Jag tycker att ni borde ha en hand på Binary Search, men om någon är lite fuzzy, vill förstärka det, vi ska bara gå genom ett exempel här. Så vi söker om arrayen innehåller sju. 

Så, är första vi gör titta i mitten, eller hur? Och även du kommer att kunna koda Binär sökning på bara en sekund. Så det kommer att bli kul. Så vi tittar på mitten små arrayer 3. Betyder tre lika 7? Inte. Det är sex. Så, är det mindre än eller större än sju? Mindre än. Ja. Fina jobb killar. Jag känner att jag gillar jag borde ha godis eftersom jag vill kasta ut den i varven. Det är vad jag kommer att göra nästa vecka. Det kommer att hålla er vassa. 

Så vi kasta bort det första halvlek, eller hur? det var mindre än. Vi vet att allt på den vänstra sidan kommer att vara mindre än vad vi är faktiskt ute efter. Så det finns ingen anledning att uppmärksamma det. Bara glöm det. Så, nu tittar vi på vår högra sida, och vi ser i mitten där borta, och nu är det nio. Så, 9 är-- --Everyone? Större än vad vi är söker, eller hur? Så vi kommer att kasta bort allt till höger. Gillar det. Nu är alla vi kvar med är en. Så vi kolla, detta är en vad Vi är ute efter? det är. Vi hittade vad vi ville ha. Så vi är klara. Bilinjär Search. 

Och om du märker, vi hade sju ingångar där. Det tog oss bara som tre gånger, men om du gör som en miljard, ni vet hur många steg det skulle ta om vi hade fyra miljarder saker? Any gissningar? Det är 32. 32 steg för att hitta något i en fyra miljarder elementgrupp på grund av potenser av två. Så två är att 32, är att fyra miljarder. 

Så ganska galet hur du fortfarande inom som ett tämligen litet antal steg hitta något i fyra miljarder element. Så på denna anmärkning, vi är kommer att koda detta så ni kan faktiskt typ av se hur detta fungerar. Okej, så ni kan koda. Jag kommer att låta er prata lite. Lär känna människor runt omkring dig, vilket är vad någon ville från förra avsnittet. 

Så lär känna människorna omkring dig. Prata om lite. Och allt jag vill ha av dig killar är just nu bara försöka skapa en översikt av pseudokod. OK? Oj. Allt jag vill ha av er är att du är bara att fylla i denna stund fallet. Så jag har ställt dessa övre och undre gränser som representerar början och slutet av vår samling. Och du ska faktiskt loopa igenom och räkna ut vad vi gör i denna stund slinga. 

Så om du kan lista out-- jag har en ledtråd there-- vilka är de fall som vi har här? Så om du vill ta reda på fall kommer vi pseudokod dem och sedan ska vi faktiskt koda dem. Och det kommer att bli, jag tänker, förhoppningsvis det ska vara lite enklare än du förväntar dig. För det är inte så mycket kod, faktiskt, vilket är riktigt coolt. 

Mm-hm? 

STUDENTEN [OHÖRBAR]? INSTRUKTÖR: Ja. Det var något att hitta i mitten. 

STUDENT: Så vi kan använda det. OK. 

INSTRUKTÖR: Perfect. Så det är det första vi måste göra. Så hitta mitten. Stor. Så har du en idé om hur vi kan faktiskt hitta mitten med koden? 

STUDENT: Ja. n över 2? INSTRUKTÖR: Så n över 2. Så en sak att komma ihåg är att din övre och undre gränser förändras. Vi håller bromsande delen av arrayen som vi är ute efter att. Så n över 2 fungerar bara för det första vi gör. Så tar övre och nedre i beaktande, Hur kan vi få det mellersta elementet? Eftersom vi vill i mitten mellan övre och nedre, eller hur? Mm-hm? 

STUDENTEN [OHÖRBAR]. 

INSTRUKTÖR: Så vi har lite mitten. Och det ska vara övre plus lägre än 2. Grymt. Det gå vi. En rad nedåt. Ni är på väg. Så nu när vi har vår mitten, vad vill vi göra? Bara i allmänhet. Du behöver inte att koda den. Ja. STUDENTEN [OHÖRBAR]? INSTRUKTÖR: Så det är plus för att du är hitta medelvärdet mellan de två av dem. Så om du tänker på dem som slag att öka in från sidorna, tänk på det när du närmar dig mitten, du vill så. Så om du var på vardera sidan av mitten, och vi har som 5 och 7. När du lägger ihop dem dig få 12, delar du med 2, är 6. 

Ibland är det svårt att förklara varför det fungerar, men om du arbetar igenom ett exempel ibland, det hjälper dig att räkna ut om det bör vara plus eller minus. Ja. 

STUDENTEN [OHÖRBAR] exakt i mitten om de hade ett fall där det finns en hel del mindre antal och som en stort antal? 

INSTRUKTÖR: Så allt du behöver är i mitten av uppsättningen. Så om du hade ett gäng små siffror och sedan en riktigt stor mängd i slutet, det spelar ingen roll. Det avgörande är att de är sorterade, du bara vill titta på mitten av arrayen eftersom du fortfarande skivning ditt problem i hälften. Cool. Så nu när vi har mitt, vad gör vi nu? 

STUDENTEN Jämför. INSTRUKTÖR: Den jämföra. Så jämför mitten till value_wanted. Cool. Så ni ser här uppe har vi detta värde som vi vill ha här uppe. Kom ihåg att detta är en array. Så mitt hänvisar till index. Så vi vill göra värden på mitten. Glöm inte om du vill att jämföra, dubbla jämlikar. Du gör enda lika är du bara kommer att dela ut det, och sedan, naturligtvis, är det kommer att vara det värde du vill ha. Så gör inte det. 

Så vi kommer att se om värdena vid mitten är lika med värdet vi vill ha. Glöm inte dina hängslen. Dropbox bör försvinna. Så vad gör vi i det här fallet? Om det är vad vi vill återvända? Vi försöker säga. 

STUDENT: Skriv ut. 

INSTRUKTÖR: Tja, vi vill inte skriva ut. Så det här är en bool här, så vi vill returnera sant eller falskt. Vi säger, är detta nummer en [? RRA? ?] Så om det är, vi tillbaka bara sant. Om jag kan stava sant. 

STUDENT: Varför skulle du inte returnera noll? INSTRUKTÖR: Så du kunde returnera noll om du ville. Men i detta fall eftersom vår funktion returnerar en bool, Vi behöver gå tillbaka antingen sant eller falskt. STUDENT: När du är säger boolska uttrycket, kan du ställa in den lika med falskt? Som om jag vill säga, om detta villkor inte uppfylls, som är övre lika falskt. Kommer det att förstå om du bara sätta falskt på andra sidan? INSTRUKTÖR: Ja. Så egentligen om du är någonsin göra något som är övre eller lägre, som returnerar sant eller falskt och det är faktiskt dålig stil till säg lika lika sant eller jämlikar lika falskt. Du vill använda detta resultat som själv som din check. Inte vad jag ville. Det är vad jag ville ha. Så i fallet med du frågar om något liknande spara i c. 

Så om vi har int main (void) och ungefär så här. Och du har om är övre av lite input och du är frågar om du kan göra ungefär så här? Rätt? STUDENT: Jag försökte att göra det [OHÖRBAR]. För om it's-- INSTRUKTÖR: Rätt. Så du vill att detta ska vara falska, eller hur? STUDENT: Ja. INSTRUKTÖR: Så i detta fall du vill att den ska köra om det inte är sant. Så cool sak du gör det finns det. Så minns utrop punkt förnekar saker? Det står [OHÖRBAR] betyder inte. Så om vi tittar på just denna del här, skulle du säger att utvärderas till falsk som du vill. Inte falskt är sant, som innebär detta skulle exekvera. Är det vettigt? STUDENT: Ja. INSTRUKTÖR: Awesome. OK. Så vi kunde bara tillbaka sant i detta fall. Så nu har vi två andra fall i det här fallet. Vilka är våra två andra fall? Låt oss bara göra det här sättet. Så låt oss börja med annat Om värden på mitten är mindre än det värde som vi vill ha. Så vårt värde i mitten är mindre än det värde som vi letar efter. 

Så som bundet gör du tror att vi vill uppdatera? Övre eller nedre? Övre? Så vilken sida av matrisen kommer vi att titta på? 

STUDENTEN Den lägre. 

INSTRUKTÖR: Vi kommer vi att titta till vänster. Så annars om litet värde är lägre. Så din mittersta värdet här är mindre än vad vi vill. Så vi vill ta höger sida av vår array. Så vi kommer att uppdatera vår nedre gräns. Så vi ska överlåta vår lägre. Och vad tror du lägre borde vara? STUDENT: Det mittersta värdet? INSTRUKTÖR: Så mitt value-- STUDENT: Plus 1. INSTRUKTÖR: --plus 1. Kan någon berätta för mig varför vi har det plus 1? 

STUDENT: [? Inget värde?] är lika med den. 

INSTRUKTÖR: Rätt. Eftersom vi redan vet att vår mittersta värdet inte är lika med det och vi vill utesluta det från alla efterföljande sökningar. Om du glömmer att plus 1, detta kommer att gilla slinga på obestämd tid. Och du kommer bara att fångas i en oändlig loop och då kommer du segfault och det går dåligt. Så alltid se till att du inte är inklusive det värde som du bara såg på. Så vi tar hand om det med ett plus 1. 

Så nu har vi vår sista villkoret som jag alltid för säkerhets skull Du kan kolla här, annars om värdet på mitten är större än värdet vi vill ha. Det betyder att vi vill den vänstra halvan. Så som man ska vi uppdatera? Övre. Och vad är det här man ska vara lika? USA minus en grund, Naturligtvis vill vi att se till att vi inte är titta på det mittersta värdet igen. Och så har vi det. Det var allt. Det är allt binär sökning är. Det är inte så illa, eller hur? Det är som 10 rader kod med blanktecken. Så mycket kraftfull, mycket användbar, kommer du att använda den i en av dina senare psets. Kanske inte den här, men senare. Så lär det. Älskar det. Den kommer att behandla dig väl. Så är det någon som har någon frågor om binär sökning? Ja. 

STUDENT: Spelar det någon roll om din n är jämnt eller udda? 

INSTRUKTÖR: Nej. Eftersom vi kastade den till mitten som en int, kommer det bara korta av den. Så det kommer att förbli ett heltal och det kommer småningom sortera igenom allt. Så du behöver inte oroa dig för det. Alla bra? Grymt. Cool. Så, ni fick detta. Bildspel. Så när vi talade om, jag vet David nämnts komplexitetsdrifttider. 

Så i bästa fall är det bara en, som vi kallar konstant tid. Kan någon berätta för mig varför det kan vara? Vilken typ av scenario som skulle innebära? Mm-hm. 

STUDENTEN [OHÖRBAR] first-- INSTRUKTÖR: Så mitten är den första element som vi kommer till, eller hur? Så antingen en matris med en eller vad vi letar efter just råkar vara smack dab i mitten. Så det är vårt bästa fall. Du får till verkliga problem, förmodligen inte kommer att nå [OHÖRBAR] så ofta. Hur är vår värsta fall? Vår värsta fall är log n. Och det har att göra med det hela befogenheter två sak som jag talade om. 

Så i värsta fall skulle det innebära att vi var tvungna att hugga arrayen ner tills det var en del av en. Så vi var tvungna att hugga ner det i hälften så många gånger som vi möjligen kunde. Det är därför det är log n eftersom du bara hålla dividera med två. Så antaganden, saker du behöver veta om du någonsin kommer att använda en binär sökning. Dina element måste sorteras. De måste sorteras, eftersom det är det enda sättet du kan veta om du kan att kasta ut hälften av det. 

Om du hade denna rörig väska av siffror och du säger, OK, jag ska kolla mitt nummer och numret jag letar efter är mindre än så, jag ska bara godtyckligt kasta ut hälften. Du skulle inte veta om din nummer i den andra halvan. Din lista måste sorteras. Vad bra, kan detta vara går framåt en liten bit, men du måste ha direktåtkomst. Du måste kunna bara gå till den mellersta del. Om du måste korsa genom något eller så tar du extra steg att komma till den mellersta del, det är inte log n längre eftersom du lägger mer arbete i den. Och detta kommer att göra en liten mer meningsfullt i två veckor, men jag bara typ av ville förord, ge er en uppfattning om vad som är att komma. Men de är de två viktiga antaganden som du behöver för en binär lista. Se till att den är sorterade. Det är den stora en för ni just nu. Och på att vi kan gå in i resten av våra slag. Så fyra sorts-- bubbla, insättning, urval och sammanslagning. De är alla ganska häftigt. Om ni väljer att ta CS 124, du kommer att lära dig om alla möjliga slag. Och om du är en XKCD fan, det är en riktigt cool serie om gillar verkligen ineffektiva slag, som jag starkt rekommendera att du ska titta på. En av dem är som panik sortera, vilket är som, åh nej, tillbaka slumpvis rad. Avstängning systemet. Lämna. Så geeky humor är alltid bra. 

Så är det någon som minns snäll av som bara en allmän uppfattning hur bubbla sortera fungerar. Ni minns? 

STUDENT: Ja. 

INSTRUKTÖR: Gå för det. 

STUDENT: Så du går igenom och om det är större, då du byter de två. 

INSTRUKTÖR: Mm-hm. Exakt. Så du bara iterera igenom. Du kontrollerar två nummer. Om man tidigare är större än en efteråt, du bara byta dem så att i detta sätt alla de högre siffror bubbla upp mot slutet av listan och alla lägre siffror bubbla ner. 

Har han visa er den svala ljudeffekt sortering video? Det är ganska häftigt. Så när Robert sa bara, algoritmen att du bara stega genom listan, byta intilliggande värdena om de inte är i ordning. Och sedan bara fortsätta att upprepa tills du inte gör några swappar. Så inte illa, eller hur? Så vi har bara en snabb exempel här. Så detta kommer att sortera dem i stigande ordning. Så när vi går igenom den första tid, ser vi till åtta och sex är uppenbarligen inte i ordning, vi byta dem. 

Så titta på nästa. Åtta och fyra inte är i ordning. Byta dem. Och sedan åtta och två, byta dem. Det gå vi. Så efter din första passet, du vet att din största antalet kommer att vara hela vägen upptill eftersom det är bara kommer att vara ständigt större än allt annat och det är bara att bubbla upp hela vägen till slutet där. Är det vettigt att alla? Cool. 

Så då tittar vi på vår andra passet. Sex och fyra, switch. Sex och två, switch. Och nu har vi ett par saker i ordning. Så för varje pass som vi gör genom hela vår lista, Vi vet att som så många siffror I slutet kommer har sorterats. Så vi gör ett tredje pass, som är en swap. Och sedan på vår fjärde passera, vi har noll slots. Och så vi vet att vår array har sorterats. 

Och det är den stora sak med bubbel sort. Vi vet att när vi har noll swappar, att innebär att allt är i fullständig ordning. Det är typ hur vi kontrollerar. Så vi kommer också att koda bubbla slag som också är inte så illa. Ingen av dessa är så illa. Jag vet att de kan verka lite skrämmande. Jag vet när jag tog klassen, även när jag undervisade klassen för första gången förra året, Jag var ut, hur gör jag detta? Det är vettigt i teorin, men hur ska vi egentligen göra det? Det är därför jag vill också gå genom kod med er här. Så jag har en pseudo för er den här gången. Så bara ha detta i åtanke när vi håller på att övergången över. Så vi har några räknare som håller reda på våra swappar, eftersom vi måste se till att vi kollar det. Och vi upprepa hela uppsättningen som vi gjorde just med detta exempel. Om elementet innan är större än elementet efter var vi är på, Vi byter dem och vi öka vår räknare eftersom så snart vi byta, Vi vill låta vår räknare vet. Några frågor där? Något verkar roligt här. STUDENT: Har du ställa räkneverket noll varje gång du går genom öglan? Vill du inte fortsätta tillbaka till noll varje gång? INSTRUKTÖR: Inte nödvändigtvis. Så vad som händer är att vi går igenom här. Så gör samtidigt, kom ihåg, detta kommer att utföra en gång utan att misslyckas. Så det kommer att ställa in räknaren är lika med noll, då det kommer att iterera igenom. Som det itererar igenom, det kommer att uppdatera räknaren. Som det uppdateras räknaren, när det är gjort, när det har nått slutet av arrayen, Om vår lista inte har sorterats, räknaren har uppdaterats. 

Så då är det en kontroll utförs och det säger, OK, är räknaren är större än noll. Om det är, gör det igen. Du vill återställa så att när du går igenom, är räknaren är lika med noll. Om du går igenom en sorterad array, förändrar ingenting, detta misslyckas, och du returnera den sorterade listan. Är det vettigt? STUDENT: Det kanske i lite. INSTRUKTÖR: OK. Om det finns någon annan fråga som kommer upp. Ja. 

STUDENTEN Vad skulle funktionen vara för att byta element? 

INSTRUKTÖR: Så vi kan faktiskt skriva att om vi ska just nu. Cool. Så på att observera, är Alison går för att växla tillbaka till apparaten. Det kommer att bli kul. Och vi har vår trevliga bubbla sortera sak här. Så jag gjorde redan cykling genom uppsättningen. Vi har våra swappar som är lika med noll. Så vi vill byta intilliggande element om de är ur funktion. Så det första måste vi gör är iterera igenom vår samling. 

Så hur tycker du att vi kanske iterera genom vår array? Vi har för och jag är lika med 0. Vi vill att jag ska vara mindre än n minus 1 minus k. Och jag ska förklara det på en sekund. Så detta är en optimering här där, minns hur jag sa efter varje pass genom uppsättningen vi vet att vad som än är on-- 

Så efter ett pass vi vet att detta är sorterad. Efter två passager vi vet att allt detta är sorterad. Efter tre passager vi vet som är sorterade. Så långt jag iteration genom uppsättningen här, är det att se till att bara gå genom vad vi vet är osorterat. OK? Det är bara en optimering. Du kan skriva det naivt bara iterera igenom allt, Det skulle bara ta längre tid. Med denna fyra slinga är det bara en trevlig optimering eftersom vi vet att efter varje helt iteration genom uppsättningen här, som varje hel slinga här, vi vet att en av dessa komponenter kommer att sorteras i slutet. 

Så vi behöver inte oroa dig för dem. Är det vettigt att alla? Den coola lilla trick? Så i så fall, om vi iterera igenom, vi vet att vi vill kontrollera om array n och n plus 1 är i ordning. OK. Så här är pseudokod. Vi vill kolla om array n och n plus 1 är i ordning. Så vad kan vi ha det? Det kommer att bli lite villkor. Det kommer att bli en om. 

STUDENT: Om matris n är mindre än array n plus 1. INSTRUKTÖR: Mm-hm. Tja, mindre än eller större än. STUDENT: Större än. Då vill vi att byta dem. Exakt. Så nu får vi in ​​vad är det mekanism för att byta dem? Så vi gick igenom det här en kort stund, en typ av swap-funktion förra veckan. Finns det någon som minns hur det fungerade? Så vi kan inte bara överlåta dem, eller hur? Eftersom en av dem kommer att gå vilse. Om vi ​​sagt A är lika med B och sedan B är lika med A, alla en plötslig båda av dem är bara lika med B. 

Så vad vi har att göra är att vi har en temporär variabel som är kommer att hålla en av våra stund vi är i färd med att byta. Så vad vi har är att vi ska ha lite int temp är lika att-- du kan tilldela den till vilken du vill, bara se till att du hålla reda på det-- så i det här fallet, kommer jag att tilldela den till array n plus 1. Så det kommer att innehåla värde i det andra blocket att vi tittar på. 

Och då vi kan göra är att vi kan gå framåt och tilldela array n plus 1, eftersom vi vet att vi har detta värde lagras. Detta är också en av de stora saker-- Jag vet inte om någon av er hade frågor där om du byter två kodrader plötsligt saker fungerade. Order är mycket viktigt i CS. Så se till att du diagram saker ut om det är möjligt om vad som faktiskt händer. Så nu ska vi överlåta array n plus 1, eftersom vi vet att vi har detta värde lagras. 

Och vi kan tilldela till array n eller i detta fall array i. För många variabler. OK. Så nu har vi tilldelas array i plus 1 till lika vad som finns i arrayen i. Och nu kan vi gå tillbaka och tilldela array i vad? Någon? 

STUDENTEN 10. 

INSTRUKTÖR: 10. Exakt. Och en sista sak. Om vi ​​har bytt det nu, Vad behöver vi göra? Vad är en sak det kommer att berätta om vi någonsin avsluta det här programmet? Vad säger oss att vi har en sorterad lista? Om vi ​​inte utför några swappar, eller hur? Om swappar är lika med noll vid slutet av denna. Så varje gång du gör en swap, som vi just gjorde här, vi vill uppdatera swappar. Och jag vet att det fanns en fråga tidigare om kan du använda noll eller ett i stället av sant eller falskt. Och det är vad det gör här. Så detta säger om inte swappar. Så om swappar är noll, som är-- jag alltid få mina sanningar och mina falses blandas ihop. Vi vill att vi ska utvärdera till true, och det är inte. Så om det är noll, då är det falskt. Om du förnekar det med en [? bang?] blir det sant. Så då denna linje körs. 

Sanningar och falska och nollor och ettor blir galen. Bara om du sakta gå igenom det kommer det att vara meningsfullt. Men det är vad denna lilla bit kod här gör. Så detta kontrollerar för att se Vi har gjort några swappar. Så om det är något annat än noll, det kommer att vara falsk och det hela är kommer att exekvera på nytt. Cool? 

STUDENTEN Vad gör break göra? 

INSTRUKTÖR: Bryt bara bryter dig ut ur loopen. Så i detta fall att det skulle precis som avslutar programmet och du skulle bara har din sorterad lista. STUDENT: Amazing. INSTRUKTÖR: Jag är ledsen? STUDENT: Eftersom vi tidigare används skrivit 1 över skriven noll att presentera att om det kommer att fungera eller inte. 

INSTRUKTÖR: Ja. Så du kan returnera noll eller 1. I det här fallet, eftersom vi är faktiskt inte gör något med funktionen, Vi vill bara att det ska gå sönder. Vi vet inte riktigt bryr sig om det. Brake är också bra om den används för att bryta ut av fyra slingor eller villkor som du inte vill behålla utföra. Det tar bara dig ur dem. Det är lite av en nyans sak. Det känns som det finns en hel del för hand vinka, som du kommer att lära dig mer om detta snart. 

Men du kommer att lära dig mer om detta snart. Jag lovar. OK. Så gör alla får bubbla sortera? Inte så illa. Iterera igenom, swap saker med en temp variabel, och vi är allt klart där? Cool. Grymt. OK. Tillbaka till PowerPoint. Eventuella frågor i allmänhet om dessa så långt? Cool. Mm-hm. 

STUDENTEN [OHÖRBAR] int main oftast. Måste man ha det för detta? 

INSTRUKTÖR: Så vi bara ute precis vid den faktiska sorteringsalgoritm. Om du hade det inom som ett större program, du skulle ha en int main någonstans. Beroende på var du använda denna algoritm, Det skulle avgöra vad som är som returneras av den. Men för vårt fall, vi är strikt titta på hur fungerar det egentligen iterera genom en matris. Så vi behöver inte oroa dig för det. 

Så vi pratade om bästa fall och värsta tänkbara scenarier för binär sökning. Så det är också viktigt att göra att för var och en av våra slag. Så vad tror du är det värsta fall runtime bubbla slag? Ni minns? 

STUDENT: N minus 1. INSTRUKTÖR: N minus 1. Så det innebär att det finns n minus 1 jämförelser. Så en sak att inse är att på den första iterationen, vi går igenom, vi jämför dessa two-- så det är 1. Dessa två, tre, fyra. Så efter en iteration vi redan har fyra jämförelser. När jag pratar om körtid och n. N representerar antalet jämförelser som en funktion av hur många element vi har. OK? 

Så vi går igenom, vi har fyra. Nästa gång du vet gör vi inte måste ta hand om detta. Vi jämför dessa två, dessa två, dessa två, och om vi inte hade att optimering med fyra slinga som jag skrev, du skulle jämföra in här ändå. Så du skulle behöva köra igenom arrayen och göra N jämförelser n gånger, eftersom varje gång vi köra igenom det vi sorterar en sak. 

Och varje gång vi kör igenom arrayen, vi gör n jämförelser. Så vår runtime för detta är faktiskt n kvadrat, vilket är mycket värre i vår log slutet eftersom det innebär om vi hade fyra miljarder element, det kommer att ta oss fyra miljarder kvadrat i stället för 32. Så inte den bästa runtime, men för vissa saker, du vet, om du är inom ett visst antal element bubbla slag kan vara bra att använda. 

OK. Så nu vad är det bästa fallet runtime? STUDENTEN Zero? Eller 1? 

INSTRUKTÖR: So 1 skulle vara en jämförelse. Höger. 

STUDENT: N minus 1? 

INSTRUKTÖR: Så, ja. Så n minus 1. När du har ett koncept som n minus 1, tenderar vi att bara släppa det och vi bara säga n för att du har att jämföra var och en av these-- varje par. Så det skulle vara n minus 1, som vi Vi skulle bara vilja säga är ungefär n. När du arbetar med runtime, allt är i approximerar. Så länge exponenten är korrekt, du är ganska bra. 

Det är hur vi hanterar den. Så att det bästa fallet är n, vilken innebär att listan redan är sorterad, och allt vi gör drivs via och kontrollera att den är sorterade. Cool. Okej. Så som ni ser här, vi bara har några fler grafer. Så n kvadrat. Fun. Mycket värre än n som vi ser, och mycket, mycket värre än log 2n. Och då får du också in i logg stockar. Och du tar 124, får du in som log stjärnan, som är som galen. Så om du är intresserad, lookup log stjärna. Det är ganska kul. Så vi har denna stora diagrammet. Bara en huvuden upp, detta är en underbart diagrammet att ha för din halva tiden eftersom vi lång tid att ställa dig dessa tunnar. Så bara en huvuden upp, har detta på din halva tiden på din fina fusklapp där. Så vi bara tittade på bubblan slag. I värsta fall, n kvadrat, bästa fall, n. Och vi kommer att titta på de andra. 

Och som ni kan se, den enda en som verkligen gör bra är merge sort, som vi kommer att få in på varför. Så vi kommer att gå till nästa här-- val slag. Finns det någon som minns hur urval sorterar fungerat? Gå för det. 

STUDENT: I ​​grund och botten gå igenom en beställning och skapa en ny lista. Och precis som du sätter element i, lägg dem på rätt plats i den nya listan. 

INSTRUKTÖR: Så det låter mer som inför slag. Men du är riktigt nära. De är mycket lika. Även jag får dem blandas ihop ibland. Innan detta avsnitt jag var som, vänta. OK. Så vad du vill do är urval sortera, det sätt du kan tänka dig om det och hur Jag ser till att jag försöker att inte få dem blandas ihop, är det går igenom och väljer den minsta antalet och det sätter det i början av din lista. Det byter det med den första platsen. De har faktiskt en förebild för mig. Grymt. Så bara ett sätt att tänka på det-- urval sortera, välja det minsta värdet. Och vi kommer att köra igenom ett exempel som jag tror kommer att hjälpa eftersom Jag tror visuella alltid hjälpa. Så vi börjar med något som är helt osorterat. Rött är osorterade, gröna kommer att sorteras. Det kommer allt vettigt i en sekund. 

Så vi går igenom och vi iterera från början till slut. Och vi säger, OK, 2 är vår minsta antalet. Så vi kommer att ta två och vi kommer att flytta den till framsidan av vår array eftersom det är den minsta antalet har vi. Så det är vad det gör här. Det är bara att byta dessa två. Så nu har vi en sortering del och en osorterad del. Och vad som är bra att komma ihåg om urval sorterar är vi bara välja från osorterade delen. 

Den sorterade delen du bara lämna ensam. Mm-hm? 

STUDENT: Hur fungerar det vet vad som är de minsta utan att jämföra till varje annat värde i arrayen. INSTRUKTÖR: Det gör det jämföra det. Vi gillar hoppade över det. Detta är bara allmänt övergripande. Yeah. När vi skriver koden är jag säker på att du kommer att bli mer nöjda. Men du lagrar denna första elementet som den minsta. Du jämföra och du säger, OK, det är mindre? Ja. Håll det. Här är det mindre? Nej? 

Detta är din minsta, tilldela den till ditt värde. Och du kommer att bli mycket lyckligare När vi går igenom koden. Så vi går igenom, vi byta den, så då vi ser på detta osorterade delen. Så vi kommer att välja tre. Vi kommer att sätta upp det på vid I slutet av vår sorterade delen. Och vi ska bara fortsätta göra att göra det, och göra det. Så det här är vår typ av pseudokod här. Vi ska koda upp det här på en sekund. Men bara något att gå igenom på en hög nivå. Du kommer att gå från i är lika med 0 till n minus 2. Det är en annan optimering. Oroa dig inte för mycket om det. Så som ni sa. Som Jakob sa, hur gör vi hålla reda på vad vår minsta är? Hur vet vi det? Vi måste jämföra allt i vår lista. 

Så minimum är lika i. Det är bara att säga i det här fallet index för vår minsta värde. Så då det kommer att iterera igenom och det går från j är lika med i plus 1. Så vi vet redan att det är vår första elementet. Vi behöver inte jämföra det med sig själv. Så vi börjar jämföra det till nästa en som är varför det är i plus 1 till n minus 1, vilket är den slutet av arrayen där. Och vi sa att om array på j är mindre än array min, sedan omtilldela vi där våra lägsta index är. 

Och om min är inte lika med I, såsom i där vi var tillbaka hit. Så som när vi först gjorde detta. I detta fall skulle det börja på noll, skulle det hamna två. Så min skulle inte lika i till slut. Det låter oss veta att vi behöver byta dem. Jag känner mig som ett konkret exempel kommer att bidra mycket mer än detta. Så jag ska koda upp detta med er just nu och jag tror det blir bättre. 

Sorterar tenderar att arbeta på det sättet i det Det är ofta bättre bara för att se dem. Så vad vi vill göra är att vi först vill ha den minsta element i sin position i arrayen. Exakt vad Jakob sade. Du måste lagra den på något sätt. Så vi kommer att börja här iteration över arrayen. Vi kommer att säga att det är vår första bara för att börja med. Så vi kommer att ha int minsta är lika med array på i. 

Så en sak att lägga märke till, varje tid denna slinga exekverar, Vi börjar ett steg längre fram. När vi börjar vi tittar på detta. Nästa gång vi iterera igenom, vi börjar på den här och tilldela det vår minsta värde. Så det är mycket lik bubbla sortera där vi vet att efter ett pass, denna sista elementet sorteras. Med valet sortera, Det är precis tvärtom. 

Vid varje pass, vet vi att den första sorteras. Efter det andra passet, det andra kommer att sorteras. Och som du såg med glid exemplen, våra sorterade delen blir bara växer. Så genom att sätta vår minsta till arrayer i, allt det gör är bromsande vad vi tittar på så för att minimera antalet jämförelser vi gör. Betyder det vettigt för alla? Vill du att jag ska gå igenom det åter långsammare eller i olika ord? Jag är glad att. OK. 

Så vi förvarar värde vid denna punkt, men vi vill också lagra index. Så vi kommer att lagra positionen för det minsta en, som just kommer att vara i. Så nu Jacob är uppfyllt. Vi har saker som lagras. Och nu måste vi titta igenom den osorterade del av matrisen. Så i detta fall skulle vara vår osorterat. Detta är i. OK. 

Så vad vi ska göra kommer att vara för en slinga. Närhelst du behöver iterera genom en matris, ditt sinne kunde gå till för en slinga. Så för vissa int k equals-- vad vi tänker k kommer att vara lika till att börja med? Detta är vad vi satt som vår minsta värde och vi vill jämföra den. Vad vill vi jämföra det med? Det kommer att vara så här nästa, eller hur? Så vi vill k initieras till i plus 1 för att starta. 

Och vi vill ha k vi i detta fall redan har storlek lagrat upp här, så vi kan bara använda storlek. Storlek att vara storleken på matrisen. Och vi bara vill uppdatera k med ett varje gång. Cool. Så nu måste vi hitta det minsta elementet här. Så om vi iterera igenom, vi vill säga, om array på k är mindre än vår minsta value-- det är där vi faktiskt hålla reda på vad som är den minsta här-- då vill vi att omplacera vad vår minsta värdet är. 

Detta innebär att, åh, vi är iterera igenom här. Oavsett värdet här är inte vårt minsta sak. Vi vill inte ha det. Vi vill dela ut det. Så om vi omplacera den, vad gör du tror kan vara i denna kod här? Vi vill tilldela minsta och placering. Så vad är minsta nu? STUDENTEN Array k. INSTRUKTÖR: Array k. Och vad är läget nu? Vad är de index i vår minsta värde? Det är bara k. Så array k, k, matchar de upp. Så vi ville att omplacera det. Och sedan när vi hittat vår minsta, så vid slutet av denna för slingan här har vi hittat vad vår minsta värdet är, så vi bara byta den. I detta fall, liksom säga vår minsta värdet är här ute. Detta är vår minsta värde. 

Vi vill bara byta den här, som är vad det swap-funktion i botten gjorde, som vi just skrev upp ihop ett par minuter sedan. Så det ska se bekanta. Och då kommer det bara iterera igenom tills den når hela vägen till slutet, vilket innebär att du har noll element som osorterade och allt annat har sorterats. Vettigt? Lite mer konkret? Koden hjälp? 

STUDENT: För en storlek, du aldrig verkligen definiera det eller ändra det, hur går det vet? 

INSTRUKTÖR: Så en sak till märker upp här är int storlek. Så vi säger i denna sort-- sort är en funktion i det här case-- det är val sortera, det passerade in med funktionen. Så om det inte skickades in, skulle du göra något liknande med längden av uppsättningen eller skulle du iterera igenom att hitta längden. Men eftersom det är passerat i, kan vi bara använda den. Du tar bara att användaren gav dig en giltig storlek som faktiskt representerar en storlek på din array. Cool? 

Om ni har några problem med dessa eller vill ha mer praxis kodning sorterar på egen hand, bör du gå till study.cs50. Det är ett verktyg. De har en pjäs som Du kan faktiskt skriva. De gör pseudokod. De har fler videor och diabilder inklusive de som jag använder här. Så om du fortfarande känner dig lite luddigt, prova att. Som alltid, kom prata med mig också. Fråga? 

STUDENT: Säger du det Storleken är som tidigare definierats? INSTRUKTÖR: Ja. Storleken tidigare definierats upp här i funktionsdeklarationen. Så du antar att det har gått i av användaren, och för enkelhets skull, vi kommer att anta att Användaren gav oss rätt storlek. Cool. Så det är val slag. Killar, jag vet att vi lär oss en hel dag. Det är en tät uppgifter för avdelning. Så med detta kommer vi för att gå till insättnings sort. 

OK. Så innan vi måste göra vår runtime analys här. Så i bästa fall beviljats ​​sedan jag visade dig tabellen jag redan slags gav det bort. Men bästa fall runtime, vad tror vi? Allt sorteras. N i kvadrat. Någon har en förklaring för varför du tror? 

STUDENT: Du jämföra through-- INSTRUKTÖR: Rätt. Du jämför igenom. Vid varje iteration, trots att vi nedräkning detta efter en, du fortfarande söka igenom allt för att hitta den minsta. Så även om din minsta värde är här i början, du fortfarande jämföra det mot allt annat att se till att det är det minsta. Så du kommer att sluta som löper genom ca n kvadrat gånger. Okej. Och vad är det värsta? Också n kvadrat eftersom du kommer att göra det samma procedur. Så i detta fall, val sortera har något som vi kallar också förväntade runtime. Så i de andra, vi vet bara de övre och undre gränser. Beroende på hur galen vår Listan är eller hur osorterat det är, de varierar mellan n eller n kvadrat. Vi vet inte. 

Men eftersom valet sort har samma värsta och bästa fall, berättar att för oss att oavsett vilken typ av input vi ha, oavsett om det är helt sorterat eller fullständigt vända sorteras, det är kommer att ta lika lång tid. Så i så fall, om du minns från vårt bord, det faktiskt hade ett värde som dessa två typer har inte, vilket är förväntat runtime. Så vi vet att när Vi kör val sortera, det är garanterat köra en n kvadrerade tid. Det finns ingen variation där. Det är bara väntat. Och, återigen, om du vill lära dig mer, ta CS 124 under våren. Okej. Vi har sett den här. Cool. Så insättnings slag. Och jag kommer nog att flamma igenom detta. Jag kommer inte att ha er koda den. Vi ska bara gå igenom det. Så insättnings slag är snäll av liknande val Sortera i att vi har både en osorterad och sorteras del av matrisen. 

Men vad är annorlunda är att när vi går igenom en efter en, vi bara ta de nummer är nästa i vår osorterade, och korrekt sortera in i vår sorterade arrayen. Det kommer att vara bättre med ett exempel. Så allt börjar som osorterat, precis som med val slag. Och vi kommer att lösa detta på stigande ordning som vi har varit. Så på vår första passet Vi tar det första värdet och vi säger, OK, du är nu i en lista själv. 

Eftersom du är i en lista själv, du är sorterade. Grattis för att vara första elementet i arrayen. Du är redan sorterade allt på egen hand. Så nu har vi en sortering och en osorterad array. Så nu tar vi det första. Vad händer mellan här och här är det vi säger, OK, vi kommer att titta på första värdet av vår osorterade array och vi kommer att mata in den i dess rätt ställe i den sorterade arrayen. 

Så vad vi gör är tar vi 5 och vi säger, OK, 5 är större än 3, så vi bara sätta in den rätt till höger om denna. Vi är bra. Så då går vi vidare till vår nästa. Och vi tar 2. Vi säger, OK, 2 är mindre än 3, så vi vet att det behöver vara vid framför vår lista nu. Så vad vi gör är att vi trycker 3 och 5 ner och vi går 2 i det första facket. Så vi bara sätter in det i rätt plats det ska vara. 

Då vi tittar på vår nästa en, och vi säger 6. OK, är 6 större än allt i vårt sorterade arrayen, så vi bara tagga det till slutet. Och så tittar vi på 4. 4 är mindre än 6, är det mindre än 5 men det är större än 3. Så vi bara sätta in den rätt in mitten mellan 3 och 5. Så för att göra det lite lite mer konkret, här är typ av uppfattning om vad som hände. Så för varje osorterade element, vi bestämma var i den sorterade delen det är. 

Så med tanke på sorterade och osorterade, vi har att passera genom och figur på var den passar i den sorterade arrayen. Och vi för in den genom att flytta element till höger om den. Och då är vi bara hålla iterera igenom tills vi ha en helt sorterade listan där osorterade nu är noll och sorterade tar upp helhet på vår lista. Så, återigen, att göra saker ännu mer konkret, vi har pseudokod. 

Så i princip för i är lika med 0 till n minus 1, det är bara längden på vår array. Vi har en del inslag som är lika med den första uppsättningen eller de första indexen. Vi sätter j lika med den. Så medan j är större än noll och matrisen, j minus ett är större än den element, så allt som gör är att se till att din j verkligen representerar den osorterade delen av matrisen. 

Så medan det finns fortfarande saker att sortera och j minus ett är-- vad är elementet henne? J var aldrig definieras här. Det är typ av irriterande. OK. Anyways. Så j minus 1, du kontrollerar elementet innan det. Du säger, OK, är elementet innan vart jag am-- låt oss faktiskt dra ut denna. Så låt oss säga att detta är som på våra andra passet. Så jag kommer att vara lika till 1, vilket är här. 

Så jag kommer att vara lika med 1. Detta skulle vara 2, 4, 5, 6, 7. Okej. Så vår del i detta ärende kommer att vara lika med 4. Och vi har några j som är kommer att vara lika med ett. Åh, är j nedräkning. Det är vad det är. Så j är lika med i, så vad det här är säger är att när vi går framåt, vi bara att se att vi inte är över indexera det här sättet när vi försöker att sätta saker i vår sorterade listan. 

Så när j är lika med 1 i detta fall och array j minus en-- så array j minus 1 är 2 i denna case-- om det är som är större än elementets, då allt detta gör skiftar ner saker. Så i detta fall, array j minus ett vore array noll, vilket är 2. 2 inte är större än 4, så detta inte köra. Så övergången inte rör sig nedåt. Vad detta innebär här är bara flytta din sorterade arrayen ner. I det här fallet, faktiskt, vi kunde do-- låt oss göra detta 3. Så om vi ska gå igenom med Detta exempel är vi nu här. Detta är sorterad. Detta är osorterade. Cool? Så i är lika med 2, så vår del är lika med 3. Och vår j är lika med 2. Så vi tittar igenom och vi säger, OK, är array j minus en större än elementet att vi tittar på? Och svaret är ja, hur? 4 är större än 3 och j är 2, så den här koden körs. 

Så nu vad vi gör en matris på 2, så just här, vi byta dem. Så vi bara säga, OK, array vid 2 kommer nu att bli 3. Och j kommer att vara lika j minus 1, vilket är ett. Det är hemskt, men ni får idén. J är nu lika med 1. Och array j bara kommer att bli lika med vår del, vilket var 4. Jag raderade något jag inte borde har eller miswrote något, men ni förstår tanken. 

Det rör sig med n. Och sedan om det fanns, skulle det loop igen och det skulle säga, OK, är j 1 nu. Och array j minus 1 är nu 2. Är 2 mindre än vår del? Nej? Det innebär att vi har insatt detta element på rätt plats i vårt sorterade arrayen. Då kan vi ta detta och vi säger, OK, är vår sorterade arrayen här. Och det skulle ta detta nummer 6 och vara liknande, OK, är 6 färre än detta antal? Nej? Cool. Vi är bra. 

Gör det igen. Vi säger 7. Är 7 färre än i slutet av våra sorterade arrayen? Nej. Så vi är bra. Så detta skulle sorteras. I princip allt detta gör det säger take den första delen av din osorterat array, räkna ut var det går i ditt sorterade arrayen. Och detta bara tar hand av swappar för att göra det. Du är i princip bara byta tills det är på rätt plats. Den visuella bilden är att du är flytta ned allt genom att göra det. 

Så det är som en halv bubbla sort-esque. Kolla undersökning 50. Jag rekommenderar starkt försöker att koda detta på egen hand. Om du har några frågor eller om du vill se exempelkod för en insättnings sortera, låt mig veta. Jag är alltid runt. Så värsta fall runtime och bästa fall runtime. Som ni killen såg från bordet jag redan visade dig, det är både n kvadrat och n. 

Så snäll att gå ut med vad vi pratade om med våra tidigare slag, värst fall runtime är att om det är helt osorterade, vi har att jämföra alla dessa n gånger. Vi gör en hel del jämförelser eftersom om det är i omvänd ordning, vi ska säga, OK, detta är densamma, är det bra, och här måste jämföras mot den första en att flyttas tillbaka. Och när vi får in mot svansen slutet, vi har att jämföra, jämföra och jämföra mot allt. 

Så det slutar som ungefär n kvadrat. Om det stämmer så har du säger, OK, 2, du är bra. 3, du är jämfört med 2. Du är bra. 4, du bara jämför med svansen. Du är bra. 6, jämför med svansen, du är bra. Så för varje plats om det redan sorterade, du gjorde en jämförelse. Så det är bara n. Och eftersom vi har en bästa fall runtime n och ett värsta runtime n kvadrat, har vi ingen förväntad körtid. 

Det beror bara på kaos på vår lista där. Och återigen, en annan graf och en annan tabell. Så skillnader mellan sorter. Jag kommer bara att knäppa genom, jag känns som vi har pratat utför om hur de alla typer av att variera och länka samman. Så Merge sort är den sista Jag ska tråka ut er med. Vi har en ganska färgstark bild. Så samman slag är en rekursiv algoritm. Så gör ni vet vad en rekursiv funktion är? 

Någon vill säga? Vill du prova? Så en rekursiv funktion är bara en funktion som kallar sig. Så om ni känner med Fibonacci-sekvensen, som har bedömts rekursiv eftersom du tar de två föregående och lägga ihop dem att få din nästa. Så rekursiv, tror jag alltid av rekursion som likt en spiral så du är som spiral ner i den. Men det är bara en funktion som kallar sig. 

Och, faktiskt, riktigt snabbt jag kan visa dig vad som ser ut som. Så rekursiv här, om vi ser, är detta den rekursiva sättet att summera över en array. Så allt vi gör är Vi har sum funktion summa som tar en storlek och en array. Och om du märker, storlek minskningar av en varje gång. Och allt det gör är om x är lika med zero-- så om storleken på matrisen är lika med zero-- den returnerar noll. 

Annars summerar detta sista elementet i arrayen, och sedan tar en summa resten av matrisen. Så det är bara att bryta ner i mindre och mindre problem. Lång historia kort, rekursion, funktion som kallar sig. Om det är allt du fick ut av detta, det är vad en rekursiv funktion är. Om du tar 51, du kommer att få mycket, mycket bekväma med rekursion. Det är verkligen häftigt. Det var meningsfullt på liknande 03:00 en natt. Och jag var som, varför har jag aldrig detta? 

Så för merge sort, i princip Vad det kommer att göra är att det är kommer att bryta ner det och bryta ner tills det är bara enskilda element. De enskilda delarna är lätta att sortera. Vi ser att. Om du har en del, det är redan som sorteras. Så på en ingång av n element, om n är mindre än 2, bara tillbaka eftersom det betyder det är antingen 0 eller 1 som vi har sett. De som anses sorterade element. 

Annars bryter den på mitten. Sortera första halvlek, sortera den andra hälften, och sedan sammanfoga dem tillsammans. Varför det kallas merge sort. Så vi har här vi ska sortera dessa. Så vi fortsätter att ha dem tills matrisstorlek är 1. Så när det är 1, vi bara tillbaka eftersom detta är en sorterad array, och detta är en sorterad array, och det är en sorterad array, vi alla sorterade. Så vad vi gör är att vi börja slå samman dem tillsammans. 

Så hur kan du tycker om sammanslagning är du bara ta bort den mindre antal av vardera av underuppsättningar och bara lägga den till framkommit arrayen. Så om du tittar här, när vi har dessa uppsättningar vi har 4, 6 och 1. När vi vill sammanfoga dessa, vi tittar på dessa två första och vi säger, OK, 1 är mindre, Det går till fronten. 4 och 6, det finns inget att jämföra det, bara tagga den på till slutet. 

När vi kombinerar dessa två, vi bara ta den mindre en av dessa två, så det är 1. Och nu tar vi mindre av dessa två, så 2. Mindre av dessa två, 3. Mindre av dessa två, fyra, fem, sex. Så du bara dra av dessa. Och eftersom de har sorterats tidigare, Du har bara en Jämförelsen varje gång. Så mer kod här, bara representation. Så du börjar på mitten och du sorterar vänster och höger och då du bara slå ihop dem. 

Och vi har inte kod för samman just här. Men, återigen, om du går på studera 50, det ska vara där. Annars kommer prata med mig om du fortfarande förvirrad. Så cool sak här är att i bästa fall, värsta fall, och förväntade runtime är alla i log n, vilken är mycket bättre än vi har sett för resten av våra slag. Vi har sett n kvadrat och vad vi faktiskt ta sig hit är n log n, vilket är bra. 

Titta på hur mycket bättre det är. En sådan fin kurva. Så mycket mer effektivt. Om du någonsin kan, användning samman slag. Det kommer att spara tid. Då igen, som sagt, om du är i detta nedre regionen, Det gör inte det mycket av en skillnad. Du får upp till tusentals och tusentals insatsvaror, du absolut vill ha en mer effektiv algoritm. Och, återigen, vår fina tabell över alla sorterar att ni lärt idag. 

Så jag vet att det har varit en tät dag. Detta är inte nödvändigtvis kommer för att hjälpa dig med din pset. Men jag vill bara göra en ansvarsfriskrivning det avsnittet handlar inte bara om psets. Allt detta material är rättvist spel för dina midterms. Och även om du fortsätter med CS, dessa är verkligen viktiga fundamenta att du skulle behöva veta. Så vissa dagar kommer att vara en lite mer pset hjälp, men några veckor kommer att vara mycket mer faktiska innehållet som kanske inte verkar super användbart för dig just nu, men jag lovar om du fortsätter på kommer att bli mycket, mycket användbart. 

Så det är det för avsnitt. Ner till viran. Jag gjorde det inom en minut. Men där du går. Och jag kommer att ha munkar eller godis. Är någon allergisk mot något, förresten? Ägg och mjölk. Så munkar är ett nej? OK. Okej. Choklad nej? Starburst. Starbursts är bra. OK. Vi kommer att ha Starburst nästa vecka då. Det är vad jag får. Ni har en bra vecka. Läs din spec. 

Låt mig veta om du har några frågor. Pset två kvaliteter bör vara ut till dig av torsdagen. Om du har några frågor om hur jag graderade något eller varför jag graderade något som jag gjorde, vänligen maila mig, kom prata med mig. Jag är lite galen ut vecka, men jag lovar Jag kommer fortfarande att svara inom 24 timmar. Så ha en bra vecka, alla. Lycka till på din pset.