[Predvaja glasba] 

ANDI PENG: Dobrodošli v tednu 3 oddelka. Hvala, fantje, za vse, ki prihajajo na ta zgodnejši čas že danes. Imamo lepo, malo intimna danes skupina. Torej, upam, da bomo prišli do konča, morda, zgodaj, malo zgodaj danes. Tako hitro, samo nekateri Sporočila za dnevni red danes. Preden začnemo, smo bo šele iti čez nekaj kratkih logistične zadeve, pset Vprašanja, debrief, take stvari. In potem bomo potopite v desno. Bomo uporabili razhroščevalnik imenovano GDB za začetek debunking našo kodo, ki David pojasnjeno v predavanju drugi dan. Mi bomo šli čez štiri vrste vrst. Bomo šli nad njimi precej hitro ker oni so precej intenzivna. Toda vemo, da vse drsi in Izvorna koda so vedno na spletu. Torej, vas prosimo, na vaše podatke, da pojdi nazaj in poglej na to. 

Šli bomo skozi asimptotska zapis, ki je samo fancy način rekel "runtimes" kjer imamo veliko O, ki je David je pojasnjeno v predavanju. In imamo tudi Omega, ki je je spodnja meja runtime. In bomo govorili malo bolj poglobljeno glede kako se ti delo. In nenazadnje, bomo šli preko binarnega iskanja, saj veliko vas, ki imajo že pogledala vaše psets verjetno veste, da da je vprašanje, ki je v vašem pset. Tako boste vsi srečni da pokrivamo to danes. 

In nenazadnje, na vaš povratne oddelek, sem dejansko levo približno 15 minut pri konec bi samo iti čez logistika pset3, vsa vprašanja, Mogoče malo smernic, če hočete, preden začnemo programiranja. Torej poskusimo priti skozi material zelo hitro. In potem bomo lahko preživeli nekaj časa ob več vprašanj za pset. V REDU. 

Hitro, tako da je le nekaj Sporočila preden začnemo danes. Prvič, dobrodošli k temu, da je preko dveh vaših psets. Ogledal sem si na your-- ja, dajmo dobil aplavz za to. Pravzaprav sem bil res, res navdušena. Jaz ocenjena prvo pset za vas Prejšnji teden in vidva storila neverjetno. 

Style je bil na mestu poleg nekaj pripomb. Poskrbite, da boste vedno komentiral svojo kodo. Ampak tvoji psets bili na mestu. In ne odnehaj. In to je dobro za greder do glej, da se vidva dajanje v toliko truda v vašem slogu in vaš design v kodi da bi radi, da vidiš. Tako da sem mimo po moje hvaležnosti za ostale ZU. 

Vendar pa obstajajo Nekaj ​​debrief vprašanja Rad bi šel čez, da bi tako moje življenje in veliko drugih TAS "živi malo lažje. Najprej sem opazil to mimo week-- koliko od vas so bili teče check50 na svojo kodo pred vami predložiti? V REDU. Torej, vsi bi morali početi check50, because-- secret-- smo dejansko teči check50 kot del naše resničnosti skripte za testiranje kodo. Torej, če je vaša koda ni check50, po vsej verjetnosti, to je verjetno, da bo ne naše ček kot dobro. Včasih si fantje imate prave odgovore. Tako kot v požrešen, nekateri imate prave številke, si izpisal nekaj dodatnih stvari. In da ekstra stvari dejansko ne opravi pregled, ker računalnik ne vem, kaj je to išče. In tako bo to šele teči skozi, vidite, da vaša proizvodnja ne ujemajo kaj pričakujemo odgovor biti, in označiti, da je narobe. 

In vem, da se je zgodilo v nekatere od vaših primerov ta teden. Zato sem šel nazaj in ročno ponovno razvrstijo kodo vsakogar. V prihodnosti, čeprav, Prosim, vas prosimo, poskrbite, da tečete preveriti 50 na kodo. Ker je to neke vrste bolečin TA bi moral iti nazaj in ročno razvrstijo vsak pset za vsak eno, malo zamudil instance. Torej nisem vzlet nobenih točk. Mislim, da sem odpeljal morda eden ali dva za oblikovanje. V prihodnosti, čeprav, če ste ni check50, Točke bodo sprejeti off za pravilnost. 

Poleg tega so psets ob petkih opoldne. Mislim, da je sedem minut pozno odlog plačila, ki vam daje. Per Harvard časa, oni dovoljeno bilo sedem minut prepozno za vse. Torej, tukaj na univerzi Yale, bomo upoštevati tudi to. Ampak precej, ob 12:07, če vaš pset ni, to se dogaja, da se označi kot prepozno. In tako, medtem ko je označen kot prepozno, TA-- sem še vedno dogaja, da se razvrščanje vaših psets. Tako boste še vedno videli razred prikazani. Vendar pa vemo, da na konec semestra, vse poznih psets bo zgolj samodejno nastavi na ničlo računalnik. 

To smo storili iz dveh razlogov. Ena, včasih smo dobili opravičil, kot izgovore dekana, kasneje, da ne vem, o tem še ni. Tako smo želeli zagotoviti, da smo razvrščanje vse samo v primeru, kot, da sem manjka izgovora Dean je. In drugič, da v Um, lahko še vedno spusti en pset da ima celotno področje točk. In tako smo želeli razred vse vaše psets samo se prepričajte, da je vaše področje je tam in si jih poskušam. Torej, tudi če je prepozno, boste še vedno dobili kredit za obseg točk, mislim. 

Torej Nauk je zgodba, da prepričajte, da vaš psets so na čas. In če niso v na čas, vem, da to ni dobro. Ja, preden sem korak naprej, ali ima kdo vsa vprašanja v zvezi z pset povratne informacije? Ja. 

OBČINSTVO: Ste Pravimo lahko spusti eno od psets? 

ANDI PENG: Ja. Torej je skupna devet psets tekom semestra. In če imate obseg points-- tako področje je le, precej, so si poskusi problem, ste dajanje v času, ste kažejo, da ste dokazali ste prebrali spec. To je precej možnosti. In če ste izpolnjevanju obseg točk smo lahko spusti najnižja eden od polnega obsega. Tako da je v vašo korist dokončanje in poskusite vsak pset. 

Tudi upload-- če nobeden od njihovo delo, jih vse naložiti. In potem se bomo, upajmo, lahko vam nekatere od teh točk nazaj. Cool. Vsa druga vprašanja? Great. 

Drugič, pisarna hours-- nekaj Hitre opombe o uradnih ur. Torej, najprej, pridite zgodaj v tednu. Nihče ni nikoli na Uradne ure ob ponedeljkih. Christabel prišel do Uradne ure sinoči. Ja, Christabel. In kaj imamo v pisarni ur sinoči, Christabel? 

OBČINSTVO: Imeli smo sladoled. 

ANDI PENG: Torej, to je pravica, smo imeli sladoled na uradnih ur sinoči. Medtem ko vam ne morem obljubiti, da bomo imeli sladoled na uradnih ur vsak teden, kaj se ti lahko obljubim je, da bo prišlo do bistveno boljši študent razmerje TA. Tako kot zakonit, je kot tri proti ena. Ker je kontrast, ki s Četrtek, imaš približno 150 Res je poudaril, otroke in ne sladoled. In to je samo ni produktivno za vsakogar. Torej Nauk zgodbe je, pridite zgodaj na uradnih ur in dobrih stvari se bo zgodilo. 

Prav tako pridejo pripravljeni, da postavljajo vprašanja. Ti veš? Glede na to, kaj ZU, I mislim, so govorili: smo bili že par študentov ki pridejo v četrtek ob, kot, 10:50 ne, ko ste prebrali spec da kot pomagajte mi, pomagajte mi. Žal na tej točki, tam je ni veliko lahko storimo, da vam pomaga. Torej, prosim pridite zgodaj v tednu. Pridite zgodaj, da uradnih ur. Pridite pripravljeni zastaviti vprašanja. Poskrbite, da vas, kot študent, tam, kjer morate biti tako, da TAS lahko vas vodijo skupaj, ki je tisto, kar uradne ure bi moral biti dodeljen za. 

Drugič, tako da vem, profesorje radi, da nas preseneti s testi. Imel sem profesorja tiste všeč, yo, mimogrede, Zapomnite si, da vmesno imate naslednji ponedeljek. Ja, nisem vedel o tem vmesnimi. Tako da bom se, da TA da vas spominja vse to kviz 0--, saj veste, da smo CS. Zdaj, ko smo naredili nizi, dobiš zakaj je kviz 0, ne kviz 1, eh? V REDU. Oh, imam nekaj smehlja o tem. V REDU. 

Torej bo kviz 0 bo 14. oktober, če ste v oddelku ponedeljek-sreda in 15. oktober, če ste v odsek torek-četrtek. To ne velja za tiste, ki ste na Harvardu who-- Mislim, da boste vsi jemanjem kvizi na 14.. 

Torej, ja, naslednji teden, če David, v predavanju, gre, ja, da o tem Kviz naslednji teden, si vse ne bo šokiran, ker ste prišli na oddelku in veš, da je vaš kviz 0 je v dveh tednih. In bomo imeli pregled Seje in vse. Torej, ne skrbi se prestrašil za to. Vsa vprašanja before-- kakršnakoli vprašanja na vseh glede logističnih vprašanj, razvrščanje, uradne ure, profili? Ja. 

OBČINSTVO: Torej je kviz bo v predavanju? 

ANDI PENG: Ja. Torej kviza, mislim, da je 60 minut dodeljene v tem terminu da boste vzemite v predavalnici. Torej vam ni treba priti v na, kot je, naključni 7:00 PM. To je vse dobro. Ja. Cool. 

V redu. Torej bomo uvesti koncept za vas ta teden, da je David že nekako od dotaknila v predavanju to čez teden dni. To se imenuje GDB. In koliko od vas, medtem ko je v potek pisanje psets, so opazili velik gumb, ki pravi, "Debug" na vrhu IDE? V REDU. Torej, zdaj bomo dejansko dobili izkopala skrivnost, kaj ta gumb dejansko počne. In zagotavljam vam, da je lepa, lepa stvar. 

Torej, do sedaj, mislim, tam je bilo dve stvari študenti so bili običajno počeli, ko debugging psets. Ena, so bodisi dodate v printf () - tako vsakih nekaj vrstic, so dodali v printf () - oh, kaj je ta spremenljivka? Oh, kaj je ta spremenljivka now-- in si nekako videti napredovanje vaše kode, saj teče. Ali druga metoda otroci storiti, je, da samo napisati celotno stvar in potem gredo takole na koncu. Upam, da to deluje. Zagotavljam vam, GDB je bolje kot oba od teh metod. Ja. Torej, to bo vaš novi najboljši prijatelj. Ker je čudovita stvar ki vizualno prikazuje oba kaj je vaša koda počne na določeni točki kot tudi kar vse si spremenljivke se prevažajo, všeč, kaj so njihove vrednote, na tej določeni točki. In na ta način, si lahko res nastavite prekinitvene točke v kodi. Lahko teči skozi linijo po liniji. In GDB bo samo še za vi, prikazana za vas, kaj vse vaše spremenljivk so, kaj počnejo, kaj se dogaja v kodeksu. In na tak način, da je toliko lažje videti kaj namesto dogaja z printf-ing ali zapišete vaše izjave. 

Torej bomo naredili zgled za to kasneje. Torej, to se zdi malo povzetek. Brez skrbi, bomo storili primere. In tako v bistvu tri največje, najbolj uporabljenih funkcij, boste morali v GDB so Next, korak več, in Korak v gumbov. Jaz grem čez glavo tam, pravzaprav prav zdaj. 

Torej, vi vsi lahko videli, da ali bi moral povečati malo? V zadnji, lahko vidite, da je? Naj povečavo? Samo malo? OK kul. Tam gremo. V REDU. 

Torej imam tukaj, moji izvedba za požrešen. In medtem ko je veliko vaju napisal požrešen v while form-- da je povsem sprejemljiv način, da to it-- drug način za to je, da preprosto razdeliti v modulu. Ker potem lahko imate vrednost, nato pa imajo svojo preostanek. In potem si lahko samo jo dodajte vse skupaj. Ali logiko, kaj delam tukaj smisla za vsakogar, preden začnemo? Recimo? Cool. Great. To je zelo seksi kos kode, bi rekel. Kot sem rekel, David, v predavanje, čez nekaj časa, boste vsi začeli videvati kodo kot nekaj, kar je lepo. In včasih, ko vidiš lepo kodo, to je tako čudovit občutek. 

Torej kljub temu, medtem ko je ta številka, je zelo lepa, ne deluje pravilno. Torej, kaj je teči check50 o tem. Preverite 50 20-- OOP. 2? Je to pset2? Ja. Oh, pset1. V REDU. Tako smo teči check50. 

In kot lahko vi vidite tukaj, to je ni nekaj primerov. In za nekatere od vas, v seveda počne tvoj problem sklopov, ste kot, ah, zakaj se ne da delati. Zakaj je delal za nekatere Vrednosti drugih pa ne? No, GDB se dogaja, da vam pomaga ugotoviti zakaj ti vnosi niso bili zaposleni. 

V REDU. Torej, da vidimo, eno od pregledih sem bil zatem check50 je vhodna vrednost 0,41. Tako je pravilen odgovor, da je morate biti pridobivanje je 4. Toda namesto da bi tisto, kar sem tiskanje je 3-n, ki je napačna. Torej, kaj je samo teči to ročno, samo poskrbite, da je check50 deluje. Naredimo ./greedy. Ups, moram narediti pohlepni. Tam gremo. Zdaj ./greedy. 

Koliko dolguje? Naredimo 0,41. In ja, vidimo tukaj da je prikazovanje 3 ko je pravilen odgovor, Dejansko bi moral biti 4. Torej, kaj je vstop GDB in videli, kako lahko greste o določitvi ta problem. 

Torej, prvi korak v Vedno razhroščevanje kodo je, da nastavite prekinitveno točko, ali je točka, na kateri ste želijo računalnika ali razhroščevalnik za začetek gledaš. Torej, če ne boste res vedo, kaj je tvoj problem, Ponavadi je tipična stvar, ki smo želeli storiti, je, da našemu prelomne točke na glavni. Torej, če lahko vi to videli rdeči gumb tam, Ja, to me je nastavljanju Ustavljanje za glavno funkcijo. Sem kliknite to. 

In potem sem lahko šel na moj gumb Debug. Sem udaril ta gumb. Naj povečavo nazaj ven, če bom lahko. Tam gremo. Torej imamo tu, na plošči na desni strani. Žal mi je, fantje v hrbtu, vi ne morem videti zelo dobro. Ampak v bistvu, vse ta pravica plošča počne se sledenja tako poudarjeno linija, ki je linija kode da je računalnik trenutno izvaja, kakor tudi vse vaše spremenljivk tukaj. 

Torej imaš centov, kovance, n, Vse razglašena za različne stvari na tej točki. Brez skrbi, saj imamo dejansko ne jih initialized na vseh spremenljivk še. Torej, v vašem računalniku, si Računalnik je samo videti, oh, 32.767 je bila nazadnje uporabljali funkcijo te pomnilniškega prostora v mojem računalniku. In tako, da je, kjer je trenutno centov. Ampak ne, da ko enkrat zaženete kodo, to bi morala postati inicializiran. 

Torej, pojdimo skozi črto, ki jo linija, kaj se dogaja tukaj. V REDU. Torej, tukaj so trije gumbi, da sem samo pojasnil. Imate igrati, ali funkcijo Run, gumb, imate Korak gumb nad, in imate tudi korak v gumb. In v bistvu, vse tri jim pojdite skozi kodo in različne stvari. 

Torej ponavadi, ko ste debugging, ne želimo, da samo hit Predvajaj, ker igra bo samo teči kodo do konca tega. In potem ne bo dejansko vedo, kaj je tvoj problem je razen če ste nastavili več prelomnih točk. Če ste nastavili več mejne vrednosti, To bo šele samodejno teči od enega mejnimi vrednostmi, na naslednjo, na naslednjo. Ampak v tem primeru, ki smo jih samo, da je eden, ker smo želijo delati naš način od zgoraj navzdol proti dnu. Torej bomo prezreti, da je gumb zdaj za namene tega programa. 

Torej je korak nad funkcijo samo koraki nad vsako posamezno vrstico in vam pove, kaj računalnik počne. Step v funkciji gre v dejanske funkcije da je na vašem vrstico kode. Tako na primer, kot printf (), da je funkcija, kajne? Če sem želel fizično korak v (funkciji printf), Jaz bi dejansko šel v kosu številka, kjer se je printf () pisno in videli kaj se dogaja tam. 

Vendar je običajno, predpostavimo, da koda, ki vam daje deluje. Predpostavljamo printf () deluje. Domnevamo, da GetInt () deluje. Tako da ni potrebe, da korak v teh funkcij. Ampak, če je nalog da ste sami napisali ki ga želite preveriti izvedeti, kaj se dogaja, bi si želeli, da okrepijo v tej funkciji. 

Torej, zdaj smo le, da bo korak nad tem delom kodeksa. Torej, poglejmo. Oh, print, "Oh hai, kako veliko sprememb dolguje? " Mi ne skrbi. Vemo, da se delajo, tako da stopimo nad njim. 

Tako n, ki je naša plovec da smo jih initialized-- ali declared-- na vrhu, smo zdaj ki je enaka da GetFloat (). Torej, kaj je korak čez to. In mi vidimo na dno tukaj, program me spodbudilo k vhodu vrednost. Torej, kaj je vhod vrednost, ki jo želimo za testiranje tod ki je 0,41. Great. 

Torej, zdaj N- storiti vidva glej tu, na bottom-- je stored-- ker smo še niso zaokrožene, da je shranjene v tem, kot velikan plovec, ki je ,4099999996, ki je dovolj blizu, da se naše namene, prav zdaj, na 0,41. In potem bomo videli kasneje, kot smo še naprej krepi nad programom, potem tukaj je n postala zaokrožen in centov je postala 41. Great. Tako smo vedeli, da je delo naše zaokroževanja je. Vemo, da imamo pravilno število centov, tako vemo, da je to ni res problem. 

Torej bomo še naprej krepi na v tem programu. Gremo tukaj. In tako po tem vrstico kode, smo bi morali vedeti, koliko četrtine imamo. Stopimo čez. In vidiš, da ne, v resnici, ima eno Četrtina ker smo odšteli 25 od naše začetne vrednosti 41. In imamo 16 levo za naše centov. 

Ali vsi razumejo, kako Program stopa skozi in zakaj je centov postala 16 in zakaj, zdaj, kovanci postala 1? Vsakdo je po tej logiki? Cool. Tako te točke je delovnega programa, kajne? Vemo, da počne točno kar smo jo želeli. In nismo dejansko morali natisniti, oh, kaj je centov na tej točki, kaj je kovance na tej točki. 

Nadaljujemo skozi program. Korak čez. Cool. Mi gremo čez dimes. Great. Vidimo, da je to delo off 0,10 $ za kovanec. In zdaj imamo dva kovanca. To je res. 

Gremo čez penijev in vidimo da smo krepko čez centov. Hmm, to je čudno. Tu gor na program, pa naj da so odšteti moje penijev. Morda nisem bil počne to postavo pravico. In žal, lahko vidite tukaj, ker vemo, da stopamo preko linij 32 in 33, da je, kjer naš program nepravilno imeli spremenljivke teči. Tako smo lahko ogledate in videli, oh, Jaz odšteje centov tukaj, ampak nisem dejansko dodal na moj kovanec vrednosti. Jaz sem dodal, da centov. In ne želim, da se doda centov, želim dodati kovancev. Torej, če bomo spremenili, da kovanci, imamo delovni program. Ne morem teči check50. Lahko samo izhod iz GDB pravice tukaj in nato ponovno zaženite check50. Jaz bi to samo naredi. Moram narediti pohlepni. 0.41. In tukaj, to je tiskanje ven pravilen odgovor. 

Tako da lahko vi vidite, GDB je res močno orodje za takrat, ko imamo toliko koda dogaja in toliko spremenljivk da je težko za nas, kot človek, za sledenje. Računalnik, v GDB razhroščevalnik, ima sposobnost slediti vsem. Vem, v Visionaire, vidva Morda so prizadele nekatere segmentacije napak ker ste bili teče izven meja vašega array. V primeru Cezarja, ki je točno to, kar sem tu izvajajo. 

Torej, sem pozabil, da preverite kaj bi se zgodilo, če bi niso imeli dva argumenta ukazne vrstice. Samo nisem dal v ta pregled. In zato, če sem teči Debug-- nastavim moj Ustavljanje tam desno. Vodim razhroščevanje. 

V REDU. Ja. Torej v resnici, je GDB naj da so mi povedali, da bilo segmentacija napaka tam. Ne vem, kaj se je dogajalo prav tam, ampak ko sem tekel, to je delal. Ko zaženete vrstic kode skozi in GDB lahko samo nenadoma nehal na vas, pojdi gor in poglej, kaj je rdeča napaka. To vam povem, hej, ti imel napako segmentacije, kar pomeni, da si se potrudil za dostop Prostor v matriki, ki ne obstaja. Ja. 

Torej v naslednji problem iz ta teden, vidva Verjetno bo veliko spremenljivke plava okoli. Ne boš, da se prepričate, kaj so vse to pomeni v določenem trenutku. Torej bo GDB res vam pomaga pri kipec izvedeti, kaj so vsi ki je enaka in da bi lahko videli, da je vizualno. Je kdo zmeden o tem, kako nič od tega delala? Cool. V redu. Torej, po tem smo dogaja, da se potopite desno v štiri različne Vrste vrst za ta teden. Koliko od vas, najprej od vsega, preden začnemo, Prebral celotno spec za pset3? V REDU. Ponosen sem na vas. To je kot polovici razreda, ki je bistveno več kot v preteklem času. 

Torej, to je super, ker ko govorimo o vsebini v lecture-- ali žal, v section-- rad povezati veliko, da nazaj na kaj je pset je in kako želite izvajati, da se v vašem pset. Torej, če ste prišli ob preberite spec, bo bo veliko lažje za vas, da razumete kaj sem govoril, ko sem rekel, oh hej, to je lahko res dober kraj za izvajanje te vrste. Torej tisti, ki ste prebrali spec vedeli, da kot del vašega pset, boste morali napisati tip vrste. Torej, to je lahko zelo koristno za veliko vas danes. 

Torej bomo začnete s, v bistvu je najbolj preprost tip za razvrščanje, izbira vrste. Tipična algoritem za kako bi se gremo o tem is-- David je šel skozi to all predavanje, tako da bom hitro premikati vzdolž here-- je v bistvu, si imajo spekter vrednosti. In potem se vam zdi Najmanjši razvrščeni vrednost in ti swap to vrednost z prvi neprebrani vrednost. In potem si ponavljajo s preostalim vašega seznama. 

In tukaj je vizualna razlaga o tem, kako bi to delovalo. Torej, za primer, če smo bili začeti s paleto petih elementov, indeks 0 do 4, s 3, 5, 2, 6 in 4 vrednosti postavi v array-- prav zdaj, smo šele tekoč, da prevzame da so si vsi razvrščeni ker nismo testirali drugače. 

Torej, kako bi izbor vrste delo je, da bi najprej teči skozi celoti nerazvrščenih array. To bi izbrati najmanjšo vrednost. V tem primeru, 3, desno Zdaj, je najmanjša. Pride do 5. Nope, 5 ni večja than-- ali žal, ni manj than-- 3. Torej je minimalna vrednost še 3. In potem prideš do 2. Računalnik vidi, OH, 2 manjša od 3. 2 mora zdaj biti minimalna vrednost. In tako 2 zamenjave s tem prvo vrednost. 

Torej, po eni priložnost, bomo zares videli da sta 2 in 3 zamenjala. In smo le, da bo še naprej delal to spet s preostalim matrike. Torej bomo šele teči skozi zadnje štiri indeksi array. Bomo videli, da je 3 Naslednji minimalna vrednost. Torej bomo zamenjali, da s 4. In potem smo šele tekoč, da bo teče skozi, dokler na koncu, boste priti do urejenih niz, v katerem 2, 3, 4, 5 in 6 so vse razporejene. Ali vsi razumejo logiko kako izbira nekako deluje? 

Imate le nekakšen minimalne vrednosti. Ste sledenja, kaj to je. In ko ga najdejo, ga zamenjajte s prvo vrednost v array-- ali ni prvi value-- naslednjo vrednost v matriki. Cool. 

Tako kot vaju vrste Videl je kratek pogled, bomo to psevdokoda ven. Torej, če vi v zadnji želite tvorijo skupino, vse na mizo lahko tvorijo malo partnerja, jaz grem da vam fantje kot treh minutah da samo govoriti skozi logika, v angleškem jeziku, o tem, kako bi morali biti sposobni izvajati psevdokoda napisati izbiro vrste. In tam je sladkarije. Prosim, pridi gor in dobili sladkarije. Če ste v hrbtu in želite sladkarije, sem lahko vrgel sladkarije na vas. Pravzaprav, ne you-- ohladi. Oh, oprosti. V REDU. 

Torej, če bi želeli, kot razred, pisanje psevdokoda za to, kako bi se dalo pristopiti ta problem, samo potipati prost. Jaz bom samo pojdi okoli in, v redu, vprašajte skupine za naslednjo linijo kaj bi morali delati. Torej, če hočete, da začnete off, kaj je prva stvar, storiti, ko ste poskušali izvajati način za rešitev tega programa za selektivno razvrstiti seznam? Naj samo prevzeti smo imajo niz, v redu? 

OBČINSTVO: boste želeli ustvariti nekaj nekako [neslišno], da ste teče skozi celotno paleto. 

ANDI PENG: Right. Torej boste želeli ponoviti skozi vsak prostor, kajne? Torej, super. Če hočete, da mi Naslednji line-- ja, v hrbtu. 

OBČINSTVO: Preverite jih vse za najmanjšo. 

ANDI PENG: Tukaj gremo. Zato želimo, da gredo skozi in preverite, videli, kaj je minimalna vrednost, kajne? Grem Skrajšati da "min". Kaj si fantje želijo storiti po ste našli minimalno vrednost? 

OBČINSTVO: [neslišno] ANDI PENG: Torej boste želeli prižgati s prvim tega niza, prav? To je začetek, bom povedal. V redu. Torej sedaj, da ste zamenjali prvi ena, kaj želite storiti po tem? Zdaj vemo, da je to ena tukaj mora biti najmanjši vrednost, ne? Potem imate dodaten počitek matrike, ki je razvrščen. Torej, kaj želite storiti tukaj, če vas fantje želijo, da mi naslednjo vrstico? OBČINSTVO: Torej hočeš Ponovil skozi preostanek niza. ANDI PENG: Ja. In tako kaj ponavljanjem skozi nekako pomeni, da bomo verjetno potrebovali? Kakšen tip of-- 

OBČINSTVO: Oh, dodatna spremenljivka? ANDI PENG: Verjetno drugo za zanke, kajne? Tako smo si verjetno želeli Ponovil through-- super. In potem boš šel nazaj in verjetno ponovno preverite minimum, prav? In ti boš ponavljajo , ker zank šele tekoč da teče, kajne? 

Tako da lahko vi vidite, smo samo še splošno psevdokoda kako hočemo ta program gledati. Ta Ponovil sem, kaj počnemo običajno morali napisati v našo kodo če želimo Ponovil posredno preko matrika, katera vrsta strukture? Mislim Christabel že to rekel prej. 

OBČINSTVO: A za zanko. 

ANDI PENG: A za zanko? Točno tako. Torej, to je verjetno bo za zanke. Kaj je preverjanje tukaj dogaja, da pomeni? Značilno je, da če hočeš, da preverite če je nekaj nekaj else-- 

OBČINSTVO: Če. 

ANDI PENG: An če je, kajne? In potem swap tukaj, bomo iti čez kasneje, zaradi Davida, šel skozi, da je v predavanju, kot dobro. In potem drugi Ponovil implies-- 

OBČINSTVO: Drug za zanko. 

ANDI PENG: --another za zanke, točno. Torej, če gledamo na to pravilno, smo lahko vidimo, da smo verjetno bomo potrebovali ugnezdene zanke s pogojnim izjavo v tam in potem dejansko del kode, ki je dogaja, da bi zamenjali vrednosti. Tako sem samo na splošno napisal psevdokoda kodo tukaj. In potem smo dejansko dogaja fizično, kot razred poskusite izvajati to danes. Vrnimo se v to IDE. 

Uh-oh. Zakaj je, da je not-- tam. V REDU. Žal mi je, da mi poskusite za povečavo malo več. Tam gremo. Vse delam tu sem jih ustvaril program, imenovan "Izbira / sort.c." Sem ustvaril niz devetih Vrednosti, 4, 8, 2, 1, 6, 9, 7, 5, 3. Trenutno, kot si lahko glej so neurejenega. n se bo število, vam pove količino vrednot imate v array. V tem primeru imamo devet vrednosti. In sem pravkar dobil za zanke tukaj da natisne neurejen array. 

In na koncu, imam tudi za zanko, ki jo je pravkar natisne znova. Torej teoretično, če ta program deluje pravilno, na koncu, bi morali videti natisnjen za zanko v kateri je 1, 2, 3, 4, 5, 6, 7, 8, 9 so vse pravilno v redu. 

Torej imamo našo psevdokoda tukaj. Ali kdo želel to-- sem samo bo šel vprašati za volunteers-- povej mi točno, kaj naj tip, če želimo, prvič, samo ponovitev po začetku tega niza? Kaj je vrstica kode sem Verjetno bo treba tukaj? 

OBČINSTVO: [neslišno] 

ANDI PENG: Ja, počutim brezplačno to-- žal, vas ne bi bilo treba stati up-- občutek brezplačno dvigniti svoj glas bit. 

OBČINSTVO: Za int i enaka 0-- 

ANDI PENG: Ja, dobro. 

OBČINSTVO: i je manjša od dolžine diod. 

ANDI PENG: Torej, ne moti tukaj, ker smo nimajo funkcijo, nam pove dolžina array, smo že imeli vrednost, ki shranjuje da. Prav? Druga stvar, ki vodijo v mind-- v array devetih vrednot, kaj so indeksi? Recimo samo, da je to zaporedje je od 0 do 3. Vidiš, da je zadnji Indeks je pravzaprav 3. To ni 4, čeprav je štiri vrednosti v matriki. 

Torej tukaj, moramo biti zelo previdni o kakšnem našem pogoj za dolžino se bo. 

OBČINSTVO: Ali ne bi bilo n minus 1? ANDI PENG: To se dogaja n minus 1, točno. Ali to smisel, zakaj je n minus 1, so vsi? To je zato, ker so nizi nič indeksirajo. Začnejo na 0 in vodijo do n minus 1. Ja, to je malce zapleteno. V REDU. In potem-- OBČINSTVO: Isnt'1 da že poskrbljeno, čeprav, ki ga preprosto ni rekel "manj ali enako "in samo rekel" manj kot? " 

ANDI PENG: To je Res dobro vprašanje. Torej, ja. Ampak tudi način, da smo uresničevanje pravice preverjanje, boste morali primerjati dve vrednosti. Torej si dejansko želijo pusti ", da" prazna. Ker če primerjate ta, ne boš šel imajo kaj po njej za primerjavo, da, kajne? Ja. Torej i ++. Dodajmo našim oklepajev v. Ops. Great. Torej imamo začetek naše zunanje zanke. Torej, zdaj smo verjetno želeli ustvariti spremenljivko za vodenje koloteka najmanjše vrednosti, kajne? Ali kdo želel, da mi vrstica kode, ki bi to naredil? Kaj potrebujemo, če gremo da želite shraniti kaj? 

Prav. Mogoče boljše ime za to bi be-- "temp" popolnoma works-- morda bolj primerno ime bi bilo, če želimo najmanjšo value-- 

OBČINSTVO: Min. ANDI PENG: min, pa gremo. min bi bilo dobro. In tako sem, kaj počnemo želite inicializirati za? To je malce zapleteno. Ker je prav zdaj v začnejo te matrike, niste pogledal na nič, kajne? Torej, kaj, samodejno, če smo samo na i enak 0, kaj želimo inicializacijo naša prva minimalno vrednost? OBČINSTVO: i. ANDI PENG: i, točno. Christabel, zakaj hočemo za inicializacijo na i? 

OBČINSTVO: Ker, dobro, smo se začne z 0. Zato, ker nimamo ničesar za primerjavo to naj bo minimalna koncu pa 0. 

ANDI PENG: Točno tako. Torej je ravno prav. Saj imamo dejansko ni pogledal kaj še, ne vemo, kaj je naša najmanjša vrednost. Želimo, da šele inicializirati na i, ki je trenutno, je tukaj. In kot smo še naprej pomaknil navzdol ta niz, bomo videli, da je z vsako Dodatna napadalca, i korakih. In tako je na tej točki, i je verjetno, želeli, da bi bila minimalna, ker se dogaja, da se karkoli je začetek nerazvrščene array. Cool. 

Torej, zdaj smo želeli dodati za zanke tukaj, ki je bo Ponovil skozi nesortirani ali preostanek tega niza. Ali kdo želel, da mi vrstica kode, ki bi to naredil? Hint-- kaj moramo tu dol? Kaj se dogaja, da gredo v to zanko? Ja. OBČINSTVO: Torej bi hočemo imajo drugačno celo število, ker smo teče skozi preostali array namesto i, zato morda j. 

ANDI PENG: Ja, j zveni dobro zame. Enaka? 

SKUPINA: Torej bi bilo i plus 1, saj ste začeli na naslednji vrednosti. In potem na end-- tako spet, j manj kot n minus 1 in nato j ++. ANDI PENG: Great. 

In potem je tukaj, smo želeli da preverite, če je naš pogoj izpolnjen, prav? Ker želite spremeniti minimalno vrednost če je dejansko manjši od tistega, ste ga primerjamo z, kajne? Torej, kaj bomo želeli tukaj? Preverite. Kakšne vrste izjave smo verjetno bo ti želeli uporabiti, če bomo želeli preveriti kaj? 

OBČINSTVO: An če izjavi. 

ANDI PENG: An če izjavo. Torej if-- in kaj se dogaja, da pogoj, da želimo v notranjosti naše če izjave? 

OBČINSTVO: Če je vrednost j manjša od vrednosti i-- 

ANDI PENG: Točno tako. Torej if-- zato je ta matrika se imenuje "Niz". Great. Torej, če array-- kaj je bilo to? Povej še enkrat. 

OBČINSTVO: Če je niz-j manj kot matrika-i, potem bi spremenila min. Torej bi bilo min j. 

ANDI PENG: Ali je to smiselno? V REDU. In zdaj tukaj, smo dejansko želijo izvajati swap, kajne? Torej se spomni, v predavanju, da David, ko je skušal the-- kaj je swap it-- pomarančni sok in milk-- 

OBČINSTVO: To je bil bruto. 

ANDI PENG: Ja, to je bilo nekako bruto. Ampak to je zelo dobro Koncept čas dokazuje. Torej, mislim, vaše vrednote tukaj. Imaš niz od min, array i, ali karkoli smo poskušali tukaj zamenjali. In verjetno jih ne morete vlijemo seboj istočasno, prav? Torej, kaj bomo bi morali ustvariti tukaj Za pravilno swap vrednote? 

OBČINSTVO: začasna spremenljivka. 

ANDI PENG: začasna spremenljivka. Torej, kaj je naredil int temp. Glej, kar bi bilo boljše Čas to-- vau, kaj je bilo to? V REDU. Torej bi bilo to bolje Čas je, da ime spremenljivke "temp." Torej, kaj je naredil int temp. Kaj bomo nastavljena temp enako tukaj? OBČINSTVO: Min? ANDI PENG: To je malce zapleteno. To pravzaprav ni pomembno, na koncu. Ni važno, kaj Da bi se odločite za zamenjavo v tako dolgo, kot ste kar prepričani, da ste sledenja, kaj ste zamenjavo. 

OBČINSTVO: Lahko bi bilo niz-i. 

ANDI PENG: Ja, dajmo narediti matrično-i. In kaj potem je naslednja vrstica kode želimo imeti tukaj? OBČINSTVO: matrika-i enaka matrično-j. ANDI PENG: In nazadnje? OBČINSTVO: niz-j enak niz-i. OBČINSTVO: Ali niz-j Ene Niz-temp-- ali temp. 

ANDI PENG: OK. Torej, kaj je teči to in videli če bo delovalo. Kjer je to dogaja? Oh, to je problem. Glej, na liniji 40, smo poskuša uporabiti matrično-j? Ampak kje pa j obstaja samo? 

OBČINSTVO: V zanko. ANDI PENG: Right. Torej, kaj bomo morali storiti? 

OBČINSTVO: ga Določite zunaj the-- OBČINSTVO: Ja, mislim, da imate uporabiti drugo, če izjavo, kajne? Tako kot, če minimum-- Vse je v redu, naj premislim. 

ANDI Peng: Fantje, poskusite da se zazremo Oglejmo glej, kaj se kaj lahko storimo tu? 

OBČINSTVO: OK. Torej, če je najmanjša ni enak j-- tako da, če je minimalna še i-- potem mi ne bi bilo treba zamenjati. 

ANDI PENG: Ali je to enako i? Kaj hočeš reči tu? 

OBČINSTVO: Ali ja, če Minimalna ne enako i, ja. ANDI PENG: OK. No, da reši, vrsta, naše težave. Ampak to še vedno ne reši Problem, kaj se zgodi, če j-- saj j ne obstaja zunaj njega, kar vam želimo storiti z njim? Jo razglasi zunaj? Poskusimo teče to. Uh-oh. Naša nekako ne deluje. 

Kot lahko vidite, naš začetnico Niz je imel te vrednote. In potem bi morala imeti je v 1, 2, 3, 4, 5, 6, 7, 8, 9. Ne deluje. Ahh. Kaj počnemo? OBČINSTVO: Debug. ANDI PENG: V redu, lahko poskusite to. Mi lahko debug. Pomanjšanje bit. Oglejmo nastavite našo prelomne točke. Pojdimo like-- OK. 

Zato, ker smo že vedeli, da te vrstice, 15 do 22, so working-- ker vse delam, je Samo ponavljanjem skozi in printing-- Lahko grem naprej in preskočite to. Začnimo na linijo 25. OOP, dovolite mi, da se znebite tega. 

OBČINSTVO: Torej prekinitvena točka je kjer debugging začne? ANDI PENG: Or ustavi. OBČINSTVO: Ali ustavi. ANDI PENG: Ja. Nastavite lahko več prelomnih točk in je lahko samo skok od enega do drugega. Toda v tem primeru ne vemo, kjer se napaka dogaja. Tako smo samo želim začeti od vrha navzdol. Ja. V REDU. 

Torej, ta črta tukaj, smo lahko korak. Si lahko ogledate tukaj, imamo celo paleto. To so vrednote da so v matriki. Se vam zdi, da je, kako indeks 0, je ustreza value-- oh, Bom poskusil, da jo povečate. Oprostite, to je res težko da see-- na matrično indeksu 0, imamo vrednost 4 in nato tako naprej in tako naprej. Imamo lokalnih spremenljivk. Zdaj i je enaka 0, kar smo želeli, da je. 

In tako naj ohranimo odskočna skozi. Naše najmanjše je enaka 0, ki smo ga prav tako želeli, da je. In potem vnesemo našo drugo za zanka, če je matrika-j manj kot matrično-i, ki ni bilo. Torej si videl, kako da je preskočila več kot to? 

OBČINSTVO: Torej bi morala, če minimum, vse that-- ne bi smeli da biti znotraj prva za zanko? ANDI PENG: Ne, ker ste vedno želeli preizkusiti. Hočeš narediti primerjavo vsak čas, tudi po tem, ko teče skozenj. Vi ne samo želim, da to storite na prvem pass-through. Hočeš, da to storite z vsak dodatni znova podaja. Torej hočeš, da preverite vaše stanje v notranjosti. Torej smo le, da bo teče tu skozi. Dam ti fantje namig. To je povezano z dejstvom, da, ko ste preverjanje vaše pogojena, niste preverjanje Za pravilno indeksa. Torej, zdaj ste preverjanje Niz indeks j manj kot niz Indeks i. Ampak, kaj počneš na na začetku zanke? Ali nisi nastavitev j enak i? 

Ja, tako da bomo lahko dejansko zapustite razhroščevalnik tukaj. Torej, dajmo si oglejte našo psevdokoda. For-- bomo začeti na i je enak 0. Mi smo šli do n minus 1. Poglejmo, ali imamo to pravico? Ja, to je bilo v redu. 

Torej notri tukaj, smo bo vzpostavila minimalno vrednost in nastavite, da je enako i. Ali bomo to naredili? Ja, to storil. Zdaj v naši notranji za zanke, smo storili j enaka i za n minus 1. Ali bomo to naredili? Dejansko smo naredili to. 

Tako pa, kaj bomo primerjali tukaj? 

OBČINSTVO: j plus 1. ANDI PENG: Točno tako. In potem boste želeli nastaviti vaša najnižja enaka j plus 1, kot tudi. Zato sem šel skozi to res hitro. Ali vi razumete zakaj je j plus 1? V REDU. 

Torej, v vašem polju, v vaš prvi navijači, Vaše zanko, za int i je enak 0, kaj je samo prevzame to še ni spremenila. Imamo celo paleto, popolnoma, le štiri nesortirane elementi, kajne? Zato želimo inicializacijo i enaka 0. In jaz se dogaja, da samo teči skozi to zanko. In tako v prvem priložnost, gremo inicializirati spremenljivko z imenom "min" da je enako tudi jaz, saj nimamo najmanjšo vrednost. Tako da je trenutno enaka 0, kot dobro. In potem smo šli skozi. In želimo še enkrat ponoviti. Zdaj, ko smo našli tisto, kar je naša minimalna je, da želimo, da ponovitev prek še enkrat, da vidim, če je to primerjavo, kajne? Torej j, tu se dogaja do enakega I, ki je 0. In potem, če matrika j plus i, ki je tista, ki je poleg več, kot manj od tistega, kar vaš trenutni minimum vrednost, ki ga želite zamenjati. 

Torej Dovolite samo reči, ki smo jih nimajo podobno, 2, 5, 1, 8. Zdaj, jaz je enaka 0 in je j enak 0. In to je naša najmanjša vrednost. Če matrično-j plus i-- tako da če eden da je po eni smo gledate je večji kot tisti pred njim, to se dogaja, da postane minimalna. 

Torej, tukaj vidimo, da 5 ne manj kot to. Tako se dogaja, da ne bo 5. Vidimo, da je manj kot 2, desno 1? Zdaj vemo, da je naša minimalna bo vrednost indeksa pri 0, 1, 2. Ja? In potem, ko si tu dol, lahko swap pravilne vrednosti. 

Torej, ko vidva bile samo ob j Prej, niste bili videti na enem po njej. Ste iskali na enako vrednost, ki Zato je le bilo ničesar ne počne. Ali, da je smiselno, da se vsem, Zato je potrebno, da je plus 1 tam? V REDU. Zdaj pa samo teče skozi to, da bi Preverite, ali je preostali del kode je pravilen. Zakaj se to dogaja? Ah, to je min tukaj. Bili smo primerjali napačno vrednost. O, ne. 

Oh ja, tukaj smo bili zamenjavo napačne vrednote, kot dobro. Ker smo iskali na i in j. To so tisti, ki smo bili preverjanja. Pravzaprav želimo, da bi zamenjali minimum, sedanja minimalna, z karkoli tisti zunaj je. In kot lahko vi vidite navzdol Tu imamo urejen niz. Samo moral storiti z dejstvo, da kadar smo preverjanju podatkov Vrednosti smo primerjali, nismo iskali na pravih vrednotah. Iskali smo na isti enem tukaj, ne dejansko zamenjavo. Moraš pogledati na enem naslednjem z njim in potem lahko swap. Torej, to je tisto, kar je bilo nekako Pred utrujaš našo kodo. In kaj sem naredil tukaj je vse Razhroščevalnik bi lahko storili za vas Pravkar sem to storil na odbor, ker je lažje da vidim, namesto da poskuša da povečate razhroščevalnik. Ali, da je smiselno, da vse? Cool. 

V redu. Mi lahko premaknete na govorimo o asimptotska zapis, ki je samo fancy način pravijo runtimes vseh teh vrst. Zato vem, Davida, v predavanju, dotaknili runtimes. In je šel skozi celotno formulo kako izračunati runtimes. Ni skrbi, da je. Če ste res radoveden o tem, kako to deluje, vas prosimo, da govori z mano po oddelku. Mi lahko sprehod skozi formule skupaj. Ampak vsi fantje imajo res vedo, da n kvadrat več kot 2 je ista stvar kot n kvadrat. Ker največjim številom, eksponent, raste najbolj. In tako za naše namene, Vse nas skrbi je, da velikan število, ki raste. 

Torej, kaj je najboljši primer runtime izbirnega vrste? Če boste imeli Ponovil skozi seznam in potem ponovitev prek preostali del tega seznama, kolikokrat so boš verjetno, v najslabšem case-- v Najboljši primer, sorry-- teče skozi? Morda je bolje, vprašanje je, vprašati, kaj je v najslabšem primeru runtime od izbora vrste. OBČINSTVO: n kvadrat. ANDI PENG: To je n kvadrat desno. Tako enostaven način, da pomislim, je to podobno, kadarkoli imate dve prepleteni za zanke, to se dogaja, da se n kvadrat. Saj ne le, da so ti teče skozi enkrat, moraš iti nazaj okoli in teče skozi njo enkrat notri za vsako vrednost. Torej, v tem primeru, ste tekmovanje v teku n krat n kvadrat, ki is-- žal, n krat n, ki je enaka n kvadrat. 

In nekako je tudi malo edinstven v smislu da ni važno, če ti Vrednosti so že v redu. To se še vedno dogaja, da teče skozi nekako. Naj samo povem, da je to 1, 2, 3, 4. Ne glede na to, ali je bilo v Da, še vedno bi tekel skozi in še vedno preveriti minimalno vrednost. To bi postavil na Enako število pregledov vsak čas, tudi če je to dejansko ni ničesar dotakniti. 

Torej, v takem primeru je najboljše in najslabše runtimes so dejansko enakovredni. Torej pričakovani runtime od izbora vrste, ki smo ga imenuje s simbolom od theta, theta, v tem primeru, bi tudi n kvadrat. Vse tri od teh bi n kvadrat. Vsakdo je jasno, zakaj runtime je n kvadrat? 

V redu. Tako da sem le, da bo hitro teči preko ostalih vrst. Algoritem za bubble sort-- spomnite, To je bila prva David je šel čez v predavanju. V bistvu, stopiš skozi celoten seznam in vi ste swap-- pravkar primerjati dva naenkrat. In če je večja, od tebe samo swap njih. Torej, če so ti višji, bi vas zamenjali. Imam uradni tukaj. 

Torej, recimo, da imaš 8, 6, 4, 2. Ti bi pa jih primerjati med 8 in 6. Ti bi morali, da jih swap. Vi bi primerjal 8 in 4. Ti bi morali, da jih swap. Če imate, da bi zamenjali 8 in z 2, jih spremeniti, pa tudi. Torej v takem smislu, lahko vidite, odvija v daljšem časovnem obdobju, kako vrednote vrsta balona na konci, kar je razlog, zakaj ga imenujemo bubble nekako. 

Mi bi samo teče skozi spet na naš drugi pass, in naš tretji napadalca, in naša četrta akcije. V bistvu, bubble nekako samo teče dokler se ne bo več nobene zamenjave. Torej v tem smislu, da je to le splošna psevdokoda za to. Brez skrbi, to bo vse na spletu. Nimamo dejansko iti čez to. 

Pravkar smo inicializacijo števec spremenljivka, ki se začne pri 0. In mi ponovitev prek celotnega niza. In če ena vrednost is--, če je to je vrednost večja od te vrednosti, boš swap njih. In potem ste pravkar dogaja, da nadaljujem. In boš prešteti. In ste šele tekoč, da delaš to pa števec večja od 0, kar pomeni, da Vsakič, ko boste morali zamenjati, veš želite iti nazaj in ponovno preverite. Želite obdržati kontrolo, dokler ne veste, da vam ni treba več zamenjati. 

Torej, kaj so najboljše in najslabše Primer runtimes za bubble vrste? In hint-- to je dejansko drugačna od izbora vrste v smislu da sta ti dve odgovori niso enake. Pomisli, kaj bi se zgodilo v primer, če je že urejeno. In pomislite, kaj bi se zgodilo, če bi bilo v primeru, v katerem ni bilo urejeno. In lahko nekako teči s zakaj to dogaja. Dam ti fantje, kot so, 30 sekund, da razmišljajo o tem. 

V REDU. Ima kdo ugibati, kaj je najslabšem primeru runtime mehurčkov vrste je? Ja. 

OBČINSTVO: Bi bilo, kot, n-krat n minus 1 ali nekaj takega? Kot, vsakič, ko ga zmanjka, to je samo, kot en swap manj da je vse, kar je bilo. 

ANDI PENG: Ja, tako ste popolnoma prav. In to je primer, v katerem si Odgovor je bil v resnici bolj zapletena od tistega moramo dati. Tako se dogaja, da run-- sem dogaja, da izbrišete vse to tukaj. So vsi dobri? Morem izbrisati to? V REDU. Ti boš teči skozi n krat prvič, kajne? In oni 'tekoč teči skozi n minus 1 drugič, kajne? In potem boš obdržati dogaja, n rudnik 2, et cetera. David je to naredil na predavanju, kjer je, če se seštejejo vse tiste vrednote, dobiš nekaj, kar je like-- yeah-- več kot 2, ki v bistvu le zmanjšuje do n kvadrati. Boste dobili čudno frakcija tam. In tako samo vem, da n kvadrat vedno ima prednost pred frakcije. In tako v tem primeru, najslabša runtime bi n kvadrat. Če je bilo v padajočem Da, mislim, vi morali narediti swap vsak čas. 

Kaj bi bilo, potencialno najboljši primer runtime? Recimo samo, če je bil seznam že V redu, kaj bi bilo runtime bilo? 

OBČINSTVO: n. ANDI PENG: To je n, točno. In zakaj je to n? OBČINSTVO: Ker vas samo morali preveriti vsak enkrat. ANDI PENG: Točno tako. Torej v najboljšem možnem runtime, če bi bil ta seznam že sorted-- recimo, 1, 2, 3, 4-- si bi samo šel skozi, bi morali preveriti, bi videli, oh, so vsi pan ven. Nisem morali zamenjati. Končal sem. Torej, v tem primeru, saj je samo n ali število korakov, ki ste jo pravkar moral preveriti na prvem seznamu. 

In potem smo zdaj hit vstavljanje razvrščanje, kjer algoritem je v bistvu za divide je v urejenem in nerazvrščene obrok. In potem enega po enega, nerazvrščenih vrednosti vstavljena v njihovo ustrezno pozicije v začetku seznama. 

Tako, na primer, imamo seznam 3, 5, 2, 6, 4 znova. Vemo, da je trenutno razvrščeni ker smo pravkar začeli gledaš na to. Mi si oglejte in vemo, da prva vrednost je razvrščen, kajne? Če iščete samo na paleto velikost enega, veš, da je to urejeno. 

Torej vemo, da je Ostali štirje so razvrščeni. Gremo skozi in smo videli, da je vrednost. Pojdimo nazaj. Glej, da vrednost 5? Bomo pogled na to. Mi ga primerjajte s 3. Vemo, da je večja od 3, tako da vemo, da je to urejeno. Tako zdaj vemo, da sta prva dva so razporejene, zadnji trije pa niso. 

Mi si oglejte 2. Najprej smo ga preveri s 5. Je manj kot 5? Ni. Zato moramo obdržati gleda. Potem si oglejte 2 off 3. Je manj kot? No. Toliko, da veš 2 se vstavi v sprednji in 3 in 5 imata, da ga vlečejo ven. Spet naredite to z 6 in 4. In smo samo sproti preverja v bistvu, kjer smo samo preveriti, preverite, preverite. In dokler je v desno Položaj smo nekako le ga vstavite v pravilnem položaju, ki je, če je ime nje prišli. 

Torej, to je samo algoritem, psevdokoda per se, vrsta, o tem, kako bi izvajanje vstavljanja vrste. Psevdokoda je tukaj. To je vse na spletu. Brez skrbi, če se vidva poskušajo kopirati to navzdol. Torej še enkrat, isto question-- kaj bi bilo najbolje in najslabše runtimes za vstavljanje vrste? To je zelo podoben zadnje vprašanje. Dam ti fantje, kot so, 30 sekund, da razmišljajo o tem, kot dobro. 

OK Ali kdo želi daj mi najhujšo runtime? Ja. 

OBČINSTVO: n kvadrat. 

ANDI PENG: To je n kvadrat. In zakaj je to n kvadrat? 

OBČINSTVO: Ker v obratnem vrstnem redu, imate iti skozi n krat n, ki is-- ANDI PENG: Ja, točno. Torej isto, kot v mehurček vrste. Če je ta seznam v padajočem vrstnem redu, vi ste bodo morali preveriti, prvi enkrat. In potem z vsakim dodatno vrednost, ste bodo morali preveriti pred vsak vrednost, kajne? In tako v celoti, si boste, da bi an krat n napadalca drugo n pass, ki je n kvadrat. Kaj o najboljšem primeru? Ja. 

SKUPINA: n minus 1, saj Prvi je že na kvadrat. 

ANDI PENG: Torej, blizu. Odgovor je pravzaprav n. Ker pa prva je razporejene, je ne more actually-- smo pravkar lucked ven, v da je na primer, da je 2 zgodilo, da se najmanjše število. Ampak, da ne bo vedno tako. Če je 2 že razporejene v začetku ampak pogledaš in tam je 1 tukaj, za 1 se dogaja, da jo prestavim. In to se dogaja, da končate up se nekako vrč. 

Torej v najboljšem primeru, To je pravzaprav šele bo n. Če imate 1, 2, 3, 4, 5, 6, 7, 8, si tekoč teči skozi da celoten seznam enkrat preveriti, da vidim, če vse je v redu. Vsakdo je jasno, na tek krat izbire, kot tudi? Vem, da bom s pomočjo ti zelo hitro. Ampak samo vem, da če veste splošnih pojmov, morate biti dobro. V REDU. Torej bom samo vam fantje morda, kot so, minuto, da se pogovorite s svojim sosedom o tem, kaj so le nekateri od glavnih razlik med temi vrstami vrst. Mi bomo šli čez, da kmalu. OBČINSTVO: Oh, v redu. ANDI PENG: Ja. V REDU. Cool, kaj je sestati kot razred. V REDU. Torej je bila to nekakšna odprta vprašanja v smislu da obstaja veliko odgovorov nanje. In bomo šli čez nekatere od njih na kratko. Želela sem, da bi dobili fantje razmišljam o tem, kaj razlikuje vse tri vrste vrst. In slišal sem, tudi, velik question-- kaj zlivanjem storiti? Great vprašanje, ker je to kaj smo zajema naslednje. 

Torej zlivanjem je ena vrsta, ki deluje zelo različno od drugih vrst. Kot lahko vidva see-- je David to naredil demo kjer je imel vse kul trušč vidim, kako združiti nekako tekel, kot so, neskončno hitreje kot drugi dve vrsti? V REDU. Torej, to je zato, ker se združita Razvrsti izvaja to ločnico in osvojiti koncept, ki smo jih govoril o veliko v predavanju. V tem smislu, da želimo delati pametneje, ne težje, ko si razdeliti in osvojiti probleme, in jih odmor navzdol, nato pa jih skupaj, dobre stvari vedno dogajajo. 

Torej tako, da združijo nekako v bistvu deluje je, da ločuje nesortirani matrika na pol. In potem je dobil dve polovici nizi. In to samo razvrsti teh dveh polovic. To samo ohranja delimo na pol, v pol, na pol, dokler se vse razporejene in nato rekurzivno ga postavlja vse skupaj. 

Tako, da je res abstraktna. Torej je to le malo psevdokoda. Ali, da je smiselno v tako, kot je tek? Torej Dovolite samo povem, imate array n elementov, kajne? Če je n manj kot 2, se lahko vrnete. Ker veš, da če je Samo ena stvar je treba razporejene. Else, boste razvrstiti levo polovico, nato pa razvrstite desno polovico, in potem si združita. 

Torej, medtem ko je videti zelo enostavno, v resnici, razmišljam o tem je nekako težko. Ker ste všeč, No, to je nekako teče sama. Prav? To je tekmovanje v teku na sebi. Torej, v tem smislu, David dotaknil ob rekurzije v razredu. In to je koncept bomo govorili o več. To je, da so to ti dve vrstici tukaj, v resnici je samo program je povedal, da se vodijo z različno močjo. Torej, namesto da se vozijo z celota n elementov, lahko ga razdeliti na levo polovico in desno polovico in ga nato znova zaženite. 

In potem bomo pogled na to vizualno, ker sem vizualni učenec. To deluje bolje za mene. Torej bomo pogled na vizualni primer tukaj. 

Recimo, da imamo niz, šest Elementi, 3, 5, 2, 6, 4, 1, niso razporejene. Vse je v redu, tam je veliko na tej strani. Torej, če lahko vi ogledate na Prvi korak tukaj, 3, 5, 2, 6, 4, 1, jo lahko razdelili na pol. Imate 3, 5, 2, 6, 4, 1. Saj veš, da ti te aren't-- Ne vem, če oni razporejene ali ne, tako da boste vedno znova zrušijo, na pol, na pol, na pol, dokler sčasoma, imate samo en element. In se en element vedno razporejene, kajne? 

Torej vemo, da 3, 5, 2, 4, 6, 1, sami po sebi, so razporejene. In zdaj smo jih lahko spet skupaj. Torej vemo, 3, 5. Čaka smo tiste skupaj. Vemo, da je razvrščeni. V 2 je še vedno tam. Mi lahko dal 4 in 6 skupaj. Vemo, da je to urejeno, tako smo se, da skupaj. In 1 je tam. 

In potem si poglej ti dve polovici tukaj. Imate 3, 5, 2, 2, 3, 5. Lahko samo primerjati začetek vsega. Ker veš, da je to urejeno in veš, da je to urejeno. Torej, potem ne boste imeli celo primerjajo 5, ki ste jo pravkar primerjati 3. In 2 manjši od 3, tako veste 2 mora iti na koncu. 

Ista stvar tam. Za 1 mora iti tukaj. In potem ko greš, da dajo ti dve vrednosti skupaj, ste vedeli, da je to urejeno in ste vedeli, da je to urejeno. Tedaj 1 in 2 je 1 manjši od 2. To vam pove, da je 1 bi morala iti na koncu tega celo brez gledaš 3 ali 5. In potem na 4, lahko samo preveriti, gre prav tu. Nimate pogledati na 5. Ista stvar s 6. Saj veš, da 6-- je samo Ni treba, da je treba preučiti. 

In tako na ta način, da ste Samo varčevanje sebe veliko korakov, ko ste primerjali. Nimate primerjati vsak element v primerjavi z drugimi elementi. Pravkar ste se primerjajo s tistimi, da boste morali, da ga primerjajo. Torej, to je nekako kot abstrakten pojem. Brez skrbi, če to ni precej vas tepe še desno. Vendar na splošno, to je kako zlivanjem deluje. Vprašanja, hitre vprašanja, preden sem korak naprej? Ja. 

OBČINSTVO: Torej, ste rekli, da ste vzeli za 1, nato pa 4 in 6 in jih dal v. Torej niso those-- niso gledaš njih kot ločenih elementov, ne kot celote? ANDI PENG: Ja. Torej, kaj se dogaja je, da si v bistvu ustvarjajo povsem novo paleto. Torej veste, da je tu, imam dve nizi velikosti 3, kajne? Torej veste, da je moja sortirani niz mora imeti šest elementov. Torej si ustvarite novo količino pomnilnika. Torej ste nekako kot pri čemer potratno spomina, vendar to ni pomembno ker je tako majhna. Torej si poglej 1 in si poglej na 2. In veste, da je manj kot 2 za 1. Torej veste, da je treba iti v 1 začetek vse tiste. 

Vam ni treba niti poglej na 3 in 5. Torej veste, 1 gre tja. Potem ste v bistvu odsekati na 1. To je, kot, mrtev za nas. Potem imamo samo 2, 3, 5 in nato 4 in 6. In potem veste, da vas primerjajo 4 in 2, Oh, 2 bi moral iti tja. Torej si Pasti za 2 navzdol, jo odsekati. Torej boste morali 3 in 5 pri 4 in 6. In ti kar naprej ga sekljanje off dokler jih dal v array. 

OBČINSTVO: Torej ste pravkar vedno primerjavo [neslišno]? 

ANDI PENG: Točno tako. Torej, v tem smislu, da ste samo primerjavo, v bistvu, ena številka zoper drugo številko. In ker veš da je to urejeno, vam ne bi bilo treba pogledati skozi vse številke. Moraš pogledati na prvega. In potem si lahko samo Pljuskanje jim dol, saj veš, jim pripadajo, kjer so morali pripadati. Ja. Dobro vprašanje. 

In potem, če kdo od vas so malo ambiciozen, vas prosimo, da pogled na to oznako. To je dejansko fizična izvedba o tem, kako bi mi napisali zlivanjem. In lahko vidite, da je zelo kratek. Toda Zamisel to so precej zapleteni. Torej, če se počutite, kot risba tole v svojo domačo nalogo nocoj, vas prosimo, da. 

V REDU. Torej, David je šel tudi čez to v predavanju. Kateri so najboljši primer runtimes, najslabšem primeru runtimes, in pričakovane runtimes z zlivanjem? Nekaj ​​sekund razmišljati. To je zelo težko, vendar vrsta intuitivno, če mislite o tem. V redu. 

OBČINSTVO: Je najslabšem primeru n log n? ANDI PENG: Točno tako. In zakaj je n log n. 

OBČINSTVO: Ali ni to zato, ker je postane eksponentno hitreje, tako je kot funkcija, ki namesto samo preprosto čemer n kvadrat ali kaj? ANDI PENG: Točno tako. Torej je razlog, zakaj je runtime na to je n log n je because-- kaj so ti delaš v vseh teh korakov? Ste pravkar sekljanje na pol, kajne? In tako, ko sva početje log, vse, kar počne je tako, da se problem v polovici, v polovici, v polovici, v več polovic. In v tem smislu, lahko nekako o odpravi linearnim modelom da smo bili z uporabo. Ker ko sesekljajte stvari na pol, to je dnevnik. To je samo matematična način, ki ga zastopajo. 

In potem na koncu, ob koncu, ste samo izdelavo ene zadnjo podajo mimo da dajo vse od njih v redu, kajne? In tako, če boste morali preveri eno stvar, ki je n. In tako si nekako množenjem dva skupaj. Torej, to je, kot imaš, da je končna preverite, n tu dol z log n tu gor. In če pomnožimo jim, da je n log n. 

In tako je najboljši primer in najslabše primera in pričakovanjih so vse n log n. To je tako kot druge vrste. To je kot izbirni vrste v smislu, da je Ni važno, kaj je tvoj seznam je, to je le, da bo narediti isto stvar vsak čas. V REDU. Tako da lahko vi vidite, čeprav so vrste, da smo šli through-- n kvadrat, da ni zelo učinkovito. In tudi to n log n ni najbolj učinkovita. Če sta vidva radovedni, tam je Mehanizmi vrsta ki so tako učinkoviti, da oni skoraj v bistvu ravno v času izvajanja. 

Imaš nekaj dnevnik n-jev. Imaš nekaj dnevnik n dnevniku. Ne dotikajte se nanje V tem razredu prav zdaj. Ampak, če ste fantje radovedni, vas prosimo, da google, kaj je najbolj učinkovitih mehanizmov za sortiranje. Ne vem, obstajajo nekateri res smešno tisti, like-- tam je nekaj res smešni tisti, ki jih ljudje naredijo. In vas sprašujem, kako so kdaj pomislil na to. Torej, google, če imate nekaj prostega Čas, on, kaj so nekatere smešne načine da people-- ter učinkovita ways-- ljudje so bili sposobni izvajati vrst. V REDU. In tukaj je samo priročen mali grafikon. Vem, da vas vse, pred tem kvizu 0, bo v svoji sobi verjetno poskuša da si zapomnimo, da je. Tako da je lepo tam za vas. Samo ne pozabite na logiko, ki made-- Zato te številke so bile, ki se pojavljajo. Če ste vedno izgubili, samo da prepričani, da veste, kaj vrste so. In lahko teče skozi jim v mislih da ugotovimo, zakaj tisti, odgovori so ti odgovori. 

V redu. Torej bomo, da se premaknete na končno na iskanje. Saj, kot tiste, ki ste ki ste prebrali pset, Iskanje je tudi del problem ta teden določa. Boste morali izvajati dve vrsti iskanj. Ena je linearna iskanje in eden je binarno iskanje. 

Torej linearna iskanje je dokaj preprost. Pravkar želite iskati element seznama, da vidim, če ste jo dobili. Moraš Ponovil skozi. In če je to enako, nekaj, si lahko samo vrniti, kajne? Ampak tisti, ki smo najbolj zanima govoriš dvojiško iskanje, desno, ki je razdeli in vladaj mehanizem, ki David je dokazovanje v predavanju. 

Spomnimo se primera telefonskega imenika da ga še naprej vzgajajo, tista, ki je nekako boril malo o tem preteklem letu, kjer si razdeliti problem na pol, na pol, na pol, znova in znova, dokler ne boste našli, kar iščete? In imaš runtime na to, kot dobro. In lahko vidite, da je bistveno bolj učinkovita kot katero koli drugo vrsto iskanja. 

Torej način, da bi šel okoli izvajanje binarno iskanje je, če bomo imeli niz, indeks 0 do 6, sedem elementov, smo lahko ogledate v sredini, right-- Žal mi je, če je naše vprašanje first-- če želimo vprašati vprašanje, ali matrika vsebuje element 7, Očitno je, da pri človeku, in ima tako majhen matrika, je enostaven za nas reči da. Toda način, da se izvaja binarno iskanje bi bilo pogledati v sredini. 

Vemo, da je indeks 3 srednji, ker smo vem, obstaja sedem elementov. Kaj 7 deljeno z 2? Lahko odsekati, da dodatno 1. Imaš 3 v sredini. Torej je niz 3 enaka 7? To ni, kajne? Ampak ne moremo storiti nekaj pregledov. Je niz 3 manj kot 7 ali je niz 3 večji kot 7? 

In vemo, da je manj kot 7. Torej vemo, da, oh, mora o tem ne bi bila v levi polovici. Vemo, da mora biti V desni polovici, kajne? Tako smo lahko samo odsekati pol array. Nimamo niti za poglej več. Ker vemo, da polovica našega problem-- vemo, da je odgovor na desna polovica našega problema. Tako smo samo poglej, da je zdaj. 

Torej, zdaj gledamo na sredina, kar je ostalo. Ta indeks 5. Smo spet naredil isto pregled in vidimo, da je manjši. Torej, gledamo na levi strani, ki. In potem smo videli, da je ček. Je vrednost niz na indeks 4 enaka 7? Je. Tako bomo lahko vrnili res, ker smo našli vrednost v našem seznamu. Ali kako sem šel skozi da je smiselno, da se vse? V REDU. Dam ti fantje morda, kot so, tri, štiri minute, da ugotovimo, kako psevdokoda to. 

Torej, si predstavljajte, sem vas prosil, da napišete Funkcija se imenuje iskanje (), ki se je vrnil vrednost, logično vrednost, da je res ali false-- podobno, res, če ugotovi, da je vrednost false, če nisi. In potem ste bili opravili na vrednost, ki jo iskali v vrednosti, ki je array-- oh, jaz definitivno dal da je na napačnem mestu. V REDU. Kakorkoli že, da bi morali imeti je na desni strani vrednot. In nato int n število elementov v tem polju. Kako bi šel o poskusu da psevdokoda ta problem v? Dam ti fantje, kot so tri minute, da to storim. Ne, mislim, da je only-- Ja, tam je ena prav tukaj. OBČINSTVO: Can I? ANDI PENG: Ja, imam te. Je to deluje? OK kul. 

V REDU. V redu fantje, mi smo tekoč, da ga nadzorovali. V REDU. Torej, predpostavimo, da smo dobili to lepo malo matrika zn vrednot v njej. Nisem pripravi proge. Toda kako bi šel o poskuša to napisati? Ali kdo želi daj mi prvo vrstico? Če želite, da bi me prva linija tega psevdokoda. 

OBČINSTVO: [neslišno] OBČINSTVO: Bi želeli Ponovil through-- OBČINSTVO: Just another za zanko? OBČINSTVO: --for. 

ANDI PENG: Torej, ta je malce zapleteno. Pomislite about-- želite da bo tekmovanje v teku to zanko znova in znova do kdaj? 

OBČINSTVO: Do [neslišno] vrednost je enaka tej vrednosti. ANDI PENG: Točno tako. Torej lahko dejansko samo write-- bomo lahko celo poenostavi več. Mi lahko samo narediti while zanko, kajne? Tako da lahko samo še loop-- vemo, da je nekaj časa. Ampak za zdaj, bom reči "zanko" - skozi kaj? Loop until-- kaj je naša konča stanje? Mislim, da sem ga slišal. Sem slišal nekoga reči. 

Publika: Vrednote enaka sredini. ANDI PENG: Ponovi. OBČINSTVO: Ali, dokler vrednost, ki jo iščete Za je enaka srednji vrednosti. 

ANDI PENG: Kaj pa, če je ni tam? Kaj, če je vrednost, ki jo iščete za dejansko ni v tem polju? OBČINSTVO: Vrnete 1. 

ANDI PENG: Ampak kaj hočemo zanka, dokler če imamo stanje? Ja. 

OBČINSTVO: Dokler obstaja samo ena vrednost? ANDI PENG: Lahko zanka until-- tako da boste vedeli, da ste dogaja, da imajo max vrednost, kajne? In veš, da boš imeti min vrednost, ne? Ker je tudi, da je nekaj Pozabil sem povedati prej, da je nekaj, kar je kritično o binarnem iskanju je, da je vaš matrika že razporejene. Ker ni način dela to če oni samo naključne vrednosti. Saj ne vem, če je večji od drugega, kajne? 

Tako da boste vedeli, da vaš max in vaše min tukaj, kajne? Če ste tekoč, da se prilagajanje Vaše max v vaših minut in mid-- kaj je samo prevzeti vaš mid vrednost je prav here-- boste v bistvu zanka, dokler vam minimum približno enako kot max, desno ali če vaš max ni isto kot vaš min. Prav? Ker, ko se to zgodi, veste, da da ste na koncu zadeli enako vrednost. Torej hočeš, da zanke, dokler vam min je manjša od ali enaka to-- oops, ni manjša ali enaka drugi način around-- max je. 

Ali, da je smisel? Vzel sem nekaj neuspešnih poizkusih, da bi dobili to pravico. Ampak zanka do vašega max vrednosti je v bistvu skoraj manj od ali enaka vaši minimum, kajne? To je, ko veš ki ste jih približale. OBČINSTVO: Ko bi vaša največja vrednost manj kot minimum? ANDI PENG: Če se boste držali ga prilagodi, kar je tisto, kar se dogaja da se delaš na tem. Ali to smiselno? Najmanjši in max so samo cela števila, ki smo verjetno dogaja, da želijo ustvariti obdržati tir, kjer iščemo. Ker je matrika obstaja ne glede na to, kaj počnemo. Kot, da smo dejansko ni fizično sekanje off matriki, kajne? Mi samo prilagajanje kjer smo iskali. Ali to smiselno? 

OBČINSTVO: Ja. 

ANDI PENG: OK. Torej, če je to pogoj za našo zanke, kaj želimo znotraj te zanke? Kaj bomo se želijo storiti? Torej sedaj, imamo max in min, desno, verjetno ustvaril tu nekje. Bomo verjetno želeli najti sredino, kajne? Kako se bomo, da bo mogli najti na sredini? Kaj je mathematical-- OBČINSTVO: Max plus min deljeno z 2. ANDI PENG: Točno tako. Ali to smiselno? In ne vi vidite, zakaj smo ni samo use-- zakaj smo to storili namesto da bi le n deliti z 2? To je zato, ker n je vrednost da se dogaja, da ostanejo enake. Prav? Toda, kot smo prilagodili našo minimalno in Najvišje vrednosti, oni bodo spremenile. In kot rezultat, naši srednji se bo preveč spremenilo. Torej, to je, zakaj hočemo to storiti prav tukaj. V REDU. 

In potem, zdaj, Ugotovili smo our-- ja. 

OBČINSTVO: Samo hitro question-- ko rečeš min in max, smo ob predpostavki, da to je že urejeno? 

ANDI PENG: Ja, to je pravzaprav predpogoj za binarnega iskanja, da moraš vedeti, da je urejeno. Kateri je razlog, zakaj nekako, pišete v vašem problem nastaviti pred vašim binarnega iskanja. V REDU. Torej sedaj, da vemo, kje je naša sredina je, kaj želiš narediti tukaj? 

OBČINSTVO: želimo primerjati da drugi. ANDI PENG: Točno tako. Torej boš za primerjavo mid da vrednost, kajne? In kaj to povedati nam, ko smo primerjali? Kaj želimo storiti potem? 

OBČINSTVO: Če je vrednost večja od srede, želimo, da ga odreže. ANDI PENG: Točno tako. Torej, če je vrednost večja od srede, smo bodo želeli spremeniti te minimum in maxes, kajne? Kaj želimo spremeniti? Torej, če vemo, da je vrednost je nekje tukaj, kaj vas storimo, da spremeniti? Želimo, da spremenimo svojo Minimalna biti sredi, kajne? In potem pa, če je v tem pol, kaj želimo spremeniti? 

OBČINSTVO: Vaša največja. ANDI PENG: Ja. In potem ste šele tekoč obdržati zanka, kajne? Ker sedaj, po eni ponovitvi skozi, imaš max tukaj. In potem lahko preračunate vmesni pregled. In potem se lahko primerjajo. In ti boš nadaljuj še min in maxes so v bistvu približale. In to je, ko veš, da da ste zadeli konec tega. In, bodisi, da ste ga našli ali niste na tej točki. 

Ali je to smiselno, da vse? V REDU. To je zelo pomembno, ker boste imeli to napisati v kodi nocoj. Ampak vi imate zelo dober občutek, kaj je treba narediti, kar je dobro. V REDU. Torej imamo približno sedem minut zapustil oddelek. Torej bomo govorili o to pset, da bomo počeli. Torej je pset razdeljena na dve polovici. Prva polovica vključuje izvajanje najdbo v katerem pišete linearno iskanje, A binarno iskanje, in sortiranje algoritem. 

Torej je to prva Čas v pset kjer bomo vam fantje, kar se imenuje distribucija koda, ki je koda da smo vnaprej napisan, ampak samo pustil nekaj kosov off za vas, da napišete. Torej, fantje, ko si poglej tole kodo, boste morda dobili res prestrašila. Če ste šele všeč, Ahh, I Ne vem, kaj to počne, Ne vem, kot, da se zdi, tako zapletena, ahh, se sprostite. To je v redu. Preberite spec. Spec bo razložil, da vam točno kaj vse te programe počnete. 

Na primer, generate.c je program da bo z vašo pset. Ne boste dejansko morali dotakniti, vendar morate razumeti, kaj počne. In generate.c, vse to počne, je bodisi generiranje naključnih števil ali lahko daš to seme, tako kot vnaprej dogovorjeno število, ki je potrebno, in ustvarja več številk. Torej obstaja poseben način izvajanje generate.c v kateri lahko samo, da kup številk za vas, da preizkusite svoje druge metode, na. 

Torej, če boste želeli, za Na primer, preizkusite svojo najdbo, bi si želeli teči generate.c, ustvariti kup številk, in nato zaženite vaš pomočniki funkcijo. Vaš pomočniki funkcija je, če ste dejansko fizično pisanje kode. In pomislite pomočnikov kot datoteko s knjižnico pišete, da je najdba kliče. In tako znotraj helpers.c, boste storiti iskanje in sortiranje. 

In potem boš v bistvu jih vse samo skupaj. Spec vam bo povedal, kako dal, da v ukazni vrstici. In boste lahko preverili, ali ni tvoja razvrščanje in iskanje delajo. Cool. Je kdo že začel in ki so se pojavljale težave ali vprašanja imajo zdaj s tem? V REDU. 

OBČINSTVO: Počakajte. Imam vprašanje. 

ANDI PENG: Ja. 

OBČINSTVO: Zato sem začel delaš linearna iskanje v helpers.c in to ni bilo res deluje. Ampak kasneje sem ugotovil, smo pravkar morali izbrisati in narediti binarno iskanje. Torej je to važno, če to ne deluje? 

ANDI PENG: Kratek odgovor je ne. Ampak, ker smo not-- OBČINSTVO: Ampak nihče dejansko preverjanje. ANDI PENG: Smo nikoli bomo videli, da. Vendar pa boste verjetno želeli, da bi Prepričajte vaše iskanje deluje. Ker če je vaš linearno iskanje ne deluje, potem so možnosti, tvoj binarni iskanje ne bo delovalo, kot dobro. Ker imate podobne logika v oba. In ne, to ni važno. Torej edine boste obrniti v so nekakšna in binarno iskanje. Ja. 

In tako je bilo veliko otrok poskušali zbrati helpers.c. Saj ne boš dejansko dovoljeno za to, ker helpers.c nima glavno funkcijo. In tako bi smeli samo bo dejansko sestavljanje ustvarjajo in najti, ker najdejo klici helpers.c in funkcije v njem. Tako da omogoča razhroščevanje bolečina v riti. Ampak to je tisto, kar moramo storiti. OBČINSTVO: Moraš narediti vse, kajne? ANDI PENG: Lahko samo narediti vse, kot tudi, ja. V REDU. Tako, da je to v smislu, kaj pset se vas prosi vse narediti. Če imate kakršnakoli vprašanja, vas prosimo, da me po oddelku vprašati. Jaz bom tu, kot, 20 minut. 

In ja, so pset je res, da ni slabo. Vidva bi morala biti v redu. To, sledite smernicam. Nekako imajo občutek, logično, kaj naj bi se dogajalo in boste v redu. Ne bodite preveč strah. Tam je veliko kode tam že napisal. Ne bodite preveč strah, če ne razumeti, kaj vse to pomeni. Če je veliko, to je povsem v redu. In prišli do uradnih ur. Pomagali vam bomo, da pogled. 

OBČINSTVO: Z dodatno funkcije, ne gledamo tiste gor? 

ANDI PENG: Ja, to so v kodeksu. V igri 15, pol leta to je že napisal za vas. Torej te funkcije so že v kodeksu. Ja. V redu. No, veliko sreče. To je ogabno dan. Torej, upam, da vama ne počutim preveč slabega o bivanju v notranjosti in kodiranja.