SPEAKER 1: Hey everyone! Sveiki sugrįžę į skyrių. Taigi džiaugiuosi, kad tiek daug jūsų tiek čia, ir visiems, kurie žiūri internete. Taigi, kaip įprasta laukiame sugrįžtant. Tikiuosi, kad jūs visi turėjo gražių savaitgalį, pilna ramybės, poilsio. Tai buvo gražus iš vakar. Taigi, tikiuosi, kad jums patiko atviras. 

Taigi, pirmiausia Skelbimų pora. Rūšiavimas. Taigi, dauguma iš jūsų turi Dotarłeś paštu nuo manęs apie savo Scratch Pset, taip pat klasifikavimo ir Pset 1. Taigi, tiesiog pora dalykų. Būtinai naudokite check50 į style50. Tai yra skirtas būti ištekliai jums vaikinai, įsitikinti, kad jūs gaunate tiek taškų, kaip jūs galite be bereikalingo prarasti juos. Taigi, tokie dalykai kaip stiliaus yra labai svarbūs. Mes ketiname pakilti už jį. Kai kurie iš jūsų galbūt jau Pastebėta, kad iš savo Pset. Ir check50 tik tikrai paprastas būdas įsitikinti kad mes iš tikrųjų grįžti kas turi būti grąžintas į vartotoją, ir kad viskas veikia tinkamai. 

Antrąją dėmesį, įsitikinkite, kad jūsų įkelti ką tinkamą aplanką. Tai daro mano gyvenimą tik Šiek tiek sunkiau jei įkeliate Pset 2 į Pset 1 nes kai aš parsisiųsti dalykų, jie ne atsisiųsti teisingai. Ir aš žinau, kad tai mažai Ļodzīgs sistemoje priprasti prie, bet tiesiog super atsargūs, jei tik man, kad, kai jūs gaunate laiškus ne kaip 2:00 ir aš rūšiavimas. Jei ne sukelti turiu ieškoti visame jūsų Pset. Cool. 

Žinau, kad tai per anksti, bet aš visiškai got imtasi užklupti iki esė Štai dėl šio penktadienis, ta mano profesoriai tiesiog patinka, oh yeah. Nepamirškite, kad jūs turite Esė dėl penktadienį. Taigi, aš žinau, niekas mėgsta galvoti apie kontrolinius, bet tavo pirmasis viktorina yra spalio 15, kuris spalio mėnesio pradžios šią savaitę. Taigi, tai gali būti anksčiau nei jūs tikėjotės ir viskas. Taigi, kad jūs ne mesti užklupti, kai Aš sakiau, kitą savaitę skyrių tą oh, Jūsų viktorina kitą savaitę, aš maniau Norėčiau duoti jums šiek tiek daugiau iš metas dabar. 

Taigi, jūsų problema nustatyti, numeris trys. Kaip žmonės skaityti spec iš smalsumo? Gerai. Mes turime pora. Rūšies žemyn nuo paskutinio savaitę, bet tai gerai. Aš žinau, tai buvo graži iš. Taigi Break Out. Tikrai po gausite padaryta šiandien perskaičiau jūsų spec mažiausiai bandyti kaip atsisiųsti pasiskirstymas kodas ir veikia kaip pirmoji pradinė dalykas, kad jie paprašys. Kadangi mes naudojame pasiskirstymas kodas ir biblioteka kad mes tik buvo using-- --It yra tik antrą kartą mes padarėme šį Pset, beprotiškas dalykai gali atsitikti su prietaisu, ir norite sužinoti, kad iš dabar versus vėliau. 

Nes jei tai Ketvirtadienio naktį ar tai Trečiadienis naktį kažkodėl Jūsų prietaisas tiesiog nėra norite paleisti su biblioteka ar su paskirstymo kodas, kuris būdas Jūs negalite net pradėti daryti kodavimas. Kadangi jūs negalite patikrinti norėdami pamatyti, jei ji veikia. Jūsų not gonna būti suteikta pamatyti, jei ji kaupia. Norite pasirūpinti tiems anksti savaitę, kai jūs vis dar galite rašyti man arba vienas iš kitų TFS, ir mes galime gauti fiksuoto telefono. Nes tie klausimai kad ketina sustabdyti jus nuo priėmimo progresuoti. Tai ne kaip vieną klaidą, kad galite tiesiog rūšies praleisti. Jei iškilo problemų su jūsų Prietaisas ar paskirstymo kodas, jūs tikrai norite gauti, kad imamasi rūpintis anksčiau nei vėliau. Taigi, net jei jūs ne viskas iš tikrųjų pradėti kodavimo, atsisiųsti paskirstymą kodas, skaitykite spec, įsitikinkite viskas gerai veikia ten. Gerai? Jei galite tiesiog padaryti, kad aš žada savo gyvenimą bus lengviau. Ir tokiu būdu jūs tikriausiai ketina tai padaryti dabar teisingai? Gerai. Taigi, bet kokie klausimai ten? Bet kokios logistikos dalykų? Kiekvienas yra gera? Gerai. 

Atsakomybės tiems Jūs kambaryje ir internete. Aš ruošiuosi bando pereiti tarp PowerPoint į prietaiso nes mes ketiname būti padaryti kai kurie kodavimo Šiandien populiarus paklausa anoniminė pasiūlymas apklausa Išsiunčiau praėjusią savaitę. Taigi, mes bus padaryti kai kodavimo. Taigi, jei jus vaikinai taip pat nori įkvėpti savo prietaisų, ir jūs turėtumėte būti gavau laišką nuo manęs, su pavyzdžio failą. Nedvejodami padaryti. 

Taigi, mes ketiname kalbėti apie GDB, kuris yra debuggerem. Jis ketina padėti jums rūšies išsiaiškinti, kur viskas vyksta blogai Jūsų kodas. Tai tikrai tik jums žingsnis būdas per savo kodą, kaip tai vyksta, ir galės atsispausdinti kintamuosius arba pamatyti, kas iš tikrųjų vyksta Pagal gaubtu Eilėraščiai savo programą tiesiog veikia, tai kaip klaida,, ir jūs kaip, neįsivaizduoju kas atsitiko čia. Aš nežinau, ką linija tai nepavyko ne. Aš nežinau, kur jis buvo blogai. Taigi, GDB ketina padėti jums, kad. Be to, jei jūs nuspręsite toliau taip, ir imtis 61, jis tikrai, tikrai bus tavo geriausias draugas, nes aš jums galiu pasakyti, nes aš ruošiuosi per tą grupę. 

Mes ketiname pažvelgti į dvejetainę paieška, kuri, jei jus vaikinai prisiminti puikus telefonas knyga pavyzdys spektaklis iš klasės. Mes bus įgyvendinti, kad ir vaikštinėjo kad šiek tiek daugiau, ir tada mes ketiname per keturias skirtingų rūšių, kurios yra burbulas, Atranka, įterpimas ir suliejimas. Cool. Taigi, GDB kaip jau minėjau, yra debuggerem. Ir tai yra rūšies didelis daiktai, didelis funkcijų arba komandas kad jūs naudojate per GDB, ir aš vaikščioti Jūs per daug jį demo sekundę. 

Taigi, tai yra ne tik ketina likti abstraktus. Bandysiu ir padaryti jį kaip betonas kaip galima jums vaikinai. Taigi, pertrauka. Tai bus arba būti pertrauka kaip, kai numeris, kuris atstovauja savo programą linija, arba galite pavadinti funkciją. Taigi, jei jūs sakote pertrauka pagrindinė, jis sustos pagrindinis, ir jums eiti per tą funkciją. 

Taip pat, jei turite šiek tiek išorinė funkcionuoja kaip Sukeisti arba kubo, kad mes pažvelgė praeitą savaitę. Jei sakai, kad sulaužytų bent vieną iš tų, kai jūsų programa hitai, kad tai lauksiu tavęs į pasakyti, ką daryti. Prieš tai tik vykdyti, todėl jūs iš tikrųjų galėtų įžengti funkcijos ir pamatyti, kas vyksta. Taigi, Kitas, tiesiog praleidžia per Kitas linija, eina per funkcijas. Žingsnis. Visa tai yra tiek abstraktus. Taigi, aš tik ketina važiuoti per juos, bet pamatysite juos naudoti sekundę. 

Įženkite į funkciją. Taigi, kaip aš sakiau, kaip su Swap, būtų leidžia realiai taip, jei esate kaip fiziškai gerinimo viduje, galite netvarka su tų kintamųjų, spausdinimo , kas jie yra, pamatyti, kas vyksta. Sąrašas bus tiesiog tiesiog atsispausdinti iš aplinkinių kodą. Taigi, jei jūs rūšies pamiršti kur esate savo programą, ar jums įdomu, kas vyksta aplink jį, tai tiesiog atsispausdinti segmentą panašių penkis ar šešis linijas aplink jį. Taigi, galite orientuotis apie tai, kur esate. 

Spausdinti šiek kintamasis. Taigi, jei turite kaip raktą į Cezaris, kad mes pažvelgti. Galite pasakyti Spausdinti Raktas bet kuriame taške. Jis jums pasakys, ką vertė yra tokia kad gal kažkur pakeliui, Jūs perrašė savo raktą. Jūs iš tikrųjų galite pasakyti, kad dėl to, Jūs iš tikrųjų galite stebėti šią vertę. 

Be vietinių gyventojų, tiesiog spausdina iš savo vietos kintamieji. Taigi, bet kuriuo metu jūs per kilpą, ir jūs tiesiog norite pamatyti, kaip, oh. Kas yra mano aš? Kas tai yra esminė vertybė kad aš inicijuoti čia? Kas yra šioje vietoje žinutė? Tai bus tiesiog atsispausdinti visas tų, kad jums neturite atskirai pasakyti, Spausdinti I. Atspausdinti pranešimą. Spausdinti Key. Ir tada ekrane. Ką tai daro, yra, kaip jūs žingsnis įgyvendinant programą, jis bus tiesiog įsitikinkite, kad jis rodyti nuo galimos kintamojo kiekviename taške. Taip, kad jūs also-- --it yra rūšies Trumpuoju kur Jūs neturite nesustoti kaip, oh. Spausdinti Raktas arba Print I. Jis tiesiog automatiškai padaryti tai už jus. 

Taigi, su tuo, kad mes ketiname pamatyti, kaip tai vyksta. Aš einu bandyti ir jungiklis į mano prietaiso. Pamatyti, jei aš galiu tai padaryti. Viskas. Mes tiesiog ketiname dubliuoti jį. Nėra nieko kvailai mano nešiojamas anyways. Gerai. Tai turi būti šis. Tai mažytis. Leiskite pamatyti, jei mes galime tai padaryti. 

Gerai. Alice akivaizdžiai kovoja čia truputį, bet mes gauti jį Momento. Gerai. Mes tiesiog ketiname padidinti tai. Gerai. Gali kiekvienas rūšies pamatyti, kad? Gal šiek tiek? Žinau, kad tai šiek tiek mažas. Galite ne visai išsiaiškinti kaip padaryti, kad šis didesnis. Jei kas nors žino. Ar kas nors žino, kaip padaryti jį didesnis? Gerai. Mes ketiname įdiegti su juo. Nesvarbu anyways, nes tai tik tai kodas, kuris jus vaikinai turėtų turi. 

Kas svarbiau yra terminalas čia. Ir mes čia Kodėl toks mažas? Parametrai. Oh. Tiesa Ike. Kaip tai? Iš ten. Yra tai, kad visiems geriau,? Gerai ,. Cool. 

Jūs žinote, kai esate per CS klasė techniniai sunkumai yra rūšies dalis the-- Taigi, galime išvalyti tai. Gerai. Taigi, čia skyrelyje, kurį mes turėjome čia. Cezaris yra vykdomasis failas. Taigi, aš padariau tai. Taigi, vienas dalykas, suvokti su GDB yra kad jis veikia tik ant vykdomąjį failą. Taigi, jūs negalite paleisti jį ant dotsy. Turite tikrai padaryti Įsitikinkite, kad jūsų kodas kaupia, ir kad ji iš tikrųjų gali būti paleisti. 

Taigi, įsitikinkite, kad, jei jis nėra kaupti, gauti jį rinkti, taip, kad jūs galite rūšies eina per jį. Taigi, norint pradėti GDB, visi jūs darote, Gloria tipas GDB, ir tada tiesiog failą, kurį norite. Aš visada su klaidomis ciesorių ". Bet jūs norite įsitikinti, nes tai vykdomąjį, TI dot flash kad reiškia, kad jūs ketinate paleisti CSI jūs ketinate vykdyti tai failai arba su derintuvės. Gerai. Taigi, jūs, kad jūs gaunate šis svaičiojimas natūra. Tai tik viską apie derintuvės. Jūs neturite iš tikrųjų turi nerimauti dabar. Ir, kaip matote, mes turime tai atviros skliaustas, BVP, artimi skliaustas, ir tiesiog rūšies atrodo mūsų komandinės eilutės, tiesa? 

Taigi, ką mes norime do-- --So, Pirmas dalykas, yra norime pasirinkti vieta sulaužyti. Taigi, yra vienas klaidą Šioje Cezario programos kad aš pristatyti, kad mes ketiname sužinoti. Tai, ką ji daro tai mano indėlis Barfoo visais dangteliais ir kažkodėl tai nekeičia A. Belieka Vien tai, Ar visa kita teisingai, bet antra raidė Nesikeičia. Taigi, mes ketiname išbandyti ir išsiaiškinti, kodėl taip yra. Taigi, pirmas dalykas, kurį paprastai noriu daryti, kai jums pradėti GDB yra išsiaiškinti, kur ją padalyti. 

Taigi imperatorius gana trumpas programa. Mes tik vieną funkciją, tiesa? Koks buvo mūsų funkcija Cezaris? Yra tik viena funkcija, Main tiesa? Pagrindinis yra funkcija visų jūsų programų. Jei nebuvo Main, galiu būti šiek tiek neramu dabar, bet aš tikiuosi, kad jūs visi turėjo Main ten. Taigi, ką mes galime padaryti, tai mes galime tiesiog pertrauka Main, kaip kad. Taigi, ji sako, gerai. Mes nustatome mūsų atskaitos tašką viena ten. 

Taigi, dabar, reikia atsiminti tai, Cezaris yra vienos komandinės eilutės argumentas teisę ir mes ne padaryti, kad dar kur nors. Taigi, ką jūs darote, yra tada, kai jūs iš tikrųjų eiti paleisti programa, bet programa, kad jūs veikia GDB, kad reikia komandų eilutę argumentai, kad jūs ketinate įvesti kai pirmą kartą pradėti eksploatuoti jį. Taigi, šiuo atveju, mes darome Paleisti su trimis pagrindiniais. Ir tai tikrai bus pradėti. 

Taigi, jei matote čia, mes turime Jei RC nėra lygus 2. Taigi, jei jus vaikinai visi kad byla, aš išsiuntė iki pamatysite, kad tai, kaip Pirmoje eilutėje mūsų pagrindinė funkcija, tiesa? Tai patikrinti, pamatyti, jei mes turime Reikiamas argumentais. Taigi, jei jums įdomu, jei RC yra teisinga, jūs galite padaryti kažką tiesiog kaip Spausdinti RC. RC yra du, kuris yra tikėjomės, tiesa? 

Taigi, mes galime eiti toliau, ir toliau per. Taigi, mes turime tam tikrą raktą ten. Ir mes galime atspausdinti savo svarbiausius įsitikinti, kad tai teisinga. Įdomi. Ne visai tai, ką mes tikėjomės. Taigi, vienas dalykas, suvokti su GDB pat yra kad tai nėra, kol jūs iš tikrųjų nukentėjo Kitas, kad linija, jums tik pamačiau iš tikrųjų įvykdytas. Taigi, šiuo atveju raktas nebuvo suteiktas, dar. Taigi, Key kai šiukšlių vertė kad matote ten apačioje. Neigiama $ 120-- --It s vienas milijardas ir kažkas keista dalykų teisę? Tai ne Key kad tikėjomės. Bet jei mes Hit Pirmyn, tada mes išbandyti ir Print key, tai tris. 

Kiekvienas matome, kad? Taigi, jei jūs gaunate kažką kad jūs kaip, palaukite. Tai yra visiškai negerai, ir aš nežinau, kaip tai įvyks, nes viskas, ką aš noriu padaryti, tai suteikia numerį, kintamasis, pabandyti pataikyti Pirmyn, bandykite spausdinti jis vėl, ir pamatyti, jei tai veikia. Nes tai tik ketina vykdyti ir realiai priskirti kažką po tavęs nukentėjo Pirmyn. Prasmės visiems? Uh huh? 

SPEAKER 2: Kai atsitiktinis numeriai, ką tai reiškia? 

SPEAKER 1: Tai tiesiog atsitiktinai. Tai tiesiog šiukšlių. Tai tiesiog kažkas, kad jūsų Kompiuteris atsitiktine priskirti. Cool. Taigi, dabar mes galime judėti per, ir taip Dabar turime šį paprastą tekstinį GetString. Taigi, leiskite man tiesiog įvesti ką nutiks, kai mes Hit Next čia. Mūsų GDB rūšies dingsta, tiesa? Tai todėl, kad GetString dabar vykdo, ar ne? Taigi, kai mes matėme teksto lygus GetString, atviros skliaustai ir skliaustai, ir mes hit Pirmyn kad turi realiai atliktus dabar. Taigi, tai laukia mums įvesties kažką. 

Taigi, mes ketiname įvesti savo maistą, kuris yra tai, ką jis nesugeba, kaip aš sakiau jums, ir kad tiesiog sako, kad tai baigė vykdyti, kad uždarytas laikiklis reiškia, kad jis išeinant iš tos kilpos. Taigi, mes galime paspausti Next, o dabar, kaip aš tikiu, kad esate visi susipažinę iš ciesorių tai, kas yra ši linija ketinate daryti. Jis skirtas int i lygu 0, N lygus Strlen, teksto, o vėliau I yra mažiau nei n, aš, plius, plius. Kas tai kilpa ketinate daryti? Atidarykite savo žinutę. Cool. Taigi, galime pradėti daryti, kad. 

Taigi, jei ši sąlyga nesutampa, mūsų pirmasis? Jei tai B, tai teksto I. Mes galite gauti informaciją apie mūsų vietiniai. Taigi, aš yra nulis, jei ir šešių, kuris tikimės, ir mūsų pagrindinis yra trys. Visa tai prasminga, ar ne? Šie skaičiai yra visi ką jie turėtų būti. Taigi, niekai? SPEAKER 3: Turiu atsitiktiniai skaičiai, minų. SPEAKER 1: Na, mes galime check-- --we galite kalbėtis apie tai per sekundę. Bet jūs turite būti gauti tai. Taigi, jei mes turime kapitalą B mūsų pirmasis, ši sąlyga turėtų sugauti jį, ar ne? Taigi, jei mes Hit Toliau matome kad šis Jeigu iš tikrųjų vykdo. Nes jei jūs po kartu savo kodą, Ši linija čia, kur teksto aš pakeičiamas šio aritmetinio, tik įvykdyti Jeigu IF sąlyga yra teisingas ar ne? 

GDB yra tik ketiname parodyti jums, dalykų, kurie yra iš tikrųjų vykdomas. Taigi, jei tai Jei sąlyga nebuvo įvykdyta, tai tik ketina pereiti prie kito linijos. Gerai? Taigi, mes turime, kad. Šis laikiklis reiškia, kad jis uždaryti iš tos kilpos dabar. Taigi, jis ketina pradėti iš naujo. Kaip, kad. Taigi, kad mes galime gauti informacijos apie mūsų vietinių gyventojų čia ir matome, kad mūsų pirmasis laiškas buvo pakeistas, ar ne? Tai dabar E, kaip ji turėtų būti. Taigi, mes galime tęsti. 

Ir mes turime šį patikrinimą. Ir šis tikrinimas turi dirbti, ar ne? Tai A. Jis turėtų būti pakeistas trys raidės priekį. Bet jei pastebėjote, mes gauti kažką kitą. Taigi šiuo atveju čia tai nustebino jis ir taip tai linija įvykdytas, kuris kartą mūsų B Tačiau, šiuo atveju čia, mes turime, kad jis tiesiog praleisti jį, ir nuėjo į [? L Siff. ?] Taigi kažkas vyksta ten. Ką tai sakau tai, kad, mes žinome, kad ji turėtų sugauti čia bet taip nėra. Ar kas nors pamatyti, ką mūsų problema yra ta linija? Tai labai minutė dalykas. Ir jūs taip pat galėtų pažvelgti į savo kodą. Jis taip pat line-- pamiršti, ką linija yra į there-- bet tai per [nesigirdi]. Taip? 

SPEAKER 4: Tai ant didesnės nei puslapis, jei jį skaityti knygą. SPEAKER 1: Būtent. Taigi, debuggerem negalėjo pasakyti Jūs, kad bet debuggerem gali jums žemyn į eilutę kad jūs žinote, neveikia. Ir kartais, kai ypač vėliau semestro, kai jūs susiduriame su šimto, kad šimtas keletą eilučių kodo, ir jūs nežinau, kur jis nesugeba, tai yra puikus būdas tai padaryti. Taigi, mes nustatėme, kad mūsų klaida. Galite nustatyti jį į savo failą, ir tada galima paleisti jį dar kartą, ir viskas veikia puikiai. Ir svarbiausias dalykas yra tai gali atrodyti kaip, Gerai. Taip. Cool. Žinai, ką jūs ieškote. Taigi, jūs žinojo, ką daryti. 

GDB gali būti itin naudinga, nes jums galite išspausdinti visus šiuos dalykus, kad jūs nebūtų. Tai daug daugiau naudingas nei printf. Kiek jūs naudojate kaip printf pareiškimų išsiaiškinti, kur klaidą buvo, tiesa? Taigi, su šiuo, jums nereikia turi nuolat grįžta, ir patinka komentuodamas į Printf arba komentuoja out, ir išsiaiškinti, kas Jūs turite būti spausdinti. Tai iš tikrųjų tik leidžia jums žingsnis per, spausdinti dalykai kaip jūs ketinate per, taip, galite stebėti, kaip jie keičiasi realiu laiku, kaip jūsų programa veikia. 

Ir tai dar reikia truputį tiek priprasti. Aš labai rekomenduoju tiesiog rūšies buvimo mažai nusivylė su juo už dabar. Jei praleisti valandą per Kitą savaitę išmokti naudotis GDB, Jūs sutaupysite sau tiek daug laiko vėliau. Ir pažodžiui. mes pasakyti tai žmonėms ir kiekvienais metais, ir aš atsimenu, kai aš paėmė klasė, buvau kaip aš bus gerai. Ne. Pset 6, išėjo, ir aš buvau kaip, aš gonna sužinoti kaip naudotis GDB nes aš ne žinoti, kas vyksta čia. 

Taigi, jei rasite laiko, kad naudoti jį mažesnių programų kad jūs ketinate būti dirba, kaip dirba per kažką panašaus Visionare, kaip šis. Arba, jei norite papildomų praktiką, aš tikiu, Galėčiau sugalvoti Buggy programas, jums debug, jei norite. 

Bet jei jūs tiesiog šiek tiek laiko gauti naudojamas į jį, tiesiog žaisti aplink su juo, ji tikrai jums gerai. Ir tai tikrai viena iš tie dalykai, kad jūs tiesiog turite pabandyti ir gauti savo rankas purvinas su prieš jūs tikrai suprasti. Aš tikrai tik supratau vieną kartą Turėjau debug dalykų su juo, ir tai daug gražiau turėti idėją kaip derinti anksčiau nei vėliau. Gerai. Cool. Aš žinau, kad tipo kaip avarijos metu į GDB, ir aš tikrai darbą gauti juos atrodo didesnis, kai kitą kartą. Cool. 

Taigi, jei mes grįžti į mūsų PowerPoint. Ar tai veikia? AWH. Taip. Gerai. Taigi, jei Jums kada nors reikės bet tie vėl ten sąrašas. Taigi Dvejetainiai Paieška, kurioje kiekvienas prisimena didelį reginį Dovydo nepaprastas telefonų knygas per pusę. I do not really gauti Telefonų knygų nebėra, nes kaip kur tu gauti telefonų knygeles šių dienų? Aš tikrai nežinau. Dvejetainiai Paieška. Ar kas nors prisiminti how Dvejetainiai paieškos darbus? Taip kuo? Taip? SPEAKER 5: Jūs žinote, kai pažvelgti kurių pusė tai būtų, Komisija, remdamasi ta, ir atsikratyti kita pusė. 

SPEAKER 1 Būtent. Taigi, Dvejetainiai Paieška, tai tipo a-- --we vadinam skaldyk ir valdyk. Taigi, ką jums daryti yra jums atrodo per vidurį, ir pamatysite, jeigu jis atitinka ką jūs ieškote. O jei ne, tada jums pabandyti išsiaiškinti, ar ruošiatės pusė arba į dešinę pusę. Taigi, tai gali būti, jei jūs ieškote ne kažką, kad abėcėliniame, matai, oh. Ar Allison ateiti prieš M? Taip. Taigi, mes ketiname peržvelgti pirmojo kėlinio. 

Arba tai gali būti, pavyzdžiui, su numeriais. Viskas, ką gali palyginti, jis gali būti rūšiuojami. Jūs galite naudoti dvejetainius paiešką. Taigi, kas tai prisiminti Grafikas arba kas tai yra? Tai Asimptotiniai sudėtingumo. Taigi, tai tiesiog grafikas aprašoma, kaip ilgai jis pateksite išspręsti problemą, kaip Padidinus dalykų kad jūs naudojate. 

Taigi, mes turime N, kuri yra linijinis laikas. Jei per du N, kuri yra šiek tiek geriau, vis tiek auga super greitai. Ir tada mes prisijungti, o tai ką mes laikome Dvejetainiai Ieškoti. Jei pastebime, kaip jūsų problemos gauna daug ir daug didesnis, laiko užtrunka jums ją išspręsti tikrai ne didinti, kad daug. Tai kaip lyginti Čia iš pradžių. Jūs kaip, Gerai. Viskas, kas čia tikrai ne Nesvarbu, kuris iš mūsų naudoti, bet jūs išeiti į milijono mlrd. Jūs bandote rasti some-- --you're bando rasti šieno kupetoje adatą. 

Manau, kad jūs norite šią problemą. Jūs norite šio sudėtingumo, o ne tiesinė, nes visiems jums žinau jūsų gonna naršęs kiekvienas individas adata, dalykas šieno, bando ieškoti savo adata. Ir tai dar ne per įdomus, mano nuomone. Man patinka greitai. Man patinka veiksminga. Ir kaip darbštūs studentai You vaikinai, žinote dirbti racionaliai, ne sunkiau tipas dalykas, kaip jus gali sudaryti šiuos algoritmus. 

Taigi, mes ketiname eiti per tik greitai pavyzdyje. Manau jums, vaikinai turėtų turėti ranka ant Binary paieška, bet jei kas nors yra šiek tiek fuzzy, noriu jį sustiprins, mes ketiname tiesiog eiti kaip pavyzdys čia. Taigi, mes ieškome jei masyvas yra septyni. 

Taigi, pirmas dalykas, kurį mes darome, yra ieškoti viduryje, tiesa? Ir jūs ketinate būti kodavimas Dvejetainiai Paieška vos sekundę. Taigi, jis ketina būti įdomus. Taigi, mes pažvelgti į vidutinio mažai masyvai 3. Ar 3 lygus 7? Nėra. Tai šeši. Taigi, tai mažiau nei arba didesnė negu septynių? Mažiau nei. Taip. Nice job guys. Jaučiu, kaip aš turėtų turėti saldainį, nes aš nori mesti jį iš į laivų statyklas. Tai, ką aš ketinu daryti kitą savaitę. Tai leis jums vaikinai aštrus. 

Taigi, mes išmetame, kad pirmąjį pusmetį, tiesa? jis buvo mažesnis nei. Mes žinome, kad viskas tą dešinėje pusėje bus mažiau, nei mes iš tikrųjų ieško. Taigi, nėra reikalo atkreipti dėmesį į tai. Tiesiog pamiršti apie jį. Taigi, dabar mes pažvelgti į mūsų dešinėje, ir mes pažvelgti į vidurį ten, ir dabar tai yra devyni. Taigi, 9 is-- --Everyone? Didesnis, nei mes esame ieško, tiesa? Taigi, mes ketiname mesti toli viskas į dešinę. Patinka. Dabar visi mes liko su viena. Taigi, mes patikrinti, ar tai vienas, kas mes ieškome? ji yra. Mes nustatėme, ką mes norėjome. Taigi, mes baigsime. Bilinear Paieška. 

Ir, jei pastebėsite, mes turėjo septynis įėjimus ten. Tai tik buvo mums kaip tris kartus, bet jei darai kaip milijardo, Jūs žinote, kiek žingsnių jis būtų imtis, jei mes turėjome keturis milijardus dalykų? Bet kokios spėlionės? Tai 32. 32 žingsnių, kaip rasti ką nors į keturis milijardus elementas masyvo, nes įgaliojimų dviejų. Taigi du yra 32, tai iki keturių milijardų. 

Taigi gana kvailai kaip jūs vis dar per lyg gana nedidelio skaičiaus žingsnių Surasti ką nors per keturis milijardus elementai. Taigi dėl šio rašto, mes ketina koduoti tai taip jus vaikinai galite realiai rūšies pamatyti, kaip tai veikia. Gerai, taigi jūs vaikinai gali koduoti. Aš ruošiuosi praleisti you guys kalbėti truputį. Gauk pažinti žmones aplink jus, kurie yra ką kažkas norėjo iš paskutinio skyrių. 

Taigi pažinti aplink jus žmonių. Kalbėti truputį. Ir viskas, ką aš noriu iš jūsų vaikinai dabar yra tiesiog pabandyti sukurti daug Pseudocode metmenis. Gerai? Whoa. Viskas, ką aš noriu iš jūsų vaikinai yra jums tik ketina užpildyti šią while atveju. Taigi aš jį pasirinkote viršutinis ir apatinė ribos, kuri atstovauti pradžią ir pabaiga mūsų masyvas. Ir jūs ketinate tikrai kilpa per ir išsiaiškinti ką mes darome šioje while cikle. 

Taigi, jei galite išsiaiškinti out-- Turiu there-- kokie atvejai užuomina kad mes čia? Taigi, jei norite suprasti, atvejai, mes Pseudocode tie ir tada mes iš tikrųjų kodą juos. Ir tai bus, aš manau, tikiuosi jis bus būti šiek tiek lengviau, nei jūs tikėjotės. Nes tai, kad daug kodas, iš tikrųjų, tai yra tikrai cool. 

Mm-hm? 

STUDENTŲ: [nesigirdi]? Instruktorius: Taip. Ten buvo kažkas rasti viduryje. 

STUDENTŲ: Taigi, mes galime naudoti, kad. Gerai. 

Instruktorius: Puikus. Štai pirmas dalykas, kurį turime padaryti. Taigi rasti vidurį. Puikus. Taigi jūs turite idėją, kaip mes galime tikrai rasti vidurį su kodu? 

STUDENTŲ: Taip. n per 2? Instruktorius: Taigi n virš 2. Taigi vienas dalykas, prisiminti tai, kad viršutinėje ir apatinė ribos keisti. Mes nuolat Traukiasi detalę masyvo mes ieškome. Taigi n per 2 veiks tik Pirmą dalyką mes. Taigi atsižvelgiant viršutinės ir apatinės į, kaip gali mes gauti, kad vidurinioji elementas? Nes mes norime, kad vidurį tarp viršutinio ir apatinio, tiesa? Mm-hm? 

STUDENTŲ: [nesigirdi]. 

Instruktorius: Taigi, mes turime šiek tiek vidurį. Ir tai bus viršutinė plius mažesnis nei 2. Nuostabus. Štai taip. Viena eilutė žemyn. Jūs vaikinai yra jūsų būdas. Taigi, dabar, kad mes turime mūsų viduryje, ką mes norime daryti? Tiesiog apskritai. Jūs neturite kodą jį. Taip. STUDENTŲ: [nesigirdi]? Instruktorius: Taigi tai pliusas, nes esate rasti tarp dviejų vidutinių iš jų. Taigi, jei jūs manote apie juos kaip natūra padidinti iš šonų, Pagalvokite apie tai, kaip jūs požiūris viduryje, norite panašaus. Taigi, jei jums buvo iš abiejų pusių viduryje, ir mes turime kaip 5 ir 7. Jei norite pridėti jas kartu jums gauti 12, padalinti iš 2, tai 6. 

Kartais sunku paaiškinti, kodėl tai veikia, bet jei jūs dirbate per pavyzdys kartais, tai padėsime Jums išsiaiškinti, ar ji turėtų būti plius minus. Taip. 

STUDENTŲ: [nesigirdi] tiksliai per vidurį jei jie buvo atvejis, kai ten mažesnį gyvūnų skaičių daug ir kaip vieną didelį skaičių? 

Instruktorius: Taigi viskas, ko jums reikia yra viduryje masyvo. Taigi, jei jūs turėjote mažų skaičių krūva ir tada iš tikrųjų daug pabaigoje, nesvarbu. Svarbu tik, kad jie rūšiuojami, jums tiesiog nori pažvelgti į vidurį masyvas, nes jūs vis dar nukirto savo problemą per pusę. Cool. Taigi, dabar, kad mes turime viduryje, ką mes darome toliau? 

STUDENTŲ: Palyginimas. Instruktorius: palyginti. Taigi palyginti viduriu value_wanted. Cool. Taigi, kaip matote čia turime ši vertė norime čia. Atminkite, kad tai masyvas. Taigi nuoroda į viduriniosios indeksą. Taigi, mes norime padaryti vertybes viduryje. Nepamirškite, jei norite palyginti, dvigubos lygių. Jūs vienas lygu tu tik ketina perleisti jį, ir tada, žinoma, tai bus norimą reikšmę. Taigi nereikia daryti. 

Taigi, mes ketiname pamatyti, jei Viename įėjimo viduryje vertės yra lygi vertei norime. Nepamirškite petnešos. Dropbox turėtų išeiti. Taigi, ką mes darome šiuo atveju? Jei tai, ką mes norime grįžti? Mes bandome pasakyti. 

STUDENTŲ Spausdinti išjungtas. 

Instruktorius: Na, mes nenoriu atsispausdinti. Taigi tai yra bool čia, todėl mes nori grįžti true arba false. Mes sakydamas tai skaičius [? RRA? ?] Taigi, jei ji yra, mes tiesiog grįžti tiesa. Jei aš galiu rašybos tiesa. 

STUDENTŲ: Kodėl gi ne grįžti prie nulio? Instruktorius: Taigi tu gali grįžti prie nulio, jei norite. Tačiau šiuo atveju, nes Mūsų funkcija grąžina bool, turime grįžti arba true arba false. STUDENTŲ: Kai būsite sakydamas loginę išraišką, galite nustatyti, kad jis lygus klaidingas? Pavyzdžiui, jei aš noriu pasakyti, jei ši sąlyga netenkinamas, kaip yra viršutinis lygus klaidinga. Ar tai suprasti, jei jūs tiesiog įdėti klaidinga, o kita pusė? Instruktorius: Taip. Taigi iš tikrųjų, jei esate kada darai kažką kaip yra viršutinė arba apatinė, kad grąžina true arba false ir tai tikrai blogai stilius tarkim lygus lygus true arba kaip lygių lygus klaidinga. Norite naudoti tą rezultatą kaip pati kaip čekį. Ne tai, ką norėjau. Štai ką aš norėjau. Taigi, jus atveju esate klausia apie kažką kaip išsaugoti tai c. 

Taigi, jei mes turime int main (void) ir kažkas panašaus į tai. Ir jūs turite jei yra viršutinė iš tų pačių įvesties ir jūs klausia, ar jūs galite padaryti kažkas panašaus į tai? Teisė? STUDENTŲ: aš bandžiau daryti tai [nesigirdi]. Nes jei it's-- Instruktorius: Teisė. Taigi jūs norite, kad tai būtų klaidinga, tiesa? STUDENTŲ: Taip. Instruktorius: Taigi, šiuo atveju jums noriu, kad ji vykdo, jei tai nėra tiesa. Taigi kietas dalykas jums yra ši. Taigi nepamirškite šauktuko taškas paneigia dalykus? Ji sako [nesigirdi] reiškia ne. Taigi, jei mes pažvelgti tik čia tai dalis, norite sako, kad vertina, kad false, kaip jūs norite. Nėra netikras tiesa, kuri reiškia tai atlikti. Ar tai prasminga? STUDENTŲ: Taip. Instruktorius: Awesome. Gerai. Taigi, mes galime tiesiog grįžti tiesa šiuo atveju. Taigi dabar mes turime dvi kitos atvejų ir šiuo atveju. Kokie du mūsų ir kitų atvejų? Tegul tik tai padaryti tokiu būdu. Taigi pradėkime dar jei koncentracijos vertės viduryje yra mažesnis nei vertė, mes norime. Taigi, mūsų vertė viduryje yra mažesnis negu vertė, mes ieškome. 

Taigi, kuris jungiasi padaryti jums manau, kad mes norime atnaujinti? Mažiausia ar didžiausia? Viršutinė? Taigi to, kurioje pusėje masyvas mes ketiname būti žiūri? 

STUDENTŲ: mažesnis. 

Instruktorius: Mes einame būtų pažvelgti į kairę. Taigi kitas, jei mažai vertė yra mažesnė. Taigi jūsų vidutinis dydis čia yra mažesnis nei tai, ką norime. Taigi, mes norime imtis Dešinėje mūsų masyvas. Taigi mes ketiname atnaujinti mūsų apatinė. Taigi mes perleisti savo mažesnės. Ir ką jūs manote mažesnis turėtų būti? STUDENTŲ: vidurinioji vertė? Instruktorius: Taigi vidurinioji value-- STUDENTŲ: Plius 1. Instruktorius: --plus 1. Ar kas nors pasakykite man, kodėl mes turime, kad plius 1? 

STUDENTŲ: [? Nėra vertė?] yra lygus daugiau į jį. 

Instruktorius: Teisė. Nes mes jau žinome, kad mūsų viduriniosios vertė nėra lygus tai ir norime ją pašalinti nuo visų tolesnių paieškų. Jei pamiršote, kad plius 1, tai patiks kilpa neribotą laiką. Ir jūs tiesiog būsite pagauti begalinis ciklas, o tada jūs segfault ir viskas vyks blogai. Taigi visada įsitikinkite, kad esate ne įskaitant kiekį, kurį ką tik pažvelgė. Taigi, mes pasirūpinsime, kad su pliuso 1. 

Taigi dabar mes turime paskutinė sąlyga aš visada už saugos labui galite patikrinti čia dar, jeigu vertė viduryje yra didesnė, negu vertė norime. Tai reiškia, kad mes norime kairė ranka pusė. Taigi, kuris iš jų mes ketiname atnaujinti? Viršutinė. Ir kas tai yra vienas ketina prilygti? Vidurio minus 1, nes, Žinoma, mes norime, įsitikinti, kad mes ne žiūri šią vidutinis dydis dar kartą. Ir tuomet mes jį. Štai ir viskas. Tai viskas, dvejetainis paieška. Tai nereiškia, kad blogai, tiesa? Tai kaip 10 eilučių kodas su tarpais. Taigi labai galingas, labai naudinga, jums naudojate jį vieną iš savo vėlesnių psets. Gal ne tai viena, bet vėliau. Taigi išmokti. Tai patinka. Jis bus su jumis elgtis gerai. Taigi ar kas nors turi bet klausimai dvejetainis paieškos? Taip. 

STUDENTŲ: Ar tai svarbu ar jūsų n yra lyginis ar nelyginis? 

Instruktorius: Ne. Nes mes retai jį į vidurį, kaip int, ji bus tiesiog trumpinti vartų. Taigi jis liks sveikasis ir jis bus galiausiai rūšiuoti per viską. Taigi jūs neturite jaudintis dėl to. Kiekvienas geras? Nuostabus. Cool. Taigi, jūs vaikinai turite tai. Skaidrės. Taigi, kaip mes kalbame apie, aš žinau, Davidas minėta sudėtingumo runtimes. 

Taigi geriausiu atveju, tai tik vienas, kurį mes vadiname pastovų laiką. Ar kas nors pasakykite man, kodėl tai gali būti? Kokio tipo scenarijų būtų, kad sukelti? Mm-hm. 

STUDENTŲ: [nesigirdi] first-- Instruktorius: Taigi vidurinioji yra Pirmasis elementas, kad mes atėjo, ar ne? Taigi, arba vienas masyvas arba Mes ieškome tik kokia būna, Žiaurus DAB viduryje. Štai mūsų geriausias atvejis. Gauni į realias problemas, tikriausiai ne ketina pasiekti [nesigirdi], kad dažnai. Ką apie mūsų blogiausiu atveju? Mūsų blogiausias atvejis žurnalas n. Ir kad turi daryti su visa įgaliojimai dviejų dalykas, kad aš kalbėjau apie. 

Taigi, blogiausiu atveju tai reikštų, kad mes turėjome pjaustyti masyvas žemyn kol jis buvo vienas elementas. Taigi mes turėjome jį nukirsti žemyn per pusę tiek kartų, kiek mes galbūt galėtų. Štai kodėl tai yra žurnalas n nes Jūs tiesiog nuolat dalijant iš dviejų. Taigi prielaidos, dalykų, kuriuos reikia žinoti, jei jūs kada nors ketinate naudoti dvejetainius paiešką. Jūsų elementai turi būti rūšiuojami. Jie turi būti rūšiuojami nes kad vienintelis būdas jums gali žinoti, jei gali išmesti lygiai pinigų. 

Jei turėjo šį Pogmatwany maišą Skaičių ir jūs sakote, Gerai, aš einu patikrinti vidurį skaičius ir skaičius Aš ieškau yra mažiau nei, kad aš tik ketina savavališkai išmesti pusę. Jūs nežinote, jei jūsų numeriai toje kitoje pusėje. Jūsų sąrašas turi būti rūšiuojami. Kaip gerai, tai gali būti vyksta į priekį šiek tiek, bet jums reikia turėti laisvą priėjimą. Jums reikia, kad būtų galima tiesiog eiti į tą vidurinę elemento. Jei turite feed per kažką arba pateksite papildomų priemonių patekti į šios viduriniosios elementų, tai nėra prisijunkite n nebėra, nes norite pridėti daugiau darbo į jį. Ir tai bus padaryti šiek tiek daugiau jausmas per dvi savaites, bet aš tiesiog rūšies norėjo įvadas, jums vaikinai, ką galite idėją ateiti. Tačiau tai du svarbios prielaidos kad jums reikia dvejetainėje sąrašą. Įsitikinkite, kad jis rūšiuojami. Štai vienas didelis už vaikinai dabar. Ir kad mes galime eiti į Mūsų rūšių poilsio. Taigi keturios sorts-- burbulas, įterpimo, atranka, ir sujungti. Jie visi cool natūra. Jei jus vaikinai nusprendžia imtis CS 124, Sužinosite apie visų rūšių rūšių. Ir jei esate XKCD ventiliatoriumi yra tikrai cool komiksų apie kaip tikrai neefektyvios rūšių, kurią aš labai rekomenduoju jums eiti ieškoti. Vienas iš jų yra kaip panikos rūšiuoti, kuris yra kaip, oh no, grįžti atsitiktinių masyvo. Stabdymo sistemos. Palikite. Taigi kelianti nuotaika visada gera. 

Taigi ar kas nors prisiminti natūra tiek kaip tiesiog bendra idėja kaip burbulas rūšiuoti veikia. Jūs prisimenate? 

STUDENTŲ: Taip. 

Instruktorius: eiti į jį. 

STUDENTŲ: Taigi jūs ketinate per ir jei tai didesnis, tada sukeisti du. 

Instruktorius: Mm-hm. Tiksliai. Taigi jūs tiesiog kartoti, kad. Patikrinti du numeriai. Jei vienas prieš didesnis nei vėliau apie tą, tiesiog apsikeitimo juos taip, kad šis būdas visus didesnius numerius burbulas iki link sąrašo gale ir visi mažesni numeriai burbulas žemyn. 

Ar jis rodo jums, vaikinai cool Garso efektų rūšiavimas video? Tai tipo kietas. Taip Robertas ką tik pasakė, kad algoritmas kad jūs tik žingsnis per sąrašą, Swapping gretimų verčių jei jie ne tam. Ir tada tiesiog nuolat kartoti kol jums nereikia atlikti jokių apsikeitimo sandoriais. Taigi nėra blogai, tiesa? Taigi mes tiesiog greitai pavyzdį čia. Taigi tai vyksta rūšiuoti juos didėjančia tvarka. Taigi, kai mes eiti per pirmas laikas, mes žiūrime per aštuonių ir šeši akivaizdžiai nėra tam mes apsikeitimo. 

Taigi pažvelgti į kitą. Aštuoni ir keturi ne tam. Apsikeitimo. Ir tada aštuonių iki dviejų, apsikeitimo. Štai taip. Taigi po pirmojo perdavimo, jūs žinoti, kad jūsų didžiausias skaičius bus visas kelias viršuje, nes tai tik bus nuolat didesnis nei visa kita ir tai tik ketina burbulo iki visą kelią iki pabaigos ten. Ar tai prasminga visiems? Cool. 

Taigi mes pažvelgti į mūsų antrąjį perdavimą. Šeši ir keturi, jungiklis. Šeši ir du, jungiklis. Ir dabar mes turime keletą dalykų, kad. Taigi už kiekvieną perdavimą, kad mes padaryti per visą mūsų sąrašą, mes žinome, kad, pavyzdžiui, kad daug skaičių pabaigoje jau bus rūšiuojami. Taigi mes trečią perdavimą, kuris yra vienas swap. Ir tada mūsų ketvirtas praeiti, mes nulis lizdus. Ir todėl mes žinome, kad mūsų masyvas išrūšiuota. 

Ir tai yra didelis dalykas su bubble rūšiuoti. Mes žinome, kad, kai mes nulis apsikeitimo, kad reiškia, kad viskas yra visiškai tvarka. Tai tipo kaip mes tikriname. Taigi mes taip pat ketiname kodą burbulas rūšiuoti, kuri taip pat yra ne tai, kad blogai. Nė vienas iš jų yra taip blogai. Žinau, kad jie gali atrodyti šiek tiek baisu. Žinau, kai aš paėmė klasė, net tada, kai aš dėstė klasės Pirmą kartą pernai, Buvau kaip, kaip man tai padaryti? Prasminga teoriškai, bet kaip mes iš tikrųjų tai padaryti? Kuris yra, kodėl aš noriu nueiti per kodą su jumis vaikinai čia. Taigi turiu Pseudocode už jus vaikinai šiuo metu. Taigi tiesiog laikyti tai galvoje, kaip mes ruošiamės pereiti per. Taigi, mes turime šiek tiek skaitiklis, kad stebi mūsų apsikeitimo sandorius, nes mums reikia įsitikinti, kad mes patikrinti, kad. Ir mes pakartoti visą spektrą kaip mes tiesiog padarė su šiuo pavyzdžiu. Jei elementas yra didesnis nei prieš po kur mes į elementą, mes apsikeitimo ir mes prieaugio DUK skaitliukas nes kai tik mes apsikeitimo, norime pranešti mūsų counter žinote, kad. Visus klausimus ten? Kažkas atrodo juokinga čia. STUDENTŲ: Ar jums nustatykite nulį skaitliukas kiekvieną kartą jūs einate per kilpą? Ar ne jūs nesustoti atgal iki nulio, kiekvieną kartą? Instruktorius: Nebūtinai. Taigi, kas atsitinka, yra mes eiti per čia. Taigi, tai, o, atminkite, tai atliks vieną kartą, be nepavyks. Taigi jis ketina nustatyti skaitiklis lygus nuliui, tada jis ketina pakartoti per. Nes ji kartojasi, ji atnaujina skaitiklis. Kaip jis patikslina skaitiklis, kai tai daroma, kai jis pasiekė masyvo pabaigos, jei mūsų sąrašas nebuvo rūšiuojamos, skaitiklis buvo atnaujintas. 

Taigi tada ji patikrina sąlygą ir ji sako, gerai, yra skaitiklis didesnis už nulį. Jei taip yra, tai padaryti dar kartą. Norite pakeisti taip, kad, kai jūs eiti per, skaitiklis yra lygi nuliui. Jei jūs einate per Rūšiuota masyvas, niekas nesikeičia, tai nepadeda, ir jūs grąžinti surūšiuoti sąrašą. Ar tai prasminga? STUDENTŲ: Tai gali dar šiek tiek. Instruktorius: Gerai. Jei yra bet koks kitas klausimas, kuris ateina į viršų. Taip. 

STUDENTŲ: koks būtų funkcija būti už Swapping elementus? 

Instruktorius: Taigi mes iš tikrųjų galite rašyti kad jei mes ketiname dabar. Cool. Taigi dėl šio rašto, Alison vyksta pereiti atgal į prietaisą. Ji ketina būti įdomus. Ir mes turime gražus burbulas rūšiuoti dalykas čia. Taigi, aš jau padariau dviračiu per masyvą. Mes turime apsikeitimo kad yra lygi nuliui. Taigi, mes norime apsikeitimo gretimų elementai, jeigu jie iš tam. Taigi pirmas dalykas, kurį mes turime do yra kartoti, kad mūsų masyvas. 

Taigi, kaip jūs manote, mes galime kartoti, kad mūsų masyvas? Mes turime ir i lygu 0. Mes norime būti mažiau i nei n minus 1 minuso k. Ir aš paaiškinti, kad per sekundę. Taigi tai yra čia, kur optimizavimas, Prisimenu, kaip sakiau po kiekvieno perdavimo per masyvą mes žinau, kad visada kas on-- 

Taigi, po vieną perdavimą mes žinau, kad tai yra rūšiuojami. Po dviejų važiavimų žinome kad visa tai yra rūšiuojami. Po trijų važiavimų mes žinau, kad manimi rūšiuojami. Taigi, kaip aš Iteracja per masyvas čia yra tai įsitikinkite, kad eiti tik per tai, ką mes žinome, yra nerūšiuotas. Gerai? Tai tiesiog optimizavimas. Galite rašyti naiviai tik Iteracja per viską, jis tiesiog trunka ilgiau. Su šia keturių kilpa tai tiesiog gražus optimizavimas nes mes žinome, kad po kiekvieno pilnas iteracijoje masyvo čia Kaip ir kiekvieną pilną kilpą čia, mes žinome, kad vienas daugiau iš šių elementų bus surūšiuoti pabaigoje. 

Taigi mes neturime nerimauti tiems. Ar tai prasminga visiems? Kad kietas mažai triukas? Taigi šiuo atveju, jei mes Iteracja per, mes žinome, kad mes norime patikrinti, ar masyvas n ir n yra 1 plius tvarka. Gerai. Taigi čia Pseudocode. Norime patikrinti, ar masyvas n ir n yra 1 plius tvarka. Taigi, kas gali šiuo metu ten? Ji ketina būti šiek tiek sąlygiškas. Tai bus jei. 

STUDENTŲ: Jei masyvas n mažiau nei masyvo n plius 1. Instruktorius: Mm-hm. Na, yra mažesnis arba didesnis nei. STUDENTŲ: Daugiau nei. Tada mes norime apsikeitimo. Tiksliai. Taigi, dabar mes į tai, kas mechanizmas Swapping juos? Taigi mes perėjome šį trumpai, Swap funkcija praėjusią savaitę tipas. Ar kas nors prisimena, kaip jis dirbo? Taigi, mes galime ne tik perleisti juos, tiesa? Kadangi vienas iš jų bus prarasti. Jei mes sakėme yra lygi B ir tada B yra lygi į A, visi staiga abu tik lygus B. 

Taigi, ką mes turime padaryti, tai mes turėti laikiną kintamąjį, kad manimi ketina surengti vieną Voyager "Mūsų laiką mes į Swapping procese. Taigi, ką mes turime, yra mes turime šiek tiek int temp lygus to-- galite priskirti jį į bet kurio norite, tiesiog Įsitikinkite, kad jums sekti it-- Taigi šiuo atveju, aš ruošiuosi priskirti ją masyvo n plius 1. Kad ketina surengti kokia vertė yra toje antrojo bloko kad mes ieškome. 

Ir tada mes galime padaryti, tai mes galime eiti į priekį ir Priskirti masyvas n plius 1, nes mes žinome, mes turi tą reikšmę, registravimo. Tai taip pat viena iš didžiausių Quake aš nežinau, jei kas nors iš jūsų turėjo problemų, kur, jei jums pereiti du eilučių kodo staiga viskas dirbo. Užsakyti Labai svarbu CS. Todėl įsitikinkite, kad žy dalykų, jei įmanoma kaip į tai, kas iš tikrųjų vyksta. Taigi, dabar mes ketiname perleisti masyvo n plius 1, nes mes žinome, mes turi tą reikšmę, registravimo. 

Ir mes galime priskirti, kad į masyvą n ar šiuo atveju masyvo i. Per daug kintamųjų. Gerai. Taigi, dabar mes perskirstomas masyvas I plius 1 prilygti kas išsirikiavo i. Ir dabar mes galime grįžti ir priskirti masyvo I-ką? Kiekvienas? 

STUDENTŲ: 10. 

Instruktorius: 10. Tiksliai. Ir paskutinis dalykas. Jei mes pavertė jį dabar, ką mes turime padaryti? Kas vienas dalykas kad ketina pasakyti mums jei mes kada nors nutraukia programą? Ką mums sako, kad mes turi surūšiuoti sąrašą? Jei mes neturime eiti jokių apsikeitimo, tiesa? Jei apsikeitimo lygus lygiu nuliui tai pabaigoje. Taigi, jei jums atlikti swap, nes mes tiesiog padariau čia, mes norime atnaujinti apsikeitimo sandoriais. Ir aš žinau, ten buvo klausimas anksčiau apie jūs galite naudoti nulį arba vieną vietoj iš true arba false. Ir tai, kas tai daro čia. Taigi tai sako jei ne apsikeitimo sandoriais. Taigi, jei apsikeitimo yra lygus nuliui, kuris is-- Visada gauti savo tiesas ir mano falses sumaišyti. Norime mums įvertinti true, ir tai ne. Taigi, jei tai nulis, tada tai klaidinga. Jei paneigti ją [? bang?] tampa tiesa. Taigi ši eilutė vykdo. 

Tiesos ir netikras nulių ir gauti iš proto. Tiesiog jei jums lėtai vaikščioti per ją jis bus prasminga. Bet tai, ką ši maža tiek kodą čia veikia. Taigi ši tikrina, mes padarėme jokių apsikeitimo sandoriais. Taigi, jei tai nieko, be nulis, jis ketina būti klaidinga ir visa tai yra ketina vykdyti dar kartą. Cool? 

STUDENTŲ: Ką pertrauka daryti? 

Instruktorius: Break tiesiog pertraukos jus iš kilpos. Taigi šiuo atveju tai būtų tik norėčiau baigti programą ir jūs, tiesiog turėti savo surūšiuoti sąrašą. STUDENTŲ: Amazing. Instruktorius: Aš atsiprašau? STUDENTŲ: Kadangi anksčiau mes panaudodavo 1 per parašyta nulis pateikti, kad jei kad dirbs, ar ne. 

Instruktorius: Taip. Taigi galite grįžti prie nulio arba 1. Šiuo atveju, nes mes ne iš tikrųjų ką nors su funkcija, mes tiesiog norime, kad ji nutraukti. Mes tikrai rūpi tai. Stabdžių pat gera, jei ji naudojama išeities iš keturių kilpų ar sąlygas Jūs nenorite išsaugoti vykdomas. Tai tik mano jus iš jų. Tai iš niuansas dalykas tiek. Jaučiu, kaip ten rankų garbanojimo daug, kaip jūs sužinosite apie tai netrukus. 

Bet jūs sužinosite apie tai netrukus. Pažadu. Gerai. Taigi ar visi gauti burbulas rūšiuoti? Neblogai. Kartoti, kad, apsikeitimo dalykų, naudojant temp kintamasis, ir mes visi nustatyti ten? Cool. Nuostabus. Gerai. Atgal į PowerPoint. Bet kokie apskritai klausimai apie tai iki šiol? Cool. Mm-hm. 

STUDENTŲ: [nesigirdi] int main paprastai. Ar jūs turite turėti, kad už tai? 

Instruktorius: Taigi mes tiesiog ieškote tiesiog faktiniu rūšiavimo algoritmą. Jei turėjo jį per kaip didesnės programos, jūs turite int main kažkur. Priklausomai nuo to, kur jums naudoti šį algoritmą, būtų nustatyti, kas , grąžinami jį. Bet mūsų atveju, mes griežtai žiūri kaip tai iš tikrųjų kartoti, kad masyvo. Taigi mes ne nerimauti apie tai. 

Taigi mes kalbame apie geriausią atvejį ir blogiausio atvejo scenarijai dvejetainis paieškos. Taigi tai taip pat svarbu daryti kad už kiekvieną iš mūsų rūšių. Taigi, ką jūs manote yra blogiausia atvejis runtime iš burbulo rūšiuoti? Vaikinai prisiminti? 

STUDENTŲ: N minus 1. Instruktorius: N minus 1. Taigi tai reiškia, kad yra n minus 1 palyginimai. Taigi vienas dalykas suprasti, kad remiantis pirmajam iteracijos procesui apskaičiavimas, mes pereiti per, mes palyginti tai two-- todėl tai 1. Šie du, trys, keturi. Taigi, po vieną iteracijos mes jau turi keturis palyginimų. Kai aš kalbu apie runtime ir n. N atstovauja palyginimų skaičių kaip kaip daug elementų funkcijos turime. Gerai? 

Taigi mes pereiti, mes turime keturis. Kitą kartą jūs žinote, mes ne turi rūpintis šio. Palyginus šias dvi, šie du, tai du, ir jei mes neturėjo tokio optimizavimas su keturių kilpa, kad aš parašiau, jums bus palyginti čia anyways. Taigi jums reikės paleisti per masyvo ir padaryti n palyginti n kartų, nes kiekvieną kartą paleisti per jį mes rikiuoti vieną dalyką. 

Ir kiekvieną kartą, kai mes paleisti per masyvas, mes n palyginimų. Taigi, mūsų runtime už tai tikrai n kvadratu, kuris yra daug blogesnė mūsų prisijungti pabaigą, nes tai reiškia, jei mes turėjome keturis Milijardas elementai, tai ketina imtis mums keturis milijardus kvadrato, o ne 32. Taigi ne pats geriausias runtime, tačiau dėl tam tikrų dalykų, žinote, jei esate per tikras asortimentas elementų burbulas rūšiuoti gali būti bauda naudoti. 

Gerai. Taigi, dabar, kas yra geriausias atvejis runtime? STUDENTŲ: Zero? Arba 1? 

Instruktorius: Taigi 1 būtų vienas palyginimas. Teisė. 

STUDENTŲ: N minus 1? 

Instruktorius: Taigi, yeah. Taigi n minus 1. Kiekvieną kartą, kai jūs turite kaip n koncepciją minus 1, mes linkę tiesiog įmeskite ir mes tiesiog pasakyti n, nes jūs turite Palyginimui kiekviena iš kiekvienos poros these--. Taigi būtų n minus 1, kurį mes mes ką tik pasakyti maždaug n. Kai jūs susiduriame su runtime, viskas yra artima. Tol eksponentė yra teisinga, jūs gana gera. 

Štai kaip mes susidoroti su juo. Taigi, kad geriausiai atvejis yra n, kuris reiškia, kad sąraše jau rūšiuojamos, ir visi mes darome, yra persmelkti ir patikrinkite, ar jis rūšiuojami. Cool. Gerai. Taigi, kaip matote čia, mes tereikia šiek tiek daugiau grafikus. Taigi n kvadratu. Pramogos. Daug blogiau nei n kaip matome, ir daug, daug blogiau, nei žurnalo 2n. Ir tada jūs taip pat patekti į žurnalo rąstų. Ir jūs imtis 124, gausite į kaip žurnalo žvaigždė, kuri yra kaip crazy. Taigi, jei jus domina, lookup žurnalas žvaigždė. Tai koks įdomus. Taigi, mes turime šį puikų grafiką. Tik metas, tai nuostabus schema turi Jūsų įpusėjusi, nes mes ilgai jums užduoti šiuos plonina. Taigi vos metas, turite šį savo laikotarpio vidurio savo gražiu Cheat sheet ten. Taigi mes tiesiog pažvelgė burbulas rūšiuoti. Blogiausiu atveju, n kvadratu, geriausiu atveju, n. Ir mes ketiname pažvelgti į kitus. 

Ir, kaip matote, tik vienas, kad tikrai gerai yra sujungti rūšiuoti, kuri mes gauti į, kodėl. Taigi, mes ketiname eiti Kitas vienas here-- pasirinkimas rūšiuoti. Ar kas nors prisimena, kaip pasirinkimas rūšiuoti dirbo? Eiti į jį. 

STUDENTŲ: Iš esmės pereiti Kad ir sukurti naują sąrašą. Ir kaip jūs pateikėte elementai į, įdėti juos į tinkamą vietą į naują sąrašą. 

Instruktorius: Taigi, kad garsai daugiau kaip įterpimo rūšiuoti. Bet jūs tikrai arti. Jie labai panašūs. Net man juos sumaišyti kartais. Prieš šioje dalyje Aš, pavyzdžiui, palaukti. Gerai. Taigi, ką jūs norite padaryti, tai pasirinkimas rūšiuoti, Taip galite galvoti apie tai ir tai, kaip Aš įsitikinkite, kad aš stengiuosi ne gauti juos sumaišyti, tai eina per ir jis atrenka Mažiausiai ir kelia, kad jūsų sąrašo pradžioje. Ji apsikeitimo su tos pirmosios vietoje. Jie iš tikrųjų turi būti pavyzdžiu man. Nuostabus. Taigi tiesiog būdas galvoti apie it-- atrankos rūšiuoti, pasirinkite mažiausią vertę. Ir mes ketiname paleisti kaip pavyzdys kad manau, padės, nes Manau vizualizacijomis visada padeda. Taigi, mes pradėti su kažkuo kad yra visiškai nerūšiuotas. Raudona bus nerūšiuotos, žalia bus surūšiuoti. Tai bus visų prasmės per sekundę. 

Taigi mes pereiti ir mes pakartoti nuo pradžios iki pabaigos. Ir mes sakome, gerai, 2 yra mūsų mažiausias skaičius. Taigi, mes ketiname imtis 2 ir mes ketiname norėdami perkelti ją į mūsų aukštos klasės priekyje nes tai Mažiausiai, ką turime. Štai, ką šis čia veikia. Tai tiesiog vyksta apsikeitimo šių dviejų. Taigi dabar mes turime sutvarkyti dalis ir nerūšiuotus dalis. Ir kas gera prisiminti apie atrankos rūšiuoti yra mes tik pasirinkus nuo nerūšiuotų dalis. 

Rūšiuota dalis tiesiog palikti ramybėje. Mm-hm? 

STUDENTŲ: Kaip ji žino, kas yra mažiausia be lyginant jį kiekvienam kitos vertės masyvo. Instruktorius: Ji palyginti. Mums patinka praleisti jį. Tai tik Bendru. Taip. Kai mes rašome kodą aš kad jums bus labiau patenkinti. Bet jums laikyti tai pirmasis elementas, kaip mažiausias. Jei lygintume ir jūs pasakyti, GERAI, tai mažesnė? Taip. Laikykite jį. Štai jis mažesnis? Ne? 

Tai jūsų mažiausias, perleisti jį į savo vertę. Ir jums bus daug laimingesni kai mes einame per kodą. Taigi mes pereiti, mes sukeisti, todėl tada mes pažvelgti į šią nerūšiuotų dalį. Taigi mes ketiname pasirinkti trys iš. Mes ketiname įdėti ją ne Mūsų išrūšiuotų dalį pabaiga. Ir mes tik ketina toliau daryti kad tai daro ir tai, kad. Taigi tai yra mūsų rūšies Pseudocode čia. Mes kodą jį čia per sekundę. Bet tiesiog kažkas vaikščioti per aukšto lygio. Jūs ketinate eiti iš i lygu 0 iki n minus 2. Štai dar vienas optimizavimas. Nesijaudinkite, per daug apie ją. Taigi, kaip jūs kalbėjo. Kaip Jokūbas sako, kaip mes sekti, kas mūsų minimalus yra? Kaip mes žinome,? Mes turime palyginti viskas mūsų sąraše. 

Taigi minimalus lygus i. Tai tiesiog pasakyti šiuo atveju mūsų mažiausios vertės indeksas. Taigi viskas vyksta paeiliui per ir jis eina iš j yra lygus i plius 1. Taigi, mes jau žinome, kad kad mūsų pirmasis elementas. Mums nereikia lyginti ją sau. Taigi, mes pradedame lyginti ją į kitą tas, kuris yra, kodėl ji yra i plius 1 iki n minus 1, tai yra pabaigoje ten masyvo. Ir mes pasakėme, jei masyvas ne j yra mažiau kaip masyvo min tada mes perleisti kur Mūsų minimalus indeksai yra. 

Ir jei min nėra lygus i, kaip į kur buvome atgal čia. Taigi norėčiau, kai mes pirmą padarė šį vieną. Šiuo atveju, ji būtų pradėti nulis, tai galų gale yra du. Taigi min nebūtų lygus i galo. Kuri leidžia mums žinoti, kad turime apsikeitimo. Jaučiu, kaip konkretų pavyzdį padės daug daugiau nei tai. Taigi aš taisykles Šis su jumis vaikinai dabar ir aš manau, kad tai bus geriau. 

Rūšys linkę dirbti tą kelią, kad tai dažnai geriau tiesiog juos matyti. Taigi, ką mes norime padaryti, tai mes pirmą kartą noriu mažiausias elementas į jos padėtį masyvo. Būtent tai, ko Jokūbas sako. Jums reikia laikyti, kad kažkaip. Taigi, mes ketiname pradėti čia Iteracja per masyvo. Mes ketiname pasakyti, kad tai mūsų Pirmoji tiesiog pradėti. Taigi, mes ketiname turėti int Mažiausias yra lygus masyvo ne i. 

Taigi vienas dalykas, kad pranešimas, kiekvienas laikas tai kilpa vykdo, mes pradedame dar vieną žingsnį į priekį. Kai mes pradėjome mes pažvelgti į šį vieną. Kitą kartą mes kartoti, kad, mes pradedant šį vieną ir paskiriant ją mūsų mažiausias dydis. Taigi, tai labai panaši į burbulų rūšiuoti kur mes žinome, kad po vienu pravažiavimu, tai paskutinis elementas yra rūšiuojama. Su atrankos rūšiuoti, tai kaip tik priešingas. 

Kiekviename perdavimą, mes žinome, kad Pirmasis yra rūšiuojami. Po antrojo kalibre, Antrasis bus surūšiuoti. Ir kaip matėte su skaidrių pavyzdžiai, mūsų rūšiuojami dalis tiesiog auga. Taigi nustatant mūsų mažiausias į masyvų i visa tai daro yra Traukiasi kas mes ieškome tiek kaip siekiant sumažinti skaičių lyginimų mes. Ar tai prasminga visiems? Ar jums reikia manęs paleisti per, kad vėl lėčiau arba kitais žodžiais? Man malonu. Gerai. 

Taigi mes saugoti vertė šiuo metu, bet mes taip pat norime, kad išsaugotumėte indeksas. Taigi mes ketiname saugoti pozicija iš mažiausių vienas, kuris yra tik ketina būti i. Taigi dabar Jokūbas, yra įvykdyta. Mes turime ką saugomi. Ir dabar mes turime pažvelgti per nerūšiuotus dalis masyvo. Taigi šiuo atveju toks būtų mūsų nerūšiuotas. Tai i. Gerai. 

Taigi, ką mes ketiname daryti, bus kilpa. Kiekvieną kartą, kai jums reikia kartoti, kad masyvo jūsų protas gali eiti į kilpa. Dar kurį int k equals-- ką mes galvojame k ketina prilygti pradėti? Tai yra tai, ką mes nustatyti kaip mūsų mažiausias vertė, ir mes norime jį palyginti. Ką mes norime jį palyginti su? Ji ketina būti tai šalia vienas, tiesa? Taigi, mes norime k inicializuoti į i plius 1 paleisti. 

Ir mes norime k šiuo atveju mes jau dydis saugomi čia, todėl galime tiesiog naudokite dydį. Dydis yra masyvo dydis. Ir mes tik norime atnaujinti k vieno kaskart. Cool. Taigi dabar mes turime rasti Mažiausias elementas čia. Taigi, jei mes kartoti, kad mes noriu pasakyti, jei masyvas prie k yra mažesnis nei mūsų mažiausias value-- tai kur mes iš tikrųjų sekti kas mažiausia here-- tada mes norime perleisti kas mūsų mažiausias dydis yra. 

Tai reiškia, kad, oi, mes Iteracja per čia. Nepriklausomai vertė yra čia ne mūsų mažiausias dalykas. Mes nenorime, kad. Norime perleisti jį. Taigi, jei mes perskirstymo tai, ką daryti, manote, gali būti šio kodekso čia? Norime perleisti Mažiausias ir pozicija. Taigi, kas yra mažiausias šiuo metu? STUDENTŲ: Array k. Instruktorius: Array k. Ir kas yra pozicijoje dabar? Kokia indeksai mūsų mažiausias vertė? Tai tiesiog k. Taigi masyvo k, k, jie atitikmenys. Taigi mes norėjome perskirstyti, kad. Ir tada, kai mes rasti mūsų mažiausias, būdamas tai pabaigoje kilpa Čia mes nustatėme, ką mūsų mažiausias vertė yra, todėl mes tiesiog sukeisti. Šiuo atveju, pavyzdžiui, pasakyti DUK mažiausia reikšmė yra čia. Tai mūsų mažiausią reikšmę. 

Mes tik norime sukeisti čia, kuris yra kas, kad swap funkcija apačioje darė, kurią mes ką tik rašė savo kartu pora min. Todėl ji turėtų atrodyti pažįstamas. Ir tada jis tiesiog pakartoti per, kol jis pasiekia visą kelią iki galo, o tai reiškia, kad jūs nulis elementus, kurie yra nerūšiuotas ir visa kita buvo rūšiuojami. Prasmės? Mažai konkrečiau? Kodas padėti? 

STUDENTŲ: Dėl dydžio, jums niekada tikrai nustatyti, ar jį pakeisti, kaip tai žinoti? 

Instruktorius: Taigi vienas dalykas pastebėsite čia yra int dydis. Taigi mes sakydamas šiame sort-- rūšiuoti yra ši funkcija case-- tai pasirinkimas rūšiuoti, tai praėjo su funkcija. Taigi, jei ji buvo neišlaikė į, jūs padaryti kažką kaip su masyvo ilgis ar jums būtų pakartoti per rasti ilgį. Bet todėl, kad jis praėjo į, mes galime tik jį naudoti. Jūs tiesiog manyti, kad vartotojas padovanojo tau galiojantį dydį iš tikrųjų atstovauja Jūsų masyvo dydis. Cool? 

Jei jus vaikinai jokių problemų su jų ar nori daugiau praktikos kodavimo rūšių savo, jums reikia eiti į study.cs50. Tai įrankis. Jie turi šaškę, kad Jūs iš tikrųjų galite rašyti. Jie Pseudocode. Jie turi daugiau vaizdo įrašų ir skaidres įskaitant tuos, aš naudoju čia. Taigi, jei jūs vis dar jaučiasi tiek neaiškus, pabandykite, kad iš. Kaip visada, ateis pasikalbėti su manimi, taip pat. Klausimas? 

STUDENTŲ: Ar tu sakai, dydis iš anksto numatytam? Instruktorius: Taip. Dydis anksčiau apibrėžta iki čia funkciniam deklaracijoje. Taigi jūs prielaidą, kad jis buvo priimtas vartotojas, ir už Paprastumo dėlei, mes ketiname daryti prielaidą, kad vartotojas davė mums tinkamą dydį. Cool. Štai atranka rūšiuoti. Vaikinai, aš žinau, mes tiek daug išmokti šiandien. Tai tankus duomenys skyriuje. Taigi su tuo, mes ketiname eiti į įterpimo rūšiuoti. 

Gerai. Taigi, prieš tai mes turime padaryti, mūsų runtime analizė čia. Taigi geriausiu atveju, suteikta, nes aš jums parodė Aš jau lentelė rūšies davė jai toli. Bet geriausias atvejis runtime, ką mes galvojame? Viskas rūšiuojami. N kvadratu. Kiekvienas turi paaiškinimą kodėl jūs manote? 

STUDENTŲ: Jūs lyginate through-- Instruktorius: Teisė. Jūs lyginate per. Kiekviename iteracijos, nors mes mažėjančio tai vieną, Jūs vis dar ieškoti per viskas rasti mažiausias. Taigi net jei jūsų mažiausias, vertė yra čia pradžioje, Jūs vis dar lyginant prieš visa kita įsitikinkite, kad jis yra mažiausias dalykas. Taigi jūs galų gale eina per maždaug n kvadrato kartus. Gerai. Ir kas blogiausiu atveju? Taip pat n kvadratu, nes jūs ketinate reikia daryti, kad ta pačia tvarka. Taigi šiuo atveju, atrankos rūšiuoti turi kažką kad mes taip pat vadiname tikimasi runtime. Taigi kiti, mes tik žinoti viršutinė ir apatinė ribos. Priklausomai nuo to, kaip kvailai mūsų sąrašas arba kaip nerūšiuotos tai, jie skiriasi n ar n kvadrato. Mes nežinome. 

Bet todėl, kad pasirinkimas rūšiuoti turi pats Blogiausia ir geriausia atveju, kad sako, kad nesvarbu, kokio tipo įėjimo mes turėti, ar tai visiškai rūšiuojami arba visiškai atgal rūšiuojamos, tai ketina imtis pat laiko. Taigi šiuo atveju, jei jūs prisiminti iš mūsų stalo, ji iš tikrųjų turėjo tokią vertę, kuri šios dvi rūšys neturi, kuris yra laukiamas runtime. Taigi mes žinome, kad, kai mes paleisti atrankos rūšiuoti, tai garantuoja, kad paleisti n kvadrato laiką. Nėra kintamumas yra. Tai tiesiog buvo tikėtasi. Ir vėl, jei norite sužinoti daugiau, imtis CS 124 pavasarį. Gerai. Mes matėme šį vieną. Cool. Taigi įterpimo rūšiuoti. Ir aš tikriausiai bus į Blaze per tai. Aš nenoriu, kad jūs, vaikinai kodą jį. Mes tiesiog vaikščioti per ją. Taigi įterpimo rūšiuoti yra natūra panašių į pasirinkimo rūšiuoti tuo, kad mes turime tiek nerūšiuotas ir rūšiuoti dalį masyvo. 

Bet kas skiriasi, kad kaip mes pereiti per vieną, mes tiesiog kad ir kiek yra šalia mūsų nerūšiuotas, ir teisingai rūšiuoti į mūsų išrūšiuotų masyvo. Tai bus daugiau prasmės, pavyzdys. Taigi viskas prasideda nerūšiuotas, Kaip ir su atrankos rūšiuoti. Ir mes ketiname rūšiuoti tai Didėjančia tvarka kaip mes buvome. Taigi mūsų pirmojo perdavimo mes žengti pirmą vertę ir sakome, gerai, jūs esate dabar vieni patys sąrašą. 

Nes esate sąrašą patys, jums bus rūšiuojami. Sveikiname yra Pirmasis elementas šiame masyve. Jūs jau Surikiuota visa savo. Taigi dabar mes turime sutvarkyti ir nerūšiuotus masyvas. Taigi, dabar mes pirmiausia. Kas atsitinka, tarp čia ir čia yra tai, kad mes sakome, Gerai, kad mes ketiname pažvelgti Pirmoji vertybė mūsų nerūšiuotų masyvo ir mes ketiname įvesti ją į savo teisinga vieta išrūšiuotų masyvo. 

Taigi, ką mes darome, yra mes 5 ir mes sakome, gerai, 5 yra didesnis nei 3, todėl mes tiesiog įdėkite jį į dešinę į šią teisę. Mes gerai. Taigi mes einame į mūsų kitą. Ir mes 2. Mes sakome, gerai, 2 mažiau nei 3, todėl mes žinome, kad jo turi būti ne frontas mūsų sąraše dabar. Taigi, ką mes darome, yra mūsų numušti 3 ir 5 ir mes judėti 2 į tą pirmą lizdą. Taigi mes tiesiog įdėti jį į teisinga vieta turėtų būti. 

Tada mes pažvelgti į mūsų Kitas vienas, ir mes sakome 6. GERAI, yra didesnis kaip 6 viskas mūsų išrūšiuotų masyvo, todėl mes tiesiog pažymėti jį iki galo. Ir tada mes pažvelgti 4. 4 yra mažesnis nei 6, tai mažiau nei 5, bet tai didesnės negu 3. Taigi mes tiesiog įdėkite jį į dešinę tarp 3 ir 5 vidurinės. Taigi, norint, kad mažai tiek daugiau betono, čia yra tipo idėja, kas atsitiko. Taigi už kiekvieną nerūšiuotų elementą, mes nustatyti, kur iš išrūšiuotų dalis ji yra. 

Taigi atsižvelgiant į tai, kad rūšiuotus ir nerūšiuotus, mes turime išanalizuoti per ir figūra iš kur jis telpa į rūšiuotų masyvo. Ir mes jį įterpti perkeliant elementai į dešinę nuo jos žemyn. Ir tada mes tiesiog laikyti Iteracja per kol mes turi visiškai surūšiuoti sąrašą kur nerūšiuotas dabar nulis ir rūšiuoti užima visuma mūsų sąraše. Taigi, dar kartą, kad viskas dar konkretesnis, turime Pseudocode. 

Taigi, iš esmės, nes aš tai lygus 0 iki n minus 1, tai tik mūsų masyvas ilgis. Mes turime tam tikrą elementą, kuris yra lygus pirmasis masyvas arba pirmieji indeksai. Mes nustatėme j lygią. Taigi, nors j yra didesnis nei nulis ir masyvas, j minus 1 yra didesnis nei elementas, taigi visi tai daro yra užtikrinti, kad Jūsų j tikrai atstovauja nerūšiuotus dalis masyvo. 

Taigi, nors vis dar yra dalykų, rūšiuoti ir j minus vienas is-- ką yra elementas jai? J nebuvo apibrėžta čia. Tai tipo erzina. Gerai. Anyways. Taigi j minus 1, jūs Tikrindami prieš jį elementas. Jūs sakote, gerai, yra elementas prieš kur aš am-- tegul iš tikrųjų tai atkreipia dėmesį. Taigi galime sakyti, tai yra kaip mūsų antrąjį perdavimą. Taigi aš bus lygus 1, kuris yra čia. 

Taigi aš bus lygus 1. Tai būtų 2, 4, 5, 6, 7. Gerai. Taigi, mūsų elementas šioje byloje bus lygus 4. Ir mes kai j, kad yra bus lygus 1. Oi, j yra mažėjančio. Štai ką ji yra. Taigi j yra lygus i, todėl, kas tai yra pasakyti, kad, kaip mes judėti į priekį, mes tiesiog įsitikinkite kad mes ne per indeksavimo šį kelią, kai mes bandome įterpti daiktus į mūsų surūšiuoti sąrašą. 

Taigi, kai j yra lygus 1 ir šiuo atveju masyvas j minus one-- todėl masyvas j minus 1 yra 2 šio case-- jei tai didesnė negu elementų, tada visa tai daro Stumdomi dalykų žemyn. Taigi, šiuo atveju, masyvas j minus vienas būtų masyvas nulis, kuris yra 2. 2 yra ne didesnis nei 4, todėl šis nevykdo. Taigi perėjimas nepereis žemyn. Kas tai čia yra tik perkelti savo rūšiuotą masyvas žemyn. Šiuo atveju, iš tikrųjų, mes gali do-- padarykime šį 3. Taigi, jei mes vaikščioti per su Šiame pavyzdyje mes dabar čia. Išrūšiuojama. Tai nerūšiuotas. Cool? Taigi, aš, yra lygus 2, todėl mūsų elementas yra lygus 3. Ir mūsų j yra lygus 2. Taigi, mes pažvelgti pro ir mes pasakyti, GERAI, yra masyvas j minus vienas didesnė negu elemento kad mes ieškome? Ir atsakymas yra "taip", ar ne? 4 yra didesnis nei 3 ir j yra 2, todėl šis kodas vykdo. 

Taigi, dabar, ką mes darome masyvą ne 2, todėl čia mes apsikeitimo. Taigi mes tiesiog pasakyti, GERAI, masyvas ne 2 dabar bus 3. Ir j ketina prilygti j minus 1, tai yra 1. Kad siaubinga, bet vaikinai gaunate idėja. J yra dabar lygus 1. Ir masyvas j tiesiog bus lygus mūsų elementas, kuris buvo 4. Aš ištrinti kažką aš ne turėti ar miswrote kažkas, bet jus vaikinai gaunate idėja. 

Tai judėti n. Ir tada, jei tai būtų, tai būtų kilpa kartą ir jis pasakytų, OK, j yra 1 metu. Ir masyvas j minus 1 yra dabar 2. Ar 2 mažiau nei mūsų elementą? Ne? Tai reiškia, kad mes įterpti šį elementą teisinga vietoje mūsų išrūšiuotų masyvo. Tada mes galime priimti tai ir sakome, Gerai, mūsų Rūšiuota masyvas yra čia. Ir tai užtruktų šį numerį 6 ir būti kaip, gerai, yra 6 mažiau nei šis skaičius? Ne? Cool. Mes gerai. 

Dar kartą. Mes sakome 7. Yra 7 mažiau nei pabaigos Mūsų išrūšiuotų masyvo? Ne. Taigi mes puikiai. Taigi tai būtų rūšiuojamos. Iš esmės visa tai daro jis sako, imk pirmasis elementas Jūsų nerūšiuotas masyvas, išsiaiškinti, kur jis eina savo išrūšiuotų masyvo. Ir tai tik rūpinasi apsikeitimo sandorių daryti. Jūs iš esmės tiesiog Swapping kol jis yra reikiamoje vietoje. Vaizdo vaizdą, kad jūs juda viską nustato tai, kad. 

Taigi, tai, kaip puse burbulo rūšiuoti esque. Patikrinkite tyrimą 50. Aš labai rekomenduoju bando koduoti tai savo. Jei turite kokių nors klausimų ar norite pamatyti pavyzdį kodą įterpties rūšiuoti, Please let me know. Aš visada aplink. Taigi blogiausiu atveju runtime ir geriausio atvejo runtime. Kaip jums vaikinas pamatė nuo stalo aš jau jums parodė, tai tiek n kvadrato ir n. 

Tiek rūšies nenukryptų, ką mes kalbėjome apie su mūsų ankstesnių rūšių, blogiausia atvejis runtime yra tai, kad jei Tai visiškai Nerūšiuotos, turime palyginti visus šių n kartų. Mes apskritai daug palyginimų nes jei tai vyksta atvirkštine eilės tvarka, mes ketiname pasakyti, GERAI, tai yra tas pats, tai yra gerai, ir tai vienas bus turi būti lyginami nuo pirmojo vieno iki būti perkeltas atgal. Ir kaip mes gauti į galine, turime palyginti, palyginti ir palyginti su viskuo. 

Todėl galų gale buvo maždaug n kvadratu. Jei ji teisinga, tada jūs pasakyti, GERAI, 2, jūs gerai. 3, jūs palyginti su 2. Jūs gerai. 4, tiesiog palyginti su uodega. Jūs gerai. 6, palyginti su uodega, tu gerai. Taigi už kiekvieną vietoje, jei tai jau rūšiuojami, kad darote vieną palyginimą. Taigi tai tiesiog n. Ir todėl, kad mes turime geriausiu atveju runtime n ir blogiausio atvejo runtime n kvadrato, mes neturime laukiamą runtime. 

Tai tiesiog priklauso nuo chaosas mūsų sąraše ten. Ir vėl, kita grafikas ir kita lentelė. Taigi skirtumai tarp rūšių. Aš tik ketina vėjas per, aš jaustis kaip mes kalbėjome plačiai apie tai, kaip jie visų tipų iš skirtis ir susieti kartu. Taigi Merge sort yra paskutinis Aš pagimdė jums, vaikinai su. Mes turime gana spalvingas vaizdas. Taigi sujungti rūšiuoti yra grįžtamojo algoritmas. Taigi jūs žinote, ką grįžtamojo funkcija? 

Kiekvienas nori pasakyti? Jūs norite išbandyti? Taigi grįžtamojo funkcija yra tik funkcija, kuri vadina save. Taigi, jei jus vaikinai žino su Fibonačio seka, Štai laikoma rekursywny nes vartojate praėjusius dvejus ir įtraukti juos kartu gauti savo kitą. Taigi grįžtamojo aš visada manau, Rekursija kaip kaip spiralė todėl jūs, kaip spirale žemyn į jį. Bet tai tik funkcija kad save vadina. 

Ir, iš tikrųjų, tikrai greitai aš gali parodyti jums, ką tai atrodo. Taigi grįžtamojo čia jei pažvelgsime, tai grįžtamojo būdas Apibendrinant per masyvą. Taigi visi tai mes darome, yra turime sumą funkciją suma, kad užtrunka dydį ir masyvą. Ir, jei pastebėsite, dydis mažinimą pagal vieną kiekvieną kartą. Ir visa tai daro, yra jei x yra lygi zero-- tad jei masyvo dydis yra lygus zero-- jis grįžta prie nulio. 

Priešingu atveju jis apibendrina tai paskutinis elementas masyve, ir tada užima sumą masyvo poilsio. Taigi tai tiesiog reikia suskirstyti į mažesnius ir mažesnius problemų. Trumpai tariant, rekursija, funkcija, kuri vadina save. Jei tai viskas, ką gavau iš to, kad tai, ką rekursywny funkcija. Pavartojus 51, jūs gausite labai, labai patogu su rekursijos. Tai tikrai cool. Buvo logiška ne kaip 03:00 Vienos nakties out. Ir man buvo kaip, kodėl aš niekada naudoti? 

Taigi merge rūšiuoti, iš esmės ką jis ketina padaryti, tai jis ketina ją padalyti ir sumušė jį žemyn, kol jis tiesiog pavieniai elementai. Pavieniai elementai lengvai rūšiuoti. Mes matome, kad. Jei turite vieną elementą, tai jau laikomas Rūšiuota. Taigi ant n elementų įvedimo, jei n yra mažiau nei 2, tiesiog grįžti, nes tuo būdu tai arba 0 arba 1, kaip mes matėme. Tie laikomi rūšiuotas elementai. 

Kitaip sulaužyti per pusę. Rūšiuoti pirmąjį pusmetį, rūšiuoti sekundę pusė, ir tada sujungti juos kartu. Kodėl jis vadinamas merge sort. Taigi, mes turime čia mes rūšiuoti juos. Taigi mes nuolat turėti juos iki masyvo dydis yra 1. Taigi, kai jis 1, mes tiesiog grįžti nes tai yra surūšiuoti masyvas, ir tai yra surūšiuoti masyvas, o tai Rūšiuota masyvas, mes visi rūšiuojami. Taigi, ką mes darome, yra mūsų pradėti sujungia juos kartu. 

Taigi, kaip jūs galite galvoti apie sujungimas yra tiesiog pašalinti mažesni numeris kiekvieno sub masyvų ir tiesiog pridėti jį prie susiformavusio masyvo. Taigi, jei jums atrodo čia, kai mes turime Šie rinkiniai mes turime 4, 6 ir 1. Kai mes norime sujungti jų mes žiūrime į šiuos du pirmuosius ir sakome, gerai, 1 yra mažesnis, jis eina į priekį. 4 ir 6, nėra nieko palyginti jis, tiesiog pažymėti jį iki galo. 

Kai mes sujungti šias dvi, mes tiesiog imtis mažesnioji iš šių dviejų, todėl 1. Ir dabar mes mažesnis iš šių dviejų, SO2. Mažesnis iš šių dviejų, 3. Mažesnis iš šių dviejų, 4, 5, 6. Taigi jūs tiesiog traukiant juos. Ir todėl, kad jie jau anksčiau rūšiuojamos, jums tereikia vieną palyginimas kiekvieną kartą. Taigi daugiau kodo čia, tiesiog atstovavimas. Taigi galite pradėti vidurį ir Jūs tarsi kairė ir dešinė ir tada jums tiesiog sujungti juos. 

Ir mes neturime kodą už sulieti čia. Bet vėl gi, jei jūs einate į studijuoti 50, tai bus ten. Kitaip ateiti pasikalbėti su manimi jei jūs vis dar painiojama. Toks kietas dalykas čia yra tai, kad geriausias atvejis, blogiausiu atveju, ir tikimasi, Runtime visi esame žurnalas n, kuris yra daug geriau, nei mes matyti, kad mūsų dvasia poilsio. Mes matėme n kvadratu ir tai, ką mes iš tikrųjų gauti čia n log n, kuris yra puikus. 

Pažvelkite, kiek daug geriau, kad yra. Toks gražus kreivė. Taigi yra daug veiksmingiau. Jei kada nors gali, naudojimas sujungti rūšiuoti. Tai bus jums sutaupyti laiko. Ir vėl, kaip mes sakėme, jei esate šiame apatinėje regione, tai nereiškia, kad kad daug skirtumų. Jūs gausite iki tūkstančių ir tūkstančiai įėjimai, jūs tikrai norite efektyvesnis algoritmas. Ir vėl, mūsų mielas lentelėje visi rūšių, kad jums, vaikinai šiandien išmokote. 

Taigi aš žinau, tai buvo tankus dieną. Tai ne visada yra siekiant padėti jums su jūsų pset. Bet aš tik noriu padaryti atsisakymas kad skyriuje yra ne tik apie psets. Visa tai medžiaga yra teisingas žaidimas jūsų kontrolinius. Ir taip pat, jei jūs darote tęsti su CS, tai tikrai svarbu pagrindai kad jums reikės žinoti. Taigi keletą dienų bus šiek tiek daugiau pset pagalba, bet kelios savaitės bus daug tikrasis turinys kad gali atrodyti super naudinga jums dabar, bet pažadu, jeigu jūs ir toliau dėl bus labai, labai naudinga. 

Štai jį skyriuje. Žemyn į vielos. Aš tai padariau per vieną minutę. Bet ten jūs einate. Ir aš turiu spurgos ar saldainiai. Ar kas nors alergiškas nieko, beje? Kiaušiniai ir pieno. Taigi spurgos ne? Gerai. Gerai. Šokoladas ne? Starburst. Pliūpsniais yra geros. Gerai. Mes ketiname turėti Starburst kitą savaitę tada. Štai ką aš gausiu. Jūs vaikinai turi labai savaitės. Skaitykite savo spec. 

Leiskite man žinoti, jei turite kokių nors klausimų. Pset dvi rūšys turėtų būti iš jums ketvirtadienis. Jei turite kokių nors klausimų, apie tai, kaip aš surūšiuoti kažką arba kodėl aš surūšiuoti kažką taip, kaip man nebuvo, rašykite man, atėjo pasikalbėti su manimi. Aš šiek tiek kvailai tai savaitę, bet aš pažadu Aš vis dar atsakyti per 24 valandas. Taigi turite puikią savaitę, kiekvieną. Sėkmės jūsų pset.