[Daqq tal-mużika] 

ANDI Peng: Merħba għall-ġimgħa 3 tas-sezzjoni. Grazzi, inti guys, għal kulħadd li ġejjin għal dan ħin tal-bidu aktar kmieni llum. Imxejna ltqajna sympathique, ftit illum grupp intima. Hekk nisperaw aħna ser tingħata biex finitura, forsi, kmieni, ftit kmieni llum. Allura malajr, biss ftit avviżi għall-aġenda tal-lum. Qabel nibdew, aħna qed se biss jmorru fuq xi kwistjonijiet loġistiċi fil-qosor, pset mistoqsijiet, jinfurmaw, affarijiet bħal dik. U allura aħna ser adsa dritt. Aħna ser jużaw debugger msejħa GDB li tibda debunking kodiċi tagħna, li David spjegat fil lecture l-oħra jum. Aħna ser jmorru fuq l-erba 'tipi ta' tipi. Aħna ser jmorru fuqhom pretty malajr peress li dawn qed pretty intensiv. Iżda nafu li l-pjastri u kodiċi tas-sors huma dejjem online. Hekk li tħossok liberu, fil-skrutinju tiegħek, li mur lura u tagħti ħarsa lejn dak. 

Aħna ser jgħaddu notazzjoni asintotiku, li huwa biss mod fancy ta 'tgħid "runtimes," fejn għandna l-O big, li David spjegat fil lecture. U wkoll għandna Omega, li huwa l-runtime Lower bound. U aħna ser nitkellmu ftit aktar fil-fond dwar kif dawk tax-xogħol. U fl-aħħar, aħna ser jmorru fuq tfittxija binarju, peress li ħafna minnkom li diġà glanced fil psets tiegħek probabilment taf li li hija kwistjoni li fil pset tiegħek. Allura inti ser kollha jkunu kuntenti li aħna tkopri dan illum. 

U fl-aħħar, kull tiegħek taqsima feedback, I attwalment xellug madwar 15 minuta fil l-aħħar għal ftit jmorru fuq loġistika ta pset3, xi mistoqsijiet, forsi daqsxejn ta 'gwida, jekk inti se, qabel nibdew programmazzjoni. Mela ejja nipprova nikseb permezz il-materjal pretty malajr. U allura nistgħu jqattgħu xi żmien tieħu aktar mistoqsijiet għall-pset. KOLLOX SEW. 

Malajr, sabiex biss ftit Avviżi qabel nibdew illum. L-ewwelnett, merħba li jagħmlu permezz tnejn mill psets tiegħek. I ħa ħarsa lejn your-- yeah, ejja jiksbu rawnd ta 'applause għal li wieħed. Fil-fatt, I kien verament, verament impressjonat. I gradati-ewwel pset għalik guys aħħar ġimgħa u inti guys ma inkredibbli. 

Style kien fuq punt minbarra ftit kummenti. Kun żgur li int dejjem tikkummenta kodiċi tiegħek. Iżda psets tiegħek kienu fuq punt. U żżommha. U dan huwa tajjeb għall-grader biex tara li inti guys qed ipoġġu fl-isforz kemm fl-istil tiegħek u d-disinn tiegħek fil-kodiċi tiegħek li nixtiequ għalik biex tara. Hekk jien tgħaddi tul gratitudni tiegħi għall-bqija tal-TAs. 

Madankollu hemm ftit mistoqsijiet jinfurmaw I biss jixtiequ li jmorru fuq dak jagħmel kemm l-ħajja tiegħi u ħafna mill-oħra TAs "ħajja daqsxejn aktar faċli. L-ewwelnett, stajt ndunat dan passat week-- kif ħafna minnkom ilhom check50 fuq kodiċi tiegħek qabel ma tissottometti? KOLLOX SEW. Sabiex kulħadd għandha tkun qiegħda tagħmel check50, because-- a secret-- għandna attwalment run check50 bħala parti mill-korrettezza tagħna skripts għal ittestjar kodiċi tiegħek. Mela jekk il-kodiċi tiegħek qed jonqos check50, fil-probabbiltà kollha, huwa probabbilment se jonqsu kontroll tagħna kif ukoll. Kultant inti guys l-tweġibiet dritt. Bħal fil greedy, xi wħud inti għandek in-numri dritt, inti biss jistampa xi għalf żejda. U li Jittieħed extra fil-fatt tonqos il-verifika, minħabba li l-kompjuter ma verament jafu liema huwa tfittex. U għalhekk se biss run permezz, tara li l-produzzjoni tiegħek ma jaqblu ma 'dak li nistennew ir-risposta li jkun, u l-marka huwa żbaljat. 

U naf li ġara fil xi wħud każijiet tiegħek din il-ġimgħa. So I marru lura u manwalment jerġa 'jiġi ggradat kodiċi kulħadd. Fil-futur għalkemm, jekk jogħġbok, jekk jogħġbok aċċerta ruħek li int taħdem check 50 fuq kodiċi tiegħek. Għaliex dan huwa tip ta 'uġigħ għall-AT li jkollhom imorru lura u manwalment klassifika mill-ġdid kull pset waħda għal kull waħda, eżempju ftit mitlufa. So I ma ħaditx off xi punti. I think I ħa off forsi wieħed jew tnejn għal disinn. Fil-futur għalkemm, jekk int fin-nuqqas check50, punti ser jiġu kkunsidrati off għall-korrettezza. 

Barra minn hekk, psets huma minħabba Ġimgħa f'nofsinhar. I think hemm seba 'minuta perjodu ta 'grazzja tard li aħna nagħtuk. Per time Harvard, li qed jitħallew jkun seba 'minuti tard għall kollox. Allura hawn fil-Yale, aħna ser jaderixxu għal dak ukoll. Iżda pjuttost ħafna, fil 00:07, jekk pset tiegħek ma tkunx fil- li għaddej biex jiġu mmarkati bħala tard. U għalhekk filwaqt li huwa mmarkat l-aktar tard, il-TA-- jien xorta se tkun gradazzjoni psets tiegħek. Sabiex tkun taf xorta tara grad jidhru. Madankollu, nafu li fil l-aħħar tas-semestru, psets tard kollha se jkun biss awtomatikament ażżerat mill-kompjuter. 

Aħna nagħmlu dan għal żewġ raġunijiet. Waħda, kultant aħna nikseb skużati, bħal skużi Dekan, aktar tard li jien ma jafux dwar s'issa. Allura aħna nixtiequ niżguraw li qed gradazzjoni kollox biss fil-każ, bħal, jien nieqsa skuża ta 'dekan tal. U t-tieni, wieħed iżomm mind, inti xorta tista qatra pset waħda li għandha sħiħa punti ambitu. U hekk aħna nixtiequ li grad kollha ta 'psets tiegħek biss biex tiżgura li l-ambitu tiegħek hemm u inti qed tipprova lilhom. Għalhekk anki jekk ma jkun tard, inti ser xorta jiksbu kreditu għall-punti ambitu, I think. 

Allura morali ta 'l-istorja hija, tagħmel żgur psets tiegħek huma fil-ħin. U jekk dawn ma jkunux fuq il-ħin, jafu li mhuwiex kbir. Yeah, qabel I jimxu fuq, ħadd ma jkollu xi mistoqsijiet rigward feedback pset? Yeah. 

UDJENZA: Ridt ngħid aħna tista 'qatra waħda mill-psets? 

ANDI Peng: Yeah. Allura hemm disa psets ġenerali matul il-kors tas-semestru. U jekk ikollok ambitu points-- hekk iskop huwa biss, pretty ħafna, inti jippruvaw l- problema, inti tqegħid fil-ħin, huma inti turi li inti stajt wera inti stajt taqra l-spec. Li ambitu pretty ħafna. U jekk inti qed jissodisfaw punti ambitu, aħna tista 'qatra l-aktar baxx wieħed barra mill-iskop sħiħ. Allura dak fil-vantaġġ tiegħek biex jitlesta u tipprova kull pset. 

Anki upload-- jekk ebda mill dawn jaħdmu, upload kollha. U allura aħna ser nisperaw tkun tista ' jagħtuk xi wħud minn dawk il-punti lura. Kessaħ. Kwalunkwe mistoqsijiet oħra? Great. 

It-tieni nett, l-uffiċċju hours-- ftit noti ta 'malajr dwar ħinijiet tal-uffiċċju. Allura l-ewwel, come kmieni fil-ġimgħa. Ħadd ma huwa qatt fil ħinijiet tal-uffiċċju nhar ta 'Tnejn. Christabel waslet għall ħinijiet tal-uffiċċju aħħar lejl. Yeah, Christabel. U dak li ma għandna għad-uffiċċju sigħat aħħar lejl, Christabel? 

UDJENZA: Kellna ġelat. 

ANDI Peng: Allura dak id-dritt, kellna ġelat fil ħinijiet tal-uffiċċju aħħar lejl. Filwaqt I ma jistax wegħda li aħna ser ikollhom ġelat fuq ħinijiet tal-uffiċċju kull ġimgħa, dak li nista 'wegħda inti hija li se jkun hemm sinifikament student aħjar li proporzjon AT. Bħal leġittimu, huwa simili 00:57. Billi, kuntrast li ma Il-Ħamis, inti stajt ltqajna madwar 150 verament enfasizzat gidjien u l-ebda ġelat. U huwa biss mhux produttivi għal kulħadd. Allura morali ta 'l-istorja hija, come kmieni li ħinijiet tal-uffiċċju u affarijiet tajbin se jiġri. 

Ukoll, jiġu ppreparati biex jistaqsu mistoqsijiet. Inti taf? Irrispettivament ta 'dak TAs, I think, ġew qal, aħna kont qed jkollna istudenti koppja li jaqgħu fil-Ħamis fil, bħal, 10:50 li ma taqra l-spec jkunu simili għinni, għinni. Sfortunatament f'dak il-punt, hemm mhux wisq li nistgħu nagħmlu biex jgħinuk. Allura jekk jogħġbok jaslu kmieni fil-ġimgħa. Come kmieni biex ħinijiet tal-uffiċċju. Jiġu ppreparati biex jistaqsu mistoqsijiet. Kun żgur li inti, bħala student, huma fejn inti jeħtieġ li tkun hekk li l- TAs jistgħu jiggwidaw inti tul, li huwa dak ħinijiet tal-uffiċċju għandu jkun allokat għall. 

It-tieni nett, so I know professuri tixtieq sorpriża għalina ma 'testijiet. I kellhom professur dawk simili, yo, mill-mod, ftakar li nofs it-term ikollok it-Tnejn li jmiss. Yeah, I ma kinitx taf dwar dan nofs it-terminu. So I m ser tkun dik TA li jfakkar inti dak kollu li kwizz 0-- għaliex, tafu, aħna qed CS. Issa li konna arrays isir, ikollok għaliex huwa kwizz 0, mhux kwizz 1, eh? KOLLOX SEW. Oh, I ltqajna xi chuckles fuq li wieħed. KOLLOX SEW. 

Allura kwizz 0 ser tkun 14 Ottubru jekk int fis-sezzjoni it-tnejn-l-Erbgħa u 15 Ott jekk int fil is-sezzjoni it-Tlieta-Ħamis. Dan ma japplikax għall dawk minnkom fil-Harvard who-- Naħseb li inti ser ikunu kollha teħid kwizzijiet tiegħek fuq il-14. 

Allura yeah, ġimgħa d-dieħla, jekk David, fil lecture, tmur, yeah, hekk dwar dan kwizz ġimgħa d-dieħla, inti kollha mhux se tkun ixxukkjat għaliex inti waslet għall-taqsima u inti taf li tiegħek kwizz 0 huwa fil-ġimgħatejn. U aħna ser ikollhom reviżjoni Sessjonijiet u kollox. Sabiex l-ebda inkwiet dwar qed jibża għal dan. Kwalunkwe mistoqsijiet before-- xi mistoqsijiet fil-kwistjonijiet loġistiċi kollha rigward, gradazzjoni, ħinijiet tal-uffiċċju, sezzjonijiet? Yeah. 

UDJENZA: Allura l-kwizz huwa se tkun matul lecture? 

ANDI Peng: Yeah. Allura l-kwizz, I think, huwa 60 minuti allokati f'dak slot ta 'ħin li tkun taf biss tieħu fis-sala lecture. Allura inti ma għandekx li ġejjin fil fuq, bħal, każwali 7:00. Dan kollu tajjeb. Yeah. Kessaħ. 

Kull dritt. Allura aħna qed tmur biex introdott kunċett lilek din il-ġimgħa li David diġà tip tal ttrattaw fil lecture din il-ġimgħa passat. Huwa sejjaħ GDB. U kif ħafna minnkom, filwaqt li fil il-kors ta kitba psets tiegħek, nnotajt buttuna kbir li tgħid "Debug" fuq il-quċċata tal IDE tiegħek? KOLLOX SEW. Allura issa aħna ser fil-fatt tikseb biex jiskopru il-misteru ta 'dak li fil-fatt buttuna ma. And I garanzija inti, huwa beautiful, ħaġa sabiħa. 

Allura sa issa, naħseb kien hemm żewġ affarijiet istudenti kienu tipikament tagħmel meta debugging psets. Waħda, huma jew iżidu fil printf () - hekk kull ftit linji, huma jżidu fil-printf () - oh, dak li huwa dan il-varjabbli? Oh, dak li huwa dan il-varjabbli now-- u inti tip ta 'tara l-progressjoni ta 'kodiċi tiegħek kif tmur. Jew it-tieni metodu gidjien tagħmel huwa li huma biss jiktbu l-ħaġa sħiħa u mbagħad mur bħal dan fl-aħħar. Nisperaw taħdem. I garanzija li inti, GDB hija aħjar minn dawn iż-żewġ metodi. Yeah. Allura dan se jkun l-aqwa ħabib ġdid tiegħek. Għaliex dan huwa ħaġa sabiħa li viżwalment juri kemm dak kodiċi tiegħek qed tagħmel f'punt speċifiku kif ukoll dak kollu tiegħek varjabbli qed iwettqu, bħal dak valuri tagħhom huma, f'dak il-punt speċifiku. U b'dan il-mod, inti tista 'verament stabbiliti breakpoints fil-kodiċi tiegħek. Inti tista 'taħdem permezz tal-linja b'linja. U GDB se jkollhom biss għal inti, murija għalik, liema kollha ta 'varjabbli tiegħek huma, liema huma jagħmlu, x'inhu għaddej fil-kodiċi. U b'tali mod, huwa daqstant faċli biex tara dak li qed jiġri minflok printf-Ing jew kitba fl dikjarazzjonijiet tiegħek. 

Allura aħna ser nagħmlu eżempju ta 'dan aktar tard. Allura dan jidher daqsxejn astratt. Nru inkwiet, aħna ser nagħmlu eżempji. U għalhekk essenzjalment, it-tliet akbar, funzjonijiet l-aktar użati ikollok bzonn fil GDB huma l-Sussegwentement, Pass fuq, u Pass lejn buttuni. Jien ser ras fuq hemm, fil-fatt, id-dritt issa. 

Allura tista 'guys kollha tara li jew għandi zoom fi ftit? Fid-dahar, inti tista 'tara li? Għandi zoom in? Just ftit? OK, berred. Hemm immorru. KOLLOX SEW. 

So I jkollhom, hawn, my implimentazzjoni għall greedy. U filwaqt li ħafna minnkom guys kiteb greedy fil-waqt li loop form-- li huwa mod perfettament aċċettabbli li tagħmel it-- mod ieħor biex tagħmel dan huwa li sempliċiment jaqsam fil-modulo. Għaliex imbagħad inti jista 'jkollhom tiegħek valur u mbagħad ikollhom bqija tiegħek. U allura inti tista 'sempliċement żid dan kollu flimkien. Il-loġika ta 'dak li qed nagħmel hawn jagħmel sens għal kulħadd, qabel nibdew? Speċi ta? Kessaħ. Great. Huwa biċċa pretty sexy tal-kodiċi, nixtieq ngħid. Like I said, David, fil lecture, wara filwaqt li, inti ser kollha tibda tara kodiċi bħala xi ħaġa li l-beautiful. U xi kultant meta inti tara beautiful kodiċi, huwa tali sensazzjoni sabiħa. 

Hekk iżda, filwaqt li dan il-kodiċi huwa ferm beautiful, din ma taħdimx kif suppost. Mela ejja jimxu check50 dwar dan. Iċċekkja 50 20-- OOP. 2? Hija li pset2? Yeah. Oh, pset1. KOLLOX SEW. Allura aħna run check50. 

U kif inti guys tista 'tara hawn, huwa fin-nuqqas ta 'ftit każijiet. U għal xi wħud minnkom, fil- kors ta 'kif isir settijiet problema tiegħek, int simili, ah, għaliex hux qed taħdem. Għaliex huwa jaħdem għal xi Valuri iżda mhux għal oħrajn? Ukoll, GDB se jgħinek figura għaliex dawk l-inputs ma kienux jaħdmu. 

KOLLOX SEW. Mela ejja ara, waħda mill- kontrolli I kien qed ifallu fl check50 kien il-valur input ta 0.41. Allura l-risposta korretta li inti għandek tkun jkollna huwa 4. Iżda minflok dak I am stampar ta huwa l-3-n, li hija żbaljata. Mela ejja biss run dan manwalment, just kun żgur li check50 qed taħdem. Ejja nagħmlu ./greedy. Oops, I għandhom jagħmlu greedy. Hemm immorru. Issa ./greedy. 

Kemm dovuti huwa? Ejja nagħmlu 0.41. U Yep, naraw hawn li huwa outputting 3 meta l-risposta korretta, fil-fatt, għandu jkun ta '4. Mela ejja jidħol GDB u tara kif aħna tista 'tmur dwar l-iffissar din il-problema. 

Allura l-ewwel pass fil dejjem debugging kodiċi tiegħek huwa li jiġi stabbilit breakpoint, jew punt li fih inti jridu li l-kompjuter jew l- debugger biex tibda tħares lejn. Mela jekk inti ma verament jafu liema problema tiegħek hija, normalment, il-ħaġa tipika rridu tagħmel huwa li jiġu stabbiliti breakpoint tagħna fil prinċipali. Mela jekk inti guys tista 'tara dan buttuna ħamra hemm dritt, Yep, li kien me iffissar ta ' breakpoint għall-funzjoni prinċipali. I ikklikkja dan. 

U mbagħad I tista 'tmur sa button debug tiegħi. I hit li buttuna. Let me zoom lura jekk nista '. Hemm immorru. Allura aħna għandna, hawn, bord ieħor fuq il-lemin. Jien sorry, guys fil-dahar, inti ma tistax verament tara verament tajjeb. Iżda essenzjalment, kollha dan il-panel dritt qed tagħmel qed iżżomm rekord ta 'kemm il-enfasizzati linja, li hija l-linja tal-kodiċi li l-kompjuter bħalissa taħdem, kif ukoll kollha ta 'varjabbli tiegħek stabbiliti hawn. 

Allura inti ħadthom ltqajna ċenteżmi, muniti, n, kollha ddikjarati għall-affarijiet differenti f'dan il-punt. Nru inkwiet, għaliex aħna ma attwalment initialized li kwalunkwe varjabbli s'issa. Allura fil-kompjuter tiegħek, tiegħek kompjuter jinsab biss jaraw, oh, 32767 kienet l-aħħar funzjoni użati ta 'dak l-ispazju memorja fil-kompjuter tiegħi. U hekk li meta ċenteżmi bħalissa. Imma l-ebda li ladarba inti tmexxi l-kodiċi, għandu jsir initialized. 

Mela ejja jmorru permezz, linja line, x'inhu għaddej hawn. KOLLOX SEW. Allura hawn huma t-tliet buttuni li jien biss spjegati. Inti għandek l-Play, jew il-funzjoni Run, buttuna, inti għandek l-Pass fuq buttuna, u inti ukoll għandek l-Pass fis buttuna. U essenzjalment, it-tlieta ta ' lilhom biss jgħaddu kodiċi tiegħek u jagħmlu affarijiet differenti. 

Allura tipikament, meta int debugging, ma rridux li biss hit Play, minħabba Play se biss run kodiċi tiegħek sa l-aħħar ta 'dan. U allura inti mhux se attwalment jafu liema problema tiegħek huwa sakemm inti twaqqaf breakpoints multipli. Jekk tkun issettjajt breakpoints multipli, se biss awtomatikament jiddekorri mill breakpoint waħda, għall-ieħor, għall-ieħor. Iżda f'dan il-każ konna biss li wieħed, għaliex aħna jridu jaħdmu mod tagħna minn fuq għal isfel għal isfel. Allura aħna qed tmur biex jinjoraw dak buttuna dritt issa għal finijiet ta 'dan il-programm. 

Allura l-pass fuq funzjoni biss passi aktar minn kull linja waħda u jgħidlek x'għandek il-kompjuter qed tagħmel. Il Pass fil-funzjoni tmur fil-funzjoni proprja li fuq linja tiegħek ta 'kodiċi. Hekk per eżempju, bħall printf (), li hija funzjoni, id-dritt? Jekk jien ridt li fiżikament pass fil-printf () funzjoni, I kien imur fil-biċċa kodiċi fejn printf () ġie miktub u ara x'inhu għaddej hemmhekk. 

Imma tipikament, aħna nassumu li il-kodiċi li aħna nagħtuk xogħlijiet. Nassumu l printf () qed taħdem. Aħna nassumu li GetInt () qed taħdem. Hekk hemm ebda bżonn li pass lejn dawk il-funzjonijiet. Imma jekk hemm funzjonijiet li tikteb lilek innifsek li inti tixtieq li jiċċekkjaw taf x'inhu għaddej, inti tixtieq li pass f'dak il-funzjoni. 

Allura issa dritt aħna qed biss jmorru pass fuq din il-biċċa ta 'kodiċi. Mela ejja ara. Oh, jistampa, "Oh hai, kif huwa dovut ħafna tibdil? " Aħna ma kura. Aħna nafu li ta 'ħidma, hekk aħna pass fuqha. 

Allura n, li huwa float tagħna li konna initialized-- jew declared-- up fil-quċċata, aħna qed issa daqs li biex GetFloat (). Mela ejja pass fuq dik. U naraw fil- qiegħ hawn, il-programm huwa tħeġġeġ me li input valur. Mela ejja il-valur rridu input biex jittestjaw hawnhekk, li huwa 0.41. Great. 

Allura issa n-- tagħmel inti guys tara hawn, fil-bottom-- huwa stored-- għaliex aħna ma jkunux tond għadhom, huwa maħżuna f'dan ġgant bħal float li hija 0.4099999996, li huwa qrib biżżejjed biex tagħna skopijiet, id-dritt issa, li 0.41. U allura aħna ser tara aktar tard, kif aħna tkompli titjib fuq il-programm, wara hawnhekk, n saret tond u ċenteżmi sar 41. Great. Allura aħna nafu li ħidma arrotondament tagħna. Aħna nafu li aħna għandna l- numru korrett ta 'ċenteżmi, hekk aħna nafu li dan huwa mhuwiex verament il-problema. 

Allura aħna nkomplu titjib fuq f'dan il-programm. Immorru hawn. U hekk wara din il-linja ta 'kodiċi, aħna għandhom ikunu jafu kemm kwarti għandna. Aħna pass fuq. U inti tara nagħmlu, fil-fatt, jkollhom waħda kwart għaliex konna mnaqqas 25 mill-valur inizjali tagħna ta '41. U aħna għandna 16-xellug għal ċenteżmi tagħna. 

Ma kulħadd jifhem kif il-programm huwa titjib permezz u għaliex ċenteżmi issa sar 16 u għaliex, issa, muniti sar 1? Huwa kulħadd wara li l-loġika? Kessaħ. Allura kif dan il-punt, il- ħidma programm, id-dritt? Nafuh qed jagħmel eżattament dak li aħna tixtieq li. U aħna ma attwalment għandek jistampa, oh, dak huwa ċenteżmi f'dan il-punt, dak li huwa l-muniti f'dan il-punt. 

Aħna tkompli għaddejja mill-programm. Pass fuq. Kessaħ. Immorru fuq dimes. Great. Naraw li huwa ħa off $ 0.10 għal dime. U issa għandna żewġ muniti. Li korretta. 

Immorru fuq pennies u naraw li konna ltqajna fadal ċenteżmu. Hmm, li stramba. Up hawn fil-programm, I kien suppost li jitnaqqsu pennies tiegħi. Forsi I biss ma kienx tagħmel dan id-dritt line. U sfortunatament, tista 'tara hawnhekk, għaliex nafu li aħna qed iżidu permezz ta 'linji 32 u 33, li fejn programm tagħna indebitament kellhom varjabbli run. Allura nistgħu nħarsu u ara, oh, Jien tnaqqas ċenteżmi hawn, imma jien ma attwalment li jżid mal-valur munita tiegħi. Jien jżid mal ċenteżmi. U ma rridx li żżid mal ċenteżmi, nixtieq li żżid mal-muniti. Mela jekk irridu bidla li għall-muniti, konna ltqajna programm ta 'ħidma. I tista 'taħdem check50. Tista 'biss ħruġ minn dritt GDB hawn u mbagħad għaddi check50 mill-ġdid. I tista 'biss tagħmel dan. I għandhom jagħmlu greedy. 0.41. U hawn, huwa istampar l-tweġiba t-tajba. 

Allura kif inti guys tista 'tara, GDB hija għodda verament b'saħħtu għal meta għandna kodiċi tant għaddej u varjabbli tant li huwa diffiċli għalina, bħala bniedem, li jżommu rekord ta. Il-kompjuter, fil-GDB debugger, għandu l-abbiltà biex iżżomm kont ta 'kollox. Naf, fil Visionaire, inti guys probabbilment jista 'jkollhom hit xi difetti segmentazzjoni għaliex inti kienu qed jaħdmu barra mill-limiti ta 'firxa tiegħek. Fl-eżempju ta 'Caesar, li eżattament dak li stajt implimentati hawn. 

So I nesa li jikkontrolla għal x'għandu jiġri jekk I ma kellux żewġ argumenti kmand linja. I biss ma poġġiex f'dak verifika. U hekk jekk I run Debug-- I sett breakpoint tiegħi għad-dritt hemmhekk. I run debug. 

KOLLOX SEW. Yeah. Allura fil-fatt, GDB kien suppost li told me hemmhekk kien tort segmentazzjoni hemmhekk. I do not know dak li kien għaddej hemm dritt, imma meta I dam, kien qed jaħdem. Meta inti tmexxi linji ta 'kodiċi permezz u GDB jistgħu biss f'daqqa nieqaf fuqek, jitla 'u jfittxu dak l-iżball aħmar huwa. Hija ser jgħidlek, ħej, inti kellhom tort segmentazzjoni, li jfisser li inti ppruvaw aċċess ispazju fil-firxa li ma kinux jeżistu. Yeah. 

Allura fil-problema li jmiss stabbiliti din il-ġimgħa, inti guys probabbilment se jkollhom ħafna ta ' varjabbli floating madwar. Int mhux se jkun ċert liema dawn kollha jfissru f'ċertu punt. Allura GDB se verament tgħinek fil jidhru barra dak li huma kollha daqs u tkun tista 'tara li viżwalment. Huwa kwalunkwe persuna konfuż dwar kif xi li kien qed jaħdem? Kessaħ. Kull dritt. Allura wara dan, aħna se adsa dritt fis erba differenti tipi ta 'tip għal din il-ġimgħa. Kemm inti, l-ewwel ta 'kollha, qabel nibdew, qrajt l-spec kollu għall pset3? KOLLOX SEW. Jien kburi inti guys. C'est simili nofs tal-klassi, li hija sinifikament aktar minn aħħar darba. 

Allura li l-kbir, għax meta nitkellmu dwar il-kontenut fi lecture-- jew sorry, fil section-- I simili li jirrelataw ħafna li lura għal dak l-pset huwa u kif inti tixtieq li jimplimentaw dik fil pset tiegħek. Mela jekk inti come li aqra l-spec, dan ser jkun ħafna aktar faċli għalik biex tifhem dak li nkun qiegħed jitkellem dwar meta I say, oh ħej, dan jista 'jkun verament post tajjeb biex jimplimentaw dan it-tip. Allura dawk minnkom li taqra l- spec jafu li, bħala parti mill-pset tiegħek, int se jkollhom jiktbu tip ta 'tip. Allura dan jista 'jkun utli ħafna għal ħafna minnkom illum. 

Allura aħna ser tibda off ma ', essenzjalment, l-aktar tip sempliċi tal sort, l-xorta għażla. L-algoritmu tipiku għall kif aħna'd tmur dwar dan is-- David marru permezz ta 'dawn kollha lecture, so I ser malajr jimxu flimkien here-- hija essenzjalment, inti jkollhom firxa ta 'valuri. U allura inti ssib l- iżgħar valur ma jiġix separat u inti tpartit dak il-valur ma ' l-ewwel valur mhux magħżul. U allura inti biss iżommu tirrepeti mal-bqija tal-lista tiegħek. 

U hawnhekk spjegazzjoni viżwali ta 'kif li tkun taħdem. Għalhekk, per eżempju, jekk konna biex tibda ma 'firxa ta' ħames elementi, indiċi 0 sa 4, bi 3, 5, 2, 6, u 4-valuri mqiegħda fil-array-- hekk dritt issa, aħna qed biss ser tassumi li dawn qed kollha mhux magħżul għaliex aħna mhux ittestjati mod ieħor. 

Allura kif sort għażla kieku xogħol huwa li dan iwassal ewwel jgħaddi mill-intier mill-firxa mhux magħżul. Ikun pick out-iżgħar valur. F'dan il-każ, 3, id-dritt issa, huwa l-iżgħar. Jiġrilha sa 5. Nope, 5 ma tkunx akbar than-- jew sorry, ma jkunx inqas than-- 3. Allura l-valur minimu għadu 3. U mbagħad ikollok għal 2. Il-kompjuter jara, oh, 2 ikun anqas minn 3. 2 issa għandu jkun il-valur minimu. U hekk 2 iswaps li l-ewwel valur. 

Allura wara pass wieħed, aħna tabilħaqq tara li l-2 u 3 huma mibdula. U aħna qed biss se tkompli tagħmel dan jerġa mal-bqija tal-firxa. Allura aħna qed tmur biex biss run permezz l-aħħar erba 'indiċi ta' l-array. Ser naraw li 3 huwa il-valur minimu li jmiss. Allura aħna qed tmur biex tpartit li ma 4. U allura aħna qed biss ser iżommu tmexxija permezz sakemm, eventwalment, inti nikseb għal firxa Issortjat li fih 2, 3, 4, 5, u 6 huma kollha magħżula. Ma kulħadd jifhem il-loġika ta 'kif xorta għażla xogħlijiet? 

Inti sempliċiment għandek xi tip ta 'valur minimu. Int iżżomm rekord ta 'dak li hu. U kull meta issibha, inti tpartit l-ewwel valur fis-array-- jew, mhux l-ewwel value-- il-valur jmiss fil-firxa. Kessaħ. 

Allura kif inti guys tip ta ' raw minn idea fil-qosor, aħna qed tmur biex pseudocode dan out. Mela jekk inti guys fil-dahar jridu jiffurmaw grupp, kulħadd fuq mejda jistgħu jiffurmaw sieħeb ftit, jien ser li jtik guys simili tliet minuti għal ftit jitkellmu permezz il-loġika, bl-Ingliż, ta 'kif nistgħu ikunu jistgħu jimplimentaw pseudocode jiktbu tip selezzjoni. U hemm kandju. Jekk jogħġbok toħroġ u jiksbu kandju. Jekk int fil-dahar u inti tixtieq kandju, I tista tarmi kandju fi inti. Attwalment, do jibred you--. Oh, sorry. KOLLOX SEW. 

Mela jekk nixtiequ li, bħala klassi, write pseudocode għal kemm wieħed jista 'approċċ din il-problema, biss tħossok liberu. I ser biss jmorru madwar u, sabiex, staqsi gruppi għal-linja li jmiss ta ' dak li għandha tkun qiegħda tagħmel. Mela jekk inti guys tixtieq li tibda off, x'inhu l-ewwel ħaġa li tagħmel meta inti qed tipprova timplimenta mod biex issolvi dan il-programm li selettivament issolvi lista? Ejja biss wieħed jassumi aħna jkollhom firxa, id-dritt? 

UDJENZA: Inti tixtieq li joħolqu xi tip ta '[inaudible] li int taħdem permezz sensiela sħiħa tiegħek. 

ANDI Peng: Dritt. Allura int tmur jridu jtenni permezz ta 'kull spazju, id-dritt? Allura, kbir. Jekk inti guys tixtieq li tagħti me l- jmiss line-- yeah, fid-dahar. 

UDJENZA: Iċċekkja minnhom kollha għall-iżgħar. 

ANDI Peng: Hemm immorru. Allura irridu jgħaddu u tikkontrolla biex tara dak il-valur minimu huwa, right? Jien ser jqassar li biex "min." What do you guys trid tagħmel wara inti stajt sabu l-valur minimu? 

UDJENZA: [inaudible] ANDI Peng: Allura int tmur jridu jaqilbu l-ewwel ta 'dak array, id-dritt? Dik hija l-bidu, jien ser ngħid. Kull dritt. Allura issa li inti stajt skambjat l-ewwel wieħed, dak li inti trid tagħmel wara dan? Allura issa aħna nafu li dan wieħed hawn għandu jkun l-iżgħar valur, id-dritt? Imbagħad għandek mistrieħ addizzjonali tal-firxa li l-mhux magħżul. Allura dak li inti trid tagħmel hawn, jekk inti guys jridu jagħtu me-linja li jmiss? UDJENZA: Mela allura inti tixtieq li jtenni permezz tal-bqija tal-firxa. ANDI Peng: Yeah. U hekk dak li ma mtennija permezz tip ta 'jimplika aħna probabilment bżonn? Liema tip of-- 

UDJENZA: Oh, varjabbli addizzjonali? ANDI Peng: Probabbilment ieħor għall loop, right? Allura aħna qed probabbilment tmur jridu li jtenni through-- kbira. U allura int se jmorru lura u probabbilment jivverifika l-minimu mill-ġdid, id-dritt? U int ser iżommu tirrepeti dan, minħabba li l-linji biss ser li jżomm taħdem, right? 

Allura kif inti guys tista 'tara, aħna biss ikollhom pseudocode ġenerali ta 'kif irridu dan il-programm tfittex. Dan jtenni hawn, liema do we tipikament bżonn jiktbu fil-kodiċi tagħna jekk irridu li jtenni permezz ta ' firxa, liema tip ta 'struttura? I think Christabel diġà qal dan qabel. 

UDJENZA: A għall loop. 

ANDI Peng: A għall loop? Eżattament. Allura dan huwa probabbilment se tkun għall loop. X'inhu kontroll hawnhekk se jimplikaw? Tipikament, jekk inti tixtieq li tivverifika jekk xi ħaġa hija xi ħaġa else-- 

UDJENZA: Jekk. 

ANDI Peng: An jekk, right? U allura l-tpartit hawn, aħna ser jmorru fuq wara, għaliex David marru permezz li lecture kif ukoll. U allura l-tieni jtenni implies-- 

UDJENZA: Ieħor għall loop. 

ANDI Peng: --another għall loop, eżattament. Allura jekk aħna qed tfittex f'dan korrett, aħna jista 'jara li aħna qed probabbilment ser jeħtieġu nested għall loop ma 'dikjarazzjoni kondizzjonali fil hemm u mbagħad biċċa attwali ta 'kodiċi li l- se tpartit l-valuri. Hekk stajt biss ġeneralment bil-miktub kodiċi pseudocode hawn. U allura aħna qed attwalment għaddejjin li fiżikament, bħala klassi, tipprova timplimenta dan illum. Ejja ħa mmorru lura fis dan IDE. 

Uh-oh. Għaliex huwa li not-- hemm hu. KOLLOX SEW. Jiddispjacini, let me jippruvaw li zoom daqsxejn aktar. Hemm immorru. All qed nagħmel hawn qed stajt maħluqa programm imsejjaħ "għażla / sort.c." Stajt ħolqot firxa ta 'disa' valuri, 4, 8, 2, 1, 6, 9, 7, 5, 3. Bħalissa, kemm tista ' tara, huma unordered. n se jkun in-numru li jgħidlek l-ammont ta 'valuri għandek fil-firxa tiegħek. F'dan il-każ, għandna disa valuri. U stajt biss ltqajna għall loop hawn li tistampa l-firxa mhux magħżul. 

U fl-aħħar, stajt ukoll ltqajna biex loop li biss prints out mill-ġdid. Allura teoretikament, jekk dan il-programm qiegħed jaħdem sew, fl-aħħar, inti għandek tara stampati għall loop li fihom 1, 2, 3, 4, 5, 6, 7, 8, 9 huma kollha b'mod korrett fl-ordni. 

Allura konna ltqajna pseudocode tagħna hawn. Hawn xi ħadd tixtieq to-- jien biss se jmorru jistaqsu għal volunteers-- tell me eżattament dak li tip jekk irridu li, minn naħa, biss jtenni permezz tal-bidu ta 'din array? X'hemm-linja tal-kodiċi jien probabbilment ser jeħtieġu hawn? 

UDJENZA: [inaudible] 

ANDI Peng: Yeah, tħossok to-- sorry ħielsa, inti ma għandekx toqgħod jħossu up-- ħielsa li jgħollu l-vuċi tiegħek daqsxejn. 

UDJENZA: Għal i int ugwali 0-- 

ANDI Peng: Yeah, tajba. 

UDJENZA: i huwa inqas minn tul firxa. 

ANDI Peng: Allura wieħed iżomm mind hawn, għaliex aħna ma jkollhomx funzjoni li tgħidilna it-tul ta 'firxa, aħna diġà għandhom valur li taħżen din. Dritt? Ħaġa oħra li wieħed iżomm fi mind-- fil-firxa ta 'disa' valuri, liema huma l-indiċijiet? Ejja ngħidu biss dan array kien 0 sa 3. Tara li l-aħħar indiċi huwa attwalment 3. Mhuwiex 4, anki jekk hemm erba 'valuri fil-firxa. 

Allura fil hawn, irridu nkunu attenti ħafna ta 'dak kundizzjoni tagħna għat-tul se tkun. 

UDJENZA: Mhux se jkun n minus 1? ANDI Peng: Huwa ser n minus 1, eżattament. Does li jagħmel sens, għaliex huwa n minus 1, kulħadd? Huwa minħabba arrays huma żero indiċjati. Huma jibdew f'0 u mixja lejn n minus 1. Yeah, huwa daqsxejn delikata. KOLLOX SEW. U then-- UDJENZA: Isnt'1 li diġà tittieħed kura ta għalkemm, bi ftit not qal "inqas minn jew daqs "u biss qal" inqas minn? " 

ANDI Peng: Li l- kwistjoni verament tajba. Allura, iva. Iżda wkoll, il-mod li aħna qed implimentat id-dritt verifika, għandek bżonn biex tqabbel żewġ valuri. Allura inti fil-fatt tixtieq li jħallu l-"għal" vojta. Għaliex jekk inti tqabbel dan wieħed, int mhux se jkollhom xejn wara dan biex tqabbel, right? Yeah. Hekk i ++. Ejja żid parentesi tagħna fil. Whoops. Great. Allura aħna għandna l-bidu tal loop barra tagħna. Allura issa aħna probabilment jridu toħloq varjabbli għaż-żamma rekord ta 'l-iżgħar valur, id-dritt? Hawn xi ħadd li tixtieq li tagħti me l- linja ta 'kodiċi li ser jagħmlu dan? What do we bżonn jekk aħna qed tmur li tixtieq li taħżen xi ħaġa? 

Dritt. Forsi isem aħjar għal dak ikun be-- "Temperatura" totalment works-- forsi aktar adattat issemmiet tkun, jekk irridu li l-iżgħar value-- 

UDJENZA: Min. ANDI Peng: min, hemm immorru. min ikun tajjeb. U hekk hawn, liema do we tixtieq li initialize li? Dan huwa daqsxejn delikata. Minħabba dritt issa fil- bidu ta 'dan array, int ma ħares lejn xejn, id-dritt? Allura dak, awtomatikament, jekk Aħna biss fuq i ugwali 0, dak li rridu initialize ewwel valur minimu tagħna li? UDJENZA: i. ANDI Peng: i, eżattament. Christabel, għaliex irridu biex initialize lill i? 

UDJENZA: Minħabba, ukoll, aħna qed jibdew bl 0. Allura għaliex għandna xejn biex iqabblu lill, il-minimu se jispiċċa jkun ta '0. 

ANDI Peng: Eżattament. Hekk hi eżattament id-dritt. Għaliex għandna attwalment ma ħares lejn xejn s'issa, ma nafux liema valur minimu tagħna huwa. Aħna rridu li biss initialize lill i, li, bħalissa, huwa dritt hawn. U kif aħna tkompli jinżel dan array, Ser naraw li, ma 'kull pass addizzjonali, i żidiet. U hekk f'dak il-punt, i huwa probabbilment se li jridu jkunu l-minimu, minħabba li għaddej biex tkun x'ikun huwa l-bidu ta 'l-array mhux magħżul. Kessaħ. 

Allura issa aħna tixtieq iżżid a għal loop hawn li l- ser jtenni permezz tal- mhux magħżul, jew il-bqija ta 'dan array. Hawn xi ħadd li tixtieq li tagħti me linja ta 'kodiċi li ser jagħmlu dan? Hint-- dak li għandna bżonn stabbiliti hawn? X'qed jiġri li jmorru f'din għal loop? Yeah. UDJENZA: Allura aħna'd tixtieq li ikollhom numru sħiħ differenti, għaliex aħna qed taħdem permezz tal-bqija tal-firxa minflok il-i, so forsi j. 

ANDI Peng: Yeah, j ħsejjes tajba għalija. Ugwali? 

UDJENZA: Allura kieku jkun i flimkien ma '1, minħabba int tibda bil-valur jmiss. U allura l-end-- hekk darb'oħra, j huwa inqas minn n minus 1, u mbagħad j ++. ANDI Peng: Great. 

U mbagħad fil hawn, aħna qed tmur jridu biex tikkontrolla biex tara jekk il-kundizzjoni tagħna hija sodisfatta, id-dritt? Għaliex inti tixtieq li jibdlu l-valur minimu jekk huwa attwalment iżgħar minn dak int tqabbil lill, id-dritt? Allura dak li aħna tmur jridu fil hawn? Iċċekkja biex tara. Liema tip ta 'dikjarazzjoni aħna probabbilment se ti jridu jużaw jekk aħna jridu jiċċekkjaw xi ħaġa? 

UDJENZA: An jekk id-dikjarazzjoni. 

ANDI Peng: An jekk id-dikjarazzjoni. Allura if-- u dak li għaddej biex tkun il-kundizzjoni li rridu ġewwa ta jekk id-dikjarazzjoni tagħna? 

UDJENZA: Jekk il-valur ta 'j huwa inqas mill-valur tal i-- 

ANDI Peng: Eżattament. Allura if-- għalhekk dan array huwa msejjaħ "matriċi." Great. Mela jekk array-- dak li kien li? Jgħidu li għal darb'oħra. 

UDJENZA: Jekk array-j hija inqas minn firxa-i, allura aħna se jibdlu l-min. Allura l-min ikun j. 

ANDI Peng: Does li jagħmel sens? KOLLOX SEW. U issa stabbiliti hawn, aħna fil-fatt jridu jimplimentaw il tpartit, right? Allura tfakkar, fl lecture, li David, meta li kien qed jipprova tpartit the-- dak li kien meraq tal-larinġ it-- u milk-- 

UDJENZA: Dan kien gross. 

ANDI Peng: Yeah, li kien tip ta 'gross. Iżda kienet pjuttost tajba kunċett turi ħin. Allura taħseb valuri tiegħek hawn. You ħadthom ltqajna firxa ta min, firxa ta 'i, jew kwalunkwe konna jippruvaw tpartit hawn. U inti probabilment ma tistax pour minnhom fil xulxin fl-istess ħin, id-dritt? Allura dak li aħna se ħtieġa li jinħoloq hawn sabiex tpartit l-valuri b'mod korrett? 

UDJENZA: A varjabbli temporanju. 

ANDI Peng: A varjabbli temporanju. Mela ejja nagħmlu temperatura int. Ara, dan ikun aħjar ħin to-- Whoa, dak li kien li? KOLLOX SEW. Allura dan kien ikun aħjar ħin biex insemmu l-varjabbli "temperatura." Mela ejja nagħmlu temperatura int. Liema huma aħna se sett temperatura ugwali għal hawn? UDJENZA: Min? ANDI Peng: Huwa daqsxejn delikata. Hija fil-fatt ma jimpurtax fl-aħħar. Ma jimpurtax dak li Sabiex inti tagħżel li tpartit fil sakemm int tagħmel żgur li int iżżomm rekord ta 'dak li qed jagħmlu skambju. 

UDJENZA: Jista 'jkun array-i. 

ANDI Peng: Yeah, ejja do firxa-i. U allura x'inhu l-linja li jmiss tal-kodiċi irridu li jkollna hawn? UDJENZA: array-i huwa ugwali array-j. ANDI Peng: U fl-aħħar? UDJENZA: array-j ugwali array-i. Udjenza: Or firxa-j ugwali -array temp-- jew, temperatura. 

ANDI Peng: OK. Mela ejja imexxu dan u ara jekk huwa sejjer jaħdem. Fejn dak jiġri? Oh, li l-problema. Ara, fuq linja 40, aħna qed jippruvaw jużaw firxa-j? Iżda fejn ma j jeżistu biss fil-? 

UDJENZA: Fil-linja għal. ANDI Peng: Dritt. Allura dak li aħna se bżonn tagħmel? 

UDJENZA: Iddefinixxi l barra the-- UDJENZA: Yeah, I raden inti għandek għall-użu ieħor jekk id-dikjarazzjoni, id-dritt? Allura simili, jekk il-minimum-- id-dritt, let me think. 

ANDI peng: Guys, ipprova li tagħti ħarsa Ejja ara, x'hemm xi ħaġa li nistgħu nagħmlu hawn? 

UDJENZA: OK. Allura jekk il-minimu ma tkunx daqs j-- hekk jekk l-minima għadhiex i-- allura aħna ma jkollhomx tpartit. 

ANDI Peng: Does that ugwali i? What do inti tixtieq li ngħid hawn? 

UDJENZA: Or yeah, jekk il- minimu mhuwiex ugwali għal i, yeah. ANDI Peng: OK. Ukoll li jsolvi, it-tip ta ', problemi tagħna. Iżda dan xorta ma kinitx issolvi l- problema ta 'x'jiġri jekk j-- peress j ma teżistix barra minnha, dak do inti irridu li tagħmel magħha? Tiddikjaraha barra? Ejja nippruvaw running dan. Uh-oh. Sort tagħna ma jaħdmux. 

Kif tistgħu taraw, inizjali tagħna firxa kellhom dawk il-valuri. U wara dan għandu jkollu Kien f'1, 2, 3, 4, 5, 6, 7, 8, 9. Huwa ma tkunx qed taħdem. Ahh. X'nagħmlu? UDJENZA: debug. ANDI Peng: Kull dritt, nistgħu nippruvaw dan. Nistgħu debug. Zoom out a bit. Ejja stabbilit breakpoint tagħna. Ejja ħa mmorru OK like--. 

Allura għaliex aħna diġà jafu li dawn il-linji, 15 permezz 22, huma working-- minħabba li kull nagħmel huwa biss mtennija permezz ta 'u printing-- I tista 'tmur quddiem u skip dan. Nibdew fil-linja 25. OOP, let me jeħles ta 'dak. 

UDJENZA: Allura l-breakpoint tal fejn il-debugging jibda? ANDI Peng: Or waqfiet. UDJENZA: Or waqfiet. ANDI Peng: Yeah. Tista 'tissettja breakpoints multipli u hija tista 'biss jaqbżu minn waħda għall-oħra. Iżda f'dan il-każ ma nafux fejn l-iżball li qed jiġri. Allura aħna biss jixtiequ tibda mill-top down. Yep. KOLLOX SEW. 

Allura din il-linja hawnhekk, nistgħu pass pulzieri. Tista 'tara l hawn, konna ltqajna firxa. Dawk huma l-valuri li huma fil-firxa. Inti tara li, kif indiċi 0, huwa jikkorrispondi għall-value-- oh, Jien ser tipprova li zoom. Jiddispjacini, huwa verament diffiċli li see-- fil-indiċi firxa 0, għandna valur tal-4 u imbagħad ibqa 'sejjer hekk u hekk. Għandna varjabbli lokali tagħna. Dritt issa i huwa ugwali għal 0, li aħna rridu li jkun. 

U hekk ejja iżommu titjib permezz. Minimu tagħna huwa ugwali għal 0, li aħna rridu wkoll li jkun. U allura aħna jidħol tieni tagħna għall loop, jekk array-j hija inqas minn firxa-i, li ma kienx. Allura ma inti tara kif li skipped fuq dan? 

UDJENZA: Allura jekk il-jekk minimu, kull that-- m'għandhomx li jkun ġewwa l-ewwel għall loop? ANDI Peng: Le, għaliex inti xorta tixtieq li jittestjaw. Inti tixtieq li tagħmel paragun kull time, anki wara li inti run permezz tiegħu. Inti ma jridux biss li tagħmel dan fl-ewwel through pass. Inti tixtieq li tagħmel dan ma kull pass addizzjonali mill-ġdid. Allura inti tixtieq li jiċċekkjaw għall kundizzjoni tiegħek ġewwa. Allura aħna qed biss ser jżomm taħdem permezz ta 'hawn. I ser jagħtuk guys ħjiel. Hija għandha tagħmel il-fatt li meta int iċċekkjar kondizzjonali tiegħek, int ma iċċekkjar għall-indiċi korretta. Allura issa dritt inti qed iċċekkjar għall indiċi firxa ta 'j hija inqas minn firxa indiċi ta 'i. Imma x'qed tagħmel up fil il-bidu tal-linja għall-? Mhumiex inti twaqqif j ugwali għal i? 

Yeah, sabiex inkunu nistgħu attwalment ħruġ tal-debugger hawn. Mela ejja tagħti ħarsa lejn pseudocode tagħna. For-- aħna qed tmur biex tibda fil i ikun egwali għal 0. Aħna ser jitla 'għal n minus 1. Ejja jivverifikaw, aħna ma dan id-dritt? Yep, dan kien dritt. 

Mela allura ġewwa hawnhekk, aħna qed se toħloq valur minimu u tistabbilixxi li ugwali għal i. Did nagħmlu dan? Yep, ma li. Issa fil ġewwa għall loop tagħna, aħna qed se tagħmel j ugwali i li n minus 1. Did nagħmlu dan? Tabilħaqq, għamilna dak. 

Allura madankollu, dak li aħna jitqabblu hawn? 

UDJENZA: j plus 1. ANDI Peng: Eżattament. U allura int tmur jridu jistabbilixxu minimu tiegħek ugwali għal j flimkien ma '1 ukoll. So I marru permezz li verament malajr. Do you guys jifhmu għaliex huwa j flimkien ma '1? KOLLOX SEW. 

Għalhekk fl array tiegħek, fil ewwel pass tiegħek permezz, tiegħek għall loop, għal int i ugwali 0, ejja biss jassumu din ma nbidilx s'issa. Għandna firxa ta ', kompletament, biss erba 'elementi mhux magħżula, id-dritt? Allura irridu li initialize i ugwali għal 0. U i se biss run permezz ta 'dan loop. U hekk fl-ewwel pass, aħna qed tmur initialize varjabbli imsejjaħ "min" li jkun daqs wkoll i, minħabba li aħna ma jkollhomx valur minimu. Allura dak li attwalment ugwali għal 0 ukoll. U allura aħna qed tmur biex jgħaddu. U rridu jtenni mill-ġdid. Issa li aħna ħadthom misjuba dak minimu tagħna huwa, irridu li jtenni permezz għal darb'oħra biex tara jekk huwa jqabbel, id-dritt? Allura j, hawnhekk, qed jiġri sabiex jaqbel i, li huwa ta '0. U mbagħad jekk firxa j plus i, li huwa dak li jmiss fuq, bħala inqas minn dak minimu attwali tiegħek valur huwa, inti tixtieq li tpartit. 

Mela ejja biss jgħidu konna ltqajna, bħal, 2, 5, 1, 8. Dritt issa, i huwa ugwali għal 0 u j hija ugwali għal 0. U li valur minimu tagħna. Jekk array-j plus i-- hekk jekk dik dan huwa wara dik aħna qed tħares lejn huwa akbar minn dak quddiemha, li għaddej biex isir il-minimu. 

Allura hawn naraw li 5 ma jkunx inqas minn dak. Allura li għaddej biex ma jkun 5. Naraw li 1 huwa inqas minn 2, id-dritt? Allura issa nafu dak il-minimu tagħna huwa se jkun il-valur indiċi ta '0, 1, 2. Yeah? U allura meta inti tikseb l isfel hawn, inti tista 'tpartit l-valuri korretti. 

Allura meta inti guys kienu biss li jkollhom l-j qabel, inti ma kinux tħares lejn l-wieħed wara dan. You kienu qed ifittxu fil l-istess valur, li hu għaliex biss ma kien isir xejn. Does li jagħmel sens għal kulħadd, għaliex għandna bżonn li flimkien ma '1 hemm? KOLLOX SEW. Issa ejja biss run permezz ta 'dan li tagħmel żgur li l-bqija tal-kodiċi hija korretta. Għaliex huwa li jiġri? Ah, huwa l-min dritt hawn. Konna tqabbel il-valur ħażina. Oh no. 

Oh yeah, stabbiliti hawn konna iskambji il-valuri żbaljati kif ukoll. Għaliex aħna kienu qed ifittxu fil iu j. Dawk huma dawk konna verifika. Aħna fil-fatt tixtieq li tpartit l- minimu, il-minimu attwali, bi kwalunkwe barra wieħed hu. U kif inti guys tista 'tara l hawnhekk, għandna firxa issortjati. Hija biss kellhom x'jaqsmu ma ' il-fatt li meta konna iċċekkjar tal- Valuri konna tqabbil, ma konniex tħares lejn il-valuri dritt. Aħna kienu qed ifittxu fl-istess wieħed hawn, ma attwalment jagħmlu skambju dan. Inti għandek tfittex fil dak li jmiss lilha u allura inti tista 'tpartit. Allura dak hu li kien tip ta ' bugging kodiċi tagħna qabel. U dak li għamilt hawn huwa kollox l debugger seta 'jsir għalik I biss ma kien fuq il- bord, għaliex dan huwa aktar faċli biex tara iktar milli jipprova li zoom fl fuq il-debugger. Does li jagħmel sens għal kulħadd? Kessaħ. 

Kull dritt. Aħna tista 'timxi fuq jitkellem dwar notazzjoni asintotiku, li huwa biss mod fancy ta 'tgħid l- runtimes kollha ta 'dawn it-tipi. So I know David, fil lecture, ssemma runtimes. U qal li permezz tal-formula kollu ta 'kif jiġu kkalkulati l-runtimes. Ebda inkwiet dwar dik. Jekk int verament kurjuż fuq kif din taħdem, tħossok liberu li tkellem lili wara taqsima. Nistgħu jimxu permezz l-formuli flimkien. Iżda kollha inti guys għandek verament tkun taf li n kwadrat fuq 2 huwa l-istess ħaġa bħat n kwadrat. Minħabba li l-akbar numru, l-esponent, tikber l-aktar. U hekk għall-għanijiet tagħna, kollha we care about huwa dak in-numru ġgant li dejjem tikber. 

Allura x'inhi l-aħjar każ runtime ta sort għażla? Jekk int ser ikollhom li jtenni permezz ta 'lista u mbagħad jtenni permezz il-bqija ta 'dik il-lista, kif ħafna drabi huma inti ser probabbilment, fl-agħar case-- fil- aħjar każ, sorry-- jgħaddi? Forsi l-kwistjoni aħjar hija li jistaqsu, dak li huwa l-agħar każ runtime tal sort għażla. UDJENZA: n kwadrat. ANDI Peng: Huwa n kwadrat, id-dritt. Allura mod faċli biex jaħsbu ta 'dan huwa simili, kwalunkwe ħin għandek żewġ nested għal-linji, li għaddej biex jiġu n kwadrat. Minħabba li mhux biss huma inti taħdem permezz darb'oħra, ikollok tmur lura madwar u run permezz tiegħu għal darb'oħra ġewwa għal kull valur. Allura f'dak il-każ, int taħdem n drabi n kwadrat, li is-- sorry, n drabi n, li jkun ugwali għal n kwadrat. 

U sort hija wkoll daqsxejn uniku fis-sens li ma jimpurtax jekk dawn Valuri huma diġà fl-ordni. Huwa għadu għaddej biex jgħaddi mill anyways. Ejja ngħidu biss dan kien 1, 2, 3, 4. Irrispettivament ta 'jekk jew le li kien fl ordni, xorta kien dam permezz u xorta ċċekkjati l-valur minimu. Huwa kien jagħmel dan l- istess numru ta 'kontrolli kull darba waħda, anki jekk ma attwalment tmissx xejn. 

Allura f'dan il-każ, l-aħjar u l-agħar runtimes huma attwalment ekwivalenti. Allura l-runtime mistenni tal sort għażla, li aħna jinnomina bis-simbolu tal theta, theta, f'dan il-każ, ikun ukoll kwadrat n. It-tlieta minn dawn ikunu kwadrat n. Hija kulħadd ċara dwar għaliex l-runtime huwa n kwadrat? 

Kull dritt. Hekk jien biss se malajr jimxu permezz tal-bqija tal-tipi. L-algoritmu għall bubble sort-- ftakar, din kienet l-ewwel waħda David marru fuq fil lecture. Essenzjalment, inti pass permezz tal-lista sħiħa u inti swap-- inti biss tqabbel tnejn fi żmien. U jekk wieħed huwa akbar, milli inti biss tpartit lilhom. Mela jekk dawn huma akbar, inti tpartit. Stajt ltqajna uffiċjali dritt hawn. 

Mela ejja biss jgħidu kellek 8, 6, 4, 2. Youd tqabbel 8 u 6. Youd bżonn li tpartit lilhom. Inti ser jipparaguna t 8 u 4. Youd bżonn li tpartit lilhom. Jekk għandek tpartit l-8 u 2, il-bidla lilhom ukoll. Dan b'tali sens, tistgħu taraw, ssirx fuq perjodu twil ta 'żmien, kif il-tip valuri ta buzzieqa sabiex -truf, li huwa għalhekk jissejjaħ sort bużżieqa. 

Nixtiequ biss run permezz darb'oħra fuq tieni pass tagħna, u t-tielet pass tagħna, u r-raba pass tagħna. Essenzjalment, bubble sort biss runs sakemm inti ma tagħmel xi swaps aktar. Allura f'dan is-sens, din hija biss l pseudocode ġenerali għal dan. Nru inkwiet, dawn kollha se jkunu online. Aħna ma jkollhom biex effettivament jmorru fuq dan. 

Aħna biss initialize kontro varjabbli li jibda b'0. U aħna jtenni permezz tal-firxa sħiħa. U jekk il-valur wieħed is-- jekk dan valur huwa aktar minn dak il-valur, int ser tpartit lilhom. U allura int biss ser jibqgħu għaddejjin. U int ser jingħaddu. U int biss ser iżommu tagħmel dan filwaqt li l-counter huwa akbar minn 0, li jfisser li kull darba li inti għandek tpartit, inti taf li inti tixtieq li tmur lura u erġa 'ċċekkja. Inti tixtieq li żżomm kontroll sakemm tkun taf li inti ma għandekx tpartit aktar. 

Allura x'inhuma l-aħjar u l-agħar każ runtimes għall tip bużżieqa? U dan hint-- huwa tabilħaqq differenti minn sort għażla fis-sens li dawn iż-żewġ tweġibiet mhumiex l-istess. Aħseb dwar dak li jiġri fil każ jekk kien diġà magħżula. U jaħsbu dwar dak jiġri jekk kien fil-każ fejn ma kienx magħżula. U inti tista 'tip ta' run permezz għaliex dan qed jiġri. I ser jagħtuk guys, bħal, 30 sekondi biex jaħsbu dwar dan. 

KOLLOX SEW. Ħadd ma jkollu raden lejn dak l- runtime agħar każ ta 'tip bużżieqa huwa? Yeah. 

UDJENZA: Ikun, bħal, n ħinijiet n minus 1 jew xi ħaġa bħal dik? Bħal, kull darba li tmur, huwa biss, bħal, tpartit waħda inqas li kwalunkwe kien. 

ANDI Peng: Yeah, hekk int totalment id-dritt. U dan huwa każ fejn tiegħek risposta kienet fil-fatt aktar kumplessi minn dak għandna nagħtu. Allura li għaddej biex run-- jien ser iħassar dan kollu hawn. Huwa kulħadd tajba? Nista iħassar din? KOLLOX SEW. Inti qed tmur biex jgħaddi mill n drabi l-ewwel darba, id-dritt? U dawn qed tmur biex jgħaddi mill n nieqes 1 it-tieni darba, id-dritt? U allura int ser iżommu tmur, minjiera n 2, eċċetera. David għamlet, lecture, fejn, jekk inti miżjud up dawk il-valuri kollha, ikollok xi ħaġa li like-- yeah-- aktar minn 2, li essenzjalment biss inaqqas isfel sa n kwadrat. Inti qed tmur biex tikseb frazzjoni stramb fil hemmhekk. U hekk biss jafu li il n kwadrat dejjem tieħu preċedenza fuq il-frazzjoni. U hekk f'dan il-każ, l-agħar runtime tkun kwadrat n. Jekk kien fl-inżul ordni, think, inti għandek tagħmel swap kull wieħed ħin. 

Liema jkun, potenzjalment, il-każ runtime aħjar? Ejja ngħidu biss, jekk il-lista kienet diġà sabiex, dak li l-runtime jkun? 

UDJENZA: n. ANDI Peng: Huwa n, eżattament. U għaliex hi n? UDJENZA: Għaliex inti biss għandhom jiċċekkjaw fuq kull darba. ANDI Peng: Eżattament. Allura fl-aħjar runtime possibbli, jekk din il-lista kienet diġà sorted-- ejja ngħidu 1, 2, 3, 4-- inti kien biss jgħaddu, inti jivverifikaw, inti tara, oh, dawn kollha pan out. I ma kellhomx tpartit. Jien jsir. Allura f'dak il-każ, huwa biss n jew in-numru ta 'passi li inti biss kellha tivverifika fl-ewwel lista. 

U wara, aħna issa hit sort inserzjoni, fejn l-algoritmu huwa essenzjalment li firda fis porzjon magħżula u mhux magħżula. U mbagħad wieħed wieħed, il-valuri mhux magħżul huma mdaħħla fil xierqa tagħhom pożizzjonijiet fil-bidu tal-lista. 

Hekk per eżempju, għandna Lista ta '3, 5, 2, 6, 4 darb'oħra. Aħna nafu li bħalissa huwa mhux magħżul għaliex aħna ħadthom biss beda tħares lejn dan. Aħna tagħti ħarsa u aħna nafu li l-ewwel valur huwa magħżul, right? Jekk int biss tħares lejn firxa ta ' daqs wieħed, inti taf li huwa magħżula. 

Mela allura aħna nafu li l- oħra erba huma mhux magħżul. Aħna jgħaddu u naraw dak il-valur. Ejja ħa mmorru lura. Ara li l-valur tal-5? Aħna tagħti ħarsa lejn dan. Inqabblu sa 3. Aħna nafu li huwa akbar minn 3, hekk aħna nafu li thats magħżula. Allura aħna issa jkunu jafu li l-ewwel tnejn huma magħżula u l-aħħar tlieta mhumiex. 

Aħna tagħti ħarsa lejn 2. Aħna l-ewwel iċċekkja ma '5. Huwa inqas minn 5? Mhuwiex. Allura aħna għandna biex iżommu tfittex stabbiliti. Imbagħad inti tiċċekkja 2 off 3. Huwa inqas minn? No Allura inti taf 2 għandu jiġi inserit fil-faċċata u 3 u 5 tnejn iridu imbuttata 'l barra. Tagħmel dan għal darb'oħra bl 6 u 4. U aħna biss iżommu kontroll essenzjalment, fejn aħna biss jiċċekkjaw, check, check. U sakemm ikun fid-dritt pożizzjoni, aħna tip ta 'ftit daħħalha fil-pożizzjoni dritt, li huwa fejn l-isem ta 'dan ġew minn. 

Allura dan huwa biss l-algoritmu, pseudocode per se, tip ta ', dwar kif aħna se jimplimentaw l sort inserzjoni. Pseudocode huwa hawnhekk. Dan kollu online. Nru inkwiet jekk inti guys huma jippruvaw kopja din stabbiliti. Għalhekk għal darb'oħra, l-istess question-- dak ikun l-aħjar u runtimes agħar għall tip inserzjoni? Dan huwa simili ħafna għall-aħħar mistoqsija. I ser jagħtuk guys, bħal, 30 sekondi biex jaħsbu dwar dan ukoll. 

OK Hawn xi ħadd li tixtieq li agħtini l-agħar runtime? Yeah. 

UDJENZA: n kwadrat. 

ANDI Peng: Huwa n kwadrat. U għaliex hi n kwadrat? 

UDJENZA: Minħabba fid ordni invers, inti għandek li jmorru permezz ta 'ħinijiet n n, li is-- ANDI Peng: Yeah, eżattament. Allura istess ħaġa bħal fil-tip bużżieqa. Jekk din il-lista fil f'ordni dixxendenti, int ser ikollhom jiċċekkjaw ewwel darba. U mbagħad ma 'kull valur addizzjonali, int ser ikollhom jiċċekkjaw kontra kull valur wieħed, id-dritt? U għalhekk għal kollox, int ser tagħmel AN n jgħaddu żminijiet oħra n jgħaddu, li huwa n kwadrat. Xi ngħidu dwar l-aħjar każ? Yeah. 

UDJENZA: n minus 1, minħabba li l- ewwel wieħed huwa diġà kwadrat. 

ANDI Peng: Allura, qrib. It-tweġiba hija attwalment n. Għaliex filwaqt li l-ewwel waħda hija magħżula, ma jistax actually-- dan aħna biss lucked out, fil li eżempju, li 2 ġara li jkun l-iżgħar numru. Iżda dan mhux dejjem ikun il-każ. Jekk 2 hu diġà magħżula fil-bidu imma inti tfittex u hemm 1 hawn, 1 se bump. U li għaddej biex tintemm jiddiżappuntaw ttellgħux anyways. 

Allura fil-aħjar xenarju, huwa attwalment biss se tkun n. Jekk għandek 1, 2, 3, 4, 5, 6, 7, 8, int ser tgħaddi minn ġos dik il-lista sħiħa darba biex tikkontrolla biex tara jekk multa kollox ta. Hija kulħadd ċar fuq tmexxija żminijiet ta 'għażla kif ukoll? I know jien ser permezz dawn verament mgħaġġel. Iżda biss jafu li jekk inti taf l- kunċetti ġenerali, inti għandek tkun tajba. KOLLOX SEW. So I ser biss jagħtuk guys forsi, bħal, minuta biex jitkellmu lill-ġirien tiegħek dwar liema huma biss ftit tad-differenzi ewlenija bejn dawn it-tipi ta 'tipi. Aħna ser jmorru fuq li dalwaqt. UDJENZA: Oh, OK. ANDI Peng: Yeah. KOLLOX SEW. Kessaħ, ejja jerġgħu jiltaqgħu bħala klassi. KOLLOX SEW. Allura dan kien tip ta ' kwistjoni open-ended fis-sens li hemm lottijiet ta 'tweġibiet għalihom. U aħna ser jmorru fuq xi wħud minnhom fil-qosor. I biss riedu li inti tikseb guys jaħsbu dwar dak differenzjati tliet tipi ta 'tipi. U smajt, ukoll, a kbira question-- dak ma jingħaqdu sort do? Kwistjoni kbira, minħabba li l dak li aħna qed jkopru jmiss. 

Allura jingħaqdu sort huwa l- sort waħda li l-funzjonijiet b'mod differenti ħafna mill-tipi oħra. Kif inti guys tista see-- ma David tagħmel dan demo fejn kellu l-jibred ħsejjes ta 'jara kemm jingħaqdu sort dam, bħal, infinitament aktar mgħaġġla mill-żewġ tipi l-oħra? KOLLOX SEW. Allura dan għaliex jingħaqdu sort timplimenta dik firda u jirbħu kunċett li konna tkellem dwar ħafna fil lecture. F'dan is-sens li aħna nixtiequ li jaħdmu aktar intelliġenti, mhux aktar diffiċli, meta inti jaqsam u jirbħu problemi, u taqsamhom isfel, u mbagħad jpoġġuhom flimkien, affarijiet tajbin dejjem iseħħ. 

Allura l-mod li jingħaqdu sort essenzjalment xogħlijiet huwa li hija taqsam l firxa mhux magħżul min-nofs. U allura huwa ltqajna żewġ nofsijiet ta 'arrays. U hija biss xorta dawn iż-żewġ nofsijiet. Hija biss iżomm diviż fil nofs, fil nofs, nofs sakemm kollox huwa magħżul u mbagħad recursively tqiegħdu kollha flimkien. 

Allura li tassew astratt. Allura dan huwa biss daqsxejn ta 'pseudocode. Does li jagħmel sens fil il-mod huwa taħdem? Mela ejja biss jgħidu għandek firxa ta 'elementi n, right? Jekk n huwa inqas minn 2, inti tista 'ritorn. Għaliex inti taf li jekk hemm unika ħaġa waħda, għandu jiġi magħżula. Inkella, inti sort l-nofs tax-xellug, u allura inti sort l-nofs tal-lemin, u allura inti jingħaqdu. 

Għalhekk, filwaqt li li jistenna verament faċli, fir-realtà, il-ħsieb dwar huwa tip ta 'diffiċli. Għax int simili, Ukoll, li tip ta 'tmexxija fuqha nfisha. Dritt? Huwa taħdem fuq innifsu. Allura f'dan is-sens, David mimsus fuq recursion fil-klassi. U li l-kunċett aħna ser nitkellmu dwar aktar. Huwa li dan, dawn iż-żewġ linji hawn, fil-fatt huwa biss il-programm javżak li jimxu ruħha b'kontribut differenti. Allura minflok jimxu ruħha ma -totalità tal-elementi N, inti tista 'tinqasam il- nofs tax-xellug u l-nofs tal-lemin u mbagħad run mill-ġdid. 

U allura aħna ser tħares lejn din viżwalment, għaliex jien qed jitgħallem viżwali. Hija taħdem aħjar għalija. Allura aħna ser tħares lejn eżempju viżwali hawn. 

Ejja ngħidu li għandna firxa, sitt elementi, 3, 5, 2, 6, 4, 1, ma jintgħażlux. Kull dritt, hemm ħafna fuq din il-paġna. Mela jekk inti guys tista 'tħares lejn il- ewwel pass hawn, 3, 5, 2, 6, 4, 1, inti tista 'tinqasam min-nofs. Inti għandek 3, 5, 2, 6, 4, 1. Inti taf li dawn aren't-- inti ma nafx jekk dawn qed magħżula jew le, sabiex inti żżomm jitkissru them down, fil nofs, fil nofs, nofs, sakemm eventwalment, inti biss għandek element wieħed. U element wieħed hija dejjem magħżula, id-dritt? 

Allura aħna nafu li 3, 5, 2, 4, 6, 1, waħedhom, huma magħżula. U issa nistgħu jqiegħduhom lura flimkien. Allura nafu 3, 5. Npoġġux dawk flimkien. Nafu li l-Issortjat. Tal-2 għadha hemm. Nistgħu npoġġu 4 u 6 flimkien. Aħna nafu li li l-magħżula, hekk aħna li jitqiegħdu flimkien. U l-1 hemm. 

U allura inti biss ħarsa lejn dawn iż-żewġ nofsijiet dritt hawn. Inti għandek l-3, 5, 2, 2, 3, 5. Tista 'biss tqabbel l bidu ta 'kollox. Għaliex inti taf li dan huwa magħżul u inti taf li li l-magħżula. Mela allura inti ma jkollhomx biex jqabblu l-5, inti biss tqabbel 3. U l-2 ikun anqas minn 3, so inti taf 2 trid tmur fl-aħħar. 

L-istess ħaġa hemmhekk. 1 trid tmur hawn. U allura meta inti tmur biex tpoġġi dawn iż-żewġ valuri flimkien, inti taf li dan huwa magħżul u inti taf li dan huwa magħżul. Mela allura l-1 u l- 2, 1 huwa inqas minn 2. Li jgħidlek li l-1 għandhom imorru fuq l-aħħar ta 'din mingħajr ma tħares lejn 3 jew 5. U allura l-4, inti tista 'sempliċement jivverifikaw, din tmur dritt fil hawn. Inti ma għandekx li tħares lejn l-5. Istess ħaġa ma 'l-6. Inti taf li l-6-- hija biss ma teħtieġx li jiġu eżaminati. 

U hekk b'dan il-mod, int biss iffrankar yourself ħafna passi meta int jqabbel. Inti ma għandekx biex iqabblu kull element kontra elementi oħra. Inti biss qabbel kontra dawk li għandek bżonn biex tqabbel kontra. Allura dak it-tip ta 'kunċett astratt. Nru inkwiet jekk mhuwiex pjuttost laqtu inti għadhom dritt. Iżda ġeneralment, dan huwa kif sort jingħaqdu xogħlijiet. Mistoqsijiet, mistoqsijiet malajr, qabel I jimxu fuq? Yeah. 

UDJENZA: Allura inti qal li inti tieħu 1, u allura l-4, u 6 u tpoġġihom fil. Allura mhumiex those-- mhumiex inti tħares lejn lilhom bħala elementi separati, mhux bħala entità sħiħa? ANDI Peng: Yeah. Allura dak li qed jiġri hija li inti bażikament qed joħolqu marka firxa ġdida. Allura inti taf li, hawnhekk, I jkollhom żewġ arrays ta 'daqs 3, id-dritt? Allura inti taf li firxa Issortjat tiegħi jeħtieġ li jkollu sitt elementi. Allura inti biss toħloq ammont ġdid ta 'memorja. Allura int it-tip ta 'prodotti simili tkun ħela ta 'memorja, iżda li ma jimpurtax għaliex dan huwa tant żgħar. Allura inti tħares lejn l-1 u inti tħares lejn l-2. U inti taf li l-1 huwa inqas minn 2. Allura inti taf li 1 għandha tmur fil il-bidu ta 'dawk kollha. 

Inti ma anki ħtieġa li tħares lejn il-3 u l-5. Allura inti taf 1 imur hemmhekk. Imbagħad inti bażikament CHOP off 1. Huwa, bħal, mejta lilna. Imbagħad aħna biss għandhom 2, 3, 5, u mbagħad 4 u 6. U allura inti taf dan, inti jqabblu l-4 u l-2, oh, 2 għandhom imorru fil hemmhekk. Allura inti plop 2 isfel, inti CHOP off. Mela allura inti biss għandek 3 u l-5 fil-4 u 6. U inti biss iżommu tqattiegħ off sakemm inti tpoġġihom fil-firxa. 

UDJENZA: Allura int biss dejjem jitqabblu l-[inaudible]? 

ANDI Peng: Eżattament. Allura f'dan is-sens, int biss jqabbel, essenzjalment, numru wieħed ħdejn in-numru ieħor. U għaliex inti taf li huwa magħżula, inti ma jkollha tħares permezz kollha tan-numri. Inti sempliċiment għandek tfittex fl-ewwel wieħed. U allura inti tista 'sempliċement plop them down, għaliex inti taf jappartjenu fejn huma meħtieġa li jappartjenu. Yeah. Tajba kwistjoni. 

U mbagħad jekk kwalunkwe inti huma daqsxejn ambizzjuż, tħossok liberu li tħares lejn dan il-kodiċi. Dan huwa effettivament il- implimentazzjoni fiżika ta 'kif aħna se jikteb tip jingħaqdu. U tista 'tara, huwa qasir ħafna. Iżda l-ideat wara dan huma pjuttost kumplessi. Mela jekk inti tħoss bħal tpinġija dan out fil tonight dar tiegħek, tħossok liberu li. 

KOLLOX SEW. Allura David marru wkoll fuq dan lecture. Liema huma l-aħjar każ runtimes, runtimes agħar każ, u l-runtimes mistennija ta 'tip jingħaqdu? A ftit sekondi biex jaħsbu. Dan huwa pjuttost diffiċli, iżda tip ta ' intuwittivi jekk inti taħseb dwarha. Kull dritt. 

UDJENZA: Huwa l-agħar każ n log n? ANDI Peng: Eżattament. U għaliex hi n log n. 

UDJENZA: Hux minħabba li isir b'mod esponenzjali aktar mgħaġġla, hekk huwa simili funzjoni ta 'dan minflok sempliċiment sempliċiment n kwadrat jew xi ħaġa? ANDI Peng: Eżattament. Allura r-raġuni għaliex il- runtime fuq dan huwa log n n huwa because-- dak li huma inti tagħmel kollha ta 'dawn il-passi? Int biss tqattiegħ min-nofs, id-dritt? U hekk meta aħna qed tagħmel l- log, dak kollu li huwa qed jagħmel huwa diviż problema fil nofs, fil nofs, nofs, f'iktar nofsijiet. U f'dan is-sens, inti tista tip tal telimina l-mudell lineari li aħna kont qed tuża. Għaliex meta inti CHOP affarijiet fil nofs, huwa log. Li jinsab biss l-matematika mod ta 'jirrappreżentawha. 

U mbagħad finalment, fl-aħħar, int biss għamel wieħed jgħaddi l-aħħar permezz li jpoġġu kollha kemm huma fl-ordni, id-dritt? U hekk jekk inti biss għandek biex check ħaġa waħda, li l-n. U hekk int tip ta ' multiplikazzjoni it-tnejn flimkien. Allura huwa simili inti stajt qbilna li finali jikkontrolla għal n stabbiliti hawn ma 'log ta n up here. U jekk inti immoltiplika minnhom, li l-log n n. 

U għalhekk l-aħjar u l-agħar każ każ u mistennija huma kollha n log n. Huwa wkoll bħal tip ieħor. Huwa simili sort għażla fis-sens li Ma jimpurtax f'liema tiegħek lista hija, huwa biss se jagħmlu l-istess ħaġa kull wieħed ħin. KOLLOX SEW. Allura kif inti guys tista 'tara, anki jekk t-tipi li konna marret through-- n kwadrat, mhuwiex effiċjenti ħafna. U anke dan log n n hija mhux l-aktar effiċjenti. Jekk inti guys huma kurjużi, hemm mekkaniżmi sort li huma daqshekk effiċjenti li dawn qed kważi essenzjalment ċatti fil runtime. 

You ħadthom ltqajna xi log n s. You ħadthom ltqajna xi log log n s. Aħna ma tmissx fuqhom f'din il-klassi dritt issa. Imma jekk inti guys huma kurjużi, tħossok liberu li google, x'hemm l-aktar mekkaniżmi effiċjenti issortjar. I do not know, hemm xi wħud verament umoristiċi, like-- hemm xi verament dawk umoristiċi li n-nies jagħmlu. U inti wonder kif dawn Qatt ħsibt ta 'dak. Allura google, jekk għandek xi spare ħin, fuq, liema huma xi modi umoristiċi li people-- kif ukoll nies ways-- effiċjenti kienu kapaċi jimplimentaw xorta. KOLLOX SEW. U hawnhekk biss chart ftit handy. Naf lilkom kollha, qabel dik kwizz 0, se jkun fil-kamra tiegħek probabbilment jippruvaw li jimmemorizza dan. Allura dak sbieħ fil hemm għalik guys. Biss ma ninsewx il-loġika li made-- għaliex dawn in-numri ġew sseħħ. Jekk inti qed dejjem mitlufa, biss tagħmel żgur li int taf liema l-xorta huma. U inti tista 'taħdem permezz fil-memorja tiegħek biex insemmu għaliex dawk tweġibiet huma dawn ir-risposti. 

Kull dritt. Allura aħna qed tmur biex jimxu fuq, finalment, li tiftix. Għaliex kif dawk minnkom li qrajt l-pset, tiftix huwa wkoll parti mill problema din il-ġimgħa settijiet. Int ser tintalab biex jimplimentaw żewġ tipi ta 'tfittxijiet. Wieħed huwa tfittxija lineari u waħda hija tfittxija binarja. 

Allura l-tfittxija lineari huwa pjuttost faċli. Inti biss trid tfittex element ta 'lista biex tara jekk inti ġġibu. Inti sempliċiment għandek jtenni permezz. U jekk tkun ugwali xi ħaġa, inti tista 'sempliċement tibagħtu lura, id-dritt? Iżda l-waħda li aħna qed aktar interessati fil jitkellem dwar huwa tiftix binarju, id-dritt, li hija l- jaqsam u jirbħu mekkaniżmu li David kien juri fil lecture. 

Ftakar l-eżempju ktieb tat-telefon li jżomm irabbu, il-wieħed li huwa tip ta 'tħabtu daqsxejn fuq din is-sena passat, fejn inti jaqsam il-problema fil nofs, fil nofs, fil nofs, għal darb'oħra u għal darb'oħra, sakemm issib dak li qed tfittex? U inti stajt ltqajna l- runtime ta 'dak ukoll. U tista 'tara, huwa sinifikament aktar effiċjenti minn kwalunkwe tip ieħor ta 'tfittxija. 

Allura l-mod li aħna tmur dwar implimentazzjoni ta 'tfittxija binarja huwa, jekk kellna firxa, indiċi minn 0 sa 6, seba 'elementi, nistgħu nħarsu fin-nofs, right-- sorry, jekk kwistjoni tagħna first-- jekk irridu li titlob il-kwistjoni tal-ma l-array fihom l-element ta '7, ovvjament, li l-bnedmin, u li bħal firxa żgħira, huwa faċli għalina ngħid iva. Iżda l-mod biex jimplimentaw binarju tfittxija tkun li tħares fin-nofs. 

Aħna nafu li l-indiċi 3 huwa il-grawnd, għaliex aħna jafu hemm seba elementi. What 7 diviż bi 2? Tista 'CHOP off li extra 1. You ħadthom ltqajna 3 fin-nofs. Allura huwa firxa ta '3 ugwali għal 7? Mhuwiex, id-dritt? Iżda nistgħu nagħmlu ftit kontrolli. Huwa firxa ta '3 anqas minn 7 jew huwa firxa ta '3 ikbar minn 7? 

U nafu li huwa inqas minn 7. Allura aħna nafu li, oh, hija għandha Ma jkun fin-nofs tax-xellug. Aħna nafu li għandu jkun fil-nofs tal-lemin, right? Allura nistgħu biss CHOP off nofs l-firxa. Aħna ma jkollhomx biex tħares lejn din jibqgħalu. Għaliex aħna nafu li nofs ta 'problem-- tagħna nafu li r-risposta hija fl in-nofs lemini tal-problema tagħna. Allura aħna biss ħarsa lejn dak issa. 

Allura issa nħarsu lejn l- nofs ta 'dak ix-xellug. L-indiċi 5. Nagħmlu l-istess kontroll mill-ġdid u naraw li huwa iżgħar. Allura aħna nħarsu lejn ix-xellug ta 'dik. U allura naraw li check. Huwa l-valur array fil indiċi 4 daqs 7? Huwa. Allura nistgħu ritorn veru, għaliex sibna l-valur fil-lista tagħna. Il-mod I marru permezz li jagħmel sens għal kulħadd? KOLLOX SEW. I ser jagħtuk guys forsi, bħal, tliet, erba 'minuti biex insemmu kif pseudocode dan. 

Allura immaġina I talab li inti jiktbu funzjoni msejħa optimization () li lura valur, valur Boolean, li kien veru jew false-- simili, veru jekk inti sabu l- valur, falza jekk inti ma. U allura inti kienu għadda fil-valur inti kienu qed ifittxu fil-valuri, li huwa l-array-- oh, I definitely tpoġġi li fil-post żbaljat. KOLLOX SEW. Anyways, li għandu jkollhom Kien għad-dritt ta 'valuri. U mbagħad int n huwa n-numru ta 'elementi fil dak array. Kif inti tmur dwar jippruvaw li pseudocode din il-problema fil-? I ser jagħtuk guys simili tliet minuti sabiex tagħmel dan. Le, I think hemm only-- yeah, hemm dritt wieħed up here. UDJENZA: Nista? ANDI Peng: Yeah, I ltqajna inti. Hija li xogħol? OK, berred. 

KOLLOX SEW. Guys dritt kollha, aħna qed se jitrażżan fil. KOLLOX SEW. Allura jassumi konna ltqajna dan sabiħ ftit array b'valuri n fiha. I ma tiġbed il-linji. Imma kif se immorru dwar tipprova tikteb dan? Hawn xi ħadd li tixtieq li agħtini l-ewwel linja? Jekk inti tixtieq li tagħti me l- ewwel linja ta 'dan pseudocode. 

UDJENZA: [inaudible] UDJENZA: Youd tixtieq li jtenni through-- UDJENZA: Just ieħor għal loop? UDJENZA: --for. 

ANDI Peng: Allura dan wieħed daqsxejn delikata. Aħseb about-- inti tixtieq li jżomm taħdem din loop fuq u aktar mill-ġdid sakemm meta? 

UDJENZA: Sakemm il-[inaudible] valur huwa ugwali għal dak il-valur. ANDI Peng: Eżattament. Allura inti tista 'attwalment biss write-- nistgħu saħansitra jissimplifika aktar. Nistgħu biss tagħmel loop waqt, id-dritt? Allura inti tista 'biss għandek loop-- nafu li huwa ftit żmien. Iżda għal issa dritt, jien ser li jgħidu "loop" - permezz ta 'dak? Loop until-- dak li hu kundizzjoni li jispiċċa tagħna? I think I smajt dan. Smajt xi ħadd jgħidu li din. 

Udjenza: Valuri ugwali nofs. ANDI Peng: Say mill-ġdid. UDJENZA: Or, sakemm il- valur int tiftix hija daqs il-valur tan-nofs. 

ANDI Peng: X'jiġri jekk mhuwiex fil hemmhekk? X'jiġri jekk il-valur int tiftix għal ma tkunx attwalment f'dan array? UDJENZA: Inti tirritorna 1. 

ANDI Peng: Imma dak li rridu loop sakemm jekk ikollna kundizzjoni? Yeah. 

UDJENZA: Sa hemm valur wieħed biss? ANDI Peng: Tista 'loop until-- sabiex inti taf li int se jkollhom valur max, right? U inti taf li int ser li jkollhom valur min, id-dritt? Minħabba wkoll, li xi ħaġa I nesa li ngħid qabel, li xi ħaġa li kritiku dwar tfittxija binarja hija li array tiegħek diġà magħżula. Minħabba li hemm ebda mod ta 'kif isir dan jekk dawn qed biss valuri każwali. Ma tafx jekk wieħed huwa akbar mill-oħra, id-dritt? 

Allura inti taf li max tiegħek u mins tiegħek hawn, id-dritt? Jekk int ser tkun aġġustament max tiegħek fil mins tiegħek u l-mid-- ejja biss wieħed jassumi tiegħek valur nofs huwa here-- dritt int ser bażikament loop sakemm minimu tiegħek huwa dwar l-istess bħal max tiegħek, id-dritt, jew jekk max tiegħek ma tkunx l-istess bħal min tiegħek. Dritt? Għaliex meta dan iseħħ, inti taf li inti stajt eventwalment laqat l-istess valur. Allura inti tixtieq li loop sakemm min tiegħek hija inqas minn jew ugwali to-- oops, mhux anqas minn jew ugwali għal, il-mod ieħor around-- max hu. 

Did li jagħmel sens? I ħa ftit tipprova tikseb dan id-dritt. Iżda loop sakemm il-valur max tiegħek huwa essenzjalment kważi inqas minn jew ugwali għal minimu tiegħek, id-dritt? Li meta inti taf li inti stajt konverġenti. UDJENZA: Meta se massimu tiegħek valur ikun anqas mill-minimu? ANDI Peng: Jekk inti żżomm jaġġustah, li huwa dak li aħna qed tmur li tkun qiegħda tagħmel f'dan. Does li jagħmel sens? Minimu u max huma biss interi li aħna probabbilment tmur jridu joħolqu biex iżommu kont ta 'fejn aħna qed tfittex. Minħabba teżisti l-array irrispettivament minn dak li qed isir. Bħal, aħna mhux qed attwalment fiżikament tqattiegħ off l-array, right? Aħna aġġustament biss fejn aħna qed tfittex. Does li jagħmel sens? 

UDJENZA: Yeah. 

ANDI Peng: OK. Allura jekk dan huwa l-kundizzjoni għall-loop tagħna, dak li rridu ġewwa ta 'dan loop? Liema huma aħna ser ikunu jridu jagħmlu? Allura issa dritt, konna ltqajna a max u min, id-dritt, probabbilment maħluqa up here x'imkien. Aħna qed tmur biex probabilment tixtieq biex isibu nofs, right? Kif aħna ser ikunu tista 'ssib l-nofs? X'hemm-mathematical-- UDJENZA: Max plus min diviż bi 2. ANDI Peng: Eżattament. Does li jagħmel sens? U ma inti guys jara għaliex aħna ma biss use-- għaliex għamilna dan minflok tagħmel biss n diviż bi 2? Huwa minħabba n huwa valur li għaddej biex tissospendi l-istess. Dritt? Imma kif aħna taġġusta minimu tagħna u Valuri massimi, dawn qed tmur għall-bidla. U bħala riżultat, tan-nofs tagħna huwa se jibdlu wisq. Allura hu għalhekk irridu tagħmel dan id-dritt hawn. KOLLOX SEW. 

U mbagħad, issa li aħna ħadthom misjuba our-- yeah. 

UDJENZA: Just a quick question-- meta inti tgħidli min u max, aħna wieħed jassumi li huwa diġà magħżula? 

ANDI Peng: Yeah, li attwalment prekondizzjoni għal tfittxija binarja, li inti għandek tkun taf huwa magħżula. Liema hu għaliex sort, tikteb fil tiegħek problema stabbiliti qabel tfittxija binarja tiegħek. KOLLOX SEW. Allura issa li nafu fejn punt tan-nofs tagħna huwa, dak li inti trid tagħmel hawn? 

UDJENZA: Aħna tixtieq li tqabbel li biex l-ieħor. ANDI Peng: Eżattament. Allura inti qed tmur biex iqabblu nofs sa valur, id-dritt? U dak li ma tgħid us meta nqabblu? What do rridu nagħmlu wara? 

UDJENZA: Jekk il-valur huwa akbar minn nofs is, irridu li jinqataw. ANDI Peng: Eżattament. Allura jekk il-valur huwa akbar minn nofs is, aħna qed tmur jridu jibdlu dawn maxes minimu u, right? What do irridu bidla? Mela jekk nafu il-valur huwa x'imkien fil hawn, dak li taħseb li aħna għall-bidla? Aħna tixtieq li tibdel tagħna minimu li jkun nofs, right? U mbagħad inkella, jekk huwa f'dan nofs, dak li rridu bidla? 

UDJENZA: massimu Your. ANDI Peng: Yeah. U allura int biss tmur li jżomm looping, right? Minħabba li issa, wara iterazzjoni waħda permezz, inti ħadthom ltqajna max hawn. U allura inti tista jerġa 'jkun ikkalkolat nofs. U allura inti tista 'tqabbel. U int ser jibqgħu għaddejjin sakemm il-minuti u l-maxes essenzjalment konverġenti. U li meta inti taf li inti ħadthom laqat il-aħħar ta 'dan. U jew inti ħadthom sabuha jew int ma f'dak il-punt. 

Does this jagħmel sens għal kulħadd? KOLLOX SEW. Dan huwa pjuttost importanti, għaliex inti ser ikollok li tikteb dan fil-kodiċi tonight tiegħek. Imma inti guys jkollhom pjuttost tajba sens ta 'dak li għandha tkun qiegħda tagħmel, li hija tajba. KOLLOX SEW. Allura konna ltqajna madwar seba ' minuti xellug taqsima. Allura aħna qed tmur biex jitkellmu dwar dan pset li aħna se tkun qed twettaq. Allura l-pset huwa maqsum f'żewġ nofsijiet. L-ewwel nofs jinvolvi implimentazzjoni isibu fejn tikteb tfittxija lineari, a tfittxija binarju, u algoritmu issortjar. 

Allura dan huwa l-ewwel darba fi pset fejn aħna ser tkun giving you guys dak li sejjaħ kodiċi ta 'distribuzzjoni, li huwa kodiċi li għandna pre-miktub, iżda biss ħalla xi biċċiet off għalik biex jintemm bil-miktub. Allura inti guys, meta inti tħares lejn din kodiċi, inti tista 'tikseb verament jibża. Jekk int biss tixtieq, Ahh, I ma nafx dak li qed jagħmel, I do not know, bħal, li jidher tant ikkumplikat, Ahh, jirrilassaw. Orrajt. Aqra l-spec. Il spec se tispjega li int eżattament liema kollha ta 'dawn il-programmi qed jagħmlu. 

Per eżempju, generate.c huwa programm li ser jiġi bl pset tiegħek. Inti ma attwalment ikollhom tmiss, iżda għandek tifhem dak li qed jagħmel. U generate.c, kull ma qed jagħmel huwa jew jiġġeneraw każwali numri jew tista 'tagħtiha żerriegħa, bħal Numru prestabbiliti li jieħu, u li jiġġenera numri aktar. Allura hemm mod speċifiku biex jimplimentaw generate.c li fihom inti tista 'biss tagħmel mazz ta' numri għalik biex jittestjaw metodi oħra tiegħek fuq. 

Mela jekk int riedu, għal eżempju, test tiegħek issib, inti tixtieq li run generate.c, jiġġeneraw mazz ta 'numri, u mbagħad għaddi helpers funzjoni tiegħek. Helpers Funzjoni huwa fejn int attwalment fiżikament miktub kodiċi. U think ta 'helpers bħala fajl librerija int bil-miktub li ssib qed jitlob. U dan fi żmien helpers.c, inti ser do tiftix u l-għażla. 

U allura int ser essenzjalment biss jpoġġuhom kollha flimkien. Il spec se jgħidulek kif għandek inti iqiegħed dak fuq il-linja tal-kmand. U inti ser tkun tista 'teżamina jekk jew mhux sort tiegħek u tfittxija qed jaħdmu. Kessaħ. Has ħadd diġà beda u problemi li ltaqgħu magħhom jew mistoqsijiet huma għandhom dritt issa ma 'dan? KOLLOX SEW. 

UDJENZA: Stenna. Għandi mistoqsija. 

ANDI Peng: Yeah. 

UDJENZA: So I bdiet tagħmel it-tfittxija lineari helpers.c u ma kienx verament jaħdem. Iżda mbagħad aktar tard, I sab aħna biss għandek iħassarha u tagħmel tfittxija binarja. Allura ma jimpurtax jekk din ma taħdimx? 

ANDI Peng: Tweġiba fil-qosor l-ebda. Iżda peress li aħna qed not-- UDJENZA: Imma l-ebda wieħed tal attwalment verifika. ANDI Peng: Aħna qatt ma ser tara li. Imma inti probabilment tixtieq li tagħmel żgur tfittxija tiegħek qed jaħdem. Għaliex jekk lineari tiegħek tfittxija ma jaħdimx, allura ċ-ċansijiet huma binarja tiegħek tfittxija mhuwiex sejjer jaħdem ukoll. Minħabba li għandek simili loġika fihom it-tnejn. U l-ebda, ma verament kwistjoni. Allura l-uniċi li inti ser idur fil huma sort u tfittxija binarja. Yeah. 

U wkoll, lott ta 'tfal kienu jippruvaw biex jikkompilaw helpers.c. Int mhux attwalment permessi li tagħmel dan, minħabba helpers.c ma jkollux funzjoni prinċipali. U allura inti għandek biss tkun fil-fatt kumpilazzjoni jiġġeneraw u jsibu, minħabba issib sejħiet helpers.c u l-funzjonijiet fi ħdan dan. Allura li jagħmel debugging uġigħ fl-butt. Imma dan huwa dak li għandna nagħmlu. UDJENZA: Inti biss tagħmel kollox, id-dritt? ANDI Peng: Inti tista 'sempliċement tagħmel id kif ukoll, yeah. KOLLOX SEW. Allura dak li f'termini ta 'dak l-pset huwa inti titlob kollha li tagħmel. Jekk għandek xi mistoqsijiet, tħossok liberu li jistaqsu lili wara taqsima. I ser tkun hawn għal, simili,-20 minuta. 

U yeah, l-pset ta verament mhux ħażin. You guys għandu jkun OK. Dawn, kemm issegwi linji gwida. Tip ta ikollhom sens ta ', loġikament, liema għandhom jiġu jiġri u tkun taf tkun multa. Ma jkun wisq jibża. Hemm ħafna ta 'kodiċi diġà bil-miktub hemmhekk. Ma jkun wisq jibża jekk inti ma jifhmu dak kollu ta 'dan ifisser. Jekk huwa ħafna, huwa totalment multa. U waslet għall ħinijiet tal-uffiċċju. Aħna ser jgħinek tagħti ħarsa. 

UDJENZA: Bl-extra funzjonijiet, do aħna nħarsu dawk up? 

ANDI Peng: Yeah, dawn huma fil-kodiċi. Fil-logħba ta '15, nofs il- huwa diġà bil-miktub għalik. Allura dawk il-funzjonijiet huma diġà fil-kodiċi. Yep. Kull dritt. Ukoll, l-isbaħ xewqat. Huwa kuljum disgusting. Hekk nisperaw li inti guys ma jħossux wisq bad dwar joqogħdu ġewwa u kodifika.