SPEAKER 1: Hei visiem! Laipni lūdzam atpakaļ uz sadaļu. Tik priecīgs redzēt tik daudzi no jums abiem šeit un ikviens, kurš ir skatoties online. Tātad, kā parasti welcome atpakaļ. Es ceru, ka jums visiem bija jauki nedēļas nogalē, pilns ar atpūtu, relaksāciju. Tas bija skaisti out vakar. Tātad, es ceru, ka jums patika ārā. 

Tātad pirmais pāris paziņojumiem. Šķirošanas. Tātad, lielākā daļa no jums būtu gotten e-pastu no manis par savu Scratch PSET, kā arī šķirošanai pēc PSET 1. Tātad, tikai pāris lietas. Pārliecinieties, lai izmantotu check50 in style50. Tie ir paredzēti, lai resursi jums, puiši, lai pārliecinātos, ka jūs saņemat tik daudz punktus, kā jūs varat bez nevajadzīgi zaudēt tiem. Tātad, lietas, piemēram, stilu ir ļoti svarīgi. Mēs gatavojamies pacelties par to. Daži no jums, iespējams, jau pamanīju, ka no jūsu PSET. Un check50 ir tikai ļoti viegls veids, kā pārliecināties ka mēs esam patiešām atgriešanās ko ir jānosūta atpakaļ lietotājam, un ka viss strādā pareizi. 

Par otro piezīmi, pārliecinieties, ka jūsu augšupielādējot lietas uz pareizo mapi. Tas padara manu dzīvi tikai mazliet grūtāk ja jūs augšupielādēt PSET 2 uz PSET 1 jo, kad es lejupielādēt lietas, tie nav lejupielādēt pareizi. Un es zinu, tas ir mazliet ļodzīgs sistēmā, lai saņemtu izmantoti, lai, bet vienkārši super uzmanīgiem, ja tikai man, tā, ka tad, kad jūs saņemat e-pastus pie kā 02:00 un es esmu šķirošanu. Ja nevar izraisīt man ir jāskatās visapkārt jūsu PSET. Atdzist. 

Es zinu, tas ir agri, bet es pilnīgi got pacēlies aizsargs ar eseju, kas ir saistīts ar šo piektdien, šā manas profesori bija tieši tāpat, oh yeah. Atcerieties, ka jums ir eseja dēļ piektdien. Tātad, es zinu, neviens patīk domāt par midterms, bet jūsu pirmais viktorīna ir oktobrī 15, kas Oktobris ir sākot no šīs nedēļas. Tātad, tas varētu būt ātrāk nekā jūs gaidīts ir viss. Tāpēc, ka jūs neesat nometusi aizsargu Es minēju nākamnedēļ sadaļu šo oh, Jūsu viktorīna nākamnedēļ, es domāju Es gribētu dot jums mazliet vairāk ar galvu uz augšu tagad. 

Tātad, jūsu problēma noteikt, skaits ir trīs. Cik cilvēki ir izlasījis spec aiz ziņkārības? OK. Mēs saņēmām pāris. Veida leju no pēdējās nedēļā, bet tas ir OK. Es zinu, tas bija skaisti out. Tik Break Out. Noteikti pēc jums izdarīt šodien lasīt jūsu spec vismaz mēģināt tāpat lejupielādējot izplatīšanas kodu un skriešana tāpat kā pirmajā, lieta, ka viņi lūdz jums. Tāpēc, ka mēs izmantojam izplatīšanas kodu un bibliotēku ka mēs esam tikai bijuši using-- --It ir tikai otrā reize, kad mēs esam darījuši šo PSET, trakas lietas var notikt ar savu ierīci, un jūs vēlaties, lai atrastu, ka kas tagad pret vēlāk. 

Jo, ja tas ir ceturtdienas vakarā, vai tas ir Svētdienas nakts un kādu iemeslu dēļ jūsu ierīce vienkārši nav vēlas darboties ar bibliotēku vai ar izplatīšanu kodu, tas nozīmē Jūs nevarat pat sākt darīt kodēšana. Jo jūs nevarat pārbaudīt lai redzētu, vai tas darbojas. Jūsu nav gonna būt iespējai lai redzētu, vai tas apkopo. Jūs vēlaties rūpēties par tiem sākumā nedēļā, kad jūs joprojām varat e-pastu man vai viens no pārējiem TFS, un mēs varam iegūt to, kas noteikts. Jo tie ir jautājumi, kas gatavojas pārtraukt jums no jebkādu reālu progresu. Tas nav kā vienu bug, ka Jūs varat vienkārši veida izlaist. Ja jums ir problēmas ar jūsu ierīce vai izplatīšana kods, jūs tiešām vēlaties, lai iegūtu, ka jāņem rūp ātrāk nekā vēlāk. Tātad, pat ja jūs ne gonna reāli sākt kodēšanu, lejupielādēt izplatīšanu kods, lasīt spec, pārliecinieties viss strādā tur. OK? Ja jūs varat darīt, ka es sola savu dzīvi būs vieglāk. Un tāpēc jūs, iespējams, gatavojas to izdarīt tieši tagad taisnība? OK. Tātad, kādi jautājumi tur? Jebkuras loģistikas lietas? Ikvienam ir labs? OK. 

Atruna par tiem Jūs istabā un internetā. Es esmu būs mēģina pārslēgties starp PowerPoint ierīcē jo mēs gatavojamies lai dara dažas kodēšana šodien tautas pieprasījums anonīms ierosinājums aptauja Es izsūtīti pagājušajā nedēļā. Tātad, mēs darīsim zināmu kodēšanu. Tātad, ja jūs puiši arī vēlaties uguns jūsu ierīces, un jums vajadzētu būt saņēmu e-pastu no manis, ar parauga failu. Lūdzu, jūtieties brīvi, lai to izdarītu. 

Tātad, mēs esam gatavojas runāt par GDB, kas ir atkļūdotājs. Tas notiek, lai palīdzētu jums veida izdomāt, kur lietas notiek nepareizi savu kodu. Tas patiešām ir tikai veids, kā jūs soli caur savu kodu, kā tas notiek, un varēs izdrukāt mainīgos vai redzēt to, kas patiesībā notiek ar kapuci verses savu programmu tikai darbojas, tas ir, piemēram faulting, un jūs, piemēram, nav ideju to, kas tikko notika šeit. Es nezinu, ko līnija tas neizdevās. Es nezinu, kur tas gāja greizi. Tātad, GDB notiek, lai palīdzētu jums ar to. Arī tad, ja jūs nolemjat turpināt jā, un ņem 61, tas tiešām, tiešām ir jūsu labākais draugs, izraisīt Es varu jums pateikt jo es eju caur šo klasi. 

Mēs ejam apskatīt bināro meklēšana, kas, ja jūs guys atcerēties liels tālruni grāmatu piemērs izrāde no klases. Mēs būsim īstenošanai ka, un ejot cauri, ka mazliet vairāk, un tad mēs ejam cauri četriem dažādu veidu, kas ir burbulis, Atlase, ievietošana, un apvienot. Atdzist. Tātad, GDB kā jau minēju, ir atkļūdotājs. Un tie ir sava veida liels lietas, lielie funkcijas vai komandas ka jūs izmantojat laikā GDB, un es staigāt Jūs caur demo tā sekundē. 

Tātad, tas ir ne tikai gatavojas palikt abstrakts. Es mēģināšu, un padarīt to par betona cik vien iespējams, lai jūs puiši. Tātad, pauze. Tas būs vai nu būs pārtraukums piemēram, daži skaits, kas pārstāv līniju savu programmu, vai jūs varat nosaukt funkciju. Tātad, ja jūs sakāt pauze galvenais, tas apstāsies pie galvenā, un ļauj staigāt pa šo funkciju. 

Tāpat, ja jums ir kāds ārējs darboties kā Swap vai Cube, ka mēs paskatījās pagājušajā nedēļā. Ja jūs sakāt pauze viens no tiem, kad jūsu programma hits, ka, tas būs jāgaida, lai jūs varētu pateikt to, ko darīt. Pirms tas būs tikai izpildīt, lai jūs reāli varētu pastiprināt iekšpusē funkciju un redzēt, kas notiek. Tātad, Next, tikai Lēcieni pār Nākamais līnija iet pāri funkcijas. Soli. Tie visi ir nedaudz abstrakti. Tātad, es esmu tikai gatavojas palaist caur tiem, bet jūs redzēsiet tos izmantošanai sekundē. 

Soli funkciju. Tā kā es jau teicu, kā ar Swap, tas būtu ļauj faktiski it kā jūs esat tāpat kā fiziski pastiprināšanu iekšā, Jūs varat sajaukt ar šiem mainīgajiem, drukas , kādi viņi ir, redzēt, kas notiek. Saraksts tiks burtiski vienkārši izdrukāt ārā apkārtējo kodu. Tātad, ja jūs veida aizmirst kur jums ir jūsu programmā, vai jūs domājām kas notiek ap to, tas vienkārši izdrukāt segments no patīk piecas vai sešas līnijas ap to. Tātad, jūs varat saņemt orientēta par to, kur jūs esat. 

Izdrukāt kādu mainīgs. Tātad, ja jums ir, piemēram, atslēgu ar ķeizaru, ka mēs apskatīt. Jūs varat teikt, Print atslēga jebkurā brīdī. Tas jums pateiks, kāda vērtība ir tik ka varbūt kaut kur pa ceļam, Jūs pārrakstīja savu atslēgu. Jūs faktiski var teikt, ka, jo jūs faktiski var novērot šo vērtību. 

Jo vietējie, tikai izdrukas savu vietējo mainīgie. Tātad, jebkurā laikā jūs esat ietvaros cilpu, un jūs vienkārši vēlaties redzēt, piemēram, oh. Kas ir mana es? Kas tas ir galvenās vērtības ka es sāktu šeit? Kāds ir vēstījums šajā brīdī? Tas būs tikai drukāt visu no tiem, tā, ka jums nav atsevišķi saka, Print I. Print Message. Print Key. Un tad Display. Kas, ka tas ir, kā jūs soli, izmantojot programmu, tas būs tikai pārliecinieties, ka tā ir attēlot kādu noteiktu mainīgo ikvienā vietā. Tā, ka jūs also-- --it ir veida īsceļu kur jums nav, lai saglabātu turpinās, piemēram, oh. Print Key vai Print I. Tas vienkārši automātiski darīt to you. 

Tātad, ar to, ka mēs ejam lai redzētu, kā tas notiek. Es esmu gatavojas izmēģināt un slēdzis pār manu ierīci. Redzēt, ja es varētu darīt. Viss. Mēs esam tikai gatavojas atspoguļot to. Tur nekas traks par manu klēpjdators anyways. OK. Tas ir nepieciešams, lai šis viens. Tas ir tik niecīga. Let 's redzēt, ja mēs varam izdarīt. 

OK. Alise ir acīmredzami cīnās šeit tikai mazliet, bet mēs saņemsiet to tādā Momento. OK. Mēs esam tikai gatavojas palielināt. OK. Var ikviens veida redzat? Varbūt mazliet? Es zinu, tas ir pārāk mazs. Jūs nevar gluži izrēķināt kā padarīt šo lielāks. Ja kāds zina. Vai kāds zina, kā padarīt to lielāks? OK. Mēs ejam, lai roll ar to. Nav svarīgi, anyways, jo tas ir tikai tas ir kods, kas jūs guys vajadzētu ir. 

Kas ir vēl svarīgāk ir terminālis šeit. Un mēs esam šeit Kāpēc tas ir tik mazs? Iestatījumus. Oh. True Ike. Kā tas ir? No turienes ārā. Ir tā, ka labāk par visiem? OK ,. Atdzist. 

Jūs zināt, kad tu esi CS klases tehniskas grūtības ir sava veida daļa the-- Tātad, pieņemsim skaidrs tas. OK. Tātad, tepat sadaļā, kas mums bija šeit. Cēzars ir izpildāmais fails. Tāpēc es to. Tātad, viena lieta ir saprast, ar GDB ir ka tas darbojas tikai izpildāmos failus. Tātad, jūs nevarat palaist to uz dotsy. Jums ir, lai faktiski padarītu Pārliecinieties, ka jūsu kods apkopo, un ka tas faktiski var darboties. 

Tātad, pārliecinieties, ka, ja tas tā nav sastādīt, saņemt to apkopot, lai jūs varētu veida palaist caur to. Tātad, lai sāktu GDB, viss, kas jums jādara, Gloria tips GDB, un tad tikai failu, ka jūs vēlaties. Es vienmēr kļūdaini Cēzaru. Bet jūs vēlaties, lai pārliecinātos jo tas ir izpildāms, TI dot flash tā, ka nozīmē, ka jūs esat gatavojas palaist CSI jūs gatavojas izpildīt šo failus vai nu ar atkļūdotājs. OK. Tātad, jūs, jūs saņemsiet šāda veida buldurēšana. Tas ir tikai visas lietas par atkļūdotājs. Jums nav tiešām ir jāuztraucas par to tieši tagad. Un, kā jūs redzat, mums ir šis atvērt parens, IKP, tuvu parens, un tikko veida izskatās Mūsu komandrindas, vai ne? 

Tātad, ko mēs gribam, lai do-- --So, Pirmā lieta ir, mēs gribam, lai izvēlētos vieta lauzt. Tātad, ir viena kļūda šajā Caesar programmā ka es ieviest, ka mēs ejam, lai uzzinātu. Tas Kas tas ir nepieciešams, ievadi Barfoo visos cepures, un kādu iemeslu dēļ tas nemaina A. Tas vienkārši atstāj tas vien, ir viss pārējais pareizi, bet otrā vēstule Paliek nemainīgs. Tātad, mēs ejam, lai mēģinātu saprast, kāpēc tas ir. Tātad, pirmā lieta, ko jūs parasti vēlas darīt, kad sākat GDB ir izdomāt, kur to lauzt. 

Tātad Cēzars ir diezgan īss programma. Mums vienkārši ir viena funkcija, vai ne? Kāda bija mūsu funkcija Cēzara? Tur ir tikai viena funkcija, Main labi? Galvenais ir funkcija visiem jūsu programmas. Ja jums nebija Main, es varētu būt mazliet noraizējies tieši tagad, bet es ceru, ka jūs visi bija Main tur. Tātad, ko mēs varam darīt, ir, mēs varam vienkārši pauze Main, tieši tāpat. Tātad, tā saka, OK. Mēs, kas mūsu pārtraukumpunkts vienu tur. 

Tātad, tagad ir atcerēties, Caesar aizņem viens komandrindas argumentu tiesības un mēs neesam darījuši, ka nekur vēl. Tātad, ko jūs darāt, ir tad, kad jūs tiešām iet palaist programma, jebkura programma, kas jūs esat darbojas GDB kas nepieciešams komandrindu argumenti, jūs gatavojas ievadi kad jūs pirmo reizi sākt rādīt to. Tātad, šajā gadījumā, mēs darām Palaist ar atslēgu trīs. Un tas faktiski sākt. 

Tātad, ja jūs redzat šeit, mēs esam Ja RC nav vienāds ar 2. Tātad, ja jūs puiši visi ir ka fails, es izsūtīti uz augšu jūs redzēsiet, ka tas ir tāpat kā Pirmā līnija mūsu galvenais uzdevums, vai ne? Tas pārbaudi, lai redzētu, vai mēs esam pareizais vairāki argumenti. Tātad, ja jūs domājām ja RC ir pareiza, jūs varat darīt kaut ko tāpat kā Print RC. RC ir divi, kas ir tas, ko mēs gaidīts, vai ne? 

Tātad, mēs varam doties tālāk, un turpināsies līdz. Tātad, mums ir dažas taustiņu tur. Un mēs varam izdrukāt savu atslēgu lai pārliecinātos, ka ir pareizi. Interesanti. Ne gluži tas, ko mēs gaidīts. Tātad, viena lieta, lai realizētu ar GDB arī ir ka tas nav, kamēr jūs faktiski hit Nākamais, ka līnija, kas jūs tikko redzēju faktiski izpildīts. Tātad, šajā gadījumā Key nav piešķirts vēl. Tātad, Key ir daži atkritumu vērtība ka jūs redzēt uz grunts tur. Negatīvs $ 120-- --It s viens miljards un kaut nepāra lietas pareizi? Tas nav atslēga, kas mums gaidāms. Bet, ja mēs hit Tālāk, un tad mēs mēģināt un Print atslēgu, tas ir trīs. 

Ikvienam redzēt, ka? Tātad, ja jums kaut kas ka jūs, piemēram, jāgaida. Tas ir pilnīgi nepareizi, un es nezinu kā tas varētu notikt, jo viss, ko es gribu darīt, ir piešķirtu numuru, mainīgs, mēģināt hitting Tālāk, mēģiniet drukāt atkal, un redzēt, ja tas darbojas. Tāpēc, ka tas ir tikai gatavojas izpildīt un faktiski piešķirt kaut pēc tevis hit Next. Jēga visiem? Uh huh? 

SPEAKER 2: Kad jūs nejauši skaitļi, ko tas nozīmē? 

SPEAKER 1: Tas ir tikai izlases. Tas ir tikai atkritumu. Tas ir tikai kaut kas jūsu dators nejauši piešķirt. Atdzist. Tātad, tagad mēs varam virzīties cauri, un tā Tagad mums ir šī teksta GetString. Tātad, ļaujiet man tikai iepazīstināt ko notiks, kad mēs hit Next šeit. Mūsu GDB veida pazūd, vai ne? Tas ir tāpēc, ka GetString tagad izpildes, vai ne? Tātad, kad mēs redzējām teksta vienāds GetString, atveriet parens un parens, un mēs hit Tālāk, kas ir faktiski izpildīts tagad. Tātad, tas ir gaida mums ieejas kaut ko. 

Tātad, mēs ejam, lai ievadītu mūsu pārtiku, kas ir tas, kas tas ir nedarot, kā es tev teicu un ka tikai saka, ka tā ir gatavo izpildes, ka slēgta kronšteins nozīmē, ka tas ir iziešanas no šīs cilpas. Tātad, mēs varam hit Next, un tagad, kā es esmu pārliecināts, ka jūs visi esat pazīstami no Cēzara, tas ir, kāda ir šī pozīcija gatavojas to darīt. Tas ir par Int es vienāds ar 0, N ir vienāds Strlen, teksta, un pēc tam I ir mazāk nekā n, I, plus, plus. Kas tas ir cilpa gatavojas darīt? Atveriet savu ziņu. Atdzist. Tātad, sāksim darīt. 

Tātad, ja šis nosacījums spēles, mūsu pirmo? Ja tas ir B, tas ir teksta I. Mums var iegūt informāciju par mūsu vietējiem. Tātad, es ir nulle, un ja sešu, kas mēs sagaidām, un mūsu galvenais ir trīs. Viss, kas ir jēga, vai ne? Šie skaitļi ir visi tieši to, ko viņiem vajadzētu būt. Tātad, smirdēt? SPEAKER 3: Man ir izlases numuri raktuvē. SPEAKER 1: Nu, mēs varam check-- --we var tērzēt par to, ka sekundē. Bet jums vajadzētu iegūt to. Tātad, ja mums ir kapitāls B mūsu pirmā, šis nosacījums būtu noķert to, labi? Tātad, ja mēs hit Tālāk, mēs redzam ka šis Ja faktiski izpilda. Jo, ja jūs pēc gar savu kodu, šī līnija šeit, kur teksta es aizstāj ar šo aritmētikā, izpilda tikai tad, ja IF nosacījums ir pareizi vai ne? 

GDB ir tikai gatavojas, lai parādītu jums lietas, kas ir faktiski izpildītāji. Tātad, ja šis Ja nosacījums nav izpildīts, tas ir tikai gatavojas, lai pārietu uz nākamo rindiņu. OK? Tātad, mums ir, ka. Tas kronšteins nozīmē, ka tas ir slēgts no šīs cilpas tagad. Tātad, tas notiek, lai sāktu no jauna. Tieši tāpat. Tāpēc, ka mēs varam iegūt informāciju par mūsu vietējiem šeit un mēs redzam, ka mūsu pirmais vēstule ir mainījies, vai ne? Tas tagad ir E, kā tam vajadzētu būt. Tātad, mēs varam turpināt. 

Un mums ir šo pārbaudi. Un ja šajā pārbaudē vajadzētu strādāt, vai ne? Tas ir A. Būtu jāmaina trīs burti uz priekšu. Bet, ja pamanāt, mēs dabūt kaut ko citu. Tātad šajā gadījumā šeit, tas nozvejotas tas, un tāpēc šī pozīcija izpildīts, kas paredzēja mainīt mūsu B. Tomēr, šajā gadījumā šeit, mums ir, ka tas ir tikai izlaistas to, un devās uz [? L siff. ?] Tātad, kaut kas notiek tur. Ko tas stāsta jums ir tas, ka, mēs zinām, ka tas būtu nozvejas šeit bet tas nav. Vai kāds redzēt, ko mūsu Problēma ir šajā rindā? Tas ir ļoti minūti lieta. Un jūs varētu arī apskatīt savu kodu. Tas ir arī line-- aizmirst to, ko līnija tas ir jo there-- bet tas ir [nedzirdama]. Jā? 

SPEAKER 4: Tas ir par vairāk nekā lapa, ja jūs lasīt to grāmatu. SPEAKER 1: Tieši tā. Tātad, atkļūdotājs nevarēja pateikt Jums, ka, bet atkļūdotājs varētu saņemt jūs uz leju, lai līnijas ka jūs zināt, nedarbojas. Un dažreiz, kad īpaši vēlāk semestrī, kad jums ir darīšana ar simts, kas ir simts dažas rindiņas kodu, un jūs nezinu, kur tas nedarot, šis ir lielisks veids, kā to darīt. Tātad, mēs noskaidrojām mūsu kļūdu. Jūs varat noteikt to savā failā, un tad jūs varētu palaist to no jauna, un viss darbosies perfekti. Un lielākais lieta ir tas var šķist, OK. Yeah. Atdzist. Jūs zināja, ko jūs meklējat. Tātad, jūs zinātu, ko darīt. 

GDB var būt super noderīgi, jo jums var izdrukāt visas šīs lietas, kas jums nebūtu. Tas ir daudz noderīgāks nekā printf. Cik daudzi no jums izmantot piemēram printf paziņojumiem izdomāt, kur kļūda bija, vai ne? Tātad, ar šo, jums nav ir saglabāt atgriežās, un patīk komentējot Printf, vai komentējot, un izdomāt, ko Jums vajadzētu drukāšanas. Tas faktiski tikai ļauj jums soli pa, izdrukāt lietas kā jūs iet cauri, tāpēc, jūs varat vērot, kā tie mainās reālā laikā, kā jūsu programma darbojas. 

Un tas prasa nedaudz mazliet jāpierod. Es ļoti ieteiktu tikai veida būt mazliet neapmierinātas ar to tieši tagad. Ja jūs pavadīt stundas pa nākamnedēļ mācīties, kā izmantot GDB, jūs ietaupīsiet sev tik daudz laika vēlāk. Un burtiski. mēs pateikt šo cilvēku katru gadu, un es atceros, kad es paņēmu klasē, man bija, piemēram, man būs labi. Nē. PSET 6 nāca un man bija piemēram, es esmu gonna mācīties kā izmantot GDB, jo man nav zināt, kas notiek šeit. 

Tātad, ja jūs lietojat laiks, lai izmantot to par mazākām programmām ka jūs esat būs strādā, piemēram, strādājot ar kaut ko līdzīgu Visionare, kā šis. Vai, ja vēlaties papildus praksi, es esmu pārliecināts, ka Es varētu nākt klajā ar buggy programmām, jums atkļūdot, ja vēlaties. 

Bet, ja jūs vienkārši aizņemt kādu laiku, lai saņemtu pieraduši pie tā, tikai spēlēt aptuveni ar to, tas tiešām kalpos jums labi. Un tas patiešām ir viens no tās lietas, ka jūs vienkārši ir izmēģināt, un saņemt rokas netīras ar, pirms jūs patiešām saprast. Es tiešām tikai saprot to vienu reizi Man bija atkļūdošanas lietas ar to, un tas ir daudz jaukāk ir ideja par kā atkļūdot ātrāk nekā vēlāk. OK. Atdzist. Es zinu, ka ir veids kā crash kurss GDB, un es noteikti strādās par iegūt tos meklēt lielāku nākamreiz. Atdzist. 

Tātad, ja mēs ejam atpakaļ uz mūsu PowerPoint. Tas notiek uz darbu? AWH. Jā. OK. Tātad, ja jums kādreiz ir nepieciešams kāds no tie atkal, tur ir saraksts. Tātad Binary Meklēt, kurā ikviens atceras lielo briļļu Dāvida lielisks tālruņu grāmatas uz pusēm. Man nav īsti iegūt telefonu grāmatas vairs, tāpēc, ka, piemēram, ja jūs saņem telefona grāmatas šajās dienās? Es tiešām nezinu. Binary Meklēt. Vai kāds atceras Kā Binary meklēšanas darbus? Ikviens vispār? Yeah? SPEAKER 5: Jūs zināt, kad paskatās kuriem puse tas būtu, pamatojoties uz to, un atbrīvoties no otra puse. 

SPEAKER 1 Tieši tā. Tātad, bināro meklēšanu, tas ir sava veida a-- --we patīk, lai izsauktu to sadalīt un iekarot. Tātad, ko jūs darīt, ir jūs meklēt pa vidu, un jūs redzēsiet, ja tas atbilst to, ko jūs meklējat. Un, ja tas tā nav, tad jūs mēģināt izdomāt, tas būs jāatstāj puse jeb labajā pusē. Tātad, tas varētu būt, ja jūs meklējat kaut ko, kas ir alphabetized, jūs redzat, oh. Vai Allison nonāk līdz M? Jā. Tātad, mēs ejam, lai apskatīt pirmajā pusē. 

Vai tas varētu būt, piemēram, ar skaitļiem. Jebkas, ka jūs varat salīdzināt, tas var būt sakārtoti. Jūs varat izmantot bināro meklēšanu. Tātad, kāds atceras šo Grafikā vai kas tas ir? Tas ir Asimptotiskā sarežģītība. Tātad, šis diagramma tikai aprakstīts, cik ilgi tas ņem jums, lai atrisinātu problēmu, kā jūs palielināt vairākas lietas ka jūs izmantojat. 

Tātad, mēs ir N, kas ir lineārs laiks. Ja N virs diviem, kas ir nedaudz labāk, tomēr aug super ātri. Un tad mēs esam saitā, kas ir tas, ko mēs uzskatām bināro meklēšanu. Ja mēs pamanām, kā jūsu problēma kļūst daudz un daudz lielāka, laiks, kas nepieciešams, lai jūs to atrisināt nav īsti palielināties, ka daudz. Tas ir tāpat kā salīdzināt šeit sākumā. Jūs, piemēram, OK. Jebkas šeit nav īsti jautājums, kuriem viens mēs izmantojam, bet jums, lai miljons, miljards. Jūs mēģināt atrast some-- --you're mēģinot atrast adatu siena kaudzē. 

Es domāju, ka jūs vēlaties šo problēmu. Vēlaties šo sarežģītību, nevis lineāra, jo visiem jums zināt jūsu gonna meklējot caur katrs indivīds adatu, lieta siena, mēģina meklēt savu adatu. Un tas nav pārāk jautri, manuprāt. Man patīk ātri. Man patīk efektīva. Un kā hardworking studentu pilsētās puiši ir, jūs zināt strādāt gudrāk, nav grūtāk tipa lieta, kā jūs var padarīt šos algoritmus. 

Tātad, mēs ejam staigāt izmantojot tikai ātri piemērs. Es domāju, ka jūs guys ir jābūt roku uz bināro meklēšanu, bet ja kāds ir nedaudz izplūdušas, vēlamies stiprināt to, mēs ejam, lai tikai iet izmantojot piemēru šeit. Tātad, mēs meklējam, ja masīvs satur septiņus. 

Tātad, pirmā lieta, ko mēs darām, ir izskatās pa vidu, vai ne? Un arī jūs esat būs kodēšanas Binārā Meklēt tikai sekundē. Tātad, tas būs jautri. Tātad mēs skatāmies vidū maz bloki 3. Vai 3 vienāds 7? Nav. Tas ir sešas. Tātad, tas ir mazāk nekā vai lielāks par septiņiem? Mazāk nekā. Jā. Nice darba puiši. Man šķiet, es, piemēram, es būtu ir candy jo es vēlaties, lai mest to ārā pagalmos. Tas ir tas, ko es esmu gatavojas darīt nākamnedēļ. Tas saglabās jums puiši asas. 

Tātad, mēs izmetam, ka pirmo pusi, vai ne? tas bija mazāk nekā. mēs zinām, ka viss šajā kreisajā pusē būs mazāks nekā tas, ko mēs patiesībā meklējam. Tātad, nav nepieciešams pievērst uzmanību. Vienkārši aizmirst par to. Tātad, tagad mēs skatāmies mūsu labajā pusē, un mēs skatāmies vidū tur, un tagad tas ir deviņi. Tātad, 9 is-- --Everyone? Lielāks nekā tas, ko mēs esam meklē, vai ne? Tātad, mēs ejam, lai mest prom, viss labi. Tāpat. Tagad, visi mēs esam atstāti ar ir viens. Tātad mēs pārbaudām, tas ir viens, ko mēs meklējam? tas ir. Mēs noskaidrojām, ko mēs vēlējāmies. Tāpēc mēs esam darījuši. Bilineāra Meklēt. 

Un, ja pamanāt, mēs bija septiņi ieejas tur. Tas tikai bija mums kā trīs reizes, bet, ja jūs darāt, piemēram, miljarda, jūs guys zināt, cik soļus tas būtu jāveic, ja mums bija četru miljardu lietas? Jebkurš guesses? Tas ir 32. 32 soļi, lai atrastu kaut ko ar četru miljardu elements masīvs jo pilnvaru diviem. Tātad divi ir 32, ir līdz četriem miljardiem. 

Tātad, diezgan traks, kā jūs joprojām laikā piemēram, diezgan nelielu skaitu soļiem lai atrastu kaut ko četru miljardu elementi. Tātad uz šo piezīmi, mēs esam gatavojas kodu šo Tātad jūs puiši faktiski var veida redzēt, kā tas darbojas. Labi, lai jūs guys var kodu. Es esmu gatavojas let you guys runāt mazliet. Iepazīt cilvēkus ap jums, kas ir ko kāds vēlējās no pēdējā sadaļā. 

Tātad iepazīt cilvēkus ap jums. Runāt mazliet. Un viss, ko es gribu no jums puiši tagad ir tikai mēģināt izveidot izklāstu pseudocode. OK? Paga. Viss, ko es gribu no jums puiši ir jūs tikai gatavojas aizpildīt to, kamēr gadījumā. Tāpēc man ir izveidojušas šos augšējā un apakšējā robeža, kas pārstāv sākumu un beigas mūsu masīvs. Un jūs gatavojas, lai faktiski cilpas cauri un izdomāt tas, ko mēs darām šajā kamēr cilpa. 

Tātad, ja jūs varat izdomāt out-- man ir mājienu there-- kādi ir gadījumi ka mēs esam šeit? Tātad, ja jūs vēlaties, lai noskaidrotu lietas, mēs pseudocode tiem un tad mēs patiesībā kodu tiem. Un tas būs, es domāju, cerams, tas būs būt mazliet vieglāk, nekā jūs sagaida. Tāpēc, ka tas nav tik daudz kodu, patiesībā, kas ir tiešām foršs. 

Mm-hm? 

STUDENTU: [dzirdams]? Instruktors: Jā. Tur bija kaut kas atrast vidū. 

STUDENTU: Tātad, mēs varam izmantot to. OK. 

Instruktors: Perfect. Tā ka ir pirmā lieta, kas mums jādara. Tāpēc atrast vidū. Lieliski. Tātad jums ir ideja par to, kā mēs varētu faktiski atrast vidū ar kodu? 

STUDENTU: Jā. n vairāk nekā 2? Instruktors: Tātad n vairāk nekā 2. Tik viena lieta atcerēties ir tas, ka jūsu augšējā un apakšējā robeža mainīt. Mēs turpinām constricting daļu masīva mēs meklējam. Tātad n vairāk nekā 2 darbosies tikai pirmā lieta, ko mēs darām. Tātad, ņemot vērā augšējo un apakšējo, kā varētu mēs šo vidējo elementu? Jo mēs gribam vidū starp augšējo un apakšējo, labi? Mm-hm? 

STUDENTU: [dzirdams]. 

Instruktors: Tātad mums ir dažas vidū. Un tas būs augšējais plus zemāka nekā 2. Awesome. Tur mēs ejam. Viena rinda uz leju. Jūs guys ir pa ceļam. Tāpēc tagad, ka mums ir mūsu vidū, ko mēs vēlamies darīt? Tikai kopumā. Jums nav kodu to. Jā. STUDENTU: [dzirdams]? Instruktors: Tātad, tas ir arī tāpēc, ka tu esi atrast vidējo starp diviem no tiem. Tātad, ja jūs domājat par to kā sava veida un pieaug no sāniem, domā par to, kā jūs pieeja vidū, jūs vēlaties, piemēram, ka. Tātad, ja tu būtu abās pusēs vidū, un mums ir, piemēram, 5 un 7. Kad jūs pievienot tos kopā, jums get 12, jūs sadalīt pa 2, ir 6. 

Dažreiz tas ir grūti izskaidrot, kāpēc tas darbojas, bet, ja jūs strādājat ar piemērs reizēm, tas tev palīdzēs jums saprast, ja tas būtu plus vai mīnus. Jā. 

STUDENTU: [dzirdams] tieši vidū ja tie bija gadījums, kad tur ir daudz mazāku skaitu un kā viena liela skaita? 

Instruktors: Tātad viss, kas jums nepieciešams ir vidū masīva. Tātad, ja jums bija ķekars nelielā skaitā un tad īsti liels skaits beigās, tas nav svarīgi. Viss, ka jautājumus ir, ka viņi šķiro, jūs vienkārši vēlaties apskatīt vidū masīvs, jo tu esi vēl sagriešana savu problēmu pusi. Atdzist. Tāpēc tagad, ka mēs esam vidū, ko mēs darīt tālāk? 

STUDENTU: Salīdzināt. Instruktors: salīdzināt. Tāpēc salīdzināt vidū uz value_wanted. Atdzist. Tātad jūs redzat, šeit mums ir šī vērtība mēs vēlamies šeit. Atcerieties, tas ir masīvs. Tā vidus attiecas uz indeksu. Tāpēc mēs vēlamies darīt vērtības vidū. Neaizmirstiet, ja vēlaties salīdzināt, dubultā vienāds. Jums viena vienāds esat tikai gatavojas pārdalīt to, un tad, protams, tas ir būs vērtību, ko vēlaties. Tāpēc nav darīt. 

Tātad mēs ejam, lai redzētu, vai vērtības, kas pa vidu ir vienāds ar vērtību, mēs vēlas. Neaizmirstiet lencēm. Dropbox vajadzētu iet prom. Tātad, ko mēs darām šajā gadījumā? Ja tas ir tas, ko mēs vēlamies, lai atgrieztos? Mēs cenšamies pateikt. 

STUDENTU: Print off. 

Instruktors: Nu, mēs negribu izdrukāt. Tātad tas ir bool šeit, tāpēc mēs vēlas atgriezties patiess vai nepatiess. Mēs sakot, tas ir skaitlis [? RRA? ?] Tātad, ja tas ir, mēs vienkārši atgriezties tā ir taisnība. Ja es varētu izskaidrot taisnība. 

STUDENTU: Kāpēc nebūtu jūs atgriezties nulle? Instruktors: Tātad jūs varētu atgriešanās nulle, ja jūs vēlējāties. Bet šajā gadījumā, jo Mūsu funkcija atgriež bool, mums ir nepieciešams, lai atgrieztos vai nu patiess vai nepatiess. STUDENTU: Kad esat sakot Būla izteiksme, Jūs varat iestatīt tā, kas vienāds ar viltus? Piemēram, ja es gribu teikt, ja šis nosacījums nav izpildīts, piemēram, ir augšējā vienāds nepatiesa. Vai tas saprast, ja jūs vienkārši likt false, no otras puses? Instruktors: Jā. Tik tiešām, ja jūs esat kādreiz kaut ko dara tāpat ir augšējā vai apakšējā, kas atgriež patiess vai nepatiess un tas ir faktiski slikti stils teiksim vienāds vienāds patiess vai vienāds vienāds nepatiesa. Jūs vēlaties izmantot šo rezultātu kā pati kā jūsu čeku. Nav tas, ko es gribēju. Tas ir tas, ko es gribēju. Tātad, ja jūs esat jautā par kaut ko, piemēram, saglabāt to C. 

Tātad, ja mums ir int galvenais (spēkā neesošs) un kaut kas līdzīgs šim. Un jums ir, ja ir augšējā par kādu ievades un jūs jautā, ja jūs varat darīt kaut kas līdzīgs šim? Taisnība? STUDENTU: Es centos to darīt [nedzirdama]. Jo, ja it's-- Instruktors: Labais. Tātad jūs vēlaties, ka tas ir viltus, vai ne? STUDENTU: Jā. Instruktors: Tātad šajā gadījumā jums vēlas to izpildīt, ja tā nav taisnība. Tik cool lieta, ko jūs darīt, ir šī. Līdz ar to atcerēties izsaukuma punkts noliedz lietas? Tajā teikts [dzirdams] nozīmē ne. Tātad, ja mēs skatāmies tikai šī daļa šeit, jūs saka, ka novērtē to viltus kā jūs to vēlaties. Nav nepatiesa ir taisnība, kas nozīmē, ka šis varētu izpildīt. Vai tas ir jēga? STUDENTU: Jā. Instruktors: satriecošs. OK. Lai mēs varētu vienkārši atgriezties taisnība šajā gadījumā. Tāpēc tagad mums ir divi citi gadījumi šajā lietā. Kādas ir mūsu divas citas lietas? Pieņemsim tikai darīt to šādā veidā. Tāpēc sāksim ar cits ja vērtības pie vidu ir mazāka nekā vērtība, kas mēs vēlas. Tātad, mūsu vērtība vidū ir mazāks nekā vērtība, ka mēs meklējam. 

Tātad, kas saistās do you domāju, ka mēs vēlamies atjaunināt? Augšējā vai apakšējā? Upper? Tā, kurā pusē no masīva mēs gribam būt apskatot? 

STUDENTU: zemāka. 

Instruktors: Mēs mēs ejam kas meklē kreisi. Tātad, kas cits, ja mazliet vērtība ir mazāka. Tik jūsu vidū vērtību šeit ir mazāks nekā tas, ko mēs gribam. Tāpēc mēs vēlamies, lai labajā pusē mūsu masīvs. Tātad mēs ejam atjaunināt mūsu apakšējo robežu. Tāpēc mēs atkārtoti piešķirt mūsu zemāka. Un ko jūs domājat, ka zemāka vajadzētu būt? STUDENTU: vidējā vērtība? Instruktors: Tātad vidējā value-- STUDENTU: Plus 1. Instruktors: --plus 1. Var kāds man pateikt, kāpēc mums ir, ka plus 1? 

STUDENTU: [? Nav vērtības?] ir vairāk vienāds ar to. 

Instruktors: Labais. Jo mēs jau zinām, ka Mūsu vidējā vērtība nav vienāds ar tas, un mēs vēlamies izslēgt no visiem turpmākajiem meklējumiem. Ja esat aizmirsis, ka plus 1, šis patiks cilpa bezgalīgi. Un jūs vienkārši nozvejotas bezgalīga cilpa, un tad jūs segfault un lietas iet slikti. Tāpēc vienmēr pārliecinieties, ka jūs neesat tostarp vērtību, ka jūs vienkārši paskatījās. Tāpēc mēs rūpējamies, ka ar plus 1. 

Tāpēc tagad mums ir mūsu pēdējā stāvokli ko es vienmēr par drošības labad Jūs varat pārbaudīt šeit, cits, ja vērtība vidū ir lielāka nekā vērtība, mēs gribam. Tas nozīmē, ka mēs gribam kreisajā pusē. Tātad kuriem viens mēs gatavojas atjaunināt? Upper. Un kas ir tas viens būs vienāds? Tuvo mīnus 1, jo, Protams, mēs vēlamies lai pārliecinātos, ka mēs neesam Aplūkojot šo vērtību vidū vēlreiz. Un tad mums ir tā. Viss. Tas ir viss, binārā meklēšana ir. Tas nav tik slikti, vai ne? Tas ir tāpat kā 10 rindiņas kodu ar atstarpēm. Tik ļoti spēcīgs, ļoti noderīga, jums būs to lietot vienā no jūsu vēlāk psets. Varbūt ne tas viens, bet vēlāk. Tāpēc apgūt. Love it. Tas būs pret jums labi. Tātad, vai kāds ir jebkurš jautājumi par bināro meklēšanu? Jā. 

STUDENTU: Vai tas ir svarīgi vai jūsu n ir pāra vai nepāra? 

Instruktors: Nē. Jo mēs meta to uz vidu, kā int, tas būs tikai saīsināt to. Tātad, tas paliks vesels skaitlis, un tas būs beidzot kārtot caur visu. Tātad jums nav jāuztraucas par to. Ikvienam labs? Awesome. Atdzist. Tātad, jūs puiši dabūja to. Slaidrādi. Tā kā mēs runājām par to, es zinu David minēja sarežģītības runtimes. 

Tātad labākajā gadījumā, tas ir tikai viens, ko mēs saucam par pastāvīgu laiku. Vai kāds man pateikt, kāpēc tas varētu būt? Kāda veida scenārija tas var radīt? Mm-hm. 

STUDENTU: [dzirdams] first-- Instruktors: Tātad vidū ir Pirmais elements, ka mēs nonākam pie, vai ne? Tātad, vai nu masīvs no vienas vai ko mēs meklējam tikai notiek, ir nokrāsa plakanzivs vidū. Tātad tas ir mūsu labākais gadījums. Nokļūsiet reālām problēmām, iespējams, nav gatavojas sasniegt [dzirdams], ka bieži. Kas par mūsu sliktākajā gadījumā? Mūsu sliktākajā gadījumā ir log n. Un tas ir jādara ar visu pilnvaras divu lieta, ka es runāju par. 

Tātad sliktākajā gadījumā tas nozīmētu ka mums bija karbonāde masīvs leju līdz brīdim, kad tas bija viens elements. Tāpēc mums bija karbonāde to uz leju pusi tik reižu, cik mēs, iespējams, varētu. Tieši tāpēc tas ir žurnāls, jo n jūs vienkārši glabāt dalot ar divi. Tātad pieņēmumus, lietas, kas jums vajag zināt, ja jūs esat kādreiz gatavojas izmantot bināro meklēšanu. Jūsu elementi ir sakārtoti. Tie ir sakārtoti, jo tas ir vienīgais veids, kā jūs var zināt, ja jums ir iespēja izsviest pusi no tā. 

Ja jums bija šis jumbled maisā skaitļu un jūs sakāt, Labi, es esmu gatavojas, lai pārbaudītu vidū skaits un es meklēju ir mazāks par to, ka es esmu tikai gatavojas patvaļīgi izsviest pusi. Jūs nezināt, ja Jūsu numurus šajā otrajā pusē. Tavs saraksts ir sakārtots. Kā arī, tas var būt iet uz priekšu mazliet, bet jums ir brīva piekļuve. Jums ir nepieciešams, lai varētu vienkārši doties uz šo elementu vidū. Ja jums ir, lai šķērsotu ar kaut ko vai tas aizņem jums papildu pasākumus nokļūt, ka vidējā elementa, tas nav log n vairs, jo jūs pievienojat vairāk darba tajā. Un tas liks nedaudz vairāk jēgas divām nedēļām, bet es tikko veida gribēju iesākt, sniegt jums guys priekšstatu par to, kas ir nākt. Bet tie ir divi svarīgi pieņēmumi kas jums ir nepieciešams, lai bināro sarakstā. Pārliecinieties, ka tas ir sakārtots. Tas ir liels vienu jūs guys tiesības tagad. Un par to mēs varam iedziļināties pārējās mūsu veidu. Tātad četri sorts-- burbulis, ievietošanas, atlase, un apvienot. Viņi visa veida atdzist. Ja jūs puiši nolemj ņemt CS 124, jūs uzzināt par visu veidu veidu. Un, ja jūs esat xkcd ventilatoru, tur ir tiešām foršs komikss par tāpat īsti neefektīvu veidu, ko es ļoti iesakām jums skatīsies. Viens no tiem ir kā panikas veida, kas ir tāpat kā, ak nē, atgriezties izlases masīvs. Shutdown sistēma. Atstāt. Tātad geeky humors vienmēr ir laba. 

Tātad vai kāds atceras veida veida kā tikai vispārēju priekšstatu par to, kā burbulis veida darbi. Jūs atceraties? 

STUDENTU: Jā. 

Instruktors: Iet par to. 

STUDENTU: Tātad jūs iet cauri, un ja tas ir lielāks, tad jūs mijmaiņas divas. 

Instruktors: Mm-hm. Tieši tā. Tātad jūs vienkārši atkārtot, izmantojot. Jūs pārbaudīt divus numurus. Ja kāds pirms ir lielāks nekā pēc tam vienu, jūs vienkārši mijmaiņas tos tā, ka Šādā veidā viss no augstāku numuru burbulis up beigās saraksta un visi zemākas skaits burbulis uz leju. 

Vai viņš parādīs puiši forši skaņas efektu šķirošanas video? Tas ir sava veida atdzist. Lai Robert tikko teica, algoritmu ka jūs vienkārši soli pa sarakstu, pārnešana blakus vērtības ja viņi nav kārtībā. Un tad tikai glabāt atkārtojot kamēr jums nav nekādas mijmaiņas darījumus. Tātad nav slikti, vai ne? Tātad mums vienkārši ir ātri piemērs šeit. Tātad tas notiek, lai sakārtotu tos augošā secībā. Tātad, kad mēs ejam cauri pirmais laiks, mēs skatāmies caur astoņiem un seši ir acīmredzami nav Lai mēs mijmaiņas tiem. 

Tātad apskatīt nākamo. Astoņi un četri nav kārtībā. Mijmaiņas tiem. Un tad astoņi un divi, mijmaiņas tiem. Tur mēs ejam. Tātad, pēc jūsu pirmā caurlaide, jums zināt, ka jūsu lielākais skaits būs visu ceļu augšpusē, jo tas ir tikai būs pastāvīgi lielāks nekā viss pārējais un tas ir tikai gatavojas burbuli up visu ceļu līdz beigām tur. Vai tas ir jēga visiem? Atdzist. 

Tātad, tad mēs skatāmies uz mūsu otro caurlaide. Seši un četri, slēdzis. Seši un divi, slēdzis. Un tagad mums ir dažas lietas kārtībā. Tātad par katru pass, ka mēs veikt caur mūsu visu sarakstu, mēs zinām, ka, piemēram, ka daudzi numuriem beigās būs sakārtoti. Tātad mēs trešo caurlaide, kas ir viens swap. Un pēc tam mūsu ceturtais caurlaide, mums ir nulle slots. Un tā mēs zinām, ka mūsu masīvs ir sakārtota. 

Un tas ir liels lieta ar burbulis kārtošanas. Mēs zinām, ka tad, kad mēs ir nulle mijmaiņas darījumus, kas nozīmē, ka viss ir pilnīgā kārtībā. Tas ir veids, kā mēs pārbaudām. Tāpēc mēs arī gatavojamies kodu burbulis kārtošanas kas arī nav tik slikti. Neviens no tiem ir, ka slikti. Es zinu, viņi var likties mazliet biedējošu. Es zinu, kad es paņēmu klase, pat tad, kad es mācīja šo klasi pirmo reizi pagājušajā gadā, Man bija tāpat, kā es varu darīt? Tas ir jēga, teorētiski, bet Kā mēs patiešām to dara? Kas ir iemesls, kāpēc es arī gribu staigāt izmantojot kodu ar jums puiši šeit. Tāpēc man ir pseudocode par jums puiši šoreiz. Tik vienkārši paturiet to prātā, kā mēs esam par pāreju pāri. Tātad mums ir dažas skaitītājs, kas seko mūsu mijmaiņas darījumu, jo mums ir nepieciešams, lai pārliecinātos, ka ka mēs pārbaudīt to. Un mēs atkārtot visu masīvs kā mēs to tikko darījām ar šo piemēru. Ja elements pirms ir lielāks nekā pēc tam, kad mēs esam pie elements mēs mijmaiņas tiem, un mēs pieauguma OUR counter jo, tiklīdz mēs swap, mēs vēlamies, lai mūsu counter zina, ka. Kādi jautājumi tur? Kaut kas šķiet smieklīgi nekā šeit. STUDENTU: Vai jūs nosakāt skaitītāju uz nulli katru reizi, kad iet caur cilpu? Vai tu glabāt notiek atpakaļ uz nulli katru reizi? Instruktors: Ne vienmēr. Tātad, kas notiek, ir mēs ejam cauri šeit. Tā darīt, bet, atceries, tas veiks reizi bez neizdoties. Tātad, tas notiek, lai uzstādītu skaitītājs ir vienāds ar nulli, tad tas būs atkārtot, izmantojot. Kā tas vairākkārt uzsvērts cauri, tas tiks atjaunināta skaitītājs. Kā tas aktualizē skaitītājs, kad tas ir izdarīts, kad tas ir sasnieguši masīva, ja mūsu saraksts nav sakārtots, skaitītājs ir atjaunoti. 

Tātad tā pārbauda stāvokli un tā saka, OK, ir pretrunā lielāka par nulli. Ja tā ir, darīt to vēlreiz. Vēlaties atiestatīt tā, ka tad, kad jūs iet cauri, skaitītājs ir vienāds ar nulli. Ja jūs iet cauri sakārtots masīvs, nekas nemainās, tas neizdodas, un jūs atgriezt sakārtoti sarakstu. Vai tas ir jēga? STUDENTU: Tas varētu kādā mazliet. Instruktors: OK. Ja tur ir kāda cita jautājums, kas nāk uz augšu. Jā. 

STUDENTU: Kas būtu funkcija būt pārnešana elementus? 

Instruktors: Tātad mēs faktiski varam rakstīt ka, ja mēs ejam uz labo tagad. Atdzist. Tātad uz šo piezīmi, Alison notiek lai pārslēgtos atpakaļ uz ierīci. Tas būs jautri. Un mums ir jauka burbulis veida lieta šeit. Tāpēc es jau darīju riteņbraukšana caur masīvs. Mums ir mūsu mijmaiņas darījumus, kas ir vienāda ar nulli. Tāpēc mēs vēlamies, lai mijmaiņas blakus elementus, ja viņi no rīkojuma. Tātad pirmā lieta, mums ir nepieciešams, lai Vai ir atkārtot, izmantojot mūsu masīvs. 

Tātad, kā jūs domājat, ka mēs varētu atkārtot, izmantojot mūsu masīvu? Mēs esam par, un es ir vienāds ar 0. Mēs vēlamies, i būs mazāk nekā n mīnus 1 mīnus k. Un es paskaidrošu, ka sekundē. Tātad šī ir optimizācija šeit, kur, atceros, kā es teicu pēc katras caurlaide caur masīva mēs zinām, ka viss ir on-- 

Tātad, pēc tam, kad vienā piegājienā mums zinu, ka tas ir sakārtots. Pēc divām caurlaidēm mēs zinām ka tas viss ir sakārtots. Pēc trīs caurlaides mums zinu, ka ir sakārtoti. Tātad, kā es esmu atkārtojot caur masīvs šeit tas ir pārliecināties, lai tikai iet caur to, ko mēs zinām, ir nešķirotas. OK? Tas ir tikai optimizāciju. Jūs varētu uzrakstīt to naivi vienkārši atkārtojot caur visu, tas vienkārši nepieciešams ilgāks laiks. Ar šo četru cilpu tā ir tikai jauka optimizācija jo mēs zinām, ka pēc katras pilnas atkārtojuma caur masīvs šeit tāpat kā katru pilnu cilpa šeit, mēs zinām ka vēl viens no šiem elementiem tiks sakārtots beigās. 

Tāpēc mums nav jāuztraucas par tiem. Vai tas ir jēga visiem? Ka atdzist maz triks? Tātad, šajā gadījumā, ja mēs atkārtojot cauri, mēs zinām, ka mēs vēlamies, lai pārbaudītu, vai masīvs n un n + 1 ir kārtībā. OK. Tātad, šeit ir pseudocode. Mēs vēlamies, lai pārbaudītu, vai masīvs n un n plus 1 ir kārtībā. Tātad, ko mēs varbūt esam tur? Tas būs daži nosacījumu. Tas ir, ja. 

STUDENTU: Ja masīvs n mazāk nekā masīvs n plus 1. Instruktors: Mm-hm. Nu, ir mazāks vai lielāks nekā. STUDENTU: Lielāka nekā. Tad mēs gribam, lai mijmaiņas tiem. Tieši tā. Tāpēc tagad mēs nokļūt, kas ir mehānisms pārnešana viņiem? Tātad, mēs devāmies caur šo īsi, tipa mijmaiņas funkciju pagājušajā nedēļā. Vai kāds atceras, kā tas strādā? Tātad, mēs varam ne tikai pārcelt tos, vai ne? Jo viens no viņiem būs pazust. Ja mēs teikt, ir vienāda ar B un pēc tam B ir vienāds ar A, visi tie abi pēkšņi ir tikai vienāda ar B 

Tātad, kas mums ir jādara, ir mums ir pagaidu mainīgo, kas ir gatavojas rīkot mūsējais brītiņa mēs esam procesā pārnešana. Tātad, kas mums ir, ir mums būs dažas int temp ir vienāds kuri paredzēti, lai jūs varētu piešķirt to uz kuru jūs vēlaties, vienkārši pārliecinieties, ka jums sekot līdzi it-- tāpēc šajā gadījumā, es esmu gatavojas piešķirt to masīva n plus 1. Tāpēc, ka gatavojas rīkot neatkarīgi vērtība ir šajā otrajā blokā ka mēs meklējam. 

Un tad mēs varam darīt, ir, mēs varam iet priekšu un Piešķirt masīvs n plus 1, jo mēs zinām, mēs ir šo vērtību glabājas. Tas ir arī viens liels things-- Es nezinu, vai kāds no jums bija problēmas, kur, ja jūs slēdzis divas rindas kods pēkšņi viss strādāja. Rīkojums ir ļoti svarīgi CS. Tātad, pārliecinieties, ka jūs diagramma lietas, ja iespējams, par to, kas patiesībā notiek. Tāpēc tagad mēs ejam pārdalīt masīvs n plus 1, jo mēs zinām, mēs ir šo vērtību glabājas. 

Un mēs varam piešķirt, ka masīvu n vai šajā gadījumā masīva i. Pārāk daudz mainīgie. OK. Tāpēc tagad mēs esam no jauna masīvs I plus 1 līdz vienādai to, kas masīvā i. Un tagad mēs varam doties atpakaļ un piešķirt masīvs I ko? Ikviens? 

STUDENTU: 10. 

Instruktors: 10. Tieši tā. Un viena pēdējā lieta. Ja mēs esam samainīti to tagad, Kas mums jādara? Kas ir viena lieta kas notiek, lai pastāstītu mums Ja mēs kādreiz pārtraukt šo programmu? Kas saka, ka mums ir sakārtoti sarakstu? Ja mums nav jāveic nekādas mijmaiņas darījumus, vai ne? Ja mijmaiņas darījumiem ir vienāds ar nulles beigās to. Tātad, ja jūs veikt mijmaiņas, kā mēs tikko bija šeit, mēs vēlamies atjaunināt mijmaiņas darījumus. Un es zinu, tur bija Jautājums agrāk par jūs varat izmantot nulle vai viens tā vietā no patiess vai nepatiess. Un tas, ko tas dara šeit. Tātad šis saka, ja ne mijmaiņas darījumus. Tātad, ja mijmaiņas līgumi ir nulle, kas is-- es vienmēr saņemt savu patiesības un mani falses sajaukti. Mēs vēlamies, lai mēs novērtētu taisnība un tas nav. Tātad, ja tas ir nulle, tad tas ir viltus. Ja jūs noliegt to ar [? sprādziena?] tas kļūst taisnība. Tātad šī līnija izpilda. 

Patiesības un viltus un nullēm un tiem get crazy. Tikai ja tu lēnām staigāt caur to tas būs jēga. Bet tas, ko šis mazais mazliet koda šeit dara. Tātad tas pārbauda, mēs esam izdarījuši nekādus mijmaiņas darījumus. Tātad, ja tas ir kaut kas papildus nulle, tas būs viltus un viss ir gatavojas izpildīt vēlreiz. Forši? 

STUDENTU: Kāda pauze darīt? 

Instruktors: Break tikko pauzes jūs no cilpas. Tātad šajā gadījumā tas būtu tāpat kā beigt programmu un jūs vienkārši jūsu sakārtoti sarakstu. STUDENTU: Amazing. Instruktors: Es atvainojos? STUDENTU: Jo agrāk mēs izmantoja rakstīts 1 pār rakstīts nulle iesniegt, ka, ja kas strādā vai ne. 

Instruktors: Jā. Lai jūs varētu atgriezties nulle vai 1. Šajā gadījumā, jo mēs neesam reāli darīt kaut ko ar funkciju, Mēs vienkārši gribam, lai izjauktu. Mums nav īsti rūp to. Bremzes ir arī labi, ja tas ir izmantots, lai izrauties četru cilpas vai apstākļiem, kas Jūs nevēlaties, lai saglabātu izpildes. Tā vienkārši notiek, jūs no tām. Tas ir mazliet nianse lieta. Es jūtos kā tur ir daudz roku vicināšanu, tāpat kā jūs uzzināt par to drīz. 

Bet jūs varēsiet uzzināt par to drīz. Es apsolu. OK. Lai vai ikviens saņemt burbuļu veida? Ne pārāk slikti. Atkārtot, izmantojot, mijmaiņas lietas izmantojot temp mainīgs, un mēs visi, kas tur? Atdzist. Awesome. OK. Atpakaļ uz PowerPoint. Kādi jautājumi kopumā par šiem tik tālu? Atdzist. Mm-hm. 

STUDENTU: [dzirdams] int galvenais parasti. Vai jums ir, ka par šo? 

Instruktors: Tātad mēs vienkārši meklējam tikai faktiskajā šķirošanas algoritmu. Ja jums bija tā laikā piemēram, plašākas programmas, jums būtu int galvenais kaut kur. Atkarībā no tā, kur jūs izmantot šo algoritmu, tas varētu noteikt, kas ir tiek atdoti to. Bet mūsu gadījumā, mēs esam stingri meklē veidus, kā to dara reāli atkārtot, izmantojot masīvu. Tāpēc mums nav jāuztraucas par to. 

Tātad mēs runājam par labāko lietu un vissliktākie scenāriji bināro meklēšanu. Tātad, tas ir arī svarīgi darīt ka katrā no mūsu veidu. Tātad, ko jūs domājat, ir sliktākais gadījums runtime burbuļiem veida? Jūs guys atceries? 

STUDENTU: N mīnus 1. Instruktors: N mīnus 1. Tātad tas nozīmē, ka ir n mīnus 1 salīdzinājumi. Tik viena lieta saprast, ir ka uz pirmo atkārtošanu, mēs ejam cauri, mēs salīdzinām šie two-- tā ka ir 1. Šie divi, trīs, četri. Tātad, pēc viena atkārtojuma mums jau ir četri salīdzinājumus. Kad es runāju par runtime un n. N apzīmē skaitu salīdzināšanu atkarībā no tā, cik elementiem mums ir. OK? 

Tātad mēs ejam cauri, mums ir četri. Nākamreiz, kad jūs zināt, mums nav ir rūpēties par to. Mēs salīdzinām šīs divas, šie divi, šie divi, un, ja mums nav, ka optimizācijas ar četriem cilpa, kas man rakstīja, jums būtu salīdzināt šeit anyways. Tātad jums būtu palaist caur masīva un veikt salīdzinājumus n n reizes, jo katru reizi, kad mēs palaist caur to mēs kārtošanas viena lieta. 

Un katru reizi, kad mēs palaist cauri masīvs, mēs n salīdzinājumus. Tātad mūsu runtime ir tas, faktiski n rūtiņām, kas ir daudz sliktāks mūsu log beigām, jo ​​tas nozīmē, ja mums bija četri miljards elementi, tas ir gatavojas veikt mums četru miljardu brusas, nevis 32. Tāpēc ne labākais runtime, bet dažām lietām, jūs zināt, ja jūs laikā zināma virkne elementu burbulis kārtošanas var labi izmantot. 

OK. Tāpēc tagad to, kas ir labākais gadījums runtime? STUDENTU: Zero? Vai 1? 

Instruktors: Tātad 1 būtu viens salīdzinājums. Pa labi. 

STUDENTU: N mīnus 1? 

Instruktors: Tātad, jā. Tātad n mīnus 1. Ikreiz, kad jums ir koncepcija, piemēram, n mīnus 1, mums ir tendence tikai piliens to izslēgtu un mēs tikai teikt n tāpēc, ka jums ir lai salīdzinātu katru these-- katra pāra. Tātad tas būtu n mīnus 1, ko mēs mēs gribētu tikai teikt, ir aptuveni n. Ja jums ir darīšana ar runtime, viss ir tuvina. Tik ilgi, kamēr eksponents ir pareizi, tu esi diezgan labi. 

Tas, kā mēs galā ar to. Tā, ka labākajā gadījumā ir n, kas nozīmē, ka saraksts ir jau sakārtots, un viss, kas mums jādara, ir palaist cauri un pārbaudiet, vai tas ir sakārtoti. Atdzist. Labi. Tātad, kā jūs redzēt šeit, mēs vienkārši ir dažas vairāk grafikus. Tātad n brusas. Jautri. Daudz sliktāk, nekā n, kā mēs redzam, un daudz, daudz sliktāk, nekā log 2 n. Un tad jūs arī nokļūt log baļķiem. Un jūs lietojat 124, jūs nokļūt piemēram, log zvaigzne, kas ir kā traks. Tātad, ja jūs interesē, lookup log zvaigzne. Tas ir sava veida jautrību. Tāpēc mums ir šo lielisko diagrammu. Tikai galvu uz augšu, tas brīnišķīgi diagramma ir Jūsu vidusposmā, jo mēs ilgi uzdot jums šos thins. Tātad tikai galvu uz augšu, ir šo par jūsu vidusposma jūsu jauku apkrāptu lapas tur. Tātad mēs vienkārši paskatījās burbulis veida. Sliktākajā gadījumā, n brusas, labākajā gadījumā, n. Un mēs ejam apskatīt citiem. 

Un, kā jūs varat redzēt, vienīgais viens, ka tiešām labi ir apvienot kārtot, ko mēs nokļūt, kāpēc. Tāpēc mēs esam gatavojas doties uz nākamais here-- izvēle kārtošanas. Vai kāds atceras, kā atlase kārtošanas strādāja? Iet uz to. 

STUDENTU: Būtībā iet cauri pasūtījumu un izveidot jaunu sarakstu. Un, tāpat kā jūs liekot elementus in, nodot tos pareizajā vietā jaunajā sarakstā. 

Instruktors: Tāpēc, ka skaņas vairāk kā ievietošanas veida. Bet tu esi patiešām tuvu. Viņi ir ļoti līdzīgi. Pat man viņus jaukt reizēm. Pirms šajā sadaļā man bija, piemēram, jāgaida. OK. Tātad, ko jūs vēlaties darīt, ir izvēle kārtot, kā jūs varat iedomāties par to un to, kā Es pārliecinos, ka man mēģiniet nav iegūt viņiem jaukt, tas iet cauri un tas izvēlas mazākais skaits un tā liek, ka sākumā savu sarakstu. Tā mijmaiņas to ar šīs pirmās vietas. Viņi tiešām ir piemērs par mani. Awesome. Tik vienkārši veids, kā domāt par it-- atlases kārtot, izvēlētos mazāko vērtību. Un mēs ejam palaist caur piemēru ka es domāju, ka palīdzēs, jo Es domāju, Visuals vienmēr palīdzēt. Tātad sākam ar kaut ko tas ir pilnīgi nešķirotas. Red būs nešķiroti, zaļā tiks sakārtoti. Tas viss jēga sekundē. 

Tātad mēs ejam cauri, un mēs atkārtot no sākuma līdz beigām. Un mēs sakām, OK, 2 ir Mūsu mazākais skaitlis. Tāpēc mēs esam gatavojas pieņemt 2. un mēs braucam lai to pārvietotu uz priekšu mūsu masīva jo tas ir Vismazāk mēs esam. Tātad tas, ko tas dara šeit. Tas ir tikai gatavojas mijmaiņas šīs divas. Tāpēc tagad mums ir sakārtoti daļa, un nešķirotas sastāvdaļa. Un, kas ir labi atcerēties par atlases veida ir, mēs esam tikai izvēloties no nešķirotiem daļas. 

Šķiroto daļa jūs vienkārši atstāt vienatnē. Mm-hm? 

STUDENTU: Kā tas zina, kas ir mazākais bez salīdzinot uz jebkuru citu vērtību masīvā. Instruktors: Tas salīdzināt to. Mums patīk izlaidis to. Tas ir tikai vispārīgs visaptverošs. Yeah. Kad mēs rakstīt kodu es esmu pārliecināts, ka jums būs vairāk apmierināti. Bet vispirms jums saglabāt šo elements, jo mazākais. Jūs salīdzināt un jūs saka, OK, tas ir mazāks? Jā. Paturiet to. Lūk, tas ir mazāks? Nē? 

Šis ir jūsu mazākais, pārdalīt to savā vērtību. Un jūs būsiet daudz laimīgāki kad mēs ejam cauri kodu. Tātad mēs ejam cauri, mēs swap to, lai pēc tam mēs skatāmies uz šo nešķirotiem daļu. Tātad mēs ejam, lai izvēlētos trīs out. Mēs ejam, lai nodot to pie beigas mūsu šķirotas porcijas. Un mēs esam tikai gatavojas, lai saglabātu darot ka to dara, un dara to. Tātad šī ir mūsu veida pseudocode šeit. Mēs kodēt to šeit sekundē. Bet tikai kaut staigāt pa augstā līmenī. Jūs gatavojas aiziet no i ir vienāds ar 0 līdz n mīnus 2. Tas ir cits optimizāciju. Neuztraucieties pārāk daudz par to. Tātad, kā jūs sakāt. Kā Jēkabs tika sakot, kā mēs sekot līdzi tam, ko mūsu minimālais ir? Kā mēs zinām? Mums ir, lai salīdzinātu viss mūsu sarakstā. 

Tātad minimālā vienāds i. Tas ir tikai saprotams, šajā gadījumā indekss mūsu minimālās vērtības. Tātad tas būs atkārtot, izmantojot un tas iet no j vienāds i plus 1. Tātad mēs jau zinām, ka tas ir mūsu pirmais elements. Mums nevajag, lai salīdzinātu to ar sevi. Tātad mēs sākam salīdzinot to ar nākamo viens, kas ir iemesls, kāpēc tas ir man plus 1 līdz n mīnus 1, kas ir gals masīva tur. Un mēs teicām, ja masīvs at j ir mazāks nekā masīvs min, tad mēs pārdalīt kur Mūsu minimālais indeksiem. 

Un ja min nav vienāds ar i, kā to, kur mēs bijām atpakaļ vairāk nekā šeit. Tātad, kā tad, kad mēs pirmo reizi bija šo vienu. Šajā gadījumā, tā sākas nulle, tas galu galā ir divi. Tātad min nebūtu vienāds i beigās. Tas ļauj mums zināt, ka mums ir nepieciešams, lai mijmaiņas tiem. Es jūtos kā konkrētu piemēru palīdzēs daudz vairāk nekā šis. Tāpēc es ņemšu kods tas ar jums, puiši tieši tagad, un es domāju, ka tā būs labāk. 

Kārto tendence strādāt, ka veids, ka tas bieži vien ir labāk, tikai, lai redzētu tos. Tātad, ko mēs vēlamies darīt, ir mēs vispirms gribam mazākais elements savā nostājā masīvā. Tieši tas, ko Jēkabs teica. Jums ir nepieciešams, lai saglabātu, ka kaut kā. Tāpēc mēs esam gatavojas sākt šeit atkārtojot pār masīva. Mēs ejam, lai saka, tas ir mūsu Pirmais tikai sākt. Tātad mēs nāksies int mazākais ir vienāds ar bloku pie i. 

Tik viena lieta, lai paziņojuma, ik reizi tas cilpa izpilda, mēs sākam vienu soli tālāk. Kad mēs sākam mēs skatāmies uz šo vienu. Nākamajā reizē, kad mēs atkārtot, izmantojot, mēs sākot šo vienu un tas mūsu mazāko vērtību piešķiršanu. Tātad, tas ir ļoti līdzīgs burbulis kārtot kur mēs zinām, ka pēc tam, kad vienā piegājienā, šis pēdējais elements ir sakārtots. Ar atlases veida, tas ir tikai pretējo. 

Katrā pass, mēs zinām, ka Pirmais ir sakārtoti. Pēc tam, kad otrās pass, Otrs tiks sakārtoti. Un, kā jūs redzēja ar slaidu piemēriem, Mūsu sakārtoti daļa vienkārši turpina pieaugt. Tātad, nosakot mūsu vismazākais lai bloki i, visi tā dara ir sašaurināšanos, ko mēs meklējam, lai tādējādi lai līdz minimumam samazinātu salīdzinājumi mēs. Vai tas ir jēga visiem? Vai jums ir nepieciešams mani, lai palaistu cauri, ka atkal lēnāk vai dažādās vārdiem? Es esmu laimīgs. OK. 

Tātad mēs esam glabāšanai vērtība šajā brīdī, bet mēs arī vēlamies, lai saglabātu indeksu. Tātad mēs ejam, lai saglabātu nostāja mazākais viens, kas ir tikai būs i. Tāpēc tagad Jēkabs ir izpildīts. Mums ir lietas saglabāti. Un tagad mums ir jāskatās caur nešķiroti daļa masīva. Tātad, šajā gadījumā tas būtu mūsu nešķirotas. Tas ir i. OK. 

Tātad, ko mēs gatavojamies darīt būs par cilpu. Ikreiz, kad jums ir nepieciešams atkārtot, izmantojot masīvu, jūsu prāts varētu doties uz cilpu. Tātad kādu int k equals-- ko mēs domājam k gatavojas vienāds sākt ar? Tas ir tas, ko mēs, kas par mūsu mazākajiem vērtība, un mēs gribam, lai salīdzinātu to. Ko mēs vēlamies, lai salīdzinātu to ar? Tas būs tas nākamais, vai ne? Tāpēc mēs vēlamies k tiks inicializēts I plus 1, lai sāktu. 

Un mēs gribam k šajā gadījumā mēs jau lielums saglabāti šeit, tāpēc mēs varam tikai izmantot izmēru. Izmērs ir izmērs masīva. Un mēs vienkārši vēlamies atjaunināt k pa vienam katru reizi. Atdzist. Tāpēc tagad mums ir jāatrod mazākais elements šeit. Tātad, ja mēs atkārtot, izmantojot, mēs gribu teikt, ja masīvs pie k ir mazāks nekā mūsu mazāko value-- tas ir, ja mēs esam patiešām sekot, kas ir mazākais here-- tad mēs gribam pārdalīt ko mūsu mazākā vērtība ir. 

Tas nozīmē, ka, ak, mēs atkārtojot cauri šeit. Kāda vērtība ir šeit ir nav mūsu mazākais lieta. Mēs to nevēlamies. Mēs vēlamies pārdalīt to. Tātad, ja mēs pārformējot, ko darīt Jūs domājat, ka varētu būt šajā kodeksā šeit? Mēs vēlamies pārdalīt Mazākais un amats. Tātad, kas ir mazākais tagad? STUDENTU: Array k. Instruktors: Array k. Un kāda ir nostāja tagad? Kas ir indeksi Mūsu vismazākā vērtība? Tas ir tikai k. Tik masīvs k, k, tie sakrīt. Tāpēc mēs vēlējāmies pārdalīt to. Un tad pēc tam mēs atradām mūsu mazākais, tik beigās šis cilpas šeit mēs esam atraduši to, ko mūsu mazākais vērtība ir, tāpēc mēs vienkārši apmainītu to. Šajā gadījumā, tāpat kā teikt, ka mūsu mazākā vērtība ir šeit. Tas ir mūsu mazākā vērtība. 

Mēs vienkārši vēlamies, lai apmainītu to šeit, kas ir ko tas mijmaiņas funkcija apakšā darīja, ko mēs tikko rakstīja augšu kopā pāris minūtes atpakaļ. Tāpēc tas izskatās pazīstami. Un tad tas būs tikai atkārtot cauri, līdz tas sasniedz visu ceļu līdz beigām, kas nozīmē, ka jums ir nulle elementi, kas ir nešķiroti un viss pārējais ir sakārtota. Jēga? Nedaudz vairāk konkrētāk? Kods palīdzēt? 

STUDENTU: Par izmēru, jūs nekad tiešām definēt to vai mainīt to, kā tas zina? 

Instruktors: Tātad viena lieta paziņojums šeit ir int izmērs. Tātad mēs esam sakot, šajā sort-- veida ir funkcija šajā case-- tas ir atlase kārtot, tas ir pagājis kas ar funkciju. Tātad, ja tas nav nodots in, jūs varētu darīt kaut ko piemēram, ar garumu masīva vai jūs varētu atkārtot, izmantojot atrast garumu. Bet tāpēc, ka tas ir pagājis in, mēs varam vienkārši izmantot. Jūs vienkārši pieņemt, ka lietotājs tev derīgu izmēru, kas faktiski pārstāv izmērs jūsu masīvs. Forši? 

Ja jums puiši ir problēmas ar šīm vai vēlaties vairāk prakses kodēšanas veidu par savu, jums vajadzētu doties uz study.cs50. Tas ir instruments. Viņi ir pārbaudītājs, kas jūs faktiski var rakstīt. Viņi dara pseudocode. Viņi ir vairāk video un diapozitīvus tostarp tiem, es izmantot šeit. Tātad, ja jūs joprojām sajūta nedaudz izplūdušas, izmēģināt šo out. Kā vienmēr, nāk runāt ar mani, too. Jautājums? 

STUDENTU: Vai Jūs sakāt lielums ir iepriekš definēti? Instruktors: Jā. Lielums ir iepriekš definēts augšu šeit funkciju deklarācijā. Tātad jūs pieņemt, ka tas ir bijis pieņemts lietotājs, un vienkāršības dēļ, mēs esam gatavojas pieņemt, ka lietotājs deva mums pareizo izmēru. Atdzist. Tā ka ir izvēle kārtošanas. Puiši, es zinu, ka mēs esam mācīšanās daudz šodien. Tas ir blīvs dati sadaļā. Tātad ar to, ka mēs ejam doties uz ievietošanas veida. 

OK. Tātad, pirms tam mums ir jādara Mūsu runtime analīze šeit. Tātad labākajā gadījumā, apmierināt, jo es jums parādīja Man jau tabula veida deva to prom. Bet labākajā gadījumā runtime, ko mēs domājam? Viss sakārtots. N brusas. Kāds ir izskaidrojums kāpēc jūs domājat? 

STUDENTU: Jūs esat salīdzinot through-- Instruktors: Labais. Jūs salīdzināt cauri. Katrā atkārtojuma, lai gan mēs esam decrementing to ar vienu, jūs joprojām meklē caur viss, lai atrastu mazāko vienu. Tātad, pat ja jūsu vismazākā vērtība ir šeit sākumā, jūs joprojām salīdzinot pret visu pārējo lai pārliecinātos, ka tas ir mazākais lieta. Tātad, jūs galu galā darbojas cauri aptuveni n kvadrātā reizes. Labi. Un, kas ir sliktākajā gadījumā? Arī n brusas, jo jūs gatavojas lai dara, ka pati procedūra. Tātad šajā gadījumā, atlasi kārtošanas ir kaut kas ka mēs arī saucam paredzamā runtime. Tātad citiem, mēs tikai zinām augšējās un apakšējās robežas. Atkarībā no tā, cik traki mūsu saraksts ir vai cik nešķirotu tas ir, tās atšķiras no n vai n rūtiņām. Mēs nezinām. 

Bet tāpēc, ka atlases veida ir tas pats sliktāko un labākajā gadījumā, kas stāsta mums, ka Nav svarīgi, kāda ieejas veida mēs ir, vai tas ir pilnīgi šķirots vai pilnībā reverse sakārtots, tas ir gatavojas veikt tikpat daudz laika. Tātad šajā gadījumā, ja jums atceros no mūsu galda, tas tiešām bija vērtību, šie divu veidu nav, kas ir sagaidāms runtime. Tātad mēs zinām, ka ikreiz, kad mēs palaist atlases veida, tas ir garantēta palaist n brusas laiku. Nav mainīgums tur. Tas ir tikai gaidāms. Un atkal, ja jūs vēlaties, lai uzzinātu vairāk, ņem CS 124 pavasarī. Labi. Mēs esam redzējuši šo vienu. Atdzist. Tā ievietošanas kārtošanas. Un es esmu, iespējams, gatavojas aizsvilties caur šo. Man nebūs jūs guys kods to. Mēs vienkārši staigāt pa to. Tātad ievietošanas kārtošanas ir laipns no līdzīga atlases veida jo mums ir gan nešķiroti un sakārtoti daļu no masīva. 

Bet to, kas ir atšķirīgs ir tas, ka kā mums iet pa vienai, mēs vienkārši veikt neatkarīgi numurs ir nākamais mūsu nešķiroti, un pareizi šķirot to mūsu šķirotiem masīvs. Tas būs daudz lietderīgāk ar piemēru. Tātad viss sākas kā nešķirotu, tāpat kā ar atlases veida. Un mēs ejam, lai sakārtotu šo augošā secībā kā mēs esam bijuši. Tātad mūsu pirmā loka mēs uzņemtu pirmo vērtību un mēs sakām, OK, jūs esat Tagad sarakstā ar sevi. 

Jo jums ir sarakstā ar sevi, jums ir sakārtoti. Apsveicam ir Pirmais elements šajā masīvā. Jūs jau sakārtoti visu par savu. Tāpēc tagad mums ir sakārtoti un nešķirotas masīvs. Tāpēc tagad mēs pirmo reizi. Kas notiek starp šeit un šeit ir tas, ka mēs sakām, Labi, mēs ejam apskatīt Pirmā vērtība mūsu nešķirotos masīva un mēs braucam, lai ievadītu to tās pareiza vieta šķirotas masīvā. 

Tātad, ko mēs darām, ir mēs 5 un mēs sakām, OK, 5 ir lielāka par 3, tāpēc mēs vienkārši ievietojiet to tiesības pa labi no tā. Mēs esam labi. Tātad, tad mēs ejam uz mūsu nākamo. Un mēs 2. Mēs sakām, OK, 2 ir mazāk par 3, tāpēc mēs zinām, ka tā jābūt pie priekšā mūsu sarakstā tagad. Tātad, ko mēs darām, ir mēs push 3. un 5. leju un mēs virzāmies 2 vērā, ka pirmajā slotā. Tātad mēs esam tikai tā ievietošanas pareizajā vietā, tam vajadzētu būt. 

Tad mēs skatāmies mūsu nākamais, un mēs sakām 6. OK, 6 ir lielāks nekā viss mūsu šķirotas masīvā, tāpēc mēs vienkārši trāpi uz beigām. Un tad mēs skatāmies 4. 4, ir mazāka par 6, tas ir mazāk par 5, bet tas ir lielāks par 3. Tātad mēs vienkārši ievietojiet to labi vidū starp 3 un 5. Tāpēc, lai padarītu ka nedaudz nedaudz vairāk betona, šeit ir sava veida ideja par to, kas noticis. Tātad katram nešķirotiem elementu, mēs noteikt, kur šajā šķirotas daļu tas ir. 

Tātad, paturot prātā, ka šķiroti un nešķiroti, mums ir traversa cauri un skaitlis , kur tas iederas šķirotas masīvā. Un mēs ievietojiet to novirzot elementi, pa labi no tā uz leju. Un tad mēs tikai glabāt atkārtojot caur kamēr mēs ir pilnīgi sakārtoti sarakstu kur šķirotas tagad ir nulle un šķiroto aizņem veselums mūsu sarakstā. Tātad, atkal, lai padarītu lietas vēl vairāk betona, mums ir pseudocode. 

Tātad būtībā par i ir ir vienāds ar 0 līdz n mīnus 1, tas ir tikai garums mūsu masīvs. Mums ir kāds elements, kas ir vienāda ar Pirmais masīvs vai pirmie indeksi. Mēs, kas j, kas ir līdzvērtīga. Tātad, kamēr j ir lielāks nekā nulle un masīvs, j mīnus 1 ir lielāks nekā elements, lai visi, kas dara ir pārliecināties, ka Jūsu j tiešām pārstāv nešķiroti daļa masīva. 

Tāpēc, kamēr vēl ir lietas, kārtot un j mīnus viens is-- ko ir elements viņas? J nekad netika šeit definēts. Tas ir sava veida kaitinošas. OK. Anyways. Tātad j mīnus 1, jūs pārbaudīt elements pirms tā. Jūs sakāt, OK, ir elements Pirms kur es am-- pieņemsim faktiski izdarīt šo out. Tātad, teiksim, tas ir piemēram, par mūsu otro caurlaide. Tāpēc es būs vienāds 1, kas ir šeit. 

Tāpēc es būs vienāds ar 1. Tas ir 2, 4, 5, 6, 7. Labi. Tātad, mūsu elements, kas šajā gadījumā būs vienāds ar 4. Un mums ir dažas J, kas ir būs vienāds ar 1. Ak, j ir decrementing. Ka tas, ko tas ir. Tātad, j ir vienāds ar i, lai to, ko tas ir teiciens ir, ka mēs virzāmies uz priekšu, mēs esam tikai pārliecinoties ka mēs esam nav beigusies indeksējot šādā veidā, kad mēs cenšamies ievietot lietas mūsu sakārtoti sarakstā. 

Tātad, ja j ir vienāds ar 1, šajā gadījumā un masīvs j mīnus one-- tāpēc masīvs j mīnus 1 ir 2 Šajā case--, ja tas ir lielāks nekā elements, tad tas viss dara mainās lietas leju. Tātad šajā gadījumā, masīvs j mīnus viens būtu masīvs nulle, kas ir 2. 2, ir ne lielāks par 4, tāpēc tas neveic. Tāpēc pāreja nav uz leju. Kas tas šeit ir tikai pārvietot savu sakārtoti masīvs leju. Šajā gadījumā, faktiski, mēs varētu do-- pieņemsim padara šo 3. Tātad, ja mēs esam staigāt cauri ar šis piemērs, mēs esam tagad šeit. Tas ir sakārtots. Tas ir nešķirotas. Forši? Tātad, i ir vienāds ar 2, lai Mūsu elements ir vienāds ar 3. Un mūsu j ir vienāds ar 2. Tātad mēs skatāmies caur un mēs saka, OK, ir masīvs j mīnus viens lielāks nekā elements ka mēs meklējam? Un atbilde ir jā, vai ne? 4 ir lielāka par 3 un j ir 2, lai šis kods izpilda. 

Tāpēc tagad, ko mēs darām masīvs at 2, tāpēc tieši šeit, mēs mijmaiņas tiem. Tātad mēs tikai teikt, OK, masīvs pie 2 tagad būs 3. Un j gatavojas vienāds j mīnus 1, kas ir 1. Tas ir briesmīgs, bet jūs guys saņemsiet ideja. J tagad ir vienāds ar 1. Un masīvs j ir tikai būs vienāda ar mūsu elementu, kas bija 4. Es izdzēsti kaut man nevajadzētu ir vai miswrote kaut ko, bet jūs guys ideja. 

Tā kustēties n. Un tad, ja tas tā būtu, tas būtu cilpa atkal un tā teiktu, OK, j ir 1 tagad. Un masīvs j mīnus 1 tagad ir 2. Ir par 2 mazāk nekā mūsu elements? Nē? Tas nozīmē, ka mēs esam ievietota šo elementu pareizajā vietas mūsu šķirotiem masīvs. Tad mēs varam pieņemt to, un mēs sakām, Labi, mūsu sakārtots masīvs ir šeit. Un tas būtu nepieciešams šo numuru 6 un jābūt piemēram, OK, ir 6 mazāks nekā šo numuru? Nē? Atdzist. Mēs esam labi. 

Darīt to vēlreiz. Mēs sakām 7. Ir 7 mazāk nekā beigās Mūsu šķirotas masīva? Nē. Tātad mēs esam labi. Tātad tas būtu sakārtoti. Būtībā tas viss dara tas ir saprotams pārņemšanu no pirmā elementa Jūsu nešķiroti masīvs, izdomāt, kur tas notiek Jūsu šķirotiem masīvs. Un tas tikai rūpējas mijmaiņas darījumu, lai to izdarītu. Jūs būtībā vienkārši pārnešana līdz brīdim, kad tas ir īstajā vietā. Vizuālais tēls ir tas, ka tu esi virzās viss uz leju, darot to. 

Tātad, tas ir tāpat kā pusi burbulis šķirot-esque. Pārbaudiet pētījumu 50. Es ļoti ieteiktu mēģināt kodēt šo par savu. Ja jums ir kādi jautājumi vai vēlaties sk parauga kodu par ievietošanas veida, lūdzu, ļaujiet man zināt. Es esmu vienmēr apkārt. Tātad sliktākajā gadījumā runtime un labākajā gadījumā runtime. Kā jūs puisis redzēja no galda man jau parādīja, jums, tas ir gan n brusas un n. 

Tā veida iet nost no tā, ko mēs runājām aptuveni ar mūsu iepriekšējiem veidu, sliktākajā lieta runtime ir tas, ka tad, ja tas ir pilnīgi Nesašķirotas, mums ir salīdzināt visus šos n reizes. Mēs darām visu daudz salīdzinājumu jo, ja tas ir apgrieztā secībā, mēs ejam teikt, OK, šis ir tas pats, tas ir labi, un tas viens būs jāsalīdzina pret pirmo, lai tiktu pārvietots atpakaļ. Un, kā mēs pret astes gals, mums ir salīdzināt, salīdzināt, un salīdzināt pret visu. 

Tātad tas beidzas ar to, aptuveni n brusas. Ja tas ir pareizs, tad jūs saka, OK, 2, jūs labi. 3, jūs, salīdzinot ar 2. Jūs labi. 4, jūs vienkārši salīdzināt ar asti. Jūs labi. 6, salīdzināt ar astes, jūs esat labi. Tātad katru vietas, ja tas ir jau šķirots, jūs gūstat vienu salīdzinājumu. Tāpēc tas ir tikai n. Un tāpēc mums ir labākajā gadījumā runtime N un vissliktākajām Runtime n brusas, mums nav gaidīto runtime. 

Tas tikai atkarīgs haoss mūsu sarakstā tur. Un atkal, cits grafiku un citā tabulā. Tāpēc atšķirības starp veidu. Es esmu tikai gatavojas brīze cauri, es justies kā mēs esam plaši runājuši par to, kā viņi visu veidu no atšķiras un saistīt kopā. Tātad apvienot kārtošanas ir pēdējais Es nesa jums puiši ar. Mums ir diezgan krāsainu attēlu. Tātad apvienot kārtošanas ir rekursīvs algoritms. Tātad jūs guys zināt, ko rekursīvs funkcija ir? 

Ikviens grib teikt? Vēlaties izmēģināt? Tātad rekursīvo funkcija ir tikai funkcija, kas sevi dēvē. Tātad, ja jūs puiši ir pazīstami ar Fibonači secība, kas ir uzskatāms rekursīvs jo Jūs lietojat iepriekšējo divu un pievienot tos kopā lai saņemtu savu nākamo. Tātad rekursīvs, es vienmēr domāju, ka no recursion kā, piemēram, spirāli lai jūs, piemēram, spirāli uz leju tajā. Bet tas ir tikai funkcija kas sevi dēvē. 

Un, patiesībā, ļoti ātri es var parādīt, ko tas izskatās. Tātad rekursīvs šeit, ja mēs skatāmies, tas ir rekursīvs veids Apkopojot pār masīvu. Tātad viss, kas mums jādara, ir mums ir summa funkcija summa, kas ņem izmēru un masīvs. Un, ja pamanāt, izmērs samazinājumi pa vienam katru reizi. Un viss, tas ir, ja x ir vienāds ar zero-- tādēļ, ja izmērs masīva ir vienāds ar zero-- tas atgriež nulli. 

Pretējā gadījumā tas rezumē šo masīva pēdējais elements, un tad ņem summu pārējā masīva. Tātad tas ir tikai laužot to uz leju mazākās un mazākās problēmas. Garš stāsts īss, rekursijas, funkcija, kas sevi dēvē. Ja tas viss jums no šīs, tas ko rekursīvs funkcija. Ja esat lietojis 51, jūs saņemsiet ļoti, ļoti apmierināti ar recursion. Tas ir patiešām foršs. Tajā bija jēga, piemēram, 03:00 viena nakts. Un man bija, piemēram, kāpēc es neesmu nekad izmantot šo? 

Tātad sapludināšanas kārtošanas, būtībā ko tā gatavojas darīt, ir tā gatavojas lauzt to uz leju, un lauzt to uz leju, līdz tas ir tikai atsevišķus elementus. Atsevišķus elementus ir viegli sakārtot. Mēs redzam, ka. Ja jums ir viens elements, tas ir jau uzskatīja sakārtots. Tā tālāk ieejā n elementiem, ja n ir mazāks par 2, vienkārši atgriezties jo tas nozīmē, tas ir vai nu 0 vai 1, kā mēs esam redzējuši. Tie tiek uzskatīti šķirotas elementi. 

Pretējā lauzt to pusi. Kārtot pirmo pusgadu, šķirot otrā puse, un pēc tam apvienot tos kopā. Kāpēc to sauc sapludināšanas kārtošanas. Tāpēc mēs esam šeit mēs sakārtotu šos. Tāpēc mēs turpinām viņus līdz masīva izmērs ir 1. Tad, kad tas ir 1, mēs vienkārši atgriezties jo tas ir sakārtots masīvs, un tas ir sakārtots masīvs, un tas ir sakārtots masīvs, mēs visi sakārtots. Tātad, ko mēs darām, ir mums sākt apvienojot tos kopā. 

Tātad, kā jūs varat domāt par apvienošanu ir jūs vienkārši izņemt mazāks skaits katrai no apakšprogrammām bloki un vienkārši pievienot to parādījās masīvs. Tātad, ja paskatās šeit, kad mums ir šie komplekti mums ir 4, 6, un 1. Kad mēs vēlamies apvienot tos, mēs skatāmies uz šiem pirmajiem diviem un mēs sakām, OK, 1 ir mazāks, tā iet uz priekšu. 4 un 6, tur nekas, lai salīdzinātu to, vienkārši trāpi uz beigām. 

Kad mēs apvienot šos divus, mēs vienkārši ņem mazāko no šīm divām, tāpēc tas ir 1. Un tagad mēs mazāko no šīm divām, SO2. Mazāko no šiem diviem, 3. Mazāko no šīm divām, 4., 5., 6. Tātad jūs vienkārši novelkot tiem. Un tāpēc, ka tie esam iepriekš sašķiroti, Jums vienkārši ir viens salīdzinājums katru reizi tur. Tātad vairāk kodu šeit, tikai pārstāvība. Tātad, jūs sākat vidū un kārtot pa kreisi un pa labi un tad jūs vienkārši apvienot tos. 

Un mums nav kodu par apvienot tieši šeit. Bet, atkal, ja jums iet tālāk studēt 50, tas būs tur. Pretējā nāk runāt ar mani ja jūs joprojām sajaukt. Tik foršs lieta šeit ir tas, ka labākajā gadījumā, sliktākajā gadījumā, un sagaidāms runtime ir visas log n, kas ir daudz labāk, nekā mēs esam uzskatīta par pārējo mūsu veidu. Mēs esam redzējuši n kvadrātā un ko mēs patiesībā nokļūt ir n log n, kas ir lieliski. 

Paskaties, cik daudz labāk tas ir. Šāds jauka līkni. Tik daudz efektīvāku. Ja jūs kādreiz iespējams, izmantot apvienot kārtošanas. Tas ietaupīs jūsu laiku. Tad atkal, kā mēs teicām, ja jūs uz leju šajā apakšējā reģionā, tas nenozīmē, ka uzņēmums daudz atšķirību. Jums līdz tūkstošiem un tūkstošiem ieejas, Jūs noteikti vēlaties efektīvāku algoritmu. Un atkal, mūsu skaisto tabula visu veidu, ka jūs puiši šodien iemācījušies. 

Tāpēc es zinu, tas ir bijis blīvs dienā. Tas ne vienmēr notiek lai palīdzētu jums ar savu PSET. Bet es tikai gribu, lai atruna šī sadaļa ir ne tikai par psets. Viss šis materiāls ir godīgi spēle jūsu midterms. Un arī tad, ja jūs turpināt ar CS, Tie ir patiešām svarīgi pamati kas jums būtu jāzina. Tātad, dažas dienas būs nedaudz vairāk PSET palīdzība, bet dažas nedēļas būs daudz faktiskais saturs ka var nelikties super noderīga, lai jūs tieši tagad, bet es apsolu, ja jūs turpināt gada būs ļoti, ļoti noderīgs. 

Tā ka ir to sadaļā. Leju, lai vadu. Es to darīju vienas minūtes laikā. Bet tur jums iet. Un man būs virtuļus vai konfektes. Vai kāds ir alerģija pret kaut ko, starp citu? Olas un piens. Tātad donuts ir nē? OK. Labi. Šokolādes nē? Zvaigžņu dzimšanas. Starbursts ir labi. OK. Mēs ejam, lai būtu Starburst nākamnedēļ tad. Tas ir tas, ko es nopirkšu. Jums puiši ir lieliska nedēļa. Lasīt jūsu spec. 

Let me know, ja jums ir kādi jautājumi. PSET divas pakāpes būtu kas jums ar ceturtdien. Ja jums ir kādi jautājumi par to, kā es kaut ko šķiro vai kāpēc es šķiro kaut kā es tomēr, lūdzu, rakstiet man, nāc ar mani runāt. Es esmu mazliet traks tas nedēļā, bet es apsolu Es joprojām būs atbildēsim 24 stundu laikā. Tā ir lieliska nedēļu, ikvienam. Good luck par savu PSET.