[Muzika] 

ANDI Peng: Mirë se vini në javën e 3 të seksionit. Thanks, ju djema, për të gjithë që vijnë në këtë kohë më parë të fillojë sot. Ne kemi marrë një e bukur, pak intime grup sot. Pra, shpresojmë se ne do të merrni për përfundojë, ndoshta, në fillim, pak më herët sot. Në mënyrë të shpejtë, vetëm disa njoftimet për rendin e ditës së sotme. Para se të fillojmë, ne jemi do të vetëm të shkuar mbi disa çështje shkurtër logjistike, pset pyetje, Debrief, gjëra të tilla si se. Dhe pastaj ne do të zhyten të drejtë në. Ne do të përdorim një Rregullues të quajtur Gdb të fillojnë hedhur poshtë kodin tonë, që Davidi shpjegohet në leksionin e të tjera ditore. Ne do të shkojnë mbi katër llojet e terezi. Ne do të shkoj për ta shumë shpejt pasi ata janë mjaft intensive. Por e di se të gjitha slides dhe Kodi burimor janë gjithmonë online. Pra mos ngurroni, në lexim tuaj, për të shkojnë prapa dhe të marrë një vështrim në atë. 

Ne do të kalojnë nëpër simbol asymptotic, e cila është vetëm një mënyrë e sofistikuar i thënë se "runtimes" ku ne kemi O madh, i cili David shpjegoi në leksion. Dhe ne gjithashtu kemi Omega, e cila është i detyruar Runtime të ulët. Dhe ne do të flasim pak më shumë në thellësi në lidhje me se si këto punë. Dhe në fund, ne do të shkojnë mbi kërkimin binar, sepse një shumë prej jush të cilët kanë tashmë lëshoi ​​në psets tuaj ndoshta e dini se kjo është një pyetje që është në pset tuaj. Pra, ju do të gjithë të jenë të lumtur që ne të mbuluar këtë sot. 

Dhe së fundi, për tuaj seksion reagime, unë në fakt lënë rreth 15 minuta në në fund të shkojnë vetëm mbi logjistika e pset3, ndonjë pyetje, ndoshta pak e udhëzimit, në qoftë se ju do të, para se të fillojmë programimin. Pra, le të përpiqen për të marrë me anë të materiali shumë shpejt. Dhe pastaj ne mund të kalojnë disa kohë duke marrë shumë pyetje për pset. NE RREGULL. 

Shpejt, kështu që vetëm disa Shpalljet e para se të fillojmë sot. Së pari, të mirëpritur për të bërë ajo përmes dy psets tuaj. Kam marrë një vështrim në your-- vërtet, le të marrë një raund të duartrokitje për këtë një të tillë. Në fakt, unë kam qenë me të vërtetë, impresionuar me të vërtetë. Unë vlerësohet pset parë për ju djema javë dhe ju djema e fundit bëri pabesueshme. 

Stil ishte në pikën përveç disa komente. Sigurohuni që ju jeni gjithmonë komentuar kodin tuaj. Por psets tuaja ishin në pikë. Dhe për të mbajtur atë lart. Dhe kjo është e mirë për grader në shihni se ju djema janë vënë në sa më shumë përpjekje në stilin tuaj dhe dizajni juaj në kodin tuaj që ne do të dëshironim për ju për të parë. Kështu që unë jam duke kaluar së bashku mirënjohjen time për pjesën tjetër të TAS. 

Megjithatë ka një Disa pyetje Debrief Unë vetëm dua të shkojë mbi atë do ta bënte edhe jetën time dhe shumë të tjera Tas 'jeton pak më e lehtë. Së pari, unë kam vënë re këtë e kaluara week-- sa prej jush kanë qenë në drejtimin check50 në Kodi tuaj para se të dorëzojnë? NE RREGULL. Kështu që të gjithë duhet të bëjnë check50, because-- një secret-- ne fakt drejtuar check50 si pjesë e saktësisë sonë Scripts për testimin kodin tuaj. Pra, në qoftë se kodi juaj është i dështuar check50, në të gjitha gjasat, kjo ndoshta do të dështojnë kontroll tonë si. Ndonjëherë ju djema kemi përgjigjet e duhura. Si, në babëzitur, disa prej ju keni numrat e duhur, ju vetëm të shtypura nga disa gjëra ekstra. Dhe kjo gjëra shtesë në fakt dështon kontrolloni, sepse kompjuteri nuk ka të vërtetë e di se çfarë është në kërkim për të. Dhe kështu ai thjesht do të kandidojë përmes, shihni se prodhimi juaj nuk ka përputhen me atë që ne presim përgjigje të jetë, dhe të shënojë atë është e gabuar. 

Dhe unë e di se ka ndodhur në disa prej rasteve tuaj këtë javë. Kështu që u ktheva dhe me dorë regraded kodin gjithëve. Në të ardhmen edhe pse, ju lutem, ju lutem sigurohuni që ju jeni duke shikoni 50 në kodin tuaj. Për shkak se ajo është lloj i një dhimbje për AT që të ketë për të shkuar mbrapa dhe me dorë regrade çdo pset vetme për çdo vetme, shembull i vogël humbi. Kështu që unë nuk heq asnjë pikë. Unë mendoj se unë u ngritën ndoshta një ose dy për dizajn. Në të ardhmen edhe pse, në qoftë se ju jeni dështuar check50, pikë do të merret off për korrektësinë. 

Për më tepër, psets janë për shkak premteve në mesditë. Unë mendoj se ka një-minuta shtatë Periudha e vonë hiri që ne të ju jap. Për kohën e Harvardit, ata janë të lejuar për të jetë shtatë minuta me vonesë për çdo gjë. Kështu që këtu në Yale, ne do të t'i përmbahen se si. Por shumë e shumë, në 12:07, nëse pset juaj nuk është në, ajo do të jetë e shënuar si vonë. Dhe kështu, ndërsa ajo është e shënuar si vonë, TA-- unë jam ende do të jenë të notimit psets tuaja. Pra, ju do të shihni ende një notë të shfaqet. Megjithatë, e di se në në fund të semestrit, Të gjitha psets vonë do të jetë vetëm zero automatikisht nga kompjuteri. 

Ne e bëjmë këtë për dy arsye. Një, ndonjëherë ne të merrni falur, si justifikime Dean, më vonë se unë nuk e di për akoma. Pra, ne si për t'u siguruar që ne jemi nota çdo gjë vetëm në rast, si, unë jam mungon një justifikim Dekanit. Dhe së dyti, të mbajtur në mendjen, ju prapë mund të bjerë një pset që ka pikë të plota fushëveprimi. Dhe kështu ne si të klasës së të gjitha psets tuaj vetëm për t'u siguruar që objekti suaj atje dhe ju jeni duke u përpjekur ato. Pra, edhe në qoftë se është vonë, ju do të ende të merrni kredi për pikë fushëveprimin, unë mendoj. 

Pra, morale e tregimit është, të bëjë i sigurt psets tuaja janë në në kohë. Dhe në qoftë se ata nuk janë në në kohë, e di se kjo nuk është e madhe. Po, para se të lëvizë, ka njeri të ketë ndonjë pyetje në lidhje me reagimet e pset? Po. 

Audienca: A ju thonë se ne mund të bjerë një nga psets? 

ANDI Peng: Po. Pra, ka nëntë psets përgjithshme gjatë semestrit. Dhe në qoftë se ju keni qëllimin points-- kështu Shtrirja është vetëm, shumë e shumë, po përpjekur Problemi, po vënë në kohë, po ju tregon se ju keni demonstruar keni lexuar spekulim. Kjo është shumë e shumë fushëveprimi. Dhe nëse ju jeni duke përmbushur Pikat fushëveprimi, ne mund të bjerë më të ulët një nga fushëveprimit të plotë. Pra, kjo është në avantazhin tuaj për të përfunduar dhe të përpiqemi çdo pset. 

Edhe upload-- qoftë se asnjë nga ato punë, ngarkoni atyre të gjithë. Dhe pastaj ne do të shpresojmë të jetë në gjendje për të ju jap disa nga këto pika prapa. Ftohtë. Ndonjë pyetje të tjera? I madh. 

Së dyti, zyra hours-- disa shënime të shpejtë rreth orarit të punës. Pra, së pari, të vijë në fillim të javës. Askush nuk është kurrë në orarit të punës të hënave. Christabel erdhi për orarit të punës natën e fundit. Po, Christabel. Dhe çfarë kemi në zyrën e orë mbrëmë, Christabel? 

Audienca: Ne kishim akullore. 

ANDI Peng: Pra, kjo është e drejtë, kemi pasur akullore në orarit të punës natën e fundit. Ndërsa unë nuk mund t'ju premtoj se ne do të kemi akullore në orarit të punës çdo javë, ajo që unë mund të ju premtojnë është se do të ketë një mënyrë të konsiderueshme Studenti më i mirë në raport AT. Si legit, kjo është si tre në një. Ndërsa, kontrast që me E enjte, ju keni marrë për 150 vërtet theksoi fëmijët dhe nuk akullore. Dhe kjo nuk është vetëm produktiv për të gjithë. Pra, morale e tregimit është, erdhi në fillim të orarit të punës dhe gjëra të mira do të ndodhë. 

Gjithashtu, vijnë të përgatitur për të bërë pyetje. Ti e di? Pavarësisht nga ajo që Tas, unë mendoj, kanë qenë duke thënë: ne kemi qenë duke marrë një çift nxënës që vijnë në të enjten në, si, 10:50 nuk ka lexuar spekulim duke qenë si më ndihmoni, më ndihmoni. Për fat të keq në atë pikë, nuk ka jo shumë mund të bëjmë për t'ju ndihmuar. Pra ju lutem të vijë në fillim të javës. Ejani në fillim të orarit të punës. Vijnë të përgatitur për të bërë pyetje. Sigurohuni që ju, si një student, ku janë duhet të jetë në mënyrë që Tas mund të ju udhëzojë gjatë, cila është ajo që orarit të punës duhet të jepen për të. 

Së dyti, kështu që unë e di profesorë si për të na habisin me teste. Unë kisha një profesor ato si, yo, nga rruga, mos harroni se afatmesëm ju keni të hënën e ardhshme. Po, unë nuk e di në lidhje me atë afatmesme. Kështu që unë jam duke shkuar të jetë se AT që ju kujton të gjithë se quiz 0-- sepse, ju e dini, ne jemi CS. Tani që ne kemi bërë vargjeve, ju merrni pse kjo është quiz 0, nuk pyes 1, eh? NE RREGULL. Oh, kam marrë disa nënqesh në se një. NE RREGULL. 

Pra quiz 0 do të jetë më 14 tetor në qoftë se ju jeni në seksionin e hënë-e mërkurë dhe 15 tetorit në qoftë se ju jeni në seksioni e martë, të enjten. Kjo nuk vlen për ata prej jush në Harvard who-- Unë mendoj se ju do të jenë të gjithë duke marrë kuize tuaj në 14. 

Pra, vërtet, javën e ardhshme, në qoftë se Davidi, në leksionin, shkon, Yeah, kështu që për këtë quiz javën e ardhshme, ju të gjithë nuk do të tronditur për shkak ju erdhi në seksionin dhe ju e dini se juaj Quiz 0 është në dy javë. Dhe ne do të kemi shqyrtim seanca dhe çdo gjë. Kështu që nuk ka shqetësime në lidhje me duke u frikësuar për atë. Çdo pyetje më herët, ndonjë pyetje në të gjitha çështjet lidhur logjistike, nota, orarit të punës, seksione? Po. 

Audienca: Pra quiz është do të jetë i gjatë ligjëratës? 

ANDI Peng: Po. Pra quiz, unë mendoj, është 60 Në minutën e ranë në atë slot kohë që ju do të vetëm të marrë në sallën e leksionit. Pra, ju nuk keni për të ardhur në në, si, një të rastit 7:00 PM. Kjo është e gjitha e mirë. Po. Ftohtë. 

Në rregull. Pra, ne jemi duke shkuar për futur një koncept për ju këtë javë se Davidi tashmë ka lloj e preku në leksionin këtë javë të fundit. Ajo që quhet Gdb. Dhe sa prej jush, ndërsa në Kursi i shkrimit psets tuaja, kanë vënë re një buton i madh që thotë "Debug" në krye të IDE tuaj? NE RREGULL. Pra, tani ne do të vërtetë të merrni për të nxjerr në dritë misterin e asaj që atë buton në fakt bën. Dhe unë ju garantoj, kjo është një bukur, gjë e bukur. 

Pra, deri tani, unë mendoj ka pasur dy gjëra studentët kanë qenë në mënyrë tipike duke bërë kur debugging psets. Një, ata ose shtoni në printf () - kështu që çdo disa rreshta, ata shtojnë në një printf () - oh, çfarë është kjo e ndryshueshme? Oh, çfarë është kjo variabël now-- dhe ju lloj i shihni progresion e kodit tuaj si ajo shkon. Ose metoda e dytë fëmijët të bëni është se ata vetëm të shkruajnë të gjithë gjë dhe pastaj të shkojnë si kjo në fund. Shpresojmë ajo punon. Unë ju garantoj, Gdb është më e mirë se të dy këto metoda. Po. Pra, kjo do të jetë miku juaj i ri më i mirë. Sepse kjo është një gjë e bukur që vizualisht tregon dy çfarë kodi juaj është duke bërë në një pikë të veçantë si dhe atë të gjithë tuaj variabla janë të mbante, si ajo që vlerat e tyre janë, në atë pikë të veçantë. Dhe në këtë mënyrë, ju mund të vërtetë vendosur breakpoints në kodin tuaj. Ju mund të drejtuar përmes linjës nga linjë. Dhe GDB do të ketë vetëm për ju, shfaqet për ju, atë që të gjithë e variablave tuaj po, çfarë po bëjnë, çfarë po ndodh në kodin. Dhe në një mënyrë të tillë, është e aq shumë e lehtë për të parë çfarë po ndodh në vend të printf-ing ose shkruar deklaratat tuaja. 

Pra, ne do të bëjmë një shembull të kësaj më vonë. Pra, kjo duket pak abstrakt. Nuk shqetësohet, ne do të bëjmë shembuj. Dhe kështu në thelb, tre më të madhe, funksionet më të përdorura që ju do të duhet në GDB janë Tjetra, Hapi mbi, dhe Hapi në buttons. Unë jam duke shkuar për kokë atje, në të vërtetë, tani për tani. 

Kështu që mund të ju djema të gjitha të shihni se ose duhet të zoom në një grimë? Në pjesën e pasme, ju mund të shihni se? A duhet të zmadhuar? Vetëm pak? OK, i ftohtë. Atje shkojmë. NE RREGULL. 

Kështu që unë kam, këtu, my Zbatimi për lakmitar. Dhe ndërsa një shumë e ju djema shkroi babëzitur në lak, ndërsa form-- se është një mënyrë krejtësisht e pranueshme për të bërë it-- një tjetër mënyrë për të bërë atë është thjesht të ndarë në modulo. Sepse atëherë ju mund të ketë tuaj Vlera dhe pastaj kanë mbetur tuaj. Dhe pastaj ju mund të vetëm shtoni atë të gjithë së bashku. A logjikën e asaj që unë jam duke bërë këtu kuptim për të gjithë, para se të fillojmë? Lloji i? Ftohtë. I madh. Kjo është një pjesë e bukur sexy e kodit, unë do të thoja. Ashtu si thashë, David, në leksion, pas një kohe, ju do të të gjithë të fillojnë të shohim kodin si diçka që është e bukur. Dhe ndonjëherë kur ju shihni e bukur Kodi, kjo është e tillë një ndjenjë e mrekullueshme. 

Pra megjithatë, ndërsa ky kod është shumë e bukur, ajo nuk punon si duhet. Pra, le të kandidojë check50 për këtë. Kontrolloni 50 20-- OOP. 2? A është kjo pset2? Po. Oh, pset1. NE RREGULL. Pra, ne të drejtuar check50. 

Dhe si ju djema mund të shihni këtu, kjo është në mungesë të disa rasteve. Dhe për disa prej jush, në Sigurisht për të bërë grupe tuaj problem, ju jeni si, ah, pse nuk është ajo punon. Pse është duke punuar për disa Vlerat por jo për të tjerët? E pra, GDB do të ndihmojë të kuptoj se pse këto inpute nuk ishin duke punuar. 

NE RREGULL. Pra, le të shohim, një nga Kontrollet unë po dështonte në check50 ishte vlera input e 0,41. Pra, përgjigja e saktë që ju duhet të marrë është një 4. Por në vend të kësaj ajo që unë jam printim është 3-n, i cili është i saktë. Pra, le të vetëm të drejtuar këtë me dorë, vetëm sigurohuni që check50 është duke punuar. Le të bëjmë ./greedy. Na falni, unë kam për të bërë babëzitur. Atje shkojmë. Tani ./greedy. 

Sa është borxh? Le të bëjmë 0,41. Dhe yep, ne shohim këtu se ajo është kompjuteri 3 kur përgjigja e saktë, në fakt, duhet të jetë 4. Pra, le të hyjë GDB dhe të shohim se si ne mund të shkoni në lidhje me fiksimin e këtij problemi. 

Pra, hapi i parë në gjithmonë debugging kodin tuaj është për të vendosur një breakpoint, ose një pikë në të cilën ju dua kompjuter ose Rregullues të fillojmë të shikojmë. Pra, nëse ju nuk bëni me të vërtetë e di se çfarë problemi juaj është, zakonisht, gjë tipike që ne duam të bëni është për të vendosur breakpoint tonë në kryesore. Pra, në qoftë se ju djema mund të shihni këtë butonin e kuq të drejtë atje, yep, që ishte më vendosjen e një breakpoint për funksionin kryesor. Unë klikoni atë. 

Dhe pastaj unë mund të shkojnë deri në butonin tim Debug. Unë goditi butonin. Më lejoni të zoom mbrapa në qoftë se unë mund. Atje shkojmë. Pra, ne kemi, këtu, një panel në të djathtë. Më vjen keq, djema në shpinë, ju nuk mund të vërtetë shoh me të vërtetë mirë. Por në thelb, të gjithë ky panel e drejtë është duke bërë është mbajtja e dy theksuar line, që është linjë e kodit se kompjuteri është aktualisht, si dhe të gjithë variablat tuaja këtu poshtë. 

Pra, ju keni marrë cent, monedha, n, gjithë deklaruar për gjëra të ndryshme në këtë pikë. Nuk shqetësohet, sepse ne nuk kemi në fakt initialized ata për çdo ndryshore ende. Pra, në kompjuterin tuaj, tuaj kompjuter është vetëm duke parë, oh, 32767 ishte funksioni i fundit i përdorur e atë hapësirë ​​e kujtesës në kompjuterin tim. Dhe kështu kjo është ajo ku cent aktualisht është. Por jo se një herë ju drejtuar kodin, ajo duhet të bëhet initialized. 

Pra, le të shkojnë nëpër, rresht pas line, çfarë po ndodh këtu. NE RREGULL. Kështu që këtu janë tre butonat që unë vetëm shpjegohet. Ju keni të riprodhimit ose funksionin Run, buton, ju keni hap mbi butonin, dhe ju gjithashtu keni Hapi në butonin. Dhe në thelb, të tre ata thjesht shkoni nëpër kodin tuaj dhe të bëjë gjëra të ndryshme. 

Pra në mënyrë tipike, kur ju jeni debugging, ne nuk duam të vetëm goditi Luaj, sepse Luaj vetëm do të kandidojë kodi juaj me fundin e saj. Dhe pastaj ju nuk do të vërtetë të e di se çfarë problemi juaj është nëse keni vendosur breakpoints shumta. Në qoftë se keni vendosur pikat e ndalimit të shumta, ajo thjesht do të automatikisht drejtuar nga një breakpoint, të ardhshëm, të ardhshëm. Por në këtë rast ne kemi vetëm se një, sepse ne duan të punojnë rrugën tonë nga lart poshtë e deri në fund. Pra, ne jemi duke shkuar për të injorojë atë buton tani për qëllime të këtij programi. 

Pra, Hapi mbi funksionin vetëm Hapat mbi çdo linjë të vetme dhe ju tregon se çfarë kompjuteri është duke bërë. Hapi në funksion shkon në funksion aktuale kjo është në linjë tuaj të kodit. Kështu për shembull, si printf (), që është një funksion, e drejtë? Në qoftë se unë të kërkuar për të fizikisht hap në printf () funksionin e, Unë në fakt do të shkoj në pjesë të Kodi ku printf () ishte shkruar dhe të shohim çfarë po ndodh atje. 

Por zakonisht, ne supozojmë se kodi që ne të ju jap punon. Supozojmë printf () është duke punuar. Ne supozojmë se GetInt () është duke punuar. Kështu që nuk ka nevojë për të futemi në këto funksione. Por në qoftë se ka funksione që ju të shkruani vetë që ju doni të kontrolloni se çfarë po ndodh, ju do të duan të hap në atë funksion. 

Deri tani ne jemi vetëm do të hap mbi këtë pjesë të kodit. Pra, le të shohim. Oh, të shtypura, "Oh hai, si ndryshim shumë është borxh? " Ne nuk e kujdesit. Ne e dimë se është duke punuar, kështu që ne hap mbi të. 

Pra n, e cila është noton ynë që ne kemi initialized-- ose declared-- deri në krye, ne jemi tani barazuar që të GetFloat (). Pra, le të hap mbi atë. Dhe ne shohim në nivel fund këtu, programi është duke bërë më të input një vlerë. Pra, le të vleren ne duam t'i fusë për të provuar këtu, e cila është 0.41. I madh. 

Deri tani n-- bëni ju djema të parë Këtu, në bottom-- është stored-- sepse ne nuk e kanë rrumbullakuar ende, kjo është ruhet në këtë si gjigant noton se është 0,4099999996, e cila është mjaft afër tonë qëllime, tani, në 0,41. Dhe pastaj ne do të shohim më vonë, si ne vazhdojnë shkelën mbi programin, pas këtu, është bërë n harmonishëm dhe cent ka bërë 41. I madh. Pra, ne e dimë se duke punuar arrestimi tonë. Ne e dimë se ne kemi Numri i saktë i cent, kështu që ne e dimë se kjo është jo të vërtetë problemi. 

Pra, ne vazhdojmë shkelën në këtë program. Ne do të shkojmë këtu. Dhe kështu pas këtë linjë të kodit, ne duhet të dinë se sa lagjet kemi. Ne hap mbi. Dhe ju shihni ne bëjmë, në fakt, kanë një të tillë e katërta, sepse ne kemi zbritur 25 nga vlera tona fillestare prej 41. Dhe ne kemi 16 u nis për cent tona. 

A e kuptojnë të gjithë si programi po rrit përmes dhe pse cent është bërë tashmë 16 dhe pse, tani, monedha është bërë 1? Është e të gjithë pas se logjika? Ftohtë. Pra, si e këtë pikë, punës programit, e drejtë? Ne e dimë se është duke bërë pikërisht ajo që ne duam që ajo të. Dhe ne fakt nuk duhet të shtypura nga, oh, çfarë është cent në këtë pikë, ajo që është monedha në këtë pikë. 

Ne vazhdojmë duke shkuar përmes programit. Hapi mbi. Ftohtë. Ne do të shkojmë mbi dimes. I madh. Ne e shohim se ajo është marrë off $ 0,10 për një monedhë. Dhe tani ne kemi dy monedha. Kjo është e saktë. 

Ne do të shkojmë mbi pennies dhe ne e shohim që ne kemi mbeti mbi cent. Hmm, kjo është e çuditshme. Deri këtu në programin, unë është dashur që kanë zbritur pennies e mia. Ndoshta unë thjesht nuk ishte duke bërë këtë të drejtë line. Dhe mjerisht, ju mund të shihni këtu, sepse ne e dimë se ne jemi shkelën përmes linjave 32 dhe 33, kjo është ajo ku programi ynë në mënyrë të paligjshme kishte variabla të kandidojë. Pra, ne mund të shohim dhe të shohim, oh, Unë jam duke zbritur cent këtu, por unë nuk jam në të vërtetë duke shtuar me vlerën time monedhë. Unë jam duke shtuar në cent. Dhe unë nuk dua të shtoj në cent, unë dua të shtoj në monedha. Pra, nëse ne ndryshojmë që të monedhave, ne kemi marrë një program pune. Unë mund të kandidojë check50. Ju vetëm mund të dalë jashtë e të drejtës gdb këtu dhe pastaj të drejtuar check50 përsëri. Unë mund ta bëjë këtë vetëm. Unë kam për të bërë babëzitur. 0.41. Dhe këtu, kjo është shtypje jashtë përgjigje të drejtë. 

Pra, si ju djema mund të shihni, Gdb është një mjet të vërtetë të fuqishme sepse kur kemi kaq shumë kod në vazhdim e sipër dhe kaq shumë ndryshore se është e vështirë për ne, si një njeri, për të mbajtur gjurmët e. Kompjuter, në GDB Rregullues, ka aftësinë të mbajnë gjurmët e çdo gjë. Unë e di, në Visionaire, ju djema ndoshta mund të ketë goditur disa gabimet e segmentimit sepse keni qenë running jashtë caqeve të vektorit tuaj. Në shembullin e Cezarit, kjo është pikërisht ajo që unë kam zbatuar këtu. 

Kështu që kam harruar për të kontrolluar për Çfarë do të ndodhë nëse unë nuk kanë dy argumente command line. Unë thjesht nuk e vënë atë në kontroll. Dhe kështu që nëse unë të drejtuar Debug-- kam vendosur breakpoint im të drejtë atje. I drejtuar debug. 

NE RREGULL. Po. Pra, në fakt, Gdb ishte menduar të ketë më tha atje ishte faji segmentimit atje. Unë nuk e di se çfarë po ndodhte ka të drejtë, por kur unë u zhvillua atë, ajo ishte duke punuar. Kur ju drejtuar rreshta të kodit dhe përmes GDB mund vetëm befas lënë në ty, shkojnë deri dhe të shohim se çfarë gabimi është i kuq. Ajo do t'ju them, hej, ju kishte një defekt segmentimit, që do të thotë se ju u përpoq për të hyrë hapësirë ​​në një grup që nuk ka ekzistuar. Po. 

Pra, në problemin e ardhshëm vendosur këtë javë, ju djema ndoshta do të ketë një shumë të variabla lundrues rreth. Ju nuk do të jetë i sigurt se çfarë ata të gjithë do të thotë në një pikë të caktuar. Pra, GDB të vërtetë do t'ju ndihmojë në zbulimin se çfarë ata janë të gjithë barabartë dhe duke qenë në gjendje për të parë se shikimi. A është ndokush hutuar se si ndonjë që ishte duke punuar? Ftohtë. Në rregull. Pra, pas kësaj, ne jemi do të zhyten të drejtë në janë katër të ndryshme llojet e llojeve për këtë javë. Sa prej jush, së pari të gjitha, para se të fillojmë, e kanë lexuar të gjithë spekulim për pset3? NE RREGULL. Unë jam krenar për ju djema. Kjo është si gjysma e klasës, i cili është dukshëm më shumë se herën e fundit. 

Pra, kjo është e madhe, sepse kur ne flasim për përmbajtjen në lecture-- apo keq, në section-- Më pëlqen të bëjnë një shumë që prapa asaj që është pset dhe si ju doni të zbatuar që në pset tuaj. Pra, nëse ju vijnë të paturit lexoni spekulim, ajo do të të jetë shumë më e lehtë për ju për të kuptuar atë që unë jam duke folur për kur unë them, oh hej, kjo mund të jetë një të vërtetë të vend i mirë për të zbatuar këtë lloj. Pra, ata që e kanë lexuar spekulim di se, si pjesë e pset tuaj, ju jeni do të duhet të shkruaj një lloj lloji. Pra, kjo mund të jetë shumë e dobishme për një shumë prej jush sot. 

Pra, ne do të nisem me, në thelb, lloji më i thjeshtë e lloj, zgjedhja lloj. Algorithm tipike për se si ne do të shkoj në lidhje me këtë is-- Davidi shkoi nëpër të gjitha këto në leksion, kështu që unë do të lëvizin shpejt së bashku here-- është në thelb, ju kanë një rrjet të vlerave. Dhe pastaj ju të gjeni të Vlera më e vogël Unsorted dhe ju bie në ujdi se vlera me vlera e parë Unsorted. Dhe atëherë ju vetëm i mbajnë përsëritur me pjesën tjetër të listës suaj. 

Dhe këtu është një shpjegim vizual e se si do të punojë. Kështu për shembull, në qoftë se ne ishim për të filluar me një grup të pesë elemente, indeksi 0 në 4, me 3, 5, 2, 6, dhe 4 vlerat vendosur në array-- në mënyrë të drejtë tani, ne jemi vetëm duke shkuar për të marrë se ata janë të gjithë Unsorted sepse ne nuk kemi testuar ndryshe. 

Pra, si një lloj përzgjedhje do Puna është se ajo do të për herë të parë drejtuar nëpër tërësinë e array pandara. Ajo do të marr nga vlerën më të vogël. Në këtë rast, 3, e drejtë tani, është më i vogël. Ajo merr të 5. Jo, 5 nuk është më i madh than-- apo vjen keq, është jo më pak than-- 3. Pra, vlera minimale është ende 3. Dhe pastaj ju merrni në 2. Kompjuteri sheh, oh, 2 është më pak se 3. 2 tani duhet të jetë vlera minimale. Dhe kështu 2 këmbime me atë vlerë të parë. 

Kështu që pas një të kaluar, ne me të vërtetë shohim se 2 dhe 3 janë swapped. Dhe ne jemi vetëm do të vazhdojnë të bëjnë kjo përsëri me pjesën tjetër të vektorit. Pra, ne jemi duke shkuar për të vetëm të drejtuar përmes katër indekset e fundit të vektorit. Ne do të shohim se 3 është vlera e ardhshme minimale. Pra, ne jemi duke shkuar për të bie në ujdi që me 4. Dhe atëherë ne jemi vetëm duke shkuar për të mbajtur kalon nëpër derisa, në fund, ju të shkoj në një grup të renditura në të cilën 2, 3, 4, 5, 6 dhe janë të renditura. A e kuptojnë të gjithë logjikën se si punon një lloj përzgjedhje? 

Ju thjesht duhet disa lloj një vlerë minimale. Ju jeni mbajtja e asaj që është. Dhe sa herë që ju të gjeni atë, ju bie në ujdi atë me vlerën e parë në array-- apo, jo value-- parë vlera tjetër në rrjet. Ftohtë. 

Pra, si ju djema lloj i pa nga një paraqitje e shkurtër të shkurtër, ne jemi duke shkuar për pseudokod këtë. Pra, nëse ju djema në shpinë duan të formojnë një grup, të gjithë në një tabelë mund të formojnë një partner të vogël, unë jam duke shkuar për të ju jap djema si tre minuta për vetëm bisedoni me anë të logjika, në gjuhën angleze, se si mund të jemi në gjendje të zbatojë pseudokod për të shkruar një lloj përzgjedhjeje. Dhe nuk ka karamele. Ju lutemi të vijnë dhe për të marrë karamele. Nëse ju jeni në shpinë dhe ju doni karamele, unë mund të hedhin karamele në ju. Në fakt, të bëjë ftohtë ju, duke filluar. Oh me falni. NE RREGULL. 

Pra, nëse ne do të donim për të, si një klasë, shkruani pseudokod për mënyrën se si dikush mund të qasen ky problem, vetëm mos ngurroni. Unë vetëm do të shkoj përreth dhe, në mënyrë që, pyesni grupet për linjën e ardhshëm të çfarë ne duhet të bëjmë. Pra, nëse ju djema doni të filloni jashtë, çfarë është gjëja e parë duhet të bëni kur jeni duke u përpjekur për të zbatojë një mënyrë për të zgjidhur këtë program për të selektive të zgjidhur një listë? Le të vetëm të supozojmë ne kanë një grup, të gjithë të drejtë? 

Audienca: Ju doni të krijoni disa lloj [e padëgjueshme] që ju jeni që kalon nëpër të gjithë grup tuaj. 

ANDI Peng: E ​​drejta. Pra, ju jeni do të duan të iterate nëpër çdo hapësirë, e drejtë? Pra, i madh. Nëse ju djema doni të më jepte tjetër line-- yeah, në pjesën e prapme. 

Audienca: Kontrolloni ata të gjitha për të vogël. 

ANDI Peng: Nuk shkojmë. Pra, ne duam të shkojnë nëpër dhe kontrolloni për të të shohim se çfarë vlera minimale është, e drejtë? Unë do të shkurtoj se në "min." Çfarë bëni ju djema doni të bëni pas ju keni gjetur vlerën minimale? 

Audienca: [padëgjueshme] ANDI Peng: Pra, ju jeni do të duan të kaloni atë me të parë të këtij grup, e drejtë? Ky është fillimi, unë jam duke shkuar për të thënë. Në rregull. Pra, tani që ju keni swapped parë një, çfarë ju doni të bëni pas kësaj? Pra, tani ne e dimë se kjo këtu duhet të jetë vlera më të vogël, apo jo? Atëherë ju keni një pushim shtesë e vektorit që është Unsorted. Pra, çfarë ju doni të bëni këtu, në qoftë se ju djema duan të më jepni linjë tjetër? Audienca: Pra, atëherë ju doni të iterate përmes pjesës së mbetur të vektorit. ANDI Peng: Po. Dhe kështu çfarë iterating përmes lloj i thotë ne ndoshta do të duhet? Çfarë lloji of-- 

Audienca: Oh, një variabël shtesë? ANDI Peng: Ndoshta një tjetër për lak, e drejtë? Pra, ne jemi me siguri do të duan të iterate through-- madh. Dhe pastaj ju do të jeni për të shkuar mbrapa dhe ndoshta kontrolloni minimale përsëri, e drejtë? Dhe ju jeni do të vazhdojnë të përsërisin kjo, sepse sythe vetëm duke shkuar për të mbajtur drejtimin, e drejtë? 

Pra, si ju djema mund të shihni, ne vetëm një pseudokod të përgjithshme se si ne duam që ky program të duken. Kjo iterate këtu, çfarë bëjmë ne zakonisht duhet të shkruani në kodin tonë në qoftë se ne duam të iterate nëpër një array, çfarë lloji i strukturës së? Unë mendoj Christabel tashmë ka thënë këtë më parë. 

Audienca: një për lak. 

ANDI Peng: një për lak? Pikërisht. Pra, kjo është ndoshta do të jetë një për lak. Çfarë është një kontroll këtu do të thotë? Në mënyrë tipike, në qoftë se ju dëshironi të shikoni nëse diçka është diçka else-- 

Audienca: Në qoftë se. 

ANDI Peng: Një në qoftë se, e drejtë? Dhe pastaj swap këtu, ne do të shkoj për më vonë, sepse David shkoi nëpër atë në leksion si. Dhe pastaj iterate dytë implies-- 

Audienca: Një tjetër për lak. 

ANDI Peng: --another për lak, pikërisht. Pra, në qoftë se ne jemi duke kërkuar në këtë të saktë, ne mund të shihni se ne jemi me siguri do të duhet një mbivendosur për lak me një deklaratë të kushtëzuar në atje dhe pastaj një pjesë aktuale e kodit që është do të bie në ujdi vlerat. Kështu që unë kam shkruar vetëm në përgjithësi një kod pseudokod këtu. Dhe pastaj ne jemi të vërtetë do për të fizikisht, si një klasë, përpiqen për të zbatuar këtë sot. Le të kthehemi në këtë IDE. 

Uh-oh. Pse është se not-- nuk është. NE RREGULL. Na vjen keq, më lejoni të përpiqen për të zoom në pak më shumë. Atje shkojmë. Të gjitha unë jam duke bërë këtu është që kam krijuar një program të quajtur "Zgjedhja / sort.c." Unë kam krijuar një grup të nëntë vlerat, 4, 8, 2, 1, 6, 7, 9, 5, 3. Aktualisht, si ju mund të shihni, ata janë të renditura. n do të jetë numri që ju tregon sasinë e vlerave ju keni në grup tuaj. Në këtë rast, ne kemi nëntë vlera. Dhe unë kam marrë vetëm një për lak këtu që printon nga array Unsorted. 

Dhe në fund, unë kam marrë edhe një për lak që vetëm printon atë përsëri. Pra teorikisht, nëse këtë program punon saktë, në fund, ju duhet të shihni një të shtypura për lak në të cilën 1, 2, 3, 4, 5, 6, 7, 8, 9 janë të gjitha në mënyrë korrekte. 

Pra, ne kemi marrë pseudokod tonë këtu. A ka dikush doni to-- unë jam vetëm do të shkojnë të kërkojnë volunteers-- më thoni saktësisht se çfarë të shkruani në qoftë se ne duam të, së pari, vetëm iterate me fillim të këtij grup? Çfarë është linjë e kodit unë jam ndoshta do të duhet këtu? 

Audienca: [padëgjueshme] 

ANDI Peng: Po, të ndjehen të pa pagesë to-- vjen keq, ju nuk duhet të qëndrojë ndjehen up-- të lirë për të ngritur zërin tuaj pak. 

Audienca: Për int i barabartë 0-- 

ANDI Peng: Po, mirë. 

AUDIENCA: i është më pak se gjatësia vektorit. 

ANDI Peng: Pra, mbani në mendjen këtu, sepse ne nuk kanë një funksion që na tregon gjatësinë e një grup, ne tashmë kemi një Vlera që ruan atë. E drejtë? Një tjetër gjë për të mbajtur në mind-- në një grup e nëntë vlerave, cilat janë tregues? Le të thonë se ky grup ishte 0 në 3. Ju shihni se fundit indeksi është në fakt 3. Kjo nuk është 4, edhe pse nuk ka katër vlerat në grup. 

Kështu që këtu, ne duhet të jenë shumë të kujdesshëm e asaj gjendjen tonë për gjatësinë do te jete. 

Audienca: Nuk do të jetë n minus 1? ANDI Peng: Ajo do n minus 1, saktësisht. E bën këtë kuptim, pse kjo është n minus 1, të gjithë? Kjo është për shkak se vargjeve janë zero-indeksuar. Ata fillojnë me 0 dhe të drejtuar deri n minus 1. Po, kjo është pak e ndërlikuar. NE RREGULL. Dhe pastaj-- Audienca: Isnt'1 se marrë tashmë kujdesin e pse, nga vetëm të mos thënë "më pak se ose e barabartë me "dhe vetëm duke thënë se" më pak se? " 

ANDI Peng: Kjo është një pyetje me të vërtetë mirë. Pra, po. Por gjithashtu, në mënyrën që ne jemi zbatimin e drejtë rrjedhëse, ju duhet të krahasoni dy vlera. Kështu që ju të vërtetë duan të lënë "në" bosh. Sepse në qoftë se ju krahasoni kjo, ju nuk jeni duke shkuar kanë asgjë pas saj të krahasohet me, apo jo? Po. Kështu që unë ++. Le të shtoni kllapa tona në. Uh. I madh. Kështu që ne kemi në fillim e lak sonë të jashtme. Deri tani ne ndoshta dëshironi të krijojë një ndryshore për mbajtjen e udhë të vlerës më të vogël, apo jo? A ka dikush duan të më jepte linjë e kodit që do ta bëjë këtë? Çfarë na duhet në qoftë se ne jemi duke shkuar të duan për të ruajtur diçka? 

E drejtë. Ndoshta një emër të mirë për atë do be-- "temp" totalisht works-- ndoshta një të quajtur më me vend do të jetë, në qoftë se ne duam value-- më të vogël 

Audienca: Min. ANDI Peng: min, atje ne do të shkojmë. min do të ishte mirë. Dhe kështu këtu, çfarë të bëjmë ne dua të nisja atë në? Kjo është pak i ndërlikuar. Sepse tani më së fillimi i këtij grup, ju nuk e keni shikuar në asgjë, e drejtë? Pra, çfarë, automatikisht, nëse ne jemi vetëm në i barabartë me 0, çfarë duam të nisja Vlera jonë e parë minimale për të? Audienca: i. ANDI Peng: i, pikërisht. Christabel, pse duam të nisja atë për të i? 

Audienca: Sepse, mirë, ne jemi duke filluar me 0. Pra, sepse ne kemi asgjë për të krahasuar atë për të, minimumi do të përfundojë si 0. 

ANDI Peng: Pikërisht. Pra, ajo është saktësisht e drejtë. Sepse ne nuk kemi në fakt shikoi ende asgjë, ne nuk e dimë se çfarë vlera ynë minimal është. Ne duam të vetëm nisja atë për Unë, i cili, aktualisht, është e drejtë këtu. Dhe si ne vazhdojmë të lëvizur poshtë këtë koleksion, ne do të shohim se, me çdo kalojë shtesë, unë increments. Dhe kështu në këtë pikë, I është ndoshta do të duan të jenë minimale, sepse ajo do të jetë çdo gjë është fillimi i vektorit pandara. Ftohtë. 

Pra, tani ne duam të shtoni një për lak këtu që është do të iterate përmes Unsorted, ose pjesa tjetër e këtij grup. A ka dikush duan të më jepni një linjë e kodit që do ta bëjë këtë? Hint-- çfarë kemi nevojë këtu poshtë? Çfarë do të shkojë në këtë për lak? Po. Audienca: Pra, ne do të duan të kanë një numër i plotë ndryshme, sepse ne jemi që kalon nëpër pjesën tjetër e array në vend të I, kështu që ndoshta j. 

ANDI Peng: Po, j tingëllon mirë për mua. Është e barabartë? 

Audienca: Pra, do të jetë unë plus 1, për shkak se ju jeni duke filluar në vlerën e ardhshëm. Dhe pastaj në end-- Pra, përsëri, j është pak se n minus 1, dhe pastaj j ++. ANDI Peng: Great. 

Dhe pastaj në këtu, ne do të duan për të kontrolluar për të parë nëse gjendja jonë është plotësuar, e drejtë? Për shkak se ju doni të ndryshoni vlerën minimale nëse kjo është në fakt më e vogël se ajo që ju jeni duke e krahasuar atë me, apo jo? Pra, çfarë do të shkojmë të duan në këtu? Kontrollo për të parë. Çfarë lloji të deklaratës po ne ndoshta do TI doni të përdorni në qoftë se ne dëshironi të shikoni diçka? 

Audienca: Një rast deklaratë. 

ANDI Peng: Një në qoftë se deklarata. Pra if-- dhe çfarë do të jetë kushti që ne duam brenda e në qoftë se deklarata tonë? 

Audienca: Nëse vlera e j është më e vogël se vlera e i-- 

ANDI Peng: Pikërisht. Pra if-- kështu që ky grup quhet "array". I madh. Pra, nëse array-- çfarë ishte kjo? Thuaj se përsëri. 

Audienca: Nëse array-j është më pak se array-i, atëherë ne do të ndryshojë min. Pra min do të j. 

ANDI Peng: ka që e bëjnë kuptim? NE RREGULL. Dhe tani këtu poshtë, ne fakt duan për të zbatuar shkëmbim, e drejtë? Pra kujtojnë, në leksionin, që Davidi, kur ai ishte duke u përpjekur për të bie në ujdi the-- çfarë ishte lëng portokalli dhe milk-- it-- 

Audienca: Kjo ishte bruto. 

ANDI Peng: Po, ajo ishte lloj i bruto. Por kjo ishte një e mirë goxha Koncepti demonstruar kohë. Pra, mendoni për vlerat tuaja këtu. Ju keni marrë një grup i min, një grup i I, apo çfarëdo ne ishim duke u përpjekur për shkëmbim këtu. Dhe ju ndoshta nuk mund të derdh ato në njëri-tjetrin në të njëjtën kohë, e drejtë? Pra, çfarë po shkojmë të duhet për të krijuar këtu në mënyrë për shkëmbim vlerat saktë? 

Audienca: Një variabël e përkohshme. 

ANDI Peng: Një variabël e përkohshme. Pra, le të bëjë int temp. Ja, kjo do të jetë një më të mirë kohë to-- ee, çfarë ishte kjo? NE RREGULL. Pra, kjo do të kishte qenë një më të mirë koha për emrin e ndryshueshme "temp." Pra, le të bëjë int temp. Çfarë do të shkojmë për vendosur temp të barabartë këtu? Audienca: Min? ANDI Peng: Kjo është pak i ndërlikuar. Ajo në fakt nuk ka rëndësi në fund. Nuk ka rëndësi se çfarë mënyrë që ju zgjidhni për të bie në ujdi në sa kohë që ju jeni duke e bërë të sigurt që ju jeni mbajtja e asaj që ju po shkëmbejnë. 

Audienca: Kjo mund të jetë array-i. 

ANDI Peng: Po, le ta bëjmë array-i. Dhe pastaj çfarë është vija e ardhshme i kodit ne duam të kemi këtu? Audienca: array-i barabartë array-J. ANDI Peng: Dhe së fundi? Audienca: array-j është e barabartë array-i. Audienca: Ose array-j barabartë array-temp-- ose, temp. 

ANDI Peng: OK. Pra, le të drejtuar këtë dhe të shohim nëse ajo do të punojë. Ku kjo ndodh? Oh, kjo është një problem. Shih, në linjë 40, ne jemi duke u përpjekur për të përdorur array-J? Por aty ku nuk j ekzistojnë vetëm në? 

Audienca: Në për lak. ANDI Peng: E ​​drejta. Pra, çfarë do të shkojmë të duhet të bëjmë? 

Audienca: Define atë jashtë the-- Audienca: Po, unë mendoj se ju keni për të përdorur një tjetër nëse deklarata, e drejtë? Pra si, në qoftë se minimum-- të gjithë të drejtë, më lejoni të mendoj. 

ANDI peng: Guys, provoni për të marrë një vështrim Le të shih, çfarë është diçka që ne mund të bëjmë këtu? 

Audienca: OK. Pra, nëse minimale nuk i barabartë j-- kështu që nëse minimumi është ende i-- atëherë ne nuk do të duhet të bie në ujdi. 

ANDI Peng: A do të barabartë unë? Çfarë doni të thoni këtu? 

Audienca: Ose po, në qoftë se minimale nuk Unë nuk të barabartë, po. ANDI Peng: OK. Mirë që zgjidh, lloj, problemet tona. Por që ende nuk e zgjidh Problemi i se çfarë ndodh në qoftë se j-- që j nuk ekziston jashtë saj, çfarë nuk ju duam të bëjmë me të? Shpallë jashtë? Le të provoni drejtimin këtë. Uh-oh. Lloj jonë nuk është duke punuar. 

Siç mund ta shikoni, fillestar ynë array kishte këto vlera. Dhe pastaj ajo duhet të ketë qenë në 1, 2, 3, 4, 5, 6, 7, 8, 9. Kjo nuk është duke punuar. AHH. Çfarë bëjmë ne? Audienca: Debug. ANDI Peng: Në rregull, ne mund të provoni se. Ne mund të debug. Zoom out pak. Le të vendosur breakpoint tonë. Le të shkojmë OK like--. 

Pra, sepse ne tashmë e dimë se këto rreshta, 15 deri 22, janë working-- sepse të gjitha unë jam duke bërë është vetëm iterating përmes dhe printing-- Unë mund të shkoj përpara dhe të kaloni atë. Le të fillojmë në linjë 25. OOP, më lejoni të shpëtoj nga kjo. 

Audienca: Pra breakpoint-së ku debugging fillon? ANDI Peng: ose ndalon. Audienca: Ose ndalesa. ANDI Peng: Po. Ju mund të vendosni breakpoints shumta dhe ajo vetëm mund të kërcejnë nga njëri në tjetrin. Por në këtë rast ne nuk e dimë ku gabimi ndodh. Pra, ne vetëm duam të të fillojë nga lart poshtë. Yep. NE RREGULL. 

Pra, kjo vijë këtu, ne mund të hap në. Ju mund të shihni këtu poshtë, ne kemi marrë një grup. Ata janë vlerat që janë në rrjet. A e shihni se, si indeksi 0, ajo korrespondon me value-- oh, Unë do të përpiqet për të zmadhuar. Na vjen keq, është e vërtetë e vështirë të see-- në indeksin e array 0, ne kemi një vlerë prej 4 dhe pastaj kështu me radhë e kështu me radhë. Ne kemi variablave tona lokale. Tani për tani i është i barabartë me 0, të cilat ne duam që ajo të jetë. 

Dhe kështu që le të mbajë shkelën përmes. Minimum ynë është i barabartë me 0, të cilat ne gjithashtu duam që ajo të jetë. Dhe pastaj hyjmë dytë tonë për lak, nëse grup-j është më pak se vargut-I, që nuk ishte. Kështu që e keni parë se si se anashkaluar kjo? 

Audienca: Pra, duhet që, nëse minimum, të gjitha that-- nuk duhet që të jetë brenda të parët për lak? ANDI Peng: Jo, sepse ju ende duan për të provuar. Ju dëshironi të bëni një krahasim çdo kohë, edhe pasi ju drejtuar nëpërmjet saj. Ju nuk duan vetëm për të bërë atë në e parë përçimit. Ju doni të bëni atë me çdo kalojë shtesë përsëri. Pra, ju doni të kontrolloni për gjendja juaj brenda. Pra, ne jemi vetëm duke shkuar për të mbajtur drejtimin përmes këtu. Unë do të ju jap djema një aluzion. Ajo ka të bëjë me faktin se kur ju jeni duke kontrolluar kushtëzuar juaj, ju nuk jeni duke kontrolluar për indeksin e saktë. Kështu që tani ju jeni duke kontrolluar për indeks grup i j është më pak se grup indeksi i i. Por, çfarë jeni duke bërë në fillimi i për lak? A nuk jeni vendosjen J barabartë për të i? 

Yeah, kështu që ne mund të vërtetë të dalë nga Rregullues këtu. Pra, le të marrin një vështrim në pseudokod tonë. For-- ne jemi duke shkuar për të fillojë në i barabartë me 0. Ne jemi duke shkuar për të shkuar deri në minus 1 n. Le të kontrolloni, nuk kemi atë të drejtë? Po, kjo ishte e drejtë. 

Kështu pra brenda këtu, ne jemi do të krijojë një vlerë minimale dhe të vendosur që të barabartë me i. A e bëjmë këtë? Po, e bëri atë. Tani në brendshme për lak tonë, ne jemi shkuar për të bërë j barabartë i të n minus 1. A e bëjmë këtë? Në të vërtetë, ne e bëmë atë. 

Pra megjithatë, çfarë jemi duke krahasuar këtu? 

Audienca: j plus 1. ANDI Peng: Pikërisht. Dhe pastaj ju jeni do të duan për të vendosur minimale juaj barabartë me j plus 1, si dhe. Kështu që unë shkova me atë të vërtetë shpejt. A e kuptoni ju djema pse kjo është j plus 1? NE RREGULL. 

Pra, në grup tuaj, në kalojë juaj e parë përmes, juaj për lak, për int i barabartë me 0, le të vetëm supozojmë kjo nuk ka ndryshuar ende. Ne kemi një grup të, krejtësisht, vetëm katër elemente Unsorted, e drejtë? Pra, ne duam të iniciojnë i barabartë me 0. Dhe unë do të vetëm drejtuar nëpër këtë lak. Dhe kështu në kalimin e parë, ne jemi duke shkuar të nisja një ndryshore të quajtur "min" që gjithashtu është e barabartë unë, sepse ne nuk kemi një vlerë minimale. Pra, kjo është aktualisht e barabartë me 0 si. Dhe pastaj ne jemi duke shkuar për të shkuar deri. Dhe ne duam të iterate përsëri. Tani që ne kemi gjetur se çfarë minimale ynë është, ne duam të iterate nëpër përsëri për të parë nëse ajo është krahasuar, e drejtë? Kështu j, këtu, do tek i barabartë, e cila është 0. Dhe pastaj, nëse array j Plus, unë, e cila është ai që më tej mbi, si më pak se çfarë minimum juaj e tanishme vlerë është, ju doni të bie në ujdi. 

Pra, le të them vetëm ne kemi mori, si, 2, 5, 1, 8. Tani për tani, unë është e barabartë me 0 dhe j eshte e barabarte me 0. Dhe kjo është vlera jonë minimale. Nëse array-J plus i-- kështu që nëse një kjo është pas atij ne jemi duke kërkuar në është më e madhe se ajo e para saj, ajo do të bëhet minimale. 

Pra, këtu ne shohim se 5 është jo më pak se. Kështu ajo do të mos jetë 5. Ne e shohim se 1 është më pak se 2, e drejtë? Pra, tani ne e dimë se minimale ynë është do të jetë vlera indeks në 0, 1, 2. Po? Dhe pastaj kur ju merrni poshtë këtu, ju mund të bie në ujdi vlerat e sakta. 

Pra, kur ju djema janë vetëm duke pasur j para, ju nuk ishin në kërkim në një pas saj. Ju keni qenë në kërkim në njëjtë vlerë që është arsyeja pse ai thjesht nuk është bërë asgjë. A ka që e bëjnë kuptim për të gjithë, pse kishim nevojë se plus 1 atje? NE RREGULL. Tani le të vetëm të drejtuar nëpërmjet saj për të bërë Sigurohuni që pjesa tjetër e kodit është e saktë. Pse është kjo ndodh? Ah, kjo është e drejtë këtu min. Ne ishim duke krahasuar vlerën e gabuar. Oh no. 

Oh yeah, këtu poshtë ne kemi qenë shkëmbejnë vlerat gabuar si edhe. Sepse ne kemi qenë në kërkim në i dhe j. Ata janë ato që ne u kontrolluar. Ne të vërtetë duan të bie në ujdi minimale, minimumi i tanishëm, me çfarëdo një jashtë është. Dhe si ju djema mund të shihni poshtë këtu, ne kemi një rrjet të renditura. Ajo vetëm kishte të bënte me fakti se kur ne ishim kontrollin e zyrave Vlerat ne u krahasuar, ne nuk ishin në kërkim në vlerat e duhura. Ne ishim duke kërkuar në të njëjtën një këtu, jo në fakt shkëmbejnë atë. Ju duhet të shikoni në një tjetër për atë dhe pastaj ju mund të bie në ujdi. Pra, kjo është ajo që ishte lloj i përgjimi kodin tonë përpara. Dhe çfarë kam bërë këtu është gjithçka debugger mund të ketë bërë për ju Unë vetëm e bëri atë në bordi, sepse është më e lehtë për të parë jo duke u përpjekur për të zoom në në Rregullues. A ka që e bëjnë kuptim për të gjithë? Ftohtë. 

Në rregull. Ne mund të lëvizin për folur për simbol asymptotic, e cila është vetëm një mënyrë e sofistikuar për të thënë se runtimes të gjitha këto llojet. Kështu që unë e di Davidin, në leksion, preken runtimes. Dhe ai kalonte nëpër tërë formule se si për të llogaritur runtimes. Nuk shqetësohet për këtë. Nëse jeni të vërtetë kurioz se si funksionon kjo, të ndjehen të lirë për të biseduar me mua pas seksion. Ne mund të ecin nëpër formula së bashku. Por të gjithë ju djema duhet të vërtetë di është se n katror mbi 2 është e njëjta gjë si n katror. Për shkak të numrit më të madh, eksponenti, rritet më. Dhe kështu për qëllimet tona, të gjithë ne lidhje me kujdes është se numri gjigant që është në rritje. 

Pra, çfarë është rasti më i mirë Runtime e përzgjedhjes lloj? Nëse ju jeni do të ketë të iterate nëpër një listë dhe pastaj iterate nëpër pjesa tjetër e kësaj liste, Sa herë janë ju do të ndoshta, në case-- më e keqe në më të mirë rast, sorry-- drejtuar përmes? Ndoshta pyetja më e mirë është të pyesni, çfarë është rasti më i keq Runtime e përzgjedhjes lloji. Audienca: katror n. ANDI Peng: Është katror n, e drejtë. Pra, një mënyrë e thjeshtë për të menduar e kjo është si, çdo herë që ju keni dy mbivendosur për sythe, ajo do të jetë katror n. Sepse jo vetëm që janë të kalon nëpër një herë, ju keni për të shkuar mbrapa përreth dhe të drejtuar nëpërmjet saj edhe një herë brenda për çdo vlerë. Pra, në këtë rast, ju jeni duke n herë n katror, ​​e cila is-- vjen keq, n herë n, e cila është e barabartë me katror n. 

Dhe lloj është edhe pak unik në kuptimin se kjo nuk ka rëndësi nëse këto Vlerat janë tashmë në mënyrë. Është ende do të vazhdojë deri anyways. Le të thonë se kjo ishte 1, 2, 3, 4. Pavarësisht nëse apo jo ajo ishte në mënyrë, ai ende do të kishte vrapoi nëpër dhe ende kontrolluar vlerën minimale. Ajo do të kishte bërë Numri i njëjtë i kontrolleve çdo herë të vetme, edhe në qoftë se ajo ka të vërtetë nuk prek asgjë. 

Pra, në një rast të tillë, më të mirë dhe më të keq runtimes të vërtetë janë ekuivalente. Pra, runtime pritet e përzgjedhjes lloji, të cilat ne të caktojë nga simboli i theta, theta, në këtë rast, gjithashtu do të jetë katror n. Të tre këto do të jetë katror n. Është kushdo qartë pse runtime është katror n? 

Në rregull. Kështu që unë jam vetëm do të shpejt të drejtuar përmes pjesës tjetër të llojet. Algorithm për flluskë sort-- kujtohet, kjo ishte e para Davidi kaloi në leksion. Në thelb, ju hap me anë të të gjithë lista dhe ju swap-- ju vetëm krahasuar dy në një kohë. Dhe në qoftë se një është më e madhe, se ju vetëm të bie në ujdi tyre. Pra, nëse këto janë më të mëdha, ju do të bie në ujdi. Kam zyrtar të drejtë këtu. 

Pra, le të them vetëm ju kishte 8, 6, 4, 2. Ju do të krahasoni 8 dhe një 6. Ju do të duhet të bie në ujdi tyre. Ju do të krahasoni 8 dhe një 4. Ju do të duhet të bie në ujdi tyre. Nëse ju duhet të bie në ujdi 8 dhe 2, të ndryshuar ato si. Pra, në një kuptim të tillë, ju mund të shihni, luajtur gjatë një periudhe të gjatë kohore, si lloj vlerat e flluskë në fundet, e cila është arsyeja pse ne e quajmë atë lloj flluskë. 

Ne vetëm do të drejtuar përmes përsëri në kalojë jonë e dytë, dhe të kalojë ynë i tretë, dhe të kalojë ynë i katërt. Në thelb, flluskë lloj vetëm shkon derisa ju nuk do të bëjë ndonjë këmbime më shumë. Pra, në këtë kuptim, kjo është vetëm pseudokod i përgjithshëm për të. Nuk shqetësohet, të gjitha këto do të jetë online. Ne nuk duhet të vërtetë të shkuar mbi këtë. 

Ne vetëm nisja një kundër variabël që fillon në 0. Dhe ne iterate nëpër tërë rrjet. Dhe në qoftë se një vlerë is-- nëse kjo vlerë është më e madhe se vlera, ju jeni do të bie në ujdi tyre. Dhe atëherë ju jeni vetëm duke shkuar për të do të mbajë. Dhe ju jeni duke shkuar për të numëruar. Dhe ju jeni vetëm do të vazhdojmë të bëjmë kjo ndërsa counter është më i madh se 0, që do të thotë se çdo herë që ju duhet të bie në ujdi, ju e dini që ju doni të shkoni mbrapa dhe kontrolloni përsëri. Ju dëshironi të mbani kontrollin deri sa ju e dini që ju nuk duhet të bie në ujdi më. 

Pra, çfarë janë më të mirë dhe më të keq Rasti runtimes për flluskë lloj? Dhe hint-- kjo është në fakt e ndryshme nga lloji përzgjedhjes në kuptimin që këto dy përgjigjet nuk janë të njëjta. Mendoni se çfarë do të ndodhte në një rast në qoftë se ajo është renditur tashmë. Dhe mendoni se çka do të ndodhte në qoftë se ajo ishte e ne rastin ku nuk është renditura. Dhe ju mund të lloj të kandidojë përmes pse kjo po ndodh. Unë do të ju jap djema, si, 30 sekonda për të menduar për këtë. 

NE RREGULL. A ka dikush me mend në çfarë Rasti Runtime keqja e flluskë lloj është? Po. 

Audienca: A do të jetë, si, n herë n minus 1 ose diçka të tillë? Si, sa herë që shkon, kjo është vetëm, si, një shkëmbim më pak se çfarëdo qoftë ajo ishte. 

ANDI Peng: Yeah, kështu që ju jeni plotësisht të drejtë. Dhe ky është një rast në të cilin tuaj Përgjigja ishte në fakt më komplekse se ajo duhet të japë. Kështu ajo do të run-- unë jam duke shkuar për të fshirë të gjitha këto këtu. Është e të gjithë mirë? A mund të fshihet kjo? NE RREGULL. Ju jeni do të vazhdojë deri n herë herë të parë, e drejtë? Dhe ata do të vazhdojë deri n minus 1 për herë të dytë, e drejtë? Dhe pastaj ju do të jeni për të mbajtur shkuar, n miniera 2, e të tjera. Davidi e bëri këtë në një leksion, ku, në qoftë se ju shtuar të gjitha këto vlera, që ju të merrni diçka që është like-- yeah-- mbi 2, e cila në thelb vetëm zvogëlon deri n katror. Ju jeni do të merrni një fraksion i çuditshëm në atje. Dhe kështu vetëm e di se n katror gjithmonë merr përparësi mbi fraksionin. Dhe kështu në këtë rast, më e keqja Runtime do të jetë katror n. Në qoftë se kjo ishte në rend zbritës rendit, mendoni, ju duhet të bëjë një shkëmbim çdo herë të vetme. 

Çfarë do të jetë, potencialisht, rasti më i mirë runtime? Le të them vetëm, në qoftë se lista ishte tashmë në mënyrë që, çfarë do të jetë runtime? 

Audienca: n. ANDI Peng: Është n, pikërisht. Dhe pse është kjo n? Audienca: sepse ju vetëm duhet të kontrolloni në çdo herë. ANDI Peng: Pikërisht. Pra, në kohën e duhur të mirë të mundshme, në qoftë se kjo listë ishte tashmë sorted-- le të themi 1, 2, 3, 4-- ju thjesht do të shkojnë nëpër, ju do të shikoni, ju do të shihni, oh, ata të gjithë nxjerr. Unë nuk duhet të bie në ujdi. Mbarova. Pra, në këtë rast, kjo është vetëm n ose numri i hapave ju vetëm kishte për të kontrolluar në listën e parë. 

Dhe pas, ne tani hit lloj futje, ku algoritmi është në thelb për të ndarë ajo në një pjesë të renditura dhe të pandara. Dhe pastaj një nga një, vlerat Unsorted janë futen në të përshtatshme të tyre pozitat në fillim të listës. 

Kështu për shembull, ne kemi një lista e 3, 5, 2, 6, 4 herë. Ne e dimë se kjo është aktualisht Unsorted sepse ne kemi vetëm filloi duke kërkuar në atë. Ne kemi marrë një sy dhe ne e dimë se vlera e parë është renditur, e drejtë? Në qoftë se ju jeni vetëm në kërkim në një grup të një madhësi, ju e dini se është e renditura. 

Pra, atëherë ne e dimë se katër të tjera janë Unsorted. Ne do të shkojmë nëpër dhe ne e shohim këtë vlerë. Le të kthehemi. Shih se vlera e 5? Ne kemi marrë një vështrim në atë. Ne krahasojnë atë me 3. Ne e dimë se kjo është më e madhe se 3, kështu që ne e dimë se kjo është renditura. Pra, ne tani e dimë se dy të parat janë të renditura dhe tre të fundit nuk janë. 

Ne kemi marrë një vështrim në 2. Ne së pari të kontrolloni atë me 5. A është më pak se 5? Nuk është. Pra, ne duhet të mbajnë në kërkim poshtë. Pastaj ju shikoni 2 off 3. A është më pak se? Jo. Pra, ju e dini se një 2 duhet të futet në pjesën e përparme dhe 3 dhe 5 të dy duhet të jetë shtyrë jashtë. A kjo përsëri me 6 dhe 4. Dhe ne vetëm i mbajnë kontrollin në thelb, ku ne vetëm kontrolloni, kontrolloni, kontrolloni. Dhe derisa kjo është në të djathtë pozicion, ne lloj i vetëm futur atë në pozitën e drejtë, i cili është ku emri i saj erdhi nga. 

Pra, kjo është vetëm algorithm, pseudokod në vetvete, lloj, se si ne do të zbatojë një lloj futje. Pseudokod është këtu. Kjo është e gjitha në internet. Nuk shqetësohet nëse ju djema janë duke u përpjekur të kopjoni këtë poshtë. Pra edhe një herë, njëjtë question-- çfarë do të jetë më e mirë dhe më të këqija runtimes për futje lloj? Është shumë e ngjashme me pyetjen e fundit. Unë do të ju jap djema, si, 30 sekonda për të menduar për këtë si edhe. 

OK A ka dikush doni të më jep Runtime të keq? Po. 

Audienca: katror n. 

ANDI Peng: Është katror n. Dhe pse është katror n? 

Audienca: Sepse në mënyrë të kundërt, ju keni për të shkuar nëpër kohë n n, e cila is-- ANDI Peng: Po, pikërisht. Pra, e njëjta gjë si në lloj flluskë. Nëse kjo listë është në rend zbritës, ju jeni do të duhet të kontrolloni herë të parë. Dhe pastaj me çdo Vlera shtesë, ju jeni do të duhet për të kontrolluar atë kundër çdo vlerë e vetme, e drejtë? Dhe kështu krejt, ju do të jeni për të bërë Pasimi n herë tjetër n kalojnë, e cila është katror n. Po në lidhje me rastin më të mirë? Po. 

Audienca: n minus 1, sepse i pari është katror tashmë. 

ANDI Peng: Pra, të ngushtë. Përgjigja është në fakt n. Sepse, ndërsa i pari është renditura, ajo nuk mund të actually-- atë ne vetëm pati fatin që, në se shembulli, se 2 ka ndodhur të jetë numër më i vogël. Por kjo nuk do të jetë gjithmonë rasti. Nëse 2 është renditur tashmë në fillim por ju shikoni dhe ka një 1 këtu, në 1 do të përplasem atë. Dhe kjo do të përfundojë duke u bumped anyways. 

Pra, në rastin më të mirë, kjo është në fakt vetëm do të jetë n. Nëse kanë 1, 2, 3, 4, 5, 6, 7, 8, ju jeni duke shkuar për të drejtuar përmes se gjithë listën dikur për të kontrolluar për të parë nëse çdo gjë gjobës së. Është e të gjithë të qartë në drejtimin kohët e përzgjedhjes si? Unë e di unë jam duke shkuar nëpër këto të vërtetë të shpejtë. Por vetëm e di se në qoftë se ju e dini koncepte të përgjithshme, ju duhet të jetë mirë. NE RREGULL. Kështu që unë vetëm do të ju jap djema ndoshta, si, një minutë për të biseduar me fqinjët tuaj në atë që janë vetëm disa nga dallimet kryesore në mes të këtyre llojeve të terezi. Ne do të shkojnë mbi atë së shpejti. Audienca: Oh, OK. ANDI Peng: Po. NE RREGULL. Cool, le të mblidhen si një klasë. NE RREGULL. Pra, kjo ishte lloj i një pyetje me fund të hapur, në kuptimin se ka shumë përgjigje për to. Dhe ne do të shkoj për disa prej tyre shkurtimisht. Unë vetëm të kërkuar për të marrë ju djema duke menduar për atë diferencuar të tre llojet e llojeve. Dhe dëgjova, gjithashtu, një i madh question-- çfarë do të bashkojë lloj bëj? Pyetje e madhe, sepse kjo është ajo që ne jemi duke mbuluar të ardhshëm. 

Pra bashkojë lloj është një lloj që funksionon shumë ndryshe nga llojet e tjera. Siç ju djema mund të see-- bëri Davidi bërë këtë demo ku ai kishte të gjitha të ftohur zhurmat e duke parë se si të bashkohen lloj vrapoi, si, pafundësisht më shpejt se të dy llojet e tjera? NE RREGULL. Pra, kjo është për shkak shkrihen lloj zbaton që ndajnë dhe të pushtuar konceptin që ne kemi biseduar rreth një shumë në leksion. Në këtë kuptim që ne si të punojmë zgjuar, jo më shumë, kur ju ndani dhe të pushtuar probleme, dhe thyejnë ato poshtë, dhe pastaj të vënë ata së bashku, gjërat e mira ndodhin gjithmonë. 

Kështu mënyrë që bashkohen lloj thelb punon është se ajo ndan një array Unsorted në gjysmë. Dhe pastaj ai e mori dy gjysmave të vargjeve. Dhe vetëm ajo i klasifikon ato dy pjesët. Vetëm ajo mban e ndarë në gjysmë, në gjysmë, në gjysmë derisa çdo gjë është renditur dhe pastaj Recursively vë atë të gjithë së bashku. 

Pra, kjo është me të vërtetë abstrakte. Pra, kjo është vetëm një grimë e pseudokod. A ka kuptim që në mënyrën se si ajo është drejtimin? Pra, le të them vetëm se ju keni një sërë elementesh n, e drejtë? Nëse n është më pak se 2, ju mund të kthehet. Sepse ju e dini se në qoftë se ka vetëm një gjë, ajo duhet të ndahen. Tjetër, ju lloj gjysmën e majtë, dhe pastaj ju lloj gjysmën e djathtë, dhe pastaj ju bashkojë. 

Kështu, ndërsa kjo duket me të vërtetë e lehtë, në të vërtetë, duke menduar në lidhje me të është lloj i vështirë. Sepse ju jeni si, pra, kjo është lloj i konkurrojnë në vetvete. E drejtë? Është kandidon për vete. Pra, në këtë kuptim, David prekur mbi recursion në klasë. Dhe kjo është një koncept ne do të flasim më shumë. Është se kjo, këto dy linja këtu, në fakt është vetëm programi thënë atë për të kandiduar vetë me të dhëna të ndryshme. Pra, në vend se të kandidojë vetë me tërësia e elementeve n, ju mund të thyejnë atë poshtë në gjysma e majtë dhe gjysma e drejtë dhe pastaj të drejtuar atë përsëri. 

Dhe pastaj ne do të shohim në atë shikimi, sepse unë jam një nxënës vizual. Ajo punon më mirë për mua. Pra, ne do të shikojmë një shembull vizual këtu. 

Le të themi se kemi një rrjet, gjashtë elemente, 3, 5, 2, 6, 4, 1, jo renditura. Të gjithë të drejtë, nuk është një shumë në këtë faqe. Pra, në qoftë se ju djema mund të shikoni në hapi i parë këtu, 3, 5, 2, 6, 4, 1, ju mund të ndarë atë në gjysmë. Të ketë 3, 5, 2, 6, 4, 1. Ju e dini se këto aren't-- ju nuk e di nëse ata janë të renditura ose jo, kështu që ju mbani thyer ato, në gjysmë, në gjysmë, në gjysmë, deri në fund, ju keni vetëm një element. Dhe një element është renditur gjithmonë, e drejtë? 

Në mënyrë që të di se 3, 5, 2, 4, 6, 1, me veten e tyre, janë të renditura. Dhe tani ne mund të vënë ato përsëri së bashku. Pra, ne e dimë 3, 5. Ne kemi vënë ata së bashku. Ne e dimë se është e renditura. Të 2 është ende atje. Ne mund të vënë 4 dhe 6 së bashku. Ne e dimë se kjo është renditura, kështu që ne kemi vënë së bashku se. Dhe 1 është atje. 

Dhe pastaj ju vetëm shikoni në këto dy gjysmat e drejtë këtu. Ke 3, 5, 2, 2, 3, 5. Ju mund të krahasoni vetëm fillimi i çdo gjëje. Sepse ju e dini se kjo është renditur dhe ju e dini se që është renditura. Pra, atëherë ju nuk duhet edhe të krahasoni 5, ju vetëm krahasoni 3. Dhe 2 është më pak se 3, kështu që ju e dini se 2 duhet të shkoni në fund. 

E njëjta gjë atje. Në 1 duhet të shkoni këtu. Dhe pastaj kur ju shkoni për të vënë këto dy vlera së bashku, ju e dini se kjo është renditur dhe ju e dini se kjo është e renditura. Pra, atëherë 1 dhe 2, 1 është më pak se 2. Kjo ju tregon se 1 duhet të shkojnë në fund të kësaj edhe pa e kërkuar në 3 ose 5. Dhe pastaj 4, ju mund vetëm kontrolloni, ajo shkon drejtë në këtu. Ju nuk duhet të shikoni në 5. E njëjta gjë me 6. Ju e dini që 6-- ajo vetëm nuk ka nevojë që të shikohen. 

Dhe kështu në këtë mënyrë, ju jeni vetëm kursim veten shumë hapa, kur ju jeni duke krahasuar. Ju nuk keni për të krahasuar çdo element kundër elementeve të tjera. Ju vetëm krahasoni kundër atyre se ju duhet të krahasojnë atë kundër. Pra, kjo është lloj i një koncept abstrakt. Nuk shqetësohet nëse kjo nuk është mjaft të goditur të drejtë ende. Por në përgjithësi, kjo është si një lloj bashkojë punon. Pyetje, pyetje të shpejtë, para se të lëvizë? Po. 

Audienca: Pra, ju tha se ju merrni 1, dhe pastaj 4 dhe 6 dhe vënë ato në. Pra, nuk janë those-- nuk janë ju në kërkim të tyre si elemente të veçanta, jo si tërësi? ANDI Peng: Po. Pra, çfarë po ndodh është se ju në thelb janë duke krijuar një koleksion të ri fringo. Pra, ju e dini se, këtu, unë kam dy vargjeve të madhësisë 3, e drejtë? Pra, ju e dini se array tim renditura duhet të ketë gjashtë elemente. Kështu që ju vetëm të krijojë një Shuma e re e kujtesës. Pra, ju jeni lloj i si duke qenë të kota e kujtesës, por kjo nuk ka rëndësi sepse është kaq i vogël. Kështu që ju shikoni në 1 dhe ju shikoni në 2. Dhe ju e dini se 1 është më pak se 2. Pra, ju e dini se 1 duhet të shkojnë në fillimi i të gjithë atyre. 

Ju nuk keni nevojë edhe për të shikoni në 3 dhe 5. Pra, ju e dini se 1 shkon atje. Pastaj ju në thelb pres off 1. Është, si, të vdekur për ne. Atëherë ne vetëm duhet 2, 3, 5, dhe pastaj 4 dhe 6. Dhe pastaj ju e dini se, ju krahasojnë 4 dhe 2, oh, e 2 duhet të shkojnë në atje. Pra, ju pllum e 2 poshtë, ju pres atë. Pra, atëherë ju vetëm duhet të 3 dhe 5 në 4 dhe 6. Dhe ju vetëm i mbajnë shëndoshë atë deri sa ju vënë ato në rrjet. 

Audienca: Pra, ju jeni vetëm gjithmonë krahasuar [e padëgjueshme]? 

ANDI Peng: Pikërisht. Pra, në këtë kuptim, ju jeni vetëm krahasuar, në thelb, një numër kundrejt numrit tjetër. Dhe për shkak se ju e dini se ajo është renditur, ju nuk kanë për të parë përmes të gjithë numrat. Ju vetëm duhet të shikoni në një të parë. Dhe atëherë ju vetëm mund të pllum ata poshtë, sepse ju e dini ata i përkasin, ku ata duhet të takojnë. Po. Pyetje e mirë. 

Dhe pastaj në qoftë se ndonjë nga ju janë pak ambicioz, të ndjehen të lirë për të parë në këtë kod. Kjo është në fakt zbatimi fizik se si ne do të shkruaj bashkojë lloj. Dhe ju mund të shihni, kjo është shumë e shkurtër. Por idetë prapa ajo janë mjaft komplekse. Pra, nëse ju ndjeheni si duke tërhequr këtë jashtë në sonte tuaj detyrave të shtëpisë, të ndjehen të lirë për të. 

NE RREGULL. Kështu Davidi shkoi mbi këtë në leksion. Cilat janë rasti më i mirë runtimes, runtimes më të keq, dhe runtimes pritshme të merge lloji? Një çift sekonda për të menduar. Kjo është shumë e vështirë, por lloji i intuitive në qoftë se ju mendoni rreth saj. Në rregull. 

Audienca: A është rasti më i keq n log n? ANDI Peng: Pikërisht. Dhe pse është n log n. 

Audienca: Nuk është kjo për shkak të bëhet në mënyrë eksponenciale më të shpejtë, kështu që është si një funksion të që në vend që thjesht të qenit n katror apo diçka? ANDI Peng: Pikërisht. Pra, arsyeja pse Runtime për këtë është log n n është because-- çfarë jeni bërë në të gjitha këto hapa? Ju jeni vetëm i shëndoshë atë në gjysmë, e drejtë? Dhe kështu, kur ne jemi duke bërë log, të gjitha që është e bërë është duke e ndarë një problem në gjysmë, në gjysmë, në gjysmë, në më shumë pjesë. Dhe në këtë kuptim, ju mund të lloj të eliminuar modelin linear që ne kemi qenë duke përdorur. Sepse kur ju pres gjërat në gjysmë, kjo është një log. Kjo është vetëm matematikore Mënyra e përfaqëson atë. 

Dhe pastaj në fund, në fund, ju jeni vetëm duke bërë një të kalojë përmes të fundit për të vënë të gjitha prej tyre në mënyrë, e drejtë? Dhe kështu që në qoftë se ju vetëm duhet të kontrolloni një gjë, kjo është n. Dhe kështu që ju jeni lloj i shumëzuar dy së ​​bashku. Pra, kjo është si ju keni marrë atë përfundimtar kontrolloni për N poshtë këtu me një regjistër të n deri këtu. Dhe nëse ju shumohen ata, që është n log n. 

Dhe kështu rasti më i mirë dhe më të keq rast dhe pritet që janë të gjithë n log n. Është gjithashtu si një tjetër lloji. Është si përzgjedhjes lloj në kuptimin që ajo nuk ka rëndësi se çfarë tuaj Lista është, ajo është vetëm duke shkuar për të bërë të njëjtën gjë çdo herë të vetme. NE RREGULL. Pra, si ju djema mund të shohim, edhe pse Llojet që ne kemi shkuar through-- n katror, ​​kjo nuk është shumë efikas. Dhe, edhe kjo log n n është jo më efikase. Nëse ju djema janë kurioz, nuk ka mekanizma lloj që janë aq të efektshme që ata janë pothuajse në thelb banesë në kohën e duhur. 

Ju keni marrë disa log n-së. Ju keni marrë disa log n log. Ne nuk prek mbi ta në këtë klasë të drejtë tani. Por në qoftë se ju djema janë kurioz, të ndjehen të lirë për të google, çfarë është mekanizmat më efikase klasifikim. Unë nuk e di, ka disa nga ato me të vërtetë qesharake, like-- ka disa me të vërtetë ato qesharake që njerëzit bëjnë. Dhe ju pyes veten se si ata menduar ndonjëherë për këtë. Pra google, në qoftë se ju keni disa rezervë kohë, në, çfarë janë disa mënyra qesharake që people-- si edhe njerëz efikase ways-- kanë qenë në gjendje të zbatojë llojet. NE RREGULL. Dhe këtu është vetëm një tabelë dobishëm pak. Unë e di se të gjithë ju, para se të quiz 0, do të jetë në dhomën tuaj ndoshta duke u përpjekur për të mësuar përmendësh atë. Pra, kjo është e bukur në atje për ju djema. Vetëm mos harroni logjikën që made-- pse ato numra ishin ndodhin. Nëse ju jeni të humbur gjithmonë, vetëm të bëjë i sigurt që ju e dini se çfarë llojet janë. Dhe ju mund të vazhdojë deri ata në mendjen tuaj të kuptoj se pse ata Përgjigjet janë këto përgjigje. 

Në rregull. Pra, ne jemi duke shkuar për të lëvizur në, më në fund, në kërkim. Sepse si ato prej jush të cilët e kanë lexuar pset, kërkim është edhe pjesë e Problemi kësaj jave përcakton. Ju do të kërkohet për të zbatuar dy lloje të kërkimeve. Njëra është një kërkim linear dhe një është një kërkim binar. 

Pra, kërkimi linear është mjaft e lehtë. Ju vetëm dëshironi të kërkoni element e një liste për të parë nëse ju merrni atë. Ju thjesht duhet të iterate nëpër. Dhe në qoftë se ajo është e barabartë me diçka, ju vetëm mund të kthejë atë, e drejtë? Por ai që ne jemi më të interesuar në duke folur për është search binar, e drejtë, që është të ndarë dhe të mekanizmit të pushtuar që Davidi u demonstruar në leksion. 

Mos harroni shembullin librin e telefonit se ai vazhdon të sjellë lart, ai që ai lloj i luftuan pak në këtë vit të kaluar, ku ju ndani problemin në gjysmë, në gjysmë, në gjysmë, përsëri dhe përsëri, derisa ju të gjeni atë që ju po kërkoni? Dhe ju keni marrë Runtime e se si. Dhe ju mund të shihni, është në mënyrë të konsiderueshme më të efektshme se çdo lloj tjetër të kërkimit. 

Pra, mënyra se si ne do të shkojnë për zbatimin e një kërkim binar është, nëse do të kishim një rrjet, indeks 0 në 6, shtatë elementë, ne mund të shikojmë në mes, right-- keq, në qoftë se pyetjes sonë first-- në qoftë se ne duam të kërkojë pyetjen e, bën array përmbajnë elementin e 7, natyrisht, duke qenë njerëzit, dhe duke pasur tillë një grup i vogël, është e lehtë për ne për të thënë po. Por mënyra për të zbatuar një binar Kërkimi do të jetë për të parë në mes. 

Ne e dimë se indeksi 3 është e mesme, sepse ne e di se ka shtatë elemente. Çfarë 7 ndarë nga 2? Ju mund të pres jashtë se Extra 1. Ju keni marrë 3 në mes. Pra, është grup i 3 barabartë me 7? Kjo nuk është, apo jo? Por ne mund të bëjë një çift të kontrolleve. Është grup i 3 më pak se 7 ose është grup i 3 më i madh se 7? 

Dhe ne e dimë se kjo është më pak se 7. Pra, ne e dimë se, oh, ajo duhet të të mos jetë në gjysmën e majtë. Ne e dimë se ajo duhet të jetë në gjysmën e djathtë, e drejtë? Pra, ne vetëm mund të pres jashtë gjysmën e array. Ne nuk kemi as të shikojnë atë më. Sepse ne e dimë se gjysma e problem-- tonë ne e dimë se përgjigja është në gjysma e drejta e problemit tonë. Pra, ne vetëm shikoni në atë tani. 

Deri tani ne shikojmë në mes të asaj që ka mbetur. Se indeksi 5. Ne bëjmë të njëjtën kontroll përsëri dhe ne e shohim se kjo është më e vogël. Pra, ne shikojmë në të majtë të kësaj. Dhe pastaj ne e shohim këtë kontroll. Është vlera array në indeks 4 barabartë me 7? Eshte. Pra, ne mund të kthehen vërtetë, sepse kemi gjetur vlerën në listën tonë. A mënyrën se unë shkova me që kanë kuptim për të gjithë? NE RREGULL. Unë do të ju jap djema ndoshta, si, tre, katër minuta për të kuptoj se si ta pseudokod këtë në. 

Pra, imagjinoni I pyetur ju për të shkruar një Funksioni i quajtur kërkimit () që u kthye një vlerë, një vlerë Boolean, kjo ishte e vërtetë apo false-- si, e vërtetë në qoftë se ju gjetur Vlera, false në qoftë se ju nuk e keni. Dhe pastaj ju ishit kaloi në vlerën e ju janë në kërkim për në vlera, të cilat është array-- oh, unë patjetër vënë që në vendin e gabuar. NE RREGULL. Anyways, që duhet të ketë qenë në të djathtë e vlerave. Dhe pastaj int n është numri i elementeve në atë rrjet. Si do të ju shkoni në lidhje me duke u përpjekur të pseudokod këtë problem në? Unë do të ju jap djema si tre minuta për të bërë këtë. Jo, unë mendoj se ka only-- Po, ka një të drejtë deri këtu. Audienca: A mund unë? ANDI Peng: Po, kam marrë ju. A është kjo pune? OK, i ftohtë. 

NE RREGULL. Të gjitha djema drejtë, ne jemi duke shkuar për të frenuar atë në. NE RREGULL. Pra, supozojmë ne kemi marrë kjo bukuroshe pak grup me vlerat n në të. Unë nuk e kam nxjerrë linja. Por si do të shkojmë në lidhje duke u përpjekur për të shkruar këtë? A ka dikush duan të më jep vijën e parë? Nëse ju doni të jepni vija e parë e këtij pseudokod. 

Audienca: [padëgjueshme] Audienca: Ju do të doni të iterate through-- Audienca: Vetëm një tjetër për lak? Audienca: --for. 

ANDI Peng: Pra, kjo është pak i ndërlikuar. Mendoni? Për ju doni për të mbajtur drejtimin e këtij loop pa pushim deri kur? 

Audienca: Deri në [e padëgjueshme] vlerë është e barabartë me atë vlerë. ANDI Peng: Pikërisht. Kështu që ju mund të vërtetë vetëm write-- ne mund edhe të thjeshtojë atë më. Ne mund të bëjë vetëm një lak, ndërsa, e drejtë? Kështu që ju mund të ketë vetëm loop-- ne e dimë se kjo është një kohë. Por për tani, unë jam duke shkuar të thonë "lak" - me çfarë? Loop until-- ajo që është gjendja jonë i dhënë fund? Unë mendoj se kam dëgjuar atë. Kam dëgjuar dikë të thotë atë. 

Audienca: Vlerat e barabartë qendër. ANDI Peng: Thuaj atë përsëri. Audienca: Ose, derisa Vlera e ju jeni në kërkim për të është e barabartë me vlerën e mesme. 

ANDI Peng: Çfarë ndodh nëse nuk është në atje? Çfarë nëse vlera ju jeni në kërkim sepse nuk është në fakt në këtë grup? Audienca: Ti kthehen 1. 

ANDI Peng: Por ajo që duam të lak derisa në qoftë se ne kemi një gjendje? Po. 

Audienca: Derisa ka vetëm një vlerë? ANDI Peng: Ju mund të loop until-- kështu që ju e dini që ju jeni do të ketë një vlerë max, e drejtë? Dhe ju e dini se ju do të jeni të ketë një vlerë min, apo jo? Sepse ashtu, kjo është diçka Kam harruar të them më parë, kjo diçka që është kritik për kërkimin binar është se grup juaj është renditur tashmë. Sepse nuk ka asnjë mënyrë për të bërë kjo nëse ata janë vlera të vetëm të rastit. Ju nuk e dini nëse dikush është më i madh se tjetri, e drejtë? 

Pra, ju e dini se max tuaj dhe min tuaj këtu, apo jo? Nëse ju do të jeni të përshtatur max juaj në minuta tuaja dhe mid-- le të supozojmë tuaj Vlera e mesit është here-- e drejtë ju jeni do të në thelb lak deri minimale juaj është pothuajse i njëjtë si max juaj, të drejtë, ose nëse max juaj nuk është i njëjtë si min tuaj. E drejtë? Sepse kur kjo ndodh, ju e dini se ju përfundimisht keni goditur të njëjtën vlerë. Pra, ju doni të lak deri min tuaj është më pak se ose e barabartë to-- Oops, jo me pak se ose te barabarte me, mënyra të tjera around-- max është. 

E që të bëjnë kuptim? Kam marrë një përpiqet pak për të marrë atë të drejtë. Por lak deri vlerën tuaj max është në thelb pothuajse më pak se ose e barabartë me minimum tuaj, apo jo? Kjo është kur ju e dini që e keni converged. Audienca: Kur do maksimale juaj Vlera të jetë më pak se minimumi? ANDI Peng: Në qoftë se ju mbani përshtatur atë që është ajo që ne jemi duke shkuar të jetë bërë në këtë. A ka kjo kuptim? Minimale dhe max janë vetëm integers se ne jemi ndoshta do të duan të krijojnë të mbajnë gjurmët e ku ne jemi duke kërkuar. Sepse array ekziston pavarësisht se çfarë jemi duke bërë. Si, ne nuk jemi në fakt fizikisht kishte prerë grup, e drejtë? Ne jemi vetëm rregullimin ku ne jemi duke kërkuar. A ka kjo kuptim? 

Audienca: Po. 

ANDI Peng: OK. Pra, nëse kjo është kusht për lak tonë, Çfarë duam brenda këtij lak? Çfarë do të shkojmë për të dashur për të bërë? Deri tani, ne kemi marrë një max dhe një min, e drejtë, ndoshta e krijuar deri këtu diku. Ne jemi duke shkuar për të ndoshta dëshironi për të gjetur një e mesme, të drejtë? Si do të jetë gjendje për të gjetur e mesme? Çfarë është mathematical-- Audienca: Max Plus min ndarë nga 2. ANDI Peng: Pikërisht. A ka kjo kuptim? Dhe ju djema shoh pse ne nuk ka vetëm use-- pse ne e bëmë këtë në vend të bërë vetëm n ndarë nga 2? Kjo është për shkak se n është një vlerë që do të mbetet e njëjtë. E drejtë? Por si ne të rregullojë minimale tonë dhe Vlerat maksimale, ata do të ndryshojë. Dhe si rezultat, të mesëm ynë do të ndryshojë shumë. Pra, kjo është arsyeja pse ne duam për të bërë këtë të drejtë këtu. NE RREGULL. 

Dhe pastaj, tani që ne kemi gjetur our-- vërtet. 

Audienca: Vetëm një question-- shpejtë kur ju thoni min dhe max, jemi duke supozuar se kjo është renditur tashmë? 

ANDI Peng: Po, kjo është në fakt një parakusht për një kërkim binar, që ju duhet të dini është e renditura. Cila është arsyeja pse lloj, ju shkruani në tuaj Problemi vënë përpara kërkimin tuaj binar. NE RREGULL. Pra, tani që ne e dimë se ku midpoint ynë po, çfarë ju doni të bëni këtu? 

Audienca: Ne duam për të krahasuar që në një tjetër. ANDI Peng: Pikërisht. Pra, ju jeni duke shkuar për të krahasuar në mes të vlerës, e drejtë? Dhe çfarë do të thoni Na kur krahasojmë? Çfarë duam të bëjmë më pas? 

Audienca: Nëse vlera është më e madhe sesa mesi, ne duam ta preje. ANDI Peng: Pikërisht. Pra, nëse vlera është më e madhe sesa mesi, ne jemi do të duan të ndryshojnë këto maxes minimale dhe, e drejtë? Çfarë duam të ndryshojë? Pra, nëse ne e dimë se vlera është diku në këtu, çfarë ju që të ndryshojë? Ne duam të ndryshojmë tonë minimale të jetë në mes, e drejtë? Dhe pastaj tjetër, në qoftë se është në këtë gjysmë, çfarë ne duam të ndryshojmë? 

Audienca: maksimumi juaj. ANDI Peng: Po. Dhe pastaj ju jeni vetëm duke shkuar për të mbajtur looping, e drejtë? Sepse tani, pas një përsëritje përmes, ju keni marrë një max këtu. Dhe pastaj ju mund të rillogarisë një mesi. Dhe pastaj ju mund të krahasohen. Dhe ju jeni duke shkuar për të mbajtur vazhdim e sipër deri në minuta dhe maxes kanë konverguar në thelb. Dhe kjo është kur ju e dini se ju keni goditur në fund të tij. Dhe as që ju keni gjetur atë apo ju nuk e keni në atë pikë. 

A ka kjo kuptim për të gjithë? NE RREGULL. Kjo është shumë e rëndësishme, sepse ju do të keni për të shkruar këtë në kodin sonte tuaj. Por ju djema keni një mjaft të mirë kuptim të asaj që ju duhet të bëni, e cila është e mirë. NE RREGULL. Pra, ne kemi marrë për shtatë minuta largua seksion. Pra, ne jemi duke shkuar për të folur për kjo pset që ne do të bëjmë. Pra pset është i ndarë në dy gjysma. Gjysma e parë përfshin zbatimin e një gjeni në të cilën ju shkruani një kërkim linear, një kërko binar, dhe një algoritmi klasifikim. 

Pra, kjo është e para kohë në një pset ku ne do të jetë duke ju djema atë që e quajti Kodin e Shpërndarjes, e cila është kodi që kemi para-shkruar, por vetëm lënë disa pjesë jashtë për ju për të përfunduar shkrimin. Pra, ju djema, kur ju shikoni në këtë Kodi, ju mund të merrni frikësuar me të vërtetë. Nëse ju jeni vetëm pëlqen, Ahh, unë nuk e di se çka e bën, Unë nuk e di, si, që duket aq e komplikuar, AHH, relaksohuni. Eshte mire. Lexoni spekulim. Spekulim do të shpjegojë për ju saktësisht Çfarë të gjitha këto programe janë duke bërë. 

Për shembull, generate.c është një program që do të vijë me pset tuaj. Ju në fakt nuk duhet të prekë atë, por ju duhet të kuptoni se çfarë është bërë. Dhe generate.c, gjithë kjo e bën është ose gjeneruar numra të rastit ose ju mund t'i jepte një farë, si një Numri i paracaktuar që ajo merr, dhe ajo gjeneron më shumë numra. Pra, ka një mënyrë të veçantë për të zbatojnë generate.c në të cilën ju mund të bëni vetëm një bandë e numrave për ju për të testuar metodat tuaja të tjera me radhë. 

Pra, nëse ju të kërkuar për të, për shembull, provoni të gjeni tuaj, ju do të duan për të drejtuar generate.c, të gjenerojë një bandë të numrave, dhe pastaj të drejtuar ndihmues funksionin tuaj. Funksioni i ndihmësit juaj është ajo ku ju jeni në fakt fizikisht shkruar kodin. Dhe të mendojnë për ndihmësve si një file bibliotekës ju jeni me shkrim se gjeni është thirrje. Dhe kështu brenda helpers.c, ju do të të bëjë kërkimin dhe klasifikim. 

Dhe pastaj ju do të jeni në thelb vetëm vënë të gjithë së bashku. Spekulim do të ju tregojnë se si për të vënë atë në rreshtin e komandave. Dhe ju do të jetë në gjendje për të provuar nëse janë apo Nuk lloj juaj dhe kërkimit janë duke punuar. Ftohtë. Ka tashmë ka filluar dikush dhe problemet e hasura ose pyetje ata kanë të drejtë tani me këtë? NE RREGULL. 

Audienca: Prisni. Kam një pyetje. 

ANDI Peng: Po. 

Audienca: Kështu që kam filluar duke bërë Kërkimi lineare në helpers.c dhe kjo nuk ishte me të vërtetë duke punuar. Por pastaj më vonë, unë kuptova që ne vetëm duhet të fshini atë dhe të bëni kërkimin binar. Pra, nuk ka rëndësi nëse ajo nuk punon? 

ANDI Peng: Përgjigje të shkurtër është jo. Por, pasi që ne jemi not-- Audienca: Por askush nuk e në fakt kontrolluar. ANDI Peng: Ne kurrë nuk jemi do të shohim se. Por ju ndoshta dëshironi të bëni i sigurt Kërkimi juaj është duke punuar. Sepse në qoftë se linear juaj Kërkimi nuk funksionon, atëherë shanset janë binare tuaj Kërkimi nuk do të punojë si edhe. Sepse ju keni ngjashme logjikë në dy prej tyre. Dhe jo, kjo nuk ka rëndësi. Pra, të vetmit që do të kthehet në janë lloj dhe kërkimi binar. Po. 

Dhe gjithashtu, shumë fëmijë ishin duke u përpjekur për të hartuar helpers.c. Ju nuk jeni i lejuar në fakt për të bërë këtë, sepse helpers.c nuk kanë një funksion kryesor. Dhe kështu që ju duhet vetëm jetë në të vërtetë përpilimin të gjenerojë dhe për të gjetur, sepse gjeni thirrjet helpers.c dhe funksionet brenda tij. Kështu që e bën debugging një dhimbje në prapanicë. Por kjo është ajo që ne duhet të bëjmë. Audienca: Ju vetëm të bëjë të gjitha, apo jo? ANDI Peng: Ju mund të vetëm të bërë të gjithë si dhe, po. NE RREGULL. Pra, kjo është ajo në drejtim të asaj pset është duke kërkuar që të gjithë ju të bëni. Nëse keni ndonjë pyetje, mos të lirë të pyesni mua pas seksion. Unë do të jem këtu për, si, 20 minuta. 

Dhe vërtet, pset-së me të vërtetë nuk është se e keqe. Ju djema duhet të jetë në rregull. Këto, thjesht ndiqni udhëzimet. Lloji i kanë një ndjenjë të, logjikisht, çfarë duhet të ndodhë dhe ju do të jetë në rregull. Mos të jetë shumë i frikësuar. Nuk është një shumë e kodit shkruar tashmë atje. Mos të jetë shumë i frikësuar në qoftë se ju nuk e bëni të kuptojnë atë që të gjithë e që do të thotë. Në qoftë se kjo është një shumë, kjo është krejtësisht në rregull. Dhe të vijnë në orarit të punës. Ne do të ju ndihmojë të marrë një sy. 

Audienca: Me shtesë funksionet, nuk shohim ato lart? 

ANDI Peng: Po, ata janë në kodin. Në ndeshjen e 15, gjysma e është e shkruar tashmë për ju. Pra, ato funksione janë tashmë në kodin. Yep. Në rregull. E pra, mirë e fat. Kjo është një ditë e pështirë. Pra, shpresojmë se ju djema nuk do të ndjehen shumë keq për të qëndruar brenda dhe kodim.