[Speel van musiek] 

ANDI Peng: Welkom by week 3 van artikel. Dankie, julle ouens, vir alle komende hierdie vroeër begin tyd vandag. Ons het 'n mooi, bietjie het intieme groep van vandag. So hopelik sal ons kry afwerking, miskien, vroeg, 'n bietjie vroeg vandag. So vinnig, net 'n paar aankondiging vir die agenda van vandag. Voordat ons begin, ons is gaan net oor te gaan paar kort logistieke probleme, pset vrae, debrief, dinge soos dat. En dan sal ons duik reg in. Ons sal 'n debugger genoem GDB om te gebruik begin debunking ons kode, wat David verduidelik in lesing die ander dag. Ons gaan oor die vier tipes van spesies. Ons gaan oor hulle redelik vinnig sedert hulle is redelik intensief. Maar weet dat al die skyfies en bronkode is altyd online. So voel vry, op jou insae, om terug te gaan en 'n blik op dit. 

Ons sal deurgaan asimptotiese notasie, wat is net 'n fancy manier sê "Runtimes," waar ons die groot O, wat David verduidelik in lesing. En ons het ook Omega, wat is die ondergrens runtime. En ons sal 'n bietjie meer praat in-diepte oor hoe die werk. En laastens, sal ons gaan oor binêre soek, omdat 'n klomp van julle wat reeds loer na jou psets waarskynlik weet dat dit is 'n vraag wat in jou pset. So jy sal gelukkig wees dat ons dek dit vandag. 

En laastens, per jou artikel terugvoer, ek het eintlik links ongeveer 15 minute by die einde net gaan oor logistiek van pset3, enige vrae het, miskien 'n bietjie van leiding, as jy wil, voordat ons begin programmering. So kom ons probeer om te kry deur middel van die materiaal redelik vinnig. En dan kan ons spandeer tyd neem meer vrae vir die pset. OK. 

Vinnig, so net 'n paar aankondigings voordat ons begin vandag. Eerstens, welkom om te maak dit deur twee van jou psets. Ek het 'n blik op your-- ja, laat kry 'n rondte van applous vir daardie een. Eintlik was ek regtig, regtig beïndruk. Ek gegradeer die eerste pset vir julle verlede week en julle het ongelooflik. 

Styl was op punt Behalwe vir 'n paar opmerkings. Maak seker dat jy is altyd kommentaar jou kode. Maar jou psets was op punt. En hou dit op. En dit is goed vir die padskraper om sien dat julle ouens is besig in soveel moeite in jou styl en jou ontwerp in jou kode wat ons graag vir jou om te sien. So ek verby langs my dankbaarheid vir die res van die Tas. 

Daar is egter 'n paar debrief vrae Ek wil net om te gaan oor wat sou beide my lewe te maak en 'n baie van die ander Tas se lewens 'n bietjie makliker te maak. Eerstens, het ek opgemerk afgelope week-- hoeveel van julle loop al check50 op jou kode voordat jy stuur? OK. So almal moet check50 doen, because-- n secret-- ons eintlik hardloop check50 as deel van ons korrektheid skrifte vir die toets van jou kode. So as jou kode faal check50, in alle waarskynlikheid, dit is waarskynlik gaan om misluk ons ​​tjek as well. Soms het jy ouens het die regte antwoorde. Soos in gulsig, sommige van jy het die regte nommers, jy net druk 'n paar ekstra dinge. En dat ekstra dinge eintlik versuim die tjek, omdat die rekenaar nie regtig weet wat dit soek. En so sal dit net loop deur, sien dat jou uitset nie ooreenstem met wat ons verwag die antwoord te wees, en merk dit is verkeerd. 

En ek weet wat gebeur het in sommige van jou gevalle hierdie week. So het ek terug gegaan en met die hand hergradeer almal se kode. In die toekoms al is, asseblief, asseblief maak seker dat jy ' check 50 op jou kode. Want dit is soort van 'n pyn vir die TA hê om terug te gaan en die hand regrade elke enkele pset vir elke enkele, klein gemis byvoorbeeld. So ek het nie neem af enige punte. Ek dink ek het dalk af een of twee vir ontwerp. In die toekoms al is, as jy versuim check50, punte sal geneem word af vir korrektheid. 

Verder is psets weens Vrydae op die middag. Ek dink daar is 'n sewe minute laat grasietydperk dat ons jou gee. Per Harvard tyd, is hulle toegelaat om sewe minute laat om alles. So hier by Yale, sal ons voldoen aan wat as goed. Maar pretty much op 00:07, as jou pset is nie in, dit gaan so laat gemerk word. En so terwyl dit gemerk so laat, die TA-- Ek is nog gaan word gradering jou psets. So sal jy nog steeds sien 'n graad verskyn. Maar weet dat by die einde van die semester, al laat psets sal net outomaties zeroed deur die rekenaar. 

Ons doen dit vir twee redes. Een, soms kry ons verskoon, soos verskonings dekaan se later op dat ek nie weet nie oor nie. So ons wil om seker te maak ons ​​gradering alles net in geval, soos, ek is ontbreek verskoning van die dekaan. En tweedens, hou in gedagte, kan jy nog steeds drop een pset dat volle omvang punte. En so het ons graag graad al jou psets net om seker te maak dat jou omvang se daar en jy hulle probeer. So selfs al is dit laat, sal jy nog steeds kry krediet vir omvang punte, dink ek. 

So moraal van die storie is, maak seker dat jou psets in op tyd. En as hulle nie in op tyd, weet dat dit is nie groot nie. Ja, voor ek aanbeweeg, nie almal het enige vrae oor pset terugvoer? Ja. 

GEHOOR: Het jy sê ons kan daal een van die psets? 

ANDI Peng: Ja. So is daar nege psets algehele in die loop van die semester. En as jy omvang points-- so omvang is net, pretty much, jy probeer die probleem is jy om in die tyd, jy wys dat jy het gedemonstreer het jy die spec te lees. Dit is pretty much omvang. En as jy die vervulling omvang punte, ons kan die laagste daal een uit volle omvang. So dit is in jou voordeel wees om voltooi en probeer om elke pset. 

Selfs indien geen van upload-- hulle werk, laai hulle almal. En dan sal ons hopelik in staat wees om gee jou 'n paar van die punte terug. Koel. Enige ander vrae? Groot. 

Tweedens, kantoor hours-- 'n paar vinnige notas oor kantoorure. So die eerste, kom vroeg in die week. Niemand is ooit op kantoorure, Maandag. Christabel gekom om kantoorure laaste nag. Ja, Christabel. En wat het ons op kantoor uur gisteraand, Christabel? 

GEHOOR: Ons het roomys. 

ANDI Peng: So dit is reg, ons het roomys by kantoorure laaste nag. Terwyl ek nie kan belowe dat ons sal roomys by kantoorure het elke week, wat ek kan belowe is dat daar aansienlik sal 'n beter student TA verhouding. Soos ligitieme, dit is soos 00:57. AANGESIEN kontrasteer wat saam met Donderdag, het jy ongeveer 150 het regtig beklemtoon kinders en geen roomys. En dit is net nie produktief vir enigiemand. So moraal van die storie is, kom vroeg om kantoorure en goeie dinge sal gebeur. 

Ook, kom voorbereid om vrae te vra. Jy weet? Ongeag van watter Tas, ek dink, is gesê, Ons het die afgelope tyd 'n paar studente wat kom op Donderdag by, soos, 10:50 nie die spec gelees om soos my help, help my. Ongelukkig op daardie punt, is daar nie veel wat ons kan doen om jou te help. So asseblief, kom vroeg in die week. Kom vroeg om kantoorure. Kom voorbereid om vrae te vra. Maak seker dat jy, as 'n student, is waar wat jy nodig het om dit te wees dat die Tas kan lei jou langs, en dit is wat kantoorure moet word toegeken vir. 

Tweedens, so ek weet professore hou om ons te verras met toetse. Ek het 'n professor diegene soos, hey, op die pad, onthou dat akademiese trimester jy het die volgende Maandag. Ja, ek het nie geweet oor wat akademiese trimester. So ek gaan wees dat TA wat herinner u alles wat quiz 0--, want jy weet, ons is CS. Nou dat ons gedoen het skikkings, kry jy Daarom is dit quiz 0, nie te toets 1, eh? OK. O, ek het 'n paar chuckles op daardie een. OK. 

So quiz 0 sal wees 14 Oktober as jy in die artikel Maandag-Woensdag en 15 Oktober as jy in die artikel Dinsdag-Donderdag. Dit geld nie vir dié van julle by Harvard wat- ek dink jy sal al wees neem jou vasvrae op die 14. 

So ja, volgende week, as David, in lesing gaan, ja, so daaroor quiz volgende week, julle almal sal nie geskok omdat jy het artikel en jy weet dat jou quiz 0 is in twee weke. En ons sal review het sessies en alles. So geen bekommernisse oor wat bang vir wat. Enige vrae before-- enige vrae Glad rakende logistieke probleme, gradering, kantoorure, afdelings? Ja. 

GEHOOR: So het die quiz is gaan wees tydens lesing? 

ANDI Peng: Ja. So het die quiz, dink ek, is 60 minute toegeken in daardie tydgleuf dat jy net sal neem in die lesingsaal. So jy hoef nie om in te kom op, soos, 'n ewekansige 07:00. Dit is alles goed. Ja. Koel. 

Alles reg. So ons gaan stel 'n konsep om jou hierdie week dat Dawid reeds soort van aangeraak in lesing die afgelope week. Dit is bekend as GDB. En hoe baie van julle, terwyl dit in die loop van die skryf van jou psets, het opgemerk 'n groot knoppie wat sê "Debug" op die top van jou IDE? OK. So nou gaan ons eintlik kry om opschommelen die geheim van wat dit eintlik knoppie doen nie. En ek waarborg jou, dit is 'n mooi, mooi ding. 

So tot nou toe, dink ek daar is twee dinge studente het gewoonlik nie doen wanneer debugging psets. Een, hulle óf voeg in printf () - so elke paar lyne, voeg hulle by in 'n printf () - O, wat is hierdie veranderlike? O, wat is hierdie veranderlike now-- en jy soort van sien die vordering van die kode soos dit loop. Of die tweede metode kinders doen, is dat hulle net skryf die hele ding en dan gaan soos hierdie aan die einde. Hopelik werk dit. Ek waarborg jou, GDB is beter as beide van die metodes. Ja. So dit sal jou nuwe beste vriend wees. Want dit is 'n pragtige ding wat visueel vertoon beide wat jou kode doen op 'n spesifieke punt asook wat al jou veranderlikes dra, soos wat hulle waardes is, op daardie spesifieke punt. En op hierdie manier, kan jy regtig stel inspeksiepunte in jou kode. Jy kan hardloop deur lyn deur die lyn. En GDB sal net vir jy, vertoon vir jou, wat al jou veranderlikes is, wat doen hulle, wat gaan aan in die kode. En in so 'n manier, dit is soveel makliker om te sien wat gebeur in plaas van printf-ing of die skryf van jou stellings. 

So sal ons 'n voorbeeld van dit later te doen. So dit lyk 'n bietjie abstrak. Geen sorge, sal ons voorbeelde te doen. En so in wese, die drie grootste, mees gebruikte funksies wat jy nodig het in GDB is die Volgende, stap oor, en stap in knoppies. Ek gaan aan die hoof oor daar eintlik nou. 

So kan julle sien dat al of moet ek in 'n bietjie zoom? In die rug, kan jy sien dat? Ek moet in zoom? Net 'n klein bietjie? OK, cool. Daar gaan ons. OK. 

So ek het, hier, my implementering vir gulsig. En terwyl baie van julle ouens het gulsig in while lus form-- dat is 'n baie aanvaarbare manier om dit te doen it-- ander manier om dit te doen is om net te verdeel in die modulo. Want dan kan jy jou waarde en dan jou res. En dan kan jy net voeg dit alles saam. Is die logika van wat ek doen hier sin maak vir almal, voordat ons begin? Soort van? Koel. Groot. Dit is 'n mooi stuk sexy van die kode, sou ek sê. Soos ek gesê het, David, in lesings, na 'n rukkie, jy sal al begin sien kode as iets wat mooi. En soms wanneer jy sien 'n pragtige kode, dit is so 'n wonderlike gevoel. 

So egter terwyl hierdie kode is baie mooi, beteken dit nie behoorlik werk nie. So laat hardloop check50 op hierdie punt. Check 50 20-- OOP. 2? Is dat pset2? Ja. O, pset1. OK. So loop ons check50. 

En as julle hier kan sien, dit is die versuim 'n paar van die gevalle. En vir 'n paar van julle, in die Natuurlik doen jou probleem stelle, jy soos, ah, waarom is dit nie werk nie. Hoekom is dit die werk vir 'n paar waardes, maar nie vir ander nie? Wel, GDB gaan om jou te help figuur hoekom diegene insette is nie werk nie. 

OK. So laat ons sien, een van die tjeks Ek was nie in check50 was die insette waarde van 0,41. So die korrekte antwoord wat moet jy kry is 'n 4. Maar in plaas wat ek uit te druk is die 3-n, wat is verkeerd. So laat ons net hierdie hand loop, net seker te maak dat check50 werk. Kom ons doen ./greedy. Oeps, ek het om te gulsig te maak. Daar gaan ons. Nou ./greedy. 

Hoeveel verskuldig is? Kom ons doen 0,41. En yep, sien ons hier dat dit uitdruk 3 wanneer die korrekte antwoord, in werklikheid, moet 4. So laat ingaan GDB en sien hoe ons kan gaan van hierdie probleem. 

So die eerste stap in altyd ontfouting jou kode is om 'n breekpunt te stel, of 'n punt waar jy wil hê dat die rekenaar of die debugger om te begin kyk. So as jy nie regtig weet wat jou probleem is, Gewoonlik is die tipiese ding wil ons doen, is om ons breekpunt stel by die hoof. So as jy ouens kan sien nie rooi knoppie net daar, yep, wat my opstel van 'n breekpunt vir die belangrikste funksie. Ek wat klik. 

En dan kan ek na my Debug knoppie. Ek getref dat die knoppie. Laat my terug zoom uit as ek kan. Daar gaan ons. Dus het ons hier, 'n paneel aan die regterkant. Ek is jammer, ouens in die rug, het jy kan nie regtig sien baie goed. Maar in wese, al hierdie reg paneel doen is die dop van beide die uitgelig lyn, wat is die reël van die kode dat die rekenaar tans aktief is, sowel as al jou veranderlikes af hier. 

So jy het sent, munte, n, alle verklaarde om verskillende dinge op hierdie punt. Geen sorge, want ons het nie eintlik geïnisialiseer hulle nog enige veranderlikes. So in jou rekenaar, jou rekenaar is net sien, oh, 32767 was die laaste gebruikte funksie van daardie geheue spasie in my rekenaar. En so dit is waar sent tans. Maar geen dat sodra jy die kode uit te voer, dit moet geïnitialiseerd geword. 

So laat deurgaan, lyn deur lyn, wat gaan hier aan. OK. So hier is die drie knoppies wat ek net verduidelik. Jy het die drama, of die funksie Run, knoppie, jy het die stap oor knoppie, en jy het ook die Stap in knoppie. En wese, al drie van hulle net gaan deur jou kode en doen verskillende dinge. 

So tipies, wanneer jy ontfouting, Ons wil nie net getref speel, omdat Play sal net loop jou kode om die einde van dit. En dan sal jy nie eintlik weet wat jou probleem is nie, tensy jy verskeie inbreekpunt stel. As jy verskeie inbreekpunt stel, Dit sal net outomaties hardloop van een breekpunt, na die volgende, na die volgende. Maar in hierdie geval het ons het net dat die een, want ons wil ons pad werk van bo af na onder. So ons gaan om dit te ignoreer knoppie nou vir die doel van hierdie program. 

So het die stap oor funksie net stappe oor elke enkele lyn en vertel jou wat die rekenaar doen. Die Stap in funksie gaan in die werklike funksie dit is op jou lyn van die kode. So byvoorbeeld, soos printf (), dit is 'n funksie, reg? As ek wou fisies stap in die printf () funksie, Ek sou eintlik gaan in die stuk Poskode waar printf () is geskryf en sien wat gaan aan daar. 

Maar tipies veronderstel ons dat die kode wat ons gee jou werk. Ons aanvaar die printf () werk. Ons aanvaar dat GetInt () werk. So daar is geen behoefte om stap in daardie funksies. Maar as daar funksies dat jy jouself skryf wat jy wil om te kyk uit te vind wat aangaan, jy wil om te stap in daardie funksie. 

So nou het ons net gaan om te stap oor hierdie stuk van die kode. So laat ons sien. Ag, druk, "O Hai, hoe veel verandering verskuldig is? " Ons gee nie om. Ons weet dat werk, sodat ons stap oor dit. 

So n, wat is ons float dat ons het initialized-- of declared-- by die top, ons is nou gelykstaande dat GetFloat (). So laat stap oor dit. En ons sien by die onderkant hier, die program is waarna my om insette 'n waarde. So laat die invoer van die waarde wat ons wil hê hier toets, wat 0,41. Groot. 

So nou n-- doen julle ouens sien hier by die bottom-- dit stored-- omdat ons het nog nie afgerond, dit is gestoor in hierdie soos reuse float wat 0,4099999996, wat naby genoeg is om ons doeleindes, reg nou, om 0.41. En dan sal ons sien later op, soos ons voortgaan versterking oor die program, ná hier, het N geword afgeronde en sent geword 41. Groot. So weet ons dat ons werk afronding se. Ons weet dat ons die korrekte aantal sent, sodat ons weet dat dit is nie regtig die probleem. 

So ons voortgaan versterking in hierdie program. Ons gaan hier. En so na hierdie lyn van die kode, ons moet weet hoeveel kwartale ons het. Ons stap oor. En jy sien ons, in werklikheid, het 'n kwartaal, want ons het afgetrek 25 van ons aanvanklike waarde van 41. En ons het 16 links vir ons sent. 

Maak almal verstaan ​​hoe die program is versterking deur middel van en waarom sent het nou '16 en waarom, nou, munte geword 1? Is almal wat volg logika? Koel. So as van hierdie punt, die werkende program se, reg? Ons weet dit is presies doen wat ons wil hê dit moet. En ons het nie eintlik het om uit te druk, o, wat is sent op hierdie punt, Wat is munte op hierdie punt. 

Ons gaan voort om deur die program. Stap oor. Koel. Ons gaan oor dimes. Groot. Ons sien dat dit geneem af $ 0,10 vir 'n sent. En nou het ons twee muntstukke. Dit is korrek. 

Ons gaan oor pennies en ons sien wat ons het oorgebly sent. Hmm, dit is vreemd. Hier by die program, was ek veronderstel my pennies het afgetrek. Miskien was ek net nie doen dat die lyn regs. En helaas, kan jy sien hier, want ons weet dat ons versterking deur lyne 32 en 33, dit is waar ons program onbehoorlik het veranderlikes hardloop. So kan ons kyk en sien, o, Ek trek sent hier, maar ek is nie eintlik toe te voeg tot my munt waarde. Ek is toe te voeg tot sent. En ek wil nie te voeg aan sent, ek wil toe te voeg tot muntstukke. So as ons verander muntstukke, ons het 'n werkende program. Ek kan check50 hardloop. Jy kan net verlaat uit GDB reg hier en dan weer hardloop check50. Ek kon dit net doen. Ek moet gulsig te maak. 0,41. En hier is dit druk uit die regte antwoord. 

So as julle kan sien, GDB is 'n baie kragtige instrument wanneer ons so veel kode gaan en so baie veranderlikes dat dit moeilik is vir ons, as 'n mens, om tred te hou. Die rekenaar in die GDB debugger, het die vermoë om tred te hou van alles te hou. Ek weet, in Visionaire, julle waarskynlik dalk 'n segmentering foute getref omdat jy hardloop buite perke van jou skikking. In die voorbeeld van die keiser en dis presies wat ek hier geïmplementeer. 

So ek het vergeet om te kyk vir wat sal gebeur as ek het nie twee command line argumente. Ek het net nie sit in daardie tjek. En so as ek hardloop Debug-- ek my breekpunt daar regs. Ek hardloop Debug. 

OK. Ja. So eintlik GDB was veronderstel het my vertel daar was 'n segmentering skuld daar. Ek weet nie wat aangaan reg daar, maar toe ek gehardloop het, dit werk nie. Wanneer jy reëls van die kode deur te hardloop en GDB dalk net skielik ophou op jou, optrek en kyk wat die rooi fout. Dit sal jou vertel, hey, jy het 'n segmentering skuld, wat beteken dat jy probeer om toegang ruimte in 'n skikking wat nie bestaan ​​het nie. Ja. 

So in die volgende probleem stel hierdie week, julle ouens sal waarskynlik 'n baie veranderlikes rond dryf. Jy gaan nie om seker te wees wat beteken hulle almal op 'n sekere punt. So GDB sal jy regtig help in die uitzoeken wat hulle almal gelyk en in staat is om visueel sien. Is daar iemand verwar oor hoe enige van wat werk? Koel. Alles reg. So na dit, ons is gaan na regs duik in vier verskillende tipes van spesies vir hierdie week. Hoeveel van julle, in die eerste van alles, voordat ons begin, die hele spec vir pset3 gelees het? OK. Ek is trots op julle. Dit is soos die helfte van die klas, wat aansienlik meer as die vorige keer. 

So dit is 'n groot, want toe ons praat oor die inhoud in lecture-- of jammer, in section-- Ek hou 'n baie wat verband hou terug na wat die pset is en hoe jy wil implementeer wat in jou pset. So as jy kom met lees die spec, sal dit wees 'n baie makliker vir jou om te verstaan wat ek praat as ek sê, oh hey, dit kan 'n baie wees goeie plek om hierdie soort te implementeer. So diegene van julle wat lees die spec weet dat, as deel van jou pset, jy gaan hê om skryf 'n tipe soort. So kan dit baie nuttig wees vir 'n klomp van julle vandag. 

So ons sal begin met, wese, die mees eenvoudige tipe van aard, die seleksie soort. Die tipiese algoritme vir hoe ons wil gaan oor hierdie is-- Dawid het deur middel van hierdie alles in lesing, so ek sal vinnig beweeg saam here-- is in wese, jy het 'n verskeidenheid van waardes. En dan vind jy die kleinste ongesorteerde waarde en jy ruil wat waarde met die eerste ongesorteerde waarde. En dan moet jy net aanhou herhaal met die res van jou lys. 

En hier is 'n visuele verduideliking van hoe dit sal werk. So byvoorbeeld, as ons begin met 'n verskeidenheid van vyf elemente, indeks 0-4, met 3, 5, 2, 6, en 4 waardes geplaas in die array-- so reg nou, ons net gaan om te aanvaar dat hulle is almal ongesorteerde want ons het nie anders getoets. 

So hoe 'n seleksie soort sou werk is dat dit sou eerste loop deur die geheel van die ongesorteerde skikking. Dit sou kies uit die kleinste waarde. In hierdie geval, 3, reg nou, is die kleinste. Dit raak tot 5. Nee, 5 is nie groter than-- of jammer, is nie minder nie than-- 3. So is die minimum waarde is nog steeds 3. En dan kry jy 2. Die rekenaar sien, o, 2 is minder as 3. 2 moet nou die minimum waarde wees. En so 2 swaps met daardie eerste waarde. 

So na een pas, het ons inderdaad sien dat die 2 en die 3 is omgeruil. En ons is maar net gaan om voort te gaan doen dit weer met die res van die skikking. So ons gaan net loop deur die laaste vier indekse van die skikking. Ons sal sien dat 3 is die volgende minimum waarde. So ons gaan ruil dit met 4. En dan is ons net gaan om te hou loop deur totdat uiteindelik, het jy kry om 'n gesorteerde skikking waarin 2, 3, 4, 5, en 6 is almal gesorteer. Verstaan ​​almal die logika van hoe 'n seleksie soort werk? 

Jy moet net 'n soort van 'n minimum waarde. Jy hou van wat dit is. En wanneer jy dit vind, jy het dit te ruil met die eerste waarde in die array-- of, nie die eerste value-- die volgende waarde in die skikking. Koel. 

So as julle soort gesien van 'n kort blik, Ons gaan hierdie pseudokode uit. So as jy ouens in die rug wil vorm 'n groep, almal by 'n tafel kan 'n bietjie vennoot vorm, ek gaan om julle ouens soos drie minute te gee net praat deur middel van die logika, in Engels, hoe ons in staat kan wees om te implementeer pseudokode om 'n seleksie soort skryf. En daar is lekkergoed. Kom asseblief en kry lekkergoed. As jy in die rug en jy wil lekkergoed, kan ek gooi candy aan jou. Eintlik doen you-- cool. Jammer. OK. 

So as ons wil, as 'n klas, skryf pseudokode hoe 'n mens kan nader hierdie probleem, net voel vry. Ek sal net gaan rond en, in orde is, vra groepe vir die volgende lyn van wat ons moet doen. So as jy ouens wil begin af, wat is die eerste ding wat om te doen wanneer jy probeer om te implementeer 'n manier om hierdie program te los om 'n lys selektief sorteer? Laat ons net ons aanvaar het 'n skikking, alles reg? 

GEHOOR: Jy wil 'n paar te skep soort van [onhoorbaar] dat jy loop deur jou hele skikking. 

ANDI Peng: Right. So jy gaan wil Itereer deur elke ruimte, reg? So, groot. As jy ouens wil my gee volgende line-- ja, in die rug. 

GEHOOR: Check hulle alles vir die kleinste. 

ANDI Peng: Daar gaan ons. So ons wil om deur te gaan en kyk na sien wat die minimum waarde is, reg? Ek gaan afkort dat "min." Wat doen jy ouens wil doen na jy die minimum waarde gevind het? 

GEHOOR: [onhoorbaar] ANDI Peng: So jy gaan om te wil skakel dit met die eerste van wat skikking, reg? Dit is die begin, ek gaan om te sê. Alles reg. So nou dat jy het omgeruil die eerste een, doen wat jy wil doen nadat dit? So nou weet ons dat hierdie een hier moet die kleinste waarde wees, reg? Dan moet jy 'n bykomende rus van die skikking wat ongesorteerde. So wat jy wil hê om hier te doen, as jy ouens wil vir my die volgende reël te gee? GEHOOR: So dan wil hê jy moet Itereer deur die res van die skikking. ANDI Peng: Ja. En so wat beteken iterating deur soort impliseer ons sal waarskynlik nodig? Watter tipe of-- 

GEHOOR: Ag, 'n addisionele veranderlike? ANDI Peng: Waarskynlik 'n ander vir lus, reg? So ons waarskynlik gaan om te wil through-- wonderlik om Itereer. En dan moet jy gaan om terug te gaan en check waarskynlik die minimum weer reg? En jy gaan hou herhaal hierdie, omdat die loops net gaan hou hardloop, reg? 

So as julle kan sien, het ons net 'n algemene pseudokode hoe ons wil hierdie program te kyk. Dit iteraat hier, wat doen ons tipies nodig om te skryf in ons kode as ons wil Itereer deur 'n skikking, watter tipe struktuur? Ek dink Christabel reeds hierdie gesê tevore. 

GEHOOR: 'n lus. 

ANDI Peng: 'n lus? Presies. So is dit waarskynlik gaan 'n lus vir. Wat is 'n tjek hier gaan om te impliseer? Tipies, as jy wil om te kyk as iets is iets else-- 

GEHOOR: As. 

ANDI Peng: 'n as, reg? En dan is die ruil hier, sal ons gaan oor later, want David het deur dat lesing as well. En dan die tweede iteraat implies-- 

GEHOOR: Nog lus. 

ANDI Peng: --another lus, presies. So as ons kyk op hierdie reg, ons kan sien dat ons is waarskynlik gaan 'n geneste lus nodig met 'n voorwaardelike verklaring daar en dan 'n werklike stuk kode wat gaan om die waardes te ruil. So ek het net oor die algemeen geskryf 'n pseudokode kode hier. En dan is ons eintlik gaan fisies, as 'n klas, probeer om te implementeer dit vandag. Kom ons gaan terug na hierdie IDE. 

Uh Oh. Hoekom is dit not-- daar is dit. OK. Jammer, laat ek probeer in 'n bietjie meer te zoom. Daar gaan ons. Al wat ek hier doen, is wat ek gemaak het 'n program genaamd "seleksie / sort.c." Ek het 'n verskeidenheid van nege geskep waardes, 4, 8, 2, 1, 6, 9, 7, 5, 3. Tans as wat jy kan sien, is hulle geordende. N gaan die aantal wees dat vertel jy die bedrag van waardes jy in jou skikking. In hierdie geval, het ons nege waardes. En ek het net 'n lus vir die hier wat word vertoon die ongesorteerde skikking. 

En aan die einde, het ek ook 'n vir lus wat net druk dit weer uit. So teoreties, as hierdie program korrek werk, aan die einde, jy moet sien vir 'n gedrukte lus waarin 1, 2, 3, 4, 5, 6, 7, 8, 9 is almal korrek in orde is. 

So het ons ons pseudokode het hier. Is daar iemand wat wil aan- Ek is net gaan om te gaan vra vir volunteers-- my vertel presies wat om te tik as ons wil, eerste, net Itereer deur die begin van hierdie reeks? Wat is die reël van die kode Ek is waarskynlik gaan hier nodig? 

GEHOOR: [onhoorbaar] 

ANDI Peng: Ja, voel gratis aan- jammer, jy hoef nie te up-- gevoel staan vry om jou stem te verhef 'n bietjie. 

GEHOOR: Vir int i gelyk 0-- 

ANDI Peng: Ja, goed. 

GEHOOR: i is minder as array lengte. 

ANDI Peng: So hou in omgee hier, want ons nie 'n funksie nie daardie vertel ons die lengte van 'n skikking, Ons het reeds 'n waarde dat stoor. Reg? Nog 'n ding om te hou in mind-- in 'n skikking nege waardes, wat die indekse? Laat ons net sê dit was array 0-3. Jy sien dat die laaste indeks is eintlik 3. Dit is nie 4, selfs al is daar vier waardes in die skikking. 

So hier het ons baie versigtig te wees van wat ons toestand vir die lengte gaan wees. 

GEHOOR: Sou dit nie n minus 1? ANDI Peng: Dit gaan N minus 1, presies. Maak dit sin, waarom dit is n minus 1, almal? Dit is omdat skikkings is nul-geïndekseer. Hulle begin by 0 en aanloop tot N minus 1. Ja, dit is 'n bietjie lastig. OK. En toe-- GEHOOR: Isnt'1 dat reeds versorg al is, deur net sê nie "minder as of gelyk aan "en net sê" minder as? " 

ANDI Peng: Dit is 'n regtig 'n goeie vraag. So, ja. Maar ook, die manier waarop ons die implementering van die kontrole reg wat jy nodig het om twee waardes te vergelyk. So wat jy eintlik wil laat die "na" leeg. Want as jy vergelyk hierdie een, jy gaan nie iets nadat dit te vergelyk met, reg? Ja. So i ++. Kom ons voeg ons in hakies. Oeps. Groot. So het ons die begin van ons buitenste lus. So nou waarskynlik wil ons skep 'n veranderlike vir die behoud van spoor van die kleinste waarde, reg? Is daar iemand wat my wil die gee lyn van kode wat dit sou doen? Wat moet ons as ons gaan om iets wil stoor? 

Reg. Miskien 'n beter naam vir daardie sou be-- "temp" heeltemal works-- miskien 'n meer gepaste naam sou wees, As ons wil hê dat die kleinste value-- 

GEHOOR: Min. ANDI Peng: min, is daar gaan ons. min sal goed wees. En so hier is, wat ons doen dit wil inisialiseer om? Dit is 'n bietjie lastig. Want nou by die begin van hierdie reeks, jy nie gekyk na enigiets, reg? So, wat outomaties as ons is net op i gelyk 0, wat wil ons inisialiseer ons eerste minimum waarde? GEHOOR: i. ANDI Peng: i, presies. Christabel, waarom wil ons om dit te inisialiseer om i? 

GEHOOR: Omdat, goed, ons begin met 0. So, want ons het niks om te vergelyk dit is die minimum sal uiteindelik '0. 

ANDI Peng: Presies. So sy is presies reg. Want ons het nie eintlik gekyk na enigiets nie, Ons weet nie wat ons minimum waarde is. Ons wil net inisialiseer dit i, wat tans, is hier. En as ons voortgaan om hierdie verskeidenheid te beweeg af, ons sal sien dat met elke addisionele pas, i vermeerderings. En so op daardie punt, i is waarskynlik gaan wil tot die minimum te wees, want dit gaan alles wees is die begin van die ongesorteerde skikking. Koel. 

So nou wil ons voeg 'n lus vir die wat hier gaan Itereer deur die ongesorteerde, of die res van hierdie skikking. Is daar iemand wat my wil gee 'n lyn van kode wat dit sou doen? Hint-- wat doen ons hier nodig het af? Wat gaan om te gaan in hierdie lus? Ja. GEHOOR: So ons wil wil 'n ander heelgetal, want ons loop deur die res van die skikking in plaas van die i, so miskien j. 

ANDI Peng: Ja, j klink goed vir my. Gelyk? 

GEHOOR: So sal ek plus 1, want jy begin by die volgende waarde. En dan na die end-- dit weer, j is minder as N minus 1, en dan j ++. ANDI Peng: Groot. 

En dan hier, ons gaan om te wil om te kyk om te sien of ons toestand nagekom word nie, reg? Want jy wil verander die minimum waarde As dit is eintlik kleiner as wat jy dit te vergelyk met, reg? So, wat gaan ons wil hier? Kyk om te sien. Watter tipe verklaring ons waarskynlik gaan ti wil gebruik as ons iets wil gaan? 

GEHOOR: 'n verklaring as. 

ANDI Peng: 'n verklaring as. So if-- en wat gaan wees die voorwaarde dat ons wil binnekant van ons as stelling? 

GEHOOR: As die waarde van j minder is as die waarde van i-- 

ANDI Peng: Presies. So if-- so hierdie verskeidenheid is die sogenaamde "skikking." Groot. So as array-- wat was dit? Sê dat die weer. 

GEHOOR: As array-j is minder as array-i, dan sou ons die min verander. So die min sou j wees. 

ANDI Peng: Maak dit sin? OK. En nou hier, ons eintlik wil die swap implementeer, reg? So onthou, in lesing, wat Dawid toe Hy het probeer om the-- wat wissel it-- lemoensap en milk-- 

GEHOOR: Dit was die bruto. 

ANDI Peng: Ja, dit was soort van die bruto. Maar dit was 'n baie goeie konsep toon tyd. So dink jou waardes hier. Jy het 'n verskeidenheid het van min, 'n verskeidenheid van i, of wat ook al ons probeer om hier te ruil. En jy waarskynlik kan hulle nie gooi in mekaar op dieselfde tyd, reg? So wat gaan ons nodig om hier te skep om die waardes korrek te ruil? 

GEHOOR: 'n tydelike veranderlike. 

ANDI Peng: 'n tydelike veranderlike. So kom ons doen int temp. Kyk, dit sou 'n beter tyd aan- whoa, wat was dit? OK. So dit 'n beter sou gewees het tyd om die veranderlike "temp." noem So kom ons doen int temp. Wat gaan ons stel temp gelyk aan hier? GEHOOR: Min? ANDI Peng: Dit is 'n bietjie lastig. Dit maak eintlik nie saak nie in die einde. Dit maak nie saak wat volgorde wat jy wil om te ruil in so lank as wat jy maak seker dat jy dop van wat jy uitruiling. 

GEHOOR: Dit kan array-i wees. 

ANDI Peng: Ja, kom ons doen array-i. En dan Wat is die volgende lyn van die kode wat ons hier wil hê? GEHOOR: array-i gelyk array-j. ANDI Peng: En laastens? GEHOOR: array-j gelyk array-i. GEHOOR: Of array-j gelykes array-temp-- of, temp. 

ANDI Peng: OK. So laat hierdie hardloop en sien As dit gaan om te werk. Waar is dit gebeur? O, dit is 'n probleem. Kyk, op die lyn 40, ons is probeer om array-j gebruik? Maar waar kom j slegs bestaan ​​in? 

GEHOOR: In die lus. ANDI Peng: Right. So, wat gaan ons doen? 

GEHOOR: Definieer dit buite the-- GEHOOR: Ja, ek dink jy het na 'n ander gebruik as verklaring, reg? Dus, net soos, as die minimum-- Alle reg, laat my dink. 

ANDI Peng: Guys, probeer om 'n blik Kom ons neem sien, wat is iets wat ons kan hier doen? 

GEHOOR: OK. So as die minimum nie gelyk j-- so as die minimum is nog i-- dan sou ons nie hoef te ruil. 

ANDI Peng: Is dit gelyk i? Wat wil jy hier sê? 

GEHOOR: Of ja, as die minimum nie gelyk i, ja. ANDI Peng: OK. Goed dat lost, soort, ons probleme. Maar wat nog los nie die probleem van wat gebeur as j-- sedert j bestaan ​​nie buite dit, wat wil jy ons om te doen met dit? Verklaar dat dit buite? Kom ons probeer om hierdie. Uh Oh. Ons soort werk nie. 

Soos jy, ons eerste kan sien array het daardie waardes. En daarna sal dit moet hê was in 1, 2, 3, 4, 5, 6, 7, 8, 9. Dit werk nie. Ahh. Wat doen ons? GEHOOR: Debug. ANDI Peng: Alle reg, kan ons probeer dit. Ons kan ontfout. Zoom uit 'n bietjie. Kom ons stel ons breekpunt. Kom ons gaan like-- OK. 

So, omdat ons reeds weet dat hierdie lyne, 15 deur 22, is working-- want al wat ek doen is net iterating deur en printing-- Ek kan voortgaan en slaan dit. Kom ons begin by lyn 25. Oop, laat my ontslae te raak van daardie. 

GEHOOR: So het die breekpunt se waar die ontfouting begin? ANDI Peng: of stop. GEHOOR: of stop. ANDI Peng: Ja. Jy kan verskeie inbreekpunt stel en dit kan net spring van die een na die ander. Maar in hierdie geval weet ons nie waar die fout gebeur. So wil ons net begin van die top-down. Yep. OK. 

So hierdie lyn hier, kan ons ingryp. Jy kan hier af sien, ons het 'n skikking. Dit is die waardes wat in die skikking. Het jy sien dat, hoe indeks 0, dit ooreenstem met die value-- oh, Ek gaan probeer om in te zoom. Jammer, dit is regtig hard om see-- op array indeks 0, ons het 'n waarde van 4 en dan so meer en so aan. Ons het ons plaaslike veranderlikes. Nou i is gelyk aan 0, wat ons wil hê dit moet wees. 

En so laat ons hou versterking deur middel van. Ons minimum is gelyk aan 0, wat ons wil dit ook te wees. En dan gaan ons ons tweede vir lus, as array-j is minder as array-i, wat dit was nie. So het jy sien hoe wat oorgeslaan oor dit? 

GEHOOR: So moet die as minimum, almal that-- behoort dit nie wees binne die eerste lus? ANDI Peng: Nee, want jy nog steeds wil om te toets. Jy wil 'n vergelyking doen elke tyd, selfs nadat jy deur dit uit te voer. Jy wil nie net om dit te doen op die eerste pass-through. Jy wil om dit te doen met elke bykomende pass weer. So jy wil om te kyk vir jou toestand binne. So ons is maar net gaan hou hardloop deur hier. Ek gee jou 'n wenk ouens. Dit het te doen met die feit dat wanneer jy keur van jou afhanklik is, jy nie die nagaan vir die korrekte indeks. So nou is jy kontrole vir verskeidenheid indeks van j is minder as array indeks van i. Maar wat doen jy by die begin van die lus? Is jy nie die opstel van j gelyk aan i? 

Ja, so ons kan eintlik verlaat hier die debugger. So laat ons neem 'n blik op ons pseudokode. For-- ons gaan begin by i gelyk 0. Ons gaan om te gaan om n minus 1. Kom ons kyk, het ons het dit reg? Yep, dit is reg. 

So dan binnekant hier, ons is gaan 'n minimum waarde te skep en stel wat gelyk is aan i. Het ons dit doen? Yep, het dit gedoen. Nou in ons innerlike lus, ons is gaan j doen is gelyk aan i om n 1 minus. Het ons dit doen? Inderdaad, ons het dit gedoen. 

So egter, wat ons hier te vergelyk? 

GEHOOR: j plus 1. ANDI Peng: Presies. En dan moet jy gaan om te wil stel jou minimum gelyk aan j plus 1 as well. So ek het deur dit regtig vinnig. Het jy ouens verstaan Daarom is dit j plus 1? OK. 

So in jou skikking, in jou eerste deurgaan jou lus vir int i gelyk 0, laat ons net neem aan dit is nog nie verander nie. Ons het 'n verskeidenheid van, heeltemal, net vier ongesorteerde elemente, reg? So wil ons inisialiseer i gelyk aan 0. En ek gaan net hardloop deur middel van hierdie lus. En so in die eerste slaag, gaan ons om 'n veranderlike genaamd "min" inisialiseer wat ook gelyk i, want Ons het nie 'n minimum waarde. So dit is tans gelyk aan 0 as well. En dan gaan ons om deur te gaan. En ons wil weer Itereer. Nou dat ons het gevind wat ons minimum is, wil ons deur Itereer weer om te sien of dit vergelyk, reg? So j, hier, gaan gelyke i, wat is 0. En dan as array j plus i, wat is die een wat volgende kom oor, as minder as wat jou huidige minimum waarde is, wat jy wil ruil. 

So laat ons net sê ons het het, soos, 2, 5, 1, 8. Nou, i is gelyk aan 0 en j is gelyk aan 0. En dit is ons minimum waarde. As array-j plus i-- so as die een dit is na die een wat ons is op soek na is groter as die een voor dit, dit gaan tot die minimum te word. 

So hier sien ons dat 5 is nie minder nie as dit. So dit gaan nie 5. Ons sien dat 1 is minder as 2, reg? So nou weet ons dat ons minimum is gaan die indeks waarde by 0, 1, 2. Ja? En dan wanneer jy hier sit, kan jy ruil die korrekte waardes. 

So wanneer jy ouens was net met die j voor, was jy nie op soek na die een nadat dit. Jy is op soek na dieselfde waarde, wat Daarom het hulle dit net nie om iets te doen. Maak dit sin om almal, waarom ons dat daar plus 1 nodig? OK. Nou laat net loop deur dit te maak seker dat die res van die kode korrek is. Hoekom is dit gebeur? Ag, dit is die min hier. Ons was die verkeerde waarde vergelyk. Ag nee. 

O ja, hier af was ons uitruiling die verkeerde waardes as well. Want ons is op soek na i en j. Dit is die mense wat ons nagaan is. Ons het eintlik wil hê dat die ruil minimum, die huidige minimum, met alles wat die mens buite is. En as julle kan sien af hier het ons 'n gesorteerde skikking. Dit het net te doen met die feit dat wanneer ons die beheer van die waardes wat ons is te vergelyk, ons was nie op soek na die regte waardes. Ons is op soek na dieselfde een hier, nie eintlik uitruiling dit. Jy het om te kyk na die volgende een om dit en dan kan jy ruil. So dit is wat was soort van afluister ons kode tevore. En wat ek gedoen het hier is alles die debugger kon gedoen het vir jou Ek het dit net op die raad, want dit is makliker eerder as om te probeer sien om in te zoem op die debugger. Maak dit sin om almal? Koel. 

Alles reg. Ons kan aanbeweeg na praat asimptotiese notasie, wat is net 'n fancy manier om te sê die Runtimes van al hierdie vorme. So ek weet Dawid in lesing aangeraak Runtimes. En hy het deur die hele formule hoe om die Runtimes bereken. Geen bekommernisse oor dit. As jy regtig nuuskierig op hoe dit werk, voel vry om my te praat na artikel. Ons kan loop deur die formules saam. Maar al wat jy ouens het regtig weet, is dat n kwadraat oor 2 is dieselfde ding as N kwadraat. Omdat die grootste getal, die eksponent, groei die meeste. En so is dit vir ons doeleindes, al wat ons omgee is dat reuse getal wat groei. 

So, wat is die beste geval runtime van seleksie soort? As jy gaan om om Itereer deur 'n lys en dan Itereer deur die res van die lys, hoeveel keer is gaan jy waarskynlik in die ergste case-- in die beste geval, sorry-- deur loop? Dalk is dit die beter vraag is vra, wat is die ergste geval runtime van seleksie soort. GEHOOR: N kwadraat. ANDI Peng: Dit is N kwadraat, reg. So 'n maklike manier om te dink dit is soos, enige tyd wat jy twee geneste lusse vir het, dit gaan n word kwadraat. Want nie net is jy loop deur weer jy het om terug te gaan rond en gaan deur dit weer binne vir elke waarde. So in daardie geval, jy hardloop N keer n vierkant, wat jammer is--, N tye N, wat gelyk N kwadraat. 

En sorteer is ook 'n bietjie uniek in die sin dat dit maak nie saak of dit waardes is reeds in orde is. Dit is nog steeds gaan om te loop deur anyways. Laat ons net sê dit was 1, 2, 3, 4. Ongeag of dit nie was in orde, sou dit nog steeds het gehardloop deur en nog steeds kyk na die minimum waarde. Dit sou gemaak het die dieselfde aantal tjeks elke keer, selfs al is dit het nie eintlik enigiets te raak. 

So in so 'n geval, die beste en slegste Runtimes is eintlik ekwivalent. So die verwagte runtime seleksie soort, wat ons aanwys deur die simbool van theta, theta, in hierdie geval, ook N vierkantig. Al drie hierdie sou N vierkantig. Is almal duidelik waarom die runtime is N kwadraat? 

Alles reg. So ek gaan net om vinnig te hardloop deur die res van die spesies. Die algoritme vir borrel sort-- onthou, dit was die eerste een Dawid het oor in lesing. Wese, jy stap deur die hele lys en jy jy net swap-- Vergelyk twee op 'n tyd. En as 'n mens is 'n groter, as jy net ruil hulle. So as dit is groter, sou jy te ruil. Ek het die amptelike het hier. 

So laat ons net sê jy het 8, 6, 4, 2. Jy wil vergelyk met die 8 en 'n 6. Wat jy nodig het om dit te ruil. Jy sal die 8 en 'n 4 te vergelyk. Wat jy nodig het om dit te ruil. As jy moet ruil die 8 en die 2, verander dit net so goed. So in so 'n sin, kan jy sien, gespeel oor 'n lang tydperk van die tyd, hoe die waardes soort borrel om die einde, wat is die rede waarom ons noem dit borrel soort. 

Ons wil net loop deur weer aan ons tweede slaag, en ons derde slaag, en ons vierde pass. Wese, borrelsortering net loop totdat jy nie meer swaps te maak. So in daardie sin, dit is net die algemene pseudokode vir dit. Geen sorge, dit sal alle online wees. Ons hoef nie te eintlik gaan oor hierdie. 

Ons inisialiseer net 'n toonbank veranderlike wat begin by 0. En ons Itereer deur die hele skikking. En as een waarde is-- as dit waarde is groter as wat waarde, jy gaan om dit te ruil. En dan is jy net gaan om voort te gaan. En jy gaan om te tel. En jy net gaan om te hou doen dit terwyl die toonbank is groter as 0, wat beteken dat elke keer as jy moet ruil, jy weet jy wil gaan terug en kyk weer. Jy wil nagaan hou totdat jy weet dat jy nie meer hoef te ruil. 

So, wat is die beste en die ergste geval Runtimes vir borrelsortering? En dit is eintlik verskillende hint-- van seleksie soort in die sin dat hierdie twee antwoorde is nie dieselfde nie. Dink oor wat sou gebeur in 'n geval as dit was reeds gesorteer. En dink oor wat sou gebeur as dit was in die geval waar dit was nie gesorteer. En jy kan soort van loop deur waarom dit gebeur. Ek gee jou ouens, soos, 30 sekondes om te dink oor dit. 

OK. Is daar iemand het 'n raaiskoot na wat die ergste geval runtime van borrel soort is? Ja. 

GEHOOR: sou dit wees, soos, n keer N minus 1 of iets soos dit? Soos elke keer as dit loop, dit is net soos een omruil minder dat alles wat dit was nie. 

ANDI Peng: Ja, so jy heeltemal reg. En dit is 'n saak waarin jou antwoord was eintlik meer kompleks as die een wat ons nodig het om te gee. So dit gaan run-- Ek is gaan dit alles hier te vee. Is almal goed? Kan ek hierdie vee? OK. Jy gaan om te loop deur n keer die eerste keer, reg? En hulle gaan om te loop deur N minus 1 die tweede keer, reg? En dan moet jy gaan hou gaan, n myn 2, ensovoorts. David het dit in 'n lesing, waar, as jy opgetel al daardie waardes, jy iets wat ons kry like-- yeah-- meer as 2, wat in wese net verminder af na N kwadraat. Jy gaan 'n te kry weird fraksie daar. En so weet net dat die N kwadraat altyd voorrang bo die breuk. En so in hierdie geval, die ergste runtime sou N vierkantig. As dit was in dalende orde, dink jy 'n ruil elke keer te maak. 

Wat sou, potensieel, die beste geval runtime? Laat ons net sê, as die lys was reeds in orde is, wat sal die runtime wees? 

GEHOOR: n. ANDI Peng: Dis N, presies. En waarom is dit n? GEHOOR: Omdat jy net het om te kyk na elke keer. ANDI Peng: Presies. So in die beste moontlike runtime, As hierdie lys was reeds sorted-- kom ons sê 1, 2, 3, 4-- jy wil net deur te gaan, sou jy kyk, jy sou sien, o, hulle almal pan uit. Ek het nie te ruil. Ek is klaar. So in daardie geval, dit is net n of die aantal stappe jy net het in die eerste lys om seker te maak. 

En ná, het ons nou getref invoeging soort, waar die algoritme is in wese te verdeel dit in 'n gesorteerde en ongesorteerde gedeelte. En dan een vir een, die ongesorteerde waardes ingevoeg in hul toepaslike posisies in die begin van die lys. 

So byvoorbeeld, het ons 'n lys van 3, 5, 2, 6, 4 weer. Ons weet dat dit tans ongesorteerde, want ons het net begin soek na dit. Ons neem 'n blik en ons weet dat die eerste waarde is gesorteer, reg? As jy net op soek na 'n verskeidenheid van grootte een, jy weet dat dit gesorteer. 

So dan weet ons dat die ander vier is ongesorteerde. Ons gaan deur en sien ons dat waarde. Kom ons gaan terug. Sien dat waarde van 5? Ons neem 'n blik op dit. Ons vergelyk dit met 3. Ons weet dat dit is groter as 3, so ons weet dat dit is gesorteer. So weet ons nou dat die eerste twee gesorteer en die laaste drie is nie. 

Ons neem 'n blik op 2. Ons gaan dit eers met 5. Is dit minder as 5? Dit is nie. So het ons om aan te hou kyk neer. Dan gaan jy 2 af 3. Is dit minder as? Geen. So jy weet 'n 2 moet ingevoeg in die voorste en 3 en 5 beide moet word uitgestoot. Doen dit weer met 6 en 4. En ons het net hou keur wese, waar ons gaan net, kyk, kyk. En totdat dit in die regte posisie, ons soort van net plaas dit in die regte posisie, en dit is waar die naam van dit kom uit. 

So dit is net die algoritme, pseudokode per se, soort van, oor hoe ons sal implementeer 'n invoeging soort. Pseudokode is hier. Dit is alles aanlyn. Geen bekommernisse as jy ouens is probeer om hierdie afskryf. So weereens dieselfde question-- wat sou die beste en die ergste Runtimes wees vir opname soort? Dit is baie soortgelyk aan die laaste vraag. Ek gee jou ouens, soos, 30 sekondes om te dink oor hierdie goed. 

OK Is daar iemand wil gee my die ergste runtime? Ja. 

GEHOOR: N kwadraat. 

ANDI Peng: Dit is N kwadraat. En hoekom is dit N kwadraat? 

GEHOOR: Want in omgekeerde volgorde, jy het om te gaan deur n keer n, wat is-- ANDI Peng: Ja, presies. So dieselfde as in die borrel soort. As hierdie lys is in dalende orde, is jy gaan hê om eerste keer te kyk. En dan met elke addisionele waarde, is jy gaan hê om dit teen elke enkele waarde nie, reg? En so geheel en al, jy gaan maak 'n N pass keer 'n ander N slaag, wat is N kwadraat. Wat van die beste geval? Ja. 

GEHOOR: N minus 1, want die eerste een is reeds in 'n vierkant. 

ANDI Peng: So, naby. Die antwoord is eintlik n. Want terwyl die eerste een is gesorteer, kan dit nie actually-- dit ons het net lucked uit, in wat byvoorbeeld dat 2 gebeur met die kleinste getal wees. Maar dat die saak nie altyd sal wees. As 2 reeds gesorteer in die begin maar jy lyk en daar is 'n 1 hier, die 1 gaan dit stamp. En dit gaan aan die einde up wat anyways gestamp. 

So in die beste geval, dit is eintlik net gaan om n wees. As jy het 1, 2, 3, 4, 5, 6, 7, 8, is jy gaan om te loop deur dat die hele lys keer om te kyk om te sien of alles fyn se. Is almal duidelik hardloop tye van seleksie as goed? Ek weet ek gaan deur hierdie baie vinnig. Maar net weet dat as jy weet wat die algemene konsepte, moet jy goed wees. OK. So ek sal net gee julle miskien, soos, 'n minuut om jou bure te praat op wat net 'n paar van die belangrikste verskille tussen hierdie tipes van spesies. Ons sal gaan oor wat binnekort. GEHOOR: O, OK. ANDI Peng: Ja. OK. Cool, laat herbelê as 'n klas. OK. So dit was soort van 'n ope vraag in die sin dat daar is baie van die antwoorde op hulle. En ons sal oor kortliks gaan sommige van hulle. Ek wou net om jou te ouens dink oor wat onderskei al drie tipes van spesies. En ek hoor, ook 'n groot question-- wat beteken fuseren soort doen? Groot vraag, want dit is wat ons oor die volgende. 

So saamsmelt soort is die een soort wat funksies baie verskillend van die ander soorte. As julle ouens kan see-- het Dawid doen demo waar hy al die cool geluide van sien hoe saamsmelt sorteer gehardloop, soos, oneindig vinniger as die ander twee tipes? OK. So dit is omdat merge soort implemente wat verdeel en oorwin konsep wat ons het gepraat oor 'n baie in lesing. In daardie sin dat ons wil werk slimmer, nie harder, wanneer jy verdeel en oorwin probleme, en verbreek hulle af, en dan sit hulle saam, goeie dinge altyd gebeur nie. 

So die manier wat saamsmelt werk soort wese is dat dit 'n verdeel ongesorteerde verskeidenheid in die helfte. En dan is dit het twee helftes van skikkings. En dit net sorteer die twee helftes. Dit hou net verdeel in die helfte, in helfte, in die helfte tot alles is gesorteer en dan rekursief sit dit alles saam. 

So dit is regtig abstrakte. So dit is net 'n bietjie van pseudokode. Maak dit sin in die manier waarop dit bestuur? So laat ons net sê jy het 'n verskeidenheid van n elemente, reg? As n is minder as 2, kan jy terugkeer. Omdat julle weet dat as daar net een ding, moet dit gesorteer. Anders, jy die linker helfte sorteer, en dan kan jy die regter helfte sorteer, en dan sal jy saam te smelt. 

Dus, terwyl dit lyk regtig maklik, in werklikheid, dink oor dit soort moeilik. Omdat jy soos, Wel, dit is soort van loop op sigself. Reg? Dit loop op sigself. So in daardie sin, David aangeraak op rekursie in die klas. En dit is 'n konsep sal ons praat oor meer. Dit is dat hierdie, hierdie twee lyne hier, eintlik net die program vertel dit aan homself te hardloop met verskillende insette. So eerder as self hardloop met die geheel van n elemente, jy kan dit af te breek in die linkerhelfte en die regter helfte en weer hardloop dit dan. 

En dan sal ons kyk na dit visueel, want ek is 'n visuele leerder. Dit werk vir my beter. So sal ons kyk na 'n visuele voorbeeld hier. 

Kom ons sê ons het 'n skikking, ses elemente, 3, 5, 2, 6, 4, 1, nie gesorteer. Alle reg, daar is 'n baie op hierdie bladsy. So as jy ouens kan kyk na die eerste stap hier, 3, 5, 2, 6, 4, 1, jy kan dit verdeel in die helfte. Jy het 3, 5, 2, 6, 4, 1. Jy weet dat hierdie aren't-- jy weet nie of hulle is gesorteer is of nie, sodat jy hou breek hulle af, in die helfte, in die helfte, in die helfte, totdat uiteindelik, jy net een element. En een element is altyd gesorteer, reg? 

So ons weet dat 3, 5, 2, 4, 6, 1, deur hulself, gesorteer. En nou kan ons hulle saam terug. So ons weet die 3, 5. Ons het die saam. Ons weet dit is gesorteer. Die 2 se nog steeds daar. Ons kan die 4 en die 6 saam te stel. Ons weet dat dit is gesorteer, sodat ons sit dit saam. En die 1 is daar. 

En dan moet jy net kyk na hierdie twee helftes hier. Jy het die 3, 5, 2, 2, 3, 5. Jy kan net vergelyk die begin van alles. Omdat jy weet dat dit is gesorteer en jy weet dat dit is gesorteer. So dan het jy nie eens hoef te vergelyk die 5, jy net vergelyk die 3. En die 2 is minder as 3, so jy weet 2 moet gaan in die einde. 

Dieselfde ding daar. Die 1 moet hier gaan. En dan wanneer jy gaan om te sit daardie twee waardes bymekaar jy weet dat dit gesorteer en jy weet dat wat gesorteer. So dan is die 1 en die 2, die 1 is minder as 2. Dit vertel jou dat die 1 moet gaan op die einde van hierdie sonder om selfs na 3 of 5. En dan is die 4, kan jy net kyk, dit gaan reg in hier. Jy hoef nie te kyk na die 5. Dieselfde ding met die 6. Jy weet dat die 6-- is dit net hoef nie te kyk. 

En so op dié manier, jy is net jouself spaar 'n baie stappe wanneer jy vergelyk. Jy hoef nie elke vergelyk element teen ander elemente. Jy vergelyk net teen die kinders wat jy nodig het om dit te vergelyk. So dit is soort van 'n abstrakte konsep. Geen bekommernisse as dit nie heel slaan jy nog reg is. Maar oor die algemeen, is dit hoe 'n merge soort werk. Vrae, vinnige vrae, voordat ek aanbeweeg? Ja. 

GEHOOR: So jy sê dat jy te neem die 1, en dan die 4 en die 6 en sit dit in. So is nie those-- is nie jy kyk na hulle as afsonderlike elemente, nie as die geheel? ANDI Peng: Ja. So wat gebeur is dat jy basies skep 'n splinternuwe reeks. So jy weet dat hier, ek het twee skikkings grootte 3, reg? So jy weet dat my gesorteerde skikking moet tot ses elemente. Sodat jy net skep 'n nuwe bedrag van die geheue. So jy soort van soos om verkwistende van die geheue, maar dit maak nie saak want dit is so klein. So jy kyk na die 1 en jy kyk na die 2. En jy weet dat die 1 is minder as 2. So jy weet dat 1 in te gaan die begin van al daardie. 

Jy hoef nie eens te kyk na die 3 en die 5. So weet jy 1 daar gaan. Dan moet jy basies afkap die 1. Dit is, soos, dood vir ons. Dan het ons net 2, 3, 5, en dan 4 en 6. En dan moet jy weet dat jy vergelyk die 4 en die 2, O, die 2 moet in daarheen te gaan. So jy plop die 2 af, het jy dit afkap. So dan is jy net die 3 en die 5 in die 4 en die 6. En jy hou net kap dit af totdat jy sit hulle in die skikking. 

GEHOOR: So jy net altyd is vergelyk die [onhoorbaar]? 

ANDI Peng: Presies. So in daardie sin, is jy net vergelyk, in wese, een getal teen die ander getal. En omdat jy weet dat dit gesorteer jy hoef nie te kyk deur al die getalle. Jy hoef net te kyk na die eerste een. En dan kan jy net plop hulle af, want jy weet hulle hoort waar hulle nodig het om te behoort. Ja. Goeie vraag. 

En dan as iemand van julle is 'n bietjie ambisieus, voel vry om te kyk na hierdie kode. Dit is eintlik die fisiese implementering hoe ons merge soort sou skryf. En jy kan sien, is dit 'n baie kort. Maar die idees agter dit is redelik kompleks. So as jy voel soos teken dit uit in jou huiswerk vanaand, voel vry om. 

OK. En Dawid het ook oor hierdie in lesing. Wat is die beste geval Runtimes, ergste geval Runtimes, en die verwagte Runtimes van merge soort? 'N Paar sekondes om te dink. Dit is baie moeilik, maar soort van intuïtief as jy daaroor dink. Alles reg. 

GEHOOR: Is die ergste geval N log n? ANDI Peng: Presies. En hoekom is dit N teken n. 

GEHOOR: Is dit nie omdat dit raak eksponensieel vinniger, so dit is soos 'n funksie van die in plaas van net bloot N kwadraat of iets? ANDI Peng: Presies. So die rede waarom die runtime op hierdie N log N is because-- wat is jy doen in al hierdie stappe? Jy is net kap dit in die helfte, reg? En so wanneer ons doen die teken, al wat dit doen is 'n probleem te verdeel in die helfte, in die helfte, in die helfte, in meer helftes. En in daardie sin, kan jy soort van elimineer die lineêre model dat ons het al met behulp. Want as jy kap dinge in die helfte, dit is 'n log. Dit is net die wiskundige manier wat dit. 

En dan uiteindelik, aan die einde, jy is net om 'n laaste aangee deur almal van hulle in orde te bring, reg? En so as jy net kyk een ding, dit is n. En so is jy soort die twee bymekaar te vermenigvuldig. So dit is soos jy dat die finale het kyk vir N down hier met 'n log van N hier. En as jy vermenigvuldig hulle, dit is n teken n. 

En so het die beste geval en die ergste geval en verwag almal n teken n. Dit is ook 'n ander soort soos. Dit is soos seleksie soort in die sin dat dit maak nie saak wat jou lys is, is dit net gaan om dieselfde ding te doen elke keer. OK. So as julle kan sien, selfs al die soort wat ons through-- N gegaan het kwadraat, dit is nie baie doeltreffend nie. En selfs hierdie N log N is nie die mees doeltreffende. As jy ouens is nuuskierig, daar is soort meganismes wat so doeltreffend dat hulle is byna wese plat in runtime. 

Jy het 'n paar log N se. Jy het 'n paar log log N se. Ons het nie op hulle raak in hierdie klas nou. Maar as jy ouens is nuuskierig, voel vry om Google wat is die mees doeltreffende sorteer meganismes. Ek weet nie, is daar 'n paar baie snaakse kinders, like-- daar is 'n paar baie snaaks dié wat mense maak. En jy wonder hoe hulle ooit daaraan gedink nie. So Google, as jy 'n paar ekstra tyd op, wat is 'n paar snaakse maniere dat people-- asook doeltreffende ways-- mense in staat was om allerhande implementeer. OK. En hier is net 'n handige klein grafiek. Ek weet almal van julle, voordat die quiz 0, sal wees in jou kamer waarskynlik probeer om te onthou dat. So dit is lekker daar vir julle. Net nie die logika wat made-- vergeet waarom dié nommers is wat plaasvind. As jy altyd verloor het, maak net seker dat jy weet wat die vorme is. En jy kan deur middel van hardloop hulle in jou gedagtes om uit te vind waarom diegene antwoorde is die antwoorde. 

Alles reg. So ons gaan om te beweeg op, uiteindelik, om te soek. Want soos dié van julle wat die pset gelees het, soek is ook deel van probleem hierdie week se stel. Jy sal gevra word om te implementeer twee tipes navrae. Een is 'n lineêre soek en een is 'n binêre soek. 

So die lineêre soek is redelik maklik. Jy wil net om te soek element van 'n lys om te sien of jy dit kry. Jy moet net om deur te Itereer. En as dit gelyk iets jy kan net terug nie, reg? Maar die een wat ons die meeste belangstel in praat oor is binêre soek, regs, wat is die verdeel en oorwin meganisme wat David is bewys in lesing. 

Onthou die telefoon boek byvoorbeeld dat hy hou die opvoeding, die een wat hy soort van gesukkel 'n bietjie op die afgelope jaar, waar jy die probleem verdeel in die helfte, in die helfte, in die helfte, weer en weer, totdat jy kry wat jy soek? En jy het die runtime van wat as goed. En jy kan sien, is dit aansienlik meer doeltreffende as enige ander tipe search. 

So die manier waarop ons te werk sal gaan implementering van 'n binêre soek is, as ons het 'n skikking, indeks 0-6, sewe elemente, ons kan kyk in die middel, right-- Jammer, as ons vraag first-- As ons wil hê dat die vraag vra, doen die skikking bevat die element van 7, natuurlik, om die mens, en met so 'n klein verskeidenheid, is dit maklik vir ons om te sê ja. Maar die manier om 'n binêre implementeer soek sal wees om te kyk in die middel. 

Ons weet dat indeks 3 is die middel, omdat ons weet daar is sewe elemente. Wat 7 gedeel deur 2? Jy kan afkap daardie ekstra 1. Jy het 3 in die middel. So is verskeidenheid van 3 tot 7 gelyk? Dit is nie, reg? Maar ons kan 'n paar tjeks te doen. Is verskeidenheid van 3 minder as 7 of is verskeidenheid van 3 groter as 7? 

En ons weet dat dit is minder as 7. So weet ons dat, oh, moet dit nie in die linker helfte. Ons weet dat dit moet wees in die regter helfte, reg? So kan ons net afkap helfte van die skikking. Ons het nie eens ' kyk na dit nie. Omdat ons weet dat die helfte van ons problem-- ons weet dat die antwoord is in die regter helfte van ons probleem. So ons net kyk na wat nou. 

So nou kyk ons ​​na die middel van wat oorbly. Dit indeks 5. Ons doen dieselfde tjek weer en ons sien dat dit is kleiner. So ons kyk na die links van daardie. En dan sien ons dat tjek. Is die skikking waarde op indeks 4 gelyk aan 7? Dit is. So kan ons ware terugkeer, want Ons het gevind dat die waarde in ons lys. Is die manier wat ek het deur dit sin maak om almal? OK. Ek sal julle miskien gee, soos, drie, vier minute om uit te vind Hoe om hierdie pseudokode in. 

So dink ek jou gevra om 'n skrywe funksie genoem soek () wat omgedraai 'n waarde, 'n Boolese waarde, dit was waar of false-- soos, waar as jy gevind dat die waarde, valse as jy nie het nie. En dan was jy geslaag in die waarde wat jy soek na waardes, wat is die array-- o, ek het beslis sit wat op die verkeerde plek. OK. In elk geval, wat moet het aan die regterkant van waardes is. En dan int n die aantal elemente in daardie skikking. Hoe sou jy te werk gaan probeer dat die probleem in pseudokode? Ek sal julle ouens soos gee drie minute om dit te doen. Nee, ek dink daar is only-- ja, daar is een reg hier. GEHOOR: Kan ek? ANDI Peng: Ja, ek het jou. Is dat werkende? OK, cool. 

OK. Alle regte ouens, ons is gaan om dit in toom. OK. So aanvaar ons het hierdie pragtige gekry bietjie verskeidenheid met n waardes in. Ek het nie die lyne te trek. Maar hoe sou ons gaan oor probeer om hierdie te skryf? Is daar iemand wat wil gee my die eerste reël? As jy wil om my te gee die eerste reël van hierdie pseudokode. 

GEHOOR: [onhoorbaar] GEHOOR: Jy wil hê om through-- Itereer GEHOOR: Net nog lus? GEHOOR: --for. 

ANDI Peng: So hierdie een is 'n bietjie lastig. Dink about-- jy wil hou die loop van hierdie lus oor en oor weer tot wanneer? 

GEHOOR: Totdat die [onhoorbaar] waarde is gelyk aan die waarde. ANDI Peng: Presies. Sodat jy kan eintlik net write-- ons kan selfs vereenvoudig meer. Ons kan net nie 'n while lus, reg? Sodat jy kan net loop-- ons weet dat dit 'n rukkie. Maar vir nou, ek gaan deur wat - om te "loop" sê? Loop until-- wat ons eindig toestand? Ek dink ek het dit gehoor. Ek het gehoor iemand sê dit. 

GEHOOR: Waardes gelyk middel. ANDI Peng: Sê dit weer. GEHOOR: Of totdat die waarde wat jy soek vir is gelyk aan die middelste waarde. 

ANDI Peng: Wat as dit nie daar? Wat as die waarde wat jy op soek is vir nie eintlik in hierdie reeks? GEHOOR: Jy terugkeer 1. 

ANDI Peng: Maar wat wil ons lus totdat as ons 'n toestand? Ja. 

GEHOOR: Tot daar net een waarde? ANDI Peng: Jy kan loop until-- sodat jy weet dat jy gaan 'n maksimum waarde, reg? En jy weet dat jy gaan om 'n min waarde, reg? Omdat ook dit is iets Ek het vergeet om voor te sê, dat iets wat krities oor binêre soek is dat jou array reeds gesorteer. Want daar is geen manier om dit te doen hierdie as hulle is net random waardes. Jy weet nie of die een is groter as die ander, reg? 

So jy weet dat jou maksimum en jou min is hier, reg? As jy gaan om te pas jou maksimum in jou min en die mid-- laat ons net aanvaar jou mid waarde is reg here-- jy gaan basies lus totdat jou minimum is ongeveer dieselfde as jou maksimum, regs, of as jou maksimum is nie dieselfde as jou min. Reg? Want as dit gebeur, moet jy weet dat jy uiteindelik het getref dieselfde waarde. So jy wil loop totdat jou min minder as of gelyk aan- oops, nie minder as of gelyk aan, die ander manier around-- Max is. 

Het dit sin maak? Ek het 'n paar drieë wat reg te kry. Maar lus totdat jou maksimum waarde is in wese byna minder as of gelyk aan jou minimum, reg? Dit is wanneer jy weet wat jy geconvergeerde. GEHOOR: Wanneer sal jou maksimum waarde minder as die minimum wees? ANDI Peng: As jy hou aanpassing dit, wat is wat ons gaan om te doen in hierdie. Maak wat sin maak? Minimum en maksimum is net heelgetalle dat ons waarskynlik gaan wil skep om aan te hou spoor van waar ons is op soek na. Omdat die skikking bestaan ongeag van wat ons doen. Soos ons is nie eintlik fisies afkap die skikking, reg? Ons is net die aanpassing waar ons is op soek na. Maak wat sin maak? 

GEHOOR: Ja. 

ANDI Peng: OK. So as dit is die toestand van ons lus, wat wil ons binnekant van hierdie lus? Wat gaan ons te wil doen? So nou, ons het 'n maksimum en 'n min, regs, waarskynlik geskep hier iewers. Ons gaan waarskynlik wil om 'n middel, reg te kry? Hoe gaan ons te wees in staat wees om die middel te vind? Wat is die mathematical-- GEHOOR: Max plus min gedeel deur 2. ANDI Peng: Presies. Maak wat sin maak? En moenie julle sien waarom ons het nie net use-- hoekom ons dit gedoen het in plaas van om net N gedeel deur 2? Dit is omdat 'n waarde is N wat gaan om dieselfde te bly. Reg? Maar soos ons pas ons minimum en maksimum waardes, gaan hulle om te verander. En as 'n gevolg, ons middelste gaan ook verander. So dit is waarom ons wil hierdie reg hier doen. OK. 

En dan, noudat ons het our-- gevind ja. 

GEHOOR: Net 'n vinnige question-- wanneer jy sê min en max, ons die veronderstelling dat dit is reeds gesorteer? 

ANDI Peng: Ja, dit is eintlik 'n voorvereiste vir 'n binêre soek, dat jy weet dit is gesorteer. Wat is die rede waarom soort, jy skryf in jou probleem voor jou binêre soek. OK. So nou dat ons weet waar ons middelpunt is, wat wil jy hier doen? 

GEHOOR: Ons wil om te vergelyk dat die ander een nie. ANDI Peng: Presies. So jy gaan om te vergelyk mid waarde, reg? En wat beteken dat vertel ons wanneer ons dit vergelyk? Wat wil ons daarna doen? 

GEHOOR: Indien die waarde is groter as die middel, wil ons dit uit te roei. ANDI Peng: Presies. So as die waarde is groter as die middel, ons is gaan wil hierdie verander minimum en maxes, reg? Wat wil ons verander? So as ons weet wat die waarde is iewers hier, wat jy doen ons om te verander? Ons wil ons verander minimum tot middel wees, reg? En dan anders, as dit in hierdie helfte, wat wil ons verander? 

GEHOOR: Jou maksimum. ANDI Peng: Ja. En dan is jy net gaan hou herhaling, reg? Want nou, na een iterasie deur, het jy 'n maksimum het hier. En dan kan jy 'n mid herbereken. En dan kan jy vergelyk. En jy gaan om voort te gaan totdat die mins en die maxes het in wese geconvergeerde. En dit is wanneer jy weet dat jy die einde van dit het getref. En óf jy het dit gevind of jy het nie op daardie punt. 

Maak dit sin om almal? OK. Dit is redelik belangrik, want jy het om te skryf in jou kode vanaand. Maar julle ouens het 'n goeie sin van wat jy moet doen, wat goed is. OK. So ons het ongeveer sewe minute oor artikel. So ons gaan om te praat oor hierdie pset dat ons sal moet doen. So die pset is verdeel in twee helftes. Die eerste helfte behels implementering van 'n vonds waarin jy 'n lineêre soek skryf, 'n binêre soek, en 'n sorteer algoritme. 

So dit is die eerste keer in 'n pset waar ons sal gee jou ouens wat genoem verspreiding kode, wat is die kode dat ons pre-geskrewe, maar net links 'n paar stukkies af vir jou om met skryf. So julle ouens, as jy kyk na hierdie kode, kan jy regtig bang. As jy net wil, ahh, ek weet nie wat dit doen, Ek weet nie, soos, wat lyk asof dit so ingewikkeld, ahh, ontspan. Dit is OK. Lees die spec. Die spec sal presies aan jou te verduidelik wat al hierdie programme doen. 

Byvoorbeeld, is 'n program generate.c wat sal kom met jou pset. Jy hoef nie eintlik om dit aan te raak nie, maar jy moet verstaan ​​wat dit doen. En generate.c, al is dit te doen, is óf genereer ewekansige getalle of jy kan dit gee 'n saad, soos 'n voorafgereëlde getal wat dit neem, en dit genereer meer getalle. So is daar 'n spesifieke manier om implementeer generate.c waarin jy kan net 'n klomp van die nommers vir jou om jou ander metodes te toets op. 

So as jy wil, vir Byvoorbeeld, toets jou vonds, jy wil generate.c hardloop, genereer 'n klomp van die nommers, en dan loop jou helpers funksie. Jou helpers funksie is waar jy is eintlik fisies kode skryf. En dink aan helpers as 'n biblioteek lêer jy skryf dit vind roep. En so binne helpers.c, sal jy doen die soek en sorteer. 

En dan gaan jy in wese net sit hulle almal saam. Die spec sal jou vertel hoe om sit dit op die command line. En jy sal in staat wees om te toets of nie jou soort en soek werk. Koel. Het iemand al begin en teëgekom probleme of vrae hulle nou met hierdie? OK. 

GEHOOR: wag. Ek het 'n vraag. 

ANDI Peng: Ja. 

GEHOOR: So ek begin doen die lineêre soektog in helpers.c en dit was nie regtig werk. Maar dan later, het ek uitgevind het ons net het om dit te verwyder en te doen binêre soek. So maak dit saak as dit nie werk nie? 

ANDI Peng: Kort antwoord is nee. Maar aangesien ons not-- GEHOOR: Maar niemand se eintlik nagaan. ANDI Peng Ons is nooit gaan om te sien dat. Maar jy waarskynlik wil om te maak seker dat jou werk soek. Want as jou lineêre soek nie werk nie, dan is die kans is jou binêre soek gaan nie so goed werk. Aangesien u soortgelyke het logika in beide van hulle. En nee, dit maak nie regtig saak nie. So die enigste jy draai in is soort en binêre soek. Ja. 

En ook, 'n baie van die kinders was probeer om helpers.c saam te stel. Jy is nie eintlik toegelaat om dit te doen, want helpers.c het nie 'n hooffunksie. En so moet jy net wees eintlik die opstel genereer en vind, want oproepe vind helpers.c en die funksies binne dit. So wat maak debugging 'n pyn in die boude. Maar dit is wat ons moet doen. GEHOOR: Jy maak almal net, reg? ANDI Peng: Jy kan net maak al so goed, ja. OK. So wat is dit in terme van wat die pset vra julle almal om te doen. As jy enige vrae het, voel vry om my te vra na artikel. Ek sal hier wees vir, soos, 20 minute. 

En ja, die pset se regtig nie so sleg nie. Julle moet OK. Hierdie, volg riglyne. Soort het 'n gevoel van, logies, wat behoort te gebeur en jy sal goed wees. Moenie te bang wees nie. Daar is 'n baie van die kode reeds daar geskryf is. Moenie te bang wees nie as jy dit nie doen nie verstaan ​​wat dit alles beteken. As dit is 'n baie, dit is heeltemal fyn. En kom na kantoorure. Ons sal jou help om 'n blik te neem. 

GEHOOR: Met die ekstra funksies, moet ons diegene up? 

ANDI Peng: Ja, dit is in die kode. In die spel van die 15, die helfte van dit is reeds vir jou geskryf. So daardie funksies is reeds in die kode. Yep. Alles reg. Wel, die beste van geluk. Dit is 'n gruwel dag. So hopelik julle ouens nie te voel sleg oor bly binne en kodering.