>> [Muziek]
>> ANDI Peng: Welkom in week 3 van de sectie.
Bedankt, jongens, voor alle komende deze vroegste starttijd vandaag.
We hebben een mooi, klein gekregen intieme groep vandaag.
Dus hopelijk krijgen afwerking, misschien, vroeg,
een beetje vroeg vandaag.
Zo snel, slechts enkele aankondigingen voor de agenda van vandaag.
Voordat we beginnen, we zijn zomaar over te gaan
enkele korte logistieke problemen, PSET vragen, debriefing, dat soort dingen.
En dan gaan we duiken recht in.
We zullen een debugger genaamd GDB te gebruiken start ontmaskeren van onze code, die David
uitgelegd in lezing de andere dag.
We gaan over de vier types van soorten.
We gaan over hen vrij snel omdat ze behoorlijk intensief.
Maar weet dat alle glijbanen en broncode zijn altijd online.
Dus voel je vrij, op uw inzage, om ga terug en neem een ​​kijkje op dat.
>> We gaan door asymptotische notatie, waarbij
is gewoon een mooie manier van te zeggen "runtimes,"
waar we de grote O, die David legde in collegezaal.
En we hebben ook Omega, die is de ondergrens runtime.
En we zullen een beetje meer te praten diepgaande over hoe die werken.
En tot slot, gaan we over binaire zoeken, omdat veel van jullie die al
wierp een blik op uw psets waarschijnlijk dat dat is een vraag die in uw PSET.
Dus je zult al blij zijn die wij dekken dit vandaag.
>> En tot slot, je per sectie feedback, ik eigenlijk
vertrokken ongeveer 15 minuten bij het einde tot iets meer dan gaan
logistiek van pset3, vragen, misschien een beetje begeleiding, zo u wilt,
voordat we beginnen met het programmeren.
Dus laten we proberen te krijgen door middel van het materiaal vrij snel.
En dan kunnen we wat tijd doorbrengen het nemen van meer vragen voor de PSET.
OK.
>> Snel, dus gewoon een paar aankondigingen voordat we beginnen vandaag.
Ten eerste, van harte welkom om te maken het door twee van uw psets.
Ik nam een ​​kijkje op uw-- ja, laten we krijgt een applaus voor die ene.
Eigenlijk was ik echt, echt onder de indruk.
Ik ingedeeld de eerste PSET voor jullie vorige week en dat jullie deed ongelooflijk.
>> Stijl was op punt naast een paar opmerkingen.
Zorg ervoor dat je altijd commentaar uw code.
Maar je psets waren over punt.
En keep it up.
En het is goed voor de grader aan zie dat jullie zetten
in zo veel moeite in uw stijl en uw ontwerp in uw code
dat we graag voor u om te zien.
Dus ik ben passeren langs mijn dank voor de rest van het TA.
>> Er zijn echter een paar debrief vragen
Ik wil alleen maar gaan over dat zou zowel mijn leven
en veel van de andere TA 'leeft een stuk makkelijker.
Ten eerste, heb ik gemerkt dit afgelopen week-- hoeveel van jullie
hebben gelopen check50 op uw code voordat u indienen?
OK.
Dus iedereen moet check50 moeten doen, because-- een secret-- we eigenlijk
gerund check50 als onderdeel van onze juistheid scripts voor het testen van uw code.
Dus als je code is niet check50, naar alle waarschijnlijkheid,
het is waarschijnlijk gaan om mislukken onze check ook.
Soms jullie hebben de juiste antwoorden.
Zoals, in gulzig, sommige je hebt de juiste nummers,
je gewoon uitprinten wat extra spullen.
En die extra dingen eigenlijk niet de cheque,
omdat de computer niet echt weten wat het zoekt.
En zo zal het gewoon doorlopen, zien dat uw output niet
overeenkomen met wat we verwachten dat het antwoord te zijn, en markeer het is verkeerd.
>> En ik weet dat er in sommige van uw gevallen deze week.
Dus ging ik terug en handmatig herindeling ieders code.
In de toekomst echter, alsjeblieft, alsjeblieft zorg ervoor dat
dat je draait Controleer 50 op uw code.
Want het is een soort van een pijn voor de TA te hebben om terug te gaan en handmatig opnieuw sorteren
elke PSET voor elke single, weinig gemist bijvoorbeeld.
Dus ik niet opstijgen geen punten.
Ik denk dat ik duurde misschien af één of twee voor het ontwerp.
In de toekomst echter, als je bent niet check50,
punten genomen off voor de correctheid.
>> Bovendien zijn psets wijten vrijdag op de middag.
Ik denk dat er een zeven minuten laat aflossingsvrije periode dat wij u.
Per Harvard tijd, ze mogen zeven minuten te laat om alles.
Dus hier in Yale, zullen we zich te houden aan dat ook.
Maar vrij veel, om 12:07, als je PSET niet in,
het gaat zo laat worden gemarkeerd.
En dus terwijl het wordt gemarkeerd zo laat de TA-- ik ben
nog steeds worden de indeling van uw psets.
Dus je zult nog steeds een cijfer verschijnen.
Echter, weet dat bij het einde van het semester,
Alle late psets zal gewoon worden automatisch op nul gezet door de computer.
>> We doen dit om twee redenen.
Eén, soms krijgen we verontschuldigd, zoals excuses decaan,
later dat ik niet weten nog niet.
Dus we willen ervoor zorgen dat we de indeling alles voor het geval, zoals, ik ben
ontbrekende excuus van een decaan.
En ten tweede, houden mind, kunt u nog steeds
laat een PSET dat heeft volledige scope punten.
En dus we willen kwaliteit al uw psets net
om ervoor te zorgen dat uw scope's er zijn en je ze proberen.
Dus zelfs als het laat, zult u nog steeds krediet voor scope punten, denk ik.
>> Dus moraal van het verhaal is, maken ervoor dat uw psets in on-time.
En als ze niet op tijd, weten dat het niet geweldig.
Ja, voordat ik verder gaan, heeft iemand Voor vragen over PSET feedback?
Ja.
>> PUBLIEK: Heb je zeggen dat we kan dalen een van de psets?
>> ANDI PENG: Ja.
Dus er is negen psets algehele in de loop van het semester.
En als je scope points-- dus scope is gewoon,
vrij veel, probeer je het probleem, brengt u in de tijd,
je laten zien dat je hebt gedemonstreerd heb je de spec lezen.
Dat is vrij veel ruimte.
En als je het vervullen scope punten, we
kan de laagste dalen een op de volledige reikwijdte.
Dus dat is in uw voordeel voltooien en probeer elke PSET.
>> Zelfs upload-- als geen van hen werken, upload ze allemaal.
En dan zullen we hopelijk in staat zijn om geven u een aantal van deze punten terug.
Cool.
Een andere vragen?
Grote.
>> Ten tweede kantoor hours-- een paar snelle notities over kantooruren.
Dus eerst, komt in het begin van de week.
Niemand is ooit spreekuur op maandag.
Christabel kwam kantooruren gisteravond.
Ja, Christabel.
En wat hebben we op het kantoor uur gisteravond, Christabel?
>> PUBLIEK: We hadden ijs.
>> ANDI PENG: Dus dat klopt, we hadden ijs op het kantoor uur gisteravond.
Terwijl ik je niet kan beloven dat we zullen ijs bij kantooruren
elke week, wat ik je kan beloven is dat er aanzienlijk zal een
betere student TA ratio.
Net als legit, het is 3-1.
Overwegende, dat contrast met Donderdag, heb je ongeveer 150 kreeg
echt gestrest kinderen en geen ijs.
En het is gewoon niet productief voor iedereen.
Dus moraal van het verhaal is, kom vroeg aan kantooruren en goede dingen
zal gebeuren.
>> Ook kom bereid om vragen te stellen.
Weet je?
Ongeacht wat TA, I denken, hebben gezegd,
we hebben het krijgen van een paar studenten die komen donderdag om, zoals, 10:50
niet de spec gelezen het zijn als help me, help me.
Helaas is op dat moment, is er niet veel wat we kunnen doen om u te helpen.
Dus kom vroeg in de week.
Kom vroeg om kantooruren.
Kom bereid om vragen te stellen.
Zorg ervoor dat u, als een student, zijn de plaatsen waar
je nodig hebt om, zodat het zijn TA kunt u langs,
dat is wat de kantooruren moet worden toegewezen voor.
>> Ten tweede, dus ik weet professoren willen ons verrassen met testen.
Ik had een professor die als, yo, door de manier,
vergeet niet dat midterm heb je volgende week maandag.
Ja, ik wist niet over dat midterm.
Dus ik ga dat TA die u eraan herinnert dat alles quiz
0-- omdat, weet je, we CS.
Nu dat we hebben gedaan arrays, krijg je waarom het quiz 0, geen quiz 1, eh?
OK.
Oh, ik heb een aantal grinnikt op die ene.
OK.
>> Dus quiz 0 zal 14 oktober als je bent in de sectie maandag-woensdag
en 15 oktober als je in de sectie dinsdag-donderdag.
Dit geldt niet voor degenen onder u aan de Harvard
who-- Ik denk dat je allemaal het nemen van uw quizzen op de 14e.
>> Dus ja, volgende week, als David, in collegezaal, gaat,
ja, zo ongeveer dat quiz volgende week jullie allemaal
zal niet geschokt omdat u sectie kwam
en je weet dat je quiz 0 is in twee weken.
En we zullen beoordeling hebben sessies en alles.
Dus geen zorgen over bang voor.
Voor vragen before-- vragen helemaal met betrekking tot logistieke problemen,
sorteren, kantooruren, secties?
Ja.
>> Publiek: Dus de quiz is gaat worden tijdens de les?
>> ANDI PENG: Ja.
Dus de quiz, denk ik, is 60 minuten toegewezen in dat tijdslot
dat je gewoon zult nemen in de collegezaal.
Dus je hoeft niet te komen op, zoals een willekeurige 07:00.
Het is al goed.
Ja.
Cool.
>> Prima.
Dus we gaan invoering van een concept voor u
deze week dat David heeft al soort van aangestipt in college afgelopen week.
Het heet GDB.
En hoeveel van jullie, terwijl in de loop van het schrijven van uw psets,
gemerkt hebben een grote knop die zegt "Debug" op de bovenkant van uw IDE?
OK.
Dus nu gaan we eigenlijk naar ontgraven het mysterie van wat die knop eigenlijk
doet.
En ik garandeer je, het is een mooi, mooi ding.
>> Dus tot nu toe, denk ik er is al twee dingen
studenten zijn doorgaans doet bij het oplossen psets.
Eén, ze ofwel voegen in printf () - dus elke paar regels,
ze voegen in een printf () - oh, wat is dit variabel?
Oh, wat is dit variabel now-- en u soort zien de progressie
van de code als het loopt.
Of de tweede methode kinderen doen is dat ze gewoon schrijven de hele zaak
en ga dan als volgt aan het eind.
Hopelijk werkt het.
Ik garandeer u, GDB is beter dan deze beide methoden.
Ja.
Dus dit zal uw nieuwe beste vriend.
Want het is een mooi ding die visueel geeft zowel
wat uw code doet op een specifiek punt
en wat al uw variabelen dragen,
als wat hun waarden zijn, op dat specifieke moment.
En op deze manier, kan je echt set breakpoints in de code.
U kunt lopen door lijn per lijn.
En GDB zal gewoon voor u, weergegeven voor u,
wat al uw variabelen zijn, wat doen ze,
wat er in de code.
En zodanig, dat het zo veel makkelijker om te zien
wat er gebeurt in plaats van printf-ing of het schrijven van uw uitspraken.
>> Dus we een voorbeeld van dit later te doen.
Dus dit lijkt een beetje abstract.
Geen zorgen, we zullen voorbeelden doen.
En zo wezen, de drie grootste, meest gebruikte functies die je nodig hebt in GDB
zijn de volgende, stap over, en Stap in knoppen.
Ik ga over het hoofd er eigenlijk nu.
>> Zodat jullie allemaal te zien dat of moet ik een beetje zoomen?
In de rug, zie je dat?
Moet ik te vergroten?
Gewoon een klein beetje?
OK, cool.
Daar gaan we.
OK.
>> Dus ik heb, hier, mijn implementatie voor hebberig.
En terwijl veel van jullie schreef hebzuchtige in while lus form-- dat
is een perfect aanvaardbare manier te doen het-- een andere manier om het te doen is om gewoon
verdelen de modulo.
Want dan kunt u uw waarde en dan heb je rest.
En dan kun je gewoon Voeg het allemaal samen.
Doet de logica van wat ik doe hier zin om iedereen,
voordat we beginnen?
Soort van?
Cool.
Grote.
Het is een vrij sexy stuk van de code, zou ik zeggen.
Zoals ik al zei, David, in lezing, na een tijdje,
u zult beginnen te zien code als iets dat is prachtig.
En soms als je ziet mooie code, het is zo'n heerlijk gevoel.
>> Dus Maar hoewel deze code is erg mooi, is het niet goed werkt.
Dus laten we lopen check50 op dit punt.
Controleer 50 20-- oop.
2?
Is dat pset2?
Ja.
Oh, pset1.
OK.
Dus we lopen check50.
>> En zoals jullie hier kunt zien, het is niet een paar gevallen.
En voor sommigen van u, in de loop van het doen van uw probleem sets,
je bent zoals, ah, waarom is het niet werkt.
Waarom is het werken voor een aantal waarden, maar niet voor anderen?
Nou, GDB gaat helpen u figuur waarom die inputs werkten niet.
>> OK.
Dus laten we zien, één van de cheques Ik was niet in check50
was de invoerwaarde van 0,41.
Dus het juiste antwoord dat moet u krijgt een 4.
Maar wat ik printen is de 3-n, dat is onjuist.
Dus laten we dit handmatig uitvoeren, net Zorg ervoor dat check50 werkt.
Laten we het doen ./greedy.
Oeps, ik hebberig te maken.
Daar gaan we.
Nu ./greedy.
>> Hoeveel is te danken?
Laten we het doen 0,41.
En yep, zien we hier dat het uitvoeren van 3
wanneer het juiste antwoord, in feite moet worden 4.
Dus laten we voeren GDB en zien hoe we kan gaan over de vaststelling van dit probleem.
>> Dus de eerste stap in altijd debuggen uw code
is een breekpunt, of een punt waarop u
wil dat de computer of de debugger te gaan kijken naar.
Dus als je niet echt weet wat je probleem is,
meestal, de typische ding willen we doen is om ons breekpunt op hoofd.
Dus als jullie dit zien rode knop daar,
yep, dat was me het instellen van een breekpunt voor de belangrijkste functie.
Ik die klik.
>> En dan kan ik gaan tot mijn Debug knop.
Ik raakte die knop.
Laat me opnieuw uit als ik kan.
Daar gaan we.
Dus we hebben, hier, een paneel aan de rechterkant.
Het spijt me, jongens in de rug, je kan niet echt heel goed.
Maar in wezen alle deze rechter paneel doet
is het bijhouden van zowel het gemarkeerde lijn, dat is de regel code
de computer momenteel actief is, alsmede alle variabelen
Hieronder.
>> Dus je hebt cent, munten, n, alle aangegeven verschillende dingen
Op dit moment.
Geen zorgen, want we hebben niet echt geïnitialiseerd ze nog enige variabelen.
Dus in uw computer, uw computer is gewoon te zien,
oh, 32767 was de laatst gebruikte functie van die geheugenruimte in mijn computer.
En dat is waar cent momenteel is.
Maar niet dat als je eenmaal de code uitvoert, Moet geïnitialiseerd worden.
>> Dus laten we gaan door, lijn door lijn, wat is hier aan de hand.
OK.
Dus hier zijn de drie knoppen die ik net uitgelegd.
Je hebt de Play of de functie Run, knop, heb je de stap op de knop,
en je hebt ook de Stap in knop.
En wezen alledrie ze gewoon gaan door de code
en doe verschillende dingen.
>> Dus meestal, als je het debuggen, we willen niet gewoon op Play,
want Play zal gewoon lopen code voor het einde van het.
En dan zul je niet echt weet wat je probleem
is tenzij u meerdere breakpoints.
Als u meerdere breekpunten ingesteld, het zal gewoon automatisch
van het ene breekpunt, naar de volgende, naar de volgende.
Maar in dit geval we hebben alleen dat ene, omdat we
willen onze manier van werken van boven naar beneden naar beneden.
Dus we gaan naar die knop te negeren op dit moment voor het doel van dit programma.
>> Dus de stap over functie net stappen op elke lijn
en vertelt je wat de computer aan het doen is.
De Stap in functie gaat in de eigenlijke functie
dat is op uw lijn van de code.
Dus bijvoorbeeld, zoals printf (), dat is een functie, toch?
Als ik wilde fysiek stap in de printf () functie,
Ik zou eigenlijk gaan in het stuk code waar de printf () werd geschreven en zien
wat gebeurt er daar.
>> Maar meestal, gaan we ervan uit dat de code die wij geven u werkt.
We veronderstellen dat de printf () werkt.
We nemen aan dat getInt () werkt.
Dus er is geen noodzaak om stap in die functies.
Maar als er functies dat je jezelf schrijven
dat u wilt controleren wat er gaande is,
je zou willen stappen in die functie.
>> Dus nu zijn we gewoon gaan stap over dit stukje code.
Dus laten we zien.
Oh, print, "Oh hai, hoe veel verandering is te danken? "
Kan ons niet schelen.
We weten dat het werkt, zodat we stap over het.
>> Zo n, dat is onze float dat we hebben initialized-- of declared--
op de top, we zijn nu gelijk dat voor GetFloat ().
Dus laten we stap over dat.
En we zien in de bodem hier het programma
wordt gevraagd mij het invoeren van een waarde.
Dus laten we het invoeren van de waarde die we willen hier testen, wat 0,41.
Grote.
>> Dus nu N-- doen jullie zien Hier, op de bottom-- het
stored-- omdat we nog niet afgerond, is het
opgeslagen in deze als reusachtige float dat is ,4099999996,
die dicht genoeg bij onze doeleinden, nu, tot 0,41.
En dan zullen we zien later, zoals we blijven intensivering over het programma,
na hier, is n geworden afgeronde en centen is geworden 41.
Grote.
Dus we weten dat het werk van onze afronding's.
We weten dat we de juiste aantal centen,
dus we weten dat dat niet echt het probleem.
>> Dus we blijven een stap in dit programma.
Wij gaan hier.
En dus na deze regel code, we moeten weten hoeveel kwartalen we hebben.
We stap over.
En je ziet wat we doen, in feite, hebben een kwartaal want we hebben afgetrokken 25
Aanbevolen beginwaarde van 41.
En we hebben 16 links voor onze centen.
>> Heeft iedereen begrijpen hoe het programma is doorlopen
en waarom cent is nu uitgegroeid tot 16 en waarom, nu, munten is geworden 1?
Is iedereen na die logica?
Cool.
Dus vanaf dit punt, de werkprogramma's, toch?
We weten dat het precies doet wat we willen dat het.
En we hebben niet echt hebben om uit te printen, oh, wat
is cent op dit punt, wat munten op dit punt.
>> We blijven gaan door het programma.
Overstappen.
Cool.
We gaan over dubbeltjes.
Grote.
We zien dat het is genomen off $ 0,10 voor een dubbeltje.
En nu hebben we twee munten.
Dat is correct.
>> We gaan over centen en we zien dat we hebben overgebleven cent.
Hmm, dat is vreemd.
Hier op het programma, moest ik mijn centen te hebben afgetrokken.
Misschien was ik gewoon niet doen die lijn recht.
En helaas, kunt u zien hier, omdat we weten
dat we de intensivering via leidingen 32 en 33,
dat is waar ons programma onjuist had variabelen lopen.
Dus we kunnen kijken en zien, oh, Ik aftrekken cent hier,
maar ik ben niet echt toevoegen aan mijn muntwaarde.
Ik ben toe te voegen aan cent.
En ik wil niet toe te voegen aan cent, ik wil toevoegen aan munten.
Dus als we dat veranderen om munten, we hebben een werkprogramma.
Ik kan check50 draaien.
Je kunt gewoon afsluiten van GDB recht hier en dan weer rennen check50.
Ik kan dit gewoon doen.
Ik moet hebberig te maken.
0,41.
En hier, het is druk het juiste antwoord.
>> Dus zoals jullie kunnen zien, GDB is echt een krachtig instrument
want als we hebben zo veel code gaande en zoveel variabelen
dat het moeilijk is voor ons, als een mens, bij te houden.
De computer, in de GDB debugger, heeft het vermogen
te houden van alles.
Ik weet het, in Visionaire, jullie waarschijnlijk kunnen sommige segmentatie fouten hebben geraakt
omdat je loopt uit grenzen van de array.
In het voorbeeld van Caesar, dat is precies wat ik heb hier geïmplementeerd.
>> Dus ik vergat om te controleren op wat er zou gebeuren als ik
niet twee commandoregel argumenten.
Ik wist alleen niet in dat het inchecken.
En dus als ik zonder Debug-- ik mijn breekpunt daar rechts.
Ik run Debug.
>> OK.
Ja.
Dus eigenlijk, GDB werd verondersteld hebben me daar verteld
was een segmentation fault daar.
Ik weet niet wat er gaande was daar, maar toen ik liep,
het werkte.
Als je regels code doorlopen en GDB zou zomaar ineens stoppen op je,
omhoog gaan en kijk wat de rode fout is.
Het zal je vertellen, hey, je had een segmentation fault,
wat betekent dat je geprobeerd om toegang te krijgen ruimte in een array die niet bestonden.
Ja.
>> Dus in het volgende probleem zet deze week, jullie
zal waarschijnlijk een heleboel variabelen rondzweven.
Je gaat niet om zeker te zijn wat ze betekenen allemaal op een bepaald punt.
Dus GDB zal je echt helpen bij het uitzoeken wat ze allemaal gelijk
en in staat om visueel te zien.
Is er iemand in de war over hoe elk van die werkzaam was?
Cool.
Prima.
Dus na dat, we zijn ga naar rechts duiken
in vier verschillende types van soorten voor deze week.
Hoeveel van jullie, de eerste van al, voordat we beginnen,
het hele spec voor pset3 hebt gelezen?
OK.
Ik ben trots op jullie.
Dat is hetzelfde als de helft van de klas, die is aanzienlijk meer dan de vorige keer.
>> Dus dat is geweldig, want als we praten over de inhoud
in lecture-- of sorry, in section-- Ik hou
een hoop die betrekking terug naar wat het is PSET
en hoe je wilt implementeren dat u in uw PSET.
Dus als je komt met lees de specificatie, het zal
een stuk makkelijker voor u om te begrijpen waar ik het over heb als ik zeg,
oh ja, dit zou een echt goede plek om dit soort uit te voeren.
Dus degenen onder u die hebben gelezen van de spec weten dat, als onderdeel van uw PSET,
je gaat te hebben om brief type soort.
Dus dit kan zeer nuttig zijn voor veel van jullie vandaag.
>> Dus we zullen beginnen met, in wezen de meest eenvoudige soort
van sorteren, de selectie sorteren.
De typische algoritme voor hoe we zouden gaan over dit
is-- David ging door deze all in lezing, dus ik zal snel bewegen langs
hier-- is in wezen, je hebben een scala van waarden.
En dan vind je het kleinste ongesorteerd waarde
en je swap die waarde met de eerste ongesorteerde waarde.
En dan moet je gewoon blijven herhalen met de rest van de lijst.
>> En hier is een visuele verklaring hoe dat zou werken.
Dus bijvoorbeeld, als we beginnen met een serie van vijf elementen, index
0-4, met 3, 5, 2, 6 en 4 waarden geplaatst in de array-- zo goed nu,
we gaan gewoon om te veronderstellen dat ze allemaal ongesorteerd
omdat we anders niet getest.
>> Dus hoe een selectie soort zou werk is dat het zou eerst
lopen door het geheel van de ongesorteerde array.
Het zou halen uit de kleinste waarde.
In dit geval 3, rechts Nu is het kleinst.
Het wordt om 5.
Nope, 5 niet groter than-- of sorry, niet minder than-- 3.
Zodat de minimale waarde is nog steeds 3.
En dan krijg je 2.
De computer ziet, oh, 2 minder dan 3.
2 moet nu de minimale waarde.
En zo 2 swaps met die eerste waarde.
>> Dus na één keer, we inderdaad zien de 2 en 3 zijn verwisseld.
En we gaan gewoon te blijven doen dit opnieuw met de rest van de matrix.
Dus we gaan gewoon doorlopen de laatste vier indexen van de array.
We zullen zien dat er 3 is de volgende minimale waarde.
Dus we gaan om te wisselen die met 4.
En dan zijn we gewoon gaan houden loopt door tot uiteindelijk je
krijgen een gesorteerde array waarin 2, 3, 4, 5 en 6 zijn allemaal gesorteerd.
Heeft iedereen begrijpt de logica van hoe een selectie soort werkt?
>> Je hoeft alleen maar een soort van een minimale waarde.
Je bent het bijhouden van wat dat is.
En wanneer je het te vinden, je swap de eerste waarde in de array--
of, niet de eerste value-- de volgende waarde in de matrix.
Cool.
>> Zodat jullie soort zag vanuit een korte blik,
we gaan dit pseudo-out.
Dus als jullie in de rug willen vormen een groep, iedereen aan tafel
kan een beetje partner te vormen, ga ik u jongens als drie minuten geven
om gewoon door te praten de logica in het Engels,
hoe kunnen we in staat zijn om uit te voeren pseudocode om een ​​selectie soort schrijven.
En er is snoep.
Kom op en krijgen snoep.
Als je in de rug en je wilt snoep, kan ik gooi snoep op jou.
Eigenlijk doe u-- cool.
Oh sorry.
OK.
>> Dus als we zouden willen, als Een cursus volgen, schrijven pseudocode
hoe men zou kunnen benaderen dit probleem, maar voel je vrij.
Ik kom net rond gaan en, in orde, vraag groepen
voor de volgende regel wat we moeten doen.
Dus als jullie willen beginnen off, wat is het eerste wat
te doen als je probeert om uitvoering van een manier om dit programma te lossen
om een ​​lijst selectief sorteren?
Laten we aannemen dat we hebben een scala, oké?
>> PUBLIEK: U wilt wat te creëren soort [onverstaanbaar] dat je
door je hele reeks.
>> ANDI Peng: Recht.
Dus je gaat te willen herhalen door elke ruimte, toch?
Zo goed.
Als jullie mij willen het geven volgende line-- ja, in de rug.
>> PUBLIEK: Check ze Alle voor de kleinste.
>> ANDI Peng: Daar gaan we.
Dus we willen om door te gaan en te controleren om zien wat de minimale waarde is, toch?
Ik ga om te korten, dat op "min."
Wat willen jullie doen na u de minimale waarde hebt gevonden?
>> PUBLIEK: [onverstaanbaar]
ANDI PENG: Dus je gaat te willen schakelaar met de eerste van die array,
toch?
Dat is het begin, ik ga zeggen.
Prima.
Dus nu dat u hebt verwisseld de eerste één, wat wil je doen na dat?
Dus nu weten we dat dit hier moet de kleinste waarde, toch?
Dan moet je een extra rust van de matrix die ongesorteerde.
Dus wat je hier wilt doen, als je jongens willen me de volgende regel te geven?
Publiek: Dus dan wil je herhalen gedurende de rest van de matrix.
ANDI PENG: Ja.
En dus wat maakt iteratie door middel van soort impliceren we zullen waarschijnlijk nodig?
Wat voor soort--
>> PUBLIEK: Oh, een extra variabele?
ANDI PENG: Waarschijnlijk een andere lus, toch?
Dus we waarschijnlijk te willen through-- geweldig om te herhalen.
En dan zul je om terug te gaan en Controleer waarschijnlijk het minimum weer,
toch?
En je gaat blijven herhalen Dit, omdat de lussen gewoon
te blijven draaien, toch?
>> Dus zoals jullie kunnen zien, we gewoon een algemene pseudocode
van hoe we willen dit programma te kijken.
Dit herhalen hier, wat doen we meestal nodig om te schrijven in onze code
als we willen doorlopen van een array, wat voor soort structuur?
Ik denk Christabel dit al eerder gezegd.
>> PUBLIEK: Een lus.
>> ANDI Peng: een lus?
Precies.
Dus dit is waarschijnlijk gaan een voor lus.
Wat is een check hier gaan betekenen?
Typisch, als u wilt controleren als er iets is iets else--
>> Publiek: Als.
>> ANDI Peng: Een als, toch?
En dan de swap Hier zullen we ga dan later, omdat David
ging door die in collegezaal ook.
En dan de tweede iterate implies--
>> PUBLIEK: Nog een lus.
>> ANDI Peng: --another lus, precies.
Dus als we kijken Dit kunnen we
kan zien dat we waarschijnlijk gaan naar een geneste lus nodig
met een voorwaardelijke instructie daar en dan een echte stukje code dat is
gaat om de waarden te wisselen.
Dus ik heb net over het algemeen geschreven een pseudocode code hier.
En dan zijn we eigenlijk gaan fysiek als klasse,
proberen om de uitvoering van deze vandaag.
Laten we terug gaan naar deze IDE.
>> Oh Oh.
Waarom is dat niet-- daar is.
OK.
Sorry, laat me proberen een beetje meer te zoomen.
Daar gaan we.
Alles wat ik hier doe is ik heb gemaakt een programma genaamd "selectie / sort.c."
Ik heb een serie van negen gecreëerd waarden, 4, 8, 2, 1, 6, 9, 7, 5, 3.
Op dit moment, als je kunt zie, zij zijn ongeordende.
n gaat het getal dat vertelt u het bedrag van de waarden
je hebt in je array.
In dit geval hebben we negen waarden.
En ik heb net een lus hier dat drukt de ongesorteerde array.
>> En aan het eind, heb ik ook nog een voor lus die gewoon wordt afgedrukt weer uit.
Dus in theorie, als dit programma correct werkt, aan het eind,
je moet zien lus een gedrukte waarin 1, 2, 3, 4, 5, 6, 7, 8,
9 zijn allemaal correct in orde.
>> Dus hebben we onze pseudocode kregen hier.
Wil iemand to-- Ik ben gewoon ga vragen volunteers--
Vertel me precies wat te typen als we willen, eerst, enkel herhalen
door middel van het begin van deze serie?
Wat is de lijn van code die ik ben waarschijnlijk zal hier nodig?
>> PUBLIEK: [onverstaanbaar]
>> ANDI Peng: Ja, voelen gratis to-- sorry, u
hoeven niet te up-- gevoel staan vrij om uw stem te verheffen een beetje.
>> Publiek: voor int i gelijk 0--
>> ANDI Peng: Ja, goed.
>> Publiek: i minder dan matrix lengte.
>> ANDI Peng: Dus houd in erg hier, omdat we
geen functie hebben die vertelt de lengte van een array,
hebben we al een waarde die opgeslagen.
Rechts?
Een ander ding te houden in mind-- in een array
van de negen waarden, wat zijn de indexen?
Laten we zeggen dat deze array was 0-3.
Je ziet dat de laatste index is eigenlijk 3.
Het is niet 4, ook al is er vier waarden in de matrix.
>> Dus hier, we moeten heel voorzichtig zijn wat onze voorwaarde voor de lengte
wordt.
>> Publiek: Zou het niet n min 1?
ANDI PENG: Het gaat n minus 1, precies.
Is dat zinvol is, waarom het n minus 1, iedereen?
Het is omdat arrays zijn zero-geïndexeerd.
Ze beginnen bij 0 en aanloop naar n min 1.
Ja, het is een beetje lastig.
OK.
En dan--
PUBLIEK: Isnt'1 dat al voor gezorgd hoewel,
door gewoon niet te zeggen "kleiner dan of gelijk aan "en gewoon zeggen" minder dan? "
>> ANDI PENG: Dat is een echt goede vraag.
Ja dus.
Maar ook de manier waarop we de uitvoering van de controle op juiste,
je nodig hebt om twee waarden te vergelijken.
Zodat je eigenlijk wilt Laat de "om" leeg.
Want als je het vergelijkt deze, je bent niet van plan
iets na te vergelijken met, toch?
Ja.
Dus i ++.
We voegen onze beugels in.
Whoops.
Grote.
Dus we hebben het begin onze buitenste lus.
Dus nu waarschijnlijk willen we creëren van een variabele voor het houden
spoor van de kleinste waarde, toch?
Wil iemand mij geven regel code die dat zou doen?
Wat hebben we nodig als we gaan te willen om iets op te slaan?
>> Rechts.
Misschien een betere naam voor die zou be-- "temp" totaal works--
misschien een meer toepasselijke naam zou zijn, Als we willen dat de kleinste value--
>> Publiek: Min.
ANDI Peng: min, daar gaan we.
min zou goed zijn.
En dus even, wat doen we wil het initialiseren aan?
Dit is een beetje lastig.
Want nu op de begin van deze matrix,
je niet hebben gekeken naar iets, toch?
Dus wat, automatisch, als we zijn gewoon op i gelijk is aan 0,
wat willen we initialiseren onze eerste minimale waarde?
Publiek: i.
ANDI Peng: Ik, precies.
Christabel, waarom willen we om het initialiseren te i?
>> Publiek: Omdat, goed, we beginnen met 0.
Dus omdat we hebben niets te vergelijken het aan de minimum wordt uiteindelijk op 0.
>> ANDI PENG: Precies.
Dus ze is precies goed.
Omdat we eigenlijk niet keek nog niets,
we weten niet wat onze minimale waarde is.
We willen gewoon initialiseren aan i, die, op dit moment, is hier.
En als we doorgaan met deze array naar beneden,
we zullen zien dat, met elkaar aanvullende pas, ik verhoogt.
En dus op dat punt, i gaat waarschijnlijk
te willen tot het minimum te zijn, omdat het gaat om wat dan ook
is het begin van het ongesorteerde array.
Cool.
>> Dus nu willen we voegen een lus hier dat is
zal doorlopen de ongesorteerd, of de rest van deze array.
Wil iemand mij een te geven regel code die dat zou doen?
Hint-- wat hebben we hier nodig beneden?
Wat is er te gaan in deze lus?
Ja.
Publiek: Dus we zouden willen een andere integer,
want we lopen door de rest van de matrix in plaats van de i, dus misschien
j.
>> ANDI Peng: Ja, j klinkt goed voor mij.
Evenaart?
>> Publiek: Dus zou ik plus 1, omdat je begint bij de volgende waarde.
En vervolgens naar de end-- Nogmaals, j minder dan n minus 1, en dan j ++.
ANDI Peng: Grote.
>> En dan hier, we gaan te willen om te controleren om te zien of onze voorwaarde is voldaan,
toch?
Omdat je wilt veranderen de minimale waarde
als het is eigenlijk kleiner dan wat je bent te vergelijken met, toch?
Dus wat gaan we willen hier?
Controleren om te zien.
Wat voor soort statement zijn we waarschijnlijk gaan
ti wilt gebruiken als we iets willen controleren?
>> Publiek: Een if statement.
>> ANDI Peng: Een if statement.
Dus if-- en wat gaat worden de voorwaarde dat we willen binnen
van onze if?
>> AUDIENCE: Als de waarde van j kleiner is dan de waarde van I--
>> ANDI PENG: Precies.
Zo if-- zodat deze array wordt "matrix".
Grote.
Dus als array-- wat was dat?
Zeg dat nog eens.
>> Doelgroep: Als serie-j is minder dan matrix-i, dan zouden we het min veranderen.
Dus de min j zou zijn.
>> ANDI Peng: Is dat logisch?
OK.
En nu hier beneden, we eigenlijk willen de swap uit te voeren, toch?
Zo herinneren, in collegezaal, dat David, toen hij probeerde te the-- wat swap
het-- sinaasappelsap en milk--
>> PUBLIEK: Dat was walgelijk.
>> ANDI Peng: Ja, dat was een soort van de bruto.
Maar het was een vrij goede Het concept demonstreren tijd.
Dus denk aan uw waarden hier.
Je hebt een scala gekregen van min, een matrix van i,
of wat we probeerden om hier te wisselen.
En u waarschijnlijk kunt ze niet giet het in elkaar tegelijkertijd, toch?
Dus wat gaan we nodig hebben om hier te creëren
teneinde de waarden correct ruilen?
>> PUBLIEK: Een tijdelijke variabele.
>> ANDI Peng: een tijdelijke variabele.
Dus laten we het doen int temp.
Zie, zou dit een beter tijd to-- whoa, wat was dat?
OK.
Dus dit een beter zou zijn geweest tijd om de variabele "temp." noemen
Dus laten we het doen int temp.
Wat gaan we set temp gelijk naar hier?
PUBLIEK: Min?
ANDI PENG: Het is een beetje lastig.
Het maakt eigenlijk niet uit in het einde.
Het maakt niet uit wat Om u ervoor kiest om te wisselen in
zolang je ervoor zorgen dat je bent het bijhouden van wat je ruilt.
>> Publiek: Het kon serie-i zijn.
>> ANDI Peng: Ja, laten we serie-i.
En wat is dan de volgende regel van de code die we hier willen hebben?
PUBLIEK: serie-i is gelijk aan serie-j.
ANDI Peng: En tot slot?
PUBLIEK: serie-j is gelijk aan serie-i.
PUBLIEK: Of serie-j gelijken matrix-temp-- of temp.
>> ANDI Peng: OK.
Dus laten we dit uitvoeren en zien als het gaat werken.
Waar is dat gebeurt?
Oh, dat is een probleem.
Zie, op lijn 40, we zijn proberen array-j gebruiken?
Maar waar komt j bestaan ​​alleen in?
>> PUBLIEK: In de lus.
ANDI Peng: Recht.
Dus wat gaan we doen?
>> Publiek: Definieer het buiten the--
Publiek: Ja, ik denk dat je moet naar een ander te gebruiken als statement, toch?
Dus als, als de minimum-- Oké, laat me denken.
>> ANDI Peng: Jongens, probeer om een ​​kijkje te laten we
zie, wat is iets wat we kunnen doen hier?
>> Publiek: OK.
Dus als het minimum niet gelijk j-- dus als het minimum is nog I--
dan zouden we niet hoeven te wisselen.
>> ANDI Peng: Is dat gelijk i?
Wat wil je hier te zeggen?
>> PUBLIEK: Of ja, als de minimum niet gelijk ik, ja.
ANDI Peng: OK.
Nou dat oplost, soort, onze problemen.
Maar dat nog steeds niet het oplossen van de probleem van wat er gebeurt als j-- sinds j
niet bestaan ​​doet daarbuiten, wat wil je dat we doen?
Verklaar het buiten?
Laten we proberen het uitvoeren van deze.
Oh Oh.
Onze soort werkt niet.
>> Zoals u, onze eerste kan zien matrix had die waarden.
En daarna zou moeten hebben is in 1, 2, 3, 4, 5, 6, 7, 8, 9.
Het werkt niet.
Ahh.
Wat doen we?
Publiek: Debug.
ANDI Peng: Oké, kunnen we proberen dat.
We kunnen debuggen.
Uitzoomen een beetje.
Laten we stellen onze breekpunt.
Laten we gaan like-- OK.
>> Omdat we weten al dat deze lijnen 15 tot 22,
zijn working-- omdat alles wat ik doe is gewoon itereren door en printing--
Ik kan gaan en overslaan.
Laten we beginnen op lijn 25.
Oop, laat me te ontdoen van.
>> Publiek: Dus het breekpunt's waar de debuggen begint?
ANDI Peng: of stopt.
Publiek: of stopt.
ANDI PENG: Ja.
U kunt meerdere breakpoints instellen en kan slechts van de ene naar de andere.
Maar in dit geval weten we niet waar de fout gebeurt.
Dus we willen gewoon starten van boven naar beneden.
Yep.
OK.
>> Dus deze lijn hier, kunnen we ingrijpen.
U kunt hier naar beneden te zien, we hebben een array.
Dat zijn de waarden die in de array.
Zie je dat, hoe index 0, is het komt overeen met de value-- oh,
Ik ga proberen om in te zoomen.
Sorry, het is echt moeilijk om see-- bij array-index 0,
We hebben een waarde van 4 en Vervolgens enzovoort, enzovoort.
We hebben onze lokale variabelen.
Nu i is gelijk aan 0, wat we willen dat het is.
>> En zo laten we doorlopen.
De minimum gelijk is aan 0, die we willen ook dat het is.
En dan gaan we onze tweede voor lus, als matrix-j minder dan matrix-i,
waarvan zij niet.
Dus heb je zien hoe dat overgeslagen dat?
>> Publiek: Dus moet het als minimum, alle dat-- moet niet dat
zijn in de eerste lus?
ANDI Peng: Nee, want je nog wilt testen.
U wilt een vergelijking elke doen tijd, zelfs nadat je door het uit te voeren.
Je hoeft niet alleen willen doen op de eerste doorvoer.
U wilt doen met elke extra pas weer.
Dus u wilt controleren je conditie binnen.
Dus we gaan gewoon blijven draaien door middel van hier.
Ik geef je jongens een hint.
Het heeft te maken met het feit dat bij je bent het controleren van uw voorwaardelijk,
je bent niet controleren de juiste index.
Dus nu je controleren op scala index van j minder dan scala
index van de i.
Maar wat doe je bij het begin van de lus?
Bent u niet instellen j gelijk aan i?
>> Ja, dus we kunnen eigenlijk verlaat hier de debugger.
Dus laten we eens een kijkje op onze pseudocode.
Voor-- we gaan beginnen bij i gelijk is aan 0.
We gaan om te gaan tot n min 1.
Laten we eens kijken, hadden we dat toch?
Yep, dat was juist.
>> Dus dan in hier, we zijn naar een minimumwaarde creëren
en stel dat gelijk is aan i.
Hebben we dat doen?
Yep, dat deed.
Nu in onze innerlijke lus, we zijn ga j doen gelijk ik tot n 1 min.
Hebben we dat doen?
Inderdaad, we deden dat.
>> Dus maar wat we hier te vergelijken?
>> PUBLIEK: j plus 1.
ANDI PENG: Precies.
En dan zul je wilt instellen uw minimale gelijk aan j plus 1 ook.
Dus ik ging door dat heel snel.
Doen jullie begrijpen waarom het j plus 1?
OK.
>> Dus in Matrix uw eerste passage door,
uw lus, voor int i gelijk is aan 0, laten we gewoon
neem aan dat dit is nog niet veranderd.
We hebben een scala van volledig, slechts vier ongesorteerde elementen, toch?
Dus we willen initialiseren i gelijk is aan 0.
En ik zal net lopen door deze lus.
En zo in de eerste pas, we gaan een variabele genaamd "min" initialiseren
die ook gelijk is aan i, omdat we hebben niet een minimale waarde.
Dus dat is momenteel gelijk aan 0 als goed.
En dan gaan we door te gaan.
En we willen weer herhalen.
Nu dat we hebben gevonden wat onze minimale is, willen we door middel van herhalen
opnieuw om te zien of het is te vergelijken, toch?
Dus j, hier gaat gelijke i, die 0.
En dan als serie j plus i, die is degene die het volgende over, als minder
dan wat uw huidige minimum waarde is, je wilt ruilen.
>> Dus laten we gewoon zeggen dat we hebben gekregen, zoals, 2, 5, 1, 8.
Nu, i is gelijk aan 0 en j gelijk is aan 0.
En dat is onze minimale waarde.
Als serie-J plus Ik-- dus als degene dat is na de ene we kijken naar
groter is dan de vorige is, het gaat om het minimum te worden.
>> Dus hier zien we dat 5 niet minder dan dat.
Dus het gaat niet 5.
We zien dat 1 minder dan 2, toch?
Dus nu weten we dat onze minimum naar de indexwaarde worden op 0, 1, 2.
Ja?
En dan als je hier beneden, U kunt wisselen de juiste waarden.
>> Dus als je jongens gewoon hadden de j eerder, was je niet kijken naar de ene
na.
Je was op zoek naar dezelfde waarde,
is de reden waarom het was gewoon niet iets te doen.
Heeft dat zin om iedereen, waarom we dat plus 1 is er nodig?
OK.
Laten we nu gewoon lopen door het te laten of de rest van de code correct is.
Waarom is dat gebeurd?
Ah, het is de min hier.
We waren de verkeerde waarde te vergelijken.
O nee.
>> Oh ja, hier beneden waren we omwisselen van de verkeerde waarden ook.
Want we waren op zoek naar i en j.
Dat zijn degenen die we het controleren waren.
We eigenlijk willen de swap minimum, de huidige minimum,
met wat degene buitenkant is.
En zoals jullie kunnen zien neer Hier hebben we een gesorteerde array.
Het had gewoon te maken met dat bij
we waren het de waarden waren we vergelijken,
we waren niet op zoek naar de juiste waarden.
We waren op zoek naar het zelfde hier, eigenlijk niet te verwisselen.
Je moet kijken naar de ene naast aan het en dan kan je wisselen.
Dus dat is wat voor soort afluisteren onze code voor.
En wat ik deed hier is alles de debugger had kunnen doen voor u
Ik deed het alleen op de boord, want het is makkelijker
eerder te zien dan te proberen om in te zoomen op de debugger.
Heeft dat zin om iedereen?
Cool.
>> Prima.
We kunnen overgaan tot het over asymptotische notatie, waarbij
is gewoon een mooie manier om te zeggen de runtimes al deze soorten.
Dus ik weet dat David, in collegezaal, aangeroerd runtimes.
En hij ging door de hele formule hoe de runtimes berekenen.
Geen zorgen over dat.
Als je echt nieuwsgierig over hoe dat werkt,
voel je vrij om me te praten na sectie.
We kunnen wandelen door de formules elkaar.
Maar alles wat je jongens hebben echt weten is dat n kwadraat meer dan 2
is hetzelfde als n kwadraat.
Omdat de meeste, de exponent, groeit de.
En dus voor onze doeleinden, alles wat we zorg over
is dat gigantische nummer dat groeit.
>> Dus wat is het beste geval runtime van selectie sorteren?
Als je gaat te hebben te herhalen door een lijst
en dan doorloopt de rest van die lijst,
hoe vaak zijn ga je waarschijnlijk,
in het ergste case-- in de beste geval sorry-- doorlopen?
Misschien is de betere vraag is om te vragen, wat is het ergste geval
runtime van de selectie sorteren.
Publiek: n kwadraat.
ANDI PENG: Het is n kwadraat, rechts.
Dus een eenvoudige manier te denken van dit is als, elke keer als je twee geneste lussen te hebben,
het gaat om n worden kwadraat.
Want niet alleen bent u loopt door nogmaals,
je hebt om terug te gaan rond en lopen er doorheen
nogmaals binnen voor elke waarde.
Dus in dat geval, je loopt n tijden n kwadraat, die droevig is--,
n keer n, die gelijk aan n kwadraat.
>> En sorteren is ook een beetje uniek in de zin
dat het niet uitmaakt of deze waarden zijn reeds ter.
Het is nog steeds te lopen door anyways.
Laten we zeggen dat dit was 1, 2, 3, 4.
Ongeacht of het in orde, zou het nog liep door
en nog steeds controleerde de minimale waarde.
Het zou hebben gemaakt van de hetzelfde aantal controles
elke keer, zelfs als het niet daadwerkelijk iets aan te raken.
>> Dus in zo'n geval de beste en slechtste runtimes zijn eigenlijk gelijk.
Zodat de verwachte runtime van de selectie sorteren,
die we aanduiden met het symbool van theta, theta, in casu
zou ook n te rijmen.
Alle drie van deze zou worden n kwadraat.
Is iedereen duidelijk waarom de runtime is n kwadraat?
>> Prima.
Dus ik ga gewoon om snel te draaien de rest van de soort.
Het algoritme voor bubble sort-- herinneren,
Dit was de eerste David ging in collegezaal.
In wezen, je stap door de hele lijst
en je je gewoon swap-- vergelijken twee tegelijk.
En als men is groter, dan je gewoon ruilen hen.
Dus als deze groter zijn, zou je ruilen.
Ik heb officiële kreeg hier.
>> Dus laten we gewoon zeggen dat je had 8, 6, 4, 2.
Je zou vergelijken met de 8 en een 6.
Je nodig hebt om ze te ruilen.
Je zou de 8 en een 4 te vergelijken.
Je nodig hebt om ze te ruilen.
Als je moet wisselen van de 8 en de 2, veranderen ze ook.
Dus in zo'n gevoel, kunt u zien, gespeeld over een lange periode van tijd,
hoe de waarden soort zeepbel de uiteinden, dat is waarom we noemen het
bubble sort.
>> We zouden alleen lopen door weer onze tweede pas, en onze derde pas,
en onze vierde pass.
In wezen, bubble sort gewoon loopt totdat je niet meer swaps te maken.
Dus in die zin, dit is gewoon de algemene pseudocode voor.
Geen zorgen, deze zullen alle online zijn.
We hoeven niet te eigenlijk gaan over dit.
>> We initialiseren gewoon een teller variabele die begint bij 0.
En wij herhalen door de gehele array.
Als één waarde is-- indien waarde groter is dan die waarde,
je gaat om ze te ruilen.
En dan ben je gewoon gaat om door te gaan.
En je gaat tellen.
En je bent gewoon te blijven doen dit terwijl de teller groter
dan 0, waardoor elke keer dat je hoeft te wisselen,
je weet dat je wilt gaan terug en controleer opnieuw.
U wilt controle houden totdat je weet dat je niet meer hoeft te wisselen.
>> Dus wat zijn de beste en slechtste case runtimes voor bubble sort?
En dit is eigenlijk anders hint-- van de selectie sorteren in de zin
dat deze twee antwoorden zijn niet hetzelfde.
Denk na over wat er zou gebeuren in een geval als het was al opgelost.
En na te denken over wat zou er gebeuren als het was
in het geval waarin het werd niet gesorteerd.
En je kunt soort lopen door middel van de reden waarom dat gebeurt.
Ik geef je jongens, als, 30 seconden over nadenken.
>> OK.
Heeft iemand een gok naar wat de ergste geval looptijd van bubble sort is?
Ja.
>> Publiek: zou het zijn, als, n keer n minus 1 of iets dergelijks?
Zoals, elke keer dat het draait, het is gewoon, zoals, een swap minder
dat wat het ook was.
>> ANDI Peng: Ja, dus je helemaal gelijk.
En dit is een geval waarin uw antwoord was eigenlijk meer complexe
dan degene die we nodig hebben om te geven.
Dus het gaat om run-- ik ben ga dit hier allemaal te wissen.
Is iedereen goed?
Kan ik dit verwijderen?
OK.
Je gaat lopen door n keer de eerste keer, toch?
En ze gaan lopen door n minus 1 de tweede keer, toch?
En dan zul je te houden gaan, n mijne 2, et cetera.
David deed dit in een lezing, waarbij, als je opgeteld al die waarden,
je iets dat is te krijgen like-- yeah-- dan 2, dat in wezen alleen vermindert
tot aan n kwadraat.
Je gaat naar een krijgen raar fractie daar.
En dus weet alleen dat n het kwadraat altijd
heeft voorrang boven de fractie.
Dus in dit geval, de slechtste runtime zou n worden kwadraat.
Als het in afnemende orde, denk, u
moet je een swap elke keer te maken.
>> Wat zou zijn, mogelijk, het beste geval runtime?
Laten we maar zeggen, als de lijst was al in orde, wat zou de runtime zijn?
>> Publiek: n.
ANDI PENG: Het is n, precies.
En waarom is het n?
Publiek: Omdat je gewoon hebben om te controleren op elke keer.
ANDI PENG: Precies.
Dus in de best mogelijke runtime, Als deze lijst was al
sorted-- laten we zeggen 1, 2, 3, 4-- u zou gewoon door te gaan, zou u controleren,
je zou zien, oh, ze allemaal de pan uit.
Ik hoefde niet te verwisselen.
Ik ben klaar.
Dus in dat geval, het is gewoon n of het aantal stappen dat je gewoon
hadden in de eerste lijst controleren.
>> En na, hebben we nu hit insertion sort, waarbij
het algoritme is in essentie te verdelen het in een gesorteerde en ongesorteerde deel.
En vervolgens een voor een, de gesorteerde waarden
ingevoegd in de juiste posities in het begin van de lijst.
>> Dus bijvoorbeeld, hebben we een lijst 3, 5, 2, 6, 4 weer.
We weten dat het momenteel ongesorteerde want we hebben net
begon te kijken naar het.
We nemen een kijkje en we weten dat de eerste waarde wordt gesorteerd, toch?
Als je alleen kijkt naar een reeks van grootte een, weet je dat het is opgelost.
>> Dus dan weten we dat de andere vier zijn ongesorteerd.
We gaan door en zien we die waarde.
Laten we terug gaan.
Zie je die waarde van 5?
We nemen een kijkje bij het.
We vergelijken met 3.
We weten dat het groter is dan 3, dus we weten dat dat is opgelost.
We weten nu dat de eerste twee worden gesorteerd en de laatste drie zijn niet.
>> We nemen een kijkje op 2.
We controleren eerst met 5.
Is het minder dan 5?
Het is niet.
Dus moeten we blijven zoeken naar beneden.
Dan kijk je 2 uit 3.
Is het minder dan?
Nee.
Dus je weet dat een 2 moet worden gestoken in de voorste en 3 en 5
beide moeten worden geduwd.
Doe dit opnieuw met 6 en 4.
En we blijven controleren wezen, waar we maar eens kijken, check, check.
En totdat het in de juiste positie, we soort van slechts
plaatst u deze in de juiste positie, dat is waar de naam van het vandaan kwam.
>> Dus dat is gewoon het algoritme, pseudocode per se, een soort van,
over hoe we zouden implementeren een insertie soort.
Pseudocode is hier.
Het is allemaal online.
Geen zorgen als jullie zijn proberen om dit te kopiëren naar beneden.
Dus nogmaals, wat hetzelfde question-- zou de beste en slechtste runtimes worden
voor het inbrengen soort?
Het is zeer vergelijkbaar met de laatste vraag.
Ik geef je jongens, als, 30 seconden na te denken over dit zo goed.
>> OK Heeft iemand willen geef mij het ergste runtime?
Ja.
>> Publiek: n kwadraat.
>> ANDI Peng: Het is n kwadraat.
En waarom is het n kwadraat?
>> Publiek: Omdat in omgekeerde volgorde, je hebt
om te gaan door n keer n, dat is--
ANDI Peng: Ja, precies.
Dus hetzelfde als in de bubble sort.
Als deze lijst is in aflopende volgorde, je bent
gaat te hebben om de eerste keer te controleren.
En vervolgens bij elke toegevoegde waarde, je bent
gaat te hebben om het te controleren tegen elke waarde, toch?
En zo totaal, je gaat maken een n pas keer een ander n pas, die
is n kwadraat.
Hoe zit het met het beste geval?
Ja.
>> PUBLIEK: n minus 1, omdat de eerste reeds kwadraat.
>> ANDI Peng: Dus, in de buurt.
Het antwoord is eigenlijk n.
Want terwijl de eerste is gesorteerd, kan zij niet actually--
we hadden geluk, in dat bijvoorbeeld dat 2
is er gebeurd met het kleinste getal.
Maar dat niet altijd het geval zal zijn.
Als 2 al naargelang het begin maar je kijkt en er is een 1 hier,
de 1 gaat om het lijf.
En het zal eindigen omhoog wordt gestoten anyways.
>> Dus in het beste geval, het is eigenlijk gewoon te n zijn.
Als je 1, 2, 3, 4, 5, 6, 7, 8, je bent
gaan lopen door dat hele lijst ooit
om te controleren om te zien of alles goed is.
Is iedereen duidelijk running tijden van de selectie ook?
Ik weet dat ik ga door deze echt snel.
Maar weet gewoon dat als je weet dat de algemene begrippen, moet je goed zijn.
OK.
Dus ik geef jullie misschien, als, een minuut om je buren te praten
op wat er net zijn enkele van de belangrijkste verschillen
tussen deze soorten van soorten.
We zullen dan gaan dat binnenkort.
PUBLIEK: Oh, OK.
ANDI PENG: Ja.
OK.
Cool, laten we opnieuw bijeen als een klasse.
OK.
Dus dit was een soort van een open vraag in die zin
dat er veel antwoorden op hen.
En we zullen meer dan in het kort te gaan een aantal van hen.
Ik wilde alleen maar om jullie te krijgen denken over wat gedifferentieerd
alle drie de soorten.
En ik hoorde, ook een grote question-- wat doet samenvoegen soort doen?
Grote vraag, want dat is wat we met betrekking tot de volgende.
>> Dus samenvoegen sorteren is de een soort die functies
zeer verschillend van de andere soorten.
Zoals jullie kunnen see-- David deed dat doen demo
waar hij had al de koele geluiden te zien hoe samenvoegen
soort liep, als, oneindig sneller dan de andere twee typen?
OK.
Dus dat is omdat samenvoegen soort implementeert die kloof
en heers concept dat we hebben sprak over een veel in collegezaal.
In die zin dat we graag werken slimmer, niet harder, als je verdelen
en heers problemen, en breken ze naar beneden, en dan zet ze samen,
goede dingen altijd gebeuren.
>> Dus de manier waarop die fuseren werkt soort wezen
dat het verdeelt een ongesorteerde array in de helft.
En dan het heeft twee helften van arrays.
En het gewoon sorteert die twee helften.
Het houdt gewoon te verdelen in de helft, in de helft, in de helft tot alles is gesorteerd
en vervolgens recursief zet het allemaal samen.
>> Dus dat is heel abstract.
Dus dit is gewoon een beetje pseudocode.
Heeft dat zin in de manier waarop het draait?
Dus laten we gewoon zeggen dat je een matrix van n elementen, toch?
Als n minder dan 2, kunt u terugkeren.
Omdat je weet dat als er maar één ding moet worden opgelost.
Anders, je de linker helft te sorteren, en dan heb je de juiste helft te sorteren,
en dan samen te voegen.
>> Dus terwijl dat ziet er echt gemakkelijk, in werkelijkheid, het denken over het
soort moeilijk. Omdat je net als, Nou, dat is soort die op zichzelf.
Rechts?
Het draait zichzelf.
Dus in die zin, David geraakt op recursie in de klas.
En dat is een concept we praten over meer.
Het is dat deze twee lijnen hier is eigenlijk gewoon het programma
vertel het aan zichzelf te voeren met verschillende input.
Dus in plaats van zelf lopen met het geheel van n elementen,
je kunt breken in de linkerhelft en de rechterhelft
en weer voer het dan.
>> En dan zullen we kijken naar het visueel, want ik ben een visuele leerling.
Het werkt beter voor mij.
Dus we zullen kijken naar een visueel voorbeeld hier.
>> Laten we zeggen dat we een array, zes elementen, 3, 5, 2, 6, 4, 1, niet gesorteerd.
Oké, er is een heleboel op deze pagina.
Dus als jullie kunt kijken naar de eerste stap hier, 3, 5, 2, 6, 4, 1,
je kunt het in tweeën.
Je hebt 3, 5, 2, 6, 4, 1.
U weet dat deze aren't-- u weet niet of ze naargelang of niet,
dus je blijft breken ze naar beneden, in de helft, in de helft, in half, totdat uiteindelijk,
u slechts één element.
En één element wordt altijd gesorteerd zijn, toch?
>> We weten dat 3, 5, 2, 4, 6, 1, op zichzelf, worden gesorteerd.
En nu kunnen we ze samen terug.
Zodat we weten dat de 3, 5.
We zetten die samen.
We weten dat is gesorteerd.
De 2 is er nog steeds.
We kunnen de 4 en de 6 in elkaar gezet.
We weten dat dat is gesorteerd zodat we dat samen.
En 1 er.
>> En dan moet je gewoon kijkt naar deze twee helften hier.
U heeft de 3, 5, 2, 2, 3, 5.
Je kunt gewoon vergelijken met de begin van alles.
Omdat je weet dat dit wordt gesorteerd en je weet dat dat is opgelost.
Dus dan hoef je niet eens hoeft te vergelijk 5, je gewoon vergelijken met de 3.
En 2 kleiner is dan 3, zodat weet je 2 moet gaan in het einde.
>> Hetzelfde daar.
De 1 moet hier gaan.
En dan als je gaat zetten deze twee waarden elkaar,
je weet dat dit wordt gesorteerd en je weet dat die wordt gesorteerd.
Dus dan de 1 en de 2, het 1 minder is dan 2.
Dat vertelt u dat het 1 moet gaan aan het einde van deze
zonder zelfs maar te kijken naar 3 of 5.
En dan de 4, kunt u gewoon controleren, gaat het recht hier.
Je hoeft niet te kijken naar de 5.
Hetzelfde met de 6.
U weet dat de 6-- het gewoon niet moeten worden bekeken.
>> En zo op die manier, je bent gewoon jezelf te besparen
veel trappen als je vergelijkt.
Je hoeft niet elke vergelijken element tegen andere elementen.
U vergelijkt alleen tegen degenen dat je nodig hebt om het te vergelijken tegen.
Dus dat is een soort van een abstract begrip.
Geen zorgen als het niet heel raken jullie nog recht.
Maar over het algemeen is dit hoe een merge soort werkt.
Vragen, korte vragen, voordat ik verder gaan?
Ja.
>> Publiek: Dus u zegt dat u het 1, en de 4 en de 6
en zet ze in.
Dus niet those-- niet u op zoek naar hen
als afzonderlijke elementen, niet als geheel?
ANDI PENG: Ja.
Dus wat er gebeurt is dat je in principe
zijn het creëren van een nieuwe array.
Zodat u weet dat hier, ik heb twee series van maat 3, rechts?
Zodat u weet dat mijn gesorteerde array moet zes elementen.
Dus je gewoon een nieuwe hoeveelheid geheugen.
Dus je bent een soort van waarbij verspilling van het geheugen,
maar dat doet er niet toe omdat het zo klein is.
Dus je kijkt naar de 1 en je kijkt naar de 2.
En je weet dat het 1 minder dan 2.
Zodat u weet dat 1 op moet gaan Begin al deze.
>> Je hoeft niet eens nodig om kijken naar de 3 en 5.
Dus je weet 1 gaat daar.
Dan moet je in principe afhakken van de 1.
Het is, net als, dood voor ons.
Dan hebben we slechts 2, 3, 5, en 4 en 6.
En dan weet je dat je vergelijk 4 en 2,
oh, de 2 moet er naartoe te gaan.
Dus je plop de 2 naar beneden, je afhakken.
Dus dan hoef je alleen maar de 3 en 5 in de 4 en 6.
En je gewoon blijven hakken het uit totdat je ze in de array.
>> Publiek: Dus je bent altijd vergelijken van de [onhoorbaar]
>> ANDI PENG: Precies.
Dus in die zin, je bent gewoon vergelijken, wezen,
een aantal tegen elkaar getal.
En omdat je weet dat het sorteren, u
hoeft niet te kijken door alle nummers.
Je hoeft alleen maar te kijken naar de eerste.
En dan kun je gewoon plop ze naar beneden, want je weet
ze behoren waar ze moeten behoren.
Ja.
Goede vraag.
>> En als iemand van jullie zijn een beetje ambitieus,
voel je vrij om te kijken naar deze code.
Dit is eigenlijk de fysieke implementatie
hoe we merge soort zou schrijven.
En u kunt zien, het is erg kort.
Maar de ideeën achter Het zijn vrij complex.
Dus als je het gevoel dat het tekenen dit uit in je huiswerk vanavond, voel je vrij om.
>> OK.
David ging ook meer dan dit in het college.
Wat zijn de beste case runtimes, slechtste geval runtimes,
en de verwachte looptijden van merge soort?
Een paar seconden na te denken.
Dit is vrij moeilijk, maar soort intuïtief als je erover nadenkt.
Prima.
>> Publiek: Is het ergste geval n log n?
ANDI PENG: Precies.
En waarom is het n log n.
>> Publiek: Is het niet omdat het exponentieel sneller,
dus het is als een functie van die plaats van simpelweg n
kwadraat of zoiets?
ANDI PENG: Precies.
Dus de reden waarom de runtime op dit n log
n because-- wat bent u doet in al deze stappen?
Je bent gewoon hakken het in de helft, toch?
En dus toen we doen het log, alles wat het doet
is een probleem verdelen in tweeën, in de helft, in de helft, meer helften.
En in die zin, kan je soort elimineren van het lineaire model
die we hebben gebruikt.
Want als je hakken dingen in de helft, het is een log.
Dat is gewoon de wiskundige manier vertegenwoordigen.
>> En dan eindelijk, op het einde, je bent gewoon het maken van een laatste passage door
om ze allemaal op orde te krijgen, toch?
En dus als je gewoon controleren een ding, dat is n.
En dus je bent soort bij elkaar te vermenigvuldigen.
Dus het is alsof je die laatste heb controleren n hier beneden met een log van n
hier boven.
En als je vermenigvuldigen hen, dat is n log n.
>> En zo het beste geval en slechtste zaak en verwacht zijn alle n log n.
Het is ook als een andere soort.
Het is als een soort selectie in die zin dat
maakt niet uit wat uw lijst is, het is gewoon
om hetzelfde te doen elke keer weer.
OK.
Dus zoals jullie kunnen zien, ook al het soort dat we through-- n gegaan
kwadraat, het is niet erg efficiënt.
En zelfs dit n log n niet het meest efficiënt.
Als jullie zijn nieuwsgierig, er is een soort mechanismen
die zo efficiënt dat ze zijn bijna wezen vlak in runtime.
>> Je hebt een aantal log n's.
Je hebt een aantal log log n's.
We niet op hen te raken in deze klasse nu.
Maar als jullie zijn nieuwsgierig, voel je vrij om google, wat is
de meest efficiënte sorteermechanismen.
Ik weet het niet, er zijn sommige echt grappig degenen,
like-- er is wat werkelijk grappig degenen die mensen maken.
En vraag je je af hoe ze ooit gedacht.
Zodat Google, als je wat vrije tijd, op, wat zijn sommige grappige manieren
dat people-- alsook efficiënte ways-- mensen
hebben kunnen allerlei voeren geweest.
OK.
En hier is gewoon een handige kleine grafiek.
Ik weet dat u allen, daarvoor quiz 0, zal in uw kamer waarschijnlijk proberen
te onthouden dat.
Dus dat is leuk in er voor jullie.
Gewoon niet de logica die made-- vergeten waarom deze nummers werden voorkomen.
Als je altijd verloren, maar zorg dat u weet wat de soort zijn.
En je kunt doorlopen ze in je geest
om erachter te komen waarom deze antwoorden die antwoorden.
>> Prima.
Dus we gaan verhuizen op slot te zoeken.
Want die van u die PSET hebben gelezen,
zoeken is ook deel uit van probleem van deze week zet.
U wordt gevraagd uit te voeren twee soorten zoekopdrachten.
Een daarvan is een lineair zoeken en een is een binair zoeken.
>> Dus het lineair zoeken is vrij eenvoudig.
Je wil gewoon om te zoeken element van een lijst om te zien als je het krijgen.
Je hoeft alleen maar om door te herhalen.
Als deze gelijk is iets, je kunt gewoon terug, toch?
Maar degene die we het meest geïnteresseerd in het praten over
binair zoeken, rechts, hetgeen de verdeel en het mechanisme te veroveren die
David werd demonstreren in collegezaal.
>> Vergeet niet het telefoonboek voorbeeld dat hij blijft de opvoeding,
de een dat hij soort van worstelde een beetje aan het afgelopen jaar,
waar u het probleem te verdelen in de helft, in de helft, in de helft, opnieuw en opnieuw,
totdat je vindt wat je zoekt?
En je hebt de runtime van dat ook.
En u kunt zien, het is aanzienlijk efficiënter
dan elke andere vorm van zoeken.
>> Dus de manier waarop we zouden gaan over implementeren van een binaire zoekopdracht
is, als we hadden een array, index 0-6, zeven elementen,
we kunnen kijken in het midden, right-- sorry, als onze vraag first--
als we willen dat de vraag te stellen, doet de array bevat het element 7,
Uiteraard zijn mensen, en met zo'n kleine serie, het is gemakkelijk voor ons
om ja te zeggen.
Maar de weg naar een binaire implementeren zoek zou zijn om te kijken in het midden.
>> We weten dat de index 3 het midden, omdat we
weet dat er zeven elementen.
Wat 7 gedeeld door 2?
U kunt afhakken die extra 1.
Je hebt 3 in het midden.
Zo is reeks 3 gelijk aan 7?
Het klopt niet?
Maar we kunnen een aantal controles te doen.
Is matrix van 3 minder dan 7 of reeks 3 is groter dan 7?
>> En we weten dat het is minder dan 7.
Dus we weten dat, oh, het moet niet in de linker helft.
We weten dat het moet in de rechter helft, toch?
Dus we kunnen gewoon afhakken de helft van de array.
We hebben niet eens aan kijken meer.
Omdat we weten dat de helft van onze probleem--
We weten dat het antwoord in de rechterhelft van ons probleem.
Dus we alleen kijken naar dat nu.
>> Dus nu kijken we naar de midden van wat er over is.
Die index 5.
Wij doen het zelfde check weer en we zien dat het kleiner.
Dus we kijken aan de linkerkant van dat.
En dan zien we dat het inchecken.
Is de array waarde bij index 4 gelijk aan 7?
Het is.
Dus we kunnen echt terug, omdat vonden we de waarde in onze lijst.
Doet de manier waarop ik ging door dat zinvol voor iedereen?
OK.
Ik zal jullie misschien te geven, zoals, drie, vier minuten te achterhalen
hoe dit pseudocode in.
>> Dus stel ik u gevraagd een schrijven functie genaamd search () die terug
een waarde, een Booleaanse waarde, dat waar was of false-- zoals,
waar als je vond het waarde false als je dat niet deed.
En dan was je aangenomen in de waarde die u
zochten naar waarden, die is de array-- oh, ik zeker zet
dat op de verkeerde plaats.
OK.
Anyways, dat zou moeten hebben rechts van waarden geweest.
En dan int n is het aantal elementen in de matrix.
Hoe zou u over het proberen dat probleem in pseudocode?
Ik zal u kerels zoals geven drie minuten om dat te doen.
Nee, ik denk dat er only-- ja, er is een recht hier.
Publiek: Kan ik?
ANDI Peng: Ja, ik heb je.
Is dat werken?
OK, cool.
>> OK.
Oké jongens, we zijn gaan om het te beteugelen.
OK.
Neem dus we hebben dit prachtige gekregen kleine array met n-waarden in.
Ik heb niet de lijnen te tekenen.
Maar hoe zouden we gaan over het proberen om dit te schrijven?
Wil iemand geef mij de eerste lijn?
Als je me wilt het geven eerste regel van deze pseudocode.
>> PUBLIEK: [onverstaanbaar]
Publiek: Je zou willen naar through-- herhalen
PUBLIEK: Gewoon weer een lus?
Publiek: --Voor.
>> ANDI PENG: Dus dit is een beetje lastig.
Denk about-- je wilt te blijven draaien deze lus
over en weer tot wanneer?
>> Publiek: Totdat de [onverstaanbaar] gelijk is aan die waarde.
ANDI PENG: Precies.
Dus je kunt eigenlijk alleen maar write-- kunnen we zelfs vereenvoudigen meer.
We kunnen gewoon een tijdje loop, toch?
Dus je kunt gewoon loop-- we weten dat het een tijdje.
Maar voor nu, ga ik door wat - naar "loop" zeggen?
Loop until-- wat onze eindigend toestand?
Ik denk dat ik het hoorde.
Ik hoorde iemand zeggen.
>> PUBLIEK: Waarden gelijk midden.
ANDI Peng: Zeg het nog eens.
PUBLIEK: Of, totdat de waarde die u zoekt
is het gelijk aan de middenwaarde.
>> ANDI Peng: Wat als het er niet in?
Wat als de waarde die u zoekt voor is eigenlijk niet in deze serie?
PUBLIEK: U keert terug 1.
>> ANDI Peng: Maar wat willen we lus totdat als we een aandoening?
Ja.
>> Publiek: Totdat er maar één waarde?
ANDI Peng: U kunt loop until-- zodat je weet dat je bent
gaan naar een maximale waarde hebben, toch?
En je weet dat je gaat een min waarde, recht?
Want ook dat is iets Ik vergat te zeggen vóór,
dat iets dat kritisch over binaire zoekopdracht
is dat array al wordt gesorteerd.
Want er is geen manier van doen Dit als ze gewoon willekeurige waarden.
Je weet niet of men is groter dan de andere, toch?
>> Zodat je weet dat je max en uw minuten zijn hier, toch?
Als je gaat worden het aanpassen uw maximum in uw minuten en de mid--
laten we gewoon aannemen je mid waarde is gelijk hier--
je gaat in principe lus totdat uw minimum
ongeveer hetzelfde als uw maximum, recht, of als je max is niet hetzelfde als uw min.
Rechts?
Want als dat gebeurt, weet je dat je uiteindelijk hebt geraakt dezelfde waarde.
Dus je wilt loop totdat je min is kleiner dan of gelijk to-- oops,
ten hoogste, andersom around-- max.
>> Wist dat zinvol?
Ik nam een ​​paar pogingen om dat recht te krijgen.
Maar loop tot je maximale waarde in wezen bijna kleiner
dan of gelijk aan uw minimum, toch?
Dat is wanneer je weet die je hebt geconvergeerd.
PUBLIEK: Wanneer zou uw maximale waarde van minder dan het minimum?
ANDI Peng: Als je blijft vast, waarin
is wat we gaan te doen dit.
Slaat dat ergens op?
Minimum en maximum zijn integers dat we waarschijnlijk
gaat te willen creëren om te houden bij waar we naar op zoek.
Omdat de array bestaat ongeacht wat we doen.
Zoals, we zijn niet fysiek afhakken van de array, toch?
We zijn gewoon aanpassen waar we op zoek bent.
Slaat dat ergens op?
>> Publiek: Ja.
>> ANDI Peng: OK.
Dus als dat is de voorwaarde voor onze loop, wat willen we binnenkant van deze lijn?
Wat gaan we te willen doen?
Dus nu, we hebben een max en een min, rechts,
Waarschijnlijk gemaakt hier ergens.
We gaan waarschijnlijk willen een midden, rechts vinden?
Hoe gaan we om in staat om het midden te vinden?
Wat is de mathematical--
PUBLIEK: Max plus min gedeeld door 2.
ANDI PENG: Precies.
Slaat dat ergens op?
En doen jullie zien waarom we niet alleen use-- waarom we dit deden
in plaats van het doen van slechts n gedeeld door 2?
Het is omdat n is een waarde dat zal hetzelfde blijven.
Rechts?
Maar als we passen onze minimale en maximale waarden, ze gaan veranderen.
En als resultaat, onze middelbare zal ook veranderen.
Dus dat is waarom we willen om dit recht te doen hier.
OK.
>> En dan, nu we hebben our-- gevonden ja.
>> PUBLIEK: Even een question-- als je zegt min en max,
gaan we ervan uit dat het is al naargelang?
>> ANDI Peng: Ja, dat is eigenlijk een Voorwaarde voor een binary search,
dat je moet weten dat het opgelost.
Dat is waarom soort, schrijf u in uw probleem ingesteld voordat uw binaire zoekopdracht.
OK.
Dus nu we weten waar onze middelpunt wordt, wat wil je hier doen?
>> PUBLIEK: We willen vergelijken dat voor het andere.
ANDI PENG: Precies.
Dus je gaat vergelijken medio aan waarde, toch?
En wat betekent dat vertellen ons als we vergelijken?
Wat willen we daarna doen?
>> Publiek: Als de waarde groter is dan het midden, willen we er afgesneden.
ANDI PENG: Precies.
Als de waarde groter is dan het midden, we zijn
gaat willen deze veranderen minimum en Maxes, toch?
Wat willen we veranderen?
Dus als we weten wat de waarde is ergens hier, wat je doen we om te veranderen?
We willen onze veranderen minimaal tot medio te zijn, toch?
En dan anders, als het in deze de helft, wat willen we veranderen?
>> Publiek: Uw maximum.
ANDI PENG: Ja.
En dan ben je gewoon te houden looping, toch?
Want nu, na één iteratie door middel van, heb je een max kreeg hier.
En dan kun je een mid herberekenen.
En dan kun je vergelijken.
En je gaat om door te gaan totdat de min en Maxes
hebben in wezen geconvergeerd.
En dat is als je weet dat u het einde van het hebt getroffen.
En of je hebt het gevonden of je hebt niet op dat punt.
>> Betekent dit zinvol om iedereen?
OK.
Dit is erg belangrijk, want je hebt
om dit te schrijven in de code vanavond.
Maar jullie hebben een redelijk goed gevoel van wat je moet doen,
wat goed is.
OK.
Dus we hebben ongeveer zeven minuten over sectie.
Dus we gaan praten over Dit PSET dat we moeten doen.
Dus de PSET verdeeld in twee helften.
De eerste helft betreft implementeren van een vondst
waar je een lineair zoeken te schrijven, een binary search, en een sorteer-algoritme.
>> Dit is dus het eerste tijd in een PSET, waar
geven we jullie wat heet verdeelsleutel, die code
die we hebben pre-geschreven, maar net vertrokken sommige stukken af
voor u om te schrijven beëindigen.
Dus jullie, als je kijkt naar deze code, zou je echt bang.
Als je gewoon wilt, ahh, ik weet niet wat dat doet,
Ik weet het niet, als, dat lijkt zo ingewikkeld, ahh, ontspannen.
Het is ok.
Lees de spec.
De spec zal precies uitleggen Wat al deze programma's aan het doen zijn.
>> Bijvoorbeeld, generate.c een programma die zal komen met uw PSET.
Je hoeft niet echt aan te raken, maar u moet begrijpen wat het doet.
En generate.c, alles wat het doet is of het genereren van willekeurige getallen
of u kunt het een zaadje, zoals een afgesproken aantal dat nodig is,
en genereert meer nummers.
Dus er is een specifieke manier om implementeren generate.c waarin
u kunt gewoon een stelletje getallen voor u om uw andere methodes te testen op.
>> Dus als je wilde, voor Zo test je vondst,
je zou willen generate.c lopen, genereren een heleboel nummers,
en voer uw helpers functie.
Uw helpers functie is waar je bent daadwerkelijk fysiek schrijven van code.
En denk aan helpers als een bibliotheek bestand je schrijft dat de vondst roept.
En zo binnen helpers.c, zult u doen het zoeken en sorteren.
>> En dan zul je in wezen zet ze allemaal samen.
De spec zal u vertellen hoe u zet dat op de opdrachtregel.
En je zult in staat zijn om te testen of niet je sorteren en zoeken werken.
Cool.
Heeft iemand al begonnen en ondervonden problemen of vragen
ze nu hebben met dit?
OK.
>> Publiek: Wacht.
Ik heb een vraag.
>> ANDI PENG: Ja.
>> Publiek: Dus ik begon te doen het lineair zoeken in helpers.c
en het was niet echt aan het werk.
Maar dan later, vond ik dat we gewoon hebben om het te schrappen en te doen binaire zoeken.
Dus maakt het uit als het niet werkt?
>> ANDI Peng: Kort antwoord is nee.
Maar aangezien we niet--
Publiek: Maar niemand eigenlijk controleren.
ANDI PENG: We zijn nooit gaan om te zien dat.
Maar wilt u waarschijnlijk te maken ervoor dat uw zoekopdracht werkt.
Want als je lineaire search werkt niet,
dan is de kans groot dat uw binaire zoek gaat niet zo goed werkt.
Want je hebt gelijk logica beiden.
En nee, het maakt eigenlijk niet uit.
Dus de enige die je draaien in zijn soort en binaire zoeken.
Ja.
>> En ook veel kinderen waren proberen helpers.c stellen.
Je bent niet echt toegestaan te doen, omdat helpers.c
heeft geen hoofdfunctie.
En dus moet je alleen zijn eigenlijk het samenstellen
genereren en te vinden, want gesprekken vinden helpers.c en de functies daarbinnen.
Dus dat maakt het debuggen een pijn in de kont.
Maar dat is wat we moeten doen.
PUBLIEK: U maken allemaal gewoon, toch?
ANDI Peng: je kunt gewoon maken allemaal zo goed, ja.
OK.
Dus dat is het in termen van wat de PSET vraagt ​​u allen te doen.
Als u vragen hebt, voel vrij om te vragen na sectie.
Ik zal er zijn voor, zoals, 20 minuten.
>> En ja, de PSET's echt niet zo slecht.
Jullie moeten zijn OK.
Deze, volg gewoon richtlijnen.
Soort hebben een gevoel van, logisch, wat dient te gebeuren en je komt wel goed.
Wees niet te bang zijn.
Er is veel van de code er al geschreven.
Wees niet te bang zijn als je dat niet doet begrijpen wat dat allemaal betekent.
Als het een stuk, het is helemaal prima.
En kom naar de kantooruren.
Wij helpen u een kijkje nemen.
>> Publiek: Met de extra functies, kijken we die op?
>> ANDI Peng: Ja, dat zijn in de code.
In het spel van 15 de helft van het is al voor u geschreven.
Dus deze functies zijn reeds in de code.
Yep.
Prima.
Nou, beste van geluk.
Het is een walgelijk dag.
Dus hopelijk jullie niet te voelen slecht over het verblijf binnen en codering.