Gjuha 1: Hey të gjithë! Mirë se vini përsëri në seksion. Aq i kënaqur për të parë kaq shumë nga ju të dy këtu, dhe të gjithë ata që është shikuar online. Pra, si zakonisht mirëpritur mbrapa. Unë shpresoj se ju të gjithë e kishin një bukuroshe fundjavë, plot pushim, relaksim. Ajo ishte e bukur nga dje. Pra, unë shpresoj se ju ka gëzuar jashtë. 

Pra, së pari disa njoftimeve. Nota. Pra, shumica prej jush duhet të ketë marrë një email nga unë në lidhje me Pset tuaj Scratch, si dhe vlerësimi për Pset 1. Pra, vetëm një disa gjëra. Jetë i sigurt për të përdorur check50 në style50. Këto janë menduar të jenë të Burimet për ju djema, për t'u siguruar që ju jeni duke marrë sa më shumë pikë si ju mund të pa pa nevojë humbur ato. Pra, gjëra të tilla si stil janë shumë të rëndësishme. Ne jemi duke shkuar për të marrë jashtë për të. Disa prej jush mund të kenë tashmë vënë re se nga Pset tuaj. Dhe check50 është vetëm një mënyrë me të vërtetë e lehtë për të bërë të sigurtë që ne jemi në fakt kthehej çfarë duhet të kthehen për të përdoruesit, dhe se çdo gjë është duke punuar si duhet. 

Në shënim të dytë, sigurohuni që tuaj ngarkimi gjëra në dosje korrekt. Kjo e bën jetën time të drejtë a pak më e vështirë në qoftë se ju të ngarkoni Pset 2 në Pset 1 sepse kur kam shkarkuar gjëra, ata nuk shkarkohet saktë. Dhe unë e di se është një tundet pak në një sistem për t'u përdorur për të, por vetëm të jetë super kujdesshëm, në qoftë se vetëm për mua, kështu që kur ju jeni duke marrë email në si 02:00 dhe unë jam i gradimit. Nëse jo të shkaktojë unë duhet të shikoni të gjithë rreth e rrotull për Pset tuaj. Ftohtë. 

Unë e di se është herët, por unë krejtësisht u marrë off roje nga një ese që është për shkak se këtë të premte, Profesorët e mi ishin ashtu si, oh yeah. Mbani mend, ju keni një ese për shkak të premten. Kështu që, unë e di se askush nuk i pëlqen të mendojnë për midterms, por quiz juaj e parë është në 15 tetor, e cila tetori filluar nga kjo javë. Pra, ajo mund të jetë më shpejt se ju pritur është mbi të gjitha. Kështu që ju nuk jeni duke hedhur off roje kur I përmend seksionin e javës së ardhshme që oh, quiz javën e tuaj të ardhshëm, mendova Unë do të ju jap një pak më shumë nga një kokat deri tani. 

Pra, problemi juaj vendosur, numri tre. Sa njerëz e kanë lexuar spekulim nga kurioziteti? OK. Ne morëm një çift. Lloji i zbritur nga të fundit javë, por kjo është në rregull. Unë e di se ishte jashtë bukur. Pra Break Out. Definitely pasi ju merrni bërë sot lexuar spekulim tuaj të paktën provoni si shkarkimit Kodi i shpërndarjes dhe drejtimin si fillestar parë gjë që ata të ju pyes për të. Sepse ne jemi duke përdorur Kodi i shpërndarjes dhe një bibliotekë se ne kemi qenë vetëm using-- --It vetëm hera e dytë që ne kemi bërë këtë Pset, gjëra të çmendur mund të ndodhë me pajisjen tuaj, dhe ju doni të gjeni se më tani kundrejt vonë. 

Sepse në qoftë se është e natën e të enjtes, ose është E mërkurë natë dhe për disa arsye pajisja juaj thjesht nuk doni të dalë me bibliotekë ose me shpërndarje kodin, kjo do të thotë ju nuk mund edhe të fillojnë të bëjnë coding. Sepse ju nuk mund të kontrolloni për të parë nëse ajo punon. Nuk gonna të tuaj të jetë në gjendje për të parë nëse ajo harton. Ju dëshironi të kujdeset për ata në fillim javë, kur ju ende mund të email mua ose njëri prej TFS tjera, dhe ne mund të merrni ato fikse. Sepse ato janë çështje që do të ndalojë ty nga bërja e ndonjë përparim të vërtetë. Ajo nuk është si një bug, se ju mund vetëm lloj të kaloni mbi të. Nëse ju jeni ka probleme me tuaj aplikim apo kodin e shpërndarjes, ju doni me të vërtetë të merrni atë bërë kujdeset më shpejt se sa më vonë. Pra, edhe në qoftë se ju nuk jeni gonna të vërtetë fillojnë coding, shkarko shpërndarjes Kodi, lexoni spekulim, sigurohuni çdo gjë është duke punuar atje. OK? Nëse ju mund të bëni vetëm se, unë premtoj jetën tuaj do të jetë më e lehtë. Dhe kështu që ju jeni me siguri do për të bërë atë të drejtë tani të drejtë? OK. Pra, ndonjë pyetje atje? Çdo gjërat logjistike? Gjithkush është e mirë? OK. 

Disclaimer për ata të ju në dhomë dhe online. Unë jam duke shkuar të jetë duke u përpjekur për të kaluar midis PowerPoint në aplikim sepse ne jemi duke shkuar të jetë bërë disa kodim sot nga kërkesa popullore anonim Sondazhi sugjerim I dërguar javën e kaluar. Pra, ne do të bëjmë disa coding. Pra, në qoftë se ju djema të doni të zjarrit deri pajisje tuaj, dhe ju duhet të keni marrë një email nga unë, me një fotografi mostër. Ju lutem mos ngurroni për të bërë këtë. 

Pra, ne do të flasim për GDB, e cila është një debugger. Kjo do të ju ndihmojë lloj të kuptoj se ku gjërat janë duke shkuar keq në kodin tuaj. Kjo është me të vërtetë vetëm një mënyrë për ju për të rritur me kodin tuaj si kjo po ndodh, dhe të jetë në gjendje për të shkruar jashtë variablave ose të shohim se çfarë është në të vërtetë ndodh nën kapuç vargjet programin tuaj vetëm drejtimin, kjo është si përgënjeshtrojnë, dhe ju jeni si, asnjë ide çfarë ka ndodhur vetëm këtu. Unë nuk e di se çfarë linjë dështoi në. Unë nuk e di ku shkoi keq. Pra, GDB do të ju ndihmojë me këtë. Gjithashtu, në qoftë se ju vendosni për të vazhdojnë po, dhe për të marrë 61, ajo do të me të vërtetë, të vërtetë të jetë tuaj shoku më i mirë, shkaku unë mund t'ju them sepse unë jam duke shkuar nëpër atë klasë. 

Ne jemi duke shkuar për të parë në binar kërko, e cila në qoftë se ju djema mbani mend i madh shembull librin e telefonit spektakël nga klasa. Ne do ta zbatojë atë, dhe ecin nëpër atë pak më shumë, dhe pastaj ne jemi duke shkuar nëpër katër llojet e ndryshme, të cilat janë Bubble, Përzgjedhja, hyrjes, dhe bashkojë. Ftohtë. Pra, GDB siç thashë, është një Rregullues. Dhe këto janë lloj i madh gjërat, funksionet mëdha apo komandat që ju përdorni në GDB, dhe unë do të ec ju nëpërmjet një demo e saj në një të dytë. 

Pra, kjo nuk është vetëm do të qëndrojë abstrakte. Unë do të përpiqet dhe të bëjë atë si beton të jetë e mundur për ju djema. Pra, pushim. Ajo do të jetë ose pushim si, disa numër, i cili përfaqëson një linjë në programin tuaj, ose ju mund të emërojë një funksion. Pra, nëse ju thoni pushim kryesor, ai do të ndalet në kryesore, dhe le të ecin nëpër atë funksion. 

Gjithashtu, në qoftë se ju keni disa të jashtëm të funksionojë si Swap apo Cube, që ne të shikuar në javën e kaluar. Në qoftë se ju thoni të shkelë një nga këto, kur programi juaj godet atë, ajo do të presë për ju për të tregoni se çfarë të bëni. Para se ai thjesht do të ekzekutojë në mënyrë të në fakt mund të hap brenda funksionit dhe të shohim se çfarë po ndodh. Pra, Next, vetëm skips gjatë Linja tjetër, shkon mbi funksionet. Hapi. Këto janë të gjitha abstrakte pak. Pra, unë jam vetëm duke shkuar për të drejtuar nëpërmjet tyre, por ju do të shihni ato në përdorim në një të dytë. 

Hapi në një funksion. Pra, siç po thosha, si me Swap, ajo do të ju lejojnë të vërtetë si në qoftë se ju jeni si fizikisht shkelën brenda, ju mund të luajnë me këto variabla, print se çfarë ata janë, shohin se çfarë po ndodh. Lista do të fjalë për fjalë vetëm të shtypura out kodin përreth. Pra, në qoftë se ju lloj i harrojmë ku ju jeni në programin tuaj, ose ju jeni të pyesin çfarë po ndodh rreth tij, kjo vetëm do të shtypura nga një segment i pëlqen pesë ose gjashtë rreshta rreth tij. Pra, ju mund të merrni të orientuar se ku je. 

Print disa ndryshore. Pra, nëse ju keni çelësin si në Cezarit, që ne do të shikojmë në të. Ju mund të thoni Shtyp Key në çdo pikë. Ajo do të ju tregojnë se çfarë vlera është aq se, ndoshta diku përgjatë rrugës, ju mbikaloi kyç tuaj. Ju në fakt mund të them se për shkak se ju në fakt mund të vëzhgojnë atë vlerë. 

Në vendasit, vetëm shtyp out variablave tuaj lokale. Pra, në çdo kohë që ju jeni në një lak, dhe ju vetëm duan të shohin si, oh. Çka është e mia unë? Çfarë është kjo vlerë kryesore që unë nisja këtu? Cili është mesazhi në këtë pikë? Ajo thjesht do të shtypura të gjitha e atyre, në mënyrë që të ju nuk kanë individualisht thonë, Print I. Print mesazh. Print Key. Dhe pastaj Display. Çfarë kjo nuk është si ti hap përmes programit, ajo vetëm do të bëni të sigurtë që kjo është shfaqur disa ndryshore të caktuar në çdo pikë. Kështu që ju also-- --it e lloj i një shkurtore ku ju nuk keni për të mbajtur vazhdim e sipër si, oh. Key Print ose Print I. Ajo vetëm automatikisht do të bëjë atë për ju. 

Pra, me këtë, ne jemi duke shkuar për të parë se si kjo shkon. Unë jam duke shkuar për të përpiqen dhe të kaloni mbi të aparatit tim. Shih nëse unë mund ta bëjë këtë. Të gjithë. Ne jemi vetëm duke shkuar për të pasqyruar atë. Nuk ka asgjë të çmendur në laptop tim anyways. OK. Kjo duhet të jetë kjo. Është kaq e vogël. Le të shohim nëse ne mund të bëjmë këtë. 

OK. Alice është padyshim duke luftuar këtu vetëm pak, por ne do të merrni atë në një momento. OK. Ne jemi vetëm duke shkuar për të rritur këtë. OK. Të gjithë mund të lloj të shihni se? Ndoshta pak? Unë e di se është pak e vogël. Ju nuk mund të mjaft të kuptoj se si për të bërë këtë më të mëdha. Nëse dikush e di. A di ndokush se si për ta bërë atë të mëdha? OK. Ne jemi duke shkuar për të rrokulliset me të. Nuk ka rëndësi anyways, sepse kjo është vetëm kjo është kodi që ju djema duhet kanë. 

Çfarë është më e rëndësishme është terminal këtu. Dhe ne kemi këtu Pse është kaq i vogël? Cilësimet. Oh. Vërtetë Ike. Si është kjo? Nga atje. A është kjo më e mirë për të gjithë? OK ,. Ftohtë. 

Ti e di kur ju jeni në një CS Vështirësitë teknike e klasës janë lloj i pjesë e the-- Pra, le të qartë këtë. OK. Pra, të drejtë këtu në seksionin, të cilin kemi pasur këtu. Caesar është një file e ekzekutueshme. Kështu që unë e bëri atë. Pra, një gjë për të realizuar me GDB është se ajo punon vetëm në fotografi ekzekutueshme. Pra, ju nuk mund të kandidojë atë në një dotsy. Ju duhet të bëjë në fakt Sigurohuni që kodi juaj përpilon, dhe se kjo në fakt mund të drejtohet. 

Pra, sigurohuni se në qoftë se ajo nuk ka të hartojë, të marrë atë për të hartuar, kështu që ju mund të lloj të kandidojë nëpërmjet saj. Pra, për të filluar GDB, të gjithë ju të bëni, Gloria lloji GDB, dhe pastaj vetëm parashtrojë që ju dëshironi. Unë gjithmonë misspell Cezarin. Por ju doni të bëni të sigurtë pasi ajo është një ekzekutueshme, TI dot flash në mënyrë që të do të thotë që ju do të jeni për të drejtuar CSI ju jeni duke shkuar për të ekzekutuar kjo fotografi ose me Rregullues. OK. Pra, ju bëni këtë, ju merrni ky lloj i dërdëllisje. Kjo është vetëm të gjitha gjërat në lidhje Rregullues. Ju nuk mund të vërtetë kanë për të merak për këtë tani. Dhe, siç e shihni, ne kemi këtë parens hapur, GDP, parens ngushtë, dhe vetëm lloj i duket si linjë tonë të komandës, e drejtë? 

Pra, ajo që ne duam të do-- --So, Gjëja e parë është që ne duam të zgjidhni një vend për të prishur atë. Pra, nuk është një bug në këtë program Caesar që unë prezantoj se ne jemi duke shkuar për të gjetur jashtë. Ajo Çfarë ajo nuk është ajo merr të dhëna Barfoo në të gjitha shkronja kapitale, dhe për disa arsye kjo nuk do të ndryshojë A. Kjo thjesht lë vetëm kjo, është çdo gjë tjetër e saktë, por letra e dytë A mbetet i pandryshuar. Pra, ne jemi duke shkuar për të përpiqen dhe të kuptoj se pse kjo është. Pra, gjëja e parë që ju zakonisht doni të bëni kur ju filloni të GDB është të kuptoj se ku për të prishur atë. 

Pra Caesar është një program mjaft të shkurtër. Ne vetëm kemi një funksion, e drejtë? Cili ishte funksioni ynë në Cezarit? Ka vetëm një funksion, e drejtë kryesore? Kryesor është një funksion për të gjitha programet tuaja. Nëse ju nuk keni Main, unë mund të të jetë pak i shqetësuar tani, por unë shpresoj që ju të gjithë e kishin Main në atje. Pra, ajo që ne mund të bëjmë është që ne mund të vetëm pushim Main, tamam si kjo. Kështu, ajo thotë, OK. Ne kemi vendosur një tonë Breakpoint atje. 

Pra, tani Gjë për të kujtuar është e Cezarit merr një komandë të drejtë argumenti linjë dhe ne nuk e kemi bërë këtë kudo ende. Pra, çfarë ju bëni është kur ju në fakt shkojnë për të kandiduar program, çdo program që ju jeni drejtimin në GDB që duhet command line argumente, ju do të jeni të dhëna kur ju së pari të fillojë drejtimin e tij. Pra, në këtë rast, kemi të bëjmë Drejtuar me një çelës të tre. Dhe ai në fakt do të fillojë. 

Pra, nëse ju shihni këtu, ne kemi RC nëse nuk është e barabartë me 2. Pra, në qoftë se ju djema të gjithë e kanë kjo fotografi që kam dërguar jashtë up ju do të shihni se kjo është si Linja e parë funksioni ynë kryesor, e drejtë? Është kontrolluar për të parë nëse ne kemi numri i saktë i argumenteve. Pra, nëse ju jeni të pyesin nëse RC është e saktë, ju mund të bëni diçka vetëm si Print RC. RC është dy, i cili është ajo që ne prisnim, e drejtë? 

Pra, ne mund të shkojmë Next, dhe të vazhdojë përmes. Pra, ne kemi një çelës atje. Dhe ne mund të shtypura jashtë çelësin tonë për t'u siguruar se është e saktë. Interesting. Jo krejt atë që kemi pritur. Pra, një gjë për të realizuar me GDB gjithashtu, është se kjo nuk është deri sa ju goditi në të vërtetë Tjetra, kjo linjë që ju vetëm e pa është ekzekutuar në të vërtetë. Pra, në këtë rast Key nuk është caktuar ende. Pra, Key është një vlerë e mbeturinave që ju shihni në fund atje. Negative $ 120-- --It e një miliard dhe diçka gjëra të çuditshme apo jo? Kjo nuk është Key që kemi pritur. Por në qoftë se ne e goditi Next, dhe pastaj ne provoni dhe Print kyç, është tre. 

Gjithkush shohim se? Pra, nëse ju merrni diçka se ju jeni si, prisni. Kjo është plotësisht e gabuar, dhe unë nuk e di se si kjo do të ndodhë, sepse të gjitha unë dua të bëni është të caktojë një numër, një variabël, provoni goditur Next, shtypjen provoni përsëri, dhe të shohim nëse që punon. Për shkak se ajo është vetëm do të kryej dhe në fakt caktojë diçka pas teje hit Next. Kuptim për të gjithë? Uh huh? 

Gjuha 2: Kur ju të rastit Numrat çfarë do të thotë kjo? 

Gjuha 1: Është vetëm të rastit. Është vetëm mbeturina. Kjo është vetëm diçka që tuaj kompjuter rastësisht do të caktojë. Ftohtë. Pra, tani ne mund të lëvizin nëpër, dhe kështu tani ne kemi këtë GetString plain text. Pra, më lejoni vetëm të prezantoj atë do të ndodhë kur ne e goditi Next këtu. GDB jonë lloj zhduket, e drejtë? Kjo është për shkak se GetString tani është ekzekutimin, e drejtë? Pra, kur të pamë teksti të thjeshtë është e barabartë me GetString, parens hapur dhe parens, dhe ne goditi Tjetra, që ka në fakt ekzekutuar tani. Pra, ajo është duke pritur për ne të dhëna diçka. 

Pra, ne jemi duke shkuar për të dhëna ushqimin tonë e cila është ajo që është e dështuar, si ju thashë dhe se vetëm thotë se është e përfunduar ekzekutimin, se mbyllur kllapa do të thotë se është daljes nga kjo loop. Pra, ne mund të goditur Next, dhe tani, si unë jam i Sigurohuni që ju jeni të gjithë të njohur nga Cezarit, kjo është, çfarë është kjo linjë do të bëjë. Është për Int I barabartë me 0, N barabartë Strlen, plain text, dhe pastaj I është më pak se n, I, plus, plus. Çfarë është kjo lak do të bëni? Hapni mesazhin tuaj. Ftohtë. Pra, le të fillojë duke bërë atë. 

Pra, duhet ky kusht përputhen, për një tonë të parë? Në qoftë se kjo është një B, është tekst i thjeshtë I. Ne mund të merrni informacion në lidhje me vendasit tanë. Kështu, I është zero, dhe nëse gjashtë, e cila ne presim, dhe çelësi jonë është tre. Të gjithë ata që e bëjnë kuptim, apo jo? Këto numra janë të gjitha saktësisht se çfarë ata duhet të jenë. Pra, hum? Gjuha 3: Unë kam numra të rastit për minierën. Gjuha 1: E pra, ne mund të check-- --we mund të bisedojnë në lidhje me atë në një të dytë. Por ju duhet të jetë duke marrë këtë. Pra, në qoftë se ne kemi një kapital B për një tonë të parë, ky kusht duhet të kapur atë, e drejtë? Pra, në qoftë se ne goditi Tjetra, ne shohim që ky rast të vërtetë ekzekuton. Sepse në qoftë se ju jeni në vijim së bashku me kodin tuaj, kjo linjë këtu, ku teksti plain I është zëvendësuar me këtë aritmetikë, vetëm ekzekuton nëse nëse gjendja është e drejtë e saktë? 

GDB është vetëm do të ju tregojnë gjërat që janë në të vërtetë ekzekutuese. Pra, nëse ky kusht Në qoftë se nuk është plotësuar, është e vetëm do të kaloni në rreshtin tjetër. OK? Pra, ne kemi atë. Kjo parantezë do të thotë se është mbyllur nga kjo loop tani. Pra, ajo do të fillojë përsëri. Ashtu si kjo. Kështu, që ne mund të merrni informacion për vendasit tona këtu, dhe të shohim se ynë i parë letër ka ndryshuar, apo jo? Kjo është tani një E, ashtu siç duhet të jetë. Pra, ne mund të vazhdojë më. 

Dhe ne e kemi këtë kontroll. Dhe ky kontroll duhet të punojë, e drejtë? Është A. Duhet të ndryshohet tre letra përpara. Por nëse ju njoftim, ne të marrë diçka të ndryshme. Pra, në këtë rast deri këtu, është kapur atë, dhe kështu që kjo linjë ekzekutuar, e cila modifikuar tonë B. Por, në këtë rast këtu, ne kemi se vetëm ajo u anashkalua atë, dhe shkoi në [? L Siff. ?] Pra, diçka po ndodh atje. Çfarë është që ju them është se, ne e dimë se ajo duhet të arrijë këtu, por kjo nuk është. Dikush mund të shihni se çfarë tonë Problemi është në këtë linjë? Kjo është një gjë shumë e minutë. Dhe ju gjithashtu mund të shikoni në kodin tuaj. Është gjithashtu line-- harrojmë atë linjë që është në there-- por kjo është në [e padëgjueshme]. Po? 

Gjuha 4: Është më i madh se Faqja në qoftë se ju lexoni atë në libër. Gjuha 1: Pikërisht. Pra, debugger nuk mund të them ju se, por debugger mund të merrni ju poshtë për një linjë që ju e dini nuk është duke funksionuar. Dhe ndonjëherë, kur sidomos më pas në semestrin, kur ju jeni që kanë të bëjnë me njëqind, një Njëqind disa rreshta të kodit, dhe ju nuk e di se ku është e dështuar, kjo është një mënyrë e madhe për të bërë atë. Pra, ne kemi gjetur bug tonë. Ju mund të rregullojmë atë në dosjen tuaj, dhe pastaj ju mund të kandidojë atë përsëri, dhe çdo gjë do të punojnë të përkryer. Dhe gjëja më e madhe është kjo mund të duket si, OK. Po. Ftohtë. Ju e dinte se çfarë ju jeni duke kërkuar për. Pra, ju e dinte se çfarë të bëni. 

GDB mund të jetë super e dobishme për shkak se ju mund të shtypura nga të gjitha këto gjëra që ju të nuk do. Kjo është shumë më e dobishme se sa printf. Sa prej jush përdorni si deklaratat printf të kuptoj se ku a bug ishte, e drejtë? Pra, me këtë, ju nuk e bëni duhet të mbajë prapa, dhe si komentuar në Printf, apo komentuar jashtë, dhe të kuptoj se çfarë ju duhet të jetë printim. Kjo në fakt vetëm ju lejon të hap përmes, të shtypura nga gjërat si ju jeni duke shkuar nëpër, kështu që, ju mund të vëzhgojnë se si ata ndryshojnë në kohë reale, si programin tuaj po kandidon. 

Dhe ajo ka marrë pak pak duke u përdorur për të. Unë do të highly recomend vetëm lloji për të qenë pak i irrituar me të për tani. Nëse keni shpenzuar një orë gjatë javën e ardhshme të mësuarit se si të përdorin GDB, ju do të kurseni veten aq shumë kohë më vonë. Dhe fjalë për fjalë. themi kjo për njerëzit çdo vit, dhe I kujtohet kur mora të klasës, unë kam qenë si, unë do të jetë mirë. Jo. Pset 6 erdhi dhe unë isha si, unë jam gonna të mësuar se si të përdorin GDB, sepse unë nuk bëj e di se çfarë po ndodh këtu. 

Pra, nëse ju merrni kohë në mënyrë e përdorin atë në programet e vogla se ju jeni do të jetë duke punuar në, si punon me diçka si Visionare, si kjo. Ose në qoftë se ju doni praktikë ekstra, unë jam i sigurt Unë mund të dalë me programe buggy, për ju që të korrigjoj, nëse ju dëshironi. 

Por në qoftë se ju vetëm të marrë disa kohë për të marrë përdoret për të, vetëm të luajnë rreth me të, ajo do të me të vërtetë të shërbejë edhe ju. Dhe kjo është me të vërtetë një nga ato gjëra që ju vetëm duhet të përpiqen dhe të marrë në duart tuaja të pista me, para se ju me të vërtetë e kuptojnë atë. Unë me të vërtetë kishte kuptuar vetëm një herë Unë kisha për të debug gjëra me të, dhe kjo është shumë nicer të ketë një ide të se si të korrigjoj më shpejt se sa më vonë. OK. Ftohtë. Unë e di se kjo është lloj i si një kurs përplasje në GDB, dhe unë patjetër do të punojnë në gjetjen e këto të shikojmë kohën e madhe e ardhshme. Ftohtë. 

Pra, nëse ne kthehemi në PowerPoint tonë. A është ky do të punojë? SHIL. Po. OK. Pra, nëse ndonjëherë ju duhet ndonjë prej ata përsëri, nuk ka lista. Pra Binary Search, të cilin të gjithë kujton spektaklin e madh të Davidit shkëlqyer libra telefonit në gjysmë. Unë nuk të vërtetë të marrë librat e telefonit më, sepse ashtu si kur të bëni ju merrni libra telefon këto ditë? Unë me të vërtetë nuk e di. Binary Kërko. A kujtohet dikush se si Binary punon Kërkimi? Çdokush në të gjitha? Vërtet? Gjuha 5: Ti e di kur ju shikoni në të cilën gjysma ajo do të jetë në, bazuar në këtë, dhe të shpëtoj nga gjysma tjetër. 

KRYETARI 1 Pikërisht. Pra, Binary Kërko, kjo është lloj i a-- --we pëlqen për të thirrur atë të ndarë dhe të pushtuar. Pra, çfarë ju do të bëni është të ju do të shikoni në mes, dhe ju do të shihni nëse ajo përputhet atë që ju po kërkoni. Dhe në qoftë se ajo nuk ka, atëherë ju përpiqeni të kuptoj se, po ai do të lihet gjysmë ose gjysmë të drejtë. Pra, kjo mund të jetë në qoftë se ju jeni në kërkim në diçka që është e alphabetized, ju shihni, oh. Ka ardhur Allison para M? Po. Pra, ne jemi duke shkuar për shikoni në pjesën e parë. 

Ose ajo mund të jetë si me numrat. Çdo gjë që ju mund të krahasuar, ajo mund të ndahen. Ju mund të përdorni kërkimin binar në. Pra, dikush kujtohet kjo grafik apo çfarë është kjo? Është Kompleksiteti Asymptotic. Pra, ky grafik vetëm përshkruan se sa kohë ju merr për të zgjidhur një problem në ju rritet numri i gjërave që ju jeni duke përdorur. 

Pra, ne kemi N, e cila është kohë lineare. N nëse mbi dy, i cili është pak më mirë, akoma rritet super të shpejtë. Dhe pastaj ne kemi Identifikohuni, e cila është ajo që ne e konsiderojmë Binary Kërko. Nëse vërejmë, si problemin tuaj merr shumë dhe shumë më të mëdha, Koha që ju duhet për të zgjidhur atë me të vërtetë nuk do të rritet aq shumë. Është si të krahasueshme këtu në fillim. Ju jeni si, OK. Çdo gjë këtu nuk ka të vërtetë një çështje që ne i përdorim, por ju merrni nga një milion, një miliard. Ju jeni duke u përpjekur për të gjetur some-- --you're duke u përpjekur për të gjetur një gjilpërë në kashtë. 

Unë mendoj se ju dëshironi këtë problem. Ju dëshironi këtë kompleksitet, jo lineare, sepse për të gjithë ju e di gonna të tuaj të kërkoni përmes çdo gjilpërë individual, gjë e barit, duke u përpjekur për të kërkuar gjilpërë tuaj. Dhe kjo nuk është shumë e fun për mendimin tim. I pëlqen të shpejtë. I pëlqen efikase. Dhe si punëtorë ju studentë djema jeni, ju e dini të punuar zgjuar, jo shumë gjë lloji, si ju mund të bëjë këto algoritme. 

Pra, ne jemi duke shkuar për të ecur me vetëm një shembull të shpejtë. Unë mendoj se ju djema duhet të ketë një dorë në Binary Kërko, por në rast se dikush është pak fuzzy, duan ta përforcuar atë, ne jemi duke shkuar për të vetëm të shkojnë përmes një shembull këtu. Pra, ne jemi duke kërkuar për nese array përmban shtatë. 

Pra, gjëja e parë që bëni është të shikoni në mes, e drejtë? Dhe gjithashtu ju do të jeni të kodim Binary Kërko në vetëm një të dytë. Pra, kjo do të jetë kënaqësi. Pra, ne shikojmë në vargjeve të mesme pak 3. A 3 të barabartë 7? Nuk ka. Është e gjashtë. Pra, është më pak se ose më e madhe se shtatë? Më pak se. Po. Nice guys punë. Unë ndjehem si unë duhet kanë karamele sepse unë duan ta hedhin atë në oborre. Kjo është ajo që unë jam duke shkuar për të bërë javën e ardhshme. Kjo do të ju mbajë djema mprehtë. 

Pra, ne flak se Gjysmën e parë, e drejtë? ajo ishte më pak se. ne e dimë se gjithçka në atë anën e majtë do të jetë më pak se ajo që ne jemi aktualisht në kërkim për të. Pra, nuk ka nevojë për të i kushtoj vëmendje për të. Vetëm harrojmë për këtë. Pra, tani që ne shohim në të djathtë anën tonë, dhe ne shikojmë në mes atje, dhe tani është nëntë. Pra, 9 is-- --Everyone? Më e madhe se ajo që ne jemi kërkim për të, e drejtë? Pra, ne jemi duke shkuar për të hedhur larg çdo gjë në të djathtë. Si kjo. Tani, të gjithë ne jemi të majtë me të është një. Pra, ne kontrolloni, është kjo ajo që ne jemi duke kërkuar për? ajo është. Ne kemi gjetur atë që kemi dashur. Pra, ne jemi duke bërë. Bilinear Kërko. 

Dhe në qoftë se ju vini re, ne kishte shtatë inputeve atje. Ai vetëm na mori si tri herë, por në qoftë se ju jeni duke bërë si një miliardë, ju djema e di se sa hapat që do të të marrë në qoftë se kemi pasur katër milliard gjëra? Çdo supozime? Është 32. 32 hapa për të gjetur diçka në katër milliard element array për shkak të kompetencave të dy. Pra, dy është në 32, është në katër miliardë lekë. 

Pra mjaft i çmendur si ju jeni ende në si një numër mjaft të vogël të hapave për të gjetur diçka në katër milliard elemente. Pra, në këtë shënim, ne jemi do ta kodin këtë kështu që ju djema mund të vërtetë lloj të shohim se si punon kjo. Në rregull, kështu që ju djema mund kodin. Unë jam duke shkuar për të le ju djema flasim për një grimë të vogël. Get të dinë njerëzit rreth jush, i cili është atë që dikush donte nga seksionin e fundit. 

Pra merrni të dinë njerëzit rreth jush. Flisni për një grimë të vogël. Dhe të gjitha unë dua nga ju djema tani është vetëm përpiqen për të krijuar një skicë të pseudokod. OK? Whoa. Të gjitha unë dua nga ju djema është që ju jeni vetëm do të plotësoni në këtë rast ndërsa. Kështu që unë kam vënë këto sipërme të mëdhenj të ulëta të cilat përfaqësojnë fillim dhe fundi i array tonë. Dhe ju do të vërtetë loop përmes dhe të kuptoj se ajo që ne jemi duke bërë në këtë lak, ndërsa. 

Pra, nëse ju mund ta kuptoj out-- kam një aluzion there-- cilat janë rastet që ne kemi këtu? Pra, nëse ju doni të kuptoj se raste, ne do të pseudokod ato dhe pastaj ne do të vërtetë kodin e tyre. Dhe kjo do të jetë, unë mendoj, shpresojmë se ajo do të të jetë një pak më e lehtë se sa ju presim. Për shkak se ajo nuk është se kodi shumë, në të vërtetë, e cila është me të vërtetë cool. 

Mm-hm? 

STUDENT: [padëgjueshme]? INSTRUKTOR: Po. Nuk ishte diçka e për të gjetur në mes. 

STUDENT: Pra, ne mund të përdorni atë. OK. 

INSTRUKTOR: Perfect. Pra, kjo është gjëja e parë që ne duhet të bëjmë. Pra, gjeni mesme. E madhe. Pra, ju keni një ide se si ne mund në fakt gjetur e mesme me kod? 

STUDENT: Po. n mbi 2? INSTRUKTOR: Pra, n mbi 2. Pra, një gjë për të kujtuar është se kufijtë tuaj sipërme dhe të poshtme të ndryshojë. Ne vazhdojmë constricting pjesë e array ne jemi duke kërkuar për të. Pra, n mbi 2 do të punojnë vetëm për gjëja e parë që ne bëjmë. Pra, të marrë pjesën e sipërme dhe të poshtme parasysh, se si mund të marrim atë element mesme? Sepse ne duam të mesme në mes të sipërme dhe të poshtme, e drejtë? Mm-hm? 

STUDENT: [padëgjueshme]. 

INSTRUKTOR: Pra, ne kemi një qendër. Dhe kjo do të jetë e sipërme plus ulët gjatë 2. Awesome. Nuk shkojmë. Një poshtë vijës. Ju djema jeni në rrugën tuaj. Pra, tani që ne kemi tonë mesme, ajo që duam të bëjmë? Vetëm në përgjithësi. Ju nuk keni për kodin atë. Po. STUDENT: [padëgjueshme]? INSTRUKTOR: Pra, kjo është plus për shkak se ju jeni gjetjen mesatare ndërmjet dy prej tyre. Pra, nëse ju mendoni se prej tyre si lloj e në rritje nga anët, të mendojnë për atë si ju qasje mesme, ju doni si kjo. Pra, nëse ju keni qenë në të dyja anët e mesme, dhe ne kemi si 5 dhe 7. Kur ju shtoni ato së bashku ju merrni 12, ju ndani me 2, është 6. 

Ndonjëherë është e vështirë për të të shpjegojë pse që punon, por në qoftë se ju punoni me një shembull ndonjëherë, ajo do të ju ndihmojë të kuptoj se nëse ajo duhet të jetë plus ose minus. Po. 

STUDENT: [padëgjueshme] pikërisht në mes në qoftë se ata kishin një rast ku ka një shumë të numrave më të vogël dhe si një numër i madh? 

INSTRUKTOR: Pra, të gjithë ju duhet është mes të vektorit. Pra, nëse keni pasur një bandë e numrave të vogël dhe pastaj një numër të vërtetë i madh Në fund, kjo nuk ka rëndësi. Të gjitha që ka rëndësi është se ata janë renditur, ju vetëm dëshironi të shikoni në mes të array sepse ju jeni ende rrafshoj problemin tuaj në gjysmë. Ftohtë. Pra, tani që ne kemi mesme, çfarë të bëjmë tjetër? 

STUDENT: Krahaso. INSTRUKTOR: krahasoni. Pra, krahasoni mes të value_wanted. Ftohtë. Kështu që ju shihni këtu kemi kjo vlerë ne duam këtu. Mos harroni kjo është një koleksion. Pra mesme referohet indeksit. Pra, ne duam të bëjmë vlerat e mesme. Mos harroni, nëse ju doni të krahasojnë, të barabartëve dyfishtë. Ju bëni vetëm ju jeni të barabartë vetëm do të reassign atë, dhe pastaj, sigurisht, është e do të jetë vlera që ju dëshironi. Pra, nuk e bëjmë atë. 

Pra, ne jemi duke shkuar për të parë nëse vlerat në mes është e barabartë me vlerën që ne duam. Mos harroni formatimin e teksteve tuaja. Dropbox duhet të shkoni larg. Pra, çfarë bëjmë ne në këtë rast? Në qoftë se kjo është ajo që ne duam të kthehemi? Ne jemi duke u përpjekur për të thënë. 

STUDENT: Print off. 

INSTRUKTOR: E pra, ne kemi nuk duan të shtypura off. Pra, kjo është një bool këtu, kështu që ne dëshirojnë të kthehen e vërtetë apo e rreme. Ne jemi duke thënë se, është ky numër një [? RRA? ?] Pra, në qoftë se ajo është, ne vetëm të kthehen vërtetë. Në qoftë se unë mund të spell vërtetë. 

STUDENT: Pse nuk do të ktheheni zero? INSTRUKTOR: Pra, ju mund të kthehet zero në qoftë se ju të kërkuar. Por në këtë rast, sepse funksioni ynë kthen një bool, ne kemi nevojë për t'u kthyer ose e vërtetë apo e rreme. STUDENT: Kur ju jeni duke thënë shprehje boolean, mund të keni vendosur të barabartë të rreme? Ashtu si në qoftë se unë dua të them, nëse ky kusht nuk është plotësuar, ashtu si është e sipërme është e barabartë false. Do të kuptoni nëse ju vetëm vënë false në anën tjetër? INSTRUKTOR: Po. Pra, në fakt, nëse ju jeni ndonjëherë duke bërë diçka si është e sipërme apo është më e ulët, që jep true ose false dhe kjo është stil të vërtetë e keqe për të themi barabartë barabartë të vërteta ose të barabartëve barabartë false. Ju dëshironi që të përdorni këtë rezultat si vetë si çek tuaj. Jo atë që kam kërkuar. Kjo është ajo që kam kërkuar. Pra, në rast se ju jeni duke kërkuar për diçka si kjo për të shpëtuar në c. 

Pra, nëse kemi int kryesor (i pavlefshëm) dhe diçka si kjo. Dhe ju keni në qoftë se është i sipërm e disa inputeve dhe ju jeni duke i kërkuar në qoftë se ju mund të bëni diçka si kjo? E drejtë? STUDENT: Unë kam qenë duke u përpjekur ta bëjë atë [e padëgjueshme]. Sepse në qoftë se it's-- INSTRUKTOR: E drejta. Pra, ju doni që kjo të jetë e rreme, e drejtë? STUDENT: Po. INSTRUKTOR: Pra, në këtë rast ju duan që ajo të ekzekutuar në qoftë se nuk është e vërtetë. Pra, gjëja e ftohtë që ju bëni nuk është kjo. Pra, mos harroni Thirrje Pika mohon gjërat? Ai thotë se [padëgjueshme] nuk do të thotë. Pra, nëse ne shikojmë në vetëm kjo pjesë këtu, ju do të thonë se vlerëson të false si ju dëshironi që ajo të. Jo false është e vërtetë e cila do të thotë që kjo do të ekzekutojë. Ka që e bëjnë kuptim? STUDENT: Po. INSTRUKTOR: mbresëlënës. OK. Pra, ne vetëm mund të kthehemi e vërtetë në këtë rast. Deri tani ne kemi dy të tjerë raste në këtë rast. Cilat janë dy raste të tona të tjera? Le të vetëm të bëjë atë në këtë mënyrë. Pra, le të fillojë me të tjerët nëse vlerat në mes është më e vogël se vlera që ne duam. Pra, vlera ynë në mes është më pak se vlera që ne jemi në kërkim për të. 

Pra, e cila lidhur bëni ju mendoj se ne duam për të rinovuar? Sipërme apo të poshtme? Upper? Pra, cila anë e array do të shkojmë të jetë në kërkim në? 

STUDENT: ulët. 

INSTRUKTOR: Ne jemi duke shkuar të jetë në kërkim në të majtë. Pra, tjetër, nëse vlera është pak më pak. Pra vlerën tuaj mesme këtu është më pak se ajo që ne duam. Pra, ne duam të marrin anën e djathtë të vektorit tonë. Pra, ne jemi duke shkuar për Përditëso detyruar tonë të ulët. Pra, ne do të reassign tonë të ulët. Dhe çfarë mendoni të ulët duhet të jetë? STUDENT: Vlera e mesme? INSTRUKTOR: Pra value-- mesme STUDENT: Plus 1. INSTRUKTOR: --plus 1. Dikush mund të më thoni pse kemi se plus 1? 

STUDENT: [? Nuk ka vlerë?] është më e barabartë me të. 

INSTRUKTOR: E drejta. Sepse ne tashmë e dimë se vlera jonë mesme nuk është e barabartë tek kjo dhe ne duam ta përjashtojë atë nga të gjitha kërkimet e mëvonshme. Nëse ju harroni se plus 1, kjo do të donte lak kohë të pacaktuar. Dhe ju do të jetë vetëm kapur në një loop pafund dhe pastaj ju do të segfault dhe gjërat shkojnë keq. Kështu që gjithmonë sigurohuni që ju nuk jeni duke përfshirë edhe vlerën që ju vetëm shikuar. Pra, ne të kujdeset që me një plus 1. 

Deri tani ne kemi gjendjen tonë të fundit që unë gjithmonë për hir të sigurisë ju mund të shikoni këtu, përndryshe nëse vlera në mesme është më e madhe se vlera ne duam. Kjo do të thotë se ne duam gjysma e majtë. Pra, i cili do të shkojmë për të rinovuar? Upper. Dhe çfarë është kjo do të barabartë? Lindja minus 1, sepse, natyrisht, ne duam për të siguruar që ne nuk jemi duke kërkuar në këtë vlerë e mesme përsëri. Dhe pastaj ne kemi atë. Kjo ishte. Kjo është e gjitha kërko binar është. Kjo nuk është edhe aq keq, apo jo? Është si 10 linjave të Kodi me hapësirë ​​të bardhë. Pra shumë e fuqishme, shumë të dobishme, ju do të të jenë duke e përdorur atë në një nga psets tuaja më vonë. Ndoshta jo këtë, por më vonë. Pra, të mësojnë atë. Love it. Ajo do të trajtojnë mirë ju. Pra, ka njeri të ketë ndonjë pyetje në kërkim binar? Po. 

STUDENTORE: A ka rëndësi a n e juaj është edhe apo i rastësishëm? 

INSTRUKTOR: Jo Sepse ne e hodhi në mes, si një int, ai thjesht do ta shkurtoj atë. Pra, kjo do të qëndrojnë një numër të plotë dhe kjo do të në fund të zgjidhur me çdo gjë. Pra, ju nuk keni për t'u shqetësuar në lidhje me atë. Gjithkush e mirë? Awesome. Ftohtë. Pra, ju djema mori këtë. Slideshow. Pra, si ne ishim duke folur rreth, unë e di David përmendur runtimes kompleksitetin. 

Pra, në rastin më të mirë, kjo është vetëm ai, që ne e quajmë kohë të vazhdueshme. Dikush mund të më thoni pse kjo mund të jetë? Çfarë lloj skenari do që të sjellë? Mm-HM. 

STUDENT: [padëgjueshme] first-- INSTRUKTOR: Pra mesme të qënit Elementi i parë që kemi ardhur për të, apo jo? Pra, ose një grup i një ose çdo gjë që ne jemi duke kërkuar për vetëm ndodh të jetë çik mu në mes. Pra, kjo është çështja jonë më e mirë. Ju merrni në probleme reale, ndoshta jo do të arrijnë [padëgjueshme] që shpesh. Po në lidhje me rastin tonë më të keq? Rasti ynë më i keq është log n. Dhe kjo ka të bëjë me tërë kompetencat e dy gjë që kam folur rreth. 

Pra, në rastin më të keq do të thotë që na u desh të pres array poshtë derisa ajo ishte një element i njërit. Pra, ne u desh të pres atë në gjysmë si shumë herë si ne ndoshta mund. Kjo është arsyeja pse ajo është log n, sepse ju vetëm i mbajnë ndarë nga dy. Pra supozimet, gjërat që ju duhet të di nëse ju jeni ndonjëherë do të përdorin një kërkim binar. Elementet e juaj duhet të ndahen. Ata duhet të zgjidhet, sepse kjo është mënyra e vetme që ju mund të dini nëse ju jeni në gjendje për të hedhur nga gjysma e tij. 

Nëse keni pasur këtë qese jumbled e numrave dhe ju jeni duke thënë, OK, unë jam duke shkuar për të kontrolluar e mesme numrin dhe numri unë jam duke kërkuar për është më pak se kaq, unë jam vetëm duke shkuar që në mënyrë arbitrare të hedhur nga një gjysmë. Ju nuk do të dini nëse juaj Numrat në atë gjysmën tjetër. Lista juaj duhet të zgjidhet. Si edhe, kjo mund të jetë duke shkuar përpara pak, por ju duhet të keni qasje të rastit. Ju duhet të jetë në gjendje të vetëm shkojnë në këtë element të mesëm. Nëse ju keni të kaloj me diçka ose ajo ju merr masa shtesë për të marrë në këtë element të mesëm, kjo nuk është të hyni më, sepse n ju jeni duke shtuar më shumë punë në të. Dhe kjo do të bëjë pak më shumë kuptim në dy javë, por unë vetëm lloj i kërkuar në parathënie, ju djema japin një ide të asaj që është e që do të vijnë. Por ato janë dy Supozimet e rëndësishme se ju keni nevojë për një listë binar. Sigurohuni që ajo është e renditura. Kjo është një i madh për ju djema tani. Dhe që ne mund të shkojnë në tjetër terezi tona. Pra, katër flluskë sorts--, futje, zgjedhja, dhe bashkojë. Ata janë të gjitha llojet e ftohtë. Në qoftë se ju djema të vendosë për të marrë CS 124, ju do të mësojnë në lidhje me të gjitha llojet e llojeve. Dhe në qoftë se ju jeni një tifoz XKCD, atje është një lidhje me të vërtetë cool komik si llojet e vërtetë të paefektshme, të cilat unë rekomandoj që ju do të shikoni në. Një prej tyre është si lloj paniku, i cili është si, oh jo, kthehen array rastit. Sistemi mbyllje. Lini. Pra, humor geeky është gjithmonë i mirë. 

Pra ka dikush kujtohet lloj e si vetëm një ide të përgjithshme se si punon flluskë lloj. Ju kujtohet? 

STUDENT: Po. 

INSTRUKTOR: Shkoni për të. 

STUDENT: Pra, ju jeni duke shkuar nëpër dhe nëse është e madhe, atëherë ju bie në ujdi dy. 

INSTRUKTOR: Mm-HM. Pikërisht. Pra, ju vetëm iterate nëpër. Ju shikoni dy numra. Në qoftë se ai më parë është më e madhe se ai më pas, ju vetëm shkëmbim të tyre në mënyrë që në në këtë mënyrë të gjithë numrat e larta flluska deri në fund të lista dhe të gjitha numrat e ulëta flluskë poshtë. 

A ai t'ju tregojë djema ftohtë Tingull Efekt sorting videon? Kjo është lloj i ftohtë. Pra vetëm si tha Robert, algorithm që ju sapo hap nëpër lista, shkëmbejnë vlerat ngjitur në qoftë se ata nuk janë në rregull. Dhe pastaj vetëm i mbajnë përsëritur derisa ju nuk do të bëni asnjë këmbime. Pra nuk është e keqe, e drejtë? Pra, ne vetëm kemi një shembull të shpejtë këtu. Pra, kjo do të zgjidhur ato në ngjitje qëllim. Pra, kur ne do të shkojmë nëpër parë kohë, ne shikojmë nëpërmjet tetë dhe gjashtë natyrisht që nuk janë të në mënyrë që, ne të bie në ujdi tyre. 

Pra, shikoni në një tjetër. Tetë dhe jo katër në rregull. Bie në ujdi tyre. Dhe pastaj tetë dhe dy, bie në ujdi tyre. Nuk shkojmë. Pra, pasi të kalojë tuaj të parë, ju e dini se numri i juaj i madh do të jetë mbi të gjitha mënyra në krye, sepse kjo është vetëm do të jetë vazhdimisht më të mëdha se çdo gjë tjetër dhe ajo është vetëm do të flluskë up gjithë rrugës deri në fund atje. A që e bën kuptim për të gjithë? Ftohtë. 

Pra, atëherë ne shohim në të kalojë tonë të dytë. Gjashtë dhe katër, kaloni. Gjashtë dhe dy, kaloni. Dhe tani ne kemi disa gjëra në mënyrë. Pra, për çdo të kalojë që ne të bëjë me të gjithë listën tonë, ne e dimë se si se një numër shumë në fund do janë renditur. Pra, ne bëjmë një abone të tretë, e cila është një swap. Dhe pastaj në të katërt ynë Kështu, ne kemi zero lojëra elektronike. Dhe kështu që ne e dimë se tonë array ka qenë të renditura. 

Dhe kjo është e madhe Gjë me flluskë lloji. Ne e dimë se kur ne kanë zero këmbime, që do të thotë se çdo gjë është në mënyrë të plotë. Kjo është lloj i si ne kontrolloni. Pra, ne jemi gjithashtu do të kodin flluskë cili lloj po ashtu nuk është edhe aq keq. Asnjë nga këto janë edhe aq keq. Unë e di se ata mund të duket pak e frikshme. Unë e di kur mora të klasës, madje edhe kur unë po mësonte të klasës për hera e parë të vitit të kaluar, Unë kam qenë si, si mund ta bëni këtë? Ajo ka kuptim në teori, por si nuk kemi të vërtetë bëjmë këtë? Cila është arsyeja pse unë gjithashtu dua të ecin nëpërmjet kodit me ju djema këtu. Kështu që unë kam një pseudokod per ju djema këtë kohë. Pra, vetëm i mbajnë në mend këtë si ne jemi gati për të tranzicionit gjatë. Pra, ne kemi disa counter se mban gjurmët e këmbime tona, sepse ne duhet të sigurohemi se ne jemi duke kontrolluar atë. Dhe ne iterate tërë array si ne vetëm e bëri me këtë shembull. Nëse elementi më parë është më i madh se element pas, ku ne jemi në të, ne shkëmbim të tyre dhe ne rrisim tonë counter sepse sa më shpejt që ne të bie në ujdi, ne duam të le counter tonë e di se. Ndonjë pyetje atje? Diçka duket qesharake mbi këtu. STUDENTORE: A keni vendosur ndesh me zero çdo herë ju shkoni nëpër lak? A nuk do të mbajë përsëri për të zero në çdo kohë? INSTRUKTOR: Jo domosdoshmërisht. Pra, ajo që ndodh është që ne të kalojnë nëpër këtu. Pra, bëni kurse, mos harroni, kjo do të ekzekutojë një herë pa të dështojnë. Pra, kjo do të vendosur kundër barabarte me zero, atëherë ajo do të iterate nëpër. Siç iterates anë, ajo do update counter. Siç rejat kundër, kur kjo është bërë, kur ajo arriti në fund të vargut, nëse lista jonë nuk ka qenë të renditura, counter do të kanë qenë të përditësuar. 

Pra, atëherë ajo kontrollon gjendjen dhe thotë, OK, është kundër madh se zero. Nëse kjo është, të bëjë atë përsëri. Ju dëshironi të rivendosur në mënyrë që kur ju shkojnë nëpër, kundër është e barabartë me zero. Nëse ju shkoni nëpër një renditura array, asgjë nuk ndryshon, kjo dështon, dhe ju kthehen listë të renditura. A kjo ka kuptim? STUDENT: Ajo mund të në një pak. INSTRUKTOR: OK. Nëse ka ndonjë tjetër pyetje që vjen deri. Po. 

STUDENTORE: Çfarë do funksioni të jetë për shkëmbejnë elementet? 

INSTRUKTOR: Pra, ne në fakt mund të shkruajmë se në qoftë se ne jemi duke shkuar për tani. Ftohtë. Pra, në këtë shënim, Alison po shkon për të kaluar përsëri në aplikim. Ajo do të jetë kënaqësi. Dhe ne kemi këndshme tonë flluskë lloj gjë këtu. Kështu që unë tashmë e bëri çiklizmit nëpër rrjet. Ne kemi këmbime tona që jane te barabarte me zero. Pra, ne duam që të bie në ujdi ngjitur Elementet nëse ata janë jashtë funksionit. Pra, gjëja e parë që ne kemi nevojë për të nuk është iterate nëpërmjet rrjet tonë. 

Pra, si mendoni ju se ne mund iterate nëpërmjet rrjet tonë? Ne kemi për të dhe i barabartë me 0. Ne duam i të jetë më pak se n minus 1 minus k. Dhe unë do të shpjegojë se në një të dytë. Pra, kjo është një optimization këtu, ku, kujtohet se si kam thënë pas çdo të kalojë përmes array ne e di se çdo gjë është on-- 

Pra, pas një pasimi ne e di se kjo është e renditura. Pas dy kalon ne e dimë se e gjithë kjo është e renditura. Pas tre pasime ne e di se është renditura. Kështu që rruga që unë jam iterating përmes array këtu, po kjo është e bërë të sigurt për të shkuar vetëm përmes asaj që ne dimë është Unsorted. OK? Kjo është vetëm një optimization. Ju mund të shkruani atë naivitet vetëm iterating me çdo gjë, ajo vetëm do të marrë më të gjatë. Me këtë lak katër është vetëm një optimization bukur sepse ne e dimë se pas çdo të plotë përsëritje nëpërmjet rrjet këtu, si çdo lak të plotë këtu, ne e dimë që një shumë prej këtyre elementëve do të zgjidhet në fund. 

Pra, ne nuk duhet të shqetësohen për ato. A që e bën kuptim për të gjithë? Kjo dredhi pak ftohtë? Pra, në këtë rast, në qoftë se ne jemi iterating përmes, ne e dimë se ne duam të kontrolloni nëse array n dhe n plus 1 janë në rregull. OK. Kështu që këtu është pseudokod. Ne duam të kontrolloni nëse array n dhe n plus 1 janë në rregull. Pra, çfarë mund të kemi atje? Ajo do të jetë një kusht. Ajo do të jetë një rast. 

STUDENT: Nëse array n është më pak se array n plus 1. INSTRUKTOR: Mm-HM. Dhe, më pak se ose e madhe se. STUDENT: madhe se. Pastaj ne duam të bie në ujdi tyre. Pikërisht. Deri tani ne kemi marrë në atë që është mekanizëm për të shkëmbejnë ato? Pra, kemi kaluar nëpër këtë kohë të shkurtër, një lloj i funksionit shkëmbim javën e kaluar. A ka dikush kujtohet se si ai ka punuar? Pra, ne nuk mund vetëm të reassign ato, apo jo? Sepse një prej tyre do të ketë humbur. Nëse ne tha A është e barabartë me b dhe pastaj B është e barabartë tek A, të gjithë a papritur dy prej tyre janë vetëm barabartë tek B. 

Pra, ajo që ne duhet të bëjmë është që ne kanë një ndryshore të përkohshme që është do të mbajë një nga jona kohë ne jemi në procesin e shkëmbejnë. Pra, ajo që ne kemi është se ne do të kemi disa int temp është e barabartë to-- ju mund ta caktojë atë për të cilado që ju dëshironi, vetëm sigurohuni që ju të mbani gjurmët e it-- kështu që në këtë rast, unë jam duke shkuar për të caktojë atë në rrjet n plus 1. Kështu që do të mbajë çdo gjë Vlera është në atë bllokun e dytë se ne jemi duke kërkuar në. 

Dhe atëherë ne mund të bëjmë është që ne mund të shkoni përpara dhe array reassign n plus 1, sepse ne e dimë ne kanë atë vlerë të depozituara. Kjo është edhe një nga më të mëdha things-- Unë nuk e di nëse ndonjë prej jush ka pasur çështje ku në qoftë se ju të kaloni dy rreshta të kodit papritur gjërat punuar. Rendit është shumë i rëndësishëm në CS. Pra, sigurohuni që ju diagramin gjëra nëse është e mundur si për atë që është në të vërtetë ndodh. Deri tani ne jemi duke shkuar për reassign array n plus 1, sepse ne e dimë ne kanë atë vlerë të depozituara. 

Dhe ne mund të caktojë se në grup n ose në këtë rast rrjet i. Too shumë variabla. OK. Array Deri tani, ne kemi ricaktuar unë po plus 1 të barazohen se çfarë është në rrjet i. Dhe tani ne mund të ktheheni mbrapsh dhe të caktojë grup i të çfarë? Çdokush? 

STUDENT: 10. 

INSTRUKTOR: 10. Pikërisht. Dhe një gjë e kaluar. Në qoftë se ne kemi swapped atë tani, çfarë duhet të bëjmë? Cila është një gjë që do të na tregoni në qoftë se ne ndonjëherë të përfundojë këtë program? Çfarë na tregon se ne kanë një listë të renditura? Nëse ne nuk do të kryejnë asnjë këmbime, e drejtë? Nëse swap është e barabartë me zero në fund të kësaj. Pra, sa herë që ju të kryer një shkëmbim, si ne vetëm e bëri këtu, ne duam të rinovuar këmbime. Dhe unë e di se ka pasur një Pyetja më parë rreth mund të ju përdorin zero ose një vend e vërtetë apo e rreme. Dhe kjo është ajo që kjo bën këtu. Pra, kjo thotë nëse jo këmbime. Pra, nëse këmbime është zero, e cila is-- unë gjithmonë merrni vërtetat e mia dhe falses mia përzier. Ne duam që ne të vlerësuar të vërtetë dhe kjo nuk është. Pra, në qoftë se është zero, atëherë është e rreme. Nëse ju mohojnë atë me një [? zhurmë?] të bëhet e vërtetë. Pra, atëherë kjo linjë ekzekuton. 

Vërteta dhe të rreme dhe zero dhe ato të merrni çmendur. Vetëm në qoftë se ju ecni ngadalë nëpërmjet saj ajo do të bëjë kuptim. Por kjo është ajo që kjo pak bit e kodit këtu bën. Pra, kjo kontrollon për të parë kemi bërë ndonjë këmbime. Pra, në qoftë se ndonjë gjë përveç zero, ajo do të jetë e rreme dhe tërë gjë është shkuar për të ekzekutuar përsëri. Ftohtë? 

STUDENTORE: Çfarë do të bëni pushim? 

INSTRUKTOR: Pushim vetëm ju shpërthen lak. Pra, në këtë rast do të ashtu si në fund të programit dhe ju do të vetëm keni listën tuaj të renditura. STUDENT: Amazing. INSTRUKTOR: Unë jam i keq? STUDENT: Sepse më parë ne përdorur shkruar 1 mbi shkrim zero për të paraqitur se në qoftë se që do të punojnë apo jo. 

INSTRUKTOR: Po. Kështu që ju mund të kthehet zero ose 1. Në këtë rast, sepse ne nuk jemi të vërtetë bëjnë asgjë me funksionin, ne vetëm duam që ajo të thyer. Ne të vërtetë nuk e kujdesit në lidhje me të. Brake është gjithashtu i mirë në qoftë se ajo është përdorur për të thyer jashtë e katër sythe apo kushte që ju nuk duan të mbajnë ekzekutimin. Ajo thjesht ju merr prej tyre. Kjo është pak e një gjë nuancë. Unë ndjehem si ka një shumë të tundë dorën, si ju do të mësojnë në lidhje me këtë së shpejti. 

Por ju do të mësojnë në lidhje me këtë së shpejti. I premtoj. OK. Pra, ka të gjithë të marrë flluskë lloj? Jo shumë e keqe. Iterate nëpërmjet, swap gjëra duke përdorur një ndryshueshme temp, dhe ne jemi të vendosur të gjithë atje? Ftohtë. Awesome. OK. Kthehu në PowerPoint. Çdo pyetje në përgjithësi në lidhje me këto deri më tani? Ftohtë. Mm-HM. 

STUDENT: [padëgjueshme] int kryesore zakonisht. A ju duhet të keni atë për këtë? 

INSTRUKTOR: Pra, ne ishim vetëm duke kërkuar vetëm në algorithm aktuale klasifikim. Nëse keni pasur atë brenda si një program më të gjerë, ju do të keni një diku int kryesore. Varësisht nga ku ju përdorni këtë algorithm, kjo do të përcaktojë se çfarë është duke u kthyer nga ajo. Por, për rastin tonë, ne jemi në mënyrë rigoroze shikuar se si e bën këtë të vërtetë iterate nëpër një rrjet. Pra, ne nuk u bëni merak për këtë. 

Pra, ne ishim duke folur për rastin më të mirë dhe të rastin më të keq për kërkim binar. Kështu që është gjithashtu e rëndësishme për të bërë se për secilin nga llojet tona. Pra, çfarë mendoni se është më e keqja Rasti runtime i flluskë lloji? Ju djema mbani mend? 

STUDENT: N minus 1. INSTRUKTOR: N minus 1. Kështu që do të thotë se janë n minus 1 krahasimet. Pra, një gjë që të kuptojnë është se në përsëritje të parë, ne do të shkojmë nëpër, ne krahasojmë këto two-- kështu që është 1. Këta dy, tre, katër. Pra, pas një ripërsëritje ne tashmë kanë katër krahasime. Kur unë jam duke folur në lidhje me kohën e duhur dhe n. N përfaqëson numrin e krahasimeve si një funksion të asaj se si shumë elemente të ne kemi. OK? 

Pra, ne do të shkojmë nëpër, ne kemi katër. Herën tjetër që ju e dini që ne nuk e bëjmë duhet të kujdeset për këtë. Ne krahasojmë këto dy, këto dy, këta dy, dhe në qoftë se ne nuk kemi atë optimization me katër lak që kam shkruar, ju do të jetë duke krahasuar këtu anyways. Pra, ju do të duhet të drejtuar nëpër rrjet dhe të bëjë krahasime n n herë, për shkak se çdo herë kemi drejtuar nëpërmjet saj ne renditjes një gjë. 

Dhe çdo herë që të drejtuar përmes array, ne kemi bërë krahasime n. Pra, runtime tonë për këtë është aktualisht katror n, e cila është shumë më keq në tonë log fund, sepse kjo do të thotë nëse do të kishim katër miliard elemente, është e do të marrë na kater miliard katror në vend të 32. Pra, nuk runtime të mirë, por për disa gjëra, ju e dini, nëse ju jeni brenda një varg të caktuar të elementeve flluskë lloj mund të jetë mirë për të përdorur. 

OK. Deri tani, çfarë është rasti runtime të mirë? STUDENT: Zero? Ose 1? 

INSTRUKTOR: Pra 1 do të jetë një krahasim. Të drejtë. 

STUDENT: N minus 1? 

INSTRUKTOR: Pra, vërtet. Pra, n minus 1. Sa herë që ju keni një koncept si n minus 1, ne priren të heqin vetëm atë dhe ne vetëm të themi n sepse ju keni për të krahasuar secili prej these-- çdo çift. Pra, kjo do të jetë n minus 1, të cilat ne ne do të themi vetëm është përafërsisht n. Kur ju jeni që kanë të bëjnë me kohën e duhur, çdo gjë është në përafërt. Për aq kohë sa është shpjegues saktë, ju jeni mjaft të mirë. 

Kjo është se si të merremi me të. Kështu që rasti më i mirë është n, e cila do të thotë se lista është renditur tashmë, dhe të gjithë ne bëjmë është drejtuar me anë të dhe kontrolloni që është e renditura. Ftohtë. Dakord. Pra, siç e shihni këtu, ne vetëm duhet disa grafikët më shumë. Pra, n katror. Fun. Shumë më keq se n siç e shohim, dhe shumë, shumë më keq se 2n log. Dhe pastaj ju merrni edhe në shkrimet log. Dhe ju merrni 124, ju merrni në si yll log, e cila është si i çmendur. Pra, nëse ju jeni të interesuar, lookup log yll. Kjo është lloj i fun. Pra, ne e kemi këtë tabelë të madhe. Vetëm një kokat lart, kjo a tabelë e mrekullueshme që të ketë për tuaj të gjatë në mes, sepse ne kohë për të ju pyes këto thins. Pra, vetëm një kokat lart, të ketë kjo në tuaj afatmesme të mashtrojnë tuaj të bukur fletë atje. Pra, ne vetëm të shikuar flluskë lloji. Rastin më të keq, n katror, ​​rastin më të mirë, n. Dhe ne jemi duke shkuar për të parë në të tjerët. 

Dhe si ju mund të shihni, e vetmja ai që me të vërtetë e bën mirë është lloj bashkojë, të cilat ne do të merrni në pse. Pra, ne jemi duke shkuar për të shkuar në tjetër një lloj here-- përzgjedhje. A mbani mend se si dikush Përzgjedhja punuar lloj? Shkoni për të. 

STUDENT: Në thelb të shkojnë nëpër një urdhër dhe për të krijuar një listë të re. Dhe ashtu si ju jeni duke elementet në, ata vënë në vendin e duhur në listën e re. 

INSTRUKTOR: Kështu që tingëllon më shumë si futje lloj. Por ju jeni me të vërtetë afër. Ata janë shumë të ngjashme. Edhe unë të marrë ato të përziera ndonjëherë. Para se këtë seksion unë kam qenë si, prisni. OK. Pra, çfarë ju doni të bëni është zgjedhja lloj, mënyrë që ju mund të mendoni në lidhje me të dhe mënyrën I sigurohuni që nuk përpiqet për të marrë ato të përziera, është ajo shkon përmes dhe zgjedh Numri më i vogël dhe kjo vendos që në fillim të listës suaj. Ajo këmbime me atë vend të parë. Ata në fakt kanë një shembull për mua. Awesome. Pra, vetëm një mënyrë për të menduar për zgjedhjen it-- lloj, zgjidhni vlerën më të vogël. Dhe ne jemi duke shkuar për drejtuar përmes një shembull që unë mendoj se do të ndihmojë, sepse Unë mendoj se visuals gjithmonë ndihmojnë. Pra, ne fillojmë me diçka që është plotësisht Unsorted. Red do të jetë Unsorted, e gjelbër do të ndahen. E gjitha do të bëjë kuptim në një të dytë. 

Pra, ne do të shkojmë nëpër dhe iterate nga fillimi në fund. Dhe ne themi, OK, 2 është numrin tonë të vogël. Pra, ne jemi duke shkuar për të marrë 2 dhe ne jemi duke shkuar për të lëvizur atë në frontin e array tonë sepse kjo është Numri më i vogël i kemi. Pra, kjo është ajo që kjo është duke bërë këtu. Është vetëm do të bie në ujdi ato dy. Deri tani, ne kemi një të renditura pjesë dhe një pjesë e Unsorted. Dhe çfarë është e mirë për të kujtuar rreth përzgjedhjes lloj është që ne jemi vetëm zgjedhjen nga pjesa Unsorted. 

Pjesa Renditur qe sapo lënë vetëm. Mm-hm? 

STUDENT: Si e dini se çfarë është të vogël pa e krahasuar atë çdo vlerë tjetër në rrjet. INSTRUKTOR: Kjo e bën të krahasojnë atë. Ne pëlqen skipped atë. Kjo është vetëm i përgjithshëm në përgjithësi. Po. Kur ne shkruani kodin unë jam që ju do të jenë më të kënaqur. Por ju ruani këtë e parë element si i vogël. Ju krahasoni dhe ju thonë, OK, është më e vogël? Po. Keep it. Këtu është ajo më e vogël? Nuk ka? 

Ky është më i vogël tuaj, reassign atë në vlerën tuaj. Dhe ju do të jetë shumë më të lumtur kur shkojmë nëpër kodit. Pra, ne do të shkojmë nëpër, ne shkëmbim atë, kështu që atëherë ne e shikojmë në këtë pjesë Unsorted. Pra, ne jemi duke shkuar për të zgjedhur tre jashtë. Ne jemi duke shkuar për të vënë atë në në fundi i pjesës sonë të renditura. Dhe ne jemi vetëm do të vazhdojmë të bëjmë që ta bëjnë këtë, dhe duke bërë atë. Pra, kjo është lloj tonë të pseudokod këtu. Ne do kod atë deri këtu në një të dytë. Por vetëm diçka për të ecur të kalojë në një nivel të lartë. Ju jeni duke shkuar për të shkuar nga i barabartë me 0 n minus 2. Kjo është një tjetër optimization. Mos u shqetësoni shumë për këtë. Pra, si ju jeni duke thënë. Si Jakobi u thoshte, si nuk kemi mbajnë gjurmët e asaj minimale tonë është? Si e dimë ne? Ne kemi për të krahasuar gjithçka në listën tonë. 

Pra minimum barabartë i. Është thjesht duke thënë se në këtë rast indeksi i vlerës sonë minimale. Pra, atëherë ajo do të iterate nëpër dhe ajo shkon nga j barabartë i plus 1. Pra, ne tashmë e dimë se kjo është elementi ynë i parë. Ne nuk duhet të krahasojnë atë me vete. Pra, ne fillojmë të krahasuar atë të ardhshëm njëra e cila është arsyeja pse është i plus 1 të n minus 1, i cili është fundi i array atje. Dhe ne i thamë nëse array në j është më pak se min vektorit, atëherë ne reassign ku Indekset ynë minimal është. 

Dhe nëse min nuk është e barabartë tek I, siç atje ku ishim përsëri këtu. Pra, si kur ne e bëmë për herë të parë në këtë një të tillë. Në këtë rast, ajo do të fillojë në zero, ajo do të përfundojë si dy. Pra min nuk do të barabartë i në fund. Kjo na lejon të dimë se ne kemi nevojë për të bie në ujdi tyre. Unë ndjehem si një shembull konkret do të ndihmojë shumë më tepër se kjo. Kështu që unë do të kodojnë këtë me ju djema tani dhe unë mendoj se kjo do të jetë më mirë. 

Llojet kanë tendencë për të punuar në këtë mënyrë në të cilat është shpesh më të mirë vetëm për të parë ato. Pra, ajo që ne duam të bëjmë është ne së pari duam të vogël element në pozicionin e saj në rrjet. Pikërisht ajo që Jakobi u thoshte. Ju duhet për të ruajtur atë disi. Pra, ne jemi duke shkuar për të filluar këtu iterating mbi array. Ne jemi duke shkuar për të thonë se kjo është tonë para vetëm për të filluar me. Pra, ne do të kemi int vogël është e barabartë me grup me i. 

Pra, një gjë në njoftim, çdo Ora kësaj loop ekzekuton, ne jemi duke filluar një hap më tej së bashku. Kur ne fillim ne shikojmë në këtë një të tillë. Herën tjetër që iterate nëpërmjet, ne jemi duke filluar në këtë një dhe caktimin kjo vlerën tonë të vogël. Pra, kjo është shumë e ngjashme me flluskë lloj ku ne e dimë se pas një pasimi, ky element i fundit është renditur. Me përzgjedhjes lloj, kjo është vetëm e kundërta. 

Në çdo të kalojë, ne e dimë se i pari është renditur. Pas kalojë dytë, e dyta do të ndahen. Dhe si ju pa me shembuj rrëshqitje, Pjesa jonë e renditura vetëm vazhdon të rritet. Pra, me vendosjen e një tonë të vogël të vargjeve i, e gjitha kjo e bën është constricting çfarë ne jemi duke kërkuar në mënyrë që për të minimizuar numrin e kemi bërë krahasime. Ka që e bëjnë kuptim për të gjithë? A keni nevojë për mua për të drejtuar përmes se përsëri ngadalshme ose me fjalë të ndryshme? Unë jam i lumtur për të. OK. 

Pra, ne jemi ruajtjen Vlera në këtë pikë, por ne gjithashtu duam të ruajtur indeksi. Pra, ne jemi duke shkuar për të ruajtur pozita më të vogël një, e cila është vetëm do të jetë i. Deri tani Jakobi është i kënaqur. Ne kemi gjëra të ruajtura. Dhe tani ne duhet të shohim përmes pjesa Unsorted e array. Pra, në këtë rast kjo do të jetë Unsorted tonë. Ky është i. OK. 

Pra, ajo që ne jemi duke shkuar për të bërë do të jetë për një lak. Kurdo që të keni nevojë për të iterate nëpërmjet një rrjet, mendjen tuaj mund të shkoni në për një lak. Pra, për disa int k equals-- çfarë ne mendojmë k do të jetë e barabartë për të filluar me? Kjo është ajo që ne kemi përcaktuar si i vogël ynë vlera dhe ne duam të krahasojmë atë. Çfarë duam ta krahasojnë atë me? Ajo do të jetë kjo një tjetër, e drejtë? Pra, ne duam k të firmosur që i plus 1 për të filluar. 

Dhe ne duam k në këtë rast ne tashmë kanë Madhësia ruajtur deri këtu, kështu që ne mund të përdorni vetëm madhësinë. Madhësia qenë madhësia e array. Dhe ne vetëm duam të Përditëso k nga një çdo kohë. Ftohtë. Deri tani ne kemi nevojë për të gjetur element të vogël këtu. Pra, nëse ne iterate nëpërmjet, ne dua të them, nëse array në k është më pak se value-- tonë të vogël ky është vendi ku ne jemi në të vërtetë mbajtja e asaj që është e here-- më të vogël atëherë ne duam të reassign ajo që vlera jonë më e vogël është. 

Kjo do të thotë se, oh, ne jemi iterating përmes këtu. Cilado qoftë vlera është këtu, është jo gjë e vogël tonë. Ne nuk e duan atë. Ne duam të reassign atë. Pra, nëse ne jemi ricaktuar atë, se çfarë bëjnë ju mendoni se mund të jetë në këtë kod këtu? Ne duam të reassign të vogël dhe pozita. Pra, ajo që është më e vogël tani? STUDENT: Array k. INSTRUKTOR: Array k. Dhe çfarë është pozita tani? Çfarë është indekset e Vlera tonë të vogël? Kjo është vetëm k. Pra array k, k, ato ndeshje deri. Pra, ne të kërkuar për të reassign atë. Dhe pastaj pasi kemi gjetur më të vogël tonë, kështu që në fund të kësaj për lak ketu kemi gjetur atë më të vogël tonë Vlera është, kështu që ne vetëm të bie në ujdi atë. Në këtë rast, siç thonë tonë Vlera më e vogël është këtu. Kjo është vlera jonë më e vogël. 

Ne vetëm duam të bie në ujdi atë këtu, e cila është se çfarë funksioni swap në fund bëri, të cilat ne vetëm shkroi së bashku minuta një çift më parë. Pra, ai duhet të duket e njohur. Dhe pastaj ai thjesht do të iterate nëpërmjet deri sa të arrijë të gjithë rrugën deri në fund, që do të thotë se ju kanë zero elemente që janë Unsorted dhe çdo gjë tjetër ka qenë të renditura. Kuptim? Një pak më konkretisht? Kodi ndihmë? 

STUDENT: Për një madhësi, ju kurrë nuk të vërtetë të përcaktojë apo ndryshojë atë, Si e di? 

INSTRUKTOR: Pra, një gjë të njoftim up këtu është madhësia int. Pra, ne jemi duke thënë në këtë lloj sort-- është një funksion në këtë case-- është Përzgjedhja lloj, është e kaluar në me funksionin. Pra, në qoftë se ajo nuk u miratua në, ju do të bëni diçka si me gjatësinë e vektorit ose ju do të iterate nëpër për të gjetur gjatësinë. Por për shkak se ajo është e kaluar në, ne vetëm mund ta përdorin atë. Ju vetëm të supozojmë se përdoruesi ju dha një madhësi të vlefshme që në fakt paraqet një Madhësia e vektorit tuaj. Ftohtë? 

Nëse ju djema keni ndonjë problem me këto ose duan më shumë praktikë coding llojet në tuaj, ju duhet shkojnë në study.cs50. Është një mjet. Ata kanë një checker që ju në fakt mund të shkruani. Ata bëjnë pseudokod. Ata kanë më shumë video dhe slides përfshirë edhe ato që unë përdorin këtu. Pra, nëse ju jeni ende ndjenja a pak fuzzy, provoni atë jashtë. Si gjithmonë, vijnë flasin për mua, too. Pyetje? 

STUDENTORE: A jeni duke thënë Madhësia është përcaktuar më parë? INSTRUKTOR: Po. Madhësia është e përcaktuar paraprakisht up këtu në deklaratën e funksionit. Pra, ju mendoni se ajo është miratuar në nga ana e përdoruesit, dhe për hir të thjeshtësisë, ne jemi duke shkuar për të supozojmë se Përdorues na dha madhësinë e saktë. Ftohtë. Pra, kjo është zgjedhja lloj. Guys, unë e di se ne jemi mësuar shumë sot. Kjo është një të dhënave të dendura për seksionin. Pra, me këtë, ne jemi duke shkuar për të shkuar në futje lloji. 

OK. Pra, para se ne duhet të bëjmë Analiza jonë Runtime këtu. Pra, në rastin më të mirë, dhënë që unë ju tregoi Tabela Unë tashmë lloji i dha atë larg. Por rasti Runtime të mirë, çfarë ne mendojmë? Çdo gjë renditura. N katror. Çdokush kanë një shpjegim Pse mendoni? 

STUDENT: Ju jeni të krahasuar through-- INSTRUKTOR: E drejta. Ju jeni krahasuar me. Në çdo përsëritje, edhe pse ne jemi decrementing këtë me një, ju jeni ende në kërkim përmes gjithçka për të gjetur një të vogël. Pra, edhe në qoftë se vlera e juaj më të vogël është këtu në fillim, ju jeni ende duke e krahasuar atë kundër çdo gjë tjetër për t'u siguruar se është gjëja më e vogël. Pra, ju do të përfundojë deri duke kaluar nëpër rreth katror n herë. Dakord. Dhe çfarë është rasti më i keq? Gjithashtu n katror, ​​sepse ju do të jeni të jetë bërë këtë procedurë të njëjtë. Pra, në këtë rast, përzgjedhje lloj ka diçka se edhe ne e quajmë Runtime pritshëm. Pra, ne të tjerët, ne vetëm e di e sipërme dhe të poshtme të mëdhenj. Varësisht se si i çmendur tonë lista është ose si Unsorted është, ato ndryshojnë në mes të n ose n katërkëndësh. Ne nuk e dimë. 

Por për shkak se zgjedhja lloj ka të njëjtën më të keq dhe rastin më të mirë, që na tregon se pa marrë parasysh se çfarë lloji i kontributit ne kanë, nëse kjo është plotësisht e renditura ose tërësisht kundërt të renditura, kjo është do të marrë të njëjtën sasi e kohës. Pra, në këtë rast, në qoftë se ju mbani mend nga tryezën tonë, në të vërtetë ajo kishte një vlerë që këto dy lloje nuk kanë, e cila është Runtime pritet. Pra, ne e dimë se sa herë kemi drejtuar përzgjedhjes lloj, është e garantuar për të drejtuar një kohë të n katror. Nuk ka variabilitet atje. Është vetëm pritet. Dhe, përsëri, në qoftë se ju doni të mësoni më, të marrë CS 124 në pranverë. Dakord. Ne e kemi parë këtë. Ftohtë. Lloj Pra futje. Dhe unë jam ndoshta do të flakët nëpër këtë. Unë nuk do të keni djema kodin atë. Ne vetëm do të ecin nëpër atë. Pra, futje lloj është lloji e ngjashme me përzgjedhjes lloj në atë që ne kemi edhe një Unsorted dhe të renditura pjesë e vektorit. 

Por ajo që është e ndryshme është se si ne të kalojnë nëpër një nga një, ne vetëm të marrë çfarëdo numri është tjetër në Unsorted tonë, dhe saktë zgjidhur atë në rrjet të renditura. Ajo do të bëjë më shumë kuptim me një shembull. Pra, çdo gjë fillon si Unsorted, ashtu si me përzgjedhjes lloj. Dhe ne jemi duke shkuar për të zgjidhur këtë në order Ascending siç kemi qenë. Pra, në të kalojë tonë të parë kemi marrë vlerën e parë dhe ne themi, OK, ju jeni tani në një listë me veten. 

Sepse ju jeni në një listë me veten, ju janë të renditura. Urime për të qenë Elementi i parë në këtë grup. Ju tashmë jeni të renditura të gjitha në tuaj. Deri tani, ne kemi një të renditura dhe një array Unsorted. Deri tani kemi marrë të parë. Çfarë ndodh në mes këtu dhe këtu është se ne themi, OK, ne do të shikojmë në Vlera e parë të vektorit tonë Unsorted dhe ne jemi duke shkuar për të dhëna atë në e saj vendin e saktë në rrjet renditura. 

Pra, ajo që ne nuk po kemi marrë 5 dhe themi, OK, 5 është më e madhe se 3, kështu që ne vetëm të futur atë të drejtë në të djathtë të atij. Ne jemi të mirë. Pra, atëherë ne do të shkojmë për në një tonë të ardhshëm. Dhe ne kemi marrë 2. Ne themi, OK, 2 më pak se 3, kështu që ne e dimë se ai duhet të jetë në para e listës tonë tani. Pra, ajo që ne bëjmë, është që ne të shtyjë 3 dhe 5 poshtë dhe ne shkojmë 2 në atë slot parë. Pra, ne jemi vetëm duke futur atë në vendin e saktë ajo duhet të jetë. 

Pastaj ne shikojmë tonë një tjetër, dhe ne themi 6. OK, 6 është më e madhe se çdo gjë në grup tonë të renditura, kështu që ne vetëm të tag atë deri në fund. Dhe pastaj të shohim në 4. 4 është më pak se 6, është më pak se 5 por kjo është më e madhe se 3. Pra, ne vetëm të futur atë të drejtë në mesme në mes të 3 dhe 5. Pra, për të bërë atë një pak pak më konkret, këtu është lloj i Ideja e asaj që ka ndodhur. Pra, për çdo element Unsorted, ne përcaktuar ku në pjesën renditura ajo është. 

Pra, duke mbajtur në mendje të të renditura dhe Unsorted, ne duhet të kaloj përmes dhe figura se ku ajo i përshtatet në rrjet renditura. Dhe ne e futur atë duke zhvendosur elementet në të djathtë të saj poshtë. Dhe pastaj ne vetëm i mbajnë iterating përmes derisa ne kanë një listë të renditura tërësisht ku Unsorted tani është zero dhe të renditura merr Tërësia e listës sonë. Pra, përsëri, për t'i bërë gjërat edhe më më konkret, ne kemi pseudokod. 

Pra, në thelb për të i është barabartë me 0 deri n minus 1, kjo është vetëm gjatësia e vektorit tonë. Ne kemi disa element që është i barabartë me array parë ose indekset parë. Ne kemi vendosur j barabartë me atë. Kështu ndërsa j është më e madhe se zero dhe array, j minus 1 është më e madhe se element, kështu që të gjithë që e bën është duke u siguruar se j juaj paraqet me të vërtetë pjesa Unsorted e array. 

Kështu, ndërsa ka ende gjëra për të zgjidhur dhe një j minus is-- çfarë është element saj? J nuk është definuar këtu. Kjo është lloj i bezdisshëm. OK. Anyways. Pra, j minus 1, ju jeni duke kontrolluar element përpara. Ju jeni duke thënë, OK, është element para kudo që am-- le në fakt nxjerrë this out. Pra, le të thonë se kjo është e si në të kalojë tonë të dytë. Kështu që unë do të jetë e barabartë me 1, e cila është këtu. 

Kaq i do të jenë të barabartë me 1. Kjo do të jetë 2, 4, 5, 6, 7. Dakord. Pra, element jonë në këtë rast do të jenë të barabartë me 4. Dhe ne kemi disa j që është e do të jenë të barabartë me 1. Oh, j është decrementing. Kjo është ajo që është. Kështu j është e barabartë tek I, kështu që kjo është ajo duke thënë është se si ne të ecim përpara, ne jemi vetëm duke u siguruar se ne nuk jemi të gjatë indeksimin e në këtë mënyrë, kur ne jemi duke u përpjekur për të futur gjërat në listën tonë të renditura. 

Kështu kur j është e barabartë me 1 në këtë rast dhe array j minus one-- kështu array j minus 1 është 2 në këtë case-- nëse kjo është e madhe se elementit, atëherë e gjithë kjo është bërë është zhvendosur gjëra poshtë. Pra, në këtë rast, një grup j minus do të jetë grup zero, i cili është 2. 2 nuk është më i madh se 4, kështu që kjo nuk do të ekzekutojë. Pra ndryshim nuk lëvizin poshtë. Çfarë kjo nuk është vetëm këtu lëviz grup tuaj të renditura poshtë. Në këtë rast, në të vërtetë, ne kemi mund do-- le të bëjmë këtë 3. Pra, nëse ne jemi të ecin me me këtë shembull, ne jemi tani këtu. Kjo është e renditura. Kjo është Unsorted. Ftohtë? Kështu i është e barabartë me 2, kështu element jonë është e barabartë me 3. Dhe j jonë është e barabartë me 2. Kështu që ne shikojmë nëpërmjet dhe ne thonë, OK, është një koleksion j minus madhe se elementit se ne jemi duke kërkuar në? Dhe përgjigja është po, e drejtë? 4 është më e madhe se 3 dhe J është 2, kështu që ky kod ekzekuton. 

Deri tani ajo që ne bëjmë një rrjet në 2, në mënyrë të drejtë këtu, ne bie në ujdi tyre. Pra, ne vetëm të themi, OK, array në 2 tani do të jetë 3. Dhe j do të jetë e barabartë j minus 1, e cila është 1. Kjo është e tmerrshme, por ju djema merrni ide. J tashmë është e barabartë me 1. Dhe array j është vetëm do të jetë barabartë me elementin tone, i cili ishte 4. Unë fshihet diçka që nuk duhet të kanë apo diçka miswrote, por ju djema merrni ide. 

Ajo lëvizin në n. Dhe pastaj në qoftë se kjo ishte, ajo do loop përsëri dhe do të thonë, OK, j është 1 tani. Dhe array j minus 1 tani është 2. Është 2 më pak se elementit tonë? Nuk ka? Kjo do të thotë se ne kemi futur këtë element në vend të saktë në rrjet të renditura. Atëherë ne mund të marrë këtë dhe të themi, OK, array tonë renditura është këtu. Dhe kjo do të marrë këtë numër 6 dhe do të jetë si, OK, është 6 më pak se ky numër? Nuk ka? Ftohtë. Ne jemi mirë. 

Të bëjë atë përsëri. Ne themi 7. 7 është më pak se fund e array tonë Renditur? Jo. Pra, ne jemi në rregull. Pra, kjo do të zgjidhet. Në thelb e gjithë kjo e bën është ajo e thënë reagim element i parë i array tuaj Unsorted, kuptoj se ku shkon në grup tuaj të renditura. Dhe kjo vetëm përkujdeset nga swap-et për të bërë atë. Ju jeni në thelb vetëm shkëmbejnë derisa ajo është në vendin e duhur. Imazhi vizual është se ju jeni lëviz gjithçka poshtë duke bërë atë. 

Pra, kjo është si gjysmë flluskoj lloj-esque. Check out studim 50. I highly recommend duke u përpjekur për kodin këtë në tuaj. Nëse keni ndonjë çështje, ose ju dëshironi të shihni kodin mostër për një lloj futje, ju lutem let me know. Unë jam gjithmonë përreth. Pra rasti Runtime të keq dhe rast Runtime të mirë. Si ju guy parë nga tabela unë tashmë e ju tregoi, ajo është edhe n katror dhe n. 

Kështu lloj të shkuar jashtë të asaj që kemi biseduar në lidhje me llojet tona të mëparshme, më e keqja Rasti runtime është se në qoftë se ajo është Unsorted plotësisht, ne duhet të krahasohen të gjitha këto kohë n. Ne bëjmë një tërësi shumë të krahasimeve sepse në qoftë se ajo është në mënyrë të kundërt, ne jemi duke shkuar për të thënë, OK, kjo është i njëjtë, kjo është e mirë, dhe kjo do të duhet të krahasohen kundër një të parë për të lëvizur prapa. Dhe si ne të merrni në drejtim të fund bisht, ne kemi për të krahasuar, krahasoni, dhe krahasojnë kundër çdo gjëje. 

Pra, ajo përfundon duke u rreth katror n. Nëse është e saktë, atëherë ju thonë, OK, 2, ju jeni të mirë. 3, ju jeni në krahasim me 2. Ju jeni të mirë. 4, ju vetëm krahasuar me bisht. Ju jeni të mirë. 6, krahasuar me bisht, ju jeni të mirë. Pra, për çdo vend, nëse kjo është tashmë të renditura, ju jeni duke bërë një krahasim. Pra, kjo është vetëm n. Dhe për shkak se ne kemi një rast Runtime të mirë i n dhe një rast Runtime të keq të n katror, ​​ne nuk kemi Runtime pritshëm. 

Kjo varet vetëm nga Kaosi i listës sonë atje. Dhe përsëri, një tjetër grafik dhe një tjetër tryezë. Pra, dallimet në mes të llojeve. Unë jam vetëm duke shkuar për të fllad përmes, I ndjehen si ne kemi folur gjerësisht në lidhje me mënyrën se si ata të gjitha llojet të ndryshojnë dhe të lidhin së bashku. Pra Merge lloj është ai i fundit Unë do t'ju lindi djema me. Ne nuk kemi një pamje mjaft të gjallë. Pra bashkojë lloj është një algoritmi rekursive. Pra, mendoni ju djema e di se çfarë një funksion gjithkund rekursive është? 

Çdokush doni të thoni? Ju dëshironi të provoni? Pra, një funksion gjithkund rekursive është vetëm një funksion që e quan veten. Pra, nëse ju djema janë të njohur me sekuencën Fibonacci, që është konsideruar rekursive sepse ju merrni dy e mëparshme dhe shtoni ato së bashku për të marrë një tuaj të ardhshëm. Pra gjithkund rekursive, unë gjithmonë mendoj i recursion si si një spirale kështu që ju jeni si spiralen poshtë në të. Por kjo është vetëm një funksion që e quan veten. 

Dhe, në të vërtetë, me të vërtetë shpejt unë mund të ju tregojnë se çfarë duket si. Pra rekursive këtu, në qoftë se ne e shikojmë, kjo është mënyrë rekursive për të përmbledhur mbi një rrjet. Pra, gjithçka që ne bëjmë është ne kemi funksion shuma Shuma që merr një madhësi dhe një rrjet. Dhe në qoftë se ju njoftim, madhësia decrements nga një çdo herë. Dhe e gjitha kjo nuk është në qoftë se x është e barabartë me zero-- kështu që nëse madhësia e array është e barabartë tek zero-- kthehet zero. 

Përndryshe ajo përmbledh këtë Elementi i fundit i vektorit, dhe pastaj merr një shumë të pjesa tjetër e array. Pra, kjo është vetëm e thyer atë në problemet e vogla dhe të vogla. Long histori e shkurtër, recursion, funksion që e quan veten. Nëse kjo është e gjitha që ju mori nga kjo, kjo është ajo që një funksion gjithkund rekursive është. Nëse ju merrni 51, ju do të merrni shumë, shumë rehat me recursion. Kjo është me të vërtetë cool. Është bërë kuptim në si 03:00 një natë jashtë. Dhe unë kam qenë si, pse kurrë nuk kam përdorni këtë? 

Pra, për merge lloj, në thelb se çfarë do të bëjë është ajo e do të thyejnë atë poshtë dhe të ndërpreni atë poshtë derisa ai është vetëm elemente të vetme. Elementet e vetme janë të lehtë për të zgjidhur. Ne e shohim se. Nëse ju keni një element, është e tashmë konsiderohet Renditur. Pra, në një input të elementeve n, nëse n është më pak se 2, kthehen vetëm për shkak se mjetet e është ose 0 ose 1 si ne kemi parë. Ato janë konsideruar si elemente të renditura. 

Përndryshe thyejnë atë në gjysmë. Lloj gjysmën e parë, lloj e dytë gjysmë, dhe pastaj bashkojë ato së bashku. Pse është quajtur bashkojë lloj. Pra, ne kemi këtu ne do të zgjidhur këto. Pra, do të vazhdojmë që ata derisa madhësia array është 1. Pra, kur është 1, ne vetëm të kthehen sepse kjo është një grup renditura, dhe kjo është një grup renditura, dhe kjo është një koleksion të renditura, ne jemi renditur të gjithë. Pra, atëherë çfarë bëjmë është që ne të fillojnë bashkimin e tyre së bashku. 

Pra, mënyra që ju mund të mendojnë për bashkimin është ju vetëm hiqni vogël Numri i secilit prej vargjeve nën dhe vetëm append atë në rrjet shfaq. Pra, nëse ju shikoni këtu, kur kemi këta grupe kanë ne 4, 6, dhe 1. Kur ne duam të bashkohen këto, ne shikojmë në këto dy parë dhe ne themi, OK, 1 është më i vogël, ajo shkon në front. 4 dhe 6, nuk ka asgjë për të krahasuar atë për të, vetëm tag atë deri në fund. 

Kur ne kombinojnë këto dy, ne vetëm të marrë një më të vogël të këtyre dy, kështu që është 1. Dhe tani kemi marrë më i vogël i këtyre dy, kështu 2. Më i vogël i këtyre dyve, 3. Më i vogël i këtyre dy, 4, 5, 6. Pra, ju jeni vetëm duke tërhequr off këto. Dhe për shkak se ata kanë janë të renditura më parë, ju vetëm keni një të tillë krahasimi çdo herë atje. Kështu që më code këtu, përfaqësimi i drejtë. Pra, ju të fillojë në mes dhe ju lloj majtë dhe djathtë dhe atëherë ju vetëm bashkojë ato. 

Dhe ne nuk kemi kod për bashkojë të drejtë këtu. Por, përsëri, në qoftë se ju shkoni në studim 50, ajo do të jetë atje. Përndryshe vijnë flasin për mua në qoftë se ju jeni ende i hutuar. Pra, gjëja e ftohtë këtu është se rasti më i mirë, rastin më të keq, dhe runtime pritshme janë të gjitha në log n, e cila është shumë më mirë se ne kemi parë për pjesën tjetër të llojeve tona. Ne e kemi parë n katror dhe çfarë ne fakt merrni këtu n log n, e cila është e madhe. 

Shikoni se si më mirë që është e. Një kurbë e tillë e bukur. Pra, shumë më efikase. Nëse ju ndonjëherë mund të, përdorimi i bashkohen lloj. Kjo do të ju kursejnë kohë. Pastaj përsëri, siç kemi thënë, në qoftë se ju jeni poshtë në këtë rajon më të ulët, kjo nuk e bën atë shumë nga një ndryshim. Ju merrni deri në mijëra dhe mijëra të inputeve, ju patjetër doni a algorithm më efikase. Dhe, përsëri, tabela jonë e bukur e të gjitha lloj që ju djema mësuar sot. 

Kështu që unë e di se kjo është një ditë e dendur. Kjo nuk është domosdoshmërisht do për t'ju ndihmuar me pset tuaj. Por unë vetëm dua të bëjë një mohim ky seksion nuk është vetëm për psets. E gjithë ky material është e drejtë lojë për midterms tuaj. Dhe gjithashtu në qoftë se ju bëni të vazhdojë më me CS, këto janë bazat me të vërtetë të rëndësishme që ju do të duhet të dini. Pra, disa ditë do të jetë një pak më shumë ndihmë pset, por disa javë do të jetë e më shumë përmbajtje aktuale që nuk mund të duket super i dobishëm për ju tani për tani, por unë premtoj se nëse ju vazhdoni ne do të jetë shumë, shumë i dobishëm. 

Pra, kjo është ajo për seksionin. Poshtë në tela. Unë e bëri atë brenda një minutë. Por ju shkoni atje. Dhe unë do të ketë donuts apo karamele. A është dikush alergjik ndaj çdo gjë, nga rruga? Vezë dhe qumësht. Pra, donuts janë jo? OK. Dakord. Chocolate jo? Starburst. Starbursts janë të mira. OK. Ne do të kemi Starburst javën e ardhshme pastaj. Kjo është ajo që unë do të merrni. Ju djema keni një javë të madhe. Lexoni spekulim tuaj. 

Më lejoni të di nëse keni ndonjë pyetje. Pset dy notat duhet të jetë nga ju deri të enjten. Nëse keni ndonjë pyetje se si I vlerësohet diçka ose pse unë të vlerësohet diçka mënyrën se si unë ka, ju lutem, të vijnë të bisedoni me mua. Unë jam një pak i çmendur këtë javë, por unë premtoj Unë ende do të përgjigjen brenda 24 orëve. Pra, kemi një javë të madhe, të gjithë. Good luck në pset tuaj.