[Musiikkia] 

ANDI Peng: Tervetuloa viikko 3 §. Kiitos, te, kaikkien tulevien Tämän aiemmin alkamisaika tänään. Meillä mukava, pieni intiimi ryhmä tänään. Joten toivottavasti saamme viimeistely, ehkä, varhainen, hieman aikaisin tänään. Niin nopeasti, vain joitakin Ilmoitukset esityslistalla tänään. Ennen kuin aloitamme, olemme menossa vain mennä yli joitakin lyhyitä logistisia kysymyksiä, PSET kysymyksiä, raportointitiedostoon, tuollaista. Ja sitten me sukellus oikealle. Käytämme debuggeri nimeltä gdb aloittaa debunking meidän koodi, joka David selitetään luento toinen päivä. Menemme yli neljä tapaisena. Menemme päälle melko nopeasti koska ne ovat melko intensiivinen. Mutta tiedämme, että kaikki diat ja lähdekoodi ovat aina verkossa. Joten rohkeasti, teidän vahvistettavaksi, että palata ja katsomaan että. 

Menemme läpi asymptoottinen merkintätapa, joka on vain hieno tapa sanoa "runtimes" jossa meillä on iso O, joka David selitetty luento. Ja meillä on myös Omega, joka on alarajan runtime. Ja puhumme hieman enemmän syvällistä siitä, miten nämä työt. Ja lopuksi, me mennä yli binäärihaku, koska monet teistä, jotka ovat jo vilkaisi teidän psets luultavasti tietää, että että on kysymys, joka on teidän PSET. Joten voit kaikki olla onnellinen että me kattaa tämän tänään. 

Ja lopuksi, teidän jakso palautetta, olen oikeastaan vasemmalle noin 15 minuuttia lopulta vain mennä yli logistiikka pset3, kysyttävää, ehkä hieman ohjeita, jos haluatte, ennen kuin aloitat ohjelmoinnin. Joten yrittää saada läpi materiaali melko nopeasti. Ja sitten voimme viettää aikaa ottaen enemmän kysymyksiä PSET. OK. 

Nopeasti, joten vain muutama ilmoitukset ennen kuin aloitamme tänään. Ensinnäkin, tervetuloa tekemään se läpi kaksi teidän psets. Otin tarkastella your-- joo, katsotaanpa saada aplodit, että yksi. Oikeastaan, olin todella, todella vaikuttunut. Olen arvostellaan ensimmäisen PSET varten te viime viikolla ja te tekivät uskomatonta. 

Tyyli oli kohta lisäksi muutamia kommentteja. Varmista, että olet aina kommentointi koodi. Mutta psets olivat piste. Ja keep it up. Ja se on hyvä luokkalainen nähdä, että te laskemisesta niin paljon vaivaa tyyliisi ja suunnittelua koodissa että haluaisimme voit nähdä. Joten olen kulkee pitkin kiitollisuuteni loput avustajat. 

Kuitenkin on olemassa muutaman pyytää raporttia kysymyksiä Haluan vain mennä yli, että tekisi molemmat elämäni ja paljon muuta TA elämää hieman helpompaa. Ensinnäkin, olen huomannut tämän viime week-- kuinka moni teistä on käynnissä check50 päälle koodi ennen kuin lähetät? OK. Joten kaikkien pitäisi tehdä check50, because-- secret-- me oikeastaan ajaa check50 osana oikeellisuuden skriptit testaat koodia. Joten jos koodia ei ole check50, todennäköisesti, se luultavasti epäonnistuvat meidän tarkistaa samoin. Joskus te on oikeat vastaukset. Kuten vuonna ahne, joissakin sinulla on oikeus numerot, te vain tulostaa ylimääräistä tavaraa. Ja että ylimääräistä tavaraa todella epäonnistuu tarkistaa, koska tietokone ei todellakaan tiedä, mitä se etsii. Ja niin se vain ajaa läpi, nähdä, että tuotanto ei ole vastannut sitä, mitä odotamme vastausta olla, ja merkitse se on väärin. 

Ja tiedän, että tapahtui joitakin tapauksia tällä viikolla. Joten menin takaisin ja käsin uudelleenluokiteltuja kaikkien koodi. Tulevaisuudessa, vaikka, ota, varmista että käytät tarkistaa 50 koodin. Koska se on eräänlainen tuskaa TA täytyy mennä takaisin ja käsin regrade joka ikinen PSET jokaisen yhden, vähän jäi esimerkiksi. Joten en ottanut pois mitään pistettä. Luulen lähti ehkä yksi tai kaksi design. Tulevaisuudessa kuitenkin, jos olet ei ole check50, näkökohdat otetaan huomioon pois oikeellisuudesta. 

Lisäksi, psets ovat koska perjantaisin keskipäivällä. Mielestäni siellä on seitsemän minuutin myöhään armonaika että annamme sinulle. Per Harvard aika, niiden sallitaan seitsemän minuuttia myöhässä kaikkeen. Joten tässä Yalen käymme kiinni että samoin. Mutta aika paljon, klo 12:07, jos PSET ei ole, se tulee merkitä myöhään. Ja niin kun se on merkitty niin myöhään, TA-- olen vielä aiotaan luokittelu teidän psets. Joten voit silti nähdä arvosana näkyviin. Kuitenkin tiedämme, että lukukauden loppuun, kaikki myöhässä psets vain on automaattisesti nollattu tietokoneen. 

Teemme tämän kahdesta syystä. Yksi, joskus saamme anteeksi, kuten Dean tekosyitä, myöhemmin, että en tiedä vielä. Joten haluamme varmistaa olemme luokittelu kaikki vain siinä tapauksessa, kuten olen puuttuu Dean tekosyy. Ja toiseksi, pitää mieli, voit silti pudota yksi PSET että on koko laajuudessaan pistettä. Ja niin haluamme luokka kaikki psets vain varmistaa, että soveltamisala on siellä ja yrität niitä. Joten vaikka se on myöhäistä, voit silti saada luottoa laajuus pistettä, luulen. 

Joten Tarinan on, tehdä varma psets ovat ajallaan. Ja jos ne eivät ole ajallaan, tietävät, että se ei ole suuri. Joo, ennen kuin eteenpäin, ei kellään kysyttävää PSET palautetta? Joo. 

Yleisö: Sanoitko me voi pudota yksi psets? 

ANDI Peng: Joo. Joten siellä on yhdeksän psets yleistä aikana lukukauden. Ja jos sinulla on soveltamisala points-- joten soveltamisala on vain, melko paljon, olet yrität ongelma, olet laskemisesta ajoissa, olet osoittaa, että olet osoitti olet lukenut spec. Se on aika paljon varaa. Ja jos täyttävät laajuus pistettä, me voi pudota alin yksi ulos koko laajuudessaan. Niin, että on eduksi täydentää ja yrittää kaikin PSET. 

Vaikka upload-- jos mikään niistä ei toimi, lataa ne kaikki. Ja sitten me voidaan toivottavasti antaa sinulle joitakin niistä pistettä takaisin. Viileä. Muita kysymyksiä? Suuri. 

Toiseksi, toimisto hours-- muutaman muistiinpanoja noin virka. Joten ensimmäinen, tulevat alkuviikosta. Kukaan ei koskaan at virka maanantaisin. Christabel tuli virka viime yönä. Joo, Christabel. Ja mitä meillä on toimistossa tuntia viime yönä, Christabelin? 

Yleisö: Meillä oli jäätelöä. 

ANDI Peng: Niin, että oikeus, meillä oli jäätelöä toimistossa tuntia viime yönä. Vaikka en voi luvata, että meidän täytyy jäätelöä virka joka viikko, mitä voin luvata on se, että siellä on huomattavasti parempi opiskelija TA suhde. Kuten legit, se on kuin viisikymmentäseitsemän yli kaksitoista. Sekä katsoo, kontrasti, että Torstai sinulla noin 150 todella stressaantunut lapset ja ei jäätelöä. Ja se vain ei ole tuottavaa kenellekään. Joten Tarinan on, tule aikaisin Office tuntia ja hyvää tapahtuu. 

Myös tulevat valmis esittää kysymyksiä. Sinä tiedät? Riippumatta siitä, mitä TAS, minä ajatella, ovat sanoneet, olemme tulossa pari opiskelijaa jotka tulevat torstaina klo, kuten, 10:50 ei lukeneeni spec on kuin auttaa minua, auttaa minua. Valitettavasti siinä vaiheessa, on olemassa ei paljon voimme tehdä auttaaksemme sinua. Joten tulkaa alkuviikosta. Tule aikaista virka. Tule valmis esittää kysymyksiä. Varmista, että olet, kuten opiskelija, ovat missä sinun täytyy olla niin, että TA voi opastaa sinua pitkin, joka on mitä virka Pitäisi olla varattu. 

Toiseksi, joten tiedän professorit haluavat yllättää meidät testejä. Minulla oli professori ne kuten, yo, muuten, muista, että puolivälin sinulla on ensi maanantaina. Joo, en tiedä, että puolivälin. Joten aion olla, että TA joka muistuttaa teille kaikille, että tietokilpailu 0-- koska, tiedäthän, olemme CS. Nyt olemme tehneet ryhmät, saat miksi se on tietokilpailu 0, ei tietokilpailu 1, eh? OK. Voi, sain naurahtaa, että yksi. OK. 

Joten tietokilpailu 0 on 14 lokakuu jos olet ma-ke jakso ja 15 lokakuu jos olet tiistaista torstaihin osiosta. Tämä ei koske Niille teistä Harvardin who-- Mielestäni sinun kaikki olla ottaen tietokilpailuja 14.. 

Niin joo, ensi viikolla, jos David, luento, menee, joo, niin siitä tietokilpailu ensi viikolla, te kaikki ei järkyttynyt, koska tulit § ja tiedät, että Quiz 0 on kaksi viikkoa. Ja meidän täytyy arvostelu istuntoja ja kaikki. Joten ei huolestuta pelätä siitä. Kaikki kysymykset before-- kysyttävää ollenkaan koskevat logistisia kysymyksiä, luokittelua, virka, kohdat? Joo. 

Yleisö: Niin tietokilpailu on olemaan aikana luento? 

ANDI Peng: Joo. Joten tietokilpailu, mielestäni, on 60 minuuttia varattu siinä aikavälissä että sinun vain ottaa salissa. Joten sinun ei tarvitse tulla on, kuten, satunnainen 19:00. Kaikki on hyvin. Joo. Viileä. 

Selvä. Joten aiomme käyttöön käsite sinulle tällä viikolla, että David on jo eräänlainen on käsitellyt luento viime viikolla. Sitä kutsutaan GDB. Ja kuinka monet teistä, kun taas aikana kirjoittamalla psets, huomannut iso painiketta, jossa lukee "Debug" päällä teidän IDE? OK. Joten nyt me itse saada kaivaa mysteeri mitä tätä nappia todella tekee. Ja takaan, se on kaunis, kaunis asia. 

Joten tähän asti, luulen että on ollut kaksi asiaa opiskelijat ovat olleet tyypillisesti tekemässä kun virheenkorjaus psets. Yksi, ne joko lisätä printf () - niin joka muutama rivi, ne lisätä printf () - Voi, mikä on tämän muuttujan? Voi, mikä on tämän muuttujan now-- ja te tavallaan nähdä etenemisen teidän koodi se toimii. Tai toinen tapa lapset eivät on että he vain kirjoittaa koko juttu ja sitten mennä näin lopussa. Toivottavasti se toimii. Takaan, GDB on parempi kuin molemmat näistä menetelmistä. Joo. Joten tämä on uusi paras ystävä. Koska se on kaunis asia että visuaalisesti näyttää molemmat mitä koodi tekee tietyssä kohdassa sekä mitä kaikki muuttujat kuljettavat, kuten mitä niiden arvot ovat, tässä erityinen kohta. Ja tällä tavalla, voit todella asettaa raja-arvot koodissa. Voit käydä läpi rivi riviltä. Ja GDB täytyy vain varten te, näytetään sinulle, mitä kaikki muuttujat ovat, mitä he tekevät, mitä tapahtuu koodissa. Ja siten, se on niin paljon helpompi nähdä mitä tapahtuu sijasta printf-ta tai kirjoittaa ylös tiliotteesi. 

Joten teemme esimerkki tästä myöhemmin. Joten tämä tuntuu vähän abstrakti. Ei hätää, teemme esimerkkejä. Ja niin olennaisesti, kolme suurinta, eniten käytettyjä toimintoja, jotka tarvitset GDB ovat Seuraavaksi askel yli, ja Astu painikkeita. Aion pään yli siellä, itse asiassa, juuri nyt. 

Niin voi te kaikki nähdä, että tai minun pitäisi suurentaa vähän? Takana, näetkö sen? Pitäisikö minun suurentaa? Ihan vähän? OK, viileä. Siellä mennään. OK. 

Olen siis, täällä, minun toteutus ahne. Ja vaikka paljon te kirjoitti ahne sisään, kun silmukka form-- että on täysin hyväksyttävä tapa tehdä it-- toinen tapa tehdä se on yksinkertaisesti kuilun modulo. Koska silloin voit saada arvo ja sitten pyydä loput. Ja sitten voit vain lisää se kaikki yhdessä. Onko logiikka, mitä olen tekemässä täällä järkevää kaikille, ennen kuin aloitamme? Eräänlainen? Viileä. Suuri. Se on aika seksikäs pala koodia, sanoisin. Kuten sanoin, David, vuonna luento, kun taas, voit kaikki alkaa nähdä koodi jotain, joka on kaunis. Ja joskus kun näet kaunis koodi, se on niin ihana tunne. 

Niin kuitenkin, vaikka tämä koodi on hyvin kaunis, se ei toimi kunnolla. Joten ajaa check50 tästä. Tarkista 50 20-- oop. 2? Onko se pset2? Joo. Voi, pset1. OK. Joten otamme check50. 

Ja kun te voi nähdä täällä, se ei ole pari tapauksissa. Ja jotkut teistä, vuonna tietenkin tehdä ongelman asettaa, olet kuin, ah, miksi ei se toimi. Miksi se toimi joidenkin arvot mutta ei muille? No, GDB aikoo auttaa sinua kuva miksi nämä tulot eivät toimi. 

OK. Joten katso, yksi tarkastukset Olin ei ole vuonna check50 oli tulon arvo 0,41. Joten oikea vastaus, että sinun pitäisi saada on 4. Mutta sen sijaan mitä olen tulostamalla on 3-n, joka on virheellinen. Joten vain ajaa manuaalisesti, vain varmista, että check50 toimii. Tehdään ./greedy. Oho, minun täytyy tehdä ahne. Siellä mennään. Nyt ./greedy. 

Kuinka paljon on velkaa? Tehdään 0,41. Ja juu, näemme täällä että se syöttöä 3 kun oikea vastaus, itse asiassa pitäisi olla 4. Joten kirjoita GDB ja miten me voi mennä noin vahvistamisesta tähän ongelmaan. 

Joten ensimmäinen askel aina virheenkorjaus koodi on asettaa keskeytyskohta, tai piste, jossa sinua haluat tietokoneen tai debuggeri alkaa tarkastella. Joten jos et todellakaan tietää, mitä ongelma on, yleensä, tyypillinen asia haluamme tehdä, on asettaa meidän keskeytyskohdan tärkein. Joten jos te voi nähdä tämän punainen painike oikeassa, Jep, joka oli minulle asettaminen raja-arvot, sillä päätehtävä. Minä sitten että. 

Ja sitten voin mennä jopa minun Debug painiketta. Osuin että painiketta. Saanen zoomata takaisin, jos voin. Siellä mennään. Joten olemme täällä, paneeli oikealla. Olen pahoillani, kaverit takaisin, te ei todellakaan voi nähdä todella hyvin. Mutta pohjimmiltaan, kaikki tämä oikeus paneeli tekee on pitää kirjaa sekä esiin linja, joka on koodiriviä että tietokone on parhaillaan käynnissä, sekä kaikki muuttujat täällä. 

Joten sinulla senttiä, kolikot, n, kaikki ilmoitetut eri asioita tässä tilanteessa. Ei hätää, koska meillä ei oikeastaan alustetaan heitä mitään muuttujia vielä. Joten tietokoneessa, sinun tietokone on vain nähdä, OH, 32767 oli viimeksi käytetty toiminto Kyseisen muistia minun tietokone. Ja niin se on silloin senttiä tällä hetkellä on. Mutta ei, että kun suorittaa koodia, sen pitäisi tulla alustettu. 

Joten mennään läpi, rivi linja, mitä täällä tapahtuu. OK. Joten täällä ovat kolme painikkeet, olen juuri selitti. Sinulla on toisto tai Run toiminto, painiketta, sinun on askel yli painikkeen, ja sinulla on myös Astu painiketta. Ja olennaisesti, kaikki kolme ne vain mennä läpi koodi ja tehdä erilaisia ​​asioita. 

Joten tyypillisesti, kun olet virheenkorjaus, emme halua painaa Play, koska Play vain ajaa koodi loppuun se. Ja sitten et itse tietää mikä ongelmasi on ellet asettaa useita raja-arvot. Jos asetat useita raja-arvot, se vain automaattisesti alkaa yksi breakpoint, seuraavaan, seuraavaan. Mutta tässä tapauksessa olemme vain että yksi, koska me haluavat työskennellä tiemme ylhäältä alas alas. Joten aiomme sivuuttaa tätä nappia juuri nyt tämän ohjelman. 

Joten askel yli toimintatavasta vaiheet yli joka ikinen viiva ja kertoo, mitä tietokone tekee. Astu toiminto menee varsinaiseen toiminto se on teidän riviä koodia. Niinpä esimerkiksi, kuten printf (), että on funktio, eikö? Jos halusin fyysisesti vaihe osaksi printf () funktio, Haluaisin todella mennä pala koodi missä printf () kirjoitettiin ja nähdä mitä siellä tapahtuu. 

Mutta tyypillisesti, oletamme, että koodi että annamme sinulle toimii. Oletamme printf () toimii. Oletamme, että GetInt () toimii. Joten ei ole tarvetta astu kyseisiä toimintoja. Mutta jos on toimintoja että kirjoitat itse että haluat tarkistaa mitä tapahtuu, haluaisi astua tuohon toiminto. 

Joten nyt me vain menossa vaiheeseen tänä koodinpätkä. Katsotaanpa. Voi, tulostaa, "Voi Hai, miten suuria muutoksia on velkaa? " Emme välitä. Tiedämme, että työskentelee, joten astua sen yli. 

Joten n, joka on meidän float että olemme initialized-- tai declared-- ylös huipulla, olemme nyt vastaten että GetFloat (). Joten askel yli sen. Ja näemme pohja tässä, ohjelma on kehotukset minua syötettävä arvo. Joten panos arvo haluamme testata tässä, joka on 0,41. Suuri. 

Joten nyt n- tehdä Näittekö täällä, bottom-- se stored-- koska me ei ole pyöristetty vielä, se on tallennettu tähän jättimäisiltä float että on ,4099999996, joka on tarpeeksi lähellä meidän tarkoituksiin, juuri nyt, 0,41. Ja sitten näemme myöhemmin, kun me jatkaa tehostamalla koko ohjelmakauden, jälkeen täällä, n on tullut pyöristetty ja senttiä on tullut 41. Suuri. Niin tiedämme, että pyöristys toimivuuden. Tiedämme, että meillä on oikea määrä senttiä, joten tiedämme, että se on ei oikeastaan ​​ongelma. 

Joten jatkamme tehostamalla on tässä ohjelmassa. Menemme täällä. Ja niin sen jälkeen tämä rivi koodia, me pitäisi tietää, kuinka monta neljäsosaa olemme. Me askel yli. Ja näet emme, itse asiassa, on yksi neljänneksellä koska olemme vähennetään 25 meidän alkuperäisestä arvosta 41. Ja meillä on 16 vasemmalle meidän senttiä. 

Onko jokainen ymmärtää, miten ohjelma on tehostaa kautta ja miksi senttiä on tullut 16 ja miksi, nyt, kolikot on tullut 1? Onko jokainen jälkeen, logiikka? Viileä. Jotta tämän kohdan, Ohjelman työ, eikö? Tiedämme, että se tekee tarkalleen mitä me haluamme sen. Ja me ei oikeastaan täytyy tulostaa, oi, mikä on senttiä tässä vaiheessa, mikä on kolikot tässä vaiheessa. 

Jatkamme läpi ohjelman. Astua yli. Viileä. Menemme yli Dimes. Suuri. Näemme, että se otetaan pois $ 0,10 penniäkään. Ja nyt meillä on kaksi kolikkoa. Pitää paikkansa. 

Menemme yli penniä ja näemme että meillä jäljellä senttiä. Hmm, se on outoa. Ylös täällä ohjelma, minun piti pitänyt vähentää minun penniä. Ehkä en vain ollut teet että linja oikea. Ja valitettavasti, voit nähdä täällä, koska tiedämme että me panemme linjojen 32 ja 33, siitähän meidän ohjelma Väärin oli muuttujat juosta. Jotta voimme katsoa ja nähdä, Oh, Olen vähentämällä senttiä täällä, mutta en ole oikeastaan lisäämällä minun kolikon arvo. Olen lisäämällä senttiä. Ja en halua lisätä senttiä, haluan lisätä kolikkoa. Joten jos muutamme että kolikot, meillä työohjelman. Voin ajaa check50. Voit vain poistua ulos GDB oikeus täällä ja suorita check50 uudelleen. Voisin tehdä tämän. Minun täytyy tehdä ahne. 0.41. Ja täällä, se on tulostus ulos oikea vastaus. 

Niin te voi nähdä, GDB on todella tehokas työkalu sillä kun meillä on niin paljon koodia tekeillä ja niin paljon muuttujia että on vaikea meille, koska ihminen, seurata. Tietokone, vuonna GDB debuggeri, on kyky seurata kaikkea. Tiedän, vuonna visionääri, te luultavasti saattanut osua joitakin segmentointi vikoja koska olit käynnissä out of bounds oman array. Esimerkissä Caesar, joka on mitä olen lisännyt täällä. 

Niin unohdin tarkistaa mitä tapahtuisi, jos en ei ollut kaksi komentoriviargumentteja. En vain laittaa, että sisään. Joten jos juoksen Debug-- otan minun breakpoint oikealle siellä. Juoksen Debug. 

OK. Joo. Joten oikeastaan, GDB piti että ovat kertoneet minulle siellä oli segmentointi vika siellä. En tiedä, mitä oli tekeillä oikeassa, mutta kun juoksin sen, se toimi. Kun suoritat riviä koodia kautta ja GDB saattaa yhtäkkiä lopettaa teitä, nousevat ja katso mitä punainen virhe on. Se tulee kertoa, hei, te oli segmentointi vika, mikä tarkoittaa, että yritit pääsy tilaa array, joka ei ollut olemassa. Joo. 

Joten seuraava ongelma asettaa tällä viikolla, te luultavasti paljon muuttujat kelluva noin. Et aio olla varma mitä ne kaikki tarkoittavat tietyssä vaiheessa. Joten GDB todella auttaa sinua miettiminen mitä he ovat kaikki verran ja että voimme nähdä, että visuaalisesti. Onko kukaan sekava miten mitään siitä toimi? Viileä. Selvä. Niin sen jälkeen, olemme menossa sukeltaa oikealle osaksi neljä erilaista tyyppisiä lajittelee tällä viikolla. Kuinka moni teistä, ensin kaikista, ennen kuin aloitamme, lukenut koko spec pset3? OK. Olen ylpeä sinusta kaverit. Se on kuin puolet luokan, joka on huomattavasti enemmän kuin viime kerralla. 

Niin, että on hienoa, koska kun puhumme sisällöstä vuonna lecture-- tai anteeksi, vuonna section-- Pidän suhteuttaa paljon joka takaisin mitä PSET on ja miten haluat toteuttaa että teidän PSET. Joten jos tulet ottaa lukea spec, se tulee olla paljon helpompaa ymmärtää mitä puhun, kun sanon, Ai hei, tämä saattaa olla todella hyvä paikka toteuttaa tämmöinen. Joten ne teistä, jotka ovat lukeneet spec tietävät, että osana PSET, olet menossa on kirjoittaa tyyppi lajitella. Joten tämä voi olla erittäin hyödyllistä varten monet teistä tänään. 

Niin me alkajaisiksi, olennaisesti, kaikkein yksinkertainen tyyppi lajitella, valinta lajitella. Tyypillinen algoritmi kuinka me halua mennä tästä is-- David meni läpi nämä kaikki luento, niin minä nopeasti liikkuvat here-- on pohjimmiltaan, te on joukko arvoja. Ja sitten löydät pienin lajittelemattomat arvo ja vaihdat että arvoa ensimmäinen lajittelemattomat arvo. Ja sitten vain pitää toistaa muun listasi. 

Ja tässä on visuaalinen selitys miten se toimisi. Niinpä esimerkiksi, jos alkaisi jossa joukko viisi elementtiä, indeksi 0-4, 3, 5, 2, 6, ja 4 arvot sijoitetaan array-- niin juuri nyt, olemme juuri menossa olettaa että he kaikki lajittelemattoman koska emme ole testanneet toisin. 

Joten miten valinta semmoista työ on, että se olisi ensin kulkevat kokonaisuudessaan ja lajittelemattoman array. Se poimia pienimmän arvon. Tässä tapauksessa 3, oikea nyt, on pienin. Se saa 5. Ehei, 5 ei ole suurempi than-- tai pahoillani, ei ole pienempi than-- 3. Joten pienin arvo on edelleen 3. Ja sitten saat 2. Tietokone näkee, oh, 2 on alle 3. 2 on nyt pienin arvo. Ja niin 2 tuotevaihdoista että ensimmäinen arvo. 

Niin sen jälkeen yksi syöttö, me todellakin nähdä että 2 ja 3 ovat vaihtuneet. Ja me vain menossa jatkossakin tehdä tämä taas muun jono. Joten aiomme vain ajaa läpi neljä viimeistä indeksien jono. Näemme, että 3 on seuraava minimiarvo. Joten aiomme vaihtaa että 4. Ja sitten me vain aio pitää kulkee läpi kunnes lopulta sinä saada lajiteltua array jossa 2, 3, 4, 5, ja 6 ovat kaikki järjestetty. Onko jokainen ymmärtää logiikkaa miten valinta lajitella toimii? 

Sinun on vain jonkinlainen vähintään arvon. Olet pitää seurata, mitä se on. Ja kun löydät sen, voit vaihtaa sen ensimmäisen arvon array-- tai, ei ole ensimmäinen value-- seuraavan arvon jono. Viileä. 

Niin te eräänlainen näki suppea vilkaisu, aiomme pseudokoodit tätä. Joten jos te takaisin haluavat muodostavat ryhmän, jokainen pöydässä voi muodostaa hieman kumppani, aion antaa te kuin kolme minuuttia vain puhua kautta logiikka, Englanti, miten voisimme toteuttaa pseudokoodi kirjoittaa valinta lajitella. Ja siellä on karkkia. Tule ylös ja saada karkkia. Jos olet takana ja haluat karkkia, voin heittää karkkia sinua. Oikeastaan ​​tehdä sinä-- viileä. Anteeksi. OK. 

Joten jos haluaisimme, niin luokka, Kirjoita pseudokoodi miten voisi lähestyä tämä ongelma, vain rohkeasti. Otan vain mennä ympäri ja, jotta, kysy ryhmät seuraavan rivin mitä meidän pitäisi tehdä. Joten jos kaverit haluavat aloittaa pois, mikä on ensimmäinen asia tehdä, kun yrität toteuttaa tapa ratkaista tämä ohjelman valikoivasti lajitella lista? Haluan vain olettaa meidän on jono, okei? 

Yleisö: Haluat luoda joitakin eräänlainen [äänetön], että olet kulkee koko joukko. 

ANDI Peng: Oikea. Joten olet menossa haluavat kerrata läpi jokaisen tilaa, eikö? Niin suuri. Jos kaverit haluavat antaa minulle seuraava line-- joo, takana. 

Yleisö: Tarkista ne kaikki pienimmille. 

ANDI Peng: Ei mennään. Joten haluamme mennä läpi ja tarkistaa mitä minimiarvo on, eikö? Aion lyhenteenä että "min." Mitä te haluat tehdä jälkeen olet löytänyt pienin arvo? 

Yleisö: [äänetön] ANDI Peng: Niin olet menossa haluavat kytke se ensimmäisen kyseisen array, oikea? Se on alku, aion sanoa. Selvä. Joten nyt olet vaihtanut ensimmäinen yksi, mitä haluat tehdä sen jälkeen? Joten nyt me tiedämme, että tämä yksi täällä on pienin arvo, eikö? Sitten on vielä levätä array, joka on lajittelematon. Joten mitä haluat tehdä täällä, jos kaverit haluavat antaa minulle seuraavalle riville? Yleisö: Niin haluat kerrata loppuosan läpi matriisin. ANDI Peng: Joo. Ja niin mitä iteroimalla läpi Tällainen tarkoita meidän täytyy luultavasti? Millaisia ​​of-- 

Yleisö: Voi, lisämuuttuja? ANDI Peng: Luultavasti toinen silmukka, oikea? Joten me luultavasti menossa haluavat iteroida through-- suuri. Ja sitten aiot mennä takaisin ja luultavasti tarkistaa vähintään kerran, oikea? Ja aiot pitää toistaa tämä, koska silmukat juuri menossa pitää käynnissä, eikö? 

Niin te voi nähdä, me vain yleinen pseudokoodina miten haluamme tämän ohjelman näyttää. Tämä toistaa täällä, mitä me tyypillisesti täytyy kirjoittaa meidän koodi jos haluamme kerrata kautta array, minkälainen rakenne? Mielestäni Christabel jo sanoneet tämän aiemminkin. 

Yleisö: silmukka. 

ANDI Peng: silmukka? Aivan. Joten tämä on luultavasti olemaan silmukka. Mikä on tarkistaa täällä menossa tarkoita? Yleensä, jos haluat tarkistaa jos jotain on jotain else-- 

Yleisö: Jos. 

ANDI Peng: jos, eikö? Ja sitten swap täällä käymme mennä yli myöhemmin, koska David meni läpi että luento samoin. Ja sitten toinen toistaa implies-- 

Yleisö: toinen silmukka. 

ANDI Peng: --another silmukka, tarkalleen. Joten jos me etsimme tässä oikein, me voi nähdä, että olemme luultavasti menossa on sisäkkäistä silmukkaa jossa ehdon siellä ja sitten todellinen koodinpätkä, joka on menossa vaihtaa arvoja. Joten olen juuri yleensä kirjallinen pseudokoodilla koodi tähän. Ja sitten me todella menossa fyysisesti, luokkana, yrittää toteuttaa tätä tänään. Mennään takaisin tähän IDE. 

O-ou. Miksi että not-- siellä se on. OK. Anteeksi, haluaisin yrittää lähentää hieman enemmän. Siellä mennään. Kaikki Teen täällä on Luomani ohjelma nimeltä "valinta / sort.c." Olen luonut joukko yhdeksän arvot, 4, 8, 2, 1, 6, 9, 7, 5, 3. Tällä hetkellä kuin voit katso, ne ovat järjestämättömiä. n tulee olemaan numero, joka kertoo määrä arvojen sinulla on joukko. Tässä tapauksessa meillä on yhdeksän arvot. Ja olen juuri saanut varten silmukka täällä että tulostaa lajittelemattoman array. 

Ja lopussa, olen myös saanut varten silmukka, joka vain tulostaa sen uudelleen. Joten teoriassa, jos tämä ohjelma toimii oikein, lopussa, sinun pitäisi nähdä painettu silmukka jossa 1, 2, 3, 4, 5, 6, 7, 8, 9 ovat kaikki oikein, jotta. 

Joten meillä meidän pseudokoodilla täällä. Haluaako joku to-- Olen vain menossa pyytämään Vapaaehtoisten kerro mitä kirjoittaa, jos haluamme, ensimmäinen, vain kerrata kautta alussa array? Mikä koodiriviä olen luultavasti menossa on täällä? 

Yleisö: [äänetön] 

ANDI Peng: Joo, tuntuu vapaa to-- pahoillani, sinä ei tarvitse seistä up-- tuntea vapaasti korota ääntäsi hiukan. 

Yleisö: INT i vastaa 0-- 

ANDI Peng: Joo, hyvä. 

Yleisö: i on pienempi kuin array pituus. 

ANDI Peng: Niin pitää mielessä täällä, koska me ei ole toimintoa, joka kertoo pituus array, meillä on jo arvoa, joka tallentaa sen. Oikea? Toinen asia pitää vuonna mind-- array yhdeksän arvot, mitkä ovat indeksejä? Haluan vain sanoa tämän array on 0-3. Voit nähdä, että viime indeksi on todella 3. Se ei ole 4, vaikka siellä neljä arvot array. 

Joten täällä, meidän on oltava hyvin varovaisia mitä meidän edellytys pituus tulee olemaan. 

Yleisö: Eikö olisi n miinus 1? ANDI Peng: Se tulee n miinus 1, tarkalleen. Onko järkeä, miksi se on n miinus 1, kaikille? Se johtuu siitä, taulukot ovat nolla-indeksoitu. He alkavat 0 ja ajaa jopa n miinus 1. Joo, se on vähän hankala. OK. Ja sitten-- Yleisö: Isnt'1 että jo hoidettu kuitenkin, mukaan vain sano "pienempi tai vastaa "ja vain sanomalla" alle? " 

ANDI Peng: Se todella hyvä kysymys. Niin, kyllä. Mutta myös, että olemme täytäntöönpanon tarkkailun oikea, sinun täytyy verrata kahta arvoa. Joten te todella haluavat jätä "ja" tyhjä. Koska jos vertaa tämä, et tule mitään sen jälkeen verrata, eikö? Joo. Joten i ++. Katsotaanpa lisätä meidän suluissa. Oho. Suuri. Joten meillä on alusta meidän ulomman silmukan. Joten nyt luultavasti halua luoda muuttujan pitää kirjaa pienimmän arvon, eikö? Haluaako joku antaa minulle koodiriviä että tekisi sellaista? Mitä me tarvitsemme, jos aiomme haluta tallentaa jotain? 

Oikea. Ehkä parempi nimi, että olisi be-- "temp" täysin works-- ehkä enemmän osuvasti nimetty olisi, jos haluamme pienin value-- 

Yleisö: Min. ANDI Peng: min, siellä mennään. min olisi hyvä. Ja niin täällä, mitä me halua alustaa sen? Tämä on vähän hankala. Koska juuri nyt alussa array, et ole tutustunut mitään, eikö? Niin mitä, automaattisesti, jos olemme pelkästään i on 0, mitä haluamme alustaa ensimmäinen pienin arvo? Yleisö: i. ANDI Peng: i, tarkalleen. Christabel, miksi haluamme alustaa se i? 

Yleisö: koska hyvin, olemme alkaen 0. Joten koska meillä ei ole mitään verrata se, vähintään päätyvät juuri 0. 

ANDI Peng: Aivan. Joten hän on juuri oikea. Koska meillä ei oikeastaan Katsoin vielä mitään, emme tiedä, mitä meidän pienin arvo on. Haluamme vain alustaa se i, joka nykyään on täällä. Ja kun jatkamme siirrä alas tämän taulukon, näemme, että jokaisen lisäkulkulupa, i kasvattaa. Ja niin siinä vaiheessa, i on todennäköisesti aio halua olla vähintään, koska se tulee olemaan mitä tahansa on alku lajittelemattoman array. Viileä. 

Joten nyt haluamme lisätä silmukan tässä, että on menossa kerrata läpi lajittelemattomien, tai muusta tämän array. Haluaako joku antaa minulle koodiriviä että tekisi sellaista? Hint-- mitä tarvitsemme täällä? Mitä tulee mennä tähän silmukka? Joo. Yleisö: Joten me haluaisi on erilainen kokonaisluku, koska olemme kulkee loput array sijaan i, niin ehkä j. 

ANDI Peng: Joo, j kuulostaa hyvältä. Yhtä? 

Yleisö: Niin olisi i + 1, koska olet alkaen seuraavan arvon. Ja sitten end-- niin taas, j on vähemmän kuin n miinus 1, ja sitten j ++. ANDI Peng: Suuri. 

Ja sitten täällä, aiomme haluavat tarkistaa, jos meidän ehto täyttyy, oikea? Koska haluat muuttaa minimiarvo jos se on itse asiassa pienempi kuin mitä olet vertaamalla sitä, eikö? Joten mitä me menossa haluavat täällä? Tarkista. Millaisia ​​lausuman me luultavasti ti haluavat käyttää, jos haluat tarkistaa jotain? 

Yleisö: jos ilmoitus. 

ANDI Peng: jos ilmoitus. Joten if-- ja mitä tulee olemaan edellytyksellä, että haluamme sisällä meidän jos ilmoitus? 

Yleisö: Jos arvo j on pienempi kuin arvo i-- 

ANDI Peng: Aivan. Joten if-- joten tämä array on nimeltään "array." Suuri. Joten jos array-- mikä se oli? Sanopa uudestaan. 

Yleisö: Jos array-j on pienempi kuin array-i, niin me muuttaisi min. Joten min olisi j. 

ANDI Peng: Onko järkeä? OK. Ja nyt täällä, me oikeastaan haluavat toteuttaa swap, eikö? Joten muistaa, luento, että David, kun hän yritti vaihtaa the-- mikä oli it-- appelsiinimehua ja milk-- 

Yleisö: Se oli brutto. 

ANDI Peng: Joo, se oli sellainen brutto. Mutta se oli aika hyvä käsite osoittaa aikaa. Niin ajattele arvosi täällä. Sinulla array min, joukko i, tai mitä yritimme vaihtaa täällä. Ja luultavasti ei kaada ne toisiaan samalla, eikö? Mitä siis menossa tarvitse luoda täällä jotta vaihtaa arvot oikein? 

Yleisö: väliaikainen muuttuja. 

ANDI Peng: väliaikainen muuttuja. Tehdäänpä int temp. Katso, tämä olisi parempi aika to-- huh, mitä se oli? OK. Joten tämä olisi ollut parempi aika nimetä muuttuja "temp." Tehdäänpä int temp. Mitä aiomme Set Temp yhtä täällä? Yleisö: Min? ANDI Peng: Se on vähän hankala. Se oikeastaan ​​ei ole väliä lopulta. Sillä ei ole väliä mitä jotta päätät vaihtua kunhan teet että olet pitää kirjaa mitä olet vaihtamalla. 

Yleisö: Se voisi olla joukko-i. 

ANDI Peng: Joo, tehdään array-i. Ja sitten mitä seuraavalle riville koodia haluamme täällä? Yleisö: array-i vastaa array-j. ANDI Peng: Ja lopuksi? Yleisö: array-j vastaa array-i. Yleisö: Tai array-j tasavertaisten array-temp-- tai lämpötila. 

ANDI Peng: OK. Joten suorittaa tämän ja nähdä jos se on menossa töihin. Missä se tapahtuu? Voi, se on ongelma. Katso, linjalla 40, olemme yrittää käyttää array-j? Mutta mistä j olemassa vain? 

Yleisö: Vuonna silmukka. ANDI Peng: Oikea. Mitä aiomme täytyy tehdä? 

Yleisö: Määrittele se ulkopuolella the-- Yleisö: Joo, kai sinulla on käyttää toista jos ilmoitus, eikö? Joten kuten, jos minimum-- okei, haluan ajatella. 

ANDI Peng: Guys, kokeile katsomaan Katsotaanpa katso, mitä emme voi tehdä täällä? 

Yleisö: OK. Joten jos vähintään ei vastaa j-- joten jos minimi on vielä i-- meidän ei tarvitsisi vaihtaa. 

ANDI Peng: Onko että yhtäläiset i? Mitä haluat sanoa täällä? 

Yleisö: Tai joo, jos vähimmäismäärä ei vastaa i, joo. ANDI Peng: OK. No, joka ratkaisee, sellainen, ongelmamme. Mutta se ei edelleenkään ratkaise ongelma, mitä tapahtuu, jos j-- alkaen j ei ole sen ulkopuolella, mitä sinä haluamme tehdä sen kanssa? Julistaa sen ulkopuolella? Kokeillaan käynnissä tätä. O-ou. Meidän sort ei toimi. 

Kuten näette, alkuperäistä array oli näitä arvoja. Ja myöhemmin se olisi ollut 1, 2, 3, 4, 5, 6, 7, 8, 9. Se ei toimi. Ahh. Mitä me teemme? Yleisö: Debug. ANDI Peng: Hyvä on, voimme yrittää että. Voimme debug. Pienennä hieman. Katsotaanpa asettaneet murtuessa. Mennään like-- OK. 

Joten koska tiedämme jo, että Näillä radoilla 15 kautta 22, ovat working-- koska kaikki mulla on vain iteroimalla läpi ja printing-- Voin mennä eteenpäin ja ohittaa tämän. Aloitetaan rivillä 25. OOP, haluaisin päästä eroon siitä. 

Yleisö: Niin keskeytyskohta n jossa virheenkorjaus alkaa? ANDI Peng: Or pysähtyy. Yleisö: Or pysähtyy. ANDI Peng: Joo. Voit asettaa useita raja-arvot ja se voi vain hypätä yhdestä muille. Mutta tässä tapauksessa emme tiedä missä virhe tapahtuu. Joten me vain haluamme Aloita ylhäältä alas. Jep. OK. 

Joten tämä linja täällä, voimme askel. Näet täällä, meillä array. Ne ovat arvoja jotka ovat jono. Näetkö, että miten indeksi 0, se vastaa value-- OH, Aion yrittää suurentaa. Anteeksi, se on todella vaikea on see-- klo taulukkoindeksin 0, meillä on arvo 4 ja sitten niin edelleen ja niin edelleen. Meillä on paikallisia muuttujia. Juuri nyt on yhtä suuri kuin 0, jonka haluamme sen olevan. 

Ja niin katsotaanpa pitää tehostamalla kautta. Meidän vähintään on yhtä suuri kuin 0, jota me myös haluamme sen olevan. Ja sitten astumme meidän toinen varten silmukka, jos array-j on pienempi kuin joukko-i, mikä se ei ollut. Joten Näitkö kuinka että ohitetaan että? 

Yleisö: Niin pitäisi, jos vähintään kaikki that-- ei pitäisi että olla sisällä ensimmäinen silmukka? ANDI Peng: Ei, koska Haluatko edelleen testata. Haluatko tehdä vertailu joka aika, vaikka olet ajaa sen läpi. Et vain halua tehdä sitä ensimmäisen läpiviennin. Haluatko tehdä sen jokaista pass uudelleen. Joten haluat tarkistaa vointisi sisällä. Joten me vain menossa pitää käynnissä läpi täällä. Minä annan teille kaverit vihje. Se on tekemistä sen kanssa, että kun olet tarkkailun ehdollinen, et ole tarkkailun oikea indeksi. Joten nyt olet tarkistanut joukko indeksi j on pienempi kuin array indeksi i. Mutta mitä teet ylös alussa silmukka? Etkö asetus j yhtä i? 

Joo, joten voimme todella Poistu debuggeri täällä. Joten katsomaan meidän pseudokoodilla. For-- aiomme alkavat i on yhtä kuin 0. Aiomme mennä jopa n miinus 1. Katsotaan tarkistaa, meillä oli tämä oikeus? Jep, se oli oikeassa. 

Joten sitten sisällä tässä, olemme luomme minimiarvoon ja asettaa että yhtä i. Teimme sen? Jep, teki sen. Nyt meidän sisempi silmukka, olemme aikoo tehdä j vastaa i n miinus 1. Teimme sen? Todellakin, teimme sen. 

Joten kuitenkin, mitä me vertaamalla täällä? 

Yleisö: j + 1. ANDI Peng: Aivan. Ja sitten olet menossa halua asettaa sinun vähintään yhtä suuri kuin j + 1 samoin. Menin läpi todella nopeasti. Onko teillä ymmärtää miksi se on j plus 1? OK. 

Joten teidän mä, ensimmäinen läpi, teidän silmukka, INT i on 0, haluan vain olettaa tämä ei ole muutettu vielä. Meillä on joukko, täysin, vain neljä lajittelematonta elementtejä, eikö? Joten haluamme alustaa i 0. Ja i on menossa vain läpi tämän silmukan. Ja niin ensikierron aiomme alustaa muuttuja nimeltä "min" että myös vastaa i, koska meillä ei ole minimiarvo. Niin, että tällä hetkellä yhtä 0 hyvin. Ja sitten me aiomme käydä läpi. Ja haluamme kerrata uudelleen. Nyt olemme löytäneet mitä meidän minimi on, haluamme kerrata kautta uudelleen nähdä, jos se on vertaamalla, eikö? Joten j, täällä, on menossa yhdenvertaiseen I, joka on 0. Ja sitten jos joukko J plus i, joka on yksi, joka on seuraava yli, vähemmän kuin mitä nykyinen vähimmäismäärä arvo on, haluat vaihtaa. 

Joten vain sanoa olemme sai, kuten, 2, 5, 1, 8. Juuri nyt, i on yhtä suuri kuin 0 ja j on yhtä suuri kuin 0. Ja se on meidän pienin arvo. Jos array-j plus i-- joten jos yksi se kun yksi me tarkastelemme on suurempi kuin ennen sitä, se tulee tulla minimiin. 

Joten tässä me näemme, että 5 ei ole pienempi. Niin se tulee olla 5. Näemme, että 1 on pienempi kuin 2, eikö? Joten nyt me tiedämme, että meidän vähimmäismäärä on olemaan indeksin arvo 0, 1, 2. Joo? Ja sitten kun saat tänne, voit vaihtaa oikeat arvot. 

Joten kun kaverit olivat vain ottaa j ennen, et ollut katsot yksi sen jälkeen. Katseltaessa sama arvo, joka Siksi se vain ei tee mitään. Tarkoittaako tämä järkevää kaikille, miksi me tarvitsimme että plus 1 siellä? OK. Nyt vain ajaa läpi sitä tehdä Varmista, että loput koodi on oikea. Miksi se tapahtuu? Ah, se min täällä. Olimme vertaamalla väärän arvon. Voi ei. 

Ai niin, täällä olimme vaihtava väärä arvot sekä. Koska me tarkastelemme i ja j. Ne ovat niitä olimme tarkkailun. Me todella haluavat vaihtaa minimi, nykyinen vähimmäistaso, kanssa, mitä yksi ulkopuolella on. Ja kun te voi nähdä alas täällä, meillä on lajiteltu array. Se vain oli tekemistä se, että kun olimme tarkkailun arvot olimme vertaamalla, emme katsot oikeita arvoja. Etsimme samalla yksi täällä, ei oikeastaan ​​vaihtamalla sitä. Sinun täytyy katsoa yksi seuraavassa sen ja sitten voit vaihtaa. Niin sitähän oli eräänlainen salakuuntelu meidän koodin ennen. Ja mitä tein täällä on kaikkea debuggeri olisi voinut tehdä sinulle Tein sen aluksella, koska se on helpompaa nähdä eikä yrittää zoomata debuggeri. Tarkoittaako tämä järkevää kaikille? Viileä. 

Selvä. Voimme siirtyä puhu asymptoottinen merkintätapa, joka on vain hieno tapa sanoa runtimes kaikkien näiden lajittelee. Joten tiedän David, luento, sivuttiin runtimes. Ja hän kävi läpi koko kaava laskemisesta runtimes. Ei huolestuta, että. Jos olet todella utelias miten se toimii, vapaasti puhua minulle jakson jälkeen. Voimme käydä läpi kaavat yhdessä. Mutta kaikki teillä todella tietää, että n potenssiin yli 2 on sama asia kuin n potenssiin. Koska eniten, eksponentti, kasvaa eniten. Ja niin meidän tarkoituksiin, kaikki välitämme on että jättimäinen määrä, joka on kasvava. 

Joten mikä on paras asia runtime valinta lajitella? Jos aiot olla iteroida kautta lista ja sitten kerrata kautta loput tämän luettelon, kuinka monta kertaa on aiot luultavasti, pahimmassa case-- vuonna Parhaassa tapauksessa sorry-- kulkevat? Ehkä parempi kysymys on kysyä, mikä on pahimmassa tapauksessa runtime valinta lajitella. Yleisö: n neliö. ANDI Peng: Se on n potenssiin, oikea. Joten helppo tapa ajatella tätä on kuin, tahansa sinulla on kaksi sisäkkäistä silmukkaa, se tulee olemaan n neliö. Koska ei vain sinä kulkee jälleen, sinun täytyy mennä takaisin ympäri ja ajaa sen läpi jälleen sisällä jokaista arvo. Niin siinä tapauksessa, näytät n ajat n potenssiin, joka is-- anteeksi, n kertaa n, joka on yhtä kuin n neliö. 

Ja lajitella on myös hieman ainutlaatuinen siinä mielessä, että sillä ei ole väliä, jos nämä arvot ovat jo kunnossa. Se on edelleen menossa läpi anyways. Sanotaan vain tämä oli 1, 2, 3, 4. Riippumatta siitä, onko se oli järjestys, se silti olisi kulki ja vielä tarkistanut minimiarvon. Se olisi tehnyt sama määrä tarkastuksia joka kerta, vaikka se ei oikeastaan ​​koske mihinkään. 

Joten tällaisessa tapauksessa paras ja huonoin runtimes ovat todella vastaavat. Joten odotettavissa runtime valinta lajitella, jota nimeävät symboli theta, theta, tässä tapauksessa, olisi myös n neliö. Nämä kaikki kolme olisi n neliö. Onko kaikki selvää miksi runtime on n potenssiin? 

Selvä. Joten olen juuri menossa nopeasti ajaa läpi loput tapaisena. Algoritmi kupla sort-- muistaa, tämä oli ensimmäinen Daavid meni ohi luento. Pohjimmiltaan, astut läpi koko lista ja te swap-- juuri vertailla kahta kerrallaan. Ja jos yksi on suurempi, kuin vain vaihtaa niitä. Joten jos nämä ovat suurempia, voit vaihtaa. Minulla virallinen täällä. 

Joten vain sanoa teillä oli 8, 6, 4, 2. Sinun vertailla 8 ja 6. Sinun täytyy vaihtaa niitä. Voisitte vertailla 8 ja 4. Sinun täytyy vaihtaa niitä. Jos sinulla on vaihtaa 8 ja 2, muuttaa niitä samoin. Joten tällaisessa mielessä, näet, pelataan yli pitkän aikaa, miten arvot sellainen kupla päät, minkä vuoksi me kutsumme sitä kuplalajittelu. 

Haluamme vain ajaa läpi jälleen Toinen pass, ja meidän kolmas pass, ja meidän neljäs omille. Pohjimmiltaan, kuplalajittelu vain kulkee kunnes et tee enää swap. Joten siinä mielessä, tämä on vain yleinen pseudokoodi se. Ei hätää, nämä kaikki on verkossa. Meillä ei tarvitse itse mennä yli tämän. 

Olemme vain alustaa laskuri muuttuja, joka alkaa 0. Ja me kerrata läpi koko ryhmän. Ja jos yksi arvo is-- jos tämä arvo on suurempi kuin arvo, aiot vaihtaa niitä. Ja sitten olet vain aikoo jatkaa. Ja aiot laskea. Ja olet juuri menossa pitää tehdä tämä kun laskurin arvo on suurempi kuin 0, mikä tarkoittaa, että joka kerta, kun täytyy vaihtaa, tiedät haluat mennä takaisin ja tarkista uudelleen. Haluat pitää tarkkailun kunnes tiedät että sinun ei tarvitse vaihtaa enää. 

Mitkä ovat parhaat ja huonoimmat tapauksessa Varakäyntiajat varten kuplalajittelu? Ja hint-- tämä on todella erilainen valinnasta lajitella siinä mielessä että nämä kaksi vastausta eivät ole samoja. Mieti, mitä tapahtuisi jos se oli jo järjestetty. Ja miettiä, mitä tapahtuisi, jos se oli tapauksessa, jossa se ei ole lajiteltu. Ja voit sellaista ajaa kautta, miksi näin tapahtuu. Annan te, kuten, 30 sekuntia ajatella, että. 

OK. Onko kellään arvata mitä Pahimmassa tapauksessa runtime kuplalajittelu on? Joo. 

Yleisö: Olisiko, kuten, n kertaa n miinus 1 tai jotain? Kuten joka kerta se toimii, se on vain, kuten, yksi swap vähemmän että mitä se oli. 

ANDI Peng: Joo, niin olet täysin oikeassa. Ja tämä on tapaus, jossa sinun Vastaus oli todella monimutkaisempi kuin yksi meidän on annettava. Joten se tulee run-- olen aikoo poistaa kaikki täällä. Onko kaikki hyvin? Voinko poistaa tämän? OK. Aiot ajaa läpi n kertaa ensimmäistä kertaa, eikö? Ja he aikovat käydä läpi n miinus 1 toisen kerran, eikö? Ja sitten aiot pitää menossa, n kaivos 2, jne. David tekivät tämän luennon, jossa, jos lasketaan yhteen kaikki ne arvot, saat jotain, joka on like-- yeah-- yli 2, joka olennaisesti vain vähentää alas n potenssiin. Olet menossa saada outo jae siellä. Ja niin juuri tietää, että n potenssiin aina menee osa. Ja niin tässä tapauksessa, pahin runtime olisi n neliö. Jos se oli laskeva järjestys, ajatella, te on tehtävä swap joka kerta. 

Mikä olisi mahdollisesti Parhaassa tapauksessa runtime? Sanotaan vain, kun luettelo on jo jotta, mikä olisi runtime olla? 

Yleisö: n. ANDI Peng: Se on n, tarkalleen. Ja miksi se n? Yleisö: Koska juuri täytyy tarkistaa jokaisen kerran. ANDI Peng: Aivan. Joten mahdollisimman runtime, jos tämä lista oli jo sorted-- sanokaamme 1, 2, 3, 4-- sinua olisi vain mennä läpi, voit tarkistaa, näkisitte, OH, he kaikki sujua. Minun ei tarvinnut vaihtaa. Minulle riitti. Niin siinä tapauksessa, se on vain n tai useita vaiheita juuri oli tarkistaa ensimmäisessä luettelossa. 

Ja kun me nyt osuma lisäyslajittelun, jossa algoritmi on lähinnä jakaa se lajitellun ja lajittelemattoman osa. Ja sitten yksi kerrallaan, lajittelemattomat arvot ovat lisätään niiden asianmukaisen tehtävissä listan alkuun. 

Niinpä esimerkiksi, meillä Luettelo 3, 5, 2, 6, 4 jälleen. Tiedämme, että se on tällä hetkellä lajittelematon koska olemme juuri aloitti katsomalla sitä. Me katsomaan ja tiedämme, että ensimmäinen arvo lajitellaan, eikö? Jos tarkastellaan vain joukko Koko Yksi, te tiedätte, että se on järjestetty. 

Joten me tiedämme, että muut neljä lajittelemattomia. Käymme läpi ja näemme, että arvo. Mennään takaisin. Katso, että arvo on 5? Me katsomaan sitä. Vertaamme sitä 3. Tiedämme, että se on suurempi kuin 3, joten tiedämme, että on lajiteltu. Joten me tiedämme nyt, että kaksi ensimmäistä lajitellaan ja kolme viimeistä eivät ole. 

Me katsomaan 2. Ensin tarkistaa sen 5. Onko se vähemmän kuin 5? Se ei ole. Joten meidän on pidettävä katsoo alas. Sitten voit tarkistaa 2 pois 3. On se alle? Ei. Niin tiedät 2 on kytkettävä etuosaan ja 3 ja 5 molemmat on työnnetty ulos. Tee näin uudelleen 6 ja 4. Ja me vain pitää tarkistaa lähinnä, jossa me vain tarkistaa, tarkista, tarkista. Ja kunnes se on oikeassa asema, me tavallaan vain aseta se oikeaan asentoon, joka on ilmoitettaessa se tuli. 

Niin se on vain algoritmi, pseudokoodilla sinänsä, sellainen, miten voisimme toteuttaa lisäyslajittelun. Pseudokoodilla on täällä. Se kaikki verkossa. Ei hätää, jos te olette yrittää kopioida tämän alas. Joten jälleen kerran, sama question-- mitä olisi paras ja huonoin runtimes asettamista varten lajitella? Se on hyvin samankaltainen viimeiseen kysymykseen. Annan te, kuten, 30 sekuntia ajatella tästä. 

OK Onko kukaan halua anna minulle pahin runtime? Joo. 

Yleisö: n neliö. 

ANDI Peng: Se on n potenssiin. Ja miksi se n potenssiin? 

Yleisö: Koska päinvastaisessa järjestyksessä, sinulla on käydä läpi n kertaa n, joka is-- ANDI Peng: Joo, täsmälleen. Joten sama asia kuin kuplalajittelu. Jos tämä luettelo on alenevassa järjestyksessä, olet täytyy ensin tarkistaa kerran. Ja sitten jokaisen lisäarvoa, olet täytyy tarkistaa, että se jokainen yksittäinen arvo, eikö? Ja niin kokonaan, aiot tehdä n syöttö kertaa toisen n pass, joka on n potenssiin. Entä Parhaassa tapauksessa? Joo. 

Yleisö: n miinus 1, koska ensimmäinen on jo potenssiin. 

ANDI Peng: Niin lähellä. Vastaus on itse asiassa n. Sillä vaikka ensimmäinen on lajitellaan, se ei voi actually-- sitä me vain lucked, vuonna että esimerkiksi, että 2 sattui olemaan pienin määrä. Mutta se ei aina tapahdu. Jos 2 on jo järjestetty alussa mutta näytät ja siellä 1 täällä, 1 on menossa kolahtaa se. Ja se tulee lopettaa up on törmäsi anyways. 

Joten parhaassa tapauksessa, se on oikeastaan ​​vain olemaan n. Jos sinulla on 1, 2, 3, 4, 5, 6, 7, 8, olet menossa ajaa läpi että koko lista kerran tarkistaa, jos kaikki on hyvin. Onko kaikki selvää käynnissä aikoina valinta samoin? Tiedän, että olen menossa läpi nämä todella nopeasti. Mutta vain tietää, että jos tiedät yleiset käsitteet, sinun pitäisi olla hyvä. OK. Niin minä vain antaa te ehkä, kuten, minuutti puhua naapurit mitä ovat vain joitakin tärkeimmistä eroista välillä tämäntyyppisiä tapaisena. Menemme yli, että pian. Yleisö: Voi, OK. ANDI Peng: Joo. OK. Cool, nyt uudelleen koolle luokkana. OK. Joten tämä oli sellainen avoin kysymys siinä mielessä että siellä on paljon niihin vastauksia. Ja me mennä yli joitakin niistä lyhyesti. Halusin vain saada te miettiä, mitä eriytetty kaikki kolme tapaisena. Ja kuulin, myös suuri question-- mitä merge sort tekee? Suuri kysymys, koska se on mitä me kattaa seuraavaksi. 

Joten yhdistää lajitella on yksi sort joka toimii hyvin eri muunlaisia. Kuten te voi see-- ei David tehdä demo jossa hän oli kaikki viileä ääniä nähdä miten yhdistää lajitella juoksi, kuten, äärettömän nopeammin kuin muut kaksi? OK. Niin, että koska yhdistää lajitella toteuttaa että kuilu ja valloittaa käsite, että olemme puhui paljon luento. Siinä mielessä, että haluamme työskennellä fiksummin, ei kovemmin, kun jaat ja valloittaa ongelmia, ja rikkoa niitä alas, ja sitten laittaa ne yhteen, hyviä asioita aina tapahdu. 

Niin että yhdistää lajitella olennaisesti toimii on se, että se jakaa lajittelematon array kahtia. Ja sitten se sai kaksi puolikasta taulukot. Ja se vain lajittelee nämä kaksi puolikasta. Se vain pitää jakamalla kahtia, vuonna puoli, puoli kunnes kaikki on järjestetty ja sitten rekursiivisesti panee kaiken yhteen. 

Niin se on todella abstrakti. Joten tämä on vain vähän pseudokoodina. Tarkoittaako tämä järkevää miten se on käynnissä? Joten vain sanoa olet joukko n osia, eikö? Jos n on pienempi kuin 2, voit palata. Koska tiedät, että jos on olemassa vain yksi asia, se on lajiteltava. Else, voit lajitella vasen puoli, ja sitten lajitella oikea puoli, ja sitten yhdistää. 

Joten vaikka joka näyttää helppoa, Todellisuudessa ajatellut se eräänlainen vaikea. Koska olet kuten, hyvin, että on tavallaan käynnissä itse. Oikea? Se käynnissä itse. Joten siinä mielessä, David kosketti kun rekursio luokassa. Ja se on käsite me puhumme enemmän. Se, että tämä, nämä kaksi riviä täällä, itse asiassa on vain ohjelma kertoo se ajaa itse eri tulo. Joten mieluummin kuin ajaa itsensä kanssa kokonaisuudessaan n elementtejä, voit rikkoa sen alas vasen puoli ja oikea puoli ja sitten ajaa se uudelleen. 

Ja sitten me tarkastelemme sitä visuaalisesti, koska olen visuaalinen oppija. Se toimii paremmin minulle. Joten me tarkastelemme visuaalinen esimerkki tästä. 

Sanotaan meillä on joukko, kuusi elementtejä, 3, 5, 2, 6, 4, 1, ei lajitella. Okei, siellä on paljon tällä sivulla. Joten jos te katsoa Ensimmäinen askel tähän, 3, 5, 2, 6, 4, 1, voit jakaa sen kahtia. Sinulla on 3, 5, 2, 6, 4, 1. Tiedät, että nämä aren't-- sinua tiedä jos he lajitellaan tai ei, joten sinun pitää rikkomatta niitä alas, puoli, kahtia, puoli, kunnes lopulta, sinulla on vain yksi elementti. Ja yksi elementti on aina lajitellaan, eikö? 

Joten tiedämme, että 3, 5, 2, 4, 6, 1, itse, lajitellaan. Ja nyt voimme laittaa ne takaisin yhteen. Joten me tiedämme 3, 5. Laitamme ne yhteen. Tiedämme, että se lajitellaan. 2 on yhä siellä. Voimme laittaa 4 ja 6 yhdessä. Tiedämme, että joka on lajiteltu, niin laitamme että yhdessä. Ja 1 on siellä. 

Ja sitten katsokaa nämä kaksi puolikasta täällä. Sinulla on 3, 5, 2, 2, 3, 5. Voit vain vertailla kaiken alku. Koska tiedät, että tämä on lajiteltu ja te tiedätte, että on lajiteltu. Joten sinun ei edes tarvitse vertailla 5, juuri vertailla 3. Ja 2 on pienempi kuin 3, niin Tiedätkö 2 on mentävä loppuun. 

Sama juttu tuolla. 1 on mentävä täällä. Ja sitten kun menet laittaa nämä kaksi arvoa yhteen, tiedät, että tämä lajitellaan ja tiedät, että se lajitellaan. Niin sitten 1 ja 2, 1 on pienempi kuin 2. Joka kertoo, että 1 pitäisi mennä loppuun katsomatta edes 3 tai 5. Ja sitten 4, voit vain tarkista, se menee suoraan tänne. Sinun ei tarvitse katsoa 5. Sama juttu 6. Tiedätte, että 6-- se vain ei syytä tarkastella. 

Ja niin tällä tavalla, olet vain säästää itsellesi runsaasti portaita kun olet verrataan. Sinun ei tarvitse verrata jokaisen elementti vastaan ​​muita elementtejä. Sinä vain verrataan niitä että sinun täytyy verrata sitä vastaan. Niin, että on tavallaan abstrakti käsite. Ei hätää, jos se ei ole aivan lyömällä sinua juuri vielä. Mutta yleisesti, tämä on miten yhdistää lajitella toimii. Kysymykset, nopea kysymyksiä, ennen jatkan? Joo. 

Yleisö: Niin sanoit että otat 1, ja sitten 4, ja 6 ja laita ne. Joten eivät those-- ei Etsitkö niitä erillisinä elementteinä, ei koko? ANDI Peng: Joo. Joten mitä tapahtuu on, että et periaatteessa luovat upouusi array. Niin tiedät, että täällä, minulla on kaksi ryhmät koko 3, eikö? Niin tiedät, että minun lajitellut array tarvitsee kuusi elementtejä. Joten sinun tarvitsee vain luoda uusi muistin määrä. Olet siis ikään kuin tuhlailevaksi muistia, mutta se ei ole väliä koska se on niin pieni. Joten sinä katsot 1 ja sinä katsot 2. Ja te tiedätte, että 1 on alle 2. Niin tiedät, että 1 pitäisi mennä alussa kaikki nämä. 

Sinun ei edes tarvitse katso 3 ja 5. Joten tiedät 1 menee siellä. Sitten et periaatteessa katkaista 1. Se on, kuten, kuollut meille. Sitten meidän on vain 2, 3, 5, ja sitten 4 ja 6. Ja niin tiedät, että sinun vertailla 4 ja 2, oh, 2 pitäisi mennä sinne. Joten voit plop 2 alas, voit pilkkoa sen pois. Niin sitten sinun täytyy vain 3 ja 5 4 ja 6. Ja te vain pitää pilkkominen se pois kunnes laitat ne array. 

Yleisö: Joten olet vain aina verrataan [äänetön]? 

ANDI Peng: Aivan. Joten siinä mielessä, olet vain vertaamalla lähinnä, yksi numero vastaan ​​toinen numero. Ja koska tiedät että se on lajiteltu, sinua ei tarvitse käydä läpi kaikki numerot. Täytyy vain katsoa ensimmäinen. Ja sitten voit vain plop ne alas, koska tiedät ne kuuluvat, jos ne täytyy kuulua. Joo. Hyvä kysymys. 

Ja sitten jos joku teistä ovat hieman kunnianhimoinen, rohkeasti katsomaan tätä koodia. Tämä on oikeastaan fyysinen toteutus miten voisimme kirjoittaa yhdistämisen lajitella. Ja näet, se on hyvin lyhyt. Mutta ideoista se on melko monimutkainen. Joten jos tuntuu piirustus tätä teidän kotitehtäviä tänä iltana, rohkeasti. 

OK. Niin David meni tänä luento. Mitkä ovat parhaassa tapauksessa runtimes, pahimmassa tapauksessa varakäyntiajat, ja odotettu runtimes on yhdistämisen lajitella? Pari sekuntia ajatella. Tämä on melko kova, mutta eräänlainen intuitiivinen jos ajattelee sitä. Selvä. 

Yleisö: Onko pahimmillaan n log n? ANDI Peng: Aivan. Ja miksi se n log n. 

Yleisö: Eikö se, koska se tulee eksponentiaalisesti nopeammin, joten se on kuin funktio, joka eikä vain yksinkertaisesti n neliö tai jotain? ANDI Peng: Aivan. Joten miksi runtime tästä on n log n on because-- mitä olet tekee kaikki nämä vaiheet? Olet vain paloittelu se puoliksi oikeassa? Ja niin kun me teemme log, kaikki, että se tekee on jakamalla ongelma kahtia, kahtia, puoli, enemmän puolikkaat. Ja siinä mielessä, voit laji ja poistaa lineaarinen malli että olemme käyttäneet. Koska kun pilko asioita puoli, se on loki. Se on vain matemaattinen tapa esittää se. 

Ja sitten lopulta, lopussa, olet vain tehdä yksi viime läpi laittaa ne kaikki järjestyksessä, eikö? Joten jos sinun täytyy vain tarkistaa yksi asia, joka on n. Ja niin olet sellainen kertomalla kaksi yhdessä. Joten se on kuin sinulla, että lopullinen tarkista N alas täällä log n täällä. Ja jos kerrot heille, joka on n log n. 

Ja niin parhaassa tapauksessa ja pahimmassa tapaus ja odotettu ovat kaikki n log n. Se on myös kuin toinen lajitella. Se on kuin valinta lajitella siinä mielessä, että se ei ole väliä, mitä lista on, se on juuri menossa tehdä sama asia joka ikinen kerta. OK. Niin te voi nähdä, vaikka lajittelee, että olemme menneet through-- n potenssiin, se ei ole kovin tehokas. Ja tämäkin n log n on ole tehokkain. Jos te olette utelias, siellä on eräänlainen mekanismeja jotka ovat niin tehokkaita, että ne ovat lähes olennaisen tasaisia ​​runtime. 

Sinulla joitakin log n n. Sinulla joitakin log n n. Emme koske heitä tässä luokassa juuri nyt. Mutta jos te olette utelias, rohkeasti google, mitä tehokkain lajittelu mekanismeja. En tiedä, on olemassa joitakin todella hauska ystävät, like-- on joitakin todella Funny niitä, jotka ihmiset tekevät. Ja ihmettelet miten he koskaan ajatellut että. Joten Google, jos sinulla on ylimääräistä aika, siitä, mitkä ovat hauskoja tapoja että people-- sekä tehokas ways-- ihmiset ovat kyenneet toteuttamaan tapaisena. OK. Ja tässä on vain kätevä kaavio. Tiedän kaiken sinusta, ennen tietokilpailu 0, on omassa huoneessa luultavasti yrittää muistaa, että. Niin, että on mukavaa siellä teitä. Mutta älä unohda logiikkaa että made-- miksi nämä numerot tapahtuivat. Jos olet aina menetetty, vain tehdä että tiedät mitä lajittelee ovat. Ja voit käydä läpi ne mielessäsi selvittää, miksi ne vastaukset ovat näitä vastauksia. 

Selvä. Joten aiomme siirtää on lopuksi haku. Koska kuin sinä jotka ovat lukeneet PSET, haku on myös osa tämän viikon ongelma asetetaan. Sinua pyydetään toteuttamaan kahdenlaisia ​​hakuja. Yksi on lineaarinen haku ja yksi on binäärihaku. 

Niin lineaarinen haku on melko helppoa. Sinä vain haluat hakea elementtiin luettelon nähdä, jos saat sen. Sinun täytyy vain kerrata kautta. Ja jos se vastaa jotain, voit vain palauttaa sen, eikö? Mutta yksi että olemme eniten kiinnostuneita puhu on binäärihakupuu, oikea, mikä on hajota ja hallitse mekanismi, joka Daavid oli osoittaa luento. 

Muista puhelinluettelon esimerkki että hän pitää kasvatuksesta, joka hän sellainen kamppaillut hieman tämän vuoden aikana, jossa jaat ongelma kahtia, kahtia, puoli, uudelleen ja uudelleen, kunnes löydät mitä etsit? Ja sinulla runtime että samoin. Ja näet, se on huomattavasti tehokkaampi kuin mikä tahansa muu haku. 

Niin että me menisi noin täytäntöön binäärihaku on, jos meillä olisi array, indeksi 0-6, seitsemän elementtiä, voimme katsoa keskellä, right-- pahoillani, jos meidän kysymys first-- jos haluamme kysyä kysymyksen, ei array sisältävät elementin 7, tietenkin, että ihmiset, ja ottaa niin pieni joukko, se on helppoa meille sanoa kyllä. Mutta tapa toteuttaa binäärisen haku olisi katsoa keskellä. 

Tiedämme, että indeksi 3 keskellä, koska me tietää on seitsemän elementtejä. Mitä 7 jaettuna 2? Voit katkaista että ylimääräinen 1. Sinulla 3 keskellä. Joten on joukko 3 yhtä 7? Se ei ole, eikö? Mutta me voimme tehdä pari tarkastuksia. On joukko 3 alle 7 tai on joukko 3 yli 7? 

Ja me tiedämme, että se on alle 7. Joten tiedämme, että, oi, sen on ei olla vasen puoli. Tiedämme, että se on oikea puoli, oikea? Joten voimme vain katkaista puoli jono. Emme edes tarvitse katsoa sitä enää. Koska tiedämme, että puolet problem-- me tiedämme, että vastaus on oikea puoli meidän ongelma. Joten me katsokaa nyt. 

Joten nyt katsomme Keskellä mitä on jäljellä. Tämä indeksi 5. Teemme sama tarkastus uudelleen ja näemme, että se on pienempi. Joten odotamme vasemmalla että. Ja sitten näemme, että tarkastus. Onko array arvo indeksi 4 vastaa 7? Se on. Joten voimme palata totta, koska löysimme arvo listallamme. Onko tapa Kävin läpi että järkeä kaikille? OK. Annan te ehkä, kuten, kolme, neljä minuuttia selvittää Miten pseudokoodilla tämä. 

Joten kuvitella Pyysin sinua kirjoittaa toiminto nimeltään haku () joka palasi arvo, Boolen arvo, että oli totta tai false-- kuten, totta, jos olet löytänyt arvo, false jos et. Ja sitten olit hyväksyttiin arvo sinua etsivät arvoiksi, joka on array-- OH, olen ehdottomasti laittaa että väärässä paikassa. OK. Ainakin, että pitäisi olla ollut oikealle arvoja. Ja sitten int n on numero elementtien että jono. Miten te sitten yrittää sen pseudokoodilla että ongelma? Annan sinulle kaverit kuten kolme minuuttia tehdä se. Ei, mielestäni on olemassa only-- joo, siellä on yksi oikea täällä. Yleisö: Voinko? ANDI Peng: Joo, Sain sinut. Onko se toimi? OK, viileä. 

OK. Selvä kaverit, olemme menossa hillitä sitä. OK. Joten olettaa meillä tämän ihanan pikku array n arvoja sen. En piirtää viivoja. Mutta miten osaamme yrittää kirjoittaa tähän? Onko kukaan halua antaa minulle ensimmäinen rivi? Jos haluat antaa minulle ensimmäinen rivi tämän pseudokoodin. 

Yleisö: [äänetön] Yleisö: Sinun haluavat iteroida through-- Yleisö: Vain toinen silmukka? Yleisö: --for. 

ANDI Peng: Eli tämä on vähän hankala. Ajattele about-- haluat pitää käynnissä tämän silmukan uudestaan ​​ja uudestaan ​​saakka? 

Yleisö: Kunnes [äänetön] arvo on sama kuin arvo. ANDI Peng: Aivan. Joten voit itse vain write-- voimme jopa yksinkertaistaa sitä enemmän. Voimme vain tehdä samalla silmukka, oikea? Joten voit vain olla loop-- me tiedämme, että se on taas. Mutta juuri nyt, aion sanoa "loop" - kautta mitä? Silmukka until-- mikä on meidän päättyy ehto? Mielestäni Kuulin sen. Kuulin jonkun sanovan sen. 

Yleisö: arvot vastaa keskellä. ANDI Peng: Sano se uudelleen. Yleisö: Tai, kunnes arvo etsit sillä on yhtä suuri kuin keskimmäinen arvo. 

ANDI Peng: Mitä jos se ei ole siellä? Mitä jos arvo etsit sillä ei ole oikeastaan ​​tässä array? Yleisö: Palaat 1. 

ANDI Peng: Mutta mitä haluamme silmukka kunnes jos meillä on kunnossa? Joo. 

Yleisö: Kunnes on olemassa vain yksi arvo? ANDI Peng: Voit silmukka until-- niin tiedät, että olet menossa on max, eikö? Ja te tiedätte, että olet menossa olla min arvo, eikö? Koska myös, että on jotain Unohdin sanoa ennen, että jotain, joka kriittinen binary haku on, että joukko on jo järjestetty. Koska ei ole mitään tapaa tehdä tämä jos he vain satunnaisesti arvoja. Et tiedä, jos yksi on suurempi kuin muut, eikö? 

Niin tiedät, että max ja teidän min tässä, eikö? Jos aiot sopeutuvan max teidän min ja mid-- Haluan vain olettaa sinun mid arvo on oikea here-- aiot pohjimmiltaan silmukka kunnes minimi on suunnilleen sama kuin korkein, oikealla, tai jos max ei ole sama kuin min. Oikea? Koska kun näin tapahtuu, te tiedätte, että olet lopulta osui sama arvo. Joten haluat silmukan kunnes min on pienempi tai yhtä suuri kuin to-- oho, ei pienempi kuin tai yhtä suuri kuin, toisinpäin around-- max. 

Onko järkeä? Otin muutaman yrittää saada tätä oikeutta. Mutta silmukka kunnes korkein arvo on olennaisesti lähes vähemmän tai yhtä suuri kuin teidän minimi, eikö? Silloin tiedät että olet lähentyneet. Yleisö: Koska korkeinta arvo on pienempi kuin pienin? ANDI Peng: Jos pidät muuttaa sitä, mikä me aiomme tekevän tässä. Onko siinä järkeä? Pienin ja suurin sallittu ovat vain kokonaislukuja, että olemme luultavasti menossa haluavat luoda pitää Seuraa jossa etsimme. Koska array olemassa riippumatta siitä, mitä teemme. Kuten, emme ole oikeastaan ​​fyysisesti paloittelu pois array, eikö? Olemme vain säätämällä jossa etsimme. Onko siinä järkeä? 

Yleisö: Joo. 

ANDI Peng: OK. Joten jos se on edellytys meidän silmukka, mitä me haluamme sisällä tämän silmukan? Mitä me aiotaan haluavat tehdä? Joten nyt, meillä Max ja min, oikea, luultavasti luotu täällä jossain. Aiomme luultavasti halua löytää keski, oikea? Miten aiomme olla löytää keskellä? Mikä mathematical-- Yleisö: Max ja min jaettuna 2. ANDI Peng: Aivan. Onko siinä järkeä? Ja te olette, miksi me ei vain use-- miksi teimme tämän sen sijaan tehdä vain n jaetaan 2? Se johtuu n on arvo joka tulee pysyä samana. Oikea? Mutta kuten me sopeutamme vähimmäis- ja enimmäisarvot, he aikovat muuttaa. Ja sen seurauksena, meidän keski tulee muuttumaan liian. Joten siksi haluamme tehdä tätä täällä. OK. 

Ja sitten, nyt olemme löytäneet our-- joo. 

Yleisö: Just a quick question-- kun sanot min ja max, me olettaen että se on jo järjestetty? 

ANDI Peng: Joo, se on todella edellytys binäärihaku, että sinun täytyy tietää se lajitellaan. Minkä vuoksi lajitella, te kirjoitatte Harjoitus ennen binäärihakupuu. OK. Joten nyt me tiedämme, missä keskipiste on, mitä haluat tehdä täällä? 

Yleisö: Haluamme verrata että toinen. ANDI Peng: Aivan. Joten aiot verrata keski- arvo, eikö? Ja mitä se kertoo meitä, kun vertaamme? Mitä haluamme tehdä jälkikäteen? 

Yleisö: Jos arvo on suurempi kuin puolivälissä, haluamme leikata se pois. ANDI Peng: Aivan. Joten jos arvo on suurempi kuin puolivälissä, olemme menossa haluavat muuttaa näitä minimi ja maxes, eikö? Mitä haluamme muuttaa? Joten jos me tiedämme arvo on jossain täällä, mitä sinä me muuttaa? Haluamme muuttaa vähintään olla puolivälissä, eikö? Ja sitten muuta, jos se on tässä puoli, mitä haluamme muuttaa? 

Yleisö: Korkeimman. ANDI Peng: Joo. Ja sitten olet juuri menossa pitää silmukoiden, eikö? Koska nyt, kun yksi iteraation kautta, sinulla max täällä. Ja sitten voit laskea puolivälissä. Ja sitten voit vertailla. Ja aiot jatkaa kunnes min ja maxes ovat olennaisesti lähentyneet. Ja silloin te tiedätte, että olet osuma lopussa. Ja joko olet löytänyt sen tai et ole tässä vaiheessa. 

Onko tämä järkevää kaikille? OK. Tämä on aika tärkeä, koska sinulla on kirjoittaa tämän koodissa tänä iltana. Mutta teillä melko hyvä tunne siitä, mitä pitäisi tehdä, mikä on hyvä. OK. Joten meillä noin seitsemän minuuttia jäljellä jakso. Joten aiomme puhua tämä PSET että me voidaan tehdä. Joten pset on jaettu kahtia. Alkupuoliskolla liittyy täytäntöönpanosta löytää jossa voit kirjoittaa lineaarinen haku, binary haku, ja lajittelualgoritmi. 

Joten tämä on ensimmäinen aika PSET jossa Annamme te mitä kutsutaan jakelu koodi, joka on koodi että olemme ennalta kirjoitetun, mutta lähti juuri joitakin paloja pois voit lopettaa kirjoittamisen. Joten te, kun sinä katsot tätä koodi, saatat saada todella pelottaa. Jos olet vain haluavat, Ahh, I eivät tiedä, mitä se on tekemässä, En tiedä, kuten, että näyttää niin monimutkainen, Ahh, rentoutua. Se on ok. Lue spec. Spec selittää sinulle täsmälleen mitä kaikki nämä ohjelmat tekevät. 

Esimerkiksi, generate.c on ohjelma jotka tulevat teidän PSET. Et itse tarvitse koskettaa sitä, mutta sinun pitäisi ymmärtää, mitä se tekee. Ja generate.c, kaikki se tekee on joko tuottaa satunnaisia ​​numeroita tai voit antaa sen siemen, kuten sovittu määrä, että se kestää, ja se tuottaa enemmän numeroita. Joten siellä erityisellä tavalla toteuttaa generate.c jossa voit vain tehdä joukko numeroita voit testata muita menetelmiä. 

Joten jos halusi, varten Esimerkiksi testata löytää, mitä haluaisi ajaa generate.c, tuottaa joukko numeroita, ja sitten ajaa auttajia toiminto. Sinun auttajia toiminto on, jos olet todella fyysisesti koodausta. Ja ajatella auttajia kuin kirjastotiedosto olet kirjallisesti että find soittaa. Ja niin sisällä helpers.c, luultavasti do etsiminen ja lajittelu. 

Ja sitten aiot olennaisesti vain laittaa ne kaikki yhdessä. Spec kertoo miten laittaa että komentorivillä. Ja voit testata, ei sinun lajitella ja etsiä toimivat. Viileä. Onko kukaan jo aloitettu ja kohdannut ongelmia tai kysymyksiä heillä on oikeus nyt tämän? OK. 

Yleisö: Odota. Minulla on kysymys. 

ANDI Peng: Joo. 

Yleisö: Aloin tehdä lineaarinen toimialalla helpers.c ja se ei todellakaan toimi. Mutta sitten myöhemmin, sain selville me vain täytyy poistaa se ja tehdä binary haku. Joten se väliä, jos se ei toimi? 

ANDI Peng: Lyhyt vastaus on ei. Mutta koska olemme not-- Yleisö: Mutta kenenkään todella tarkkailun. ANDI Peng: Emme ole koskaan menossa katsomaan että. Mutta todennäköisesti haluat tehdä Varmista hakua toimii. Koska jos lineaarinen haku ei toimi, niin mahdollisuudet ovat sinun binary haku ei tule toimimaan samoin. Koska sinulla on samanlaisia logiikka molemmat. Ja ei, se ei ole oikeastaan ​​väliä. Joten ainoat voit kääntyä vuonna ovat lajitella ja binäärihakupuu. Joo. 

Ja myös, paljon lapset olivat yrittää koota helpers.c. Et oikeastaan ​​sallittu tehdä niin, koska helpers.c ei ole päätehtävä. Ja niin sinun pitäisi vain olla todella kokoaminen tuottaa ja löytää, koska löytää puhelut helpers.c ja toimintojen sisällä. Niin että tekee virheenkorjaus kipu Butt. Mutta se, mitä meidän täytyy tehdä. Yleisö: Sinä vain tehdä kaikki, eikö? ANDI Peng: Voit vain tehdä kaikki samoin, joo. OK. Niin, että se siitä, mitä PSET pyytää teitä kaikkia tekemään. Jos sinulla on kysyttävää, ota vapaasti kysyä minulta jakson jälkeen. Olen täällä, kuten, 20 minuuttia. 

Ja joo, PSET n todellakaan ole niin paha. Te pitäisi olla OK. Nämä, seuraa vain ohjeita. Kind of on tunne, loogisesti, mitä pitäisi tapahtua ja voit olla hieno. Älä ole liian peloissaan. Siellä on paljon koodia jo kirjoitettu siellä. Älä uskalla jos et ymmärtää, mitä kaikki tämä tarkoittaa. Jos se on paljon, se on täysin hieno. Ja tulevat virka. Autamme sinua katsomaan. 

Yleisö: Kun ylimääräinen toiminnot, näytämmekö ne ylös? 

ANDI Peng: Joo, ne ovat koodi. Pelissä on 15, puolet se on jo kirjoitettu puolestasi. Joten ne toiminnot jo koodi. Jep. Selvä. No, onnea. Se on inhottavaa päivä. Joten toivottavasti te eivät ole kovin paha mieli pysyä sisällä ja koodausta.