SPEAKER 1: Hei kaikille! Tervetuloa takaisin osiosta. Niin iloinen, että niin monet teistä sekä täällä, ja jokainen, joka tarkkailee verkossa. Joten, kuten tavallista tervetuloa takaisin. Toivon, että te kaikki oli ihana viikonloppu, täynnä lepoa, rentoutumista. Se oli kaunis eilen. Joten, toivon olet nauttinut ulkona. 

Joten ensimmäinen pari ilmoituksia. Arvostelu. Niin, suurin osa teistä olisi saanut sähköposteihin minulle omasta Scratch PSET, sekä luokittelu- ja PSET 1. Joten, vain pari asiaa. Muista käyttää check50 vuonna style50. Näiden on tarkoitus olla resursseja te, varmista, että olet saada niin monta pistettä kuin mahdollista ilman turhaan menettää ne. Joten asiat kuten tyyli ovat erittäin tärkeitä. Aiomme ottaa pois sitä. Jotkut teistä saattavat olla jo huomannut, että teidän PSET. Ja check50 on vain todella helppo tapa varmistaa että olemme todella palaamassa mitä on palautettava käyttäjälle, ja että kaikki on toimi kunnolla. 

Toisessa huomata, varmista, että lataamalla asioita oikeaan kansioon. Se tekee elämästäni juuri hieman vaikeampaa jos lataat PSET 2 osaksi PSET 1 koska kun lataan asioita, ne eivät lataa oikein. Ja tiedän, että se on vähän hutera järjestelmässä tottua, mutta vain olla erittäin varovainen, jos vain minulle, niin, että kun olet saada sähköposteja Like 2 A.M. ja olen luokittelu. Jos ei aiheuta minun täytyy katsoa kaikki ympäri sinun PSET. Cool. 

Tiedän että se on aikaisin, mutta en täysin sai ottaa kenet jonka essee, joka on asianmukaisesti tämän perjantaina, että minun professorit olivat aivan kuten, oh yeah. Muista, olet essee takia perjantaina. Niin, tiedän kukaan ei tykkää ajatella midterms, mutta ensimmäinen tietokilpailu on 15. lokakuuta, joka Lokakuu on tästä viikosta alkaen. Niin, se voisi olla ennemmin kuin odotit on kaikki. Niin että et ole heittänyt pois vartija kun Mainitsen ensi viikon jaksossa, että oi, tietokilpailun ensi viikolla, ajattelin Antaisin teille vähän enemmän of heads up nyt. 

Joten ongelma asetettu, numero kolme. Miten ihmiset lukenut spec uteliaisuudesta? OK. Saimme pari. Eräänlainen alas viime viikossa, mutta se on OK. Tiedän, että se oli kaunista. Joten Break Out. Ehdottomasti jälkeen saat tehdä tänään lukea spec ainakin kokeile kuten lataamista jakelu koodi ja käynnissä kuin ensimmäiseen, asia, että he pyytävät sinua. Koska käytämme jakelu koodin ja kirjasto että olemme vasta using-- --It vain toinen kerta, kun olemme tehneet tämän PSET, hulluja asioita voi tapahtua laitteen kanssa, ja haluat löytää, että ulos nyt vai myöhemmin. 

Koska jos se on torstai-iltana tai sen Keskiviikkoiltana ja jostain syystä Laitteen vain ei haluavat ajaa kirjasto tai jakeluun koodia, että välineet et voi edes alkaa tehdä koodausta. Koska et voi tarkistaa nähdä, jos se toimii. Sinun ei tule pystyä nähdä, jos se kokoaa. Haluat huolehtia näiden aikaisin viikolla, kun voit silti lähettää minulle sähköpostia tai jonkin muun TF: iä, ja voimme saada ne kiinteät. Koska nämä kysymykset jotka ovat menossa pysäyttää sinut tekemästä mitään todellista edistystä. Se ei ole kuin yksi vika, joka voit vain sellaista ohittaa. Jos sinulla on ongelmia teidän Laitteen tai jakelu koodi, Haluatko todella päästä, että otetaan care of mieluummin ennemmin kuin myöhemmin. Joten vaikka et aio itse aloittaa koodaus, lataa jakelu koodi, lukea spec, varmista kaikki työskentelee siellä. OK? Jos voit vain tehdä sen, minä luvata elämänne on helpompaa. Ja niin olet todennäköisesti menossa tehdä se nyt oikein? OK. Niin, kysyttävää siellä? Mikä tahansa logistisen asioita? Jokainen on hyvä? OK. 

Disclaimer niille te huoneeseen ja verkossa. Aion yrittää vaihtaa välillä PowerPoint laite koska olemme menossa olla tekemässä joitakin koodaus tänään suosittu kysynnän anonyymi ehdotus kysely Lähetin viime viikolla. Joten, teemme joitakin koodaus. Joten, jos te myös haluavat tulipalon up your laitteet, ja sinun pitäisi saanut sähköpostia minulta, jossa näytteen tiedosto. Voit vapaasti tehdä niin. 

Joten, aiomme puhua GDB, joka on debuggeri. Se tulee auttamaan sinua eräänlainen selvittää missä asiat ovat menossa pieleen koodissa. Se on oikeastaan ​​vain tapa, jolla voit astua läpi koodia, koska se tapahtuu, ja voi tulostaa muuttujien tai nähdä mitä todella tapahtuu konepellin alle jakeet ohjelma juuri käynnissä, se on kuin faulting, ja et pidä, ei ole aavistustakaan mitä juuri tapahtui täällä. En tiedä, mitä linjaa se epäonnistui. En tiedä missä se meni pieleen. Joten, GDB aikoo auttaa sinua siinä. Lisäksi, jos päätät jatkaa kyllä, ja ottaa 61, se todella, todella olla sinun paras ystävä, koska minä voi kertoa koska koen, että luokassa. 

Menemme katsomaan binary haku, joka jos te muistaa suuri puhelinluettelo esimerkki spektaakkeli luokasta. Tulemme täytäntöön panemiseksi, ja kävelevän että vähän enemmän, ja sitten olemme menossa läpi neljä Erilaisille, jotka ovat Bubble, Valinta, lisäys, ja Merge. Cool. Niin, GDB kuten mainitsin, on debuggeri. Ja nämä ovat sellaisia ​​suuria asioita, iso toimintoja tai komentoja että käytät sisällä GDB-, ja minä vaellan läpi demon se toinen. 

Niin, tämä ei ole vain tarkoitus jäädä abstrakti. Yritän tehdä niin konkreettisia mahdollisimman teitä. Niin, tauko. Se tulee joko tauko kuten jotkut numero, joka edustaa linjaa oman ohjelman, tai voit nimetä toiminnon. Joten, jos sanot rikkoa tärkein, se pysähtyy tärkein, ja voit kävellä läpi tämän tehtävän. 

Samoin jos sinulla on jokin ulkoinen toimivat kuten Swap tai Cube, että me katsoimme viime viikolla. Jos sanot rikkoa yksi niistä, aina, kun ohjelma osuu, että se tulee odottaa sinua kertoa se, mitä tehdä. Ennen se vain toteuttaa niin sinua voisi todella astu toiminto ja katso mitä tapahtuu. Joten seuraavan, vain hyppää yli seuraavalle riville, menee toimintoja. Askel. Nämä ovat kaikki hieman abstrakteja. Joten, olen juuri menossa ajaa niiden läpi, mutta näet ne käytössä toinen. 

Astu toimintoa. Joten kuten sanoin, kuten swap, se olisi voit itse kuin jos olet kuten fyysisesti tehostamalla sisällä, voit sotkea niitä muuttujia, tulostaa mitä he ovat, mitä on tekeillä. Luettelo kirjaimellisesti vain tulostaa ulos ympäröivään koodi. Joten, jos sellainen unohtaa missä olet oman ohjelman, tai mietit mitä tapahtuu sen ympärillä, tämä vain tulostaa segmentin samankaltaisten viisi tai kuusi riviä sen ympärille. Joten, voit saada suuntautunut siitä, missä olet. 

Tulosta jokin muuttuja. Joten, jos sinulla on avain, kuten Caesar, että me tarkastelemme. Voit sanoa Tulosta Key missään vaiheessa. Se kerron teille, mitä arvoa on niin että ehkä jossain matkan varrella, sinun korvasi avain. Voit itse kertoa, että koska voit itse todeta, että arvo. 

Vuonna paikalliset, vain tulostaa Anna paikallisia muuttujia. Joten, milloin olet sisällä silmukan, ja haluat vain nähdä kuin, oh. Mikä on minun minä? Mikä on tämä keskeinen arvo että minä alustaa täällä? Mikä on viesti tässä vaiheessa? Se vain tulostaa kaikki niistä, jotta voit ei tarvitse erikseen sanoa, Print I. Tulosta viesti. Tulosta Key. Ja sitten Näyttö. Mitä se tekee, on kuin selata ohjelman se täytyy vain varmistaa, että se on näyttänyt tiettyjä muuttuja joka kohdasta. Niin että te also-- --it on eräänlainen oikotie, jossa sinun ei tarvitse pitää käynnissä kuin, oh. Tulosta Key tai Tulosta I. Se vain automaattisesti tehdä sen sinulle. 

Niin, että aiomme nähdä, miten tämä menee. Aion yrittää ja kytkin yli minun laite. Nähdä, jos voin tehdä tämän. Kaikki. Olemme juuri menossa peilata sitä. Ei ole mitään hullua minun laptop anyways. OK. Tämän on oltava tämä. Se on niin pieni. Katsotaanpa, jos voimme tehdä tämän. 

OK. Alice on ilmeisesti kamppailee tässä vain vähän, mutta saamme sen momento. OK. Olemme juuri menossa nostaa. OK. Voivatko kaikki sellainen nähdä, että? Ehkä vähän? Tiedän, se on vähän pieni. Et voi täysin selvittää miten tämä suurempi. Jos joku tietää. Ei kukaan tiedä, miten tehdä se iso? OK. Aiomme roll sitä. Ei ole väliä muutenkaan, koska se on vain se koodi, että te pitäisi on. 

Mikä on tärkeämpää on päätelaite täällä. Ja meillä on täällä Miksi se on niin pieni? Asetukset. Oh. True Ike. Miten tämä on? Pois sieltä. Onko se parempi kaikille? OK ,. Cool. 

Tiedät, kun olet CS luokan teknisiä ongelmia ovat tavallaan osa the-- Joten, nyt tyhjentää. OK. Niin, täällä jaksossa, joka meillä oli täällä. Caesar on suoritettava tiedosto. Joten tein sen. Niin, yksi asia on ymmärrettävä kanssa GDB on että se toimii vain ohjelmatiedostoja. Joten, et voi käyttää sitä dotsy. Sinun täytyy itse tehdä Varmista, että koodi kokoaa, ja että se voi todella ajaa. 

Joten varmista, että jos se ei koota, saada se koota, jotta voit sellaista ajaa sen läpi. Joten aloittaa GDB, kaikki te teette, Gloria tyyppi GDB, ja sitten vain tiedosto, jonka haluat. Olen aina kirjoitusvirheitä Caesar. Mutta haluat varmistaa, koska se on suoritettavan, TI: n piste flash jotta tarkoittaa olet menossa ajaa CSI aiot toteuttaa Tämän tiedostot joko debugger. OK. Joten, et, että saat tällainen siansaksaa. Se on vain kaikki asiat noin virheenkorjauksen. Sinun ei todellakaan tarvitse murehtia sitä juuri nyt. Ja kuten näette, meillä on tämä avoin parens, BKT, lähellä parens, ja juuri sellainen näyttää meidän komentoriviltä, ​​eikö? 

Joten, mitä haluamme do-- --So, Ensimmäinen asia me haluamme valita paikka rikkoa sitä. Niin, siellä on yksi vika Tässä Caesar ohjelmaan että esittelen, että aiomme selvittää. Se Mitä se on se vie tulo Barfoo kokonaan isoilla kirjaimilla, ja jostain syystä se ei muuta A. Se vain jää yksin, on kaikkea muuta oikein, mutta toinen kirje Pysyy ennallaan. Joten, aiomme yrittää selvittää, miksi näin on. Joten, ensimmäinen asia mitä yleensä haluavat tehdä, kun aloitat GDB- on selvittää, mistä rikkoa sitä. 

Joten Caesar on melko lyhyt ohjelma. Meillä on vain yksi toiminto, eikö? Mikä oli meidän toiminnon Caesar? On vain yksi toiminto, Main oikea? Tärkein on funktio kaikki ohjelmat. Jos sinulla ei ole Main, voisin olla hieman huolissaan juuri nyt, mutta toivon teille kaikille oli Main siellä. Joten, mitä voimme tehdä, on voimme vain rikkoa Main, noin vain. Niin, se sanoo, OK. Asetamme murtuessa ketään. 

Joten, nyt asia on muistaa Caesar kestää yhden komentorivillä oikeus ja emme ole tehneet, että missään vielä. Joten, mitä tehdä, on, kun voit itse mennä ajaa ohjelman, mitään ohjelmaa, joka olet käynnissä GDB- joka tarvitsee komentoriviltä argumentteja, aiot syöttää kun aloitat käynnissä se. Eli tässä tapauksessa, teemme Juokse keskeinen kolme. Ja se todella alkaa. 

Joten, jos näet täällä, meillä on Jos RC ei ole sama kuin 2. Joten jos te kaikki on että tiedosto, joka Lähetin ylös näet, että se on kuin Ensimmäinen rivi meidän päätehtävä, eikö? Se tarkistaa, onko meillä oikea määrä argumentteja. Joten, jos mietit jos RC on oikea, voit tehdä jotain aivan Tulosta RC. RC on kaksi, joka on mitä odotimme, eikö? 

Joten, voimme mennä seuraavaksi, ja jatkaa kautta. Niin, meillä on joitakin keskeisiä siellä. Ja voimme painaa läpi keskeiset varmistaa, että on oikea. Mielenkiintoinen. Ei aivan sitä mitä odotimme. Niin, yksi asia on ymmärrettävä GDB myös, on että se ei ole ennen kuin olet itse osuma Seuraavaksi tästä, jonka olet juuri nähnyt on todella toteutettu. Eli tässä tapauksessa Key ei ole vielä asetettu. Niin, Key on joitakin roskat arvo että näet pohjassa siellä. Negatiivinen $ 120-- --It miljardista ja jotain outoa asiat oikein? Se ei ole avain, että odotimme. Mutta jos me osuma Seuraava ja sitten me yrittää Tulosta avain, se on kolme. 

Jokainen nähdä, että? Joten, jos saat jotain että et pidä, odota. Tämä on täysin väärin, ja en tiedä miten tämä tapahtuisi, koska kaikki mitä haluan tehdä, on antaa numeron, muuttuja, yrittää osua Seuraavaksi kokeile tulostusta sen uudelleen, ja katso jos se toimii. Koska se on vain menossa toteuttaa ja todella antaa jotain, kun olet osuma Seuraava. Järkevää kaikille? Uh huh? 

SPEAKER 2: Kun satunnainen numerot mitä se tarkoittaa? 

SPEAKER 1: Se on vain satunnaisesti. Se on vain roskaa. Se on vain jotain, että Tietokone satunnaisesti luovuttaa. Cool. Joten, nyt voimme liikkua, ja niin Nyt meillä on tämä pelkkää tekstiä GetString. Joten, haluan vain esitellä mitä tapahtuu, kun me osuma Seuraava täällä. Meidän GDB- sellainen katoaa, eikö? Tämä johtuu GetString nyt pystyvät, eikö? Joten, kun näimme pelkkää tekstiä on yhtä kuin GetString, avoin parens ja parens, ja me osuma Seuraavaksi tästä on toteutettuja nyt. Niin, se odottaa meille syöttää jotain. 

Joten, aiomme syöttää ruokamme joka on, mitä se ei ole kuten jo sanoin ja että vain sanoo, että se on päättynyt täytäntöönpanosta, että suljettu kiinnike tarkoittaa että se on poistuminen ulos että silmukka. Joten, voimme lyödä Seuraavaksi ja nyt, koska olen varma, että olet kaikki tutut Caesar, tämä on, mitä tämä linja tulee tekemään. Se on int i on 0, n on Strlen, pelkkää tekstiä, ja sitten I on pienempi kuin N, I, plus, plus. Mikä on tämä silmukka aiot tehdä? Avaa viesti. Cool. Joten, nyt alkaa tehdä niin. 

Joten, jos tämä ehto täsmää, meidän ensimmäinen? Jos se on B, se on pelkkää tekstiä I. Me voivat saada tietoa paikallisia. Joten, minä on nolla, ja jos kuusi, joka odotamme, ja meidän avain on kolme. Kaikki tämä järkevää, eikö? Nämä numerot ovat kaikki mitä niiden pitäisi olla. Niin, hyräillä? SPEAKER 3: Olen satunnaislukuja minun. SPEAKER 1: No, voimme check-- --we voi jutella, että toinen. Mutta sinun pitäisi saada tämä. Joten, jos meillä on pääomaa B meidän ensimmäinen, Tämä tila on kiinni se, eikö? Joten, jos me osuma Seuraavaksi näemme että tämä olisi tosiasiassa suorittaa. Koska jos olet seuraavista pitkin koodissa, tämä linja täällä, missä tavallinen teksti I korvataan tämän aritmeettinen, pannaan täytäntöön ainoastaan, jos Jos ehto on oikea oikea? 

GDB on vain menossa näyttämään asioita, jotka ovat tosiasiassa ajetaan. Joten jos tämä Jos ehto ei täyty, se juuri menossa siirtyä seuraavalle riville. OK? Niin, meillä on tuo. Tämä teline tarkoittaa että se suljettu pois, että silmukka nyt. Niin, se tulee aloittaa uudelleen. Aivan niin. Niin, että voimme saada tietoa meidän paikalliset täällä, ja me näemme, että ensimmäinen kirjain on muuttunut, eikö? Se on nyt E, kuin sen pitäisi olla. Voimme siis jatkaa. 

Ja meillä on tämä tarkastus. Ja tämä tarkistus pitäisi toimia, eikö? Se on A. Se pitäisi muuttaa kolme kirjainta eteenpäin. Mutta jos huomaat, me saada jotain erilaista. Joten tässä tapauksessa täällä, se kiinni se, ja niin tämä linja toteutetaan, joka muutti meidän B. Mutta tässä tapauksessa täällä, meillä on, että se vain ohitetaan se, ja meni [? L Siff. ?] Joten jotain siellä tapahtuu. Mitä tuo kertoo teille, että, me tiedämme, että se olisi kiinni täällä, mutta se ei ole. Näkeekö kukaan, mitä meidän Ongelmana on, että linja? Se on hyvin minuutin juttu. Ja voit myös tarkastella koodia. Se on myös line-- unohtaa, mitä linjaa se on vuonna there-- mutta se on [kuultavissa]. Kyllä? 

SPEAKER 4: Se on suurempi kuin sivulla, jos olet lukenut sen kirjan. SPEAKER 1: Aivan. Niin, debuggeri voinut kertoa teille, mutta debuggeri voisi saada sinut alas linja että tiedät ei toimi. Ja joskus, kun erityisesti myöhemmin lukukauden, kun olet tekemisissä sata, sata muutaman rivin koodia, ja voit en tiedä missä se ei ole, tämä on hyvä tapa tehdä se. Niin, löysimme bug. Voit korjata sen tiedoston, ja sitten voisi käyttää sitä uudelleen, ja kaikki toimisi täydellisesti. Ja suurin asia on tämä voi tuntua, OK. Joo. Cool. Tiesit mitä etsit. Niin, tiesit mitä tehdä. 

GDB- voi olla erittäin hyödyllistä, koska olet voi tulostaa kaikki nämä asiat, jotka olet ei. Se on paljon enemmän hyötyä kuin printf. Kuinka moni teistä käyttää kuten printf lausunnot selvittää, missä vika on, eikö? Niin, tässä, et täytyy pitää menossa takaisin, ja haluavat kommentoi Printf, tai kommentoimalla ulos, ja selvittää, mitä kannattaa tulostaa. Tämä oikeastaan ​​vain voit selata, tulostaa asiat koska olet menossa läpi, joten voit tarkkailla, miten ne muuttuvat reaaliajassa, koska ohjelma on käynnissä. 

Ja se vie vähän hieman totuttelua. Voin lämpimästi suositella vain eräänlainen olemisen hieman turhautuneita siihen juuri nyt. Jos vietät tunnin aikana ensi viikolla opetella käyttämään GDB, säästät itsesi niin paljon aikaa myöhemmin. Ja kirjaimellisesti. kerromme Tämän ihmisiä joka vuosi, ja muistan, kun otin luokka, olin kuin, aion olla hieno. Ei. PSET 6 tuli ja olin kuten, aion oppia miten käyttää GDB- koska en tietää, mitä täällä tapahtuu. 

Joten jos otat aikaa niin käyttää sitä pienempiä ohjelmia että aiot olla työskentelevät, kuten työskentely kautta jotain Visionare, kuten tämä. Tai jos haluat lisää Käytännössä olen varma Voisin keksiä buginen ohjelmia, voit debug jos haluat. 

Mutta jos vain kestää jonkin aikaa saada käyttää sitä, vain leikkiä sen kanssa, se todella toimii hyvin. Ja se on todella yksi niitä asioita, jotka juuri täytyy yrittää ja saada kädet likainen kanssa, ennen kuin todella ymmärtää se. Olen oikeastaan ​​vain ymmärtänyt sitä kerran Jouduin debug asioita sen kanssa, ja se on paljon mukavampi olla ajatus miten debug mieluummin ennemmin kuin myöhemmin. OK. Cool. Tiedän, että on tavallaan kuin pikakurssin GDB, ja aion ehdottomasti työskennellä saada Näiden etsiä isompi ensi kerralla. Cool. 

Joten, jos menemme takaisin meidän PowerPoint. Onko tämä menossa töihin? AWH. Kyllä. OK. Joten, jos joskus tarvitset jotakin ne uudelleen, siellä on lista. Joten Binäärihaku, jonka kaikki muistaa suuri spektaakkeli David repimässä puhelinluetteloita kahtia. En todellakaan saa puhelinluetteloita enää, koska kuten Mistä saada puhelinluetteloita näinä päivinä? En todellakaan tiedä. Binary Search. Muistaako kukaan miten Binary Search toimii? Kuka tahansa? Joo? SPEAKER 5: Tiedätkö milloin sinä katsot mikä puoli se olisi sen pohjalta, ja päästä eroon toinen puoli. 

SPEAKER 1 Täsmälleen. Joten, Binäärihaku, se on eräänlainen a-- --we haluavat kutsua sitä hajoita ja hallitse. Joten, mitä voit tehdä on näytät keskellä, ja näet, jos se vastaa mitä etsit. Ja jos ei, niin yrität selvittää, se aikoo jättää puoli tai oikea puoli. Niin, tämä voisi olla, jos etsit jotain, joka on aakkosjärjestyksessä, näet, oh. Onko Allison tullut ennen M? Kyllä. Joten, aiomme katsokaa alkupuoliskolla. 

Tai se voi olla kuin numeroita. Mitään, että voit vertaa, se voidaan lajitella. Voit käyttää binary haku. Niin, kukaan muistaa tämä kaavio tai mitä tämä on? Se Asymptoottinen monimutkaisuus. Niin, tämä kuvaaja vain kuvataan, kuinka kauan se vie sinua ratkaisemaan ongelman voit lisätä monia asioita että käytät. 

Niin, meillä on N, joka on lineaarinen aika. Jos N yli kaksi, joka on hieman parempi, silti kasvaa erittäin nopeasti. Ja sitten olemme Kirjaudu, joka on mitä pidämme binäärihaku. Jos huomaamme, sillä ongelma saa paljon ja paljon suurempi, aikaa se vie sinua ratkaisemaan sen ei oikeastaan ​​lisätä, että paljon. Se on kuin verrattavissa täällä alussa. Olet kuin, OK. Mitään täällä ei oikeastaan väliä kumpi käytämme, mutta saat ulos miljoonaa miljardia. Yrität löytää some-- --you're yrittää löytää neulaa heinäsuovasta. 

Luulen haluat tämän ongelman. Haluat tätä monimutkaisuutta, ei lineaarinen koska kaikille teille tietää gonna hakuja jokainen yksittäinen neula, asia heinää, yrittää etsiä neulan. Ja joka ei ole liian hauskaa mielestäni. Pidän nopeasti. Pidän tehokas. Ja niin ahkera opiskelijaa kaverit ovat, tiedät työskennellä fiksummin, ei kovemmin tyyppinen asia, miten voi keksiä näitä algoritmeja. 

Joten, aiomme kävellä läpi vain nopea esimerkki. Mielestäni te pitäisi olla käsi binäärihaku, mutta jos joku on hieman sumea, haluamme vahvistaa sitä, aiomme vain mennä läpi esimerkki tästä. Joten etsimme jos array sisältää seitsemän. 

Joten ensimmäinen asia mitä teemme on katso keskellä, eikö? Ja myös aiot olla koodaus Binary Etsi vain toinen. Niin, se tulee olemaan hauskaa. Joten katsomme keskellä pieni taulukot 3. Onko 3 yhtä 7? Ei. Se on kuusi. Niin, on se alle tai suurempi kuin seitsemän? Alle. Kyllä. Mukava työ kaverit. Tunnen Pidän minun pitäisi karkkia koska en halua heittää sen ulos metriä. Se, mitä aion tehdä ensi viikolla. Se pitää teidät teräviä. 

Joten, me heittää pois, että alkupuoliskolla, eikö? se oli alle. me tiedämme, että kaiken siitä, että vasemmalla puolella tulee olemaan pienempi kuin mitä me todella etsivät. Joten, ei ole tarvetta kiinnittää siihen huomiota. Vain unohtaa sen. Joten, nyt katsomme meidän oikealla puolella, ja katsomme keskellä tuolla, ja nyt se on yhdeksän. Niin, 9 is-- --Everyone? Suurempi kuin mitä me olemme etsimässä, eikö? Joten, aiomme heittää pois kaiken oikealle. Niin. Nyt kaikki olemme jäljelle jää yksi. Niin voimme tarkistaa, on tämä yksi mitä etsimme? se on. Löysimme mitä halusimme. Joten olemme tehneet. Bilinear Hae. 

Ja jos huomaat, me oli seitsemän tuloa siellä. Se kesti vain meitä kuin kolme kertaa, mutta jos teet kuten miljardia, Tiedättekö kuinka monta askelta se olisi ota, jos meillä olisi neljän miljardin asioita? Arvauksia? Se on 32. 32 vaiheet löytää jotain vuonna neljän miljardin alkiotaulukon koska kahden potensseja. Joten kaksi on 32, on neljä miljardia euroa. 

Joten ihan hullu miten olet vielä sisällä kuten melko pieni määrä vaiheita löytää jotain neljän miljardin elementtejä. Niin Komitea suosittelee, että olemme menossa koodaamaan tämän joten te voi itse sellaista nähdä, miten tämä toimii. Okei, joten te voi koodata. Aion antaa te puhua vähän. Tutustua ihmisiin ympärilläsi, joka on mitä joku halusi viime jaksossa. 

Niin saat tietää ihmisiä ympärilläsi. Puhua vähän. Ja kaikki mitä haluan sinulta kaverit nyt on vain yrittää luoda ääriviivat pseudokoodin. OK? Vau. Haluan teiltä kaverit on olet juuri menossa täyttää tässä taas asiassa. Joten olen ottanut ne ylemmän ja alarajojen joka edustavat alussa ja lopussa meidän array. Ja aiot todella silmukan läpi ja selvittää mitä me teemme tämän, kun silmukka. 

Joten jos voit selvittää out-- Olen vihje there-- mitkä ovat tapausten että meillä on täällä? Joten jos haluat selvittää tapauksissa me pseudokoodina nämä ja sitten me itse koodata ne. Ja se tulee olemaan, minä ajatella, toivottavasti se tulee olla hieman helpompaa kuin odotit. Koska se ei ole niin paljon koodia, oikeastaan, mikä on todella hienoa. 

Mm-hm? 

Opiskelija: [kuulumaton]? Ohjaaja: Kyllä. Siellä oli jotain löytää keskellä. 

Opiskelija: Joten voimme käyttää sitä. OK. 

Ohjaaja: Perfect. Niin, että ensimmäinen asia, joka meidän täytyy tehdä. Niin löytää keskellä. Suuri. Joten sinulla on idea siitä, miten voisimme itse löytää keskellä koodilla? 

Opiskelija: Joo. n yli 2? Ohjaaja: Eli n yli 2. Niin yksi asia on muistaa, että ylempi ja alempi rajat muuttuvat. Pidämme constricting osa array etsimme. Joten n yli 2 toimii vain Ensimmäisen mitä teemme. Joten kun ylempi ja alempi huomioon, miten voisimme saada, että keski-elementti? Koska haluamme keskellä ylemmän ja alemman, eikö? Mm-hm? 

Opiskelija: [kuulumaton]. 

Ohjaaja: Eli meillä on keskellä. Ja se tulee olemaan ylä- ja alempi yli 2. Mahtava. Siellä mennään. Yksi rivi alaspäin. Te olette matkalla. Joten nyt meillä on keskimmäinen, mitä haluamme tehdä? Vain yleisesti. Sinun ei tarvitse koodata sitä. Kyllä. Opiskelija: [kuulumaton]? Ohjaaja: Joten se on plussaa, sillä olet löytää keskimäärin kahden niistä. Joten jos luulet niitä eräänlaisina lisätä sisään puolin, ajattele sitä, kun lähestyt keskimmäinen, jonka haluat niin. Joten jos olit kummallakin puolella keskimmäinen, ja meillä on, kuten 5 ja 7. Kun lisäät ne yhteen, saat 12, jaat 2, on 6. 

Joskus on vaikea miksi se toimii, mutta jos työn kautta Esimerkiksi joskus, se auttaa sinua selvittää, jos sen pitäisi olla plus tai miinus. Kyllä. 

Opiskelija: [kuulumaton] täsmälleen keskellä jos heillä oli tapaus, jossa siellä on paljon pienempi määrä ja kuten yksi suuri numero? 

Ohjaaja: Eli kaikki mitä tarvitset on ryhmän keskellä. Joten jos sinulla on ollut joukko pieniä numeroita ja sitten yksi todella suuri määrä lopussa, sillä ei ole väliä. Tärkeää on, että he lajiteltu, juuri halua katsoa keskellä array koska olet vielä viipalointi teidän ongelma puoli. Cool. Joten nyt meillä on keskellä, mitä teemme seuraavaksi? 

Opiskelija: Vertaa. Ohjaaja: vertaa. Joten vertailla keskeltä value_wanted. Cool. Niin näet täällä meillä Tämän arvon haluamme tänne. Muista tämä on jono. Niin keskellä viittaa indeksiin. Joten haluamme tehdä arvojen keskellä. Älä unohda, jos haluat vertailla, kaksinkertainen tasavertaisina. Teet yhden yhtä kuin olet juuri menossa luovuttamaan sen, ja sitten tietenkin, se on olemaan arvoa haluat. Joten älä tee sitä. 

Joten aiomme nähdä, jos arvojen keskellä on arvoa haluamme. Älä unohda henkselit. Dropbox pitäisi mennä pois. Joten mitä me teemme tässä tapauksessa? Jos se on mitä me haluamme palata? Yritämme sanoa. 

Opiskelija: Tulosta pois. 

Ohjaaja: No, me halua tulostaa. Joten tämä on bool täällä, niin me haluavat palata tosi tai epätosi. Sanomme, on tämä numero [? Rra? ?] Niin, jos se on, me vain palata totta. Jos voin kirjoittaa totta. 

Opiskelija: Miksi et palaa nolla? Ohjaaja: Joten voi palauttaa nolla jos halusi. Mutta tässä tapauksessa, koska meidän funktio palauttaa bool, Meidän täytyy palata joko tosi tai epätosi. Opiskelija: Kun olet sanoen Boolen lauseke, voit asettaa sen yhtä väärä? Kuten jos haluan sanoa, jos tämä ehto ei täyty, kuten on ylempi on yhtä väärä. Voiko se ymmärtää, jos vain laittaa vääriä toisella puolella? Ohjaaja: Joo. Joten itse asiassa, jos olet koskaan tehdä jotain kuten on ylempi tai alempi, joka palauttaa true tai false ja se on todella huono tyyli vaikkapa yhtä kuin yhtä kuin todellinen tai vertaistensa on yhtä väärä. Haluat käyttää tämän tuloksen niin itse check. Ei ollut mitä halusin. Se mitä halusin. Joten jos kyseessä kysyt noin jotain tallentaa C. 

Joten jos meillä on int main (void) ja jotain tällaista. Ja sinulla on, jos on ylempi Joidenkin tulo ja olet kysytään, voit tehdä jotain tällaista? Oikea? Opiskelija: Yritin tehdä sen [kuultavissa]. Koska jos it's-- Ohjaaja: Oikea. Joten haluat sen olevan väärä, oikea? Opiskelija: Joo. Ohjaaja: Joten tässä tapauksessa sinua haluavat sen toteuttaa, jos se ei ole totta. Niin cool juttu et siellä on tämä. Joten muistakaa huudahdus kohta tyhjäksi asioita? Se sanoo [kuultavissa] tarkoittaa ei. Joten jos tarkastelemme vain Tässä osa täällä, olisit sanovat, että antaa arvon väärä kuin haluat sen. Ei väärä on totta joka tarkoittaa tämä toteuttaa. Onko järkeä? Opiskelija: Joo. Ohjaaja: Awesome. OK. Joten voisimme vain palata paikkansa tässä tapauksessa. Joten nyt meillä on kaksi muuta tapauksissa tässä asiassa. Mitkä ovat kaksi muuta tapausta? Haluan vain tehdä se tällä tavalla. Joten aloittaa muu Jos arvot keskellä on pienempi kuin arvo haluamme. Joten meidän keskellä arvo on vähemmän kuin arvo, että etsimme. 

Joten joka sitoi sinä ajatella haluamme päivittää? Ylempi tai alempi? Ylä? Niin joka puolella array aiomme katsot? 

Opiskelija: alempi. 

Ohjaaja: Me olemme menossa olisi katsot vasemmalle. Joten muuta, jos pikku-arvo on pienempi. Joten keskimmäinen arvo täällä on pienempi kuin mitä me haluamme. Joten haluamme ottaa oikealla puolella meidän array. Joten aiomme Päivitämme alaraja. Niin me siirtää meidän pienempi. Ja mitä mieltä olette alempi pitäisi olla? Opiskelija: keskimmäinen arvo? Ohjaaja: Eli keskellä value-- Opiskelija: Plus 1. Ohjaaja: --plus 1. Voiko joku kertoa minulle, miksi meillä on tuo plus 1? 

Opiskelija: [? Mitään arvoa?] on yhtä suuri kuin se. 

Ohjaaja: Oikea. Koska me tiedämme jo, että Meidän keskimmäinen arvo ei ole yhtä kuin sen ja haluamme jättää sen kaikista myöhemmistä haut. Jos unohdat että plus 1, tässä toivomaa jatkua loputtomiin. Ja sinun vain takertua päättymättömään silmukkaan ja sitten sinun segfault ja asiat menevät huonosti. Joten varmista aina, että et ole myös arvo, jota juuri katsoin. Joten me huolehdimme, että plus 1. 

Joten nyt meillä on meidän viimeinen ehto joka olen aina varmuuden vuoksi voit tarkistaa täällä, muu, jos arvo keskellä on suurempi kuin arvo haluamme. Tämä tarkoittaa, että haluamme vasen puoli. Niin kumpi aiomme päivittää? Ylempi. Ja mikä on tämä yksi menossa tasa-arvoisia? Lähi miinus 1, koska Tietenkin me haluamme varmistaa, että emme ole katsomalla, että keskimmäinen arvo uudelleen. Ja sitten meillä on. Siinä kaikki. Siinä kaikki binäärihaku on. Se ei ole niin paha, eikö? Se on kuin 10 riviä koodia valkoinen tila. Niin hyvin voimakas, erittäin hyödyllinen, tulet olla käyttää sitä yhdessä teidän myöhemmin psets. Ehkä ei tämä yksi, mutta myöhemmin. Joten oppia se. Rakastan sitä. Se kohtelee sinua hyvin. Joten ei kellään mitään kysymyksiin Binäärihaku? Kyllä. 

Opiskelija: Onko sillä väliä onko n on parillinen tai pariton? 

Ohjaaja: Ei. Koska heitimme sen keskellä kuin int, se vain katkaista se. Joten se pysyy kokonaisluku ja se tulee lopulta lajitella läpi kaiken. Joten sinun ei tarvitse huolehtia siitä. Jokainen hyvä? Mahtava. Cool. Joten, te sai tämän. Diaesitys. Niin puhuimme, tiedän David mainittu monimutkaisuus runtimes. 

Joten parhaassa tapauksessa se on vain yksi, jota kutsumme vakioaikaisia. Voiko joku kertoa minulle, miksi se voisi olla? Minkälainen skenaario, joka merkitsee? Mm-hm. 

Opiskelija: [kuulumaton] first-- Ohjaaja: Eli keskellä on Ensimmäinen elementti, että me tulemme, eikö? Joten joko joukko yhden tai mitä etsimme juuri sattuu olemaan Smack DAB keskellä. Niin, että paras asia. Saat todellisia ongelmia, luultavasti ei menossa päästä [kuultavissa], että usein. Entä huonoin? Meidän pahin on log n. Ja että on tekemistä koko valtuuksia kaksi asia, että puhuin. 

Joten pahimmassa tapauksessa se tarkoittaisi että meidän piti pilkkoa array alas kunnes se oli osa yksi. Joten meidän piti pilkkoa se alas puoli niin monta kertaa kuin vain pystyimme. Siksi se on log n, koska kun vain jakamalla kahdella. Joten oletukset, mitä täytyy tietää, jos olet koskaan aio käyttää binäärihaku. Sinun osat on lajiteltava. Ne on lajiteltu, koska se on ainoa tapa voi tietää, jos pystyt heittää pois puolet siitä. 

Jos sinulla on ollut tämä sekaisin laukku numeroita ja sanot, OK, aion tarkistaa keskellä numero ja numeron Etsin on pienempi kuin, että olen juuri menossa mielivaltaisesti heittää pois puolet. Ette tiedä, jos numerot, että toinen puoli. Sinun luettelo on lajiteltu. Kuten hyvin, tämä voi olla menee eteenpäin hieman, mutta sinun täytyy olla random access. Sinun täytyy pystyä vain mene, että keskimmäinen osa. Jos joudut kulkemaan kautta jotain tai se vie ylimääräistä vaiheet päästä että keskimmäinen elementti, se ei ole log n enää, koska lisäät enemmän työtä siihen. Ja tämä tekee hieman järkevämpää kahden viikon, mutta olen juuri sellainen halusi esipuhe, antaa te käsitys siitä, mitä on tulla. Mutta nämä ovat kaksi tärkeimmät olettamukset että tarvitset binary luettelon. Varmista, että se on järjestetty. Se on suuri harppaus te juuri nyt. Ja että voimme mennä loput meidän tapaisena. Joten neljä sorts-- kupla, lisäys, valinta, ja yhdistää. Ne ovat kaikki eräänlainen jäähtyä. Jos te päätät ottaa CS 124, opit kaikenlaisia ​​tapaisena. Ja jos olet XKCD fani, siellä on todella viileä sarjakuva noin kuten todella tehoton lajittelee, jonka minä Suosittelemme sinua menossa katsomaan. Yksi heistä on kuin paniikki lajitella, joka on kuin, oh no, palata satunnainen joukko. Shutdown järjestelmä. Jätä. Joten Nörttihenkiset huumori on aina hyvä. 

Joten Muistaako kukaan sellaista samankaltaisten vain yleinen ajatus miten Kuplalajittelu toimii. Muistatko? 

Opiskelija: Joo. 

Ohjaaja: Tsemppiä. 

Opiskelija: Eli olet menossa läpi ja jos se on isompi, niin voit vaihtaa kaksi. 

Ohjaaja: Mm-hm. Täsmälleen. Joten sinun tarvitsee vain kerrata läpi. Voit tarkistaa kaksi numeroa. Jos yksi ennen on isompi kuin yksi jälkeenpäin, juuri vaihtaa niitä siten, että Tällä tavoin kaikki suuremmat numerot kupla ylös kohti listan loppuun ja kaikki pienemmät numerot kupla alas. 

Oliko hän näyttää te viileä ääniefektin lajittelu video? Se on eräänlainen jäähtyä. Niin Robert juuri sanoi, algoritmi että olet vain selata luetteloa, vaihtamalla vierekkäisten arvojen jos ne eivät ole kunnossa. Ja sitten vain toistavat kunnes et tee mitään swap. Joten ei paha, vai mitä? Joten meidän on vain nopea esimerkki tästä. Joten tämä tulee lajitella ne nousevassa järjestyksessä. Joten kun käymme läpi ensin aikaa, katsomme läpi kahdeksan ja kuusi eivät tietenkään ole jotta me vaihtaa niitä. 

Joten katso seuraava. Kahdeksan ja neljä ei järjestyksessä. Vaihtaa niitä. Ja sitten kahdeksan ja kaksi, vaihtaa niitä. Siellä mennään. Joten kun ensimmäinen pass, voit tietää, että eniten tulee olemaan aina yläosassa, koska se on vain olemaan jatkuvasti suurempi kuin kaikki muu ja se tekee vain kupla kaikki loppuun asti siellä. Onko se järkevää kaikille? Cool. 

Niin sitten katsomme meidän toinen pass. Kuusi ja neljä, kytkin. Kuusi ja kaksi, kytkin. Ja nyt meillä on muutamia asioita kuntoon. Joten jokaiselle, että me tehdä läpi koko listan, me tiedämme, että niin monta numeroa lopussa tulee on lajiteltu. Joten teemme kolmasosaa pass, joka on yksi swap. Ja sitten meidän neljäs pass, meillä on nolla lähtö. Ja niin me tiedämme, että meidän array on lajiteltu. 

Ja se on iso juttu Kuplalajittelu. Tiedämme, että kun me on nolla swap, että tarkoittaa sitä, että kaikki on täydellisessä järjestyksessä. Se on tavallaan kuinka tarkistamme. Joten olemme myös menossa koodaamaan kupla Lajittele joka myös ei ole niin paha. Mikään näistä ei niin paha. Tiedän, että ne voivat tuntua hieman pelottavalta. Tiedän, kun otin luokka, vaikka en opetti luokka ensimmäisen kerran viime vuonna, Olin ihan, miten voin tehdä tämän? On järkevää teoriassa, mutta Miten voimme itse tehdä tämän? Minkä takia haluan myös kävellä koodin avulla teidän kanssa täällä. Joten minulla on pseudokoodina sillä te tällä kertaa. Joten pitää tämä mielessä, kun aiomme siirtymisessä. Joten meillä on laskuri, joka pitää kirjaa meidän swap, koska meidän täytyy varmistaa, että me tarkistaa sitä. Ja me kerrata koko ryhmän kuten juuri teimme tässä esimerkissä. Jos elementti ennen on suurempi kuin elementin jälkeen, jossa me olemme, me vaihtaa niitä ja me kasvattaa meidän counter sillä heti kun me vaihtaa, haluamme antaa meidän laskuri tietää. Kysyttävää siellä? Jotain tuntuu hauska tänne. Opiskelija: Haluatko asettaa nollaksi joka kerta mennä läpi silmukan? Etkö jatka takaisin nollaan joka kerta? Ohjaaja: Ei välttämättä. Mitä tapahtuu, on käymme läpi täällä. Niin tehdä, kun, muistakaa, tämä tulee suorittaa kerran ilman epäonnistua. Joten se tulee asettaa laskurin nolla, sitten se tulee kerrata läpi. Koska se iteroi kautta, se päivittää laskuri. Koska se päivittää vasta, kun se on tehty, kun se on saavuttanut taulukon loppuun, Jos lista ei ole lajiteltu, Laskuri on päivitetty. 

Niin sitten se tarkistaa kunnossa ja se sanoo, OK, on ​​laskuri suurempi kuin nolla. Jos se on, tee se uudestaan. Haluatko palauttaa niin, että kun läpi, laskuri on nolla. Jos menet läpi lajitellun array, mikään ei muutu, tämä epäonnistuu, ja olet palata lajiteltu luettelo. Onko se järkevää? Opiskelija: Se saattaisi myös hieman. Ohjaaja: OK. Jos on olemassa muita kysymys, joka tulee esille. Kyllä. 

Opiskelija: Mikä olisi toiminto olla vaihtamalla osia? 

Ohjaaja: Voimme siis itse kirjoittaa että jos aiomme juuri nyt. Cool. Niin Komitea suosittelee, että Alison on menossa Vaihda takaisin laitteeseen. Se tulee olemaan hauskaa. Ja meillä on mukavaa Kuplalajittelu juttu täällä. Joten olen jo tehnyt pyöräily kautta array. Meillä swap ovat yhtä kuin nolla. Joten haluamme vaihtaa vieressä elementit, jos he ovat epäkunnossa. Joten ensimmäinen asia, joka meidän täytyy do on kerrata kautta array. 

Niin miten luulet voisimme kerrata kautta array? Meillä on ja minä yhtä kuin 0. Haluamme I olevan vähemmän kuin n miinus 1 miinus k. Niin selitän, että toinen. Joten tämä on optimointi täällä missä, Muistan kuinka sanoin välein syöttö kautta array me tietää, että mitä on on-- 

Joten yhden läpisyötön jälkeen me tietää, että tämä on lajiteltu. Kahden kulkee tiedämme että kaikki tämä on lajiteltu. Kolmen kulkee meillä tietää, että on lajiteltu. Joten miten olen iteroidessaan kautta array täällä, on se tekee varmasti vain mennä läpi mitä tiedämme on lajittelemattoman. OK? Se on vain optimointia. Voisit kirjoittaa se sinisilmäisesti vain iteroidessaan kaiken läpi, se vain kestää kauemmin. Tämän neljän silmukan se vain kiva optimointi koska tiedämme, että jokaisen täyden iterointi array täällä, kuten jokainen loop täällä, tiedämme että yksi näistä elementeistä ratkeaa lopussa. 

Joten meidän ei tarvitse huolehtia niistä. Onko se järkevää kaikille? Että viileä pikku temppu? Niin siinä tapauksessa, jos olemme iteroidessaan kautta, me tiedämme, että haluamme tarkistaa, onko array n ja n + 1 ovat kunnossa. OK. Joten tässä pseudokoodina. Haluamme tarkistaa, jos joukko n ja n + 1 ovat kunnossa. Mikä siis meillä on siellä? Se tulee olemaan noin ehdollinen. Se on, jos. 

Opiskelija: Jos array n on alle array n + 1. Ohjaaja: Mm-hm. No, vähemmän kuin tai suurempi kuin. Opiskelija: Suurempi kuin. Sitten haluamme vaihtaa niitä. Täsmälleen. Joten nyt saamme mitä mekanismi vaihtamalla niitä? Joten kävimme läpi tämän hetken, tyyppi swap toiminto viime viikolla. Muistaako kukaan, miten se toimi? Joten emme voi vain siirtää niitä, eikö? Koska yksi niistä eksy. Jos sanoimme vastaa B ja sitten B on yhtä suuri, kaikki yhtäkkiä molemmat ovat vain yhtä B. 

Joten mitä meidän täytyy tehdä, on meillä on väliaikainen muuttuja, joka on aikoo järjestää yhden omistamme taas olemme parhaillaan vaihtava. Eli meillä on meillä on joitakin int Lämpötila on yhtä to-- voit määrittää sen kumpi niistä haluamasi, vain Varmista, että pidät kirjaa it-- joten tässä tapauksessa, aion määrittää sen array n + 1. Niin että menee pitämään tahansa arvo on, että toinen lohko että me tarkastelemme. 

Ja sitten voimme tehdä on, että voimme mennä eteenpäin ja siirtää array n + 1, sillä me tiedämme, että meillä on, että arvo tallennetaan. Tämä on myös yksi iso things-- En tiedä, jos joku teistä oli kysymyksiä, joissa jos vaihdat kaksi riviä koodia yhtäkkiä asiat toimivat. Järjestys on erittäin tärkeää CS. Varmista siis kaavio asiat, jos mahdollista siitä, mitä todella tapahtuu. Joten nyt olemme menossa siirtää array n + 1, sillä me tiedämme, että meillä on, että arvo tallennetaan. 

Ja voimme antaa, että joukko n tai tässä tapauksessa array i. Liian monia muuttujia. OK. Joten nyt olemme virkamieskierrossa array i plus 1 suuruiseksi mitä array i. Ja nyt voimme mennä takaisin ja määrittää array i mitä? Kukaan? 

Opiskelija: 10. 

Ohjaaja: 10. Täsmälleen. Ja viimeinen asia. Jos olemme vaihtaneet sen nyt, Mitä meidän pitää tehdä? Mikä yksi asia että menee kertomaan meille Jos joskus lopettaa tämän ohjelman? Mikä kertoo meille, että me on lajiteltu lista? Jos emme tee mitään swap, eikö? Jos swap on yhtä kuin nolla lopussa. Joten kun teet swap, koska me vain teimme täällä, haluamme päivittää swap. Ja tiedän siellä oli kysymys aiemmin siitä voitte käyttää nolla tai yksi sen sijaan tosi tai epätosi. Ja sitähän tämä tekee täällä. Joten tämä sanoo, että jos ei swap. Joten jos swap on nolla, mikä is-- olen aina saan totuuksia ja minun falses sekaisin. Haluamme voimme arvioida totta ja se ei ole. Joten jos se on nolla, niin se on väärä. Jos estäisi sen kanssa [? bang?] siitä tulee totta. Niin sitten tämä linja suorittaa. 

Totuuksia ja vääriä ja nollia ja ykkösiä saada hullu. Vain jos hitaasti kävellä kautta se on järkevää. Mutta sitähän tämä pieni vähän koodia täällä tekee. Joten tämä tarkistaa, olemme tehneet mitään swap. Joten jos se on mitään lisäksi nolla, se tulee olemaan vääriä ja koko juttu on menossa suorittaa uudelleen. Cool? 

Opiskelija: Mitä tauko tekee? 

Ohjaaja: Tauko juuri taukoja sinua ulos silmukan. Joten tässä tapauksessa olisi vain haluavat lopettaa ohjelman ja olisit juuri pyydä lajiteltu luettelo. Opiskelija: Amazing. Ohjaaja: Olen pahoillani? Opiskelija: Koska aikaisemmin olemme käytetty kirjallisuutta 1 yli kirjoitettu nolla esittää, että jos joka toimii tai ei. 

Ohjaaja: Joo. Joten voit palata nolla tai 1. Tässä tapauksessa, koska emme ole oikeastaan tehdä mitään toimintoa, me vain haluamme sen murtaa. Emme oikeastaan ​​välitä siitä. Jarru on myös hyvä, jos sitä käytetään puhkeamassa neljä silmukoita tai ehtoja, jotka et halua säilyttää täytäntöönpanosta. Se vain vie pois niistä. Se on hieman vivahde asia. Tunnen siellä paljon käsi heiluttaa, kuten opit tästä pian. 

Mutta opit tästä pian. Lupaan. OK. Joten ei kaikki saavat Kuplalajittelu? Ei liian huono. Kerrata läpi, swap asioita käyttäen temp muuttuja, ja me kaikki asettaa siellä? Cool. Mahtava. OK. Takaisin PowerPoint. Kaikki kysymykset yleensä näistä tähän mennessä? Cool. Mm-hm. 

Opiskelija: [kuulumaton] int main yleensä. Onko sinulla olla, että tähän? 

Ohjaaja: Eli olimme vain etsimässä juuri todellinen lajittelu algoritmi. Jos sinulla oli se sisällä kuten suurempaa ohjelmaa, olisit int main jonnekin. Riippuen siitä, missä olet käyttää tätä algoritmia, se määrittää, mitä palautetaan sen. Mutta meidän tapauksessa olemme tiukasti katsomalla miten tämä todellisuudessa kerrata läpi array. Joten emme välitä siitä. 

Joten puhuimme parhaassa tapauksessa ja Pahimmassa tapauksessa skenaarioita binäärihaku. Joten se on myös tärkeää tehdä että jokaisen meidän tapaisena. Joten mitä luulet on pahin kyseessä runtime Kuplalajittelu? Te muistaa? 

Opiskelija: N miinus 1. Ohjaaja: N miinus 1. Niin se tarkoittaa, on olemassa n miinus 1 vertailuja. Niin yksi asia on ymmärrettävä, että ensimmäistä iterointia, käymme läpi, vertaamme Näiden two-- niin se on 1. Nämä kaksi, kolme, neljä. Joten yhden iteraation me jo neljä vertailuja. Kun puhun runtime ja n. N edustaa vertailujen lukumäärä funktiona kuinka monta elementtiä meillä. OK? 

Joten käymme läpi, meillä on neljä. Seuraavan kerran, kun tiedämme, että meillä ei täytyy huolehtia tästä. Me vertailua, Näiden kahden, nämä kaksi, ja jos meillä ei ole, että optimointi neljän silmukan, että olen kirjoittanut, sinun olisi vertaamalla täällä anyways. Joten sinulla olisi läpi array ja tekemään n vertailua n kertaa, koska joka kerta kun sen läpi Lajittelemme yksi asia. 

Ja joka kerta käymme läpi array, teemme n vertailuja. Joten meidän runtime tähän on oikeastaan ​​n potenssiin, joka on paljon pahempi meidän log end koska tarkoittaa, että jos meillä oli neljä miljardia elementtejä, se on vie meidät neljään miljardiin potenssiin sijasta 32. Joten ei paras runtime, mutta joitakin asioita, tiedät, jos olet sisällä tiettyjen elementtien alueen Kuplalajittelu voi olla hieno käyttää. 

OK. Mitä nyt on paras asia runtime? Opiskelija: Zero? Tai 1? 

Ohjaaja: So 1 olisi yksi vertailu. Oikea. 

Opiskelija: N miinus 1? 

Ohjaaja: Niin, joo. Joten n miinus 1. Aina kun on käsite, kuten n miinus 1, meillä on tapana vain pudottaa sen pois ja me vain sanoa n, koska olet vertaamaan kunkin these-- kunkin parin. Niin se olisi n miinus 1, jota olimme vain sanoa on noin n. Kun olet tekemisissä runtime, kaikki on lähentää. Niin kauan kuin eksponentti on oikea, olet aika hyvä. 

Näin me käsitellä sitä. Niin että parhaassa tapauksessa on n, joka tarkoittaa sitä, että luettelo on jo järjestetty, ja kaikki mitä teemme on ajaa läpi ja tarkista, että se on järjestetty. Cool. Selvä. Joten kuten näette täällä, me vain hieman enemmän kuvaajia. Niin n potenssiin. Hauskaa. Paljon huonommin kuin N, kun näemme, ja paljon, paljon pahempi kuin log 2n. Ja sitten myös päästä loki lokit. Ja otat 124, joudut kuten log tähti, joka on kuin hullu. Joten jos olet kiinnostunut, lookup log tähti. Se on tavallaan hauskaa. Joten meillä on tämä loistava kaavio. Vain heads up, tämä ihana kaavio on oman puolivälin koska me pitkään kysyä näitä ohenee. Joten vain heads up, on tämä teidän puolivälin teidän kiva lunttilappua siellä. Joten me vain katsoi Kuplalajittelu. Pahimmassa tapauksessa n potenssiin, parhaassa tapauksessa n. Ja olemme menossa katsomaan muita. 

Ja kuten näette, vain joka todella hyvin on Lomituslajittelu, joka Pääsemme miksi. Joten aiomme mennä seuraava here-- valinta lajitella. Muistaako kukaan, miten valinta lajitella toiminut? Tsemppiä. 

Opiskelija: periaatteessa mennä läpi järjestystä ja luoda uuden listan. Ja aivan kuten olet laskemisesta osia vuonna, laita ne oikeaan paikkaan uudessa luettelossa. 

Ohjaaja: jotta äänet enemmän kuin lisäyslajittelu. Mutta olet todella lähellä. Ne ovat hyvin samankaltaisia. Vaikka saan ne sekaisin joskus. Ennen tätä jaksoa olin kuin, odota. OK. Joten mitä haluat tehdä, on valinta lajitella, miten voit ajatella siitä ja miten Varmistan En yritä päästä niitä sekaisin, on se menee läpi ja se valitsee Pienin määrä ja sen tuo, että alussa listasi. Se swap sen kanssa, että ensin paikalla. He todella ovat esimerkkinä minulle. Mahtava. Joten vain tapa ajatella it-- valinta Lajittele, valitse pienin arvo. Ja aiomme ajaa läpi esimerkki mielestäni auttaa, koska Mielestäni grafiikka aina auttaa. Joten aloitamme jotain että on täysin lajittelemattomia. Punainen on lajittelemattoman, vihreä lajitellaan. Se kaikki on selvää toisessa. 

Joten käymme läpi, ja me kerrata alusta loppuun. Ja me sanomme, OK, 2 meidän pienin numero. Niin me otamme 2 ja aiomme siirtää sen edessä meidän array koska se on Vähiten meillä. Niin, että mitä tämä tekee täällä. Se on juuri menossa vaihtaa nämä kaksi. Joten nyt meillä on lajiteltu osa ja lajittelemattoman osa. Ja mikä on hyvä muistaa Tietoja valinta Lajittele on me vain valitsemalla alkaen lajittelemattomat osa. 

Lajitellut osa vain jättää yksin. Mm-hm? 

Opiskelija: Miten se tietää, mitä on pienin vertaamatta sitä joka toinen arvo array. Ohjaaja: Se verrata sitä. Pidämme ohitetaan se. Tämä on vain yleinen yleinen. Joo. Kun me kirjoittaa koodia olen varma, että voit olla tyytyväinen. Mutta tallentaa tämän ensimmäisen elementti kuin pienin. Vertaa ja sinä sanovat, OK, on ​​se pienempi? Kyllä. Pidä se. Tässä on se pienempi? Ei? 

Tämä on pienin, luovuttamaan sen omaan arvoon. Ja voit olla paljon onnellisempi kun käymme läpi koodin. Joten käymme läpi, me vaihtaa sitä, niin sitten tarkastelemme tätä lajittelemattoman osaan. Joten aiomme valita kolme. Aiomme laittaa sen päälle Lopussa meidän lajitellut osan. Ja me vain aio pitää tehdä että tee sitä, ja näin. Joten tämä on meidän kaltaisemme pseudokoodin täällä. Me koodi sen tänne toista. Mutta vain jotain kävellä läpi korkealla tasolla. Aiot mennä i on yhtä kuin 0 n miinus 2. Se on toinen optimointi. Älä huolehdi liikaa siitä. Niin sanoitte. Kuten Jaakob sanoi, miten me seurata, mitä meidän pienin on? Mistä tiedämme? Meidän täytyy vertailla kaikki listallamme. 

Niin vähintään yhtä suuri kuin minä. Se on vain sanonta tässä tapauksessa indeksi meidän pienin arvo. Niin sitten se tulee kerrata läpi ja se menee j on yhtä kuin i + 1. Joten me jo tiedämme, että se on meidän ensimmäinen elementti. Emme tarvitse verrata sitä itse. Joten alamme vertaamalla sitä seuraava yksi minkä vuoksi se on i ja 1-n miinus 1, joka on taulukon loppuun siellä. Ja me sanoimme jos array j on pienempi kuin array min, sitten siirtää missä Meidän pienin indeksit. 

Ja jos min ei ole yhtä kuin minä, koska kaupungissa, jossa olimme takaisin tänne. Niin kuin kun ensin teki tämä yksi. Tässä tapauksessa se alkaisi nolla, se lopulta kaksi. Joten min eikö yhdenvertaisen i lopussa. Tämä kertoo meille, että meidän täytyy vaihtaa niitä. Tunnen konkreettinen esimerkki auttaa paljon enemmän kuin tämä. Niin minä koodata tämän kanssa te juuri nyt ja mielestäni se tulee olemaan parempi. 

Lajittelee yleensä toimi sillä tavalla, että se on usein parempi vain nähdä niitä. Joten mitä me haluamme tehdä, on haluamme ensin pienin elementti asemaansa array. Mitä Jaakob sanoi. Sinun täytyy tallentaa se jotenkin. Joten aiomme aloittaa tästä iteroidessaan rivin yli. Aiomme sanoa se on meidän Ensimmäinen vain aloittaa. Joten aiomme olla int Pienin on yhtä array i. 

Niin yksi asia huomata, joka kun tämä silmukka suorittaa, Aloitamme askeleen kauempana. Kun aloitamme katsomme tämän yhden. Seuraavan kerran me kerrata läpi, me aloitamme tällä yhdellä ja osoittaa se meidän pienin arvo. Joten se on hyvin samankaltainen Kuplalajittelu jos me tiedämme, että kun yksi pass, tämä viimeinen elementti on lajiteltu. Valinnalla lajitella, se on juuri päinvastoin. 

Joka pass, me tiedämme, että ensimmäinen lajitellaan. Toisen pass, toinen ratkeaa. Ja kuten näit kanssa dia esimerkkejä, Meidän lajiteltu osa vain kasvaa. Niin asettamalla meidän pienin ja taulukot I, kaikki se tekee on rajoittavaa, mitä etsimme niin minimoida vertailuja teemme. Onko järkeä kaikille? Tarvitaanko minua juoksemaan läpi taas hitaammin tai eri sanoin? Olen onnellinen. OK. 

Joten olemme tallentamiseen arvo tässä vaiheessa, mutta haluamme myös säilyttää indeksiin. Joten aiomme säilyttää asema pienimmän yksi, joka on juuri menossa olevan i. Joten nyt Jaakob on tyytyväinen. Meillä on asiat tallennetaan. Ja nyt meidän täytyy katsoa läpi lajittelemattomat matriisin osan. Joten tässä tapauksessa tämä olisi meidän lajittelemattomat. Tämä on i. OK. 

Joten mitä me aiomme tehdä tulee olemaan varten silmukka. Kun haluat kerrata läpi array, mielesi voisi mennä varten silmukka. Joten joidenkin int k equals-- mitä ajattelemme K on menossa sama aloittaa? Tämä on mitä me asettaneet pienimmän arvo ja haluamme verrata sitä. Mitä haluamme verrata sitä? Se tulee olemaan tämä seuraava, eikö? Joten haluamme k alustettavaksi ja i + 1 aloittaa. 

Ja haluamme k tässä tapauksessa me jo koko tallennettu tänne, joten voimme vain käyttää kokoa. Koko on taulukon koko. Ja me vain haluamme päivittää k yhdellä joka kerta. Cool. Nyt meidän täytyy löytää pienimmän alkion täällä. Joten jos me kerrata läpi, me haluan sanoa, jos array K on pienempi kuin meidän pienin value-- tämä on, jos olemme todella pitää kirjaa siitä, mitä on pienin here-- Sitten haluamme siirtää mitä meidän pienin arvo on. 

Tämä tarkoittaa, että oi, olemme iteroidessaan kautta täällä. Mikä tahansa arvo on tässä ei meidän pienin juttu. Emme halua sitä. Haluamme siirtää sitä. Joten jos me uudelleen kohdentamisesta se, mitä tehdä luulet voisi olla tässä koodi täällä? Haluamme siirtää Pienin sijaintia. Niin mikä on pienin nyt? Opiskelija: Array k. Ohjaaja: Array k. Ja mikä on nyt tilanteemme? Mikä indeksit meidän pienin arvo? Se on vain k. Niin joukko K, K, ne vastaavat. Joten halusimme siirtää sitä. Ja sitten kun löysimme meidän pienin, niin lopussa tämä silmukka täällä olemme löytäneet mitä meidän pienin arvo on, niin me vain vaihtaa sitä. Tässä tapauksessa, kuten sanovat meidän Pienin arvo on täällä. Tämä on pienin arvo. 

Haluamme vain vaihtaa sitä täällä, joka on mitä se swap toiminto alareunassa teki, jonka me vain kirjoitti ylös yhdessä pari minuuttia sitten. Joten sen pitäisi näyttää tutulta. Ja sitten se vain kerrata läpi, kunnes se saavuttaa koko matkan loppuun, mikä tarkoittaa sitä, että on nolla elementtejä, jotka ovat lajittelemattomia ja kaikki muu on lajiteltu. Järkeä? Hieman konkreettisemmin? Apua? 

Opiskelija: n koon, et koskaan todella määritellä se tai muuttaa sitä, miten se tietää? 

Ohjaaja: Eli yksi asia huomaa täällä on int koko. Niin sanomme tässä sort-- Lajittele on funktio tässä case-- se valinta lajitella, se on läpäissyt in toiminnolla. Joten jos se ei mennyt läpi kaupungissa, tekisit jotain kuten pituuden kanssa array tai voit kerrata läpi löytää pituutta. Mutta koska se on läpäissyt vuonna, voimme vain käyttää sitä. Sinä vain olettaa, että käyttäjä antoi sinulle voimassa koko, joka todellisuudessa merkitsee kokoa array. Cool? 

Jos teillä on ongelmia näillä tai haluavat enemmän käytännön koodaus lajittelee oman, sinun pitäisi Siirry study.cs50. Se on työkalu. Heillä tarkistin että voit itse kirjoittaa. He tekevät pseudokoodilla. Heillä on enemmän videoita ja dioja mukaan lukien ne, käytän täällä. Joten jos olet vielä tunne hieman sumea, kokeile että ulos. Kuten aina, tule puhumaan minulle, liian. Kysymys? 

Opiskelija: Sanotko koko on aikaisemmin määritelty? Ohjaaja: Kyllä. Koko on aikaisemmin määritelty ylös täällä toiminto ilmoituksen. Niin oletat, että se on ohitettu käyttäjä, ja yksinkertaisuuden vuoksi, aiomme olettaa, että Käyttäjä antoi meille oikean koon. Cool. Niin, että valinta lajitella. Kaverit, tiedän olemme oppimisen paljon tänään. Se on tiheä tietoja osiosta. Niin, että aiomme mennä lisäyslajittelu. 

OK. Joten sitä ennen meidän on tehtävä Meidän runtime analyysi täällä. Joten parhaassa tapauksessa, alkaen myönnetyt Näytin taulukossa I jo Tällainen antoi sen pois. Mutta parhaassa tapauksessa runtime, mitä ajattelemme? Kaikki lajiteltu. N potenssiin. Kellään selitystä miksi luulet? 

Opiskelija: olet verrataan through-- Ohjaaja: Oikea. Olet verrataan kautta. Joka iteraatio, vaikka me pienentämällä tämä yksi, olet vielä hakuja kaikki löytää pienin. Joten vaikka pienin arvo on tässä alussa, olet vielä vertaamalla sitä vastaan ​​kaikki muu varmista, että se on pienin asia. Joten voit päätyä kulkee noin n potenssiin kertaa. Selvä. Ja mitä pahimmassa tapauksessa? Myös n potenssiin, koska olet menossa olla tekemässä, että samaa menettelyä. Joten tässä tapauksessa valinta Lajittele on jotain että me vaadimme odotettavissa runtime. Joten muut, me vain tiedämme ylä- ja alarajoja. Riippuen siitä, kuinka hullu meidän lista on tai kuinka lajittelemattoman se on, ne vaihtelevat välillä n tai n potenssiin. Emme tiedä. 

Mutta koska valinta lajitella on sama parhaan ja huonoimman tapauksen, joka kertoo meille, että Ei ole väliä, millainen panos me on, onko se kokonaan lajiteltu tai kokonaan kääntää lajiteltu, se on vie saman verran aikaa. Niin siinä tapauksessa, jos Muistan meidän pöytä, se todella oli arvo, Näiden kahden lajittelee ei ole, jonka odotetaan runtime. Joten me tiedämme, että aina me juoksemme valinta lajitella, se on taattu ajaa n potenssiin aikaa. Ei ole mitään vaihtelua siellä. Se on vain odotettavissa. Ja taas, jos haluat oppia enemmän, ota CS 124 keväällä. Selvä. Olemme nähneet tämän. Cool. Niin lisäyslajittelu. Ja olen luultavasti menossa blaze kautta. En ole teitä koodi sen. Me vain kävellä sen läpi. Joten lisäyslajittelu on eräänlainen on samanlainen valinta Lajittele että meillä on sekä lajittelemattoman ja lajitellaan osa array. 

Mutta mikä on erilaista on se, että kun käymme läpi yksi kerrallaan, me vain ottaa mitä numero on seuraava meidän lajittelemattoman, ja oikein lajitella meidän lajitellut array. Se tulee järkevämpää esimerkin. Niin kaikki alkaa lajittelemattoman, Aivan kuten valinta lajitella. Ja aiomme järjestää tämän nousevassa järjestyksessä kuin olemme. Joten meidän ensimmäinen syöttö otamme ensimmäisen arvon ja sanomme, OK, olet nyt listan itse. 

Koska olet luettelossa itse, olet lajitellaan. Onnittelut siitä, että Ensimmäinen osa tätä array. Olet jo lajiteltu kaikki itse. Joten nyt meillä on lajiteltu ja lajittelemattoman array. Joten nyt otamme ensin. Mitä tapahtuu välillä täällä Ja tässä on se, että sanomme, OK, olemme menossa katsomaan Ensimmäinen arvo meidän lajittelemattoman array ja aiomme syöttää sitä sen oikea paikka lajitellut array. 

Joten mitä me teemme on otamme 5 ja sanomme, OK, 5 on suurempi kuin 3, joten me vain lisätä se oikea oikealle että. Olemme hyviä. Niin sitten mennään eteenpäin meidän seuraavaan. Ja otamme 2. Sanomme, OK, 2 on vähemmän kuin 3, niin me tiedämme, että se on oltava edessä meidän lista nyt. Joten mitä teemme on meidän työntää 3 ja 5 alas ja siirrymme 2 tuohon ensimmäiseen korttipaikkaan. Joten me vain työntämällä se oikea paikka olisi. 

Sitten katsomme meidän seuraava, ja sanomme 6. OK, 6 on suurempi kuin kaikki meidän lajiteltua array, joten me vain merkitä sen loppuun. Ja sitten katsomme 4. 4 on alle 6, se on vähemmän kuin 5, mutta se on enemmän kuin 3. Joten me vain työnnä se keskellä välillä 3 ja 5. Niin tehdä, että vähän vähän konkreettisempia, tässä eräänlainen käsitys siitä, mitä tapahtui. Joten jokaisen lajittelemattoman elementti, me määrittää missä lajitellut osan se on. 

Niin pitää mielessä lajitellaan ja lajittelemattomat, meidän täytyy kulkea läpi ja kuva missä se sopii lajitellut array. Ja me aseta se siirtämällä elementit oikealle alas. Ja sitten me vain pitää iteroimalla läpi kunnes me on täysin lajiteltu lista jossa lajittelemattomat on nyt nolla ja lajitellaan vie kokonaisuudessaan listallamme. Joten, jälleen, tehdä asioita vielä konkreettisempia, meillä pseudokoodit. 

Joten pohjimmiltaan i on yhtä kuin 0-n miinus 1, se on vain pituus meidän array. Meillä on joitakin elementti, joka on yhtä kuin ensimmäinen array tai ensimmäinen indeksit. Asetimme j yhtä suuri. Joten vaikka j on suurempi kuin nolla ja array, j miinus 1 on suurempi kuin elementti, niin kaikki mitä teemme on varmistaa, että sinun j edustaa oikeastaan lajittelemattomat osa array. 

Joten kun vielä on asioita lajitella ja j miinus yksi is-- mitä on osa hänen? J ei koskaan määritelty tässä. Se on tavallaan ärsyttävää. OK. Anyways. Niin j miinus 1, olet tarkkailun elementti ennen sitä. Sanot, OK, on ​​elementti ennen kun sillä am-- katsotaanpa todella vetää tämän pois. Joten sanokaamme tämä on kuten meidän toisella kierroksella. Joten en tulee olla yhtä suuri 1, joka on tässä. 

Joten i tulee olemaan yhtä suuri kuin 1. Tämä olisi 2, 4, 5, 6, 7. Selvä. Joten meidän elementti tässä tapauksessa tulee olemaan sama kuin 4. Ja meillä on joitakin j, joka on olemaan yhtä kuin 1. Voi j pienentämällä. Sitähän se on. Joten J on yhtä i, niin mitä tämä on sanonta on, että kun menemme eteenpäin, me vain varmistaa, että emme ole ohi indeksointi tällä tavalla, kun yritämme lisätä asioita meidän lajiteltu luettelo. 

Joten kun j = 1. Tässä tapauksessa ja array j miinus one-- niin array j miinus 1 on 2 tässä case-- jos se suurempi kuin elementin, niin kaikki tämä tekee on siirtymässä asioita alas. Joten tässä tapauksessa, array j miinus yksi olisi array nolla, mikä on 2. 2 ei ole suurempi kuin 4, joten tämä ei suorita. Joten muutos ei liiku alas. Mitä tämä tekee tässä vain liikuttamalla lajitellut array alas. Tässä tapauksessa, itse asiassa, me voisi do-- Tehdään tästä 3. Joten jos olemme kulkea kanssa Tässä esimerkissä olemme nyt täällä. Tämä on lajiteltu. Tämä on lajittelemattomat. Cool? Joten i on yhtä suuri kuin 2, niin Meidän elementti on yhtä kuin 3. Ja meidän j on 2. Joten katsomme läpi ja me sanovat, OK, on ​​joukko j miinus yksi suurempi kuin elementin että me tarkastelemme? Ja vastaus on kyllä, eikö? 4 on suurempi kuin 3 ja j on 2, joten tämä koodi suorittaa. 

Mitä nyt teemme array 2, niin täällä, me vaihtaa niitä. Joten me vain sanoa, OK, array 2 on nyt menossa on 3. Ja j on menossa sama j miinus 1, joka on 1. Se on kamala, mutta te saada idea. J on nyt yhtä suuri kuin 1. Ja joukko J on juuri menossa olevan yhtä elementtimme, mikä oli 4. Olen poistetaan jotain minun ei pitäisi on tai miswrote jotain, mutta te saada idea. 

Se liikkua n. Ja sitten, jos tämä olisi, se silmukka uudelleen ja se sanoisi, OK, j on 1 nyt. Ja joukko j miinus 1 on nyt 2. On 2 vähemmän kuin meidän elementti? Ei? Tämä tarkoittaa, että olemme Lisätään tämä elementti oikeaan kohtaan meidän lajitellun array. Sitten voimme ottaa tämän ja sanomme, OK, meidän lajitellun array on täällä. Ja se veisi tämän numeron 6 ja olla kuten, OK, on ​​6 alle tämän numeron? Ei? Cool. Olemme kunnossa. 

Tee se uudestaan. Sanomme 7. On 7 vähemmän kuin lopussa meidän lajitellut array? Ei. Joten olemme kunnossa. Joten tämä olisi järjestetty. Periaatteessa kaikki tämä tekee on se sanoo take Ensimmäinen osa teidän lajittelemattomat array, selvittää, missä se menee oman lajitellut array. Ja tämä vain huolehtii swap tehdä. Olet pohjimmiltaan vain vaihtamalla kunnes se on oikealla paikalla. Visuaalinen ilme on että olet liikkuvat kaiken alas tekemällä niin. 

Joten se on kuin puoli Kuplalajittelu-herra. Tutustu tutkimuksessa 50. Olen erittäin suositella yrittää koodata tämän itse. Jos sinulla on kysymyksiä tai haluat Katso näyte koodi lisäyslajittelu, kerro minulle. Olen aina noin. Joten pahimmassa tapauksessa runtime ja parhaassa tapauksessa runtime. Kun kaveri näki pöydästä olen jo osoitti teille, se on sekä n potenssiin ja n. 

Joten tavallaan menossa pois, mitä puhuimme Tietoja meidän edellinen lajittelee, pahin tapauksessa runtime on, että jos se on täysin Lajittelemattomat meidän täytyy verrata kaikkia näitä n kertaa. Teemme paljon vertailuja koska jos se on käänteisessä järjestyksessä, aiomme sanoa, OK, tämä on sama, tämä on hyvä, ja tämä yksi on verrattava vastaan ​​ensimmäinen siirrettävä takaisin. Ja kun saamme kohti loppupää, meillä on vertailla, vertailla ja vertautuvat kaiken. 

Joten se päätyy noin n potenssiin. Jos se on oikein niin olet sanovat, OK, 2, olet hyvä. 3, olet verrattuna 2. Olet hyvä. 4, juuri verrata häntä. Olet hyvä. 6, verrata häntä, olet hieno. Joten jokaiselle paikalla, jos se on jo lajiteltu, teet yhden vertailun. Joten se on vain n. Ja koska meillä on parhaassa tapauksessa runtime n: n ja pahimmassa tapauksessa käyntiaika n potenssiin, meillä ei ole odotettavissa runtime. 

Se vain riippuu siitä, kaaos lista siellä. Ja vielä toinen kuvaaja ja toinen pöytä. Joten erot tapaisena. Olen juuri menossa tuulta läpi, minä tuntuu olemme puhuneet laajasti siitä, miten he kaikenlaisia sekä vaihtelevat ja linkitetään yhteen. Joten Lomituslajittelu on viimeinen Aion pitkästyttää teitä kanssa. Meillä on melko värikäs kuva. Joten Lomituslajittelu on rekursiivinen algoritmi. Joten Tiedättekö mitä rekursiivinen funktio on? 

Joku haluaa sanoa? Haluatko kokeilla? Joten rekursiivinen funktio on vain funktio, joka kutsuu itseään. Joten jos te olette tuttuja kanssa Fibonaccin, joka on katsottu rekursiivinen koska otat kahden edellisen ja lisää ne yhdessä saada seuraavaan. Joten rekursiivinen, ajattelen aina ja rekursio samankaltaisina spiraali niin olet kuin kuolinkierteeseen siihen. Mutta se on vain toiminto joka kutsuu itseään. 

Ja todella, todella nopeasti I voi näyttää mitä se näyttää. Joten rekursiivinen täällä, jos katsomme, tämä on rekursiivinen tapa esittää yli array. Niin kaikki mitä teemme on meillä on summa toiminto summa, joka vie koko ja array. Ja jos huomaat, koko pienenee yhdellä joka kerta. Ja kaikki se on, jos x on yhtä suuri kuin zero-- joten jos taulukon koko on yhtä suuri kuin zero-- se palaa nolla. 

Muuten se kiteyttää tämän viime alkiota, ja sitten otetaan summa loput array. Niin se vain murtaa se alas pienempiin ja pienempiin ongelmiin. Pitkä tarina lyhyt, rekursio, funktio, joka kutsuu itseään. Jos se kaikki mitä sinulla ulos tästä, niinhän rekursiivinen funktio on. Jos otat 51, saat hyvin, erittäin mukava rekursio. Se on todella siistiä. Se oli järkevää Like 3 AM yhden yön pois. Ja olin kuin, miksi olen koskaan käytä tätä? 

Joten Lomituslajittelu, pohjimmiltaan mitä se aikoo tehdä, on se aio rikkoa sen alas ja rikkoa sitä alaspäin, kunnes se on vain yhden elementtejä. Yksittäinen elementit ovat helppo lajitella. Näemme, että. Jos sinulla on yksi elementti, se on jo harkinnut lajitellaan. Joten tuloon n elementtejä, jos n on pienempi kuin 2, vain palata, koska se tarkoittaa se on joko 0 tai 1, kuten olemme nähneet. Nämä katsotaan lajiteltua elementtejä. 

Muuten rikkoa se kahtia. Lajitella alkupuoliskolla, järjestää toinen puoli, ja sitten yhdistää ne yhteen. Miksi sitä kutsutaan Lomituslajittelu. Joten meillä on täällä me järjestellä näitä. Joten pidämme ottaa heidät kunnes jonon pituus on 1. Joten kun se on 1, me vain palata koska tämä on lajiteltua array, ja tämä on lajitellun array, ja se on Lajittele array, me kaikki lajiteltu. Joten mitä sitten teemme, on meillä alkaa sulautuvat ne yhteen. 

Joten miten voit ajatella yhdistäminen on voit vain poistaa pienempiä määrä kunkin osa paneelit ja vain liittää se syntyi jono. Joten jos katsot täällä, kun meillä on Näiden sarjaa meillä on 4, 6, ja 1. Kun haluamme yhdistää nämä, katsomme näiden kahden ensimmäisen ja sanomme, OK, 1 on pienempi, se menee eteen. 4 ja 6, ei ole mitään verrata se vain merkitä sitä loppuun. 

Kun yhdistämme nämä kaksi, me vain ottaa pienempi näistä kahdesta, joten se on 1. Ja nyt otamme pienempi näistä kahdesta, niin 2. Pienempi näistä kahdesta, 3. Pienempi näistä kahdesta, 4, 5, 6. Joten olet vain vetämällä pois nämä. Ja koska he ovat on lajiteltu aiemmin, sinulla on vain yksi Vertailun joka kerta siellä. Joten enemmän koodia tässä, juuri edustus. Joten aloitat keskeltä ja voit lajitella vasen ja oikea ja sitten vain yhdistää ne. 

Ja meillä ei ole koodia varten yhdistää täällä. Mutta jälleen kerran, jos menet opiskella 50, se on siellä. Muuten tulla juttelemaan Jos olet edelleen sekava. Niin cool juttu tässä on, että parhaassa tapauksessa Pahimmassa tapauksessa, ja odotettavissa runtime ovat kaikki log n, joka on paljon parempi kuin me olet nähneet loput meidän tapaisena. Olemme nähneet n potenssiin ja mitä me oikeastaan tänne on n log n, joka on suuri. 

Katsokaa kuinka paljon parempi se on. Tällainen kiva käyrä. Niin paljon tehokkaampaa. Jos joskus voi käyttää Lomituslajittelu. Se säästää aikaa. Sitten taas, kuten sanoimme, jos olet alas tässä ala-alueella, se ei tee, että paljon eroa. Saat jopa tuhansia ja tuhansia panoksia, et varmasti halua tehokkaampi algoritmi. Ja taas, meidän ihana pöytä kaikista lajittelee, että te oppinut tänään. 

Joten tiedän, että se on ollut tiivis päivä. Tämä ei välttämättä mene auttaa sinua PSET. Mutta en vain halua tehdä vastuuvapauslauseke että osa ei ole vain psets. Kaikki tämä materiaali on oikeudenmukainen peli sinun midterms. Ja jos et jatka CS, nämä ovat todella tärkeitä perustekijöitä että sinun pitäisi tietää. Joten joinakin päivinä tulee olemaan hieman PSET apua, mutta joitakin viikkoja tulee paljon enemmän todellista sisältöä että ei voi tuntua erittäin sinulle hyötyä juuri nyt, mutta lupaan, jos jatkat siitä tulee olemaan erittäin, erittäin hyödyllinen. 

Niin se on siinä osassa. Viime hetkeen saakka. Tein sen minuutin kuluessa. Mutta siellä mennään. Ja minulla on munkkeja tai karkkia. Onko joku allerginen mitään, muuten? Munat ja maito. Niin munkkeja on ei? OK. Selvä. Suklaa ei? Escape. Starbursts ovat hyviä. OK. Aiomme olla Starburst ensi viikolla sitten. Se mitä saan. Teillä hyvä viikko. Lue spec. 

Kerrothan, jos sinulla on kysyttävää. PSET kahta laatua pitäisi olla ulos sinulle torstaina. Jos sinulla on kysyttävää miten olen lajitellut jotain tai miksi arvostellaan jotain niin kuin minä ei, lähetä sähköpostia minulle, tule juttelemaan. Olen hieman hullu tämä viikko, mutta lupaan Aion silti vastata 24 tunnin kuluessa. Niin on hyvä viikko, kaikille. Onnea PSET.