SPEAKER 1: Ahoj všichni! Vítejte zpět na části. Tak rád, že se tak mnoho z vás i zde, a každý, kdo se dívá online. Takže jako obvykle vítejte zpátky. Doufám, že jste všichni měli krásné víkend plný odpočinku, relaxace. To včera byla krásná ven. Takže doufám, že se vám to líbilo venku. 

Takže nejprve pár oznámení. Třídění. Takže většina z vás by měl dostat napište mi o vašem Scratch pset, jakož i třídění pro pset 1. Takže, jen pár věcí. Ujistěte se, že používáte check50 v style50. Ty mají být prostředky pro vás, aby se ujistil, že jste stále co nejvíce bodů, jak můžete aniž by zbytečně jejich ztráty. Takže věci, jako je styl jsou velmi důležité. Chystáme se sundat za to. Někteří z vás možná již si všiml, že z vašeho pset. A check50 je jen Opravdu snadný způsob, aby se ujistil, že jsme vlastně vrací to, co musí být se vrátil k uživateli, a že vše funguje správně. 

Na druhou poznámku, ujistěte se, že nahrát věci do správné složky. To je můj život jen trochu složitější pokud nahrajete pset 2 do pset 1 protože když jsem stáhnout něco, nemají stahovat správně. A já vím, že je to trochu blbě v systému zvyknout, ale jen být super pozor, i když jen pro mě, tak, že když jste se dostal e-maily v jako 2 A.M. a já jsem třídění. Pokud ne, protože jsem se podívat všude kolem pro pset. V pohodě. 

Já vím, že je to brzy, ale já úplně dostal vzlétlo stráž eseje, která je v důsledku této pátek, že moji profesoři byli jen rádi, oh yeah. Pamatujte si, že máte esej kvůli v pátek. Takže vím, že nikdo rád přemýšlet o tom, midterms, ale váš první kvíz je 15. října, který října se začíná tento týden. Tak, to by mohlo být dříve než jste očekávali, je vše. Tak, že nejste házet nepřipraveného když Zmiňuji se o část příští týden, že oh, Váš test příští týden, myslel jsem, Já bych vám trochu více z hlav se nyní. 

Takže nastavit váš problém, číslo tři. Jak lidé číst spec ze zvědavosti? OK. Máme pár. Druh dolů z posledního týdně, ale to je v pořádku. Vím, že to bylo krásné ven. Tak Break Out. Rozhodně po stihnout dnes číst spec alespoň zkuste jako stažení Distribuce kód a provoz jako první počáteční věc, která vás žádají, abyste. Protože jsme pomocí distribuce kód a knihovny že jsme teprve using-- --It jen Podruhé jsme udělali tuto pset, bláznivé věci se může stát s přístrojem, a chcete zjistit, že venku proti později. 

Vzhledem k tomu, jestli je to ve čtvrtek v noci, nebo je to Ve středu v noci a z nějakého důvodu Váš spotřebič prostě není chcete spustit s knihovnou nebo distribuce kód, to znamená nemůžete ani začít dělat kódování. Protože není možné kontrolovat aby zjistil, jestli to funguje. Váš nebudu moci aby zjistil, jestli to překládá. Chcete se postarat o ty, které na začátku roku týden, kdy můžete mi ještě e-mail nebo jeden z dalších TFS a můžeme dostat ty, které stanoví. Vzhledem k tomu, to jsou otázky, které tě zastavit v tom, aby žádný skutečný pokrok. Není to jako jednu chybu, že můžete jen tak přeskočit. Pokud máte problémy se svým zařízení nebo distribuce kód, Opravdu chcete, aby si to vzít péče o spíše dříve než později. Takže i když jste nebudeš ve skutečnosti začít psát kód, stáhněte si distribuci kód, přečtěte si spec, ujistěte se, všechno, co se tam pracuje. OK? Pokud se vám prostě to, že jsem Slibuji svůj život bude jednodušší. A tak budete pravděpodobně to udělat teď hned? OK. Takže tam nějaké otázky? Veškeré logistické věci? Každý, kdo je dobrý? OK. 

Disclaimer pro ty, Jste v místnosti a on-line. Budu se snažit přepínat mezi PowerPoint v zařízení Protože se chystáme bude dělat nějaké kódování dnes populární poptávky anonymní návrh hlasování jsem poslal minulý týden. Takže budeme dělat nějaké kódování. Takže pokud vy také chtít střílet vaše zařízení, a měli jste dostali e-mail ode mne, s ukázkový soubor. Prosím, neváhejte to udělat. 

Takže, budeme mluvit o GDB, který je debugger. Bude to, aby vám pomohl druh zjistit, kde věci jdou špatně v kódu. Je to opravdu jen způsob, jak krok prostřednictvím kódu, jak je to se děje, a musí být schopen vytisknout proměnné nebo zjistit, co se vlastně děje Pod kapotou verše program právě běží, je to jako chybující, a ty jsi jako, žádný nápad co se tu právě stalo. Já nevím, co řádek to propadlo na. Nevím, kde se stala chyba. Takže, GDB bude, aby vám pomohl s tím. Také, pokud se rozhodnete pokračovat ano, a vzít 61, to bude opravdu, ale opravdu být vaše nejlepší přítel, protože jsem vám říct, proto, že jsem procházel této třídy. 

Jedeme se podívat na binární Hledání, které, pokud vy pamatovat velký telefonní seznam příkladů Podívaná ze třídy. Budeme se provádí to, a procházce, že trochu víc, a pak jedeme přes čtyři různé druhy, které jsou Bubble, Výběr, vkládání, a sloučit. V pohodě. Takže, GDB, jak jsem již zmínil, je debugger. A ty jsou trochu velký věci, velké funkce nebo příkazy které používáte v GDB, a já budu chodit si přes demo se převede do druhé. 

Takže, to není jen Zůstaneš abstraktní. Pokusím se, aby to jako beton jak je to možné pro vás. Takže, zlomit. To bude přestávka buď jako, nějaké číslo, které představuje řádek v programu, nebo můžete pojmenovat funkci. Takže, pokud řekneš rozbít hlavní, se zastaví na hlavní, a umožní vám projít tuto funkci. 

Stejně tak, pokud máte nějaké externí fungují jako Swap nebo kostka, že jsme se podívali na minulý týden. Pokud řeknete rozbít jeden z těch, když váš program zasáhne to, to na tebe čekat na říká, co má dělat. Než to bude jen spustit, takže vám by se skutečně krok uvnitř funkce a uvidíte, co se děje. Takže další, prostě přeskočí další řádek, přejde funkce. Krok. To vše jsou trochu abstraktní. Tak jsem jen tak běžet přes ně, ale vy je uvidíte v použití v druhé. 

Vstupte do funkce. Takže jak jsem říkal, jako u Swap, by to umožňují skutečně, jako kdyby jste jako fyzicky krokování uvnitř, můžete si s těmito proměnnými, tisk to, co oni jsou, co se děje. Seznam bude doslova jen vytisknout z okolního kódu. Takže, pokud jste trochu zapomenout kde jste ve vašem programu, nebo jste zvědaví, co se děje kolem něj, to bude jen vytisknout segmentu podobných pět nebo šest řádků kolem něj. Takže můžete lépe zorientovat o tom, kde se právě nacházíte. 

Vytisknout nějaké proměnné. Takže, pokud máte klíč jako v Caesar, že se podíváme na. Můžete říct, že PRINT na každém místě. To vám řeknu, co je hodnota, takže že možná někde na cestě, k přepisu klíč. Můžete si skutečně říct, že proto, že můžete skutečně sledovat tuto hodnotu. 

V místních obyvatel, jen tisky z vašich lokálních proměnných. Takže, kdykoliv jste ve smyčce, a vy prostě chcete vidět podobné, oh. Jaká je moje já? Jaká je tato hodnota klíče že jsem inicializovat tady? Co je zpráva v tomto bodě? To bude jen vytisknout vše z těch, takže vás Nemusíte se jednotlivě říci, tisk I. Print Message. Print Key. A poté displej. Co to dělá, je jako vy krok v rámci programu, to bude jen ujistit, že je to zobrazovat jen některé proměnné v každém bodě. Aby jste also-- --it to druh zástupce kde nemusíte jít dál, jako, oh. Print Key nebo Tisk I. Prostě automaticky to pro vás. 

Takže, s tím, že budeme vidět, jak to jde. Budu se snažit a spínače k mému přístroji. Uvidíme, jestli to zvládnu. All. Jsme jen bude zrcadlit. Není nic, co blázen na mém notebooku kdekoli. OK. To musí být tato. Je to tak malé. Uvidíme, jestli to můžeme udělat. 

OK. Alice se samozřejmě snaží zde jen trochu, ale my si to v Momento. OK. Jsme jen poroste to. OK. Může každý druh vidět, že? Možná trochu? Já vím, je to trochu malý. Nemůžete docela přijít na to, jak se dělá to větší. Pokud někdo zná. Ví někdo, jak na to větší? OK. Chystáme se vrátit s ním. Nezáleží na tom tak jako tak, protože je to jen To je kód, který vy by mají. 

Co je důležitější, je terminál zde. A máme tady Proč je to tak malý? Nastavení. Oh. Pravda Ike. Jak je to? Odtamtud. Je to lepší pro všechny? OK ,. V pohodě. 

Víte, kdy jste v CS třídy technické problémy jsou trochu součástí the-- Takže, pojďme vyčistit to. OK. Takže, tady v sekci které jsme tu měli. Caesar je spustitelný soubor. Tak jsem udělal to. Takže jedna věc je si uvědomit, s GDB je že to funguje jen na spustitelné soubory. Takže nemůžete spustit na dotsy. Musíte vlastně dělat Ujistěte se, že váš kód zkompiluje, a že to může být ve skutečnosti spustit. 

Takže, ujistěte se, že pokud se tak nestane sestavit si to zkompilovat, takže můžete trochu projet. Tak pro začátek GDB, vše, co udělat, Typ Gloria GDB, a pak už jen soubor, který chcete. Vždycky jsem chybně Caesara. Ale vy chcete ujistit, protože je to spustitelný, TI dot blesk tak, aby znamená, že jdeš spustit CSI budete provádět to soubory buď v debuggeru. OK. Takže, to, že se dostanete tento druh blábol. Je to jen všechno o debuggeru. Ty opravdu nemají na starat o to právě teď. A jak vidíte, máme to otevřené parens, HDP, v blízkosti parens, a jen tak vypadá naše příkazového řádku, je to tak? 

Takže, co chceme do-- -SO, První věc, je chceme vybrat místo, kde je zlomit. Takže, tam je jedna chyba v tomto programu Caesar že jsem se představit, že jdeme zjistit. To, co to je, že se vstup Barfoo ve všech čepice, a z nějakého důvodu nemění A. Je to prostě odejde je sám, je všechno ostatní v pořádku, ale druhý dopis Zůstává beze změny. Takže, budeme se snažit a přijít na to, proč tomu tak je. Takže první věc, kterou obvykle chci dělat při každém spuštění na GDB je přijít na to, kde ji zlomit. 

Takže Caesar je docela krátký program. Máme jen jednu funkci, ne? Jaké bylo naše funkce v Caesar? Je tu jen jedna funkce, hlavní je to tak? Hlavní je funkce pro všechny programy. Pokud jste neměli Main, mohl bych je hned trochu strach teď, ale doufám, že jste všichni měli Main tam. Takže, co můžeme udělat, je, můžeme prostě rozbít Main, stejně jako to. Tak, to říká, OK. Tam My jsme nastavili zarážky jeden. 

Tak, teď věc k zapamatování je Caesar trvá jeden argument příkazového řádku právo a my jsme to ještě neudělali kdekoliv. Takže, co děláte, je-li jste vlastně jít spustit program, program, který jste běží v GDB, který potřebuje příkazový řádek argumenty, budete k zadání při prvním spuštění běží to. Takže v tomto případě, my Běh s klíčem tři. A to se skutečně začít. 

Takže, pokud zde vidíte, máme Je-li RC se nerovná 2. Takže pokud vy všichni mají že soubor, který jsem poslal nahoru uvidíte, že to je jako První řádek naše hlavní funkce, ne? Je to kontroluje, zda je k dispozici správný počet argumentů. Takže, pokud jste přemýšlel, RC-li správné, můžete dělat něco jen jako Print RC. RC je dvě, což je to, co jsme očekávali, že jo? 

Takže můžeme jít dál, a pokračovat přes. Takže, máme tam nějaký klíč. A můžeme vytisknout náš klíč aby se ujistil, že je to správné. Zajímavé. Ne tak docela, co jsme očekávali. Takže jedna věc je si uvědomit, s GDB také, je že to není, dokud se skutečně hit Dále, že řádek, který jste právě viděli je ve skutečnosti proveden. Takže v tomto případě klíčem nebylo přiděleno dosud. Takže klíč je nějaký odpad hodnota které vidíte na tam dole. Negativní --It je jeden miliard dolarů 120-- a něco divného věci do pořádku? Není to klíč, který jsme očekávali. Ale když jsme narazili na Další a pak jsme pokusit Print klíč, je to tři. 

Všichni vidí, že? Takže, pokud máte něco že jste jako, počkejte. To je zcela špatně, a já nevím, jak by se to stalo, protože všechno, co chci udělat, je přiřadit číslo, proměnná, zkuste bít Další, zkuste tisknout znovu, a uvidíme, jestli to funguje. Vzhledem k tomu, že to jen bude provádět a vlastně přiřadit něco po vás Další hit. Smysl pro každého? Hm? 

SPEAKER 2: Při náhodné čísla, co to znamená? 

SPEAKER 1: Je to jen náhodný. Je to jen odpad. Je to prostě něco, že vaše Počítač bude náhodně přiřadí. V pohodě. Tak, teď se můžeme pohybovat, a tak nyní máme tento prostý text getString. Takže, dovolte mi představit, co se stane, když jsme narazili Další zde. Naše GDB druh zmizí, že jo? To proto, že getString Nyní je realizovat, ne? Takže, když jsme viděli, prostý text rovná GetString, otevřené parens a parens, a my hit Další, která má Nyní skutečně popraven. Takže, je to čekání na nám vstup něco. 

Takže jdeme na vstup naše jídlo, které je to, co to nedaří, jak jsem vám řekl, a to jen říká, že je to po spuštění, že zavřeno držák znamená, že je vystupující z této smyčky. Takže můžeme zasáhnout Další a teď, když jsem jistý, že jste všichni obeznámeni od Caesara, je to, co je tato linka bude dělat. Je to pro int i = 0, N se rovná Strlen, prostý text, a pak I je menší než n, I, plus, plus. Co je to smyčka dělat? Otevřete zprávu. V pohodě. Takže, pojďme začít dělat to. 

Takže, pokud by tato podmínka zápas, pro naše první? Pokud je to B, je to prostý text I. jsme můžete získat informace o našich místních obyvatel. Takže, je nula, a je-li šest, které očekáváme, a naším hlavním je tři. Vše, co dává smysl, ne? Tato čísla jsou přesně to, co by mělo být. Takže, hučení? SPEAKER 3: Mám náhodná čísla pro můj. SPEAKER 1: No, můžeme check-- --we můžete chatovat o tom ve vteřině. Ale měli byste být stále to. Takže, pokud máme kapitál B pro naše první, tato podmínka by ho chytit, ne? Takže, když jsme narazili na Next, vidíme, že, pokud skutečně vykonává. Protože pokud jste po spolu v kódu, tento řádek tady, kde prostý text I se nahrazuje tímto aritmetice, provede pouze v případě if Podmínkou je správné v pořádku? 

GDB bude jen ukázat vám, věci, které jsou skutečně provádění. Takže pokud tato podmínka Pokud nebyla splněna, je to jen tak přeskočit na další řádek. OK? Takže, máme to. Tento držák znamená, že je zavřeno z této smyčky teď. Takže, bude to začít znovu. Stejně jako, že. Tak, že se můžeme dostat informace o našich místních obyvatel zde, a vidíme, že naše první dopis změnilo, že? Nyní je E, jak to má být. Ano, můžeme pokračovat dál. 

A máme tuto kontrolu. A pokud tato kontrola by měla fungovat, ne? Je to A. Je třeba změnit tři písmena vpřed. Ale pokud si všimnete, my něco jiného. Takže v tomto případě tady, to chytil to, a tak tato linka vykonán, které upravovalo naši B. Ale v tomto případě je zde, jsme, že to prostě přeskočí ji, a šel na [? L Koná. ?] Takže něco se tam děje. Co, že to říkám, je to, víme, že by měl zachytit tu, ale není tomu tak. Může někdo vidět, co naši Problém je v tomto řádku? Je to velmi minutu věc. A můžete se také podívat na váš kód. Je to také line-- zapomenout na to, co vedení je v there-- ale je to v [neslyšitelné]. Ano? 

SPEAKER 4: Je to na více než strana, pokud ji četl v knize. SPEAKER 1: Přesně tak. Takže, debugger nemohl říct si to, ale debugger Ty by mohly získat až na linii že víte, není funkční. A někdy, když zejména později v semestru, kdy máte co do činění s sto, a sto pár řádků kódu, a vy Nevím, kde se to nedaří, je to skvělý způsob, jak to udělat. Takže jsme našli chybu. Můžete opravit v souboru, a pak je možné jej znovu spustit, a všechno bude perfektně fungovat. A největší věc je to může zdát, OK. Jo. V pohodě. Věděli jste, co hledáte. Takže jste věděl, co má dělat. 

GDB může být super užitečné, protože vám můžete vytisknout všechny tyto věci, které jste ne. Je to mnohem užitečnější než printf. Jak mnozí z vás používají jako prohlášení printf zjistit, kde chyba byla, že jo? Takže, s tím, že ne musí neustále vracet, a jako komentování na Printf nebo okomentování, a zjistit, co měli byste být tisk. To vlastně jen vám umožní krokovat, vytiskněte věci jak jste prochází, takže můžete pozorovat, jak se mění v reálném čase, jak váš program běží. 

A to trvat trochu trochu zvykat. Já bych Velmi doporučuji jen tak z toho trochu frustrovaný s ním právě teď. Máte-li strávit hodinu po Příští týden ale naučit se používat GDB, ušetříte sami tolik času později. A to doslova. řekneme to lidí každý rok, a vzpomínám si, když jsem se třídy, byl jsem rád, že budu v pořádku. Ne. Pset 6 přišla a já jsem byl jako, já jsem chtěl učit jak používat GDB, protože se mi nelíbí vědět, co se tady děje. 

Takže pokud budete mít tak čas použít na menší programy že budete mít pracuje, stejně jako pracovní přes něco jako Visionare, jako je tento. Nebo chcete-li další praxi, jsem si jistý, Nemohl jsem přijít s buggy programy, pro vás ladit, pokud chcete. 

Ale pokud si jen vzít nějaký čas, aby si na to zvyklí, jen hrát si s ním, to bude opravdu sloužit dobře. A je to opravdu jedna z ty věci, které jste právě muset zkusit a dostat své špinavé ruce se předtím, než se opravdu pochopit. Opravdu jen jednou pochopil Musel jsem ladit věci s ním, a je to mnohem příjemnější mít představu o tom, ladění spíše dříve než později. OK. V pohodě. Vím, že je to něco jako rychlokurz v GDB, a já budu určitě pracovat na získání Tyto vypadat větší příště. V pohodě. 

Takže, pokud se vrátíme k naší aplikaci PowerPoint. Je to bude fungovat? AWH. Ano. OK. Takže, pokud jste někdy potřebovat některý z ty zase, tam je seznam. Tak binární vyhledávání, které každý vzpomíná na skvělou podívanou Davida kopírování telefonních seznamů na polovinu. Nemám opravdu dostat telefonní seznamy už, protože stejně jako kde se vám si telefonní seznamy v těchto dnech? Já opravdu nevím. Binární vyhledávání. Pamatuje si někdo, Jak Binární hledání práce? Vůbec někdo? Jo? SPEAKER 5: Víte, kdy se podíváte na nichž polovina to by bylo v, na tom základě, a zbavit druhé poloviny. 

SPEAKER 1 Přesně tak. Takže, binární vyhledávání, je to docela je-- --we chtěl volat to rozděl a panuj. Takže, co budete dělat, je budete vypadat ve středu, a uvidíte, zda to odpovídá to, co hledáte. A pokud tomu tak není, zkuste se zjistit, je, že bude ponechán polopenze nebo pravou polovinu. Takže by to mohlo být, pokud hledáte na něco, co je podle abecedy, vidíš, oh. Má Allison přijít před M? Ano. Takže jdeme na podívejte se na prvním pololetí. 

Nebo by to mohlo být jako s čísly. Cokoliv, co můžete porovnání, to může být tříděny. Můžete použít binární vyhledávání na. Takže, někdo pamatovat graf nebo co to je? Je to asymptotickou složitost. Takže, tento graf jen popisuje, jak dlouho dostanete vyřešit problém, jak zvýšíte počet věcí který používáte. 

Takže máme N, což je lineární čas. Pokud N více než dva, což je o něco lepší, stále roste super rychlý. A pak jsme Přihlášení, který je to, co považujeme za binární vyhledávání. Pokud si všimneme, jak váš problém dostane mnohem a mnohem větší, Čas, který zabere vám to vyřešit není opravdu zvyšuje, že hodně. Je to jako srovnatelné tady na začátku. Jsi jako, OK. Něco tady není opravdu ohledu na to, který z nich používáme, ale dostanete se k milionu, miliarda. Snažíte se najít some-- --you're se snaží najít jehlu v kupce sena. 

Myslím si, že chcete tento problém. Chcete tuto složitost, ne lineární, protože za všechno, co víte, že vaše bude se prohledávat každý jednotlivec jehla, co sena, snaží hledat jehlu. A to není podle mého názoru příliš zábavné. Rychle, že jsem rád. Mám rád efektivní. A jak pracovití studenti vám přináší kluci, víte pracovat chytřeji, ne těžší typ věc, jak se vám může tvořit tyto algoritmy. 

Takže, jdeme na procházku přes jen rychlý příklad. Myslím si, že kluci by měli mít ruku na binární vyhledávání, ale v případě, že někdo je trochu rozmazaný, chcete ho posílit, budeme prostě jít přes příklad. Takže, hledáme-li pole obsahuje sedm. 

Takže první věc, kterou děláme, je hledat ve středu, ne? A také budete se kódování Binary Search pár sekund. Takže, to bude legrace. Tak jsme se podívat do střední malé pole 3. Má 3 se rovná 7? Není. Je to šest. Takže, to je méně než nebo větší než sedm? Méně než. Ano. Dobrá práce kluci. Mám pocit, že bych měl mít sladkosti, protože jsem chtějí vyhodit do dvorů. To je to, co budu dělat příští týden. Bude vás kluci ostré. 

Takže, vyhodíme, že první polovina, je to tak? to bylo méně než. víme, že všechno, na té levé straně bude menší než to, co jsou vlastně hledáme. Takže, není třeba, aby věnovat pozornost. Prostě na to zapomeň. Tak, teď se podíváme na naši pravé straně, a my se ve středu tam, a teď je to devět. Takže, 9 je-- --Everyone? Větší, než to, co jsme hledat, že jo? Takže jdeme hodit pryč vše vpravo. Takhle. Nyní vše, co jste odešel s jedním. Tak jsme se zjistit, je to jedno, co hledáme? to je. Zjistili jsme, co jsme chtěli. Takže jsme hotovi. Bilineární Search. 

A pokud si všimnete, my měl tam sedm vstupů. To nám trvalo jen jako třikrát, ale pokud děláte jako miliardy vy víte, kolik kroků to by trvat, pokud jsme měli čtyři miliardy věci? Jakékoli odhady? Je to 32. 32 kroků, jak najít něco, ve čtyři miliardy prvek pole, protože síly dva. Takže dva je 32, je na čtyři miliardy korun. 

Tak dost šílené, jak jste stále v jako poměrně malém počtu kroků najít něco, co v čtyřmi miliardami prvky. Takže v takovém případě, že jsme bude kód této tak vy můžete opravdu druh vidět, jak to funguje. Dobře, takže vy můžete kódovat. Jdu si kluci nechat mluvit trochu. Poznejte lidi kolem sebe, což je to, co by někdo chtěl z poslední části. 

Takže poznat lidi kolem sebe. Mluvit trochu. A všechno, co chci od vás Kluci právě teď je jen pokusit se vytvořit nástin pseudokódu. OK? Whoa. Jediné, co chci od vás, je, že jste jen tak pro vyplnění této chvíli případu. Tak jsem si stanovili tyto vyšší a dolní meze, které představují začátek a konec našeho pole. A budete skutečně procházet a přijít na to, to, co děláme v rámci tohoto cyklu while. 

Takže pokud můžete přijít out-- mám nápověda there-- jaké jsou případy, že tady máme? Takže pokud chcete zjistit, případy, budeme pseudokódu ty a pak budeme vlastně kód je. A to bude, jsem si, doufejme, že to bude být o něco snazší, než jste očekávali. Vzhledem k tomu, že to není tak moc kód, ve skutečnosti, což je opravdu cool. 

Mm-hm? 

STUDENT: [neslyšitelné]? Instruktor: Ano. Tam bylo něco najít ve středu. 

Žák: Takže můžeme použít. OK. 

Instruktor: Perfect. Tak to je první věc, kterou musíme udělat. Takže najít střed. Skvělé. Takže máte představu o tom, jak bychom mohli skutečně najít střed s kódem? 

STUDENT: Jo. n nad 2? Instruktor: Takže n nad 2. Takže jedna věc k zapamatování je, že Vaše horní a dolní hranice měnit. Neustále škrtit část matice se díváme na. Tak n nad 2 bude fungovat pouze první věc, kterou děláme. Tak přičemž horní a dolní v úvahu, jak bychom mohli dostat, že prostřední prvek? Protože chceme, aby střední mezi horní a dolní, že jo? Mm-hm? 

STUDENT: [neslyšitelné]. 

Instruktor: Takže máme nějaký střed. A to bude horní a dolní nad 2. Úžasné. Tak jdeme. Jeden řádek dolů. Vy jste na vaší cestě. Takže teď, že máme prostřední, co chceme dělat? Jen obecně. Nemusíte to kód. Ano. STUDENT: [neslyšitelné]? Instruktor: Takže je to navíc proto, že jste nalezení průměr mezi dvěma z nich. Takže pokud si myslíte, že z nich jako druh zvýšení v ze stran, přemýšlet o tom, jak se budete blížit střední, chcete takhle. Takže pokud jste byli na obou stranách střední a máme jako 5 a 7. Když je sečteme vám získat 12, rozdělit o 2, 6. 

Někdy je to těžké vysvětlit, proč to funguje, ale pokud budete pracovat přes Příklad někdy, to vám pomůže zjistit, zda by mělo být plus nebo minus. Ano. 

STUDENT: [neslyšitelné] přesně ve středu kdyby měli případ, kdy je tu spousta menších čísel a jako jeden velký počet? 

Instruktor: Takže vše, co potřebujete je uprostřed pole. Takže pokud jste měli spoustu malých čísel a pak jeden opravdu velký počet Na konci, na tom nezáleží. Vše, na čem záleží, je, že oni jsou řazeny, které jste právě Chcete se podívat na středu pole, protože jste stále krájení váš problém na polovinu. V pohodě. Takže teď, že máme prostřední, co budeme dělat dál? 

STUDENT: Porovnejte. Instruktor: porovnat. Takže srovnávat střední až value_wanted. V pohodě. Takže vidíte, tady máme tato hodnota chceme tady. Pamatujte, je to pole. Takže střední odkazuje na indexu. Takže chceme dělat hodnot uprostřed. Nezapomeňte, pokud chcete porovnat, dvoulůžkové rovná. Děláte single rovná jste jen tak ji přeřadit, a pak, samozřejmě, je to Bude na hodnotu, kterou chcete. Takže nedělejte to. 

Takže jdeme zjistit, zda hodnoty na střed je rovna hodnotě chceme. Nezapomeňte na své rovnátka. Dropbox měl jít pryč. Tak co budeme dělat v tomto případě? Pokud je to, co chceme vrátit? Snažíme se říct. 

STUDENT: Tisk off. 

Instruktor: No, my jsme nechcete vytisknout. Tak to je bool tady, a tak jsme chcete vrátit hodnotu true nebo false. Říkáme, je toto číslo [? RRA? ?] Takže pokud je to, jen jsme se vrátit to pravda. Když se mi podaří kouzlo pravda. 

STUDENT: Proč by se tedy vrátíte nula? Instruktor: Takže byste mohli vrátí nulu, pokud jste chtěli. Ale v tomto případě použitelné, protože naše funkce vrací hodnotu typu bool, Musíme se vrátit buď true nebo false. STUDENT: Když jste řka: boolean výrazu, Můžete je rovna false? Stejně jako když jsem chtěl říct, je-li tato podmínka není splněna, jako je horní rovná false. Bude to, pokud jste právě pochopili dát falešný na straně druhé? Instruktor: Jo. Takže ve skutečnosti, pokud jste někdy něco jako je horní nebo je nižší, která vrací true nebo false a je to vlastně špatné styl řekněme rovná rovná pravda nebo rovno rovná false. Chcete-li použít tento výsledek jak sám jako kontrola. Ne to, co jsem chtěl. To je to, co jsem chtěl. Takže v případě, že se ptáte o něčem, jako je uložení této vc. 

Takže pokud máme int main (void) a něco takového. A máte-li je horní nějakého vstupu a jste s dotazem, zda můžete dělat něco takového? Je to tak? STUDENT: Snažil jsem se jak to udělat, [neslyšitelné]. Protože pokud it's-- Instruktor: Správně. Takže vy chcete to, že je falešný, ne? STUDENT: Jo. Instruktor: Takže v tomto případě, Chcete to provést, pokud to není pravda. Takže v pohodě věc, kterou udělat, je to. Takže pamatujte výkřik bod popírá věci? To říká, že [neslyšitelné] znamená ne. Takže pokud se podíváme na právě tato část zde, měli byste říkají, že je vyhodnocen false, jak chcete, aby. Ne falešný je pravda, která znamená, že tento by se spustit. Dává to smysl? STUDENT: Jo. Instruktor: Úžasné. OK. Takže jsme mohli jen vrátit platí v tomto případě. Takže teď máme další dvě případy, v tomto případě. Jaké jsou naše dva další případy? Řekněme to udělat takhle. Takže začněme s jiný pokud hodnoty na střed je menší než hodnota, kterou chceme. Takže naše hodnoty ve středu, je méně než hodnota, kterou hledáme pro. 

Tak který vázaný vás dělat , že chceme aktualizovat? Horní nebo dolní? Horní? Takže, na které straně pole se budeme dívat na? 

STUDENT: nižší. 

Instruktor: My jdeme že se dívá na levé straně. Takže else if málo hodnota je menší. Tak tady vaší střední hodnotou je méně než to, co chceme. A tak chceme, aby se Pravá strana naší nabídku. Takže jdeme na aktualizovat naše dolní mez. Takže budeme přiřadit naše nižší. A co si myslíte, že by měla být nižší? STUDENT: střední hodnota? Instruktor: Takže střední value-- STUDENT: Plus 1. Instruktor: --plus 1. Může mi někdo říct, proč máme to plus 1? 

STUDENT: [? Žádná hodnota?] je roven něj. 

Instruktor: Správně. Protože už víme, že Naše střední hodnota není rovna to a chceme vyloučit ze všech následných vyhledávání. Jestliže jste zapomněl, že plus 1, tato bude líbit smyčky na dobu neurčitou. A budete jen být zachyceny nekonečné smyčky, a pak budete segfault a věci jdou špatně. Takže vždy ujistěte, že nejste včetně hodnoty, které jste právě Podíval se na. Tak jsme se o to postarat se znaménkem plus 1. 

Takže teď máme poslední podmínku který jsem vždy z bezpečnostních důvodů si můžete prohlédnout zde, else if hodnota na prostřední je větší než hodnota chceme. To znamená, že chceme levá polovina. Takže, který z nich se budeme aktualizovat? Horní. A co je tohle bude rovnat? Střední minus 1, protože Samozřejmě, chceme aby se ujistil, že nejsme při pohledu na této střední hodnotě znovu. A pak jsme si to. To je všechno. To je vše, binární vyhledávání. Není to tak špatné, ne? Je to jako 10 řádků kód s mezerou. Tak velmi silný, velmi užitečné, budete být použití v jedné ze svých pozdějších psets. Možná ne tenhle, ale později. Tak se to naučit. Milovat. To vám dobře léčit. Takže má někdo jakékoliv Otázky týkající se binární hledání? Ano. 

STUDENT: Záleží na tom, zda je váš n je sudé nebo liché? 

Instruktor: Ne Protože jsme obsadil ji do středu as int, bude to jen zkrátit jej. Tak to zůstane celé číslo a to bude nakonec roztřídit všechno. Takže nemusíte mít strach o tom. Každý dobrý? Úžasné. V pohodě. Takže, vy jste dostali to. Slideshow. Tak, jak jsme mluvili o, já vím, David zmínil složitost doby chodu. 

Takže v nejlepším případě, je to jen jeden, který nazýváme konstantní čas. Může mi někdo říct, proč by to mohlo být? Jaký typ scénáře by to znamenalo? Mm-hm. 

STUDENT: [neslyšitelné] first-- Instruktor: Takže střední bytí Prvním prvkem, který se dostáváme k, ne? Takže buď pole jedné nebo co jsme hledali jen se stane, že plácnutí DAB ve středu. Tak to je naše nejlepší případ. Se dostanete do skutečné problémy, pravděpodobně ne bude dosáhnout [neslyšitelné], které se často. Co o našem nejhorším případě? Náš nejhorší případ je log n. A že má co do činění s celým pravomoci dvě věci, které jsem hovořil. 

Takže v nejhorším případě by to znamenalo že jsme museli sekat pole dolů dokud nebylo součástí jedné. Takže jsme museli rozsekat ho na polovinu tolikrát, kolikrát, jak jsme jen mohli. To je důvod, proč je to log n, protože stačí držet dělení dvěma. Takže předpoklady, věci, které Potřebuju vědět, jestli jste někdy bude používat binární vyhledávání. Vaše prvky musí být řazeny. Musí být tříděny, protože že je to jediný způsob, jak můžete vědět, jestli jste schopni vyhodit polovinu. 

Pokud jste měli tuto neuspořádané pytel čísel a vy říkáte, OK, jdu zkontrolovat střed číslo a číslo Sháním je méně než to, že jsem prostě jít libovolně vyhodit jednu polovinu. Ty by, ne-li vědět vaše Čísla v tomto druhém pololetí. Váš seznam musí být vyřešeno. Stejně tak to může být pokračuje trochu, ale musíte mít náhodný přístup. Musíte být schopni jen jít do té prostřední prvek. Máte-li procházet něčím nebo to trvá vám další kroky abych se dostal do středního prvku, to se přihlásit n už proto, přidáváte více práce do něj. A to bude trochu větší smysl za dva týdny, ale já jsem tak nějak chtěl začínat, dát Vy představu o tom, co je přijít. Ale to jsou dva důležité předpoklady které budete potřebovat pro binární seznamu. Ujistěte se, že je to třídit. To je ten velký pro vy právě teď. A na to můžeme jít do zbytek našich druhů. Takže čtyři sorts-- bublina, vložení, výběr a korespondence. Jsou to všechno docela fajn. Jestliže vy rozhodnete pro CS 124, Dozvíte se o všech možných druhů. A pokud jste fanoušek xkcd zde Je to opravdu v pohodě komiks o jako velmi neefektivní druhů, které jsem Velmi doporučuji vám jít podívat. Jedním z nich je jako panické druhu, který je rád, oh ne, vrátí náhodné pole. Vypnutí systému. Odejít. Takže geeky humor je vždy dobré. 

Takže má někdo pamatovat druh jako se jen obecnou představu o tom, jak bublina trochu funguje. Pamatuješ? 

STUDENT: Jo. 

Instruktor: Jdi do toho. 

Žák: Takže jdeš skrz pokud je větší, pak vyměnit dva. 

Instruktor: Mm-hm. Přesně tak. Takže stačí iterovat. Můžete zkontrolovat dvě čísla. Jestliže před jeden je větší než je poté, stačí vyměnit je tak, aby v Tímto způsobem všechny vyšších čísel bublina až ke konci seznamu a všechny nižší počty bublina dolů. 

Řekl vám ukázat kluci v pohodě zvukový efekt třídění video? Je to docela v pohodě. Tak jen řekl Robert, algoritmus který jste právě krok v seznamu, vymění sousední hodnoty v případě, že nejste v pořádku. A pak už jen stále opakovat dokud nemáte žádné swapy. Takže to není špatné, ne? Tak jsme si dát rychlý příklad zde. Takže to bude třídit je ve vzestupném pořadí. Takže když jsme se projít první Tentokrát jsme se podívat přes osm a šest očividně nejsou v pořadí, jsme je vyměnit. 

Tak se podívejte na ten příští. Osm a čtyři není v pořádku. Vyměňte je. A pak osm a dvě, vyměňte je. Tak jdeme. Takže po prvním průchodu, víte, že váš největší počet bude po celou cestu na vrcholu, protože je to jen bude neustále větší než všechno ostatní a to jen tak, aby bubliny se celou cestu až tam do konce. Má to smysl pro každého? V pohodě. 

Takže se podíváme na naši druhém průchodu. Šest a čtyři, switch. Šest a dvě, switch. A teď tu máme pár věcí do pořádku. Takže pro každý průchod, které jsme aby po celou dobu našeho seznamu, Víme, že stejně jako, že mnoho čísel na konci bude muset být seřazeny. Takže děláme třetí přihrávku, který je jedním swap. A pak se na náš čtvrtý projít, máme nulové štěrbiny. A tak víme, že naše pole bylo řazeny. 

A to je velký věc bublinkové druhu. Víme, že když jsme mají nulovou swapy, které znamená, že vše, co je zcela pořadí. Je to trochu jak zkontrolovat. Tak jsme se také bude kód bublinu druh, který také není tak špatné. Žádný z nich není tak špatné. Vím, že se může zdát trochu děsivé. Vím, že když jsem se třída, i když jsem učil třídu pro poprvé v loňském roce, Byl jsem rád, jak to mám udělat? To dává smysl v teorii, ale jak to vlastně udělat? Což je důvod, proč i já chci jít prostřednictvím kódu s vámi zde. Takže mám pseudokódu pro vás tentokrát. Takže stačí mít na paměti, jak chystáme se přejít přes. Takže máme nějaké počítadlo, které udržuje naše swapů, protože musíme ujistit, že jsme ověřit, že. A my opakovat celou řadu jak jsme právě udělal s tímto příkladem. Je-li prvek předtím, než je větší než prvek později, kde jsme v, jsme vyměnit je a my zvýšit dotazy counter protože jakmile jsme se vyměnit, Chceme, aby naše counter vědět. Nějaké otázky? Něco se zdá legrační sem. STUDENT: Myslíte si nastavit počítadlo na nulu pokaždé, když jdete přes smyčku? Nezdá se vám jít dál zpět na nulu pokaždé? Instruktor: Ne nutně. Takže co se stane, je, že jsme projít zde. Tak dělat, když, pamatujte, že tato bude provádět jednou bez výjimky. Takže to bude nastavení čítač roven nule, pak to bude iterovat. Jak to projde, to bude aktualizovat počítadlo. Jak se aktualizuje čítač, když se to dělá, když to dosáhne konce pole, pokud náš seznam není tříděny, čítače byly aktualizovány. 

Tak se kontroluje stav a to říká: OK, je čítač větší než nula. Pokud je, udělat to znovu. Chcete-li obnovit tak, že když vás projít, čítač je rovna nule. Pokud půjdete přes tříděných pole, nic se nezmění, tento postup selže, a vrátit seřazený seznam. Má to smysl? STUDENT: Mohlo by se trochu. Instruktor: OK. Pokud existuje jakákoli jiná otázka, která přijde. Ano. 

STUDENT: Co by funkce být pro přečerpání prvky? 

Instruktor: Takže vlastně můžeme napsat že pokud budeme právě teď. V pohodě. Takže v takovém případě, Alison se děje přepnout zpět do přístroje. To bude legrace. A máme pěkný bubble sort, co tady. Tak jsem to již udělal na kole přes pole. Máme swapy, které jsou rovny nule. Takže chceme vyměnit přilehlé prvky, pokud jsou mimo provoz. Takže první věc, kterou musíme to je iterovat naší nabídku. 

Tak jak si myslíte, že bychom mohli iterovat naší nabídku? Máme pro a i = 0. Chceme být i nižší než n mínus 1 mínus k. A já budu vysvětlovat, že ve vteřině. Tak tohle je optimalizace tady, kde Vzpomínám si, jak jsem řekl, po každém průchodu přes pole my vím, že to, co je on-- 

Takže po jednom průchodu jsme vím, že to je řazen. Po dvou průchodech víme, že to vše je seřazen. Po třech průchodech jsme vím, že je třídit. Tak, jak jsem iterace přes pole zde Je to ujistěte se, jít jen prostřednictvím toho, co víme, je netříděný. OK? To je jen optimalizace. Dalo by se napsat naivně jen iterace přes všechno, by to prostě trvat déle. S tímto čtyři smyčky je jen pěkný optimalizace protože víme, že po každé plné iteraci přes pole zde, jako každou celou smyčku tady víme, že jeden z těchto prvků budou rozděleny na konci. 

Tak jsme se nemuseli starat o ty. Má to smysl pro každého? Že v pohodě malý trik? Takže v tomto případě, pokud jsme iterace, víme, že chceme zjistit, zda pole n a n + 1 jsou v pořádku. OK. Tak tady je pseudokódu. Chceme zjistit, zda pole n a n a 1 jsou v pořádku. Takže to, co můžeme mít, že? Bude to mít nějaký podmíněné. Bude-li. 

STUDENT: Je-li pole n je méně než pole n plus 1. Instruktor: Mm-hm. No, menší nebo větší než. STUDENT: Větší než. Pak je chceme vyměnit. Přesně tak. Takže teď jsme se dostali do toho, co je Mechanismus je vyměňovat? Tak jsme šli přes tuto krátkou dobu, typ funkce odkládacího minulý týden. Pamatuje si někdo, jak to funguje? Takže můžeme nejen přiřadit jim, že jo? Vzhledem k tomu, jeden z nich se ztratí. Jestliže jsme řekli, se rovná B a B je rovna A, všechny náhle oba jsou jen rovná B. 

Takže to, co musíme udělat, je, že jsme mají dočasné proměnné, které je bude držet jeden z našich chvíli jsme v procesu vyměňovat. Takže to, co máme, je, že budeme muset nějakou int teplota je rovna to-- můžete přiřadit se podle toho, co potřebujete, stačí ujistěte se, že budete mít přehled o to-- takže v tomto případě budu přiřadit k poli n plus 1. Tak, že to bude držet bez ohledu na hodnota je v tomto druhém bloku že se díváme. 

A potom, co můžeme udělat je, že může jít dopředu a Přeřadit pole n + 1, protože my víme, mají tuto hodnotu uloženou. To je také jeden z velkých things-- nemám, pokud někdo z vás vědět, měl problémy, kde když přepnete dva řádků kódu náhle věci fungují. Objednávka je velmi důležité v CS. Takže se ujistěte, diagram věci, pokud je to možné pokud jde o to, co se skutečně děje. Takže teď budeme přiřazení pole n + 1, protože my víme, mají tuto hodnotu uloženou. 

A můžeme přiřadit, že na poli n, nebo v tomto případě i pole. Příliš mnoho proměnných. OK. Takže teď jsme převelen pole I plus 1 se rovná, co je v poli i. A teď se můžeme vrátit a přiřadit pole jsem se, co? Každý, kdo? 

STUDENT: 10. 

Instruktor: 10. Přesně tak. A ještě jedna poslední věc. Pokud jsme vyměnili hned, Co musíme udělat? Co je jedna věc, , co se děje, aby nám řekli jestli se někdy ukončit tento program? Co nám říká, že mají seřazený seznam? Pokud nebudeme provádět žádné swapy, že jo? Pokud swapů se rovná nulu na konci tohoto. Takže kdykoliv provést výměnu, jako my právě tady udělal, chceme aktualizovat swapy. A vím, že tam byl Otázka dříve o můžete použít nula nebo jedna, místo true nebo false. A to je to, co to dělá tady. Tak to říká, ne-li swapy. Takže pokud swapů je nula, což je-- vždycky dostat mé pravdy a mé falses popletl. Chceme, abychom mohli zhodnotit na hodnotu true, a to není. Takže pokud je to nula, pak je to falešné. Pokud to popírají s [? bang?] se stává pravdou. Takže tento řádek spustí. 

Pravdy a falešné a nul a jedniček si blázen. Jen pokud jste pomalu chodit přes to, že bude mít smysl. Ale to je to, co tento malý bit kódu tady dělá. Takže to zkontroluje, jsme udělali nějaké swapy. Takže pokud je to něco navíc nula, bude to, že je falešný a celá věc je bude znovu spustit. V pohodě? 

Student: Co je přestávka dělat? 

Instruktor: Přestávka jen vypukne vás ze smyčky. Takže v tomto případě by stejně jako ukončení programu a ty by jen mít svůj seřazený seznam. STUDENT: Amazing. Instruktor: Omlouvám se? STUDENT: Protože předtím jsme použité písemné 1 přepsány nulu představit, že v případě, že bude fungovat, nebo ne. 

Instruktor: Jo. Takže se můžete vrátit nula nebo jedna. V tomto případě, protože nejsme ve skutečnosti dělat něco s funkcí, chceme jen to zlomit. Jsme opravdu nestarám o to. Brzda je také dobré, pokud je použita pro propukají ze čtyř smyček nebo podmínek, které Nechcete, aby provádění. Stačí jen ti z nich. Je to trochu nuance věc. Mám pocit, že je tu hodně ruční ondulaci, stejně jako se dozvíte o tom brzy. 

Ale vy se dozvíte o tom brzy. Slibuji. OK. Takže se všichni dostat Bublinkové řazení? Není to tak zlé. Iterovat, výměnné věci pomocí temp variabilní, a všichni tam nastavit? V pohodě. Úžasné. OK. Zpět na PowerPoint. Jakékoliv otázky obecně o nich tak daleko? V pohodě. Mm-hm. 

STUDENT: [neslyšitelné] int main obvykle. Máte mít to za to? 

Instruktor: Tak jsme byli jen hledáte jen na skutečný třídění algoritmu. Pokud jste ji měl v rámci jako většího programu, budete mít int main někde. V závislosti na tom, kde jste použití tohoto algoritmu, by to zjistit, co je vracené to. Ale pro náš případ, my jsme striktně při pohledu na to, jak to dělá ve skutečnosti iterovat pole. Tak jsme se nemusíte starat o to. 

Tak jsme mluvili o nejlepším případě a nejhorších scénářů pro binární vyhledávání. Tak to je také důležité, aby se že pro každý z našich druhů. Takže to, co si myslíte, že je to nejhorší, Případ runtime bublinkové druhu? Vy pamatujete? 

STUDENT: N minus 1. Instruktor: N minus 1. Takže to znamená, že existují n minus 1 srovnání. Takže jedna věc je uvědomit si, že na první iteraci, projdeme, budeme porovnávat Tyto two-- tak to je 1. Tyto dva, tři, čtyři. Takže po jednom průchodu jsme již čtyři srovnání. Když mluvím o běhu a n. N představuje počet porovnání v závislosti na tom, jak mnoho prvků máme. OK? 

Tak jsme se projít, máme čtyři. Až se příště budete vědět, že ne musí se postarat o to. Porovnáme tyto dva, tyto dvě, tyto dva, a když jsme neměli, že optimalizace se čtyřmi smyčky, které jsem napsal, byste se porovnání zde tak jako tak. Takže budete muset projít pole a aby n n srovnání časy, protože pokaždé, když běh přes to třídíme jednu věc. 

A pokaždé, když jsme se projít pole, děláme n srovnání. Takže naše runtime je to ve skutečnosti n na druhou, což je mnohem horší v naší Přihlášení konec, protože to znamená, že pokud jsme měli čtyři miliardy prvky, je to bude nám trvat čtyři miliardy čtvercový místo 32. Takže není nejlepší runtime, ale některé věci, víte, pokud jste v určitý sortiment prvků bublina druh může být v pohodě použít. 

OK. Takže teď to, co je v nejlepším případě runtime? STUDENT: Zero? Nebo 1? 

Instruktor: Takže 1 by být jeden srovnání. Přesně tak. 

STUDENT: N minus 1? 

Instruktor: Tak jo. Tak n minus 1. Kdykoli budete mít představu, jako n minus 1, máme tendenci nech ho a my jsme jen říct, n, protože máte porovnat každý z these-- každého páru. Bylo by tedy n minus 1, které jsme právě řekl je přibližně n. Když máte co do činění s běhu, vše je v sbližuje. Tak dlouho, jak je exponent správné, že jste docela dobrý. 

To je to, jak se s tím vypořádat. Tak, že nejlepším případě je n, který znamená, že seznam je již řazeno, a vše, co udělat, je spustit pomocí a zkontrolujte, zda je to třídit. V pohodě. Dobrá. Takže jak vidíte zde, abychom jen nějaké další grafy. Tak n na druhou. Fun. Mnohem horší než n, jak vidíme, a mnohem, mnohem horší, než log 2n. A pak se můžete také dostat do protokolů protokolu. A budete mít 124, se dostanete do jako log Star, kterého se jako blázen. Takže pokud máte zájem, vyhledávání log hvězda. Je to docela legrace. Takže máme tento skvělý graf. Jen heads up, to nádherný graf mít pro střednědobé, protože jsme dlouho se vás zeptat na tyto tenčí. Takže jen heads up, mít to na vašem v polovině období na svém pěkném tahák zde. Tak jsme se jen podíval na bubliny druhu. V nejhorším případě, n na druhou, nejlepší věc, n. A budeme se podívat na ostatní. 

A jak můžete vidět, pouze ten, který opravdu dělá dobře je merge sort, který budeme mít na to, proč. Takže jsme jít do příští here-- výběr sort. Pamatuje si někdo, jak Výběr sort pracoval? Jít na to. 

STUDENT: V podstatě projít pořadí a vytvořit nový seznam. A stejně jako vy uvedení prvky in, dal je na správném místě v novém seznamu. 

Instruktor: Takže zvuky spíš vkládání druhu. Ale ty jsi opravdu blízko. Jsou velmi podobné. Dokonce jsem si je popletl někdy. Před této sekci byl jsem rád, počkejte. OK. Takže to, co chcete udělat, je výběr třídit, způsob, jak si můžete myslet o něm a způsobu Mohu ujistit, že jsem se pokusit se dostat je popletl, je to prochází a vybere Nejmenší číslo, a to uvádí, že na začátku seznamu. To swapy s tímto prvním místě. Jsou to vlastně máme příklad pro mě. Úžasné. Takže jen způsob, jak myslet na to-- výběru druh, vyberte nejmenší hodnotu. A budeme se spustit pomocí příkladu si myslím, že pomůže, protože Myslím si, že vizuální vždy pomoci. Takže začneme s něčím že je zcela netříděný. Red bude netříděný, zelená bude třídit. To všechno dává smysl ve vteřině. 

Tak jsme se projít a my iterovat od začátku až do konce. A my říkáme, OK, 2 naše nejmenší číslo. Takže budeme mít 2 a jedeme přesunout do přední části naší nabídku protože je to nejmenší číslo máme. Takže to je to, co to dělá. Je to jen tak vyměnit ty dva. Takže teď jsme řazeny část a netříděné část. A co je dobré si uvědomit, o výběru druhu je, že jsme už jen výběr z netříděného části. 

Vytříděný část, kterou prostě nechat na pokoji. Mm-hm? 

STUDENT: Jak to víš, co je nejmenší bez srovnání na každé jiné hodnoty v poli. Instruktor: Dělá porovnat. Rádi přeskočí to. To je jen obecná celkově. Jo. Když jsme psát kód Jsem jisti, že budete více spokojeni. Ale uložit tento první prvek nejmenší. Můžete porovnat a říkají, OK, je to menší? Ano. Nech si to. Zde je to menší? Ne? 

To je vaše nejmenší, přiřadit ji ke svému hodnotu. A budete mnohem šťastnější když jdeme přes kód. Tak jsme se projít, jsme to vyměnit, tak pak se podíváme na tomto netříděného části. Takže jdeme vybrat tři z. Chystáme se dát na na konec naší tříděného části. A my jsme jen tak, aby dělal to, že dělá to, a dělat, že. Tak tohle je náš druh pseudokódu zde. Budeme kód to tady ve vteřině. Ale jen něco chodit přes na vysoké úrovni. Budeš chodit od i = 0 pro n minus 2. To je další optimalizace. Nebojte se příliš mnoho o tom. Tak jak jsi říkal. Jak Jacob říkal, jak my sledovat, co náš minimum je? Jak to víme? Musíme porovnat vše v našem seznamu. 

Takže minimálně rovná i. Je to jen říkám, v tomto případě index našeho minimální hodnotu. Takže to bude iterovat a to jde od j je roven i + 1. Takže už víme, že to je náš první prvek. Nepotřebujeme porovnat ji k sobě. Takže začneme porovnejte ji s další ten, který je důvod, proč je i a 1 až n minus 1, což je konec pole tam. A my, pokud pole v uvedeném j je menší než pole min, pak přeřadit, kde Naše minimální indexy je. 

A v případě, min není rovno I, jak je tam, kam jsme se vrátili sem. Tak, jako když jsme poprvé dělali tenhle. V tomto případě by byl start na nula, bylo by to skončí tím, že dva. Takže by min nerovná i na konci. To nám umožňuje vědět, že musíme je vyměnit. Cítím se jako konkrétní příklad pomůže mnohem víc než to. Takže budu kódu to s vámi právě teď a myslím, že to bude lepší. 

Druhy mají tendenci pracovat tímto způsobem v tom je to často lepší, jen je vidět. Takže to, co chceme udělat, je nejprve chci nejmenší část v její poloze v poli. Přesně to, co Jacob říkal. Musíte uložit, že nějak. Takže budeme začněte zde iterace přes pole. Budeme říkat, že je to naše První z nich jen začít. Takže budeme mít int nejmenší je rovná pole v i. 

Takže jedna věc je si všimnout, každý když se to spustí smyčka, začínáme o krok dál. Když začneme se podíváme na tento jeden. Příště budeme iterovat, začínáme na tomto jednom a přiřazení je náš nejmenší hodnota. Takže je to velmi podobné bubliny druhu kde víme, že po jednom průchodu, Tento poslední prvek je tříděn. Při výběru druhu, že je to právě naopak. 

Při každém průchodu, víme, že První z nich je seřazen. Po druhém průchodu, druhá bude třídit. A jak jsi viděl s příklady prezentací, naše řazeny část prostě pořád roste. Takže nastavením naši nejmenší z na pole i vše to dělá se omezí, co se díváme na to, jak minimalizovat počet srovnávání děláme. Znamená to, že smysl pro každého? Líbí se mi třeba projít, že opět pomaleji nebo jinými slovy? Jsem rád, že. OK. 

Takže jsme skladování hodnota v tomto bodě, ale také chceme uložit index. Takže budeme ukládat pozice nejmenší jeden, který se jen bude i. Takže teď Jacob je spokojen. Máme věci uloženy. A teď se musíme dívat přes netříděného část pole. Takže v tomto případě, že tento Bude nám netříděný. To je i. OK. 

Takže to, co budeme dělat bude pro smyčce. Kdykoli budete potřebovat iterovat přes pole, vaše mysl může jít do pro smyčce. Tak pro některé int k equals--, co si myslíme, že k se bude rovnat začít? To je to, co jsme si stanovili jako naše nejmenší hodnotu a chceme srovnávat. Co chceme srovnávat to? Je to bude to příští, je to tak? Tak jsme se chceme k nutné inicializovat aby i plus 1 na start. 

A my chceme k v tomto případě již velikost uloženy tady, takže stačí použít velikost. Velikost je velikost pole. A my prostě chceme, aby aktualizovat K některým pokaždé. V pohodě. Takže teď musíme najít nejmenší prvek zde. Takže pokud budeme iterovat jsme chci říct, je-li pole na k je nižší než naše nejmenší value-- to je místo, kde jsme vlastně sledování toho, co je nejmenší here-- pak chceme přiřadit co naše nejmenší hodnota je. 

To znamená, že, oh, my jsme iterace zde. Ať už je hodnota zde není naše nejmenší věc. Nechceme ho. Chceme ji přiřadit. Takže pokud jsme ho přerozdělují, co dělat si myslíte, že by mohlo být v tomto kódu tady? Chceme přiřadit Nejmenší a pozice. Takže to, co je nejmenší teď? STUDENT: Array k. Instruktor: Array k. A jaká je pozice teď? Co je na indexy naše nejmenší hodnota? Je to jen k. Takže pole k, k, se shodují se. Takže jsme chtěli přiřadit to. A potom jsme našli naše nejmenší, takže na konci tohoto cyklu for zde jsme našli to, co naše nejmenší je hodnota, takže jsme prostě vyměnit ji. V tomto případě, stejně jako že naše Nejmenší hodnota je tady. Toto je náš nejmenší hodnota. 

Chceme jen, aby ho vyměnit tu, která je co, že funkce odkládací na dně ano, které jsme právě sepsal spolu před pár minutami. Tak by to mělo vypadat povědomě. A pak to bude jen opakovat až dokud nedosáhne celou cestu až do konce, což znamená, že mají nulovou prvky, které nejsou roztříděné a vše, co bylo řazeny. Smysl? Trochu konkrétněji? Kód pomoci? 

STUDENT: Pro velikosti, nikdy Opravdu jej definovat nebo změnit, jak to víš? 

Instruktor: Takže jedna věc je Všimněte si, tady je velikost int. Takže říkáme v tomto sort-- druhu je funkce v tomto case-- je to výběr třídit, je předáván v s funkcí. Takže pokud to nebyl přijat ve byste něco jako s délkou pole nebo byste iterovat najít délku. Ale protože je předáván v, můžeme jen použít. Jste jen předpokládat, že uživatel vám dal platnou velikost, která vlastně představuje Velikost vašeho pole. V pohodě? 

Jestliže vy máte nějaké problémy s těmito nebo chcete více praxe kódování druhů na vlastní pěst, měli byste přejít na study.cs50. Je to nástroj. Mají checker, který můžete skutečně psát. Dělají pseudokódu. Mají více videí a snímků včetně těch, které používám zde. Takže pokud jste stále pocit, trochu rozmazaný, zkuste to ven. Jako vždy, pojď se mnou mluvit, taky. Otázka? 

STUDENT: Chceš říct, že Velikost je definováno výše? Instruktor: Ano. Velikost je definováno výše up tady v deklaraci funkce. Takže lze předpokládat, že to bylo předáno do uživatelem, a pro jednoduchost, budeme předpokládat, že Uživatel nám správnou velikost. V pohodě. Tak to je výběr sort. Chlapi, vím, že učíme dnes hodně. Je to hustý dat pro sekci. Takže s tím budeme jít na vložení druhu. 

OK. Takže než to, co musíme udělat naše runtime analýza zde. Takže v nejlepším případě, udělena, protože jsem vám ukázal tabulka Už jsem druh dal pryč. Ale nejlepším případě runtime, co si myslíme, že? Vše řazeny. N druhou. Každý, kdo má vysvětlení proč si myslíte, že? 

STUDENT: Jste porovnání through-- Instruktor: Správně. Jste porovnání projít. V každé iteraci, i když jsme dekrementování to po druhém, jste stále prohledávat vše najít nejmenší jeden. Takže i když vaše nejmenší hodnota je tady na začátku, jste stále porovnávání proti vším aby se ujistil, že je to nejmenší věc. Takže skončíte procházející přibližně n na druhou krát. Dobrá. A co je nejhorší? Také n na druhou, protože budete bude dělat, že stejný postup. Takže v tomto případě výběr druh má něco že jsme také volat očekávané runtime. Takže ostatní, jsme jen vím, horní a dolní hranice. V závislosti na tom, jak blázen naše Seznam je netříděný nebo jak to je, se liší mezi n nebo n na druhou. Nevíme. 

Ale protože výběr druh má stejné nejhorší a nejlepší případ, že nám říká, že bez ohledu na to, jaký typ vstupu jsme mají, ať už je to zcela řazeny nebo zcela reverzní řazeny, je to bude trvat stejnou dobu. Takže v tomto případě, pokud vás pamatovat z našeho stolu, ve skutečnosti měla hodnotu, která Tyto dva druhy nemají, což je předpokládaná doba zálohování. Takže víme, že vždy, když narazíme výběr druhu, je zaručeno, aby spustit n na druhou dobu. Není tam žádná variabilita. Je to od nich očekává. A opět, pokud se chcete dozvědět, více, vzít CS 124 na jaře. Dobrá. Viděli jsme tohle. V pohodě. Takže vložení sort. A já asi bude na požár přes to. Nebudu mít vy to kód. Budeme se jen procházet přes to. Takže vložení druh je druh o podobný výběru druhu v tom, že máme oba netříděné a seřazena část pole. 

Ale to, co je, je, že jak jsme se projít jeden po druhém, jsme prostě vzít bez ohledu na počet je další v našem netříděný, a správně třídit do našeho tříděného pole. Bude to větší smysl na příkladu. Takže vše, co začíná jako netříděný, Stejně jako u výběru druhu. A budeme třídit na tuto vzestupně, jak jsme byli. Takže na našem prvním průchodu Vezmeme první hodnotu a říkáme, OK, jste nyní v seznamu sami. 

Protože jste v seznamu sami, jste řazeny. Gratulujeme k bytí první prvek v tomto poli. Jste již řazeno vše na vlastní pěst. Takže teď jsme řazeny a netříděné pole. Takže teď jsme se poprvé. Co se stane mezi zde a zde je to, že říkáme, OK, jdeme se podívat na První hodnota naší netříděný pole a budeme vstup je ve svém správné místo v tříděném poli. 

Takže to, co děláme, je bereme 5 a říkáme, OK, 5 je vyšší než 3, takže stačí vložit ji přímo na pravé straně, že. Jsme dobře. Takže jdeme na naše další. A vezmeme 2. My říkáme, OK, 2 menší než 3, takže víme, že to musí být v Přední část našeho seznamu nyní. Takže to, co děláme, je, že jsme tlačit 3 a 5 se a přejdeme 2 do toho prvního slotu. Takže jsme prostě vložením do správné místo, to by mělo být. 

Pak se podíváme na naše příští, a říkáme 6. OK, 6 je větší než vše v našem tříděném poli, tak jsme prostě označit ji až do konce. A pak se podíváme na 4. 4 je menší než 6, je to méně než 5, ale je to menší než 3. Tak jsme prostě vložte ji přímo do uprostřed mezi 3 a 5. Tak, aby se to trochu trochu konkrétnější, Zde je druh představa o tom, co se stalo. Takže pro každý prvek netříděného, ​​jsme určit, kde v tříděném části to je. 

Tak, aby se nezapomínalo na tříděny a netříděné, musíme projít skrz a obr , kde se vejde do tříděného pole. A my ho vložit posunutím prvky vpravo dolů. A pak jsme prostě udržet iterace, dokud mají zcela seřazený seznam kde netříděné je nyní nulová a tříděný zabírá celistvost našeho seznamu. Takže, ještě jednou, aby se věci ještě konkrétnější, máme pseudokódu. 

Takže v podstatě pro i je rovno 0 do n mínus 1, to je jen délka našeho pole. Máme nějaký prvek, který se rovná První pole nebo první indexy. Nastavili jsme j, která se rovná. Takže zatímco j je větší než nula a pole, j minus 1 je větší než prvek, takže vše, co dělá je zajistit, aby Váš j Vás doopravdy zastupuje netříděného část pole. 

Takže zatímco tam je ještě věci třídit a j mínus jedna je-- co je její součástí? J zde nebyla definována. Je to trochu nepříjemné. OK. Tak jako tak. Tak j minus 1, máte kontrolu prvek před ním. Říkáte, že, OK, je element předtím, než tam, kde jsem am-- pojďme skutečně čerpat na to. Takže řekněme, že je to jako na našem druhém průchodu. Takže i se bude rovnat 1, který je zde. 

Takže i bude roven 1. To by bylo 2, 4, 5, 6, 7. Dobrá. Takže naše prvkem v tomto případě bude rovna 4. A máme nějaké j, který je bude roven 1. Oh, j je dekrementování. To je to, co to je. Tak j je roven i tak, co to je Říká se, že, jak jsme kupředu, jsme jen ujistit že nejsme přes indexování tímto způsobem, když se snažíme vložit věci do našeho seznamu seřazené. 

Takže když j je roven 1, v tomto případě, a array j minus one-- tak array j minus 1 je 2 v tomto case--, pokud je to větší než prvek, pak to všechno dělá se přesouvá věci dolů. Takže v tomto případě, pole j mínus jedna by pole nulová, což je 2. 2 není větší než 4, tak to neprovede. Takže posun nepohybuje dolů. Co to však je zde jen pohybem seřazené pole dolů. V tomto případě, ve skutečnosti, jsme by do-- udělejme tuto tři. Takže pokud jsme se projít s tento příklad, my jsme teď tady. To je seřazen. To je netříděný. V pohodě? Takže i je rovno 2, takže náš prvek je rovno 3. A naše j je roven 2. Tak jsme se prohlédnout a my říkají, OK, je pole j mínus jedna větší než prvek že se díváme? A odpověď je ano, je to tak? 4 je větší než 3, a j je 2, takže tento kód spustí. 

Takže teď to, co děláme pole na 2, tak tady jsme se je vyměnit. Tak jsme se jen říct, OK, pole na 2 se nyní bude 3. A j bude rovnat j minus 1, což je 1. To je hrozné, ale vy dostanete nápad. J je nyní roven 1. A pole j se jen bude rovná naší prvku, který byl 4. I vymazat něco, co jsem neměl mají nebo miswrote něco, ale vy dostanete nápad. 

To se pohybují n. A pak, pokud tomu tak bylo, bylo by to smyčka znovu, a to bych řekl, OK, j je 1 nyní. A pole j minus 1 je nyní 2. Je 2 menší než naše prvek? Ne? To znamená, že máme vkládá tento prvek ve správném místě v našem tříděného poli. Pak se můžeme vzít a říkáme, OK, naše seřazené pole je tady. A to by se toto číslo 6 a musí být jako, OK, 6 menší než toto číslo? Ne? V pohodě. Jsme v pořádku. 

Udělej to znovu. Říkáme 7. Je menší než 7 do konce naší tříděného pole? Ne. Takže jsme v pohodě. Takže by to být tříděny. V podstatě to všechno dělá Je to říká vzít První prvek Váš netříděné pole, zjistit, kde to jde v tříděném poli. A to jen stará swapů k tomu, že. Vy jste v podstatě jen vymění dokud je to na správném místě. Vizuální image je to, že jste pohybující se všechno se tím, že. 

Takže je to jako polovina bublina trochu ve stylu. Podívejte se na studii 50. Vřele doporučuji se snaží kódovat na vlastní pěst. Pokud máte nějaké otázky, nebo chcete-li viz ukázkový kód pro vložení druhu, dejte mi prosím vědět. Vždycky jsem se kolem sebe. Takže v nejhorším případě runtime a nejlepším případě runtime. Jak jste chlap viděl z tabulky už jsem vám ukázal, že to tak n na druhou a n. 

Tak laskav a šel pryč z toho, co jsme si povídali o s našimi předchozími druhy, nejhorší případ runtime je, že pokud je to zcela netříděného musíme porovnat všechny tyto n-krát. Děláme spoustu srovnání protože pokud je to v opačném pořadí, budeme říkat, OK, to je stejný, to je dobré, a ten bude muset být ve srovnání proti první se přesunout zpět. A jak se dostaneme k konec ocasu, máme porovnávat, porovnávat a porovnat proti všemu. 

Takže to nakonec byla n přibližně čtvercový. Pokud je to v pořádku, tak si říkají, OK, 2, jsi dobrý. 3, jste v porovnání s 2. Jsi dobrá. 4, stačí porovnat na ocasu. Jsi dobrá. 6, v porovnání s ocasem, že jsi v pořádku. Takže pro každé místo, pokud je již řazeny, děláš jednu srovnání. Takže je to jen n. A protože máme nejlepší případovou runtime n a nejhorším případě běhu n čtvercový, nemáme očekávaný runtime. 

Záleží jen na chaos našeho seznamu zde. A opět další graf a další tabulky. Takže rozdíly mezi druhy. Já jsem prostě jít vánek přes, I pocit, že jsme mluvili značně o tom, jak všechny druhy o lišit a propojit. Takže Merge sort je poslední I se nesl vám kluci s. Máme dost barevný obraz. Takže sloučit druh je rekurzivní algoritmus. Tak si kluci vědí, co rekurzivní funkce? 

Každý, kdo chtěl říct? Chcete-li to zkusit? Tak rekurzivní funkce je jen funkce, která volá sama sebe. Takže pokud vy jste obeznámeni s Fibonacci sekvence, která je považována za rekurzivní, protože budete mít předchozí dva a přidejte je spolu dostat své další. Tak rekurzivní, Vždycky si myslím, rekurze jako jako spirála takže jste jako po spirále dolů do něj. Ale je to jen funkce která volá sama sebe. 

A ve skutečnosti, velmi rychle jsem může ukázat, jak to vypadá. Tak tady rekurzivní, podíváme-li se, je to rekurzivní způsob, jak shrnout přes pole. Takže vše, co děláme, je máme funkci sum částka, která má velikost a pole. A pokud si všimnete, velikost úbytky podle jednoho pokaždé. A to vše dělá, je, pokud x je rovno zero-- takže pokud velikost pole je roven zero-- vrátí nulu. 

Jinak to shrnuje tento poslední prvek pole, a pak vezme součet zbytek pole. Takže je to jen rozebrat to do menších a menších problémů. Dlouhý příběh krátký, rekurze, funkce, která volá sama sebe. Jestli je to všechno, co máš z toho, že to, co rekurzivní funkce. Pokud budete mít 51, dostanete velmi, velmi pohodlné s rekurze. Je to opravdu cool. Dávalo to smysl, jako 3 AM jednu noc. A byl jsem rád, proč Nikdy jsem použít? 

Takže pro sloučení druhu, v podstatě co to bude dělat, je, že je to chystá vyrazit a zlomit to dolů, dokud je to jen jednotlivé prvky. Jednotlivé prvky jsou lehce vyřešit. Vidíme, že. Máte-li jeden prvek, je to již považován za tříděný. A tak na vstupu n prvků, jestliže n je menší než 2, jen vrátit protože to znamená to je buď 0 nebo 1, jak jsme viděli. Ty jsou považovány za tříděné prvky. 

Jinak rozbít na polovinu. Seřadit první polovinu, třídit druhý poloviny, a pak spojit je dohromady. Proč se to jmenuje merge sort. Takže máme tu budeme třídit tyto. Tak jsme se držet s nimi dokud se velikost pole je 1. Takže když je to 1, právě jsme se vrátit protože se jedná o setříděné pole, a to je tříděného pole, a to je setříděné pole, jsme všichni řazeny. Takže to, co děláme, je, že jsme začít sloučení dohromady. 

Takže způsob, jak můžete přemýšlet o slučování je stačí odstranit menší Počet každé z dílčích polí a jen připojit jej k objevily pole. Takže, když se podíváte tady, když máme Tyto sady máme 4, 6, a 1. Když chceme sloučit tyto, Podíváme se na těchto prvních dvou a říkáme, OK, 1 menší, to jde dopředu. 4 a 6, není nic k porovnání to, stačí označit ji až do konce. 

Když jsme se spojit tyto dvě, právě jsme mít menší jeden z těchto dvou, takže je to jedno. A teď jsme se menší z těchto dvou, SO 2. Menší z těchto dvou, 3. Menší z těchto dvou, 4, 5, 6. Takže jste právě sundal ty. A protože jsem byly řazeny dříve, stačí jedno Porovnání pokaždé, když. Takže více kódu, prostě reprezentace. Takže začnete ve středu a třídit vlevo a vpravo a pak stačí spojit ty. 

A my nemáme kód pro sloučení tady. Ale opět, když jdete na studium 50, bude to tam. V opačném případě přijde se mnou mluvit pokud jste stále zmatená. Tak super věc je, že nejlepší případ, v nejhorším případě, a očekává, že runtime jsou v protokolu n, které je mnohem lepší, než jsme vidět po zbytek našich druhů. Viděli jsme n na druhou a to, co jsme vlastně sem je n log n, což je skvělé. 

Podívejte se, jak daleko lepší to je. Taková pěkná křivka. Tak mnohem efektivnější. Pokud jste někdy možné, použijte sloučit druh. To vám ušetří čas. Pak znovu, jak jsme řekli, je-li jste v této nižší regionu, to neznamená, že to velký rozdíl. Získáte až tisíce a tisíce vstupů, budete určitě chtít efektivnější algoritmus. A opět, naše milá tabulka všech druhy, které kluci se dnes dozvěděl. 

Takže vím, že to byl hustý den. To nemusí nutně jít které vám pomohou s vaší pset. Ale jen chci, aby disclaimer že oddíl není jen o psets. To vše materiál je fér Hra pro vaše midterms. A také pokud si pokračovat s CS, Toto jsou opravdu důležité základy které budete potřebovat vědět. Takže pár dní bude trochu pset pomoc, ale několik týdnů bude mnohem skutečný obsah že se může zdát Super užitečné pro vás právě teď, ale slibuji, že pokud budete pokračovat na bude velmi, velmi užitečné. 

Tak to je pro sekci. Dolů drátu. Udělal jsem to během jedné minuty. Ale tam jdete. A já budu mít koblihy nebo bonbóny. Je někdo alergický na něco, mimochodem? Vajec a mléka. Takže koblihy jsou ne? OK. Dobrá. Čokoláda ne? Starburst. Starburst jsou dobré. OK. Budeme mít Starburst příští týden poté. To je to, co budu mít. Vy máte skvělý týden. Číst vaše spec. 

Dejte mi vědět, pokud máte jakékoliv dotazy. Pset dva stupně by měla být k tobě do čtvrtka. Pokud máte nějaké otázky o tom, jak jsem se třídí něco nebo proč jsem se třídí něco tak, jak jsem se, prosím, napište mi, pojď se mnou mluvit. Jsem trochu blázen to týden, ale slibuji, Budu ještě odpovědět do 24 hodin. Takže mají velký týden, všichni. Hodně štěstí na vaší pset.