SPEAKER 1: Hej svima! Dobro došli natrag u odjeljak. Tako mi je vidjeti kako mnogi od vas oboje ovdje, i svatko tko gleda na internetu. Dakle, kao što je to uobičajeno dobrodošlice leđa. Nadam se da ste imali lijep vikend, puno odmora, opuštanja. Bilo je lijepo jučer. Dakle, nadam se da ste uživali u prirodi. 

Dakle, prvi par najave. Ocjenjivanja. Dakle, većina od vas treba imati stečen e-mail od mene o svom Scratch Pset, kao i ocjenjivanje za Pset 1. Dakle, samo par stvari. Budite sigurni da koristite check50 u style50. To su trebali biti resursi za vas dečki, kako bi bili sigurni da ste dobivanje onoliko bodova kao što možete bez bespotrebno ih izgubiti. Dakle, stvari poput stila su vrlo važni. Mi ćemo poletjeti za to. Neki od vas su već primijetio da iz svog Pset. I check50 je samo stvarno jednostavan način kako bi bili sigurni da smo zapravo vraćaju ono treba se vratiti korisnika, i da sve radi ispravno. 

Na drugoj bilješci, provjerite je li upload stvari na ispravan mapu. To čini moj život samo malo teže ako upload Pset 2 u Pset 1 jer kad sam preuzeti stvari, ne točno preuzeti. I znam da je malo klimav u sustavu da se navikne, nego samo biti super oprezni, ako je samo za mene, tako da kada ste dobivanje e-pošte na sličan 02:00 i ja sam ocjenjivanja. Ako ne uzrokuju moram gledati sve oko za svoj Pset. Cool. 

Znam da je rano, ali ja totalno dobio skinut straže po eseju koji je zbog ovog petka toj moji profesori su baš kao i, oh yeah. Zapamtite, imate esej zbog petak. Dakle, znam da nitko ne voli razmišljati o midterms, ali vaš prvi kviz je 15. listopada, koji listopad počinje ovaj tjedan. Dakle, to bi moglo biti što prije nego što se očekivalo je sve. Znači da niste bacili nespremni kada Spominjem idući tjedan dio tog oh, Vaš kviz sljedeći tjedan, mislio sam Ja bih vam dati malo više od Upozoravamo vas sada. 

Dakle, vaš problem postaviti, broj tri. Kako su ljudi pročitali spec iz znatiželje? U redu. Imamo par. Vrsta dolje od prošlog tjedno, ali to je u redu. Znam da je to bilo lijepo van. Tako break out. Definitivno nakon što bi učinio danas pročitao tvoj spec najmanje probati kao preuzimanje Raspodjela kod i trčanje kao prvi početni Ono što se od vas tražiti da. Budući da smo se koriste distribucije koda i knjižnica da mi je samo što su using-- --It samo drugi put smo učinili ovo Pset, lude stvari mogu dogoditi sa svojim aparatom, a vi želite da kako je sada u odnosu na kasnije. 

Jer ako je to u četvrtak navečer, ili je to U srijedu navečer, a iz nekog razloga Vaš aparat jednostavno ne želite pokrenuti s knjižnicom ili distribucije koda, to znači ne mogu ni početi raditi kodiranje. Zato što se ne može provjeriti vidjeti ako to radi. Vaš neće biti u mogućnosti da li se izrađuje. Želite li voditi brigu o onima koji rano tjedna, kad još uvijek možete mi e-mail ili jedan od drugih TFS, i možemo dobiti one fiksne. Jer to su problemi koji će vas zaustaviti od izrade stvarni napredak. Nije kao jedan bug, da možete samo vrsta preskočiti. Ako imate problema sa svojim uređaja ili distribucije koda, stvarno želite da se to uzeti brigu o prije nego kasnije. Dakle, čak i ako nećeš zapravo započeti kodiranja, preuzeti distribuciju koda, pročitajte spec, pobrinite sve što radi tamo. OK? Ako samo možete to učiniti, ja Obećavam svoje živote će biti lakše. I tako ste vjerojatno idući to učiniti upravo sada pravo? U redu. Dakle, bilo kakva pitanja tamo? Bilo logističke stvari? Svatko je dobro? U redu. 

Odricanje za one ste u sobi i on-line. Idem se pokušava prebaciti između PowerPoint u aparatu jer mi se događa da se radi neke kodiranje Danas po popularnim potražnje za anonimne Prijedlog anketa sam poslao prošli tjedan. Dakle, mi ćemo biti događaj neki kodiranje. Dakle, ako ti dečki također žele na vatru svoje aparate, a trebali ste dobili e-mail od mene, s uzorkom datoteku. Slobodno to učiniti. 

Dakle, idemo razgovarati o GDB, što je ispravljanje pogrešaka. To će vam pomoći vrsta shvatiti gdje stvari idu krivo u svom kodu. To je zapravo samo način da korak putem koda, kao što se događa, i biti u mogućnosti ispisati varijable ili vidjeti što se zapravo događa pod napa stihova svoj program samo trčanje, to je kao rasjedanjem, a ti si kao, bez ideje što se upravo ovdje dogodilo. Ne znam što linija nije uspio u. Ne znam gdje je pošlo po zlu. Dakle, GDB će vam pomoći u tome. Isto tako, ako odlučite nastavljaju da, i uzeti 61, to će stvarno, stvarno biti vaš najbolji prijatelj, jer ja mogu vam reći jer sam prolazio kroz tu klasu. 

Idemo pogledati binarnom pretraživanje, što ako se vi sjećate veliki telefonski imenik primjer Spektakl iz razreda. Mi ćemo biti provedbi toga, i šetnju kroz to malo više, a onda idemo kroz četiri različite vrste, koje su mjehurić, Izbor, umetanje, i spoji. Cool. Dakle, GDB kao što sam spomenuo, je ispravljanje pogrešaka. A to su vrste veliko stvari, veliki funkcije ili naredbe koje koristite u GDB, i ja ću hodati što kroz demo to u sekundi. 

Dakle, to nije samo će ostati sažetak. Pokušat ću i učiniti ga kao beton što je moguće za vas dečki. Dakle, razbiti. To je bilo će biti stanka kao, neki broj, koji predstavlja liniju u svom programu, ili možete imenovati funkciju. Dakle, ako ti kažeš razbiti glavna, to će zaustaviti na glavni, i neka vas kroz tu funkciju. 

Isto tako, ako imate neki vanjski funkcioniraju kao swap ili Cube, da smo gledali na prošli tjedan. Ako kažeš razbiti jedan od onih, kad god je vaš program pogodi koja, to će vas čekati na reci to što učiniti. Prije nego što će izvršiti samo tako da vam zapravo mogao zakoračiti u funkciji i vidjeti što se događa. Dakle, Zatim, samo preskače Sljedeći linija, ide preko funkcije. Korak. To su sve mala apstraktna. Dakle, ja samo idem na trčanje kroz njih, ali ćete ih vidjeti u uporabi u sekundi. 

Zakoračite u funkciju. Dakle, kao što sam rekao, kao i kod swap, to bi omogućuju vam da se zapravo kao da ste kao što je fizički stupi unutra, možete igrati s tim varijablama, print što su oni, vidjeti što se događa. Popis će doslovno samo ispisati iz okolnih koda. Dakle, ako ste vrsta zaboraviti gdje ste u svom programu, ili pitate što se događa oko njega, to će samo ispisati segment više vole pet ili šest linije oko njega. Dakle, možete dobiti orijentirani o tome gdje se nalazite. 

Ispišite neku varijablu. Dakle, ako imate ključ kao U Cezara, koji ćemo gledati. Možete reći Print ključ u bilo kojem trenutku. To će vam reći ono što je vrijednost tako da, možda negdje na putu, što prepisani preko ključ. Vi zapravo možete reći da je zbog zapravo možete promatrati tu vrijednost. 

U mještana, samo ispise iz svojih lokalnih varijabli. Dakle, bilo da ste unutar petlje, a vi samo želite vidjeti kao, oh. Što je moj ja? Što je ovo ključna vrijednost da sam inicijalizirati ovdje? Koja je poruka u ovom trenutku? To će samo ispisati sve od onih, pa vas ne moraju pojedinačno kažu, Ispis I. Ispis poruka. Ispis ključ. A onda prikaz. Što da radi kao ti korak kroz program, to samo ćete biti sigurni da je to prikazujući neke određene varijable u svakom trenutku. Tako da also-- --it je vrsta prečaca gdje ne morate držati ide kao, oh. Ispis Ključ ili Print I. To samo automatski će to učiniti za vas. 

Dakle, s tim, idemo da vidim kako to ide. Ja ću pokušati switch do mog uređaja. Pogledajte ako ja mogu to učiniti. Sve. Mi samo će to ogledalo. Nema ništa ludo na moj laptop ionako. U redu. To treba biti ovaj jedan. To je tako malen. Da vidimo možemo li to učiniti. 

U redu. Alice je očito bori ovdje samo malo, ali ćemo ga dobiti u Momento. U redu. Mi samo će povećati ovaj. U redu. Može li svatko vrsta vidjeli? Možda malo? Znam da je malo mali. Ne mogu sasvim shvatiti kako bi se ova veća. Ako itko zna. Se bilo tko znati kako to učiniti veći? U redu. Idemo roll s njom. Nije važno bilo kako, jer to je samo to je kod koji ti dečki trebali ima. 

Što je važnije je terminal ovdje. I mi imamo ovdje Zašto je to tako mali? Postavke. Oh. Istina Ike. Kako je ovo? Od tamo. Je li to bolje za sve? U redu ,. Cool. 

Znate, kada ste u CS razred tehničkih poteškoća su vrsta dio the-- Dakle, neka je jasno to. U redu. Dakle, upravo ovdje u odjeljku, koje smo imali ovdje. Cezar je izvršna datoteka. Tako sam to napravio. Dakle, jedna stvar realizirati s GDB je da se to radi samo na izvršne datoteke. Dakle, ne možete ga pokrenuti na dotsy. Morate zapravo čine sigurni da je vaš broj prikuplja, i da ona zapravo može pokrenuti. 

Dakle, pobrinite se da, ako se to ne dogodi sastaviti, preuzmite ga sastaviti, tako da možete vrsta trčanje kroz njega. Dakle, za početak GDB, sve što trebate učiniti, Gloria tipa GDB, a onda samo datoteku koju želite. Uvijek sam se krivo Cezara. No, želite biti sigurni budući da je izvršna, TI dot bljeskalice, tako da znači ideš pokrenuti CSI idete izvršiti ova datoteka ili s ispravljanje pogrešaka. U redu. Dakle, što učiniti da biste dobili ta vrsta besmislice. To je samo sve stvari o ispravljanje pogrešaka. Vi stvarno ne morate brinuti o tome sada. I kao što vidite, imamo ovo otvoreni navodnik, BDP, bliski navodnik, i samo vrsta izgleda kao naš naredbenog retka, zar ne? 

Dakle, ono što želimo do-- -SO, Prva stvar je želimo izabrati mjesto da ga razbiti. Dakle, postoji jedan bug U ovom programu Caesar da sam uvesti, da ćemo saznati. To što se radi je potrebno ulaz Barfoo u svim kape, a iz nekog razloga to ne mijenja A. To samo ostavlja ona sama, sve ostalo je točno, ali drugo pismo Ostaje nepromijenjena. Dakle, idemo pokušati shvatiti zašto je to tako. Dakle, prva stvar koju obično želite učiniti kada počnete na GDB je shvatiti gdje ga razbiti. 

Dakle, Cezar je prilično kratkog programa. Imamo samo jednu funkciju, zar ne? Ono što je naša funkcija u cara? Postoji samo jedna funkcija, Glavni zar ne? Glavna je funkcija za sve svoje programe. Ako nisu imali Main, mogao bih biti malo zabrinuti upravo sada, ali nadam se da ste svi imali Main tamo. Dakle, ono što možemo učiniti je da možemo Samo slomiti Main, baš kao što je to. Dakle, on kaže, u redu. Mi smo postavili naše Prijelomna točka jedan tamo. 

Dakle, sada je stvar za zapamtiti je Cezar traje jedan naredbeni redak argument pravo a nismo učinili da nigdje još. Dakle, ono što vam je činiti kada što zapravo ići na trčanje Program, bilo koji program koji ste trčanje u GDB da treba naredbenog retka argumenti, ti ćeš ulaz kada se prvi put početi prikazivati. Dakle, u ovom slučaju, mi radimo Trčanje s ključem od tri. I to će zapravo početi. 

Dakle, ako vidite ovdje, imamo Ako RC nije jednako 2. Dakle, ako vi svi imaju da je datoteka koja sam poslao gore vidjet ćete da je to poput Prva linija naša glavna zadaća, zar ne? To je provjera da li imamo točan broj argumenata. Dakle, ako pitate Ako RC točna, možete učiniti nešto jednostavno poput Print RH. RC je dva, koji je ono što smo očekivali, zar ne? 

Dakle, možemo ići Dalje, i dalje kroz. Dakle, imamo neku tipku tamo. I možemo ispisati naš ključ kako bi bili sigurni da je to točno. Zanimljivi. Nije baš ono što smo očekivali. Dakle, jedna stvar realizirati s GDB također je da to nije sve što je zapravo pogodio Zatim, da je linija koja ste upravo vidjeli zapravo izvršava. Dakle, u ovom slučaju Ključ nije dodijeljena još. Dakle, ključ je neka smeća vrijednost da vidite na dnu tamo. Negativan 120-- $ --It je milijardu i nešto čudne stvari zar ne? Nije ključ koji smo očekivali. Ali ako smo hit Dalje, a onda smo probati i ispis ključ, to je tri. 

Svi su to vidjeli? Dakle, ako se nešto da ste kao, pričekajte. To je posve u redu, a ja ne znam kako će se to dogoditi, jer sve što želim učiniti se dodijeliti broj, promjenjiva, pokušajte udaranje Dalje, pokušajte ispis opet, i vidjeti ako to radi. Zato što će samo izvršiti i zapravo dodijeliti nešto poslije tebe hit Next. Smisla svima? Aha? 

ZVUČNIK 2: Kada slučajna brojeva, što to znači? 

SPEAKER 1: To je samo slučajna. To je samo smeće. To je samo nešto što je vaš Računalo će se nasumce. Cool. Dakle, sada možemo kretati kroz, i tako Sada imamo običan tekst GetString. Dakle, dopustite mi da uvedu ono će se dogoditi kad smo hit Next ovdje. Naš GDB vrsta nestaje, zar ne? To je zato što GetString sada izvršenja, zar ne? Dakle, kad smo vidjeli običan tekst jednako GetString, otvoreni navodnik i navodnik, a mi hit Dalje, koja ima zapravo izvršava sada. Dakle, to je čekao nam ulazni nešto. 

Dakle, idemo na ulazu našu hranu koja je ono što se nije kao što sam vam rekao i to samo govori da je završio izvršenja, koji zatvorena Nosač znači da je izlaska iz tog kruga. Dakle, možemo pogoditi Dalje, a sada, kao što sam sigurni da ste svi upoznati s Cezara, to je ono što je ova linija će učiniti. To je za Int sam jednak 0, N jednak Strlen, običan tekst, a zatim I je manji od nje, ja, plus, plus. Što je to petlje učiniti? Otvorite poruku. Cool. Dakle, počnimo raditi to. 

Dakle, trebali ovo stanje podudaraju, za naš prvi? Ako je B, to je običan tekst I. smo mogu dobiti informacije o našim mještanima. Dakle, sam je nula, a ako šest, koji je očekujemo, a naš ključ je tri. Sve to ima smisla, zar ne? Ti brojevi su svi upravo ono što bi trebao biti. Dakle, pjevušiti? SPEAKER 3: Imam slučajnih brojeva za mine. SPEAKER 1: Pa, mi --we može check-- Možete razgovarati o tome da se u sekundu. Ali ti bi trebao biti uzimajući ovaj. Dakle, ako imamo kapital B za naš prvi, ovo stanje treba ga uhvatiti, zar ne? Dakle, ako smo hit Dalje, vidimo da je to Ako zapravo izvršava. Jer ako ste nakon zajedno u kodu, ta crta ovdje, gdje sam običan tekst zamjenjuje s ovim aritmetika, samo izvršava ako je If Uvjet je ispravan pravo? 

GDB samo će vam pokazati stvari koje su zapravo obavljaju. Dakle, ako je to Ako uvjet nije ispunjen, to je samo ide za prijelaz na sljedeći redak. OK? Dakle, imamo to. To znači da je nosač zatvorena iz tog kruga sada. Dakle, to će početi ponovno. Baš kao što je to. Dakle, da možemo dobiti informacije o našim mještanima ovdje i vidimo da je naš prvi Pismo se promijenilo, zar ne? Sada E, kao što bi trebao biti. Dakle, možemo nastaviti dalje. 

I mi smo tu provjeru. A to ček trebali raditi, zar ne? To je A. To treba mijenjati Tri slova naprijed. Ali ako primijetite, mi dobili nešto drugo. Dakle, u ovom slučaju ovdje, to je uhvaćen je, i tako ova linija pogubljeni, što mijenjati naš B. No, u ovom slučaju ovdje smo da je to samo ga preskočiti, i otišao do [? L siff. ?] Dakle, nešto što se događa tamo. Ono što je reći da je, znamo da bi trebalo uhvatiti ovdje, ali nije. Može li itko vidjeti što naši Problem je u toj liniji? To je vrlo minute stvar. A možete se također može pogledati kodu. Također je line-- zaboraviti ono što je linija U there-- ali je u [nečujan]. Da? 

SPEAKER 4: To je na više od Stranica ako ga pročitati u knjizi. SPEAKER 1: Točno. Dakle, debugger ne može reći što je to, ali debugger mogao dobiti do linije da znate ne funkcionira. A ponekad, kada se posebno kasnije u semestru, kada imate posla sa sto, a sto nekoliko linija koda, a vi ne znam gdje to nije, To je sjajan način da to učinite. Dakle, pronašli smo našu grešku. Možete ga popraviti u datoteci, i onda bi mogao ponovo pokrenuti, i sve će raditi savršeno. A najveća stvar je to može činiti kao, u redu. Da. Cool. Znao si ono što tražite. Dakle, što je znao što treba učiniti. 

GDB može biti super korisno jer vas možete ispisati sve te stvari koje ste ne bi. To je mnogo više koristan nego printf. Koliko koristite kao printf izjavama shvatiti gdje bug je, zar ne? Dakle, s ovim, ti ne moraju vraćati, i sviđa komentirajući u Printf ili komentiranjem, i shvatiti što trebali biti tiskanje. To zapravo samo vam omogućuje da korak kroz, isprintati stvari kao što prolaziš, tako, možete promatrati kako se mijenja u realnom vremenu, kao svoj program radi. 

I to ne uzeti malo malo koristi za dobivanje. Ja bih visoko preporučiti samo vrsta bude malo frustriran s njim za sada. Ako ćete potrošiti sat tijekom sljedeći tjedan učenje kako koristiti GDB, uštedjet ćete sebe toliko vremena kasnije. I doslovno. možemo reći to ljudi svake godine, i sjećam se kad sam uzeo klase, bio sam kao, ja ću biti u redu. Ne. Pset 6 Izašao je i sam bio kao, ja ću učiti kako koristiti GDB, jer ja ne znam znam što se ovdje događa. 

Dakle, ako se uzme vrijeme, tako koristiti ga na manje programe da ćeš biti radi na, kao što je rad kroz nešto slično Visionare, kao što je ovaj. Ili, ako želite dodatnu praksu, siguran sam Mogao bih se s lud programima, za vas ispravljanje ako želite. 

Ali, ako se samo uzeti malo vremena kako bi dobili naviknuti na to, samo se poigrati s njim, to stvarno će vam dobro poslužiti. I to je stvarno jedan od one stvari koje ste upravo morati probati i dobiti vaše ruke prljave sa, prije nego što stvarno ga razumijem. Stvarno sam ga samo jednom shvatiti Morao sam ispravljanje stvari s njim, i to je puno ljepše imati ideju kako ispravljanje prije nego kasnije. U redu. Cool. Znam da je vrsta kao što ubrzani tečaj u GDB, i ja definitivno će raditi na dobivanje to izgledati veće sljedeći put. Cool. 

Dakle, ako se vratimo na naše PowerPoint. Hoće li ovo raditi? AWH. Da. U redu. Dakle, ako vam zatreba bilo koji od oni opet, tu je popis. Dakle Binarna pretrage, koje svatko pamti veliki spektakl Davida kopiranja telefonske knjige u pola. Ja stvarno ne shvaćam telefonski imenici više, jer kao gdje vi dobili telefonske knjige ovih dana? Ja stvarno ne znam. Binarna pretrage. Se bilo tko sjetiti koliko Binarna Traži djela? Svatko uopće? Da? SPEAKER 5: Znate kada pogledate kojih polovica to će biti u, na temelju toga, i riješiti drugu polovicu. 

SPEAKER 1 Točno. Dakle, binarna pretrage, to je vrsta A- --we željeli nazvati ga podijeli pa vladaj. Dakle, što ćete učiniti je ćete pogledati u sredini, a vi ćete vidjeti ako to odgovara ono što tražite. A ako se to ne dogodi, onda ćete pokušati shvatiti, je da će ostati polovina ili desna polovica. Dakle, to može biti ako ste u potrazi na nešto što je abecednom, vidiš, oh. Da li Allison doći prije M? Da. Dakle, idemo pogledajte prvog poluvremena. 

Ili bi to moglo biti kao s brojevima. Sve što možete usporedbu, to može biti riješeno. Možete koristiti binarno pretraživanje na. Dakle, tko zapamtite ovo graf ili što je to? To je asimptotičnu složenosti. Dakle, ovaj graf jednostavno opisuje koliko dugo vodi vas riješiti problem što je možete povećati broj stvari da upotrebljavate. 

Dakle, imamo N, što je linearno vrijeme. Ako je više od dva N, koji je malo bolje, i dalje raste super brzo. A onda smo Prijavite se, što je ono što mi smatramo binarno pretraživanje. Ako primijetite, kao što je vaš problem dobiva mnogo i mnogo veći, Vrijeme vam je potrebno kako bi ga riješiti zapravo ne povećava toliko. To je kao usporediti ovdje u početku. Ti si kao, u redu. Sve što se ovdje zapravo ne obzira na to što neki koristimo, ali ste dobili na milijun, milijarda. Pokušavaš pronaći some-- --you're pokušavajući naći iglu u plastu sijena. 

Mislim da želite taj problem. Želiš tu složenost, a ne linearno, jer za sve vas znate li će biti u potrazi kroz svaki pojedinac igle, stvar sijena, pokušavaju tražiti vaše igle. I to nije previše zabavno po mom mišljenju. Volim brzo. Volim učinkovita. I kao vrijedni studenti Vi Dečki su, znaš raditi pametnije, Ne teže tipa stvar, kako ti može nadoknaditi tih algoritama. 

Dakle, idemo u šetnju kroz samo brzi primjer. Mislim da ti dečki trebali imati Ruka na Binary Traži, ali u slučaju da je netko malo fuzzy, žele ga ojačati, ćemo samo ići kroz primjer ovdje. Dakle, tražimo, ako polje sadrži sedam. 

Dakle, prva stvar koju radimo je gledati u sredini, zar ne? A i ti ćeš biti kodiranja Binarna Traži u samo sekundi. Dakle, to će biti zabavno. Tako smo gledati u Srednji mali nizovi 3. Da li 3 jednaka 7? Ne. To je šest. Dakle, to je manje od ili veći od sedam? Manje od. Da. Lijepo dečki posao. Osjećam volim da bih trebala imaju slatkiša jer sam želim ga izbaciti u dvorištima. To je ono što ću učiniti sljedeći tjedan. To će vas dečki oštar. 

Dakle, mi bacaju da Prva polovica, zar ne? ona je manja od. znamo da je sve na toj lijevoj strani će biti manje od onoga mi zapravo tražimo. Dakle, nema potrebe da se obratite pozornost na to. Samo zaboraviti o tome. Dakle, sada je gledamo na našoj desnoj strani, i gledamo na sredini tamo, a sada je devet. Dakle, 9 is-- --Everyone? Veći nego što smo tražite, zar ne? Dakle, idemo baciti daleko je sve u desno. Kao da je. Sada, svi smo s lijeve strane je jedan. Tako smo provjeriti, je li to ono što jedan tražimo? je. Pronašli smo ono što smo htjeli. Tako smo učinili. Bilinearnog pretrage. 

A ako primijetite, mi je imao sedam ulaza tamo. To nam samo uzeo kao tri puta, ali ako radite kao milijardu, vi znate koliko koraka da bi poduzeti ako smo imali četiri milijarde stvari? Bilo nagađanja? To je 32. 32 koraka kako pronaći nešto u četiri milijarde Element niz zbog ovlasti dva. Dakle, dva je 32, je na četiri milijarde eura. 

Dakle, prilično ludo kako ste i dalje u kao relativno malom broju koraka pronaći nešto u četiri milijarde elemenata. Dakle, na toj bilješci, mi smo ide to kod ove tako da vi zapravo može vrsta vide kako se to radi. U redu, tako da vi možete kodirati. Ja ću vas dečki pustiti razgovor za malo. Upoznajte ljude oko sebe, što je ono što je netko htio od prošlog odjeljka. 

Dakle, upoznati ljude oko vas. Razgovor za malo. I sve što želim od tebe dečki sada je samo pokušati stvoriti obris Pseudokod. OK? Opa. Sve što želim od vas dečki je da ste Samo će ispuniti u ovom slučaju, dok. Zato sam postavio to gornja i donje granice koja predstavljaju početak i kraj naše ponude. A što ćete zapravo loop i shvatiti što radimo u ovom while petlje. 

Dakle, ako možete shvatiti out-- Imam savjet there-- što su slučajevi da smo ovdje? Dakle, ako želite shvatiti slučajevi, mi ćemo Pseudokod onima a onda ćemo ih zapravo kodirati. I to će biti, ja mislim, nadam se da ću biti malo lakše nego što očekujete. Budući da to nije toliko broj, Zapravo, što je stvarno cool. 

Mm-hm? 

UČENIK: [nečujan]? INSTRUKTOR: Da. Bilo je nešto naći u sredini. 

UČENIK: Pa možemo koristiti. U redu. 

INSTRUKTOR: Savršeno. Dakle, to je prva stvar koju trebate učiniti. Dakle, pronaći sredinu. Veliki. Dakle, imate li ideju kako bismo mogli zapravo naći sredinu s kodom? 

UČENIK: Da. n preko 2? INSTRUKTOR: Pa n preko 2. Dakle, jedna stvar je da zapamtite da Vaši gornje i donje granice mijenjati. Mi stalno stežuća dio od niza smo u potrazi za. Tako n nad 2 će raditi samo za prvo radimo. Tako da gornji i donji u obzir, kako bismo mogli dobiti taj srednji elementa? Zato želimo sredini između gornje i donje, zar ne? Mm-hm? 

UČENIK: [nečujan]. 

INSTRUKTOR: Dakle, imamo neku sredinu. I to će biti veliko plus manji preko 2. Strašan. Tamo idemo. Jedan redak prema dolje. Vi ste na putu. Tako da sada imamo naš srednje, što želimo učiniti? Samo u cjelini. Ne morate ga kodirati. Da. UČENIK: [nečujan]? INSTRUKTOR: Dakle, to je plus, jer ste pronalaženje prosjeku između dva od njih. Dakle, ako mislite o njima kao vrsta povećanje sa strane, razmišljam o tome kako se približavate srednje, želite tako. Dakle, ako ste bili na obje strane srednje, a imamo kao 5 i 7. Kada ih dodati zajedno vam dobili 12, podijelite s 2, 6. 

Ponekad je teško objasniti zašto to radi, ali ako radite preko Primjer ponekad, to će vam pomoći shvatiti ako to bi trebao biti plus ili minus. Da. 

UČENIK: [nečujan] točno u sredini ako su imali slučaj gdje postoji puno manjem broju i kao jedan veliki broj? 

INSTRUKTOR: Dakle, sve što je potrebno je usred polja. Dakle, ako ste imali hrpu malih brojeva a onda se stvarno velik broj Na kraju, to ne smeta. Sve što je bitno je da oni su razvrstani, samo Želite gledati na sredini niz jer ste još uvijek rezanje svoj problem na pola. Cool. Tako da sada imamo srednje, što nam je činiti dalje? 

UČENIK: Usporedite. INSTRUKTOR: usporediti. Dakle, usporedite sredinu za value_wanted. Cool. Dakle, vidite ovdje imamo ova vrijednost želimo ovdje. Zapamtite ovo polje. Tako srednji odnosi na indeks. Dakle, želimo napraviti vrijednosti sredini. Ne zaboravite, ako želite za usporedbu, dvostruki jednakima. Možete napraviti jednu jednak si Samo će ga preraspodijeliti, a onda, naravno, to je će biti vrijednost koju želite. Dakle, nemojte to raditi. 

Tako ćemo vidjeti ako vrijednosti u sredini jednaka vrijednosti želimo. Ne zaboravite aparatić. Dropbox bi trebao otići. Dakle, što nam je činiti u tom slučaju? Ako je to ono što želimo vratiti? Mi pokušavamo reći. 

UČENIK: Ispis off. 

INSTRUKTOR: Pa, mi ne želim ispisati. Dakle, ovo je bool ovdje, tako da mi žele vratiti true ili false. Mi tvrdimo, je taj broj [? RRA? ?] Dakle, ako je to, samo mi vratiti to istina. Ako mogu čarolija istina. 

UČENIK: Zašto ne bi li se vratiti na nulu? INSTRUKTOR: tako da bi mogao povratak na nulu, ako ste htjeli. No, u ovom slučaju, jer naša funkcija vraća bool, moramo se vratiti bilo istinito ili lažno. UČENIK: Kad ste govoreći logički izraz, možete ga postaviti jednaka netočno? Kao, ako želim reći, ako je to uvjet nije upoznao, kao što je gornja jednako lažna. Hoće li razumjeti ako ste upravo stavili lažno na drugoj strani? INSTRUKTOR: Da. Pa zapravo, ako ste sve radi nešto kao što je gornja ili je niži, koji vraća true ili false i to je zapravo loše stil recimo jednaka jednaka istina ili jednakima jednako lažna. Želite li koristiti taj rezultat što je i sama kao ček. Nije ono što sam htio. To je ono što sam htjela. Tako je u slučaju tražiš o nečemu kao što je spasi ovaj u c. 

Dakle, ako imamo int glavni (prazninu) i nešto poput ovoga. A imate li je gornja neke ulaz i da ste molba ako možete učiniti nešto ovako? Pravo? UČENIK: Pokušavao sam to učiniti [nečujan]. Jer ako it's-- INSTRUKTOR: Upravo. Dakle, želite da to bude lažna, zar ne? UČENIK: Da. INSTRUKTOR: Dakle, u ovom slučaju želite izvršiti ako to nije istina. Dakle, super stvar koju ne postoji ova. Pa sjetite se uzvik Točka negira stvari? Ona kaže [nečujan] ne znači. Dakle, ako gledamo samo ovaj dio ovdje, ti bi kažu da se procjenjuje na lažna kao što želite da. Ne lažna istina koja znači to bi izvršiti. Znači li to smisla? UČENIK: Da. INSTRUKTOR: Strašan. U redu. Tako smo samo mogli vratiti istina u ovom slučaju. Tako sada imamo dva druga slučajeva u ovom slučaju. Koje su naše dvije drugi slučajevi? Ajmo to ovako učiniti. Pa počnimo s drugom Ako vrijednosti u sredini manja od vrijednosti želimo. Tako je naša vrijednost u sredini manje od vrijednosti koje tražimo. 

Zato što vezani vi mislim želimo ažurirati? Gornja ili niži? Gornji? Dakle, koja je strana niza ćemo se gleda? 

UČENIK: niže. 

INSTRUKTOR: Mi ćemo da se gleda na lijevo. Dakle, ako je ostalo nešto je manji. Dakle srednjom vrijednosti ovdje je manje od onoga što želimo. Dakle, želimo da se desna strana našeg polja. Tako ćemo ažurirati naš donja granica. Tako ćemo preraspodijeliti naše niže. A što misliš manji bi trebao biti? UČENIK: srednja vrijednost? INSTRUKTOR: Pa srednje value-- UČENIK: Plus 1. INSTRUKTOR: --plus 1. Može bilo tko reći mene zašto imamo da plus 1? 

UČENIK: [? Bez vrijednost?] više jednak njoj. 

INSTRUKTOR: Upravo. Budući da smo već znali da naša srednja vrijednost nije jednaka to i želimo ga isključuje od svih kasnijih pretraživanja. Ako ste zaboravili da je plus 1, ovaj će vam se svidjeti petlju na neodređeno vrijeme. A vi ćete samo biti uhvaćen u beskonačna petlja, a onda ćete segfault i stvari idu loše. Dakle, uvijek bi bili sigurni da niste uključujući vrijednost koju ste upravo pogledala. Tako ćemo se pobrinuti da se s plus 1. 

Tako sada imamo posljednji uvjet koji sam uvijek za sigurnost radi možete provjeriti ovdje, drugdje ako je vrijednost na srednji veća od vrijednosti želimo. To znači da želimo lijeva ruka na pola. Dakle, koje ćemo ažurirati? Gornji. A što je ovo jedna će biti jednak? Srednji minus 1, jer, Naravno, želimo kako bi bili sigurni da nismo gleda na toj srednjoj vrijednosti opet. I onda smo ga. To je to. To je sve binarno pretraživanje. Nije to loše, zar ne? To je kao 10 linija Kod sa bijelom prostoru. Dakle, vrlo moćan, vrlo korisno, hoćete ga koristiti u jednom od svojih kasnijih psets. Možda ne ovaj jedan, ali je kasnije. Tako ga naučiti. Ljubav je. To će vas tretirati dobro. Dakle, bilo tko imati bilo Pitanja o binarnom potrazi? Da. 

UČENIK: Je li važno je li vaš nje čak i čudno? 

INSTRUKTOR: Ne. Zato smo ga bacili na sredini kao što je int, samo će ga skratiti. Tako da će ostati cijeli broj i to će na kraju sortirati kroz sve. Dakle, ne morate brinuti o tome. Svi su dobro? Strašan. Cool. Dakle, ti dečki dobio ovo. Slideshow. Dakle, kao što smo pričali o tome, ja znam David spominje složenosti vremena izvođenja. 

Dakle, u najboljem slučaju, to je samo jedan, što nazivamo stalnu vrijeme. Može bilo tko reći mene zašto bi to moglo biti? Koja vrsta scenarija bi to značiti? Mm-hm. 

UČENIK: [nečujan] first-- INSTRUKTOR: Pa srednje se Prvi element koji smo došli do, zar ne? Dakle, bilo niz jednu ili sve što tražimo samo događa da se ukus stručnjak u sredini. Tako da je naš najbolji slučaj. Možete dobiti u stvarne probleme, vjerojatno ne ide do [nečujan] koji često. Što je s našim najgorem slučaju? Naš najgori slučaj je log n. A to ima veze s cijelom ovlasti dvije stvari koje sam govorio o tome. 

Dakle, u najgorem slučaju to bi značilo da smo morali nasjeckati niz prema dolje dok je bio jedan element. Dakle, morali smo ga kotlet dolje na pola onoliko puta koliko smo mogli. To je razlog zašto je zapisnik nje, jer vi samo zadržati dijeljenjem s dva. Tako da su pretpostavke, stvari koje trebate znati ako ste ikada će koristiti binarno pretraživanje. Vaši elementi moraju biti razvrstani. Oni moraju biti razvrstani, jer to je jedini način na koji ste mogu znati ako ste u mogućnosti izbaciti pola od toga. 

Ako ste imali tu zbrkan torbu brojeva, a vi govorite, U redu, ja ću provjeriti u sredini broj i broj tražim je manje od toga, ja samo idem samovoljno izbaciti jednu polovicu. Ne bih znati ako vaš Brojevi u toj drugoj polovici. Vaš popis mora biti riješeno. Kao što je dobro, to može biti ide naprijed malo, ali morate imati slučajni pristup. Morate biti u mogućnosti da samo ići na taj srednji element. Ako imate proći kroz nešto ili je potrebno vam dodatne korake doći do tog srednjeg elementa, to nije prijavite n više jer dodajete više posla u nju. A to će učiniti malo više smisla u dva tjedna, ali ja samo vrsta želio predgovor, daju ti dečki ideju o tome što je doći. No, to su dva važne pretpostavke što vam je potrebno za binarnom popis. Uvjerite se da je riješeno. To je jedan veliki za vi upravo sada. A na koje možemo ići u Ostatak naših sorti. Dakle, četiri sorts-- mjehur, umetanje, odabir i pisma. Svi su oni vrsta cool. Ako vi odlučite uzeti CS 124, ćete saznati sve o svim vrstama vrsta. A ako ste xkcd ventilator, postoji je stvarno cool strip o kao što je stvarno neučinkovitih sorti, koje sam Preporučujemo ćete pogledati. Jedan od njih je poput panike vrste, koji je kao, oh ne, vratite slučajan niz. Isključenje sustava. Ostavite. Dakle geeky humor je uvijek dobro. 

Tako se bilo tko sjetiti kakav poput samo opće ideje koliko mjehurića vrsta radi. Sjećate se? 

UČENIK: Da. 

INSTRUKTOR: Idi za to. 

UČENIK: Znači idete kroz i ako je veći, onda ste zamijeniti dva. 

INSTRUKTOR: Aha. Točno. Dakle, vi samo ponoviti kroz. Možete provjeriti dva broja. Ako jedan prije je veći od one nakon toga, samo ih mijenjati, tako da je u na taj način sve većem broju mjehurić prema kraju popisa i sve niže brojeve mjehur prema dolje. 

Je li vam pokazati dečki kul zvučni efekt sortiranje videa? To je vrsta cool. Dakle, kao što je Robert upravo rekao, algoritma da ste samo korak po popisu, zamjene susjednih vrijednosti ako oni nisu u redu. I onda samo ponavljamo sve dok ne bi bilo swaps. Pa nije loše, zar ne? Tako smo nabrzinu primjer ovdje. Dakle, ovo će sortirati ih u uzlaznom redoslijedu. Dakle, kada smo proći kroz prvi Vrijeme, gledamo kroz osam i šest očito nisu kako ćemo ih zamijeniti. 

Pa pogledajte sljedeću. Osam i četiri nije u redu. Mijenjati ih. A onda osam i dva, mijenjati ih. Tamo idemo. Dakle, nakon prvog prolaza, što znate da je vaš najveći broj će biti skroz na vrhu, jer to je samo će biti stalno veći od svega ostalog i to samo ide na balon se sve do kraja tamo. Da li to ima smisla svima? Cool. 

Pa onda gledamo u našem drugom prolazu. Šest i četiri, prekidač. Šest i dva, prekidač. I sada imamo nekoliko stvari u red. Dakle, za svaki pass da mi bi se kroz cijelu našu listu, znamo da kao što je to mnogo brojeva na kraju će biti razvrstani. Tako smo napraviti treću loptu, koja je jedna zamjena. A onda se na naš četvrti prolaze, imamo nula utora. I tako znamo da je naš Niz je riješeno. 

I to je velika stvar s mjehur vrste. Mi znamo da kad smo ima nula swaps, da znači da je sve je u potpunoj red. To je vrsta kako smo provjerili. Dakle, mi također ide to kod mjehurić vrsta što također nije loše. Nijedan od njih su tako loše. Znam da mogu činiti pomalo zastrašujuće. Znam kad sam uzeo klase, čak i kada sam predavao klase za Prvi put prošle godine, Ja se kao, kako mogu to učiniti? To ima smisla u teoriji, ali Kako mi zapravo to učiniti? Koji je razlog zašto sam i želim hodati putem koda s vama ovdje. Dakle, imam Pseudokod za vas dečki ovaj put. Dakle, samo imajte to na umu smo Prenijet više. Dakle, imamo neki brojač koji prati naših swapova, zato moramo biti sigurni da mi provjere da. A mi ponoviti cijeli niz kao što smo upravo učinili s ovom primjeru. Ako se element prije nego je veći od Element Nakon gdje smo na, možemo ih mijenjati i mi povećajte našu stranicu Brojač jer čim smo mijenjati, želimo da naš brojač znati. Bilo kakva pitanja tamo? Nešto se čini smiješno ovamo. UČENIK: Da li postaviti brojač na nulu svaki put kad ide kroz petlju? Ne možete zadržati ide natrag na nulu svaki put? INSTRUKTOR: Ne nužno. Dakle, ono što se događa je idemo ovuda. Tako raditi dok, ne zaboravite, ovo će izvršiti jednom bez iznimke. Dakle, to će postaviti brojač jednak nuli, onda će se ponoviti kroz. Kao što iterira putem, to će ažurirati brojač. Kako se ažurira brojač, kada se to radi, kada je stigao do kraja niza, Ako nije razvrstani naš popis, Brojač će biti ažurirana. 

Pa onda provjerava stanje i kaže, u redu, je brojač veći od nule. Ako je, to učiniti opet. Želite resetirati, tako da kad vas proći kroz, brojač je jednaka nuli. Ako idete kroz sortirati Niz, ništa se ne mijenja, to ne uspije, a vi povratak na popis sortiran. Da li to smisla? STUDENT: To bi moglo u malo. INSTRUKTOR: U redu. Ako postoji bilo koji drugi Pitanje koje dolazi. Da. 

UČENIK: Što bi funkcija biti za zamjene elemenata? 

INSTRUKTOR: Dakle, mi zapravo može pisati da, ako ćemo upravo sada. Cool. Dakle, na toj bilješci, Alison se događa prebaciti natrag na aparat. To će biti zabavno. I mi imamo lijepo mjehurić vrsta stvar ovdje. Tako sam već učinio biciklizam kroz niz. Mi imamo swaps da jednake nuli. Dakle, želimo mijenjati u susjedstvu elemente, ako oni iz reda. Dakle, prva stvar koju moramo nemojte se ponoviti kroz naše polje. 

Pa kako misliš da bismo mogli ponoviti kroz naše ponude? Imamo za i ja jednak 0. Želimo i da se manje od n minus 1 minus k. A ja ću objasniti da u sekundi. Dakle, ovo je optimizacija ovdje gdje je, sjećam se kako sam rekao nakon svakog igrača kroz polja i mi znam da sve što je on-- 

Dakle, nakon što jednom prolazu smo znam da je to riješeno. Nakon dva prolaza znamo da je sve to riješeno. Nakon tri prolaza smo znam da je riješeno. Dakle, na koji način sam iterating kroz niz ovdje, je to pazeći da samo ide kroz ono što znamo je nesortiran. OK? To je samo optimizacije. Ti bi mogao napisati samo naivno iterating kroz sve, to bi samo potrajati duže. S ovim četiri petlje je Samo lijepo optimizacija jer znamo da nakon svake pune iteracija kroz niz ovdje, Kao i svake punu petlju ovdje, znamo da je još jedan od tih elemenata bit će razvrstani na kraju. 

Dakle, ne morate brinuti o onima. Da li to ima smisla svima? To je super mali trik? Dakle, u tom slučaju, ako je smo iterating putem, znamo da želimo provjeriti je li Niz n i n plus 1 u redu. U redu. Dakle, ovdje je Pseudokod. Želimo da provjerite je li niz n i n plus 1 u redu. Pa što bi moglo imamo tamo? To će biti neki uvjetno. To će biti, ako. 

UČENIK: Ako je niz n manje od niza n plus 1. INSTRUKTOR: Aha. Dakle, manja ili veća od. UČENIK: Veće. Tada želimo ih mijenjati. Točno. Dakle, sada smo dobili u ono što je mehanizam za njih zamjene? Tako smo prošli kroz ovaj kratko, vrsta swapu funkcije prošlog tjedna. Se bilo tko sjetiti kako je to radio? Dakle, ne možemo ih samo preraspodijeliti, zar ne? Budući da je jedan od njih će izgubiti. Ako smo rekli jednaka do točke B, a zatim B jednaka je A, sve odjednom obojica samo su jednaka B. 

Dakle, ono što moramo učiniti je da imaju privremenu varijablu koja je će održati jedan od naših vrijeme mi smo u procesu zamjene. Dakle, ono što imamo je da ćemo imati neki int temp jednaka to-- možete ga dodijeliti na koji god želite, samo pobrinite se da pratimo it-- tako da u ovom slučaju, ja ću dodijeliti je niz n plus 1. Tako da će se održati bez obzira na Vrijednost je u tom drugom bloku da gledamo. 

A onda možemo učiniti je da možemo ići naprijed i preraspodijeliti niz n plus 1, jer mi znamo ima tu vrijednost pohranjena. To je također jedan od velikih things-- Ne znam je li itko od vas imali problema gdje ako prebaciti dva linija koda odjednom stvari radio. Narudžba je vrlo važno u CS. Dakle, budite sigurni da dijagram stvari se ako je moguće o tome što se zapravo događa. Dakle, sada ćemo preraspodijeliti array n plus 1, jer mi znamo ima tu vrijednost pohranjena. 

I možemo dodijeliti da je niz n ili u ovom slučaju niz sam. Previše varijabli. U redu. Dakle, sada smo rasporediti niz I. plus 1 jednaka što je u nizu i. A sada možemo vratiti i dodijeliti niz I Za što? Svatko? 

UČENIK: 10. 

INSTRUKTOR: 10. Točno. I jedna posljednja stvar. Ako smo ga zamijenili sada, ono što trebamo učiniti? Što je jedna stvar što će nam reći Ako smo ikada raskinuti ovaj program? Što nam govori da mi imate popis sortiran? Ako ne obavljaju nikakve swapove, zar ne? Ako swapova jednaka nula na kraju ovoga. Dakle, kad god izvršiti zamjenu, kao i mi upravo učinio ovdje, želimo ažurirati swaps. I znam da postoji Pitanje ranije o tome može li koristiti nula ili jedan, umjesto od true ili false. I to je ono što ovaj radi ovdje. Dakle, to govori ako ne i swapove. Dakle, ako swaps je nula, što sam uvijek is-- dobili moje istine i moji falses miješaju. Želimo nas za procjenu da istina i nije. Dakle, ako je nula, onda je lažna. Ako ga negiraju s [? bang?] to postaje istina. Pa onda ta crta izvršava. 

Istine i lažna i nule i one poludi. Samo ako se polako hoda kroz njega to će imati smisla. Ali to je ono što ova mala Malo koda ovdje radi. Dakle, to provjerava smo učinili sve swaps. Dakle, ako je to ništa, osim nula, to će biti lažna a cijela stvar je će ponovno izvršiti. Cool? 

UČENIK: Što pauze učiniti? 

INSTRUKTOR: Break jednostavno break vas iz petlje. Dakle, u ovom slučaju to bi baš kao i završiti program i ti bi samo imati svoj popis sortiran. UČENIK: Amazing. INSTRUKTOR: Žao mi? STUDENT: Zbog ranije smo koristili napisao 1 nad napisao nulu prezentirati da ako koji će raditi ili ne. 

INSTRUKTOR: Da. Na taj način možete vratiti na nulu ili 1. U ovom slučaju, jer smo zapravo nije radiš ništa s funkcijom, mi samo želimo da razbiti. Mi zapravo nije stalo do njega. Kočnica je također dobar ako se koristi za razbijanje od četiri petlje ili stanja koja ne želite zadržati izvršenje. Potrebno je samo vas iz njih. To je malo nijansom stvar. Osjećam se kao da postoji puno ruku mahali, kao što ćete saznati o tome uskoro. 

No, saznat ćete o tome uskoro. Obećavam. U redu. Dakle, nema svatko dobiti mjehur vrsta? Nije loše. Iteraciju kroz, mijenjati stvari pomoću temp varijablu, i svi smo si postavili tamo? Cool. Strašan. U redu. Natrag na PowerPoint. Bilo kakva pitanja u cjelini O njima do sada? Cool. Mm-hm. 

UČENIK: [nečujan] int glavna obično. Imate li imati da za to? 

INSTRUKTOR: Tako smo upravo bili u potrazi Upravo na stvarni sortiranje algoritma. Ako ste ga imali u poput većeg programa, ti bi imati int glavni negdje. Ovisno o tome gdje vas koristiti ovaj algoritam, da bi se utvrdilo što je se vratio po nju. No, za naš slučaj, mi smo strogo gledajući kako se to zapravo ponoviti kroz niz. Dakle, ne brinite o tome. 

Tako smo razgovarali o najboljem slučaju i najgore scenarije za binarno pretraživanje. Dakle, to je također važno raditi da je za svaki od naših sorti. Pa što misliš da je najgore Slučaj runtime bubble vrste? Vi sjećaš se? 

UČENIK: N minus 1. INSTRUKTOR: N minus 1. Dakle, to znači da postoje n minus 1 usporedbe. Dakle, jedna stvar za shvatiti je da je na prvoj iteraciji idemo putem, usporedimo to two-- tako da je 1. Ove dvije, tri, četiri. Tako je nakon jedne iteracije smo već četiri usporedbe. Kad Govorim o izvođenja i n. N predstavlja broj usporedbe kao funkcija kako mnogo elemenata imamo. OK? 

Tako smo proći, imamo četiri. Sljedeći put kada znate što mi ne znamo moraju voditi brigu o tome. Usporedimo li ove dvije, ove dvije, ova dva, a ako nismo imali tu optimizaciju s četiri petlje da sam napisao, ti bi se usporedbom ovdje ionako. Dakle, ti bi trebala trčanje kroz niz i napraviti usporedbe n n puta, jer svaki put kad smo prođite kroz to Razvrstavamo jednu stvar. 

I svaki put kad prolaze kroz polje, izrađujemo n usporedbe. Dakle, naš runtime za to je zapravo n kvadrat, koji je je mnogo gore u našim prijavite kraj jer to znači, ako smo imali četiri milijardu elemente, to je će nam uzeti četiri milijarde kvadrat, umjesto 32. Dakle, nije najbolji izvođenja, ali za neke stvari, znate, ako ste u roku određeni niz elemenata mjehurić vrsta može biti u redu koristiti. 

U redu. Tako je sada ono što je najbolje, runtime? UČENIK: Nula? Ili 1? 

INSTRUKTOR: 1 Tako bi biti jedna usporedba. Pravo. 

UČENIK: N minus 1? 

INSTRUKTOR: Dakle, da. Tako n minus 1. Kad god imate koncept kao što je n minus 1, skloni smo samo kap off a mi samo reći n zato što imate usporediti svaku od these-- svakog para. Dakle, to bi bilo n minus 1, što smo bismo samo reći je oko nje. Kada ste se bave runtime, sve je u približna. Tako dugo dok je eksponent točna, ti si prilično dobro. 

To je kako se nositi s njom. Tako da, najbolje n, koji znači da je popis već razvrstani, a sve što radimo je trčanje kroz i provjerite da je to riješeno. Cool. U redu. Dakle, kao što vidite ovdje, mi samo još neke grafove. Tako n kvadrat. Zabava. Mnogo gore nego n kao što vidimo, i mnogo, mnogo gore nego log 2n. I onda ćete također dobiti u log trupaca. A ti uzeti 124, što se u kao što su log zvijezda, koja je kao lud. Dakle, ako ste zainteresirani, pretraživanja dnevnik zvijezda. To je vrsta zabave. Dakle, imamo veliki grafikon. Samo heads up, to divno grafikon imati za svoj srednjem roku jer mi dugo da te pitam ove stanjuje. Dakle, samo heads up, ima to na vašem srednjoročna na svom lijepo varati list tamo. Tako smo samo pogledao bubble vrste. U najgorem slučaju, n kvadrat, najboljem slučaju, n. A mi ćemo gledati na druge. 

I kao što možete vidjeti, samo onaj koji uistinu dobro je spajanje vrsta, koje ćemo dobiti u zašto. Tako ćemo ići Sljedeći here-- odabir vrsta. Se bilo tko sjetiti kako Izbor vrsta radio? Idi za to. 

UČENIK: Uglavnom prolaze red i stvoriti novi popis. I baš kao što ste stavljajući elemente u, stavite ih na pravom mjestu U novom popisu. 

INSTRUKTOR: Tako da zvukovi više poput umetanja vrste. Ali ti si jako blizu. Oni su vrlo slični. Čak i ja bi ih pomiješao ponekad. Prije ovog poglavlja bio sam poput čekati. U redu. Dakle, ono što želite to je izbor vrsta, način na koji se možete sjetiti o tome i na koji način Ja bi bili sigurni Pokušavam ne dobiti ih pomiješali, je li prolazi kroz i to odabire Najmanji broj i to stavlja da je na početku svog popisa. Ona ga zamijeni s tom prvom mjestu. Oni su zapravo primjer za mene. Strašan. Tako je samo način da razmišljaju o it-- izbor sortiranje, odabir najmanju vrijednost. A mi ćemo se prođite kroz primjer mislim da će pomoći, jer Mislim vizuale uvijek pomoći. Tako smo početi s nečim to je potpuno nesortiran. Crveni će biti nesortiran, zeleni će biti riješeno. Sve to će imati smisla u sekundi. 

Tako smo proći i mi ponoviti od početka do kraja. A mi kažemo, u redu, 2 naš najmanji broj. Tako ćemo uzeti 2 i idemo kako biste ga premjestili ispred naše ponude zato što je Najmanji broj imamo. Dakle, to je ono što se to radi ovdje. To samo će zamijeniti one dvije. Dakle, sada smo razvrstani Dio te nesortiran dio. A ono što je dobro zapamtiti oko odabira vrste je mi smo samo odabir iz nerazvrstani dijela. 

Sortirati dio ti samo ostaviti na miru. Mm-hm? 

UČENIK: Kako to znati što je Najmanji bez usporedbe za svaku drugu vrijednost u polju. INSTRUKTOR: To ne usporediti ga. Volimo ga preskaču. Ovo je samo općenito u ukupnom poretku. Da. Kad pišemo kod ja sam sigurni da ćete biti zadovoljni. Ali ti to pohraniti prvi Element kao najmanji. Možete usporediti i vi kažu, u redu, to je manja? Da. Držite ga. Ovdje je to manja? Ne? 

Ovo je tvoj najmanji, ga preraspodijeliti na svoju vrijednost. A vi ćete biti puno sretniji kad idemo kroz kod. Tako smo proći, možemo ga mijenjati, pa onda gledamo ovom nerazvrstani dio. Tako ćemo odabrati tri out. Mi ćemo ga staviti na po kraj našeg sortiranog dijela. I samo ćemo se držati događaj da, da radi i da radi. Dakle, ovo je naša vrsta Pseudokod ovdje. Mi ćemo ga kod ovdje u sekundi. Ali samo nešto hodati putem na visokoj razini. Ti ćeš otići iz ja jednak 0 do n minus 2. To je još jedna optimizacije. Ne brinite previše o tome. Dakle, kao što ste rekli. Kao što je Jakov je govorio, kako radimo pratiti što naša minimalna je? Kako ćemo znati? Imamo za usporedbu sve što je u našoj listi. 

Dakle, minimalno jednak ja. To samo govori u ovom slučaju Indeks naše minimalne vrijednosti. Pa onda će to ponoviti kroz i to ide od j jednak i plus 1. Dakle, mi već znamo da to je naš prvi element. Ne moramo ga usporediti sebe. Tako ćemo početi uspoređujući ga sljedeći onaj koji je razlog zašto je i plus 1 do n minus 1, koji je kraj niza tamo. I rekli smo, ako niz u j je manji od polja min, onda ćemo preraspodijeliti gdje naši minimalni indeksi je. 

A ako min nije jednak i, što je u kojoj smo ponovno ovdje. Dakle, kao kad smo prvi put je ovaj jedan. U ovom slučaju, to bi započeti u nula, to bi završiti kao dva. Dakle min ne bi jednak i na kraju. To omogućuje nam da moramo ih mijenjati. Osjećam se kao konkretan primjer pomoći će mnogo više od toga. Tako ću kodirati ovaj gore s vama upravo sada i mislim da će biti bolje. 

Vrste imaju tendenciju da rade na taj način da se u to je često bolje samo da ih vidim. Dakle, ono što želimo učiniti je prvo želim najmanji Element u položaj u nizu. Točno ono što Jakov govori. Morate spremiti da nekako. Tako ćemo započeti ovdje iterating preko polja. Idemo reći da je naš Prvi je samo početak. Tako ćemo imati int Najmanji je jednaka polja na i. 

Dakle, jedna stvar za primijetiti, svaka put ove petlje izvršava, mi smo početkom korak dalje zajedno. Kad počnemo gledamo ove. Sljedeći put ćemo ponoviti kroz, mi smo početkom u ovom jednom i to je naša najmanja vrijednost dodjeljivanje. Dakle, to je vrlo sličan bubble vrste gdje smo znali da nakon jednom prolazu, ovaj zadnji element razvrstani. Uz odabir vrste, to je upravo suprotno. 

U svakom prolazu, znamo da Prvi je riješeno. Nakon drugog prolaza, Druga će biti riješeno. I kao što ste vidjeli na primjerima slajd, naš razvrstani dio samo raste. Tako postavljanjem naš najmanji na polja i sve to radi stežuća je ono što gledamo kako smanjiti broj usporedaba ćemo napraviti. Je li to smisla svima? Da li mi je potrebna za pokretanje kroz to opet sporije ili u različitim riječima? Ja sam sretan. U redu. 

Tako smo skladištenje vrijednost u ovom trenutku, ali mi također želimo pohraniti indeksa. Tako ćemo pohraniti položaj najmanji jedan, koji je upravo će biti ja. Tako sada Jakov je zadovoljan. Imamo stvari pohranjene. A sada moramo gledati kroz nesortiran dio niza. Dakle, u ovom slučaju to će biti naš nesortiran. To je ja. U redu. 

Pa što ćemo učiniti će biti za petlju. Kad god vam je potrebno ponoviti kroz niz, vaš um mogao ići na petlju. Tako je za neke int k equals-- što mislimo k će jednaka za početak? To je ono što smo postavili kao naš najmanji Vrijednost i želimo ga usporediti. Što želimo usporediti ga? To će biti taj sljedeći, zar ne? Dakle, želimo k bi se vratiti u tvorničke da ja plus 1 za početak. 

I želimo k u ovom slučaju smo Već su veličine pohranjene ovdje, tako da mi samo može koristiti veličinu. Veličina se veličina polja. A mi samo želimo ažurirati k po jedan svaki put. Cool. Tako sada trebamo pronaći najmanji element ovdje. Dakle, ako ćemo ponoviti kroz ćemo želim reći, ako je polje na k manji od našeg najmanji value-- ovo je mjesto gdje smo zapravo praćenje onoga što je Najmanji here-- onda želimo preraspodijeliti ono što je naša najmanja vrijednost. 

To znači da je, oh, mi smo iterating ovuda. Bez obzira na vrijednost ovdje Nije naša najmanja stvar. Mi to ne želimo. Želimo ga preraspodijeliti. Dakle, ako mi ga prenamjene, što učiniti mislite da bi moglo biti u ovom kodu ovdje? Želimo preraspodijeliti Najmanji i položaj. Dakle, ono što je sada najmanji? UČENIK: Array k. INSTRUKTOR: Array k. A što je stav sada? Što su indeksi naša najmanja vrijednost? To je samo k. Dakle polja k, k, oni podudaraju. Zato smo htjeli da se preraspodijeliti. A onda nakon što smo pronašli naš najmanji, tako da je na kraju to za petlje Ovdje smo našli ono što naš najmanji vrijednost, pa smo samo ga zamijeniti. U ovom slučaju, kao što kažu naši najmanja vrijednost ovdje. To je naša najmanja vrijednost. 

Mi samo želimo da ga zamijene mjesta, što je što je to zamjena funkcija na dnu učinili, što smo upravo napisao gore zajedno prije par minuta. Dakle, to bi trebalo izgledati poznato. A onda će samo ponoviti kroz sve dok ne dosegne sve do kraja, što znači da vas ima nula elemenata koji su nesortiran a sve ostalo je riješeno. Smisla? Malo konkretnije? Kod pomoć? 

UČENIK: Za veličinu, nikada stvarno ga definirati ili ga promijeniti, kako se to zna? 

INSTRUKTOR: Dakle, jedna stvar primjetiti ovdje je veličina int. Dakle, mi govorimo u ovom sort-- vrste je funkcija u ovom case-- je Izbor vrsta, to je prošlo u funkciju. Dakle, ako nije donesen u, što će učiniti nešto kao i s duljinom niza ili će ponoviti kroz pronaći duljinu. Ali zato što je prošlo u, mi samo možemo ga koristiti. Vi samo pretpostaviti da korisnik vam je dao valjanu veličinu koja zapravo predstavlja veličina vašeg polja. Cool? 

Ako vi imate bilo kakvih problema s njima ili želite više prakse kodiranja vrste na svoju ruku, trebali ići na study.cs50. To je alat. Oni imaju provjeru kako zapravo možete pisati. Oni ne Pseudokod. Oni imaju više videa i slajdove uključujući i one koje koristim ovdje. Dakle, ako ste još uvijek osjeća malo fuzzy, pokušajte da se. Kao i uvijek, dolaze razgovarati sa mnom, previše. Pitanje? 

UČENIK: Jeste li govoreći Veličina je prethodno definirano? INSTRUKTOR: Da. Veličina je prethodno definiran se ovdje u funkciji izjavi. Dakle, pretpostavimo da je donesen u od strane korisnika, i Radi jednostavnosti, ćemo pretpostaviti da Korisnik nam je dao točnu veličinu. Cool. Tako da je izbor vrsta. Dečki, znam da učite puno danas. To je gusta podataka za odjeljku. Dakle s tim, idemo ići na umetanja vrste. 

U redu. Dakle, prije toga moramo napraviti naš runtime analiza ovdje. Dakle, u najboljem slučaju, odobravaju od vas pokazali stol sam već vrsta ga je dao daleko. No najboljem slučaju izvođenja, što mi mislimo? Sve riješeno. N kvadrat. Svatko ima objašnjenje zašto mislite? 

UČENIK: Ti si usporedbom through-- INSTRUKTOR: Upravo. Vi uspoređujete kroz. U svakoj iteraciji, iako mi smo to se smanjuje za jedan, ste još uvijek u potrazi kroz sve kako bi pronašli najmanji jedan. Pa čak i ako je vaš najmanja vrijednost ovdje na početku, ti si još uvijek ga uspoređujući Protiv sve ostalo kako bi bili sigurni da je najmanja stvar. Tako ćete završiti trčanje kroz oko nje kvadrat puta. U redu. A što je najgori slučaj? Također n kvadrat, jer ćeš da se radi tu istu proceduru. Dakle, u ovom slučaju, izbor vrsta ima nešto Tako ćemo i mi zovemo očekuje runtime. Tako je u drugima, mi samo znamo Gornje i donje granice. Ovisno o tome kako ludi našim Popis je ili kako nesortiran je, oni variraju između n ili n kvadrata. Ne znamo. 

Ali zato izbor vrsta ima isti Najgori i najbolji slučaj, kako nam kaže da bez obzira na vrstu ulaza smo ima, da li je u potpunosti razvrstani ili potpuno obrnuti razvrstani, to je će uzeti istu količinu vremena. Dakle, u tom slučaju, ako vas sjećate iz našeg stola, to je zapravo imao vrijednost koja ove dvije vrste nemaju, što je očekivao runtime. Dakle, mi znamo da kad god trčimo izbor vrsta, to je zasigurno pokrenuti n kvadrat vrijeme. Nema varijabilnost postoji. To je samo što se očekivalo. A, opet, ako želite naučiti više, uzeti CS 124 u proljeće. U redu. Vidjeli smo ovaj jedan. Cool. Dakle, umetanje sortiranje. I ja sam vjerojatno idući da sjala kroz to. Neću dopustiti da ti dečki to kodirati. Samo ćemo prošetati kroz njega. Dakle, umetanje vrsta je vrsta je slična odabira vrste da smo oboje nesortiran i razvrstani dio niza. 

No, ono što je drugačije je da kao što smo proći kroz jedan po jedan, mi samo uzeti bez obzira na broj je sljedeći na naš nesortiran, i točno to riješiti u našu sortiranog niza. To će učiniti više smisla s primjerom. Dakle, sve počinje kao nerazvrstani, Kao i kod odabira vrste. A mi ćemo izdvojiti to najnoviji poredak kao što smo bili. Dakle, na našem prvom prolazu uzmemo prvu vrijednost a mi reći, ok, ti ​​si Sada na popisu po sebi. 

Budući da ste u popisu po sebi, koju su razvrstani. Čestitke za što Prvi element u tom nizu. Vi ste već razvrstani sve na svoju ruku. Dakle, sada smo razvrstani i nesortiran niz. Dakle, sada smo se prvi put. Što se događa između ovdje i ovdje je da kažemo, U redu, idemo pogledati Prva vrijednost našeg nerazvrstani niza a mi ćemo unijeti ga u svojoj točno mjesto u sortiranog niza. 

Dakle, ono što mi se uzmemo 5 i kažemo, u redu, 5 veći od 3, pa smo samo ga ubacite u pravu desno od toga. Mi smo dobri. Pa onda idemo na naš sljedeći jedan. I uzmemo 2. Kažemo, OK, 2 manje od 3, tako da znamo da je to treba biti na Prednji dio našeg popisa sada. Dakle, ono što mi radimo je da gurnuti 3 i 5 prema dolje i krećemo 2 u taj prvi utor. Dakle, mi samo umetanja u točno mjesto bi trebao biti. 

Onda gledamo naše Sljedeći, i kažemo 6. OK, 6 je veća od sve što je u našoj sortiranog niza, pa smo samo označiti na kraju. I onda gledamo 4. 4 je manje od 6, to je manje od 5 ali je veći od 3. Tako smo samo ga stavite izravno u Srednji između 3 i 5. Dakle, da bi se to malo malo konkretniji, Ovdje je vrsta Ideja o tome što se dogodilo. Dakle, za svaki nerazvrstani elementa, mi odrediti gdje se u sortiranog dijela je. 

Dakle, imajući u vidu razvrstani i nesortiran, moramo proći kroz te lik gdje se uklapa u sortiranog niza. I mi ga ubacite prebacivanjem Elementi desno od njega dolje. A onda smo samo zadržati iterating kroz sve mi ima popis potpuno sortirani gdje nesortiran je sada nula i sortirati zauzima cjelokupnost našeg popisa. Dakle, još jednom, da bi stvari čak i konkretniji, imamo Pseudokod. 

Tako je u osnovi za ja je jednak 0 do n minus 1, to je samo duljina naše ponude. Imamo neki element koji je jednak Prvi niz ili prvi indeksi. Postavili smo j jednaka. Dakle, dok j je veći od nula i niz, j minus 1 veći od Element, tako da sve što radi je pazeći da Vaš j stvarno predstavlja nesortiran dio polja. 

Dakle, dok je još stvari sortiranje i j minus jedan is-- što je element koji ju? J nikad nije bio ovdje definirana. To je vrsta neugodno. U redu. Uglavnom. Tako j minus 1, koju provjeru Element pred njim. Kažeš, u redu, je element Prije nego tamo gdje sam am-- neka je zapravo izvući ovo. Pa recimo da je ovo kao i na našem drugom prolazu. Dakle, ja će biti jednaka na 1, što je ovdje. 

Dakle, ja će biti jednaka 1. To će biti 2, 4, 5, 6, 7, U redu. Tako je naš element u ovom slučaju će biti jednak 4. I mi imamo neke j koji je će biti jednak 1. Oh, j je se smanjuje. To je ono što je. Tako j je jednak i, pa što je ovo rekao je da kao i mi krenuti naprijed, mi samo pazeći da nismo više indeksiranje na ovaj način, kada pokušavamo umetnuti stvari u našem popisu poredani. 

Dakle, kada j je 1, a u ovom slučaju Niz j minus one-- tako niz j minus 1 2 u ovom case-- ako je to veći od elementa, onda sve to radi prebacuje stvari dolje. Dakle, u ovom slučaju, niz j minus jedan bi niz nula, što je 2. 2 nije veći od 4, tako da to ne izvrši. Dakle pomak ne pomiče prema dolje. Što se ovo ovdje je samo pomicanjem sortirani niz prema dolje. U tom slučaju, u stvari, da mogao do-- učinimo ovaj 3. Dakle, ako smo u šetnju kroz s ovaj primjer, mi smo danas ovdje. To je riješeno. To je nesortiran. Cool? Tako da je jednak 2, tako naš element je jednak 3. I naša j je jednak 2. Tako smo i mi gledati kroz kažu, u redu je niz j minus jedan veći od elementa da gledamo? A odgovor je da, zar ne? 4 je veći od 3, a j 2, tako da je ovo kod izvršava. 

I što sada radimo niz na 2, tako da upravo ovdje, možemo ih mijenjati. Tako smo samo reći, OK, polje na 2 sada će biti 3. A j će jednak j minus 1, koji je 1. To je strašno, ali ti dečki dobiti ideju. J je sada jednak 1. I niz j samo će biti jednaka našoj elementa, koji je bio 4. Ja izbrisani nešto što ne bi trebali imate ili miswrote nešto, ali ti dečki dobiti ideju. 

To premjestiti na n. I onda kad bi to bilo, to bi petlje opet i to će reći, u redu, j je 1 danas. I niz j minus 1 je sada 2. Iznosi 2 manje od našeg elementa? Ne? To znači da smo umetnuta ovaj element u ispravnom mjestu u našoj sortiranog niza. Onda možemo uzeti i kažemo, U redu, naša sortirati niz je ovdje. I to bi se taj broj 6 i biti kao, u redu, je 6 manje od tog broja? Ne? Cool. Mi smo u redu. 

Učinite to opet. Kažemo 7. Je 7 manje nego na kraju našeg sortiranog niza? Ne. Tako smo u redu. Dakle, to će biti riješeno. Uglavnom sve to radi Je li to govori odvesti prvi element Vaš nesortiran polje, shvatiti gdje to ide u svom sortiranog niza. I to samo vodi brigu swapova za to. Vi ste zapravo samo zamjene dok je na pravom mjestu. Vizualna slika koje ste kreće sve dolje na taj. 

Dakle, to je kao pola bubble vrsta veliku. Provjerite studiju 50. Ja visoko preporučiti pokušavam kodirati to na svoju vlastitu. Ako imate bilo kakvih pitanja ili želite vidi primjer koda za umetanje vrste, molim javite mi. Ja sam uvijek oko. Dakle, u najgorem slučaju izvođenja i najbolji slučaj runtime. Kao što ste vidjeli momak iz tablice sam već pokazala vas, to je i n kvadratna i n. 

Dakle vrsta ide izvan onoga što smo razgovarali o tome s našim prethodnim vrstama, najgore Slučaj runtime je da ako to je potpuno nerazvrstani, moramo usporediti sve ove n puta. Mi radimo puno usporedbe jer ako je to u obrnutom redoslijedu, idemo reći, u redu, to je isti, to je dobro, a ovaj će morati biti u odnosu Protiv prvog se preselio natrag. I kao što smo dobili prema rep kraj, imamo za usporedbu, usporedite i usporediti protiv svega. 

Tako da završi kao oko nje kvadrat. Ako je to točno onda ste kažu, u redu, 2, ti si dobar. 3, ti si u odnosu na 2. Ti si dobar. 4, samo usporediti rep. Ti si dobar. 6, u usporedbi s repa, ti si u redu. Dakle, za svaku točku ako je već razvrstani, radite jednu usporedbu. Dakle, to je samo n. I zato imamo najboljeg slučaja runtime n i najgorem slučaju izvođenja n kvadrat, nemamo očekivani izvođenja. 

To samo ovisi o kaos našeg popisa tamo. I opet, još jedan graf i još jedan stol. Dakle, razlika između sorti. Samo ću se povjetarac kroz, ja Osjećam se kao da smo razgovarali opširno o tome kako su sve vrste o razlikovati i povezivati. Dakle spajaju sorta je posljednji Ja ću ti rodila dečki s. Mi nemamo prilično šarene slike. Dakle, spajanje vrsta je rekurzivna algoritam. Dakle, da li vi momci znate što rekurzivna funkcija? 

Svatko želi reći? Želite li probati? Dakle, rekurzivna funkcija je samo funkcija koja sebe naziva. Dakle, ako ti dečki su upoznati s Fibonacci nizu, koji je smatra rekurzivna, jer uzmete prethodna dva i dodati ih zajedno kako bi dobili svoj sljedeći. Dakle rekurzivna, uvijek mislim od rekurzije kao poput spirale tako ste poput spirale prema dolje u nju. Ali to je samo funkcija koji se poziva. 

I, zapravo, jako brzo sam mogu vam pokazati kako to izgleda. Dakle rekurzivna ovdje, ako gledamo, ovo je rekurzivna način da zaključimo preko niz. Dakle, sve što radimo je mi smo zbroj funkciju suma koja ima veličinu i niz. A ako primijetite, veličina umanjenje broja doza po jedan svaki put. I sve je to ipak ako je x jednak zero-- pa ako veličina polja jednaka zero-- vraća nulu. 

Inače to sažima to Posljednji element polja, a zatim uzima zbroj Ostatak polja. Dakle, to je samo to što se razbije u sve manje i manje problema. Da ne duljimo, rekurzija, funkcija koja sebe naziva. Ako je to sve što je izašao iz toga, to je ono što rekurzivna funkcija. Ako se uzme 51, dobit ćete vrlo, Vrlo ugodno rekurzije. To je stvarno cool. To je imalo smisla, na sličan 3:00 jedne noći van. I ja sam bio kao, zašto sam nikada se ne koristi ovo? 

Tako je za spajanje vrsta, u osnovi ono što će učiniti je da je će ga razbiti i slomiti ga dolje dok je to samo pojedinačni elementi. Pojedinačni elementi su lako razvrstati. Vidimo da. Ako imate jedan element, to je Već smatra riješeno. Tako na ulazu n elemenata, ako je n manji od 2, Samo vratiti jer to znači to je bilo 0 ili 1, kao što smo vidjeli. Oni smatraju slagala elemente. 

Inače ga slomiti na pola. Sortirati prvo poluvrijeme, sortirati drugi polovice, a zatim ih spojiti zajedno. Zašto se to zove spajanje vrsta. Tako imamo ovdje ćemo sortirati njih. Dakle, držimo ih ima dok veličina niz je 1. Dakle, kad je 1, samo smo se vratili jer je to sortirati niz, i to je sortirati niz, a to je sortirati niz, svi smo razvrstani. Pa onda ono što radimo je da početi spajanje ih zajedno. 

Dakle, način na koji možete razmišljati o spajanju je možete samo ukloniti manji Broj svakog polja pod i samo ga dodajte na nastao niz. Dakle, ako pogledate ovdje, kada imamo ovi setovi imamo 4, 6 i 1. Kada želimo spojiti njih, gledamo ove prve dvije a mi reći, u redu, 1 manja, to ide prema naprijed. 4 i 6, nema ništa za usporedbu da, samo ga označiti na kraju. 

Kada smo kombinirati ove dvije, samo mi uzeti manji jedan od ta dva, tako da je 1. I sada mi se Manji od ta dva, pa 2. Manji od ta dva, 3. Manji od ove dvije, 4, 5, 6. Dakle, ti si jednostavno povlačenjem tih. I zato što ste Prethodno razvrstani, imate samo jedan Usporedba svaki put tamo. Dakle, više kod ovdje, samo prikaz. Dakle, vi početi na sredini i omogućuje sortiranje lijevo i desno i onda jednostavno spojiti one. 

I nemamo kod za spajanje upravo ovdje. Ali, opet, ako idete na studirati 50, to će biti tamo. Inače dolaze razgovarati sa mnom Ako ste još uvijek zbunjeni. Dakle, super stvar ovdje je da najbolji slučaj, najgorem slučaju, a očekuje se runtime su sve u zapisniku n, koji je je daleko bolje nego što smo vidi za ostatak naših sorti. Vidjeli smo n na kvadrat i što mi zapravo doći ovdje n prijavite nje, što je super. 

Pogledajte kako je puno bolje da je. Takva lijepa krivulja. Dakle, mnogo učinkovitiji. Ako ste ikada može, korištenje spojiti vrsta. To će vam uštedjeti vrijeme. Onda opet, kao što smo rekli, ako je ti si u ovom donjem dijelu, ne bi da je mnogo razlika. Možete doći do tisuća i tisuće ulaza, što svakako želite učinkovitiji algoritam. A, opet, naš lijepi stol svega vrste koje ti dečki naučili danas. 

Tako da znam da je bilo gusto dan. To nije nužno ide kako bi vam pomoći s vašim pset. Ali ja samo želim napraviti disclaimer taj dio je ne samo o psets. Sve to je materijal sajam Igra za midterms. A isto tako ako ne nastaviti sa CS, to su stvarno važne osnove da ti bi trebao znati. Dakle, nekoliko dana će biti malo više pset pomoć, ali nekoliko tjedana neće biti mnogo više stvarni sadržaj da možda ne izgleda super korisne za vas upravo sada, ali obećajem ako nastavite o će biti vrlo, vrlo korisno. 

Dakle, to je to za odjeljku. Do žice. Učinio sam to u roku od jedne minute. Ali tamo idete. I ja ću imati krafne ili slatkiše. Je li netko alergičan na ništa, usput? Jaja i mlijeko. Dakle, krafne su zar ne? U redu. U redu. Čokolada nema? Zvjezdana prašina. Zvjezdana prašina su dobri. U redu. Mi ćemo imati Eksplozija sljedeći tjedan onda. To je ono što ću dobiti. Ti dečki imaju veliki tjedan. Pročitajte svoj spec. 

Pustiti mene znati ako imate bilo kakvih pitanja. Pset dva razreda bi trebao biti kako bi vas do četvrtka. Ako imate bilo kakvih pitanja o tome kako sam se ocjenjuju nešto ili zašto sam nešto ocjenjuju način na koji sam jeste, molimo pošaljite email me, došao razgovarati sa mnom. Ja sam malo luda to tjedan, ali obećavam I dalje će odgovoriti u roku od 24 sata. Dakle, imaju veliki tjedan, svima. Sretno na svom pset.