>> Spreker 1: Hey almal!
Welkom terug na afdeling.
So bly so baie van julle albei hier om te sien, en almal wat aanlyn kyk.
So, soos gewoonlik welkom terug.
Ek hoop dat julle almal het 'n pragtige naweek, vol rus, ontspanning.
Dit was 'n pragtige uit gister.
So, ek hoop jy geniet die buitelug.
>> So eers 'n paar van die aankondiging.
Gradering.
So, moet die meeste van julle gekry het 'n e-pos van my oor jou Scratch Pset,
sowel as die formaat vir Pset 1.
So, net 'n paar dinge.
Maak seker dat jy check50 te gebruik in style50.
Dit is bedoel om te wees hulpbronne vir julle,
om seker te maak dat jy kry maak soveel punte as wat jy kan
sonder onnodig verloor het.
So, dinge soos styl is baie belangrik.
Ons gaan om af te neem, want dit.
Sommige van julle kan reeds opgemerk dat van jou Pset.
En check50 is net 'n baie maklike manier om seker te maak
dat ons eintlik is terug wat moet teruggestuur word aan die gebruiker,
en dat alles is goed werk.
>> Op die tweede noot, maak seker dat jou oplaai dinge aan die korrekte gids.
Dit maak my lewe net 'n bietjie meer moeilik
As jy Pset 2 oplaai in Pset 1 want toe ek aflaai dinge,
hulle nie korrek laai.
En ek weet dit is 'n bietjie onstabiel in 'n stelsel om gewoond te raak aan,
maar net super wees versigtig, al is dit net vir my,
sodat wanneer jy kry e-pos op soos 02:00 en ek is gradering.
Indien nie want ek het om te kyk alles rondom jou Pset.
Cool.
>> Ek weet dit is vroeg, maar ek heeltemal het geneem onkant
deur 'n opstel wat as gevolg van hierdie Vrydag, wat my professore is net soos, o ja.
Onthou, jy het 'n opstel gevolg op Vrydag.
So, ek weet niemand hou na te dink oor midterms,
maar jou eerste toets is op 15 Oktober wat Oktober is die begin van hierdie week.
So, is dit dalk gouer wees as wat jy verwag is nie.
Sodat jy nie afgegooi betrap toe Ek noem die volgende week se artikel wat o,
jou quiz volgende week, het ek gedink Ek sal vir jou 'n bietjie meer
van 'n kop nou.
>> So, jou probleem stel, nommer drie.
Hoe mense lees die spec uit nuuskierigheid?
OK.
Ons het 'n paar.
Soort van uit die verlede week, maar dit is OK.
Ek weet dit was 'n pragtige uit.
So Breek Uit.
Beslis nadat jy gedoen te kry vandag lees jou spec ten minste
probeer om soos die aflaai verspreiding kode en hardloop
soos die eerste aanvanklike ding wat hulle vra om jou te.
Want ons is met behulp van verspreiding-kode en 'n biblioteek
dat ons net using-- --It is net die tweede keer dat ons hierdie Pset gedoen het,
gek dinge kan gebeur met jou apparaat,
en jy wil om te vind dat nou uit versus later.
>> Want as dit is Donderdagaand of dit Woensdagaand en vir een of ander rede
jou toestel nie net nie wil om te hardloop met die biblioteek
of met die verspreiding kode, wat beteken dat
jy kan nie eens begin om die kodering.
Omdat jy nie kan sien om te sien of dit werk.
Jou nie eers in staat wees om om te sien of dit stel.
Jy wil vroeg in die sorg van diegene te neem die week, toe jy my nog kan e-pos
of een van die ander TFS, en ons kan kry die vaste.
Want dit is kwessies wat gaan om jou te stop
uit die maak van enige werklike vordering.
Dit is nie soos 'n fout, wat jy kan net soort van spring oor.
As jy probleme met jou toestel of verspreiding kode,
jy regtig wil om te kry wat geneem sorg van vroeër eerder as later.
So selfs as jy nie eintlik nou eers begin kodering, laai die verspreiding
kode, lees die spec, maak seker alles is daar werk.
OK?
As jy net kan doen wat ek jou lewe belowe, sal makliker wees.
En so gaan jy waarskynlik om dit te doen nou reg?
OK.
So, enige vrae is daar?
Enige logistieke dinge?
Almal is goed?
OK.
>> Disclaimer vir dié van jy in die kamer en aanlyn.
Ek gaan om te probeer om oor te skakel tussen PowerPoint in die toestel
want ons gaan te wees om 'n paar kodering
vandag deur die gewilde vraag van die anonieme voorstel poll Ek het verlede week.
So, sal ons doen 'n paar kodering.
So, as jy ouens wil ook te brand jou toestelle,
en jy moet gekry het 'n e-pos van my, met 'n voorbeeld lêer.
Voel asseblief vry om dit te doen.
>> So, ons gaan om te praat oor GDB, wat 'n debugger.
Dit gaan om jou te help soort uit te vind waar
dinge verkeerd gaan in jou kode.
Dit is regtig net 'n manier vir jou om te stap deur jou kode as dit gebeur,
en in staat wees om uit te druk veranderlikes of sien wat regtig aangaan
onder die enjinkap verse jou program net loop, is dit soos onderbrekings,
en jy soos, geen idee wat net hier gebeur het.
Ek weet nie watter lyn dit nie by.
Ek weet nie waar dit verkeerd gegaan het.
So, is GDB gaan om jou te help met dit.
Ook, as jy besluit om te voortgaan ja, en neem 61,
dit sal regtig, regtig jou beste vriend, want ek kan jou vertel
want ek gaan deur middel van die klas.
>> Ons gaan om te kyk na binêre soek, en as julle onthou
die groot telefoon boek voorbeeld skouspel uit die klas.
Ons sal word implementering nie, en loop deur dat 'n bietjie meer,
en dan gaan ons deur middel van vier verskillende soorte, wat borrel,
Keuring, plasing, en saam te smelt.
Cool.
So, GDB soos ek genoem het, is 'n debugger.
En dit is soort van die groot dinge, die groot funksies of opdragte
dat jy binne GDB gebruik, en ek sal loop jou deur 'n demonstrasie van dit in 'n tweede.
>> So, dit is nie net gaan abstrakte te bly.
Ek sal probeer en maak dit as konkrete as moontlik vir julle.
So, breek.
Dit sal óf breek soos sommige nommer, wat
verteenwoordig 'n lyn in jou program, of jy kan noem 'n funksie.
So, as jy sê breek hoof, dit sal stop by die hoof,
en laat jou deur daardie funksie te loop.
>> Net so, as jy 'n paar eksterne funksioneer soos Swap of Cube,
dat ons kyk na verlede week.
As jy sê breek een van daardie, wanneer jou program treffers wat,
dit sal wag vir jou om te vertel dit wat om te doen.
Voor dit sal net so voer jy kon eintlik stap in die funksie
en kyk wat aangaan.
So, Volgende, spring net oor die volgende lyn, gaan oor funksies.
Stap.
Dit is al die klein abstrakte.
So, ek gaan net om te loop deur hulle maar jy sal dit sien in die gebruik in 'n tweede.
>> Stap in 'n funksie.
So as ek gesê het, soos met Swap, sou dit
toelaat dat jy eintlik asof jy soos fisies binne trap,
jy kan mors met daardie veranderlikes, druk uit wat hulle is, sien wat gaan aan.
Lys sal letterlik net druk uit die omliggende kode.
So, as jy soort van vergeet waar jy in jou program,
of jy wonder wat gaan aan om dit
dit sal net druk 'n segment van soos vyf of ses lyne rondom.
So, kan jy georiënteerde raak oor waar jy is.
>> Druk 'n paar veranderlike.
So, as jy die sleutel hou in Caesar, dat ons sal kyk.
Jy kan sê Print Sleutel by enige punt.
Dit sal jou vertel wat die waarde is dus dat, miskien iewers langs die pad,
jy overwrote jou sleutel.
Jy kan eintlik sê dat omdat jy kan eintlik sien dat waarde.
>> In die plaaslike bevolking, net druk uit jou plaaslike veranderlikes.
So, wanneer jy in 'n lus, en jy wil net om te sien soos, ag.
Wat is my ek?
Wat is hierdie sleutel waarde dat ek hier inisialiseer?
Wat is die boodskap op hierdie punt?
Dit sal net druk al van daardie, sodat jy
nie individueel te sê Print I. Druk boodskap.
Print Sleutel.
En dan vertoon.
Wat nou gebeur is dat as jy stap vir stap deur die program,
dit sal net seker maak dat dit vertoon 'n sekere veranderlike
op elke punt.
Sodat jy also-- --it is soort van 'n kortpad waar
jy hoef nie om aan te hou soos, ag.
Print Sleutel of Print I. Dit het net sal outomaties doen dit vir jou.
>> So, met wat, ons gaan om te sien hoe dit gaan.
Ek gaan om te probeer en skakelaar oor my toestel.
Sien as ek dit kan doen.
Almal.
Ons is net gaan om dit te weerspieël.
Daar is niks gek op my laptop anyways.
OK.
Dit moet aan hierdie een wees.
Dit is so klein.
Kom ons kyk of ons dit kan doen.
>> OK.
Alice is natuurlik sukkel hier net 'n bietjie,
maar ons sal dit kry in 'n momento.
OK.
Ons is net gaan om dit te verhoog.
OK.
Kan almal soort van sien dat?
Miskien 'n bietjie?
Ek weet dit is 'n bietjie klein.
Jy kan nie heeltemal uit te vind hoe dit groter te maak.
As iemand weet.
Is daar iemand wat weet hoe om dit groter te maak?
OK.
Ons gaan aan die gang met dit.
Maak nie saak nie anyways, want dit is net dit is die kode wat julle moet
het.
>> Wat is meer belangrik is die terminale hier.
En ons het hier Hoekom is dit so klein?
Instellings.
O.
Ware Ike.
Hoe is dit?
Daar uit.
Is dit beter vir almal?
OK ,.
Cool.
>> Jy weet wanneer jy in 'n CS klas tegniese probleme
is soort van 'n deel van the-- So, laat ons duidelik nie.
OK.
So, hier in afdeling wat ons hier gehad het.
Caesar is 'n uitvoerbare lêer.
So ek het dit gemaak.
So, een ding om te besef met GDB is dat dit werk net op uitvoerbare lêers.
So, jy kan nie loop dit op 'n dotsy.
Jy moet eintlik maak seker dat jou kode stel,
en dat dit eintlik kan uitgevoer word.
>> So, maak seker dat indien dit nie gebeur nie stel, kry dit saam te stel,
sodat jy kan soort van loop deur dit.
So, GDB om te begin, alles wat jy doen, Gloria tipe GDB, en dan net die
lêer wat jy wil.
Ek het altyd spelfoute Caesar.
Maar jy wil om seker te maak want dit is 'n uitvoerbare,
tie se dot flits sodat beteken jy gaan
hardloop CSI jy gaan om uit te voer hierdie lêers óf met die debugger.
OK.
So, jy doen nie, jy hierdie soort van brabbeltaal.
Dis net alles oor debugger.
Jy het nie regtig te bekommerd wees oor dit nou.
En as jy sien, ons het hierdie oop parens, BBP, naby parens,
en net soort van lyk Ons opdrag lyn, reg?
>> So, wat ons wil do-- --So, Die eerste ding
is wat ons wil om te kies 'n plek om dit te breek.
So, daar is 'n fout in hierdie Caesar program
dat ek stel dat ons gaan om uit te vind.
Dit Wat beteken dit is wat dit neem om die insette Barfoo in hoofletters, en vir een of ander rede
dit nie verander A. Dit laat net dit alleen, is alles anders korrek is,
maar die tweede brief A bly onveranderd.
So, ons gaan om te probeer en uit te vind waarom dit is.
So, die eerste ding wat jy tipies wil doen wanneer jy begin op GDB
is uit te vind waar om dit te breek.
>> So Caesar is 'n mooi kort program.
Ons het net een funksie, reg?
Wat was ons funksie in die keiser?
Daar is net een funksie, Main reg?
Main is 'n funksie vir al jou programme.
As jy het nie Main, kan ek 'n bietjie bekommerd nou,
maar ek hoop julle almal het Main daar.
So, wat ons kan doen, is om ons kan net breek Main, net soos dit.
So, dit sê, OK.
Ons stel ons breekpunt een daar.
>> So, nou die ding om te onthou, is die keiser neem een ​​command line argument reg
en ons het nie gedoen wat enige plek nie.
So, wat jy doen, is wanneer jy eintlik gaan na afloop
die program, 'n program wat jy hardloop in GDB wat moet command line
argumente, jy gaan om insette wanneer jy die eerste keer begin om dit te draai.
So, in hierdie geval, ons doen Begin met 'n sleutel van drie.
En dit sal eintlik begin.
>> So, as jy hier sien, het ons ' As RC is nie gelyk aan 2.
So as julle almal lêer wat ek uitgestuur het
sal jy sien dat dit is soos die eerste reël ons vernaamste funksie, reg?
Dit is om te kyk of ons 'n die korrekte aantal argumente.
So, as jy wonder As RC korrek is,
jy iets net soos Print RC kan doen.
RC is twee, wat wat ons verwag het, reg?
>> Dus, kan ons nou volgende, en gaan voort deur middel van.
So, ons het 'n paar belangrike daar.
En ons kan druk ons ​​sleutel om seker te maak dat die inligting korrek is nie.
Interessant.
Nie heeltemal wat ons verwag het.
So, een ding om te besef met GDB ook is
dat dit nie totdat jy eintlik getref Volgende, dat die lyn wat jy nou net gesien
is eintlik uitgevoer.
So, in hierdie geval Sleutel het nie toegeken is nie.
So, Sleutel is 'n gemors waarde wat jy sien op die bodem daar.
Negatiewe $ 120-- --It se een biljoen en iets vreemd dinge reg?
Dit is nie die sleutel wat ons verwag het.
Maar as ons getref Volgende, en dan moet ons probeer Print sleutel, dit is drie.
>> Almal sien dat?
Dus, as jy iets dat jy soos, wag.
Dit is heeltemal verkeerd is, en ek weet nie
hoe dit sal gebeur nie, want al wat ek wil te doen, is wys 'n nommer, 'n veranderlike,
probeer slaan Volgende, probeer om druk dit weer, en sien as dit werk.
Want dit gaan net om uit te voer en eintlik iets wys nadat jy
getref Volgende.
Sin maak vir almal?
Uh huh?
>> Spreker 2: Wanneer jy ewekansige getalle wat beteken dit?
>> Spreker 1: Dis net lukraak.
Dis net gemors.
Dit is net iets wat jou rekenaar sal lukraak toeken.
Cool.
So, nou kan ons beweeg deur, en so nou het ons hierdie eenvoudige teks GetString.
So, laat my net stel wat sal gebeur wanneer ons Next hier getref.
Ons GDB soort verdwyn, reg?
Dit is omdat GetString is nou die uitvoering, reg?
So, toe ons sien plain text gelyk GetString, oop parens en parens,
en ons getref Volgende, wat eintlik nou uitgevoer word.
So, is dit wag vir ons insette iets.
>> So, gaan ons insette ons kos wat is wat dit versuim as ek jou vertel
en wat net sê dat dit klaar te voer, dat die geslote
bracket beteken dit opwindende uit daardie lus.
Dus, kan ons getref Volgende, en nou, want ek is seker dat jy al bekend van Caesar,
dit is, wat is hierdie lyn gaan doen.
Dis vir Int ek gelyk 0, N is gelyk aan Strlen, gewone teks, en dan
Ek is minder as N, Ek, plus, plus.
Wat is hierdie lus gaan doen?
Maak jou boodskap.
Cool.
So, laat ons begin om dit te doen.
>> So, moet hierdie toestand pas, vir ons eerste een?
As dit is 'n B, dit is plain text I. Ons kan inligting oor ons locals kry.
So, ek is nul, en as ses, wat ons verwag, en ons sleutel is drie.
Al wat sin maak, reg?
Hierdie syfers is almal presies wat hulle behoort te wees.
So, neurie?
SPREKER 3: Ek het ewekansige nommers vir my.
Spreker 1: Wel, kan ons --we check-- kan gesels oor wat in 'n tweede.
Maar jy moet wees om hierdie.
So, as ons 'n kapitale B vir ons eerste een,
hierdie toestand moet dit vang, reg?
So, as ons getref Volgende, sien ons dat hierdie As eintlik voer.
Want as jy volgende saam in jou kode,
hierdie lyn hier, waar plain text ek vervang met hierdie rekenkundige,
net voer indien die As toestand is korrek reg?
>> GDB is slegs gaan om jou te wys dinge wat eintlik die uitvoering.
So as dit Indien die toestand nie nagekom is, dit is net gaan na die volgende lyn.
OK?
So, ons het dit.
Dit bracket beteken dit gesluit nou uit daardie lus.
So, dit gaan om weer te begin.
Net soos dit.
So, dat ons inligting kan kry oor ons plaaslike inwoners hier,
en ons sien dat ons eerste brief verander het, reg?
Dit is nou 'n E, soos dit moet wees.
Dus, kan ons voortgaan op.
>> En ons het die tjek.
En die tjek moet werk, reg?
Dit is A. Dit moet verander word drie letters vorentoe.
Maar as jy sien, ons kry iets anders.
So in hierdie geval hier, dit gevang dit, en so hierdie lyn uitgevoer word,
wat aangepas ons B. Maar, in hierdie geval hier,
Ons het dit net oorgeslaan het, en na die [? L siff. ?]
So iets gaan daar aan.
Wat dit is wat jy vertel is dat, ons weet dat dit hier moet vang,
maar dit is nie.
Kan iemand sien wat ons probleem is in die lyn?
Dit is 'n baie klein ding.
En jy kan ook kyk na jou kode.
Dit is ook line-- vergeet wat lyn is dit in there-- maar dit is in die [onhoorbaar].
Ja?
>> SPREKER 4: Dit is op die groter as bladsy as jy dit lees in die boek.
Spreker 1: Presies.
So, kon die debugger nie vertel jy dit nie, maar die debugger
kon kry jy af na 'n lyn dat jy weet nie in werking is.
En soms, wanneer veral later in die semester, wanneer
jy met 'n honderd, 'n honderd paar reëls van die kode, en jy
Ek weet nie waar dit versuim, dit is 'n goeie manier om dit te doen.
So, ons het ons fout.
Jy kan dit los in jou lêer, en dan kan jy dit weer te hardloop,
en alles sal goed werk.
En die grootste ding is Dit kan lyk soos, OK.
Ja.
Cool.
Jy het geweet wat jy soek.
So, jy het geweet wat om te doen.
>> GDB kan wees super nuttig omdat jy Al hierdie dinge kan uitdruk dat jy
sou nie.
Dit is baie meer nuttig is as printf.
Hoeveel van julle gebruik soos printf state
om uit te vind waar 'n fout was, reg?
So, met hierdie, jy doen nie het om aan te hou terug,
en graag kommentaar in Printf, of kommentaar het,
en uit te vind wat jy moet druk.
Dit eintlik net kan jy stap vir stap deur, druk dinge
as jy gaan, so, kan jy sien hoe hulle verander in reële tyd,
as jou program loop.
>> En dit neem 'n bietjie bietjie gewoond raak aan.
Ek sou raai net soort om 'n bietjie gefrustreerd met dit
vir nou.
As jy oor die spandeer 'n uur volgende week leer hoe GDB om te gebruik,
sal jy jouself red so baie tyd later.
En letterlik. ons vertel hierdie mense elke jaar,
en ek onthou toe ek die klas, ek was soos ek sal goed wees.
No.
Pset 6 gekom en ek was soos, ek gaan leer
hoe GDB te gebruik, want ek doen nie weet wat gaan hier aan.
>> So as jy die tyd, so neem gebruik dit op kleiner programme
wat jy gaan wees werk, soos die werk
deur iets soos Visionare, soos hierdie.
Of as jy wil ekstra oefening, ek is seker Ek kon kom met karretjie programme,
vir jou om te ontfout as jy wil.
>> Maar as jy net 'n tyd neem om te kry gebruik om dit, net speel rond met dit,
dit sal regtig dien jou goed.
En dit is regtig een van daardie dinge wat jy net
het om te probeer, en jou hande vuil kry met, voordat jy regtig dit verstaan.
Ek het regtig net een keer verstaan ​​dit Ek moes debug dinge met dit,
en dit is baie lekkerder om 'n idee te hê van hoe om vroeër eerder as later te ontfout.
OK.
Cool.
Ek weet dit is soort van soos 'n crash kursus in GDB,
en ek sal beslis werk om hierdie groter volgende keer te kyk.
Cool.
>> So, as ons gaan terug na ons PowerPoint.
Is dit gaan om te werk?
AWH.
Ja.
OK.
So, as jy ooit enige van nodig diegene weer, daar is die lys.
So binêre soek, wat almal onthou die groot skouspel van Dawid
rip telefoon boeke in die helfte.
Ek het nie regtig kry nie die telefoon boeke nie,
want soos waar doen jy kry telefoon boeke hierdie dae?
Ek weet regtig nie.
Die binêre soek.
Is daar iemand onthou hoe binêre soek werk?
Enigeen by almal?
Ja?
SPREKER 5: Jy weet wanneer jy kyk na wat die helfte
dit sou in wees, op grond van dat, en ontslae te raak van die ander helfte.
>> Spreker 1 Presies.
So, binêre soek, dit is soort van a-- --we graag noem dit verdeel en oorwin.
So, wat jy doen, is jy kyk in die middel,
en jy sal sien as dit ooreenstem met wat jy soek.
En as dit nie gebeur nie, dan probeer om jou te uit te vind, gaan dit gelaat word
half of die regter helfte.
So, kan dit wees as jy op soek is na op iets wat analfabeet,
jy sien, o.
Maak Allison kom voor M?
Ja.
So, gaan ons kyk na die eerste helfte.
>> Of dit kan wees soos met nommers.
Enigiets wat jy kan vergelyk, kan dit gesorteer word.
Jy kan binêre soektog op gebruik.
So, almal onthou hierdie grafiek of wat dit is nie?
Dit is Asymptotische kompleksiteit.
So, hierdie grafiek net beskryf hoe lank dit
neem jou 'n probleem op te los as jy verhoog die aantal van die dinge wat
wat jy gebruik.
>> So, ons het N, wat is lineêr tyd.
As N meer as twee, wat effens beter, groei steeds super vinnig.
En dan het ons Teken, wat wat ons beskou as binêre soek.
As ons sien, as jou probleem kry veel en veel groter,
die tyd wat dit neem om dit op te los nie regtig verhoog dat baie.
Dit is soos 'n vergelykbare hier in die begin.
Jy is soos, OK.
Enigiets hier nie regtig saak watter een wat ons gebruik,
maar jy kry uit 'n miljoen, 'n miljard.
Jy probeer some-- --you're te vind probeer om 'n naald in 'n hooimied te vind.
>> Ek dink jy wil hierdie probleem.
Jy wil hierdie kompleksiteit, nie lineêr want vir alles wat jy
weet wat jou gaan soek word deur elke individuele naald ding van hooi,
probeer om te kyk vir jou naald.
En dit is nie te lekker in my opinie.
Ek hou van vinnig.
Ek hou van doeltreffende.
En as hardwerkende studente jy ouens is, weet jy slimmer te werk,
nie harder soort ding, hoe jy kan maak om hierdie algoritmes.
>> So, ons gaan om te loop deur net 'n vinnige voorbeeld.
Ek dink jy ouens moet 'n hand op binêre soek,
maar in die geval iemand is 'n bietjie vaag, dit wil versterk,
ons gaan net gaan deur 'n voorbeeld hier.
Dus, is ons op soek na as die skikking bevat sewe.
>> So, die eerste ding wat ons doen, is om kyk in die middel, reg?
En ook jy gaan word kodering Binêre soek in net 'n tweede.
So, dit gaan pret wees.
So ons kyk in die middel bietjie skikkings 3.
Maak 3 gelyke 7?
Nie.
Dit is ses.
So, is dit minder as of groter is as sewe?
Minder as.
Ja.
Nice job ouens.
Ek voel ek soos ek moet het lekkergoed, want ek
wil dit uit te gooi in die meter.
Dit is wat ek gaan volgende week te doen.
Dit sal verseker dat jy ouens skerp.
>> So, gooi ons weg wat eerste helfte, reg?
dit was minder as.
ons weet dat alles op daardie linkerkant
gaan minder wees as wat ons is eintlik op soek na.
So, daar is geen behoefte om te aandag te gee aan dit.
Net nie vergeet nie.
So, nou is ons kyk na ons regterkant, en ons kyk na die middel daar,
en nou is dit nege.
So, 9 is-- --Everyone?
Groter is as wat ons is soek, reg?
So, ons gaan om te gooi alles weg aan die regterkant.
Soos dit.
Nou, is al wat ons gelaat met een.
So ons kyk, is hierdie een wat Ons is op soek na? dit is.
Ons het gevind wat ons wou hê.
So het ons klaar is.
Bilinear Search.
>> En as jy sien, ons het sewe insette daar.
Dit het ons het net soos drie keer, Maar as jy doen soos 'n miljard,
julle weet hoe baie stappe wat dit sou neem as ons het 4000000000 dinge?
Enige raaiskote?
Dit is 32.
32 stappe om iets te vind in 'n 4000000000
element skikking gevolg van magte van twee.
So twee is tot 32, is tot vier miljard gestyg.
>> So mooi mal hoe jy nog steeds binne soos 'n redelik klein aantal stappe
om iets te vind in 4000000000 elemente.
So op daardie noot, ons gaan om dit te kodeer
sodat julle kan eintlik soort van sien hoe dit werk.
Alle reg, sodat julle kan kode.
Ek gaan julle te laat praat vir 'n bietjie.
Kry mense om jou te leer ken, wat wat iemand wou van die laaste artikel.
>> So kry die mense om jou te leer ken.
Praat vir 'n bietjie.
En al wat ek wil graag van jou ouens is nou net
probeer om 'n uiteensetting van pseudokode te skep.
OK?
Whoa.
Al wat ek wil van julle ouens is jy net gaan in hierdie geval, terwyl te vul.
So het ek hierdie boonste stel en laer perke wat
verteenwoordig die begin en einde van ons reeks.
En jy gaan eintlik loop deur en uit te vind
wat ons doen in hierdie while lus.
>> So as jy kan uitvind out-- Ek het 'n wenk there-- wat die gevalle
dat ons hier?
So as jy wil om uit te vind die gevalle, sal ons pseudokode diegene
en dan sal ons werklik kodeer hulle.
En dit gaan wees, het ek dink, hopelik sal dit
'n bietjie makliker as wat jy verwag.
Want dit is nie dat veel kode, eintlik, wat is regtig cool.
>> Mm-hm?
>> STUDENT: [onhoorbaar]?
INSTRUCTOR: Ja.
Daar was iets te vind in die middel.
>> STUDENT: So ons kan gebruik nie.
OK.
>> INSTRUCTOR: Perfect.
So wat is die eerste ding wat ons moet doen.
So vind die middel.
Groot.
So jy het 'n idee van hoe ons kan eintlik vind die middel met 'n kode?
>> STUDENT: Ja.
N meer as 2?
INSTRUCTOR: So n meer as 2.
So een ding om te onthou, is dat jou boonste en onderste grense verander.
Ons hou versmoor die deel van die skikking wat ons soek na.
So n meer as 2 sal net werk vir die eerste ding wat ons doen.
So neem die boonste en onderste in ag, Hoe kan ons kry dat die middel element?
Want ons wil die middel tussen die boonste en onderste, reg?
Mm-hm?
>> STUDENT: [onhoorbaar].
>> INSTRUCTOR: So ons het 'n paar middel.
En dit sal die boonste plus laer as 2 wees.
Awesome.
Daar gaan ons.
Een lyn af.
Julle is op jou pad.
So nou dat ons ons middel, doen wat ons wil doen?
Net in die algemeen.
Jy hoef nie om dit te Code.
Ja.
STUDENT: [onhoorbaar]?
INSTRUCTOR: So is dit plus omdat jy vind die gemiddeld tussen die twee
van hulle.
So as jy dink van hulle as soort verhoog in van die kante,
dink oor dit as jy nader die middel, jy wil soos dit.
So as jy aan weerskante van die middel, en ons het soos 5 en 7.
Wanneer jy hulle voeg julle saam kry 12, jy verdeel deur 2, 6.
>> Soms is dit moeilik om te verduidelik waarom dit werk,
maar as jy deur te werk 'n voorbeeld soms,
dit sal jou help om uit te vind of dit plus of minus moet wees.
Ja.
>> STUDENT: [onhoorbaar] presies in die middel
As hulle 'n saak waar daar is 'n baie kleiner getalle
en soos een groot aantal?
>> INSTRUCTOR: So al wat jy moet is die middel van die skikking.
So as jy 'n klomp van die klein getalle en dan 'n baie groot aantal
aan die einde is, beteken dit nie saak nie.
Al wat saak maak, is dat hulle gesorteer, jy moet net
wil om te kyk na die middel van die skikking, want jy is nog steeds
sny jou probleem in die helfte.
Cool.
So nou dat ons die middel, wat doen ons nou?
>> STUDENT: vergelyk.
INSTRUCTOR: Die vergelyk.
So vergelyk middel tot value_wanted.
Cool.
So jy sien hier het ons 'n hierdie waarde wil ons hier.
Onthou, dit is 'n skikking.
So middel verwys na die indeks.
So wil ons waardes van die middel te doen.
Moenie vergeet as jy wil , dubbel gelykes te vergelyk.
Jy doen enkele gelyk is jy net gaan om dit te toewys,
en dan, natuurlik, dit is gaan die waarde wat jy wil wees.
So dit nie doen nie.
>> So ons gaan om te sien of die waardes by die middel
gelyk is aan die waarde wat ons wil hê.
Moenie jou draadjies vergeet nie.
Dropbox moet weggaan.
So wat doen ons in hierdie geval?
As dit is wat ons wil om terug te keer?
Ons probeer om te sê.
>> STUDENT: Druk af.
>> INSTRUCTOR: Wel, ons wil nie te druk nie.
So dit is 'n Bool hier, so ons wil terugkeer waar of vals is.
Ons sê, is hierdie getal 'n [? RRA? ?] So as dit is,
Ons het net stuur dit waar is.
As ek kan spel waar.
>> STUDENT: Hoekom sal jy nie terug nul?
INSTRUCTOR: So jy kan terugkeer nul as jy wil.
Maar in hierdie geval, omdat ons funksie gee terug 'n Bool,
Ons moet as waar of onwaar om terug te keer.
STUDENT: As jy sê Boole-uitdrukking,
kan jy stel dit gelyk aan vals?
Soos as ek wil sê, as hierdie toestand nie nagekom word nie, soos is bo gelyk vals.
Sal dit verstaan ​​as jy net sit valse aan die ander kant?
INSTRUCTOR: Ja.
So eintlik as jy ooit iets doen
soos is bo of laer, wat terugkeer waar of vals
en dit is eintlik slegte styl sê gelyk gelyk waar of gelykes
gelyk vals.
Jy wil hê dat die resultaat te gebruik as homself as u tjek.
Nie wat ek wou hê.
Dit is wat ek wou hê.
So in die geval van jy vra oor iets soos stoor hierdie in c.
>> So as ons int main (void) en iets soos hierdie.
En jy het as is bo van 'n paar insette en jy
vra of jy kan doen iets soos hierdie?
Reg?
STUDENT: Ek het probeer om dit te doen [onhoorbaar].
Want as it's--
INSTRUCTOR: Right.
So jy wil hierdie vals is, reg?
STUDENT: Ja.
INSTRUCTOR: So in hierdie geval wil dit uit te voer as dit is nie waar nie.
So die koel ding wat jy doen daar is dit.
So onthou uitroep punt negeer dinge?
Dit sê [onhoorbaar] beteken nie.
So, as ons kyk na net hierdie deel hier, wil jy
sê dat evalueer om valse as jy wil om dit te.
Nie vals is waar wat beteken dit sou voer.
Maak dit sin maak?
STUDENT: Ja.
INSTRUCTOR: awesome.
OK.
So kan ons net terug waar in hierdie geval.
So nou het ons twee ander gevalle in hierdie geval.
Wat is ons twee ander gevalle?
Kom ons doen dit net op hierdie manier.
So laat ons begin met die ander As waardes by die middel
minder is as die waarde wat ons wil hê.
So ons waarde in die middel is minder as die waarde wat ons soek.
>> So wat gebind doen jy dink ons ​​wil om te werk?
Boonste of onderste?
Bo?
So watter kant van die skikking gaan ons kyk na?
>> STUDENT: Die laer.
>> INSTRUCTOR: Ons gaan ons om te kyk na die linkerkant.
So anders as min waarde is minder.
Sodat jou middelste waarde hier minder is as wat ons wil hê.
So wil ons die te neem regs van ons verskeidenheid.
So ons gaan werk ons ​​ondergrens.
So sal ons ons laer toewys.
En wat dink jy laer behoort te wees?
STUDENT: Die middelste waarde?
INSTRUCTOR: So het die middel value--
STUDENT: Plus 1.
INSTRUCTOR: --plus 1.
Kan iemand vir my sê hoekom Ons het dit plus 1?
>> STUDENT: [? Geen waarde?] meer gelyk aan dit.
>> INSTRUCTOR: Right.
Omdat ons reeds weet dat ons middelste waarde is nie gelyk aan
en ons wil om dit te sluit van alle daaropvolgende navrae.
As jy vergeet dat plus 1, hierdie sal graag lus vir onbepaalde tyd.
En jy sal net in 'n gevang word oneindige lus, en dan sal jy segfault
en dinge gaan sleg.
So maak seker dat jy nie insluitend die waarde wat jy net
gekyk.
So ons sorg dat ons met 'n plus 1.
>> So nou het ons ons laaste voorwaarde wat ek altyd ter wille van veiligheid
jy hier kan sien, anders as waarde op die middel is groter as die waarde
ons wil hê.
Dit beteken dat ons wil die linkerhand helfte.
So watter een gaan ons te werk?
Boonste.
En wat is hierdie een gaan gelyk?
Midde minus 1 omdat natuurlik, ons wil
om seker te maak dat ons nie ' soek weer op daardie middelste waarde.
En dan het ons dit.
Dit is dit.
Dit is al wat binêre soek is.
Dit is nie so sleg nie, reg?
Dit is soos 10 reëls van kode met wit ruimte.
So baie sterk, baie nuttig, sal jy wees om dit te gebruik in een van jou later psets.
Miskien nie hierdie een nie, maar later.
So leer.
Mal daaroor.
Dit sal jou goed behandel.
So het iemand enige vrae oor binêre soek?
Ja.
>> STUDENT: Maak dit saak of jou n ewe of onewe?
>> INSTRUCTOR: No.
Omdat ons dit gegooi in die middel as 'n int, dit sal net dit afgebreek word.
So sal dit 'n heelgetal te bly en dit sal uiteindelik sorteer deur middel van alles.
Sodat jy nie hoef te bekommer oor dat.
Almal goeie?
Awesome.
Cool.
So, julle het hierdie.
Skyfievertoning.
So as ons praat, ek weet David genoem kompleksiteit Runtimes.
>> So in die beste geval, dit is net een, wat ons noem konstante tyd.
Kan iemand vir my sê hoekom dit kan wees?
Watter tipe scenario sou dit behels?
Mm-hm.
>> STUDENT: [onhoorbaar] first--
INSTRUCTOR: So het die middel om die eerste element wat ons kom na, reg?
So óf 'n verskeidenheid van een of alles wat ons is op soek na net
gebeur smack schar in die middel te wees.
So dit is ons beste geval.
Jy kry in die werklike probleme, waarskynlik nie gaan wat dikwels bereik [onhoorbaar].
Wat van ons ergste geval?
Ons ergste geval is log n.
En wat te doen het met die hele magte van twee ding wat ek het gepraat oor.
>> So in die ergste geval, sou dit beteken wat ons gehad het die skikking af te kap
totdat dit 'n element van die een.
So ons moes dit af te kap in die helfte soveel keer as wat ons moontlik kan.
Dit is waarom dit is log N omdat jy hou net deur twee te deel.
So aannames, dinge wat jy nodig het om te weet as jy ooit
gaan 'n binêre soek om te gebruik.
Jou elemente moet uitgesorteer word.
Hulle moet gesorteer word nie omdat dit is die enigste manier waarop jy
kan weet as jy in staat is om uit te gooi die helfte van dit.
>> As jy het hierdie deurmekaar sak van getalle en jy sê,
OK, ek gaan die middel te gaan en die aantal Ek is op soek na
is minder as dit, ek gaan net arbitrêr gooi die een helfte.
Jy sal nie weet of jou getalle in die ander helfte.
Jou lys moet gesorteer word.
Asook, kan dit wees voort te gaan om 'n bietjie,
maar jy moet ewekansige toegang te hê.
Jy moet in staat wees om net gaan na die middel element.
As jy het om te deurkruis deur iets
of dit neem jou ekstra stappe te kry om dit middel element,
dit is nie inteken N nie, want nie meer werk toe te voeg in dit.
En dit sal 'n bietjie te maak meer sin in twee weke,
maar ek het net soort wou voorwoord, gee julle 'n idee van wat
te kom.
Maar dit is die twee belangrike aannames
wat jy nodig het vir 'n binêre lys.
Maak seker dit is gesorteer.
Dit is die groot een vir julle nou.
En dat ons kan gaan in die res van ons spesies.
So vier sorts-- borrel, plasing, seleksie, en voeg.
Hulle is al die soort van cool.
As jy ouens besluit CS 124 te neem, sal jy leer oor allerhande soorte.
En as jy 'n Kletskerk fan, daar is 'n baie cool komiese oor
soos baie oneffektief vorme, wat ek raai jy gaan om te kyk na.
Een van hulle is soos paniek soort, wat is soos, o nee, terugkeer ewekansige skikking.
Afsluit stelsel.
Verlaat.
So geeky humor is altyd goed.
>> So nie almal soort onthou van soos net 'n algemene idee
hoe borrel soort werk.
Jy onthou?
>> STUDENT: Ja.
>> INSTRUCTOR: Gaan vir dit.
>> STUDENT: So jy gaan en As dit is groter, dan kan jy ruil die twee.
>> INSTRUCTOR: MM-hm.
Presies.
Sodat jy net Itereer deur.
Jy is so twee getalle.
As die een is voor groter as die een daarna,
jy net ruil hulle so dat in hierdie manier al die hoër getalle
borrel teen die einde van die lys en al die laer getalle borrel af.
>> Het hy wys julle ouens die koel klank effek sorteer video?
Dit is soort van cool.
So as Robert het net gesê, die algoritme dat jy net stap vir stap deur die lys,
uitruiling aangrensende waardes as hulle nie in orde is.
En dan hou net herhaal totdat jy maak nie enige verteenwoordig.
So nie sleg nie, reg?
So ons moet net 'n vinnige voorbeeld hier.
So dit gaan om te sorteer hulle in stygende volgorde.
So wanneer ons deur die eerste tyd, ons kyk deur agt
en ses is natuurlik nie in orde, ons ruil hulle.
>> So kyk na die volgende een.
Agt en vier nie in orde is.
Ruil hulle.
En dan agt en twee, ruil hulle.
Daar gaan ons.
So na jou eerste slaag, moet jy weet dat jou grootste getal
gaan al die pad wees by die top, want dit is net
gaan voortdurend groter as alles anders
en dit is net gaan om te borrel tot al die pad na die einde daar.
Doen wat sin maak vir almal?
Cool.
>> So dan is ons kyk na ons tweede slaag.
Ses en vier, skakel.
Ses en twee, skakel.
En nou het ons 'n paar dinge in orde is.
So vir elke pass dat ons maak deur ons hele lys,
ons weet dat net soos wat baie nommers aan die einde sal uitgesorteer het.
So ons doen 'n derde slaag, Dit is een omruil.
En dan op ons vierde slaag, het ons 'n nul slots.
En so weet ons dat ons skikking is gesorteer.
>> En dit is die groot ding met borrel soort.
Ons weet dat wanneer ons nul swaps, wat
beteken dat alles is in 'n volledige orde.
Dit is soort van hoe ons gaan.
So is ons ook gaan borrel te kodeer soort wat ook nie so sleg nie.
Nie een van hierdie is so sleg nie.
Ek weet hulle kan lyk 'n bietjie scary.
Ek weet toe ek die klas, selfs wanneer ek
is die onderrig van die klas vir die eerste keer verlede jaar,
Ek was soos, hoe doen ek dit?
Dit maak sin in teorie, maar hoe ons eintlik doen dit?
Dit is waarom ek wil ook so te wandel deur kode met julle ouens hier.
So ek het 'n pseudokode vir julle hierdie tyd.
Dus net dit in gedagte hou as ons is oor die oorgang oor.
So ons het 'n paar counter dat hou van ons swaps,
omdat ons nodig het om seker te maak dat ons seker te maak dat.
En ons Itereer die hele skikking as ons nou net gedoen met hierdie voorbeeld.
As die element voor groter as die element na waar ons op,
ruil ons hulle en ons inkrementeer ons counter want sodra ons ruil,
ons wil laat ons counter weet dat.
Enige vrae is daar?
Iets lyk snaaks hier.
STUDENT: stel jy die toonbank tot nul elke keer as jy gaan deur die loop?
Hou jy nie gaan elke keer terug na nul?
INSTRUCTOR: Nie noodwendig nie.
So, wat gebeur is dat ons gaan hier deur.
So doen terwyl, onthou, hierdie sal weer uit te voer sonder versuim.
So dit gaan die te stel counter gelyk aan nul,
dan is dit gaan om deur te Itereer.
As dit iterate deur, dit sal werk toonbank.
As dit updates toonbank, wanneer dit gedoen is, wanneer dit aan die einde van die skikking,
As ons lys is nie gesorteer, counter sal opgedateer het.
>> So dan is dit gaan die toestand en dit sê, OK, is teen groter as nul.
As dit is, dit weer doen.
Jy wil so dat wanneer jy weer gaan deur, counter is gelyk aan nul.
As jy gaan deur 'n gesorteerde skikking, niks verander nie,
dit misluk, en jy terugkeer om die lys gesorteer.
Doen wat sin maak?
STUDENT: Dit mag in 'n bietjie.
INSTRUCTOR: OK.
As daar enige ander vraag wat opkom.
Ja.
>> STUDENT: Wat sou die funksie wees vir die uitruiling van die elemente?
>> INSTRUCTOR: So kan ons eintlik skryf dat as ons gaan nou reg te stel.
Cool.
So op daardie noot, is Alison gaan terug te keer na die toestel skakel.
Dit gaan pret wees.
En ons het ons mooi borrel soort ding hier.
So ek reeds gedoen het fietsry deur die skikking.
Ons het ons swaps wat is gelyk aan nul.
So ons wil ruil aangrensende elemente as hulle buite orde.
So die eerste ding wat ons nodig het om te doen, is Itereer deur ons verskeidenheid.
>> So hoe dink jy ons kan Itereer deur ons verskeidenheid?
Ons het vir en ek is gelyk aan 0.
Ons wil ek minder te wees as n minus 1 minus k.
En Ek sal verduidelik wat in 'n tweede.
So, dit is 'n optimalisering hier waar, onthou hoe ek gesê het na elke pass
deur die skikking ons weet dat net die on--
>> So na 'n pass ons weet dat dit gesorteer is.
Na twee aangeë ons weet dat dit alles gesorteer.
Na drie aangeë ons weet dit is gesorteer.
So die manier waarop ek iterating deur die skikking hier
is dit om seker te maak om net te gaan deur middel van wat ons weet, is ongesorteerde.
OK?
Dit is net 'n optimalisering.
Jy kan dit naïef skryf net iterating deur alles,
sou dit net langer neem.
Met hierdie vier lus is dit net 'n mooi optimalisering
omdat ons weet dat na elke volledige iterasie deur die skikking hier
soos elke volle lus hier is, weet ons dat 'n mens meer van hierdie elemente
sal gesorteer word aan die einde.
>> Sodat ons nie hoef te bekommer oor hulle.
Doen wat sin maak vir almal?
Dit koel bietjie truuk?
So in daardie geval, indien ons iterating deur,
ons weet wat ons wil om te kyk of skikking N en N plus 1 in orde is.
OK.
So hier is die pseudokode.
Ons wil om te kyk of skikking N en N plus 1 in orde is.
So, wat kan ons daar?
Dit gaan 'n voorwaardelike wees.
Dit sal 'n as.
>> STUDENT: As skikking N is minder as skikking N plus 1.
INSTRUCTOR: MM-hm.
Wel, minder as of groter as.
STUDENT: Meer as.
Dan wil ons hulle te ruil.
Presies.
So nou kry ons in wat die meganisme vir die uitruiling hulle?
So het ons deur hierdie kort, 'n tipe van ruil-funksie verlede week.
Is daar iemand onthou hoe dit gewerk het?
So kan ons nie net toewys hulle, reg?
Omdat een van hulle verlore sal gaan nie.
As ons sê A is gelyk aan B en dan B is gelyk aan A, al 'n skielike beide van hulle
is net gelyk aan B.
>> So wat ons moet doen, is om ons 'n tydelike veranderlike wat
gaan een van ons s'n, terwyl te hou Ons is in die proses van uitruiling.
So, wat ons het, is ons sal 'n paar int het temp is gelyk aan- jy dit kan wys
om watter een jy wil, net maak seker dat jy die spoor van it-- hou
So in hierdie geval, ek gaan toewys om dit te skikking N plus 1.
So wat gaan hou wat waarde is in die tweede blok
dat ons is op soek na.
>> En dan het ons kan doen is om ons kan gaan voor en toewys skikking N plus 1,
omdat ons weet dat ons het wat waarde gestoor.
Dit is ook een van die groot things-- Ek weet nie of enige van julle
het probleme waar as jy oorskakel twee reëls van die kode skielik dinge gewerk het.
Orde is baie belangrik in die CS.
So maak seker dat jy diagram dinge uit indien moontlik
oor wat eintlik gebeur.
So nou gaan ons toewys skikking N plus 1,
omdat ons weet dat ons het wat waarde gestoor.
>> En ons kan wys wat aan skikking N of in hierdie geval verskeidenheid i.
Te veel veranderlikes.
OK.
So nou het ons oorgeplaas verskeidenheid i plus 1 tot gelyke wat is opgestel i.
En nou kan ons teruggaan en toewys verskeidenheid i na wat?
Iemand?
>> STUDENT: 10.
>> INSTRUCTOR: 10.
Presies.
En een laaste ding.
As ons nou omgeruil het, wat moet ons doen?
Wat is die een ding wat gaan om ons te vertel
As ons ooit hierdie program beëindig?
Wat vertel ons dat ons 'n gesorteerde lys?
As ons nie enige swaps presteer nie, reg?
As swaps is gelyk aan nul aan die einde van hierdie.
So wanneer jy voer 'n ruil, soos ons net hier gedoen het, wil ons swaps te werk.
En ek weet daar was 'n vraag vroeër oor wat jy kan
gebruik nul of een plaas van waar of vals is.
En dit is wat dit beteken hier.
So dit sê indien nie verteenwoordig.
So as swaps is nul, wat is-- Ek het altyd kry my waarhede en my falses deurmekaar.
Ons wil hê ons moet evalueer waar en dit is nie.
So as dit is zero, dan is dit vals.
As jy dit ontken met 'n [? bang?] dit waar is.
So dan hierdie lyn voer.
>> Waarhede en valse en nulle en ene kry mal.
Net as jy stadig loop deur dit sal sin maak.
Maar dit is wat hierdie klein bietjie van die kode hier doen.
So hierdie tjeks om te sien het ons gedoen om enige verteenwoordig.
So as dit is iets anders nul, gaan dit vals te wees
en die hele ding is weer gaan voer.
Cool?
>> STUDENT: Wat beteken break doen?
>> INSTRUCTOR: Breek net breek jy uit van die lus.
So in hierdie geval sou dit wil slegs die einde van die program
en jy wil net jou gesorteer lys.
STUDENT: Amazing.
INSTRUCTOR: Ek is jammer?
STUDENT: Omdat voorheen ons gebruik is geskryf 1 oor geskryf nul
wat aan te bied as wat sal werk of nie.
>> INSTRUCTOR: Ja.
Sodat jy kan terug nul of 1.
In hierdie geval, want ons is nie eintlik om iets te doen met die funksie,
ons wil net om dit te breek.
Ons het nie regtig omgee oor dit.
Brake is ook goed as dit gebruik word vir die breek
vier sirkelroetes of toestande wat jy nie wil hê om te hou die uitvoering.
Dit neem jy net uit hulle.
Dit is 'n bietjie van 'n nuanse ding.
Ek voel daar is 'n baie van die hand swaai,
soos jy sal leer oor hierdie gou.
>> Maar jy sal leer oor dit binnekort.
Ek belowe.
OK.
So het almal kry borrel soort?
Nie te sleg nie.
Itereer deurgaan nie, ruil kosse met 'n tydelike veranderlike, en ons is almal daar te vestig?
Cool.
Awesome.
OK.
Terug na die PowerPoint.
Enige vrae in die algemeen oor hierdie so ver?
Cool.
Mm-hm.
>> STUDENT: [onhoorbaar] int main gewoonlik.
Het jy wat vir hierdie te hê?
>> INSTRUCTOR: Ons is net op soek na net op die werklike sorteringsalgoritme.
As jy dit binne soos 'n groter program,
jy sal moet 'n int main iewers.
Afhangende van waar jy gebruik hierdie algoritme
dit sal bepaal wat is teruggestuur word deur dit.
Maar vir ons geval, ons is streng kyk na hoe dit eintlik
Itereer deur 'n skikking.
Sodat ons nie daaroor bekommer nie.
>> So ons praat oor die beste geval en ergste geval scenario's vir binêre soek.
So is dit ook belangrik om te doen wat vir elkeen van ons spesies.
So, wat dink jy is die ergste geval runtime van borrel soort?
Julle onthou?
>> STUDENT: N minus 1.
INSTRUCTOR: N minus 1.
Dus beteken dit dat daar N minus 1 vergelykings.
So een ding om te besef is wat op die eerste iterasie,
ons gaan deur, ons vergelyk hierdie two-- so dit is 1.
Hierdie twee, drie, vier.
So na een iterasie ons reeds vier vergelykings.
Wanneer ek praat runtime en n.
N verteenwoordig die aantal vergelykings as 'n funksie van hoeveel elemente
ons het.
OK?
>> So gaan ons deur ons vier.
Die volgende keer wat jy weet ons dit nie doen nie het om te sorg van hierdie.
Ons vergelyk hierdie twee, hierdie twee, die twee,
en as ons nie daardie optimalisering met die vier lus wat ek geskryf het,
jy sal vergelyk word hier anyways.
So jy sal moet loop deur die skikking
en maak n vergelykings N keer nie, want elke keer as ons
loop deur dit soort een ding wat ons.
>> En elke keer as ons loop deur die skikking, maak ons ​​n vergelykings.
Sodat ons runtime hiervoor is eintlik n vierkant, wat
is veel erger in ons teken einde, want dit
beteken dat as ons het vier miljard elemente, is dit
gaan ons 4000000000 te neem vierkantig plaas uit 32.
So nie die beste runtime, maar vir 'n paar dinge,
jy weet, as jy binne 'n sekere verskeidenheid van elemente
borrel soort kan fyn te gebruik.
>> OK.
So nou, wat is die beste geval runtime?
STUDENT: Zero?
Of 1?
>> INSTRUCTOR: So 1 sou een vergelyking.
Right.
>> STUDENT: N minus 1?
>> INSTRUCTOR: So, ja.
So n minus 1.
Wanneer jy 'n konsep soos n minus 1, is ons geneig om net gooi dit af
en ons net sê N, want jy het elk van these-- elke paar te vergelyk.
So dit sou wees n minus 1, wat ons Ons wil net sê, is ongeveer N.
Wanneer jy met runtime, alles is in benadering.
Solank as wat die eksponent korrek is, is jy redelik goed.
>> Dit is hoe ons dit hanteer.
Sodat die beste geval is N, wat beteken dat die lys is reeds gesorteer is,
en alles wat ons doen is loop deur en seker te maak dat dit gesorteer.
Cool.
Alle regte.
So as jy hier sien, het ons net 'n paar meer grafieke.
So n vierkant.
Pret.
Veel erger as N as ons sien, en baie, baie erger as log 2n.
En dan kry jy ook by log stompe.
En jy neem 124, kry jy in soos log ster, wat soos mal.
So as jy belangstel, soek log ster.
Dit is soort van pret.
So ons het hierdie groot grafiek.
Net 'n kop, dit 'n wonderlike grafiek te hê
vir jou mid-term, want ons lank jy hierdie verdunt te stel.
Dus net 'n kop, het dit op jou mid-term op jou mooi oneerlik blad
daar.
Sodat ons net kyk na borrel soort.
Ergste geval, n vierkant, die beste geval, n.
En ons gaan om te kyk na die ander.
>> En soos jy kan sien, is die enigste een wat regtig goed
is merge soort, wat ons kry in waarom.
So ons gaan om te gaan na die volgende een here-- seleksie soort.
Is daar iemand onthou hoe seleksie soort gewerk?
Gaan vir dit.
>> STUDENT: Eintlik gaan deur 'n bevel en die skep van 'n nuwe lys.
En net soos jy om elemente in, sit hulle in die regte plek
in die nuwe lys.
>> INSTRUCTOR: So wat klanke meer soos invoeging soort.
Maar jy is baie naby.
Hulle is baie soortgelyk.
Selfs ek kry hulle deurmekaar soms.
Voordat hierdie artikel Ek was soos, wag.
OK.
So wat jy wil doen, is seleksie soort,
die manier waarop jy kan dink oor dit en die manier waarop
Ek maak seker ek probeer om nie te kry hulle deurmekaar, is dit gaan deur
en dit kies die kleinste getal en dit
plaas wat aan die begin van die lys.
Dit ruil dit met die eerste plek.
Hulle het eintlik 'n voorbeeld vir my.
Awesome.
So net 'n manier om te dink it-- seleksie sorteer, kies die kleinste waarde.
En ons gaan loop deur 'n voorbeeld
wat ek dink sal help, want Ek dink beeldmateriaal altyd help.
So het ons begin met iets dit is heeltemal ongesorteerde.
Rooi sal ongesorteerde wees, groen sal gesorteer word.
Dit sal al sin maak in 'n tweede.
>> So gaan ons deur en ons Itereer van die begin tot die einde.
En ons sê, OK, 2 is ons kleinste getal.
So ons gaan neem 2 en ons gaan om dit te skuif na die voorkant van ons verskeidenheid
want dit is die kleinste getal wat ons het.
So dit is wat dit is hier om te doen.
Dit is net gaan die twee te ruil.
So nou het ons 'n gesorteer deel en 'n ongesorteerde deel.
En wat is goed om te onthou oor seleksie soort
is ons net kies uit die ongesorteerde deel.
>> Die gesorteer deel jy net uitlos.
Mm-hm?
>> STUDENT: Hoe weet wat die kleinste, sonder dat dit te vergelyk
elke ander waarde in die skikking.
INSTRUCTOR: Dit maak dit vergelyk.
Ons hou oorgeslaan nie.
Dit is net 'n algemene algehele.
Ja.
Wanneer ons skryf die kode ek seker jy sal meer tevrede wees.
Maar jy slaan die eerste element as die kleinste.
Jy kan vergelyk en u sê, OK, is dit kleiner?
Ja.
Hou dit.
Hier is dit kleiner?
Geen?
>> Dit is jou kleinste, toewys dit aan jou waarde.
En jy sal baie gelukkiger wees wanneer ons gaan deur die kode.
So ons gaan deur ons ruil dit, so dan ons kyk na hierdie ongesorteerde gedeelte.
So ons gaan drie uit te kies.
Ons gaan om dit te sit op ten die einde van ons gesorteerde gedeelte.
En ons is net gaan om te hou doen dat dit te doen, en om dit te doen.
So dit is ons soort van pseudokode hier.
Ons sal kodeer dit hier in 'n tweede.
Maar net om iets te loop deur op 'n hoë vlak.
Jy gaan om te gaan uit Ek is gelyk aan 0 tot N minus 2.
Dit is 'n ander optimalisering.
Moenie te veel bekommerd wees oor dit.
So as jy sê.
As Jakob het gesê, hoe kan ons spoor van wat ons minimum is hou?
Hoe weet ons dit?
Ons het om te vergelyk alles in ons lys.
>> So minimum gelyk aan i.
Dit is net te sê in hierdie geval die indeks van ons minimum waarde.
So dan is dit gaan om Itereer deur en dit gaan van j gelyk i plus 1.
So het ons reeds weet dat dit is ons eerste element.
Ons moet nie huiwer om dit te vergelyk met self.
So het ons begin vergelyk dit na die volgende een wat is die rede waarom dit is i plus 1 tot N
minus 1, wat is die einde van die skikking is daar.
En ons het gesê dat indien die rigting van j is minder as skikking min,
dan toewys ons waar ons minimum indekse.
>> En as min is nie gelyk aan Ek, as in waar ons terug hier.
So hou wanneer ons die eerste het hierdie een.
In hierdie geval, sou dit begin by nul, sou dit uiteindelik 'n twee.
So min wil nie gelyk i in die einde.
Dit laat ons weet wat ons nodig het om hulle te ruil.
Ek voel soos 'n konkrete voorbeeld sal help om veel meer as dit.
So ek sal hierdie kode met julle nou en ek dink dit sal beter wees.
>> Allerhande geneig dat die pad in die werk dit is dikwels beter om net om hulle te sien.
So wat ons wil doen, is Ons wil eers die kleinste
element in sy posisie in die skikking.
Presies wat Jakob gesê het.
Jy moet dit een of ander manier te stoor.
So ons gaan hier begin iterating oor die skikking.
Ons gaan om te sê dit is ons eerste een net om te begin met.
So ons gaan int te hê kleinste is gelyk aan die rigting van i.
>> So een ding, elke op te let keer lus voer,
begin ons 'n stap verder.
Wanneer ons begin ons kyk na hierdie een.
Die volgende keer wat ons Itereer deur, ons begin by hierdie een
en die toeken dit ons kleinste waarde.
So dit is baie soortgelyk aan borrel soort waar ons weet dat daar na een pas,
hierdie laaste element is gesorteer.
Met seleksie soort, dit is net die teenoorgestelde.
>> By elke slaag, weet ons dat Die eerste een is gesorteer.
Na afloop van die tweede slaag, die tweede een sal gesorteer word.
En as jy sien met die skyfie voorbeelde, ons gesorteer gedeelte hou net groei.
So deur die instelling van ons kleinste een om skikkings i, al is dit doen
is versmoor wat Ons is op soek na so
om die getal te verminder vergelykings wat ons maak.
Maak dit sin maak vir almal?
Het jy my nodig het om te loop deur wat weer stadiger of in ander woorde?
Ek is bly om te.
OK.
>> So ons is die stoor van die waarde op hierdie punt,
maar ons wil ook die indeks te stoor.
So ons gaan die stoor posisie van die kleinste
een wat net gaan ek te wees.
So nou Jacob tevrede is.
Ons het dinge gestoor.
En nou het ons nodig het om te kyk deur die ongesorteerde deel van die skikking.
So in hierdie geval die sou wees om ons ongesorteerde.
Dit is Ek.
OK.
>> So wat ons gaan doen gaan wees vir 'n lus.
Wanneer jy nodig het om te Itereer deur 'n skikking,
jou gedagtes kan gaan vir 'n loop.
So vir 'n paar int k equals-- wat dink ons
k gaan gelyk te begin met?
Dit is wat ons stel as ons kleinste waarde en ons wil om dit te vergelyk.
Wat wil ons dit te vergelyk met?
Dit gaan hierdie volgende een wees, reg?
So ons wil k geïnisialiseer word te i plus 1 te begin.
>> En ons wil k in hierdie geval het ons reeds grootte opgegaar hier
sodat ons kan net gebruik grootte.
Grootte synde die grootte van die skikking.
En ons wil net werk k deur elke keer een.
Cool.
So nou het ons nodig het om te vind die kleinste element hier.
So as ons Itereer deur ons wil sê, as die rigting van k
minder is as ons kleinste value-- dit is waar ons is eintlik
dop van wat die kleinste here--
dan wil ons toewys wat ons kleinste waarde is.
>> Dit beteken dat, o, ons iterating deur hier.
Wat ook al waarde is hier nie ons kleinste ding.
Ons wil dit nie.
Ons wil om dit te toewys.
So as ons gehou indiensneming nie, wat doen dink jy kan wees in hierdie kode hier?
Ons wil toewys kleinste en posisie.
So, wat is die kleinste nou?
STUDENT: Array k.
INSTRUCTOR: Array k.
En wat is die posisie nou?
Wat is die indekse van ons kleinste waarde?
Dit is net k.
So verskeidenheid k, k, pas hulle op.
Sodat ons wou dit toewys.
En dan na ons gevind dat ons kleinste, So aan die einde van hierdie lus
Hier het ons het gevind wat ons kleinste waarde is, sodat ons net ruil nie.
In hierdie geval, soos sê ons kleinste waarde is hier.
Dit is ons kleinste waarde.
>> Ons wil dit net hier te ruil, wat wat dit omruil funksie aan die onderkant
gedoen het, wat ons nou net geskryf het saam 'n paar minute gelede.
So dit moet lyk bekend.
En dan sal dit net Itereer deur totdat dit al die pad bereik
tot aan die einde, wat beteken dat jy nul elemente wat ongesorteerde
en alles is gesorteer.
Sin maak?
'N bietjie meer konkreet?
Die kode hulp?
>> STUDENT: Vir 'n grote, jy nooit dit regtig definieer of verander dit,
hoe dit weet?
>> INSTRUCTOR: So een ding om te sien hier is int grootte.
So ons is in hierdie sort-- soort sê is 'n funksie in hierdie case-- dit
seleksie soort, is dit verby met die funksie.
So as dit was nie geslaag in, sal jy iets doen
soos met die lengte van die skikking of jy wil Itereer deur
die lengte te vind.
Maar, want dit is verby in, kan ons dit net gebruik.
Jy aanvaar net dat die gebruiker het jy 'n geldige grootte wat
eintlik verteenwoordig 'n grootte van jou skikking.
Cool?
>> As julle enige probleme met hierdie of wil jy meer praktyk kodering vorme
op jou eie, moet jy gaan na study.cs50.
Dit is 'n instrument.
Hulle het 'n checker wat jy eintlik kan skryf.
Hulle doen pseudokode.
Hulle het meer video's en skyfies insluitend die wat ek hier gebruik.
So as jy nog steeds voel 'n bietjie fuzzy, probeer om uit te.
Soos altyd, kom praat met my ook.
Vraag?
>> STUDENT: Is jy sê die grootte voorheen gedefinieer?
INSTRUCTOR: Ja.
Grootte voorheen gedefinieer up hier in die funksie verklaring.
So jy aanneem dat dit in is verby deur die gebruiker, en ter wille van eenvoud,
ons gaan om te aanvaar dat die gebruiker het ons die regte grootte.
Cool.
So dit is seleksie soort.
Ouens, ek weet ons leer baie vandag.
Dit is 'n digte data vir artikel.
So met dit, gaan ons om te gaan na voeg soort.
>> OK.
So voor dat ons te doen het ons runtime analise hier.
So in die beste geval, toegestaan, want ek het julle
die tafel ek reeds soort het dit weg.
Maar die beste geval runtime, wat dink ons ​​doen?
Alles gesorteer.
N vierkant.
Enigiemand het 'n verduideliking waarom jy dink?
>> STUDENT: Jy vergelyk through--
INSTRUCTOR: Right.
Jy vergelyk deur.
By elke iterasie, selfs al ons decrementing hierdie een,
jy nog soek deur alles wat die kleinste een te vind.
So selfs as jou kleinste waarde is hier aan die begin,
jy nog steeds dit te vergelyk teen alles
om seker te maak dit is die kleinste ding maak.
So sal jy eindig loop deur ongeveer N vierkantig tye.
Alle regte.
En wat is die ergste geval?
Ook N vierkantig want jy gaan om te doen wat dieselfde prosedure.
So in hierdie geval, keuring soort iets
dat ons ook 'n beroep verwagte looptyd.
So in die ander, het ons net weet die boonste en onderste grense.
Afhangende van hoe mal ons lys is of hoe ongesorteerde dit is,
hulle wissel tussen N of n vierkant.
Ons weet nie.
>> Maar omdat seleksie soort het dieselfde ergste en die beste geval, wat ons vertel dat
maak nie saak watter tipe van insette wat ons het, of dit nou heeltemal
gesorteer of heeltemal reverse gesorteer, dit is
gaan dieselfde hoeveelheid tyd te neem.
So in daardie geval, as jy Onthou van ons tafel,
dit het eintlik 'n waarde wat hierdie twee vorme het nie,
wat verwag runtime.
So ons weet dat wanneer loop ons seleksie soort,
dit is gewaarborg om hardloop 'n n vierkant tyd.
Daar is geen variasie daar.
Dit is net wat verwag is.
En weer, as jy wil leer meer, neem CS 124 in die lente.
Alle regte.
Ons het gesien dat hierdie een.
Cool.
So voeg soort.
En ek is waarskynlik gaan te brand deur middel van hierdie.
Ek wil nie hê dat julle ouens die kode nie.
Ons sal net loop deur dit.
So voeg soort is 'n soort van soortgelyke seleksie soort
in wat ons het beide 'n ongesorteerde en gesorteer deel van die skikking.
>> Maar wat anders is, is dat as ons gaan deur een vir een,
Ons het net neem wat die getal langs in ons ongesorteerde,
en korrek sorteer dit in ons gesorteerde skikking.
Dit sal meer sin maak met 'n voorbeeld.
So alles begin as ongesorteerde, Net soos 'n seleksie soort.
En ons gaan dit in te sorteer stygende volgorde soos ons gewees het.
So op ons eerste pas neem ons die eerste waarde
en ons sê, OK, jy is nou in 'n lys wat deur jouself.
>> Omdat jy in 'n lys deur jouself, is jy gesorteer.
Baie geluk vir die feit dat die eerste element in hierdie reeks.
Jy is reeds gesorteer al op jou eie.
So nou het ons 'n gesorteer en 'n ongesorteerde skikking.
So nou het ons neem die eerste.
Wat gebeur tussen hier en hier is dat ons sê:
OK, ons gaan om te kyk na die eerste waarde van ons ongesorteerde skikking
en ons gaan om insette dit in sy regte plek in die gesorteerde skikking.
>> So, wat ons doen, is ons 5 en ons sê, OK, 5 is groter as 3,
sodat ons net plaas dit reg aan die regterkant van die.
Ons is goed.
So dan gaan ons na ons volgende een.
En ons neem 2.
Ons sê, OK, 2 minder as 3, so ons weet dat dit
moet wees by die voor ons lys nou.
So wat ons doen is ons druk 3 en 5 af en ons beweeg 2 in die eerste slot.
So ons is net te voeg dit in die regte plek dit behoort te wees.
>> Dan kyk ons ​​na ons volgende een, en ons sê 6.
OK, 6 is groter as alles in ons gesorteerde skikking,
sodat ons net merk dit aan die einde.
En dan moet ons kyk na 4.
4 is minder as 6, is dit minder as 5 maar dit is groter as 3.
Sodat ons net plaas dit regs in die middel tussen 3 en 5.
So maak dat 'n bietjie bietjie meer konkrete,
hier is 'n soort van die idee van wat gebeur het.
So vir elke ongesorteerde element, ons bepaal waar in die gesorteerde gedeelte
dit is.
>> So in gedagte hou die gesorteer en ongesorteerde,
Ons het om oor te steek deur en figuur uit waar dit inpas in die gesorteerde skikking.
En ons plaas dit deur die verskuiwing van die elemente aan die regterkant van dit af.
En dan moet ons net aanhou iterating deur totdat ons
het 'n heeltemal gesorteer lys waar ongesorteerde is nou nul
en gesorteer neem die geheel van ons lys.
So, weer, om dinge selfs meer konkrete, ons het pseudokode.
>> So basies, want ek is gelyk aan 0 tot N minus 1,
dit is net die lengte van ons verskeidenheid.
Ons het 'n element wat gelyk is aan die eerste skikking of die eerste indekse.
Ons stel j gelyk aan dit.
Dus, terwyl j is groter as nul en die skikking, j minus 1
groter is as die element, so al wat doen
is om seker te maak dat jou j regtig verteenwoordig
die ongesorteerde gedeelte van die skikking.
>> Dus, terwyl daar is nog dinge te sorteer en j minus een is-- wat
is die element haar?
J was nog nooit hier gedefinieer.
Dit is soort van irriterende.
OK.
In elk geval.
So j minus 1, jy kontrolering die element voor dit.
Jy sê, OK, is die element voor waar ek am-- laat
eintlik trek dit uit.
So kom ons sê dit is soos op ons tweede slaag.
So ek gaan om gelyk te wees 1, wat is hier.
>> So ek gaan gelyk aan 1 te wees.
Dit sou wees 2, 4, 5, 6, 7.
Alle regte.
So ons element in hierdie geval gaan gelyk aan 4 nie.
En ons het 'n paar j dis gaan gelyk aan 1 te wees.
O, is j decrementing.
Dit is wat dit is.
So j is gelyk aan i, so wat dit is sê, is dat as ons vorentoe beweeg,
ons is net om seker te maak dat ons oor is nie
kruip op hierdie manier wanneer ons probeer dinge te voeg in ons gesorteer lys.
>> So wanneer j is gelyk aan 1 in hierdie geval en verskeidenheid j minus one-- so skikking j minus 1
2 in hierdie case-- as dit is groter is as die element,
dan sal al hierdie doen verskuif dinge af.
So in hierdie geval, verskeidenheid j minus een sou skikking nul, wat 2 wees.
2 is nie groter as 4, sodat dit nie uit te voer.
So het die skof nie af beweeg.
Wat dit beteken hier is net beweeg jou gesorteerde skikking af.
In hierdie geval, eintlik, ons kon do-- laat ons hierdie 3.
So as ons te loop deur met hierdie voorbeeld, het ons nou hier is.
Dit word gesorteer.
Dit is ongesorteerde.
Cool?
So ek is gelyk aan 2, so ons element is gelykstaande aan 3.
En ons j is gelyk aan 2.
So ons kyk deur en ons sê, OK, is verskeidenheid j minus een
groter is as die element dat ons is op soek na?
En die antwoord is ja, reg?
4 is groter as 3 en j is 2, dus is hierdie kode voer.
>> So nou wat ons doen 'n skikking te 2, so reg hier, ons ruil hulle.
Sodat ons net sê, OK, skikking op 2 nou gaan wees 3.
En j gaan gelyk j minus 1, wat is 1.
Dit is verskriklik, maar julle kry die idee.
J is nou gelyk aan 1.
Skikking j is net gaan om te wees gelyk aan ons element, wat 4.
Ek iets uitgewis ek moet nie het of miswrote iets,
maar julle ouens kry die idee.
>> Dit beweeg teen n.
En dan as dit was, sou dit lus weer en dit sou sê, OK, j is 1 nou.
Skikking j minus 1 is nou 2.
2 minder as die element?
Geen?
Dit beteken dat ons plaas hierdie element
in die regte plek in ons gesorteerde skikking.
Dan kan ons hierdie en ons sê, OK, ons gesorteerde skikking is hier.
En dit sal die nommer 6 neem en soos, OK, 6 minder as die getal?
Geen?
Cool.
Ons is goed.
>> Doen dit weer.
Ons sê 7.
7 minder as die einde van ons gesorteerde skikking?
No.
So ons is fine.
So dit sal uitgesorteer word.
Basies alles doen is dit gesê neem
die eerste element van jou ongesorteerde skikking,
uit te vind waar dit gaan in jou gesorteerde skikking.
En dit neem net sorg van swaps om dit te doen.
Jy is basies net uitruiling totdat dit in die regte plek.
Die visuele beeld is dat jy beweeg om alles af deur dit te doen.
>> So dit is soos half borrel soort-esque.
Check studie 50.
Ek raai probeer hierdie kode op jou eie.
Indien u enige kwessies of jy wil sien voorbeeld kode vir 'n inplanting soort,
laat weet my asseblief.
Ek is altyd rond.
So ergste geval runtime en die beste geval runtime.
As jy man gesien het van die tafel ek reeds het julle dit beide n vierkant en n.
>> So soort gaan af van wat ons gepraat oor ons vorige vorme, ergste
geval runtime is dat indien Dit is heeltemal ongesorteerde,
ons het al hierdie n keer te vergelyk.
Ons doen 'n hele klomp van vergelykings want as dit is in omgekeerde volgorde,
ons gaan om te sê, OK, dit is dieselfde, dit is goed,
en hierdie een sal hê om te vergelyk teen die eerste een te wees verhuis terug.
En as ons in die rigting van die stertkant, ons het
te vergelyk, te vergelyk, en vergelyk teen alles.
>> So is dit eindig word ongeveer N vierkant.
As dit korrek is dan is jy sê, OK, 2, jy is goed.
3, is jy in vergelyking met 2.
Jy is goed.
4, jy vergelyk net die stert.
Jy is goed.
6, vergelyk met die stert, jy is fine.
So vir elke plek as dit reeds gesorteer, jy maak 'n vergelyking.
So dit is net n.
En omdat ons 'n beste geval runtime van N en 'n ergste geval runtime van N
vierkantig, ons het nie verwag runtime.
>> Dit hang net op die chaos van ons lys is daar.
En weer 'n ander grafiek en 'n ander tafel.
So verskille tussen spesies.
Ek is net gaan om te briesie deur, het ek voel soos ons het breedvoerig gepraat
oor hoe hulle al die soort van verskil en met mekaar skakel.
Sodat fuseren soort is die laaste een Ek sal julle gebaar ouens met.
Ons het 'n mooi kleurvolle prentjie.
So saamsmelt soort is 'n rekursiewe algoritme.
So weet julle nie wat 'n rekursiewe funksie is?
>> Iemand wil hê om te sê?
Jy wil om te probeer?
So 'n rekursiewe funksie is net 'n funksie wat homself.
So as julle vertroud is met die Fibonacci-ry,
dit is geag rekursiewe omdat neem jy die vorige twee
en voeg hulle saam jou volgende een te kry.
So rekursiewe, dink ek altyd van rekursie as soos 'n spiraal
sodat jy soos stygende af in dit.
Maar dit is net 'n funksie wat roep self.
>> En eintlik, regtig vinnig I kan jy wys wat dit lyk.
So rekursiewe hier, as ons kyk, is dit die rekursiewe manier op te som oor 'n skikking.
So al wat ons doen is ons het som funksie
som wat nie 'n grote en 'n skikking.
En as jy sien, grootte decrements deur een elke keer.
En al wat dit doen is as x is gelyk aan zero-- so as die grootte van die skikking
is gelyk aan zero-- dit gee nul.
>> Anders is dit vat hierdie laaste element van die skikking,
en neem dan 'n bedrag van die res van die reeks.
So dit is net dit af te breek in kleiner en kleiner probleme.
Lang storie kort, rekursie, funksie wat homself.
As dit is al wat jy het om uit hierdie, dit is wat 'n rekursiewe funksie is.
As jy 51 is, sal jy baie kry, baie gemaklik met rekursie.
Dit is regtig cool.
Dit het sin soos 03:00 een aand uit.
En ek was soos, hoekom Ek gebruik dit nooit?
>> So vir merge soort, basies wat dit gaan doen, is dit
gaan dit af te breek en breek dit totdat dit is net enkele elemente.
Die enkele elemente is maklik om te sorteer.
Ons sien dat.
As jy een element, is dit reeds beskou gesorteer.
So op 'n bydrae van N elemente, As n is minder as 2,
net terugkeer, want dit beteken dit is óf 0 of 1 soos ons gesien het.
Diegene oorweeg gesorteer elemente.
>> Anders breek dit in die helfte.
Sorteer die eerste helfte, sorteer die tweede helfte, en dan saam te smelt hulle saam.
Hoekom is dit genoem merge soort.
So het ons hier ons sal sorteer.
So hou ons met hulle totdat die skikking grootte is 1.
So wanneer dit 1, het ons net terug want dit is 'n gesorteerde skikking,
en dit is 'n gesorteerde skikking, en dit is 'n gesorteerde skikking, ons is almal gesorteer.
So dan wat ons doen, is ons begin samesmelting hulle saam.
>> So die manier wat jy kan dink oor samesmelting is
jy net verwyder die kleiner getal van elk van die sub skikkings
en net voeg dit aan die lig gekom skikking.
So as jy kyk hier, wanneer ons hierdie stelle ons het 4, 6, en 1.
Wanneer ons wil om dit te smelt, ons kyk na die eerste twee
en ons sê, OK, 1 is kleiner, dit gaan na die front.
4 en 6, daar is niks om te vergelyk dit net merk dit aan die einde.
>> Wanneer ons kombineer hierdie twee, het ons net neem die kleiner een van die twee,
so dit is 1.
En nou het ons neem die kleiner van die twee, so 2.
Kleiner van die twee, 3.
Kleiner van die twee, 4, 5, 6.
So jy net trek uit hierdie.
En omdat hulle voorheen gesorteer,
jy moet net een vergelyking elke keer daar.
Sodat meer kode hier, net verteenwoordiging.
So jy begin by die middel en jy soort links en regs
en dan kan jy net saam te smelt hulle.
>> En ons het nie 'kode vir saamsmelt hier.
Maar, weer, as jy gaan op studeer 50, sal dit daar wees.
Anders kom praat met my As jy nog steeds verward.
So cool ding hier is dat die beste geval, ergste geval, en verwag runtime
is almal in log N, wat is baie beter as wat ons het
gesien vir die res van ons spesies.
Ons het gesien hoe n vierkant en wat ons eintlik
kry hier is n teken n, wat is groot.
>> Kyk hoe baie beter wat.
So 'n mooi kurwe.
Soveel meer doeltreffend te maak.
As jy ooit kan, gebruik saamsmelt soort.
Dit sal jou tyd bespaar.
Dan weer, soos ons gesê het, as jy in hierdie laer streek,
dit maak nie dat veel van 'n verskil maak.
Jy kry tot duisende en duisende van insette,
jy beslis wil 'n meer doeltreffende algoritme.
En weer, ons pragtige tafel van alle spesies wat julle vandag geleer het.
>> So ek weet dit is 'n digte dag.
Dit is nie noodwendig gaan om jou te help met jou pset.
Maar ek wil net 'n disclaimer te maak daardie artikel is nie net oor psets.
Al hierdie materiaal is regverdig spel vir jou midterms.
En ook as jy voortgaan met CS, Dit is baie belangrik grondbeginsels
wat jy nodig sou wees om te weet.
So 'n paar dae sal wees om 'n bietjie meer pset hulp
maar sommige weke sal wees veel meer werklike inhoud
wat mag lyk nie super nuttig vir jou nou,
maar ek belowe as jy aanhou op sal baie, baie nuttig.
>> So dit is dit vir artikel.
Af na die draad.
Ek het dit in 'n minuut.
Maar daar gaan jy.
En Ek sal donuts of lekkergoed.
Is daar iemand allergies vir enigiets op die pad?
Eiers en melk.
So donuts is 'n nie?
OK.
Alle regte.
Sjokolade geen?
Burst.
Starbursts is goed.
OK.
Ons gaan hê Burst volgende week dan.
Dit is wat ek kry.
Julle het 'n groot week.
Lees jou spec.
>> Laat my weet as jy enige vrae het.
Pset twee grade moet wees uit na jou teen Donderdag.
As jy enige vrae het oor hoe ek iets gegradeer
of waarom ek gegradeer iets wat die manier waarop ek het nie, kan u my e-pos, kom praat met my.
Ek is 'n bietjie mal hierdie week, maar ek belowe
Ek sal nog steeds 'n antwoord binne 24 uur.
So het 'n groot week, almal.
Sterkte op jou pset.