SPEAKER 1: Ahoj všetci! Vitajte späť na časti. Tak rád, že sa tak veľa z vás aj tu, a každý, kto sa pozerá online. Takže ako obvykle vitajte späť. Dúfam, že ste všetci mali krásne víkend plný oddychu, relaxácie. To včera bola krásna von. Takže dúfam, že sa vám to páčilo vonku. 

Takže najprv pár oznámenia. Triedenie. Takže väčšina z vás by mal dostať napíšte mi o vašom Scratch pset, ako aj triedenie pre pset 1. Takže, len pár vecí. Uistite sa, že používate check50 v style50. Tie majú byť prostriedky pre vás, aby sa ubezpečil, že ste stále čo najviac bodov, ako môžete bez toho, aby zbytočne ich straty. Takže veci, ako je štýl sú veľmi dôležité. Chystáme sa zložiť za to. Niektorí z vás možno už si všimol, že z vášho pset. A check50 je len Naozaj jednoduchý spôsob, aby sa ubezpečil, že sme vlastne vracia to, čo musí byť sa vrátil k užívateľovi, a že všetko funguje správne. 

Na druhú poznámku, uistite sa, že nahrať veci do správnej zložky. To je môj život len trochu zložitejšie ak nahráte pset 2 do pset 1 pretože keď som stiahnuť niečo, nemajú sťahovať správne. A ja viem, že je to trochu blbo v systéme zvyknúť, ale len byť super pozor, aj keď len pre mňa, tak, že keď ste sa dostal e-maily v ako 2 A.M. a ja som triedenia. Ak nie, pretože som sa pozrieť všade okolo pre pset. V pohode. 

Ja viem, že je to skoro, ale ja úplne dostal vzlietlo stráž eseje, ktorá je v dôsledku tejto piatok, že moji profesori boli len radi, oh yeah. Pamätajte si, že máte esej kvôli v piatok. Takže viem, že nikto rád premýšľať o tom, midterms, ale váš prvý kvíz je 15. októbra, ktorý októbra sa začína tento týždeň. Tak, to by mohlo byť skôr ako ste očakávali, je všetko. Tak, že nie ste hádzať nepripraveného keď Zmieňujem sa o časť budúci týždeň, že oh, Váš test budúci týždeň, myslel som, Ja by som vám trochu viac z hláv sa teraz. 

Takže nastaviť váš problém, číslo tri. Ako ľudia čítať spec zo zvedavosti? OK. Máme pár. Druh dole z posledného týždenne, ale to je v poriadku. Viem, že to bolo krásne von. Tak Break Out. Rozhodne po stihnúť dnes čítať spec aspoň skúste ako stiahnutie Distribúcia kód a prevádzku ako prvý počiatočné vec, ktorá vás žiadajú, aby ste. Pretože sme pomocou distribúcia kód a knižnice že sme ešte len using-- --It len Druhýkrát sme urobili túto pset, bláznivé veci sa môže stať s prístrojom, a chcete zistiť, že vonku proti neskôr. 

Vzhľadom k tomu, či je to vo štvrtok v noci, alebo je to V stredu v noci a z nejakého dôvodu Váš spotrebič jednoducho nie je chcete spustiť s knižnicou alebo distribúcie kód, to znamená nemôžete ani začať robiť kódovanie. Pretože nie je možné kontrolovať aby zistil, či to funguje. Váš nebudem môcť aby zistil, či to prekladá. Chcete sa postarať o tie, ktoré na začiatku roka týždeň, kedy môžete mi ešte e-mail alebo jeden z ďalších TFS a môžeme dostať tie, ktoré stanovuje. Vzhľadom k tomu, to sú otázky, ktoré ťa zastaviť v tom, aby žiadny skutočný pokrok. Nie je to ako jednu chybu, že môžete len tak preskočiť. Ak máte problémy so svojím zariadenie alebo distribúcia kód, Naozaj chcete, aby si to vziať starostlivosť o skôr skôr ako neskôr. Takže aj keď ste nebudeš v skutočnosti začať písať kód, stiahnite si distribúciu kód, prečítajte si spec, uistite sa, všetko, čo sa tam pracuje. OK? Ak sa vám jednoducho to, že som Sľubujem svoj život bude jednoduchší. A tak budete pravdepodobne to urobiť teraz hneď? OK. Takže tam nejaké otázky? Všetky logistické veci? Každý, kto je dobrý? OK. 

Disclaimer pre tých, Ste v miestnosti a on-line. Budem sa snažiť prepínať medzi PowerPoint v zariadení Pretože sa chystáme bude robiť nejaké kódovanie dnes populárnej dopytu anonymný návrh hlasovania som poslal minulý týždeň. Takže budeme robiť nejaké kódovanie. Takže ak vy tiež chcieť strieľať vaše zariadenie, a mali ste dostali e-mail odo mňa, s ukážkový súbor. Prosím, neváhajte to urobiť. 

Takže, budeme hovoriť o GDB, ktorý je debugger. Bude to, aby vám pomohol druh zistiť, kde veci idú zle v kóde. Je to naozaj len spôsob, ako krok prostredníctvom kódu, ako je to sa deje, a musí byť schopný vytlačiť premenné alebo zistiť, čo sa vlastne deje Pod kapotou verše program práve beží, je to ako chybující, a ty si ako, žiadny nápad čo sa tu práve stalo. Ja neviem, čo riadok to prepadlo na. Neviem, kde sa stala chyba. Takže, GDB bude, aby vám pomohol s tým. Tiež, ak sa rozhodnete pokračovať áno, a vziať 61, to bude naozaj, ale naozaj byť vaša najlepší priateľ, pretože som vám povedať, preto, že som prechádzal tejto triedy. 

Ideme sa pozrieť na binárne Hľadania, ktoré, ak vy pamätať veľký telefónny zoznam príkladov Podívaná z triedy. Budeme sa vykonáva to, a prechádzke, že trochu viac, a potom ideme cez štyri rôzne druhy, ktoré sú Bubble, Výber, vkladanie, a zlúčiť. V pohode. Takže, GDB, ako som už spomenul, je debugger. A tie sú trochu veľký veci, veľké funkcie alebo príkazy ktoré používate v GDB, a ja budem chodiť si cez demo sa prevedie do druhej. 

Takže, to nie je len Zostaneš abstraktné. Pokúsim sa, aby to ako betón ako je to možné pre vás. Takže, zlomiť. To bude prestávka buď ako, nejaké číslo, ktoré predstavuje riadok v programe, alebo môžete pomenovať funkciu. Takže, ak povieš rozbiť hlavné, sa zastaví na hlavné, a umožní vám prejsť túto funkciu. 

Rovnako tak, ak máte nejaké externé fungujú ako Swap alebo kocka, že sme sa pozreli na minulý týždeň. Ak poviete rozbiť jeden z tých, keď váš program zasiahne to, to na teba čakať na hovorí, čo má robiť. Než to bude len spustiť, takže vám by sa skutočne krok vnútri funkcie a uvidíte, čo sa deje. Takže ďalší, jednoducho preskočí ďalší riadok, prejde funkcie. Krok. To všetko sú trochu abstraktné. Tak som len tak bežať cez ne, ale vy ich uvidíte v použitie v druhej. 

Vstúpte do funkcie. Takže ako som hovoril, ako u Swap, by to umožňujú skutočne, ako keby ste ako fyzicky krokovanie vnútri, môžete si s týmito premennými, tlač to, čo oni sú, čo sa deje. Zoznam bude doslova len vytlačiť z okolitého kódu. Takže, ak ste trochu zabudnúť kde ste vo vašom programe, alebo ste zvedaví, čo sa deje okolo neho, to bude len vytlačiť segmente podobných päť alebo šesť riadkov okolo neho. Takže môžete lepšie zorientovať o tom, kde sa práve nachádzate. 

Vytlačiť nejaké premenné. Takže, ak máte kľúč ako v Caesar, že sa pozrieme na. Môžete povedať, že PRINT na každom mieste. To vám poviem, čo je hodnota, takže že možno niekde na ceste, k prepisu kľúč. Môžete si skutočne povedať, že preto, že môžete skutočne sledovať túto hodnotu. 

V miestnych obyvateľov, len výtlačky z vašich lokálnych premenných. Takže, kedykoľvek ste v slučke, a vy jednoducho chcete vidieť podobné, oh. Aká je moja ja? Aká je táto hodnota kľúča že som inicializovať tu? Čo je správa v tomto bode? To bude len vytlačiť všetko z tých, takže vás Nemusíte sa jednotlivo povedať, tlač I. Print Message. Print Key. A potom displej. Čo to robí, je ako vy krok v rámci programu, to bude len uistiť, že je to zobrazovať len niektoré premenné v každom bode. Aby ste also-- --it to druh zástupca kde nemusíte ísť ďalej, ako, oh. Print Key alebo Tlač I. Proste automaticky to pre vás. 

Takže, s tým, že budeme vidieť, ako to ide. Budem sa snažiť a spínače k môjmu prístroju. Uvidíme, či to zvládnem. All. Sme len bude zrkadliť. Nie je nič, čo blázon na mojom notebooku kdekoľvek. OK. To musí byť táto. Je to tak malé. Uvidíme, či to môžeme urobiť. 

OK. Alice sa samozrejme snaží tu len trochu, ale my si to v Momento. OK. Sme len porastie to. OK. Môže každý druh vidieť, že? Možno trochu? Ja viem, je to trochu malý. Nemôžete celkom prísť na to, ako sa robí to väčšia. Ak niekto pozná. Vie niekto, ako na to väčšie? OK. Chystáme sa vrátiť s ním. Nezáleží na tom tak ako tak, pretože je to len To je kód, ktorý vy by majú. 

Čo je dôležitejšie, je terminál tu. A máme tu Prečo je to tak malý? Nastavenie. Oh. Pravda Ike. Ako je to? Odtiaľ. Je to lepšie pre všetkých? OK,. V pohode. 

Viete, kedy ste v SK triedy technické problémy sú trochu súčasťou the-- Takže, poďme vyčistiť to. OK. Takže, tu v sekcii ktoré sme tu mali. Caesar je spustiteľný súbor. Tak som urobil to. Takže jedna vec je si uvedomiť, s GDB je že to funguje len na spustiteľné súbory. Takže nemôžete spustiť na DOTS. Musíte vlastne robiť Uistite sa, že váš kód skompiluje, a že to môže byť v skutočnosti spustiť. 

Takže, uistite sa, že ak sa tak nestane zostaviť si to skompilovať, takže môžete trochu prejsť. Tak pre začiatok GDB, všetko, čo urobiť, Typ Gloria GDB, a potom už len súbor, ktorý chcete. Vždy som chybne Caesara. Ale vy chcete byť istý, pretože je to spustiteľný, TI dot blesk tak, aby znamená, že ideš spustiť CSI budete vykonávať to súbory buď v debuggeri. OK. Takže, to, že sa dostanete tento druh blabol. Je to len všetko o debuggera. Tie naozaj nemajú na starať o to práve teraz. A ako vidíte, máme to otvorené parens, HDP, v blízkosti parens, a len tak vyzerá naše príkazového riadku, je to tak? 

Takže, čo chceme do-- -SO, Prvá vec, ich chceme vybrať miesto, kde je zlomiť. Takže, tam je jedna chyba v tomto programe Caesar že som sa predstaviť, že ideme zistiť. To, čo to je, že sa vstup Barfoo vo všetkých čiapky, a z nejakého dôvodu nemení A. Je to jednoducho odíde je sám, je všetko ostatné v poriadku, ale druhý list Zostáva bezo zmeny. Takže, budeme sa snažiť a prísť na to, prečo to tak je. Takže prvá vec, ktorú zvyčajne chcem robiť pri každom spustení na GDB je prísť na to, kde ju zlomiť. 

Takže Caesar je celkom krátky program. Máme len jednu funkciu, nie? Aké bolo naše funkcie v Caesar? Je tu len jedna funkcia, hlavné je to tak? Hlavné je funkcia pre všetky programy. Ak ste nemali Main, mohol by som je hneď trochu strach teraz, ale dúfam, že ste všetci mali Main tam. Takže, čo môžeme urobiť, je, môžeme proste rozbiť Main, rovnako ako to. Tak, to hovorí, OK. Tam My sme nastavili zarážky jeden. 

Tak, teraz vec na zapamätanie je Caesar trvá jeden argument príkazového riadku právo a my sme to ešte neurobili kdekoľvek. Takže, čo robíte, ak je ste vlastne ísť spustiť program, program, ktorý ste beží v GDB, ktorý potrebuje príkazový riadok argumenty, budete na zadanie pri prvom spustení beží to. Takže v tomto prípade, my Beh s kľúčom tri. A to sa skutočne začať. 

Takže, ak tu vidíte, máme Ak je RC sa nerovná 2. Takže ak vy všetci majú že súbor, ktorý som poslal hore uvidíte, že to je ako Prvý riadok naše hlavné funkcie, nie? Je to kontroluje, či je k dispozícii správny počet argumentov. Takže, ak ste premýšľal, RC ak je správne, môžete robiť niečo len ako Print RC. RC je dve, čo je to, čo sme očakávali, že jo? 

Takže môžeme ísť ďalej, a pokračovať cez. Takže, máme tam nejaký kľúč. A môžeme vytlačiť náš kľúč aby sa ubezpečil, že je to správne. Zaujímavé. Nie tak celkom, čo sme očakávali. Takže jedna vec je si uvedomiť, s GDB tiež, je že to nie je, kým sa skutočne hit Ďalej, že riadok, ktorý ste práve videli je v skutočnosti vykonaný. Takže v tomto prípade kľúčom nebolo pridelené doteraz. Takže kľúč je nejaký odpad hodnota ktoré vidíte na tam dole. Negatívne --It je jeden miliárd dolárov 120-- a niečo divného veci do poriadku? Nie je to kľúč, ktorý sme očakávali. Ale keď sme narazili na Ďalšie a potom sme pokúsiť Print kľúč, je to tri. 

Všetci vidia, že? Takže, ak máte niečo že ste ako, počkajte. To je úplne zle, a ja neviem, ako by sa to stalo, pretože všetko, čo chcem urobiť, je priradiť číslo, premenná, skúste biť Ďalšie, skúste tlačiť znova, a uvidíme, či to funguje. Vzhľadom k tomu, že to len bude vykonávať a vlastne priradiť niečo po vás Ďalší hit. Zmysel pre každého? Hm? 

SPEAKER 2: Pri náhodnej čísla, čo to znamená? 

SPEAKER 1: Je to len náhodný. Je to len odpad. Je to proste niečo, že vaša Počítač bude náhodne priradí. V pohode. Tak, teraz sa môžeme pohybovať, a tak teraz máme tento obyčajný text getString. Takže, dovoľte mi predstaviť, čo sa stane, keď sme narazili Ďalšie tu. Naše GDB druh zmizne, že jo? To preto, že getString Teraz je realizovať, nie? Takže, keď sme videli, obyčajný text rovná GetString, otvorené parens a parens, a my hit Ďalšia, ktorá má Teraz skutočne popravený. Takže, je to čakanie na nám vstup niečo. 

Takže ideme na vstup naše jedlo, ktoré je to, čo to nedarí, ako som vám povedal, a to len hovorí, že je to po spustení, že zatvorené držiak znamená, že je vystupujúce z tejto slučky. Takže môžeme zasiahnuť Ďalšie a teraz, keď som istý, že ste všetci oboznámení od Caesara, je to, čo je táto linka bude robiť. Je to pre int i = 0, N sa rovná Strlen, obyčajný text, a potom Aj je menšie ako n, I, plus, plus. Čo je to slučka robiť? Otvorte správu. V pohode. Takže, poďme začať robiť to. 

Takže, ak by táto podmienka zápas, pre naše prvé? Ak je to B, je to obyčajný text I. sme môžete získať informácie o našich miestnych obyvateľov. Takže, je nula, a ak je šesť, ktoré očakávame, a naším hlavným je tri. Všetko, čo dáva zmysel, nie? Tieto čísla sú presne to, čo by malo byť. Takže, hučanie? SPEAKER 3: Mám náhodné čísla pre môj. SPEAKER 1: No, môžeme check-- --we môžete chatovať o tom v sekunde. Ale mali by ste byť stále to. Takže, ak máme kapitál B pre naše prvé, táto podmienka by ho chytiť, nie? Takže, keď sme narazili na Next, vidíme, že, ak skutočne vykonáva. Pretože ak ste po spolu v kóde, tento riadok tu, kde obyčajný text I sa nahrádza takto aritmetike, vykoná len v prípade if Podmienkou je správne v poriadku? 

GDB bude len ukázať vám, veci, ktoré sú skutočne vykonávanie. Takže ak táto podmienka Pokiaľ nebola splnená, je to len tak preskočiť na ďalší riadok. OK? Takže, máme to. Tento držiak znamená, že je zatvorené z tejto slučky teraz. Takže, bude to začať znova. Rovnako ako, že. Tak, že sa môžeme dostať informácie o našich miestnych obyvateľov tu, a vidíme, že naše prvé list zmenilo, že? Teraz je E, ako to má byť. Áno, môžeme pokračovať ďalej. 

A máme túto kontrolu. A ak táto kontrola by mala fungovať, nie? Je to A. Je treba zmeniť tri písmená vpred. Ale ak si všimnete, my niečo iné. Takže v tomto prípade tu, to chytil to, a tak táto linka vykonaný, ktoré upravovalo našu B. Ale v tomto prípade je tu, sme, že to jednoducho preskočí ju, a šiel na [? L Koná. ?] Takže niečo sa tam deje. Čo, že to hovorím, je to, vieme, že by mal zachytiť tú, ale nie je tomu tak. Môže niekto vidieť, čo naši Problém je v tomto riadku? Je to veľmi minútu vec. A môžete sa tiež pozrieť na váš kód. Je to tiež line-- zabudnúť na to, čo vedenie je v there-- ale je to v [nepočuteľné]. Áno? 

SPEAKER 4: Je to na viac ako strana, pokiaľ ju čítal v knihe. SPEAKER 1: Presne tak. Takže, debugger nemohol povedať si to, ale debugger Tie by mohli získať až na líniu že viete, nie je funkčná. A niekedy, keď najmä neskôr v semestri, kedy máte čo do činenia s sto, a sto pár riadkov kódu, a vy Neviem, kde sa to nedarí, je to skvelý spôsob, ako to urobiť. Takže sme našli chybu. Môžete opraviť v súbore, a potom je možné ho znova spustiť, a všetko bude perfektne fungovať. A najväčšia vec je to môže zdať, OK. Jo. V pohode. Vedeli ste, čo hľadáte. Takže ste vedel, čo má robiť. 

GDB môže byť super užitočné, pretože vám môžete vytlačiť všetky tieto veci, ktoré ste nie. Je to oveľa užitočnejšie než printf. Ako mnohí z vás používajú ako vyhlásenie printf zistiť, kde chyba bola, že jo? Takže, s tým, že nie musí neustále vracať, a ako komentovanie na Printf alebo okomentovaní, a zistiť, čo mali by ste byť tlač. To vlastne len vám umožní krokovať, vytlačte veci ako ste prechádza, takže môžete pozorovať, ako sa mení v reálnom čase, ako váš program beží. 

A to trvať trochu trochu zvykať. Ja by som Veľmi odporúčam len tak z toho trochu frustrovaný s ním práve teraz. Ak máte stráviť hodinu po Budúci týždeň ale naučiť sa používať GDB, ušetríte sami toľko času neskôr. A to doslova. povieme to ľudí každý rok, a spomínam si, keď som sa triedy, bol som rád, že budem v poriadku. Nie. Pset 6 prišla a ja som bol ako, ja som chcel učiť ako používať GDB, pretože sa mi nepáči vedieť, čo sa tu deje. 

Takže ak budete mať tak čas použiť na menšie programy že budete mať pracuje, rovnako ako pracovné cez niečo ako Visionary, ako je tento. Alebo ak chcete ďalšie praxi, som si istý, Nemohol som prísť s buggy programy, pre vás ladiť, ak chcete. 

Ale ak si len vziať nejaký čas, aby si na to zvyknutí, len hrať sa s ním, to bude naozaj slúžiť dobre. A je to naozaj jedna z tie veci, ktoré ste práve musieť skúsiť a dostať svoje špinavé ruky sa predtým, než sa naozaj pochopiť. Naozaj len raz pochopil Musel som ladiť veci s ním, a je to oveľa príjemnejšie mať predstavu o tom, ladenie skôr skôr ako neskôr. OK. V pohode. Viem, že je to niečo ako rýchlokurz v GDB, a ja budem určite pracovať na získanie Tieto vyzerať väčšie nabudúce. V pohode. 

Takže, ak sa vrátime k našej aplikácii PowerPoint. Je to bude fungovať? AWH. Áno. OK. Takže, ak ste niekedy potrebovať niektorý z ty zase, tam je zoznam. Tak binárne vyhľadávanie, ktoré každý spomína na skvelú podívanou Davida kopírovanie telefónnych zoznamov na polovicu. Nemám naozaj dostať telefónne zoznamy už, pretože rovnako ako kde sa vám si telefónne zoznamy v týchto dňoch? Ja naozaj neviem. Binárne vyhľadávanie. Pamätá si niekto, Ako Binárne hľadaní práce? Vôbec niekto? Jo? SPEAKER 5: Viete, kedy sa pozriete na ktorých polovica to by bolo v, na tom základe, a zbaviť druhej polovice. 

SPEAKER 1 Presne tak. Takže, binárne vyhľadávanie, je to celkom je-- --we chcel volať to rozdeľ a panuj. Takže, čo budete robiť, je budete vyzerať v stredu, a uvidíte, či to zodpovedá to, čo hľadáte. A ak to tak nie je, skúste sa zistiť, je, že bude ponechaný polpenzia alebo pravú polovicu. Takže by to mohlo byť, ak hľadáte na niečo, čo je podľa abecedy, vidíš, oh. Má Allison prísť pred M? Áno. Takže ideme na pozrite sa na prvom polroku. 

Alebo by to mohlo byť ako s číslami. Čokoľvek, čo môžete nákupný, to môže byť triedené. Môžete použiť binárne vyhľadávanie na. Takže, niekto pamätať graf alebo čo to je? Je to asymptotickej zložitosť. Takže, tento graf len opisuje, ako dlho dostanete vyriešiť problém, ako zvýšite počet vecí ktorý používate. 

Takže máme N, čo je lineárny čas. Ak N viac ako dva, čo je o niečo lepšie, stále rastie super rýchly. A potom sme Prihlásenie, ktorý je to, čo považujeme za binárne vyhľadávanie. Ak si všimneme, ako váš problém dostane oveľa a oveľa väčší, Čas, ktorý zaberie vám to vyriešiť nie je naozaj zvyšuje, že veľa. Je to ako porovnateľné tu na začiatku. Si ako, OK. Niečo tu nie je naozaj ohľadu na to, ktorý z nich používame, ale dostanete sa k miliónu, miliarda. Snažíte sa nájsť some-- --you're sa snaží nájsť ihlu v kope sena. 

Myslím si, že chcete tento problém. Chcete túto zložitosť, nie lineárny, pretože za všetko, čo viete, že vaša bude sa prehľadávať každý jednotlivec ihla, čo sena, snaží hľadať ihlu. A to nie je podľa môjho názoru príliš zábavné. Rýchlo, že som rád. Mám rád efektívna. A ako pracovití študenti vám prináša chlapci, viete pracovať chytrejšie, nie ťažšie typ vec, ako sa vám môže tvoriť tieto algoritmy. 

Takže, ideme na prechádzku cez len rýchly príklad. Myslím si, že chlapci by mali mať ruku na binárne vyhľadávanie, ale v prípade, že niekto je trochu rozmazaný, chcete ho posilniť, budeme jednoducho ísť cez príklad. Takže, hľadáme ak pole obsahuje sedem. 

Takže prvá vec, ktorú robíme, je hľadať v stredu, nie? A tiež budete sa kódovanie Binary Search pár sekúnd. Takže, to bude sranda. Tak sme sa pozrieť do stredné malé pole 3. Má 3 sa rovná 7? Nie je. Je to šesť. Takže, to je menej ako alebo väčší ako sedem? Menej ako. Áno. Dobrá práca chlapci. Mám pocit, že by som mal mať sladkosti, pretože som chcú vyhodiť do dvorov. To je to, čo budem robiť budúci týždeň. Bude vás chlapci ostré. 

Takže, vyhodíme, že prvá polovica, je to tak? to bolo menej ako. vieme, že všetko, na tej ľavej strane bude menšia ako to, čo sú vlastne hľadáme. Takže, nie je potrebné, aby venovať pozornosť. Proste na to zabudni. Tak, teraz sa pozrieme na našu pravej strane, a my sa v stredu tam, a teraz je to deväť. Takže, 9 je-- --Everyone? Väčšie, než to, čo sme hľadať, že jo? Takže ideme hodiť preč všetko vpravo. Takhle. Teraz všetko, čo ste odišiel s jedným. Tak sme sa zistiť, je to jedno, čo hľadáme? to je. Zistili sme, čo sme chceli. Takže sme hotoví. Bilineárne Search. 

A ak si všimnete, my mal tam sedem vstupov. To nám trvalo len ako trikrát, ale ak robíte ako miliardy vy viete, koľko krokov to by trvať, ak sme mali štyri miliardy veci? Akékoľvek odhady? Je to 32. 32 krokov, ako nájsť niečo, vo štyri miliardy prvok poľa, pretože sily dva. Takže dva je 32, je na štyri miliardy korún. 

Tak dosť šialené, ako ste stále v ako pomerne malom počte krokov nájsť niečo, čo v štyrmi miliardami prvky. Takže v takom prípade, že sme bude kód tejto tak vy môžete naozaj druh vidieť, ako to funguje. Dobre, takže vy môžete kódovať. Idem si chlapci nechať hovoriť trochu. Spoznajte ľudí okolo seba, čo je to, čo by niekto chcel z poslednej časti. 

Takže spoznať ľudí okolo seba. Hovoriť trochu. A všetko, čo chcem od vás Chlapci práve teraz je len pokúsiť sa vytvoriť náčrt pseudokódu. OK? Whoa. Jediné, čo chcem od vás, je, že ste len tak pre vyplnenie tejto chvíli prípadu. Tak som si stanovili tieto vyššie a dolné medze, ktoré predstavujú začiatok a koniec nášho poľa. A budete skutočne prechádzať a prísť na to, to, čo robíme v rámci tohto cyklu while. 

Takže ak môžete prísť out-- mám nápoveda there-- aké sú prípady, že tu máme? Takže ak chcete zistiť, prípady, budeme pseudokódu ty a potom budeme vlastne kód je. A to bude, som si, dúfajme, že to bude byť o niečo ľahšie, než ste očakávali. Vzhľadom k tomu, že to nie je tak moc kód, v skutočnosti, čo je naozaj cool. 

Mm-hm? 

STUDENT: [nepočuteľné]? Inštruktor: Áno. Tam bolo niečo nájsť v stredu. 

Žiak: Takže môžeme použiť. OK. 

Inštruktor: Perfect. Tak to je prvá vec, ktorú musíme urobiť. Takže nájsť stred. Skvelé. Takže máte predstavu o tom, ako by sme mohli skutočne nájsť stred s kódom? 

STUDENT: Jo. n nad 2? Inštruktor: Takže n nad 2. Takže jedna vec na zapamätanie je, že Vaša horná a dolná hranica meniť. Neustále škrtiť časť matice sa pozeráme na. Tak n nad 2 bude fungovať iba prvá vec, ktorú robíme. Tak pričom horné a dolné do úvahy, ako by sme mohli dostať, že prostredný prvok? Pretože chceme, aby stredná medzi hornou a dolnou, že jo? Mm-hm? 

STUDENT: [nepočuteľné]. 

Inštruktor: Takže máme nejaký stred. A to bude horná a dolná nad 2. Úžasné. Tak ideme. Jeden riadok dole. Vy ste na vašej ceste. Takže teraz, že máme prostredný, čo chceme robiť? Len všeobecne. Nemusíte to kód. Áno. STUDENT: [nepočuteľné]? Inštruktor: Takže je to navyše preto, že ste nájdenie priemer medzi dvoma z nich. Takže ak si myslíte, že z nich ako druh zvýšenie v zo strán, premýšľať o tom, ako sa budete blížiť stredná, chcete takto. Takže ak ste boli na oboch stranách strednej a máme ako 5 a 7. Keď je sčítame vám získať 12, rozdeliť o 2, 6. 

Niekedy je to ťažké vysvetliť, prečo to funguje, ale ak budete pracovať cez Príklad niekedy, to vám pomôže zistiť, či by malo byť plus alebo mínus. Áno. 

STUDENT: [nepočuteľné] presne v strede keby mali prípad, kedy je tu veľa menších čísel a ako jeden veľký počet? 

Inštruktor: Takže všetko, čo potrebujete je uprostred poľa. Takže ak ste mali veľa malých čísiel a potom jeden naozaj veľký počet Na konci, na tom nezáleží. Všetko, na čom záleží, je, že oni sú radené, ktoré ste práve Chcete sa pozrieť na stredu pole, pretože ste stále krájanie váš problém na polovicu. V pohode. Takže teraz, že máme prostredný, čo budeme robiť ďalej? 

STUDENT: Porovnajte. Inštruktor: porovnať. Takže porovnávať stredné až value_wanted. V pohode. Takže vidíte, tu máme táto hodnota chceme tu. Pamätajte, je to pole. Takže stredná odkazuje na indexe. Takže chceme robiť hodnôt uprostred. Nezabudnite, ak chcete porovnať, dvojlôžkové rovná. Robíte single rovná ste len tak ju preradiť, a potom, samozrejme, je to Bude na hodnotu, ktorú chcete. Takže nerobte to. 

Takže ideme zistiť, či hodnoty na stred je rovná hodnote chceme. Nezabudnite na svoje rovnátka. Dropbox mal ísť preč. Tak čo budeme robiť v tomto prípade? Ak je to, čo chceme vrátiť? Snažíme sa povedať. 

STUDENT: Tlač off. 

Inštruktor: No, my sme nechcete vytlačiť. Tak to je bool tu, a tak sme chcete vrátiť hodnotu true alebo false. Hovoríme, je toto číslo [? RRA? ?] Takže ak je to, len sme sa vrátiť to pravda. Keď sa mi podarí kúzlo pravda. 

STUDENT: Prečo by sa teda vrátite nula? Inštruktor: Takže by ste mohli vráti nulu, ak ste chceli. Ale v tomto prípade použiteľné, pretože naša funkcia vracia hodnotu typu bool, Musíme sa vrátiť buď true alebo false. STUDENT: Keď ste riekol: boolean výrazu, Môžete je rovná false? Rovnako ako keď som chcel povedať, ak je táto podmienka nie je splnená, ako je horná rovná false. Bude to, ak ste práve pochopili dať falošný na strane druhej? Inštruktor: Jo. Takže v skutočnosti, ak ste niekedy niečo ako je horná alebo je nižšia, ktorá vracia true alebo false a je to vlastne zlé štýl povedzme rovná rovná pravda alebo rovné rovná false. Ak chcete použiť tento výsledok ako sám ako kontrola. Nie to, čo som chcel. To je to, čo som chcel. Takže v prípade, že sa pýtate o niečom, ako je uloženie tejto vc. 

Takže ak máme int main (void) a niečo také. A ak máte je horná nejakého vstupu a ste s otázkou, či môžete robiť niečo také? Je to tak? STUDENT: Snažil som sa ako to urobiť, [nepočuteľné]. Pretože ak it's-- Inštruktor: Správne. Takže vy chcete to, že je falošný, nie? STUDENT: Jo. Inštruktor: Takže v tomto prípade, Chcete to vykonať, ak to nie je pravda. Takže v pohode vec, ktorú urobiť, je to. Takže pamätajte výkrik bod popiera veci? To hovorí, že [nepočuteľné] znamená nie. Takže ak sa pozrieme na práve táto časť tu, mali by ste hovoria, že je vyhodnotený false, ako chcete, aby. Nie falošný je pravda, ktorá znamená, že tento by sa spustiť. Dáva to zmysel? STUDENT: Jo. Inštruktor: Úžasné. OK. Takže sme mohli len vrátiť platí v tomto prípade. Takže teraz máme ďalšie dve prípady, v tomto prípade. Aké sú naše dva ďalšie prípady? Povedzme to urobiť takto. Takže začnime s iný ak hodnoty na stred je menšia ako hodnota, ktorú chceme. Takže naše hodnoty v strede, je menej ako hodnota, ktorú hľadáme pre. 

Tak ktorý viazaný vás robiť , Že chceme aktualizovať? Hornej alebo dolnej? Horné? Takže, na ktorej strane poľa sa budeme pozerať na? 

STUDENT: nižšia. 

Inštruktor: My ideme že sa pozerá na ľavej strane. Takže else if málo hodnota je menšia. Tak tu vašej strednou hodnotou je menej ako to, čo chceme. A tak chceme, aby sa Pravá strana našu ponuku. Takže ideme na aktualizovať naše dolná hranica. Takže budeme priradiť naša nižšia. A čo si myslíte, že by mala byť nižšia? STUDENT: stredná hodnota? Inštruktor: Takže stredná value-- STUDENT: Plus 1. Inštruktor: --plus 1. Môže mi niekto povedať, prečo máme to plus 1? 

STUDENT: [? Žiadna hodnota?] je rovný neho. 

Inštruktor: Správne. Pretože už vieme, že Naša stredná hodnota nie je rovná to a chceme vylúčiť zo všetkých následných vyhľadávania. Ak zabudnete, že plus 1, táto bude páčiť slučky na dobu neurčitú. A budete len byť zachytené nekonečnej slučky, a potom budete segfault a veci idú zle. Takže vždy uistite, že nie ste vrátane hodnoty, ktoré ste práve Pozrel sa na. Tak sme sa o to postarať sa znamienkom plus 1. 

Takže teraz máme poslednú podmienku ktorý som vždy z bezpečnostných dôvodov si môžete pozrieť tu, else if hodnota na prostredný je väčšia ako hodnota chceme. To znamená, že chceme ľavá polovica. Takže, ktorý z nich sa budeme aktualizovať? Horný. A čo je toto bude rovnať? Stredná mínus 1, pretože Samozrejme, chceme aby sa ubezpečil, že nie sme pri pohľade na tejto strednej hodnote znova. A potom sme si to. To je všetko. To je všetko, binárne vyhľadávanie. Nie je to tak zlé, nie? Je to ako 10 riadkov kód s medzerou. Tak veľmi silný, veľmi užitočné, budete byť použitie v jednej zo svojich neskorších psets. Možno nie tento, ale neskôr. Tak sa to naučiť. Milovať. To vám dobre liečiť. Takže má niekto akékoľvek Otázky týkajúce sa binárne hľadanie? Áno. 

STUDENT: Záleží na tom, či je váš n je párne alebo nepárne? 

Inštruktor: Nie Pretože sme obsadil ju do stredu as int, bude to len skrátiť ho. Tak to zostane celé číslo a to bude nakoniec roztriediť všetko. Takže nemusíte mať strach o tom. Každý dobrý? Úžasné. V pohode. Takže, vy ste dostali to. Slideshow. Tak, ako sme hovorili o, ja viem, David spomenul zložitosť doby chodu. 

Takže v najlepšom prípade, je to len jeden, ktorý nazývame konštantný čas. Môže mi niekto povedať, prečo by to mohlo byť? Aký typ scenára by to znamenalo? Mm-hm. 

STUDENT: [nepočuteľné] first-- Inštruktor: Takže stredná bytia Prvým prvkom, ktorý sa dostávame k, nie? Takže buď pole jednej alebo čo sme hľadali len sa stane, že plácnutí DAB v stredu. Tak to je naša najlepšia prípad. Sa dostanete do skutočné problémy, pravdepodobne nie bude dosiahnuť [nepočuteľné], ktoré sa často. Čo o našom najhoršom prípade? Náš najhorší prípad je log n. A že má čo do činenia s celým právomoci dve veci, ktoré som hovoril. 

Takže v najhoršom prípade by to znamenalo že sme museli kosiť polia dole kým nebolo súčasťou jednej. Takže sme museli rozsekať ho na polovicu toľkokrát, koľkokrát, ako sme len mohli. To je dôvod, prečo je to log n, pretože stačí držať delenie dvoma. Takže predpoklady, veci, ktoré Potrebujem vedieť, či ste niekedy bude používať binárne vyhľadávanie. Vaša prvky musia byť radené. Musia byť triedené, pretože že je to jediný spôsob, ako môžete vedieť, či ste schopní vyhodiť polovicu. 

Ak ste mali túto neusporiadané vrece čísel a vy hovoríte, OK, idem skontrolovať stred číslo a číslo Zháňam je menej ako to, že som jednoducho ísť ľubovoľne vyhodiť jednu polovicu. Tie by, ak nie vedieť vaše Čísla v tomto druhom polroku. Váš zoznam musí byť vyriešené. Rovnako tak to môže byť pokračuje trochu, ale musíte mať náhodný prístup. Musíte byť schopní len ísť do tej prostrednej prvok. Ak máte prechádzať niečím alebo to trvá vám ďalšie kroky aby som sa dostal do stredného prvku, to sa prihlásiť n už preto, pridávate viac práce do neho. A to bude trochu väčší zmysel za dva týždne, ale ja som tak nejako chcel začínať, dať Vy predstavu o tom, čo je prísť. Ale to sú dva dôležité predpoklady ktoré budete potrebovať pre binárne zoznamu. Uistite sa, že je to triediť. To je ten veľký pre vy práve teraz. A na to môžeme ísť do zvyšok našich druhov. Takže štyri sorts-- bublina, vloženie, výber a korešpondencie. Sú to všetko celkom fajn. Ak vy rozhodnete pre CS 124, Dozviete sa o všetkých možných druhov. A ak ste fanúšik xkcd tu Je to naozaj v pohode komiks o ako veľmi neefektívne druhov, ktoré som Veľmi odporúčam vám ísť pozrieť. Jedným z nich je ako panickej druhu, ktorý je rád, oh nie, vráti náhodné polia. Vypnutie systému. Odísť. Takže geek humor je vždy dobré. 

Takže má niekto pamätať druh ako sa len všeobecnú predstavu o tom, ako bublina trochu funguje. Pamätáš? 

STUDENT: Jo. 

Inštruktor: Choď do toho. 

Žiak: Takže ideš skrz ak je väčšia, potom vymeniť dva. 

Inštruktor: Mm-hm. Presne tak. Takže stačí iterovat. Môžete skontrolovať dve čísla. Ak pred jeden je väčší než je potom, stačí vymeniť ich tak, aby v Týmto spôsobom všetky vyšších čísel bublina až ku koncu zoznamu a všetky nižšie počty bublina dole. 

Povedal vám ukázať chlapci v pohode zvukový efekt triedenia video? Je to celkom v pohode. Tak len povedal Robert, algoritmus ktorý ste práve krok v zozname, vymení susedné hodnoty v prípade, že nie ste v poriadku. A potom už len stále opakovať kým nemáte žiadne swapy. Takže to nie je zlé, nie? Tak sme si dať rýchly príklad tu. Takže to bude triediť je vo vzostupnom poradí. Takže keď sme sa prejsť prvý Tentoraz sme sa pozrieť cez osem a šesť očividne nie sú v poradí, sme ich vymeniť. 

Tak sa pozrite na ten budúci. Osem a štyri nie je v poriadku. Vymeňte ich. A potom osem a dve, vymeňte ich. Tak ideme. Takže po prvom prechode, viete, že váš najväčší počet bude po celú cestu na vrchole, pretože je to len bude neustále väčší než všetko ostatné a to len tak, aby bubliny sa celú cestu až tam do konca. Má to zmysel pre každého? V pohode. 

Takže sa pozrieme na našu druhom prechode. Šesť a štyri, switch. Šesť a dve, switch. A teraz tu máme pár vecí do poriadku. Takže pre každý priechod, ktoré sme aby po celú dobu nášho zoznamu, Vieme, že rovnako ako, že veľa čísel na konci bude musieť byť zoradené. Takže robíme tretej prihrávku, ktorý je jedným swap. A potom sa na náš štvrtý prejsť, máme nulové štrbiny. A tak vieme, že naše pole bolo radené. 

A to je veľký vec bublinkové druhu. Vieme, že keď sme majú nulovú swapy, ktoré znamená, že všetko, čo je úplne poradí. Je to trochu ako skontrolovať. Tak sme sa tiež bude kód bublinu druh, ktorý tiež nie je tak zlé. Žiadny z nich nie je tak zlé. Viem, že sa môže zdať trochu desivé. Viem, že keď som sa trieda, aj keď som učil triedu pre prvýkrát v minulom roku, Bol som rád, ako to mám urobiť? To dáva zmysel v teórii, ale ako to vlastne urobiť? Čo je dôvod, prečo aj ja chcem ísť prostredníctvom kódu s vami tu. Takže mám pseudokódu pre vás tentoraz. Takže stačí mať na pamäti, ako chystáme sa prejsť cez. Takže máme nejaké počítadlo, ktoré udržuje naše swapov, pretože musíme uistiť, že sme overiť, že. A my opakovať celý rad ako sme práve urobil s týmto príkladom. Ak je prvok predtým, než je väčšia než prvok neskôr, kde sme v, sme vymeniť je a my zvýšiť otázky counter pretože akonáhle sme sa vymeniť, Chceme, aby naše counter vedieť. Nejaké otázky? Niečo sa zdá smiešne sem. STUDENT: Myslíte si nastaviť počítadlo na nulu zakaždým, keď idete cez slučku? Nezdá sa vám ísť ďalej späť na nulu zakaždým? Inštruktor: Nie nevyhnutne. Takže čo sa stane, je, že sme prejsť tu. Tak robiť, keď, pamätajte, že táto bude vykonávať raz bez výnimky. Takže to bude nastavenie čítač rovný nule, potom to bude iterovat. Ako to prejde, to bude aktualizovať počítadlo. Ako sa aktualizuje čítač, keď sa to robí, keď to dosiahne konca poľa, ak náš zoznam nie je triedené, čítača boli aktualizované. 

Tak sa kontroluje stav a to hovorí: OK, je čítač väčší ako nula. Ak je, urobiť to znova. Ak chcete obnoviť tak, že keď vás prejsť, čítač je rovná nule. Ak pôjdete cez triedených polia, nič sa nezmení, tento postup zlyhá, a vrátiť zoradený zoznam. Má to zmysel? STUDENT: Mohlo by sa trochu. Inštruktor: OK. Ak existuje akákoľvek iná otázka, ktorá príde. Áno. 

STUDENT: Čo by funkcia byť pre prečerpanie prvky? 

Inštruktor: Takže vlastne môžeme napísať že ak budeme práve teraz. V pohode. Takže v takom prípade, Alison sa deje prepnúť späť do prístroja. To bude sranda. A máme pekný bubble sort, čo tu. Tak som to už urobil na bicykli cez pole. Máme swapy, ktoré sú rovné nule. Takže chceme vymeniť priľahlé prvky, pokiaľ sú mimo prevádzky. Takže prvá vec, ktorú musíme to je iterovat našu ponuku. 

Tak ako si myslíte, že by sme mohli iterovat našej ponuku? Máme pre a i = 0. Chceme byť aj nižšia ako n mínus 1 mínus k. A ja budem vysvetľovať, že v sekunde. Tak toto je optimalizácia tu, kde Spomínam si, ako som povedal, po každom priechode cez pole my viem, že to, čo je on-- 

Takže po jednom prechode sme viem, že to je radený. Po dvoch priechodoch vieme, že to všetko je usporiadaný. Po troch priechodoch sme viem, že je triediť. Tak, ako som iterácie cez pole tu Je to uistite sa, ísť len prostredníctvom toho, čo vieme, je netriedený. OK? To je len optimalizácia. Dalo by sa napísať naivne len iterácie cez všetko, by to jednoducho trvať dlhšie. S týmto štyri slučky je len pekný optimalizácia pretože vieme, že po každej plnej iteráciu cez pole tu, ako každú celú slučku tu vieme, že jeden z týchto prvkov budú rozdelené na konci. 

Tak sme sa nemuseli starať o tie. Má to zmysel pre každého? Že v pohode malý trik? Takže v tomto prípade, ak sme iterácie, vieme, že chceme zistiť, či polia n a n + 1 sú v poriadku. OK. Tak tu je pseudokódu. Chceme zistiť, či pole n a n a 1 sú v poriadku. Takže to, čo môžeme mať, že? Bude to mať nejaký podmienené. Ak bude. 

STUDENT: Ak je pole n je menej ako pole n plus 1. Inštruktor: Mm-hm. No, menšia alebo väčšia ako. STUDENT: Väčšie ako. Potom ich chceme vymeniť. Presne tak. Takže teraz sme sa dostali do toho, čo je Mechanizmus je vymieňať? Tak sme šli cez túto krátku dobu, typ funkcie odkladacieho minulý týždeň. Pamätá si niekto, ako to funguje? Takže môžeme nielen priradiť im, že jo? Vzhľadom k tomu, jeden z nich sa stratí. Ak sme povedali, sa rovná B a B je rovná A, všetky náhle obaja sú len rovná B. 

Takže to, čo musíme urobiť, je, že sme majú dočasné premenné, ktoré je bude držať jeden z našich chvíľu sme v procese vymieňať. Takže to, čo máme, je, že budeme musieť nejakú int teplota je rovná to-- môžete priradiť sa podľa toho, čo potrebujete, stačí uistite sa, že budete mať prehľad o to-- takže v tomto prípade budem priradiť k poľu n plus 1. Tak, že to bude držať bez ohľadu na hodnota je v tomto druhom bloku že sa pozeráme. 

A potom, čo môžeme urobiť je, že môže ísť dopredu a Preradiť pole n + 1, pretože my vieme, majú túto hodnotu uloženú. To je tiež jeden z veľkých things-- nemám, ak niekto z vás vedieť, mal problémy, kde keď prepnete dvaja riadkov kódu náhle veci fungujú. Objednávka je veľmi dôležité v CS. Takže sa uistite, diagram veci, ak je to možné pokiaľ ide o to, čo sa skutočne deje. Takže teraz budeme priradenie pole n + 1, pretože my vieme, majú túto hodnotu uloženú. 

A môžeme priradiť, že na poli n, alebo v tomto prípade aj pole. Príliš veľa premenných. OK. Takže teraz sme prevelený pole I plus 1 sa rovná, čo je v poli i. A teraz sa môžeme vrátiť a priradiť polia som sa, čo? Každý, kto? 

STUDENT: 10. 

Inštruktor: 10. Presne tak. A ešte jedna posledná vec. Ak sme vymenili hneď, Čo musíme urobiť? Čo je jedna vec, , Čo sa deje, aby nám povedali či sa niekedy ukončiť tento program? Čo nám hovorí, že majú zoradený zoznam? Ak nebudeme vykonávať žiadne swapy, že jo? Ak swapov sa rovná nulu na konci tohto. Takže kedykoľvek vykonať výmenu, ako my práve tu urobil, chceme aktualizovať swapy. A viem, že tam bol Otázka skôr o môžete použiť nula alebo jedna, miesto true alebo false. A to je to, čo to robí tu. Tak to hovorí, ak nie swapy. Takže ak swapov je nula, čo je-- vždycky dostať moje pravdy a mojej falses poplietol. Chceme, aby sme mohli zhodnotiť na hodnotu true, a to nie je. Takže ak je to nula, potom je to falošné. Ak to popierajú s [? bang?] sa stáva pravdou. Takže tento riadok spustí. 

Pravdy a falošné a núl a jednotiek si blázon. Len ak ste pomaly chodiť cez to, že bude mať zmysel. Ale to je to, čo tento malý bit kódu tu robí. Takže to skontroluje, sme urobili nejaké swapy. Takže ak je to niečo naviac nula, bude to, že je falošný a celá vec je bude znovu spustiť. V pohode? 

Študent: Čo je prestávka robiť? 

Inštruktor: Prestávka len vypukne vás zo slučky. Takže v tomto prípade by rovnako ako ukončenie programu a tie by len mať svoj zoradený zoznam. STUDENT: Amazing. Inštruktor: Ospravedlňujem sa? STUDENT: Pretože predtým sme použité písomné 1 prepísané nulu predstaviť, že v prípade, že bude fungovať, alebo nie. 

Inštruktor: Jo. Takže sa môžete vrátiť nula alebo jedna. V tomto prípade, pretože nie sme v skutočnosti robiť niečo s funkciou, chceme len to zlomiť. Sme naozaj nestarám o to. Brzda je tiež dobré, ak je použitá pre prepukajú zo štyroch slučiek alebo podmienok, ktoré Nechcete, aby vykonávanie. Stačí len tí z nich. Je to trochu nuansy vec. Mám pocit, že je tu veľa ručnej onduláciu, rovnako ako sa dozviete o tom čoskoro. 

Ale vy sa dozviete o tom čoskoro. Sľubujem. OK. Takže sa všetci dostať Bublinkové triedenie? Nie je to tak zlé. Iterovat, výmenné veci pomocou temp variabilný, a všetci tam nastaviť? V pohode. Úžasné. OK. Späť na PowerPoint. Akékoľvek otázky všeobecne o nich tak ďaleko? V pohode. Mm-hm. 

STUDENT: [nepočuteľné] int main zvyčajne. Máte mať to za to? 

Inštruktor: Tak sme boli len hľadáte len na skutočný triedenie algoritmu. Ak ste ju mal v rámci ako väčšieho programu, budete mať int main niekde. V závislosti na tom, kde ste použitie tohto algoritmu, by to zistiť, čo je vrátenej to. Ale pre náš prípad, my sme striktne pri pohľade na to, ako to robí v skutočnosti iterovat poľa. Tak sme sa nemusíte starať o to. 

Tak sme hovorili o najlepšom prípade a najhorších scenárov pre binárne vyhľadávanie. Tak to je tiež dôležité, aby sa že pre každý z našich druhov. Takže to, čo si myslíte, že je to najhoršie, Prípad runtime bublinkovej druhu? Vy pamätáte? 

STUDENT: N mínus 1. Inštruktor: N mínus 1. Takže to znamená, že existujú n mínus 1 porovnanie. Takže jedna vec je uvedomiť si, že na prvú iteráciu, prejdeme, budeme porovnávať Tieto two-- tak to je 1. Tieto dva, tri, štyri. Takže po jednom prechode sme už štyri porovnanie. Keď hovorím o behu a n. N predstavuje počet porovnaní v závislosti na tom, ako veľa prvkov máme. OK? 

Tak sme sa prejsť, máme štyri. Až sa nabudúce budete vedieť, že nie musí sa postarať o to. Porovnáme tieto dva, tieto dve, tieto dva, a keď sme nemali, že optimalizácia so štyrmi slučky, ktoré som napísal, by ste sa nákupný tu tak ako tak. Takže budete musieť prejsť pole a aby n n porovnanie časy, pretože zakaždým, keď beh cez to triedime jednu vec. 

A zakaždým, keď sme sa prejsť pole, robíme n porovnanie. Takže naša runtime je to v skutočnosti n na druhú, čo je oveľa horšia v našej Prihlásenie koniec, pretože to znamená, že ak sme mali štyri miliardy prvky, je to bude nám trvať štyri miliardy štvorcový miesto 32. Takže nie je najlepší runtime, ale niektoré veci, viete, ak ste v určitý sortiment prvkov bublina druh môže byť v pohode použiť. 

OK. Takže teraz to, čo je v najlepšom prípade runtime? STUDENT: Zero? Alebo 1? 

Inštruktor: Takže 1 by byť jeden porovnanie. Presne tak. 

STUDENT: N mínus 1? 

Inštruktor: Tak jo. Tak n mínus 1. Kedykoľvek budete mať predstavu, ako n mínus 1, máme tendenciu nechaj ho a my sme len povedať, n, pretože máte porovnať každý z these-- každého páru. Bolo by teda n mínus 1, ktoré sme práve povedal je približne n. Keď máte čo do činenia s behu, všetko je v zbližuje. Tak dlho, ako je exponent správne, že ste celkom dobrý. 

To je to, ako sa s tým vysporiadať. Tak, že najlepšom prípade je n, ktorý znamená, že zoznam už je zoradený, a všetko, čo urobiť, je spustiť pomocou a skontrolujte, či je to triediť. V pohode. Dobrá. Takže ako vidíte tu, aby sme len nejaké ďalšie grafy. Tak n na druhú. Fun. Oveľa horšie ako n, ako vidíme, a oveľa, oveľa horšie, než log 2n. A potom sa môžete tiež dostať do protokolov protokolu. A budete mať 124, sa dostanete do ako log Star, ktorého sa ako blázon. Takže ak máte záujem, vyhľadávanie log hviezda. Je to celkom sranda. Takže máme tento skvelý graf. Len heads up, to nádherný graf mať pre strednodobé, pretože sme dlho sa vás opýtať na tieto tenšie. Takže len heads up, mať to na vašom v polovici obdobia na svojom peknom ťahák tu. Tak sme sa len pozrel na bubliny druhu. V najhoršom prípade, n na druhú, najlepšia vec, n. A budeme sa pozrieť na ostatné. 

A ako môžete vidieť, len ten, ktorý naozaj robí dobre je merge sort, ktorý budeme mať na to, prečo. Takže sme ísť do budúci here-- výber sort. Pamätá si niekto, ako Výber sort pracoval? Ísť na to. 

STUDENT: V podstate prejsť poradí a vytvoriť nový zoznam. A rovnako ako vy uvedenie prvky in, dal ich na správnom mieste v novom zozname. 

Inštruktor: Takže zvuky spíš vkladanie druhu. Ale ty si naozaj blízko. Sú veľmi podobné. Dokonca som si ich poplietol niekedy. Pred tejto sekcii bol som rád, počkajte. OK. Takže to, čo chcete urobiť, je výber triediť, spôsob, ako si môžete myslieť o ňom a spôsobe Môžem uistiť, že som sa pokúsiť sa dostať je poplietol, je to prechádza a vyberie Najmenšie číslo, a to uvádza, že na začiatku zoznamu. To swapy s týmto prvom mieste. Sú to vlastne máme príklad pre mňa. Úžasné. Takže len spôsob, ako myslieť na to-- výbere druh, vyberte najmenšiu hodnotu. A budeme sa spustiť pomocou príkladu si myslím, že pomôže, pretože Myslím si, že vizuálna vždy pomôcť. Takže začneme s niečím že je úplne netriedený. Red bude netriedený, zelená bude triediť. To všetko dáva zmysel v sekunde. 

Tak sme sa prejsť a my iterovat od začiatku až do konca. A my hovoríme, OK, 2 naše najmenšie číslo. Takže budeme mať 2 a ideme presunúť do prednej časti našej ponuku pretože je to najmenšie číslo máme. Takže to je to, čo to robí. Je to len tak vymeniť tie dva. Takže teraz sme radené časť a netriedené časť. A čo je dobré si uvedomiť, o výbere druhu je, že sme už len výber z netriedeného časti. 

Vytriedený časť, ktorú jednoducho nechať na pokoji. Mm-hm? 

STUDENT: Ako to vieš, čo je najmenší bez porovnania na každej iné hodnoty v poli. Inštruktor: Robí porovnať. Radi preskočí to. To je len všeobecná celkovo. Jo. Keď sme písať kód Som istí, že budete viac spokojní. Ale uložiť tento prvý prvok najmenší. Môžete porovnať a hovoria, OK, je to menšie? Áno. Nechaj si to. Tu je to menšie? Nie? 

To je vaše najmenšie, priradiť ju k svojmu hodnotu. A budete oveľa šťastnejší keď ideme cez kód. Tak sme sa prejsť, sme to vymeniť, tak potom sa pozrieme na tomto netriedeného časti. Takže ideme vybrať tri z. Chystáme sa dať na na koniec našej triedeného časti. A my sme len tak, aby robil to, že robí to, a robiť, že. Tak toto je náš druh pseudokódu tu. Budeme kód to tu v sekunde. Ale len niečo chodiť cez na vysokej úrovni. Budeš chodiť od i = 0 pre n mínus 2. To je ďalšia optimalizácia. Nebojte sa príliš veľa o tom. Tak ako si hovoril. Ako Jacob hovoril, ako my sledovať, čo náš minimum je? Ako to vieme? Musíme porovnať všetko v našom zozname. 

Takže minimálne rovná i. Je to len hovorím, v tomto prípade index nášho minimálnu hodnotu. Takže to bude iterovat a to ide od j je rovný i + 1. Takže už vieme, že to je náš prvý prvok. Nepotrebujeme porovnať ju k sebe. Takže začneme porovnajte ju s ďalšie ten, ktorý je dôvod, prečo je aj a 1 až n mínus 1, čo je koniec poľa tam. A my, ak pole v uvedenom j je menšie ako pole min, potom preradiť, kde Naša minimálna indexy je. 

A v prípade, min nie je rovné I, ako je tam, kam sme sa vrátili sem. Tak, ako keď sme prvýkrát robili tento. V tomto prípade by bol štart na nula, bolo by to skončí tým, že dvaja. Takže by min nerovná aj na konci. To nám umožňuje vedieť, že musíme ich vymeniť. Cítim sa ako konkrétny príklad pomôže oveľa viac než to. Takže budem kódu to s vami práve teraz a myslím, že to bude lepšie. 

Druhy majú tendenciu pracovať týmto spôsobom v tom je to často lepšie, len je vidieť. Takže to, čo chceme urobiť, je najprv chcem najmenší časť v jej polohe v poli. Presne to, čo Jacob hovoril. Musíte uložiť, že nejako. Takže budeme začnite tu iterácie cez pole. Budeme hovoriť, že je to naša Prvý z nich len začať. Takže budeme mať int najmenších je rovná poľa v i. 

Takže jedna vec je si všimnúť, každý keď sa to spustí slučka, začíname o krok ďalej. Keď začneme sa pozrieme na tento jeden. Nabudúce budeme iterovat, začíname na tomto jednom a priradenie je náš najmenší hodnota. Takže je to veľmi podobné bubliny druhu kde vieme, že po jednom priechodu, Tento posledný prvok je triedený. Pri výbere druhu, že je to práve naopak. 

Pri každom priechode, vieme, že Prvý z nich je usporiadaný. Po druhom prechode, druhá bude triediť. A ako si videl s príkladmi prezentácií, naše radené časť jednoducho stále rastie. Takže nastavením naši najmenší z na pole i všetko to robí sa obmedzí, čo sa pozeráme na to, ako minimalizovať počet porovnávanie robíme. Znamená to, že zmysel pre každého? Páči sa mi treba prejsť, že opäť pomalšie alebo inými slovami? Som rád, že. OK. 

Takže sme skladovanie hodnota v tomto bode, ale tiež chceme uložiť index. Takže budeme ukladať pozície najmenší jeden, ktorý sa len bude aj. Takže teraz Jacob je spokojný. Máme veci uložené. A teraz sa musíme pozerať cez netriedeného časť poľa. Takže v tomto prípade, že tento Bude nám netriedený. To je aj. OK. 

Takže to, čo budeme robiť bude pre slučke. Kedykoľvek budete potrebovať iterovat cez pole, vaša myseľ môže ísť do pre slučke. Tak pre niektoré int k equals--, čo si myslíme, že k sa bude rovnať začať? To je to, čo sme si stanovili ako našich najmenších hodnotu a chceme porovnávať. Čo chceme porovnávať to? Je to bude to budúci, je to tak? Tak sme sa chceme k nutné inicializovať aby aj plus 1 na štart. 

A my chceme k v tomto prípade už veľkosť uložené tu, takže stačí použiť veľkosť. Veľkosť je veľkosť poľa. A my jednoducho chceme, aby aktualizovať K niektorým zakaždým. V pohode. Takže teraz musíme nájsť najmenší prvok tu. Takže ak budeme iterovat sme chcem povedať, ak je pole na k je nižšia než naše najmenšie value-- to je miesto, kde sme vlastne sledovanie toho, čo je najmenší here-- potom chceme priradiť čo naša najmenšia hodnota je. 

To znamená, že, oh, my sme iterácie tu. Či už je hodnota tu nie je naša najmenšia vec. Nechceme ho. Chceme ju priradiť. Takže ak sme ho prerozdeľujú, čo robiť si myslíte, že by mohlo byť v tomto kóde tu? Chceme priradiť Najmenší a pozície. Takže to, čo je najmenší teraz? STUDENT: Array k. Inštruktor: Array k. A aká je pozícia teraz? Čo je na indexy naša najmenšia hodnota? Je to len k. Takže pole k, k, sa zhodujú so. Takže sme chceli priradiť to. A potom sme našli našich najmenších, takže na konci tohto cyklu for tu sme našli to, čo naše najmenšie je hodnota, takže sme jednoducho vymeniť ju. V tomto prípade, rovnako ako že naše Najmenšia hodnota je tu. Toto je náš najmenší hodnota. 

Chceme len, aby ho vymeniť tú, ktorá je čo, že funkcia odkladacia na dne áno, ktoré sme práve spísal spolu pred pár minútami. Tak by to malo vyzerať povedome. A potom to bude len opakovať až kým nedosiahne celú cestu až do konca, čo znamená, že majú nulovú prvky, ktoré nie sú roztriedené a všetko, čo bolo radené. Zmysel? Trochu konkrétnejšie? Kód pomôcť? 

STUDENT: Pre veľkosti, nikdy Naozaj ho definovať alebo zmeniť, ako to vieš? 

Inštruktor: Takže jedna vec je Všimnite si, tu je veľkosť int. Takže hovoríme v tomto sort-- druhu je funkcia v tomto case-- je to výber triediť, je odovzdávaný v s funkciou. Takže ak to nebol prijatý vo by ste niečo ako s dĺžkou poľa alebo by ste iterovat nájsť dĺžku. Ale pretože je odovzdávaný v, môžeme len použiť. Ste len predpokladať, že užívateľ vám dal platnú veľkosť, ktorá vlastne predstavuje Veľkosť vášho poľa. V pohode? 

Ak vy máte nejaké problémy s týmito alebo chcete viac praxe kódovanie druhov na vlastnú päsť, mali by ste prejsť na study.cs50. Je to nástroj. Majú checker, ktorý môžete skutočne písať. Robia pseudokódu. Majú viac videí a snímok vrátane tých, ktoré používam tu. Takže ak ste stále pocit, trochu rozmazaný, skúste to von. Ako vždy, poď so mnou hovoriť, taky. Otázka? 

STUDENT: Chceš povedať, že Veľkosť je definované vyššie? Inštruktor: Áno. Veľkosť je definované vyššie up tu v deklarácii funkcie. Takže možno predpokladať, že to bolo odovzdané do užívateľom, a pre jednoduchosť, budeme predpokladať, že Užívateľ nám správnu veľkosť. V pohode. Tak to je výber sort. Chlapi, viem, že učíme dnes veľa. Je to hustý dát pre sekciu. Takže s tým budeme ísť na vloženie druhu. 

OK. Takže ako to, čo musíme urobiť naše runtime analýza tu. Takže v najlepšom prípade, udelená, pretože som vám ukázal tabuľka Už som druh dal preč. Ale najlepšom prípade runtime, čo si myslíme, že? Všetko radené. N druhú. Každý, kto má vysvetlenie prečo si myslíte, že? 

STUDENT: Ste nákupný through-- Inštruktor: Správne. Ste nákupný prejsť. V každej iterácii, aj keď sme dekrementování to po druhom, ste stále prehľadávať všetko nájsť najmenší jeden. Takže aj keď vaše najmenšie hodnota je tu na začiatku, ste stále porovnávanie proti všiam aby sa ubezpečil, že je to najmenšie vec. Takže skončíte prechádzajúcej približne n na druhú krát. Dobrá. A čo je najhoršie? Tiež n na druhú, pretože budete bude robiť, že rovnaký postup. Takže v tomto prípade výber druh má niečo že sme tiež volať očakávané runtime. Takže ostatní, sme len viem, horná a dolná hranica. V závislosti na tom, ako blázon naše Zoznam je netriedený alebo ako to je, sa líši medzi n alebo n na druhú. Nevieme. 

Ale pretože výber druh má rovnaké najhorší a najlepší prípad, že nám hovorí, že bez ohľadu na to, aký typ vstupu sme majú, či už je to úplne radené alebo úplne reverznej radené, je to bude trvať rovnakú dobu. Takže v tomto prípade, ak vás pamätať z nášho stola, v skutočnosti mala hodnotu, ktorá Tieto dva druhy nemajú, čo je predpokladaná doba zálohovania. Takže vieme, že vždy, keď narazíme výber druhu, je zaručené, aby spustiť n na druhú dobu. Nie je tam žiadna variabilita. Je to od nich očakáva. A opäť, ak sa chcete dozvedieť, viac, vziať CS 124 na jar. Dobrá. Videli sme toto. V pohode. Takže vloženie sort. A ja asi bude na požiar cez to. Nebudem mať vy to kód. Budeme sa len prechádzať cez to. Takže vloženie druh je druh o podobný výbere druhu v tom, že máme obaja netriedené a zoradená časť poľa. 

Ale to, čo je, je, že ako sme sa prejsť jeden po druhom, sme jednoducho vziať bez ohľadu na počet je ďalší v našom netriedený, a správne triediť do nášho triedeného poľa. Bude to väčší zmysel na príklade. Takže všetko, čo začína ako netriedený, Rovnako ako pri výbere druhu. A budeme triediť na túto vzostupne, ako sme boli. Takže na našom prvom prechode Vezmeme prvú hodnotu a hovoríme, OK, ste teraz v zozname sami. 

Pretože ste v zozname sami, ste radené. Gratulujeme k bytiu prvý prvok v tomto poli. Ste už je zoradený všetko na vlastnú päsť. Takže teraz sme radené a netriedené poľa. Takže teraz sme sa prvýkrát. Čo sa stane medzi tu a tu je to, že hovoríme, OK, ideme sa pozrieť na Prvá hodnota našej netriedený pole a budeme vstup je vo svojom správne miesto v triedenom poli. 

Takže to, čo robíme, je berieme 5 a hovoríme, OK, 5 je vyššia ako 3, takže stačí vložiť ju priamo na pravej strane, že. Sme dobre. Takže ideme na naše ďalšie. A vezmeme 2. My hovoríme, OK, 2 menšie ako 3, takže vieme, že to musí byť v Predná časť nášho zoznamu teraz. Takže to, čo robíme, je, že sme tlačiť 3 a 5 sa a prejdeme 2 do toho prvého slotu. Takže sme jednoducho vložením do správne miesto, to by malo byť. 

Potom sa pozrieme na naše budúci, a hovoríme 6. OK, 6 je väčšia než všetko v našom triedenom poli, tak sme jednoducho označiť ju až do konca. A potom sa pozrieme na 4. 4 je menšie ako 6, je to menej ako 5, ale je to menej ako 3. Tak sme jednoducho vložte ju priamo do uprostred medzi 3 a 5. Tak, aby sa to trochu trochu konkrétnejší, Tu je druh predstava o tom, čo sa stalo. Takže pre každý prvok netriedeného, ​​sme určiť, kde v triedenom časti to je. 

Tak, aby sa nezabúdalo na triedené a netriedené, musíme prejsť skrz a obr , Kde sa zmestí do triedeného poľa. A my ho vložiť posunutím prvky vpravo dole. A potom sme jednoducho udržať iterácie, až kým majú úplne zoradený zoznam kde netriedené je teraz nulová a triedený zaberá celistvosť nášho zoznamu. Takže, ešte raz, aby sa veci ešte konkrétnejšie, máme pseudokódu. 

Takže v podstate pre i je presne 0 do n mínus 1, to je len dĺžka nášho poľa. Máme nejaký prvok, ktorý sa rovná Prvé pole alebo prvý indexy. Nastavili sme j, ktorá sa rovná. Takže zatiaľ čo j je väčšia než nula a polia, j mínus 1 je väčšia než prvok, takže všetko, čo robí je zabezpečiť, aby Váš j Vás naozaj zastupuje netriedeného časť poľa. 

Takže zatiaľ čo tam je ešte veci triediť a j mínus jedna je-- čo je jej súčasťou? J tu nebola definovaná. Je to trochu nepríjemné. OK. Tak ako tak. Tak j mínus 1, máte kontrolu prvok pred ním. Hovoríte, že, OK, je element predtým, než tam, kde som am-- poďme skutočne čerpať na to. Takže povedzme, že je to ako na našom druhom prechode. Takže aj sa bude rovnať 1, ktorý je tu. 

Takže aj bude rovný 1. To by bolo 2, 4, 5, 6, 7. Dobrá. Takže naše prvkom v tomto prípade bude rovná 4. A máme nejaké j, ktorý je bude rovný 1. Oh, j je dekrementování. To je to, čo to je. Tak j je rovný aj tak, čo to je Hovorí sa, že, ako sme vpred, sme len uistiť že nie sme cez indexovanie týmto spôsobom, keď sa snažíme vložiť veci do nášho zoznamu zoradené. 

Takže keď j je rovný 1, v tomto prípade, a array j mínus one-- tak array j mínus 1 je 2 v tomto case--, ak je to väčšie ako prvok, potom to všetko robí sa presúva veci dolu. Takže v tomto prípade, pole j mínus jedna by poľa nulová, čo je 2. 2 nie je väčší ako 4, tak to nevykoná. Takže posun nepohybuje nadol. Čo to však je tu len pohybom zoradené polia dole. V tomto prípade, v skutočnosti, sme by do-- urobme túto tri. Takže ak sme sa prejsť s tento príklad, my sme teraz tu. To je zoradený. To je netriedený. V pohode? Takže aj je rovná 2, takže náš prvok je rovné 3. A naša j je rovný 2. Tak sme sa pozrieť a my hovoria, OK, je pole j mínus jedna väčšie ako prvok že sa pozeráme? A odpoveď je áno, je to tak? 4 je väčší ako 3, a j je 2, takže tento kód spustí. 

Takže teraz to, čo robíme poľa na 2, tak tu sme sa ich vymeniť. Tak sme sa len povedať, OK, polia na 2 sa teraz bude 3. A j bude rovnať j mínus 1, čo je 1. To je hrozné, ale vy dostanete nápad. J je teraz rovný 1. A pole j sa len bude rovná našej prvku, ktorý bol 4. Aj vymazať niečo, čo som nemal majú alebo miswrote niečo, ale vy dostanete nápad. 

To sa pohybujú n. A potom, ak to tak bolo, bolo by to slučka znova, a to by som povedal, OK, j je 1 teraz. A pole j mínus 1 je teraz 2. Je 2 menšie než naše prvok? Nie? To znamená, že máme vkladá tento prvok v správnom mieste v našom triedeného poli. Potom sa môžeme vziať a hovoríme, OK, naša zoradené poľa je tu. A to by sa toto číslo 6 a musí byť ako, OK, 6 menšie ako toto číslo? Nie? V pohode. Sme v poriadku. 

Urob to znova. Hovoríme 7. Je menšia ako 7 do konca našej triedeného poľa? Nie. Takže sme v pohode. Takže by to byť triedené. V podstate to všetko robí Je to hovorí vziať Prvý prvok Váš netriedené polia, zistiť, kde to ide v triedenom poli. A to len stará swapov k tomu, že. Vy ste v podstate len vymení kým je to na správnom mieste. Vizuálnej image je to, že ste pohybujúce sa všetko sa tým, že. 

Takže je to ako polovica bublina trochu v štýle. Pozrite sa na štúdii 50. Vrelo odporúčam sa snaží kódovať na vlastnú päsť. Ak máte nejaké otázky, alebo ak chcete pozri ukážkový kód pre vloženie druhu, dajte mi prosím vedieť. Vždy som sa okolo seba. Takže v najhoršom prípade runtime a najlepšom prípade runtime. Ako ste chlap videl z tabuľky už som vám ukázal, že to tak n na druhú a n. 

Tak láskavý a šiel preč z toho, čo sme sa rozprávali o s našimi predchádzajúcimi druhmi, najhoršie prípad runtime je, že ak je to úplne netriedeného musíme porovnať všetky tieto n-krát. Robíme veľa porovnanie pretože ak je to v opačnom poradí, budeme hovoriť, OK, to je rovnaký, to je dobré, a ten bude musieť byť v porovnaní proti prvej sa presunúť späť. A ako sa dostaneme k koniec chvosta, máme porovnávať, porovnávať a porovnať proti všetkému. 

Takže to nakoniec bola n približne štvorcový. Ak je to v poriadku, tak si hovoria, OK, 2, si dobrý. 3, ste v porovnaní s 2. Si dobrá. 4, stačí porovnať na chvoste. Si dobrá. 6, v porovnaní s chvostom, že si v poriadku. Takže pre každé miesto, ak je už radené, robíš jednu porovnanie. Takže je to len n. A pretože máme najlepšiu prípadovú runtime n a najhoršom prípade behu n štvorcový, nemáme očakávaný runtime. 

Záleží len na chaos nášho zoznamu tu. A opäť ďalší graf a ďalšie tabuľky. Takže rozdiely medzi druhmi. Ja som jednoducho ísť vánok cez, I pocit, že sme hovorili značne o tom, ako všetky druhy o líšiť a prepojiť. Takže Merge sort je posledná Aj sa niesol vám chalani s. Máme dosť farebný obraz. Takže zlúčiť druh je rekurzívny algoritmus. Tak si chlapci vedia, čo rekurzívne funkcie? 

Každý, kto chcel povedať? Ak chcete to skúsiť? Tak rekurzívne funkcie je len funkcia, ktorá volá sama seba. Takže ak vy ste oboznámení s Fibonacci sekvencie, ktorá je považovaná za rekurzívny, pretože budete mať predchádzajúce dva a pridajte ich spolu dostať svoje ďalšie. Tak rekurzívne, Vždy si myslím, rekurzia ako ako špirála takže ste ako po špirále dole do neho. Ale je to len funkcia ktorá volá sama seba. 

A v skutočnosti, veľmi rýchlo som môže ukázať, ako to vyzerá. Tak tu rekurzívny, ak sa pozrieme, je to rekurzívny spôsob, ako zhrnúť cez pole. Takže všetko, čo robíme, je máme funkciu sum čiastka, ktorá má veľkosť a polia. A ak si všimnete, veľkosť úbytky podľa jedného zakaždým. A to všetko robí, je, ak x je rovné zero-- takže ak veľkosť poľa je rovný zero-- vráti nulu. 

Inak to zhŕňa tento posledný prvok poľa, a potom vezme súčet zvyšok poľa. Takže je to len rozobrať to do menších a menších problémov. Dlhý príbeh krátky, rekurzia, funkcia, ktorá volá sama seba. Ak je to všetko, čo máš z toho, že to, čo rekurzívne funkcie. Ak budete mať 51, dostanete veľmi, veľmi pohodlné s rekurzia. Je to naozaj cool. Dávalo to zmysel, ako 3 AM jednu noc. A bol som rád, prečo Nikdy som použiť? 

Takže pre zlúčenie druhu, v podstate čo to bude robiť, je, že je to chystá vyraziť a zlomiť to nadol, kým je to len jednotlivé prvky. Jednotlivé prvky sú ľahko vyriešiť. Vidíme, že. Ak máte jeden prvok, je to už považovaný za triedený. A tak na vstupe n prvkov, ak n je menšie ako 2, len vrátiť pretože to znamená to je buď 0 alebo 1, ako sme videli. Tie sú považované za triedené prvky. 

Inak rozbiť na polovicu. Zoradiť prvú polovicu, triediť druhý polovice, a potom spojiť ich dohromady. Prečo sa to volá merge sort. Takže máme tu budeme triediť tieto. Tak sme sa držať s nimi kým sa veľkosť poľa je 1. Takže keď je to 1, práve sme sa vrátiť pretože sa jedná o zotriedené pole, a to je triedeného poľa, a to je zotriedené pole, sme všetci radené. Takže to, čo robíme, je, že sme začať zlúčenie dohromady. 

Takže spôsob, ako môžete premýšľať o zlučovaní je stačí odstrániť menšie Počet každej z čiastkových polí a len pripojiť ho k objavili poľa. Takže, keď sa pozriete tu, keď máme Tieto sady máme 4, 6, a 1. Keď chceme zlúčiť tieto, Pozrieme sa na týchto prvých dvoch a hovoríme, OK, 1 menšia, to ide dopredu. 4 a 6, nie je nič k porovnaniu to, stačí označiť ju až do konca. 

Keď sme sa spojiť tieto dve, práve sme mať menšie jeden z týchto dvoch, takže je to jedno. A teraz sme sa menšia z týchto dvoch, SO 2. Menšia z týchto dvoch, 3. Menšia z týchto dvoch, 4, 5, 6. Takže ste práve vyzliekol tie. A pretože som boli radené skôr, stačí jedno Porovnanie zakaždým, keď. Takže viac kódu, proste reprezentácie. Takže začnete v stredu a triediť vľavo a vpravo a potom stačí spojiť tie. 

A my nemáme kód pre zlúčenie tady. Ale opäť, keď idete na štúdium 50, bude to tam. V opačnom prípade príde so mnou hovoriť ak ste stále zmätená. Tak super vec je, že najlepší prípad, v najhoršom prípade, a očakáva, že runtime sú v protokole n, ktoré je oveľa lepší, než sme vidieť po zvyšok našich druhov. Videli sme n na druhú a to, čo sme vlastne sem je n log n, čo je skvelé. 

Pozrite sa, ako ďaleko lepšie to je. Taká pekná krivka. Tak oveľa efektívnejšie. Ak ste niekedy možné, použite zlúčiť druh. To vám ušetrí čas. Potom znova, ako sme povedali, ak je ste v tejto nižšej regióne, to neznamená, že to veľký rozdiel. Získate až tisíce a tisíce vstupov, budete určite chcieť efektívnejší algoritmus. A opäť, naša milá tabuľka všetkých druhy, ktoré chlapci sa dnes dozvedel. 

Takže viem, že to bol hustý deň. To nemusí nutne ísť ktoré vám pomôžu s vašou pset. Ale len chcem, aby disclaimer že oddiel nie je len o psets. To všetko materiál je fér Hra pre vaše midterms. A tiež ak si pokračovať s CS, Toto sú naozaj dôležité základy ktoré budete potrebovať vedieť. Takže pár dní bude trochu pset pomoc, ale niekoľko týždňov bude oveľa skutočný obsah že sa môže zdať Super užitočné pre vás práve teraz, ale sľubujem, že ak budete pokračovať na bude veľmi, veľmi užitočné. 

Tak to je pre sekciu. Dole drôtu. Urobil som to počas jednej minúty. Ale tam idete. A ja budem mať šišky alebo cukríky. Je niekto alergický na niečo, mimochodom? Vajec a mlieka. Takže šišky sú nie? OK. Dobrá. Čokoláda nie? Starburst. Starburst sú dobré. OK. Budeme mať Starburst budúci týždeň potom. To je to, čo budem mať. Vy máte skvelý týždeň. Čítať vaše špec. 

Dajte mi vedieť, ak máte akékoľvek otázky. Pset dva stupne by mala byť k tebe do štvrtka. Ak máte nejaké otázky o tom, ako som sa triedi niečo alebo prečo som sa triedi niečo tak, ako som sa, prosím, napíšte mi, poď so mnou hovoriť. Som trochu blázon to týždeň, ale sľubujem, Budem ešte odpovedať do 24 hodín. Takže majú veľký týždeň, všetci. Veľa šťastia na vašej pset.