>> [Muzikos grojimo]
>> ANDI Peng: Sveiki skirsnio 3 savaitės.
Ačiū, vaikinai, nes visi ateina į šį ankstesnį pradžios laiką šiandien.
Mes turime gražus, šiek tiek intymus grupė šiandien.
Taigi, tikiuosi, mes susisieksime su apdaila, galbūt, per anksti,
šiek tiek anksti šiandien.
Taigi greitai, tik kai skelbimai darbotvarkę ir šiandien.
Prieš pradėdami, mes vyksta tiesiog eiti per
kai trumpas logistikos klausimai, pset klausimai, Zdać, dalykų, pavyzdžiui, kad.
Ir tada mes neria tiesiai.
Mes naudosime debugerem vadinamas GDB į pradėti nuvainikuoti mūsų kodą, kurį Davidas
paaiškinta paskaitą kitą dieną.
Mes eiti per keturių tipų rūšių.
Mes eiti per juos gana greitai nes jie gana intensyvus.
Bet žinoti, kad visi skaidres ir kodo yra visada internete.
Taigi nedvejodami, jūsų perskaitymas, kad grįžti atgal ir pažvelgti, kad išvaizdą.
>> Mes eiti per asimptotinio žymėjimas, kuris
yra tik išgalvotas būdas sakydamas "runtimes"
kur mes turime didelį O, kuris Davidas paaiškinta paskaita.
Ir mes taip pat turime Omega, kuris yra apatinė Runtime.
Ir mes kalbame šiek tiek daugiau nuodugniai apie tai, kaip šios darbus.
Ir galiausiai, mes eiti per dvejetainis paieškos, nes daug iš jūsų, kurie jau
pažiūrėjau jūsų psets tikriausiai žinote, kad tai yra klausimas, kuris yra jūsų pset.
Taigi jūs visi būti laimingi kad mes padengti tai šiandien.
>> Ir galiausiai, už savo skyriuje atsiliepimai, aš iš tikrųjų
paliktas apie 15 minučių esant pabaiga tiesiog eiti per
logistika pset3, kokių nors klausimų, gal orientavimo tiek, jei norite,
prieš pradedant programavimą.
Taigi pabandykime gauti per medžiaga gana greitai.
Ir tada mes galime praleisti šiek tiek laiko atsižvelgiant daugiau klausimų dėl pset.
GERAI.
>> Greitai, todėl tik nedaugelis skelbimai kol mes pradėti šiandien.
Pirma, kviečiame priėmimo jis per du savo psets.
Aš paėmė pažvelgti your-- taip, tegul gauti plojimų, kad vienas.
Tiesą sakant, aš buvau tikrai, tikrai sužavėtas.
Aš rūšiuojami pirmąjį pset jums vaikinai Praėjusią savaitę ir vaikinai padarė neįtikėtinas.
>> Stilius buvo taško Be to keletą pastabų.
Įsitikinkite, kad jūs visada komentuodamas savo kodą.
Bet tavo psets buvo ant taško.
Ir keep it up.
Ir tai gerai, kad į rūšiuotojas matyti, kad vaikinai yra išleisti
AS daug pastangų savo stilių ir jūsų dizainas kodą
kad mes norėtume jums pamatyti.
Taigi, aš perdavę savo dėkingumą už etatus poilsio.
>> Tačiau yra Keletas aptarime klausimai
Aš tik noriu eiti per tą būtų ir mano gyvenimą
ir iš kitos daug Tas "gyvena šiek tiek lengviau.
Pirma, aš pastebėjau, tai praeitis week-- kaip daugelis iš jūsų
jau veikia check50 nuo Jūsų kodas prieš jums pateikti?
GERAI.
Taigi kiekvienas turėtų daryti check50, because-- secret-- mes iš tikrųjų
paleisti check50, kaip dalis mūsų teisingumą scenarijus išbandyti savo kodą.
Taigi, jei jūsų kodas yra nepakankamai check50, greičiausiai,
tai tikriausiai nesugeba mūsų čekį, taip pat.
Kartais jūs vaikinai turi teisingus atsakymus.
Kaip, į gobšus, kai Jūs turite teisę numerius,
jūs tiesiog atspausdinti keletą papildomų dalykų.
Ir kad papildomų dalykų iš tikrųjų nepavyksta čekį,
nes kompiuteris nėra tikrai žinote, ką jis ieško.
Ir taip bus tiesiog paleisti per, pamatysite, kad jūsų produkcija nėra
atitiktų tai, ką mes tikimės atsakymą būti ir pažymėkite tai yra negerai.
>> Ir aš žinau, kad atsitiko kai kurie iš jūsų atvejais šią savaitę.
Taigi grįžau ir rankiniu būdu perrūšiuoti kiekvieno kodą.
Ateityje, nors, Prašome įsitikinkite,
kad jūs dirbate Tikrinti 50 savo kodą.
Kadangi tai tipo, skirto TA skausmo turėti grįžti ir rankiniu perrūšiuoti
kiekvienas pset už kiekvieną vieną, tiek praleistų atvejis.
Taigi aš ne kilimo jokių taškų.
Manau, nusiėmė gal vienas arba du už dizainą.
Ateityje, nors, jei jūs nesugeba check50,
Taškai bus imtasi ne už duomenų teisingumą.
>> Be to, psets yra dėl penktadienį vidurdienį.
Aš manau, kad yra septynių minučių vėlai atidėjimo laikotarpis, kad mes suteikiame jums.
Per Harvardo metu, jie gali būti septynias minutes vėlu viską.
Taigi čia Jeilio, mes taip pat laikytis, kad.
Tačiau gana daug, ne 12:07, Jei jūsų pset nėra,
jis bus pažymėtas kaip vėlai.
Ir taip, o tai yra pažymėta kaip pavėluotai, TA-- aš
vis dar bus klasifikavimo savo psets.
Taigi jūs vis dar pamatysite laipsnio atrodo.
Tačiau žinau, kad ne Semestro pabaigoje,
Visi vėlai psets bus tik automatiškai nulis kompiuteriu.
>> Mes tai dėl dviejų priežasčių.
Vienas iš jų, kartais mes gauname atleisti, kaip ir dekano pasiteisinimų,
vėliau, kad aš nežinau apie dar.
Taigi mes norėtume įsitikinti, mes klasifikavimo viskas tik tuo atveju, pavyzdžiui, aš
Trūksta dekano pasiteisinimas.
Ir antra, turėkite Protas, vis tiek galite
lašas vieną pset kad turi pilna apimtimi taškų.
Ir taip mes norėtume klasė visi jūsų psets tik
įsitikinkite, kad jūsų sritis s ten ir bandote juos.
Taigi, net jei ji per vėlai, jūs vis dar gauti kreditą apimtis kiekis, manau.
>> Taigi Istorijos moralas yra, kad Įsitikinkite, kad jūsų psets yra dėl laiko.
Ir jei jie nėra dėl laiko, žinau, kad tai nėra didelis.
Taip, kol aš judėti į priekį, ar kas nors turi Turite klausimų dėl pset atsiliepimus?
Taip.
>> Auditorija: Ar jums pasakyti, kad mes gali sumažėti vieną iš psets?
>> ANDI Peng: Taip.
Taigi ten devyni psets Bendras per semestro metu.
O jei turite apimtį points-- todėl taikymo sritis yra teisingas,
gana daug, jūs pasikėsinimą problema, jūs išleisti laiku,
jūs rodo, kad jūs parodė, jūs perskaitėte spec.
Tai gana daug galimybių.
Ir jei jūs vykdyti Taikymo sritis taškai, mes
gali sumažėti žemiausia vienas iš pilna apimtimi.
Taigi, kad savo pranašumą tai, kad užbaigti ir išbandyti kiekvieną pset.
>> Net upload-- jei nė vienas iš juos dirbti, įkelkite juos visus.
Ir tada mes tikimės galėti duoti jums kai kurie iš šių taškų atgal.
Saunus.
Visi kiti klausimai?
Didysis.
>> Antra, biuro hours-- nedaugelis Greitos pastabos apie darbo valandomis.
Taigi, pirmiausia, ateiti anksti savaitę.
Niekas kada nors ne Darbo valandos pirmadieniais.
Christabel atėjo Darbo valandos paskutinis naktį.
Taip, Christabel.
Ir ką mes turime biure valandos praėjusią naktį, Christabel?
>> Auditorija: Mes turėjome ledų.
>> ANDI Peng: Taigi tai tiesa, mes turėjome ledai ne darbo valandomis praėjusią naktį.
Nors aš negaliu pažadėti jums, kad mes turime ledų biure valandų
kiekvieną savaitę, ką aš galiu jums pažadu yra tai, kad ten bus žymiai
geriau studentui TP santykis.
Kaip teisėtas, tai kaip trijų iki vieno.
Kadangi, kontrastas, kad su Ketvirtadienis, jūs turite apie 150
tikrai pabrėžė vaikams ir ne ledų.
Ir tai tik ne produktyvus visiems.
Taigi Istorijos moralas yra, atvykti anksčiau kad darbo valandomis ir gerų dalykų
atsitiks.
>> Be to, būkite pasiruošę užduoti klausimus.
Tu žinai?
Nepriklausomai nuo to, TAS, aš manau, buvo sakydamas,
mes buvo gauti pora studentams kurie ateina į ketvirtadienį, kaip, 10:50
nėra perskaitęs spec yra kaip man padėti, padėk man.
Deja, tuo metu, ten ne per daug mes galime padaryti, siekiant padėti jums.
Taigi, prašome atvykti anksčiau šią savaitę.
Ateik anksti darbo valandomis.
Ateikite pasiruošę užduoti klausimus.
Įsitikinkite, kad jūs, kaip studentas, yra kur
reikia būti taip, kad Struktūra gali padėti jums kartu,
o tai, ką darbo valandomis turėtų būti skiriamos už.
>> Antra, todėl žinau, profesoriai patinka stebinti mus su testais.
Turėjau profesorius tuos kaip, Yo, beje,
prisiminti, kad laikotarpio vidurio jūs turite kitą pirmadienį.
Taip, aš nežinojau apie tą koliokviumui.
Taigi, aš ruošiuosi būti, kad TA kuri primena jums visiems, kad viktoriną
0--, nes, žinote, mes CS.
Dabar, kad mes padarėme masyvai, jūs gaunate kodėl tai Viktorina 0, o ne Quiz 1, eh?
GERAI.
Ech, man got some kad vienas chuckles.
GERAI.
>> Taigi Viktorina 0 bus spalis 14, jei Jūs esate pirmadienio trečiadienį skyriuje
iki spalio 15-jei esate antradienis-ketvirtadienis skyriuje.
Tai netaikoma Tiems iš jūsų, Harvarde
who-- Manau, kad jūs visi būsite atsižvelgiant jūsų viktorinos ant 14.
>> Taigi, taip, kitą savaitę, jei Davidas, į paskaitą, eina,
Taip, taip, apie tai viktorina kitą savaitę, jūs visi
nebus šokiruotas, nes atėjote į skyrių
ir jūs žinote, kad jūsų viktorina 0 yra per dvi savaites.
Ir mes turime peržiūrą sesijų ir viskas.
Taigi ne apie rūpesčius buvo išsigandęs, kad.
Turite klausimų before-- klausimų visais dėl logistikos klausimus,
rūšiavimo, darbo valandomis, sekcijos?
Taip.
>> Auditorija: Taigi viktorina yra bus paskaitos metu?
>> ANDI Peng: Taip.
Taigi viktorinoje, manau, yra 60 min skiriamų toje laiko tarpsnių
kad jūs tiesiog į paskaitą salėje.
Taigi jūs neturite ateiti apie, pavyzdžiui, atsitiktinės 7:00 PM.
Viskas gerai.
Taip.
Saunus.
>> Gerai.
Taigi mes ketiname pristatyti koncepciją jums
šią savaitę, kad Dovydas jau natūra iš palietė į paskaitą praeitą savaitę.
Tai vadinama GDB.
Ir kaip daugelis iš jūsų, o rašymo savo psets Žinoma,
pastebėjau didelį mygtuką, kad sako "Debug" ant jūsų IDE viršuje?
GERAI.
Taigi dabar mes iš tikrųjų gauti iškasti klausimą, ką mygtuką paslaptis iš tikrųjų
veikia.
Ir aš jums garantuoti, tai yra gražus, gražus dalykas.
>> Taigi iki šiol, manau, ten buvo du dalykai
studentai jau paprastai daro, kai derinate psets.
Vienas iš jų, jie arba pridėti printf () - todėl kiekvienas keletą eilučių,
jie įtraukti į printf () - oh, kas yra šis kintamasis?
Oi, kas tai yra kintamasis now-- ir jūs rūšies pamatyti progresavimą
Jūsų kodas, kaip ji veikia.
Arba antrasis metodas vaikai padaryti, tai kad jie tiesiog parašyti visa tai
ir tada eiti, kaip tai pabaigoje.
Tikimės, kad tai veikia.
Aš jums garantuoti, GDB yra geriau nei tiek iš šių metodų.
Taip.
Taigi tai bus jūsų naujas geriausias draugas.
Nes tai gražus dalykas kad vizualiai rodo ir
ką jūsų kodas daro specifiniuose taškuose
taip pat ką visus savo kintamieji yra vykdyti,
patinka tai, ką jų vertės yra, tuo konkrečiu klausimu.
Ir tokiu būdu, galite tikrai nustatyti ribines vertes jūsų kodu.
Jūs galite paleisti per eilutė po eilutės.
Ir GDB turės tik už Jums, rodomas jums,
ką visi jūsų kintamųjų yra, ką jie daro,
kas vyksta kodą.
Ir tokiu būdu,, tai taip daug lengviau pamatyti
kas vyksta vietoj printf-ING arba užrašyti savo pareiškimus.
>> Taigi mes padarysime Tokio pavyzdį vėliau.
Taigi, tai atrodo šiek tiek abstrakti.
Jokių rūpesčių, mes padarysime pavyzdžių.
Ir taip iš esmės, trijų didžiausių labiausiai naudojamas funkcijas, jums reikia į GDB
yra šalia, Step daugiau, ir žingsnis į mygtukus.
Aš ruošiuosi per galvą ten, iš tikrųjų, dabar.
>> Taigi galite vaikinai visi matome, kad ar man reikia padidinti šiek tiek?
Gale, jūs galite pamatyti, kad?
Ar turėčiau padidinti?
Tiesiog truputį?
Gerai.
Čia mes eiti.
GERAI.
>> Taigi turiu čia, mano įgyvendinimas godus.
Ir nors iš jūsų vaikinai daug rašė gobšus į while cikle form-- kad
yra visiškai priimtinas būdas tai padaryti it-- kitą būdą tai padaryti yra tiesiog
padalinti į Modulo.
Nes tada jūs galite turėti savo vertė ir tada turėti savo dalį.
Ir tada jūs galite tiesiog pridėti jį visi kartu.
Ar į ką darau logika čia prasmės visiems,
kol mes pradėti?
Maždaug?
Saunus.
Didysis.
Tai gana seksualus gabalas kodo, sakyčiau.
Kaip ir sakiau, Davidas, ir paskaitą, po kurio laiko,
jūs visi pradėsite matyti kodą kaip kažkas, kad gražus.
Ir kartais, kai pamatysite gražus kodas, tai toks nuostabus jausmas.
>> Taigi Tačiau, nors šis kodas yra labai gražus, jis neveikia tinkamai.
Taigi leiskite paleisti check50 apie tai.
Patikrinkite 50 20-- OOP.
2?
Ar tai pset2?
Taip.
Oi, pset1.
GERAI.
Taigi, mes paleisti check50.
>> Ir kaip jus vaikinai galite pamatyti čia tai jei yra atvejų pora.
Ir kai kurie iš jūsų, į Žinoma daro jūsų problema rinkinius,
jūs kaip, ah, kodėl ne darbo.
Kodėl jis dirba kai vertės, bet ne kiti?
Na, GDB ketina padėti jums išsiaiškinti kodėl tie įėjimai buvo neveikia.
>> GERAI.
Taigi pažiūrėkime, vienas iš patikrinimai buvau nepakankamai check50
buvo įvesties vertė 0,41.
Taigi teisingas atsakymas, kad Jums reikia gauti yra 4.
Bet vietoj to, ką aš spausdinti yra 3-N, kuri yra klaidingas.
Taigi tegul tiesiog paleisti rankiniu būdu, tiesiog įsitikinkite, kad check50 veikia.
Darom ./greedy.
Oi, aš turiu padaryti godus.
Čia mes eiti.
Dabar ./greedy.
>> Kiek skolingas?
Darom 0,41.
Ir yep, mes pamatyti čia kad jis išvedė 3
kai teisingas atsakymas, Iš tiesų, turėtų būti 4.
Taigi leiskite įvesti GDB ir pamatyti, kaip mes gali eiti apie nustatant šią problemą.
>> Taigi, pirmąją pakopą visada derinti savo kodą
yra nustatyti atskaitos tašką, arba vieta, kurioje galite
noriu kompiuterio arba debugeris pradėti ieškoti.
Taigi, jei jūs tikrai ne žinoti, ką jūsų problema yra,
Paprastai tipiškas dalykas, mes norime padaryti, tai nustatyti mūsų atskaitos tašką ne pagrindinis.
Taigi, jei jus vaikinai galite pamatyti raudoną mygtuką tiesiai ten,
Taip, tai buvo man nustatymo , ribinė pagrindiniam funkcija.
Aš spustelėkite, kad.
>> Ir tada aš galiu eiti į savo Debug mygtuką.
Aš smūgį mygtuką.
Leiskite padidinti atgal, jei aš galiu.
Čia mes eiti.
Taigi, mes turime čia, yra dešinėje skydelyje.
Aš atsiprašau, vaikinai gale, jums tikrai negali pamatyti tikrai gerai.
Bet iš esmės, visi ši teisė panelė daro
yra sekti tiek išryškino linija, kuri yra kodo eilutę
kad kompiuteris šiuo metu veikia, taip pat visi jūsų kintamųjų
žemyn čia.
>> Taigi, jūs turite centų monetos, N, visų deklaruotų skirtingų dalykų
Šiuo atveju.
Nesijaudinkite, nes mes ne iš tikrųjų inicializuoti juos visus kintamuosius dar.
Taigi jūsų kompiuteryje, jūsų Kompiuterių tik pamatyti,
oh, 32767 buvo paskutinis naudojamą funkciją tos atminties mano kompiuteryje.
Ir taip, kad ten centų metu.
Bet ne, kad kai jūs paleisti kodą, ji turėtų tapti inicializuoti.
>> Taigi eikime pro linija linija, kas vyksta čia.
GERAI.
Taigi čia yra trys mygtukai, kad aš tiesiog paaiškinti.
Jūs turite žaisti, arba paleisti funkciją, mygtuką, jūs turite per mygtuką žingsnis,
ir jūs taip pat turite Žingsnis į mygtuką.
Ir iš esmės, visi trys juos tiesiog pereiti per savo kodą
ir daryti skirtingus dalykus.
>> Taigi paprastai, kai jūs derinti, mes nenorime tiesiog paspauskite Play
nes Groti bus tiesiog paleisti Jūsų kodas jo pabaigoje.
Ir tada jūs ne iš tikrųjų žinoti, ką jūsų problema
yra, nebent jūs nustatyti kelis ribines vertes.
Jei nustatėte kelis atskaitos taškus, Jis tiesiog automatiškai
paleisti iš vienos nutrūkimo taške, į kitą, į kitą.
Tačiau šiuo atveju mes tik, kad vienas, nes mes
noriu dirbti savo kelią iš viršaus į apačią iki apačios.
Taigi mes ketiname ignoruoti tą mygtuką dabar tikslais šioje programoje.
>> Taigi virš funkcijos žingsnis tik žingsnių per kiekvieną eilutę
ir jums pasakys, ką kompiuteris daro.
Žingsnis į funkciją eina į faktinį funkcija
tai savo linijos kodą.
Taigi, pavyzdžiui, kaip ir printf (), kad yra funkcija, tiesa?
Jei aš norėjau fiziškai žingsnis į printf () funkcija,
Aš iš tikrųjų eiti į kūrinio kodas, kai printf () buvo parašyta ir pamatyti
kas ten vyksta.
>> Bet paprastai, mes manome, kad kodas, kad mes suteikiame Jums veikia.
Manome, kad printf () dirba.
Manome, kad GetInt () yra darbo.
Taigi nėra reikalo žingsnis į šių funkcijų.
Bet jei ten funkcijas kad rašote sau
kad jūs norite patikrinti , kas vyksta,
Jūs norėtumėte žingsnis į šią funkciją.
>> Taigi dabar mes tiesiog vyksta peržengti šio kodo gabalas.
Taigi pažiūrėkime.
O, spausdinti, "O hai, kaip daug pokyčių yra skolingas? "
Mums nerūpi.
Mes žinome, kad manimi dirbti, todėl mes žingsnis per jį.
>> Taigi, n, kuris yra mūsų plūdė, kad Mes initialized-- arba declared--
iki viršuje, mes dabar lygus, kad į GetFloat ().
Taigi leiskite dėti daugiau, kad.
Ir mes matome ne dugnas čia programa
yra raginimo man įvesti vertės.
Tad indėlis vertę mes norime išbandyti čia, kuris yra 0,41.
Didysis.
>> Taigi dabar n-- Ar jums vaikinai pamatyti čia ne bottom-- tai
stored-- nes mes ne apvalinama dar, tai
saugomi šiame kaip milžinas plūdė, kuri yra 0,4099999996,
kuris yra pakankamai arti, kad mūsų tikslams, dabar, iki 0,41.
Ir tada mes pamatysime vėliau, kaip mes toliau žengia per programa,
po čia n tapo apvalus ir centų tapo 41.
Didysis.
Taigi mes žinome, kad mūsų apvalinimo darbingo.
Mes žinome, kad mes turime teisingas skaičius centų,
todėl mes žinome, kad tai tikrai ne problema.
>> Taigi mes ir toliau žengia nuo šioje programoje.
Mes einame čia.
Ir taip po šio kodo eilutę, mes turėtų žinoti, kiek ketvirtadaliai turime.
Mes peržengti.
Ir matote mes, tiesą sakant, turi vieną ketvirtį, nes mes atimama 25
iš mūsų pradinės vertės 41.
Ir mes turime 16 išvyko į mūsų centų.
>> Ar visi suprasti, kaip programa žengia per
ir kodėl centų tapo 16 ir kodėl, dabar monetų tapo 1?
Ar visi taip, kad logika?
Saunus.
Taigi, kaip šio punkte, Programos darbo, tiesa?
Mes žinome, kad tai daro tiksliai ką mes norime jį.
Ir mes iš tikrųjų nebuvo turi išspausdinti, oi, ką
yra centų šiuo metu, kas monetų šiuo klausimu.
>> Mes ir toliau išgyvena programą.
Žingsnis vyresnis.
Saunus.
Mes einame per dimes.
Didysis.
Mes matome, kad tai atsižvelgti nuo $ 0,10 bulvarinis.
Ir dabar mes turime dvi monetas.
Teisingai.
>> Mes einame per centus ir matome kad mes turime liko centų.
Hmm, tai keista.
Iki čia programos, turėjau , kad atimama savo centus.
Galbūt aš tiesiog nebuvo daro ta linija teisę.
Ir deja, jūs galite pamatyti čia, nes mes žinome,
kad mes gerinimo per 32 ir 33 linijų,
tai kur mūsų programa netinkamai buvo kintamieji paleisti.
Taigi, mes galime pažvelgti ir pamatyti, OH, Aš atimant centų čia
bet aš ne iš tikrųjų pridedant prie mano monetų vertės.
Aš pridedant prie centų.
Ir aš nenoriu įtraukti į centai, noriu įtraukti į monetas.
Taigi, jei mes pakeisime, kad su monetomis, mes turime darbo programą.
Galiu paleisti check50.
Jūs galite tiesiog išeiti iš GDB teisė čia ir paleiskite check50 dar kartą.
Galėčiau tik tai padaryti.
Aš turiu padaryti godus.
0,41.
Ir čia jis spausdinimas iš dešinės atsakymą.
>> Taigi, kaip jūs vaikinai galite pamatyti, GDB yra tikrai galingas įrankis
, kai mes turime tiek daug kodas vyksta ir tiek daug kintamųjų
kad sunku mums, kaip žmogaus, sekti.
Kompiuteris, į GDB debugeris, turi galimybę
sekti viską.
Žinau, visų Visionaire, vaikinai tikriausiai galėjo pataikyti keletą segmentavimo gedimus
nes jūs naudojate iš ribų jūsų masyvo.
Atsižvelgiant į Cezario Pavyzdžiui, tai ką aš įgyvendino čia.
>> Taigi, aš pamiršau patikrinti kas nutiktų, jei aš
neturėjo dviejų komandų eilutės argumentus.
Aš tiesiog neišleido toje čekiu.
Ir todėl, jei aš paleisti Debug-- nustatyti mano atskaitos tašką į dešinę ten.
Aš paleisti derinti.
>> GERAI.
Taip.
Taigi iš tikrųjų, GDB turėjo kad jie ten man pasakė,
buvo segmentavimo kaltės nėra.
Aš nežinau, kas vyksta tiesiai ten, bet kai išbėgau,
jis dirbo.
Paleidus kodo eilutes per ir GDB gali tik staiga mesti jums,
eiti ir ieškoti, kas raudona yra klaida.
Jis jums pasakys, ei, jus turėjo segmentavimo kaltės,
o tai reiškia, kad jūs bandėte atidaryti vietos masyve, kad neegzistavo.
Taip.
>> Taigi, į kitą problemą Nustatykite šią savaitę vaikinai
tikriausiai turime daug kintamieji plūduriuojančius aplink.
Jūs esate nesiruošia būti tikras, ką visi jie reiškia tam tikru.
Taigi GDB tikrai padės jums suprasti , ką jie visi lygus
ir kad galėtų pamatyti, kad vizualiai.
Ar kas nors nežino, kaip bet, kad buvo darbo?
Saunus.
Gerai.
Taigi po to, esame ketina pasinerti į dešinę
į keturių skirtingų tipų rūšių šią savaitę.
Kaip daugelis iš jūsų pirmas iš visų, prieš pradedant,
Perskaičiau visą spec už pset3?
GERAI.
Aš didžiuojuosi jumis vaikinai.
Štai kaip pusė klasės, kuri yra žymiai daugiau nei paskutinį kartą.
>> Taigi tai puiku, nes kai mes kalbame apie turinį
į lecture-- arba Atsiprašome, į section-- man patinka
susieti daug, kad Atgal į ką pset yra
ir kaip norite įgyvendinti, kad jūsų pset.
Taigi, jei tu atėjai, turintys skaityti spec, jis bus
bus daug lengviau jums suprasti ką aš kalbu, kai sakau,
oi ei, tai gali būti tikrai gera vieta įgyvendinti šį rūšiuoti.
Taigi tie iš jūsų, kurie skaityti spec žinoti, kad dalį savo pset,
jūs ketinate turi parašyti rūšiuoti tipą.
Taigi, tai gali būti labai naudinga už jus šiandien daug.
>> Taigi mes pradėti su, Iš esmės, pats paprasčiausias tipas
rūšiuoti, atrankos rūšiuoti.
Tipiškas algoritmas kaip mes norime eiti apie tai
is-- Dovydas nuėjo per šias visi paskaita, todėl aš greitai judėti
here-- iš esmės, jums turėti vertybių masyvo.
Ir tada jūs rasti Mažiausias nerūšiuotos vertė
ir jūs apsikeitimo šią vertę su pirmasis nerūšiuotos vertė.
Ir tada jums tiesiog nuolat kartoti su savo sąrašą poilsio.
>> Ir štai vizualus paaiškinimas kaip kad galėtų dirbti.
Taigi, pavyzdžiui, jei mes pradėti Su iš penkių elementų masyvas, indeksas
0 iki 4, su 3, 5, 2, 6, ir 4 reikšmės dedamas į array-- tiek dabar,
mes tik ketina prisiimti kad jie visi nerūšiuotų
nes mes ne testuoti kitaip.
>> Taigi, kaip atrankos Rūšiuoti būtų darbas yra tai, kad būtų pirmas
eina per visas iš nerūšiuotų masyvo.
Būtų išpešti mažiausią vertę.
Šiuo atveju, 3, dešinę dabar yra mažiausias.
Ji gauna iki 5.
Ne, 5, yra ne didesnė than-- arba Atsiprašome, yra ne mažesnis than-- 3.
Taigi minimali vertė vis dar yra 3.
Ir tada jūs gausite 2.
Kompiuteris mato, OH, 2 yra mažesnis nei 3.
Dabar 2, turi būti minimali vertė.
Ir taip 2 apsikeitimo su tos pirmosios vertę.
>> Taigi, po vieną perdavimą, mes iš tikrųjų pamatyti kad 2 ir 3 yra sukeistos.
Ir mes tik ketina toliau daryti Tai vėl su masyvo poilsio.
Taigi mes ketiname tiesiog paleisti per per pastaruosius ketverius indeksai masyvo.
Pamatysime, kad 3 yra Kitas minimali vertė.
Taigi mes ketiname apsikeitimo, kad su 4.
Ir tada mes tik ketina išlaikyti veikia per kol, galų gale, jums
patekti į rūšiuotų masyvo, kurioje 2, 3, 4, 5, 6, ir visi yra rūšiuojami.
Ar visi suprasti logiką kaip atrankos Rūšiuoti veikia?
>> Jūs tiesiog turite kokią nors minimalaus vertę.
Jūs sekti, kas tai yra.
Ir kiekvieną kartą, kai jūs ją rasti, galite sukeisti su pirmuoju verte array--
arba, ne pirmas value-- Kitas vertė masyvo.
Saunus.
>> Taigi, kaip jūs vaikinai rūšies pamačiau iš trumpo žvilgsnis,
mes ketiname Pseudocode this out.
Taigi, jei jus vaikinai gale noriu sudaro grupę, kiekvienas prie stalo
gali susidaryti šiek tiek partnerį, aš ruošiuosi duoti jums, vaikinai kaip tris minutes
tiesiog pasikalbėti per logika, anglų kalba,
kaip mes galėtų įgyvendinti Pseudocode parašyti atrankos rūšiuoti.
Ir ten saldainiai.
Prašome ateiti ir gauti saldainių.
Jei esate nugaros ir norite saldainiai, galiu mesti saldainiai jums.
Tiesą sakant, tai you-- atvėsti.
O, atsiprašau.
GERAI.
>> Taigi, jei mes norėtume, kaip klasė, rašyti Pseudocode
kiek vienas gali kreiptis į Ši problema, tiesiog nedvejodami.
Aš tiesiog eiti aplink ir tam, kreipkitės į grupes
kito linijos Ką turėtume daryti.
Taigi, jei jus vaikinai nori pradėti išjungti, kas yra pirmas dalykas,
daryti, kai jūs bandote įgyvendinti būdas išspręsti šią programą
selektyviai rūšiuoti sąrašą?
Tegul tik daryti prielaidą, mes turi masyvą, gerai?
>> Auditorija: Jūs norite sukurti kai rūšiuoti [nesigirdi], kad esate
veikia per visą savo masyvo.
>> ANDI Peng: Teisė.
Taigi, jūs ketinate norite pakartoti per kiekvieną erdvę, tiesa?
Taigi, puikus.
Jei vaikinai nori duoti man Kitas line-- taip, gale.
>> Auditorija: Pabandykite juos Viskas mažiausias.
>> ANDI Peng: Nėra mes einame.
Taigi mes norime pereiti ir patikrinkite, pamatyti, kas minimali vertė yra tiesa?
Aš ruošiuosi sutrumpinti, kad į "min".
Ką vaikinai nori daryti po radote mažiausią vertę?
>> Auditorija: [nesigirdi]
ANDI Peng: Taigi jūs ketinate norite perjungti jį su pirmojo iš tos masyvą,
tiesa?
Štai pradžia, aš ruošiuosi pasakyti.
Gerai.
Taigi dabar, kad jūs pavertė pirmas viena, ką jūs norite daryti po to?
Taigi, dabar mes žinome, kad tai vienas čia turi būti mažiausios vertės, tiesa?
Tada jūs turite papildomą poilsio masyvo Štai nerūšiuotos.
Taigi, ką jūs norite daryti čia, jei jums vaikinai nori man duoti kitą eilutę?
Auditorija: Taigi jūs norite pakartoti per masyvo likusią dalį.
ANDI Peng: Taip.
Ir taip ką Iteracja per rūšies reiškia, mes tikriausiai reikia?
Kokios of--
>> AUDITORIJA: Oi, papildomas kintamasis?
ANDI Peng: Tikriausiai kita kilpa, tiesa?
Taigi, mes tikriausiai norės į pakartoti through-- didelis.
Ir tada jūs ketinate grįžti ir tikriausiai patikrinti mažiausiai kartą
tiesa?
Ir jūs ketinate nuolat kartoti tai, nes kilpos tik ketina
nuolat veikia, tiesa?
>> Taigi, kaip jūs vaikinai galite pamatyti, mes tiesiog turėti bendrą Pseudocode
kaip mes norime, kad tai programos ieškoti.
Tai kartoti čia ką mes paprastai reikia parašyti mūsų kodas
jei norime pakartoti per masyvas, kokios rūšies struktūros?
Manau Christabel jau sakiau anksčiau.
>> Auditorija: A kilpa.
>> ANDI Peng: A kilpa?
Būtent.
Taigi tai tikriausiai bus už kilpa.
Kas yra čekis čia ketina reikšti?
Paprastai, jei norite patikrinti jei kažkas yra kažkas else--
>> Auditorija: Jei.
>> ANDI Peng: IF, tiesa?
Ir tada apsikeitimo čia mes eiti per vėliau, nes Dovydo
išgyveno, kad paskaitos, taip pat.
Ir tada antra kartoti implies--
>> Auditorija: Kitas kilpą.
>> ANDI Peng: --another už kilpos, tiksliai.
Taigi, jei mes ieškome ne tai teisingai, mes
galite pamatyti, kad mes tikriausiai ketinate reikia už kilpa įdėtos
su lygtiniu pareiškimą ten ir tada tikrasis kodo fragmentą, kad tai
ketina sukeisti vertybes.
Taigi aš tiesiog paprastai parašyta Pseudocode kodas čia.
Ir tada mes iš tikrųjų ketiname fiziškai, kaip klasė,
pabandykite tai šiandien įgyvendinti.
Grįžkime į šį IDE.
>> Uh Oh.
Kodėl taip yra not-- ten jis yra.
GERAI.
Atsiprašome, leiskite man pabandyti padidinti šiek tiek daugiau.
Čia mes eiti.
Viskas, ką aš darau čia aš sukūriau programa, vadinama "atranka / sort.c".
Aš sukūrė devynių masyvo vertės, 4, 8, 2, 1, 6, 9, 7, 5, 3.
Šiuo metu, kaip jūs galite pamatyti, jie yra netvarkingai.
n yra ketina būti numerį, jums pasakys vertybių sumą
turite savo masyvo.
Šiuo atveju, yra devyni reikšmes.
Ir aš ką tik gavo už kilpos čia kad spausdina į nerūšiuotas masyvo.
>> Ir galų gale, aš taip pat gavo už kilpa, kad tik spausdina jį dar kartą.
Taigi, teoriškai, jeigu šios programos veikia teisingai, pabaigoje,
Jūs turėtumėte pamatyti spausdinami kilpa kur 1, 2, 3, 4, 5, 6, 7, 8,
9 yra visi teisingai, kad.
>> Taigi mes turime mūsų Pseudocode čia.
Ar kas nors nori to-- Aš tiesiog ketina eiti prašyti volunteers--
pasakykite man, ką rašyti, jei mes norime, pirma, tik pakartoti
per šio masyvo pradžios?
Koks kodo eilutę aš tikriausiai reikia čia?
>> Auditorija: [nesigirdi]
>> ANDI Peng: Taip, jaučia nemokama to-- Atsiprašome, bet jūs
neturi stovėti up-- jaustis nemokama pakelti jūsų balsas truputį.
>> Auditorija: Dėl int i lygus 0--
>> ANDI Peng: Taip, gerai.
>> AUDITORIJA: i yra mažiau nei masyvo ilgį.
>> ANDI Peng: Taigi turėkite mind čia, nes mes
neturi funkciją, kuri pasakoja mums masyvo ilgis,
Mes jau turime vertė, kuri saugo, kad.
Teisė?
Kitas dalykas, kad į mind-- masyve
devynių vertybių, kokie yra rodikliai?
Leiskite tik pasakyti, tai masyvas, rezultatas buvo 0 iki 3.
Jūs matote, kad paskutinis indeksas yra iš tikrųjų 3.
Tai ne 4, nors ten Keturi vertės masyvo.
>> Taigi čia mes turime būti labai atsargūs, apie tai, ką mūsų sąlyga ilgio
bus.
>> Auditorija: Ar nebūtų n atėmus 1?
ANDI Peng: Tai vyksta n atėmus 1, tiksliai.
Ar tai prasminga, kodėl tai n atėmus 1, visi?
Tai todėl, kad matricos yra nulinės indeksuojami.
Jie pradeda nuo 0 ir paleisti iki n atėmus 1 d.
Taip, tai šiek tiek sudėtinga.
GERAI.
Ir tada--
Auditorija: Isnt'1 kad jau pasirūpinta, nors,
tiesiog nesakau "mažesnis arba lygi ", o tiesiog pasakyti" mažiau nei? "
>> ANDI Peng: Tai šiek tikrai geras klausimas.
Taigi, taip.
Bet taip pat, kaip kad mes Įgyvendinant tikrinimo teisę,
jums reikia palyginti dvi reikšmes.
Taigi jūs iš tikrųjų norite palikti "į" tuščias.
Nes jei jūs palyginkite tai viena, jūs nesiruošia
nieko po to, kai palyginti su, tiesa?
Taip.
Taigi aš ++.
Pridėkime mūsų skliausteliuose.
Oi.
Didysis.
Taigi, mes turime pradžią mūsų išorinio kontūro.
Taigi dabar mes tikriausiai norėsite sukurti išlaikant kintamasis
kelio mažiausio vertės, tiesa?
Ar kas nors nori duoti man linija kodą, kuris būtų tai padaryti?
Ką mes turime, jei mes ketiname nori laikyti kažką?
>> Teisė.
Gal geriau pavadinimą, kad būtų be-- "Temp" visiškai works--
gal daugiau taikliai pavadino būtų, Jeigu norime, kad mažiausią value--
>> Auditorija: Min.
ANDI Peng: min ten einame.
min Būtų gerai.
Ir todėl čia, ką mes nori inicijuoti jį?
Tai yra šiek tiek sudėtinga.
Nes dabar ne pradžioje šio masyvo,
turite ne pažvelgė nieko, tiesa?
Taigi, kas, savaime, jei Užtenka tik ant i yra lygus 0,
ką mes norime inicijuoti mūsų pirmasis minimali vertė?
AUDITORIJA: i.
ANDI Peng: I, tiksliai.
Christabel, kodėl mes norime inicijuoti jį i?
>> Auditorija: Kadangi gerai, mes pradedant 0.
Taigi todėl, kad mes nieko palyginti kad ji, minimalus bus baigti yra 0.
>> ANDI Peng: Būtent.
Taigi ji visiškai teisus.
Nes mes ne iš tikrųjų pažvelgė nieko dar,
mes nežinome, kas mūsų minimali vertė yra.
Mes norime, kad tik inicijuoti jį Aš, kuris šiuo metu yra čia.
Ir kaip mes toliau žemyn šį masyvą,
matysime, kad vieni su Papildoma kamuolį, aš žingsniais.
Ir taip, kad tuo momentu, Aš tikriausiai vyksta
nori būti minimali,, nes jis bus whatever
yra nerūšiuotų masyvo pradžia.
Saunus.
>> Taigi dabar mes norime pridėti už kilpos čia tai
ketina pakartoti per nerūšiuotus, arba šio masyvo poilsio.
Ar kas nors nori man duoti linija kodą, kuris būtų tai padaryti?
Hint-- Ką turime žemyn čia?
Kas vyksta eiti tai už kilpa?
Taip.
Auditorija: Taigi mes norime norite turi skirtingą sveikasis skaičius,
nes mes paleisti per likusį masyvo vietoj I, tai gal
j.
>> ANDI Peng: Taip, j skamba gerai man.
Lygu?
>> Auditorija: Taigi būtų i plius 1, nes jūs pradedant kitą vertę.
Ir tada į end-- Taigi dar kartą, j yra mažiau nei n minus 1, ir po to j ++.
ANDI Peng: Didysis.
>> Ir tada čia mes ketiname nori patikrinti, pamatyti, jei mūsų sąlyga yra įvykdyta,
tiesa?
Kadangi jūs norite pakeisti mažiausią vertę
jei tai tikrai mažesnis nei Jūs lyginant ją, tiesa?
Taigi, ką mes ketiname nori čia?
Patikrinkite, pamatyti.
Kokios ataskaitos mes tikriausiai
TI norite naudoti, jei mes norite patikrinti kažką?
>> Auditorija: if.
>> ANDI Peng: if.
Taigi if-- ir kas bus sąlyga, kad mes norime viduje
Mūsų IF?
>> Auditorija: Jei j vertė yra mažesnis nei i-- vertės
>> ANDI Peng: Būtent.
Taigi if-- todėl šis masyvas vadinamas "masyvas".
Didysis.
Taigi, jei array-- kas tai buvo?
Pakartok.
>> AUDITORIJA: Jei masyvo-j yra mažiau nei masyvas-i, tada mes turėtume pakeisti min.
Taigi min būtų j.
>> ANDI Peng: Ar tai prasminga?
GERAI.
Ir dabar žemyn čia, mes iš tikrųjų nori įgyvendinti apsikeitimo sandoriai, tiesa?
Taigi prisiminti, kad paskaita, kad Dovydas, kai jis bando apsikeitimo the-- kas buvo
it-- apelsinų sultys ir milk--
>> Auditorija: Tai buvo bruto.
>> ANDI Peng: Taip, tai buvo natūra bruto.
Bet tai buvo gana geras koncepcija parodyti laiką.
Taigi manau, jūsų vertybėmis čia.
Jūs turite masyvą nuo min, o tai yra i masyvas,
ar kas mes stengiamės apsikeitimo čia.
Ir jūs turbūt negali supilkite juos į tuo pačiu metu, vienas nuo kito, teisę?
Taigi, ką mes ketiname kad reikia sukurti čia
tam, kad apsikeitimo reikšmes teisingai?
>> Auditorija: laikinai kintamasis.
>> ANDI Peng: laikinai kintamasis.
Taigi darykime int temp.
Žr, tai būtų geriau, laikas to-- Whoa, kas tai buvo?
GERAI.
Taigi tai būtų buvę geriau laikas pavadinti kintamasis "Temp".
Taigi darykime int temp.
Ką mes ketiname nustatyti temp lygią čia?
Auditorija: Min?
ANDI Peng: Tai šiek tiek sudėtinga.
Tai iš tikrųjų nesvarbu, galų gale.
Nesvarbu, ką Kad jūs nuspręsite apsikeitimo
kaip ilgai, kaip jūs darote, kad esate sekti, ką jūs Swapping.
>> Auditorija: Tai gali būti masyvas-i.
>> ANDI Peng: Taip, darykime masyvo-I.
Ir kas tada bus kitas linija kodo norime turėti čia?
Auditorija: masyvas-i yra lygus masyvo-J.
ANDI Peng: Ir galiausiai?
Auditorija: masyvas-J lygus masyvo-i.
Auditorija: arba matriciniai-j nelygiaverčiai masyvas-temp-- arba temp.
>> ANDI Peng: Gerai.
Taigi leiskite veikti tai ir pamatyti jei jis vyksta į darbą.
Kur yra ta, kad vyksta?
Oi, tai problema.
Žr ant 40 eilutėje, mes bando naudoti masyvo-J?
Bet kur j egzistuoja tik?
>> Auditorija: Į for ciklas.
ANDI Peng: Teisė.
Taigi, ką mes ketiname daryti?
>> Auditorija: Nustatykite jį ne the--
Auditorija: Taip, aš manau, jūs turite naudoti kitą, jei teiginys, tiesa?
Taigi, kaip, jei minimum-- Gerai, leiskite man galvoti.
>> ANDI Peng: Vaikinai, pasistenkite pažvelgti Leiskite
Žr ką kažkas, ką galime padaryti čia?
>> Auditorija: Gerai.
Taigi, jei minimalus nėra lygi j-- todėl, jei minimalus vis dar i--
tada mes neturi apsikeitimo.
>> ANDI Peng: Ar tai lygūs i?
Ką noriu pasakyti čia?
>> Auditorija: Arba taip, jei Minimalus nėra lygi i, taip.
ANDI Peng: Gerai.
Gerai, kad sprendžia, kokios mūsų problemos.
Bet, kad vis dar nėra išspręsti problema kas atsitiks, jei j-- nes j
neegzistuoja už jį, kas jūs norime daryti su juo?
Pripažinti jį ne?
Pabandykime veikia tai.
Uh Oh.
Mūsų Rūšiuoti neveikia.
>> Kaip matote, mūsų pradinis masyvas turėjo šias vertybes.
Ir vėliau, jis turėtų būti buvo 1, 2, 3, 4, 5, 6, 7, 8, 9.
Tai neveikia.
Ak.
Ką mes darome?
Auditorija: Derinti.
ANDI Peng: Gerai, mes galime pabandyti tai.
Mes galime derinti.
Zoom out truputį.
Leiskite nustatyti mūsų atskaitos tašką.
Vykime like-- OK.
>> Taigi todėl, kad mes jau žinome, kad Šios linijos, 15 per 22,
yra working--, nes viskas, ką aš darau yra tik Iteracja per ir printing--
Aš galiu eiti į priekį ir praleisti, kad.
Pradėkime eilutėje 25 d.
Oop, leiskite man atsikratyti, kad.
>> Auditorija: Taigi atskaitos tašką s kur derinimo prasideda?
ANDI Peng: Arba sustoja.
Auditorija: Arba sustoja.
ANDI Peng: Taip.
Galite nustatyti kelis ribines vertes ir jis gali tik pereiti iš vieno į kitą.
Tačiau šiuo atveju mes nežinome, kai klaida vyksta.
Taigi, mes tik norime pradėti nuo viršaus į apačią,.
Yep.
GERAI.
>> Taigi ši eilutė čia, mes galime žingsnis.
Jūs galite pamatyti žemyn čia mes turime masyvą.
Tai yra vertybės kad yra masyvo.
Ar matote, kad kaip 0 indeksas, jis atitinka value-- oh,
Aš ruošiuosi pabandyti padidinti.
Atsiprašome, tai tikrai sunku į see-- ne masyvo indeksas 0,
mes vertė yra 4, ir tada taip toliau, ir taip toliau.
Mes turime vietinius kintamuosius.
Dabar aš yra lygus 0, o mes norime, kad ji būtų.
>> Ir todėl galime laikyti užlipti.
Mūsų minimalus yra lygus 0, kurią mes taip pat norime, kad ji būtų.
Ir tada mes įvesti mūsų sekundę kilpa, jei masyvo-j yra mažiau nei masyvo-i,
kurio nebuvo.
Taigi matei, kaip kad praleista daugiau, kad?
>> Auditorija: Taigi turėtų, jei Minimalus visi that-- turėtų ne tai, kad
būti viduje pirmąjį kilpa?
ANDI Peng: Ne, nes jūs vis dar norite išbandyti.
Jūs norite padaryti palyginimą kiekvieną laikas, net po to, kai eina per jį.
Jūs neturite tiesiog norite tai padaryti pirmą pereinamas.
Jūs norite tai padaryti su už kiekvieną papildomą perdavimas dar kartą.
Taigi jūs norite patikrinti Jūsų būklė viduje.
Taigi mes tik ketina nuolat veikia per čia.
Aš duosiu jums, vaikinai užuominą.
Ji turi daryti su tuo, kad, kai jūs patikrinti jūsų sąlyginė,
Jūs neprisijungęs tikrinti už teisingą indekso.
Taigi dabar jūs tikrinti masyvo indeksas j yra mažesnis nei masyvo
indeksas I priedą.
Bet ką tu darai iki ne Iš už kilpos pradžia?
Ar ne jūs nustatant j lygus i?
>> Taip, taip, mes galime iš tikrųjų išeiti debugerem čia.
Taigi leiskite pažvelgti mūsų Pseudocode išvaizdą.
For-- mes ketiname prasidės I lygus 0.
Mes ketiname eiti n atėmus 1 d.
Leiskite patikrinti, ar mes turime tokią teisę?
Taip, tai buvo teisus.
>> Taigi viduje čia mes ketina sukurti mažiausią vertę
ir nustatyti, kad lygi i.
Ar mes tai darome?
Taip, tai padarė.
Dabar mūsų vidinis už kilpos, mes ketina daryti j lygi i n atėmus 1.
Ar mes tai darome?
Iš tiesų, mes padarėme tai.
>> Taigi Tačiau tai, ką mes lyginti čia?
>> Auditorija: j plius 1.
ANDI Peng: Būtent.
Ir tada jūs ketinate norite nustatyti minimali lygi j plius 1 taip pat.
Taigi aš per, kad tikrai greitai.
Ar jus vaikinai suprasti kodėl tai j plius 1?
GERAI.
>> Taigi jūsų masyvas, į Jūsų pirmasis perdavimas per,
Jūsų for ciklas, skirtas int Aš lygus 0, tegul tiesiog
manyti, tai nebuvo pakeistas dar.
Mes turime iš masyvo, visiškai, tik keturi nerūšiuotos elementai, tiesa?
Taigi mes norime inicijuoti Aš lygus 0.
Ir aš ketina tik paleisti per šį kilpa.
Ir taip per pirmąjį perdavimą, mes ketiname inicijuoti kintamąjį vadinamą "min"
kuris taip pat yra lygus i, nes mes neturime mažiausią vertę.
Taigi, kad šiuo metu lygus 0, taip pat.
Ir tada mes ketiname eiti per.
Ir mes norime pakartoti dar kartą.
Dabar, kad mes pastebėjome, ką mūsų minimalus yra, mes norime pakartoti per
vėl pamatyti, jei ji manimi lyginant, tiesa?
Taigi j, čia vyksta į vienodą i, kuris yra 0.
Ir tada, jei masyvas j plius aš, kuris yra vienas, kad yra kitas daugiau, mažiau
nei tai, ką jūsų dabartinę minimumo reikšmė yra, jūs norite sukeisti.
>> Taigi galime tik pasakyti, mes gavo, kaip, 2, 5, 1, 8.
Dabar, aš lygus 0, o j yra lygus 0.
Ir tai mūsų minimali vertė.
Jei masyvo-j plius i-- todėl, jei vienas tai po vieną mes ieškome
yra didesnis nei prieš vieną, jis ketina tapti minimalus.
>> Taigi čia matome, kad 5 yra ne mažesnis nei.
Taigi, tai bus ne 5.
Mes matome, kad 1 yra mažesnis kaip 2, tiesa?
Taigi, dabar mes žinome, kad mūsų minimalus yra bus indekso reikšmė, esant 0, 1, 2.
Taip?
Ir tada, kai jūs gaunate žemyn čia galite sukeisti teisingas reikšmes.
>> Taigi, kai jūs vaikinai buvo tiesiog J anksčiau, jums nebuvo žiūri į vieną
po jo.
Jūs buvote ieško tas pats vertę, kuri
Štai kodėl jis tiesiog buvo nieko nedaryti.
Ar tai prasminga visiems, Kodėl mums reikia, kad ir 1 ten?
GERAI.
Dabar tegul tiesiog paleisti per jį padaryti Patikrinkite, ar likusia kodas yra teisinga.
Kodėl tai vyksta?
Ak, tai min čia.
Mes buvome lyginant klaidingą vertę.
O ne.
>> Oh yeah, žemyn čia mes buvome Swapping neteisingus vertybes, taip pat.
Kadangi mes ieškojome ne i ir j.
Tai yra tie, buvome tikrinimą.
Mes iš tikrųjų norite apsikeitimo Minimalus einamosios minimalus,
su kokia viena už tai.
Ir kaip jus vaikinai galite pamatyti žemyn čia mes turime rūšiuotą masyvo.
Jis tiesiog turėjo daryti su tai, kad, kai
mes buvome pažymėdami vertės buvome palyginus,
mes ne žiūri į dešinę vertybes.
Mes ieškojome tuo pačiu vienas čia ne iš tikrųjų Swapping ją.
Jūs turite pažvelgti į vieną Kitas jai ir tada jūs galite apsikeitimo.
Taigi tai, kas buvo natūra prieš bugging mūsų kodą.
Ir ką aš čia padariau yra viskas Debugger galėjo padaryti už jus
Aš tiesiog padarė tai dėl lenta, nes jis lengviau
pamatyti, o ne bandyti priartinti išriktuotojo.
Ar tai prasminga visiems?
Saunus.
>> Gerai.
Mes galime pereiti prie kalbame apie asimptotinio žymėjimas, kuris
yra tik išgalvotas būdas sakydamas katilas visų šių rūšių.
Taigi aš žinau, Dovydą, į paskaitą, palietė Runtimes.
Ir jis nuėjo per visą formulę kaip apskaičiuoti runtimes.
Nesijaudinkite apie tai.
Jei esate tikrai smalsu apie tai, kaip tai veikia,
nedvejodami kreipkitės į mane, kai skyriuje.
Mes galime eiti per formulės kartu.
Tačiau visi vaikinai turi tikrai žinau, kad n kvadratu nei 2
yra tas pats, kaip n kvadratu.
Kadangi daugiausiai, eksponentinis, auga labiausiai.
Ir taip mūsų tikslais, visi mes rūpinamės
yra tai, kad milžiniškas skaičius, kuris auga.
>> Taigi, kas yra geriausias atvejis Trukmė Atrankos rūšiuoti?
Jei jūs ketinate turėti į pakartoti per sąrašą
ir tada pakartoti per iš šio sąrašo poilsio,
kiek kartų yra jūs ketinate tikriausiai,
blogiausiu case-- Europos Sąjungos oficialiajame Geriausiu atveju sorry-- paleisti per?
Gal geriau klausimas yra paklausti, kas yra blogiausias atvejis
Trukmė Atrankos rūšiuoti.
AUDITORIJA: N kvadratu.
ANDI Peng: Tai n kvadratu, tiesa.
Taigi paprastas būdas galvoti apie tai, kaip, bet kuriuo metu Jūs turite dvi įdėtos už kilpos,
tai bus n kvadratu.
Kadangi ne tik jūs veikia per kartą,
jūs turite eiti atgal aplink ir paleisti per jį
vėl viduje kiekvienam vertės.
Taigi šiuo atveju, jūs vykdote n times n kvadratu, kuris is-- Atsiprašome,
n kartų, n, kuris lygus n kvadratu.
>> Ir rūšiuoti taip pat yra šiek tiek unikalus tuo,
kad ji neturi reikšmės, jei jas reikšmės yra jau tam.
Jis vis dar ketina paleisti per anyways.
Leiskite tik pasakyti, kad tai buvo 1, 2, 3, 4.
Nepriklausomai nuo to, ar tai buvo Kad, jis vis dar būtų bėgo per
ir vis dar tikrinamas mažiausią vertę.
Būtų padarė pats patikrų skaičius
kiekvieną kartą, net jei tai iš tikrųjų nebuvo paliesti bet ką.
>> Taigi, tokiu atveju, geriausias ir labiausiai katilas yra tikrai lygiaverčiai.
Taigi tikimasi, Runtime Atrankos rūšiuoti,
kurį mes paskirti simboliu iš teta, teta, šiuo atveju,
Taip pat būtų n kvadratu.
Visi šie trys būtų n kvadrato.
Ar visi aišku, kodėl runtime yra N kvadratu?
>> Gerai.
Taigi, aš tik ketina greitai paleisti per iš rūšių poilsio.
Už algoritmas burbulas sort-- atminkite,
Tai buvo pirmasis Davidas perėjo į paskaitą.
Iš esmės, jūs žingsnis per visą sąrašą
ir jūs swap-- jums tiesiog palyginti du vienu metu.
Ir jei vienas yra didesnis, nei jūs tiesiog apsikeitimo juos.
Taigi, jei jie yra didesni, galima būtų sukeisti.
Aš turiu oficialus čia.
>> Taigi tegul tiesiog pasakyti jums buvo 8, 6, 4, 2.
Jūs norite lyginti 8 ir 6.
Jums reikia apsikeitimo juos.
Galima būtų lyginti 8 ir 4.
Jums reikia apsikeitimo juos.
Jei jūs turite apsikeitimo 8 ir 2, jas pakeisti, taip pat.
Taigi tokiu prasme, jūs galite pamatyti, sužaistos per ilgą laiką,
kaip vertybės rūšies burbulas galai, kuris yra, kodėl mes jį vadiname
burbulas rūšiuoti.
>> Mes tiesiog paleisti per vėl Mūsų antra perdavimas, ir mūsų trečiasis perdavimas,
ir mūsų ketvirtasis perdavimą.
Iš esmės, burbulas rūšiuoti tiesiog veikia kol jums nereikia atlikti jokių daugiau apsikeitimo sandoriais.
Taigi šia prasme, tai tik bendras Pseudocode už jį.
Nesijaudinkite, tai visi bus internete.
Neturime iš tikrųjų eiti per tai.
>> Mes tiesiog inicijuoti skaitiklis kintamasis, kuris prasideda 0.
Ir mes pakartoti visą masyvą.
Ir jei viena vertė is-- jei tai vertė yra didesnė už tos vertės,
jūs ketinate apsikeitimo juos.
Ir tada jūs tiesiog ketina nesustoti.
Ir jūs ketinate pasikliauti.
Ir jūs tik ketina toliau daryti tai, o skaitiklis yra didesnis
už 0, tai reiškia, kad kiekvieną kartą jūs turite apsikeitimo,
jūs žinote, jūs norite eiti atgal ir vėl patikrinkite.
Norite nuolat tikrinti, kol jūs žinote, kad jūs neturite apsikeitimo nebėra.
>> Taigi, kas yra geriausia ir blogiausia atveju katilas už burbulas rūšiuoti?
Ir hint-- iš tikrųjų tai yra skirtingi nuo atrankos rūšiuoti ta prasme
, kad šie du atsakymai nėra ta pati.
Pagalvokite apie tai, kas nutiktų atvejis, jei jis jau buvo rūšiuojamos.
Ir galvoti apie tai, ką nutiktų, jei ji buvo
ir tuo atveju, kurioje jis buvo ne rūšiuojami.
Ir jūs galite rūšies paleisti per, kodėl tai vyksta.
Aš duosiu jums vaikinai, kaip, 30 sekundžių galvoti apie tai.
>> GERAI.
Ar kas nors turite, ką atspėti blogiausiu atveju Runtime burbuliukų rūšiuoti yra?
Taip.
>> Auditorija: tai būtų, pavyzdžiui, n kartų n atėmus 1 ar kažkas panašaus?
Kaip, kiekvieną kartą jis eina, tai tiesiog, kaip, viena apsikeitimo mažiau
kad ir kokia ji buvo.
>> ANDI Peng: Taip, taip, esate visiškai teisus.
Ir tai yra tokiu atveju jūsų Atsakymas iš tikrųjų buvo sudėtingesnis
nei vienas mes turime duoti.
Taigi jis ketina run-- aš ketina sunaikinti visa tai čia.
Ar kiekvienas geras?
Ar galiu ištrinti tai?
GERAI.
Jūs ketinate paleisti per n kartų pirmą kartą, tiesa?
Ir jie ketina paleisti per n atėmus 1 antrą kartą, tiesa?
Ir tada jūs ketinate laikyti vyksta, n kasyklos 2 et cetera.
Dovydas darė tai paskaitos, tam tikrais atvejais, jei įtraukėte visus šias vertybes,
jūs gaunate kažką, kad like-- yeah-- per 2, kuris iš esmės tik sumažina
iki n kvadratu.
Jūs ketinate gauti keistai frakcija ten.
Ir taip tiesiog žinau, kad n visada kvadrato
viršenybę prieš frakcija.
Ir šiuo atveju taip, blogiausia Trukmė būtų n kvadratu.
Jei jis buvo mažėjančia Kad, manau, jums
turite padaryti apsikeitimo kiekvieną kartą.
>> Koks būtų potencialiai, Geriausiu atveju Runtime?
Leiskite tik pasakyti, jei sąrašas buvo jau tam, ką runtime būti?
>> Auditorija: N.
ANDI Peng: Tai n tiksliai.
Ir kodėl tai n?
Auditorija: nes jums tiesiog turi patikrinti kiekvieną kartą.
ANDI Peng: Būtent.
Taigi geriausiu įmanomu runtime, jei šis sąrašas jau buvo
sorted-- tarkim 1, 2, 3, 4-- jums tiesiog eiti per, jums bus patikrinti,
galėtumėte pamatyti, oi, visi jie išdegti.
Aš neturėjau apsikeitimo.
Aš baigiau.
Taigi šiuo atveju, tai tik n ar žingsnių jūs tiesiog
turėjo patikrinti pirmoje sąrašo.
>> Ir po to mes dabar nukentėjo įterpimo rūšiuoti, kur
algoritmas iš esmės yra padalinti jį į rūšiuotus ir nerūšiuotus dalį.
Ir tada po vieną, kad nerūšiuotos vertybės
įdėta į jų tinkamas pozicijos į sąrašo pradžioje.
>> Taigi, pavyzdžiui, turime sąrašas 3, 5, 2, 6, 4 dar kartą.
Mes žinome, kad tai šiuo metu nerūšiuotos, nes mes tiesiog
pradėjo žiūri į jį.
Mes pažvelgti ir mes žinome, kad pirmoji vertė yra rūšiuojami, tiesa?
Jei jūs tik ieškote bent iš masyvo dydis vienas, jūs žinote, kad jis rūšiuojami.
>> Taigi mes žinome, kad kiti keturi yra nerūšiuotos.
Mes pereiti ir matome, kad vertę.
Grįžkime.
Žiūrėkite, kad 5 vertę?
Mes pažvelgsime jo išvaizdą.
Mes lyginame jį 3.
Mes žinome, kad tai yra didesnis nei 3, todėl mes žinome, kad manimi rūšiuojami.
Taigi dabar mes žinome, kad pirmieji du yra rūšiuojami ir paskutinis trijų nėra.
>> Mes pažvelgsime 2 išvaizdą.
Mes pirmą kartą ją patikrinti su 5.
Ar tai yra mažiau nei 5?
Tai nėra.
Taigi, mes turime nuolat ieško žemyn.
Tada jums patikrinti 2 išjungtas 3.
Ar tai mažiau nei?
Ne.
Taigi jūs žinote, 2, turi būti įrašomas į priekį ir 3 ir 5
abu turi būti išstumtas.
Ar tai vėl su 6 ir 4.
Ir mes tiesiog nuolat tikrinti iš esmės, kur mes tiesiog patikrinti, patikrinti, patikrinti.
Ir tol, kol jis yra dešinėje pozicija, mes natūra tik
įterpti jį į dešinę poziciją, kuris yra, kur jo pavadinimas atsirado.
>> Taigi tai tik algoritmas, Pseudocode per se, rūšies,
apie tai, kaip mes norėtume įgyvendinti įterpimas rūšiuoti.
Pseudocode yra čia.
Tai viskas internete.
Nesijaudinkite, jei jus vaikinai yra bando kopijuoti šį žemyn.
Taigi, dar kartą, tas pats, kas question-- būtų geriausias ir blogiausias runtimes
intarpas rūšiuoti?
Tai labai panašus į pastarąjį klausimą.
Aš duosiu jums vaikinai, kaip, 30 sekundžių galvoti apie tai, kaip gerai.
>> Gerai Ar kas nors nori man blogiausia runtime?
Taip.
>> AUDITORIJA: N kvadratu.
>> ANDI Peng: Tai n kvadratu.
Ir kodėl jis n kvadratu?
>> Auditorija: Kadangi atvirkštine tvarka, Jūs turite
eiti per n kartų, n, kuris is--
ANDI Peng: Taip, tiksliai.
Taigi tas pats, kaip burbulas rūšiuoti.
Jei šis sąrašas yra mažėjančia tvarka, esate
teks patikrinti pirmą kartą.
Ir tada su kiekviena papildomą vertę, esate
teks patikrinti prieš kiekvienas vertė, tiesa?
Ir taip visiškai, jūs ketinate padaryti N Pass kartų dar N praeiti, kuri
yra N kvadratu.
Ką apie geriausiu atveju?
Taip.
>> AUDITORIJA: n minus 1, dėl to, kad Pirmasis jau kvadratu.
>> ANDI Peng: Taigi, arti.
Atsakymas yra iš tikrųjų n.
Kadangi kol pirmasis vienas yra rūšiuojamos, ji negali actually-- ją
mes tiesiog lucked, į kad pavyzdys, kad 2
atsitiko mažiausias skaičius.
Bet tai ne visada bus tas atvejis.
Jei 2 jau rūšiuojamos pradžioje bet jums atrodo ir ten 1 čia
1-ketina guzas.
Ir jis ketina baigti iki Iškilioji anyways.
>> Taigi geriausiu atveju, tai tikrai tik bus n.
Jei turite 1, 2, 3, 4, 5, 6, 7, 8, esate
ketina paleisti per kad visą sąrašą kartą
patikrinti, ar viskas gerai.
Ar kiekvienas aiškiai veikia kartų atrankos, taip pat?
Aš žinau, aš ruošiuosi per tai tikrai greitai.
Bet tik žinau, kad jei jūs žinote, Bendrosios sąvokos, jums turėtų būti gerai.
GERAI.
Taigi aš tiesiog suteikti jums vaikinai gal, pavyzdžiui, minutę pasikalbėti su savo kaimynais
apie tai, kas yra tik keletas iš pagrindinių skirtumų
tarp šių rūšių tipų.
Mes eiti per, kad netrukus.
AUDITORIJA: O, gerai.
ANDI Peng: Taip.
GERAI.
Cool, tegul susirinks kaip klasė.
GERAI.
Taigi tai buvo natūra Kurių neterminuotas klausimas ta prasme,
kad ten daug atsakymų į juos.
Ir mes eiti per kai kurias iš jų trumpai.
Aš tik norėjau jums vaikinai galvoju apie tai, ką diferencijuojamas
visi trys tipai rūšių.
Ir aš girdėjau, taip pat puikus question-- ką sujungti rūšiuoti daryti?
Didelis klausimas, nes tai ką mes apimantis toliau.
>> Taigi sujungti rūšiuoti yra vienokį, kad funkcijos
labai skirtingai nuo kitų rūšių.
Kaip jus vaikinai galite see-- Dovydas daryti kad demo
kur jis turėjo visą atvėsti triukšmas matyti, kaip sujungti
Rūšiuoti bėgo, kaip, be galo greičiau nei kitų dviejų tipų?
GERAI.
Štai dėl suliejimo Rūšiuoti įgyvendina šią atskirtį
ir užkariauti koncepciją, kad mes kalbėjo apie į paskaitą aikštelė.
Ta prasme, kad mes norėtume dirbti protingesni, o ne sunkiau, kai padalinti
ir užkariauti problemas ir jas laužyti žemyn, ir tada juos kartu,
geri dalykai visada.
>> Taigi taip, kad sujungti Rūšiuoti esmės veikia
tai, kad ji perskiria nerūšiuotų masyvas per pusę.
Ir tada jis gavo dvi puses matricos.
Ir tai tik rūšiuoja šias dvi puses.
Jis tiesiog išlaiko dalijant per pusę, į pusę, per pusę, kol viskas yra rūšiuojami
ir tada rekursyviai įdėkite jį visi kartu.
>> Taigi tai tikrai abstrakti.
Taigi tai yra tik Pseudocode tiek.
Ar tai prasminga taip tai veikia?
Taigi leiskite tiesiog pasakyti jums turėti masyvas n elementų, tiesa?
Jei n yra mažesnis nei 2, galite grįžti.
Nes jūs žinote, kad jei yra tik vienas dalykas, ji turi būti rūšiuojami.
Kita, galite rūšiuoti yra kairėje pusėje, ir tada rūšiuoti tinkamą pusę,
ir tada sujungti.
>> Taigi, nors, kad atrodo labai paprasta, iš tikrųjų, galvoju apie tai
rūšies sunku. Kadangi jūs esate kaip ir, Na, tai kokios veikia savaime.
Teisė?
Jis veikia savaime.
Taigi šia prasme, Davidas palietė nuo rekursijos klasėje.
Ir tai yra koncepcija mes kalbame apie daugiau.
Tai, kad ši, šios dvi linijos čia iš tikrųjų yra tik programa
pasakoti ją paleisti save su skirtingais įėjimo.
Taigi, o ne paleisti save su n elementų visuma,
galite ją padalyti į kairė pusė ir teisė pusę
ir tada paleisti jį dar kartą.
>> Ir tada mes pažvelgti į jį vizualiai, nes aš vizualiai besimokantysis.
Ji veikia geriau už mane.
Taigi mes pažvelgti vizualiai pavyzdyje.
>> Tarkime, mes turime masyvą, šeši elementai, 3, 5, 2, 6, 4, 1, nebuvo išrūšiuoti.
Gerai, ten Šiame puslapyje daug.
Taigi, jei jus vaikinai galite peržvelgti pirmas žingsnis čia, 3, 5, 2, 6, 4, 1,
galite padalinti per pusę.
Turite 3, 5, 2, 6, 4, 1.
Jūs žinote, kad tai aren't-- jus nežinau, jei jie rūšiuojami, ar ne,
todėl jūs nuolat kad juos žemyn, per pusę, per pusę, per pusę, kol galiausiai,
turite tik vieną elementą.
Ir vienas elementas visada rūšiuojamos, tiesa?
>> Taigi, žinome, kad 3, 5, 2, 4, 6, 1, patys, yra rūšiuojami.
Ir dabar mes galime įdėti juos atgal kartu.
Taigi mes žinome, 3, 5 d.
Mes įdėti tie kartu.
Mes žinome, kad tai Rūšiuota.
Į 2 "vis dar ten.
Mes galime įdėti 4 ir 6 kartu.
Mes žinome, kad manimi rūšiuojamos, todėl mes įdėti, kad kartu.
Ir 1 yra.
>> Ir tada jūs tiesiog pažvelgti Šios dvi puselės čia.
Čia turi 3, 5, 2, 2, 3, 5.
Jūs galite tiesiog lyginti pradžioje viskas.
Nes jūs žinote, kad tai yra rūšiuojami ir jūs žinote, kad manimi rūšiuojami.
Taigi jūs neturite net turi palyginti 5, jūs tiesiog palyginti 3.
Ir 2 yra mažesnis nei 3, taip, jūs žinote, 2 turi eiti iki galo.
>> Tas pats ten.
1 m, turi eiti čia.
Ir tada, kai jūs einate įdėti šios dvi vertybės kartu,
jūs žinote, kad tai yra rūšiuojamos ir jūs žinote, kad yra rūšiuojami.
Taigi, tada 1, ir 2, 1-yra mažiau nei 2.
Tai jums pasakys, kad 1 turėtų eiti apie tai pabaigoje
net žiūri 3 arba 5.
Ir 4 Tada galite tiesiog Tikrinti, jis eina tiesiai čia.
Jūs neturite pažvelgti į 5.
Tas pats su 6.
Jūs žinote, kad 6-- jis tiesiog nereikia būti pažvelgė.
>> Ir taip tokiu būdu, esate tik sutaupyti sau
žingsnių daug, kai jūs lyginant.
Jūs neturite palyginti kas elementas su kitais elementais.
Jūs tiesiog palyginti su tų, kad jums reikia palyginti jį prieš.
Taigi, kad tipo abstrakti sąvoka.
Nesijaudinkite, jei tai ne gana pataikyti jums dar teisus.
Tačiau paprastai, tai yra kaip sujungti rūšiuoti veikia.
Klausimai, klausimai, greitai kol aš pereiti?
Taip.
>> Auditorija: Taigi jūs sakėte, kad Jūs vartojate 1-, ir tada 4, ir 6
ir įdėti jas į.
Taigi nėra those-- nėra Ieškote juos
kaip atskiri elementai, o ne kaip į visumą?
ANDI Peng: Taip.
Taigi, kas vyksta yra ta, kad jūs iš esmės
yra sukurti naują masyvo.
Taigi jūs žinote, kad čia, aš turiu dvi matricos dydis 3, tiesa?
Taigi jūs žinote, kad mano Rūšiuota masyvo turi turėti šešias elementus.
Taigi jūs tiesiog sukurti Nauja suma atminties.
Taigi jūs esate lyg yra išlaidavimas atminties,
bet tai nesvarbu nes jis toks mažas.
Taigi jums pažvelgti į 1 ir jums pažvelgti į 2.
Ir jūs žinote, kad 1 yra mažesnis kaip 2.
Taigi jūs žinote, kad 1 turi eiti iš visų tų pradžia.
>> Jums net nereikia reikia peržvelgti 3 ir 5.
Taigi jūs žinote, 1 eina ten.
Tada jūs iš esmės nukirsti prie 1 d.
Tai, kaip, miręs mums.
Tada mes tiesiog turime 2, 3, 5, ir tada 4 ir 6.
Ir tuomet jūs žinote, kad jums lyginti 4 ir 2,
Oi, 2 reikia eiti ten.
Taigi jūs pūkštelėti į 2 žemyn, galite pjaustyti ant kojų.
Taigi jūs tiesiog turite 3 ir į 4 ir 6 5.
Ir jūs tiesiog laikyti jį išjungti kapojimo kol jūs įdėti juos į masyvą.
>> Auditorija: Taigi jūs tiesiog visada lyginant [nesigirdi]?
>> ANDI Peng: Būtent.
Taigi šia prasme, jūs tik lyginant, iš esmės,
vienas skaičius prieš kitą numerį.
Ir todėl, kad jūs žinote, kad jis rūšiuojamos, jums
neturi atrodyti per visus numerius.
Jums tereikia pažvelgti į pirmąją.
Ir tada galite tiesiog pūkštelėti juos žemyn, nes jūs žinote,
jie priklauso, kur jie turi priklausyti.
Taip.
Geras klausimas.
>> Ir tada, jei kas nors iš jūsų yra šiek tiek ambicinga,
nedvejodami pažvelgti į šį kodą.
Tai iš tikrųjų fizinis įgyvendinimas
kaip mes norėtume parašyti suliejimo rūšiuoti.
Ir matote, tai labai trumpas.
Bet idėjos atsilieka tai yra gana sudėtinga.
Taigi, jei jūs manote, kaip piešimo tai iš į savo namų vakarą, nedvejodami.
>> GERAI.
Dovydas taip pat perėjo tai paskaita.
Kas yra geriausias atvejis katilas, blogiausio atvejo katilas,
ir numatomi katilas iš merge rūšiuoti?
Pora sekundžių galvoti.
Tai yra gana sunku, tačiau natūra intuityvus, jei jūs manote apie tai.
Gerai.
>> Auditorija: Ar blogiausiu atveju N log N?
ANDI Peng: Būtent.
Ir kodėl jis n log n.
>> Auditorija: Ar ne jį, nes jis tampa eksponentiškai greičiau,
todėl tarsi Ši funkcija vietoj tiesiog yra n
kvadrato ar kažkas?
ANDI Peng: Būtent.
Taigi priežastis, kodėl Trukmė apie tai yra n Prisijungti
n yra because-- ką jūs daro visų šių žingsnių?
Jūs esate tik kapoti jį per pusę, tiesa?
Ir todėl, kai mes darote prisijungti, visi, kad jis tai daro
yra dalijant problemą pusę, per pusę, per pusę, daugiau puselės.
Ir šia prasme, jūs galite natūra nuo panaikinti tiesinę modelį
kad mes jau naudojate.
Nes kai jūs sukapoti viskas per pusę, tai žurnalą.
Tai tiesiog matematinis būdas jam atstovaujantys asmenys.
>> Ir galiausiai, pabaigoje, jūs tiesiog padaryti vieną paskutinį perdavimo per
įdėti juos visus, kad, tiesa?
Ir todėl, jei jums tereikia Tikrinti vieną dalyką, tai n.
Ir todėl jūs rūšies dauginant du kartu.
Taigi, tai, kaip jūs turite, kad galutinis patikrinti n žemyn čia su n log
čia.
Ir jei jūs daugintis jiems, kad manimi n log n.
>> Ir todėl geriausias ir blogiausią ir tikėtinų visi n log n.
Taip pat kaip ir kitos panašaus.
Tai tarsi atrankos rūšiuoti į prasme, kad ji
Nesvarbu, koks jūsų sąrašas, tai tiesiog vyksta
daryti tą patį kiekvieną kartą.
GERAI.
Taigi, kaip jūs vaikinai galite pamatyti, nors Į rūšių, kad mes Dingo through-- n
kvadrato, tai nėra labai veiksminga.
Ir net tai n log n yra ne pats efektyviausias.
Jei vaikinai yra smalsus, ten tarsi mechanizmai
kad yra toks efektyvus, kad jie beveik esmės butas aplinką.
>> Jūs turite šiek tiek log n-aisiais.
Jūs turite šiek tiek žurnalo log n-aisiais.
Mes nelieskite ant jų Šioje klasėje dabar.
Bet jei jūs vaikinai yra smalsus, nedvejodami google, kas
Efektyviausi rūšiavimo mechanizmai.
Aš nežinau, yra keletas tikrai juokingi tie,
like-- ten tikrai juokingi tie, kurie žmonės.
Ir jums įdomu, kaip jie kada nors galvojote, kad.
Taigi google, jei turite kokių nors atsarginių laiku,, kas yra kai kurie juokingi būdai
kad people-- taip pat Efektyviausi ways-- žmonės
galėjusi įgyvendinti rūšių.
GERAI.
Ir čia tik patogus mažai diagrama.
Aš žinau, jūs visi, iki tos viktorinos 0, bus jūsų kambaryje tikriausiai bando
įsiminti, kad.
Štai gražus ten jums vaikinai.
Tik nepamirškite logika, kad made-- kodėl šie skaičiai buvo pasikartojimui.
Jei jūs visada prarasti, tiesiog įsitikinkite, Įsitikinkite, kad žinote, ką rūšių yra.
Ir jūs galite paleisti per juos savo proto
išsiaiškinti, kodėl tie atsakymai yra tie atsakymai.
>> Gerai.
Taigi mes ketiname pereiti ant, galiausiai, paieškai.
Kadangi, kaip tie iš jūsų, kurie skaityti pset,
paieška taip pat yra dalis šią savaitę problema rinkiniai.
Jūsų bus paprašyta įgyvendinti dviejų tipų paieškas.
Vienas iš jų yra tiesinis paieškos ir Vienas iš jų yra dvejetainis paieškos.
>> Taigi linijinis paieška yra gana lengva.
Jūs tiesiog norite ieškoti elementą iš sąrašo, pamatyti, jei jūs jį gauti.
Jūs tiesiog turite pakartoti per.
Ir jeigu ji yra lygi kažką, galite tiesiog grąžinti ją, tiesa?
Tačiau vienas, kad mes dauguma domina kalbame apie
yra dvejetainis paieškos, teisė, kuri yra Skaldyk ir valdyk mechanizmą, kuris
Dovydas demonstruodamas paskaita.
>> Prisiminti telefonų knygos pavyzdį kad jis išlaiko auklėjant,
vienas, kad jis tipo kovojo ant šio pastaruosius metus šiek tiek,
kur padalinti problemą per pusę, per pusę, per pusę, vėl ir vėl,
kol rasite tai, ką jūs ieškote?
Ir jūs sutvarkysite dinaminis iš kad taip pat.
Ir jūs galite pamatyti, tai žymiai efektyviau
nei bet kokio kito tipo paieška.
>> Taigi taip, kad mums būtų eiti apie įgyvendinant dvejetainį paiešką
yra, jei mes turėjome masyvą, indeksas 0 iki 6, septynių elementų,
galime pažvelgti centru, right-- Atsiprašome, jei mūsų klausimą first--
jei norime paprašyti klausimą, ar masyvas yra 7 elementą,
Akivaizdu, kad yra žmones, ir turintys tokia maža matrica, tai lengva mums
pasakyti "taip".
Bet būdas įgyvendinti dvejetainis Paieška būtų ieškoti per vidurį.
>> Mes žinome, kad 3 indeksas yra viduryje, nes mes
žinau, ten yra septyni elementai.
Ką 7, padalytą iš 2?
Jūs galite nukirsti, kad papildomą 1 d.
Jūs turite 3 per vidurį.
Taigi yra masyvas 3 yra lygus 7?
Tai nėra, teisę?
Tačiau mes galime padaryti patikrinimų pora.
Ar masyvas 3 mažiau kaip 7 arba yra masyvas 3 didesnis nei 7?
>> Ir mes žinome, kad tai mažiau kaip 7.
Taigi mes žinome, kad, oi, ji turi negali būti kairėje pusėje.
Žinome, kad ji turi būti teisinga puse, tiesa?
Taigi, mes galime tik nukirsti pusę masyvo.
Mes net turime pažvelgti į jį daugiau.
Nes mes žinome, kad pusė mūsų problem--
mes žinome, kad atsakymas yra teisė pusė mūsų problema.
Taigi mes tik pažvelgti, kad dabar.
>> Taigi dabar mes pažvelgti į vidurys, kas liko.
Šis indeksas 5.
Mes darome tą patį vėl patikrinti ir mes matome, kad tai mažesnė.
Taigi, mes tikimės, kad to kairę.
Ir tada mes matome, kad patikrinimą.
Ar masyvo vertė 4 puslapis lygus 7?
Tai yra.
Taigi, mes galime grąžinti tiesa, nes mes nustatėme, kad mūsų sąraše vertę.
Ar kaip aš per tai prasminga visiems?
GERAI.
Aš duosiu jums vaikinai gal, pavyzdžiui, trijų, keturių minučių išsiaiškinti,
Kaip Pseudocode tai.
>> Taigi įsivaizduokite, aš paklausiau jūsų parašyti funkcija vadinama paiešką (), kad grįžo
vertės, Būlio vertė, tai buvo tiesa ar false-- patinka,
tiesa, jei radote vertė, false, jei tu negali.
Ir tada tu buvai priimtas vertės Jums
ieško į vertybes, kurios yra array-- oh, aš tikrai įdėti
kad ne vietoje.
GERAI.
Anyways, kad turi būti buvo į vertybių dešinėje.
Ir tada int n yra skaičius elementų šioje masyvo.
Kaip jūs einate apie bando į Pseudocode kad problemą?
Aš duosiu jums vaikinai, kaip tris minutes padaryti.
Ne, manau, kad ten jei jums reikia Taip, ten yra vienas teisingas čia.
Auditorija: Ar galiu?
ANDI Peng: Taip, aš turiu jums.
Ar tai darbo?
Gerai.
>> GERAI.
Visos teisės vaikinai, mes ketina pažaboti jį.
GERAI.
Taigi manyti, mes turime tai puikus mažai masyvas su n verčių jį.
Aš ne padaryti linijas.
Bet kaip mes einame apie bando rašyti tai?
Ar kas nors nori man pirmą eilutę?
Jei norite suteikti man Pirmoji eilutė šio Pseudocode.
>> Auditorija: [nesigirdi]
Auditorija: Jūs norėtumėte į pakartoti through--
Auditorija: Tiesiog kitą kilpą?
Auditorija: --for.
>> ANDI Peng: Taigi tai vienas šiek tiek sudėtinga.
Pagalvokite about-- norite nuolat veikia šio ciklo
vėl ir vėl, kol kada?
>> Auditorija: Iki [nesigirdi] vertė yra lygi tai vertei.
ANDI Peng: Būtent.
Taigi jūs iš tikrųjų galite tik write-- mes netgi galite jį supaprastinti daugiau.
Mes galime tik daryti, o kilpa, tiesa?
Taigi, galite tiesiog loop-- mes žinome, kad tai nors.
Bet dabar, aš ruošiuosi pasakyti "kilpa", - per ką?
Ciklas until-- kas Mūsų baigiasi liga?
Manau, kad tai išgirdo.
Aš girdėjau kažkas pasakyti.
>> Auditorija: Vertybės yra lygus vidurį.
ANDI Peng: Pasakykite jį dar kartą.
Auditorija: Arba, kol vertė jūs ieškote
už yra lygus vidutinis dydis.
>> ANDI Peng: Ką daryti, jei tai ne ten?
Ką daryti, jei vertė jūs ieškote už faktiškai nėra šiame masyve?
Auditorija: Jūs return 1.
>> ANDI Peng: Bet ką mes norime kilpa, kol jei mes turime būklę?
Taip.
>> AUDITORIJA: Iki ten tik viena vertė?
ANDI Peng: Jūs galite kilpa until--, kad jūs žinote, kad esate
ketinate turėti max vertę, tiesa?
Ir jūs žinote, kad jūs ketinate turėti min vertę, tiesa?
Nes taip, kad kažkas Aš pamiršau pasakyti anksčiau,
kad kažkas tai kritiškai dvejetainis paieškos
yra tai, kad jūsų masyvas jau rūšiuojamos.
Kadangi nėra daryti būdas tai, jei jie tiesiog atsitiktinių dydžių.
Jūs nežinote, jei vienas yra didesnis nei kita, teisę?
>> Taigi jūs žinote, kad jūsų max ir Jūsų min esate čia, tiesa?
Jei jūs ketinate būti koreguojant Jūsų max jūsų min ir mid--
tegul tiesiog prisiimti savo Vidutinės vertės yra teisinga here--
jūs ketinate iš esmės kilpa, kol jūsų minimumas yra
apie tą patį kaip savo max, į dešinę, arba Jei jūsų max yra ne tas pats, kaip jūsų min.
Teisė?
Nes kai tai atsitiks, jūs žinote, kad jūs galų gale nukentėjo tą pačią vertę.
Taigi jūs norite kilpą, kol savo min yra mažesnis arba lygus to-- Oi,
ne mažiau nei arba lygus, Kitas būdas around-- max.
>> Ar tai prasminga?
Aš paėmė keletą bando gauti šią teisę.
Bet kilpa, kol jūsų max iš esmės yra beveik mažiau
nei arba lygus savo minimumo, tiesa?
Štai tada jūs žinote, kad jūs susiliejęs.
AUDITORIJA: Kada jūsų maksimalus vertė būti mažesnis nei minimalų?
ANDI Peng: Jei norite išsaugoti pritaikant jį, kuris
yra tai, ką mes ketiname reikia daro tai.
Ar tai prasminga?
Minimalus ir maksimalus yra tik sveikieji skaičiai, kad mes tikriausiai
ketinate norite sukurti išlaikyti stebėti, kur mes ieškome.
Kadangi masyvo egzistuoja nepriklausomai nuo to, ką mes darome.
Kaip mes nesame iš tikrųjų fiziškai atkirtimas masyvo, tiesa?
Užtenka tik koreguojant kur mes ieškome.
Ar tai prasminga?
>> Auditorija: Taip.
>> ANDI Peng: Gerai.
Taigi, jei tai už mūsų kilpa sąlyga, ką mes norime viduje šio kilpa?
Ką mes ketiname būti nori daryti?
Taigi dabar, mes turime max ir min, tiesa,
tikriausiai sukūrė čia kažkur.
Mes ketiname tikriausiai nori rasti vidurį, tiesa?
Kaip mes ketiname būti sugebėti rasti vidurį?
Koks mathematical--
Auditorija: Max plius min padalinta iš 2.
ANDI Peng: Būtent.
Ar tai prasminga?
Ir vaikinai, kodėl mes buvo ne tik use-- kodėl mes tai padarė
užuot tiesiog n padalytą iš 2?
Tai todėl, kad n yra, vertės kad ketina likti tas pats.
Teisė?
Bet kaip mes reguliuoti mūsų minimalios ir didžiausios vertės, jie ketina pakeisti.
Ir kaip rezultatas, mūsų viduriniosios ketina per keistis.
Štai kodėl mes norime tai padaryti čia.
GERAI.
>> Ir tada, kad dabar mes pastebėjome our-- taip.
>> Auditorija: Tiesiog greitai question-- kai jūs kalbate MIN ir MAX,
mes prielaidą, kad jis jau rūšiuojami?
>> ANDI Peng: Taip, tai iš tikrųjų sąlyga dvejetainis paieškos,
kad jūs turite žinoti, kad manimi rūšiuojami.
Kuris yra, kodėl rūšiuoti, jums reikia parašyti savo problema nustatyti prieš jūsų dvejetainiai paiešką.
GERAI.
Taigi dabar, kad mes žinome, kur mūsų Mediana yra, ką jūs norite daryti čia?
>> Auditorija: Mes norime palyginti kad į kitą vieną.
ANDI Peng: Būtent.
Taigi, jūs ketinate palyginti Vidutinės vertės, tiesa?
Ir ką tai pasakyti mus, kai mes palyginti?
Ką mes norime daryti po to?
>> Auditorija: Jei vertė yra didesnė nei vidurio, mes norime nukirsk ją.
ANDI Peng: Būtent.
Taigi, jei reikšmė yra didesnė nei vidurio, mes
ketinate norite pakeisti jų mažiausias ir Maxes, tiesa?
Ką mes norime pakeisti?
Taigi, jei mes žinome vertė yra kažkur čia, ką jūs, mes pakeisti?
Mes norime pakeisti mūsų Minimalus būti vidurio, tiesa?
Ir tada kitur, jei tai šiame pusę, ką mes norime pakeisti?
>> AUDITORIJA: Jūsų maksimali.
ANDI Peng: Taip.
Ir tada jūs esate tik ketina išlaikyti kilpų, tiesa?
Nes dabar, po vienos iteracijos per, jūs turite maks čia.
Ir tada jūs galite perskaičiuoti viduryje.
Ir tada jūs galite palyginti.
Ir jūs ketinate nesustoti kol minučių ir Maxes
jau iš esmės sutapo.
Ir tai, kai jūs žinote, kad jūs nukentėjo jo pabaigos.
Ir nors jūs ją radau ar turite ne šiuo klausimu.
>> Ar tai prasminga visiems?
GERAI.
Tai gana svarbu, nes jūs turėsite
rašyti tai jūsų kodas vakarą.
Bet jūs vaikinai turi gana geras jausmas, ką turėtų daryti,
kuris yra geras.
GERAI.
Taigi mes turime apie septynis minučių liko skyrių.
Taigi mes ketiname kalbėti apie tai pset, kad mes daryti.
Taigi pset yra padalintas į dvi dalis.
Pirmoji pusė apima įgyvendinti randa
kuriame rašote linijinis paiešką A dvejetainis paieškos, ir rūšiavimo algoritmas.
>> Taigi, tai yra pirmasis kartą iš pset kur
mes būsime duoti jums, vaikinai, kas vadinama paskirstymo kodas, kuris yra kodas
kad mes iš anksto raštu, bet tiesiog paliko keletą vienetų išjungtas
jums baigti rašyti.
Taigi jūs vaikinai, kai jūs žiūrite į tai kodas, galite gauti tikrai išsigandęs.
Jei jūs tik norite, ahh, aš nežinau, kas tai daro,
Aš nežinau, kaip, kad atrodo taip sudėtinga, ahh, atsipalaiduoti.
Viskas gerai.
Skaityti spec.
SPEC jums paaiškins tiksliai Ką visas šias programas darai.
>> Pavyzdžiui, generate.c yra programa, kad ateis su savo pset.
Jūs neturite iš tikrųjų turi jį liesti, bet Jūs turite suprasti, ką jis daro.
Ir generate.c, visa tai daro, yra arba generuoti atsitiktinius numerius
arba galite suteikti jai sėklą, tarsi iš anksto susitaręs numeris, užtrunka,
ir jis generuoja daugiau numerių.
Taigi ten konkretus būdas įgyvendinti generate.c, kurioje
galite tiesiog padaryti skaičių krūva jums išbandyti savo kitus metodus toliau.
>> Taigi, jei norite, už Pavyzdžiui, išbandyti savo randa,
jūs norite paleisti generate.c, generuoti numerius krūva,
ir tada paleisti savo pagalbininkų funkciją.
Jūsų pagalbininkai funkcija yra kur esate iš tikrųjų fiziškai rašyti kodą.
Ir manau, pagalbininkų, kaip bibliotekos failą rašote, kad radinys skambina.
Ir taip per helpers.c, jums padaryti paieškos ir rūšiavimo.
>> Ir tada jūs ketinate iš esmės tiesiog įdėti juos visus kartu.
SPEC parodys jums, kaip įdėti, kad komandinėje eilutėje.
Ir jums bus suteikta galimybė išbandyti, ar ne tavo rūšiuoti ir paieška dirba.
Saunus.
Ar kas nors jau pradėjo ir kilo problemų ar klausimų
jie dabar su tai?
GERAI.
>> Auditorija: Palaukite.
Aš turiu klausimą.
>> ANDI Peng: Taip.
>> Auditorija: Taigi aš pradėjau daryti linijinis paiešką helpers.c
ir tai nebuvo tikrai dirba.
Bet vėliau, aš sužinojau, mes tiesiog turite jį ištrinti ir padaryti dvejetainis paiešką.
Taigi ar tai svarbu, jei jis neveikia?
>> ANDI Peng: Trumpas atsakymas yra ne.
Bet kadangi mes not--
Auditorija: Bet Niekieno iš tikrųjų tikrinimą.
ANDI Peng: Mes niekada ketiname pamatyti, kad.
Bet jūs tikriausiai norite padaryti Įsitikinkite, kad jūsų paiešką veikia.
Nes jei tavo linijinis Paieška neveikia,
tada šansai yra jūsų dvejetainis Paieška nesiruošia dirbti taip pat.
Kadangi jūs turite panašios logika abu.
Ir ne, tai tikrai ne klausimas.
Taigi vieninteliai jūs pasukite Åre rūšiuoti ir dvejetainis paieškos.
Taip.
>> Ir taip pat, iš vaikams daug buvo bando surinkti helpers.c.
Jūs neprisijungęs tikrųjų leido tai padaryti, nes helpers.c
neturi pagrindinę funkciją.
Ir todėl jūs turite tik būtų faktiškai sudarant
generuoti ir sužinoti, nes rasti kvietimus helpers.c ir pagal ją funkcijas.
Taigi, kad daro derinimo į užpakalis skausmas.
Bet tai, ką mes turime daryti.
Auditorija: Jūs tiesiog padaryti visi, tiesa?
ANDI Peng: Jūs galite tiesiog kad visi taip, taip.
GERAI.
Taigi, kad viskas, kalbant apie tai, ką pset klausia jūs visi daryti.
Jei turite kokių nors klausimų, nedvejodami nemokama paklausti manęs po skyriuje.
Aš būsiu čia, kaip, 20 min.
>> Ir Taip, pset s tikrai ne todėl, kad blogai.
Vaikinai turėtų būti OK.
Tai, atlikite gaires.
Rūšis turėti jausmą, logiškai, ką turėtų būti vyksta ir jums bus gerai.
Ar ne per daug baisu.
Yra kodo daug jau parašyta ten.
Ar ne per daug bijo, jei jūs neturite suprasti, ką visa tai reiškia.
Jei tai daug, tai visiškai gerai.
Ir atvykti į darbo valandomis.
Mes padėsime jums pažvelgti.
>> Auditorija: Su papildoma funkcijos, mes pažvelgti tiems iki?
>> ANDI Peng: Taip, tie, kurie kodą.
Per 15 žaidimo pusę nuo tai jau parašyta jums.
Taigi šios funkcijos yra jau kodu.
Yep.
Gerai.
Na, kuo geriausios kloties.
Tai bjaurus dieną.
Taigi tikiuosi jus vaikinai nesijaučia per blogai apie buvimo viduje ir kodavimo.