[Glazbom] 

ANDI PENG: Dobrodošli u tjednu 3. poglavlju. Hvala, dečki, za sve koji dolaze ovaj ranije danas starta. Imamo lijep, malo intimna skupina danas. Dakle, nadam se da ćemo doći do završiti, možda, rano, malo ranije danas. Tako brzo, samo su neki najave dnevnom redu danas. Prije nego što počnemo, mi smo će samo ići preko neka kratka logistički problemi, pset pitanja, ispitati, takve stvari. A onda ćemo roniti u pravu. Mi ćemo koristiti debugger zove GDB se početi Debunking naš kod, koji je David objasnio u predavanju neki dan. Mi ćemo ići preko četiri vrste sorti. Mi ćemo ići preko njih vrlo brzo jer oni su prilično intenzivna. Ali znam da su svi slajdovi i Izvorni kod su uvijek online. Dakle, slobodno, na lektira, na vratiti i pogledati to. 

Mi ćemo proći kroz asimptotske zapis koji je samo fancy način govoreći: "runtimes" gdje imamo veliki O, koji David je objasnio u predavanju. I mi također imaju Omega, koji je donja granica runtime. A mi ćemo govoriti malo više u dubini pogledu kako ti posao. I na kraju, mi ćemo ići preko binarnog pretraživanja, jer puno vas koji su već Pogledao je svoje psets vjerojatno znate da to je pitanje koje je u svom pset. Dakle, svi vi ćete biti sretni koje pokrivaju to danas. 

I na kraju, po svoj poglavlje povratne informacije, ja zapravo ostavi 15 minuta na kraj samo ići preko logistika pset3, bilo kakva pitanja, možda malo smjernice, ako hoćete, Prije nego što počnemo programiranje. Tako ćemo pokušati dobiti kroz materijal prilično brzo. A onda možemo provesti neko vrijeme uzimanje više pitanja za pset. U REDU. 

Brzo, pa samo malo najave prije nego što počnemo već danas. Prvo, dobrodošli u izradi to kroz dvije svoje psets. Uzeo sam pogled na your-- da, neka je dobili aplauz za taj jedan. Zapravo, bio sam jako, stvarno impresioniran. I polaže prvi pset za vas momci Prošlog tjedna, a vi učinili nevjerojatno. 

Stil je bio na mjestu osim nekoliko komentara. Pobrinite se da uvijek Komentirajući svoj kod. Ali tvoji psets bili na mjestu. I držati ga se. I to je dobro za greder na vidim da su ti dečki stavljajući u koliko truda u svom stilu i vaš dizajn u kodu da želimo za vas vidjeti. Tako sam prolazeći zahvalnosti ostatak TAS. 

Međutim postoji Nekoliko ispitati pitanja Ja samo želim ići preko toga kako bi moj život i puno drugoga TAS 'živi malo lakše. Prvo, sam primjetio ovo prošlosti week-- koliko vas su trčanje na check50 Vaš broj prije nego što pošaljete? U REDU. Dakle, svatko bi trebao biti događaj check50, because-- secret-- smo zapravo pokrenuti check50 kao dio naše ispravnosti skripte za testiranje svoj kod. Dakle, ako je vaš broj je u nedostatku check50, po svemu sudeći, vjerojatno će uspjeti našu provjeru, kao dobro. Ponekad ti dečki ima prave odgovore. Kao, u pohlepni, neki od imate pravo brojeve, ti samo isprintati neke dodatne stvari. I to extra stvar zapravo ne ček, jer računalo ne znam što to traži. I tako će se izvoditi samo kroz, vidjeti da je vaš izlaz ne onome što očekujemo odgovor da, i označiti da je u krivu. 

I znam što se dogodilo u neke od svojih slučajeva ovaj tjedan. Pa sam otišao natrag i ručno regraded svačiji kôd. U budućnosti ipak, molimo, provjerite da radite provjeriti 50 na svom kodu. Zato što je to vrsta boli za PU morati vratiti i ručno ponovo ocijeniti svaki pset za svaki jedan, malo promašio instanca. Pa nisam skinuti bodove. Mislim da sam skinuo možda jedan ili dva za oblikovanje. U budućnosti iako, ako ti si u nedostatku check50, bodovi će se poduzeti off za ispravnost. 

Nadalje, psets su zbog petkom u podne. Mislim da postoji sedam minuta kasno poček da vam dati. Po Harvard vremena, oni smiju biti sedam minuta kasno za sve. Dakle ovdje na Yaleu, mi ćemo pridržavati se to kao dobro. Ali prilično mnogo, na 12:07, ako vaš pset nije, to će biti označena kao kasno. I tako, dok je označena tek je TA-- sam i dalje će se ocjenjivanje vaše psets. Dakle, i dalje ćete vidjeti ocjenu pojaviti. Međutim, znamo da je u kraj semestra, sve kasni psets će biti samo nulira automatski od strane računala. 

Mi to iz dva razloga. Jedan, ponekad smo dobili Ispričao poput dekana isprike, kasnije da ja ne znam o još. Stoga smo željeli biti sigurni da smo ocjenjivanja sve samo u slučaju, kao što sam nedostaje Dean je isprika. I drugo, imajte na uma, još uvijek možete ispusti jedan pset da ima puni opseg bodova. I tako smo željeli stupnja sve svoje psets jednostavno kako bi bili sigurni da je vaš opseg je postoji i da ste ih težak. Dakle, čak i ako je kasno, i dalje ćete dobiti kredit za djelokrug točaka, mislim. 

Dakle pouka ove priče je, učiniti je li vaše psets su na vrijeme. A ako nisu u na vrijeme, znam da to nije velika. Da, prije nego što sam krenuti dalje, bilo tko imati Bilo kakva pitanja vezana pset povratne informacije? Da. 

PUBLIKA: Jeste li kažemo može pasti jedan od psets? 

ANDI PENG: Da. Dakle, postoji devet psets ukupni tijekom semestra. A ako imate opseg points-- tako opseg je jednostavno, prilično mnogo, vi pokušate problem su stavljanjem u vremenu, ti pokazuje da ste pokazali ste pročitali spec. To je prilično mnogo prostora. A ako ispunjava Opseg poena, što može pasti najniže jedan od punog opsega. Dakle, to je u svoju korist na završiti i pokušajte svaki pset. 

Čak i ako nitko od upload-- im posao, stavi ih sve. A onda ćemo, nadamo se moći vam dati neke od tih točaka natrag. Cool. Ima li još pitanja? Veliki. 

Drugo, ured hours-- malo Brzi Bilješke o radnog vremena. Prvo, došao početkom tjedna. Nitko nije nikada na Radno vrijeme ponedjeljkom. Christabel došao Radno vrijeme prošle noći. Da, Christabel. A što imamo u uredu sata sinoć, Christabel? 

PUBLIKA: Imali smo sladoled. 

ANDI PENG: Pa to je točno, imali smo sladoled u uredovno vrijeme prošle noći. Iako ne mogu vam obećati da ćemo morati sladoled na radnog vremena svaki tjedan, što mogu obećati je da će biti znatno Bolje učenik TA omjeru. Kao čitljiv, to je kao tri prema jedan. Dok, kontrast koji s Četvrtak, imaš oko 150 stvarno je naglasio djecu i ne sladoled. A to jednostavno nije produktivno za svakoga. Dakle pouka ove priče je, doći rano za radnog vremena i dobre stvari dogodit će se. 

Također, dolaze spremni postavljati pitanja. Znaš? Bez obzira što Tas, ja mislim, je rekao: mi smo bili uzimajući par studente koji dolaze u četvrtak, na, kao, 10:50 nije čitao spec biti kao mi pomoći, pomozi mi. Nažalost u tom trenutku, ne postoji ne možemo mnogo učiniti kako bi vam pomoći. Dakle, molim Vas, došli početkom tjedna. Dođi rano za radnog vremena. Dođite spremni postavljati pitanja. Pazite da vas, kao student, gdje su morate biti tako da TAS mogu vas voditi zajedno, što je ono radno vrijeme trebao biti dodijelili za. 

Drugo, tako da znam profesore vole nas iznenaditi s testovima. Imao sam profesora one kao, Yo, usput, sjetite se da na polovici trajanja imate sljedećeg ponedjeljka. Da, nisam znao o toj polovici trajanja. Tako ću biti da TA koji vam podsjeća sve da kviz 0-- jer, znate, mi smo CS. Sada kada smo učinili polja, te dobiti zašto je kviz 0, a ne 1 kviz, ha? U REDU. Oh, dobio sam neke nasmijao na taj jedan. U REDU. 

Dakle kviz 0 će biti 14. listopada, ako ti si u dijelu ponedjeljka u srijedu i 15. listopada, ako ste u odjeljak Utorak-četvrtak. To se ne odnosi na one od vas na Harvardu who-- Mislim da svi ćete biti uzimati kvizova 14.. 

Tako da, sljedeći tjedan, ako David je u predavanju, ide, Da, tako o tome Kviz sljedeći tjedan, svi neće biti šokirani, jer ste došli na odjeljak a vi znate da je vaš kviz 0 je u dva tjedna. I mi ćemo imati pregled sjednice i sve. Tako da nema brige o se prepala za to. Bilo kakva pitanja before-- kakvih pitanja na svim vezi logističkih poteškoća, ocjenjivanja, radno vrijeme, dijelovi? Da. 

PUBLIKA: Dakle kviz je će biti tijekom predavanja? 

ANDI PENG: Da. Dakle kviza, mislim, 60 minute dodijelili u tom terminu da ćete samo uzeti u dvorani. Dakle, ne morate doći u na, kao, slučajnih 7:00. Sve je dobro. Da. Cool. 

U redu. Tako ćemo uvesti koncept za vas ovaj tjedan da je David je već neka vrsta od dotaknuo u predavanju prošli tjedan. To se zove GDB. I kako mnogi od vas, dok je u tijek pisanja psets, primijetili veliki gumb na kojem piše "Debug" na vrhu vašeg IDE? U REDU. Dakle, sada smo zapravo ću iznijeti Otajstvo što to zapravo gumba ne. A ja vam jamčim, to je lijepa, lijepa stvar. 

Dakle, do sada, mislim došlo je do dvije stvari studenti su obično radi kada pogrešaka psets. Jedan od njih, oni ili dodati u printf () - pa svakih nekoliko redaka, dodali su u printf () - Oh, što je to varijabla? Oh, što je to promjenjiva now-- i vrsta vidjeti napredovanje vašeg koda, kao da radi. Ili drugi način djeca učiniti je da samo napisati cijelu stvar a zatim ići ovako na kraju. Nadam se to radi. Jamčim ti, GDB je bolje nego oba od tih metoda. Da. Dakle, to će biti vaš novi najbolji prijatelj. Zato što je lijepa stvar koji vizualno prikazuje kako što je vaš broj radi na određenom mjestu kao i ono što sve svoje varijable nosi, kao što su njihove vrijednosti, u tom određenom trenutku. I na ovaj način, možete zaista postavite prijelomnih točaka u kodu. Možete izvoditi kroz liniju po liniju. I GDB će samo za ti, prikazani za vas, ono sve svoje varijable su, što rade, što se događa u kodu. I na takav način, da je tako mnogo lakše vidjeti što se događa, umjesto printf-ing ili zapisivao svoje izjave. 

Tako ćemo napraviti primjer za to kasnije. Dakle, to se čini malo sažetak. Bez brige, mi ćemo učiniti primjere. I tako u biti, tri najveće, najčešće korištene funkcije morat ćete u GDB su Dalje, Korak više, i Korak u tipki. Idem nad glavom Postoji, zapravo, upravo sada. 

Dakle, možete li vi svi vidite da ili bih trebao uvećanje malo? U leđa, možete vidjeti? Trebam li zumirati? Samo malo? OK super. Idemo tamo. U REDU. 

Tako sam, ovdje, moj Provedba za pohlepni. I dok mnogi od vas pisali pohlepni u while petlji form-- da je savršeno prihvatljiv način za napraviti it-- još jedan način da to učinite je da se jednostavno podijeliti u modulom. Jer onda možete imati svoj vrijednost, a zatim su svoj ostatak. I onda možete jednostavno dodajte sve to zajedno. Da li logiku što radim Ovdje smisla svima, Prije nego što počnemo? Vrsta? Cool. Veliki. To je prilično seksi komad koda, rekao bih. Kao što sam rekao, David, u predavanje, nakon nekog vremena, svi vi ćete početi dobivati ​​kod kao nešto što je lijepo. A ponekad kad vidite lijepo kod, to je takav prekrasan osjećaj. 

Pa ipak, dok je to kod vrlo lijepo, to ne radi ispravno. Tako ćemo pokrenuti check50 o tome. Provjerite 50 20-- OOP. 2? Je li to pset2? Da. Oh, pset1. U REDU. Tako smo pokrenuti check50. 

A što vi vidite ovdje, to nije par slučajeva. A za neke od vas, u Naravno da radi svoj problem seta, ti si kao, ah, zašto se ne radi. Zašto je to raditi za neke vrijednosti, ali ne i za druge? Pa, GDB će vam pomoći shvatiti zašto ti inputi nisu radili. 

U REDU. Tako ćemo vidjeti, jedan od Provjere sam u nedostatku u check50 je ulazni vrijednost 0,41. Dakle točan odgovor da trebali biti uzimajući je 4. No, umjesto onoga što sam ispis je 3-N, što je netočno. Pa neka je samo pokrenuti to ručno, samo pobrinite se da check50 radi. Učinimo ./greedy. Ups, moram napraviti pohlepni. Idemo tamo. Sada ./greedy. 

Koliko je dugovao? Učinimo 0.41. I Yep, vidimo ovdje da je to izlaza 3 kada je točan odgovor, U stvari, treba biti 4. Tako ćemo ući GDB i vidjeti kako ćemo možete ići oko rješavanja tog problema. 

Dakle, prvi korak u Uvijek ispravljanje pogrešaka kôd je postaviti prijelomna točka, ili točka u kojoj ste Želite računala ili debugger za početak obličje at. Dakle, ako ne stvarno Znaš što je tvoj problem, Obično, tipična stvar želimo učiniti je postaviti našim Kontrolna točka na glavni. Dakle, ako vi možete vidjeti crveni gumb pravo postoji, Da, to je meni podešavanje a Prijelomna točka za glavnu funkciju. Kliknem da. 

I onda ja mogu ići i do mog gumb Debug. Sam pogodio taj gumb. Dopustite mi uvećanje natrag ako mogu. Idemo tamo. Tako smo, evo, ploča na desnoj strani. Žao mi je, dečki u leđa, što stvarno ne mogu vidjeti jako dobro. Ali u biti, sve to pravo ploča radi se praćenje i označena linija, što je linija koda da računalo trenutno radi, kao i sve svoje varijable ovdje. 

Pa imaš centi, novčići, n, svi proglasili za različite stvari u ovom trenutku. Bez brige, jer imamo zapravo nije inicijalizacije ih na bilo varijable još. Tako je u računalu, Računalo je samo vidio, oh, 32767 bio je posljednji korišteni funkcija te memorijskog prostora u mom računalu. I tako je to u kojoj se trenutno nalazi centi. Ali ne da nakon što pokrenete kod, to bi trebao postati inicijalizacije. 

Tako ćemo proći, liniju linija, što se ovdje događa. U REDU. Dakle, ovdje su tri tipke koje sam upravo objasnio. Imate igrati, ili Run funkciju, gumb, imate korak iznad gumba, a imate i korak u gumb. A u biti, sve troje ih jednostavno proći kroz kodu i raditi različite stvari. 

Tako obično, kad si ispravljanje pogrešaka, mi ne želimo samo pritisnite Play, jer Igra će samo pokrenuti Vaš broj na kraj njega. A onda nećete zapravo Znaš što je tvoj problem je, osim ako ste postavili više breakpoints. Ako ste postavili više prijelomnih točaka, to će samo automatski pokrenuti iz jedne prelomne tačke, na sljedeći, na sljedeći. No, u ovom slučaju mi ​​smo samo da je jedan, jer mi želite raditi naš put od vrha prema dolje do dna. Tako ćemo ignorirati tu tipku sada za potrebe ovog programa. 

Tako je korak više funkcija samo koraci više svaku liniju i govori što računalo radi. Korak u funkciju prolazi u stvarni funkciju to ti je na liniji koda. Tako, na primjer, kao što printf (), da je funkcija, zar ne? Da sam htio fizički korak u printf () funkcije, Ja bi zapravo ići u komadu broj gdje je napisao printf () i vidjeti što se događa tamo. 

Ali obično, pretpostavimo da kod koje smo dati radi. Pretpostavljamo da printf () radi. Pretpostavljamo da GetInt () radi. Dakle, nema potrebe da se korak u tim funkcijama. Ali ako postoji funkcija da sami pišu koju želite provjeriti što se događa, što bi željeli korak u tu funkciju. 

Dakle, sada smo samo ćemo prekoračiti ovaj dio koda. Tako ćemo vidjeti. Oh, print, "O hai, kako mnogo promjena je dugovao? " Mi ne briga. Znamo da radi, tako da smo korak preko njega. 

Dakle nje, što je naš plutaju da mi smo initialized-- ili declared-- gore na vrhu, mi smo sada izjednačavanje to GetFloat (). Tako ćemo korak preko toga. A mi vidjeti na Dno ovdje, program me navelo da unos vrijednost. Tako ćemo Unesite vrijednost želimo testirati ovdje, što je 0,41. Veliki. 

Tako sada n- to vi vidite Ovdje, na bottom-- je stored-- jer mi još nisu zaobljeni, to je pohranjen u ovoj poput diva plovak koji je 0,4099999996, što je dovoljno blizu da naš svrhe, upravo sada, na 0,41. A onda ćemo vidjeti kasnije, kao što smo nastavak koračni preko programa, Nakon ovog, n postala zaokružene centi postao 41. Veliki. Dakle, znamo da naše zaokruživanja radi. Znamo da imamo točan broj centi, pa znamo da je to zapravo nije problem. 

Tako smo i dalje napravio u ovom programu. Idemo ovdje. I tako, nakon ove linije koda, mi treba znati koliko četvrtine imamo. Mi korak više. A vidiš mi, u stvari, ima jedan kvartal, jer smo oduzeti 25 iz naše početne vrijednosti 41. I imamo 16 otišao u našim centi. 

Da li su svi shvate kako Program je napravio preko i zašto centi sada postala 16 i zašto, sada, kovanica je postao 1? Je li svatko slijedi tu logiku? Cool. Tako da u tom trenutku Program je radni, zar ne? Znamo to radi točno ono što mi to želimo. A mi zapravo nije moraju ispisati, oh, što je centa u ovom trenutku, Što je kovanice u ovom trenutku. 

Mi i dalje ide kroz program. Korak više. Cool. Idemo preko novčića. Veliki. Vidimo da je uzeo off 0,10 $ za dime. I sada imamo dva novčića. To je točno. 

Idemo preko novčana jedinica i vidimo da imamo lijevo preko centi. Hmm, to je čudno. Ovdje gore na programu, trebao sam da oduzme moje novčana jedinica. Možda jednostavno nisam bila radi te crte pravo. I nažalost, možete vidjeti ovdje, jer znamo da smo koračni kroz linije 32 i 33, to je gdje je naš program nepropisno imao varijabli trčanje. Tako možemo pogledati i vidjeti, oh, Ja oduzimanjem centi ovdje ali nisam zapravo dodajući da moj novac vrijednosti. Ja sam dodao da centi. A ja ne želim dodati centi, želim dodati novca. Dakle, ako smo promijenili da bi kovanica, imamo program rada. Mogu se izvoditi check50. Vi samo možete izaći iz GDB prava ovdje i onda pokrenuti check50 opet. Upravo sam mogao učiniti. Moram napraviti pohlepni. 0.41. I ovdje, to je tisak iz pravi odgovor. 

Dakle, kao što vi vidite, GDB je stvarno moćan alat kad imamo toliko broj događa i toliko varijabli da je teško za nas, kao što je ljudski, pratiti. Računalo, u GDB program za pronalaženje pogrešaka, ima mogućnost pratiti sve. Znam, u Visionaire, vi vjerojatno možda pogoditi neke segmentacije greške zato što su trčanje izvan granica svoje polje. U primjeru Caesar, koji je upravo ono što sam provoditi ovdje. 

Tako sam zaboravio provjeriti Što će se dogoditi ako ja nisu imali dva argumente naredbenog retka. Samo nisam stavio u toj prijavi. I tako, ako sam pokrenuti Debug-- postaviti moja prijelomna točka na pravo postoji. Vodim Debug. 

U REDU. Da. Pa zapravo, GDB je trebao da su mi rekli tamo bio kriv segmentacije tamo. Ne znam što se događa pravo postoji, ali kad sam ga vodio, to je radio. Kada pokrenete linija koda putem i GDB možda samo iznenada prestati na vas, ići gore i pogledajte što je crvena pogreška. To će vam reći, hej, ti imao kvar segmentiranja, što znači da ste pokušali pristupiti Prostor u niz koji nije postojao. Da. 

Dakle, u sljedećem problemu Postavite ovaj tjedan, vi vjerojatno će imati puno varijable plutajući oko. Nećeš biti sigurni što svi oni znače u određenom trenutku. Dakle GDB stvarno će vam pomoći u otkrivanju što su sve izjednačavanje i biti u mogućnosti da se vidi da vizualno. Je li netko zbunjeni o tome ništa od toga radi? Cool. U redu. Tako je nakon toga smo će roniti pravo u četiri različite vrste sorti za ovaj tjedan. Koliko vas prvo od svega, prije nego što počnemo, Pročitao cijelu spec za pset3? U REDU. Ja sam ponosan na vas momci. To je kao pola klase, koji je znatno više nego prošli put. 

Dakle, to je super, jer kad govorimo o sadržaju u lecture-- ili žao, u section-- volim povezati mnogo toga natrag na ono što je pset i kako želite implementirati da u svom pset. Dakle, ako ste došli s pročitajte spec, to će biti puno lakše za vas da razumijete ono što sam pričaju kad kažem, Oh, hej, to može biti jako dobro mjesto za provesti ovu vrstu. Dakle, oni od vas koji su pročitali spec znaju da, kao dio svoje pset, ti si idući u morati napisati tip vrste. Dakle, to može biti vrlo korisno za puno vas danas. 

Tako ćemo krenuti s, u biti, najviše jednostavan tip od vrsta, odabir vrsta. Tipična algoritam za kako ćemo ići o tome is-- David je po njima sve u predavanje, pa ću se brzo kreću here-- je bitno, što imaju niz vrijednosti. I onda naći Najmanji Nesortirano vrijednost i zamijeniti tu vrijednost s prvi Nesortirano vrijednost. I onda ti samo ponavljamo s ostatkom vašeg popisa. 

I ovdje je vizualni objašnjenje kako bi to moglo raditi. Tako na primjer, ako smo za početak s nizom od pet elemenata, indeks 0 do 4, s 3, 5, 2, 6 i 4 vrijednosti stavljen u array-- tako upravo sada, samo ćemo pretpostaviti da su svi nesortiran jer nismo testirali drugačije. 

Pa kako izbor vrsta bi Rad je da bi prvi izvoditi kroz cijelosti od nerazvrstani polja. Bilo bi izabrati najmanju vrijednost. U ovom slučaju, 3, pravo Sada, je najmanji. Ona dobiva 5. Nope, 5 nije veći than-- ili mi je, ne manje than-- 3. Dakle, minimalna vrijednost je i dalje 3. I onda ste dobili na 2. Računalo vidi, oh, 2 manje od 3. 2. mora biti minimalna vrijednost. I tako 2 zamjene s tog prvog vrijednosti. 

Dakle, nakon što jednom prolazu, doista ne vidim koji su zamijenili 2 i 3. I samo ćemo nastaviti raditi ovo ponovno s ostatkom polja. Tako ćemo samo prolaze kroz posljednjih četiri indeksi polja. Mi ćemo vidjeti da 3 sljedeća minimalna vrijednost. Tako ćemo mijenjati da sa 4. I onda mi samo ide da bi trčanje kroz sve, na kraju, što doći do sortiranog niza u kojem 2, 3, 4, 5, i 6 su svi razvrstani. Da li su svi razumiju logiku kako je izbor vrsta radi? 

Vi samo morati nekakvu minimalne vrijednosti. Ti praćenje što je to. I kad god ga pronaći, možete ga zamijeniti s prvim vrijednosti u array-- ili, nije prvi value-- sljedeća vrijednost u polju. Cool. 

Dakle, što je vama vrsta Vidio iz kratak pogled, ćemo pseudokod ovo. Dakle, ako vi u leđa želite tvore skupinu, sve na stol može formirati malo partnera, idem da vam dečki poput tri minute samo kroz razgovor logika, na engleskom jeziku, kako bismo mogli provesti pseudokod napisati odabir vrsta. A tu je bombona. Molimo vas da dođete i dobiti slatkiše. Ako ste u leđima i želite Candy, ja mogu baciti bombon na vas. Zapravo, to you-- cool. O oprosti. U REDU. 

Dakle, ako želimo, kao klasa, pisati pseudokod koliko bi se moglo pristupiti ovaj problem, samo slobodno. Ja ću samo ići okolo i, kako, pitajte grupe za sljedeću liniju što bismo trebali raditi. Dakle, ako vi želite započeti off, što je prva stvar učiniti kada pokušavate implementirati način da se riješi ovaj program selektivno sortirati popis? Neka je samo pretpostavimo imaju niz, u redu? 

PUBLIKA: Vi želite stvoriti neke vrsta [nečujan] da si trčanje kroz cijelu lepezu. 

ANDI PENG: Tako je. Dakle, ti si idući u ištanje to ponoviti kroz svaki prostor, zar ne? Odlično. Ako vi želite mi dati Sljedeći line-- da, u leđa. 

PUBLIKA: Provjerite ih sve za najmanji. 

ANDI PENG: Tu idemo. Zato želimo proći i provjerite vidjeti što je minimalna vrijednost, zar ne? Idem skratiti da bi "min." Što vi želite učiniti nakon ste pronašli najmanju vrijednost? 

PUBLIKA: [nečujan] ANDI PENG: Znači ti si idući u ištanje to prebacite ga s prvom od tog niza, zar ne? To je početak, ja ću reći. U redu. Pa sada da ste zamijenili prvi jedan, što želiš raditi nakon toga? Dakle, sada znamo da je to neki ovdje mora biti najmanja vrijednost, zar ne? Onda imate dodatni odmor od niza koji je Nesortirano. Dakle, ono što želite učiniti ovdje, ako vas dečki žele mi dati sljedeći redak? PUBLIKA: Dakle želite ponoviti kroz ostatak polja. ANDI PENG: Da. I tako ono što se kroz iterating vrsta podrazumijeva ćemo vjerojatno trebati? Koja vrsta of-- 

PUBLIKA: Oh, dodatna varijabla? ANDI PENG: Vjerojatno drugi za petlje, zar ne? Tako smo vjerojatno idući u ištanje da ponoviti through-- super. A onda ćeš se vratiti i vjerojatno ponovno provjerite minimum, zar ne? I ti ćeš ponavljamo ovo, jer petlje samo ide držati trčanje, zar ne? 

Dakle, kao što vi vidite, mi samo opći pseudokod kako želimo ovaj program izgledati. Ovo ponoviti ovdje, ono što radimo obično je potrebno napisati u našem kodu ako želimo ponoviti preko jedne niz, što tip od strukture? Mislim Christabel već je to rekao prije. 

PUBLIKA: for petlje. 

ANDI PENG: for petlje? Točno. Dakle, ovo je vjerojatno će biti za petlju. Što je provjeriti ovdje će se podrazumijeva? Obično, ako želite provjeriti ako je nešto nešto else-- 

PUBLIKA: Ako. 

ANDI PENG: IF, zar ne? A onda je swap ovdje, mi ćemo ići preko kasnije, jer Davida prošao kroz koji je u predavanju, kao dobro. A onda druga ponoviti implies-- 

PUBLIKA: Još jedan za petlju. 

ANDI PENG: --another for petlja, upravo. Dakle, ako tražimo ovo ispravno, mi možete vidjeti da smo vjerojatno Trebat će ugniježđena za petlje sa uvjet u tu a onda stvarni dio koda koji je će zamijeniti vrijednosti. Pa sam samo općenito napisano pseudokod kod ovdje. A onda smo zapravo događa fizički, kao klasu, pokušati provesti ovo danas. Idemo natrag u ovom IDE. 

Uh oh. Zašto je to not-- tu je. U REDU. Žao nam je, dopustite mi da povećavanje malo više. Idemo tamo. Sve što radim ovdje sam stvoren program koji se zove "izbor / sort.c." Napravio sam niz devet vrijednosti, 4, 8, 2, 1, 6, 9, 7, 5, 3. Trenutno, kao što možete Vidite, oni su neuređen. nje će biti broj koji kaže vam iznos vrijednosti imate u nizu. U ovom slučaju, imamo devet vrijednosti. A ja sam samo dobio za petlju ovdje koji ispisuje iz nesortiranog polje. 

I na kraju, ja sam dobio za petlja koja samo ispisuje ponovo. Dakle teoretski, ako ovaj program ispravno radi, na kraju, trebali vidjeti tiskani for petlje u kojoj 1, 2, 3, 4, 5, 6, 7, 8, 9 su sve ispravno u redu. 

Dakle, imamo našu pseudokod ovdje. Se bilo tko ištanje to-- Ja sam samo ići tražiti volunteers-- reci mi točno što tip, ako želimo, prvi, samo ponoviti kroz početku ovog niza? Što je linija koda sam Vjerojatno će trebati ovdje? 

PUBLIKA: [nečujan] 

ANDI PENG: Da, osjećam besplatno to-- Nažalost, ne moraju stajati up-- dojam besplatno podići svoj glas malo. 

PUBLIKA: Za int ja jednako 0-- 

ANDI PENG: Da, dobro. 

PUBLIKA: ja manja od duljine polja. 

ANDI PENG: Tako bi se u smeta ovdje, jer mi nemaju funkciju koja govori nam da je duljina niza, Već smo vrijednost koja pohranjuje to. Pravo? Još jedna stvar koju treba imati u mind-- u nizu devet vrijednosti, što su indeksi? Recimo samo to polje bilo 0 do 3. Vidiš da je posljednji Indeks je zapravo 3. To nije 4, iako postoji Četiri vrijednosti u nizu. 

Dakle ovdje, moramo biti vrlo oprezni o tome što je naš uvjet za duljinu će biti. 

PUBLIKA: Zar ne bi bilo n minus 1? ANDI PENG: To se događa n minus 1, točno. Da li to smisla, zašto to je n minus 1, svatko? To je zato što su nizovi nula indeksirana. Oni počinju u 0 i pokrenuti do n minus 1. Da, to je malo zeznuto. U REDU. I onda-- PUBLIKA: Isnt'1 da već zbrinuta ipak, strane samo ne govori "manje ili jednako "i samo govori" manje od? " 

ANDI PENG: To je jako dobro pitanje. Dakle, da. Ali isto tako, na način na koji smo provedbu provjere pravo, morate usporediti dvije vrijednosti. Tako da zapravo žele ostaviti "na" prazna. Jer ako usporedite ovo, ne ide ništa nakon nje usporediti, zar ne? Da. Tako i ++. Dodajmo naše zagrade u. Ups. Veliki. Tako smo na početku naše vanjske petlje. Dakle, sada smo vjerojatno želite stvoriti varijablu za čuvanje Staza od najmanjih vrijednosti, zar ne? Se bilo tko želi mi dati linija koda koji će to učiniti? Što nam je potrebno ako ćemo da želite spremiti nešto? 

Tako je. Možda bolje ime za koji bi be-- "temp" potpuno works-- možda više podesno zove biti, ako želimo najmanji value-- 

PUBLIKA: Min. ANDI PENG: min, tamo idemo. min bi bilo dobro. I tako ovdje, što nam je činiti želite inicijalizirati se? To je malo zeznuto. Zato odmah na početkom ovog niza, nisi pogledao ništa, zar ne? Pa što, automatski, ako mi smo samo na sam jednak 0, Što želimo inicijalizirati naš prvi minimalna vrijednost? PUBLIKA: ja. ANDI PENG: ja, zapravo. Christabel, zašto želimo da ga inicijalizirati na i? 

PUBLIKA: Jer, dobro, smo počevši 0. Pa zato što nemam ništa za usporedbu da, minimalna će završiti 0. 

ANDI PENG: Točno. Tako da je to točno. Budući da smo zapravo pogledao ništa još, ne znamo što je naša minimalna vrijednost. Želimo samo ga inicijalizirati na I, što, trenutno, nalazi upravo ovdje. I kao što smo i dalje pomicati prema dolje taj niz, vidjet ćemo da je, sa svakim Dodatni proći, ja koracima. I tako u tom trenutku, Vjerojatno će da žele biti minimalna, jer to će biti ono je početak nerazvrstani polja. Cool. 

Dakle, sada želimo dodati for petlja ovdje to će ponoviti kroz nesortirani ili ostatak ovog polja. Se bilo tko želi mi dati linija koda koji će to učiniti? Hint-- što trebamo ovdje dolje? Što će ići ovo za petlje? Da. PUBLIKA: Tako bismo želite imaju različite cijeli broj, zato što smo trčanje kroz ostatak od niza umjesto I, pa možda j. 

ANDI PENG: Da, j zvuči dobro za mene. Jednako? 

PUBLIKA: Tako bi ja plus 1, jer je ste počinju na sljedećem vrijednosti. A onda se na end-- Pa opet, j manji od n minus 1, a zatim j ++. ANDI PENG: Veliki. 

I onda ovdje, idemo želite provjeriti da li se susreli naš uvjet, zar ne? Jer želite mijenjati minimalnu vrijednost ako je to zapravo manji nego što je ste uspoređujući ga, zar ne? Pa što ćemo željeti ovdje? Provjerite vidjeti. Koja vrsta izjave su mi vjerojatno ide TI želite koristiti ako želite provjeriti nešto? 

PUBLIKA: An ako izjavi. 

ANDI PENG: if izjava. Dakle if-- i što će biti uvjet da želimo unutar naše ukoliko izjave? 

PUBLIKA: Ako je vrijednost j manja od vrijednosti i-- 

ANDI PENG: Točno. Dakle if-- tako da ovaj niz se naziva "polje". Veliki. Dakle, ako array-- što je to? Reci to ponovo. 

PUBLIKA: Ako array-j je manje od Niz-ja, onda bismo promijenili min. Dakle min bi j. 

ANDI PENG: Da li to smisla? U REDU. I sada ovdje, mi zapravo želite provesti zamjenu, zar ne? Pa sjećam, u predavanju, da je David, kad je je pokušavao the-- što je bilo zamijeniti it-- sok od naranče i milk-- 

PUBLIKA: To je bruto. 

ANDI PENG: Da, to je vrsta bruto. Ali to je bio prilično dobar Koncept pokazujući put. Dakle, mislim da od svojih vrijednosti ovdje. Imate niz od min, niz I., ili što god su mi pokušavamo zamijeniti ovdje. A vjerojatno ne možete ih sipati u jedni druge u isto vrijeme, zar ne? Dakle, što ćemo da je potrebno stvoriti ovdje kako bi se mijenjati vrijednosti ispravno? 

PUBLIKA: Privremena promjenjiva. 

ANDI PENG: Privremena promjenjiva. Tako ćemo učiniti int temp. Vidi, to će biti bolje Vrijeme to-- Hej, što je to? U REDU. Dakle, to bi bio bolji Vrijeme u ime varijablu "temp". Tako ćemo učiniti int temp. Što ćemo postavljen temp jednaka do ovdje? PUBLIKA: Min? ANDI PENG: To je malo zeznuto. To zapravo nije bitno na kraju. Nije važno što Kako bi se odlučite zamijeniti u dok god ste sigurni da ste praćenje ono što zamjene. 

PUBLIKA: To bi mogao biti niz-ja. 

ANDI PENG: Da, neka je učiniti array-i. I što onda je sljedeći redak koda mi želimo imati ovdje? PUBLIKA: array-ja jednako array-j. ANDI PENG: I na kraju? PUBLIKA: array-j jednak niz-ja. Publika: Ili niz-j jednaki Niz-temp-- ili, temp. 

ANDI PENG: U redu. Tako ćemo pokrenuti ovo i vidjeti ako će to raditi. Gdje se to događa? Oh, to je problem. Vidi, na liniji 40, mi smo pokušavate koristiti array-j? Ali gdje se j postoje samo u? 

PUBLIKA: U for petlji. ANDI PENG: Tako je. Dakle, što ćemo morati učiniti? 

PUBLIKA: Definirajte ga van the-- PUBLIKA: Da, mislim da imate koristiti drugo, ako izjava, zar ne? Dakle kao što je, ako je minimum-- Sve je u redu, da razmislim. 

ANDI Peng: Dečki, pokušajte pogledati Idemo vidjeti, što je nešto što možemo učiniti ovdje? 

PUBLIKA: U redu. Dakle, ako je minimalna nije jednak j-- tako dalje, ako je minimalna je i-- onda neće morati mijenjati. 

ANDI PENG: Da li to jednako ja? Što želiš reći ovdje? 

PUBLIKA: Ili da, ako je Minimalna nije jednak ja, da. ANDI PENG: U redu. Pa to rješava, vrsta, naši problemi. Ali to još uvijek ne riješi problem što će se dogoditi ako j-- jer j ne postoji izvan njega, što je Što želimo učiniti s njom? Objavite ga van? Pokušajmo trčanje ovo. Uh oh. Naša vrsta ne radi. 

Kao što možete vidjeti na prvi pogled Niz je imao te vrijednosti. I nakon toga bi trebao imati je u 1, 2, 3, 4, 5, 6, 7, 8, 9. Ne radi. Ahh. Što nam je činiti? PUBLIKA: Debug. ANDI PENG: U redu, možemo pokušati. Možemo ispravljanje. Smanjivanje malo. Idemo postaviti našim Kontrolna točka. Idemo volimo-članovima OK. 

Pa zato što smo već znali da ove linije, 15 do 22, su working-- jer sve što radim je Samo iterating kroz i printing-- Ja mogu ići naprijed i preskočiti to. Krenimo na liniji 25. OOP, neka mi dobili osloboditi od toga. 

PUBLIKA: Tako je prijelomna točka-a gdje počinje ispravljanje pogrešaka? ANDI PENG: ili zaustavlja. PUBLIKA: ili zaustavlja. ANDI PENG: Da. Možete postaviti više kontrolne točke i to samo može skočiti iz jednog u drugi. No, u ovom slučaju ne znamo gdje je greška se događa. Dakle, mi samo želimo početi od vrha prema dolje. Yep. U REDU. 

Dakle, ovaj redak ovdje, možemo uskočiti. Možete vidjeti ovdje, imamo niz. Oni su vrijednosti da su u nizu. Vidiš da je, kako je indeks 0, to odgovara value-- oh, Ja ću pokušati za uvećanje. Nažalost, to je stvarno teško da see-- na indeks polja 0, imamo vrijednost 4 i zatim slično i tako dalje. Mi imamo lokalne varijable. Sada sam je jednaka 0, što želimo da bude. 

I tako ćemo zadržati koračni kroz. Minimalnog jednak 0, što želimo da bude. A onda ulazimo naš drugi za petlje, ako je niz-j je manja od polja-i, koji nije. Pa jeste li vidjeli kako da preskočili to? 

PUBLIKA: Dakle, treba li, ako minimalna, sve that-- ne treba da biti u prva for petlja? ANDI PENG: Ne, jer dalje želite testirati. Želite napraviti usporedbu sve Vrijeme, čak i nakon što pokrenete kroz njega. Ne samo želite učiniti na prvom prolaznih. Želiš to učiniti s svaka dodatna opet proći. Dakle, želite da provjerite vaše stanje unutra. Dakle, mi samo ide na držati trčanje ovuda. Dat ću ti dečki savjet. To ima veze s činjenicom da kada ste checking vaš uvjetno, niste provjeru za ispravan indeksa. Dakle, sada ste provjere niz indeks j manji od niza indeks i. No, ono što radiš gore na Početkom za petlje? Niste li postavljanje j jednak I.? 

Da, tako da možemo zapravo zatvorili debugger ovdje. Tako ćemo pogledati našu pseudokod. For-- ćemo početi na sam jednak 0. Mi ćemo ići do n minus 1. Pogledajmo, nije mi imamo to pravo? Da, to je u redu. 

Pa onda iznutra ovdje smo će stvoriti minimalnu vrijednost i postaviti to jednako i. Jesmo li to učiniti? Da, to učinio. Sada u našem unutarnjem za petlju, mi smo učiniti j jednak ja se n 1 minus. Jesmo li to učiniti? Doista, mi to učinili. 

Pa ipak, što smo uspoređujući ovdje? 

PUBLIKA: j plus 1. ANDI PENG: Točno. A onda idete da želite postaviti Vaš minimalno jednak j plus 1, kao i. Tako sam prošao kroz to jako brzo. Razumijem da li vi momci zašto je j plus 1? U REDU. 

Dakle, u svom polju, u Vaš prvi proći kroz, Vaš for petlji, za int ja jednak 0, neka je samo Pretpostavljamo da je to još nije promijenio. Imamo niz, u potpunosti, samo četiri Nesortirani elemente, zar ne? Dakle, želimo inicijalizirati i jednaka 0. I ja se događa samo prođite kroz ovaj petlje. I tako je u prvom prolazu, idemo inicijalizirati varijablu pod nazivom "min" koji je također jednako ja, jer nemamo minimalnu vrijednost. Tako da je sada jednaka 0, kao dobro. A onda ćemo proći. I želimo opet ponoviti. Sada kada smo otkrili što je naša minimalna je, želimo ponoviti kroz opet vidjeti ako je usporedbom, zar ne? Tako j, ovdje će na jednako i, što je 0. A onda, ako niz j plus ja, koji je onaj koji je pored više, što je manje nego što vaš trenutni minimum vrijednost, što želite mijenjati. 

Pa neka je samo reći da smo nema, kao što je, 2, 5, 1, 8. Upravo sada, ja je jednak 0 i j je jednak 0. I to je naša minimalna vrijednost. Ako array-j plus i-- pa ako jedan to je poslije onog Gledamo je veća od one prije nje, to će postati minimum. 

Dakle ovdje vidimo da 5 nije manja od toga. Dakle, to će ne biti 5. Vidimo da je 1 manje od 2, zar ne? Dakle, sada znamo da je naša minimalna je će biti vrijednost indeksa na 0, 1, 2. Da? I onda kada se ovdje, možete mijenjati ispravne vrijednosti. 

Pa kad vi jednostavno su vlasništvo j prije, ne gleda na jedan nakon njega. Gledate istu vrijednost, što Zato jednostavno ne radi ništa. Znači li to da smisla svima, Zato je potrebno da se plus 1 tamo? U REDU. Sada samo trčanje kroz to da bi je li ostatak koda je ispravan. Zašto se to događa? Ah, to je min ovdje. Mi smo bili uspoređujući pogrešnu vrijednost. O ne. 

O da, ovdje smo zamjene pogrešne vrijednosti, kao dobro. Budući da smo bili u potrazi na i i j. To su oni bili smo provjeru. Mi zapravo žele mijenjati minimalna, trenutna minimalna, s onim što ona vani. A što vi vidite dolje Ovdje imamo sortirani niz. To jednostavno morali učiniti s Činjenica da kada smo provjere Vrijednosti su nas uspoređuju, nismo bili u potrazi na pravim vrijednostima. Tražili smo na istom jednom Ovdje, zapravo ne zamjene. Morate pogledajte jedan pored na njega i onda možete mijenjati. Dakle, to je ono što je vrsta prislušni naš kod prije. I ono što sam učinio ovdje je sve debugger može učiniti za vas Upravo sam to učinio na odbora, zato što je lakše vidjeti nego pokušava za povećavanje na ispravljanje pogrešaka. Znači li to da smisla svima? Cool. 

U redu. Možemo prijeći na razgovor o asimptotske zapis koji je samo fancy način rekavši runtimes svih tih vrsta. Pa ja znam Davida, u predavanju, dotakla trajanjima. I on je otišao kroz cijeli formuli kako izračunati runtimes. Bez brige o tome. Ako ste stvarno znatiželjan o tome kako se to radi, slobodno razgovarati sa mnom nakon dijelu. Možemo prošetati Formule zajedno. No, svi ti dečki moraju stvarno znam je da je n na kvadrat preko 2 je ista stvar kao n na kvadrat. Budući da najveći broj, eksponent, raste najviše. I tako za naše potrebe, sve nam je stalo je da je div broj koji raste. 

Dakle, ono što je najbolje, Runtime od odabira vrste? Ako ćeš imati se ponoviti kroz popis a zatim ponoviti kroz Ostatak tog popisa, koliko puta su ćete vjerojatno, u najgorem case-- u najboljem slučaju, sorry-- izvoditi kroz? Možda je bolje pitanje pitati, što je najgori slučaj Runtime od odabira vrste. PUBLIKA: n na kvadrat. ANDI PENG: To je n na kvadrat, zar ne. Tako jednostavan način da mislite to je kao, svaki put imate dva ugniježđena za petlje, to će biti n na kvadrat. Jer ne samo da su ti prolazi kroz još jednom, morate se vratiti oko i prođite kroz njega jednom u svakom vrijednosti. Dakle, u tom slučaju, vi radite n puta n na kvadrat, koji is-- žao, n puta n, koja je jednaka n na kvadrat. 

A vrsta je i malo jedinstvena u smislu da nije važno ako ti vrijednosti su već u redu. I dalje će se izvoditi kroz ionako. Recimo samo da je to bio 1, 2, 3, 4. Bez obzira da li ili ne to je u red, i dalje bi vodio kroz i još uvijek provjeriti minimalnu vrijednost. To bi napravio Isti broj provjera svaki put, čak i ako je to nije zapravo ništa dirati. 

Dakle, u takvom slučaju, najbolje i najgore runtimes su zapravo ekvivalent. Dakle, očekivani izvođenja od odabira vrste, koju odredi simbolom od theta, theta, u ovom slučaju, Također bi se n na kvadrat. Sva tri od njih će se n na kvadrat. Jesu li svi jasno zašto vrijeme izvođenja n na kvadrat? 

U redu. Dakle, Samo ću se brzo pokretanje kroz ostatak vrstama. Algoritam za mjehurić sort-- zapamtite, ovo je bio prvi David prijeđe u predavanju. U osnovi, vi korak cijeli popis a vi ste samo swap-- Usporedite dvije odjednom. A ako je veća, nego ti samo ih zamijeniti. Dakle, ako su veća, što bi zamijeniti. Imam službeni ovdje. 

Pa neka je samo reći da je imao 8, 6, 4, 2. Ti bi usporediti 8 i 6. Ti bi ih morati zamijeniti. Ti bi usporediti 8 i 4. Ti bi ih morati zamijeniti. Ako morate mijenjati 8 i 2, promijenite ih kako je dobro. Tako je u tom smislu, što možete vidjeti, igrao tijekom dugog vremenskog razdoblja, kako se vrijednosti vrsta mjehurić krajevi, što je razlog zašto smo ga nazvati mjehurić vrsta. 

Mi bi samo pokrenuti kroz ponovno naš drugi prolaz, a naš treći proći, i naš četvrti proći. U osnovi, Bubble sort samo radi dok ne bi bilo više swap. Dakle, u tom smislu, ovo je samo opći pseudokod za to. Bez brige, to će sve biti online. Mi ne moramo zapravo ići preko toga. 

Mi samo inicijalizirati brojača varijabla koja počinje na 0. A mi ponoviti kroz cijeli niz. A ako jedna vrijednost is-- ako je to vrijednost veća od te vrijednosti, ti ćeš ih zamijeniti. I onda si jednostavno će zadržati ide. A ti ćeš brojati. A ti si samo ide da radi to dok je brojač je veći od 0, što znači da je svaki put morate zamijeniti, znate da želite ići natrag i ponovno provjeriti. Želite li zadržati provjere sve dok ne znate da ne moram mijenjati više. 

Dakle, što su najbolje i najgore Slučaj trajanjima mjehurića vrste? I hint-- to je zapravo drugačija od odabira vrste u smislu da ta dva odgovora nisu isti. Razmislite o tome što će se dogoditi u slučaj, ako je već riješeno. I razmišljati o tome što će se dogoditi ako je to u slučaju kada nije riješeno. A možete vrsta pokrenuti kroz zašto to događa. Dat ću ti dečki, kao što su, 30 sekunde razmišljati o tome. 

U REDU. Se bilo tko imati pogodak na ono što je najgori slučaj runtime od mjehurića vrste je? Da. 

PUBLIKA: Biste li se, poput, n puta n minus 1 ili nešto slično? Kao i svaki put radi, to je samo, kao, jedna zamjena manje da što god to bilo. 

ANDI PENG: Da, tako ti si potpuno u pravu. A ovo je slučaj u kojem svoj Odgovor je zapravo složenija od onoga što je potrebno dati. Dakle, to će run-- sam će izbrisati sve ovo ovdje. Jesu li svi dobro? Mogu li izbrisati ovo? U REDU. Ti si idući u trčanje kroz n puta prvi put, zar ne? I oni će se izvoditi kroz n minus 1 drugi put, zar ne? A onda idete zadržati ide, n moja 2, i tako dalje. David je to učinio u predavanju, gdje je, ako zbrojiti sve te vrijednosti, dobivate nešto što je volimo-članovima yeah-- više od 2, što u biti samo smanjuje do n na kvadrat. Ti si idući u dobiti čudno udio tamo. I tako samo znam da n kvadratna uvijek ima prednost u odnosu na frakcije. I tako, u ovom slučaju, najgore runtime bi se n na kvadrat. Ako je u silaznom red, mislim, vi napraviti swap svaki put. 

Što bi, potencijalno, najbolji slučaj izvođenja? Recimo, ako je popis je već bio kako bi, što bi runtime biti? 

PUBLIKA: n. ANDI PENG: To je nje, točno. A zašto je to nje? PUBLIKA: jer ste upravo moraju provjeriti na svaki jednom. ANDI PENG: Točno. Tako na najbolji mogući izvođenja, ako je ovaj popis je već bio sorted-- recimo 1, 2, 3, 4-- si će samo proći kroz, što bi provjeriti, vidjet ćete, oh, svi oni uspjeti. Nisam za zamjenu. Gotov sam. Dakle, u tom slučaju, to je samo n ili broj koraka koji ste upravo morao provjeriti na prvom popisu. 

A nakon toga, mi sada hit umetanje vrsta, gdje algoritam je bitno podijeliti je u razvrstana i nerazvrstani dio. A onda jedan po jedan, su Nesortirani vrijednosti umetnuta u njihovo primjereno pozicije u početku liste. 

Tako, na primjer, imamo Popis 3, 5, 2, 6, 4 ponovo. Mi znamo da je to trenutno nesortirani jer smo upravo počeo gledati u njega. Mi pogledamo i znamo da je prva vrijednost razvrstani, zar ne? Ako ste samo gleda na niz jedna veličina, znaš da je to riješeno. 

Dakle, onda znamo da je ostala četiri su Nesortirano. Idemo kroz i vidimo tu vrijednost. Vratimo. Vidiš onu vrijednost 5? Mi se na to gledate. Mi to usporediti s 3. Znamo da je veći od 3, tako da smo znali da je to riješeno. Dakle, sada znamo da su prve dvije su razvrstani a zadnje tri nisu. 

Mi pogledamo 2. Prvo smo to provjeriti s 5. Je li to manje od 5? Nije. Dakle, moramo držati obličje dolje. Zatim provjerite 2 gola 3. Je li to manje od? Ne. Pa znate 2 mora biti umetnuta sprijeda i 3 i 5 oba moraju biti gurnula van. Učinite to opet sa 6 i 4. A mi samo držati ček u biti, gdje smo samo provjeriti, ček, ček. I dok je u pravu Položaj smo vrsta samo umetnite ga u pravom položaju, što je, gdje ime je došao iz. 

Dakle, to je samo algoritam, pseudokod po sebi, vrsta, kako bismo provesti umetanje vrsta. Pseudokod je ovdje. To je sve na internetu. Bez brige, ako ti dečki su pokušavaju kopirati ovaj dolje. Dakle, još jednom, ista question-- ono bilo bi najbolje i najgore runtimes za umetanje vrste? To je vrlo slično na posljednje pitanje. Dat ću ti dečki, kao što su, 30 sekunde razmišljati o tome što je dobro. 

OK bilo tko želi daj mi najgori runtime? Da. 

PUBLIKA: n na kvadrat. 

ANDI PENG: To je n na kvadrat. I zašto je n kvadrat? 

PUBLIKA: Budući da u obrnutom redoslijedu, imate proći kroz n puta n, koji is-- ANDI PENG: Da, točno. Dakle ista stvar kao u balonu vrste. Ako ovaj popis u silaznom redoslijedu, ti si morati provjeriti prvi puta. I onda sa svakim dodatna vrijednost, ti si morati provjeriti protiv svaki vrijednosti, zar ne? I tako zajedno, ti si idući u izraditi N proći vremena još n prođe, što je n kvadrat. Što o najboljem slučaju? Da. 

PUBLIKA: n minus 1, jer je Prvi je već na kvadrat. 

ANDI PENG: Dakle, u neposrednoj blizini. Odgovor je zapravo nje. Jer dok se prvi je razvrstani, ne može ga actually-- samo smo sreće, u to primjer, da 2 dogodilo se da je najmanji broj. Ali to neće uvijek biti slučaj. Ako 2 već razvrstani u početku ali izgleda i tu je 1 ovdje U 1. će ga čekić. A to će završiti gore bitak nabasao ionako. 

Dakle, u najboljem slučaju, to je zapravo samo će biti n. Ako imate 1, 2, 3, 4, 5, 6, 7, 8, ti si će se izvoditi kroz da cijeli popis odjednom provjeriti da li je sve u redu. Jesu li svi jasno na trčanje Vremena izbor isto kao i? Znam da ću kroz to jako brzo. Ali samo znam da ako znate opći pojmovi, te bi trebao biti dobar. U REDU. Pa ja samo ću ti dečki možda, kao što je, minutu da razgovaraju sa svojim susjedima o tome što su samo neki od glavnih razlika između ovih tipova sorti. Mi ćemo ići preko uskoro. PUBLIKA: Oh, u redu. ANDI PENG: Da. U REDU. Cool, neka je ponovno sastati kao klasa. U REDU. Dakle, to je neka vrsta otvoreni pitanje u smislu da ima puno odgovora na njih. A mi ćemo ići preko neke od njih nakratko. Samo sam htjela da ti dečki razmišljam o tome što diferencira Sve tri vrste sorti. I ja sam čuo, također, velika question-- što se spajaju vrsta učiniti? Veliko pitanje, jer je to ono što smo pokrivaju sljedeća. 

Dakle spojiti vrsta je jedna vrsta koja funkcionira vrlo različito od ostalih vrsta. Kako vi možete see-- David učinio da demo gdje je imao sve svjež zvukovi vidim kako spojiti vrsta ran, kao, beskonačno brže od druge dvije vrste? U REDU. Dakle, to je zato spajanje sortirati provodi tu podjelu i osvojiti koncept da smo govorio o puno u predavanju. U tom smislu da smo htjeli raditi pametnije, a ne teže, kada podijelimo i osvojiti probleme, te ih razbiti prema dolje, a zatim ih staviti zajedno, dobre stvari uvijek događaju. 

Tako je način na koji se spajaju sortirati suštini radi je da dijeli nesortirani niz na pola. A onda je dobio dvije polovice polja. I to samo sortira te dvije polovice. To samo čuva podjele na pola, u pola, na pola dok je sve sortirano a onda rekurzivno stavlja sve to zajedno. 

Tako da je stvarno sažetak. Dakle, ovo je samo malo pseudokod. Znači li to da smisla u način na koji je pokrenut? Pa neka je samo reći imate niz od n elemenata, zar ne? Ako je n manji od 2, možete se vratiti. Zato što znam da ako postoji samo jedna stvar, to mora biti riješeno. Inače, možete sortirati lijevu polovicu, i onda sortirati desnu polovicu, i onda spojiti. 

Dakle, dok je izgleda stvarno lako, u stvarnosti, razmišljam o tome je vrsta teško. Jer ti si kao, Pa, to je vrsta radi na sebi. Pravo? To je trčanje po sebi. Dakle, u tom smislu, David dotaknu nakon rekurzije u klasi. I to je koncept ćemo govoriti o više. To je da je ovaj, ove dvije linije Ovdje, zapravo je samo program to govori da se izvoditi s različitim ulazom. Dakle, umjesto da se izvoditi u cjelokupnost n elemenata, možete ga razbiti dolje u lijeva polovica, a pravo pola a zatim ga ponovno pokrenuti. 

A onda ćemo gledati na to vizualno, jer sam vizualni učenik. To radi bolje za mene. Tako ćemo pogledati vizualnom primjer ovdje. 

Recimo imamo niz, šest Elementi, 3, 5, 2, 6, 4, 1, nije riješeno. U redu, tu je mnogo na ovoj stranici. Dakle, ako vi možete pogledati na Prvi korak ovdje, 3, 5, 2, 6, 4, 1, možete ga podijeliti na pola. Imate 3, 5, 2, 6, 4, 1. Vi znate da oni vas aren't-- ne znam ako su razvrstani ili ne, tako da bi ih se razbije, na pola, na pola, na pola, sve dok na kraju, imate samo jedan element. I jedan element uvijek razvrstani, zar ne? 

Tako znamo da je 3, 5, 2, 4, 6, 1, po sebi, su razvrstani. I sada možemo ih staviti natrag zajedno. Dakle, mi znamo 3, 5. Mi smo stavili one zajedno. Mi znamo da je to riješeno. Na 2 je još tamo. Možemo staviti 4 i 6 zajedno. Znamo da je to riješeno, pa smo stavili zajedno. A 1 je tu. 

I onda samo pogledajte ove dvije polovice ovdje. Imate 3, 5, 2, 2, 3, 5. Vi samo možete usporediti početak svega. Zato što znam da je to razvrstani a vi znate da je to riješeno. Pa onda ne morate usporediti 5, samo usporediti 3. A 2 je manje od 3, tako da znate 2 mora ići na kraju. 

Ista stvar tamo. U 1. mora ići ovdje. I onda kad idete staviti te dvije vrijednosti zajedno, znate da je to razvrstani i znate da je to riješeno. Pa onda 1 i 2 je 1 manja od 2. To vam govori da je 1 treba ići na kraju ovog čak i bez gledanja na 3 ili 5. A onda je 4, možete jednostavno ček, to ide ovdje. Ne morate gledati na 5. Ista stvar sa 6. Znaš da je to samo 6-- ne treba pogledao. 

I tako na taj način, ti si Samo se štedi puno koraka kada se uspoređuju. Ne morate usporediti svaku Element protiv drugih elemenata. Vi samo usporediti protiv onih što vam je potrebno da ga usporediti protiv. Dakle, to je vrsta apstraktnog koncepta. Bez brige, ako to nije dosta vas udarajući još u pravu. Ali općenito, to je kako spajanje vrsta radova. Pitanja, kratkih pitanja, prije nego što sam krenuti dalje? Da. 

PUBLIKA: Pa rekli ste da uzmete U 1., a zatim 4, i 6 i stavio ih u. Pa nisu those-- nisu gledaš ih kao zasebne elemente, a ne kao cjelinu? ANDI PENG: Da. Dakle, što se događa je da u osnovi stvaraju potpuno novi niz. Tako da znate da, ovdje sam dva polja od veličine 3, zar ne? Pa znaš da je moj sortirati niz treba imati šest elemenata. Dakle, vi samo stvoriti Nova količina memorije. Dakle, ti si nešto kao biti rasipan memorije, ali to nije važno zato što je tako mali. Tako da pogledajte 1 a vi pogledajte 2. I znate da je 1 manje od 2. Pa znaš da je 1 bi trebao ići u početak svima. 

Ne morate čak ni pogledajte 3 i 5. Pa znate 1 ide tamo. Onda ti zapravo odsjeći na 1. To je, kao što je, mrtav za nas. Onda imamo samo 2, 3, 5, i 6, a zatim 4. A onda znate da, vas usporediti 4 i 2, oh, 2 bi trebao ići tamo. Znači li pasti na 2 dolje, možete ga odsjeći. Pa onda samo imaju 3 i 5 u 4 i 6. A ti samo nastavi ga sjeckanje off dok ih stavite u nizu. 

PUBLIKA: Znači ti si samo uvijek Uspoređujući [nečujan]? 

ANDI PENG: Točno. Dakle, u tom smislu, da ste Samo usporedbom, u biti, jedan broj u odnosu na drugi broj. A budući da znate da je to riješeno, te ne moraju gledati kroz svi brojevi. Vi samo morati gledati na prvom. I onda možete jednostavno pasti ih dolje, jer znate oni pripadaju, gdje im je potrebno da pripadaju. Da. Dobro pitanje. 

A onda, ako bilo koji od vas su malo ambiciozan, slobodno pogledajte ovaj kod. To je zapravo fizička implementacija kako bismo pisati pisma vrsta. A što možete vidjeti, to je vrlo kratko. Ali ideje iza to su prilično složena. Dakle, ako se osjećate kao crtež ovo u zadaću večeras, slobodno. 

U REDU. Tako David prijeđe ovo predavanje. Koji su najbolji slučaj runtimes, najgori slučaj runtimes, a očekivani runtimes udruživanja vrste? Nekoliko sekundi razmišljati. To je prilično teško, ali nekako intuitivno, ako mislite o tome. U redu. 

PUBLIKA: Je najgori slučaj n log n? ANDI PENG: Točno. A zašto je to n log n. 

PUBLIKA: Nije li to zato što postaje eksponencijalno brže, pa to je kao funkcija koje umjesto da jednostavno se n kvadrat ili nešto? ANDI PENG: Točno. Dakle, razlog zašto je runtime na to n log n because-- što ste vi radi u svim ovim koracima? Ti si samo cijepanje na pola, zar ne? I tako, kada činimo prijavite, sve što to radiš se dijeljenjem problem na pola, na pola, na pola, na više polovice. I u tom smislu, možete vrsta od eliminirati linearnog modela koje smo koristili. Jer kada nasjeckajte stvari u poluvremenu, to je zapisnik. To je samo matematički način ga zastupa. 

I onda na kraju, na kraju, ti si samo što još jednu loptu kroz staviti ih sve u redu, zar ne? I tako, ako je samo da provjeriti jednu stvar, to je nje. I tako ste vrsta množenjem dva zajedno. Dakle, to je kao da ste je dobio da konačna provjerite n ovdje sa log n ovdje. A ako pomnožite ih, što je n log n. 

I tako, najbolje i najgore Slučaj i očekuje se svi n log n. To je također kao drugoj vrsti. To je kao izbor vrste u smislu da ne smeta što je vaš Popis je, to samo ide kako napraviti istu stvar svaki put. U REDU. Dakle, kao što vi vidite, iako su vrste koje smo prošli through-- n kvadrat, nije učinkovit. Pa čak i to n log n Ne najučinkovitiji. Ako ti dečki su znatiželjni, postoji sortirati mehanizmi koji su toliko učinkovita da su oni gotovo suštini stan u runtime. 

Imaš neki dnevnik n-a. Imaš neki log log n-a. Mi ne dirati po njima u ovoj klasi upravo sada. Ali, ako ti dečki su znatiželjni, slobodno google, što je Najučinkovitiji mehanizmi sortiranje. Ne znam, postoje neke one stvarno smiješno, volimo-članovima ima nekih stvarno smiješne one koje ljudi čine. A vi se pitate kako ikada razmišljali o tome. Dakle google, ako imate neki rezervni vrijeme, na što su neke smiješne načine da people-- kao učinkovite svatko od ljudi bili u mogućnosti provesti vrste. U REDU. I ovdje je samo zgodan mali grafikon. Znam sve vas, prije tog kviza 0, će biti u vašoj sobi, vjerojatno pokušavajući zapamtiti da. Tako da je lijepo tamo za vas momci. Samo ne zaboravite logiku da made-- zašto ti brojevi su događaju. Ako ste uvijek gubi, samo bi sigurni da znate što vrste su. A možete pokrenuti preko ih u svom umu shvatiti zašto oni odgovori su ti odgovori. 

U redu. Tako ćemo premjestiti na kraju, na traženje. Jer kao što je one od vas koji su pročitali pset, Pretraživanje je također dio ovotjedni Problem postavlja. Vi ćete biti zatraženo da provede dvije vrste pretraživanja. Jedan je linearni pretraživanje i jedan je binarno traženje. 

Tako je linearna pretraživanje je prilično jednostavan. Vi samo želite potražiti elementa popisa vidjeti ako ste ga dobili. Vi samo morati ponoviti kroz. A ako je jednak nešto, možete jednostavno vratiti, zar ne? Ali onaj koji smo najviše zainteresirani za razgovor o je binarno pretraživanje, pravo, koje je podijeli pa vladaj mehanizam koji David pokazujući na predavanju. 

Zapamti imeniku primjer da je stalno odgoja, onaj koji je vrsta borili malo o ovoj protekloj godini, gdje ste podijeliti problem na pola, na pola, na pola, opet i opet, dok ne pronađete ono što tražite? A ti si dobio Runtime to kao dobro. A što možete vidjeti, to je značajno učinkovitije od bilo koje druge vrste pretraživanja. 

Dakle, način na koji bismo otići o provedbi binarnu pretragu je, ako smo imali niz, indeks 0 do 6, sedam elemenata možemo gledati u sredini, redu- ispričavam se, ako je naše pitanje first-- ako želimo postaviti pitanje, ne Niz sadrži element 7, Očito, kao ljudi, i da tako mala polje, to je lako za nas reći da. No, način provedbe binarnu Traženje bi gledati u sredini. 

Znamo da je indeks 3 srednji, jer mi znam postoji sedam elemenata. Što 7 podijeljeni po 2? Možete odsjeći da dodatni 1. Imaš 3 u sredini. Tako je niz 3 jednaka do 7? To nije, zar ne? Ali možemo napraviti par čekova. Je niz 3 manje od 7 ili je niz 3 veći od 7? 

A mi znamo da je manje od 7. Dakle, znamo da, oh, ona mora ne biti u lijevoj polovici. Znamo da to mora biti u desnoj polovici, zar ne? Dakle, možemo samo odsjeći pola niz. Mi čak ne moraju na to gledate više. Jer znamo da pola naše problem-- znamo da je odgovor u pravo polovice našeg problema. Tako smo samo pogledajte kako je sada. 

Dakle, sada gledamo sredina ono što je ostalo. To Indeks 5. Mi radimo isti ček opet a vidimo da je to manja. Dakle, mi gledamo na lijevoj strani kako. A onda ćemo vidjeti da je ček. Je vrijednost niz na Indeks 4 jednaka do 7? Je. Tako možemo vratiti istina, jer našli smo vrijednosti u našem listu. Da li način na koji sam otišao kroz koje imaju smisla svima? U REDU. Dat ću ti dečki možda, kao što je, tri, četiri minute shvatiti kako pseudokod to. 

Pa zamislite Pitao sam vas napisati funkcija zove pretragu () koji se vratio vrijednost, Boolean vrijednost, to je istina ili false-- slično, vrijedi ako je utvrdio vrijednost false ako nije. I onda si prošao u vrijednosti koju tražili u vrijednosti, koje je array-- oh, definitivno staviti da na krivom mjestu. U REDU. Uglavnom, koji bi trebao imati bio na pravom vrijednosti. A onda int n broj elemenata u tom nizu. Kako bi idete o težak da pseudokod taj problem? Dat ću ti dečki poput tri minute da to učiniti. Ne, mislim da only-- Da, postoji jedan pravi ovdje. PUBLIKA: Mogu li? ANDI PENG: Da, dobio sam. Je li to radi? OK super. 

U REDU. U redu dečki, mi smo će ga obuzdati. U REDU. Dakle, pretpostavimo da imamo ovu lijepu Malo polje sn vrijednosti u njemu. Nisam nacrtati linije. No, kako bi se ići o pokušavajući napisati to? Da li netko želi daj mi prvu liniju? Ako želite da mi daju prva linija ovog pseudokod. 

PUBLIKA: [nečujan] PUBLIKA: želiš na ponoviti through-- PUBLIKA: Samo još jedan za petlju? PUBLIKA: --for. 

ANDI PENG: Pa ovo je malo zeznuto. Razmislite about-- želite držati trčanje ovu petlju iznova i iznova do kada? 

PUBLIKA: Do [nečujan] vrijednost je jednaka toj vrijednosti. ANDI PENG: Točno. Tako da zapravo možete samo write-- možemo čak ga pojednostaviti više. Mi samo možemo učiniti while petlja, zar ne? Tako možete samo imati loop-- znamo da je to neko vrijeme. No, za sada, idem reći "petlju" - kroz što? Petlja until-- ono što je naša završava stanje? Mislim da sam čuo. Čuo sam da je netko to reći. 

Publika: Vrijednosti jednaka sredini. ANDI PENG: Ponovit. PUBLIKA: Ili, dok se Vrijednost ste u potrazi je jednaka srednja vrijednost. 

ANDI PENG: Što ako to nije tamo? Što ako je vrijednost koju traži je zapravo u tom nizu? PUBLIKA: Vraćate 1. 

ANDI PENG: Ali ono što želimo petlje sve dok, ako imamo stanje? Da. 

PUBLIKA: Do postoji samo jedna vrijednost? ANDI PENG: Možete petlje until-- tako da znate da ste će imati max vrijednosti, zar ne? I znate da idete imati min vrijednost, pravo? Zato također, da je nešto Zaboravio sam reći prije, da nešto što je kritički o binarnom pretraživanje je da je vaš niz već riješeno. Budući da ne postoji način radi to ako su samo slučajne vrijednosti. Ne znam je li on to veći od drugoga, zar ne? 

Dakle, znate da je vaš i Max Vaši minuta ovdje, zar ne? Ako ste idući u biti podešavanje Vaša max u vašem min i mid-- neka je samo pretpostaviti da Sredinom vrijednost je u pravu here-- ti si idući u osnovi petlje sve dok je vaš minimum otprilike isto kao max, pravo, ili ako vaš Max nije isto kao minuta. Pravo? Jer kad se to dogodi, znate da si na kraju pogodio istu vrijednost. Dakle, želite petlju dok vam min je manji od ili jednak to-- Ups, ne manje od ili jednake, Drugi način around-- max je. 

Je li to smisla? Uzeo sam nekoliko pokušaja da se to pravo. Ali petlje do maks vrijednosti je u biti skoro manje od ili jednak vašem minimum, zar ne? To je kad znaš da ste konvergentne. PUBLIKA: Kad bi vaš maksimalni vrijednost biti manja od minimalno? ANDI PENG: Ako zadržite podešavanja, koja je ono što ćemo da se radi na tome. Ima li to smisla? Minimalna i maksimalna samo integers da smo vjerojatno će htjeti stvoriti zadržati zapis u kojem tražimo. Budući da je niz postoji bez obzira na to što radimo. Kao, nismo zapravo fizički cijepanje off niz, zar ne? Mi samo podešavanje gdje tražimo. Ima li to smisla? 

PUBLIKA: Da. 

ANDI PENG: U redu. Dakle, ako je to uvjet za naše petlji, Što želimo unutar ove petlje? Što ćemo se žele učiniti? Pa sada, imamo max i min, pravo, Vjerojatno je stvorio ovdje negdje. Idemo vjerojatno želite pronaći sredinu, pravo? Kako ćemo biti mogućnosti naći sredinu? Što je mathematical-- PUBLIKA: Max plus min podijeljena 2. ANDI PENG: Točno. Ima li to smisla? I nemojte vi vidite zašto smo nije samo use-- zašto je to učinio umjesto da radi samo n podijeljeni po 2? To je zato što je n vrijednost to će ostati isti. Pravo? No, kao što smo prilagoditi naše najmanje i maksimalne vrijednosti, oni će se promijeniti. I kao rezultat toga, naša sredina će se promijeniti. Pa zato što želimo to učiniti upravo ovdje. U REDU. 

A onda, sad kad našli smo our-- da. 

PUBLIKA: Just a quick question-- kad kažeš min i max, smo uz pretpostavku da to je već razvrstani? 

ANDI PENG: Da, to je zapravo Preduvjet za binarnog pretraživanja, koje morate znati je to riješeno. Koji je razlog zašto vrsta, pišete u svom Problem postaviti prije binarnog pretraživanja. U REDU. Pa sada da znamo gdje je naša sredina je, što želiš raditi ovdje? 

PUBLIKA: Želimo usporedbu da na drugi. ANDI PENG: Točno. Dakle, ti si idući u usporedbu Sredinom na vrijednosti, zar ne? A što to kažem nas kada usporedimo? Što želimo učiniti nakon toga? 

PUBLIKA: Ako je vrijednost veća od sredine, želimo ga odrezati. ANDI PENG: Točno. Dakle, ako je vrijednost veća od sredine, mi smo idući u ištanje to promijenili minimalne i maxes, zar ne? Što želimo promijeniti? Dakle, ako znamo da je vrijednost negdje ovdje, što ti mi za promjenu? Želimo promijeniti naš Minimalna biti sredinom, zar ne? A onda drugo, ako je to u ovom pola, što želimo promijeniti? 

PUBLIKA: Vaša maksimalna. ANDI PENG: Da. A onda ste samo ide zadržati petlje, zar ne? Jer sada, nakon jedne iteracije putem, imaš max ovdje. A onda možete ponovno izračunati sredine. A onda možete usporediti. A vi ćete zadržati ide do minuta i maxes su u biti konvergentne. A to je kada znaš da je si pogodio kraj njega. A bilo ste ga pronašli ili niste u tom trenutku. 

Da li to smisla svima? U REDU. To je prilično važno, jer ćete imati napisati to u kodu večeras. Ali ti dečki imaju prilično dobar Osjećaj ono što bi trebao biti događaj, što je dobro. U REDU. Dakle, imamo oko sedam minuta napustio odjeljak. Tako ćemo razgovarati o ovo pset da ćemo biti događaj. Dakle pset je podijeljen u dva dijela. Prva polovica uključuje provedbi nalaz u kojem ste napisali linearnog traženja, binarno traženje i sortiranje algoritam. 

Dakle, ovo je prvi Vrijeme u pset gdje mi ćemo biti dajući vam dečki što se zove Raspodjela kod, što je kod koje smo prethodno napisano, ali jednostavno ostavio neke dijelove off ti završiti pisanje. Dakle, momci, kada pogledate ovaj broj, možda ćete stvarno dobiti prepala. Ako ste samo željeli, ahh, ja ne znam što da radi, Ne znam, kao da se čini tako komplicirano, ahh, opustite se. Uredu je. Pročitajte spec. Spec će vam objasniti točno Što sve od tih programa rade. 

Na primjer, generate.c je program koji će doći sa svojim pset. Vi zapravo ne morate dirati, ali trebali shvatiti što to radite. I generate.c, sve što radi je bilo generiranje slučajnih brojeva ili možete dati ga sjeme, poput planiran broj koji je potrebno, i to stvara više brojeva. Dakle, postoji određeni način provesti generate.c u kojoj možete jednostavno napraviti hrpa brojeva za vas testirati svoje druge metode dalje. 

Dakle, ako ste htjeli, za primjer, testirati svoje otkriće, što bi željeli pokrenuti generate.c, generiranje hrpa brojeva, a zatim pokrenuti pomagača funkciju. Vaš pomagači funkcija gdje ste zapravo fizički pisanja koda. A misliti pomagača kao knjižnica datoteke pišete da otkriće zove. I tako u helpers.c, vi ćete ne traži i sortiranje. 

A onda idete na osnovi Samo ih sve staviti zajedno. Spec će vam reći kako staviti na komandne linije. A vi ćete biti u mogućnosti testirati hoće li ili nije tvoja vrsta i traženje rade. Cool. Je li netko već počeli i Problemi s kojima se susreću ili pitanja oni su sada s tim? U REDU. 

PUBLIKA: Čekaj. Imam jedno pitanje. 

ANDI PENG: Da. 

PUBLIKA: Tako sam počeo raditi linearni traži u helpers.c i to nije stvarno radi. Ali onda kasnije sam saznala smo upravo morati izbrisati i napraviti binarno pretraživanje. Tako je to važno, ako to ne radi? 

ANDI PENG: Kratak odgovor je ne. No, budući da smo not-- PUBLIKA: Ali nitko ne zapravo provjeru. ANDI PENG: Mi smo Nikad će to vidjeti. Ali vjerojatno želite učiniti je li vaša potraga radi. Jer ako vaš linearni traži ne radi, onda su šanse vaš binarni Traženje ne ide na posao kao dobro. Jer imate slične Logika u oba od njih. I ne, to nije važno. Dakle, jedini ćete uključiti u su vrsta i binarno traženje. Da. 

I također, puno djece su pokušava sastaviti helpers.c. Nisi zapravo dopušteno to učiniti, jer helpers.c nema glavnu ulogu. I tako da bi trebao samo se zapravo sastavljanju generiranje i naći, jer naći pozive helpers.c i djeluje u njemu. Tako da čini ispravljanje pogrešaka bol u kundak. No, to je ono što moramo učiniti. PUBLIKA: Vi samo napraviti sve, zar ne? ANDI PENG: Možete samo učiniti sve što je dobro, da. U REDU. Dakle, to je to u smislu onoga što pset traži da svi rade. Ako imate bilo kakvih pitanja, osjećam slobodno me pitajte nakon dijelu. Ja ću biti ovdje, kao što su, 20 minuta. 

I da, u pset-a stvarno nije tako loše. Vi bi trebali biti u redu. To, samo slijedite upute. Vrsta imaju osjećaj, logično, što treba biti događa i što će biti u redu. Nemojte biti previše uplašena. Postoji mnogo koda već napisao tamo. Nemojte biti previše uplašena, ako ne shvatiti što sve to znači. Ako je puno, to je potpuno u redu. I doći do radnog vremena. Mi ćemo vam pomoći da se pogledati. 

PUBLIKA: Uz doplatu Funkcije, ne gledamo one gore? 

ANDI PENG: Da, oni su u kodu. U igri 15, pola to je napisano već za vas. Dakle, oni su funkcije Već u kodu. Yep. U redu. Pa, mnogo sreće. To je odvratno dan. Dakle, nadamo se da dečki ne osjećam previše loše borave unutar i kodiranje.