Ræðumaður 1: Hey allir! Velkomin aftur til kafla. Svo fegin að sjá svo mörg ykkar bæði hér, og hver sem er að horfa á netinu. Svo, eins og venjulega velkominn. Ég vona að þú hefðir allt yndisleg helgi, fullur af hvíld, slökun. Það var falleg í gær. Svo ég vona að þú njóta utandyra. 

Svo fyrst par tilkynninga. Flokkun. Svo, flest ykkar ættu að hafa fengið að email frá mér um Scratch Pset þína, sem og fyrir flokkun á Pset 1. Svo, bara nokkra hluti. Vertu viss um að nota check50 í style50. Þetta er ætlað að vera úrræði fyrir ykkur, að ganga úr skugga um að þú ert að fá eins mörg stig eins og þú getur án óþörfu tapa þeim. Svo hlutir eins stíl eru mjög mikilvæg. Við erum að fara að taka burt fyrir það. Sumir af þú mega hafa þegar tók eftir því að frá Pset þínum. Og check50 er bara mjög auðveld leið til að ganga úr skugga um að við erum í raun að aftur hvað þarf að koma aftur til the notandi, og að allt er að vinna almennilega. 

Á annarri huga, tryggja þinn hlaða það til the réttur mappa. Það gerir líf mitt bara svolítið erfiðara ef þú sendir Pset 2 inná Pset 1 vegna þess að þegar ég sótt hlutina, þeir sæki ekki rétt. Og ég veit að það er lítið wonky í kerfi að venjast, en bara vera frábær varkár, ef aðeins fyrir mig, þannig að þegar þú ert að fá tölvupóst á eins 02:00 og ég er einkunnakerfi. Ef ekki því ég verð að líta allt í kring um Pset þína. Cool. 

Ég veit að það er snemma, en ég algerlega fékk tekið burt vörður með ritgerð sem er vegna á föstudaginn, þann prófessorar mínir voru bara eins, ó já. Mundu, þú hefur ritgerð vegna á föstudaginn. Svo, ég veit enginn finnst að hugsa um midterms, en fyrst quiz er 15. október, sem október er að hefjast í þessari viku. Svo það gæti verið fyrr en búist er allur. Svo að þú ert ekki kastað burt vörður þegar Ég nefni næstu viku kafla sem ó, quiz næstu viku þinn, hugsaði ég Ég myndi gefa þér smá meira af a höfuð núna. 

Svo, vandamál þitt sett, númer þrjú. Hvernig fólk hefur lesið sérstakur út af forvitni? OK. Við fengum nokkra. Konar niður frá síðustu viku en það er allt í lagi. Ég veit að það var fallegt út. Svo brjótast út. Ákveðið eftir að þú fá gert dag lesa sérstakur amk reyna eins sækja dreifingu kóða og keyra eins og fyrsta upphaflega hlutur sem þeir biðja um. Vegna þess að við erum að nota dreifingu kóða og bókasafn að við höfum aðeins verið að using-- --It er bara í annað skipti sem við höfum gert þetta Pset, brjálaður hlutir geta gerst með tækið þitt, og þú vilt að finna að út núna á móti síðar. 

Vegna þess að ef það er fimmtudagskvöld eða það er Miðvikudagskvöldið og fyrir sumir ástæða Búnaðurinn er bara ekki langar að hlaupa með á bókasafnið eða með dreifingu númer, sem þýðir þú getur ekki einu sinni byrjað að gera erfðaskrá. Þar sem þú getur ekki stöðva til að sjá hvort það virkar. Ekki ađ þitt vera fær til að sjá hvort það safnar. Þú vilt að gæta af þeim snemma í viku, þegar þú getur samt email mig eða einn af hinum TFS, og við getum fengið þá fastur. Vegna þess að þeir eru málefni sem eru að fara að stoppa þig frá því allir alvöru framfarir. Það er ekki eins og einn galla, að þú getur bara svona sleppa yfir. Ef þú ert að hafa mál með þinn tæki eða dreifingu kóða, þú vilt virkilega að fá að taka umönnun fyrr frekar en síðar. Svo jafnvel ef þú ert ekki ađ raun byrja kóðun, sækja dreifingu kóða, lesa sérstakur, ganga úr skugga um allt er að vinna þar. OK? Ef þú getur bara gert það, ég lofa líf þitt verður auðveldara. Og svo þú ert líklega að fara að gera það núna ekki satt? OK. Svo, einhverjar spurningar þarna? Allar logistic hlutir? Allir er gott? OK. 

Fyrirvari fyrir þau þú í herberginu og á netinu. Ég ætla að vera að reyna að skipta milli PowerPoint í tækið vegna þess að við erum að fara að vera að gera einhverja kóðun dag með eftirspurnar af nafnlaus tillaga kosning Ég sendi út í síðustu viku. Svo munum við vera að gera sumir kóðun. Svo ef þú krakkar vilja einnig að skjóta upp tæki þínum, og þú ættir að hafa fengið tölvupóst frá mér, með sýnishorn skrá. Vinsamlegast ekki hika við að gera það. 

Svo erum við að fara að tala um GDB, sem er aflúsara. Það er að fara að hjálpa þér konar reikna út hvar hlutirnir eru að fara úrskeiðis í kóðanum þínum. Það er í raun bara leið fyrir þig til að stíga gegnum númerið þitt eins og það er að gerast, og vera fær um að prenta út breytur eða sjá hvað er raunverulega að gerast undir hetta vers program bara að keyra, það er eins faulting, og þú ert eins og, ekki hugmynd hvað bara gerðist hér. Ég veit ekki hvað lína það ekki á. Ég veit ekki hvar það fór úrskeiðis. Svo, GDB er að fara að hjálpa þér með það. Einnig, ef þú ákveður að áfram já, og taka 61, það mun í raun, í raun að vera þitt besti vinur, því ég get sagt þér vegna þess að ég ætla að fara í gegnum þeim flokki. 

Við erum að fara að horfa á tvöfaldur leita, sem ef þú krakkar muna mikill símaskránni dæmi sjón af bekknum. Við munum vera að innleiða það, og ganga í gegnum það svolítið meira, og þá erum við að fara í gegnum fjögur mismunandi tegundir, sem eru Bubble, Val, innsetningu, og sameinast. Cool. Svo, GDB eins og ég nefndi, er aflúsara. Og þetta eru eins konar stór hluti, stóru aðgerðir eða skipanir sem þú notar innan gdb, og ég mun ganga þú gegnum kynningu um það í sekúndu. 

Svo, þetta er ekki bara fara að vera ágrip. Ég ætla að reyna og gera það sem steypu og mögulegt er fyrir ykkur. Svo, brjóta. Það verður annað hvort að vera brjóta eins, sumir tala, sem táknar línu í forritinu, eða þú getur kallað aðgerð. Svo, ef þú segir brjóta helstu, það hættir á helstu, og láta þig ganga í gegnum þessi virka. 

Sömuleiðis, ef þú hafa sumir utanaðkomandi virka eins Víxla eða Cube, að við skoðuðum í síðustu viku. Ef þú segir brýtur eitt af þeim, hvenær program hits að það mun bíða eftir þér að segja það hvað ég á að gera. Áður en það verður bara að framkvæma þannig að þú gæti raunverulega stíga inn í aðgerð og sjá hvað er að gerast. Svo, Next, bara sleppa yfir næsta lína, fer yfir aðgerðir. Step. Þetta eru allar litlu ágrip. Svo ég ætla bara að fara að hlaupa í gegnum þá, en þú munt sjá þá í notkun í annarri. 

Stíga inn í aðgerð. Svo eins og ég var að segja, eins og með Víxla, myndi það leyfa þú til raunverulega eins og ef þú ert eins líkamlega stepping inni, þú getur klúðrar með þeim breytum, prenta hvað þeir eru, sjá hvað er að gerast. Listi mun bókstaflega bara prenta út umhverfis kóða. Svo ef þú gleymir konar hvar þú ert í forritinu, eða þú ert að velta fyrir mér hvað er að gerast í kringum það, þetta mun bara prenta út hluti af eins og fimm eða sex línur í kringum hana. Svo er hægt að fá stilla um hvar þú ert. 

Prenta sumir breytu. Svo ef þú hefur lykillinn eins í keisaranum sem við munum líta á. Þú getur sagt Prenta takkann á hverjum tímapunkti. Það mun segja þér hvaða gildi er svo að kannski einhvers staðar á leiðinni, þú overwrote lykil. Þú getur í raun sagt að vegna þess að þú getur raunverulega sjá að gildi. 

Í heimamenn, bara framköllun út staðbundnar breytur þínar. Svo, hvenær þú ert innan lykkju og þú vilt bara til að sjá eins og ó. Hvað er ég mitt? Hvað er þetta lykill gildi að ég frumstilla hér? Hver er boðskapurinn á þessum tímapunkti? Það verður bara að prenta allt af þeim, svo að þér þarft ekki að sig segja, Print I. Print Message. Print Key. Og þá sýna. Hvað það gerir er eins og þú stíga í gegnum forritið, Það verður bara að ganga úr skugga um að það er sýna einhverja ákveðna breytu á hverjum stað. Svo að þú also-- --it er konar smákaka þar þú þarft ekki að halda áfram eins og, ó. Print Key eða Print I. Það bara mun sjálfkrafa gera það fyrir þig. 

Svo, með það, við erum að fara til að sjá hvernig þetta fer. Ég ætla að reyna og skipta yfir til tæki minn. Sjá hvort ég get gert þetta. Allir. Við erum bara að fara að spegla það. Það er ekkert brjálaður á minn laptop engu að síður. OK. Þetta þarf að vera svona einn. Það er svo lítið. Við skulum sjá hvort við getum gert þetta. 

OK. Alice er augljóslega erfiðleikum hér bara svolítið, en við munum fá það í momento. OK. Við erum bara að fara að auka þetta. OK. Geta allir konar sjá að? Kannski svolítið? Ég veit að það er svolítið lítil. Þú getur ekki alveg reikna út hvernig á að gera þetta stærra. Ef einhver veit. Hefur einhver veit hvernig á að gera það stærri? OK. Við erum að fara að rúlla með það. Skiptir ekki máli hvort eð því það er bara það er kóðinn sem þú krakkar ættu hafa. 

Hvað er mikilvægara er flugstöðinni hér. Og við höfum hér Hvers vegna er það svo lítið? Stillingar. Oh. True Ike. Hvernig er þetta? Þarna. Er það betra fyrir alla? OK ,. Cool. 

Þú veist þegar þú ert í CS flokki tæknilegir erfiðleikar eru eins konar hluti af the-- Svo skulum við hreinsa þetta. OK. Svo, hérna í kafla, sem við höfðum hér. Caesar er executable skrá. Svo ég gerði það. Svo eitt að átta sig með GDB er að það virkar aðeins á executable skrá. Svo getur þú ekki keyrt hana á dotsy. Þú þarft að raunverulega gera viss um að kóðinn þinn safnar, og að það getur í raun að keyra. 

Svo, ganga úr skugga um að ef það virkar ekki saman, fá það til að safna saman, þannig að þú getur konar hlaupa í gegnum það. Svo, til að byrja GDB, allt sem þú gerir, Gloria tegund GDB, og þá bara skrá sem þú vilt. Ég stafa vitlaust alltaf Caesar. En þú vilt ganga úr skugga um þar sem það er óákveðinn greinir í ensku executable, punktur glampi Ti, svo að þýðir að þú ert að fara að keyra CSI þú ert að fara að framkvæma þetta skrá annaðhvort með aflúsara. OK. Svo, þú þarft að þú færð þessu tagi gibberish. Það er bara allt um aflúsara. Þú þarft í raun ekki að hafa áhyggjur af því núna. Og eins og þú sérð, höfum við á þessu opna parens landsframleiðslan, loka parens, og bara svona lítur eins stjórn lína okkar, ekki satt? 

Svo, það sem við viljum að do-- --So, Það fyrsta sem er að við viljum að velja staður til að brjóta það. Svo, það er einn padda í þessu Caesar áætlun sem ég kynna að við erum að fara að finna út. Hann það sem hann gerir er að það tekur inntak Barfoo í öllum húfur, og fyrir sumir ástæða það breytir ekki A. Það fer bara það eitt og sér, er allt annað rétt, en annað bréf A óbreytt. Svo erum við að fara að reyna að reikna út hvers vegna það er. Svo, the fyrstur hlutur þú venjulega vilja til að gera þegar þú byrjar á gdb er að reikna út hvar á að brjóta það. 

Svo er Caesar ansi stutt program. Við höfum bara eina aðgerð, ekki satt? Hvað var virka okkar í keisarans? Það er aðeins ein aðgerð, Main satt? Main er fall fyrir öll forrit. Ef þú myndað af did ekki hafa helstu, gæti ég vera smá áhyggjur núna, en ég vona að þú hefðir allt Main þar. Svo, hvað við getum gert er að við getum bara brjóta helstu, bara svona. Svo segir það, OK. Við setjum breakpoint einn okkar þar. 

Svo, nú hlutur til muna er Caesar tekur einn stjórn rök lína rétt og við höfum ekki gert það einhvers staðar enn. Svo, hvað þú gerir er þegar þú ferð í raun að keyra The program, hvaða forrit sem þú ert gangi í gdb sem þarf stjórn lína rök, ert þú að fara að inntak þegar þú byrjar fyrst að keyra hana. Svo, í þessu tilfelli, gera við Hlaupa með lykill af þremur. Og það mun í raun að byrja. 

Svo ef þú sérð hér, höfum við Ef RC er ekki jafnt og 2. Svo ef þú krakkar hafa allir þessi skrá sem ég sendi út allt þú munt sjá að það er eins og Fyrsta lína Meginhlutverk okkar, ekki satt? Það er að haka við að sjá hvort við höfum réttan fjölda rök. Svo, ef þú ert að velta fyrir mér ef RC er rétt, þú getur gert eitthvað bara eins Print RC. RC er tveir, sem er hvað við ráð fyrir, ekki satt? 

Svo getum við farið á Next, og halda áfram í gegnum. Svo höfum við nokkur lykil þar. Og við getum prentað út lykill okkar til að tryggja það er rétt. Interesting. Ekki alveg það sem við bjuggumst við. Svo eitt að gera sér grein fyrir með gdb Einnig er að það er ekki fyrr en þú högg í raun Next, að línan sem þú sást bara er í raun framkvæmt. Svo, í þessu tilfelli Key hefur ekki verið úthlutað ennþá. Svo, Key er sumir sorp gildi sem þú sérð á the botn þar. Neikvætt $ 120-- --It er einn milljarð og eitthvað stakur hlutina rétt? Það er ekki lykillinn sem við bjuggumst við. En ef við högg á Next og þá erum við reyna Print takkann, er það þrisvar. 

Allir sjá að? Svo ef þú færð eitthvað að þú ert eins og, bíddu. Þetta er alveg rangt, og ég veit ekki hvernig þetta myndi gerast því allt sem ég vil að gera er að tengja símanúmer, breytu, reyna hitting Next, reyna prentun það aftur og sjá hvort það virkar. Því það er bara að fara að framkvæma og reyndar framselja eitthvað eftir yður högg á Next. Skynsamleg fyrir alla? Uh ha? 

Ræðumaður 2: Þegar þú handahófi tölur hvað þýðir það? 

Ræðumaður 1: Það er bara af handahófi. Það er bara sorp. Það er bara eitthvað sem þinn tölvan mun handahófi úthluta. Cool. Svo nú getum við fara í gegnum, og svo nú höfum við þetta látlaus texta GetString. Svo láta mig kynna bara hvað mun gerast þegar við högg Next hér. GDB okkar konar hverfur, ekki satt? Það er vegna þess að GetString er nú framkvæmd, ekki satt? Svo, þegar við sáum texta jafngildir GetString, opin parens og parens, og við högg Next, sem hefur reyndar keyrð núna. Svo, það er að bíða eftir okkur að inntak eitthvað. 

Svo erum við að fara að inntak mat okkar sem er það sem það er galli sem ég sagði þér og það bara segir að það er lokið framkvæmd, að lokað krappi þýðir að það er spennandi út úr því lykkja. Svo getum við högg Next, og nú, eins og ég er viss um að þú ert allur þekki frá keisarans, þetta er, hvað er þessi lína að fara að gera. Það er fyrir Int I er 0, N jafngildir Strlen, texta, og þá I er minna en n, I, auk, plús. Hvað er þetta lykkja fara að gera? Opnaðu skilaboðin. Cool. Svo, við skulum byrja að gera það. 

Svo ætti þetta ástand passa, fyrir fyrsta einn okkar? Ef það er B, það er látlaus texti I. Við hægt að fá upplýsingar um heimamenn okkar. Svo, ég er núll, og ef sex, sem við gerum ráð fyrir, og lykill okkar er þriggja. Allt sem skynsamleg, ekki satt? Þær tölur eru allar nákvæmlega hvað þeir ættu að vera. Svo, raula? Ræðumaður 3: Ég hef handahófi tölur fyrir minn. Ræðumaður 1: Jæja, við getum check-- --we geta spjallað um það í sekúndu. En þú ættir að vera að fá þetta. Svo ef við höfum fjármagn B fyrir fyrsta okkar, þetta ástand ætti skilið það, ekki satt? Svo, ef við högg Next, sjáum við að þetta Ef keyrir raun. Vegna þess að ef þú ert að elta eftir í kóðanum þínum, þessi lína hér, þar látlaus texti I er skipt út með þessum tölur, aðeins framkvæmir ef if ástand er rétt ekki satt? 

GDB er bara að fara að sýna þér hlutir sem eru í raun framkvæmd. Þannig að ef þetta ef ástand var ekki fullnægt, það er bara að fara til að sleppa í næstu línu. OK? Svo höfum við það. Þessi krappi þýðir að það er lokað út af því að lykkja núna. Svo það er að fara að byrja aftur. Bara svona. Svo að við getum fengið upplýsingar um heimamenn okkar hér, og við sjáum að fyrstu okkar bréf hefur breyst, ekki satt? Það er nú E, eins og það ætti að vera. Svo getum við haldið áfram á. 

Og við höfum þessa ávísun. Og þetta stöðva ætti að vinna, ekki satt? Það er A. Það ætti að breyta þrír stafir áfram. En ef þú tekur eftir, við fá eitthvað öðruvísi. Þannig að í þessu tilfelli hér, tók um hann það, og svo þessi lína keyrð, sem breytt B. okkar En, í þessu tilfelli hér, við höfum það sleppt bara það, og fór á [? L Siff. ?] Svo eitthvað er að gerast þar. Hvað það er að segja þér er að, við vitum að það ætti skilið hér, en það er ekki. Getur einhver séð hvað okkar Vandamálið er í þeirri línu? Það er mjög mínútu hlutur. Og þú getur líka að líta á kóðann þinn. Það er líka line-- gleyma hvaða línu það er í there-- en það er í [inaudible]. Já? 

Ræðumaður 4: Það er á meira en síðu ef þú lest það í bókinni. Ræðumaður 1: Einmitt. Svo, aflúsara gat ekki sagt þú það, en aflúsara gætu fengið þig niður að línu að þú veist er ekki að virka. Og stundum, þegar sérstaklega síðar í önn, þegar þú ert að takast á við hundrað, a hundrað nokkrar línur af kóða, og þú veit ekki hvar það er galli, þetta er frábær leið til að gera það. Svo fannst okkur galla okkar. Þú getur lagað það í skrána, og þá gætir þú keyrt það aftur, og allt myndi vinna fullkomlega. Og stærsta málið er þetta getur virst eins og, OK. Já. Cool. Þú vissir hvað þú ert að leita að. Svo, þú vissir hvað ég á að gera. 

GDB má frábær gagnlegt vegna þess að þú getur prentað út alla þessa hluti, sem þú væri ekki. Það er miklu meira gagni en printf. Hversu margir af þú notar eins printf yfirlýsingar að reikna út hvar villa var, ekki satt? Svo, með þetta, þú ert ekki þarf að fara til baka, og eins athugasemd í Printf eða athugasemdir út, og reikna út hvað þú ættir að vera að prenta. Þetta í raun bara leyfa þér að stíga gegnum, prenta út hluti eins og þú ert að fara í gegnum, svo, þú getur fylgjast með hvernig þeir breytast í rauntíma, sem kerfið er í gangi. 

Og það þýðir að taka smá hluti af að sættast við. Ég vildi mjög mæla með bara svona að vera svolítið svekktur með það fyrir núna. Ef þú eyðir klukkutíma yfir í næstu viku að læra hvernig á að nota GDB, þú verður að vista sjálfur svo miklum tíma síðar. Og bókstaflega. við segja þetta fólk á hverju ári, og ég man þegar ég tók flokki, ég var eins og, Ég mun vera í lagi. No. Pset 6 kom á og ég var eins, ég ætla að læra hvernig á að nota GDB því ég ekki vita hvað er að gerast hér. 

Þannig að ef þú takir þér tíma svo nota það á minni verkefnum að þú ert að fara til vera vinna á, eins og að vinna gegnum eitthvað eins Visionare, svona. Eða ef þú vilt auka æfa, ég er viss um Ég gæti komið upp með gallaðir forrit, fyrir þig að kemba ef þú vilt. 

En ef þú tekur bara einhvern tíma að fá venjast því, bara að leika í kring með það, það verður í raun að þjóna þér vel. Og það er í raun einn af Þeir hlutir sem þú bara verð að reyna, og fá þinn snertið ekki óhrein með, áður en þú skilur það í raun. I raun aðeins skilið það einu sinni Ég þurfti að kemba hluti með það, og það er miklu betur að hafa hugmynd um hvernig á að kemba fyrr en síðar. OK. Cool. Ég veit það er góður af eins og a hrun námskeið í GDB, og ég mun örugglega vinna á getting þessir að líta stærri næst. Cool. 

Svo ef við förum aftur til PowerPoint okkar. Er þetta að fara að vinna? Awh. Já. OK. Svo, ef þú alltaf þörf einhverju þá aftur, það er á listanum. Svo Binary Search, sem allir minnist mikla sjón Davíðs stórfínn bækur símann í tvennt. Ég í raun ekki fá sími bækur lengur, vegna eins og hvar heldur þú fá bækur símann þessa dagana? Ég virkilega veit ekki. The Binary Search. Hefur einhver man hvernig Binary Search virkar? Einhver yfirleitt? Já? Ræðumaður 5: Þú veist þegar þú horfir á sem helmingur það væri í, byggist á því, og losna við hinn helminginn. 

Ræðumaður 1 Nákvæmlega. Svo, Binary Search, það er góður af a-- --we kalla það skipta og sigra. Svo, hvað þú munt gera er þú munt líta í miðjunni, og þú munt sjá ef það passar hvað þú ert að leita að. Og ef það virkar ekki, þá reyna að reikna út, er það að fara að vera vinstri helmingur eða rétt helmingur. Svo, þetta gæti verið ef þú ert að leita á eitthvað sem er alphabetized, þú sérð, ó. Er Allison koma fyrir M? Já. Svo erum við að fara að líta á fyrri hluta ársins. 

Eða það gæti verið eins og með tölum. Nokkuð sem þú getur bera saman, það geta vera flokkaður. Þú getur notað tvöfaldur leita á. Svo, einhver man þetta línurit eða hvað þetta er? Það er Asymptotic Þyngdarstig. Svo þetta línurit bara lýsir hversu lengi það tekur þig að leysa vandamál eins og þú aukið fjölda af hlutum að þú ert að nota. 

Svo höfum við N, sem er línuleg tími. Ef N yfir tveimur, sem er lítillega betri, enn vex frábær fljótur. Og þá höfum við tenging, sem er það sem við teljum Tvíundarleit. Ef við tökum eftir, sem vandamál þitt fær mikið og miklu stærri, tíminn sem það tekur þig að leysa það ekki raunverulega auka það mikið. Það er eins og sambærileg hér í upphafi. Þú ert eins og, OK. Nokkuð hér er í raun ekki Sama hvort er notað, en þú færð út til milljón, milljarð. Þú ert að reyna að finna some-- --you're reyna að finna nál í Heysátan. 

Ég held að þú viljir þetta vandamál. Þú vilt þetta flókið, ekki línuleg því fyrir allt sem þú vita ætla þín vera að leita í gegnum hver einstaklingur nál, hlutur af heyi, reyna að leita að nálinni þína. Og það er ekki of gaman að mínu mati. Mér líkar hratt. Ég eins duglegur. Og eins hardworking nemendur ÞIG krakkar eru, þú veist vinna betri, ekki erfiðara tegund hlutur, hvernig þér getur gert upp þessi reiknirit. 

Svo erum við að fara að ganga gegnum bara fljótur dæmi. Ég held að þú krakkar ættu að hafa a hönd á Binary Search, en ef einhver er a lítill loðinn, langar að styrkja það, við erum að fara að fara bara gegnum dæmi hér. Svo, við erum að leita ef array inniheldur sjö. 

Svo, fyrsta sem við gerum er líta í miðju, ekki satt? Og einnig þú ert að fara að vera erfðaskrá Tvöfaldur Leita í bara annað. Svo það er að fara að vera skemmtilegt. Þannig að við að líta í miðja lítið fylki 3. Er 3 jafnir 7? Gerir það ekki. Það er sex. Svo er það minna en eða meiri en sjö? Minna en. Já. Nice starf krakkar. Mér finnst ég eins og ég ætti hafa nammi því ég langar að kasta út í metra. Það er það sem ég er að fara að gera í næstu viku. Það mun halda ykkur skarpur. 

Svo henda við í burtu því fyrri helmingi, ekki satt? það var minna en. við vitum að allt á þeirri vinstri hönd er að fara að vera minna en það sem við erum í raun að leita að. Svo, það er engin þörf á að borga eftirtekt til það. Bara gleyma óður í það. Svo nú erum við að líta á hægri hönd okkar hlið, og við skoðum miðjuna þarna, og nú er það níu. Svo, 9 is-- --Everyone? Meiri en það sem við erum leita að, ekki satt? Svo erum við að fara að kasta burt allt til hægri. Eins og þessi. Nú eru allir sem við vinstri með er einn. Þannig að við að athuga er þetta eitt, hvað við erum að leita að? það er. Við fundum það sem við vildum. Þannig að við erum að gera. Bilinear Search. 

Og ef þú tekur eftir, við átti sjö inntak þar. Það tók ekki nema okkur eins þrisvar sinnum, en ef þú ert að gera eins og milljarð, þú krakkar vita hversu mörg skref það væri taka ef við hefðum fjóra milljarða hluti? Allar getgátur? Það er 32. 32 Leiðir til að finna eitthvað í fjóra milljarða þátturinn array vegna veldi af tveimur. Svo tvö er að 32, er í fjóra milljarða. 

Svo falleg brjálaður hvernig þú ert enn innan eins nokkuð fáeinum skrefum að finna eitthvað í fjóra milljarða atriði. Svo á að huga, við erum fara að kóða þetta svo þú krakkar geta raunverulega konar sjá hvernig þetta virkar. Allt í lagi, svo þú krakkar geta kóða. Ég ætla að láta ykkur tala um smá. Fá að kynnast fólki í kringum þig, sem er hvað einhver vildi frá síðasta kafla. 

Svo fá að vita að fólk í kringum þig. Tala í smá. Og allt sem ég vil frá þér krakkar er núna bara reyna að búa til yfirlit yfir sauðakóða. OK? Whoa. Allt sem ég vil frá ykkur er að þú ert bara að fara til að fylla í þetta þegar tilfelli. Þannig að ég hef sett þetta efri og lægri mörk sem tákna upphaf og lok array okkar. Og þú ert að fara til raunverulega lykkja í gegnum og reikna út hvað við erum að gera innan þessa meðan lykkja. 

Svo ef þú getur fundið out-- ég hef vísbending there-- hvað eru tilfelli að við höfum hér? Svo ef þú vilt að reikna út tilvikum munum við sauðakóða þeim og þá munum við í raun að kóða þau. Og það er að fara að vera, ég hugsa, vonandi það verður vera svolítið auðveldara en þú átt von á. Vegna þess að það er ekki það mikið kóða, reyndar, sem er mjög flott. 

Mm-HM? 

Nemandi: [inaudible]? Umsjón: Já. Það var eitthvað að finna í miðju. 

Nemandi: Svo við getum notað það. OK. 

Umsjón: Perfect. Svo er það fyrsta sem við þurfum að gera. Svo að finna miðjuna. Great. Svo þú ert með hugmynd um hvernig við gætum í raun að finna miðju með kóða? 

Nemandi: Já. n yfir 2? Umsjón: So n yfir 2. Svo er eitt sem þarf að muna að efri og neðri mörk breytast. Við höldum að þrengja hluta í fylkinu við erum að leita að. Svo n yfir 2 mun aðeins vinna í fyrsta sem við gerum. Svo taka efri og neðri mið, hvernig gætum við fengið að miðju þáttur? Vegna þess að við viljum að miðju milli efri og neðri, ekki satt? Mm-HM? 

Nemandi: [inaudible]. 

Umsjón: Þannig að við höfum sumir miðju. Og það verður efri plús minni á 2. Ógnvekjandi. There við förum. Ein lína niður. Þú krakkar eru á vegi þínum. Svo nú er að við höfum okkar miðja, hvað viljum við gera? Bara almennt. Þú þarft ekki að kóða það. Já. Nemandi: [inaudible]? Umsjón: Svo það er plús vegna þess að þú ert finna meðaltal á milli tveggja af þeim. Svo ef þú hugsa um þá eins konar auka í frá hliðum, hugsa um það eins og þú nálgast miðju, þú vilt svona. Svo ef þú varst á hvorri hlið af the miðja, og við höfum eins og 5 og 7. Þegar þú bætir við þeim saman þér fá 12, skipta þér um 2, er 6. 

Stundum er það erfitt að útskýra hvers vegna það virkar, en ef þú vinnur í gegnum dæmi stundum, það mun hjálpa þér að reikna út ef það ætti að vera plús eða mínus. Já. 

Nemandi: [inaudible] nákvæmlega í miðju ef þeir höfðu að ræða þar það er a einhver fjöldi af minni númer og eins og ein stór tala? 

Umsjón: Svo allt sem þú þarft er miðja fylkisins. Svo ef þú átt fullt af litlum tölum og síðan einn mjög stór tala í lok, er það ekki máli. Allt sem skiptir máli er að þeir eru raðað, þú bara langar að horfa á miðju array vegna þess að þú ert enn sneið vandamál í tvennt. Cool. Svo nú er að við höfum miðja, hvað gerum við næst? 

Nemandi: Bera saman. Umsjón: The bera saman. Svo bera miðsvæðið value_wanted. Cool. Svo þú sérð hér að við höfum þetta gildi við viljum hér. Muna þetta er fylki. Svo vísar miðja til vísitölu. Þannig að við viljum gera gildi miðju. Ekki gleyma ef þú vilt að bera saman, tvöfaldir jafn. Þú gerir einn jafngildir þú ert bara að fara að breyta henni, og þá, að sjálfsögðu, það er fara að vera gildið sem þú vilt. Svo gera það ekki. 

Þannig að við erum að fara að sjá hvort gildin á miðju er jöfn að verðmæti við viljum. Ekki gleyma axlabönd þínum. Dropbox ætti að fara í burtu. Svo hvað eigum við að gera í þessu tilfelli? Ef það er það viljum við aftur? Við erum að reyna að segja. 

Nemandi: prenta út. 

Umsjón: Jæja, við vil ekki að prenta út. Þannig að þetta er bool hér, svo vér vilja til að fara aftur satt eða ósatt. Við erum að segja, er þetta númer er [? RRA? ?] Svo ef það er, við aftur bara það satt. Ef ég getur stafa satt. 

Nemandi: Hvers vegna vildi þú ekki aftur núll? Umsjón: Svo þú gætir skila núll ef þú vildir. En í þessu máli þar sem Fallið okkar skilar bool, við þurfum að skila annað hvort sönn eða ósönn. Nemandi: Þegar þú ert segja Boolean tjáningu, getur þú sett það jafn ósatt? Eins og ef ég á að segja, ef þetta ástand er ekki fullnægt, eins er efri jafngildir ósatt. Mun það skilja ef þú bara setja rangar á hinni hliðinni? Umsjón: Já. Svo reyndar ef þú ert alltaf að gera eitthvað eins er efri eða lægri, sem skilar satt eða ósatt og það er í raun slæmt stíl til segjum jafnt jafnt satt eða jafn jafngildir falskur. Þú vilt nota þessi niðurstaða eins sig sem stöðva þinn. Ekki það sem ég vildi. Það er það sem ég vildi. Svo í að ræða og þú ert að spyrja um eitthvað svona vista þetta í c. 

Þannig að ef við höfum int helstu (tóm) og eitthvað svona. Og þú hefur ef er efri sumra inntak og þú ert spyrja hvort þú getur gert eitthvað eins og þetta? Hægri? Nemandi: Ég var að reyna að gera það [inaudible]. Vegna þess að ef it's-- Umsjón: Hægri. Svo þú vilt að þetta sé rangt, ekki satt? Nemandi: Já. Umsjón: Þannig að í þessu tilfelli þú vilja það til að framkvæma ef það er ekki satt. Svo kaldur hlutur sem þú gerir það er þetta. Svo man upphrópunarmerki lið negates hluti? Það segir [inaudible] þýðir ekki. Þannig að ef við skoðum bara þessi hluti hér, að þú vilt segja að metur að rangar eins og þú vilt hafa það til. Ekki rangar er sönn sem þýðir þetta myndi framkvæma. Er að skynsamleg? Nemandi: Já. Umsjón: Awesome. OK. Þannig að við gætum bara aftur satt í þessu tilviki. Svo nú höfum við tvö önnur tilvik í þessu tilfelli. Hvað eru tveir aðrir mál okkar? Skulum bara gera það með þessum hætti. Svo skulum byrja á annað Ef gildi á miðju er minna en gildið sem við viljum. Svo er gildi okkar í miðjunni minna en gildið sem við erum að leita að. 

Svo sem bindur gera þér held að við viljum uppfæra? Efri eða neðri? Upper? Svo sem megin í fylkinu erum við að fara að vera að horfa á? 

Nemandi: Neðri. 

Umsjón: Við erum að fara að vera að horfa á vinstri. Svo annað ef lítið gildi er minna. Svo miðju gildi þitt hér er minna en það sem við viljum. Þannig að við viljum taka Hægri hlið array okkar. Þannig að við erum að fara að uppfæra neðri mörk okkar. Þannig að við munum endurúthluta okkar lægri. Og hvað finnst þér lægri ætti að vera? Nemandi: The Middle gildi? Umsjón: Svo miðja value-- Nemandi: Plus 1. Umsjón: --plus 1. Getur einhver sagt mér hvers vegna við höfum sem plús 1? 

Nemandi: [? No gildi?] er jafnt því. 

Umsjón: Hægri. Þar sem við vitum nú þegar að miðja gildi okkar er ekki jafnt og það og við viljum útiloka það frá öllum síðari leitum. Ef þú gleymir að plús 1, þetta verður eins lykkja endalaust. Og þú munt bara vera veiddur í óendanlega lykkja og þá munt segfault og hlutirnir fara illa. Svo alltaf að tryggja að þú ert ekki þ.mt gildi sem þú bara horfði á. Þannig að við að gæta um það með plús 1. 

Svo nú höfum við síðustu ástand okkar sem ég alltaf fyrir öryggi sakir þú getur athugað hér, annars ef verð í miðjunni er meiri en gildið við viljum. Það þýðir að við viljum vinstri hönd hálfa. Svo sem einn erum við að fara að uppfæra? Efri. Og hvað er þetta einn að fara til að jafna? Middle mínus 1 vegna þess, að sjálfsögðu, að við viljum að ganga úr skugga um að við erum ekki horfa á þessi miðju gildi aftur. Og þá höfum við það. Það er hann. Það er allt tvöfaldur leit. Það er ekki svo slæmt, ekki satt? Það er eins og 10 línur af kóðann með hvítt rúm. Svo mjög öflugur, mjög gagnlegt, þú verður vera með það í eitt af síðari psets þínum. Kannski ekki þessu, en síðar. Svo að læra það. Elska það. Það mun við þig vel. Svo hjartarskinn einhver hafa allir spurningar um tvöfaldur leit? Já. 

Nemandi: Skiptir máli hvort n er jafnvel eða stakur? 

Umsjón: Nei Þar sem við kastaði það til miðju eins int, það verður bara HÃ það. Þannig að það mun vera heiltölu og það mun lokum raða í gegnum allt. Svo þú þarft ekki að hafa áhyggjur óður í það. Allir góður? Ógnvekjandi. Cool. Svo, þú krakkar fékk þetta. Slideshow. Svo eins og við vorum að tala um, ég veit David getið flókið runtimes. 

Svo í besta tilfelli, það er bara einn, sem við köllum föstu tíma. Getur einhver sagt mér hvers vegna það gæti verið? Hvaða tegund af atburðarás væri að för með sér? Mm-HM. 

Nemandi: [inaudible] first-- Umsjón: Svo miðju vera Fyrsta þáttur sem við komum til, ekki satt? Svo annað hvort fylki eitt eða hvað sem við erum að leita að bara gerist að vera smack DAB í miðju. Svo er það besta mál okkar. Þú færð í alvöru vandamál, sennilega ekki fara að ná [inaudible] að oft. Hvað um versta tilfelli okkar? Versta tilfelli okkar er Log n. Og það hefur að gera með allt veldi af tveimur hlutur sem ég talaði um. 

Svo í versta tilfelli myndi þýða sem við þurftum að höggva array niður þar til það var þáttur í einn. Þannig að við þurftum að höggva það niður í tvennt eins oft og við gátum hugsanlega. Þess vegna er Log n vegna þú halda bara deila með tveimur. So forsendum, hlutir sem þú þarft að vita ef þú ert alltaf fara að nota tvöfaldur leit. Þætti þína verður raðað. Þeir verða að vera flokkaður því það er eina leiðin sem þú getur vita ef þú ert fær um að henda út hluta af því. 

Ef þú hefðir þetta jumbled poka af tölum og þú ert að segja, OK, ég ætla að athuga miðjuna númer og fjöldi ég er að leita að er minna en það, ég ætla bara að fara að geðþótta henda út helming. Þú myndir ekki vita ef þú tölur í síðarnefnda hluta. Listinn þarf að vera flokkaður. Eins og vel, þetta getur verið að fara á undan svolítið, en þú þarft að hafa handahófi aðgang. Þú þarft að vera fær til réttlátur fara til miðju frumefni. Ef þú ert að fara gegnum eitthvað eða það tekur þig auka skref að fá til að miðju frumefni, það er ekki skráð þig n aftur því þú ert að bæta meiri vinnu í það. Og þetta mun gera a lítill meira vit í tvær vikur, en ég bara svona langaði til að formála, gefa ykkur hugmynd um hvað er að koma. En þeir eru tveir mikilvægar forsendur að þú þarft fyrir tvöfaldur lista. Gakktu úr skugga um að það er raðað. Það er ein stór fyrir þú krakkar núna. Og að við getum farið inn í restin af konar okkar. Svo fjórum sorts-- kúla, innsetning, val og sameinast. Þeir eru allir góður af kaldur. Ef þú krakkar ákveða að taka CS 124, þú munt læra óður í alls konar konar. Og ef þú ert XKCD aðdáandi, þar er mjög flott grínisti um raunverulega eins árangurslaus konar, sem ég mjög mæla með að þú að fara að horfa á. Einn af þeim er eins læti tagi, sem er eins, ó nei, aftur handahófi fylkisins. Lokun kerfisins. Fara. Svo er geeky húmor alltaf gott. 

Svo er einhver man góður af eins bara almenn hugmynd um hvernig kúla Raða virkar. Þú manst? 

Nemandi: Já. 

Umsjón: Fara til það. 

Nemandi: Svo þú ert að fara í gegnum og ef það er stærri, þá skipta um tvö. 

Umsjón: Mm-HM. Einmitt. Svo þú iterate bara í gegnum. Þú athuga tvær tölur. Ef sá áður er stærri en einn eftir það, þú skipta bara þá svo að í þessum hætti allar hærri tölur kúla upp undir lok listanum og allir lægri tölur kúla niður. 

Átti hann að sýna ykkur kaldur hljóði flokkun vídeó? Það er góður af kaldur. Þannig Robert sagði bara, reiknirit að þú stíga bara í gegnum listann, skipta aðliggjandi gildi ef þeir eru ekki í röð. Og þá bara halda að endurtaka þar til þú ekki gera neinar skiptasamninga. Svo ekki slæmt, ekki satt? Þannig að við höfum bara fljótur dæmi hér. Þannig að þetta er að fara að raða þá í vaxandi röð. Svo þegar við förum í gegnum fyrsta tími, líta við í gegnum átta og sex eru augljóslega ekki í röð, skipta við þá. 

Svo líta á næsta einn. Átta og fjórir ekki í röð. Skipta á þeim. Og svo átta og tveir, skipta á þeim. There við förum. Svo eftir fyrstu umferð, þú vita að stærsti númerið þitt er að fara til vera alla leið efst því það er bara fara að vera stöðugt stærri en allt annað og það er bara að fara að kúla upp alla leið til enda þar. Er að vit alla? Cool. 

Svo þá við skoðum seinni okkar fara. Sex og fjórir, rofi. Sex og tveir, rofi. Og nú höfum við nokkur atriði í röð. Svo fyrir hvert skarðið sem við gera í gegnum allt listanum okkar, við vitum að svona margar tölur á enda, mun hafa verið flokkuð. Svo við gerum þriðja framhjá, sem er eitt skipti. Og þá á fjórða okkar líða, höfum við núll rifa. Og svo vitum við að okkar array hefur verið raðað. 

Og það er stóra hlutur með kúla tagi. Við vitum að þegar við hafa núll skiptasamninga, að þýðir að allt sé í fullkomnu röð. Það er góður af því hvernig við athugum. Þannig að við erum líka að fara að kóða kúla Raða sem einnig er ekki svo slæmt. Ekkert þessara eru svo slæmt. Ég veit að þeir geta virst svolítið skelfilegt. Ég veit þegar ég tók bekknum, jafnvel þegar ég var að kenna bekknum um í fyrsta sinn á síðasta ári, Ég var eins og, hvernig á ég að gera þetta? Það er vit í orði, en hvernig gerum við í raun þetta? Hver er ástæða þess að ég vil líka að ganga gegnum kóðann með ykkur hér. Svo ég hef sauðakóða fyrir ykkur að þessu sinni. Svo bara að halda þetta í huga sem við erum að fara að umbreyta yfir. Þannig að við höfum sumir gegn sem heldur utan um skiptasamninga okkar, vegna þess að við þurfum að ganga úr skugga um að við erum að athuga það. Og við iterate Fylkið eins og við gerðum bara með þessu dæmi. Ef þáttur áður er stærri en þátturinn eftir hvar við erum á, við skipta á þeim og við hækka OKKAR gegn því eins fljótt og við skipta, Við viljum láta gegn okkar vita það. Einhverjar spurningar þarna? Eitthvað virðist fyndið hérna. Nemandi: Ert þú sett teljarann ​​á núll hvert skipti sem þú ferð í gegnum lykkjuna? Ert þú ekki að halda áfram aftur til núll í hvert skipti? Umsjón: Ekki endilega. Svo það sem gerist er að við að fara í gegnum hér. Svo að gera á meðan, muna, þetta mun framkvæma einu án mistakast. Svo það er að fara til að stilla gegn jafnt og núll, þá er það að fara að iterate gegnum. Eins og það iterates gegnum, það mun uppfæra teljara. Eins og það endurnýja gegn, þegar það er gert, þegar það er náð enda fylkisins, Ef listinn okkar hefur ekki verið raðað, gegn mun hafa verið uppfærð. 

Svo þá fer það ástand og það segir, OK, er gegn hærri en núll. Ef það er, gera það aftur. Þú vilt endurstilla svo að þegar þú fara í gegnum, gegn er jafnt og núll. Ef þú ferð í gegnum a Raðað array, ekkert breytist, það tekst ekki, og þú skila raðað lista. Er það er vit? Nemandi: Það gæti í smá. Umsjón: OK. Ef það er einhver annar Spurningin sem kemur upp. Já. 

Nemandi: Hvað myndi virka vera fyrir skipta þætti? 

Umsjón: Svo við getum raunverulega skrifað að ef við erum að fara að núna. Cool. Svo á að huga, Alison er að fara að skipta aftur yfir á tækið. Það er að fara að vera skemmtilegt. Og við höfum Nice okkar kúla Raða hlutur hér. Svo ég gerði þegar hjólreiðar gegnum array. Við höfum skiptasamninga okkar að eru jafnt og núll. Þannig að við viljum skipta við hliðina þættir ef þeir eru út af röð. Svo það fyrsta sem við þurfum að gera er kunnugt gegnum fylking okkar. 

Svo hvernig heldurðu að við gæti iterate gegnum fylking okkar? Við höfum fyrir og ég er 0. Við viljum i að vera minna en n mínus 1 mínus k. Og ég skal útskýra það í annað. Svo er þetta hagræðingu hér þar, man hvernig ég sagði eftir hvert skarðið gegnum array vér veit að allt sem er on-- 

Svo eftir einni umferð við vita að þetta er flokkað. Eftir tvær umferðir við vitum að allt þetta er raðað. Eftir þrjár umferðir við veit það er raðað. Þannig að hvernig ég ætla iterating gegnum array hér, er það er að gera viss um að aðeins að fara gegnum það sem við vitum er óflokkuðum. OK? Það er bara um hagræðingu. Þú getur skrifað það naively bara iterating gegnum allt, það myndi bara taka lengri tíma. Með þessu fjórum lykkja það er bara ágætur hagræðingu vegna þess að við vitum að eftir hvert fullur endurtekning gegnum array hér, eins og sérhver fullur lykkja hér, við vitum að ein fleiri af þessum þáttum verður raðað í lokin. 

Þannig að við þurfum ekki að hafa áhyggjur óður í þá. Er að vit alla? Þessi kaldur lítið bragð? Svo í því tilfelli, ef við erum iterating gegnum, við vitum að við viljum athuga hvort array n og n plús 1 eru í því skyni. OK. Svo hér er sauðakóða. Við viljum athuga hvort array n og n auk 1 eru í röð. Svo hvað gæti við höfum það? Það er að fara að vera einhver skilyrt. Það mun vera ef. 

Nemandi: Ef array n er minna en array n plús 1. Umsjón: Mm-HM. Jæja, minna en eða meira en. Nemandi: Greater en. Þá viljum við að skipta á þeim. Einmitt. Svo nú erum við að fá í það er Orsakir skipta þá? Þannig að við fórum í gegnum þetta stutta stund, a tegund skiptasamninga virka í síðustu viku. Hefur einhver man hvernig það unnið? Þannig að við getum ekki bara endurúthluta þeim, ekki satt? Vegna þess að einn af þeim mun villast. Ef við því að áðurnefnt A er jöfn og B og síðan að b er jafnt og A, allt í einu þau bæði eru bara jafn B. 

Svo það sem við þurfum að gera er að við hafa tímabundið breytu sem er að fara að halda eitt af okkar stund við erum í því ferli að skipta. Svo það sem við höfum er að við munum hafa sumir int afleysingamanneskja er jafn to-- þú geta framselja það til hvort sem þú vilt, bara vertu viss um að þú halda utan um it-- svo í þessu tilfelli, ég ætla að framselja það til array n plús 1. Svo það er að fara að halda hvað sem gildi er í þeirri seinni blokk að við erum að horfa á. 

Og þá getum við gert er að við getum farið undan og endurúthluta array n plús 1, vegna þess að við vitum að við hafa þessi gildi eru geymdar. Þetta er einnig einn af the stór things-- Ég veit ekki hvort einhver ykkar haft mál þar sem ef þú skiptir tvo línur af kóða skyndilega hlutirnir virkuðu. Order er mjög mikilvægt í CS. Svo tryggja þú skýringarmynd hlutina út ef mögulegt um hvað er í raun að gerast. Svo nú erum við að fara að endurúthluta array n plús 1, vegna þess að við vitum að við hafa þessi gildi eru geymdar. 

Og við getum falið að til array n eða í þessu tilfelli array i. Of margar breytur. OK. Svo nú höfum við færður array I plús 1 til að jafna það er fylkt i. Og nú getum við farið til baka og úthluta array ég við það? Einhver? 

Nemandi: 10. 

Umsjón: 10. Einmitt. Og eitt síðasta hlutur. Ef við höfum skipst það nú, Hvað þurfum við að gera? Hvað er eitt það er að fara að segja okkur ef við segja alltaf þetta forrit? Hvað segir okkur að við hafa raðað lista? Ef við gerum framkvæma neinar skiptasamninga, ekki satt? Ef skiptasamninga er jafnt og núll í lok þessa. Svo þegar þú framkvæma skipti, eins og vér bara gerði hér, viljum við að uppfæra skiptasamninga. Og ég veit að það var spurning áðan um getur þú nota núll eða einn stað af satt eða ósatt. Og það er það sem þetta gerir hér. Svo segir þetta ef ekki skiptasamninga. Svo ef skiptasamninga er núll, sem is-- ég alltaf fá sannleika mínir og falses mínir ruglað. Við viljum okkur að meta true og það er ekki. Þannig að ef það er núll, þá er það ósatt. Ef þú ógilt það með a [? Bang?] það verður satt. Svo þá keyrir þessa línu. 

Sannleikur og ósatt núll og sjálfur fá brjálaður. Bara ef þú gengur hægt gegnum það að það mun gera vit. En það er það sem þetta litla bita af kóða hér gerir. Svo athugar þetta að sjá höfum við gert neinar skiptasamninga. Þannig að ef það er eitthvað að auki núll, það er að fara að vera falskur og the heild hlutur er fara að framkvæma aftur. Cool? 

Nemandi: Hvað er Break gera? 

Umsjón: Brot bara brýtur þig út úr lykkja. Þannig að í þessu tilfelli hefði það bara dauðdagi forritið og þú myndir bara hafa raðað lista þinn. Nemandi: Amazing. Umsjón: Fyrirgefðu? Nemandi: Þar áður við notuð skrifað 1 yfir skriflega núll að kynna að ef sem vilja vinna eða ekki. 

Umsjón: Já. Svo er hægt að fara aftur núll eða 1. Í þessu tilfelli, vegna þess að við erum í raun ekki gera neitt með virkni, við viljum bara það að brjóta. Við gerum í raun ekki sama um það. Brake er einnig gott ef það er notað til að brjóta út af fjórum lykkjur eða aðstæður sem þú vilt ekki að halda framkvæmd. Það tekur bara þig út af þeim. Það er a hluti af a Litbrigði hlutur. Mér finnst eins og það er a einhver fjöldi af hendi veifa, eins og þú munt læra um þetta fljótlega. 

En þú munt læra um þetta fljótlega. Ég lofa. OK. Svo þýðir allir fá kúla tagi? Ekki of slæmt. Iterate gegnum, Víxla hlutina með a afleysingamanneskja breytu, og við erum öll sett þar? Cool. Ógnvekjandi. OK. Til baka í PowerPoint. Einhverjar spurningar almennt um þessum svo langt? Cool. Mm-HM. 

Nemandi: [inaudible] int helstu venjulega. Ert þú þarft að hafa að fyrir þetta? 

Umsjón: Þannig að við vorum bara að horfa bara á raunverulegri flokkunarstöð reiknirit. Ef þú hefðir það í eins stærri áætlun, þú vildi hafa int helstu einhversstaðar. Fer eftir því hvar þú nota þessa reiknirit, það myndi ákveða hvað er verið skilað af henni. En fyrir okkar tilviki erum við stranglega horfa á hvernig virkar þetta í raun iterate gegnum fjölda. Svo við ekki hafa áhyggjur óður í það. 

Þannig að við vorum að tala um besta tilfelli og versta veg fyrir tvöfaldur leit. Svo það er einnig mikilvægt að gera að fyrir hvert konar okkar. Svo er það finnst þér það versta ræða afturkreistingur af kúla tagi? Þú krakkar muna? 

Nemandi: N minus 1. Umsjón: N minus 1. Svo það þýðir að það eru n mínus 1 samanburð. Svo er eitt að gera sér grein fyrir að á fyrsta endurtekning, við förum í gegnum, bera saman við þessir two-- svo er það 1. Þessir tveir, þrír, fjórir. Svo eftir eina endurtekning við þegar hafa fjórar samanburð. Þegar ég er að tala um afturkreistingur og n. N táknar fjölda samanburð sem fall af hvernig margir þættir við höfum. OK? 

Svo við förum í gegnum, við höfum fjóra. Í næsta skipti sem þú veist að við gerum ekki að taka thessu. Við berum saman þessar tvær, þessir tveir, þessir tveir, og ef við ekki hafa að hagræðingar með fjórum lykkju sem ég skrifaði, þú vildi vera að bera saman hér engu að síður. Svo þú þyrftir að hlaupa í gegnum array og gera n samanburð n sinnum, vegna þess að í hvert skipti sem hlaupa í gegnum það sem við flokkunarröð eitt. 

Og í hvert skipti sem við hlaupa í gegnum array, gera við n samanburð. Svo er afturkreistingur okkar fyrir þetta í raun n í öðru veldi, sem er miklu verra í okkar log enda vegna þess að það þýðir að ef við hefðum fjóra milljarða frumefni, það er að fara að taka okkur fjóra milljarða veldi í stað 32. Svo ekki besta afturkreistingur, en fyrir sumum hlutum, þú veist, ef þú ert innan ákveðnum fjölda þátta kúla Raða kann vera í lagi að nota. 

OK. Svo nú er það besta málið afturkreistingur? Nemandi: Zero? Eða 1? 

Umsjón: So 1 myndi vera einn samanburður. Hægri. 

Nemandi: N mínus 1? 

Umsjón: Svo, já. Svo n minus 1. Alltaf þegar þú ert með hugmynd eins N mínus 1, við hafa tilhneigingu til að bara sleppa henni og við segjum bara n vegna þess að þú ert að bera saman hvert these-- hvert par. Svo það væri n mínus 1, sem við við myndum bara segja er um n. Þegar þú ert að takast á við afturkreistingur, allt er í samsvari. Svo lengi sem veldisvísirinn er rétt, þú ert nokkuð góður. 

Það er hvernig við takast á við það. Þannig að besta málið sé n, sem þýðir að listinn er nú þegar raðað, og allt sem við gerum er að keyra í gegnum og athuga hvort það er raðað. Cool. Allt í lagi. Svo eins og þú sérð hér, við bara hafa fleiri myndrit. Svo n veldi. Fun. Miklu verra en n eins og við sjáum, og miklu, miklu verri en log 2n. Og þá færðu líka inn log logs. Og þú tekur 124, þá færðu inn eins log stjörnu, sem er eins og brjálaður. Svo ef þú hefur áhuga, leit Log stjarna. Það er góður af gaman. Svo við höfum þetta mikla töfluna. Bara höfuð upp, þetta a dásamlegt Mynd til að hafa um miðjan tíma þínum vegna þess að við lengi til að spyrja þig þessar thins. Svo bara höfuð upp, þetta á þinn miðannar á fallegu svindlari lak þar. Svo við horfði bara á kúla tagi. Versta tilfelli, n veldi, besta tilfelli, n. Og við erum að fara að horfa á aðra. 

Og eins og þú geta sjá, eina sá sem raunverulega gerir vel er Mergesort, sem við munum fá inn af hverju. Þannig að við erum að fara að fara á Næsta einn here-- val tagi. Hefur einhver man hvernig val Raða unnið? Að fara í það. 

Nemandi: grundvallaratriðum fara í gegnum fyrirmæli og búa til nýjan lista. Og rétt eins og þú ert að setja þætti í, setja þá á réttum stað í nýju skránni. 

Umsjón: Svo að hljóð meira eins Innsetningarröðun. En þú ert mjög nálægt. Þeir eru mjög svipuð. Jafnvel ég fá þá ruglað stundum. Fyrir þessa kafla sem ég var eins og, bíddu. OK. Svo það sem þú vilt gera er val tagi, hvernig hægt er að hugsa um það og hvernig Ég tryggt að ég reyni ekki að fá þá ruglað, er það fer í gegnum og það velur minnsti fjöldi og það setur það í upphafi á listanum þínum. Það skiptir það með því fyrsta staðnum. Þeir hafa í raun dæmi fyrir mig. Ógnvekjandi. Svo bara leið til að hugsa um it-- val raða, velja minnstu gildi. Og við erum að fara að hlaupa í gegnum dæmi að ég tel að muni hjálpa því Ég held myndefni alltaf hjálpa. Svo erum við að byrja út með eitthvað það er alveg óflokkað. Red verður óflokkuðu, Grænn verður raðað. Það mun allt vit í annað. 

Svo við förum í gegnum og við iterate frá upphafi til enda. Og við segjum, OK, 2 er minnsti fjöldi okkar. Þannig að við erum að fara að taka 2 og við erum að fara að færa það til the andlit af array okkar því það er minnsti fjöldi sem við höfum. Svo það er það sem þetta er að gera hér. Það er bara að fara að skipta þessum tveimur. Svo nú höfum við a raðað hluti og óflokkuðum hluta. Og hvað er gott að muna um val tagi er að við erum aðeins að velja frá óflokkaðs hluta. 

The Raðað hluti þú skilur bara einn. Mm-HM? 

Nemandi: Hvernig virkar það vita hvað er minnstu án bera það að öll önnur gildi í array. Umsjón: Það gerir bera það. Við eins sleppt því. Þetta er bara almenn heild. Já. Þegar við að skrifa kóðann sem ég ætla viss um að þú munt vera fleiri ánægðir. En þú vistar fyrst þáttur sem minnstu. Að bera og þú segja, OK, er það minni? Já. Hafðu það. Hér er það minni? Nei? 

Þetta er minnsti þinn, breyta henni til gildi. Og þú munt vera miklu ánægðari þegar við förum í gegnum kóðann. Svo við förum í gegnum, skipta við það, svo þá Við lítum á þetta óflokkuðum hluta. Þannig að við erum að fara að velja þremur. Við erum að fara að setja það á á enda flokkaðs hluta okkar. Og við erum bara að fara að halda að gera að gera það, og gera það. Svo er af þessu tagi okkar sauðakóða hér. Við munum kóða það upp hér í annað. En bara eitthvað að ganga gegnum á háu stigi. Þú ert að fara að fara frá Ég er 0 til n mínus 2. Það er önnur fínstillingu. Ekki hafa áhyggjur of mikill óður í það. Svo eins og þú varst að segja. Eins Jakob var að segja, hvernig vér halda utan um hvað lágmarki okkar er? Hvernig vitum við? Við verðum að bera saman allt í listanum okkar. 

Svo lágmarki jafngildir i. Það er bara að segja í þessu tilfelli vísitölu lágmarksgildi okkar. Svo þá er það að fara að iterate gegnum og það fer frá J er jafnt ég plús 1. Þannig að við vitum nú þegar að sem er fyrsta þáttur okkar. Við þurfum ekki að bera saman það að sjálfu sér. Svo erum við að byrja að bera saman það til the næstur einn sem er hvers vegna það er ég auk 1 til N mínus 1, sem er enda fylkisins þar. Og við sögðum ef array á j er minna en array min, þá erum endurúthluta hvar lágmarkskröfur vísitölur okkar er. 

Og ef mín er ekki jafnt og i, eins og í þar sem við vorum aftur hérna. Svo eins og þegar við gerðum fyrst þetta einn. Í þessu tilviki, að það myndi byrja á núll, það myndi enda upp tilvera tvö. Svo mín myndi ekki jafn i í lokin. Sem leyfir okkur að vita að við þurfum að skipta á þeim. Mér líður eins og steypu dæmi mun hjálpa mikið meira en þetta. Svo ég ætla að kóða þetta upp með ykkur núna og held ég að það verður að vera betra. 

Konar tilhneigingu til að vinna þannig í því það er oft betra bara að sjá þær. Svo það sem við viljum gera er við viljum fyrst minnstu þáttur í stöðu sinni í array. Einmitt það Jakob var að segja. Þú þarft að geyma það á einhvern hátt. Þannig að við erum að fara að byrja hér iterating yfir array. Við erum að fara að segja að það er okkar fyrsta bara til að byrja með. Þannig að við erum að fara að hafa int minnstu er jafnt og array á i. 

Svo eitt að taka eftir, á hverjum skipti sem þetta lykkja keyrir, við erum að byrja einu skrefi lengra. Þegar við byrjum að líta á þetta einn. Næst þegar við iterate gegnum, við erum farin á þessu einn og framselja það minnsta gildi okkar. Svo það er mjög svipað og kúla tagi þar sem við vitum að eftir einni umferð, þetta síðasta þáttur er flokkaður. Með val tagi, það er bara hið gagnstæða. 

Á hverjum skarðinu, við vitum að sá fyrsti er raðað. Eftir seinni skarðið, sem seinni verður raðað. Og eins og þú sást við glæruna dæmi, raðað hluti okkar heldur bara áfram að stækka. Svo með því að setja minnstu einn okkar til fylki i, allt það er að gera er að þrengja það við erum að horfa á svo sem til að draga úr fjölda samanburða við tökum. Er að gera skilningarvit til alla? Ert þú þarft mig að hlaupa í gegnum það aftur hægari eða í mismunandi orðum? Ég er fús til að. OK. 

Þannig að við erum að geyma gildi á þessum tímapunkti, en við viljum líka að geyma vísitölu. Þannig að við erum að fara að geyma staða minnstu einn, sem er bara að fara að vera i. Svo nú er Jakob sáttur. Við höfum hluti geymdar. Og nú þurfum við að horfa í gegnum sem óflokkuðu hluti fylkisins. Þannig að í þessu tilfelli væri óflokkuðum okkar. Þetta er i. OK. 

Svo það sem við erum að fara að gera er að fara að vera fyrir lykkju. Alltaf þegar þú þarft að iterate gegnum fjölda, hugur þinn gæti farið til lykkju. Svo fyrir einhverjum int k equals-- hvað við hugsum k er að fara til að jafna til að byrja með? Þetta er það sem við setjum sem minnstu okkar gildi og við viljum bera það. Hvað viljum við bera saman það til? Það er að fara að vera svona næsta einn, ekki satt? Þannig viljum við k að frumstilla til ég plús 1 til að byrja. 

Og við viljum k í þessu tilfelli erum við þegar hafa stærð geymt upp hér, svo við getum bara notað stærð. Size vera stærð fylkisins. Og við viljum bara til uppfæra k í hvert skipti. Cool. Svo nú þurfum við að finna minnsti þáttur hér. Þannig að ef við iterate gegnum, við langar að segja, ef array á k er minna en minnstu value-- okkar þetta er þar sem við erum í raun og veru halda utan um hvað er minnsti here-- þá viljum við að endurúthluta hvað minnstu gildi okkar er. 

Þetta þýðir að, ó, við erum iterating gegnum hér. Whatever gildi er hér er ekki okkar minnstu hlutur. Við viljum það ekki. Við viljum breyta henni. Þannig að ef við erum að reassigning það, hvað þú heldur kannski að vera í þessum kóða hér? Við viljum að endurúthluta minnstu og stöðu. Svo er það minnsta núna? Nemandi: Array k. Umsjón: Array k. Og hvað er staða núna? Hvað er vísitala Minnsta gildi okkar? Það er bara k. Svo array k, k, passa þeir upp. Þannig að við vildum að endurúthluta því. Og svo eftir að við fannst minnstu okkar, svo í lok þessa fyrir lykkju hér höfum við fundið það minnsta okkar gildi er, þannig að við skipta bara. Í þessu tilviki, eins og sagt okkar Minnsta gildi er út hér. Þetta er minnsta gildi okkar. 

Við viljum bara að skipta henni hér, sem er hvað sem skipta á virka neðst gerði, sem við skrifuðum bara upp saman í nokkrar mínútur síðan. Svo það ætti að líta kunnuglegt. Og þá mun það bara iterate í gegnum þar til það nær alla leið til enda, sem þýðir að þú hafa núll þætti sem eru óflokkaðar og allt annað hefur verið raðað. Skynsamleg? Smá meira concretely? Kóðinn hjálp? 

Nemandi: Fyrir stærð, þú aldrei virkilega skilgreina það eða breyta því, hvernig virkar það vita? 

Umsjón: Svo eitt til taka upp hér er INT stærð. Þannig að við erum að segja í þessu sort-- tagi er fall í þessu case-- það val tagi, það er liðin með fallinu. Þannig að ef það var ekki samþykkt í, sem þú myndir gera eitthvað eins og með lengd array eða þú vildi iterate gegnum að finna lengd. En vegna þess að það er liðin í, við getum bara notað það. Þú tekur bara að notandinn gaf þér gilt stærð sem reyndar táknar stærð array þinn. Cool? 

Ef þú krakkar hafa allir vandræðum með þessum eða vilja fleiri æfa erfðaskrá konar á eigin spýtur, þú ættir fara til study.cs50. Það er a tól. Þeir hafa afgreiðslumaður sem þú getur raunverulega skrifa. Þeir gera sauðakóða. Þeir hafa fleiri myndbönd og skyggnur þar á meðal þær sem ég nota hér. Svo ef þú ert enn að tilfinning a lítið loðinn, reyna það út. Eins og alltaf, koma tala við mig líka. Spurning? 

Nemandi: Ertu að segja að stærð er áður skilgreint? Umsjón: Já. Size er og áður var skilgreint upp hér í aðgerðina yfirlýsingu. Svo þú gera ráð fyrir að það er verið samþykkt í af notanda, og fyrir sakir einfaldleika er, við erum að fara að gera ráð fyrir að notandi gaf okkur rétta stærð. Cool. Svo er það val tegund. Krakkar, ég veit að við erum að læra mikið í dag. Það er þétt gögn fyrir kafla. Svo með það, við erum að fara að fara í innsetningu tagi. 

OK. Svo áður en að við þurfum að gera Runtime greiningu okkar hér. Svo í besta tilfelli, veitt síðan ég sýndi þér Taflan ég þegar konar gaf henni. En best að ræða afturkreistingur, hvað við höldum? Allt flokkað. N veldi. Einhver hafa skýringu fyrir því hvers vegna þú heldur? 

Nemandi: Þú ert að bera saman through-- Umsjón: Hægri. Þú ert að bera saman í gegnum. Á hverjum endurtekning, jafnvel þótt við erum decrementing þetta með einn, þú ert enn að leita í gegnum allt til að finna minnstu einn. Svo jafnvel ef minnstu gildi þitt er hér í upphafi, þú ert enn að bera það gegn allt annað að ganga úr skugga um að það er minnsti hlutur. Svo þú munt á endanum að keyra í gegnum bil n veldi sinnum. Allt í lagi. Og hvað er versta? Einnig n veldi vegna þess að þú ert að fara að vera að gera það sama aðferð. Þannig að í þessu tilfelli, val Raða eitthvað sem við köllum líka ráð afturkreistingur. Svo í öðrum, við vitum bara efri og neðri mörk. Það fer eftir því hvernig brjálaður okkar listi er eða hvernig óflokkuðu það er, þeir breytileg á milli n eða n öðru veldi. Við vitum það ekki. 

En vegna val raða hefur sömu versta og besta tilfelli, sem segir okkur að sama hvaða tegund af inntak við hafa, hvort sem það er alveg raðað eða alveg andstæða raðað, það er fara að taka sama magn af tíma. Svo í því tilfelli, ef þú muna frá borð okkar, það hafði í raun gildi sem þessir tveir tegund hafa ekki, sem er gert ráð fyrir afturkreistingur. Þannig að við vitum að þegar hlaupum val konar, það er ábyrgð að keyra n veldi tíma. Það er engin breytileiki þar. Það er bara gert ráð fyrir. Og aftur, ef þú vilt læra meira, taka CS 124 í vor. Allt í lagi. Við höfum séð þetta einn. Cool. Svo insertion sort. Og ég er líklega að fara að loga í gegnum þetta. Ég mun ekki hafa þið kóða það. Við verðum bara að ganga í gegnum það. Svo er insertion sort góður af svipað val tagi í því að við höfum bæði óflokkuðu og raðað hluta fylkisins. 

En hvað er öðruvísi er að eins og við förum í gegnum eitt af öðru, við tökum bara hvað sem tala er næst í óflokkaðs okkar, og rétt tegund það inn flokkaðs array okkar. Það mun gera meira vit með dæmi. Svo byrjar allt sem óflokkuðu, bara eins og með val tagi. Og við erum að fara að raða þessu í Hækkandi röð eins og við höfum verið. Svo á fyrsta okkar fara við taka fyrsta gildi og við segjum, OK, þú ert nú á lista sjálfur. 

Þar sem þú ert á lista sjálfur, þú ert flokkuð. Til hamingju fyrir að vera Fyrsta þáttur í þessu fylki. Þú ert nú þegar raðað allt á eigin spýtur. Svo nú höfum við a raðað og óflokkuðum array. Svo nú erum við að taka fyrst. Hvað gerist á milli hér og hér er að við segjum, OK, við erum að fara að horfa á Fyrsta gildi óflokkaðs array okkar og við erum að fara að inntak það í sinni réttum stað í flokkaðs fylkisins. 

Svo það sem við gerum er að við að taka 5 og við segjum, OK, 5 er meira en 3, svo við setja bara það rétt til hægri á það. Við erum góð. Svo þá förum við á næsta einn okkar. Og við tökum 2. Við segjum, OK, 2 er minna en 3, þannig að við vitum að það þarf að vera á framan á listanum okkar núna. Svo það sem við gerum er að við ýta 3 og 5 niður og við að færa 2 í það fyrsta rifa. Þannig að við erum bara að setja það inn réttum stað það ætti að vera. 

Þá erum við að líta á okkar næsta einn, og við segjum 6. OK, 6 er meiri en allt í flokkaðs fylking okkar, svo við tag bara það á til enda. Og þá erum við að líta á 4. 4 er minna en 6, það er minna en 5 en það er meira en 3. Þannig að við að setja bara það rétt inn mitt á milli 3 og 5. Svo til að gera það svolítið aðeins meira steypu, hér er góður af hugmynd um hvað gerðist. Svo fyrir hvert óflokkuðu frumefni, við ákvarða hvar í flokkaðs hluta það er. 

Svo hafðu í huga að raðað og óflokkaðar, við verðum að fara í gegnum og mynd út hvar það passar í flokkaðs fylkisins. Og við setja það með því að færa þættir til hægri það niður. Og þá erum við að halda bara iterating gegnum þar til við hafa a fullkomlega raðað lista þar óflokkuðu er nú núll og raðað tekur upp heild á listanum okkar. Svo, aftur, til að gera hlutina enn meira steypu, höfum við sauðakóða. 

Svo í grundvallaratriðum fyrir i er jafnt og 0 til n mínus 1, það er bara lengd array okkar. Við höfum sumir þáttur sem er jafn fyrsta array eða fyrstu vísitölur. Við setjum j jafnan við það. Svo á meðan j er meiri en núll og array, J mínus 1 er meiri en þáttur, þannig að allt sem er að gera er að tryggja að J þitt raunverulega táknar sem óflokkuðu hluta fylkisins. 

Svo á meðan það er enn hluti að flokka og j mínus einn is-- hvað er þáttur hennar? J var aldrei skilgreint hér. Það er góður af pirrandi. OK. Engu að síður. Svo J mínus 1, þú ert að stöðva þátturinn fyrir það. Þú ert að segja, OK, er þáttur áður þar sem ég am-- skulum reyndar draga þetta út. Svo skulum segja að þetta sé eins og á öðrum okkar fara. Svo ég er að fara að vera jöfn til 1, sem er hér. 

Svo ég er að fara að vera jafnt og 1. Þetta mundi vera 2, 4, 5, 6, 7. Allt í lagi. Svo þáttur okkar í þessu tilfelli er að fara að vera jafn og 4. Og við höfum einhverja j sem er fara að vera jafnt og 1. Ó, j er decrementing. Það er það sem það er. Svo er J jöfn i, svo hvað þetta er segja er að eins og við halda áfram, við erum bara að gera viss að við erum ekki yfir flokkun með þessum hætti þegar við erum að reyna að setja hlutina inn raðað lista okkar. 

Svo þegar j er jafnt og 1 í þessu tilfelli og array J mínus one-- svo array J mínus 1 er 2 í þessu case-- ef það er meiri en frumefni, þá allt þetta er að gera er að breytast það niður. Þannig að í þessu tilfelli, array J mínus einn væri array núll, sem er 2. 2 er ekki meiri en 4, svo þetta er ekki keyrt. Svo breyting ekki að fara niður. Hvað þetta gerir hér er bara færa raðað array niður. Í þessu tilviki, í raun, að við gæti do-- skulum gera þetta 3. Þannig að ef við erum að ganga í gegnum með þetta dæmi, við erum nú hér. Þetta er flokkað. Þetta er óflokkuðum. Cool? Svo er ég jafnt og 2, þannig þáttur okkar er jafnt og 3. Og j okkar er jafnt og 2. Svo við horfir í gegnum og við segja, OK, er array J mínus einn meiri en frumefni að við erum að horfa á? Og svarið er já, ekki satt? 4 er meiri en 3 og j er 2, þannig að þetta númer framkvæmd. 

Svo nú hvað við gerum á fjölbreytta á 2, svo hérna, skipta við þá. Þannig að við segjum bara, OK, array á 2 er nú að fara að vera 3. Og j er að fara til að jafna J mínus 1, sem er 1. Það er hræðilegt, en þú krakkar fá hugmynd. J er nú jafnt og 1. Og array j er bara að fara að vera jafn þáttur okkar sem var 4. Ég þurrkast eitthvað sem ég ætti ekki að hafa eða miswrote eitthvað, en þú krakkar fá hugmynd. 

Það að færa á n. Og þá ef þetta væri, myndi það lykkja aftur og það myndi segja, OK, j er 1 núna. Og array J mínus 1 er nú 2. Er 2 minna en frumefni okkar? Nei? Það þýðir að við höfum sett þennan þátt í réttri blettur í flokkaðs array okkar. Þá getum við tekið þetta og við segjum, OK, raðað array okkar er hér. Og það myndi taka þetta númer 6 og vera eins, OK, er 6 minna en þetta númer? Nei? Cool. Við erum í lagi. 

Gerðu það aftur. Við segjum 7. Er 7 minna en í lok flokkaðs array okkar? No. Þannig að við erum í lagi. Þannig að þetta myndi vera flokkaður. Rauninni allt þetta er það að segja taka fyrsta þáttur í óflokkaðs array þinn, reikna út hvar það fer í flokkaðs fylking þinni. Og þetta tekur bara umönnun skiptasamninga til að gera það. Þú ert í rauninni bara að skipta þar til það er í rétta staðnum. Sjónræna mynd er að þú ert færa allt niður með því að gera það. 

Svo það er eins og hálf kúla tegund-esque. Kíkja rannsókn 50. Ég mæli reyna að kóða þetta á eigin spýtur. Ef þú hefur einhverjar málefni eða ef þú vilt sjá dæmi um kóða fyrir Innsetningarröðun, vinsamlegast láttu mig vita. Ég er alltaf í kring. Svo versta tilfelli afturkreistingur og besta tilfelli afturkreistingur. Eins og þú sást strákur frá töflunni ég þegar sýndi þér, það er bæði n veldi og n. 

Svo góður að fara burt af því sem við ræddum um með fyrri konar okkar, versta ræða afturkreistingur er að ef það er alveg óflokkað, við verðum að bera allar þessar n sinnum. Við gerum allt fullt af samanburði því ef það er í öfugri röð, við erum að fara að segja, OK, þetta er það sama, þetta er gott, og þetta verður að vera í samanburði gegn þeirri fyrstu til að vera flutt til baka. Og eins og við fá til hala lok, við höfum að bera saman, bera saman, og bera saman við allt. 

Svo það endar að vera bil n veldi. Ef það er rétt þá er segja, OK, 2, þú ert góður. 3, ætlar þú miðað við 2. Þú ert góður. 4, bera bara á skottið. Þú ert góður. 6, bera saman við skottið, þú ert fínn. Svo fyrir hvern staðnum ef það er þegar raðað, ert þú að gera einn samanburð. Svo er það bara n. Og vegna þess að við höfum besta tilfelli afturkreistingur n og versta afturkreistingur af n veldi, höfum við enga vænta afturkreistingur. 

Það veltur bara á óreiðu af listanum okkar þar. Og aftur, annar línurit og annað borð. Svo mismunandi milli konar. Ég ætla bara að fara að gola í gegnum, ég finnst eins og við höfum talað mikið um hvernig þeir allskonar af mismunandi og tengja saman. Svo Mergesort er síðasta einn Ég skal ól ykkur með. Við höfum nokkuð litríka mynd. Svo sameinast tegund er endurkvæma reiknirit. Svo þú krakkar vita hvað a endurkvæma virka er? 

Einhver vilja til segja? Þú vilt reyna? Svo er a endurkvæma virka bara fall sem kallar sig. Svo ef þú krakkar eru kunnugir með Fibonacci röð, sem er talið endurkvæma vegna þú tekur síðustu tveimur og bæta þeim saman að fá næsta einn. Svo endurkvæma, held ég alltaf af endurkvæmni sem eins spíral svo þú ert eins og ört vaxandi niður í það. En það er bara fall sem kallar sig. 

Og reyndar, í raun fljótt ég getur sýnt þér hvað það lítur út. Svo endurkvæma hér, ef við lítum, þetta er endurkvæma leiðin að summa yfir fylki. Svo allt sem við gerum er við höfum summa virka fjárhæð sem tekur stærð og fjölda. Og ef þú tekur eftir, stærð skjárínn telur niður um einn tíma. Og allt það gerir er ef X er jafnt zero-- svo ef stærð fylkisins er jafnt zero-- það skilar núll. 

Annars er það fjárhæðir þetta síðasta þáttur í fylkinu, og þá tekur summu af restin af fylkisins. Svo það er bara að brjóta það niður í smærri og smærri vandamál. Long saga stutt, endurkvæmni, fall sem kallar sig. Ef það er allt sem þú fékk út úr þessu, það er það a endurkvæma virka er. Ef þú tekur 51, þú vilja fá mjög, mjög ánægð með endurkvæmni. Það er mjög svalt. Það vit á eins 03:00 eitt kvöldið út. Og ég var eins og, af hverju hef ég aldrei notað þetta? 

Svo fyrir Mergesort, grundvallaratriðum hvað það er að fara að gera er að það er að fara að brjóta það niður og brjóta það niður þar til það er bara single þættir. The einn þættir eru auðvelt að raða. Við sjáum það. Ef þú ert einn þáttur, það er þegar talið flokkuð. Svo á inntak n þáttum, ef n er minna en 2, bara aftur því það þýðir að það er annað hvort 0 eða 1 eins og við höfum séð. Þeir teljast flokkuð þættir. 

Annars brjóta það í tvennt. Raða fyrri hluta, raða annað helmingur, og þá sameinast þeim saman. Hvers vegna það er kallað Mergesort. Þannig að við höfum hér við munum raða þeim. Svo við höldum með þeim þar til array stærð er 1. Svo þegar það er 1, aftur við bara því þetta er Raðað array, og þetta er Raðað array, og það er a Raðað array, erum við öll flokkuð. Svo þá hvað við gerum er að við byrja samruna þeim saman. 

Svo eins og þú getur hugsa um sameiningu er þú fjarlægir bara minni fjöldi hver af sub fylki og bara auka við það að skapast fylkisins. Svo ef þú lítur hér, þegar við höfum Þetta setur við höfum 4, 6, og 1. Þegar við viljum sameina þetta, við líta á þessum fyrstu tveimur og við segjum, OK, 1 er minni, það fer að framan. 4 og 6, það er ekkert til að bera saman það til, bara merkja það á til enda. 

Þegar við sameina þessar tvær, við bara taka minni einn af þessum tveimur, svo það er 1. Og nú erum við að taka minni af þessum tveimur, SO 2. Minna af þessum tveimur, 3. Minna af þessum tveimur, 4, 5, 6. Svo þú ert bara að toga á þessum. Og vegna þess að þeir eru búnir verið raðað áður, þú ert bara einn samanburður í hvert sinn þar. Svo fleiri kóða hér, bara framsetning. Svo þú byrjar á miðju og þú raða vinstri og hægri og þá sameinast bara þá. 

Og við höfum ekki númerið fyrir steypa hérna. En, aftur, ef þú ferð á rannsókn 50, það verður þar. Annars koma að tala við mig Ef þú ert enn að rugla. Svo kaldur hlutur hér er að besta tilfelli, versta tilfelli, og gert ráð fyrir afturkreistingur eru allir í log n, sem er miklu betra en við höfum séð fyrir afganginn af tegund okkar. Við höfum séð n veldi og það sem við raunverulega fá hér er n log n, sem er frábært. 

Horfðu á hversu mikið betur sem er. Slík ágætur bugða. Svo mun skilvirkari. Ef þú getur alltaf, nota Mergesort. Það mun spara þér tíma. Þá aftur, eins og ég sagði, ef þú ert niður í þennan litla svæði, það þýðir ekki að gera það mikið af a mismunur. Þú færð allt að þúsund og þúsundir af aðföngum, þú vilt örugglega skilvirkari reiknirit. Og aftur, kæri borðið okkar af öllu tegund sem þú krakkar lært í dag. 

Þannig að ég veit að það hefur verið þétt dag. Þetta er ekki endilega að fara til að hjálpa þér með pset þinn. En ég vil bara að gera höfnun þessi hluti er ekki bara um psets. Allt þetta efni er sanngjörn leikur fyrir midterms þínum. Og einnig ef þú halda áfram á CS, þetta eru virkilega mikilvæg grundvallaratriði að þú myndir þurfa að vita. Svo nokkrum dögum verður lítið meira pset hjálp, en sumir vikur verða miklu meira raunverulegt innihald sem geta ekki virðast frábær gagnlegt fyrir þig núna, en ég lofa ef þú heldur áfram á verður mjög, mjög gagnlegt. 

Svo það er það fyrir hluta. Niður á vírinn. Ég gerði það innan einnar mínútu. En þar sem þú ferð. Og ég mun hafa kleinuhringir eða sælgæti. Er einhver með ofnæmi eitthvað, við the vegur? Egg og mjólk. Svo kleinuhringir eru ekki? OK. Allt í lagi. Súkkulaði nei? Gylltu. Starbursts eru góðar. OK. Við erum að fara að hafa Gylltu næstu viku þá. Það er það sem ég næ. Þú krakkar hafa a mikill viku. Lesa sérstakur þína. 

Láttu mig vita ef þú hefur einhverjar spurningar. Pset tvær einkunna skal út til þín frá fimmtudag. Ef þú hefur einhverjar spurningar um hvernig ég farið eitthvað eða hvers vegna ég farið eitthvað og ég gerði, vinsamlegast sendu mér tölvupóst, koma tala við mig. Ég er svolítið brjálaður á þessu viku, en ég lofa Ég mun samt svara innan 24 klst. Svo hafa a mikill viku, allir. Gangi þér vel á pset þinni.