SPEAKER 1: ħej kulħadd! Merħba lura għat-taqsima. Ferħan li tara tant minnkom kemm hawn, u kulħadd li s jaraw online. Allura, bħas-soltu welcome back. Nispera li intom kollha kellhom sabiħ weekend, sħiħ ta 'mistrieħ, rilassament. Hija kienet sabiħa bieraħ. So, I hope inti tgawdi l-barra. 

Allura l-ewwel koppja ta 'avviżi. Gradazzjoni. Allura, ħafna minnkom għandu gotten email mill me dwar Pset Scratch tiegħek, kif ukoll gradazzjoni għall Pset 1. Allura, affarijiet biss ftit. Ikunu żguri li jużaw check50 fil style50. Dawn huma intenzjonati li jkunu riżorsi għall inti guys, biex taċċerta ruħek li qed jkollna punti kemm inti tista ' mingħajr ma inutilment jitilfu minnhom. Allura, affarijiet simili istil huma importanti ħafna. Aħna ser jieħdu off għal dan. Xi wħud minnkom jista 'jkollok diġà ndunat li minn Pset tiegħek. U check50 huwa biss mod verament faċli biex tagħmel żgur li aħna qed attwalment jirritornaw liema jeħtieġ li jiġi rritornat lill-utent, u li kollox ta 'ħidma kif suppost. 

Fuq it-tieni nota, kun żgur tiegħek uploading affarijiet għall-folder korretta. Hija tagħmel il-ħajja tiegħi biss ftit aktar diffiċli jekk inti upload Pset 2 fis Pset 1 għaliex meta I affarijiet download, dawn ma download b'mod korrett. U naf huwa wonky ftit f'sistema biex jidraw, imma biss tkun super bir-reqqa, jekk biss għalija, b'tali mod li meta int jkollna emails fil like 02:00 u jien gradazzjoni. Jekk ma jikkawżax I jkollha tħares kollha madwar għall Pset tiegħek. Kessaħ. 

Naf huwa kmieni, imma I totalment ltqajna meħuda off guard minn esej li dovut din il-ġimgħa, li professuri tiegħi kienu biss nixtieq, oh yeah. Ftakar, inti għandek essay dovut nhar il-Ġimgħa. So, I know-ebda waħda jħobb biex jaħsbu dwar midterms, iżda l-ewwel kwizz tiegħek huwa fuq 15 Ottubru, li ottubru qed jibda din il-ġimgħa. Allura, jista 'jkun qabel milli suppost mistenni hija kollha. Hekk li int mhux mibrum off guard meta Nsemmi taqsima ġimgħa d-dieħla li oh, kwizz ġimgħa d-dieħla tiegħek, ħsibt I d jagħtuk ftit aktar ta 'kapijiet up issa. 

Allura, il-problema tiegħek sett, numru tlieta. Kif in-nies qrajt l- spec out ta 'kurżità? OK. Aħna ltqajna koppja. Tip ta 'isfel mill-aħħar ġimgħa iżda li OK. Naf li kien barra sbieħ. Hekk Break Out. Żgur wara ikollok jsir illum taqra spec tiegħek mill-inqas ipprova bħal tniżżil kodiċi distribuzzjoni u t-tmexxija bħall-ewwel inizjali ħaġa li jgħidlek biex. Għaliex aħna qed jużaw kodiċi ta 'distribuzzjoni u librerija li konna biss qed using-- --It biss it-tieni darba aħna ghamilt dan Pset, affarijiet crazy jista 'jiġri mal-appliance tiegħek, u inti tixtieq li ssib li out issa versus aktar tard. 

Għaliex jekk huwa lejl il-Ħamis jew huwa Erbgħa bil-lejl u għal xi raġuni appliance tiegħek biss ma tixtieq li tmexxi bl-librerija jew mad-distribuzzjoni kodiċi, li l-mezzi inti ma tista 'anki jibdew jagħmlu l-kodifikazzjoni. Għaliex inti ma tistax tiċċekkja biex tara jekk din taħdem. Ma gonna tiegħek tkun kapaċi biex tara jekk jikkompila. Inti tixtieq li tieħu kura ta 'dawk fil-bidu il-ġimgħa, meta inti xorta tista 'email me jew wieħed mill-TFS oħra, u nistgħu jiksbu dawk iffissati. Għaliex dawk huma kwistjonijiet li huma ser tieqaf milli tagħmel kwalunkwe progress reali. Mhuwiex simili bug wieħed, li inti tista 'biss tip ta' skip fuq. Jekk int wara kwistjonijiet mal tiegħek appliance jew kodiċi ta 'distribuzzjoni, int verament tixtieq li tikseb li jittieħdu kura ta 'mill-aktar. Għalhekk anki jekk int ma gonna attwalment tibda kodifikazzjoni, tniżżel il distribuzzjoni kodiċi, aqra l-spec, kun żgur kollox ta 'ħidma hemmhekk. OK? Jekk inti tista 'biss tagħmel dan, I wegħda ħajja tiegħek se jkun aktar faċli. U hekk int probabbilment se biex tagħmel dan id-dritt issa dritt? OK. Allura, xi mistoqsijiet hemmhekk? Kwalunkwe affarijiet loġistiċi? Kulħadd huwa tajjeb? OK. 

Ċaħda ta 'responsabbiltà għal dawk ta' inti fil-kamra u online. Jien ser tkun qed tipprova li jaqilbu bejn PowerPoint fil-appliance għaliex aħna qed tmur li tkun qiegħda tagħmel xi kodifikazzjoni illum mid-domanda popolari ta 'l-anonimu poll suġġeriment I bagħtet aħħar ġimgħa. Allura, aħna se tkun qiegħda tagħmel xi kodifikazzjoni. Allura, jekk inti guys tixtieq ukoll li fire up apparat tiegħek, u inti għandek ltqajna email mill me, ma fajl kampjun. Nitolbok li tħossok liberu li tagħmel dan. 

Allura, aħna qed tmur biex jitkellmu dwar GDB, li huwa debugger. Li għaddej biex jgħinek tip ta 'figura fejn affarijiet sejrin ħażin fil-kodiċi tiegħek. Huwa tassew biss mod biex inti pass permezz kodiċi tiegħek kif jiġri, u jkun kapaċi li jistampa varjabbli jew tara x'inhu verament jiġri taħt il-barnuża versi programm tiegħek biss running, huwa simili faulting, u int simili, l-ebda idea dak li ġara biss hawn. I do not know liema linja hija naqset bi. I do not know fejn marret ħażin. Allura, GDB se jgħinuk ma 'dak. Ukoll, jekk inti tiddeċiedi li tkompli iva, u jieħdu 61, dan se verament, verament tkun tiegħek aqwa ħabib, jikkawżaw I jista 'jgħidlek għaliex jien għaddejjin dik il-klassi. 

Aħna qed tmur biex tħares lejn binarju tfittxija, li jekk inti guys tiftakar l-eżempju ktieb tat-telefon kbir spettaklu mill-klassi. Aħna ser tkun implimentattivi li, u mixi permezz ta 'dak ftit aktar, u allura aħna qed tmur permezz ta 'erba xorta differenti, li huma Bubble, Għażla, Inserzjoni, u Jingħaqdu. Kessaħ. Allura, GDB kif semmejt, huwa debugger. U dawn huma tip ta 'l-big affarijiet, il-funzjonijiet kbar jew l-ordnijiet li tuża ġewwa GDB, u jien se jimxu inti permezz demo ta 'dan fit-tieni. 

Allura, dan mhux biss ser jibqgħu astratt. I ser jippruvaw u jagħmilha bħala konkreti kemm possibbli għalik guys. Allura, break. Hija ser jkun jew pawża bħal, xi numru, li jirrappreżenta linja fil-programm tiegħek, jew inti tista 'isem funzjoni. Allura, jekk inti tgħidli break prinċipali, se tieqaf fil prinċipali, u let inti timxi permezz dik il-funzjoni. 

Bl-istess mod, jekk għandek xi esterna funzjoni bħal Swap jew Cube, li ħarisna lejn ġimgħa li għaddiet. Jekk tgħid break wieħed minn dawk, kull meta program tiegħek hits li, inneħħu stenna għalik biex għid x'għandek tagħmel. Qabel se biss tesegwixxi sabiex inti tista 'effettivament pass ġewwa l-funzjoni u ara x'inhu għaddej. Allura, Sussegwentement, ftit skips fuq il- linja li jmiss, tmur fuq il-funzjonijiet. Pass. Dawn huma kollha astratt ftit. Allura, jien biss ser jimxu permezz tagħhom, iżda inti ser tara minnhom fl-użu fit-tieni. 

Pass lejn funzjoni. So I kif kien qal, bħal ma Swap, ikun jippermettu li inti fil-fatt kif jekk int bħal fiżikament titjib ġewwa, inti tista mess ma 'dawk varjabbli, print out dak li huma, tara x'inhu għaddej. Lista se litteralment biss print l-kodiċi tal-madwar. Allura, jekk inti tip ta tinsa fejn inti fil-programm tiegħek, jew int mintix x'inhu għaddej madwaru, dan se biss jistampa segment ta simili ħames jew sitt linji madwaru. Allura, inti tista 'tikseb orjentati dwar fejn int. 

Stampa xi varjabbli. Għalhekk, jekk inti għandek l-muftieħ simili fil Caesar, li aħna ser tħares lejn. Tista 'tgħid Stampa Key fi kwalunkwe punt. Hija ser jgħidlek dak il-valur huwa tant li, forsi x'imkien matul it-triq, inti overwrote prinċipali tiegħek. Inti tista 'attwalment tgħid li minħabba inti tista 'attwalment josservaw dak il-valur. 

Fil-lokal, biss prints out varjabbli lokali tiegħek. Allura, ghaċ int fi loop, u inti biss trid tara simili, oh. X'inhu I tiegħi? X'inhu dan il-valur ewlieni li I initialize hawn? X'inhu l-messaġġ f'dan il-punt? Hija se biss print kollha ta 'dawk, sabiex inti ma għandekx individwalment jgħidu, Stampa I. Stampa Message. Key Stampa. U mbagħad Display. Dak li ma huwa kif inti pass permezz tal-programm, dan ser biss tagħmel ċert li huwa wiri xi varjabbli partikolari f'kull punt. Allura li inti also-- --it s tip ta 'shortcut fejn inti ma għandekx biex iżommu għaddejjin bħal, oh. Key Stampa jew Stampa I. Hija biss awtomatikament se tagħmel dan għalik. 

Allura, ma 'dan, aħna qed tmur biex tara kif dan imur. Jien ser jippruvaw u switch trasferiti għas appliance tiegħi. Ara jekk I tista 'tagħmel dan. Kollha. Aħna biss se jirrifletti dan. M'hemm xejn crazy fuq laptop tiegħi anyways. OK. Dan jeħtieġ li jkun dan wieħed. Huwa hekk ċkejkna. Ejja naraw jekk nistgħu nagħmlu dan. 

OK. Alice hija ovvjament tissara hawn biss ftit, iżda aħna ser ġġibu fil momento. OK. Aħna biss ser iżżid dan. OK. Jistgħu kulħadd tip ta 'tara li? Forsi ftit? Naf huwa ftit żgħira. Inti ma tistax pjuttost figura kif jagħmlu dan akbar. Jekk xi ħadd jaf. Ħadd ma jaf kif jagħmlu dan akbar? OK. Aħna qed tmur biex roll magħha. Ma jimpurtax anyways għaliex huwa biss dak l-kodiċi li inti guys għandhom jkollhom. 

X'hemm aktar importanti huwa l-terminal hawnhekk. U aħna għandna hawnhekk Għaliex huwa tant żgħar? Settings. Oh. Ike veru. Kif jgħid dan? Minn hemmhekk. Hija li aħjar għal kulħadd? OK ,. Kessaħ. 

Inti taf meta int fil-CS diffikultajiet tekniċi klassi huma tip ta 'parti mill the-- Allura, ejja ċar dan. OK. Allura, dritt hawn fit-taqsima, li kellna hawn. Caesar huwa fajl eżekutibbli. So I għamilha. Allura, ħaġa waħda li tirrealizza ma GDB huwa li taħdem biss fuq fajls eżekutibbli. Allura, inti ma tista 'taħdem fuq dotsy. Inti għandek tagħmel attwalment żgur li kodiċi tiegħek jikkompila, u li jkun jista 'effettivament jitmexxew. 

Allura, kun żgur li jekk ma jikkompilaw, ġġibu biex jikkompilaw, sabiex inti tista 'tip ta' run permezz ta 'dan. Allura, biex tibda GDB, kull ma għandek tagħmel, Gloria tip GDB, u mbagħad biss l- fajl li inti tixtieq. Jien dejjem misspell Caesar. Iżda inti tixtieq li tagħmel ċert peress li huwa eżekutibbli, ti tal dot flash hekk li ifisser li inti qed tmur jiddekorri CSI int ser tesegwixxi dan fajls jew mal-debugger. OK. Allura, inti tagħmel dan, inti tikseb dan it-tip ta 'gibberish. Huwa biss l-affarijiet kollha dwar debugger. Inti ma verament ikollhom tinkwieta dwar dan id-dritt issa. U kif tara, aħna għandna dan parens miftuħa, PGD, parens qrib, u biss tip ta 'qisu linja tal-kmand tagħna, id-dritt? 

Allura, dak li rridu do-- --So, L-ewwel ħaġa huwa irridu jagħżlu post li din tinqasam. Allura, hemm bug wieħed f'dan il-programm Caesar li nintroduċi, li aħna qed tmur biex issir taf. Hija Dak li dan huwa li tieħu l-input Barfoo fil tappijiet kollha, u għal xi raġuni dan ma jbiddilx A. Hija biss tħalli waħdu, Huwa kollox korretti, iżda t-tieni ittra A tibqa 'mhux mibdula. Allura, aħna qed tmur biex jippruvaw u figura għaliex dan huwa. Allura, l-ewwel ħaġa li għandek tipikament trid tagħmel kull meta inti tibda fuq GDB huwa insemmu fejn li din tinqasam. 

Allura Caesar huwa programm pretty qasir. Aħna biss għandhom funzjoni waħda, id-dritt? Dak li kien il-funzjoni tagħna fl Caesar? Hemm wieħed biss funzjoni, id-dritt Main? Main hija funzjoni għall-programmi kollha tiegħek. Jekk inti ma kellhiex Main, I jista jkun ftit inkwetat dritt issa, imma nispera li intom kollha kellhom Main fil hemmhekk. Allura, dak li nistgħu nagħmlu huwa li nistgħu biss break Main, biss bħal dik. Allura, huwa jgħid, OK. Waqqafna wieħed breakpoint tagħna hemmhekk. 

Allura, issa l-ħaġa li tiftakar huwa Caesar jieħu kmand wieħed argument linja dritt u aħna ma għamlu dan għadu kullimkien. Allura, dak li għandek tagħmel huwa meta inti fil-fatt tmur run il-programm, kwalunkwe programm li int li jibda fil GDB li jeħtieġ linja ta 'kmand argumenti, int ser input meta inti l-ewwel tibda taħdem dan. Allura, f'dan il-każ, nagħmlu Mexxi ma 'ċavetta ta' tlieta. U fil-fatt se tibda. 

Allura, jekk inti tara hawn, aħna għandna Jekk RC mhuwiex ugwali għal 2. Hekk jekk inti guys kollha għandhom dan il-fajl li I bagħtet up tkun taf tara li dan huwa bħall- ewwel linja funzjoni prinċipali tagħna, id-dritt? Huwa verifika biex tara jekk ikollna in-numru korrett ta 'argumenti. Allura, jekk int mintix jekk RC hija korretta, inti tista 'tagħmel xi ħaġa bħad Stampa RC. RC huwa tnejn, li huwa dak li aħna mistennija, id-dritt? 

Allura, nistgħu mmorru Sussegwentement, u tkompli permezz. Allura, aħna għandna xi ċavetta hemmhekk. U nistgħu jistampaw ewlieni tagħna tagħmel ċert li l-korretta. Interessanti. Mhux pjuttost dak li aħna mistennija. Allura, ħaġa waħda li tirrealizza ma GDB wkoll, huwa li mhuwiex sakemm inti fil-fatt hit Sussegwentement, li l-linja li inti biss raw huwa attwalment eżegwita. Allura, f'dan il-każ Key ma ġiex assenjat s'issa. Allura, Key hija xi valur żibel li tara fuq il-qiegħ hemmhekk. Negattiv $ 120-- --It ta 'biljun u xi ħaġa affarijiet fard dritt? Mhuwiex l-Key li aħna mistennija. Imma jekk aħna hit Sussegwentement, u allura aħna jippruvaw u Stampa ewlieni, huwa tlieta. 

Kulħadd tara li? Allura, jekk ikollok xi ħaġa li int tixtieq, stenna. Dan huwa kompletament ħażin, u jien ma nafx kif dan jiġri minħabba kollha nixtieq tagħmel hu li tassenja numru, varjabbli, jippruvaw laqtu Sussegwentement, ipprova istampar mill-ġdid, u ara jekk li x-xogħlijiet. Għaliex dan huwa biss ser jesegwixxu u attwalment tassenja xi ħaġa wara li inti hit jmiss. Jagħmel sens għal kulħadd? Uh huh? 

SPEAKER 2: Meta inti każwali numri dak ma jfisser? 

SPEAKER 1: Huwa biss bl-addoċċ. Huwa biss żibel. Huwa biss xi ħaġa li tiegħek kompjuter se saltwarjament tassenja. Kessaħ. Allura, issa nistgħu jimxu permezz, u għalhekk issa għandna din GetString test sempliċi. Allura, let me biss jintroduċu liema se jiġri meta aħna hit li jmiss hawn. GDB tagħna tip ta tisparixxi, id-dritt? Dak għax GetString issa qed jesegwixxi, id-dritt? Allura, meta rajna test sempliċi ugwali GetString, parens miftuħa u parens, u aħna hit Sussegwentement, li għandha attwalment esegwiti issa. Allura, huwa stennija għal ahna xi ħaġa input. 

Allura, aħna qed tmur biex input ikel tagħna li huwa dak huwa jonqos kif I qallek u li biss jgħid li huwa lest eżekuzzjoni, li l-magħluqa bracket ifisser li huwa joħorġu barra minn dak loop. Allura, nistgħu hit Sussegwentement, u issa, kif jien żgur li int kollha familjari minn Caesar, dan huwa, x'hemm din il-linja se jagħmlu. Huwa għal Int I ikun egwali għal 0, N ugwali Strlen, test sempliċi, u mbagħad I hija inqas minn n, I, plus, plus. X'inhu dan loop se jagħmlu? Iftaħ il-messaġġ tiegħek. Kessaħ. Allura, ejja tibda tagħmel dan. 

Allura, jekk din il-kundizzjoni jaqblu, għall-ewwel waħda tagħna? Jekk huwa B, huwa test sempliċi I. Aħna tista 'tikseb informazzjoni dwar lokal tagħna. So, I huwa żero, u jekk sitta, li nistennew, u ewlenin tagħna huwa tlieta. Kollha li jagħmel sens, id-dritt? Dawn in-numri huma kollha eżattament dak li għandu jkun. Allura, HUM? SPEAKER 3: Għandi każwali numri għal mini. SPEAKER 1: Well, nistgħu check-- --we tista 'chat dwar dan fit-tieni. Imma inti għandek tkun jkollna dan. Allura, jekk għandna kapital B għall-ewwel waħda tagħna, din il-kondizzjoni għandha qabda, id-dritt? Allura, jekk aħna hit Sussegwentement, naraw li din Jekk attwalment tesegwixxi. Għaliex jekk int wara flimkien fil-kodiċi tiegħek, din il-linja hawn, fejn test sempliċi I huwa mibdul ma 'dan aritmetika, tesegwixxi biss jekk il Jekk kundizzjoni huwa dritt korretta? 

GDB huwa biss se nuruk affarijiet li huma attwalment esekuzzjoni. Mela jekk din il-kundizzjoni Jekk ma kinitx sodisfatta, huwa biss se skip sa l-linja li jmiss. OK? Allura, aħna għandna dan. Dan bracket ifisser li huwa magħluq ta 'dak loop issa. Allura, li għaddej biex jerġa 'jibda. Eżatt bħal dik. Allura, li nistgħu jiksbu info dwar lokal tagħna hawn, u naraw li l-ewwel tagħna ittra inbidlet, id-dritt? Huwa issa E, kif għandu jkun. Allura, nistgħu tkompli fuq. 

U aħna għandna dan il-kontroll. U dan il-kontroll għandhom jaħdmu, right? Huwa A. Għandu jinbidlu tliet ittri quddiem. Imma jekk tinnota, aħna nikseb xi ħaġa differenti. Allura f'dan il-każ up here, maqbuda dan, u għalhekk din il-linja eżegwit, li modifikata tagħna B. Iżda, f'dan il-każ hawnhekk, aħna għandna li hija biss skipped dan, u marru għall-[? L siff. ?] Allura xi ħaġa għaddej fuq hemmhekk. Dak thats tghidlek huwa li, nafu li dan għandu qabda hawnhekk, iżda mhux. Jista 'xi ħadd tara dak tagħna problema hija f'dik il-linja? Hija ħaġa ħafna minuta. U inti tista 'wkoll tħares lejn kodiċi tiegħek. Huwa line-- wkoll tinsa liema linja huwa fil there-- imma hija fil-[inaudible]. Iva? 

SPEAKER 4: Hu l fuq l-akbar minn paġna jekk inti taqraha fil-ktieb. SPEAKER 1: Eżattament. Allura, l-debugger ma setax jgħid inti, iżda l-debugger jistgħu jiksbu inti isfel ma 'linja li inti taf ma tkunx qed taħdem. U xi kultant, meta speċjalment aktar tard fil-semestru, meta int jittrattaw mitt, a mitt ftit linji tal-kodiċi, u inti ma nafx fejn huwa fin-nuqqas, dan huwa mod tajjeb ħafna biex jagħmlu dan. Allura, sibna bug tagħna. Inti tista 'tiffissa lilha fil-fajl tiegħek, u allura inti tista 'tmexxi dan mill-ġdid, u kollox se taħdem perfettament. U l-akbar ħaġa hija dan jista 'jidher simili, OK. Yeah. Kessaħ. Inti taf dak li qed tfittex. Allura, inti kienu jafu x'għandhom jagħmlu. 

GDB jista 'jkun utli super għaliex inti jista jistampa dawn kollha affarijiet li inti kieku ma. Huwa ħafna aktar utli minn printf. Kemm inti tuża bħal dikjarazzjonijiet printf biex insemmu fejn bug kien, id-dritt? Allura, ma 'dan, inti ma għandhom iżommu tmur lura, u simili kummentar fil Printf, jew jikkummentaw out, u ċifra barra dak inti għandek tkun l-istampar. Dan fil-fatt biss tippermetti li inti pass permezz, jistampa affarijiet kif int għaddejjin, hekk, inti tista ' josservaw kif dawn jinbidlu fil-ħin reali, kif program tiegħek tkun qed taħdem. 

U ma tieħu ftit daqsxejn ta 'jkollna użati biex. I jirrakkomanda ħafna biss tip li tkun ftit frustrat magħha għal dritt issa. Jekk inti tqatta siegħa fuq il- ġimgħa d-dieħla tagħlim kif tuża GDB, inti se jiffrankaw yourself tant żmien aktar tard. U litteralment. we tell dan nies kull sena, u I tiftakar meta I ħa l- klassi, I kien simili, I se tkun multa. No Pset 6 daħal fuq u I kien bħal, jien gonna jitgħallmu kif tuża GDB minħabba I ma jafu x'inhu għaddej hawn. 

Mela jekk inti tieħu l-ħin hekk użu fuq programmi iżgħar li int ser tkun jaħdmu fuq, bħal xogħol permezz xi ħaġa bħal Visionare, bħal dan. Jew jekk inti tixtieq prattika żejda, jien ċert I tista 'toħroġ bi programmi Buggy, għalik biex debug jekk inti tixtieq. 

Imma jekk inti biss tieħu ftit ħin biex tikseb użati biex dan, biss play madwar magħha, se int verament sservi tajjeb. U huwa verament wieħed mill dawk l-affarijiet li inti biss jkollhom biex jippruvaw, u tikseb idejk maħmuġin ma ', qabel ma int verament tifhem dan. I really mifhum biss darba I kellha affarijiet debug magħha, u huwa ħafna nicer li jkollhom idea ta ' kif debug mill-aktar. OK. Kessaħ. Naf li tip simili kors tiġrifa fil GDB, u jien se definittivament taħdem fuq jkollna dawn biex tħares ħin li jmiss akbar. Kessaħ. 

Allura, jekk immorru lura għall PowerPoint tagħna. Huwa dan se jaħdem? AWH. Iva. OK. Allura, jekk inti qatt bżonn xi wieħed dawk darb'oħra, hemm il-lista. Allura Binarju Fittex, li kulħadd jiftakar l-ispettaklu kbir ta 'David ripping phone kotba fil nofs. I ma verament tikseb l- kotba tat-telefon aktar, għaliex bħal fejn do inti tikseb kotba tat-telefon dawn il-jiem? I verament ma nafx. Il Fittex Binarju. Hawn xi ħadd ftakar kif Binarju Fittex xogħlijiet? Kulħadd fil-livelli kollha? Yeah? SPEAKER 5: Inti taf meta inti tħares lejn li nofshom ikun fi, Ibbażat fuq dan, u jeħles mill-nofs l-ieħor. 

SPEAKER 1 Eżattament. Allura, Binarju Fittex, huwa tip ta 'a-- --we simili li hija sejħa jaqsam u jirbħu. Allura, dak li inti ser tagħmel hu inti ser tħares fin-nofs, u tkun taf tara jekk logħbiet dak li qed tfittex. U jekk ma jiġrix dan, allura inti tipprova insemmu, huwa se jitħalla nofs jew il-nofs tal-lemin. Allura, dan jista 'jkun jekk inti qed tfittex fuq xi ħaġa thats alphabetized, tara, oh. Does Allison jiġi qabel M? Iva. Allura, aħna qed tmur biex tħares lejn l-ewwel nofs. 

Jew jista 'jkun simili bin-numri. Kwalunkwe ħaġa li inti tista ' iqabblu, dan jistgħu jiġu magħżula. Inti tista 'tuża tfittxija binarja fuq. Allura, xi ħadd ftakar dan grafika jew dak li din hija? Huwa Kumplessità Asymptotic. Allura, din il-graff biss tiddeskrivi kemm hija tieħdok biex isolvu problema bħala inti jiżdied in-numru ta 'affarijiet li inti qed tuża. 

Allura, aħna għandna N, li huwa żmien lineari. Jekk N fuq tnejn, li hija ftit aħjar, xorta tikber super fast. U allura aħna għandna Login, li hija dak li aħna nikkunsidraw Binarju Search. Jekk aħna Avviż, kif l-problema tiegħek gets ħafna u ħafna akbar, il-ħin li tieħu inti issolviha ma verament jżidu li ħafna. Huwa simili komparabbli hawn fil-bidu. Int simili, OK. Xejn hawn ma verament kwistjoni li wieħed nużaw, imma inti toħroġ lil miljun, biljun. Inti qed tipprova ssib some-- --you're jippruvaw isibu labra fil haystack. 

Naħseb li inti tixtieq din il-problema. Inti tixtieq din il-kumplessità, mhux lineari għaliex għal kull ma għandek taf gonna tiegħek tkun tiftix permezz kull labra individwali, ħaġa tal ħuxlief, tipprova tfittex għal labra tiegħek. U li mhux wisq gost fl-opinjoni tiegħi. I simili fast. I simili effiċjenti. U l-istudenti kif hardworking inti guys huma, inti taf taħdem aktar intelliġenti, mhux aktar diffiċli ħaġa tip, kif inti jista 'jagħmel sa dawn algoritmi. 

Allura, aħna qed tmur biex jimxu permezz biss eżempju malajr. Naħseb li inti guys għandu jkollhom idejn fuq Binarju Fittex, iżda fil-każ ħadd huwa ftit fuzzy, tixtieq li din tissaħħaħ, aħna qed tmur biex jmorru biss permezz ta 'eżempju hawn. Allura, aħna qed tfittex jekk l-array fih sebgħa. 

Allura, l-ewwel ħaġa li għandna nagħmlu huwa ħarsa fin-nofs, id-dritt? U wkoll int se tkun kodifikazzjoni Binarju Fittex fi ftit tieni. Allura, li għaddej biex tkun divertenti. Allura aħna tfittex fil- arrays ftit nofs 3. Does 3 ugwali 7? Ma. Huwa sitta. Allura, huwa inqas minn jew akbar minn seba? Inqas minn. Iva. Guys xogħol sbieħ. Inħoss I simili I għandhom jkollhom kandju minħabba I tixtieq li tarmi it out fil-tarzni. Huwa dak li jiena ser tagħmel ġimgħa d-dieħla. Hija se jżommok guys qawwija. 

Allura, aħna armih li ewwel nofs, id-dritt? kien inqas minn. nafu li kollox fuq dik in-naħa tax-xellug se tkun inqas minn dak aħna qed fil-fatt tfittex. Allura, hemm ebda bżonn li tagħti attenzjoni għalih. Just tinsieh. Allura, issa irridu nħarsu lejn in-naħa tagħna tal-lemin, u nħarsu lejn l-nofs hemmhekk, u issa huwa disgħa. Allura, 9 is-- --Everyone? Akbar minn dak li aħna qed tfittex, id-dritt? Allura, aħna qed tmur biex tarmi bogħod kollox lejn il-lemin. Bħal dik. Issa, kollox aħna qed xellug ma huwa wieħed. Allura aħna jiċċekkjaw, huwa dan wieħed dak aħna qed tfittex? huwa. Sibna dak li ridna. Allura aħna qed isir. Bilinear Search. 

U jekk tinnota, aħna kellhom seba inputs hemmhekk. Hija biss ħadet us bħal tliet darbiet, imma jekk int tagħmel bħal biljun, inti guys taf kif ħafna passi li kieku jieħu jekk kellna erba 'biljun affarijiet? Kwalunkwe guesses? Huwa 32. 32 passi biex isibu xi ħaġa fil-erba 'biljun element array minħabba setgħat ta 'tnejn. Allura tnejn huwa sa 32, huwa li erba 'biljun. 

Kif so pretty crazy int xorta ġewwa bħal numru pjuttost żgħir ta 'passi biex isibu xi ħaġa fil erba 'biljun elementi. Allura fuq din in-nota, aħna qed jmorru għall-kodiċi dan Allura inti guys tista 'attwalment tip ta 'tara kif dan xogħlijiet. Kull dritt, sabiex inti guys tista 'kodiċi. Jien ser tavżak guys jitkellmu għal ftit. Jsiru jafu nies ta 'madwarek, li hija dak li xi ħadd ried mill-aħħar taqsima. 

Allura isiru jafu l-poplu madwar inti. Jitkellmu għal ftit. U kollha nixtieq minn int guys dritt issa huwa biss tipprova toħloq kontorn ta pseudocode. OK? Whoa. All I trid mill inti guys huwa int biss se timla f'dan il-każ waqt. So I waqqfu dawn ta 'fuq u limiti baxxi li jirrappreżentaw il-bidu u t-tmiem ta 'firxa tagħna. U inti ser attwalment loop permezz ta 'u figura dak li aħna qed tagħmel fi ħdan dan loop waqt. 

Hekk jekk inti tista 'figura out-- Għandi ħjiel there-- liema huma l-każijiet li għandna hawnhekk? Mela jekk inti tixtieq li insemmu l- każijiet, aħna se pseudocode dawk u allura aħna ser attwalment kodiċi lilhom. U li għaddej biex tkun, I think, nisperaw inneħħu jkun ftit aktar faċli milli għandek tistenna. Għaliex dan m'huwiex kodiċi ħafna, attwalment, li huwa verament jibred. 

Mm-hm? 

STUDENT: [inaudible]? Istruttur: Iva. Kien hemm xi ħaġa li ssib fil-nofs. 

STUDENT: Allura nistgħu nużaw dak. OK. 

Istruttur: Perfect. Allura li l-ewwel ħaġa li għandna bżonn tagħmel. Allura ssib-nofs. Kbira. Allura inti għandek idea ta 'kif nistgħu attwalment issib l-nofs bil-kodiċi? 

STUDENT: Yeah. n aktar minn 2? Istruttur: Allura n aktar minn 2. Allura ħaġa waħda hija li tiftakar li limiti ta 'fuq u t'isfel tiegħek bidla. Inżommu constricting l-parti mill-firxa aħna qed tfittex għal. Allura n aktar minn 2 se taħdem biss għall-ewwel ħaġa li għandna nagħmlu. Allura tieħu fuq u t'isfel kont, kif tista nikbru li element tan-nofs? Għaliex irridu-nofs bejn fuq u t'isfel, id-dritt? Mm-hm? 

STUDENT: [inaudible]. 

Istruttur: Allura aħna għandna xi nofs. U dan ser ikun ta 'fuq plus t'isfel fuq 2. Biża. Hemm immorru. Wieħed linja stabbiliti. Inti guys fuq tiegħek mod. Allura issa li għandna tagħna nofs, dak li rridu nagħmlu? Just b'mod ġenerali. Inti ma għandekx kodiċi lilha. Iva. STUDENT: [inaudible]? Istruttur: Allura huwa plus għax int konstatazzjoni tal-medja bejn it-tnejn minnhom. Mela jekk inti taħseb minnhom bħala tip ta 'żieda fil mill-ġnub, taħseb dwarha bħala inti approċċ l-nofs, inti tixtieq bħal dik. Mela jekk inti kienu fuq kull naħa tal- tan-nofs, u għandna simili 5 u 7. Meta inti żid lilhom flimkien inti nikseb 12, inti iddividi 2, huwa 6. 

Xi kultant huwa diffiċli li jispjega għaliex li x-xogħlijiet, imma jekk inti taħdem permezz eżempju kultant, dan ser jgħinek insemmu jekk għandu jkun plus jew minus. Iva. 

STUDENT: [inaudible] eżattament fin-nofs jekk kellhom każ fejn hemm ħafna ta 'numri iżgħar u bħal wieħed numru kbir? 

Istruttur: Allura kull ma għandek bżonn huwa l-nofs tal-firxa. Mela jekk kellek mazz ta 'numri żgħar u mbagħad numru wieħed verament kbir fl-aħħar, ma jimpurtax. Dak kollu li huwa importanti huwa li dawn qed magħżula, inti biss tixtieq li tħares lejn l-nofs ta ' l-array għax int xorta tiflil problema tiegħek nofs. Kessaħ. Allura issa li aħna għandna l- nofs, dak li nagħmlu jmiss? 

STUDENT: Qabbel. Istruttur: Il jqabblu. Allura jqabblu nofs biex value_wanted. Kessaħ. Allura inti tara up here għandna dan il-valur irridu up here. Ftakar li dan huwa firxa. Hekk nofs tirreferi għall-indiċi. Allura rridu nagħmlu valuri ta 'nofs. Tinsiex jekk inti tixtieq li jqabblu, ugwali doppja. You do wieħed ugwali int biss se jassenja mill-ġdid, u mbagħad, ovvjament, huwa se jkun il-valur li trid. Allura ma tagħmel dan. 

Allura aħna qed tmur biex tara jekk il-valuri fil-nofs huwa ugwali għall-valur li rridu. Tinsiex braces tiegħek. Dropbox għandhom imorru. Allura x'nistgħu nagħmlu f'dan il-każ? Jekk huwa dak li rridu li jirritornaw? Aħna qed nipprova ngħid. 

STUDENT: Stampa off. 

Istruttur: Well, aħna ma jridux li jistampaw off. Allura dan huwa BOOL hawn, hekk aħna jridu jirritornaw vera jew falza. Aħna qed tgħid, huwa dan in-numru l [? RRA? ?] Mela jekk huwa, aħna biss ritorn veru. Jekk I jistgħu jfissru veru. 

STUDENT: Għaliex ma inti tirritorna żero? Istruttur: Allura inti tista ritorn żero jekk int riedu. Iżda f'dan il-każ għaliex funzjoni tagħna jirritorna BOOL, għandna bżonn li jirritornaw jew vera jew falza. STUDENT: Meta int qal espressjoni Boolean, inti tista 'tistabbilixxi lilha ugwali għal falza? Bħal jekk irrid ngħid, jekk din il-kundizzjoni ma tiġix sodisfatta, bħal huwa fuq ugwali falza. Se tifhem jekk inti biss tpoġġi falza fuq in-naħa l-oħra? Istruttur: Yeah. Mela attwalment jekk int qatt tagħmel xi ħaġa bħall hija ta 'fuq jew t'isfel, li jirritorna veru jew falza u huwa stil attwalment ħażina li jiġifieri ugwali ugwali vera jew partijiet ugwali ugwali falza. Inti tixtieq li tuża dik riżultat kif ruħu bħala check tiegħek. Mhux dak li ridt. Dan huwa dak li ridt. Hekk fil-każ ta 'int tistaqsi dwar xi ħaġa bħal tiffranka dan fil ċ. 

Hekk jekk ikollna int prinċipali (vojt) u xi ħaġa bħal din. U inti għandek jekk huwa ta 'fuq ta 'xi kontribut u int tistaqsi jekk inti tista 'tagħmel xi ħaġa bħal din? Dritt? STUDENT: I ​​kien qed jipprova biex tagħmel dan [inaudible]. Għaliex jekk it's-- Istruttur: Dritt. Allura inti tixtieq li dan ikun falz, id-dritt? STUDENT: Yeah. Istruttur: Allura f'dan il-każ inti tixtieq li tesegwixxi jekk mhuwiex veru. Allura l-ħaġa jibred li inti tagħmel hemm dan. Mela ftakar exclamation punt jiċħad l-affarijiet? Hija tgħid [inaudible] ifisser mhux. Mela jekk inħarsu lejn biss din il-parti hawn, youd jgħidu li jevalwa li falza kif inti tixtieq li. Mhuwiex falz huwa veru li ifisser dan ikun tesegwixxi. Ma li jagħmel sens? STUDENT: Yeah. Istruttur: biża. OK. Allura nistgħu biss ritorn veru f'dan il-każ. Allura issa għandna tnejn l-oħra każijiet f'dan il-każ. Liema huma żewġ każijiet l-oħra tagħna? Ejja biss tagħmel dan il-mod. Mela ejja nibdew mal-ieħor jekk il-valuri fil-nofs huwa inqas mill-valur li rridu. Allura valur tagħna fin-nofs huwa inqas mill-valur li aħna qed tfittex. 

Allura liema marbuta do you think irridu li taġġorna? Fuq jew t'isfel? Upper? Allura liema naħa tal-firxa huma aħna se tkun tħares lejn? 

STUDENT: L-inqas. 

Istruttur: Aħna ser nieħdu tkun tħares lejn ix-xellug. Mela inkella jekk il-valur ftit huwa inqas. Allura valur tan-nofs tiegħek hawn huwa inqas minn dak li rridu. Allura aħna tixtieq li tieħu l- lemin ta 'firxa tagħna. Allura aħna qed tmur biex taġġorna inferjuri tagħna. Allura aħna ser jassenja mill-ġdid aktar baxx tagħna. U x'taħseb aktar baxx għandu jkun? STUDENT: Il-valur tan-nofs? Istruttur: Allura l-value-- nofs STUDENT: Plus 1. Istruttur: --plus 1. Jista 'xi ħadd tell me għaliex għandna li flimkien ma '1? 

STUDENT: [? Ebda valur?] huwa aktar ugwali għal dan. 

Istruttur: Dritt. Għaliex aħna diġà jafu li valur tan-nofs tagħna ma tkunx ugwali għal dan u rridu li teskludiha minn tfittxijiet kollha sussegwenti. Jekk inti tinsa li flimkien ma '1, dan se bħal loop indefinittivament. U inti taf biss tkun maqbuda fi loop infinita u allura inti ser segfault u l-affarijiet imorru ħażin. Hekk dejjem kun żgur li int mhux inkluż il-valur li inti biss ħares lejn. Allura aħna jieħdu ħsieb ta 'li bil plus 1. 

Allura issa għandna l-aħħar kondizzjoni tagħna li jiena dejjem għall-finijiet tas-sigurtà tista 'tiċċekkja hawn, inkella jekk il-valur fil l-nofs huwa akbar mill-valur irridu. Dan ifisser li aħna rridu l-nofs tax-xellug. Allura liema waħda huma aħna se taġġorna? Upper. U dak li huwa dan wieħed se ugwali? Nofs minus 1 għaliex, naturalment, irridu biex tiżgura li aħna mhux qed tħares lejn dak il-valur tan-nofs mill-ġdid. U allura aħna għandna hija. Thats it. Li kollox tfittxija binarja huwa. Huwa mhux ħażin, id-dritt? Huwa simili 10 linji ta ' kodiċi bi spazju abjad. Allura qawwija ħafna, utli ħafna, inti se tkun qed tuża din f'waħda mill psets aktar tard tiegħek. Forsi mhux dan wieħed, iżda iktar tard. Allura jitgħallmu. Imħabba tiegħu. Hija se jikkurak ukoll. Allura ħadd ma jkollu xi mistoqsijiet dwar tfittxija binarja? Iva. 

STUDENT: Ma jimpurtax jekk n tiegħek huwa saħansitra jew fard? 

Istruttur: No Għaliex aħna mitfugħa lill-nofs bħala l int, se biss truncate dan. Għalhekk se jibqgħu integer u se eventwalment sort permezz kollox. Allura inti ma għandekx għalfejn tinkwieta dwar dan. Kulħadd tajba? Biża. Kessaħ. Allura, inti guys sibt dan. Wirja. Allura kif aħna kienu jitkellem dwar, I know David imsemmi runtimes kumplessità. 

Hekk fil-każ aħjar, huwa biss waħda, li aħna sejħa ta 'żmien kostanti. Jista 'xi ħadd tell me għaliex dan jista' jkun? Liema tip ta 'xenarju li jinvolvi? Mm-hm. 

STUDENT: [inaudible] first-- Istruttur: Allura-nofs huwa l- ewwel element li aħna jaslu għal, id-dritt? Dan jew firxa ta 'wieħed jew ikun x'ikun aħna qed tfittex għal ftit jiġri li jkun smack dab fin-nofs. Allura dak il-każ l-almu tagħna. Ikollok fis-problemi reali, probabbilment mhux ser tilħaq [inaudible] li spiss. What about agħar każ tagħna? Agħar każ tagħna huwa log n. U li għandha x'taqsam ma 'l-sħiħ setgħat ta 'żewġ ħaġa li I tkellem dwar. 

Allura fl-agħar każ li jista 'jfisser li kellna biex CHOP l-array isfel sakemm kien element ta 'wieħed. Hekk kellna biex CHOP l-isfel fil-nofs kemm drabi aħna possibilment jistgħu. C'est pourquoi huwa log n għax inti biss iżommu diviż bi tnejn. Allura suppożizzjonijiet, affarijiet inti jeħtieġ li tkun taf jekk int qatt ser tuża tfittxija binarja. Elementi tiegħek għandhom jiġu magħżula. Huma għandhom jiġu magħżula minħabba dak l-uniku mod inti tista 'tkun taf jekk inti kapaċi li tarmi l-nofs ta 'dan. 

Jekk kellek dan il-borża jumbled ta 'numri u inti qed tgħid, OK, jien ser jiċċekkja l-nofs numru u n-numru jien infittxu huwa inqas minn dak, jien biss se biex arbitrarjament tarmi out nofs. Inti ma tkunx taf jekk tiegħek numri li nofs l-ieħor. Lista tiegħek għandha tkun magħżula. Kif ukoll, dan jista 'jkun jimxu 'l quddiem ftit, iżda inti għandek bżonn li jkollhom aċċess bl-addoċċ. Inti jeħtieġ li tkun kapaċi biss tmur f'dak l-element tan-nofs. Jekk għandek travers permezz xi ħaġa jew din tieħdok passi addizzjonali biex jiksbu għal dak l-element tan-nofs, mhuwiex log n jibqgħalu għaliex int żżid aktar xogħol fis dan. U dan se jagħmel ftit aktar sens fil-ġimgħatejn, imma I biss tip ta 'riedu prefazju, jagħtuk guys idea ta 'x'hemm li ġejjin. Iżda dawk huma ż-żewġ suppożizzjonijiet importanti li għandek bżonn għal lista binarja. Kun ċert li huwa magħżula. Dik hija l-waħda kbira għal inti guys dritt issa. U fuq li aħna tista 'tmur fil il-bqija ta 'tipi tagħna. Allura erba bużżieqa sorts--, inserzjoni, selezzjoni, u jingħaqdu. Huma qed kull tip ta 'kessaħ. Jekk inti guys jiddeċiedu li jieħdu CS 124, inti ser jitgħallmu dwar kull xorta ta 'xorta. U jekk int fan XKCD, hemm huwa dwar komiks verament jibred bħal xorta verament ineffettivi, li jiena jirrakkomanda ħafna li inti tmur biex tħares lejn. Waħda minnhom hija simili sort paniku, li huwa simili, oh no, ritorn firxa każwali. Sistema għeluq. Leave. Allura Humer geeky huwa dejjem tajjeb. 

Sabiex ħadd ma tiftakar tip ta 'prodotti simili biss idea ġenerali ta 'kif sort bużżieqa xogħlijiet. Tiftakar? 

STUDENT: Yeah. 

Istruttur: Mur għaliha. 

STUDENT: Allura inti qed tmur permezz u jekk huwa akbar, allura inti tpartit it-tnejn. 

Istruttur: Mm-hm. Eżattament. Allura inti biss jtenni permezz. Inti tiċċekkja żewġ numri. Jekk il-wieħed qabel hija akbar minn dak wara, inti biss tpartit lilhom b'tali mod li fil- dan il-mod kollha tal-numri ogħla bużżieqa up lejn l-aħħar tal-lista u il-numri baxxi bużżieqa isfel. 

Did hu nuruk guys l-jibred ħoss effett issortjar video? Huwa tip ta 'kessaħ. Allura kif Robert biss qal, l-algoritmu li inti biss pass permezz tal-lista, iskambji tal-valuri biswit jekk dawn mhux qed fl-ordni. U mbagħad biss iżommu tirrepeti sakemm inti ma tagħmel xi swaps. Allura mhux ħażin, right? Allura aħna biss ikollhom eżempju quick hawn. Allura dan se sort minnhom axxendenti ordni. Allura meta aħna jgħaddu l-ewwel ħin, irridu nħarsu permezz tmienja u sitta huma ovvjament mhux sabiex, aħna tpartit minnhom. 

Allura tħares lejn dak li jmiss. Tmienja u erbgħa mhux fl-ordni. Tpartit minnhom. U mbagħad tmienja u tnejn, tpartit minnhom. Hemm immorru. Allura wara l-ewwel pass tiegħek, inti jafu li l-akbar numru tiegħek se tkun it-triq kollha fil-quċċata għaliex huwa biss se jiġu kostantement akbar minn kull ħaġa oħra u huwa biss se bużżieqa up-triq kollha sa l-aħħar hemmhekk. Does li jagħmel sens għal kulħadd? Kessaħ. 

Hekk allura aħna nħarsu lejn it-tieni pass tagħna. Sitta u erbgħa, swiċċ. Sitta u tnejn, swiċċ. U issa għandna ftit affarijiet fl-ordni. Allura għal kull pass li aħna jagħmlu permezz lista tagħna kollu, nafu li bħal li ħafna numri fl-aħħar se jkunu ġew magħżula. Allura nagħmlu terz pass, li hija tpartit wieħed. U mbagħad fuq raba tagħna jgħaddu, aħna għandna żero slots. U hekk aħna nafu li tagħna array jkunu ġew magħżula. 

U li huwa l-big ħaġa ma sort bużżieqa. Aħna nafu li meta aħna ikollhom żero tpartit, li ifisser li kollox hija fl-ordni kompluta. Huwa tip ta 'kif aħna jiċċekkjaw. Allura aħna wkoll se kodiċi bużżieqa sort li huwa wkoll mhux ħażin. Xejn minn dawn huma ħżiena. I jafu li jistgħu jidhru ftit scary. I know I meta ħa il-klassi, anki meta I kien tagħlim l-klassi għal l-ewwel darba aħħar sena, I kien simili, kif nista 'nagħmlu dan? Jagħmel sens fit-teorija, iżda kif nistgħu fil-fatt jagħmlu dan? Liema hu għaliex I wkoll jixtiequ li jimxu permezz kodiċi miegħek guys hawn. So I jkollhom pseudocode għalik guys din id-darba. Hekk biss jżomm dan f'moħħu kif aħna qed dwar li transizzjoni fuq. Allura aħna għandna xi counter li iżomm rekord ta 'swaps tagħna, għaliex għandna bżonn tagħmel ċert li aħna qed tiċċekkja li. U aħna jtenni l-array kollu kif aħna biss għamlet ma 'dan l-eżempju. Jekk l-element qabel hija akbar minn l-element wara fejn aħna qed fil, aħna tpartit lilhom u aħna inkrement tagħna kontro għaliex hekk kif aħna tpartit, irridu let kontro tagħna jafu li. Kwalunkwe mistoqsijiet hemm? Xi ħaġa jidher umoristiċi hawn fuq. STUDENT: Do tissettja l-counter għal żero kull darba li inti tmur permezz tal-linja? Ma inti żżomm għaddej lura għal żero kull darba? Istruttur: Mhux bilfors. Allura dak li jiġri huwa immorru permezz ta 'hawn. Allura tagħmel waqt, ftakar, dan se tesegwixxi darba mingħajr dubju. Allura li għaddej biex tiffissa l- counter ugwali għal żero, allura li għaddej biex jtenni permezz. Kif itenni permezz, din se taġġorna counter. Kif aġġornamenti counter, meta dan isir, meta huwa laħqu t-tmiem ta 'l-array, jekk il-lista tagħna ma tkunx ġiet magħżula, kontro se jkunu ġew aġġornati. 

Mela allura din il-kontrolli l-kundizzjoni u jgħid, OK, huwa kontro akbar minn żero. Jekk huwa, jagħmlu mill-ġdid. Inti tixtieq li reset hekk li meta inti jgħaddu, kontro huwa ugwali għal żero. Jekk inti tmur permezz ta 'issortjati firxa, xejn bidliet, dan ma jirnexxix, u int jirritorna l-lista magħżula. Does li jagħmel sens? STUDENT: Jista fi ftit. Istruttur: OK. Jekk hemm xi ieħor kwistjoni li taqa up. Iva. 

STUDENT: Liema kieku l-funzjoni jkun għall-iskambji l-elementi? 

Istruttur: Allura nistgħu ngħidu jikteb li jekk aħna qed tmur biex dritt issa. Kessaħ. Allura fuq din in-nota, Alison va li jaqilbu lura għall-appliance. Li għaddej biex tkun divertenti. U aħna għandna sbieħ tagħna bubble ħaġa sort hawn. So I diġà għamlu ċikliżmu permezz tal-firxa. Għandna swaps tagħna li huma ugwali għal żero. Hekk irridu li tpartit biswit Elementi jekk dawn qed out of order. Allura l-ewwel ħaġa li għandna bżonn li do huwa jtenni permezz firxa tagħna. 

Allura kif taħseb nistgħu jtenni permezz firxa tagħna? Għandna għall ui ikun egwali għal 0. Aħna tixtieq li i tkun inqas minn n minus 1 minus k. U jien ser jispjegaw li fit-tieni. Allura dan huwa ottimizzazzjoni hawnhekk fejn, tiftakar kif I qal wara kull pass permezz tal-firxa aħna jafu li kwalunkwe s on-- 

Allura wara pass wieħed we taf li dan huwa magħżul. Wara żewġ passes nafu li dan kollu huwa magħżul. Wara tliet passes aħna jafu li s magħżula. Allura l-mod jien mtennija permezz tal-firxa hawn, huwa Hi tagħmel żgur li jmorru biss permezz ta 'dak li nafu hu mhux magħżul. OK? Li jinsab biss l-ottimizzazzjoni. Inti tista 'tikteb it naively biss mtennija permezz kollox, hija kienet ser ħu itwal. Ma 'dan erba loop huwa biss ottimizzazzjoni sbieħ għaliex aħna nafu li wara kull sħiħa iterazzjoni permezz tal-firxa hawn, bħal kull linja sħiħa hawn, nafu li wieħed aktar ta 'dawn l-elementi se jiġu magħżula fl-aħħar. 

Allura aħna ma jkollhomx għalfejn tinkwieta dwar dawk. Does li jagħmel sens għal kulħadd? Li jibred trick ftit? Allura f'dak il-każ, jekk aħna qed jiġu mtennija permezz, nafu li aħna rridu li jiċċekkjaw jekk firxa nu n plus 1 huma fl-ordni. OK. Allura hawnhekk-pseudocode. Aħna rridu li jiċċekkjaw jekk array n u n plus 1 huma fl-ordni. Allura dak li jista għandna hemmhekk? Huwa ser jkun hemm xi kondizzjonali. Se jkun jekk. 

STUDENT: Jekk array n huwa inqas minn firxa n plus 1. Istruttur: Mm-hm. Ukoll, inqas minn jew akbar minn. STUDENT: Akbar minn. Imbagħad irridu li tpartit lilhom. Eżattament. Allura issa nikbru fil x'inhu l- mekkaniżmu għall iskambji għalihom? Allura aħna marru permezz ta 'dan fil-qosor, tip ta 'funzjoni tpartit ġimgħa li għaddiet. Hawn xi ħadd ftakar kif maħduma? Allura ma nistgħux biss assenjati mill-ġdid, id-dritt? Minħabba li wieħed minnhom se jintilfu. Jekk għidna A hija ugwali għal B u mbagħad B hija ugwali għal A, kollha f'daqqa tnejn minnhom huma biss ugwali għal B. 

Allura dak li għandna nagħmlu hija aħna jkollhom varjabbli temporanja li l- ser ikollhom wieħed mid filwaqt tagħna aħna qed fil-proċess ta 'iskambji. Allura dak li għandna huwa aħna ser ikollhom xi int temperatura hija ugwali to-- inti tista 'tassenja dan għal liema waħda tixtieq, biss aċċerta ruħek li żżomm rekord ta 'it-- hekk f'dan il-każ, jien ser tassenja lill array n plus 1. Allura li għaddej biex iżommu kwalunkwe valur huwa f'dan it-tieni blokk li aħna qed tħares lejn. 

U allura nistgħu nagħmlu huwa nistgħu mmorru quddiem u firxa jassenja mill-ġdid n plus 1, għaliex aħna nafu li aħna jkollhom dak il-valur maħżun. Din hija wkoll waħda mill-kbar things-- I do not know jekk kwalunkwe inti kienu kwistjonijiet fejn jekk inti jaqilbu tnejn linji ta 'kodiċi f'daqqa affarijiet maħduma. Ordni huwa importanti ħafna fil CS. Sabiex tagħmel żgur li int dijagramma affarijiet out jekk possibbli dwar dak li qed jiġri attwalment. Allura issa aħna qed tmur biex jassenja mill-ġdid array n plus 1, għaliex aħna nafu li aħna jkollhom dak il-valur maħżun. 

U nistgħu tassenja li biex array n jew f'dan il-każ firxa i. Varjabbli wisq. OK. Firxa Allura issa konna assenjati i plus 1 sa ugwali x'hemm firxa i. U issa nistgħu mmorru lura u tassenja firxa i għal dak? Xi ħadd? 

STUDENT: 10. 

Istruttur: 10. Eżattament. U l-aħħar ħaġa waħda. Jekk aħna għandna skambjat issa, dak li għandna bżonn tagħmel? X'hemm-ħaġa waħda li għaddej biex tgħidilna jekk aħna qatt tittermina dan il-programm? Liema tgħidilna li aħna jkollhom lista magħżula? Jekk aħna ma jwettqu l-ebda tpartit, id-dritt? Jekk Swaps hija ugwali għal żero fl-aħħar ta 'dan. Allura kull meta inti twettaq tpartit, kif aħna biss ma hawn, irridu li taġġorna swaps. U naf kien hemm mistoqsija preċedenti dwar tista 'inti jużaw żero jew wieħed minflok ta 'vera jew falza. U dak hu li dan ma hawn. Allura dan jgħid jekk mhux swaps. Hekk jekk swaps huwa żero, li is-- jien dejjem nikseb veritajiet tiegħi u falses tiegħi mħallta up. Aħna rridu magħna biex tevalwa li veru u mhuwiex. Mela jekk huwa żero, allura huwa falz. Jekk inti jċaħħdu dan bil- [? bang?] isir veru. Mela allura din il-linja tesegwixxi. 

Veritajiet u foloz u żerijiet u dawk nikseb crazy. Just jekk inti bil-mod timxi permezz ta 'dan hija ser tagħmel sens. Imma dak hu dan ftit daqsxejn ta 'kodiċi hawn ma. Allura dan kontrolli biex tara li aħna għamlu xi swaps. Mela jekk huwa xi ħaġa minbarra żero, li għaddej biex tkun falza u l-ħaġa sħiħa hija ser tesegwixxi darb'oħra. Kessaħ? 

STUDENT: X'tagħmel break tagħmel? 

Istruttur: Break biss pawżi inti out tal-linja. Allura f'dan il-każ kieku bħad tmiem il-programm u inti biss jkollhom lista magħżula tiegħek. STUDENT: Amazing. Istruttur: Jien sorry? STUDENT: Għaliex qabel we użati bil-miktub 1 fuq miktub żero biex tippreżenta li jekk li se jaħdmu jew le. 

Istruttur: Yeah. Allura inti tista 'ritorn żero jew 1. F'dan il-każ, għaliex aħna mhux qed attwalment tagħmel xejn mal-funzjoni, aħna biss jixtiequ li jinkiser. Aħna ma verament kura dwar dan. Brejk hija wkoll tajba jekk huwa użat għall-breaking out ta 'erba' linji jew kundizzjonijiet li inti ma tixtieq li żżomm eżekuzzjoni. Hija biss jieħu inti out minnhom. Huwa daqsxejn ta 'ħaġa influwenzata. Inħoss bħal hemm lott ta 'waving idejn, bħal inti ser jitgħallmu dwar dan dalwaqt. 

Imma inti ser jitgħallmu dwar dan dalwaqt. I wegħda. OK. Allura ma kulħadd nikseb sort bużżieqa? Mhux wisq ħażina. Jtenni permezz, affarijiet tpartit bl-użu ta ' temperatura varjabbli, u aħna qed kollha stabbiliti hemmhekk? Kessaħ. Biża. OK. Lura għall-PowerPoint. Kwalunkwe mistoqsijiet b'mod ġenerali dwar dawn s'issa? Kessaħ. Mm-hm. 

STUDENT: [inaudible] int prinċipali normalment. Do inti trid li jkollha li għal dan? 

Istruttur: Allura konna biss tfittex biss fil-algoritmu issortjar attwali. Jekk kellek dan fi bħal programm akbar, inti jkollha x'imkien prinċipali int. Jiddependi fuq fejn inti jużaw dan algoritmu, hija tiddetermina x'inhu jkun mibgħut lura minnha. Iżda għall-każ tagħna, aħna qed strettament tħares lejn kif ma dan fil-fatt jtenni permezz ta 'firxa. Allura aħna ma tinkwieta dwar dan. 

Allura konna nitkellmu dwar l-aħjar każ u xenarji każ agħar għal tfittxija binarja. Allura huwa wkoll importanti li jagħmlu li għal kull tip tagħna. Allura dak li taħseb hija l-agħar każ runtime ta sort bużżieqa? Inti guys tiftakar? 

STUDENT: N minus 1. Istruttur: N minus 1. Allura dan ifisser li hemm n minus 1 paraguni. Allura ħaġa waħda li tirrealizza hija li fuq l-ewwel iterazzjoni, aħna jgħaddu, inqabblu dawn two-- b'tali mod li għamilhom 1. Dawn tnejn, tlieta, erbgħa. Allura wara iterazzjoni waħda we diġà jkollhom erba paraguni. Meta jien jitkellem dwar runtime u n. N jirrappreżenta n-numru ta 'tqabbil bħala funzjoni ta 'kif ħafna elementi għandna. OK? 

Allura aħna jgħaddu, għandna erba. Il-ħin li jmiss inti taf aħna ma għandek tieħu kura ta 'dan. Inqabblu dawn iż-żewġ, dawn iż-żewġ, dawn iż-żewġ, u jekk aħna ma kellhiex dak ottimizzazzjoni bl-erba 'linja li I kiteb, inti tkun tqabbel fil hawn anyways. Allura inti jkollha jgħaddi mill-firxa u jagħmlu paraguni n n żminijiet, għaliex kull darba aħna run permezz ta 'dan aħna xorta ħaġa waħda. 

U kull darba we run permezz l-array, aħna jagħmlu paraguni n. Allura runtime tagħna għal dan huwa attwalment n kwadrat, li hija ħafna agħar fl tagħna log aħħar minħabba li tfisser jekk kellna erba biljun elementi, huwa se tieħu lilna erba 'biljun kwadrat minflok 32. Hekk mhux l-aħjar runtime, iżda għal xi affarijiet, inti taf, jekk int fi ċertu firxa ta 'elementi sort bużżieqa tista 'tkun multa għall-użu. 

OK. Allura issa dak li huwa l-każ runtime aħjar? STUDENT: Zero? Jew 1? 

Istruttur: Allura 1 kieku jkun paragun wieħed. Dritt. 

STUDENT: N minus 1? 

Istruttur: Allura, yeah. Allura n minus 1. Kull meta għandek kunċett bħal n minus 1, għandna t-tendenza li biss qatra off u aħna biss jgħidu n għax għandek li tqabbel kull wieħed these-- kull par. Għalhekk ikun n minus 1, li aħna aħna'd biss jgħidu huwa ta 'madwar n. Meta inti qed jittrattaw ma runtime, kollox huwa fl tapprossima. Sakemm l-esponent huwa korretta, int pretty tajba. 

Thats kif aħna jittrattaw dan. Hekk li l-aħjar każ huwa n, li ifisser li l-lista hija diġà riżolta, u kollha għandna nagħmlu hija mmexxija permezz u jivverifikaw li huwa magħżula. Kessaħ. Kull dritt. Allura kif tara hawn, aħna biss għandhom xi graffs aktar. Allura n kwadrat. Gost. Ħafna agħar milli n kif naraw, u ħafna, ħafna agħar minn log 2n. U allura inti wkoll tikseb fis zkuk log. U inti tieħu 124, ikollok fis bħal log star, li huwa simili crazy. Hekk jekk int interessat, Lookup star log. Huwa tip ta 'gost. Allura aħna għandna din it-tabella kbira. Just a kapijiet up, dan ta ' chart wunderbare li jkollhom għal nofs it-terminu tiegħek għaliex aħna twil biex nitolbuk dawn thins. Hekk biss kapijiet up, jkollhom dan fuq tiegħek nofs it-terminu fuq folja iqarrqu sbieħ tiegħek hemmhekk. Allura aħna biss ħares lejn sort bużżieqa. Agħar każ, n kwadrat, aħjar każ, n. U aħna qed tmur biex tħares lejn l-oħrajn. 

U kif tistgħu taraw, l-uniku wieħed li verament ma ukoll huwa tip jingħaqdu, li aħna ser jsibu rwieħhom għaliex. Allura aħna qed tmur biex tmur fil- li jmiss minn tip wieħed ta 'għażla here--. Hawn xi ħadd ftakar kif għażla ħadem sort? Mur għaliha. 

STUDENT: Bażikament jgħaddu ordni u joħolqu lista ġdida. U hekk kif int tqegħid elementi fil, tpoġġihom fil-post it-tajjeb fil-lista l-ġdida. 

Istruttur: Allura li ħsejjes aktar simili sort inserzjoni. Imma int verament qrib. Huma qed simili ħafna. Anke I tikseb minnhom mħallta up kultant. Qabel din is-sezzjoni I kien simili, stenna. OK. Allura dak li trid tagħmel huwa sort għażla, il-mod inti tista 'taħseb dwar dan u l-mod I jagħmlu ċert I ipprova ma tikseb minnhom mħallta up, huwa tmur permezz u huwa jagħżel l- iżgħar numru u ipoġġi li fil-bidu tal-lista tiegħek. Hija tpartit ma 'dik l-ewwel post. Huma għandhom attwalment eżempju għalija. Biża. Allura biss mod biex jaħsbu ta 'għażla it-- sort, tagħżel l-iżgħar valur. U aħna qed tmur biex run permezz ta 'eżempju li naħseb se jgħinu għaliex Naħseb visuals dejjem tgħin. Allura aħna tibda ma 'xi ħaġa li huwa kompletament mhux magħżul. Red se jkun mhux magħżula, aħdar se jiġu magħżula. Dan kollu jagħmel sens fit-tieni. 

Allura aħna jgħaddu u aħna jtenni mill-bidu sat-tmiem. U aħna ngħidu, OK, 2 hija iżgħar numru tagħna. Allura aħna qed tmur biex tieħu 2 u aħna qed tmur li jġorrhom lejn il-quddiem tal-firxa tagħna għaliex dan huwa l- iżgħar numru għandna. Allura dak hu li din qed tagħmel hawn. Huwa biss se tpartit dawn iż-żewġ. Allura issa għandna magħżula parti u parti mhux magħżul. U x'hemm tajjeb li niftakru dwar sort għażla hija aħna qed biss għażla mill-parti mhux magħżul. 

Il-parti magħżul inti biss leave waħdu. Mm-hm? 

STUDENT: Kif ma taf liema hu l-iżgħar mingħajr tqabbilha għal kull valur ieħor fil-firxa. Istruttur: Hija ma din titqabbel. Aħna simili skipped dan. Dan huwa biss ġenerali globali. Yeah. Meta aħna tikteb l-kodiċi jien żgur li int ser tkun aktar sodisfatti. Imma int taħżen din l-ewwel element bħala l-iżgħar. Tqabbel u int jgħidu, OK, huwa iżgħar? Iva. Żomm dan. Hawnhekk huwa iżgħar? No? 

Dan huwa l-iżgħar tiegħek, jassenja mill-ġdid lill-valur tiegħek. U tkun taf tkun ferm kuntenti meta aħna jgħaddu mill-kodiċi. Allura aħna jgħaddu, aħna tpartit, hekk allura aħna nħarsu lejn dan il-porzjon mhux magħżul. Allura aħna qed tmur biex jagħżlu tlieta out. Aħna qed tmur biex tqiegħed lilha fuq mill l-aħħar tal-porzjon magħżul tagħna. U aħna qed biss jmorru biex iżommu tagħmel li, tagħmel dan, u tagħmel dan. Allura dan huwa tip tagħna ta pseudocode hawn. Aħna ser kodiċi it up here fit-tieni. Iżda biss xi ħaġa li jimxu permezz ta 'fuq livell għoli. Inti qed tmur biex jmorru minn i ugwali 0 sa n minus 2. C'est ottimizzazzjoni ieħor. Tinkwetax wisq dwar dan. Allura kif inti kienu jgħidu. Kif Jacob kien qal, kif do we iżommu rekord ta 'dak minimu tagħna huwa? Kif inkunu nafu? Aħna jkollu jqabbel kollox fil-lista tagħna. 

Allura minimu ugwali i. Huwa biss qal f'dan il-każ l-indiċi tal-valur minimu tagħna. Mela allura li għaddej biex jtenni permezz u jmur minn j ugwali i plus 1. Allura aħna diġà jafu li li l-ewwel element tagħna. Ma kellniex bżonn li din titqabbel ma innifsu. Allura nibdew jitqabbel mal-li jmiss waħda li hija għaliex huwa i plus 1 sa n minus 1, li hija l- aħħar tal-firxa hemmhekk. U aħna qal jekk firxa fi j huwa inqas minn firxa min, allura aħna jassenja mill-ġdid fejn indiċijiet minimi tagħna huwa. 

U jekk min mhuwiex ugwali għal i, kif fil fejn konna lura fuq hawn. Allura simili meta aħna ewwel għamlet dan wieħed. F'dan il-każ, ikun jibdew fil żero, ikun jispiċċaw tnejn. Allura min kieku ma ugwali i fl-aħħar. Li tikri minna nafu li għandna bżonn li tpartit lilhom. Inħoss bħal eżempju konkret se jgħin ħafna aktar minn dan. So I ser kodiċi dan up miegħek guys dritt issa u naħseb li ser tkun aħjar. 

Xorta għandhom tendenza li jaħdmu dak il-mod f'dik huwa spiss aħjar biss biex tara minnhom. Allura dak li rridu nagħmlu huwa aħna l-ewwel trid l-iżgħar element fil-pożizzjoni tagħha fil-firxa. Eżattament dak Jacob kien qal. Ikollok bżonn taħżen li b'xi mod. Allura aħna qed tmur biex tibda hawn mtennija tul l-arranġament. Aħna qed tmur biex ngħid huwa tagħna ewwel wieħed biss biex tibda bil. Allura aħna ser ikollhom int iżgħar hija ugwali għal firxa fil i. 

Allura ħaġa waħda li l-avviż, kull żmien dan loop tesegwixxi, aħna qed jibdew pass ulterjuri flimkien. Meta nibdew inħarsu lejn dan wieħed. Il-ħin li jmiss aħna jtenni permezz, aħna qed jibdew minn dan wieħed u assenjazzjoni tiegħu iżgħar valur tagħna. Allura huwa simili ħafna għall tip bużżieqa fejn nafu li wara pass wieħed, dan l-aħħar element huwa magħżul. Bil sort għażla, huwa biss l-oppost. 

F'kull pass, aħna nafu li l-ewwel wieħed huwa magħżul. Wara t-tieni pass, il- tieni waħda se jiġu magħżula. U kif inti raw mal-eżempji slide, porzjon magħżula tagħna biss tkompli tikber. Allura billi tistabbilixxi iżgħar wieħed tagħna biex arrays i, kollha li qed jagħmel huwa constricting liema aħna qed tħares lejn sabiex biex jimminimizzaw in-numru ta 'paraguni nagħmlu. Ma li jagħmel sens għal kulħadd? Għandek bżonn lili biex imexxu permezz ta 'dak għal darb'oħra bil-mod jew fi kliem differenti? Ninsab kuntenta li. OK. 

Allura aħna qed ħażna tal- valur f'dan il-punt, imma aħna wkoll tixtieq li taħżen l-indiċi. Allura aħna qed tmur biex jaħżnu l- pożizzjoni tal-iżgħar wieħed, li huwa biss se tkun i. Allura issa Jacob huwa sodisfatt. Għandna affarijiet maħżuna. U issa għandna bżonn li tfittex permezz il-parti mhux magħżul mill-firxa. Allura f'dan il-każ dan Ikun mhux magħżul tagħna. Dan huwa i. OK. 

Allura dak li aħna qed tmur biex tagħmel se tkun għal loop. Kull meta għandek bżonn biex jtenni permezz ta 'firxa, moħħok tista 'tmur għall għal loop. Allura għal xi int k equals-- dak li aħna naħsbu k se indaqs biex tibda bil? Dan huwa dak li aħna waqqafna bħala iżgħar tagħna valur u rridu li din titqabbel. What do rridu li din titqabbel ma? Li għaddej biex jkun dan wieħed li jmiss, id-dritt? Hekk irridu k li għandu initialized biex i flimkien ma '1 biex tibda. 

U rridu k f'dan il-każ aħna diġà qies maħżuna up here, hekk nistgħu biss tuża daqs. Daqs huwa l-daqs tal-array. U aħna biss jixtiequ taġġorna k minn wieħed kull darba. Kessaħ. Allura issa għandna bżonn li ssib l-element iżgħar hawn. Hekk jekk aħna jtenni permezz, aħna irrid ngħid, jekk array fi k huwa inqas minn iżgħar value-- tagħna dan huwa fejn aħna qed attwalment iżżomm rekord ta 'x'hemm l-iżgħar here-- allura irridu jassenja mill-ġdid dak iżgħar valur tagħna huwa. 

Dan ifisser li, oh, aħna qed mtennija permezz ta 'hawn. Tkun xi valur huwa hawnhekk huwa mhux ħaġa iżgħar tagħna. Aħna ma jriduhom. Aħna rridu li jassenja mill-ġdid. Mela jekk aħna qed jassenjaw mill-ġdid huwa, liema do inti taħseb li tista 'tkun f'dan il-kodiċi hawn? Aħna rridu li jassenja mill-ġdid iżgħar u l-pożizzjoni. Allura dak li huwa l-iżgħar issa? STUDENT: Array k. Istruttur: Array k. U dak li huwa f'pożizzjoni issa? X'hemm l-indiċi ta ' iżgħar valur tagħna? Huwa biss k. Allura firxa k, k, huma jaqblu. Hekk ridna li jassenja mill-ġdid dik. U allura wara sibna iżgħar tagħna, hekk fl-aħħar ta dan għall loop hawn sibna dak iżgħar tagħna valur huwa, hekk aħna biss tpartit. F'dan il-każ, bħal ngħidu tagħna iżgħar valur huwa hawnhekk. Dan huwa l-iżgħar valur tagħna. 

Aħna biss trid li tpartit hawnhekk, li hija dak dik il-funzjoni tpartit fil-qiegħ ma, li aħna biss kiteb up flimkien koppja minuti ilu. Għalhekk għandha tfittex familjari. U allura biss se jtenni permezz sakemm jilħaq it-triq kollha sa l-aħħar, li jfisser li inti ikollhom elementi żero li mhumiex magħżulin u kull ħaġa oħra tkun ġiet magħżula. Jagħmel sens? A ftit aktar konkret? L-għajnuna kodiċi? 

STUDENT: Għal daqs, int qatt ma verament jiddefinixxu jew jibdlu, kif ma taf? 

Istruttur: Allura ħaġa waħda li Avviż up hawnhekk huwa daqs int. Allura aħna qed tgħid f'dan it-tip sort-- hija funzjoni f'dan case-- huwa sort għażla, huwa għadda fil mal-funzjoni. Mela jekk ma kienx għadda fil, inti se tagħmel xi ħaġa bħall mat-tul tal-firxa jew inti se jtenni permezz biex isibu l-tul. Iżda għaliex dan huwa għadda fil, nistgħu tagħmel użu minnha biss. Inti biss wieħed jassumi li l-utent ħadt daqs valida li attwalment tirrappreżenta daqs ta 'firxa tiegħek. Kessaħ? 

Jekk inti guys jkollhom xi problemi ma 'dawn jew tixtieq aktar prattika kodifikazzjoni xorta fuq tiegħek, inti għandek mur study.cs50. Huwa għodda. Huma għandhom kontrollur li inti tista 'attwalment tikteb. Huma jagħmlu pseudocode. Huma għandhom aktar videos u slides inklużi dawk I użu hawn. Mela jekk int xorta tħossok ftit fuzzy, ipprova li minn. Bħal dejjem, come tkellem lili, wisq. Mistoqsija? 

STUDENT: Inti tgħid l- Daqs huwa definit preċedentement? Istruttur: Iva. Id-daqs jiġi qabel definit up hawn fid-dikjarazzjoni funzjoni. Allura inti jassumi li huwa kien għadda fi mill-utent, u għall-finijiet ta 'sempliċità, aħna qed tmur li wieħed jassumi li l- utent tawna l-daqs korrett. Kessaħ. Allura dak it-tip ta 'għażla. Guys, I know aħna qed jitgħallmu ħafna llum. Huwa data dens għal taqsima. Allura ma 'dan, aħna ser biex tmur sort inserzjoni. 

OK. Allura qabel li għandna nagħmlu analiżi runtime tagħna hawn. Hekk fil-każ aħjar, mogħti peress I wera li inti -tabella I diġà tip ta 'tatha bogħod. Iżda każ runtime aħjar, dak li aħna naħsbu? Kollox magħżula. N kwadru. Kull min ikollu spjegazzjoni għal għaliex taħseb? 

STUDENT: Inti jitqabblu through-- Istruttur: Dritt. Inti jitqabblu permezz. F'kull iterazzjoni, anki jekk aħna qed decrementing dan billi wieħed, int xorta tiftix permezz kollox biex isibu l-iżgħar waħda. Għalhekk anki jekk iżgħar valur tiegħek huwa hawn fil-bidu, int xorta tqabbilha kontra kull ħaġa oħra biex tagħmel ċert li huwa l-ħaġa iżgħar. Allura inti ser jispiċċaw taħdem permezz madwar n kwadrat żminijiet. Kull dritt. U x'inhu l-agħar każ? Wkoll n kwadrat għaliex inti qed tmur li tkun qiegħda tagħmel l-istess proċedura. Allura f'dan il-każ, l-għażla sort għandu xi ħaġa li aħna wkoll sejħa runtime mistenni. Allura fl-oħrajn, aħna biss nafu il-limiti ta 'fuq u t'isfel. Skond kif crazy tagħna lista hija jew kif mhux magħżul huwa, dawn ivarjaw bejn n jew n kwadrat. Ma nafux. 

Iżda minħabba sort għażla għandha l-istess agħar u l-aħjar każ, li tgħidilna li x'ikun it-tip ta 'input aħna jkollhom, kemm jekk huwa kompletament magħżula jew kompletament reverse magħżula, huwa ser tieħu l-istess ammont ta 'ħin. Allura f'dak il-każ, jekk inti ftakar mit-tabella tagħna, hija effettivament kellha valur li dawn iż-żewġ tipi ma jkollhomx, li huwa runtime mistenni. Allura aħna nafu li kull meta we run sort għażla, huwa garantit li run n kwadrat żmien. M'hemm l-ebda varjabilità hemmhekk. Huwa biss mistenni. U, għal darb'oħra, jekk inti tixtieq titgħallem aktar, tieħu CS 124 fil-Rebbiegħa. Kull dritt. Rajna dan wieħed. Kessaħ. Sort hekk inserzjoni. U jien probabbilment se blaze permezz ta 'dan. I mhux se jkollhom inti guys kodiċi dan. Aħna ser biss walk permezz tiegħu. Allura sort inserzjoni huwa tip ta 'tip simili għal għażla f'dak għandna kemm mhux magħżul u magħżula parti mill-firxa. 

Imma x'hemm differenti hija li kif aħna jgħaddu waħda waħda, aħna biss jieħdu kwalunkwe numru huwa li jmiss fil mhux magħżul tagħna, u sort korrettament fis firxa ssortjat tagħna. Hija ser tagħmel aktar sens ma 'eżempju. Hekk kollox jibda bħala mhux magħżul, Eżatt bħal ma sort għażla. U aħna qed tmur biex dan sort fl axxendenti ordni kif ilna. Allura fuq l-ewwel pass tagħna nieħdu l-ewwel valur u aħna ngħidu, OK, inti issa f'lista mill yourself. 

Għaliex inti fil-lista minnek, inti huma magħżula. Congratulations talli kienet l- ewwel element f'din firxa. Int diġà magħżula kollha fuq tiegħek. Allura issa għandna magħżula u l-firxa mhux magħżul. Allura issa aħna jieħdu l-ewwel. X'jiġri bejn hawn u hawnhekk hija li aħna ngħidu, OK, aħna qed tmur biex tħares lejn il- ewwel valur tal-firxa mhux magħżul tagħna u aħna qed tmur biex input fil tagħha post korretta fil-firxa ssortjat. 

Allura dak li nagħmlu huwa nieħdu 5 u ngħidu, OK, 5 huwa akbar minn 3, hekk aħna biss daħħal dan id-dritt għad-dritt ta 'dak. Aħna qed tajba. Allura mbagħad immorru fuq xi wiehed jmiss tagħna. U nieħdu 2. Aħna ngħidu, OK, 2 huwa inqas minn 3, hekk aħna nafu li jeħtieġ li tkun fil- quddiem tal-lista tagħna issa. Allura dak li nagħmlu huwa aħna timbotta 3 u 5 isfel u nimxu 2 f'dak l-ewwel slot. Allura aħna qed biss ddaħħalha fis il-post korretta għandu jkun. 

Allura aħna nħarsu lejn tagħna wieħed li jmiss, u aħna ngħidu 6. OK, 6 huwa akbar minn kollox fil-firxa ssortjat tagħna, hekk aħna biss tag fuq l-aħħar. U allura aħna nħarsu lejn 4. 4 huwa inqas minn 6, huwa inqas minn 5 iżda huwa akbar minn 3. Allura aħna biss daħħal dan id-dritt fis -nofs bejn 3 u 5. Allura biex jagħmlu dak ftit ftit aktar konkreti, hawnhekk huwa tip ta 'l- idea ta 'dak li ġara. Allura għal kull element mhux magħżul, aħna ddeterminat fejn fil-porzjon magħżul huwa. 

Allura jżomm f'moħħu l- magħżula u mhux magħżula, għandna biex travers permezz u figura fejn taqbel fil-firxa ssortjat. U aħna daħħalha billi ċċaqlaq il- elementi għad-dritt ta l-isfel. U allura aħna biss iżommu iterazzjoni permezz sakemm aħna jkollhom lista kompletament magħżula fejn mhux magħżul issa huwa żero u magħżula jieħu l- intier tal-lista tagħna. Allura, għal darb'oħra, biex tagħmel affarijiet anke aktar konkreti, għandna pseudocode. 

Allura bażikament għall I huwa ugwali għal 0 sa n minus 1, li jinsab biss t-tul ta 'firxa tagħna. Għandna xi element li huwa ugwali għal l-ewwel firxa jew l-ewwel indiċi. Waqqafna j ugwali għal dak. Allura filwaqt li j huwa akbar minn żero u l-array, j minus 1 huwa akbar mill- element, sabiex dak kollu li qed jagħmel qed tagħmel ċert li j tiegħek verament tirrappreżenta il-porzjon mhux magħżul mill-firxa. 

Allura filwaqt li għad hemm affarijiet biex issolvi u wieħed nieqes j is-- liema huwa l-element tagħha? J qatt ġie definit hawn. Huwa tip ta 'annoying. OK. Anyways. Allura j minus 1, int iċċekkjar l-element quddiemha. Inti qed tgħid, OK, huwa l-element qabel kull fejn I am-- ejja attwalment tiġbed dan out. Mela ejja ngħidu li dan huwa simili fuq it-tieni pass tagħna. Hekk i se jkun ugwali għal 1, li hija hawnhekk. 

Hekk i se tkun ugwali għal 1. Dan ikun 2, 4, 5, 6, 7. Kull dritt. Allura element tagħna f'dan il-każ se tkun ugwali għal 4. U aħna għandna xi j thats se jkun ugwali għal 1. Oh, j huwa decrementing. Dan huwa dak li hu. Allura j hija ugwali għal i, hekk dak li din hija tgħid huwa li kif nimxu 'l quddiem, aħna qed biss tagħmel ċert li aħna mhux qed fuq indiċjar B'dan il-mod meta aħna qed jippruvaw li daħħal l-affarijiet fil-lista magħżula tagħna. 

Allura meta j hija ugwali għal 1 f'dan il-każ u firxa j minus one-- hekk firxa minus j 1 hija ta '2 f'dan case-- jekk dan huwa akbar mill-element, allura dan kollu qed tagħmel qed tiċċaqlaq affarijiet isfel. Allura f'dan il-każ, array nieqes j wieħed Ikun firxa żero, li huwa 2. 2 ma tkunx akbar minn 4, għalhekk dan ma jeżegwixxix. Allura l-bidla ma jiċċaqlaqx isfel. X'inhu dan ma hawn huwa biss jiċċaqilqu firxa ssortjat tiegħek isfel. F'dan il-każ, fil-fatt, aħna jista do-- ejja jagħmlu dan 3. Hekk jekk aħna qed jimxu permezz ma dan l-eżempju, aħna qed issa hawn. Dan huwa magħżul. Dan huwa mhux magħżul. Kessaħ? Hekk i huwa ugwali għal 2, hekk element tagħna hija ugwali għal 3. U j tagħna hija ugwali għal 2. Allura aħna tfittex permezz u aħna jgħidu, OK, huwa wieħed nieqes firxa j akbar mill-element li aħna qed tħares lejn? U t-tweġiba hija iva, id-dritt? 4 huwa akbar minn 3 u j huwa ta '2, tant dan il-kodiċi tesegwixxi. 

Allura issa dak li nagħmlu firxa fi 2, hekk dritt hawn, aħna tpartit minnhom. Allura aħna biss jgħidu, OK, array ta '2 issa se jkun ta' 3. U j se ugwali j minus 1, li hija l-1. C'est horrible, iżda inti guys jiksbu l-idea. J issa huwa ugwali għal 1. U firxa j huwa biss se tkun ugwali għal element tagħna, li kienet ta '4. I mħassra xi ħaġa I ma għandu ikollhom jew xi ħaġa miswrote, imma inti guys jiksbu l-idea. 

Hija jimxu n. U mbagħad jekk dan kien, ikun loop għal darb'oħra u ngħid, OK, j huwa 1 issa. U firxa j minus 1 issa 2 hija. Huwa inqas minn 2 element tagħna? No? Dan ifisser li aħna stajt mdaħħal dan l-element fil-post korretta fil-firxa ssortjat tagħna. Imbagħad nistgħu nieħdu dan u aħna ngħidu, OK, array magħżul tagħna huwa hawnhekk. U hija kienet ser tieħu dan in-numru 6 u tkun simili, OK, hija ta '6 inqas minn dan in-numru? No? Kessaħ. Aħna qed multa. 

Jagħmlu mill-ġdid. Ngħidu 7. Huwa 7 inqas mill-aħħar ta 'firxa ssortjat tagħna? No Allura aħna qed multa. Għalhekk dan ikun jiġu magħżula. Bażikament dan kollu ma huwa Hi tgħid jieħdu l-ewwel element ta ' firxa mhux magħżul tiegħek, insemmu fejn din tmur fil-firxa ssortjat tiegħek. U dan biss jieħu kura ta 'swaps sabiex tagħmel dan. Inti bażikament biss iskambji sakemm ikun fil-post dritt. L-immaġni viżwali hija li int jiċċaqalqu kollox stabbiliti billi tagħmel dan. 

Allura huwa simili nofs bużżieqa tip esque. Check out istudju 50. I jirrakkomanda ħafna jippruvaw għall-kodiċi dan fuq tiegħek stess. Jekk għandek xi kwistjonijiet jew inti tixtieq li tara kodiċi kampjun għal tip inserzjoni, jekk jogħġbok let me know. Jien dejjem madwar. Allura runtime agħar każ u l-każ runtime aħjar. Kif inti Guy raw mit-tabella I diġà wera inti, huwa kemm n kwadrat u n. 

Tant tip ta 'għaddej off ta' dak li tkellimna dwar ma xorta preċedenti tagħna, agħar każ runtime huwa li jekk huwa kompletament mhux magħżul, għandna biex iqabblu kollha ta 'dawn iż-żminijiet n. We do lott kollu ta 'paraguni għaliex jekk huwa fl-ordni invers, aħna qed tmur biex ngħid, OK, dan huwa l-istess, dan huwa tajjeb, u dan wieħed se jkollhom jiġu mqabbla kontra l-ewwel waħda li għandha tiġi mċaqalqa lura. U kif nikbru lejn l-aħħar denb, għandna biex iqabblu, iqabblu, u qabbel kontra kollox. 

Allura huwa jispiċċa jkun madwar n kwadrat. Jekk huwa korrett allura inti jgħidu, OK, 2, int tajba. 3, int imqabbel ma '2. Int tajba. 4, inti biss mqabbla mal-denb. Int tajba. 6, mqabbla mal-denb, int multa. Allura għal kull post jekk huwa diġà magħżula, int tagħmel paragun wieħed. Allura huwa biss n. U għaliex għandna każ runtime aħjar ta n u runtime agħar każ ta 'n kwadrat, għandna l-ebda runtime mistenni. 

Hija biss tiddependi fuq il- kaos tal-lista tagħna hemmhekk. U għal darb'oħra, ieħor graff u tabella ieħor. Allura differenzi bejn xorta. Jien biss ser riħ permezz, I jħossu bħal konna tkellimna estensiv dwar kif dawn kull tip tal ivarjaw u torbot flimkien. Allura jingħaqdu sort hija l-aħħar waħda I għandhom bore inti guys ma. We do jkollhom stampa pretty colorful. Allura jingħaqdu sort huwa algoritmu rikursivi. Allura do inti guys taf liema funzjoni jirrikorri hu? 

Kull min jixtiequ li ngħid? Inti tixtieq li jippruvaw? Allura funzjoni jirrikorri huwa biss funzjoni li s-sejħiet innifsu. Hekk jekk inti guys huma familjari mas-sekwenza Fibonacci, thats meqjusa rikursivi għaliex tieħu l-żewġ preċedenti u żidhom flimkien biex tikseb wieħed li jmiss tiegħek. So rikursivi, I dejjem taħseb ta 'recursion bħala bħal spirali hekk int simili jaqaw isfel fis dan. Imma huwa biss funzjoni li s-sejħiet innifsu. 

U, fil-fatt, verament malajr I inti tista 'turi dak li qisu. Allura rikursivi hawn, jekk inħarsu, dan huwa il-mod rikursivi li qosor fuq firxa. Allura dak kollu li nagħmlu huwa għandna funzjoni somma somma li tieħu daqs u l-firxa. U jekk tinnota, id-daqs ta 'tnaqqis minn wieħed kull darba. U kull ma tagħmel hija jekk x huwa ugwali għal zero-- hekk jekk id-daqs tal-array hija ugwali għal zero-- dan jirritorna żero. 

Inkella somom din aħħar element tal-firxa, u mbagħad jieħu somma ta il-bqija tal-firxa. Allura huwa biss jitkissru l-isfel fis-problemi iżgħar u iżgħar. Long storja qasira, recursion, funzjoni li s-sejħiet innifsu. Jekk dan huwa kull ma għandek ltqajna barra ta 'dan, dan huwa dak funzjoni jirrikorri hu. Jekk inti tieħu 51, inti se tikseb ħafna, ħafna komda mal recursion. Huwa verament jibred. Kien jagħmel sens fi simili 03:00 wieħed bil-lejl out. U I kien simili, għaliex jiena qatt ma jużaw dan? 

Allura għal tip jingħaqdu, bażikament dak li għaddej biex tagħmel huwa huwa se din tinqasam u farrku isfel sakemm huwa biss elementi singoli. L-elementi singoli huma faċli biex sort. Naraw li. Jekk għandek element wieħed, huwa diġà kkunsidrati magħżul. Allura fuq input ta 'elementi n, jekk n hija inqas minn 2, sempliċiment tirritorna għax li l-mezzi huwa jew 0 jew 1 kif aħna stajt tidher. Dawk huma kkunsidrati elementi magħżula. 

Inkella jitkisser fil nofs. Isolvi l-ewwel nofs, sort-tieni nofs, u mbagħad jingħaqdu flimkien. Għaliex huwa msejjaħ sort jingħaqdu. Allura aħna għandna hawnhekk aħna ser sort dawn. Hekk aħna iżommu jkollhom magħhom sakemm id-daqs array huwa 1. Allura meta huwa 1, aħna biss ritorn minħabba li din hija firxa magħżula, u dan huwa firxa magħżula, u li l- firxa ssortjat, aħna qed kollha magħżula. Mela allura dak li nagħmlu hija aħna tibda jgħaqqadhom flimkien. 

Allura l-mod inti tista ' jaħsbu dwar amalgamazzjoni huwa inti biss tneħħi l-iżgħar numru ta 'kull wieħed mill-arrays sub u biss tehmeż lill-firxa ħarġu. Mela jekk inti tfittex hawn, meta jkollna dawn is-settijiet għandna 4, 6, u 1. Meta irridu li jingħaqdu dawn, aħna nħarsu lejn dawn l-ewwel tnejn u aħna ngħidu, OK, 1 hija iżgħar, din tmur għall-quddiem. 4 u 6, m'hemm xejn li jqabblu li, biss tag fuq l-aħħar. 

Meta aħna jgħaqqdu dawn iż-żewġ, aħna biss jieħdu l-iżgħar waħda minn dawn tnejn, hekk huwa 1. U issa aħna jieħdu l- iżgħar ta 'dawn iż-żewġ, hekk 2. Iżgħar ta 'dawn iż-żewġ, 3. Iżgħar ta 'dawn iż-żewġ, 4, 5, 6. Allura int biss ġbid off dawn. U minħabba li ħadthom ġew magħżula preċedentement, inti biss għandek wieħed paragun kull darba li jkun hemm. Allura aktar kodiċi hawn, biss rappreżentazzjoni. Allura inti tibda fil-nofs u inti sort xellug u l-lemin u mbagħad inti biss jingħaqdu dawk. 

U aħna ma jkollhomx kodiċi għall jingħaqdu dritt hawn. Iżda, għal darb'oħra, jekk inti tmur fuq tistudja 50, dan ser ikun hemm. Inkella come tkellem lili jekk int xorta konfuż. Allura jibred ħaġa hawnhekk huwa li l-aħjar każ, agħar każ, u runtime mistennija huma kollha fil log n, li hija ħafna aħjar minn konna dehru għall-bqija ta 'tipi tagħna. Rajna n kwadrat u dak li għandna attwalment wasalt hawn huwa n log n, li hija kbira. 

Ħares lejn kif ħafna aħjar li hu. Tali kurva sbieħ. Għalhekk ħafna aktar effiċjenti. Jekk inti qatt tista ', l-użu jingħaqdu sort. Hija se jiffrankaw il-ħin. Mbagħad, kif għidna, jekk int stabbiliti f'dan ir-reġjun t'isfel, ma jagħmilx dan ħafna ta 'differenza. Ikollok up għal eluf u eluf ta 'inputs, inti definittivament tixtieq a algoritmu aktar effiċjenti. U, għal darb'oħra, tabella sabiħ tagħna ta 'kulħadd xorta li inti guys tgħallmu llum. 

So I know huwa kien jum dens. Dan mhux neċessarjament ser biex jgħinuk bil pset tiegħek. Imma I biss jixtiequ jagħmlu dikjarazzjoni ta 'ċaħda dik is-sezzjoni mhix biss dwar psets. Dan kollu materjal huwa ġust logħba għall midterms tiegħek. U wkoll jekk inti tagħmel tkompli fuq il CS, dawn huma elementi fundamentali verament importanti li għandek bżonn tkun taf. Allura xi jiem se jkun ftit aktar għajnuna pset, iżda xi ġimgħat se jkun ħafna aktar kontenut attwali li ma jista 'jidher super utli għalik dritt issa, imma I wegħda jekk inti tkompli fuq se jkun ħafna, utli ħafna. 

Allura dak għal sezzjoni. L isfel għall-wajer. I ma kien fi żmien minuta. Iżda hemm inti tmur. U jien se jkollhom donuts jew kandju. Huwa xi ħadd allerġiku għal xejn, mill-mod? Bajd u ħalib. Allura doughnuts huma no? OK. Kull dritt. Ebda ċikkulata? Starburst. Starbursts huma tajbin. OK. Aħna qed tmur biex ikollhom Starburst ġimgħa d-dieħla mbagħad. Dan huwa dak I ser tingħata. Inti guys jkollhom ġimgħa kbira. Aqra spec tiegħek. 

Let me know jekk għandek xi mistoqsijiet. Pset żewġ gradi għandhom ikunu out lilek mill-Ħamis. Jekk għandek xi mistoqsijiet dwar kif I gradati xi ħaġa jew għaliex I gradati ħaġa li l-mod I ma, jekk jogħġbok email me, come tkellem lili. Jien din crazy ftit ġimgħa, iżda I wegħda I xorta se jwieġeb fi żmien 24 siegħa. Allura jkollhom ġimgħa kbira, kulħadd. Xorti tajba fuq pset tiegħek.