SPEAKER 1: Hey mindenki! Üdv újra a szakasz. Örülök, hogy ilyen sokan itt is, és mindenki, aki figyel az interneten. Szóval, mint mindig szívesen vissza. Remélem, hogy mindannyian egy szép hétvége, tele pihenés, kikapcsolódás. Gyönyörű volt tegnap. Szóval, remélem, tetszett a szabadban. 

Tehát először egy pár bejelentések. Osztályozás. Szóval, a legtöbb akkor ütött egy e-mailbe nekem a Scratch Pset, valamint az osztályozási Pset 1. Szóval, csak egy pár dolgot. Ügyeljen arra, hogy a check50 style50. Ezek célja, hogy források srácok, hogy megbizonyosodjon arról, hogy kapsz annyi pontot, amennyit csak tudsz anélkül, hogy feleslegesen elveszítik. Szóval, a dolgok, mint a stílus nagyon fontos. Mi lesz, hogy vegye le azt. Néhányan talán már észrevette, hogy az Ön Pset. És check50 csak egy nagyon egyszerű módja annak, hogy hogy mi valójában mit vissza vissza kell küldenie a felhasználó, és hogy minden működik megfelelően. 

A második megjegyzés, győződjön meg róla, feltölteni dolgokat a megfelelő mappába. Ez teszi az életem csak egy kicsit nehezebb ha feltölt Pset 2 az 1 Pset mert amikor én letölteni a dolgokat, nem helyesen letölteni. És tudom, hogy ez egy kicsit rozoga rendszerben kell szokni, de csak szuper óvatos, ha csak nekem, így amikor kapok e-mailt A mint 2:00 és én vagyok osztályozás. Ha nem okoz azt kell nézni körül a Pset. Cool. 

Tudom, hogy korán van, de én Teljesen kapott levették őr egy esszé, ami miatt ezen a héten pénteken, hogy tanáraim voltak, mint, oh yeah. Ne feledje, hogy egy esszé esedékes pénteken. Szóval, tudom, hogy senki sem szereti gondolni midterms, de az első kvíz október 15-én, amely október kezd ezen a héten. Szóval, lehet, hogy előbb a vártnál minden. Annak érdekében, hogy te nem dobták ki őr, ha Azért említem a jövő heti rész, hogy jaj, A kvíz a jövő héten, azt hittem, Adnék egy kicsit A heads-up most. 

Tehát a probléma beállítva, három szám. Hogy az emberek olvasni a spec a kíváncsiság? OK. Van egy pár. Kicsit le az utolsó héten, de ez rendben van. Tudom, hogy gyönyörű out. Így kitörni. Határozottan után kap tenni Ma olvastam a spec legalább próbálja meg, mint letölteni elosztás kód és futás mint az első eredeti dolog, hogy kérjük, hogy. Mert mi használ eloszlás kód és a könyvtár hogy mi már csak using-- --It csak a második alkalom, hogy megtette ezt Pset, őrült dolog történhet az a készülék, és meg akarja találni, hogy ki most versus később. 

Mert ha ez a csütörtök este, vagy ez Szerda este, és valamilyen oknál fogva a készülék csak nem szeretné futtatni a könyvtár vagy forgalmazásával kódot, hogy eszközök akkor nem is kezdeni ezzel a kódolás. Mert nem tudja ellenőrizni hogy ha működik. Ön nem lesz képes hogy ha lefordítja. Azt akarod, hogy vigyázzon az ilyen korán A hét, amikor is e-mailt nekem vagy az egyik a másik TF, és kapunk a fix. Mivel ezek olyan kérdések, hogy fognak megállítani attól, hogy valódi előrelépés. Ez nem olyan, mint egy hiba, hogy akkor csak ilyen átugorják. Ha problémái vannak a készülék vagy forgalmazási kódot, szeretné, hogy kap, hogy a meghozandó érdekel az inkább előbb, mint utóbb. Tehát akkor is, ha nem fog ténylegesen elkezdeni kódolni, töltse le az elosztás kód, olvassa el a spec, győződjön meg róla, minden működik ott. OK? Ha tudod csak csinálni, én Megígérem életetek könnyebb lesz. És akkor valószínűleg megy csinálni most jobb? OK. Tehát bármilyen kérdése van? Minden logisztikai dolgokat? Mindenki jó? OK. 

Fontos azoknak a Ön a szobában és az online. Megyek próbál váltani között PowerPoint a készülék mert megyünk hogy csinál valami kódolás Ma a népszerű kereslet az anonim javaslat szavazás küldtem ki a múlt héten. Szóval, mi lesz ennek valami kódolás. Tehát, ha ti is akar hogy indítsa el a készülék, és akkor már megvan egy e-mailt tőlem, egy minta fájlt. Kérjük, hogy erre. 

Szóval, fogunk beszélni GDB, ami a debugger. Ez fog segíteni fajta kitalálni, hogy hol a dolgok rosszul a kódban. Ez tényleg csak egy módja, hogy lépést át a kódot, ez történik, és képesnek kell lennie, hogy nyomtassa ki a változók vagy, hogy mi történik valójában a motorháztető alatt verseket a programot éppen fut, ez olyan, mint hibás, és te, mint, fogalmam sincs, mi történt itt. Nem tudom, mit nem sikerült a sort. Nem tudom, hol rontottam el. Szóval, GDB fog segíteni neked ebben. Továbbá, ha úgy dönt, hogy tovább igen, és megteszi a 61., ez tényleg, igazán meg legjobb barátom, mert azt lehet mondani, mert megyek át az osztályban. 

Fogunk nézni bináris keresés, amely, ha a srácok eszébe jut a nagy telefonkönyv példa látvány az osztályból. Mi lesz azt végrehajtó, és séta, hogy egy kicsit, aztán megyünk keresztül négy fajtájára, amelyek Bubble, Selection, beszúrás, és egyesítése. Cool. Szóval, GDB mint említettem, egy debugger. És ezek a fajta nagy dolgok, a nagy funkciók és parancsok hogy használja GDB belül, és én járni Ön egy demo azt egy másik. 

Szóval, ez nem csak fog maradni elvont. Megpróbálom, és ez a konkrét lehetséges a srácok. Szóval, szünet. Ez lesz vagy legyen szünet mint például, néhány szám, amely jelentése sor a programban, vagy nevet adhat a funkciót. Tehát, ha mondjuk a fő szünet, akkor megáll a legfontosabb, és hagyom, hogy ezt a funkciót séta. 

Hasonlóképpen, ha van valamilyen külső úgy működnek, mint a Csere vagy Cube, néztük meg a múlt héten. Ha azt mondod, csak egyet is megront e, amikor a programot, hogy üt, ez lesz várni, hogy mondani, hogy mi a teendő. Mielőtt majd csak végre, így ténylegesen beléphet a funkció meg, hogy mi folyik itt. Szóval, Next, csak átugorja a következő sorba megy át funkciókat. Step. Ezek mind apró elvont. Szóval, én csak fog futni rajtuk, de látni fogod őket használat a második. 

Lépjen be a funkciót. Szóval mint mondtam, mint a Swap, akkor lehetővé teszi, hogy valóban, mintha te mint fizikailag léptető belül, akkor rendetlenség azokat a változókat, nyomtatás ki, mik ezek, hogy mi folyik itt. Listája a szó szoros értelmében csak nyomtatni ki a környező kódot. Tehát, ha a fajta elfelejteni hol van a programban, vagy te kíváncsi mi folyik körülötte, ez csak nyomtassa ki a szegmens A, mint öt vagy hat sor körül. Szóval, lehet kapni orientált arról, hogy hol vannak. 

Nyomtatás néhány változó. Tehát, ha a kulcs, mint Caesar, hogy akkor nézd meg. Azt lehet mondani, nyomtatás Key bármikor. Azt fogja mondani, hogy mi az érték, így hogy talán valahol az út mentén, Ön felülírta a kulcsot. Tudod valójában mondani, hogy azért, mert akkor valóban megfigyelhető, hogy az érték. 

A helyiek, csak nyomtat meg a helyi változókat. Szóval, bármikor maga egy hurok, és te csak azt szeretném látni, mint, oh. Mi az én? Mi ez a kulcs érték hogy én inicializálni itt? Mi az az üzenet, ezen a ponton? Ez csak nyomtatni minden e, úgy, hogy Nem kell külön-külön mondjuk, I. Print Nyomtatás üzenet. Print Key. És akkor Display. Mi az, hogy nem, mint te menj végig a programot, akkor csak győződjön meg róla, hogy ez az megjelenítése néhány bizonyos változó minden pontján. Úgy, hogy ez also-- --it egyfajta parancsikon ahol nem kell, hogy menj, mint, oh. Print vagy Print Key I. Ez csak automatikusan megcsinálja helyetted. 

Szóval, hogy mi megyünk hogy milyen ez megy. Fogom próbálni és switch át a készüléket. Lássuk, meg tudom csinálni ezt. All. Mi csak úgy a tükör is. Nincs semmi őrült az én laptop egyébként. OK. Ez kell, hogy legyen ez. Ez annyira apró. Lássuk, ha képes erre. 

OK. Alice nyilvánvalóan küzd itt egy kicsit, de mi lesz akkor a momento. OK. Mi csak növekedni fog ez. OK. Lehet mindenki milyen látni, hogy? Talán egy kicsit? Tudom, hogy ez egy kicsit kicsi. Nem lehet elég kitalálni, hogyan lehet ezt a nagyobb. Ha valaki tudja. Tudja valaki, hogyan kell tenni a nagyobb? OK. Fogunk roll vele. Nem számít egyébként, mert ez csak hogy a kód, amit a srácok kellene van. 

Mi a fontosabb a terminál itt. És mi van itt Miért olyan kicsi? Beállítások. Oh. Igaz Ike. Hogy ez? Onnan. Ez jobb mindenkinek? OK ,. Cool. 

Tudod, amikor az ember a CS osztály technikai nehézségek a fajta részének a-- Nos, nézzük törölje ezt. OK. Szóval, itt a rész, ami volt itt. Caesar egy futtatható fájl. Szóval tette. Szóval, az egyik dolog, hogy észre a GDB hogy csak akkor működik, futtatható fájlokat. Szóval, nem tudja futtatni a dotsy. Meg kell, hogy valóban tenni arról, hogy a kód lefordul, és hogy ténylegesen futni. 

Szóval, győződjön meg arról, hogy ha nem lefordítani,, hogy a program, így ilyen fut át ​​rajta. Így kezdeni GDB, minden, amit csinál, Gloria típusú GDB, és majd csak a fájl, amit akar. Mindig elgépelt Caesar. De azt szeretnénk, hogy győződjön meg arról, mivel ez egy végrehajtható, ti a pont, hogy a vaku azt jelenti, hogy mész futtatni CSI fogsz végre ezt fájlokat akár a debugger. OK. Szóval, akkor, kapsz ez a fajta halandzsa. Csak egész dolgot debugger. Nem igazán kell aggódni, hogy most. És mint látod, itt van ez a nyitott parens, GDP, közeli parens, és csak hasonít a parancssor, ugye? 

Szóval, mit akarunk do-- --So, Az első dolog, az, akarunk választani Egy hely, ahol törni. Szóval, van egy bug ebben Caesar programban hogy bemutatom, hogy fogjuk megtudni. Ez mi ez az tart a bemenet Barfoo minden sapkák, és valamilyen oknál fogva ez nem változik A. Csak hagy egyedül, minden mást a helyes, de a második levél Egy változatlan marad. Szóval, megyünk próbálni, és rájönni, hogy miért van ez. Tehát az első dolog, amit általában akar csinálni, amikor kezdődik GDB hogy kitaláljuk, hol törni. 

Így Caesar egy nagyon rövid programot. Csak egy funkció, igaz? Mi volt a funkciója Caesar? Csak egy függvény, Main jobb? Main függvény az összes programot. Ha nem rendelkezik Main, talán egy kicsit aggódott most, de remélem, mindannyian Main ott. Szóval, mit tehetünk az, hogy mi is csak szünet Main, csak úgy. Szóval, azt mondja, rendben van. Mi meg a töréspont ott. 

Szóval, most a dolog, hogy emlékezzen, Caesar vesz egy parancssori argumentum helyes és mi nem történt meg, hogy sehol sem. Szóval, mit csinálsz, amikor valóban megy futni A program olyan program, amely maga futó GDB igénylő parancssorban érvek fogsz bemenet amikor először kezdi fut. Szóval, ebben az esetben, mi Fuss egy kulcsfontosságú a három. És ez valóban indul. 

Tehát, ha úgy látja, itt van Ha a RC nem egyenlő 2. Tehát, ha a srácok mind a fájl, hogy én küldtem ki fel látni fogod, hogy ez olyan, mint a első sorban a fő funkciója, ugye? Ez ellenőrzi, hogy ha van a megfelelő számú érvet. Tehát, ha kíváncsi ha RC helyes, meg tudod csinálni valamit, mint Print RC. RC kettő, ami amit vártunk, nem? 

Szóval, mehetünk Next, és tovább folytatódik. Szóval, van néhány kulcsfontosságú ott. És ki is nyomtathatja a legfontosabb hogy megbizonyosodjon arról, hogy ez helyes. Érdekes. Nem elég, amit vártunk. Szóval, az egyik dolog, hogy észre A GDB is, ez hogy nem, amíg ténylegesen hit Ezután, hogy a vonal, amit csak látott ténylegesen végrehajtásra. Így, ebben az esetben a kulcs nem rendeltek még. Szóval, kulcs némi szemét érték hogy látod alul. Negatív $ 120-- --It egymilliárd és valami furcsa dolgokat? Ez nem a kulcs, hogy mi várható. De ha megüt a Tovább gombra, majd próbálja Print gomb, ez három. 

Mindenki látja, hogy? Tehát, ha kap valamit hogy te, mint várni. Ez teljesen rossz, és én nem tudom hogy ez fog történni, mert minden, amit akarok tennie, hogy rendelni egy számot, egy változó, próbáld ütő Ezután próbálja nyomtatás újra, és nézd meg, hogy működik. Mert ez csak akkor fog végrehajtani, és valójában rendelni valami után megüt a Tovább gombra. Értelme mindenki? Uh huh? 

SPEAKER 2: Ha a véletlen szám mit jelent? 

SPEAKER 1: Ez csak véletlen. Ez csak szemét. Ez csak valami, hogy a számítógép véletlenszerűen rendelni. Cool. Szóval, most már mozoghat, és így most itt van ez a sima szöveg getString. Szóval, hadd vezessen mi fog történni, amikor elérünk Next itt. A GDB fajta eltűnik, ugye? Ennek oka, hogy getString most végrehajtó, ugye? Tehát, amikor láttuk, egyszerű szöveges értéke GetString, nyitott parens és parens, és elérünk Next, amely ténylegesen elvégzett most. Szóval, ez vár minket bemenet valamit. 

Szóval, fogunk bemeneti élelmiszer, amely mi ez hiányában ahogy mondtam és hogy csak azt mondja, hogy ez az kész végrehajtó, hogy a zárt konzol azt jelenti, hogy kilépő ki, hogy a hurok. Szóval, mi is megüt gombra, és most, ahogy vagyok Biztos, hogy minden ismerős Caesar, ez az, amit ez a vonal fog tenni. Ez Internethez I értéke 0, N = Strlen, sima szöveg, majd a Én kevesebb, mint n, én, plusz, plusz. Mi ez a hurok fog csinálni? Nyissa meg az üzenetet. Cool. Szóval, kezdjük csinálja. 

Tehát, amennyiben ez a feltétel egyezik, a mi első? Ha ez a B, akkor az egyszerű szöveges I. Mi kaphat információt a helyiek. Így, én nulla, és ha nem hat, amely várunk, és a legfontosabb az a három. Minden, ami van értelme, igaz? Ezek a számok mind pontosan mit kell lenniük. Szóval, hum? SPEAKER 3: Van véletlen számok az enyém. SPEAKER 1: Nos, azt check-- --we lehet beszélgetni, hogy a második. De legyen szerzés ez. Tehát, ha van egy főváros B az első, ezt a feltételt kell elkapni, igaz? Tehát, ha megüt Ezután látjuk hogy ez valóban végrehajtja ha. Mert ha a következő mellett a kódot, ezt a sort itt, ahol az egyszerű szöveges I helyébe e számtani, csak ha végrehajtja a ha feltétel helyes helyes? 

GDB csak akkor fog mutatni dolgok valójában végrehajtó. Tehát, ha ez a Ha a feltétel nem teljesül, akkor Csak megy ugorjon a következő sorra. OK? Szóval, van, hogy. Ez azt jelenti, hogy konzol zárt ki, hogy a hurok most. Szóval, ez lesz újrakezdeni. Csak úgy. Szóval, hogy be tudjuk szerezni info a mi helyiek itt, és azt látjuk, hogy az első levél változott, ugye? Ez most az E, mint amilyennek lennie kellene. Szóval, mi is tovább. 

És mi van erre az ellenőrzésre. És ezt az ellenőrzést kell dolgoznia, igaz? Ez A. Meg kell változtatni három betű előre. De ha azt veszi észre, mi kap valami más. Tehát ebben az esetben itt, elkapta , és így ezt a sort végre, amely a módosított B. De ebben az esetben is, van, hogy csak kihagytam, és elment a [? L Siff. ?] Tehát valami folyik ott. Ez azt mondja ki, hogy, tudjuk, hogy meg kell fogni itt, de ez nem. Tud valaki, hogy mi a probléma van a sorban? Ez egy nagyon percenként dolog. És azt is nézd meg a kódot. Ez is line-- felejtsd el, amit vonal is A there-- de a [hallható]. Igen? 

SPEAKER 4: ez a több, mint oldalon, ha elolvassa azt a könyvet. SPEAKER 1: Pontosan. Szóval, a debugger nem tudta megmondani te, de a debugger lehetne még le, hogy a vonal amelyről tudja, hogy nem működik. És néha, amikor különösen később a félévben, amikor a van dolgunk, a száz, a száz pár sornyi kódot, és Nem tudom, hol van ennek hiányában, ez egy nagyszerű módja annak, hogy csináld. Szóval, mi megtaláltuk a hibát. Meg tudod oldani, hogy a fájlban, és akkor lehet futni újra, és minden tökéletesen fog működni. És a legnagyobb dolog ez úgy tűnik, mint, OK. Igen. Cool. Azt tudta, hogy mit keres. Szóval, tudta, mit kell tennie. 

GDB lehet szuper hasznos, mert kinyomtathatja az összes ezeket a dolgokat, amit nem. Ez sokkal hasznosabb, mint a printf. Hányan használ mint printf kitalálni, hogy hol a hiba volt, ugye? Szóval, ezzel, akkor nem kell menj vissza, és mint kommentálja a Printf, vagy megjegyzésbe, és kitalálni, mit kell nyomtatni. Ez valójában csak lehetővé teszi, hogy menj végig, nyomtassa ki a dolgok ahogy mész át, így, akkor megfigyelni, hogyan változik a valós idejű, mint a program fut. 

És ez nem fog egy kicsit kicsit megszokni. Én nagyon ajánlom csak ilyen Az, hogy egy kicsit csalódott vele jobb most. Ha kiad egy óra alatt a a jövő héten a tanulás, hogyan kell használni GDB, akkor mentse magát annyi időt később. És szó szerint. Elmondjuk ezt az ember minden évben, és emlékszem, mikor vettem a osztály, olyan volt, mint, én minden rendben lesz. Nem. Pset 6 jött, és én mint, fogok tanulni hogyan kell használni GDB mert én nem tudja, mi folyik itt. 

Tehát, ha rászánja az időt, így használja a kisebb programok hogy te lesz dolgozik, mint a munka keresztül valami hasonló Visionare, mint ez. Vagy ha azt szeretnénk, extra gyakorlat, biztos vagyok benne, Tudtam felér hibás programok az Ön számára, hogy hibakeresést, ha szeretne. 

De ha egy kis időt, hogy megszoktam, csak a játék körül vele, ez tényleg megéri. És ez valóban az egyik azokat a dolgokat, amit csak meg kell próbálni, és a kezed piszkos be, mielőtt igazán értem. Én tényleg csak megértette egyszer Kellett túlbonyolított vele, és ez sokkal szebb, ha egy ötlet hogyan debug inkább előbb, mint utóbb. OK. Cool. Tudom, hogy ez olyan, mint egy gyorstalpaló GDB, és én biztosan dolgozni kezd ezeket nézni nagyobb legközelebb. Cool. 

Tehát, ha megyünk vissza a PowerPoint. Fog ez működni? AWH. Igen. OK. Tehát, ha valaha is szüksége a azok megint ott van a listán. Szóval bináris keresés, amely mindenki emlékszik a nagy látvány Dávid rippelés telefonkönyvek felét. Én nem igazán kap a telefonkönyv többé, mert mint ahol ugye kap telefonkönyvek manapság? Én tényleg nem tudom. A bináris keresés. Tudja valaki emlékszik hogyan bináris keresés működik? Bárki, aki egyáltalán? Igen? SPEAKER 5: Tudod, amikor megnézi, amelynek a felét az lenne, hogy alapul, és megszabadulni a másik felét. 

SPEAKER 1. Pontosan. Szóval, bináris keresés, ez a fajta a-- --we hívjuk, hogy oszd meg és uralkodj. Szóval, mit fogsz csinálni a akkor meg a közepén, és látni fogod, ha az megfelel amit keres. És ha nem, akkor próbálja kitalálni, ez fog hagyni fele vagy a jobb felét. Szóval, ez lehet, ha keres valamit, ami betűrendbe, látod, oh. Vajon Allison elé M? Igen. Szóval, megyünk nézd meg az első félidőben. 

Vagy lehet, mint a számok. Bármi, amit tud összehasonlítani, lehet válogatni. Használhatja bináris keresés. Szóval, valaki emlékszik erre grafikon, vagy mi ez? Ez Aszimptotikus komplexitás. Szóval, ez a grafikon csak leírja, hogy mennyi ideig úgy, hogy megoldja a problémát növeli a néhány dolog hogy használ. 

Szóval, van N, amely a lineáris idő. Ha N több mint két, ami valamivel jobb, még mindig nő szuper gyors. És akkor már be, ami amit mi úgy bináris keresés. Ha azt vesszük észre, mivel a probléma lesz sokkal és sokkal nagyobb, a szükséges időt, hogy megoldja azt nem igazán növeli, hogy sok. Ez olyan, mint hasonló itt az elején. Te, mint, OK. Bármi, itt nem igazán számít, melyik az általunk használt, de akkor kap arra, hogy egy millió, milliárd. Megpróbálod megtalálni some-- --you're megpróbálja megtalálni a tűt a szénakazalban. 

Azt hiszem, szeretné ezt a problémát. Azt akarjuk, hogy ez a komplexitás, nem lineáris, mert minden, amit tudni, hogy a kereső segítségével lesz minden egyes tű, dolog széna, próbál keresni a tűt. És ez nem túl szórakoztató véleményem. Szeretem gyorsan. Szeretem hatékony. És szorgalmas diákok akkor fiúk, tudod a munka okosabb, Nem nehezebb típusú dolog, hogy vagy lehet, hogy ezeket az algoritmusokat. 

Szóval, megyünk sétálni keresztül csak egy gyors példa. Szerintem nektek kellett volna a kezét bináris keresés, de ha valaki egy kicsit fuzzy, szeretnék megerősíteni azt, megyünk csak megy egy példán keresztül itt. Szóval, keresünk, ha A tömb hét. 

Szóval, az első dolog, amit tehetünk, nézd középen, ugye? És azt is meg leszel kódolás Binary Keresés csak a második. Szóval, lesz móka. Így néz ki a középső kis tömbök 3. Van 3 egyenlő 7? Hát nem. Ez hat. Szóval, ez kevesebb, mint vagy nagyobb, mint hét? Kevesebb, mint. Igen. Szép munka fiúk. Úgy érzem, olyan, mint én kellene Van cukorka, mert szeretné, hogy dobja ki a yard. Ez az, amit én fogok csinálni a jövő héten. Ez fogja srácok éles. 

Szóval, dobja el, hogy első felében, ugye? alatti volt. tudjuk, hogy mindent az, hogy a bal oldali lesz kisebb, mint amit mi valójában keresnek. Szóval, nem kell, hogy figyelni rá. Csak felejtsd el. Szóval, most nézzük meg a jobb oldalon, és nézzük meg középen ott, és most már kilenc. Szóval, 9. ez-- --Everyone? Nagyobb, mint amit mi keresnek, igaz? Szóval, megyünk dobni el minden jobbra. Mint azt. Most minden mi maradt egy. Így ellenőrizni, ez egy milyen keresünk? az. Azt találtuk, amit akartunk. Szóval kész. Keresés a bilineáris. 

És ha azt veszi észre, mi pedig hét bemenetek ott. Csak elvitt minket mint háromszor, de ha csinálsz, mint egy milliárd tudjátok, hogy hány lépést is lenne hozni, ha volt négymilliárd dolgokat? Minden találgatások? Ez a 32. 32 lépés, hogy talál valamit egy négymilliárd elem tömb miatt hatáskörének kettő. Tehát kettő 32, hogy négymilliárd. 

Szóval, elég őrült, hogy hogyan, hogy még mindig belül mint egy viszonylag kis számú lépést találni valamit négymilliárd elemekkel. Szóval ez a megjegyzés, vagyunk majd ezt a kódot így ti is valójában milyen látni, hogy ez hogyan működik. Rendben, így ti is kódot. Én hagyom, hogy a srácok beszélni egy kicsit. Ismerd meg az embereket körülötted, ami amit valaki akart az utolsó szakasz. 

Így megismerik az emberek körülötted. Beszéljen egy kicsit. És minden, amit akarok tőled srácok most csak megpróbál létrehozni egy vázlatot pszeudokódja. OK? Hú. Csak azt szeretném tőletek van te csak úgy, hogy töltse ki ezt, miközben az esetben. Szóval már meg ezeket a felső és alsó határ, amely képviseli a kezdet és vége a tömb. És fogsz ténylegesen hurkolt és kitalálni mit csinálunk ebben a while ciklus. 

Tehát, ha a szám out-- van egy tipp there-- mik az esetek hogy mi van itt? Tehát, ha azt szeretnénk, hogy kitaláljuk, a esetben, akkor azokat pszeudokódja és akkor majd tényleg kódot őket. És ez lesz, én gondolom, remélhetőleg ez lesz egy kicsit könnyebb, mint gondolnád. Mert ez nem olyan sok kódot, valójában, ami nagyon klassz. 

Mm-hm? 

Diák: [hallható]? OKTATÓ: Igen. Volt valami megtalálni a közepén. 

Diák: Így tudjuk használni azt. OK. 

OKTATÓ: Tökéletes. Szóval ez az első dolog, amit tennie kell. Így találja a közepén. Nagy. Szóval van egy ötletem, hogyan lehet ténylegesen meg középen kódot? 

Diák: Igen. n több mint 2? OKTATÓ: Tehát n több mint 2. Tehát az egyik dolog, hogy emlékezzen, hogy A felső és alsó határ változik. Tartjuk a szűkítő rész a tömb keresünk a. Tehát n több mint 2 csak akkor működik, Az első dolog, amit tenni. Így vesz a felső és alsó venni, hogyan lehet azt kapjuk, hogy középső elem? Mert azt akarjuk, hogy a középső a felső és alsó, ugye? Mm-hm? 

Diák: [hallható]. 

Oktató: Tehát némi közepén. És ez lesz a felső plusz alsó vége 2. Félelmetes. Ott megyünk. Egy sorral lejjebb. Vagytok az utat. Most, hogy megvan a középső, mit akarunk csinálni? Csak általában. Nem kell kódolni azt. Igen. Diák: [hallható]? Oktató: Tehát plusz azért, mert te megtalálása átlagosan két őket. Tehát, ha úgy gondolja, rájuk, mint kedves fokozódni oldalról, gondolj bele, ahogy közeledünk A középső, kívánt ilyesmi. Tehát, ha úgy döntesz, mindkét oldalán a középső, és mi, mint az 5. és a 7.. Ha hozzá őket együtt, kap 12, akkor ossza 2, 6. 

Néha nehéz miért, hogy működik, de ha a munka révén Példaként néha, ez segíteni fog kitalálni, ha meg kell plusz vagy mínusz. Igen. 

Diák: [hallható] pontosan a közepén ha volt egy eset, amikor van egy csomó kisebb számok és mint egy nagy szám? 

OKTATÓ: Szóval csak annyit kell a középső a tömb. Tehát, ha volt egy csomó kis számok majd egy igazán nagy szám a végén, nem számít. Csak az számít, hogy ők válogatni, csak szeretné nézni a közepén A tömb azért, mert te még mindig szeletelés a problémát ketté. Cool. Tehát most, hogy már a középső, mit csinálunk a következő lépés? 

STUDENT: Hasonlítsa össze. Oktató: The össze. Így összehasonlítani középső value_wanted. Cool. Így látod itt van Ezt az értéket szeretnénk itt. Ne feledje, ez egy tömb. Tehát középső utal az index. Szóval akarok értékeinek közepén. Ne felejtsd el, ha azt szeretné, összehasonlítani, kettős egyenlők. Te egy egyenlő te Csak megy újra ki kell jelölni, és akkor persze, hogy lesz a kívánt értéket. Tehát nem tehetem. 

Így fogunk látni, ha Az értékeket a középső egyenlő értéket akarunk. Ne felejtsd el a fogszabályozó. Dropbox elmúlnak. Szóval mit tegyünk ebben az esetben? Ha ez az, amit akarunk visszatérni? Azt akarod mondani. 

DIÁK: Print le. 

Oktató: Nos, nem akar nyomtatni ki. Tehát ez egy bool itt, ezért vissza akar térni igaz vagy hamis. Azt mondod, ez a szám Egy [? RRA? ?] Tehát, ha van, mi csak vissza igaz. Ha én is pontosan igaz. 

Diák: Miért nem tér vissza nulla? Oktató: így lehet vissza nulla, ha akarod. De ebben az esetben, mivel a függvény a bool, vissza kell térnünk igaz vagy hamis. DIÁK: Ha mondván: logikai kifejezés, lehet beállítani azt egyenlő hamis? Mint ha azt akarom mondani, hogy ha ez a feltétel nem teljesül, mint a felső értéke hamis. Vajon megértjük, ha csak fel hamis a másik oldalon? OKTATÓ: Igen. Tehát tulajdonképpen ha valaha csinál valamit mint a felső vagy az alsó, hogy vissza igaz vagy hamis és ez valóban rossz stílusban mondjuk értéke eléri vagy valódi egyenlőségen egyenlő hamis. Azt akarod használni, hogy eredmény mint magát a csekket. Nem az, amit akartam. Ez az, amit én akartam. Tehát abban az esetben, kérded valami hasonló mentse ezt a c. 

Tehát, ha van int main (void) és valami ilyesmi. És van, ha a felső Az egyes input és te kérdezi, ha meg tudod csinálni valami ilyesmi? Jobb? Diák: Megpróbáltam csinálni [hallható]. Mert ha it's-- OKTATÓ: Így van. Tehát azt szeretnénk, hogy ez hamis, nem igaz? Diák: Igen. Oktató: Tehát ebben az esetben akarjuk, hogy végre, ha ez nem igaz. Így a hűvös dolog, amit tennie van ez. Úgy emlékszem, felkiáltás pont tagadja a dolgokat? Azt mondja [hallható] azt sem. Tehát, ha megnézzük csak ez a rész itt, jobb lenne, ha azt mondják, hogy értékeli a hamis, ahogy jónak látja. Nem hamis igaz, amely ez azt jelenti, végre. Van ennek értelme? Diák: Igen. OKTATÓ: Félelmetes. OK. Így lehet csak vissza igaz ebben az esetben. Tehát most már két másik esetek ebben az esetben. Melyek a két másik esetben? Nézzük csak ezt így. Szóval kezdjük mással ha a középső értékek kisebb, mint az érték akarunk. Tehát mi az érték a középső kevésbé mint az érték, amit keresünk. 

Szóval, ami ugye kötött hiszem, szeretné frissíteni? Felső vagy alsó? Felső? Tehát melyik oldalon a tömb fogunk vizsgálni? 

Diák: Az alsó. 

Oktató: Mi megyünk hogy nézi a bal oldalon. Tehát, még ha csekély értéke kisebb. Így a középső érték itt kevesebb, mint amit mi szeretnénk. Ezért szeretnénk, hogy a jobb oldalán a tömbben. Így megyünk frissítjük alsó korlátot. Tehát mi a mi alacsonyabb hozzárendelését. És mit gondol az alacsonyabb legyen? Diák: A középső érték? OKTATÓ: Tehát a középső value-- Diák: Plusz 1. Oktató: --plus 1. Tud valaki mondja meg, miért van, hogy a plusz 1? 

Diák: [? Nem érték?] inkább egyenlő vele. 

OKTATÓ: Így van. Mert már tudjuk, hogy a középső érték nem egyenlő , és azt akarjuk, hogy kizárja azt minden későbbi keresést. Ha elfelejti, hogy plusz 1, az lesz, mint a hurok a végtelenségig. És akkor csak fogott egy végtelen ciklus és akkor majd segfault és a dolgok rosszra fordulnak. Tehát, mindig győződjön meg arról, hogy te nem beleértve az értéket, amit csak nézett. Tehát vigyázni, hogy a plusz 1. 

Tehát most van az utolsó állapot amely mindig a biztonság kedvéért Itt ellenőrizheti, ha más érték a középső érték nagyobb, mint a akarunk. Ez azt jelenti, hogy azt akarjuk, A bal felét. Igen, melyik megyünk frissíteni? Felső. És mi ez lesz egyenlő? Közel mínusz 1, mert, Természetesen szeretnénk hogy győződjön meg arról, hogy nem vagyunk nézi, hogy a középső érték megint. És akkor mi van ez. Ennyi. Ez minden bináris keresés. Ez nem olyan rossz, ugye? Ez olyan, mint a 10 soros kód, fehér térben. Szóval nagyon erős, nagyon hasznos, akkor legyen használja az egyik később psets. Lehet, hogy nem ez, hanem később. Így tanulni. Szerelem ez. Ez jól bánnak veled. Szóval nem akárki rendelkezik kérdésre bináris keresés? Igen. 

Diák: Számít hogy az n páros vagy páratlan? 

Oktató: Nem. Mert öntött, hogy a középső, mint int, akkor csak azt csonkolni. Így marad az egész, és ez lesz végül kereshetőség mindent. Szóval nem kell aggódni, hogy a. Mindenki jó? Félelmetes. Cool. Szóval, srácok ezt. Slideshow. Tehát ahogy beszéltünk, én tudom, David említett komplexitás runtimes. 

Így a legjobb esetben ez csak egy, mely az állandó idő. Tud valaki mondja meg, miért lehet? Milyen típusú forgatókönyv jelentő? Mm-hm. 

Diák: [hallható] first-- OKTATÓ: Tehát a középső pedig a első elemét, hogy mi jön, ugye? Így akár egy sor egy vagy amit keresünk, csak történetesen smack dab közepén. Szóval ez a legjobb eset. Ön kap a valós problémákra, valószínűleg nem fog elérni [hallható], hogy gyakran. Mi a helyzet a legrosszabb esetben? A legrosszabb esetben log n. És hogy köze van az egész hatásköre két dolog, hogy én beszéltem. 

Így a legrosszabb esetben ez azt jelentené, hogy mi volt, hogy vágja le a tömb amíg ez egy elem az egyik. Így kellett vágja le a fél ahányszor csak lehetséges lehetett. Ez miért van, mert log n csak tartani elosztjuk kettővel. Szóval feltevések dolgot tudnia kell, ha valaha fogja használni a bináris keresés. Az elemeket kell válogatni. Ezeket nem kell válogatni, mert hogy ez az egyetlen módja annak, lehet tudni, ha tudja hogy dobja ki a felét. 

Ha már ez a zagyva táska a számok és azt mondod, OK, megyek, hogy ellenőrizze a középső és a szám keresem kevesebb, mint, hogy én csak megy hogy önkényesen dobja ki az egyik felét. Azt nem tudom, hogy a számok a másik felét. A listát meg kell válogatni. Is, ez lehet megy előre egy kicsit, de meg kell, hogy véletlen elérésű. Meg kell tudni, hogy csak megy, hogy a középső elem. Ha van áthalad keresztül valami vagy visz extra lépéseket eljutni, hogy a középső elem, ez nem log n, mert már te hozzá több munkát bele. És ez, hogy egy kis több értelme van két hét, de én csak egyfajta akart előszó, adni nektek arról, hogy mi az, hogy jöjjön. De ezek a két fontos feltételezések hogy szükség van a bináris listát. Győződjön meg róla, hogy rendezve. Ez a nagy egy-egy srácok most. És, hogy mi mehet be a többi a mi fajta. Tehát négy sorts-- buborék, beillesztés, kiválasztás, és merge. Ők mindenféle klassz. Ha úgy dönt, hogy a srácok CS 124, megtudhatja mindenféle fajta. És ha egy XKCD rajongó, ott egy nagyon jó képregény a következőről: mint valójában hatástalan fajta, amit Javasoljuk fogsz nézni. Ezek közül az egyik, mint a pánik fajta, amely mint, ó, nem, vissza véletlen tömb. Shutdown rendszer. Hagyjuk. Tehát geeky humor mindig jó. 

Tehát nem mindenki emlékszik kedves hasonló csak egy általános képet hogy milyen fajta buborék működik. Emlékszel? 

Diák: Igen. 

Oktató: Hajrá. 

DIÁK: Szóval megy keresztül, és ha ez nagyobb, akkor a két csere. 

Oktató: Mm-hm. Pontosan. Szóval csak halad végig. Kivárunk két számot. Ha az egyik előtt nagyobb mint az utána, csak cserélni őket, azért, hogy a Ily módon az összes nagyobb számban buborék fel vége felé a lista és a kisebb számok buborék le. 

Vajon mutatni nektek a hideg hang hatás válogatás videó? Ez klassz. Szóval mint Robert csak azt mondta, az algoritmus hogy csak végig a listán, csere a szomszédos értékek ha ők nem azért. És akkor csak folyamatos ismétlése amíg meg nem tesznek swap. Szóval nem rossz, ugye? Szóval csak egy gyors példa itt. Tehát ez fog rendezni őket növekvő sorrendben. Így, amikor átmegyünk az első idő, nézzük a nyolc és hat nyilvánvalóan nem annak érdekében, hogy azt cserélni őket. 

Szóval nézd meg a következőt. Nyolc és négy nem azért. Cserélni őket. Aztán nyolc és kettő, cserélni őket. Ott megyünk. Így aztán az első menetben, akkor tudja, hogy a legnagyobb számban lesz egészen tetején, mert ez csak lesz folyamatosan nagyobb, mint minden más és ez csak fog buborék fel egészen a végéig ott. Van ennek értelme mindenki? Cool. 

Akkor nézzük a második menetben. Hat és négy kapcsoló. Hat és két kapcsoló. És most van egy pár dolog, hogy. Tehát minden elmúlik, hogy mi hogy a mi teljes lista tudjuk, hogy ilyen sok a számok a végén lesz rendezve. Tehát mi egy harmadik lépés, amely az egyik csere. És akkor a mi negyedik át, már nulla helyekkel. És tudjuk, hogy a tömb lett rendezve. 

És ez a nagy dolog buborék sort. Tudjuk, hogy amikor nulla csereügyletek, hogy azt jelenti, hogy minden a teljes rend. Elég, hogy hogyan ellenőrizzük. Így is lesz kódolni buborék fajta, amely szintén nem olyan rossz. Ezek egyike sem olyan rossz. Tudom, hogy úgy tűnik, egy kicsit ijesztő. Tudom, hogy mikor vettem az osztály, akkor is, ha én tanította az osztályt Az első alkalommal tavaly, Én, mint, hogyan tudom ezt megtenni? Annak van értelme elméletben, de hogyan ténylegesen ezt teszik? Éppen ezért én is szeretnék járni a kód veletek itt. Szóval van egy pszeudokódja A srácok ezúttal. Tehát csak ezt tartsd szem előtt, vagyunk arról, hogy átmeneti felett. Tehát néhány számláló nyomon követi a mi swapok, mert meg kell győződjön meg róla, hogy mi, hogy ellenőrizték. És mi navigálhat az egész tömb ahogy mi most csináltam ezt a példát. Ha az elem előtt nagyobb, mint Az elem után itt tartunk, mi cserélni őket, és mi a növedék számláló mert amint cserélni, azt akarja, hogy mi tudjuk, hogy a számláló. Bármilyen kérdése van? Valami vicces tűnik itt. DIÁK: Ön a számláló nullára minden alkalommal, amikor megy át a hurok? Ne menj vissza nullára minden alkalommal? Oktató: Nem feltétlenül. Tehát mi történik, mi megy itt keresztül. Tehát nem közben, emlékszem, ez a végrehajtja egyszer hiba nélkül. Így fog beállítani a számláló nulla, akkor ez meg fog halad végig. Ahogy lépked, naprakésszé számláló. Mivel frissíti számláló, ha kész, ha ez elérte a végén a tömb, ha a lista még nem rendezett, számláló frissítve lett. 

Tehát akkor ellenőrzi a feltételt, és azt mondja, OK, számláló nullánál nagyobb. Ha így van, újra meg újra. Azt akarod állítani úgy, hogy ha megy át, számláló egyenlő nullával. Ha valaki átmegy a rendezett tömb, semmi nem változik, ez nem sikerül, és vissza a rendezett lista. Van ennek értelme? DIÁK: Ez lehet, hogy egy kicsit később. OKTATÓ: OK. Ha bármi más kérdés, hogy jön fel. Igen. 

Diák: És mi lenne a funkciója legyen átszivatásáho elemek? 

Oktató: Tehát valójában írni hogy ha megyünk most. Cool. Tehát, hogy a megjegyzés, Alison megy visszaváltani a készülék. Ez lesz szórakoztató. És mi van a mi szép buborék fajta dolog itt. Szóval már megtettem kerékpározás a tömb. Megvan a swapok hogy egyenlő nullával. Ezért szeretnénk cserélni szomszédos elemeket, ha ők elromlott. Tehát az első dolog, amit meg kell nem is halad végig a tömbben. 

Szóval, mit gondolsz mi lehet, hogy halad végig a tömb? Van meg és az i értéke 0-ra. Azt akarjuk, én kevésbé mint n mínusz 1-mínusz k. És leírom, hogy a második. Tehát ez egy olyan optimalizálási itt, ahol, emlékszem, hogy azt mondta, miután minden elmúlik, a tömb, amit tudom, hogy ez bármi on-- 

Így aztán egy menetben is tudjuk, hogy ez rendezve. Miután két menetben tudjuk hogy mindez rendezve. Három menetben is tudom, hogy van rendezve. Tehát ahogy én iterációjával a tömb itt, van ez így biztos, hogy csak menjen keresztül mi tudjuk, hogy nem válogatott. OK? Ez csak egy optimalizálás. Írhatsz azt naivan csak iterációjával át mindent, ez csak tovább tart. Ezzel a négy hurok ez csak egy szép optimalizálás mert tudjuk, hogy miután minden teljes ismétlés a tömb itt, mint minden teljes hurok van, tudjuk, hogy az egyik több ilyen elem lesz rendezve a végén. 

Tehát nem kell aggódni ilyen. Van ennek értelme mindenki? Ez jó kis trükk? Így abban az esetben, ha vagyunk iterációjával keresztül, tudjuk, hogy szeretnénk, ha szeretné ellenőrizni array n és n + 1 rendben vannak. OK. Tehát itt a pszeudokód. Azt akarjuk, hogy ellenőrizze, ha tömb n és az n + 1-rendben vannak. Szóval, mi van ott? Ez lesz valami feltételes. Ez lesz, ha. 

Diák: Ha a tömb n kevesebb mint tömb n + 1. Oktató: Mm-hm. Nos, kisebb vagy nagyobb, mint. Diák: Nagyobb, mint. Aztán szeretnénk cserélni őket. Pontosan. Így most bejutni, mi a mechanizmust swapping őket? Így mentünk át ezt röviden, egyfajta swap függvény a múlt héten. Tudja valaki emlékszik, hogyan működött? Tehát nem csak hozzárendelését, ugye? Mivel egyikük eltévedni. Ha azt mondtuk, A egyenlő B, majd B egyenlő az A, mind egy hirtelen mindkettő csak egyenlő B. 

Tehát mi kell tennie, hogy mi Van egy átmeneti változó, ami fog tartani, míg a miénk mi vagyunk a folyamat csere. Szóval mi van az, hogy mi lesz néhány int temp egyenlő to-- hozzárendelheti hogy melyik kívánt, csak győződjön meg róla, hogy nyomon követheti it-- így ebben az esetben fogom hozzárendelheti tömb n + 1. Annak érdekében, hogy meg fog tartani bármilyen érték ebben a második blokk hogy keresünk. 

És akkor, amit tehetünk, mehetünk előre, és újra sor n + 1, mert tudjuk, Van, hogy a tárolt értéket. Ez is az egyik nagy things-- Nem tudom, ha valakinek volt kérdés, ahol, ha váltani két sornyi kódot hirtelen működnek a dolgok. Rend nagyon fontos a CS. Ügyeljen arra, hogy rajz dolgok, ha lehetséges hogy mi történik valójában. Tehát most megyünk hozzárendelését tömb n + 1, mert tudjuk, Van, hogy a tárolt értéket. 

És mi lehet rendelni, hogy a tömb n vagy ebben az esetben a tömb i. Túl sok a változó. OK. Így most már újraosztani array i plusz 1 egyenlő, mi van a tömb i. És most mehetünk vissza, és rendelni tömb i mi? Valaki? 

Diák: 10. 

OKTATÓ: 10. Pontosan. És egy utolsó dolog. Ha már cserélték most, mit kell csinálni? Mi az az egy dolog hogy fog mondani ha valaha is megszünteti ezt a programot? Mi azt mondja, hogy egy rendezett lista? Ha nem végez semmilyen csereügyletek, ugye? Ha a swap ügyletek egyenlő nulla végén e. Így amikor végre a csere, hiszen Csak nem itt, szeretnénk frissíteni swap. És tudom, hogy ott volt a kérdés korábban arról te is használjon nulla vagy egy helyett igaz vagy hamis. És ez az, amit ez csinál itt. Tehát, ez azt mondja, ha nem swap. Tehát, ha a swap ügyletek nulla, ami ez-- mindig kap az igazságok és a falses összekeveredett. Azt akarják, hogy értékelje az igaz, és ez nem az. Tehát, ha ez nulla, akkor az hamis. Ha tagadja meg a [? bumm?] lesz igaz. Akkor ezt a sort végrehajtja. 

Igazság és hamis és nullák megőrülnek. Csak ha lassan járni rajta akkor van értelme. De ez az, amit ez a kis kis kód itt nem. Tehát ez ellenőrzi, hogy tettünk semmi swap. Tehát, ha ez valami mellett nulla, akkor lesz hamis és az egész dolog megy végre újra. Cool? 

DIÁK: Mit csinál szünet? 

OKTATÓ: szünet csak tör téged a hurok. Így ebben az esetben is lenne csakúgy, mint a végén a program és akkor csak már a rendezett lista. STUDENT: Csodálatos. Oktató: Sajnálom? Diák: Mert mi korábban használt írott 1 felett írott nulla bemutatni, hogy ha hogy működni fog-e vagy sem. 

OKTATÓ: Igen. Így vissza nulla vagy 1. Ebben az esetben, mert nem vagyunk valójában csinál semmit a funkciója, mi csak szeretnénk azt megtörni. Nem igazán érdekli. A fék is jó, ha ez használt kitörésre A négy hurok és feltételeket, amelyek ha nem akarjuk megtartani végrehajtó. Csak viszi ki őket. Ez egy kicsit árnyalatot dolog. Úgy érzem, van sok kézzel integetett, mint megtudhatja ilyen hamar. 

De fogsz tanulni ezt hamarosan. Ígérem. OK. Tehát nem mindenki kap buborék sort? Nem rossz. Halad végig, csere dolgok egy temp változó, és készen is van ott? Cool. Félelmetes. OK. Vissza a PowerPoint. Bármilyen kérdése általában Ezekről eddig? Cool. Mm-hm. 

Diák: [hallható] int main általában. Van, hogy, hogy ez? 

OKTATÓ: Szóval mi csak keresünk éppen az aktuális rendezési algoritmus. Ha már belül mint egy nagyobb program, akkor van egy int main valahol. Attól függően, hogy hol ezt algoritmust, ez határozza meg, mi a által visszaadott azt. De a mi esetünkben, mi szigorúan megnézzük, hogyan működik ez valójában halad végig egy tömböt. Tehát ne aggódj emiatt. 

Így beszéltünk legjobb esetben, és legrosszabb forgatókönyv bináris keresés. Ezért is fontos, hogy hogy minden a mi fajta. Szóval, mit gondolsz a legrosszabb esetében runtime buborék sort? Srácok, emlékszel? 

DIÁK: N mínusz 1. OKTATÓ: N mínusz 1. Annak érdekében, hogy azt jelenti, hogy n mínusz 1 összehasonlítást. Tehát az egyik dolog, hogy észre is hogy az első ismétlés, megyünk keresztül, összehasonlítjuk ezek two-- szóval ez 1. Ez a két, három, négy. Így aztán egy iteráció mi Már négy összehasonlítást. Amikor beszélek runtime és n. N jelentése az összehasonlítások száma függvényében, hogy hány elem van. OK? 

Így megy át, van négy. A következő alkalommal, amikor tudod, hogy mi nem kell intézni. Összevetjük a két, E két, ez a két, és ha nem volt, hogy optimalizálás a négy hurok, hogy én írtam, akkor lehet összehasonlítani az itt egyébként. Szóval kellett volna végigmenni a tömb , és n összehasonlítást n idő, mert minden alkalommal, amikor fuss keresztül mi fajta egy dolog. 

És minden alkalommal, amikor fut át a tömb teszünk n összehasonlítást. Így a runtime az, tulajdonképpen n négyzet, amely sokkal rosszabb a mi log végén, mert azt azt jelenti, hogy ha volt négy milliárd elemek, akkor fog minket négymilliárd négyzetes helyett 32. Tehát nem a legjobb runtime, de néhány dolgot, tudod, ha belül egy bizonyos tartományon elemek buborék sort lehet jól használható. 

OK. Szóval most mi a legjobb esetben futásidejű? Diák: Zero? Vagy 1? 

OKTATÓ: Tehát 1 lenne az egyik összehasonlítás. Right. 

DIÁK: N mínusz 1? 

Oktató: Szóval, igen. Tehát n mínusz 1. Amikor van egy koncepció, mint n mínusz 1, hajlamosak vagyunk csak csepp le és mi csak mondjuk n azért, mert van hogy összehasonlítsák az egyes these-- minden pár. Így lenne n mínusz 1, amelyhez mi lenne, csak mondjuk kb n. Amikor foglalkozó runtime, minden a közelíti. Mindaddig, amíg a kitevő helyes, te nagyon jó. 

Így is foglalkozni vele. Úgy, hogy a legjobb esetben n, amely azt jelenti, hogy a lista már rendezett, és minden, amit tennie, hogy végigmenni és ellenőrizze, hogy ez rendezett. Cool. Rendben van. Szóval mint látod itt, mi Csak még egy kis grafikon. Így n négyzeten. Fun. Sokkal rosszabb, mint n, mint látjuk, és sokkal, de sokkal rosszabb, mint a log 2n. És akkor is kap a napló naplók. És veszel 124, bejutni mint log csillag, ami olyan, mint egy őrült. Tehát, ha érdekel, keresési napló csillag. Ez a fajta szórakozás. Így van ez a nagy táblázat. Csak egy heads-up, ez a Csodálatos, hogy a diagram a középtávú mert hosszú kérdezni ezeket elvékonyodik. Tehát csak a heads-up, ezt a félidős a szép puskát ott. Szóval csak nézett bubble sort. Legrosszabb eset, n faragva, legjobb esetben, n. És megyünk, hogy nézd meg a többiek. 

És mint látható, az egyetlen az egyik, hogy valóban jól a merge sort, amit kapsz, hogy miért. Így fogunk menni a következő here-- kiválasztás sort. Tudja valaki emlékszik, hogyan kiválasztás sort dolgozott? Megy ez. 

Diák: Alapvetően megy át megrendelés és hozzon létre egy új listát. És ahogy te olyan elemek a, tedd őket a megfelelő helyre Az új listában. 

Oktató: Annak érdekében, hogy a hangok inkább beillesztés sort. De te nagyon közel van. Nagyon hasonló. Még én is őket néha összekeveredett. Mielőtt ez a rész volt, mint én, várjon. OK. Szóval, mit akarsz tennie kiválasztás sort, ahogy lehet gondolni róla, és az út Azt, hogy biztos, hogy megpróbál, hogy nem kap őket összekeverednek, ez megy át és kiválasztja a legkisebb számot és teszi, hogy az elején a lista. A swap azt, hogy az első helyen. Ők valójában egy példa számomra. Félelmetes. Tehát csak egy módja annak, hogy gondolni it-- kiválasztás sort, válassza ki a legkisebb érték. És megyünk fuss egy példán keresztül Azt hiszem, hogy segíteni fog, mert Azt hiszem, látvány mindig segít. Tehát elindul valami hogy teljesen nem válogatott. Red lesz válogatás nélkül, zöld lesz rendezve. Ez minden értelme a második. 

Így megy keresztül, és mi folyamatosan léptetjük az elejétől a végéig. És azt mondjuk, rendben van, 2 a legkisebb szám. Szóval megy, hogy a 2. és megyünk mozgatni, hogy az első a mi tömb mert a legkisebb szám van. Szóval, ez az, amit ez csinál itt. Ez csak fog cserélni a két. Tehát most már a rendezve rész és egy rendezetlen rész. És mi a jó emlékezni szelekciós sort a mi csak adja a nem válogatott rész. 

A rendezett rész hagyod egyedül. Mm-hm? 

Diák: Hogyan tudja, mi a a legkisebb, ha összevetjük azt minden más értéket a tömbben. Oktató: Ez nem összehasonlítani. Szeretjük kihagytam. Ez csak általános, átfogó. Igen. Amikor írunk a kódot vagyok Biztosan lesz még elégedett. De tárolja az első elem, mint a legkisebb. Összehasonlítani és azt mondják, OK, ez kisebb? Igen. Tartsd meg. Itt van ez a kisebb? Nem? 

Ez a legkisebb, újra ki kell jelölni, hogy az érték. És akkor sokkal boldogabb mikor megyünk át a kódot. Így megy át, cseréljük, így aztán nézzük ezt nem válogatott rész. Szóval majd válassza ki a három. Mi megy, hogy azt a a végén a mi rendezett rész. És mi csak fog tartani csinál hogy csinálja, és csinálja. Szóval ez a mi fajta pszeudokódja itt. Majd kódot fel itt egy másik. De csak valami járni keresztül egy magas szinten. Fogsz menni i értéke 0 és n mínusz 2. Ez egy másik optimalizálás. Ne aggódj túl sokat róla. Szóval mint mondtál. Ahogy Jacob mondott, hogyan is nyomon követni, hogy mi a minimum? Honnan tudjuk? Meg kell összehasonlítani minden listánkon. 

Tehát minimum értéke i. Ez csak azt mondom, ebben az esetben Az index a legkisebb érték. Akkor ez lesz a halad végig és megy a j értéke i + 1. Így már tudjuk, hogy ez az első elem. Nem kell, hogy hasonlítsa össze magát. Így kezd hasonlítsa össze a következő amely ezért ez az i + 1-től n- mínusz 1, ami a végén a tömb ott. És mi azt mondtuk, ha tömbbel j értéke kisebb, mint a tömb perc, akkor átrendelhet ahol a minimum indexek. 

És ha perc nem egyenlő, az i oda, ahol voltunk vissza ide. Tehát, mint amikor először tette ezt. Ebben az esetben ez kezdődik nulla, akkor a végén, hogy kettő. Tehát min nem egyenlő i a végén. Ez tudatja velünk, hogy meg kell cserélni őket. Úgy érzem magam, mint egy konkrét példa segít sokkal több, mint ez. Úgyhogy ezt a kódot fel srácok most, és azt hiszem, jobb lesz. 

Fajta hajlamosak így működik, hogy a ez gyakran jobb, csak látni őket. Szóval, mit akarunk csinálni az először akarjuk, hogy a legkisebb elem pozícióját a tömbben. Pontosan az, amit Jacob mondott. Meg kell tárolni, hogy valahogy. Így fogunk kezdeni itt iterációjával át a tömböt. Fogjuk mondani, hogy a mi először egy csak kezdeni. Tehát megy, hogy int legkisebb egyenlő tömbbel i. 

Tehát az egyik dolog, amit észre, minden amikor ez a ciklus végrehajtja, kezdjük egy lépéssel távolabb. Ha elkezdünk megnézzük ezt. A következő alkalommal, amikor halad végig, mi kezdve ezt rendeli, a legkisebb érték. Tehát nagyon hasonlít a buborék rendezés ahol tudjuk, hogy miután egy menetben, Ez utóbbi elem rendezve. A kiválasztás sort, ez éppen az ellenkezője. 

Minden pass, tudjuk, hogy az elsőt rendezve. Miután a második lépés, a második lesz rendezve. És ahogy láttam a dia példák a rendezett rész csak folyamatosan növekszik. Tehát kitűzésében legkisebb a tömb i, mind csinál A szűkítő milyen keresünk, így számának minimalizálása összehasonlítások tesszük. Van ennek értelme mindenki? Szüksége van rám, hogy fut át, hogy a ismét lassabban vagy más szavakkal? Örülök, hogy. OK. 

Szóval tárolása érték ezen a ponton, de mi is szeretnénk tárolni az index. Így megyünk tárolni a helyzete a legkisebb egy, ami csak lesz i. Tehát most Jacob teljesül. Van dolgokat tárolni. És most meg kell, hogy nézze át A szétválogatás nélkül része a tömbben. Tehát ebben az esetben ez a lenne a mi válogatás nélkül. Ez i. OK. 

Szóval, mit fogunk csinálni lesz egy hurok. Ha meg kell halad végig egy tömb, elméd lehetett menni a hurok. Így néhány int k equals-- mit gondolunk k fog egyenlő kezdeni? Ez az, amit mi meg, mint a legkisebb érték és szeretnénk összehasonlítani. Mit akarunk összehasonlítani, hogy? Ez lesz ez a következő egy, igaz? Ezért szeretnénk k inicializálni kell az i plusz 1-től indul. 

És azt akarjuk, k ebben az esetben már méret tárolt itt, így tudjuk csak használni méretét. Méret, hogy a méret a tömb. És mi csak szeretnénk frissítse k által egy-egy alkalommal. Cool. Tehát most meg kell találni A legkisebb elem itt. Tehát, ha halad végig, mi akarom mondani, ha a tömb k kevesebb, mint a legkisebb value-- ez az, ahol vagyunk valójában nyomon követése, hogy mi a A legkisebb here-- akkor szeretnénk átminősítése mi a legkisebb érték. 

Ez azt jelenti, hogy jaj, mi iterációjával át itt. Bármi érték itt nem a legkisebb dolog. Nem akarjuk azt. Azt akarjuk, hogy újra ki kell jelölni. Tehát, ha már átcsoportosításával, mit csinál Ön szerint lehet ezt a kódot itt? Szeretnénk átminősítése legkisebb és pozíció. Tehát mi az a legkisebb most? Diák: Array k. Oktató: Array k. És mi a helyzet most? Mi az indexek a legkisebb érték? Ez csak k. Szóval tömb k, k, azok megegyeznek. Így akartuk átminősítése azt. Aztán miután megtaláltuk a legkisebb, így a végén ez a for ciklus Itt azt találja, amit a legkisebbek érték, ezért csak azt cserélni. Ebben az esetben, mint mondjuk a mi legkisebb érték itt. Ez a legkisebb érték. 

Csak azt akarjuk cserélni azt itt, ami hogy mit swap alul tette, amit most írt fel együtt a pár perccel ezelőtt. Így kell kinéznie ismerős. És akkor csak navigálhat keresztül, amíg el nem éri az utat a végére, ami azt jelenti, hogy nulla elemeket, amelyek szétválogatás nélkül és minden más lett rendezve. Értelme? Egy kicsit konkrétabban? A kód segítségével? 

DIÁK: Egy méret, soha nem igazán meghatározni, vagy megváltoztatni, hogyan tudja? 

Oktató: Tehát az egyik dolog, hogy észre itt int méret. Szóval azt mondja ebben sort-- fajta egy olyan funkció, ebben case-- ez kiválasztás sort, ez elmúlt az a funkciója. Tehát, ha nem telt el az, akkor valamit csinálni mint a hossza a tömb vagy akkor halad végig hogy megtalálja a hosszát. De mivel ez elmúlt -ban, akkor csak használja azt. Csak feltételezik, hogy a felhasználó adta meg egy érvényes mérete valójában jelent a mérete a tömb. Cool? 

Ha a srácok semmi baj ezekkel a vagy többet szeretne gyakorlat kódolási fajta a saját, meg kell menj study.cs50. Ez egy eszköz. Nekik van egy ellenőrző, amely akkor valóban írni. Ők pszeudokódja. Ezek további videók és diák többek között az is használom itt. Tehát, ha még mindig érzi a kicsit homályos, próbáld ki azt. Mint mindig, gyere beszélj hozzám is. Kérdés? 

DIÁK: Azt mondod, az méret megfelel a korábban megadottaknak? OKTATÓ: Igen. A méret korábban meghatározott fel itt a függvény deklaráció. Szóval feltételezzük, hogy ez már átadott a felhasználó, és az egyszerűség kedvéért, fogjuk feltételezni, hogy a felhasználó adta a megfelelő méretet. Cool. Szóval ez a fajta kiválasztás. Srácok, tudom, hogy tanulunk sokat ma. Ez egy sűrű adatokat részben. Tehát, hogy mi lesz menni beillesztés sort. 

OK. Szóval mielőtt, hogy meg kell csinálni a runtime elemzés itt. Így a legjobb esetben, óta odaítélt megmutattam A tábla már fajta adta el. De a legjobb esetben futásidejű, mit gondolsz? Minden rendezve. N négyzeten. Bárki, aki magyarázatot miért gondolod? 

Diák: Te összehasonlítása through-- OKTATÓ: Így van. Te összehasonlítása útján. Minden iteráció, bár mi fogásvétel- csökkentéssel ez az egyik, még mindig keresi a mindent, hogy megtalálja a legkisebb. Tehát akkor is, ha a legkisebb érték itt az elején, még mindig hasonlítsa össze szemben minden más hogy megbizonyosodjon arról, hogy ez a legkisebb dolog. Szóval akkor a végén fut keresztül körülbelül n négyzeten alkalommal. Rendben van. És mi a legrosszabb esetben? Szintén n négyzetes mert mész hogy csinál, hogy ugyanezzel az eljárással. Így ebben az esetben, a kiválasztás sort valami hogy mi is nevezzük várható runtime. Így a többiek, mi csak tudjuk, a felső és az alsó határ. Attól függően, hogy a bolond lista vagy hogy válogatás nélkül van, ezek között változhat n vagy n négyzeten. Nem tudjuk. 

Hanem azért, mert a fajta kiválasztás ugyanaz legrosszabb és a legjobb eset, hogy azt mondja, hogy nem számít, hogy milyen típusú bemenet is van, hogy ez teljesen rendezve, vagy teljesen fordított sorrendje, ez fog tartani az azonos idő alatt. Tehát ebben az esetben, ha a emlékszem a mi asztal, hogy valóban volt olyan érték, ez a két fajta nem rendelkezik, ami várható futási. Tehát tudjuk, hogy ha futunk kiválasztás sort, ez garantáltan fuss egy n négyzeten idő. Nincs változékonyság létezik. Ez csak várt. És újra, ha meg akarja tanulni több, vegye CS 124 a tavaszi. Rendben van. Láttuk ezt. Cool. Így beillesztés sort. És én talán lesz hogy lángol át ezt. Nem akarom, hogy ti kódot is. Majd csak menj át rajta. Tehát beillesztés sort kedves A hasonló fajta kiválasztás az, hogy mind egy rendezetlen és rendezve része a tömb. 

De mi más az, hogy ahogy megy keresztül egy-egy, mi csak megteszi szám mellett van a mi válogatás nélkül, és helyesen rendezni a mi rendezett tömbben. Nem lesz több értelme egy példát. Tehát minden kezdődik a háztartási, Csakúgy, mint a kiválasztás sort. És fogunk rendezni ezt a növekvő sorrendben, ahogy kellett volna. Tehát első lépésben vesszük az első érték és azt mondjuk, OK, akkor most a listán magad. 

Mert ha van egy lista egyedül, akkor rendezve. Gratulálunk, hogy a első elem ebben a tömbben. Te már rendezve minden saját. Tehát most már a rendezve és egy rendezetlen tömb. Így most, hogy az első. Mi történik itt között és az, hogy azt mondjuk, OK, megyünk, hogy nézd meg a első érték a szétválogatás nélküli tömb és fogunk input hogy saját megfelelő helyen a rendezett tömbben. 

Tehát mi nem is veszünk 5 és azt mondjuk, OK, 5 nagyobb, mint 3, így csak helyezze megfelelő a jogot, hogy a. Vagyunk jó. Akkor megyünk tovább a következőre. És mi fog 2. Azt mondjuk, rendben van, 2 kisebb 3-nál, így tudjuk, hogy ez szükséges, hogy előtte a előtt a lista most. Mi tehát az, hogy mi nyomja a 3. és 5. lefelé és haladunk a 2 az első nyílásba. Szóval csak behelyezi a megfelelő helyre kell tenni. 

Akkor nézd meg következő, és azt mondjuk, 6. OK, 6 nagyobb, mint mindent a rendezett tömbben, így csak címkézni azt, hogy a végén. És akkor nézzük 4. 4 kisebb, mint 6, ez kevésbé mint 5, de ez nagyobb mint 3. Szóval csak nyomja mélyen a középső 3 és 5 közötti. Tehát, hogy ez egy kicsit bit konkrétabb, Itt a fajta a ötlet, hogy mi történt. Tehát minden osztályozatlan elem, mi határozza meg, ahol a rendezett rész az. 

Így szem előtt tartva a válogatni és osztályozatlan, van, hogy áthalad keresztül, és a szám ki hol illik a rendezett tömbben. És helyezze eltolásával a elemek jobbra le. És akkor már csak tartani iterációjával keresztül, amíg egy teljesen rendezett lista ahol osztályozatlan most nulla és rendezett veszi fel a teljes egészében a lista. Szóval, megint, hogy a dolgok még Pontosabban, van pszeudokódja. 

Tehát alapvetően az i egyenlő 0-n mínusz 1, hogy csak a hossza a tömb. Van néhány tényező, amely az egyenlő Az első tömb vagy az első indexek. Mi meg j egyenlő. Tehát miközben j nagyobb, mint nulla és a tömb, j mínusz 1 nagyobb, mint a elem, tehát minden, ami ezzel annak biztosítása, hogy A j képviseli igazán A szétválogatás nélkül része a tömb. 

Tehát miközben még mindig a dolgok rendezni és j mínusz egy ez-- mi az elem neki? J soha meg itt. Elég bosszantó. OK. Egyébként. Tehát j mínusz 1, akkor ellenőrzi az elem előtte. Azt mondod, OK, ez az elem előtt, ahol én am-- nézzük valójában dolgozzon ki ezt. Mondjuk ez mint a mi második menetben. Tehát én lesz egyenlő 1, ami itt van. 

Tehát én lesz 1-gyel egyenlő. Ez lenne a 2., 4., 5., 6., 7. Rendben van. Így a jelen esetben egyébként lesz egyenlő 4. És van néhány, ami j lesz egyenlő 1-gyel. Oh, j fogásvétel- csökkentéssel. Ez az, ami van. Így j egyenlő i, akkor mi ez mondás, hogy ahogy haladunk előre, mi csak így biztos hogy nem vagyunk át indexelése így amikor próbálunk beszúrni dolgokat a rendezett lista. 

Így, ha j értéke 1-gyel egyenlő, és ebben az esetben tömb j mínusz one-- olyan kitűnő j mínusz 1 2 ebben case-- ha ez nagyobb, mint az elem, akkor mindez csinál tolódik dolgokat. Tehát ebben az esetben, tömb j mínusz egy tömb nulla lenne, ami 2. 2 nem nagyobb, mint 4, így ez nem hajtja végre. Így a váltás nem mozdul lefelé. Mi ez itt csak mozog a rendezett tömbben le. Ebben az esetben valójában, mi lehetne do-- csináljunk 3. Tehát, ha mi vagyunk a séta a Ennél a példánál vagyunk most itt. Ez rendezve. Ez nem válogatott. Cool? Így i értéke 2, így mi elem egyenlő 3-mal. És a mi j értéke egyenlő 2. Szóval nézzük át, és mi azt mondják, OK, tömb j mínusz egy nagyobb, mint az elem hogy keresünk? És a válasz igen, ugye? 4 nagyobb, mint 3 és j 2, így ezt a kódot végrehajtja. 

Szóval, most mit teszünk egy tömbbel 2, így itt, mi cserélni őket. Szóval csak azt mondom, OK, array 2 most lesz 3. És j fog egyenlő j mínusz 1, amely az 1. Ez szörnyű, de srácok az ötlet. J jelentése most 1-gyel egyenlő. És tömb j csak lesz egyenlő a mi elem, ami 4. I törölt valamit, amit nem kellene van vagy miswrote valami, de a srácok az ötlet. 

A mozogni n. Aztán ha ez, akkor hurok újra és azt mondaná, rendben, j 1 most. És tömb j mínusz 1 most 2. 2 kisebb, mint a mi elem? Nem? Ez azt jelenti, hogy 've ki ez az elem a megfelelő hely a mi rendezett tömbben. Akkor ezt, és azt mondjuk, OK, a rendezett tömbben nem itt. És ez, hogy ezt a 6-os, és mint, OK, 6 kisebb, mint ez a szám? Nem? Cool. Jól vagyunk. 

Csináld újra. Azt mondjuk 7. 7, kevesebb, mint a végén a mi rendezett tömb? Nem. Így vagyunk jól. Tehát ez lenne rendezve. Alapvetően mindez nem van az mondja take az első eleme A osztályozatlan tömb, kitalálni, hová megy a rendezett tömbben. És ez csak ügyel swap erre. Te alapvetően csak csere amíg ez a jó helyen. A vizuális kép az, hogy te vagy mozgó mindent le csinálja. 

Szóval, ez olyan, mint fél sort buborék-szerű. Nézd meg tanulmány 50. Én nagyon ajánlom próbál kódra ezt a saját. Ha bármilyen kérdés vagy szeretné lásd a minta kódot beiktatási sort, kérem, tudassa velem. Én mindig körül. Így legrosszabb esetben runtime és legjobb esetben runtime. Ahogy a srác meglátta az asztalon már mutatta meg, ez mind a négyzeten n és n. 

Tehát egyfajta megy ki, hogy mit beszéltünk körülbelül a korábbi fajta, legrosszabb eset runtime az, hogy ha ez teljesen szétválogatott, meg kell összehasonlítani az összes ilyen n-szer. Mi egy csomó összehasonlítás mert ha ez fordított sorrendben, fogunk mondani, OK, ez ugyanaz, ez jó, és ez lesz, hogy össze kell hasonlítani szemben az első, hogy vissza kell másolni. És ahogy megkapjuk felé A farok végén van összehasonlítani, összehasonlítani, és összehasonlítani mindent. 

Így végül is körülbelül n négyzeten. Ha ez helyes, akkor azt mondják, OK, 2, te vagy a jó. 3, akkor, mint a 2. Te jó. 4, csak összehasonlítani a farok. Te jó. 6, hasonlítsa össze a farkát, akkor minden rendben van. Így minden helyszínen, ha ez már válogatni, még van egy összehasonlítás. Tehát csak az n. És mivel van egy legjobb esetben futásidejű n és legrosszabb futási n négyzet, nincs elvárt runtime. 

Ez csak attól függ, a káosz listánk van. És ismét egy másik grafikon és egy asztal. Tehát különbségek fajta. Én csak megy keresztül szél, én érzem, mi már beszéltünk alaposan arról, hogyan minden kedves A változó és összekapcsolni. Tehát egyesülésről sort az utolsó Fogom untatni srácok. Nekünk van egy szép színes képet. Így összeolvad sort egy rekurzív algoritmus. Szóval tudjátok, mi Egy rekurzív függvény? 

Bárki, aki akar mondani? Meg akarod próbálni? Tehát egy rekurzív függvény csak funkció, amely magát. Tehát, ha a srácok ismerős A Fibonacci-sorozat, ami ítélt rekurzív mert Ön a korábbi két és add össze őket kap a következő. Szóval rekurzív, mindig azt gondolom rekurzió, úgy, mint a spirál így Ön, mint a spirál bele. De ez csak egy függvény amely magát. 

És tényleg, nagyon gyorsan én megmutatja, milyen, hogy néz ki. Tehát itt rekurzív, ha megnézzük, ez a rekurzív módon összefoglalni több mint egy tömb. Tehát minden, amit tennie, mi összeg funkcióval összeg, hogy vesz egy méret és egy tömbben. És ha azt veszi észre, méret csökkenti az értéket egy-egy alkalommal. És igen, ha x egyenlő zero-- így ha a méret a tömb egyenlő zero-- visszatér nullára. 

Egyébként összefoglalja ezt utolsó eleme a tömb, majd vesz egy összeget a többi tömb. Szóval ez csak lebontva kisebb és kisebb problémák. Hosszú történet rövid, rekurzió, funkció, amely magát. Ha ez mind megvan ebből, ez az, amit a rekurzív függvény. Ha az előírtnál 51, akkor kap nagyon, nagyon kényelmes rekurzió. Ez nagyon klassz. Volt értelme a hasonló 03:00 egy éjszaka out. És én, mint, hogy miért még soha nem használja ezt? 

Tehát merge sort, alapvetően mit fog csinálni ez az fogja lebontani és törni lefelé, amíg ez csak egy elem. Az egyes elemek könnyen rendezni. Látjuk, hogy. Ha van egy elem, akkor már úgy rendezett. Így egy input n elemek ha n értéke kisebb, mint 2, csak azért, mert azt vissza eszközök ez 0 vagy 1. láttunk. Ezeket tekintik rendezett elemekkel. 

Egyébként szünet félbe. Rendezés az első felében, a második rendezni fél, majd egyesíti őket. Miért hívják merge sort. Tehát itt fogunk rendezni ezeket. Így tartjuk, hogy azokat míg a tömb mérete 1. Tehát, ha ez 1, akkor csak vissza mert ez egy rendezett tömbben, és ez a rendezett tömb, és ez a rendezett tömb, mi minden rendezve. Akkor mit teszünk, mi indítsa összevonással együtt. 

Szóval, ahogy tud gondolj összevonása is csak eltávolítani a kisebb száma az egyes al tömbök és csak hozzáfűzni azt, hogy a kialakult tömb. Tehát, ha meg itt, amikor már ezek a készletek már 4, 6, és 1. Ha azt akarjuk, hogy ezeket egyesíteni, megnézzük az első két és azt mondjuk, rendben van, 1 kisebb, megy az első. 4. és 6., nincs mit összehasonlítani azt, csak jelezd a végére. 

Amikor a kettőt összekapcsolják, mi csak hogy a kisebbik a két, így 1. És most vesszük a E két kisebb, így 2. Kisebb a két, 3. Kisebb a két, 4, 5, 6. Szóval csak húzza le ezeket. És mivel ők már szétválogatott korábban, csak egy összehasonlítás minden alkalommal. Tehát több kódot itt, csak képviselet. Szóval kezdődik a középső és Ön sort a bal és a jobb és akkor csak azokat egyesíteni. 

És nincs kód A merge itt. De ismét, ha megy tovább tanulmány 50, akkor lesz ott. Ellenkező esetben jön talk to me ha még mindig zavaros. Szóval jó dolog az, hogy legjobb esetben, legrosszabb esetben, és a várható futási mind a log n, ami sokkal jobb, mint voltunk láttam a többi a mi fajta. Láttuk n négyzeten és amit valójában hogy itt n log n, ami nagyszerű. 

Nézd meg, hogy sokkal jobb, hogy van. Egy ilyen szép görbe. Így sokkal hatékonyabb. Ha valaha is lehet, használat merge sort. Ez időt takarít meg. Aztán megint, mint már említettük, ha te meg az e tartomány alsó nem teszi azt sok a különbség. Ez akár több ezer és több ezer bemenet, akkor biztosan szeretne hatékonyabb algoritmus. És ismét, a mi kedves táblázat összes fajta, hogy a srácok ma tanult. 

Szóval tudom, hogy volt egy sűrű nap. Ez nem feltétlenül fog hogy segítsen a PSET. De én csak azt szeretném, hogy a felelősségi nyilatkozat e szakasz nem csupán a psets. Mindez az anyag igazságos játék a midterms. És akkor is, ha ezt továbbra is a CS, Ezek nagyon fontos alapvető hogy meg kellene tudni. Szóval néhány napon belül lesz kicsit PSET segítség, de néhány hét lesz sokkal inkább a tényleges tartalom hogy nem tűnik szuper hasznos az Ön számára most, de ígérem, ha továbbra is A lesz nagyon, nagyon hasznos. 

Szóval ez a rész. Le a vezeték. Csináltam egy percen belül. De megy. És lesz fánkot vagy édességet. Van valaki allergiás semmit, az úton? Tojás és a tej. Tehát egy fánk nem? OK. Rendben van. Csokoládé nincs? Starburst. Starbursts jó. OK. Mi lesz, hogy Csillagkeletkezési jövő héten majd. Ez az, amit hozok. Srácok, van egy nagy héten. Olvassa el spec. 

Hadd tudja, ha bármilyen kérdése van. Pset két évfolyamon kell ki az Ön által csütörtök. Ha bármilyen kérdése van arról, hogyan osztályozzák valami vagy miért osztályozva valamit, ahogy én nem, kérjük, írjon nekem, gyere velem beszélni. Én egy kicsit őrült ez héten, de ígérem Én továbbra is válaszolni 24 órán belül. Tehát van egy nagy hét, mindenki. Sok szerencsét a PSET.