SPEAKER 1: Hei kõigile! Tere tulemast tagasi lõik. Nii hea meel näha, et paljud teist nii siin, ja igaüks, kes valvab võrgus. Nii nagu ikka teretulnud tagasi. Loodan, et teil kõigil oli armas Nädalavahetusel täielikult puhata, lõõgastuda. See oli ilus välja eile. Niisiis, ma loodan, et te nautida õues. 

Nii et esimese paari teadaandeid. Hindamissüsteem. Niisiis, enamik teist oleks saanud saatke mulle oma Scratch pset, samuti liigitamise eest pset 1. Niisiis, lihtsalt paar asja. Kindlasti kasutada check50 sisse style50. Need on mõeldud olema ressursse kutid, veenduda, et te saate nii palju punkte kui võimalik ilma asjata kaotamisega. Niisiis, asjad nagu stiil on väga olulised. Me startida ta. Mõned teist võivad olla juba märganud, et oma pset. Ja check50 on lihtsalt väga lihtne viis, veendumaks, et me tegelikult tagastamise tuleb tagasi kasutaja ja et kõik töötab korralikult. 

Teisel tähele, veenduge, et teie üleslaadimisel asjad õigesse kausta. See teeb mu elu lihtsalt natuke raskem kui saadate pset 2 arvesse pset 1 sest kui ma alla laadida asju, nad ei lae korralikult. Ja ma tean, et see on natuke logisev süsteemis harjuda, aga lihtsalt super ettevaatlik, kui ainult minu jaoks, nii et kui te saate e-kirju on nagu 02:00 ja ma olen mune. Kui ei põhjusta pean vaatama kogu oma pset. Külm. 

Ma tean, et see vara, aga ma täiesti sai maha võetud valvur mida essee, mis on tingitud sel reedel, et minu professorid olid lihtsalt meeldib, oh yeah. Pea meeles, et teil on essee tõttu reedel. Niisiis, ma tean, et keegi ei meeldi mõelda midterms, aga oma esimesele viktoriin on 15. oktoobril mis oktoober on alates sellest nädalast. Niisiis, see võib olla varem kui sa oodata on kõik. Nii et sa ei visatud välja kaitsepiire kui Mainin järgmise nädala jagu, et oh, Sinu viktoriin järgmisel nädalal, ma arvasin Ma annan teile natuke rohkem heads up nüüd. 

Seega on teie probleem määrata, number kolm. Kuidas inimesed lugenud spec uudishimust? OK. Saime paar. Kind of maha viimane nädalas, kuid see on OK. Ma tean, et see oli ilus välja. Nii et välja murda. Kindlasti pärast sa saad teha täna lugeda oma spec vähemalt proovida nagu allalaadimine jaotus kood ja töö nagu esimese esialgse asi, mida nad paluda teil. Kuna me kasutame jaotus kood ja raamatukogu et me oleme alles kasutades-- --It on ainult teist korda oleme teinud seda pset, hull asju võib juhtuda oma seadme ja sa tahad teada, et nüüd välja võrreldes hiljem. 

Sest kui see on neljapäeva õhtul või see on Kolmapäeva õhtul ja mingil põhjusel Teie seade lihtsalt ei tahan joosta raamatukogu või jaotus kood, mis vahendid te ei saa isegi alustada teed kodeerimine. Sest sa ei saa kontrollida et näha, kas see toimib. Teie ei hakka saama kas see kogub. Sa tahad, et hoolitseda nende vara nädalal, kui saate siiski emaili mulle või mõnda muud TF, ja me saame need fikseeritud. Kuna need on küsimused mis hakkavad teid peatada tegemast tõelist edu. See ei ole nagu üks viga, et võid lihtsalt omamoodi vahele jätta. Kui sul on küsimusi oma seadme või levitamine koodi sa tõesti tahad saada, et võtta hooli pigem varem kui hiljem. Nii et isegi kui Sa ei tegelikult alustada kodeerimine, jaotuse alla laadida kood, lugege spec, siis veenduge, kõik töötab seal. OK? Kui saate lihtsalt teha, et ma luban teie elu saab olema lihtsam. Ja et sa oled ilmselt läheb seda teha just nüüd õige? OK. Niisiis, mingeid küsimusi on? Iga logistiline asjad? Igaühel on hea? OK. 

Hoiatus neile, sa ruumis ja internetis. Ma lähen, et ta püüab üle minna vahel PowerPoint seadmesse sest me olla teeme mõned kodeerimist täna populaarne nõudlus anonüümne soovitus küsitlus I saatis eelmisel nädalal. Niisiis, me teeme mõned kodeerimist. Niisiis, kui te poisid ka taha tulekahju up your seadmete ja sa oleks saanud talle minult, proovi fail. Vastake teha. 

Niisiis, me ei kavatse rääkida GDB, mis on siluri. See saab aidata teil omamoodi aru saada, kus asjad lähevad valesti koodi. See on tõesti lihtsalt viis, kuidas saate samm läbi oma kood, nagu see juhtub, ja suutma välja printida muutujad või näha, mis tegelikult toimub kapoti alla salmid oma programmi just jooksmine, see on nagu faulting, ja sa oled nagu, ei tea mis nüüd juhtus siin. Ma ei tea, mida, mida ta läbi kukkunud. Ma ei tea, kus ta läks valesti. Niisiis, GDB läheb, et aidata teil selle. Samuti, kui sa otsustad jätkama jah, ja võtta 61, see tõesti olema oma parim sõber, sest ma võin teile öelda, sest ma lähen läbi selle klassi. 

Me läheme vaatama binaarne otsing, mis, kui teiega mäletan suur telefoniraamat näiteks etendus klassi. Uurime seda rakendavate ja jalgsi läbi, et natuke rohkem, ja siis me läheme läbi nelja Erinevad, mis on mull, Valik, paigaldamine ja ühendamine. Külm. Niisiis, GDB nagu ma mainisin, on siluri. Ja need on omamoodi suur asjad, suur funktsioone või käske et te kasutate jooksul GDB ja ma käin teid läbi demo see teine. 

Niisiis, see ei ole lihtsalt jään abstraktseks. Ma püüan ja teha see nii konkreetseid kui võimalik kutid. Niisiis, murda. Seda saad olla kas murda nagu mõned number, mis kujutab endast rida oma programmi, või saate nimi funktsioon. Niisiis, kui sa ütled murda peamine, ta ei peatu peamine, ja kust sa suudad selle funktsiooni. 

Samuti siis, kui teil on mõned välised toimi nagu Vaheta või Cube, et me vaatasime eelmisel nädalal. Kui te ütlete murda üks neist, kui teie programm tabamust, et see ootan teid öelda seda, mida teha. Enne seda lihtsalt teostada, et sa võiks tegelikult samm sees funktsiooni ja vaadata, mis juhtub. Niisiis, Next, lihtsalt ignoreerib üle järgmisele reale läheb üle funktsioone. Etapp. Need kõik on veidi abstraktne. Niisiis, ma lihtsalt joosta neil, aga näete neid kasutada teist. 

Astu funktsiooni. Nii nagu ma ütlesin, jms Swap, oleks võimaldab teil tegelikult, kui sa oled nagu füüsiliselt samm sees, saate jama need muutujad, print mida nad on, vaadake, mis toimub. Nimekiri sõna otseses mõttes lihtsalt printida välja ümbritseva koodi. Niisiis, kui teil selline unustada kus sa oled oma programmi, või sa ei tea, mis toimub ümber, see lihtsalt välja printida segment ja meeldib viis või kuus liinid ümber. Nii saad orienteeritud kohta, kus sa oled. 

Prindi mõned muutuv. Niisiis, kui sul on võti, nagu in Caesar, et me vaatame. Võite öelda Prindi Key igal hetkel. See ütlen teile, mis on väärtus nii et äkki kuskil mööda teed, sa overwrote oma võti. Võite tegelikult öelda, et kuna tegelikult võite täheldada, et väärtus. 

In kohalikega, lihtsalt pildid oma kohaliku muutujad. Niisiis, millal sa oled sees silmus, ja sa lihtsalt tahad näha nagu, oh. Mis on minu olen? Mis on see põhiväärtus et ma initsialiseerida siin? Mis on sõnum selles küsimuses? See lihtsalt printida kõik neist, et te ei pea eraldi öelda, Print I. Prindi Sõnum. Prindi Key. Ja siis Kuva. Mida see teeb, on, nagu te sammult läbi programmi siis saad lihtsalt veenduda, et see on väljapanek mõned teatud muutuja igas punktis. Nii et te also-- --it on mingi otsetee kus sa ei pea jätkama nagu, oh. Prindi Key või Print I. See lihtsalt automaatselt seda teile. 

Niisiis, et me ei kavatse näha, kuidas see läheb. Ma lähen, et proovida ja lüliti üle minu aparaat. Vaata, kas ma suudan seda. Kõik. Me lihtsalt hakkab peegeldama seda. Ei ole midagi hull minu sülearvuti niikuinii. OK. See peab olema see üks. See on nii pisike. Vaatame, kas me saame seda teha. 

OK. Alice on ilmselt hädas siin natuke, kuid me jõuame seda momento. OK. Me lihtsalt läheb seda suurendama. OK. Kas igaüks omamoodi näe? Võib-olla natuke? Ma tean, et see on natuke väike. Sa ei saa päris aru saada, kuidas see võimalik on suurem. Kui keegi teab. Kas keegi teab, kuidas seda suurem? OK. Me läheme veeretada seda. Vahet pole niikuinii, sest see on lihtsalt see on kood, mida poisid peaks olema. 

Veelgi enam oluline on terminal siin. Ja meil on siin Miks on see nii väike? Seaded. Oh. Tõsi Ike. Kuidas see on? Pole seal. Kas see on parem kõigi jaoks? OK ,. Külm. 

Tead, kui oled CS klassi tehnilised raskused on mingi osa the-- Niisiis, oletame, selge see. OK. Niisiis, siin rubriigis, mis meil oli siin. Caesar on käivitatav fail. Nii et ma tegin seda. Niisiis, üks asi realiseerida koos GDB on et see töötab ainult käivitatava faili. Niisiis, te ei saa kasutada seda dotsy. Sa pead tegelikult tegema Veenduge, et teie kood koostab, ja et ta võib tegelikult juhtida. 

Seega veenduge, et kui see ei ole koguda, saan seda koguda, nii, et saate mingi joosta läbi. Niisiis, alustada GDB, kõik, mida teha, Gloria tüüp GDB, ja siis lihtsalt fail, mida soovite. Olen alati vigadega kirjutama Caesar. Kuid sa tahad teha kindel, sest see on käivitatav, ti punktisagedus flash, nii et tähendab, et sa lähed joosta CSI sa lähed täitma Neid faile kas siluri. OK. Niisiis, sa, et sa saad selline jama. See on lihtsalt kõik asjad umbes siluri. Sa tõesti ei pea muretse praegu. Ja nagu näete, meil on see avatud Sulgudes SKP lähedal Sulgudes, ja lihtsalt selline välja näeb meie käsurida, eks? 

Niisiis, mida me tahame do-- -seega, Esimene asi, on me tahame valida koht murdma. Niisiis, seal on üks viga Selles Caesar programmi mis ma saan, et me lähme välja selgitada. Ta Mis see on, mis kulub sisend Barfoo kõik mütsid, ja mingil põhjusel see ei muuda A. See lihtsalt jätab üksi, on kõik muu õige, kuid teine ​​kiri Jääb muutumatuks. Niisiis, me ei kavatse proovida ja selgitada, miks see nii on. Niisiis, esimene asi, mida sa tavaliselt tahad teha, kui te alustate GDB on aru saada, kus murdma. 

Nii et Caesar on päris lühike programm. Me peame lihtsalt üks funktsioon, eks? Mis oli meie funktsioon Caesar? Seal on ainult üks funktsioon, Main õige? Peamine on funktsioon kõik oma programmid. Kui sa ei ole Main, võin olla natuke mures just nüüd, aga ma loodan, et teil kõigil oli Main seal. Niisiis, mida me saame teha, on meil võimalik lihtsalt murda Main, just niimoodi. Nii, see ütleb, et OK. Me seame meie murdepunkti üks seal. 

Nii, nüüd on meeles pidada, Caesar võtab üks käsurea argument õigus ja me ei ole teinud, et kuskil veel. Niisiis, mida te teete, on see, kui sa tegelikult minema joosta Programmi ühtegi programmi, et sa oled töötab GDB, mis vajab käsurea argumente, sa lähed sisend kui te esimest korda hakatakse seda. Niisiis, käesoleval juhul me Käivita võtmega kolm. Ja see tegelikult alustada. 

Niisiis, kui sa näed siin on meil Kui RC ei ole võrdne 2. Nii et kui te poisid kõik on et fail, mida ma saatnud üles näete, et see on nagu Esimene rida meie peamine ülesanne, eks? See kontrollides, et näha, kas meil on õige mitmeid argumente. Niisiis, kui sa ei tea, kui RC on õige, saab midagi teha nagu Print RC. RC on kaks, mis on mida me ootasime, eks? 

Niisiis, me saame minna Edasi ja jätkake. Nii, meil on mõned olulised seal. Ja meil on võimalik välja printida meie peamiste veenduda, et on õige. Huvitav. Mitte päris see, mida me ootasime. Niisiis, üks asi realiseerida koos GDB Samuti on et see ei ole kuni te tegelikult tabanud Edasi, et rida, et sa lihtsalt nägin on tegelikult tehtud. Niisiis, käesoleval juhul Key ei ole veel omistatud. Niisiis, Key on mõned prügi väärtus et näete allservas. Negatiivne $ 120-- --It on üks miljard ja midagi imelikke asju eks? See ei ole võti, et me ootasime. Aga kui me tabanud Next ja siis üritada Prindi võti, see on kolm. 

Igaüks näe? Niisiis, kui sa midagi et sa oled nagu, oota. See on täiesti vale, ja ma ei tea kuidas see juhtub, sest kõik, mida ma tahan tegema, on määrata number, muutuja, proovida lööb Järgmiseks proovige trükkimine seda uuesti, ja vaata, kas see toimib. Sest see on ainult kavatse täita ja tegelikult määrama midagi pärast tabas Next. Mõtet kõigile? Uh huh? 

SPEAKER 2: Kui sa juhuslikult numbrid mida see tähendab? 

SPEAKER 1: See on lihtsalt juhuslikult. See on lihtsalt prügi. See on lihtsalt midagi, mida teie Arvuti juhuslikult määrata. Külm. Nii, nüüd me saame liikuda, ja nii Nüüd on meil see lihtteksti getString. Niisiis, lubage mul tutvustada, mida juhtub siis, kui me tabanud Järgmine siin. Meie GDB omamoodi kaob, eks? Ongi, sest getString Nüüd on täidesaatva, eks? Niisiis, kui me nägime lihttekstina võrdub GetString, avatud Sulgudes ja Sulgudes, ja me tabanud Järgmiseks, mis on tegelikult tehtud nüüd. Nii, see on oodanud meil sisend midagi. 

Niisiis, me ei kavatse sisend meie toit on see, mida see ei suuda nagu ma ütlesin, ja mis lihtsalt ütleb, et see on valmis täidesaatva, et suletud sulg tähendab see väljudes välja, et silmus. Nii võime tabas Next ja nüüd, kui ma olen Kindlasti olete kõik tuttavad Caesar, see on, mis see liin kavatse seda teha. See eest Int I võrdub 0, N võrdub Strlen, lihttekstina ja siis Mul on vähem kui n, I, pluss, pluss. Mis see on loop tegema hakkad? Ava oma sõnum. Külm. Niisiis, alustame seda tehes. 

Nii peaks see tingimus Naudi meie esimene? Kui see on B, siis on ainult tekst I. Me saab infot meie kohalikega. Niisiis, ma on null, ja kui kuue, mille ootame ja meie võti on kolm. Kõik, mida on mõtet, eks? Need numbrid on kõik täpselt, mida nad peaksid olema. Niisiis, hum? SPEAKER 3: mul on juhuslike arvude jaoks minu. SPEAKER 1: Noh, me saame kontroll-- --Meil saab vestelda, et teises. Aga siis peaks olema saada see. Niisiis, kui meil on kapitali B meie esimene, seda tingimust tuleks püüda seda, eks? Seega, kui me tabanud Järgmisena näeme et see kui tegelikult täidab. Sest kui sa oled järgmine koos oma koodi see joon siin, kus tavaline teksti I asendatakse käesoleva aritmeetika, täidab üksnes juhul, kui Kui tingimus on õige eks? 

GDB on ainult kavatse näidata teile asju, mis on tegelikult täidetakse. Nii et kui see Kui tingimus ei ole täidetud, siis on lihtsalt läheb liikuda järgmise rea. OK? Niisiis, meil on see. See sulg tähendab see suletud välja et loop nüüd. Niisiis, see läheb uuesti alustada. Just niimoodi. Nii, et saame info meie kohalikud siin ja me näeme, et meie esimene kirjas on muutunud, eks? Nüüd on E, nagu see peaks olema. Nii võime jätkata. 

Ja meil on see kontroll. Ja selle kontrolli peaks tegema, eks? On A. Tuleb muutunud kolm tähte edasi. Aga kui te märkate, oleme midagi erinevat. Nii et kui siin, see on püütud see ja nii see rida täidetud, millega muudeti meie B. Kuid antud juhul, meil on see lihtsalt vahele see, ja läks [? L Siff. ?] Nii et midagi seal toimub. Mida see räägib teile on, et me teame, et see tuleks püüda siin kuid see ei ole. Kas keegi näha, mida meie Probleem on selles, et piir? See on väga minut asi. Ja siis võiks ka vaadata oma koodi. Samuti on LINE unustada, mida joon on aastal there-- kuid see on [kuuldamatu]. Jah? 

SPEAKER 4: See on suurem kui lehel, kui sa loed seda raamatut. SPEAKER 1: Täpselt. Niisiis, siluri ei ütle te, kuid siluri saame sind liinile et sa tead, ei tööta. Ja mõnikord, kui eriti hiljem semester, kui olete tegelevad saja, sada paar rida koodi, ja sa ei tea, kus see ei anna tulemusi, see on suurepärane võimalus seda teha. Niisiis, me leidsime meie viga. Võite parandada oma faili ja siis võiks kasutada seda uuesti, ja töötaks kõik suurepäraselt. Ja suurim asi on see võib tunduda, OK. Jah. Külm. Sa teadsid, mida te otsite. Nii, et sa tead, mida teha. 

GDB saab super kasulik, sest sa saab välja printida kõik need asjad, mida ei teeks. See on palju kasulikum kui printf. Kui paljud teist kasutavad nagu printf avaldusi aru saada, kus viga oli, eks? Niisiis, see, sa seda ei tee on hoida naasmine, ja meeldib kommenteerib Printf või kommenteerides välja, ja aru saada, mis sa peaks printimist. See tegelikult lihtsalt võimaldab teil sammult läbi, välja printida asju kui sa lähed läbi, nii saate jälgida, kuidas nad muutuvad reaalajas kui teie programm töötab. 

Ja see võtab vähe natuke harjumist. Ma väga soovitada just sellist olla veidi pettunud ta jaoks just nüüd. Kui sa kulutad tunni jooksul Järgmisel nädalal õppida, kuidas kasutada GDB, säästad ennast nii palju aega hiljem. Ja sõna otseses mõttes. me öelda Selle inimestele igal aastal ja ma mäletan, kui ma võtsin klassi, ma olin nagu, ma saab trahvi. Ei. Pset 6 tuli ja ma olin nagu, ma hakkan õppima kuidas kasutada GDB, sest ma ei ole tea, mis siin toimub. 

Nii et kui te võtate aega, et kasuta seda väiksemad programmid et sa lähed, et olla kallal, nagu töötamine läbi midagi Visionare, niimoodi. Või kui soovite Täiendava tava, ma olen kindel Ma võiks tulla lollakas programmide teile siluda, kui soovite. 

Aga kui sa lihtsalt võtta aega, et saada harjunud, lihtsalt mängida seda, see tõesti teenib sind hästi. Ja see on tõesti üks neid asju, mida sa lihtsalt on proovida ja saada oma käed määrdunud koos, enne kui sa tõesti aru. Ma tõesti ainult aru kord Mul oli silumiseks asju see, ja see on palju kenamaks on idee kuidas siluda pigem varem kui hiljem. OK. Külm. Ma tean, et on selline nagu kiirkursuse GDB, ja ma kindlasti tööle saada Nende vaatama suurem järgmine kord. Külm. 

Niisiis, kui me läheme tagasi meie PowerPoint. Kas see läheb tööle? AWH. Jah. OK. Niisiis, kui te kunagi vaja mis tahes need jälle seal nimekirjas. Nii Binary Search, kus igaüks mäletab suurt vaatemängu David rippimise telefon raamatuid pooleks. Ma tõesti ei saa telefon raamatuid enam, sest nagu kus sa saada telefon raamatuid nendel päevadel? Ma tõesti ei tea. Binary Search. Kas keegi mäletab, kuidas Binary Search töötab? Keegi üldse? Jah? SPEAKER 5: Tead, kui te vaatate millest pool see oleks, tuginedes, et ja vabaneda teise poole. 

SPEAKER 1 Täpselt. Niisiis, Binary Search, see on selline a-- --Meil meeldib seda nimetada jaga ja valitse. Niisiis, mida saate teha, on saate otsida keskel, ja te näete, kui see vastab mida te otsite. Ja kui seda ei juhtu, siis proovige nuputada, ta kavatseb jätta pool või paremal pool. Nii võib see olla, kui otsite on midagi, mis on Tähestikuline, näed, oh. Kas Allison tulla enne M? Jah. Niisiis, me ei kavatse vaadata esimesel poolel. 

Või võiks see olla numbritega. Midagi, mis saab võrrelda, siis võib sorteerida. Võite kasutada binaarne otsing. Niisiis, keegi mäletab seda graafik või mis see on? See on asümptootilisest keerukus. Niisiis, see graafik lihtsalt kirjeldab, kui kaua viib teid, kuidas lahendada probleemi, kui te arvu suurendada asjad et te kasutate. 

Nii, meil on N, mis on lineaarne aeg. Kui N üle kahe, mis on veidi parem ikka kasvab super kiire. Ja siis oleme sisse, mis on mis meie arvates Binary Search. Kui märkame, kui teie probleem saab palju ja palju suurem, aega kulub sul seda lahendada ei ole tegelikult suurendada nii palju. See on nagu võrrelda siin alguses. Sa oled nagu, OK. Midagi siin ei ole tõesti asi, millest üks, mida me kasutame, kuid sa välja miljon, miljard. Sa üritad leida some-- --you're püüdes leida nõela heinakuhjas. 

Ma arvan, et sa tahad seda probleemi. Tahad keerulisemaks see, et ei lineaarne, sest kõik, mida tean oma saab olema läbi otsida iga nõela asi hein, püüdes leida nõela. Ja see pole liiga lõbus minu arvates. Mulle meeldib kiire. Mulle meeldib väga tõhus. Ja kui töökas õpilastele sa kutid on, sa tead, töö targemaks, mitte raskem tüüpi asi, kuidas sa saab teha kuni nende algoritme. 

Niisiis, me ei kavatse käia kaudu lihtsalt kiire näide. Ma arvan, et kutid peaks olema käsi Binary Search, kuid kui keegi on natuke udune, soovime tugevdada seda, me lähme lihtsalt minema näitena siin. Niisiis, me otsime, kui massiiv sisaldab seitset. 

Niisiis, esimene asi, mida me teha, on vaata keskel, eks? Ja ka sa lähed tuleb kodeerimine Binary Search vaid teine. Nii, see saab olema lõbus. Nii et me vaatame keskel väike massiivid 3. Kas 3 võrdub 7? Mitte. See on kuus. Nii, see on vähem kui või rohkem kui seitse? Vähem kui. Jah. Nice töö poisid. Tunnen nagu ma peaks kommid, sest ma taha visata see viidud meetrit. See on see, mida ma kavatsen teha järgmisel nädalal. See hoiab kutid terav. 

Niisiis, me visata, et esimesel poolel, eks? see oli alla. me teame, et kõik kohta, et vasakul pool läheb vähem, kui me tegelikult otsivad. Niisiis, ei ole vaja pöörama tähelepanu sellele. Lihtsalt unusta see. Nii, nüüd me vaatame meie löögile, ja me vaatame keskel seal, ja nüüd on üheksa. Niisiis, 9 on-- --Everyone? Rohkem kui see, mida me oleme otsin, eks? Niisiis, me ei kavatse visata ära kõik paremale. Niimoodi. Nüüd on kõik me oleme jäänud on. Nii et me kontrollime, on see, mida me otsime? see on. Leidsime, mida me tahtsime. Nii ongi kõik. Bilineaarne otsing. 

Ja kui te märkate, oleme oli seitse sisendid olemas. See kestis vaid meid nagu kolm korda aga kui sa teed nagu miljardit te teate, mitu sammu ta oleks võtta, kui meil oleks 4000000000 asju? Kõik oletused? See on 32. 32 sammu, et leida midagi a 4000000000 element massiivi tõttu volitused kaks. Nii kaks on kuni 32, on 4000000000. 

Nii et päris hull, kui sa oled ikkagi nagu suhteliselt väike arv samme leida midagi 4000000000 elemente. Nii et selle teadmiseks, me oleme läheb kodeerida selle nii kutid saavad tegelikult omamoodi aru, kuidas see töötab. Olgu, et te kutid saate kodeerida. Ma lähen teile poisid rääkida natuke. Tutvu inimesi enda ümber, mis on mida keegi tahtis viimane osa. 

Nii tundma inimesi enda ümber. Arutelu natuke. Ja kõik, mida ma tahan sinult poisid just nüüd on lihtsalt püüame luua ülevaade pseudokoodi. OK? Vau. Ma tahan kutid on sul lihtsalt läheb täita seda samas asjas. Nii et ma olen pannud nende ülemine ja alumised piirid, mis esindama alguses ja lõpuks meie massiivi. Ja sa lähed tegelikult aas läbi ja nuputada mida me teeme selles samas silmus. 

Nii et kui te saate aru out-- mul vihje there-- millistel juhtudel mis meil siin on? Nii et kui sa tahad välja nuputada juhtudel me pseudokoodi nende ja siis me tegelikult kodeerida neid. Ja see saab olema, ma arvan, loodetavasti see saab olla natuke lihtsam kui sa oodata. Sest see ei ole nii palju koodi tegelikult, mis on väga lahe. 

Mm-hm? 

Õpilane: [kuuldamatu]? Juhendaja: Jah. Seal oli midagi leida keskel. 

Õpilane: Nii saame kasutada seda. OK. 

Juhendaja: Perfect. Nii et esimene asi, mida me peame tegema. Nii et leida kuldset. Suur. Nii et sul on idee, kuidas me võiksime tegelikult leida kuldset koodiga? 

Õpilane: Jah. n üle 2? Juhendaja: Nii n üle 2. Nii et üks asi on meeles pidada, et oma ülemise ja alumise piire muuta. Hoiame constricting osa massiivi me otsitavat. Nii n üle 2 töötab ainult et esimene asi, mida me teeme. Nii võttes ülemise ja alumise arvesse kuidas võiks saame, et keset element? Kuna me tahame keskel vahel ülemise ja alumise, eks? Mm-hm? 

Õpilane: [kuuldamatu]. 

Juhendaja: Nii et meil on mõned keskel. Ja see saab olema ülemise pluss madalam üle 2. Awesome. Seal me läheme. Üks rida alla. Te olete oma viis. Nüüd, et meil on keskel, mida me tahame teha? Lihtsalt üldiselt. Sa ei pea koodi ta. Jah. Õpilane: [kuuldamatu]? Juhendaja: Nii et see on pluss, sest sa oled leidmisel keskmiselt kahe neist. Nii et kui te arvate neist omamoodi suurendada sealt külge, mõtle selle peale kui sa lähenemine keskel, tahad niimoodi. Nii et kui sa olid mõlemal pool keskel, ja me oleme nagu 5 ja 7. Kui lisate neid koos te saada 12, siis jagage 2 on 6. 

Vahel on raske selgitada, miks see toimib, aga kui sa töö kaudu Näiteks mõnikord see aitame sind mõtlema, kui see peaks olema pluss või miinus. Jah. 

Õpilane: [kuuldamatu] täpselt keskel kui neil oleks juhul, kui seal on palju väiksemad numbrid ja nagu üks suur number? 

Juhendaja: Nii et kõik, mida vaja on keset massiivi. Nii et kui teil oli hunnik väike arv ja siis üks tõeliselt suur hulk lõpus, see ei ole tähtis. Loeb see, et nad sorteeritud, sa lihtsalt tahad vaadata keskel massiiv, sest sa oled veel viilutamine oma probleemi pooleks. Külm. Nii et nüüd, kui meil keskel, mida me teeme siis? 

Õpilane: võrrelge. Juhendaja: võrrelda. Nii et võrrelda keskelt value_wanted. Külm. Nii et näete siin on meil Selle raha me tahame siin. Pea meeles, et see on massiiv. Nii keskel viitab indeks. Nii et me tahame teha väärtuste keskel. Ärge unustage, kui soovite võrrelda, topelt võrdsete. Sa teed ühe võrdub oled lihtsalt läheb ümber jaotada see, ja siis muidugi see saab olema väärtus, mida soovite. Nii ei saa seda teha. 

Nii et me ei kavatse vaadata, kas väärtuste keskel on võrdne väärtus tahame. Ära unusta oma traksid. Dropbox peaks minema. Mida me siis teeme sel juhul? Kui see on see, mida me tahame naasta? Me püüame öelda. 

Õpilane: Prindi välja. 

Juhendaja: Noh, me ei taha välja printida. Nii et see on tõeväärtus siin, nii et me soovivad naasta õige või vale. Me öeldes on see number [? RRA? ?] Nii et kui see on me lihtsalt tagasi see tõsi. Kui ma ei saa kirjutada tõsi. 

Õpilane: Miks sa ei naasta null? Juhendaja: Nii võid tagasi null, kui sa tahad. Aga sel juhul, sest meie funktsioon tagastab bool, me peame tagastama kas õige või vale. Õpilane: Kui sa oled öeldes boolean väljend, saate seada see võrdne vale? Nagu kui ma tahan öelda, kui see tingimus ei ole täidetud, nagu on ülemine võrdub vale. Kas see mõista, kui sa lihtsalt panna vale teisel pool? Juhendaja: Jah. Nii et tegelikult, kui sa oled kunagi midagi nagu on ülemine või väiksem, mis tagastab tõene või väär ja see on tegelikult halb stiil ütleme võrdub võrdub tõsi või võrdsete võrdub vale. Te soovite kasutada, et tulemus kui ise oma kontrolli all. Pole see, mida ma tahtsin. See, mida ma tahtsin. Seega juhul, kui sa palud midagi nagu salvestada see c. 

Nii et kui meil on int main (void) ja midagi sellist. Ja sul on, kui on ülemine mõne sisendi ja sa oled küsib, kas sa saad teha midagi sellist? Õigus? Õpilane: Ma üritasin seda teha [kuuldamatu]. Sest kui it's-- Juhendaja: Õigus. Nii et sa tahad, et see on vale, eks? Õpilane: Jah. Juhendaja: Nii et kui te taha seda täita, kui see ei ole tõsi. Nii lahe asi, mida teha on see. Seega pidage meeles, hüüatus punkt eitab asju? Ta ütleb [kuuldamatu] tähendab mitte. Nii et kui me vaatame ainult see osa siin, siis oleksin öelda, et tulemus on vale kui sa tahad seda. Ei ole vale on tõsi, mis tähendab see täita. Kas on mõtet? Õpilane: Jah. Juhendaja: vinge. OK. Nii et me võiks lihtsalt tagasi tõsi käesolevas asjas. Nüüd on meil kaks teiste juhul käesolevas asjas. Millised on meie kahel juhul? Lihtsalt tee seda sel moel. Niisiis alustame veel kui väärtuste keskel on väiksem kui väärtus tahame. Nii et meie väärtus keskel on vähem kui väärtus, et me otsime. 

Nii et mis seondub sa arvan, et me tahame uuendada? Ülemist või alumist? Ülemine? Nii, kummal pool massiiv kas me tegeleme? 

Õpilane: madalam. 

Juhendaja: Me hakkame tuleb vaadata vasakule. Nii teine ​​kui vähe väärtus on väiksem. Nii et teie keskel väärtus siin on väiksem kui see, mida me tahame. Nii et me tahame võtta paremal pool meie massiivi. Nii et me ei kavatse uuendada meie alampiiri. Nii me ümber jaotada meie madalam. Ja mis sa arvad madalam peaks olema? Õpilane: keskel väärtus? Juhendaja: Nii keskel value-- Õpilane: Plus 1. Juhendaja: --plus 1. Kas keegi mulle öelda, miks meil on see pluss 1? 

Õpilane: [? No raha?] on võrdne sellega. 

Juhendaja: Õigus. Sest me juba teame, et meie keskel väärtus ei ole võrdne seda ja me tahame jätta see kõik hilisemad otsingud. Kui te unustate, et pluss 1, selles meeldib loop lõputult. Ja sa lihtsalt püütud lõputu silmuse ja siis saate segfault ja asjad lähevad halvasti. Nii et alati veenduma, et sa ei ole sealhulgas raha, et sa lihtsalt vaatasin. Nii et me hoolitseme, et koos pluss 1. 

Nii et nüüd on meil viimane tingimus mida ma alati ohutuse huvides võite vaadata siin, teine, kui väärtus keskel on suurem kui väärtus me tahame. See tähendab, et me tahame vasakul pool. Nii et mis üks me kavatseme uuendada? Upper. Ja mis on see üks läheb võrdsed? Lähis-miinus 1, sest Loomulikult tahame veenduda, et me ei ole Vaadates, et keset väärtus uuesti. Ja siis meil on see. Nii see on. See on kõik, binaarne otsing on. See ei ole nii halb, eks? See on nagu 10 rida kood valge ruumi. Nii et väga võimas, väga kasulik, siis olla kasutades seda ühe oma hilisema psets. Võib-olla ei ole see üks, vaid hiljem. Nii õppima. Armastan seda. Ta kohtleb sind hästi. Nii et kas keegi on mingeid küsimustele Kahendotsingupuu? Jah. 

Õpilane: Kas see, kas teie n on paaris või paaritu? 

Juhendaja: No. Kuna me enamus selle keskel nagu int, see lihtsalt kärpima ta. Seega jääb täisarv ja see lõpuks sorteeri kõike. Nii et sa ei pea muretsema, et. Igaühel on hea? Awesome. Külm. Niisiis, kutid sain selle. Slideshow. Nii et kui me rääkisime, ma tean David mainitud keerukus runtimes. 

Nii et parimal juhul on see lihtsalt üks, mida me nimetame konstantse ajaga. Kas keegi mulle öelda, miks see võiks olla? Mis tüüpi stsenaarium, mis toovad kaasa? Mm-hm. 

Õpilane: [kuuldamatu] first-- Juhendaja: Nii keskel olles Esimene osa, mis me tuleme, eks? Nii et kas massiivi ühe või mida iganes me otsime lihtsalt juhtub olema maitsema DAB keskel. Nii et meie parimal juhul. Sa satuvad tegelikke probleeme, tõenäoliselt mitte jõuame [kuuldamatu], et tihti. Aga meie halvimat? Meie halvimal juhul on log n. Ja see on pistmist kogu volitused kaks asja, mida ma rääkisin. 

Nii et halvimal juhul tähendaks see seda, et pidime raiuma massiivi alla kuni see oli element ühe. Nii et meil tuli vanaks alla poole nii mitu korda, kui me vähegi võimalik. See on põhjus, miks see log n kuna sa muudkui jagatakse kahega. Nii eeldused, mida te vaja teada, kas sa oled kunagi kavatsete kasutada binaarne otsing. Sinu elemendid tuleb sorteerida. Nad peavad olema järjestatud sest see on ainus viis, kuidas ei tea, kas teil on võimalik visata poole. 

Kui teil oli see segamini kott numbrite ja sa räägid, OK, ma lähen, et kontrollida keskel arv ja number Otsin alla, et ma lihtsalt suvaliselt visata pool. Sa ei tea, kas teie numbrid, et teine ​​pool. Sinu loetelu tuleb sorteerida. Samuti võib see olla läheb edasi natuke, aga sa pead ligi pääsema. Sa pead suutma lihtsalt mine selle keskel element. Kui teil läbida läbi midagi või kulub sulle ekstra sammu saada, et keset element, see ei ole sisse n enam, sest olete lisatud rohkem tööd ta. Ja see teeb natuke mõttekam kahe nädala pärast, aga ma lihtsalt omamoodi tahtis eessõna, teile poisid idee, mida on tulema. Kuid need on kaks oluline eeldused et peate binaarne nimekirja. Veenduge, et see on järjestatud. See on suur üks kutid kohe. Ja et me ei saa minna Ülejäänud meie kehvasti. Nii et neli sorts-- mull, sisestamise, valik ja ühendamine. Need kõik on omamoodi lahe. Kui poisid otsustavad võtta CS 124, saad infot igasuguseid kehvasti. Ja kui sa oled XKCD fänn, siis on tõesti lahe koomiline kohta nagu tõesti ebaefektiivne kehvasti, mida ma Soovitame teil läheb vaadata. Üks neist on nagu paanika sort, mis on nagu, oh ei, tagastab juhusliku massiiv. Shutdown süsteem. Jäta. Nii geeky huumor on alati hea. 

Nii ei keegi mäletab liiki samasuguse ainult üldine idee kuidas mull omamoodi toimib. Mäletad? 

Õpilane: Jah. 

Juhendaja: minna seda. 

Õpilane: Nii et sa lähed läbi ja kui see on suurem, siis swap kaks. 

Juhendaja: Mm-hm. Täpselt. Nii et sa lihtsalt kordamiseks kaudu. Sa kontrollima kaks numbrit. Kui üks enne on suurem kui ühe hiljem sa lihtsalt vahetada neid nii, et Sel viisil on kõik suuremad numbrid mulksuma lõpupoole nimekirja ja kõik madalamad numbrid mull maha. 

Kas ta näitab teile, poisid jahe heliefekti sorteerimine video? See on selline lahe. Nii nagu Robert just ütles, algoritmi et sa lihtsalt sammult läbi nimekirja Vahetatakse lähima väärtuse kui nad ei ole selleks. Ja siis muudkui korrates kuni sa ei tee vahetustehinguid. Nii et pole paha, eks? Nii et meil on lihtsalt kiire näide. Nii et see saab sortida neid tõusvas järjekorras. Nii et kui me minna läbi esimese aega, vaatame läbi kaheksa ja kuus on ilmselgelt mitte et me vahetada neid. 

Nii et vaadata järgmist. Kaheksa ja neli mitte selleks. Vahetada neid. Ja siis kaheksa ja kaks, vahetada neid. Seal me läheme. Nii et pärast esimest pass, siis teate, et teie suurim number läheb kogu tee ülaosas, sest see on lihtsalt saab olema pidevalt suurem kui kõik muu ja see lihtsalt läheb mull kuni kõik viis lõpuks seal. Kas see on mõistlik kõigile? Külm. 

Siis me vaatame meie teine ​​pass. Kuus ja neli lülitit. Kuus ja kaks lülitit. Ja nüüd on meil mõned asjad korras. Nii et iga pass, et me teha läbi kogu meie nimekirja me teame, et niimoodi mitu numbrit lõpus on arutanud. Nii et me kolmanda pass, mis on üks swap. Ja siis meie neljas edasi on meil null pesadesse. Ja nii me teame, et meie massiiv on sorteeritud. 

Ja see on suur asi mull sorteerida. Me teame, et kui me null vahetuslepinguid tähendab, et kõik on täiesti korras. See on selline, kuidas me vaadata. Nii oleme ka läheb koodi mull sort, mis samuti ei ole nii hull. Ükski neist pole nii hull. Ma tean, et nad võivad tunduda veidi hirmutav. Ma tean, et kui ma võtsin klassi, isegi kui ma õpetas klass esimest korda eelmisel aastal, Ma olin nagu, kuidas ma seda teen? Mõttekas teoorias, kuid kuidas me tegelikult seda teha? Mis on põhjus, miks ma tahan ka käia läbi kood teiega siin. Nii et mul on pseudokoodi kutid seekord. Nii lihtsalt pidage seda meeles, kui me parasjagu ülemineku üle. Nii et meil on mõned loendur jälgib meie vahetuslepingud sest meil on vaja veendumaks, et me kontrollime seda. Ja meil kinnitada, kogu massiivi kui me just tegin seda näiteks. Kui element enne on suurem kui element pärast, kus me oleme, me vahetada neid ja me juurdekasvu meie counter, sest niipea, kui oleme vahetada, me tahame, et lasta meie counter tean seda. Kõik küsimused on? Midagi tundub naljakas siin. Õpilane: Kas sinu loenduri nullimiseks iga kord, kui sa lähed läbi silmuse? Kas sa ei jätka tagasi nulli iga kord? Juhendaja: Mitte tingimata. Mis juhtub, on meil läbida siit. Nii et samal ajal, mäletan seda täidab korraga ilma jätma. Nii see läheb, et seada counter võrdub nulliga, siis see läheb itereerima kaudu. Kuna itereerib kaudu, ajakohastab ta counter. Kuna see värskendab counter, kui see on tehtud, kui see on jõudnud lõpuks massiiv, Kui meie nimekirjas ei ole sorteeritud, loendur on uuendatud. 

Nõnda siis kontrollib seisund ja see ütleb OK, on ​​vastuolus suurem kui null. Kui on, siis seda uuesti teha. Sa tahad nullida nii, et kui sa läbida, counter on võrdne nulliga. Kui sa lähed läbi sorteeritud massiiv, miski ei muutu, see ei õnnestu ja te tagasi järjestatud nimekirja. Kas see on mõistlik? Õpilane: Mõnikord võib natuke. Juhendaja: OK. Kui seal on kõik muud küsimus, mis kerkib. Jah. 

Õpilane: Mida funktsiooni olema Vahetatakse elemendid? 

Juhendaja: Nii saame tegelikult kirjutada et kui me läheme kohe. Külm. Nii et selle teadmiseks, Alison läheb tagasi lülituda seadme. See saab olema lõbus. Ja meil on kena mull omamoodi asi siin. Ma juba tegin jalgrattasõit läbi massiivi. Meil on vahetustehingud, et on võrdne nulliga. Nii et me tahame, et vahetada külgnevate elemente kui nad rikkis. Nii et esimene asi, mida peame ei ei itereerima meie massiivi. 

Niisiis, kuidas sa arvad, me võiksime itereerima meie massiivi? Meil on ja i on 0. Tahame i vähem kui n miinus 1 miinus k. Ja ma seletan, et teises. Nii et see on optimeerimise siin, kus mäletan, kuidas ma ütlesin pärast iga pass läbi massiivi me tean, et kõike, mis on nüüd-- 

Nii et pärast ühe liigu me tean, et see sorteeritakse. Pärast kahte möödub me teame et see kõik on sorteeritud. Pärast kolme möödub me tean, et on järjestatud. Niisiis, kuidas ma iterating läbi massiivi siin on see teeb kindlasti minna ainult läbi, mida me teame, on sortimata. OK? See on lihtsalt optimeerimine. Sa võid kirjutada naiivselt lihtsalt iterating läbi kõik, see oleks lihtsalt kauem. Selle neli loop see lihtsalt kena optimeerimine sest me teame, et pärast iga täis iteratsiooni kaudu massiivi siin nagu iga täis silmus siin, me teame, et üks nendest elementidest sorteeritakse lõpus. 

Nii et me ei pea muretsema neid. Kas see on mõistlik kõigile? See lahe väike trikk? Nii et juhul kui me iterating kaudu, me teame, et me tahame, et kontrollida, kas massiivi n ja n + 1 on korras. OK. Nii et siin on pseudokoodi. Me tahame, et kontrollida, kas massiiv n ja n + 1 on korras. Mis võiks meil olemas? See saab olema mingi tingimuslik. See on siis, kui. 

Õpilane: Kui massiiv n on väiksem kui massiivi n + 1. Juhendaja: Mm-hm. Hästi, väiksem või suurem kui. Õpilane: Suurem kui. Siis me tahame, et vahetada neid. Täpselt. Nii et nüüd me saame selle kohta, mis on mehhanism nende vahetamisest? Me läksime läbi selle lühidalt tüüpi swap funktsiooni eelmisel nädalal. Kas keegi mäletab, kuidas ta töötas? Nii et me ei saa lihtsalt neid ümber jaotada, eks? Kuna üks neist eksida. Kui me ütlesime, on võrdne B ja seejärel B võrdub kõigil järsku mõlemad on lihtsalt võrdne B. 

Niisiis, mida me peame tegema, on meil olla ajutine muutuja, mis on kavatse pidada ühe meie ajal me oleme protsessis vahetada. Mis meil on on meil mõned int temp on võrdne-- saate määrata selle et kumb sa tahad, lihtsalt Veenduge, et hoida silma peal it-- Käesoleval juhul see nii, et ma lähen määrata selle massiivi n + 1. Nii et läheb hoidke iganes väärtus on see, et teine ​​plokk et me vaatame. 

Ja siis me saame teha, on saame minna ees ja ümber jaotada massiivi n + 1, sest me teame, et me on, et raha hoitakse. See on ka üks suur things-- Ma ei tea, kas keegi teist oli probleeme, kui kui lülitate kaks rida koodi äkki asjad töötasid. Tellimus on väga oluline CS. Seega veenduge, et diagramm asju teha kui võimalik selle kohta, mis tegelikult toimub. Nüüd me ei kavatse ümber jaotada massiivi n + 1, sest me teame, et me on, et raha hoitakse. 

Ja meil on võimalik määrata, et massiivi n või antud juhul massiivi i. Liiga palju muutujaid. OK. Nüüd oleme ümber jaotada massiivi i pluss 1 on võrdne, mis on massiivi i. Ja nüüd me ei saa minna tagasi ja määrata massiivi i mida? Keegi? 

Õpilane: 10. 

Juhendaja: 10. Täpselt. Ja viimane asi. Kui oleme vahetasin ta nüüd, Mida me peame tegema? Mis on üks asi, mis läheb meile kui me kunagi lõpetada selle programmi? Mida ütleb meile, et me on järjestatud nimekirja? Kui me ei täida mis tahes vahetustehingud, eks? Kui vahetustehingud on võrdne null lõpuks selle. Nii et kui te sooritate swap, kui me just tegin siin, me tahame uuendada vahetustehinguid. Ja ma tean, oli küsimus varem, sa saad kasutada null või ühe asemel on tõene või väär. Ja see, mida see teeb siin. Nii et see ütleb, et kui ei vahetustehinguid. Nii et kui vahetustehingud on null, mis on-- ma alati saan tõed ja minu falses sassi. Me tahame, meil hinnata tõsi ja see ei ole. Nii et kui see on null, siis on see vale. Kui te vabasta see [? paugu?] muutub see tõsi. Nii siis see rida hukatakse. 

Tõde ja vale ja nulli ja need hulluks. Just siis, kui sa aeglaselt kõndima läbi see mõtet. Aga see, mida see väike natuke koodi siin teeb. Nii et see kontrollib, me oleme teinud iga vahetustehinguid. Nii et kui see on midagi peale null, siis läheb valeks ja kogu asi on läheb sooritama uuesti. Cool? 

Õpilane: Mida paus teha? 

Juhendaja: Break lihtsalt murrab sind välja silmus. Nii et kui see oleks lihtsalt meeldib lõpetada programmi ja sa oleks lihtsalt teie järjestatud nimekirja. Õpilane: Amazing. Juhendaja: Vabandust? Õpilane: Kuna varem oleme kasutatud kirjutatud 1 üle kirjutatud null esitada, et kui mis toimib või mitte. 

Juhendaja: Jah. Nii võite pöörduda null või 1. Sel juhul, kuna me ei ole tegelikult mittemidagitegemise funktsiooni me lihtsalt tahame seda murda. Me tõesti ei hooli sellest. Pidur on ka hea, kui see on kasutatud murdmas nelja silmuseid või tingimused, mis sa ei taha, et hoida täidesaatvas. See lihtsalt viib teid välja. See nüanss asja. Ma tunnen, et seal on palju käsitsi vehkimine, nagu sa õppida seda kiiresti. 

Aga sa õppida seda kiiresti. Ma luban. OK. Nii ei igaüks saada mull sorteerida? Mitte liiga halb. Käi läbi, swap asju kasutades temp muutuja, ja me kõik loodud on? Külm. Awesome. OK. Tagasi PowerPoint. Kõik küsimused üldiselt nendest nii palju? Külm. Mm-hm. 

Õpilane: [kuuldamatu] int main tavaliselt. Kas teil on, et see on? 

Juhendaja: Nii et me lihtsalt otsin just tegelik sortimise algoritm. Kui oleksite ta jooksul nagu suurema programmi, siis oleks int main kusagil. Sõltuvalt sellest, kus sa kasutama seda algoritmi, määrab see, mis on tagastab ta. Aga meie puhul me rangelt vaadates kuidas see tegelikult itereerima läbi massiivi. Nii et me ei muretse selle pärast. 

Nii me rääkisime parimal juhul ja halvima stsenaariumi eest binaarne otsing. Nii et see on ka oluline, mida teha et iga meie kehvasti. Mis sa arvad, on kõige halvem juhul runtime mull sorteerida? Te mäletad? 

Õpilane: N miinus 1. Juhendaja: N miinus 1. Nii et see tähendab on n miinus 1 võrdlusi. Nii et üks asi, mida mõista on et esimese iteratsiooni meil läbida, võrdleme Nende two-- nii see on 1. Need kaks, kolm, neli. Nii et pärast ühe iteratsiooni me juba neli võrdlusi. Kui ma räägin runtime ja n. N tähistab võrdluste arv funktsioonina, mitu elementi meil on. OK? 

Nii et me läheme läbi on meil neli. Järgmine kord, kui sa tead, me ei ole on hoolitseda selle. Me võrrelda neid kahte, Nende kahe, need kaks, ja kui me ei ole, et optimeerida nelja silmuse, mis ma kirjutasin, sa oleks võrrelda siin niikuinii. Nii et teil oleks jookseb läbi massiivi ja teha n võrdlusi n korda, sest iga kord, kui me jookseb läbi see meil justkui üks asi. 

Ja iga kord, kui me joosta massiiv, teeme n võrdlusi. Nii et meie runtime on see, tegelikult n ruudus, mis on palju hullem meie logi end sellepärast, et tähendab, et kui meil oli neli miljardit elemendid, see on läheb meid 4000000000 ruuduline asemel 32. Nii ei ole parim runtime, kuid mõned asjad, sa tead, kui sa oled sees teatud hulga elemendid mull omamoodi võib trahvi kasutada. 

OK. Nüüd sellest, mis on parimal juhul runtime? Õpilane: Zero? Või 1? 

Juhendaja: Nii et 1 oleks üks võrdlus. Õigus. 

Õpilane: N miinus 1? 

Juhendaja: Nii et, jah. Nii n miinus 1. Kui teil on mõiste, nagu n miinus 1, kaldume me lihtsalt tilk see välja ja me lihtsalt öelda, n, sest sa oled võrrelda iga these-- iga paari. Seega oleks n miinus 1, mida me me tahaks lihtsalt öelda, on umbes n. Kui olete tegelevad käitustõrge, kõik on ligilähedane. Niikaua kui eksponent on õige, sa oled päris hea. 

See, kuidas me sellega tegeleda. Nii et parimal juhul on n, mis tähendab, et nimekiri on juba sorteeritud, ja kõik me teeme, on joosta ja veenduge, et see on järjestatud. Külm. Hea küll. Nii et nagu näete siin, me lihtsalt mõned graafikud. Nii n ruudus. Fun. Palju hullem kui n nagu me näeme, ja palju, palju hullem kui log 2 n. Ja siis ka sattuda log kajakad. Ja te võtate 124, sa sattuda nagu log täht, mis on nagu hull. Seega, kui olete huvitatud, lookup log star. See on selline lõbus. Nii et meil on see suur diagrammi. Lihtsalt heads-up, see imeline skeem on Teie keskpikas perspektiivis, sest me kaua paluda teil need thins. Nii lihtsalt heads-up, on see sinu vahekokkuvõtte oma kena petma lehte seal. Nii et me lihtsalt vaatas mull sorteerida. Halvim, n ruudus, parimal juhul n. Ja me ei kavatse vaadata teisi. 

Ja nagu näete, on ainult üks, mis tõesti hästi on Mestimissortimine, mida me võtame arvesse, miks. Nii et me ei kavatse minna kõrval üks siin-- valik omamoodi. Kas keegi mäletab, kuidas Valiksortimine töötanud? Mine seda. 

Õpilane: Põhimõtteliselt läbima järjekorras ja luua uue nimekirja. Ja nagu sa oled pannes elemendid sisse, panna neid õiges kohas uue nimekirja. 

Juhendaja: Nii et helid rohkem nagu sisestamise omamoodi. Aga oled sa tõesti lähedal. Nad on väga sarnased. Isegi mina saan neid sassi mõnikord. Enne käesoleva paragrahvi Ma olin nagu, oota. OK. Nii et mida sa tahad teha on valik sorteerida, kuidas sa ei mõtle seda ja teed Ma veenduge, ma püüan mitte saada neid segamini, on see läbi läheb ja ta valib Kõige vähem ning see paneb et alguses oma nimekirja. Ta vahetab seda, et esimene koht. Nad tegelikult on näiteks minu jaoks. Awesome. Nii lihtsalt võimalus mõelda it-- valik sorteerida, valida väikseim väärtus. Ja me ei kavatse joosta näiteks et ma arvan, et aitab, sest Ma arvan, visuaalid alati aidata. Nii et hakkame välja midagi mis on täiesti sortimata. Punane on sorteerimata, roheline sorteerida. See kõik on mõtet sekundis. 

Nii et me läheme läbi ja me kinnitada, algusest lõpuni. Ja me ütleme, OK, 2 meie väikseim number. Nii et me läheme 2 ja me lähme liikuda selle ees meie massiivi sest see on Kõige vähem on meil. Nii see on, mida see siin teeb. See lihtsalt läheb vahetada need kaks. Nii et nüüd oleme järjestatud osa ja sorteerimata osa. Ja mis on hea meeles pidada, umbes Valiksortimine on meil ainult valides alates sorteerimata osa. 

Sorteeritud osa sa lihtsalt rahule jätma. Mm-hm? 

Õpilane: kuidas see teada, mis on väikseim ilma võrrelda seda iga teine ​​väärtus massiivi. Juhendaja: See ei võrdle. Meile meeldib vahelejätmine. See on lihtsalt üldine üldine. Jah. Kui me kirjutada koodi ma olen kindel, et sa olla rahul. Aga teil salvestada see esimene element väikseim. Sa võrrelda ja sa öelda, OK, see on väiksem? Jah. Hoia seda. Siin on see väiksem? Ei? 

See on sinu väikseim, ümber jaotada see oma väärtuse. Ja sa pead olema palju õnnelikum kui me minna läbi koodi. Nii et me läheme läbi, me vahetada, seega siis me vaatame seda sorteerimata osa. Nii et me ei kavatse valida kolm. Me läheme pani selle juures lõpus meie sorteeritud osa. Ja me lihtsalt läheb hoida teed et seda tehes, ja seda tehes. Nii et see on meie liiki pseudokoodi siin. Me kodeerida see siin teine. Aga midagi käima läbi kõrgel tasemel. Sa lähed minna i võrdub 0 kuni n miinus 2. See on teine ​​optimeerimine. Ärge muretsege liiga palju seda. Nii nagu te ütlesite. Kuna Jacob ütles, kuidas me jälgida, mida meie miinimum on? Kuidas me teame? Meil võrrelda kõik meie nimekirjas. 

Nii minimaalne võrdub i. See on lihtsalt öeldes antud juhul Indeksi meie miinimumi. Siis see läheb itereerima kaudu ja see läheb j võrdub i pluss 1. Nii et me teame juba, et see on meie esimene element. Meil ei ole vaja võrrelda seda ise. Nii et hakkame võrreldes seda järgmise üks, mis on põhjus, miks see i pluss 1 kuni n miinus 1, mis on lõpuks massiiv seal. Ja me ütlesime, kui reaga j on väiksem kui massiivi min, siis me ümber jaotada, kui meie miinimum indeksid on. 

Ja kui min ei ole võrdne i, kuna aastal, kui olime tagasi siia. Nii nagu siis, kui me esimest korda tegin seda. Sel juhul oleks alustada null, siis oleks lõpuks on kaks. Nii et min ei oleks võrdne i lõpuni. See võimaldab meil teada, et meil on vaja vahetada neid. Ma tunnen, et konkreetne näide aitab palju rohkem. Nii et ma kodeerida selle üles teiega kohe, ja ma arvan, et see saab olema parem. 

Sorts kipuvad tööd nii, et see on tihti parem lihtsalt neid näha. Nii et see, mida me tahame teha, on kõigepealt on ju väikseim element oma positsiooni massiiv. Täpselt, mida Jacob rääkis. Sa pead hoida, et kuidagi. Nii et me ei kavatse hakata siin iterating üle massiiv. Me läheme öelda, et see meie Esimene lihtsalt alustada. Nii et me ei kavatse on int Väikseim on võrdne reaga i. 

Nii et üks asi, mida tähele, iga aeg see ahel täidab, oleme hakanud üks samm edasi mööda. Kui hakkame me vaatame seda. Järgmine kord, kui me kinnitada, läbi, me alates selle ühe ning määrates selle meie väikseim väärtus. Nii et see on väga sarnane mull omamoodi kus me teame, et pärast ühe liigu, see viimane element on järjestatud. Kui valik sorteerida, see on just vastupidine. 

Igal liigu, me teame, et Esimene neist on järjestatud. Pärast teist pass, teine ​​sorteerida. Ja nagu sa nägid koos slaidi näiteid, Meie järjestatud osa muudkui kasvab. Seega, luues meie väikseim et massiivid i, kõik see läheb on constricting mida me vaatame nii arvu minimeerimiseks võrdluste teeme. Kas on mõtet kõigile? Kas teil on vaja mulle joosta, et jälle aeglasemalt või teiste sõnadega? Mul on hea meel. OK. 

Nii et me ladustamiseks väärtus sel hetkel, kuid me tahame ka salvestada indeks. Nii et me ei kavatse hoidke asend väikseima üks, mis on lihtsalt saab olema i. Nüüd Jacob on täidetud. Meil on asjad salvestatakse. Ja nüüd peame vaatama läbi sorteerimata osa massiivi. Nii et kui see Oleks meie sorteerimata. See on i. OK. 

Niisiis, mida me teeme läheb silmus. Kui teil on vaja itereerima läbi massiiv, meelt võiks minna silmus. Nii et mõned int k equals-- mida me arvame k läheb võrdne alustada? See on see, mida me seame meie väikseim väärtus ning me soovime seda võrrelda. Mida me tahame võrrelda seda? See saab olema selle kõrval üks, eks? Nii et me tahame k lähtestada i + 1 alustamiseks. 

Ja me tahame k antud juhul juba suurus salvestatud siin, nii et me saame lihtsalt kasutada suurusest. Suurus on suurus massiiv. Ja me tahame uuendada k ühe võrra. Külm. Nii et nüüd me peame leidma väikseim element siin. Nii et kui me itereerima kaudu me tahan öelda, kui reaga k on väiksem kui meie väikseim value-- see on koht, kus me tegelikult jälgida, mis on väikseim siin-- siis tahame ümber jaotada millised on meie väikseim väärtus. 

See tähendab, et oh, me oleme iterating siit läbi. Ükskõik väärtus on siin ei ole meie kõige väiksem asi. Me ei taha seda. Tahame ümber jaotada see. Nii et kui me ümberjagamise see, mida teha teie arvates võiks selles kood here? Tahame ümber jaotada Väikseim ja positsiooni. Mis on väikseim nüüd? Õpilane: Array k. Juhendaja: Array k. Ja milline on seisukoht nüüd? Mis on indeksid meie väikseim väärtus? See on lihtsalt k. Nii massiivi k, k, nad vastakuti. Nii et me tahtsime ümber jaotada nii. Ja siis, kui oleme leidnud meie väikseim, nii et lõpuks see silmus siin me oleme leidnud selle, mida meie väikseim väärtus on, nii et me lihtsalt vahetada. Sel juhul, nagu ütlevad meie Väikseim väärtus on siin. See on meie väikseim väärtus. 

Me lihtsalt tahame, et vahetada see siin, mis on mida see swap funktsiooni allosas tegi, mida me lihtsalt kirjutas üles koos paar minutit tagasi. Nii et see peaks välja nägema tuttav. Ja siis lihtsalt kordamiseks läbi, kuni see jõuab kõik viis lõpuni, mis tähendab, et sa null elemente, mis on sortimata ja kõik muu on sorteeritud. Mõtet? Natuke konkreetsemalt? Kood aidata? 

Õpilane: Sest suurus, kunagi tegelikult määrata või muuta, kuidas see teada? 

Juhendaja: Nii et üks asi teate siin on int suurus. Nii me ütleme selles sort-- sorteeri on funktsioon selles case-- see valik omamoodi, see on möödas sisse funktsiooni. Nii et kui ta ei ole läbinud aastal, siis oleks midagi jms pikkus array või siis oleks itereerima kaudu leida pikkusega. Aga kuna see on möödas , saame lihtsalt kasutada. Sa lihtsalt eeldatakse, et kasutaja saatis sulle kehtiv suurus, mis tegelikult tähendab suurusest massiivist. Cool? 

Kui poisid on mingeid probleeme nende või tahad rohkem harjutamist kodeerimine kehvasti ise, siis tuleb minna study.cs50. See on vahend. Nad on kontrollija, et tegelikult võite kirjutada. Nad teevad pseudokoodi. Neil on rohkem videoid ja slaidid sealhulgas need, ma kasutan siin. Nii et kui sa ikka tunned vähe udune, proovige selle välja. Nagu alati, tule räägi minuga ka. Küsimus? 

Õpilane: Kas sa väidad, suurus on eelnevalt defineeritud? Juhendaja: Jah. Suurus eelnevalt defineeritud üles siin funktsiooni deklaratsioon. Nii et sa eeldada, et see on olnud möödunud aastal kasutaja ja lihtsuse mõttes, me lähme eeldada, et kasutaja andis meile õige suurusega. Külm. Nii et valik omamoodi. Poisid, ma tean, et me õppida palju täna. See on tihe andmete osas. Nii et me ei kavatse minna sisestamise omamoodi. 

OK. Nii et enne, et me peame tegema meie runtime analüüs siin. Nii et parimal juhul anda, sest ma näitasin teile laua Ma juba liiki andis selle ära. Kuid parimal juhul runtime, mida me arvame? Kõik sorteerida. N ruudus. Igaüks on selgitus miks sa arvad? 

Õpilane: Sa oled võrrelda through-- Juhendaja: Õigus. Sa võrdled kaudu. Igal iteratsiooni, kuigi me decrementing see üks, sa oled ikka läbi otsida kõike leida väikseim. Nii et isegi kui teie väikseim väärtus on siin alguses, sa oled ikka võrrelda seda vastu kõik muu veendumaks, et see on kõige väiksem asi. Nii saate lõpuks läbiv umbes n ruudus korda. Hea küll. Ja mis kõige halvemal juhul? Ka n ruudus sest sa lähed et teeme sama korra alusel. Nii antud juhul valiku sort on midagi et loeme oodata tööaega. Nii et teised, me lihtsalt tean ülemiste ja alumiste piiride. Sõltuvalt sellest, kuidas hull meie nimekiri on või kuidas sorteerimata see on, nad erinevad n või n ruudus. Me ei tea. 

Aga kuna valik sort on sama Halvim ja parim juhul, mis ütleb meile, et ükskõik mis tüüpi sisend me on, kas see on täiesti sorteeritud või täielikult tagurpidi sorteeritud, see on aega võtab sama palju aega. Nii et juhul kui mäletan meie lauda see tegelikult oli raha, et Nende kahe kehvasti pole, mis on eeldatavasti tööaega. Nii et me teame, et kui võtame valiku sorteerida, see on garanteeritud, et käivitada n ruudus korda. Ei ole varieeruvuse seal. See on lihtsalt oodata. Ja jällegi, kui sa tahad õppida rohkem võtta CS 124 aasta kevadel. Hea küll. Me oleme näinud seda. Külm. Nii sisestamise omamoodi. Ja ma ilmselt läheb lauk läbi selle. Ma ei ole teiega koodeksi. Me lihtsalt kõndida läbi. Nii sisestamise sorteerida on omamoodi on sarnane valik sorteeri et meil on nii sortimata ja järjestatud osa massiivi. 

Aga mis on erinev see, et kui me minna läbi ükshaaval, me lihtsalt võtta mis tahes arv kõrval on meie sorteerimata, ja õigesti sortida meie sorteeritud massiiv. Seda saad mõttekam näiteks. Nii et kõik algab sortimata, Just nagu valik omamoodi. Ja me läheme sorteerida seda kasvavas järjekorras oleme olnud. Nii et meie esimene pass võtame esimene väärtus ja me ütleme, OK, siis on nüüd nimekirja ise. 

Sest sa oled nimekirjas ise, siis on järjestatud. Palju õnne, sest ta oli esimene element selles massiivi. Sa oled juba järjestatud kõik ise. Nii et nüüd oleme järjestatud ning sortimata massiivi. Nüüd võtame kõigepealt. Mis juhtub vahel siin ja siin on see, et me ütleme, OK, me ei kavatse vaadata esimene väärtus meie sorteerimata massiivi ja me ei kavatse sisend seda oma õige koha sorteeritud massiiv. 

Niisiis, mida me teeme, on me võtame 5 ja ütleme, OK, 5 on suurem kui 3, nii me lihtsalt sisestada see õige üles paremale. Oleme head. Siis me läheme meie järgmise üks. Ja me võtame 2. Me ütleme, OK, 2 on vähem kui 3, nii et me teame, et see peab olema ees meie nimekirja nüüd. Niisiis, mida me teeme, on meil suruda 3 ja 5 ette ja astume 2 arvesse, et esimene pesa. Nii et me lihtsalt sisestamist õige koht peaks olema. 

Siis me vaatame meie kõrval üks, ja me ütleme 6. OK, 6 on suurem kui kõik, mis meie sorteeritud massiiv, nii me lihtsalt sildistada seda lõpuni. Ja siis me vaatame 4. 4 on vähem kui 6, see on vähem kui 5, kuid see on suurem kui 3. Nii et me lihtsalt sisestada see paremale keskel 3 ja 5 vahel. Nii, et muuta see veidi natuke konkreetsem, siin on selline Idee, mis juhtus. Nii et iga sortimata element, me kindlaks teha, kus on sorteeritud osa see on. 

Nii et pidades silmas sorteeritud ja sorteerimata, meil läbida läbi ja joonis välja, kui see sobib sorteeritud massiiv. Ja me lisada see, nihutades elementide paremal maha. Ja siis me muudkui iterating läbi kuni me on täiesti järjestatud nimekiri kus sorteerimata on nüüd null ja sorteeritud kulub kogu meie nimekirjas. Nii et jällegi, et teha asju veelgi konkreetsemad meil pseudokoodi. 

Nii et põhiliselt i võrdne 0 kuni n miinus 1, see on lihtsalt pikkuse meie massiivi. Meil on mõned element, mis on võrdne Esimene massiiv või esimese indekseid. Seame j, mis on võrdne. Niisiis, kui j on suurem kui null ja massiivi, j miinus 1 on suurem kui element, seega kõik, mis teed on tagada, et oma j tegelikult esindab sorteerimata osa massiivi. 

Nii kaua kui on veel asju sorteerida ja j miinus üks on-- mida on element teda? J oli kunagi siin määratletud. See on selline tüütu. OK. Niikuinii. Nii j miinus 1, loed element enne seda. Ütled, OK, on ​​element Enne kus ma am-- olgem tegelikult juhtida seda. Ütleme, et see on nagu meie teine ​​läbimine. Nii et ma ei kavatse olla võrdne 1, mis on siin. 

Nii et ma ei kavatse olla võrdne 1. See peaks olema 2, 4, 5, 6, 7. Hea küll. Nii et meie element antud juhul saab olema võrdne 4. Ja meil on mõned j, mis on saab olema võrdne 1. Oh, j on decrementing. See, mis see on. Nii j on võrdne i, nii et mis see on ütlus on, et kui me liigume edasi, me lihtsalt hoolitsedes et me ei ole enam indekseerimist nii, kui me üritame lisada asju meie järjestatud nimekirja. 

Nii et kui j on 1 antud juhul ja massiivi j miinus one-- nii massiivi j miinus 1 on 2 selles case-- kui see on suurem kui element, siis kõik see teeb nihkub asju ette. Nii et antud juhul massiivi j miinus üks oleks array null, mis on 2. 2 ei ole suurem kui 4, nii et see ei täida. Nii et üleminek ei liigu alla. Mida see teeb siin on lihtsalt liigub oma sorteeritud massiivi alla. Sel juhul tegelikult me võiks do-- teeme seda 3. Nii et kui me kõndida läbi koos Selles näites me oleme nüüd siin. See on sorteeritud. See on sorteerimata. Cool? Niisiis i on võrdne 2, nii Meie element võrdub 3. Ja meie j on võrdne 2. Nii et me vaatame läbi ja me öelda, OK, on ​​massiivi j miinus üks suurem kui element et me vaatame? Ja vastus on jah, eks? 4 on suurem kui 3 ja j on 2, seega see kood hukatakse. 

Nüüd, mida me teeme reaga 2, seega siin me vahetada neid. Nii et me lihtsalt öelda, OK, massiiv 2 on nüüd saab olema 3. Ja j läheb võrdsed j miinus 1, mis on 1. See on kohutav, kuid kutid idee. J on nüüd võrdne 1. Ja massiivi j on lihtsalt saab olema võrdne meie element, mis on 4. I kustutada midagi, mida ma ei tohiks on või miswrote midagi, aga kutid idee. 

See liikuma n. Ja siis kui see nii oli, oleks loop uuesti ja ta ütleks, OK, j on 1 nüüd. Ja massiivi j miinus 1 on nüüd 2. Kas 2 alla meie element? Ei? See tähendab, et me oleme lisatakse see element õigesse kohta meie sorteeritud massiiv. Siis saame seda ning me ütleme, OK, meie sorteeritud massiiv on siin. Ja ta võtab selle number 6 ja olema nagu OK, on ​​6 vähem kui see number? Ei? Külm. Oleme trahvi. 

Tee seda uuesti. Me ütleme 7. Kas 7 alla lõpuks Meie sorteeritud massiivi? Ei. Nii et meil läheb hästi. Nii et see oleks sorteerida. Põhimõtteliselt kõik see ei on see ütlus võtta esimene osa Sinu sorteerimata massiiv, aru saada, kus see läheb Teie sorteeritud massiiv. Ja see lihtsalt hoolitseb vahetuslepingute teha. Sa põhimõtteliselt lihtsalt vahetada kuni see on õige koha peal. Visuaalne kujund on see, et sa oled liigub kõik alla, tehes seda. 

Nii et see on nagu pool mull sort-esque. Tutvu uuring 50. Ma väga soovitada üritab kodeerida selle ise. Kui teil on küsimusi või soovite vaata proovi kood sisestamise sorteerida, palun andke mulle teada. Ma olen alati ümber. Nii et halvimal juhul runtime ja parimal juhul tööaega. Nagu te kutt nägi laualt ma juba näitasin teile, see on nii n ruudus ja n. 

Nii et selline läheb maha sellest, mida me rääkisime umbes meie eelmise kehvasti, halvim juhul runtime on see, et kui see on täiesti sortimata, meil võrrelda kõiki neid n korda. Teeme kogu palju võrdlusi sest kui see on vastupidises järjekorras, me ei kavatse öelda, OK, see on sama, see on hea, ja see üks tuleb võrrelda vastu esimene, kes viiakse tagasi. Ja kui saame poole saba lõppu, on meil võrrelda, võrrelda ja võrreldakse kõike. 

Nii et see jõuab on umbes n ruudus. Kui see on õige, siis öelda, OK, 2, sa oled hea. 3, sa oled võrreldes 2. Sa oled hea. 4, sa lihtsalt võrrelda saba. Sa oled hea. 6, võrrelda saba, sa oled hea. Nii et iga kohapeal kui see on juba sorteeritud, et sa üritad üks võrdlus. Nii et see on lihtsalt n. Ja kuna meil on parimal juhul runtime n ja halvima runtime n ruuduline ole meil oodata tööaega. 

See lihtsalt sõltub kaos meie nimekirjas olemas. Ja jälle teine graafik ja teises tabelis. Nii et erinevused kehvasti. Ma lihtsalt imelihtne läbi, ma tunne, nagu me oleme rääkinud ulatuslikult kuidas nad igasugu on erinevad ja ühendaks. Nii Mestimissortimine on viimane Ma kandis te poisid. Meil on päris värvikas pilt. Nii Mestimissortimine on rekursiivne algoritm. Nii et te poisid teavad, mida rekursiivne funktsioon on? 

Igaüks tahan öelda? Soovite proovida? Nii rekursiivne funktsioon on lihtsalt funktsioon, mis nimetab ennast. Nii et kui te poisid tunnevad koos Fibonacci jada, mis on loetud rekursiivne, sest te võtate kahe eelmise ning lisage need koos saada oma järgmise üks. Nii rekursiivne, ma alati arvan, kohta recursion nagu nagu spiraal nii et sa oled nagu spiraali mööda ta. Aga see on lihtsalt funktsioon mis nimetab ennast. 

Ja tegelikult, tõesti kiiresti ma mis näitab teile, milline see välja näeb. Nii rekursiivne siin, kui me vaatame, on see rekursiivne viis Kokkuvõttes üle massiivi. Nii et kõik, mis me teeme, on meil summa funktsioon summa, mis võtab suurus ja massiivi. Ja kui te märkate, suurus Count üks iga kord. Ja kõik see on kui x on võrdne zero-- nii kui suurust massiivi võrdub zero-- tagastab null. 

Vastasel juhul võtab see viimane element massiivi, ja võtab siis summa ülejäänud massiivi. Nii et see on lihtsalt murda see maha üha väiksemateks probleeme. Pikk lugu lühike, recursion, funktsioon, mis nimetab ennast. Kui see on kõik sul läbi selle, see on, mida rekursiivne funktsioon. Kui te võtate 51, saad väga, väga rahul recursion. See on väga lahe. See oli loogiline on nagu 03:00 üks õhtu. Ja ma olin nagu, miks ma olen kunagi seda kasutada? 

Nii Mestimissortimine, põhiliselt mida ta kavatseb teha, on see kavatse murda see maha ja katki alla, kuni see on lihtsalt ühe elemente. Ühtne elemendid on lihtne sorteerida. Me näeme, et. Kui teil on üks element, see on loetakse juba sorteeritud. Nii et sisend n elementi, kui n on vähemalt 2, lihtsalt tagasi, sest see vahend see on 0 või 1, sest me oleme näinud. Need peetakse sorteeritud elemendid. 

Vastasel murda see pooleks. Sorteeri aasta esimesel poolel, sorteerida teine poole ja siis liita need kokku. Miks seda nimetatakse Mestimissortimine. Nii et meil on siin me sorteeri need. Nii et me peame laskma neid kuni massiivi suurus on 1. Nii et kui see on 1, me lihtsalt tagasi sest see on sorteeritud massiiv, ja see on sorteeritud massiiv, ja see on sorteeritud massiiv, me kõik sorteerida. Niisiis, mida me teeme, on meie alustada ühinevad nendega koos. 

Niisiis, kuidas sa saad mõtle ühendamine on sa lihtsalt eemaldada väiksem arv iga sub massiivid ja lihtsalt lisada see tekkinud massiiv. Nii et kui sa vaatad siin, kui meil on Nende komplekti meil on 4, 6 ja 1. Kui me tahame, et koondada need, me vaatame neid kahte esimest ja me ütleme, OK, 1 on väiksem, see läheb ees. 4 ja 6, seal on midagi võrrelda see lihtsalt sildistada seda lõpuni. 

Kui me ühendame need kaks, me lihtsalt võta väiksem kui üks neist kahest, nii et see on 1. Ja nüüd me võtame väiksemad neist kahest, nii 2. Väiksemad neist kaks, 3. Väiksemad neist kahest, 4, 5, 6. Nii et sa oled lihtsalt tõmmates lahti need. Ja kuna nad on sorteeritud varem, sa lihtsalt üks Võrdluseks iga kord. Nii et enam-koodi siin, just esitus. Nii et kui hakkate keskel ja sa omamoodi vasakul ja paremal ja siis lihtsalt ühendada need. 

Ja me ei pea koodi jaoks ühendada siin. Kuid jällegi, kui sa lähed õppida 50, siis tulen sinna. Muidu tulevad minuga rääkima kui sa oled veel segaduses. Nii lahe asi on see, et parimal juhul Halvimal juhul ja oodata runtime kõik log n, mis on palju parem kui me oleme näinud kogu meie kehvasti. Me oleme näinud n ruudus ja mida me tegelikult siia on n log n, mis on suurepärane. 

Vaata, kui palju parem see on. Selline kena kõver. Nii palju tõhusamaks. Kui sa kunagi saab kasutada Mestimissortimine. See säästab aega. Aga samas, kui me ütlesime, kui sa oled alla selles alumises, see ei muuda seda palju erinevust. Sa saad kuni tuhandeid ja tuhandeid sisendeid, te kindlasti soovite tõhusam algoritm. Ja jällegi, meie armas tabeli kõikidest kehvasti, et kutid õppinud täna. 

Nii et ma tean, et see on olnud tihe päev. See ei ole tingimata positiivsed mis aitavad teil oma pset. Aga ma tahan teha disclaimer see lõik ei ole ainult psets. Kõik see materjal on õiglane mäng oma midterms. Ja ka siis, kui sa seda jätkata koos CS, need on tõesti oluline põhialused et siis oleks vaja teada. Nii et mõned päevad on veidi rohkem pset abi, kuid mõned nädalad on palju tegelikku sisu mis ei pruugi tunduda super Teile kasulik just nüüd, aga ma luban, kui jätkate aasta saab olema väga, väga kasulik. 

Nii et see osa. Alla traat. Ma tegin seda ühe minuti jooksul. Aga seal lähete. Ja mul sõõrikud või kommi. Kas keegi on allergiline midagi, muide? Munad ja piim. Nii sõõrikud on ei? OK. Hea küll. Chocolate ei ole? Tähesära. Starbursts on head. OK. Me läheme on Starburst järgmisel nädalal siis. See, mida ma saan. Kutid on suurepärane nädal. Loe oma spec. 

Anna mulle teada, kui teil on mingeid küsimusi. Pset kaks palgaastet peaks olema teile välja hiljemalt neljapäeval. Kui teil on küsimusi, kuidas ma sorteeritud midagi või miks ma sorteeritud midagi nii, nagu ma ei, siis palun kirjuta mulle, tule räägi minuga. Ma olen natuke hull see nädal, kuid ma luban Ma ikka vastata 24 tunni jooksul. Nii on suurepärane nädalal kõigile. Õnn oma pset.