>> 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.