[MUZIKO Ludante] 

ANDI PENG: Bonvenon semajno 3 de sekcio. Dankon, vi infanoj, por ĉiuj venontaj al tiu pli frua komenco tempo hodiaŭ. Ni havas belan, iom intima grupo hodiaŭ. Do espereble ni atingos finpoluro eble frue, iomete frue hodiaŭ. Tiel rapide, nur iuj anoncoj por la tagordo hodiaŭ. Antaŭ ni komencas, ni estas tuj ĝuste transiru iujn mallongajn loĝistikaj temoj, pset demandojn, debrief, aĵoj tiel. Kaj poste ni plonĝi juste. Ni uzos erarserĉilo nomita GDB al komenci desenmascarar nia kodo, kiun David klarigis en prelego la alia tago. Ni transiru la kvar tipoj de varoj. Ni iros super ilin bela rapide ĉar ili estas belaj intensivaj. Sed scias ke ĉiuj diapozitivoj kaj fontkodon ĉiam rete. Do bonvolu, en via legado, al reiru kaj rigardu tion. 

Ni iros tra asimptota skribmaniero, kiu estas nur ornama metodo diri "runtimes" kie ni havas la granda O, kiu Davido klarigis en prelego. Kaj ni ankaŭ havas la Omega, kiu estas la suba baro ekzekuto. Kaj ni parolos iom pli detala koncerne al kiel tiuj laboroj. Kaj laste, ni transiru duuma serĉo, ĉar multe de vi kiu havas jam rigardetis vian psets probable scias ke ke estas demando kiu estas en via pset. Do vi ĉiuj kontentus ke ni kovras ĉi hodiaŭ. 

Kaj fine, por via sekcio retrosciigon, mi efektive lasis ĉirkaŭ 15 minutoj je Fine nur iri super loĝistiko de pset3, demandojn, eble iom de gvidado, se vi volas, antaŭ ni komencos programado. Do ni provu trairi la materialo bela rapide. Kaj tiam ni povas elspezi iun tempon prenante pli demandojn por la pset. BONE. 

Rapide, tiel nur kelkaj anoncoj antaux ni komencos hodiaŭ. Unue, bonvenon al farante ĝin tra du el viaj psets. Mi prenis rigardu your-- yeah, ni akiri rondon de aplaŭdo por tiu. Fakte, mi estis vere, vere impresita. Mi prijuĝis la unua pset por vi infanoj lasta semajno kaj vi infanoj faris nekredeblan. 

Stilo estis sur punkto krom kelkaj komentoj. Certiĝu ke vi estas ĉiam komentante vian kodon. Sed via psets estis sur punkto. Kaj observu ĝin. Kaj ĝi estas bona por la lernojarano al vidu ke vi uloj estas metantaj en tiel penado en via stilo kaj via desegno en via kodo ke ni ŝatus ke vi vidu. Do mi pasante kune mian dankemon por la resto de la TAS. 

Tamen ekzistas kelkaj debrief demandoj Mi nur volas iri super tiu farus ambaŭ mia vivo kaj multajn el la aliaj TAS 'vivas iom pli facila. Unue, mi rimarkis tiun pasinteco week-- cuantos de ili estis kuranta check50 sur via kodo antaŭ sendi? BONE. Do ĉiuj devus esti faranta check50, because-- a secret-- ni efektive kuri check50 kiel parto de nia praveco skriptojn por testi vian kodon. Do se via kodo estas malsukcesanta check50, en ĉiu verŝajneco, ĝi estas probable tuj malsukcesos nia ĉeko ankaŭ. Kelkfoje vi infanoj rajtas respondoj. Kiel, en avida, kelkaj el vi rajtas nombroj, vi nur presi iun ekstran materialon. Kaj tiu ekstra materialo fakte mankas la ĉeko, ĉar la komputilo ne vere scias kio ĝi estas serĉanta. Kaj do ĝi nur kuras tra, vidi ke via eligo ne kongrui kion ni atendas la respondon esti, kaj marki ĝin estas malĝuste. 

Kaj estu kiu okazis en iuj viaj kazoj ĉi tiu semajno. Do mi revenis kaj permane regraded ĉies kodon. En la estonteco, tamen, bonvolu, bonvolu certiĝi ke vi uzas kontroli 50 en via kodo. Ĉar ĝi estas speco de doloro por la TA devos reiri kaj permane regrade ĉiu unuopa pset por ĉiu sola, iom maltrafis ekz. Do mi ne demetis neniun punktoj. Mi kredas ke mi deprenis eble unu aŭ du por dezajno. En la estonteco kvankam, se vi malsukcesanta check50, punktoj estos prenita ekstere por korekto. 

Plue, psets estas pro vendredo tagmeze. Mi kredas, ke estas sep-minuta malfrue graco periodo ke ni donu al vi. Po Harvard tempo, ili estas permesitaj sep minutojn malfrue al ĉio. Do tie ĉe Yale, ni aliĝas al tiu ankaŭ. Sed preskaux, je 12:07, se via pset estas ne en, ĝi tuj estos markita kiel malfrue. Kaj tiel dum estas markitaj tiom malfrue, la TA-- mi ankoraŭ tuj estos grading vian psets. Do vi devos ankoraŭ vidi lernojaro aperi. Tamen, sciu ke la fino de la semestro, ĉiuj malfrue psets nur estos aŭtomate zeroed per la komputilo. 

Ni faru tion por du kialoj. Unu, kelkfoje ni preni ekskuzis, kiel dekano de ekskuzoj, poste, ke mi ne scias pri ankoraŭ. Do ni ŝatus certigi ni grading ĉio ĉiaokaze, kiel, mi estas mankas dekano la ekskuzo. Kaj due, teni en menson, vi povas ankoraŭ delasi unu pset ke havas plenan amplekson punktoj. Kaj tiel ni ŝatas lernojaro ĉiuj viajn psets nur certigi ke via atingo la tie kaj vi provas ilin. Do eĉ se ĝi estas malfrue, vi ankoraŭ akiri krediton por atingo punktoj, mi pensas. 

Do moralo de la rakonto estas, faru certe via psets estas en sur-tempo. Kaj se ili ne estas en sur-tempaj, scias ke ĝi ne estas granda. Jes, antaŭ mi pluiru, ĉu iu havas demandojn pri pset sugestoj? Yeah. 

Spektantaro: Ĉu vi diras, ke ni povas fali unu el la psets? 

ANDI PENG: Yeah. Do ekzistas naŭ psets entuta dum de la semestro. Kaj se vi havas atingon points-- tiom medio estas nur, preskaux, vi provis la problemon, vi incitas en tempo, vi montrante, ke vi havas pruvis vi legis la specifon. Tio estas sufiĉe multe medio. Kaj se vi plenumante amplekso punktoj, ni povas fali la plej malalta unu el plena amplekso. Do jen en via avantaĝo kompletigi kaj provi ĉiu pset. 

Eĉ upload-- se neniu el ilin labori, alŝuti ilin cxiujn. Kaj tiam ni espereble povos doni al vi iom de tiuj punktoj reen. Malvarmeta. Aliajn demandojn? Granda. 

Due, oficejo hours-- kelkaj rapidaj notoj pri oficejo horoj. Do unue, venis frue en la semajno. Neniu estas iam ĉe oficejo horoj lunde. Christabel venis oficejo horoj lastan nokton. Yeah, Christabel. Kaj kion ni havas ĉe oficejo horojn hieraŭ nokte, Christabel? 

Publiko: Ni havis glaciaĵo. 

ANDI PENG: Do mi pravas, ni devis glaciaĵon ĉe oficejo horoj lastan nokton. Dum mi ne povas promesi al vi, ke ni devos glaciaĵon ĉe oficejo horoj ĉiusemajne, kion mi povas promesi al vi estas ke estos signife bona lernanto al TA rilatumo. Kiel legit, estas kiel tri al unu. Dum kiu, kontrastigi ke kun Ĵaŭdo, vi havas pri 150 vere emfazis infanoj kaj ne glaciaĵo. Kaj estas simple ne produktivaj por neniu. Do moralo de la rakonto estas, veni frue al oficejo horoj kaj bonaĵojn okazos. 

Ankaŭ, venis preparita demandojn. Vi scias? Sendepende de kion tas, mi pensas, estas jene: ni estis prenanta paron studentoj enirantoj ĵaŭde ĉe, kiel, 10:50 Ne leginte la spec estante kiel helpos min, helpu min. Bedaŭrinde en tiu punkto, ekzistas ne multe ni povas fari por helpi vin. Do bonvolu veni frue en la semajno. Venu frua al oficejo horoj. Venu preta fari demandojn. Certiĝu ke vi, kiel studento, estas kie Vi devas esti tiel ke la Tas povas gvidi vin kune, Kiu estas kio oficejaj horoj devus esti asignita por. 

Due, do mi scias instruistojn ŝatas surprizi nin kun provoj. Mi havis instruiston tiuj kiel, yo, cetere, memoru ke midterm vi havas sekva lundo. Jes, mi ne sciis pri tio midterm. Do mi tuj esti ke TA tio memorigas vin cxiujn ke kvizo 0-- ĉar, vi scias, ke ni estas CS. Nun ke ni faris arrays, vi ricevas kial estas kvizo 0, ne Kvizo 1, eh? BONE. Ho, mi ricevis kelkajn sonoj sur tiu unu. BONE. 

Do kvizo 0 Estos oktobro 14 se vi estas en la lundo-merkredo sekcio kaj oktobro 15 se vi estas en la mardo-ĵaŭdo sekcio. Tiu ne validas por tiuj el vi en Harvard who-- Mi pensas vin voli ĉiujn esti prenante vian kvizojn sur la 14a. 

Do jes, la proksima semajno, se Davido, en prelego, iras, Jes, do pri tio kvizo venontsemajne, vi ĉiuj ne estos ŝokitaj pro vi venis al sekcio kaj vi scios, ke via kvizo 0 estas en du semajnoj. Kaj ni devos revizii kunsidoj kaj ĉiu. Do ne maltrankviligas estanta timigita por tio. Demandojn before-- demandojn ĉe ĉiu lin relativa loĝistikaj problemoj, gradiganta, oficejo horoj, sekcioj? Yeah. 

Publiko: Do ​​la kvizo estas tuj estos dum prelego? 

ANDI PENG: Yeah. Do la kvizo, mi pensas, estas 60 minutoj asignitaj en tiu tempo fendo ke vi nur prenas en la prelego halo. Do vi ne devas veni en sur, kiel, hazarda 7:00 PM. Ĝi estas tute bona. Yeah. Malvarmeta. 

Bone. Do ni tuj enkonduki koncepto al vi tiu semajno ke Davido havas jam ia de tuŝis sur en prelego tiu pasinta semajno. Ĝi nomiĝas GDB. Kaj kiel multaj de vi, dum en la kurso de skribi vian psets, rimarkis grandan butonon kiu diras "Debug" sur la supro de via Ide? BONE. Do nun ni vere ricevas elterigi la mistero de kion tiu butono reale faras. Kaj mi garantias vin, ĝi estas bela, bela afero. 

Do ĝis nun, mi pensas tie jam du aferoj studentoj estis tipe faranta kiam elpurigi psets. Unu, ili aŭ aldoni en printf () - por ĉiu malmultaj linioj, ili aldonas en printf () - ho, kia estas tiu variablo? Ho, kio estas tiu variablo now-- kaj vi speco de vidi la progreson de via kodo kiel regente. Aŭ la dua metodo infanoj fari estas ke ili simple skribi la tutan aferon kaj poste iru kiel tiu ĉe la fino. Espereble ĝi funkcias. Mi garantias al vi, GDB estas bona ol ambaŭ de tiuj metodoj. Yeah. Do tiu estos via nova pli bona amiko. Ĉar ĝi estas bela afero ke vide ekranoj ambaŭ kion via kodo estas faranta je specifa punkto tiel kiel kion ĉiuj viaj variabloj estas portantinoj, kiel kio iliaj valoroj estas, en tiu specifa punkto. Kaj en ĉi tiu vojo, Vi povas vere fiksita breakpoints en via kodo. Vi povas kuri tra linio por linio. Kaj GDB simple devos por vi, montriĝas por vi, kio ĉiuj viaj variabloj estas, kion ili faras, kio okazas en la kodo. Kaj tiel, ĝi estas tiom pli facile vidi kio okazas anstataŭ printf-Ing aŭ notante vian deklaroj. 

Do ni faru ekzemplon de tio poste. Do tio ŝajnas iom abstrakta. Neniu ĉagrenoj, ni faros ekzemploj. Kaj tial esence, la tri plej grandaj, plej uzataj funkcioj vi bezonos en GDB estas la Next, Transpaŝi, kaj Paŝi en butonoj. Mi tuj gvidi super tie, vere, nun. 

Do vi povas vidi ke ĉiuj uloj aŭ ĉu mi zomi iom? En la dorso, vi povas vidi ke? Devus min zomi? Nur iomete? Bone, mojose. Tie ni marŝos. BONE. 

Do mi havas, tie, mia efektivigo por avidaj. Kaj dum multe de vi uloj skribis avidaj je dum buklo form-- ke estas perfekte akceptebla maniero fari it-- alia maniero fari ĝin estas simple dividi en la module. Ĉar tiam vi povas havi vian valoro kaj tiam havas viajn cetero. Kaj tiam vi povas simple aldoni ĝin ĉiuj kune. Ĉu la logiko de kion mi faras tie havas sencon por ĉiuj, antaŭ ni komencos? Speco de? Malvarmeta. Granda. Ĝi estas bela peco sexy de kodo, mi dirus. Kiel mi diris, Davido, en prelegi, post momento, vi ĉiuj komencas vidi kodo kiel iu kiu estas bela. Kaj kelkfoje kiam vi vidos belan kodo, ĝi estas tia mirinda sento. 

Do tamen, dum tiu kodo estas tre bela, ĝi ne funkcias konvene. Do ni kuras check50 sur tiu. Kontrolu 50 20-- OOP. 2? Ĉu pset2? Yeah. Ho, pset1. BONE. Do ni kuras check50. 

Kaj kiel vi infanoj povas vidi ĉi tie, ĝi estas malsukcesanta kelkaj kazoj. Kaj por iuj el vi, en la kurso de faras via problemo aroj, vi estas kiel, ah, kial ĉu ne laboras. Kial oni laboras por iu valoroj sed ne por aliaj? Nu, GDB tuj helpos vin figuro kial tiuj enigoj ne funkcias. 

BONE. Do ni vidas, unu el la ĉekojn mi maltrafis en check50 estis la eniga valoro de 0.41. Do la korekta respondo kiu vi devus esti akiranta estas 4. Sed anstataŭe, kion mi presi el Estas la 3-n, kiu estas malĝusta. Do ni nur kuri ĉi permane, nur certiĝu ke check50 laboras. Ni faru ./greedy. Oops, Mi devi fari avidaj. Tie ni marŝos. Nun ./greedy. 

Kiom estas ŝuldis? Ni faru 0.41. Kaj Yep, ni vidos tie ke ĝi estas elirigi 3 kiam la ĝusta respondo, fakte, devus esti 4. Do ni eniras GDB kaj vidi kiel ni povas promenadi fiksi tiun problemon. 

Do la unua paŝo en ĉiam elpurigi vian kodon Estas agordi Haltpunkto, aŭ punkto je kiu vi volas la komputilo aŭ la erarserĉilo komenci rigardanta. Do se vi ne vere scias kion via problemo estas, kutime, la tipa afero ni volas fari estas starigis Haltpunkto ĉe nia ĉefa. Do se vi infanoj povas vidi ĉi ruĝa butono dekstre tie, Yep, ke estis mi fiksanta Haltpunkto por la ĉefa funkcio. Mi klakas tion. 

Kaj tiam mi povas iri ĝis mia Debug butonon. Mi batis tiun butonon. Lasu min zoom reen eksteren se mi povas. Tie ni marŝos. Do ni havas, tie, panelo dekstre. Mi bedaŭras, knaboj en la dorso, vi ne povas vere vidi vere bone. Sed esence, ĉiuj ĉi tiu rajto panelo faras estas konservanta trako de ambaŭ la elstarigita linio, kiu estas la linio de kodo ke la komputilo estas nuntempe kuranta, tiel kiel ĉiuj viaj variabloj malsupren tie. 

Do vi hvas cendoj, moneroj, n, ĉiuj deklaris al malsamaj aferoj ĉe tiu punkto. Neniu ĉagrenoj, ĉar ni ne vere pravalorizitaj ilin al ajna variabloj ankoraŭ. Do en via komputilo, via komputilo estas nur vidante, ho, 32767 estis la lastan uzitan funkcio de tiu memoro spaco en mia komputilo. Kaj tiel tio estas kie cendoj aktuale estas. Sed neniu kiun fojo vi kuras la kodon, ĝi devus iĝi pravalorizitaj. 

Do ni iru tra, linion post linio, kio okazas ĉi tie. BONE. Do supren tie estas la tri butonoj kiuj mi ĵus klarigis. Vi havas la Play, aŭ la Run funkcio, butonon, vi havas la Transpaŝi butonon, kaj vi ankaŭ havas la Paŝo al butonon. Kaj esence, ĉiuj tri ili simple iru tra via kodo kaj fari malsamajn aferojn. 

Do tipe, kiam vi elpurigante, ni ne volas nur batis Play, ĉar Play simple kuri via kodo al la fino de ĝi. Kaj tiam vi ne reale scias kion via problemo estas krom se vi agordi multnombraj breakpoints. Se vi fiksis multoblaj breakpoints, ĝi simple aŭtomate kuri el unu Haltpunkto, al la sekva, la sekvanta. Sed en ĉi tiu kazo ni havas nur tiu, ĉar ni volas labori nian vojon de supro malsupren al fundo. Do ni tuj ignori ke butono nun por celoj de ĉi tiu programo. 

Do la Transpaŝi funkcio nur ŝtupojn super ĉiu unuopa linio kaj informas vin kio la komputilo faras. La Paŝo en funkcio iras en la fakta funkcio jen sur viaj linio de kodo. Do ekzemple, kiel printf (), ke estas funkcio, ĉu ne? Se mi volis fizike paŝo en la printf () funkcio, Mi vere iru en la peco de kodo kie printf () estis skribita kaj vidu kio okazas tie. 

Sed tipe, ni supozas ke la kodo kiun ni donos al vi laboras. Ni supozu la printf () laboras. Ni supozas ke GetInt () laboras. Do ne estas bezono paŝi en tiuj funkcioj. Sed se estas funkcioj ke vi skribu mem ke vi volas kontroli kio okazas, vi volus paŝi en tiu funkcio. 

Do ĝuste nun ni ĵus tuj paŝi super ĉi koderon. Do ni vidu. Ho, presi, "Ho hai, kiom multe ŝanĝo ŝuldis? " Ni ne zorgas. Ni scias ke estas laborante, do ni transpaŝas ĝin. 

Do n, kiu estas nia kaleŝego ke ni havas initialized-- aŭ declared-- supre ĉe la supro, ni estas nun egalante ke GetFloat (). Do ni transpaŝas tio. Kaj ni vidos ĉe la fundo tie, la programo estas instigante min eniga valoro. Do ni enigo la valoro ni volas testi tie, kio estas 0.41. Granda. 

Do nun n-- vi uloj vidi tie, ĉe la bottom-- estas stored-- ĉar ni ne rondoforma tamen, ĝi estas stokitaj en ĉi kiel giganto kaleŝego ke estas 0,4099999996, kiuj estas sufiĉe proksimaj al nia celoj, nun, al 0.41. Kaj tiam ni vidos poste, kiel ni daŭrigi paŝante super la programo, post ĉi tie, n fariĝis rondoformaj kaj cendoj fariĝis 41. Granda. Do ni scias ke nia rondigas laboral. Ni scias, ke ni havas la korekta nombron de cendoj, tial ni scias ke tio ne vere la problemo. 

Do ni daŭre tretante en tiu ĉi programo. Ni iru tien. Kaj do post tiu linio de kodo, ni povosciu multaj kvaronoj ni havas. Ni ne transpaŝas. Kaj vi vidas ni, fakte, havas unu kvarono ĉar ni subtrahita 25 de nia komenca valoro de 41. Kaj ni havas 16 maldekstra por nia cendoj. 

Ĉu ĉiuj komprenas kiel la programo estas paŝanta tra kaj kial cendoj nun fariĝis 16 kaj kial, nun, moneroj fariĝis 1? Ĉu ĉiuj sekvante tiu logiko? Malvarmeta. Do kiel de tiu punkto, la programo laboras, ĉu ne? Ni scias ĝi estas faranta ekzakte kion ni volas ke ĝi. Sed ni ne reale devas presi, ho, kia estas cendoj ĉe tiu punkto, kio estas moneroj ĉe tiu punkto. 

Daŭre irante tra la programo. Transpaŝi. Malvarmeta. Ni transiru dimes. Granda. Ni vidos ke ĝi estas prenita for $ 0.10 por groŝon. Kaj nun ni havas du monerojn. Tio ĝustas. 

Ni transiru pencoj kaj ni vidas ke ni havas superflue cendoj. Hmm, jen stranga. Tie supre en la programo, mi supozis esti subtrahita mia pencoj. Eble mi nur ne estis faranta tion linio pravas. Kaj ho ve, vi povas vidi tie, ĉar ni scias ke ni tretas tra linioj 32 kaj 33, tio estas kie nia programo nedece havis variabloj kuri. Do ni povas rigardi kaj vidi, ho, Mi subtrahadon cendoj tie, sed mi ne reale aldonante al mia monera valoro. Mi aldonante al cendoj. Kaj mi ne volas aldoni al cendoj, mi volas aldoni al moneroj. Do se ni ŝanĝu tion al moneroj, ni havas funkciantan programon. Mi povas kuri check50. Vi povas simple eliri el GDB dekstra tie kaj poste ekzekuti check50 denove. Mi povis nur fari tion. Mi devas fari avidaj. 0.41. Kaj tie, ĝi estas presanta el la ĝustan respondon. 

Do kiel vi uloj povas vidi, GDB estas vere potenca ilo cxar ni ja havas multe kodo irante plu kaj tiel multaj variabloj ke estas malfacile por ni, kiel homa, spuri. La komputilo, en la GDB erarserĉilo, havas la kapablon konservi trako de ĉio. Mi scias, en Visionaire, vi uloj verŝajne eble trafis iuj segmentación misfarojn ĉar vi kuradis el baroj de via tabelo. En la ekzemplo de Cezaro, jen precize kion mi implementado tie. 

Do mi forgesis kontroli por kio okazus se mi ne havu du komandlinio argumentoj. Mi nur ne metis en tiu ĉeko. Do se mi kuros Debug-- mi turnis mia Haltpunkto dekstren tie. Mi kuros Debug. 

BONE. Yeah. Do efektive, GDB laŭsupoze diri tion al mi tie Estis segmentación kulpo tie. Mi ne scias kio okazas Dekstre, sed kiam mi kuris ĝin, laboris. Kiam vi kuri linioj de kodo per kaj GDB nur povus subite forlasi vin, iru kaj rigardu kion la ruĝa eraro estas. Ĝi diros al vi, hej, vi havis segmentación kulpo, kio signifas ke vi provis aliri spaco en tabelo kiu ne ekzistis. Yeah. 

Do en la sekva problemo starigis ĉi semajno, vi infanoj probable havos multajn variabloj ŝvebantan. Vi ne tuj esti certa kio ili ĉiuj signifi je certa punkto. Do GDB vere helpos vin en elŝeligi el kio ili estas ĉiuj egalante kaj povante vidi ke vide. Estas iu konfuzita sur kiel iu el kiuj estis laboranta? Malvarmeta. Bone. Do post tio, ni estas tuj plonĝi dekstra en kvar malsamaj tipojn de varoj por tiu semajno. Kiel multaj el vi, unue de ĉiuj, antaŭ ol ni komencu, legis la tutan spec por pset3? BONE. Mi fieras de vi uloj. Tio estas kiel la duono de la klaso, kiuj estas signife pli ol lastfoje. 

Do jen granda, ĉar kiam ni parolas pri la enhavo en lecture-- aŭ bedaŭras, en section-- Mi ŝatas rilatigi multajn ke reen al kion la pset estas kaj kiel vi volas efektivigu, ke en via pset. Do se vi venas havante legi la spec, ĝi devos esti multe pli facila por vi kompreni kion mi parolas, kiam mi diras, Oh hey, tio povus esti vere bona loko por apliki ĉi varon. Do tiuj el vi kiuj legis la Spec scias ke, kiel parto de via pset, vi tuj devos Skribi tipo de varo. Do tio povas esti tre helpema cxar multajn vi hodiaŭ. 

Do ni dividi kun, esence, la plej simpla tipo de varo, la selektado varon. La tipa algoritmo por kiamaniere ni irus pri tiu is-- David iris tra tiuj ĉiuj en prelego, do mi rapide movi kune here-- estas esence, vi havas tabelo de valoroj. Kaj tiam vi trovos la malgranda unsorted valoro kaj vi interŝanĝu tiun valoron kun la unua unsorted valoro. Kaj tiam vi simple observu ripetante kun la resto de via listo. 

Kaj jen vida klarigo de kiel kiu laborus. Do ekzemple, se ni devis komenci kun tabelo de kvin elementoj, indekso 0 ĝis 4, kun 3, 5, 2, 6, kaj 4 valoroj metitaj en la tabelo do nun, ni nur tuj supozi ke ili ĉiuj unsorted cxar ni ne provis alie. 

Do kiel selektado speco volus laboro estas ke ĝi farus unua kuri tra la tuteco de la unsorted tabelo. Estus atentaro la plej malgranda valoro. En tiu kazo, 3, dekstra nun, estas la plej malgranda. Ĝi alvenas al 5. Nope, 5 ne estas granda than-- aŭ bedaŭras, ne malpli than-- 3. Do la minimuma valoro estas ankoraŭ 3. Kaj tiam vi atingos 2. La komputilo vidas, ho, 2 estas malpli ol 3. 2 devas nun esti la minimuma valoro. Kaj do 2 svopoj kun tiu unua valoro. 

Do post unu enirpermesilo, ni ja vidos ke la 2 kaj la 3 estas interŝanĝitaj. Kaj ni ĵus tuj daŭre fari ĉi denove kun la resto de la tabelo. Do ni tuj simple kuri tra la lastaj kvar indeksoj de la tabelo. Ni vidos ke 3 estas la sekva minimuma valoro. Do ni tuj interŝanĝi ke kun 4. Kaj tiam ni ĵus tuj teni kurante tra ĝis, finfine, vi akiri al ordo tabelo en kiu 2, 3, 4, 5, kaj 6 estas ĉiuj ordigitaj. Ĉu ĉiuj komprenas la logikon de kiel selektado speco laboras? 

Vi nur devas ian de minimuma valoro. Vi konservanta trako de kio tio estas. Kaj kiam vi trovas ĝin, vi interŝanĝi ĝi kun la unua valoro en la tabelo aŭ, ne la unua value-- la sekva valoro en la tabelo. Malvarmeta. 

Do kiel vi infanoj ia ekvidis de mallonga ekvido, ni tuj _Pseudocode_ ĉi ekstere. Do se vi infanoj en la dorso volas ariĝi, ĉiuj ĉe tablo povas formi iom partnero, mi tuj doni vin uloj kiel tri minutoj nur paroli tra la logiko, en la angla, de kiel ni eble povus apliki _pseudocode_ skribi selektado varon. Kaj estas bombono. Bonvolu veni kaj peti dolĉaĵoj. Se vi estas en la dorso kaj vi volas sukeraĵo, kaj mi povas ĵeti dolĉaĵoj ĉe vi. Fakte, Fari you-- malvarmeta. Ho, pardonon. BONE. 

Do se ni volus, kiel klaso, registran _pseudocode_ cxar kial oni povus alproksimigi tiun problemon, nur bonvolu. Mi nur ĉirkaŭiri kaj, en ordo, petu grupoj por la sekva linio de kion ni devus fari. Do se vi infanoj volas komenci malproksime, kio estas la unua aĵo fari kiam vi provas apliki metodon solvi ĉi programo elekte ordigi liston? Ni simple supozi ni havas tabelo, bone? 

Spektantaro: Vi volas krei iun ia [inaudible] ke vi estas kurante tra via tuta tabelo. 

ANDI PENG: Dekstra. Do vi tuj volas persisti tra ĉiu spaco, dekstra? Do, granda. Se vi infanoj volas doni al mi la sekva line-- yeah, en la dorso. 

Publiko: Kontrolu ilin ĉiuj por la plej eta. 

ANDI PENG: Tie ni marŝos. Do ni volas iri tra kaj kontrolu vidi kion la minimuma valoro estas, ĉu ne? Mi tuj mallongigi tion al "min." Kion vi infanoj volas fari post vi trovis la minimuman valoron? 

Spektantaro: [inaudible] ANDI PENG: Do vi tuj volas ŝanĝi ĝin per la unua el tiu tabelo, dekstra? Jen komence, mi intencis diri. Bone. Do nun ke vi interŝanĝis la unuan Ho, kion vi volas fari poste? Do nun ni scias ke ĉi tiu tie devas esti la plej malgranda valoro, dekstra? Tiam vi havas aldonan resto de la tabelo jen unsorted. Do kion vi volas fari tie, se vi uloj volas doni al mi la sekva linio? Publiko: Sekve vi volas persisti tra la resto de la tabelo. ANDI PENG: Yeah. Kaj tiel kion faras ripetanta tra ia implicas ni probable bezonas? Kio tipo of-- 

Publiko: Ho, plia variablo? ANDI PENG: Probable alia por buklo, ĉu ne? Do ni probable tuj volas persisti through-- granda. Kaj tiam vi tuj reiri kaj probable kontroli la minimuma denove, dekstra? Kaj vi tuj daŭre ripetante tiu, ĉar la maŝojn simple tuj teni kuranta, dekstra? 

Do kiel vi uloj povas vidi, ni nur havas ĝeneralan _pseudocode_ de kiel ni volas tiun programon rigardi. Ĉi tie ripeti, kion ni faras tipe bezonas skribi en nia kodo se ni volas persisti tra tabelo, kio tipo de strukturo? Mi pensas Christabel jam diris ĉi tion antaŭe. 

Publiko: A por buklo. 

ANDI PENG: A por buklo? Ekzakte. Do tiu estas probable tuj esti por buklo. Kio estas ĉekon tie tuj implicas? Tipe, se vi volas kontroli se io estas io else-- 

Publiko: Se. 

ANDI PENG: An se, dekstra? Kaj tiam la interŝanĝa tie, ni transiru poste, ĉar Davido iris tra kiuj en prelego ankaŭ. Kaj tiam la dua ripeti implies-- 

Publiko: Alia por buklo. 

ANDI PENG: --another por buklo, ekzakte. Do se ni serĉas ĉe ĝuste tiu, ni povas vidi, ke ni verŝajne tuj bezonas por buklo nestitaj kun kondiĉa deklaro tien kaj tiam fakta peco de kodo kiu estas tuj interŝanĝi la valorojn. Do mi ĵus ĝenerale skribita _pseudocode_ kodo tie. Kaj tiam ni efektive tuj fizike, kiel klaso, provu apliki tiun hodiaŭ. Ni iru returne en tiu IDE. 

Uh-oh. Kial estas ke not-- tie ĝi estas. BONE. Pardonu, lasu min provi zomi iom pli. Tie ni marŝos. Ĉiuj mi faras ĉi tie estas mi kreis programo nomata "selektado / sort.c." Mi kreis tabelon de naŭ valoroj, 4, 8, 2, 1, 6, 9, 7, 5, 3. Nuntempe, kiel vi povas vidu, ili estas neordigitaj. n tuj estos la nombro kiu diras al vi la kvanton de valoroj vi havas en via tabelo. En tiu kazo, ni havas naŭ valoroj. Kaj mi ĵus ricevis por buklo tie kiu presas el la unsorted tabelo. 

Kaj fine, mi ankaŭ ricevis por buklo ke nur presas ĝin denove. Do teorie, se tiu programo korektan funkcion, fine, Vi devus vidi presita por buklo en kiu 1, 2, 3, 4, 5, 6, 7, 8, 9 estas ĉiuj korekte en ordo. 

Do ni havas nian _pseudocode_ tie. Ĉu iu volas to-- mi estas nur tuj iru peti volunteers-- diru al mi precize kion tajpi se Ni volas, unua, nur persisti tra la komenco de tiu tabelo? Kio estas la linio de kodo mi estas verŝajne tuj bezonos ĉi tie? 

Spektantaro: [inaudible] 

ANDI PENG: Yeah, senti libera to-- bedaŭras, vi ne devas stari up-- sento libera levi vian voĉon iom. 

Publiko: Por int i egalas 0-- 

ANDI PENG: Jes, bone. 

Publiko: mi estas malpli ol tabelo longo. 

ANDI PENG: Observu do en gravas tie, ĉar ni ne havas funkcion kiu diras al ni la longo de tabelo, ni jam havas valoro kiu stokas tio. Dekstra? Alia afero teni en mind-- en tabelo de naŭ valoroj, kio estas la indeksojn? Ni simple diru tiu tabelo estis 0 al 3. Vi vidos ke la lasta indekso estas fakte 3. Ĝi ne estas 4, kvankam ekzistas kvar valoroj en la tabelo. 

Do tie, ni devas esti tre zorgema de kio nia kondiĉo por la longo tuj estos. 

Spektantaro: Ĉu ne estus n minus 1? ANDI PENG: Ĝi tuj n minus 1, ĝuste. Ĉu tio havas sencon, kial ĝi estas n minus 1, ĉiuj? Estas ĉar tabeloj estas nulo-indeksitaj. Ili komencas je 0 kaj kuri ĝis n minus 1. Jes, ĝi estas iom malfacila. BONE. Kaj tiam-- Publiko: Isnt'1 ke jam prizorgita de tamen, por nur ne diri "malpli ol aŭ egala al "kaj nur diras" malpli ol? " 

ANDI PENG: Tio estas vere bona demando. Do, jes. Sed ankaŭ, la vojo kiun ni estas efektiviganta la kontrolanta pravas, vi devas kompari du valoroj. Do vi vere volas forlasi la "al" malplenaj. Ĉar se oni komparas ĉi tiu, vi ne tuj havas nenion post ĝi kompari al, dekstra? Yeah. Do i ++. Ni aldonu nian krampoj en. Whoops. Granda. Do ni havas la komenco de nia ekstera buklo. Do nun ni probable volas krei variablon por konservanta trako de la plej malgranda valoro, dekstra? Ĉu iu volas doni min la linion de kodo kiu faros tion? Kion ni bezonas, se ni iras voli stoki ion? 

Dekstra. Eble pli bona nomo por tiu estus be-- "temp" plene works-- eble pli trafe nomita estus, se ni volas la plej malgranda value-- 

Publiko: Min. ANDI PENG: min, tie ni iras. min estus bona. Kaj tiel tie, kion ni faras volas pravalorizi ĝin? Tio estas iom malfacila. Ĉar nun en la komencante de tiu tabelo, vi ne rigardis ion, ĉu ne? Do kion, aŭtomate, se ni ĵus estas sur i egalas 0, Kion ni volas pravalorizi nia unua minimuma valoro al? Publiko: i. ANDI PENG: i, precize. Christabel, kial ni volas pravalorizi ĝin al mi? 

Publiko: Ĉar, nu, Ni komencas kun 0. Do ĉar ni havas nenion por kompari ĝin, la minimuma finos esti 0. 

ANDI PENG: Ekzakte. Do ŝi estas ekzakte pravas. Ĉar ni ne reale rigardis ion ankoraŭ, ni ne scias kion niaj minimuma valoro estas. Ni volas nur pravalorizi ĝin al i, kiu, nuntempe, estas ĝuste ĉi tie. Kaj ni daŭre movi malsupren tiu tabelo, ni vidos ke, kun ĉiu aldona enirpermesilo, i pliigoj. Kaj tiel en tiu punkto, i estas probable tuj voli esti la minimumo, ĉar ĝi estas tuj estos ajn estas la komenco de la unsorted tabelo. Malvarmeta. 

Do nun ni volas aldoni por buklo tie jen tuj persisti tra la unsorted, aŭ la resto de tiu tabelo. Ĉu iu volas doni min linion de kodo kiu faros tion? Hint-- kion ni bezonas cxi tie? Kio okazas iri en ĉi por buklo? Yeah. Publiko: Do ​​ni dezirus havas malsaman entjero, ĉar ni kuris tra la resto de la tabelo anstataŭ la i, do eble j. 

ANDI PENG: Yeah, j sonas bona al mi. Egalas? 

Publiko: Do ​​estus i plus 1, ĉar vi komencas je la venonta valoro. Kaj tiam al la end-- tiel denove, j estas malpli ol n minus 1, kaj tiam j ++. ANDI PENG: Granda. 

Kaj tiam tie, ni tuj volas kontroli por vidi se nia kondiĉo estas konita, dekstra? Ĉar vi volas ŝanĝi la minimuma valoro se ĝi estas fakte pli malgranda ol kion vi komparante ĝin, ĉu ne? Do kion ni tuj volas tien? Kontrolu vidi. Kio tipo de deklaro ni probable tuj TI volas uzi se ni volas kontroli ion? 

Publiko: An se aserto. 

ANDI PENG: An se aserto. Do if-- kaj kio tuj estos kondiĉe ke ni volas ene de niaj se aserto? 

Publiko: Se la valoro de j estas malpli ol la valoro de i-- 

ANDI PENG: Ekzakte. Do if-- tiel ĉi tabelo estas nomata "array". Granda. Do se tabelo kio estis tio? Diru tion denove. 

Publiko: Se tabelo-j estas malpli ol tabelo-i, tiam ni ŝanĝus la min. Do la min estus j. 

ANDI PENG: Ĉu tio sencon? BONE. Kaj nun cxi tie, ni reale volas apliki la swap, dekstra? Do memoru, en prelego, David, kiam li klopodis interŝanĝi the-- kio it-- oranĝa suko kaj milk-- 

Publiko: Tio estis malpuraj. 

ANDI PENG: Jes, tio estis speco de malneta. Sed estis sufiĉe bona koncepto pruvante fojo. Do pensu pri viaj valoroj tie. Vi havas tabelo de min, tabelo de i, aŭ kion ajn ni provis interŝanĝi tie. Kaj vi verŝajne ne povas verŝi ilin en reciproke samtempe, ĉu ne? Do kion ni tuj al devas krei ĉi tie Por interŝanĝi la valorojn korekte? 

Publiko: Labor variablo. 

ANDI PENG: Labor variablo. Do ni faru int temp. Vidu, tio estus bona tempo to-- Whoa, kio estis tio? BONE. Do tiu estus estinta pli bona tempo nomumi la variablo "temp." Do ni faru int temp. Kio estas ni iranta fiksita temp egala al tie? Publiko: min? ANDI PENG: Estas iom malfacila. Ĝi efektive ne gravas en la fino. Negrave kio Por vi elektas interŝanĝi en kiel longe kiel vi estas faranta certe ke vi estas konservanta trako de kio vi estas interŝanĝanta. 

Publiko: Eblus tabelo-i. 

ANDI PENG: Jes, ni faru tabelo-i. Kaj tiam kio estas la sekva linio de kodo ni volas havi tie? Publiko: tabelo-i egalas tabelo-j. ANDI PENG: Kaj laste? Publiko: tabelo-j egalas tabelo-i. Publiko: Aŭ tabelo-j egaluloj tabelo-temp-- aŭ, temp. 

ANDI PENG: OK. Do ni kuras ĉi, kaj vidu se ĝi tuj labori. Kie estas ke okazas? Ho, tio estas problemo. Vidu, sur linio 40, ni estas provas uzi tabelo-j? Sed kiel tio rilatas j nur ekzistas en? 

Publiko: En la por buklo. ANDI PENG: Dekstra. Do kion ni tuj bezonas fari? 

Publiko: Difini ĝin ekstere the-- Publiko: Yeah, Mi supozas ke vi havas uzi alian se aserto, dekstra? Do kiel, se la minimum-- Bone, lasu min pensi. 

ANDI PENG: Knaboj, provi preni rigardon Lasu nin vidu, kio ion ni povos fari tie? 

Publiko: OK. Do se la minimuma ne egala j-- do se la minimumo estas ankoraŭ i-- tiam ni ne devus interŝanĝi. 

ANDI PENG: Ĉu tio egala i? Kion vi volas diri ĉi tie? 

Publiko: Aŭ jes, se la minimumo ne egala i, jes. ANDI PENG: OK. Nu kiu solvas, ia, niaj problemoj. Sed tio ankoraŭ ne solvas la problemo de kio okazas se j-- ekde la j ne ekzistas ekster ĝi, kion vi ni volas fari kun ĝi? Rakontu ĝin ekstere? Ni provu kurante ĉi. Uh-oh. Nia speco ne estas laboranta. 

Kiel vi povas vidi, nia komenca tabelo havis tiujn valorojn. Sed poste gxi devus havi estis en 1, 2, 3, 4, 5, 6, 7, 8, 9. Ĝi ne funkcias. Ahh. Kion ni faru? Publiko: Debug. ANDI PENG: Bone, ni povas provi tion. Ni povas elpurigi. Malzomi iom. Ni metis niajn Haltpunkto. Ni iru like-- OK. 

Do ĉar ni jam scias ke tiuj linioj, 15 tra 22, estas working-- ĉar ĉiuj mi faras estas nur ripetanta tra kaj printing-- Mi povas antaŭeniri kaj salti tio. Komencu ĉe linio 25. OOP, lasu min forigi tion. 

Publiko: Do ​​la Haltpunkto La kie la elpuriganta komenciĝas? ANDI PENG: Aŭ haltoj. Publiko: Aŭ haltoj. ANDI PENG: Yeah. Vi povas agordi multnombraj breakpoints kaj ĝi povas nur salti de unu al la alia. Sed en ĉi tiu kazo ni ne scias kie la eraro okazas. Do ni nur volas komenci de la supro malsupren. Yep. BONE. 

Do tiu linio tie, ni povas interveni. Vi povas vidi ĉi tie, ni havas tabelo. Tiuj estas la valoroj kiuj estas en la tabelo. Ĉu vi vidis tion, kiom indekso 0, ĝi respondas al la value-- ho, Mi tuj provos zomi. Pardonu, estas vere malfacile al Konsideru en tabelo indekso 0, ni havas valoron de 4 kaj tiam tiel plu kaj tiel plu. Ni havas niajn lokajn variablojn. Nun i estas egala al 0, kiu ni volas ke ĝi estu. 

Kaj do ni observu tretante tra. Nia minimuma estas egala al 0, kiun ni ankaŭ volas ĝin esti. Kaj poste ni eniras nia dua por buklo, se tabelo-j estas malpli ol tabelo-i, kiu ne estis. Do ĉu vi vidas, kiel ke saltis super tio? 

Publiko: Do ​​devus la se minimuma, ĉiuj that-- malakceptu ke esti ene la unua por ciklo? ANDI PENG: Ne, ĉar vi ankoraŭ volas testi. Vi volas fari komparon ĉiun tempo, eĉ post vi kuras tra ĝi. Vi ne nur volas fari ĝin sur la unua enirpermesilo-tra. Vi volas fari ĝin kun ĉiu plia pasu denove. Do vi volas kontroli por via kondiĉo ene. Do ni simple tuj teni kuranta tra tie. Mi donos al vi infanoj aludo. Ĝi devas vidi kun la fakto ke kiam vi estas kontrolanta vian kondicionalo, vi ne kontrolanta por la ĝusta indekso. Do nun vi estas kontrolanta por tabelo indekso de j estas malpli ol tabelo indekso de i. Sed kion vi faras supre ĉe la komenco de la por buklo? Ĉu vi opcio j egalas al i? 

Yeah, do ni povas reale eliri la erarserĉilo tie. Do ni rigardu nian _pseudocode_. For-- ni tuj starti je i egalas 0. Ni tuj iru al n minus 1. Ni kontrolu, ĉu ni havas tiun rajton? Yep, ke pravis. 

Tial ene tie, ni estas tuj krei minimuma valoro kaj starigis kiu egala al i. Ĉu ni faru tion? Yep, faris tion. Nun en nia interna por ciklo, ni estas faros j egalas i al n minus 1. Ĉu ni faru tion? Efektive, ni faris tion. 

Do tamen, kion ni komparas tie? 

Publiko: j plus 1. ANDI PENG: Ekzakte. Kaj tiam vi tuj volas agordi via minimuma egala al j plus 1 ankaŭ. Do mi iris tra tiu vere rapide. Ĉu vi uloj kompreni kial estas j plus 1? BONE. 

Do en via tabelo, en via unua trairo, via por buklo, por int i egalas 0, ni nur supozi ĉi ne estis ŝanĝita ankoraŭ. Ni havas tabelo de, tute, nur kvar unsorted elementoj, ĉu ne? Do ni volas pravalorizi i egalas al 0. Kaj mi tuj simple kuri tra tiu buklo. Kaj tiel en la unua enirpermesilo, ni tuj pravalorizi variablo nomata "min" kiu ankaŭ egalas i, ĉar ni ne havas minimuman valoron. Do jen aktuale egalaj al 0, tiel. Kaj tiam ni tuj iru tra. Kaj ni volas persisti denove. Nun ke ni trovis kion nia minimuma estas, ni volas persisti tra denove vidi se ĝi estas komparanta, dekstra? Do j, tie, tuj egalan mi, kiu estas 0. Kaj tiam se tabelo j plus mi, kio Estas kiu estas apud super, kiel malpli ol kio via nuna minimumo valoro estas, vi volas interŝanĝi. 

Do ni nur diros ni havas ricevis, kiel, 2, 5, 1, 8. Ĝuste nun, mi estas egala al 0 kaj j estas egala al 0. Kaj tio estas nia minimuma valoro. Se tabelo-j plus i-- do se la jen post unu ni rigardis estas pli granda ol tiu antaŭ ĝi, ĝi tuj fariĝis la minimumo. 

Do jen ni vidas ke 5 ne malpli ol tio. Do ĝi tuj ne estu 5. Ni vidas ke 1 estas malpli ol 2, ĉu ne? Do nun ni scias ke nia minimumo estas tuj estos la indekso valoro je 0, 1, 2. Yeah? Kaj tiam kiam vi ricevas tie, Vi povas interŝanĝi la korekta valoroj. 

Do kiam vi infanoj estis nur havi la j antaŭe, vi ne rigardas la post ĝi. Vi rigardis la sama valoro, kiun Tial ĝi simple ne faris ion ajn. Ĉu tio havas sencon por ĉiuj, kial ni bezonas ke plus 1 tie? BONE. Nun ni nur kuri tra ĝi fari certe la reston de la kodo estas ĝusta. Kial tio okazas? Ha, la min tie. Ni estis komparante la erara valoro. Ho ne. 

Oh yeah, cxi tie ni estis interŝanĝante la nekorektajn valorojn ankaŭ. Ĉar ni estis rigardantaj i kaj j. Tiuj estas la ones ni kontrolanta. Ni vere volas interŝanĝi la minimuma, la nuna minimumo, kun kiom la ekstera estas. Kaj kiel vi infanoj povas vidi sube tie, ni havas ordo tabelo. Ĝi ĵus devis fari kun la fakto ke kiam ni kontrolanta la valoroj ni komparas, Ni ne rigardante dekstren valoroj. Ni rigardis la sama tie, ne vere interŝanĝi ĝin. Vi devas rigardi la sekva al ĝi kaj tiam vi povas interŝanĝi. Do jen kio estis speco de bugging nia kodo antaŭ. Kaj kion mi faris tie estas ĉio la erarserĉilo povus esti farita por vi Mi nur faris ĝin sur la tabulo, ĉar ĝi estas pli facila vidi prefere ol provado por zomi en sur la erarserĉilo. Ĉu tio havas sencon por ĉiuj? Malvarmeta. 

Bone. Ni povas movi antaŭen al parolante pri asimptota skribmaniero, kiu estas nur fantazio maniero diri la runtimes de ĉiuj de ĉi tiuj varoj. Do mi konas David, en prelego, tuŝis sur runtimes. Kaj li iris tra la tuta formulo de kiel kalkuli la runtimes. Neniu ĉagrenoj pri tio. Se vi estas vere kurioza sur kiel tio funkcias, bonvolu paroli al mi post sekcio. Ni povas marŝi tra la formuloj kune. Sed ĉiuj vi infanoj devos vere scii estas ke n kvadratoj super 2 Estas la sama afero kiel n kvadratoj. Ĉar la plej granda nombro, la eksponento, kreskas la plej. Kaj do por niaj celoj, ĉiuj ni zorgas pri estas la liga nombro kiu estas kreskanta. 

Do kio estas la plej bona kazo runtime de selektado speco? Se vi iras por havi persisti tra listo kaj tiam persisti tra la resto de tiu listo, Multfoje estas vi tuj probable, en la plej malbona case-- en la bona kazo, sorry-- kuri tra? Eble la pli bona demando estas demandi, kio estas la plej malbona kazo runtime de selektado varon. Publiko: n kvadratoj. ANDI PENG: Ĝi estas n kvadratoj, dekstre. Do facila vojo pensi de ĉi tiu estas kiel, ajna tempo vi havas du nestitaj por bukloj, ĝi tuj estos n kvadratoj. Ĉar ne nur vi kurante tra refoje, vi devos iri reen ĉirkaŭ kaj kuri tra ĝi refoje interne por ĉiu valoro. Do en tiu kazo, ke vi uzas n times n kvadratoj, kiuj is-- bedaŭras, n × n, kio egalas n kvadratoj. 

Kaj varo estas ankaŭ iom unika en la senco ke ne gravas se tiuj valoroj estas jam en ordo. Ĝi estas ankoraŭ iranta kuri tra anyways. Ni nur diras tiun estis 1, 2, 3, 4. Sendepende de ĉu aŭ ne ĝi estis en ordo, ĝi ankoraŭ estus trakuris kaj ankoraŭ kontrolis la minimuman valoron. Ĝi estus farinta la sama nombro de ĉekoj ĉiu ununura tempo, eĉ se ĝi ne fakte tuŝas nenion. 

Do en tia kazo, la bona kaj plej malbona runtimes estas fakte ekvivalenta. Do la atendata ekzekuto de selektado speco, kiun ni designar per la simbolo de theta, teto, en tiu kazo, ankaŭ estus n kvadratoj. Ĉiuj tri de ĉi tiuj estus N kvadrato. Estas cxiu klara sur kial la ekzekuto estas n kvadratoj? 

Bone. Do mi simple tuj rapide kuri tra la resto de la varoj. La algoritmo por bobelo sort-- memoras, tio estis la unua David transiris en prelego. Esence, vi tretas tra la tutan liston kaj vi swap-- vi nur kompari du samtempe. Kaj se unu estas pli granda, ol vi simple interŝanĝu ilin. Do se ili estas pli granda, vi devus interŝanĝi. Mi havas oficialan tie. 

Do ni nur diros vi havis 8, 6, 4, 2. Vi estus kompari la 8 kaj 6. Vi bezonus interŝanĝi ilin. Vi devus kompari la 8 kaj 4. Vi bezonus interŝanĝi ilin. Se vi devi interŝanĝi la 8 kaj La 2, ŝanĝi ilin ankaŭ. Do en tia senco, vi povas vidi, ludata dum longa periodo de tempo, kiom la valoroj ia bobelo al la finoj, kio estas kial ni nomas ĝin bobelo varon. 

Ni nur kuri tra denove sur nia dua enirpermesilo, kaj nia tria enirpermesilo, kaj nia kvara enirpermesilo. Esence, bobelo varo simple kuras ĝis vi ne faru plue svopoj. Do en tiu senco, tio estas nur la ĝenerala _pseudocode_ por ĝi. Neniu ĉagrenoj, tiuj cxio estos rete. Ni ne devas reale transiru ĉi. 

Ni nur pravalorizi vendotablo variablo kiu komenciĝas ĉe 0. Kaj ni persisti tra la tuta tabelo. Kaj se unu valoro is-- se ĉi valoro estas pli granda ol tiu valoro, vi tuj interŝanĝi ilin. Kaj tiam vi estas nur tuj plu iri. Kaj vi tuj rakonti. Kaj vi ĝuste tuj observu fari tiu dum la vendotablo estas pli granda ol 0, kio signifas ke ĉiufoje vi devas interŝanĝi, vi scias ke vi volas iri dorso kaj kontroli denove. Vi volas teni kontrolanta ĝis vi scias ke vi ne devas interŝanĝi anymore. 

Do kio estas la plej bona kaj plej malbona kazo runtimes por bobelo varo? Kaj hint-- tio estas fakte malsama el selektado varo en la senco ke tiuj du respondoj estas ne la sama. Pensu pri kio okazos en kazo se ĝi jam ordo. Kaj pensas pri kio okazus se ĝi estis en la kazo en kiu ne estis ordo. Kaj vi povas ia kuri tra kial tio okazas. Mi donos al vi infanoj, kiel, 30 sekundojn por pripensi tion. 

BONE. Ĉu iu havas konjekton ĉe kio la plej malbona kazo runtime de bobelo varo estas? Yeah. 

Publiko: Cxu estus, kiel, n fojoj n minus 1 aŭ io simila? Kiel, ĉiufoje ĝi kuras, ĝi estas nur, kiel, unu interŝanĝa malpli ke cxio estis. 

ANDI PENG: Jes, do vi estas tute prava. Kaj tiu estas kazo en kiu via respondo estis fakte pli kompleksa ol la ni bezonas doni. Do ĝi estas tuj run-- mi tuj viŝos ĉiu ĉi tie. Ĉu ĉiu bona? Ĉu mi povas viŝi ĉi? BONE. Vi tuj kuros tra n tempoj la unua fojo, dekstra? Kaj ili tuj kuras tra n minus 1 duafoje, dekstra? Kaj tiam vi tuj daŭre irante, n mia 2, kaj tiel plu. David faradis tion en prelego, kie, se vi aldonis ĉiujn tiujn valorojn, vi ricevas ion ke estas like-- yeah-- super 2, kiuj esence nur reduktas malsupren al n kvadratoj. Vi tuj ricevos weird frakcio en tie. Kaj tiel nur scias ke la n kvadratoj ĉiam havas prioritaton super la frakcio. Kaj tiel en tiu kazo, la plej malbona ekzekuto estus N kvadrato. Se ĝi estis en malsupreniranta ordo, pensu, vi devi fari interŝanĝa ĉiu ununura tempo. 

Kio estus, potenciale, la plej bona kazo ekzekuto? Ni nur diras, se la listo estis jam en ordo, kia estus la ekzekuto estu? 

Publiko: n. ANDI PENG: Ĝi estas n, precize. Kaj kial estas ĝi n? Publiko: Ĉar vi ĵus devas kontroli sur ĉiu unufoje. ANDI PENG: Ekzakte. Do en la plej bona ebla ekzekuto, se tiu listo estis jam sorted-- diru 1, 2, 3, 4-- vi simple iri tra, vi devus kontroli, vi vidus, ho, ili ĉiuj pan eksteren. Mi ne devis interŝanĝi. Mi faris. Do en tiu kazo, estas nur n aŭ la nombro de paŝoj vi ĵus devis kontroli en la unua listo. 

Kaj poste, ni nun trafis inserción varo, kie la algoritmo estas esence dividi ĝi enen ordo kaj unsorted porcion. Kaj tiam unu post alia, la unsorted valoroj enigita en iliajn taŭga pozicioj en la komenco de la listo. 

Do ekzemple, ni havas listo de 3, 5, 2, 6, 4 denove. Ni scias ke ĝi estas aktuale unsorted ĉar ni ĵus komenciĝis rigardi. Ni rigardu kaj ni scias ke la unua valoro estas ordigataj ĉu ne? Se vi nur rigardas tabelo de grandeco, komprenu ke ĝi estas ordo. 

Tial ni scias ke la aliaj kvar estas unsorted. Ni iras tra kaj ni vidas ke valoro. Ni reiru. Vidu ke valoro de 5? Ni rigardu ĝin. Ni komparu ĝin al 3. Ni scias ke ĝi estas pli granda ol 3, do ni scias ke tio estas ordo. Do ni nun scias ke la unuaj du estas ordo kaj la lastaj tri ne. 

Ni rigardu 2. Ni unue kontroli ĝin per 5. Ĉu malpli ol 5? Ne estas. Do ni devas teni rigardante malsupren. Tiam vi kontrolu 2 for 3. Ĉu malpli ol? No. Do vi konas 2 devas esti enmetitaj en la fronto kaj 3 kaj 5 ambaŭ devas esti puŝitaj eksteren. Ĉu ĉi denove kun 6 kaj 4. Kaj ni simple observu kontrolanta esence, kie ni nur kontroli, kontroli, kontroli. Kaj ĝis ĝi estas en la dekstra pozicion, ni ia simple enmeti ĝin en la ĝusta pozicio, kio estas kie la nomo de ĝi venis de. 

Do tio estas nur la algoritmo, _pseudocode_ per, ia, sur kiel ni devus apliki inserción varon. _Pseudocode_ Estas tie. Estas ĉio rete. Neniu ĉagrenoj se vi uloj estas provas kopii tiun malsupren. Do denove sama question-- kio estus la plej bona kaj plej malbonaj runtimes por inserción varo? Ĝi estas tre simila al la lasta demando. Mi donos al vi infanoj, kiel, 30 sekundoj pripensi ĉi tiel. 

OK Ĉu iu volas donu al mi la plej malbona ekzekuto? Yeah. 

Publiko: n kvadratoj. 

ANDI PENG: Ĝi estas n kvadratoj. Kaj kial ĝi n kvadratoj? 

Publiko: Ĉar en inversa ordo, vi havas iri tra n × n, kio is-- ANDI PENG: Jes, ĝuste. Do samon kiel en la bobelo varon. Se la listo estas en malkreskanta ordo, vi estas tuj devas kontroli unuan fojon. Kaj tiam kun ĉiu aldona valoro, vi estas tuj devas kontroli ĝin kontraŭ ĉiu unuopa valoro, dekstra? Kaj do entute, vi tuj faros n pass fojojn alia n okazintajxon, kiun estas n kvadratoj. Kio pri la plej bona kazo? Yeah. 

Publiko: n minus 1, ĉar la unua unu estas jam kvadrato. 

ANDI PENG: Do, fermo. La respondo fakte estas n. Ĉar dum la unua estas ordigataj gxi ne actually-- ĝi ni nur lucked ekstere, en ke ekzemple, ke 2 pasis al esti la plej malgranda nombro. Sed tio ne ĉiam la kazo. Se 2 estas jam ordo en la komenco sed vi rigardi kaj ekzistas 1 tie, la 1 tuj pusxigxas ĝin. Kaj ĝi tuj finos estante ekfrapita anyways. 

Do en la plej bona kazo scenaro, ĝi estas vere nur tuj estos n. Se vi havas 1, 2, 3, 4, 5, 6, 7, 8, vi estas tuj kuri tra ke tutan liston iam por kontroli ĉu ĉio estas bone. Estas ĉiuj klaraj kurado tempoj de selektado tiel? Mi scias mi iros tra tiuj vere rapida. Sed ĝuste scias ke se vi konas la ĝeneralaj konceptoj, vi devus esti bona. BONE. Do mi nur doni vi infanoj eble, kiel, minuton por paroli al viaj najbaroj sur kio estas nur iuj de la ĉefaj diferencoj inter tiuj tipoj de varoj. Ni iros super kiuj baldaŭ. Publiko: Oh, OK. ANDI PENG: Yeah. BONE. Cool, ni reconvene kiel klaso. BONE. Do tiu estis speco de senfinan demandon en la senco ke restas multaj de respondoj al ili. Kaj ni iros super kelkaj el ili mallonge. Mi nur volis akiri vin infanoj pensante pri kio diferencis ĉiuj tri tipoj de varoj. Mi auxdis, ankaŭ, granda question-- kion merge varo fari? Granda demando, ĉar tio estas kion ni kovrante sekva. 

Do kunfandi speco estas la unu varo kiun funkcioj tre alimaniere de la aliaj varoj. Kiel vi uloj povas Konsideru , David fari tion demo kie li ricevis ĉiujn malvarmeta bruoj de vidanta kiel kunfandi ia kuris, kiel, senfine rapide ol la aliaj du tipoj? BONE. Do tio estas ĉar merge ia implementa disfenditajn kaj konkeri koncepto kiun ni havas parolis multe en lekcio. En tiu senco, ke ni ŝatas labori inteligenta, ne pli malfacila, kiam oni dividas kaj konkeri problemojn, kaj rompi ilin malsupren, kaj tiam meti ilin kune, bonaĵoj ĉiam okazos. 

Do la vojo ke kunfandi speco esence laboras estas ke ĝi dividas de unsorted tabelo duono. Kaj tiam ĝi havas du duonojn de tabeloj. Kaj ĝi simple ordigas tiuj du duonoj. Ĝi nur tenas dividadon en duono, en duono, duono ĝis ĉio estas aranĝita kaj tiam rikure metas ĝin ĉiuj kune. 

Do jen vere abstrakta. Do tio estas nur iom de _pseudocode_. Ĉu tio havas sencon en la vojo ĝi estas kurante? Do ni nur diros vi havas tabelo de n eroj, dekstra? Se n estas malpli ol 2, vi povas reveni. Ĉar vi scias ke se estas nur unu aferon, tio devas esti ordo. Alie, vi ordigi la maldekstra duono, kaj tiam vi ordigi la dekstra duono, kaj tiam vi kunigi. 

Do dum kiu aspektas vere facila, en realeco, pensante ke estas speco de malfacila. Ĉar vi estas kiel, Nu, tio estas ia kuranta sur sin. Dekstra? Ĝi estas kuranta sur sin. Do en tiu senco, Davido tuŝis sur rekursio en klaso. Kaj tio estas koncepto ni parolos pri pli. Estas tiu ĉi, tiujn du liniojn tie, fakte estas nur la programo rakontanta ŝin kuri mem kun malsamaj enigo. Do anstataŭ kuri kun la tuteco de n eroj, vi povas rompi ĝin malsupren en la maldekstra duono kaj la dekstran duonon kaj poste ruli ĝin denove. 

Kaj poste ni rigardas ĝin vide, ĉar mi vida lernanto. Ĝi funkcias bone por mi. Do ni rigardu vida ekzemplo tie. 

Supozu ke ni havas aron, ses elementoj, 3, 5, 2, 6, 4, 1, ne ordo. Bone, ke ekzistas multe en tiu paĝo. Do se vi infanoj povas rigardi la unua ŝtupo tie, 3, 5, 2, 6, 4, 1, vi povas fendi ĝin en duono. Vi havas 3, 5, 2, 6, 4, 1. Vi scias, ke tiuj aren't-- vi ne scias se ili estas ordo aŭ ne, do vi tenas rompante ilin malsupren, en la duono, en duono, en duono, ĝis fine, vi nur havas unu elemento. Kaj unu elemento estas ĉiam ordo, ĉu ne? 

Do ni scias ke 3, 5, 2, 4, 6, 1, aparte, estas ordo. Kaj nun ni povas meti ilin reen kune. Do ni scias la 3, 5. Ni metu tiujn kune. Ni scias, ke tio ordo. La 2 la ankoraŭ tie. Ni povas meti la 4 kaj la 6 kune. Ni scias ke tiu estas ordigataj do ni enkalkulu kune. Kaj la 1 estas tie. 

Kaj tiam vi simple rigardi tiuj du duonoj tie. Vi havas la 3, 5, 2, 2, 3, 5. Vi povas simple kompari la komencante de ĉio. Ĉar vi scias, ke tiu estas ordigita kaj vi scias ke tio estas ordo. Do tiam vi eĉ ne devos kompari la 5, vi simple komparas la 3. Kaj la 2 estas malpli ol 3, Do vi scios 2 devas iri en la fino. 

Samon tie. La 1 devas iri tien. Kaj tiam kiam vi iros meti tiuj du valoroj kune, vi scias, ke tiu estas ordigita kaj vi scias ke tio estas ordo. Do tiam la 1 kaj la 2, la 1 estas malpli ol 2. Kiu rakontas al vi ke la 1 iru sur la fino de ĉi sen eĉ rigardante 3 aŭ 5. Kaj tiam la 4, vi povas simple kontroli, ĝi iras bone tie. Vi ne devas rigardi la 5. Sama afero kun la 6. Vi scias ke la 6-- ĝi ĵus ne bezonas esti rigardis. 

Kaj tiel en tiu maniero, vi estas nur savanta vin mem multajn ŝtupojn kiam vi komparas. Vi ne devas kompari ĉiun elemento kontraŭ aliaj elementoj. Vi nur kompari kontraŭ tiuj ke vi devas kompari ĝin kontraŭ. Do jen speco de abstrakta koncepto. Neniu ĉagrenoj se ĝi ne estas tute frapanta vi pravas ankoraŭ. Sed ĝenerale, tiu estas kiel merge varo funkcias. Demandojn, rapidaj demandoj, antaŭ mi pluiru? Yeah. 

Publiko: Do ​​vi diras, ke vi prenas la 1, kaj tiam la 4 kaj la 6 kaj metis ilin en. Do ne those-- ne vi rigardas ilin kiel apartaj elementoj, ne kiel la tuto? ANDI PENG: Yeah. Do kio okazas estas ke vi resume kreas novegan tabelo. Do vi scias ke, tie, mi havas du tabeloj de amplekso 3, dekstra? Do vi scias ke mia ordo tabelo bezonas havi ses elementoj. Do vi simple kreu nova kvanto da memoro. Do vi estas ia kiel esti malŝparema de memoro, sed tio ne gravas ĉar ĝi estas tiel malgranda. Do oni rigardas la 1 kaj vi rigardas la 2. Kaj vi scias, ke la 1 estas malpli ol 2. Do vi scias ke 1 devus iri en la komenco de ĉiu el tiuj. 

Vi eĉ ne bezonas rigardu la 3 kaj la 5. Do vi scias 1 iras tien. Tiam vi esence detranĉus la 1. Ĝi estas, kiel, mortintojn ni. Tiam ni nur havas 2, 3, 5, kaj tiam 4 kaj 6. Kaj tiam vi scios, ke vi kompari la 4 kaj la 2, ho, la 2 devus iri tien. Do vi Plop la 2 malsupren, vi haki ĝin. Tial vi nur havas la 3 kaj la 5 en la 4 kaj la 6. Kaj vi simple observu batante ĝin ĝis vi metis ilin en la tabelo. 

Publiko: Do ​​vi estas nur ĉiam komparante la [inaudible]? 

ANDI PENG: Ekzakte. Do en tiu senco, ke vi estas nur komparante, esence, unu numeron kontraŭ la alia nombro. Kaj ĉar vi scias ke ĝi estas ordo, vi ne devas rigardi tra ĉiuj la nombroj. Vi nur devas rigardi la antauxa. Kaj tiam vi povas simple Plop ilin malsupren, ĉar vi scias apartenas kie bezonas aparteni. Yeah. Bona demando. 

Kaj tiam se iu el vi estas iom ambicia, bonvolu rigardi tiun kodon. Tiu estas fakte la fizika efektivigo de kiel ni skribus merge varon. Kaj vi povas vidi, estas tre mallongaj. Sed la ideoj malantaŭ ĝi estas sufiĉe kompleksa. Do se vi sentas kiel desegni ĉi ekstere en via hejmtasko ĉinokte, bonvolu. 

BONE. Do ankaux David transiris ĉi en prelego. Kio estas la plej bona kazo runtimes, plej malbona kazo runtimes, kaj la atendata runtimes de merge varo? Paro sekundoj pripensi. Tio estas sufiĉe malfacila, sed ia intuicia se vi pensas pri ĝi. Bone. 

Spektantaro: Ĉu la plej malbona kazo n log n? ANDI PENG: Ekzakte. Kaj kial n log n. 

Spektantaro: Ĉu ne pro tio iĝas eksponente pli rapida, do ĝi estas kiel funkcio de tiu anstataŭ ĝuste simple esti n kvadrato aŭ ion? ANDI PENG: Ekzakte. Do la kialo kial la ekzekuto sur ĉi estas n logo n estas because-- kio estas vi faras en ĉiu de ĉi tiuj paŝoj? Vi nur batante ĝin en duono, dekstra? Kaj tial kiam ni faras la log, cxiuj ĝi estas faranta estas dividanta problemo en duono, en duono, en duono, en pli duonoj. Kaj en tiu senso, vi povas ia de forigi la lineara modelo ke ni uzis. Ĉar kiam vi haki aferojn en duono, estas loglibro. Tio estas nur la matematika maniero reprezenti ĝin. 

Kaj poste fine, fine, vi estas nur faranta lastan enirpermesilon tra meti cxiuj en ordo, ĉu ne? Kaj do se vi simple devas kontroli unu aferon, jen n. Kaj tiel vi estas speco de multiplikante la du kune. Do estas kiel vi hvas tiu fina kontroli por n malsupren tie kun log de n supren tie. Kaj se vi multiplikas ili, kiu estas n logo n. 

Kaj tial la plej bona kazo kaj plej malbona kazo kaj atendita ĉiuj n log n. Estas ankaŭ kiel alia speco. Estas kiel selektado speco en la senco ke ĝi Negrave kion via listo estas, ĝi estas nur irante fari la samon ĉiu ununura tempo. BONE. Do kiel vi uloj povas vidi, eĉ kvankam la varoj kiujn ni iris through-- n kvadrato, ĝi ne estas tre efika. Kaj eĉ tiu n log n estas ne la plej efika. Se vi uloj estas scivolema, ekzistas ia meĥanismoj kiuj estas tiel efikaj ke ili estas preskaŭ esence plata en ekzekuto. 

Vi havas kelkajn log n a. Vi havas kelkajn log log n a. Ni ne tuŝi sur ilin en ĉi klaso nun. Sed se vi uloj estas scivolema, bonvolu google, kio estas la plej efika ordigado mekanismojn. Mi ne scias, estas kelkaj vere amuza, ili like-- ekzistas kelkaj vere amuza kiuj homoj faras. Kaj vi scivolas kiel iam pensis pri tio. Do Google, se vi havas iuj neutiligata tempo, sur, kio estas amuzaj manieroj ke people-- tiel kiel efika ways-- personoj povis efektivigi varojn. BONE. Kaj tie estas nur oportuna iom diagramo. Mi konas vin ĉiujn, antaŭ tiu kvizo 0, estos en via ĉambro probable provas enmemorigi ke. Do jen bela en tie por vi uloj. Nur ne forgesu la logiko ke made-- kial tiuj nombroj estis okazanta. Se vi ĉiam perdita, nur fari certe vin scias kion la varoj estas. Kaj vi povas kuri tra ilin en via menso ekkompreni kial tiuj respondoj estas tiuj respondoj. 

Bone. Do ni tuj movas sur, fine, al serĉado. Ĉar kiel tiuj de vi kiuj legis la pset, serĉado estas ankaŭ parto de tiu semajno problemo aroj. Vi estos petita implementar du tipoj de serĉoj. Unu estas lineara serĉo kaj unu estas duuma serĉo. 

Do la linia serĉo estas sufiĉe facila. Vi nur volas serĉi elemento de listo por vidi se vi ricevas ĝin. Vi nur devas persisti tra. Kaj se ĝi egalas io, vi povas simple reveni, vero? Sed kiu ni estas plej interesas parolas estas duuma serĉo, dekstra, kiu estas la dividu kaj konkeru mekanismo kiu David pruvante en prelego. 

Memoru la telefono libro ekzemplo ke li tenas disvastigante, kiu li ia baraktis iom sur ĉi tiu pasinta jaro, kie oni dividas la problemon en duono, en duono, en duono, denove kaj denove, ĝis vi trovos kion vi serĉas? Kaj vi havas la ekzekuto de tiu tiel. Kaj vi povas vidi, estas signife pli efika ol ajna alia tipo de serĉo. 

Do la maniero ke ni irus pri efektivigado duuma serĉo estas, se ni havis tabelo, indekso 0 ĝis 6, sep elementoj, ni povas rigardi en la mezo, right-- bedaŭras, se nia demando first-- se ni volas fari la demandon de, faras la tabelo enhavas la elementon de 7, evidente, esti homoj, kaj havante tia malgranda tabelo, facilas por ni diri jes. Sed la vojo al apliki duuma serĉo estus rigardi en la mezo. 

Ni scias ke indekso 3 estas la mezo, ĉar ni scii estas sep elementoj. Kio 7 dividita per 2? Vi povas gardeme tiu ekstra 1. Vi havas 3 en la mezo. Do estas aro de 3 egalas 7? Ne estas, ĉu ne? Sed ni povas fari kelkajn ĉekojn. Estas tabelo de 3 malpli ol 7 aŭ estas tabelo de 3 pli granda ol 7? 

Kaj ni scias, ke ĝi estas malpli ol 7. Do ni scias ke, ho, ĝi devas Ne estu en la maldekstra duono. Ni scias, ke ĝi devas esti en la dekstra duono, dekstra? Do ni povas simple gardeme duono la tabelo. Ni eĉ ne devas rigardu ĝin anymore. Ĉar ni scias ke duonon de niaj problem-- ni scias, ke la respondo estas en la dekstra duono de nia problemo. Do ni nur rigardu tion nun. 

Do nun ni rigardas la mezo de kio restas. Ke indekson 5. Ni faru la saman ĉeko denove kaj ni vidas ke ĝi estas pli malgranda. Do ni rigardu al la maldekstra de tio. Kaj tiam oni vidas ke ĉeko. Ĉu la tabelo valoro je indekso 4 egala al 7? Ĝi estas. Do ni povas reveni vera, ĉar Ni trovis la valoron en nia listo. Ĉu la vojo mi iris tra ke sencon al ĉiuj? BONE. Mi donos al vi infanoj eble, kiel, tri, kvar minutoj elkompreni kiel _Pseudocode_ ĉi en. 

Do imagu Mi petis vin skribi funkcio nomita serĉo () kiu revenis valoro, Bulea valoro, Tio estas vera aŭ false-- kiel, vera se vi trovis la valoro, falsa se vi ne. Kaj tiam vi estis pasis en la valoro vi serĉis en valoroj, kiujn estas la tabelo ho, mi definitive meti ke en la malĝusta loko. BONE. Anyways, ke devus havi estis dekstre de valoroj. Kaj tiam int n estas la nombro de elementoj en tiu tabelo. Kiel vi iras pri provanta al _Pseudocode_ ke problemo en? Mi donos al vi infanoj kiel tri minutojn por fari tion. Ne, mi kredas, ke estas only-- yeah, ekzistas unu dekstra supren tie. Publiko: Can I? ANDI PENG: Jes, mi havas vin. Ĉu tio funkcias? Bone, mojose. 

BONE. Bone, knaboj, ni estas tuj bridi ĝin. BONE. Do supozu ni havas tiun belan iom tabelo kun n valoroj en gxi. Mi ne eltiris la linioj. Sed kiel volus ni iras pri provas skribi ĉi? Ĉu iu volas donu al mi la unua linio? Se vi volas doni al mi la unua linio de ĉi _pseudocode_. 

Spektantaro: [inaudible] Spektantaro: Vi volus persisti through-- Spektantaro: Nur alia por buklo? Publiko: --for. 

ANDI PENG: Do ĉi tiu estas iom malfacila. Pensu about-- vi volas teni kuranta ĉi buklo saciedad ĝis kiam? 

Publiko: Ĝis la [inaudible] valoro egalas al tiu valoro. ANDI PENG: Ekzakte. Do vi povas efektive nur write-- ni povas eĉ simpligi ĝin pli. Ni povas nur fari dum buklo, ĉu ne? Do vi povas simple havi loop-- Ni scias ke ĝi estas momenton. Sed por ĝusta nun, mi tuj diri "buklo" - tra kio? Cirkla until-- kio estas nia finanta kondiĉo? Mi kredas ke mi aŭdis ĝin. Mi aŭdis iun diri ĝin. 

Publiko: Valoroj egalas mezo. ANDI PENG: Diru ĝin denove. Publiko: Aŭ, ĝis la valoro vi serĉas cxar estas egala al la meza valoro. 

ANDI PENG: Kio se ĝi ne estas tie? Kio se la valoro vi serĉas cxar estas ne fakte en tiu tabelo? Spektantaro: Vi revenos 1. 

ANDI PENG: Sed kion ni volas buklo ĝis se ni havas kondiĉo? Yeah. 

Publiko: Ĝis tie estas nur unu valoro? ANDI PENG: Vi povas buklo until-- tiel vi scias ke vi estas tuj havos max valoron, ĉu ne? Kaj vi scias ke vi tuj havi min valoron, ĉu ne? Ĉar ankaŭ, ke estas io Mi forgesis diri antaŭ, ke io tio kritikaj pri duuma serĉo estas ke via tabelo jam ordo. Ĉar ekzistas neniu maniero fari tiu se ili estas nur hazarda valoroj. Vi ne scias se unu estas pli granda ol la aliaj, ĉu ne? 

Do vi scias ke via max kaj via Mins estas ĉi tie, ĉu ne? Se vi tuj estos ŝanĝanta via maks en via Mins kaj la mid-- ni nur supozi via mez valoro pravas here-- vi tuj esence buklo ĝis via minimumo estas pri la sama kiel via maks, dekstra, aŭ se via max estas ne la sama kiel via min. Dekstra? Ĉar kiam tiu okazas, vi scias ke vi finfine atingis la saman valoron. Do vi volas buklo ĝis via min estas malpli ol aŭ egala to-- oops, ne malpli ol aŭ egala al, la alia vojo around-- max estas. 

Ĉu tio havas sencon? Mi prenis kelkajn klopodoj trovi tiun rajton. Sed buklo ĝis via max valoro estas esence preskaŭ malpli ol aŭ egala al via minimuma, dekstra? Tio estas kiam vi scias ke vi konverĝis. Spektantaro: Kiam farus vian maksimuman valoro estos malpli ol la minimuma? ANDI PENG: Se vi tenas ĝustigante ŝin, kion estas kio ni iras esti farante en tiu. Ĉu tio havas sencon? Minimuma kaj max estas nur entjeroj ke ni estas probable tuj volas krei teni trako de kie ni serĉas. Pro la tabelo ekzistas Ĉiaokaze de kio ni faras. Kiel, ni ne estas fakte fizike hakado for la tabelo, dekstra? Ni nur ĝustigante kie ni serĉas. Ĉu tio havas sencon? 

Publiko: Yeah. 

ANDI PENG: OK. Do se tio estas la kondiĉo por nia ciklo, Kion ni volas ene de ĉi buklo? Kion ni devas voli fari? Do nun, ni devas max kaj min, dekstra, probable kreita tien ie. Ni tuj probable volas trovi mezan, dekstran? Kiel ni esti povis trovi la mezo? Kio estas la mathematical-- Publiko: Max plus min dividita per 2. ANDI PENG: Ekzakte. Ĉu tio havas sencon? Kaj vi uloj vidi kial ni ne nur use-- kial ni faris ĉi anstataŭ fari nur n dividita per 2? Estas ĉar n estas valoro ke tuj restos la sama. Dekstra? Sed kiel ni ĝustigi nia minimuma kaj maksimumaj valoroj, ili tuj ŝanĝos. Kaj kiel rezulto, niaj mezo tuj ŝanĝos tro. Tial do ni volas fari ĉi tie. BONE. 

Kaj tiam, nun ke ni trovis our-- yeah. 

Spektantaro: Nur rapida question-- kiam vi diras min kaj max, ni supozante ke ĝi estas jam ordo? 

ANDI PENG: Jes, tio estas vere antaŭkondiĉo por duuma serĉo, ke vi devi scii ĝi estas ordo. Tial varon, vi skribas en via problemo starigis antaux viajn duuma serĉo. BONE. Do nun ke ni konas kie nia mezpunkto estas, kion vi volas fari tie? 

Publiko: Ni volas kompari ke al la aliaj unu. ANDI PENG: Ekzakte. Do vi tuj kompari meze taksi, ĉu ne? Kaj kion tio diri kiam ni komparas? Kion ni volas fari poste? 

Publiko: Se la valoro estas pli granda ol la meza, ni volas detranĉu. ANDI PENG: Ekzakte. Do se la valoro estas pli granda ol la mezaj, ni estas tuj volas ŝanĝi tiujn minimuma kaj maxes, dekstra? Kion ni volas ŝanĝi? Do se oni scias la valoro estas ie en tie, kion vi ni ŝanĝi? Ni volas ŝanĝi nian minimumo esti meze, dekstra? Kaj tiam alie, se ĝi estas en tiu duono, kion ni volas ŝanĝi? 

Publiko: Via maksimumo. ANDI PENG: Yeah. Kaj tiam vi simple iranta teni looping, dekstra? Ĉar nun, post unu ripeto tra, vi hvas max tie. Kaj tiam vi povas _recalculate_ mez. Kaj poste vi povas kompari. Kaj vi tuj plu iri ĝis la Mins kaj la maxes esti esence konverĝis. Kaj tio estas kiam vi scias ke vi batis la fino de ĝi. Kaj ĉu vi trovis ĝin aŭ vi havas ne ĉe tiu punkto. 

Ĉu tio havas sencon por ĉiuj? BONE. Tiu estas sufiĉe grava, ĉar vi devos skribi tion en via kodo ĉinokte. Sed vi uloj havas sufiĉe bonan senco de kio vi devus esti faranta, bonon. BONE. Do ni havas ĉirkaŭ sep minutoj forlasis sekcio. Do ni iras por paroli pri ĉi pset ke ni estos faranta. Do la pset estas dividita en du duonoj. La unua duono engaĝas implementando trovaĵo en kiuj vi skribas lineara serĉo, a duuma serĉo, kaj ordiga algoritmo. 

Do tiu estas la unua tempo en pset kie ni estos donanta vin uloj kio nomiĝas dissendo kodo, kiu estas kodo ke ni havas pre-skribitaj, sed nur restis kelkaj pecoj ekstere ke vi finu skribi. Do vi infanoj, kiam vi rigardas tiun kodon, vi povus akiri vere timigis. Se vi nur volas, Ahh, mi ne scias kion tiu faras, Mi ne scias, kiel, kiu ŝajnas tiom komplika, Ahh, malstreĉiĝi. Estas bone. Legu la specifon. La spec klarigos al vi precize kio ĉiuj tiuj programoj faras. 

Ekzemple, generate.c estas programo kiuj venos kun via pset. Vi ne vere devas tuŝi ĝin, sed vi devas kompreni kio ĝi estas faranta. Kaj generate.c, ĉiuj ĝi estas faranta estas ĉu generante hazardaj nombroj aŭ vi povas doni ĝin al la idaro, kiel antaŭaranĝita nombro kiu prenas, kaj ĝi generas pli numeroj. Do ekzistas specifa maniero efektivigu generate.c en kiu vi povas nur fari faskon de nombroj por vin elprovi viajn aliajn metodojn sur. 

Do se vi volus, por Ekzemple, testi vian trovaĵo, vi volus kuri generate.c, generi aron de nombroj, kaj poste ekzekuti viajn helpantoj funkcio. Via helpantoj funkcio estas kie vi estas fakte fizike skribi kodon. Kaj pensi de helpantoj kiel biblioteko dosiero vi skribas ke trovaĵo alvokas. Kaj tiel ene helpers.c, vi faru serĉado kaj ordigi. 

Kaj tiam vi tuj esence nur meti ilin ĉiujn kune. La spec rakontos vin kiel enkalkulu en la komandlinio. Kaj vi povos testi ĉu aŭ Ne via varo kaj serĉo laboras. Malvarmeta. Ĉu iu jam komencis kaj renkontis problemojn aŭ demandojn ili havas nun kun ĉi? BONE. 

Publiko: Atendu. Mi havas demandon. 

ANDI PENG: Yeah. 

Publiko: Do ​​mi komencis fari la lineara serĉo en helpers.c kaj ĝi ne funkciis. Sed tiam poste, mi eltrovis ni ĵus devas forigi ĝin kaj fari duuma serĉo. Do gravas se ĝi ne funkcias? 

ANDI PENG: Mallonga respondo estas ne. Sed ĉar ni estas not-- Publiko: Sed nenies fakte kontrolanta. ANDI PENG: Ni neniam tuj vidos tion. Sed vi verŝajne deziras fari certe via serĉo laboras. Ĉar se via lineara serĉo ne funkcias, tiam ŝancojn estas via Binara serĉo ne tuj funkcios tiel. Ĉar vi havas similan logiko en ambaux. Kaj ne, ĝi ne vere gravas. Do la solaj vi turnos en estas varo kaj duuma serĉo. Yeah. 

Kaj ankaŭ, multan infanoj estis provas kompili helpers.c. Vi fakte ne permesis fari tion, ĉar helpers.c ne havas ĉefan funkcion. Kaj do vi devus nur esti reale kompili generi kaj trovi, ĉar trovi alvokoj helpers.c kaj funkcioj ene de ĝi. Do kiu faras elpuriganta doloro en la pugo. Sed tio kion ni devas fari. Spektantaro: Vi simple ĉiuj, ĉu ne? ANDI PENG: vi povas nur fari cxiujn tiel, jes. BONE. Do jen ĝi en terminoj de kio la pset estas demandanta vin ĉiujn fari. Se vi havas demandojn, bonvolu liberan demandi min post sekcio. Mi estos ĉi tie por, kiel, 20 minutoj. 

Kaj jes, la pset La vere ne estas tiel malbona. Vi uloj devus esti OK. Tiuj, nur sekvi gvidliniojn. Speco de havi senton de, logike, kio devus esti pasante kaj vi estos bone. Ne estu tro timigita. Estas multe da kodo jam skribis tie. Ne estu tro timigita se vi faras ne kompreni kion ĉiuj de tiu signifas. Se ĝi estas multe, estas tute bone. Kaj venu al oficejo horoj. Ni helpos vin rigardu. 

Publiko: Kun la ekstra funkcioj, ni rigardu tiujn supren? 

ANDI PENG: Jes, tiuj estas en la kodo. En la ludo de 15, la duono de ĝi estas jam skribita por vi. Do tiuj funkcioj estas jam en la kodo. Yep. Bone. Nu, plej bone de fortuno. Estas naŭza tago. Do espereble vi uloj ne sentas tro malbona pri restante ene kaj kodigo.