1 00:00:00,000 --> 00:00:03,332 >> [Musik spiller] 2 00:00:03,332 --> 00:00:06,490 >> ANDI Peng: Velkommen til uge 3 i afsnit. 3 00:00:06,490 --> 00:00:09,550 Tak, gutter, for alle der kommer til dette tidligste starttidspunkt dag. 4 00:00:09,550 --> 00:00:11,466 Vi har fået en dejlig, lille intime gruppe i dag. 5 00:00:11,466 --> 00:00:14,570 Så forhåbentlig vil vi komme til slut, måske tidligt, 6 00:00:14,570 --> 00:00:15,780 en lille smule tidligt i dag. 7 00:00:15,780 --> 00:00:22,057 Så hurtigt, blot nogle meddelelser for dagsordenen i dag. 8 00:00:22,057 --> 00:00:23,890 Før vi begynder, er vi kommer til at bare gå over 9 00:00:23,890 --> 00:00:28,910 nogle korte logistiske problemer, pset spørgsmål, debriefing, ting som. 10 00:00:28,910 --> 00:00:30,250 Og så vil vi dykke ret i. 11 00:00:30,250 --> 00:00:34,710 Vi vil bruge en debugger kaldet GDB til begynde Debunking vores kode, som David 12 00:00:34,710 --> 00:00:36,550 forklaret i foredrag forleden. 13 00:00:36,550 --> 00:00:39,420 Vi vil gå over de fire typer af slags. 14 00:00:39,420 --> 00:00:42,310 Vi vil gå over dem ret hurtigt da de er temmelig intensiv. 15 00:00:42,310 --> 00:00:45,710 Men ved, at alle dias og kildekoden er altid online. 16 00:00:45,710 --> 00:00:50,810 Så velkommen på din orientering, til gå tilbage og tage et kig på det. 17 00:00:50,810 --> 00:00:53,930 >> Vi vil gå igennem asymptotisk notation, som 18 00:00:53,930 --> 00:00:55,944 er bare en fancy måde at sige "runtime" 19 00:00:55,944 --> 00:00:58,360 hvor vi har den store O, som David forklaret i forelæsning. 20 00:00:58,360 --> 00:01:01,550 Og vi har også Omega, som er den nedre grænse runtime. 21 00:01:01,550 --> 00:01:06,450 Og vi vil tale lidt mere dybdegående om, hvordan de arbejder. 22 00:01:06,450 --> 00:01:10,160 Og endelig vil vi gå over binær søgning, fordi en masse af jer, der allerede har 23 00:01:10,160 --> 00:01:15,190 kiggede på dine psets sikkert, at det er et spørgsmål, som er i din pset. 24 00:01:15,190 --> 00:01:17,470 Så du alle være glade at vi dækker denne dag. 25 00:01:17,470 --> 00:01:20,610 >> Og endelig, pr din sektion feedback, jeg faktisk 26 00:01:20,610 --> 00:01:23,000 venstre omkring 15 minutter ved enden til bare gå over 27 00:01:23,000 --> 00:01:27,730 logistik pset3, spørgsmål, måske en smule vejledning, hvis du vil, 28 00:01:27,730 --> 00:01:28,990 før vi begynder programmering. 29 00:01:28,990 --> 00:01:30,890 Så lad os prøve at komme igennem materialet temmelig hurtigt. 30 00:01:30,890 --> 00:01:33,880 Og så kan vi bruge lidt tid tager flere spørgsmål til pset. 31 00:01:33,880 --> 00:01:35,230 OK. 32 00:01:35,230 --> 00:01:39,570 >> Hurtigt, så blot et par meddelelser før vi begynder i dag. 33 00:01:39,570 --> 00:01:45,410 For det første, velkommen til at gøre det gennem to af dine psets. 34 00:01:45,410 --> 00:01:49,432 Jeg tog et kig på your-- yeah, lad os få en runde af bifald for at en. 35 00:01:49,432 --> 00:01:51,140 Faktisk, jeg var virkelig, virkelig imponeret. 36 00:01:51,140 --> 00:01:55,800 Jeg sorterede den første pset for jer sidste uge, og du fyre gjorde utroligt. 37 00:01:55,800 --> 00:01:58,290 >> Stil var på punkt ud over et par kommentarer. 38 00:01:58,290 --> 00:02:00,660 Sørg for, at du altid er kommentere din kode. 39 00:02:00,660 --> 00:02:03,040 Men dine psets var på punkt. 40 00:02:03,040 --> 00:02:05,549 Og holde det op. 41 00:02:05,549 --> 00:02:08,090 Og det er godt for grader til se, at du fyre lægger 42 00:02:08,090 --> 00:02:10,704 i så stor en indsats i din stil og dit design i din kode 43 00:02:10,704 --> 00:02:12,120 at vi gerne for dig at se. 44 00:02:12,120 --> 00:02:16,450 Så jeg passerer langs min taknemmelighed for resten af ​​TAS. 45 00:02:16,450 --> 00:02:19,210 >> Men der er en få debriefing spørgsmål 46 00:02:19,210 --> 00:02:22,010 Jeg ønsker blot at gå over, at ville gøre både mit liv 47 00:02:22,010 --> 00:02:24,900 og en masse af den anden AT'er liv lidt nemmere. 48 00:02:24,900 --> 00:02:28,220 For det første har jeg bemærket dette fortid week-- hvor mange af jer 49 00:02:28,220 --> 00:02:32,301 har kørt check50 på din kode, før du sender? 50 00:02:32,301 --> 00:02:32,800 OK. 51 00:02:32,800 --> 00:02:36,690 Så alle bør gøre check50, because-- en secret-- vi faktisk 52 00:02:36,690 --> 00:02:41,540 køre check50 som en del af vores korrekthed scripts til at teste din kode. 53 00:02:41,540 --> 00:02:45,480 Så hvis din kode er ikke check50, efter al sandsynlighed, 54 00:02:45,480 --> 00:02:47,570 Det er nok at gå til svigte vores kontrol så godt. 55 00:02:47,570 --> 00:02:49,320 Nogle gange er du fyre har de rigtige svar. 56 00:02:49,320 --> 00:02:52,200 Ligesom i grådige, nogle af du har de rigtige tal, 57 00:02:52,200 --> 00:02:53,960 du bare udskrive nogle ekstra ting. 58 00:02:53,960 --> 00:02:55,940 Og det ekstra ting faktisk ikke checken, 59 00:02:55,940 --> 00:02:58,440 fordi computeren ikke virkelig ved, hvad det er på udkig efter. 60 00:02:58,440 --> 00:03:00,981 Og så vil det bare løbe igennem, se, at dit output ikke 61 00:03:00,981 --> 00:03:03,810 matche, hvad vi forventer svaret at være, og markere det er forkert. 62 00:03:03,810 --> 00:03:06,560 >> Og jeg ved, at der skete i nogle af dine sager i denne uge. 63 00:03:06,560 --> 00:03:09,870 Så jeg gik tilbage og manuelt nedklassificeret alles kode. 64 00:03:09,870 --> 00:03:12,780 I fremtiden selv, please, skal du sørge for 65 00:03:12,780 --> 00:03:14,570 at du kører tjek 50 på din kode. 66 00:03:14,570 --> 00:03:17,970 Fordi det er sådan en smerte for TA nødt til at gå tilbage og manuelt nedklassificering 67 00:03:17,970 --> 00:03:21,197 hver eneste pset for hver enkelt, lille savnet instans. 68 00:03:21,197 --> 00:03:22,530 Så jeg ikke tage nogen point. 69 00:03:22,530 --> 00:03:25,210 Jeg tror, ​​jeg tog måske en eller to for design. 70 00:03:25,210 --> 00:03:27,710 I fremtiden, selv hvis du ikke check50, 71 00:03:27,710 --> 00:03:31,330 punkter vil blive taget off for korrekthed. 72 00:03:31,330 --> 00:03:35,020 >> Endvidere er psets grund fredagen ved middagstid. 73 00:03:35,020 --> 00:03:38,990 Jeg tror, ​​der er en syv minutters sene afdragsfri periode, at vi giver dig. 74 00:03:38,990 --> 00:03:42,434 Per Harvard tid, er de lov til at være syv minutter for sent til alt. 75 00:03:42,434 --> 00:03:44,350 Så her på Yale, vi får holde sig til, at så godt. 76 00:03:44,350 --> 00:03:47,910 Men temmelig meget på 00:07, hvis din pset ikke er i, 77 00:03:47,910 --> 00:03:49,720 det vil blive markeret som sent. 78 00:03:49,720 --> 00:03:53,160 Og så mens det er mærket så sent, at TA-- jeg er 79 00:03:53,160 --> 00:03:54,870 stadig vil være klassificering dine psets. 80 00:03:54,870 --> 00:03:56,760 Så du stadig se en karakter vises. 81 00:03:56,760 --> 00:03:58,820 Dog ved, at ved I slutningen af ​​semestret, 82 00:03:58,820 --> 00:04:02,270 alle sene psets vil bare være automatisk nulstilles af computeren. 83 00:04:02,270 --> 00:04:04,490 >> Det gør vi af to grunde. 84 00:04:04,490 --> 00:04:09,220 Én, nogle gange får vi undskyldt, ligesom Dean undskyldninger, 85 00:04:09,220 --> 00:04:10,762 senere, at jeg ikke ved om endnu. 86 00:04:10,762 --> 00:04:13,761 Så vi vil gerne sikre, at vi er klassificering alt bare i tilfælde, ligesom, jeg er 87 00:04:13,761 --> 00:04:15,080 mangler et dekanens undskyldning. 88 00:04:15,080 --> 00:04:17,000 Og for det andet, skal du sind, kan du stadig 89 00:04:17,000 --> 00:04:19,370 drop én pset der har fulde omfang point. 90 00:04:19,370 --> 00:04:21,430 Og så vi gerne til lønklasse alle dine psets bare 91 00:04:21,430 --> 00:04:24,730 at sikre, at din rækkevidde s der, og du forsøger dem. 92 00:04:24,730 --> 00:04:29,150 Så selv om det er sent, vil du stadig få kredit for rækkevidde punkter, tror jeg. 93 00:04:29,150 --> 00:04:33,730 >> Så moralske af historien er, at gøre at dine psets er i on-tiden. 94 00:04:33,730 --> 00:04:38,350 Og hvis de ikke er i den tid, vide, at det ikke er stor. 95 00:04:38,350 --> 00:04:41,678 Ja, inden jeg går videre, nogen der har spørgsmål vedrørende pset feedback? 96 00:04:41,678 --> 00:04:42,178 Ja. 97 00:04:42,178 --> 00:04:43,630 >> PUBLIKUM: Sagde du, vi kan falde en af ​​psets? 98 00:04:43,630 --> 00:04:44,296 >> ANDI Peng: Ja. 99 00:04:44,296 --> 00:04:47,050 Så der er ni psets samlet i løbet af semestret. 100 00:04:47,050 --> 00:04:50,610 Og hvis du har rækkevidde points-- så omfanget er bare, 101 00:04:50,610 --> 00:04:53,567 temmelig meget, er du forsøger at problem, er du sætte i gang, 102 00:04:53,567 --> 00:04:56,150 viser du, at du har demonstreret du har læst spec. 103 00:04:56,150 --> 00:04:57,191 Det er temmelig meget rækkevidde. 104 00:04:57,191 --> 00:04:59,370 Og hvis du opfylder Anvendelsesområde punkter, vi 105 00:04:59,370 --> 00:05:03,360 kan droppe laveste en ud af fulde omfang. 106 00:05:03,360 --> 00:05:06,790 Så det er i din fordel at udfylde og prøve hver pset. 107 00:05:06,790 --> 00:05:10,320 >> Selv upload-- hvis ingen af dem arbejde, uploade dem alle. 108 00:05:10,320 --> 00:05:13,711 Og så vil vi forhåbentlig kunne give dig nogle af disse punkter tilbage. 109 00:05:13,711 --> 00:05:14,210 Cool. 110 00:05:14,210 --> 00:05:16,780 Andre spørgsmål? 111 00:05:16,780 --> 00:05:17,840 Great. 112 00:05:17,840 --> 00:05:21,960 >> For det andet kontor hours-- et par hurtige noter om kontortid. 113 00:05:21,960 --> 00:05:24,300 Så først, kommer tidligt på ugen. 114 00:05:24,300 --> 00:05:26,909 Ingen er nogensinde på kontortid om mandagen. 115 00:05:26,909 --> 00:05:28,700 Christabel kom til kontortid aftes. 116 00:05:28,700 --> 00:05:29,691 Ja, Christabel. 117 00:05:29,691 --> 00:05:32,190 Og hvad gjorde vi har på kontoret timer i aftes, Christabel? 118 00:05:32,190 --> 00:05:33,020 >> PUBLIKUM: Vi havde is. 119 00:05:33,020 --> 00:05:36,160 >> ANDI Peng: Så det er rigtigt, vi havde is på kontortid aftes. 120 00:05:36,160 --> 00:05:39,390 Mens jeg ikke kan love dig, at vi får is på kontortid 121 00:05:39,390 --> 00:05:43,230 hver uge, hvad jeg kan love dig er, at der vil være en betydelig 122 00:05:43,230 --> 00:05:45,380 bedre studerende til TA-forholdet. 123 00:05:45,380 --> 00:05:47,650 Ligesom legit, det er ligesom 3-1. 124 00:05:47,650 --> 00:05:50,350 Betragtninger, kontrast, at med Torsdag du har omkring 150 125 00:05:50,350 --> 00:05:52,830 virkelig stressede børn og ingen is. 126 00:05:52,830 --> 00:05:55,360 Og det er bare ikke produktive for nogen. 127 00:05:55,360 --> 00:05:58,730 Så moralske af historien er, kommer tidligt til kontortid og gode ting 128 00:05:58,730 --> 00:06:00,310 vil ske. 129 00:06:00,310 --> 00:06:02,110 >> Også, kommer parat til at stille spørgsmål. 130 00:06:02,110 --> 00:06:03,200 Du ved? 131 00:06:03,200 --> 00:06:05,420 Uanset hvad TAS, I tror, ​​har sagt, 132 00:06:05,420 --> 00:06:10,710 Vi har været at få et par studerende der kommer ind på torsdag på, ligesom, 10:50 133 00:06:10,710 --> 00:06:15,100 ikke have læst spec være som hjælp mig, hjælp mig. 134 00:06:15,100 --> 00:06:18,200 Desværre på det tidspunkt, der er ikke meget vi kan gøre for at hjælpe dig. 135 00:06:18,200 --> 00:06:19,590 Så kan du komme tidligt på ugen. 136 00:06:19,590 --> 00:06:22,040 Kom tidligt at kontortid. 137 00:06:22,040 --> 00:06:23,350 Kommer parat til at stille spørgsmål. 138 00:06:23,350 --> 00:06:25,310 Sørg for at du, som en studerende, er der, hvor 139 00:06:25,310 --> 00:06:27,620 du skal være således, at AT'er kan vejlede dig sammen, 140 00:06:27,620 --> 00:06:32,850 Hvilket er, hvad kontortid bør tildeles efter. 141 00:06:32,850 --> 00:06:37,380 >> For det andet, så jeg ved professorer gerne overraske os med tests. 142 00:06:37,380 --> 00:06:39,439 Jeg havde en professor dem lignende, slå om, ved den måde, 143 00:06:39,439 --> 00:06:41,230 husk at midterm du har næste mandag. 144 00:06:41,230 --> 00:06:42,855 Ja, jeg vidste ikke, om det midterm. 145 00:06:42,855 --> 00:06:45,630 Så jeg har tænkt mig at være, at TA der minder dig alt, quiz 146 00:06:45,630 --> 00:06:47,270 0-- fordi, du ved, vi er CS. 147 00:06:47,270 --> 00:06:50,730 Nu, hvor vi har gjort arrays, får du hvorfor det er quiz 0, ikke quiz 1, eh? 148 00:06:50,730 --> 00:06:51,320 OK. 149 00:06:51,320 --> 00:06:52,490 Åh, jeg fik nogle chuckles på at en. 150 00:06:52,490 --> 00:06:53,120 OK. 151 00:06:53,120 --> 00:06:59,710 >> Så quiz 0 vil være 14 oktober, hvis du er i mandag onsdag sektion 152 00:06:59,710 --> 00:07:02,920 og oktober 15, hvis du er i tirsdag-torsdag sektionen. 153 00:07:02,920 --> 00:07:05,630 Dette gælder ikke for dem af jer på Harvard 154 00:07:05,630 --> 00:07:10,350 who-- jeg tror du vil alle være tage dine quizzer på 14.. 155 00:07:10,350 --> 00:07:13,560 >> Så yeah, i næste uge, hvis David i foredrag, går, 156 00:07:13,560 --> 00:07:15,747 yeah, så om det Quizzen næste uge, jer alle 157 00:07:15,747 --> 00:07:17,580 vil ikke blive chokeret, fordi du kom til afsnit 158 00:07:17,580 --> 00:07:19,664 og du ved, at din quiz 0 er i to uger. 159 00:07:19,664 --> 00:07:21,580 Og vi vil have bedømmelse sessioner og alt. 160 00:07:21,580 --> 00:07:26,360 Så ingen bekymringer om være bange for det. 161 00:07:26,360 --> 00:07:29,890 Eventuelle spørgsmål before-- spørgsmål på alle logistiske problemer med hensyn til, 162 00:07:29,890 --> 00:07:32,591 sortering, kontortid, sektioner? 163 00:07:32,591 --> 00:07:33,090 Ja. 164 00:07:33,090 --> 00:07:35,100 >> PUBLIKUM: Så quizzen er kommer til at være under forelæsning? 165 00:07:35,100 --> 00:07:35,766 >> ANDI Peng: Ja. 166 00:07:35,766 --> 00:07:39,460 Så quizzen, tror jeg, er 60 minut tildelt i denne tid slot 167 00:07:39,460 --> 00:07:42,240 at du bare vil tage i auditoriet. 168 00:07:42,240 --> 00:07:44,810 Så du behøver ikke at komme i på, ligesom, en tilfældig 07:00. 169 00:07:44,810 --> 00:07:46,140 Det er alle gode. 170 00:07:46,140 --> 00:07:47,100 Ja. 171 00:07:47,100 --> 00:07:50,060 Cool. 172 00:07:50,060 --> 00:07:50,840 >> Okay. 173 00:07:50,840 --> 00:07:54,330 Så vi kommer til at indføre et koncept for dig 174 00:07:54,330 --> 00:08:00,760 denne uge, at David har allerede slags af berørt i forelæsning i sidste uge. 175 00:08:00,760 --> 00:08:02,010 Det hedder GDB. 176 00:08:02,010 --> 00:08:05,570 Og hvor mange af jer, mens der i forløbet af at skrive dine psets, 177 00:08:05,570 --> 00:08:09,981 har bemærket en stor knap, der hedder "Debug" på toppen af ​​dit IDE? 178 00:08:09,981 --> 00:08:10,480 OK. 179 00:08:10,480 --> 00:08:13,770 Så nu får vi faktisk komme til at grave mysteriet om, hvad der knap faktisk 180 00:08:13,770 --> 00:08:14,270 gør. 181 00:08:14,270 --> 00:08:16,790 Og jeg garanterer dig, er det en smukke, smukke ting. 182 00:08:16,790 --> 00:08:20,740 >> Så indtil nu, tror jeg der har været to ting 183 00:08:20,740 --> 00:08:23,320 studerende har været typisk gør, når debugging psets. 184 00:08:23,320 --> 00:08:27,635 Én, de enten tilføje printf () - så hvert par linjer, 185 00:08:27,635 --> 00:08:29,760 de tilføje i en printf () - Åh, hvad er denne variabel? 186 00:08:29,760 --> 00:08:32,551 Åh, hvad er denne variabel nu-- og du slags se progression 187 00:08:32,551 --> 00:08:33,940 af din kode, som det kører. 188 00:08:33,940 --> 00:08:37,030 Eller den anden metode kids gøre, er at de bare skrive det hele 189 00:08:37,030 --> 00:08:38,610 og derefter gå ligesom dette i slutningen. 190 00:08:38,610 --> 00:08:39,970 Forhåbentlig det fungerer. 191 00:08:39,970 --> 00:08:44,851 Jeg garanterer dig, GDB er bedre end begge disse metoder. 192 00:08:44,851 --> 00:08:45,350 Ja. 193 00:08:45,350 --> 00:08:46,980 Så dette vil være din nye bedste ven. 194 00:08:46,980 --> 00:08:51,780 Fordi det er en smuk ting der visuelt viser både 195 00:08:51,780 --> 00:08:54,850 hvad din kode gør på et bestemt punkt 196 00:08:54,850 --> 00:08:57,486 samt hvad alle dine variabler bærer, 197 00:08:57,486 --> 00:08:59,610 ligesom hvad deres værdier er, på det specifikke punkt. 198 00:08:59,610 --> 00:09:02,670 Og på denne måde, kan du virkelig sætte breakpoints i din kode. 199 00:09:02,670 --> 00:09:04,350 Du kan køre igennem linje for linje. 200 00:09:04,350 --> 00:09:07,324 Og GDB vil bare have for Dem, der vises for dig, 201 00:09:07,324 --> 00:09:09,490 hvad alle dine variabler er, hvad laver de, 202 00:09:09,490 --> 00:09:10,656 hvad der foregår i koden. 203 00:09:10,656 --> 00:09:13,240 Og på en sådan måde, er det så meget lettere at se 204 00:09:13,240 --> 00:09:17,120 hvad der sker i stedet for printf-ing eller skrive ned dine udtalelser. 205 00:09:17,120 --> 00:09:19,160 >> Så vi vil gøre et eksempel på dette senere. 206 00:09:19,160 --> 00:09:20,660 Så det synes lidt abstrakt. 207 00:09:20,660 --> 00:09:23,490 Ingen bekymringer, vil vi gøre eksempler. 208 00:09:23,490 --> 00:09:29,170 Og så væsentlige, de tre største, mest anvendte funktioner, du har brug for i GDB 209 00:09:29,170 --> 00:09:32,500 er de næste, trin over, og Træd ind knapper. 210 00:09:32,500 --> 00:09:34,860 Jeg har tænkt mig at gå over der, faktisk, lige nu. 211 00:09:34,860 --> 00:09:40,930 >> Så kan du fyre alle se, at eller skal jeg zoome ind lidt? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 I ryggen, kan du se det? 214 00:09:44,470 --> 00:09:45,730 Skal jeg zoome ind? 215 00:09:45,730 --> 00:09:46,480 Bare en lille smule? 216 00:09:46,480 --> 00:09:49,390 OK, cool. 217 00:09:49,390 --> 00:09:50,280 Der vi går. 218 00:09:50,280 --> 00:09:50,960 OK. 219 00:09:50,960 --> 00:09:57,000 >> Så jeg har, her, min implementering for grådige. 220 00:09:57,000 --> 00:10:01,430 Og mens en masse af jer skrev grådige i while-løkke form-- at 221 00:10:01,430 --> 00:10:04,890 er en helt acceptabel måde at gøre det-- en anden måde at gøre det på er simpelthen at 222 00:10:04,890 --> 00:10:06,280 opdele i modulo. 223 00:10:06,280 --> 00:10:09,290 Fordi så kan du få din værdi og så har din resten. 224 00:10:09,290 --> 00:10:11,150 Og så kan du bare føje det hele sammen. 225 00:10:11,150 --> 00:10:13,390 Er logikken i, hvad jeg gør her giver mening for alle, 226 00:10:13,390 --> 00:10:14,117 før vi begynder? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 Slags? 229 00:10:17,980 --> 00:10:18,710 Cool. 230 00:10:18,710 --> 00:10:19,210 Great. 231 00:10:19,210 --> 00:10:21,290 Det er en temmelig sexet stykke kode, vil jeg sige. 232 00:10:21,290 --> 00:10:23,502 Ligesom jeg sagde, David, i foredrag, efter et stykke tid, 233 00:10:23,502 --> 00:10:25,960 du vil alle begynde at se kode som noget, der er smukt. 234 00:10:25,960 --> 00:10:29,950 Og nogle gange, når du ser smuk kode, det er sådan en vidunderlig følelse. 235 00:10:29,950 --> 00:10:35,410 >> Så dog mens denne kode er meget smuk, betyder det ikke korrekt. 236 00:10:35,410 --> 00:10:37,750 Så lad os køre check50 på dette. 237 00:10:37,750 --> 00:10:39,440 Tjek 50 20-- oop. 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 Er det pset2? 241 00:10:44,990 --> 00:10:46,870 Ja. 242 00:10:46,870 --> 00:10:47,520 Åh, pset1. 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 OK. 245 00:10:52,890 --> 00:10:53,900 Så vi kører check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> Og som du fyre kan se her, det er ikke et par tilfælde. 248 00:11:07,170 --> 00:11:10,165 Og for nogle af jer, i løbet af at gøre dit problem sæt, 249 00:11:10,165 --> 00:11:11,110 du er ligesom, ah, hvorfor er det ikke fungerer. 250 00:11:11,110 --> 00:11:13,318 Hvorfor er det at arbejde for nogle værdier, men ikke for andre? 251 00:11:13,318 --> 00:11:17,760 Nå, er GDB vil hjælpe dig tal ud af, hvorfor disse input ikke fungerede. 252 00:11:17,760 --> 00:11:18,320 >> OK. 253 00:11:18,320 --> 00:11:21,640 Så lad os se, en af ​​de checks Jeg tabte check50 254 00:11:21,640 --> 00:11:24,920 var input værdi på 0,41. 255 00:11:24,920 --> 00:11:27,830 Så det korrekte svar, der du skal få er et 4. 256 00:11:27,830 --> 00:11:33,090 Men i stedet hvad jeg udskrivning ud er 3-n, som er ukorrekt. 257 00:11:33,090 --> 00:11:36,190 Så lad os bare køre det manuelt, bare sørge for, at check50 virker. 258 00:11:36,190 --> 00:11:36,940 Lad os gøre ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Ups, jeg er nødt til at gøre grådige. 261 00:11:43,340 --> 00:11:43,840 Der vi går. 262 00:11:43,840 --> 00:11:44,381 Nu ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Hvor meget skylder? 265 00:11:47,670 --> 00:11:49,550 Lad os gøre 0,41. 266 00:11:49,550 --> 00:11:52,590 Og jep, vi ser her at det er udsende 3 267 00:11:52,590 --> 00:11:55,160 når det korrekte svar, Faktisk bør være 4. 268 00:11:55,160 --> 00:12:01,460 Så lad os komme ind GDB og se, hvordan vi kan gå om fastsættelse af dette problem. 269 00:12:01,460 --> 00:12:03,992 >> Så det første skridt i altid debugging din kode 270 00:12:03,992 --> 00:12:05,950 er at sætte et breakpoint, eller et punkt, hvor du 271 00:12:05,950 --> 00:12:09,079 vil have computeren eller debugger til at begynde at kigge på. 272 00:12:09,079 --> 00:12:11,120 Så hvis du ikke virkelig vide, hvad dit problem er, 273 00:12:11,120 --> 00:12:14,670 normalt, den typiske ting, vi ønsker at gøre, er at sætte vores breakpoint på main. 274 00:12:14,670 --> 00:12:18,520 Så hvis du fyre kan se dette røde knap lige der, 275 00:12:18,520 --> 00:12:22,860 jep, det var mig at sætte en -grænseværdien for den vigtigste funktion. 276 00:12:22,860 --> 00:12:24,130 Jeg klikker det. 277 00:12:24,130 --> 00:12:26,130 >> Og så kan jeg gå op til min Debug-knappen. 278 00:12:26,130 --> 00:12:27,036 Jeg ramte den knap. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Lad mig ind igen, hvis jeg kan. 281 00:12:36,555 --> 00:12:38,020 Der vi går. 282 00:12:38,020 --> 00:12:40,730 Så vi har, her, et panel til højre. 283 00:12:40,730 --> 00:12:43,680 Jeg er ked af, fyre i ryggen, du kan ikke rigtig se rigtig godt. 284 00:12:43,680 --> 00:12:49,090 Men det væsentlige alle denne ret panel gør 285 00:12:49,090 --> 00:12:53,130 holder styr på både den fremhævede line, som er kodelinje 286 00:12:53,130 --> 00:12:56,640 at computeren kører i øjeblikket, såvel som alle dine variabler 287 00:12:56,640 --> 00:12:57,600 hernede. 288 00:12:57,600 --> 00:13:00,487 >> Så du har fået cents, mønter, n, alle erklæret forskellige ting 289 00:13:00,487 --> 00:13:01,070 på dette tidspunkt. 290 00:13:01,070 --> 00:13:04,850 Ingen bekymringer, fordi vi har faktisk ikke initialiseret dem til eventuelle variable endnu. 291 00:13:04,850 --> 00:13:07,200 Så i din computer, din computer er bare at se, 292 00:13:07,200 --> 00:13:14,376 Åh, 32767 var den sidst brugte funktion af denne hukommelsesplads i min computer. 293 00:13:14,376 --> 00:13:16,000 Og så det er hvor cent i øjeblikket er. 294 00:13:16,000 --> 00:13:19,360 Men nej, at når du kører koden, Det bør blive initialiseret. 295 00:13:19,360 --> 00:13:24,110 >> Så lad os gå igennem, linje linje, hvad der foregår her. 296 00:13:24,110 --> 00:13:25,350 OK. 297 00:13:25,350 --> 00:13:29,400 Så heroppe er tre knapper, jeg forklarede bare. 298 00:13:29,400 --> 00:13:34,090 Du har Play, eller Kør-funktion, knap, har du Step-knappen igen, 299 00:13:34,090 --> 00:13:36,600 og du har også Træd ind knappen. 300 00:13:36,600 --> 00:13:41,260 Og i det væsentlige, alle tre dem bare gå gennem din kode 301 00:13:41,260 --> 00:13:42,690 og gøre forskellige ting. 302 00:13:42,690 --> 00:13:45,680 >> Så typisk, når du debugging, Vi ønsker ikke at bare trykke Play, 303 00:13:45,680 --> 00:13:47,930 fordi Play vil bare køre din kode til slutningen af ​​det. 304 00:13:47,930 --> 00:13:49,070 Og derefter vil du faktisk ikke vide, hvad dit problem 305 00:13:49,070 --> 00:13:51,432 er medmindre du indstille flere breakpoints. 306 00:13:51,432 --> 00:13:53,890 Hvis du indstille flere breakpoints, Det vil bare automatisk 307 00:13:53,890 --> 00:13:56,030 løbe fra den ene breakpoint, til den næste, til den næste. 308 00:13:56,030 --> 00:13:58,030 Men i dette tilfælde vi har bare, at man, fordi vi 309 00:13:58,030 --> 00:13:59,970 ønsker at arbejde os fra top ned til bunden. 310 00:13:59,970 --> 00:14:04,830 Så vi kommer til at ignorere, at knap lige nu med henblik på dette program. 311 00:14:04,830 --> 00:14:08,230 >> Så trin over funktion bare trin over hver enkelt linje 312 00:14:08,230 --> 00:14:11,510 og fortæller dig, hvad computeren gør. 313 00:14:11,510 --> 00:14:14,630 Den Træd ind funktionen går i den aktuelle funktion 314 00:14:14,630 --> 00:14:16,000 der er på din linje kode. 315 00:14:16,000 --> 00:14:19,070 Så for eksempel, som printf (), der er en funktion, ikke? 316 00:14:19,070 --> 00:14:21,980 Hvis jeg ønskede at fysisk trin i printf () funktion, 317 00:14:21,980 --> 00:14:25,610 Jeg vil faktisk gå ind i stykke kode, hvor printf () blev skrevet og se 318 00:14:25,610 --> 00:14:26,730 hvad der foregår der. 319 00:14:26,730 --> 00:14:29,924 >> Men typisk antager vi, at den kode, vi giver dig fungerer. 320 00:14:29,924 --> 00:14:31,340 Vi antager printf () arbejder. 321 00:14:31,340 --> 00:14:33,170 Vi antager, at GetInt () arbejder. 322 00:14:33,170 --> 00:14:35,170 Så der er ingen grund til at træde ind i disse funktioner. 323 00:14:35,170 --> 00:14:37,170 Men hvis der er funktioner at du skriver dig selv 324 00:14:37,170 --> 00:14:39,060 at du ønsker at kontrollere ud af, hvad der foregår, 325 00:14:39,060 --> 00:14:41,200 du ønsker at træde ind i denne funktion. 326 00:14:41,200 --> 00:14:43,940 >> Så lige nu er vi bare at træde over dette stykke kode. 327 00:14:43,940 --> 00:14:44,485 Så lad os se. 328 00:14:44,485 --> 00:14:46,547 Åh, print, "Oh hai, hvordan meget forandring skylder? " 329 00:14:46,547 --> 00:14:47,130 Vi er ligeglade. 330 00:14:47,130 --> 00:14:49,830 Vi ved, at arbejder, så vi træder over det. 331 00:14:49,830 --> 00:14:53,290 >> Så n, som er vores float, at vi har initialized-- eller declared-- 332 00:14:53,290 --> 00:14:56,810 op i toppen, er vi nu svarende til at GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Så lad os træde over det. 334 00:14:57,810 --> 00:14:59,580 Og vi ser på bunden her, programmet 335 00:14:59,580 --> 00:15:03,360 er at spørge mig for at indtaste en værdi. 336 00:15:03,360 --> 00:15:08,580 Så lad os input den værdi, vi ønsker at teste her, som er 0,41. 337 00:15:08,580 --> 00:15:09,160 Great. 338 00:15:09,160 --> 00:15:12,780 >> Så nu n- gør du fyre se Her ved bottom-- det er 339 00:15:12,780 --> 00:15:15,140 stored-- fordi vi ikke har rundet endnu, det er 340 00:15:15,140 --> 00:15:19,540 gemmes i denne lignende gigant float, der er ,4099999996, 341 00:15:19,540 --> 00:15:22,550 som er tæt nok til vores formål, lige nu, til 0,41. 342 00:15:22,550 --> 00:15:26,090 Og så vil vi se senere, da vi fortsætte med at træde over programmet, 343 00:15:26,090 --> 00:15:29,850 efter her, er n blevet afrundede og cents er blevet 41. 344 00:15:29,850 --> 00:15:30,350 Great. 345 00:15:30,350 --> 00:15:32,230 Så vi ved, at vores afrunding arbejdstid. 346 00:15:32,230 --> 00:15:34,700 Vi ved, at vi har den korrekte antal cents, 347 00:15:34,700 --> 00:15:36,990 så vi ved, at det er egentlig ikke problemet. 348 00:15:36,990 --> 00:15:40,050 >> Så vi fortsætter med at træde indenfor dette program. 349 00:15:40,050 --> 00:15:40,900 Vi går her. 350 00:15:40,900 --> 00:15:46,139 Og så efter denne linje kode, vi bør vide, hvor mange kvartaler vi har. 351 00:15:46,139 --> 00:15:46,680 Vi trin over. 352 00:15:46,680 --> 00:15:52,040 Og du ser vi, i virkeligheden, har en kvartal fordi vi har trukket 25 353 00:15:52,040 --> 00:15:53,790 fra vores oprindelige værdi på 41. 354 00:15:53,790 --> 00:15:55,890 Og vi har 16 til venstre for vores cents. 355 00:15:55,890 --> 00:15:58,830 >> Er alle forstå, hvordan programmet er at træde igennem 356 00:15:58,830 --> 00:16:02,980 og hvorfor cents er nu blevet 16 og hvorfor, nu, mønter er blevet 1? 357 00:16:02,980 --> 00:16:04,610 Alle er efter denne logik? 358 00:16:04,610 --> 00:16:05,110 Cool. 359 00:16:05,110 --> 00:16:07,860 Så i dette punkt, at programmets arbejde, ikke? 360 00:16:07,860 --> 00:16:09,797 Vi ved, det gør præcis hvad vi ønsker det. 361 00:16:09,797 --> 00:16:11,880 Og det gjorde vi faktisk ikke nødt til at udskrive, åh, hvad 362 00:16:11,880 --> 00:16:14,430 er cents på dette punkt, hvad der er mønter på dette punkt. 363 00:16:14,430 --> 00:16:17,170 >> Vi fortsætte med at gå gennem programmet. 364 00:16:17,170 --> 00:16:18,100 Træd over. 365 00:16:18,100 --> 00:16:18,620 Cool. 366 00:16:18,620 --> 00:16:19,700 Vi gå over Dimes. 367 00:16:19,700 --> 00:16:20,200 Great. 368 00:16:20,200 --> 00:16:22,367 Vi ser, at det er taget off $ 0,10 for en skilling. 369 00:16:22,367 --> 00:16:23,450 Og nu har vi to mønter. 370 00:16:23,450 --> 00:16:25,260 Det er korrekt. 371 00:16:25,260 --> 00:16:31,555 >> Vi gå over øre, og vi ser at vi har tilovers cents. 372 00:16:31,555 --> 00:16:32,680 Hmm, det er mærkeligt. 373 00:16:32,680 --> 00:16:37,540 Heroppe på programmet, skulle jeg at have trukket mine øre. 374 00:16:37,540 --> 00:16:39,400 Måske var jeg bare ikke at gøre det linje lige. 375 00:16:39,400 --> 00:16:42,190 Og desværre, kan du se her, fordi vi ved 376 00:16:42,190 --> 00:16:44,360 at vi er ved at styrke gennem ledninger 32 og 33, 377 00:16:44,360 --> 00:16:50,560 det er, hvor vores program uretmæssigt havde variabler køre. 378 00:16:50,560 --> 00:16:55,136 Så vi kan se og se, åh, Jeg fratrække cents her, 379 00:16:55,136 --> 00:16:57,010 men jeg er faktisk ikke tilføje til min møntværdi. 380 00:16:57,010 --> 00:16:57,860 Jeg tilføje til cents. 381 00:16:57,860 --> 00:17:00,234 Og jeg ønsker ikke at føje til cent, jeg ønsker at tilføje til mønter. 382 00:17:00,234 --> 00:17:05,420 Så hvis vi ændrer det til mønter, vi har fået et arbejdsprogram. 383 00:17:05,420 --> 00:17:06,730 Jeg kan køre check50. 384 00:17:06,730 --> 00:17:11,063 Du kan bare gå ud fra GDB højre her og derefter køre check50 igen. 385 00:17:11,063 --> 00:17:11,938 Jeg kunne bare gøre det. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Jeg er nødt til at gøre grådige. 388 00:17:18,480 --> 00:17:19,940 0,41. 389 00:17:19,940 --> 00:17:22,819 Og her, det er udskrivning ud det rigtige svar. 390 00:17:22,819 --> 00:17:26,569 >> Så som du fyre kan se, GDB er en virkelig kraftfuldt værktøj 391 00:17:26,569 --> 00:17:29,940 for når vi har så meget kode foregår og så mange variabler 392 00:17:29,940 --> 00:17:32,510 at det er svært for os, som et menneske, til at holde styr på. 393 00:17:32,510 --> 00:17:35,360 Computeren, i GDB debugger, har evnen 394 00:17:35,360 --> 00:17:37,020 at holde styr på alt. 395 00:17:37,020 --> 00:17:40,480 Jeg ved, i Visionaire, du fyre sandsynligvis kunne have ramt nogle segmentering fejl 396 00:17:40,480 --> 00:17:43,150 fordi du kørte out of bounds i dit array. 397 00:17:43,150 --> 00:17:46,510 I eksemplet med Cæsar, det er præcis, hvad jeg har implementeret her. 398 00:17:46,510 --> 00:17:50,060 >> Så jeg glemte at kontrollere for hvad der ville ske, hvis jeg 399 00:17:50,060 --> 00:17:52,510 havde ikke to kommandolinjeargumenter. 400 00:17:52,510 --> 00:17:53,880 Jeg vidste bare ikke sætte i denne kontrol. 401 00:17:53,880 --> 00:17:57,380 Og så hvis jeg kører Debug-- jeg indstille min breakpoint til højre der. 402 00:17:57,380 --> 00:17:58,055 Jeg løber Debug. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> OK. 405 00:18:16,550 --> 00:18:17,050 Ja. 406 00:18:17,050 --> 00:18:20,350 Så faktisk blev GDB meningen at have fortalt mig der 407 00:18:20,350 --> 00:18:22,300 var en segmentering fejl der. 408 00:18:22,300 --> 00:18:24,883 Jeg ved ikke, hvad der foregik lige der, men da jeg kørte det, 409 00:18:24,883 --> 00:18:25,590 det fungerede. 410 00:18:25,590 --> 00:18:29,410 Når du kører linjer kode igennem og GDB måske bare pludselig holde op på dig, 411 00:18:29,410 --> 00:18:31,540 gå op og se hvad den røde fejlen er. 412 00:18:31,540 --> 00:18:33,930 Det vil fortælle dig, hey, du havde en segmentering fejl, 413 00:18:33,930 --> 00:18:38,550 hvilket betyder, at du har forsøgt at få adgang plads i et array, der ikke eksisterede. 414 00:18:38,550 --> 00:18:39,050 Ja. 415 00:18:39,050 --> 00:18:43,280 >> Så i det næste problem fastsat i denne uge, du fyre 416 00:18:43,280 --> 00:18:45,600 vil sandsynligvis have en masse variabler flyder rundt. 417 00:18:45,600 --> 00:18:48,560 Du kommer ikke til at være sikker på, hvad de alle betyder på et bestemt tidspunkt. 418 00:18:48,560 --> 00:18:53,560 Så GDB vil virkelig hjælpe dig med at regne ud af, hvad de alle er svarende 419 00:18:53,560 --> 00:18:55,940 og at kunne se, at visuelt. 420 00:18:55,940 --> 00:19:01,995 Er der nogen forvirret om, hvordan noget af det var i orden? 421 00:19:01,995 --> 00:19:02,495 Cool. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Okay. 424 00:19:10,620 --> 00:19:14,260 Så efter det, vi er kommer til at dykke ret 425 00:19:14,260 --> 00:19:17,562 i er fire forskellige typer af slags til denne uge. 426 00:19:17,562 --> 00:19:19,520 Hvor mange af jer, først af alt, inden vi begynder, 427 00:19:19,520 --> 00:19:23,020 har læst hele spec for pset3? 428 00:19:23,020 --> 00:19:23,824 OK. 429 00:19:23,824 --> 00:19:24,740 Jeg er stolt af jer. 430 00:19:24,740 --> 00:19:29,110 Det er ligesom halvdelen af ​​klassen, som er betydeligt mere end sidste gang. 431 00:19:29,110 --> 00:19:33,950 >> Så det er godt, fordi når vi taler om indholdet 432 00:19:33,950 --> 00:19:36,170 i lecture-- eller ked af det, i section-- Jeg kan lide 433 00:19:36,170 --> 00:19:38,210 at relatere en masse, der tilbage til, hvad det pset er 434 00:19:38,210 --> 00:19:40,210 og hvordan du vil implementere det i din pset. 435 00:19:40,210 --> 00:19:42,400 Så hvis du kommer med læse spec, det vil 436 00:19:42,400 --> 00:19:45,510 være meget nemmere for dig at forstå hvad jeg taler om, når jeg siger, 437 00:19:45,510 --> 00:19:48,720 åh hey, kan dette være en rigtig godt sted at gennemføre denne slags. 438 00:19:48,720 --> 00:19:52,870 Så dem af jer der har læst den spec vide, at som en del af din pset, 439 00:19:52,870 --> 00:19:54,900 du nødt til at skrive en type slags. 440 00:19:54,900 --> 00:19:58,670 Så det kan være meget nyttigt for en masse af jer i dag. 441 00:19:58,670 --> 00:20:01,760 >> Så vi vil starte med, væsentlige den mest simple form 442 00:20:01,760 --> 00:20:04,580 af sortering, udvælgelse slags. 443 00:20:04,580 --> 00:20:06,800 Den typiske algoritme til hvordan vi ville gå om dette 444 00:20:06,800 --> 00:20:10,460 is-- David gik gennem disse alle i foredrag, så jeg vil hurtigt bevæger sig langs 445 00:20:10,460 --> 00:20:13,900 her-- er hovedsagelig, du har en bred vifte af værdier. 446 00:20:13,900 --> 00:20:17,170 Og derefter finde dig mindste usorteret værdi 447 00:20:17,170 --> 00:20:20,200 og du bytte den værdi med den første usorteret værdi. 448 00:20:20,200 --> 00:20:22,700 Og så skal du bare holde gentage med resten af ​​din liste. 449 00:20:22,700 --> 00:20:25,740 >> Og her er en visuel forklaring på, hvordan det ville fungere. 450 00:20:25,740 --> 00:20:30,460 Så for eksempel, hvis vi skulle starte med et array af fem elementer, indeks 451 00:20:30,460 --> 00:20:35,910 0 til 4, med 3, 5, 2, 6 og 4 værdier placeret i array-- så lige nu, 452 00:20:35,910 --> 00:20:38,530 vi bare kommer til at påtage sig at de er alle usorteret 453 00:20:38,530 --> 00:20:41,130 fordi vi har ikke testet på anden måde. 454 00:20:41,130 --> 00:20:44,130 >> Så hvordan et valg slags ville arbejde er, at det ville først 455 00:20:44,130 --> 00:20:46,800 løber gennem hele af usorteret array. 456 00:20:46,800 --> 00:20:49,120 Det ville udvælge den mindste værdi. 457 00:20:49,120 --> 00:20:51,750 I dette tilfælde, 3, højre nu, er den mindste. 458 00:20:51,750 --> 00:20:52,680 Det bliver til 5. 459 00:20:52,680 --> 00:20:55,620 Nope, 5 er ikke større than-- eller ked af det, ikke er mindre than-- 3. 460 00:20:55,620 --> 00:20:57,779 Så den mindste værdi er stadig 3. 461 00:20:57,779 --> 00:20:58,695 Og så får du til 2. 462 00:20:58,695 --> 00:21:00,990 Computeren ser, åh, 2 er mindre end 3. 463 00:21:00,990 --> 00:21:02,750 2 må nu være den mindste værdi. 464 00:21:02,750 --> 00:21:06,630 Og så 2 swaps med det første værdi. 465 00:21:06,630 --> 00:21:10,702 >> Så efter en aflevering, kan vi faktisk se at de 2 og 3 er byttet. 466 00:21:10,702 --> 00:21:13,910 Og vi bare kommer til at fortsætte med at gøre dette igen med resten af ​​arrayet. 467 00:21:13,910 --> 00:21:17,660 Så vi kommer til at bare køre igennem de sidste fire indekser af matrixen. 468 00:21:17,660 --> 00:21:20,670 Vi vil se, at 3 er næste minimumsværdi. 469 00:21:20,670 --> 00:21:23,240 Så vi kommer til at bytte det med 4. 470 00:21:23,240 --> 00:21:26,900 Og så er vi bare kommer til at holde løber gennem indtil i sidste ende, du 471 00:21:26,900 --> 00:21:33,730 komme til en sorterede matrix, hvor 2, 3, 4, 5 og 6 er alle sorter. 472 00:21:33,730 --> 00:21:37,530 Har alle forstå logikken af, hvordan et valg slags virker? 473 00:21:37,530 --> 00:21:39,669 >> Du skal bare have en vis form af en mindsteværdi. 474 00:21:39,669 --> 00:21:41,210 Du holder styr på, hvad det er. 475 00:21:41,210 --> 00:21:45,170 Og når du finder det, du bytte det med den første værdi i array-- 476 00:21:45,170 --> 00:21:48,740 eller, ikke den første value-- den næste værdi i arrayet. 477 00:21:48,740 --> 00:21:50,150 Cool. 478 00:21:50,150 --> 00:21:55,460 >> Så som du fyre slags så fra en kort glimt, 479 00:21:55,460 --> 00:21:58,450 vi kommer til at pseudokode det ud. 480 00:21:58,450 --> 00:22:02,510 Så hvis du fyre i ryggen vil danne en gruppe, alle på et bord 481 00:22:02,510 --> 00:22:06,170 kan danne en lille partner, vil jeg at give dig fyre som tre minutter 482 00:22:06,170 --> 00:22:08,190 at bare tale gennem logikken, på engelsk, 483 00:22:08,190 --> 00:22:14,161 af, hvordan vi kan være i stand til at implementere pseudokode til at skrive et valg slags. 484 00:22:14,161 --> 00:22:14,910 Og der er slik. 485 00:22:14,910 --> 00:22:16,118 Kom op og få slik. 486 00:22:16,118 --> 00:22:19,520 Hvis du er i ryggen, og du ønsker slik, kan jeg kaster slik på dig. 487 00:22:19,520 --> 00:22:22,850 Faktisk gør du-- cool. 488 00:22:22,850 --> 00:22:23,552 Åh undskyld. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 OK. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Så hvis vi gerne vil, som en klasse, skrive pseudokode 493 00:25:27,140 --> 00:25:30,466 for, hvordan man kunne nærme sig dette problem, bare du velkommen. 494 00:25:30,466 --> 00:25:32,340 Jeg vil bare gå rundt og, i orden, spørg grupper 495 00:25:32,340 --> 00:25:35,065 for den næste linje med hvad vi skal gøre. 496 00:25:35,065 --> 00:25:37,840 Så hvis du fyre ønsker at starte off, hvad er den første ting 497 00:25:37,840 --> 00:25:40,600 at gøre, når du forsøger at gennemføre en måde at løse dette program 498 00:25:40,600 --> 00:25:43,480 til selektivt at sortere en liste? 499 00:25:43,480 --> 00:25:46,349 Lad os bare antage, vi har et array, okay? 500 00:25:46,349 --> 00:25:49,088 >> PUBLIKUM: Du ønsker at skabe nogle slags [uhørligt], at du er 501 00:25:49,088 --> 00:25:50,420 løber gennem hele din array. 502 00:25:50,420 --> 00:25:51,128 >> ANDI Peng: Right. 503 00:25:51,128 --> 00:25:54,100 Så du vil ønsker at gentage gennem hver plads, ikke? 504 00:25:54,100 --> 00:26:05,490 Så stor. 505 00:26:05,490 --> 00:26:08,600 Hvis du fyre ønsker at give mig næste line-- yeah, i ryggen. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> PUBLIKUM: Tjek dem alle for de mindste. 508 00:26:13,290 --> 00:26:14,248 >> ANDI Peng: Der går vi. 509 00:26:14,248 --> 00:26:17,438 Så vi ønsker at gå igennem og kontrollere, se, hvad den mindste værdi, ikke? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Jeg har tænkt mig at forkorte det til "min." 512 00:26:24,840 --> 00:26:27,658 Hvad tror du fyre ønsker at gøre efter du har fundet den mindste værdi? 513 00:26:27,658 --> 00:26:28,533 >> PUBLIKUM: [uhørligt] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI Peng: Så du vil ønsker at skifte det med det første af denne array, 516 00:26:33,150 --> 00:26:33,650 højre? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 Det er begyndelsen, jeg har tænkt mig at sige. 519 00:26:46,850 --> 00:26:47,220 Okay. 520 00:26:47,220 --> 00:26:50,386 Så nu, at du har byttet den første en, hvad vil du gøre efter det? 521 00:26:50,386 --> 00:26:54,840 Så nu ved vi, at denne ene her skal være den mindste værdi, ikke? 522 00:26:54,840 --> 00:26:58,310 Så har du en ekstra hvile af arrayet, der er usorteret. 523 00:26:58,310 --> 00:27:01,569 Så hvad du ønsker at gøre her, hvis du fyre ønsker at give mig den næste linie? 524 00:27:01,569 --> 00:27:04,610 PUBLIKUM: Så du ønsker at gentage gennem resten af ​​arrayet. 525 00:27:04,610 --> 00:27:05,276 ANDI Peng: Ja. 526 00:27:05,276 --> 00:27:09,857 Og så hvad betyder iteration gennem slags antyde, vi skal nok bruge? 527 00:27:09,857 --> 00:27:10,440 Hvilken type of-- 528 00:27:10,440 --> 00:27:12,057 >> PUBLIKUM: Åh, en ekstra variabel? 529 00:27:12,057 --> 00:27:13,890 ANDI Peng: Sandsynligvis anden for-løkke, ikke? 530 00:27:13,890 --> 00:27:28,914 Så vi sandsynligvis vil ønsker at gentage through-- stor. 531 00:27:28,914 --> 00:27:31,830 Og så er du kommer til at gå tilbage og sandsynligvis kontrollere mindst en gang, 532 00:27:31,830 --> 00:27:32,100 højre? 533 00:27:32,100 --> 00:27:34,975 Og du kommer til at holde gentage dette, fordi løkkerne bare 534 00:27:34,975 --> 00:27:36,010 at holde kørende, ikke? 535 00:27:36,010 --> 00:27:39,190 >> Så som du fyre kan se, vi bare har en generel pseudokode 536 00:27:39,190 --> 00:27:41,480 af, hvordan vi ønsker, at dette program til at se ud. 537 00:27:41,480 --> 00:27:46,646 Denne ITERATE- her, hvad gør vi typisk brug for at skrive i vores kode 538 00:27:46,646 --> 00:27:49,270 hvis vi ønsker at gentage gennem en array, hvilken type struktur? 539 00:27:49,270 --> 00:27:51,030 Jeg tror Christabel allerede sagt det før. 540 00:27:51,030 --> 00:27:51,500 >> PUBLIKUM: en for-løkke. 541 00:27:51,500 --> 00:27:52,160 >> ANDI Peng: en for-løkke? 542 00:27:52,160 --> 00:27:52,770 Præcis. 543 00:27:52,770 --> 00:27:56,060 Så det er nok vil være en for-løkke. 544 00:27:56,060 --> 00:27:59,240 Hvad er en check her kommer til at betyde? 545 00:27:59,240 --> 00:28:02,536 Typisk hvis du ønsker at kontrollere hvis noget er noget else-- 546 00:28:02,536 --> 00:28:03,270 >> PUBLIKUM: Hvis. 547 00:28:03,270 --> 00:28:06,790 >> ANDI Peng: An hvis, ikke? 548 00:28:06,790 --> 00:28:10,790 Og så swap her, vi får gå over senere, fordi David 549 00:28:10,790 --> 00:28:12,770 gik gennem det i forelæsning så godt. 550 00:28:12,770 --> 00:28:14,580 Og så den anden ITERATE- implies-- 551 00:28:14,580 --> 00:28:15,120 >> PUBLIKUM: Endnu for-løkke. 552 00:28:15,120 --> 00:28:16,745 >> ANDI Peng: --another for-løkke, nøjagtigt. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Så hvis vi ser på dette korrekt, vi 555 00:28:22,000 --> 00:28:24,680 kan se, at vi er nok vil få brug for en indlejret for løkke 556 00:28:24,680 --> 00:28:28,330 med en betinget erklæring derinde og derefter en faktiske stykke kode, der er 557 00:28:28,330 --> 00:28:31,360 kommer til at bytte de værdier. 558 00:28:31,360 --> 00:28:35,980 Så jeg har bare generelt skrevet en pseudokode kode. 559 00:28:35,980 --> 00:28:38,910 Og så er vi faktisk går fysisk, som en klasse, 560 00:28:38,910 --> 00:28:40,700 forsøge at gennemføre denne dag. 561 00:28:40,700 --> 00:28:42,486 Lad os gå tilbage til denne IDE. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> Uh-oh. 564 00:28:50,230 --> 00:28:51,754 Hvorfor er det not-- der er det. 565 00:28:51,754 --> 00:28:52,253 OK. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Beklager, lad mig prøve at zoome ind lidt mere. 568 00:28:57,500 --> 00:28:59,310 Der vi går. 569 00:28:59,310 --> 00:29:05,060 Alt jeg gør her, er jeg har oprettet et program kaldet "udvælgelse / sort.c." 570 00:29:05,060 --> 00:29:10,860 Jeg har oprettet en vifte af ni værdier, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 I øjeblikket, som du kan se, de er uordnet. 572 00:29:14,370 --> 00:29:17,880 n vil være det nummer, fortæller dig mængden af ​​værdier 573 00:29:17,880 --> 00:29:18,920 du har i dit array. 574 00:29:18,920 --> 00:29:20,670 I dette tilfælde har vi ni værdier. 575 00:29:20,670 --> 00:29:23,760 Og jeg har lige fået en for-løkke her der udskriver det usorterede array. 576 00:29:23,760 --> 00:29:28,370 >> Og i slutningen, har jeg også fået en for løkke, der bare udskriver det ud igen. 577 00:29:28,370 --> 00:29:32,070 Så teoretisk, hvis dette program fungerer korrekt, i slutningen, 578 00:29:32,070 --> 00:29:35,670 bør du se en trykt for løkke hvor 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 er alle korrekt i orden. 580 00:29:39,310 --> 00:29:43,410 >> Så vi har fået vores pseudokode her. 581 00:29:43,410 --> 00:29:46,090 Er der nogen der ønsker at-- jeg er bare kommer til at gå bede om volunteers-- 582 00:29:46,090 --> 00:29:49,540 fortælle mig præcis, hvad de skal skrive om vi ønsker at det første, bare gentage 583 00:29:49,540 --> 00:29:52,840 gennem begyndelsen af ​​dette array? 584 00:29:52,840 --> 00:29:55,204 Hvad er linje kode jeg sandsynligvis vil få brug for her? 585 00:29:55,204 --> 00:29:56,990 >> PUBLIKUM: [uhørligt] 586 00:29:56,990 --> 00:29:59,010 >> ANDI Peng: Ja, føler gratis at-- ked af det, du 587 00:29:59,010 --> 00:30:02,318 behøver ikke at stå up-- føler fri til at hæve stemmen lidt. 588 00:30:02,318 --> 00:30:08,190 >> PUBLIKUM: Til int i lig 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI Peng: Ja, godt. 590 00:30:10,690 --> 00:30:15,220 >> PUBLIKUM: Jeg er mindre end vifte længde. 591 00:30:15,220 --> 00:30:19,630 >> ANDI Peng: Så hold i tankerne her, fordi vi 592 00:30:19,630 --> 00:30:23,060 ikke har en funktion, fortæller os længden af ​​en matrix, 593 00:30:23,060 --> 00:30:25,790 Vi har allerede en værdi, der lagrer det. 594 00:30:25,790 --> 00:30:27,920 Højre? 595 00:30:27,920 --> 00:30:31,010 En anden ting at huske i mind-- i et array 596 00:30:31,010 --> 00:30:33,940 ni værdier, hvad er indekser? 597 00:30:33,940 --> 00:30:38,720 Lad os bare sige dette array var 0 til 3. 598 00:30:38,720 --> 00:30:41,500 Du ser, at den sidste indeks er faktisk 3. 599 00:30:41,500 --> 00:30:45,530 Det er ikke 4, selvom der er fire værdier i arrayet. 600 00:30:45,530 --> 00:30:49,866 >> Så her er vi nødt til at være meget forsigtige af, hvad vores betingelse for længden 601 00:30:49,866 --> 00:30:50,490 kommer til at være. 602 00:30:50,490 --> 00:30:51,948 >> PUBLIKUM: Ville det ikke være n minus 1? 603 00:30:51,948 --> 00:30:54,440 ANDI Peng: Det kommer n minus 1, nøjagtigt. 604 00:30:54,440 --> 00:30:57,379 Giver det mening, hvorfor det er n minus 1, alle? 605 00:30:57,379 --> 00:30:58,920 Det er fordi arrays er nul-indekseret. 606 00:30:58,920 --> 00:31:02,010 De starter ved 0 og køre op til n minus 1. 607 00:31:02,010 --> 00:31:03,210 Ja, det er lidt tricky. 608 00:31:03,210 --> 00:31:03,730 OK. 609 00:31:03,730 --> 00:31:05,929 Og så-- 610 00:31:05,929 --> 00:31:08,054 PUBLIKUM: Isnt'1 at allerede taget sig af selv, 611 00:31:08,054 --> 00:31:11,400 ved bare ikke at sige "mindre end eller lig med "og bare sige" mindre end? " 612 00:31:11,400 --> 00:31:13,108 >> ANDI Peng: Det er en rigtig godt spørgsmål. 613 00:31:13,108 --> 00:31:13,630 Så, ja. 614 00:31:13,630 --> 00:31:17,410 Men også, den måde, at vi er gennemførelsen af ​​retten kontrol, 615 00:31:17,410 --> 00:31:19,120 du nødt til at sammenligne to værdier. 616 00:31:19,120 --> 00:31:21,009 Så du rent faktisk ønsker at forlade "til" tom. 617 00:31:21,009 --> 00:31:23,050 Fordi hvis du sammenligner denne ene, du ikke vil 618 00:31:23,050 --> 00:31:25,530 har noget, efter at den at sammenligne med, ikke? 619 00:31:25,530 --> 00:31:27,460 Ja. 620 00:31:27,460 --> 00:31:29,297 Så jeg ++. 621 00:31:29,297 --> 00:31:30,380 Lad os tilføje vores beslag på. 622 00:31:30,380 --> 00:31:30,880 Hovsa. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Great. 625 00:31:34,710 --> 00:31:39,117 Så vi har begyndelsen vores ydre loop. 626 00:31:39,117 --> 00:31:41,450 Så nu er vi sikkert gerne oprette en variabel til at holde 627 00:31:41,450 --> 00:31:43,085 styr på den mindste værdi, ikke? 628 00:31:43,085 --> 00:31:45,751 Er der nogen ønsker at give mig linje kode, der ville gøre det? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Hvad har vi brug for, hvis vi skal at ønsker at gemme noget? 631 00:31:53,570 --> 00:31:55,047 >> Højre. 632 00:31:55,047 --> 00:31:57,630 Måske et bedre navn for det ville være-- "temp" helt works-- 633 00:31:57,630 --> 00:32:00,655 måske en mere passende navn ville være, hvis vi ønsker den mindste value-- 634 00:32:00,655 --> 00:32:01,624 >> PUBLIKUM: Min. 635 00:32:01,624 --> 00:32:02,790 ANDI Peng: min, der vi gå. 636 00:32:02,790 --> 00:32:05,230 min ville være godt. 637 00:32:05,230 --> 00:32:08,340 Og så her, hvad gør vi vil initialisere det til? 638 00:32:08,340 --> 00:32:09,620 Dette er en smule tricky. 639 00:32:09,620 --> 00:32:13,580 Fordi lige nu på begyndelsen af ​​dette array, 640 00:32:13,580 --> 00:32:15,730 du ikke har kigget på noget, ikke? 641 00:32:15,730 --> 00:32:19,200 Så hvad, automatisk, hvis vi er bare på jeg er lig med 0, 642 00:32:19,200 --> 00:32:22,302 hvad ønsker vi at initialisere vores første minimumsværdi til? 643 00:32:22,302 --> 00:32:22,802 PUBLIKUM: i. 644 00:32:22,802 --> 00:32:24,790 ANDI Peng: i, nøjagtigt. 645 00:32:24,790 --> 00:32:27,040 Christabel, hvorfor vi ønsker at initialisere den til jeg? 646 00:32:27,040 --> 00:32:28,510 >> PUBLIKUM: Fordi, ja, vi starter med 0. 647 00:32:28,510 --> 00:32:31,660 Så fordi vi har noget at sammenligne det vil minimum ende med at blive 0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI Peng: Præcis. 649 00:32:32,451 --> 00:32:34,400 Så hun er helt rigtigt. 650 00:32:34,400 --> 00:32:36,780 Fordi vi har faktisk ikke så på noget endnu, 651 00:32:36,780 --> 00:32:38,680 Vi ved ikke, hvad vores minimum værdi. 652 00:32:38,680 --> 00:32:41,960 Vi ønsker at bare initialisere den til I, som for tiden er lige her. 653 00:32:41,960 --> 00:32:44,750 Og som vi fortsætter med at flytte ned dette array, 654 00:32:44,750 --> 00:32:48,122 vi vil se, at med hver ekstra aflevering, jeg intervaller. 655 00:32:48,122 --> 00:32:49,830 Og så på det tidspunkt, Jeg er sandsynligvis vil 656 00:32:49,830 --> 00:32:52,329 at ville være det mindste, fordi det vil være, hvad 657 00:32:52,329 --> 00:32:54,520 er begyndelsen af ​​usorteret array. 658 00:32:54,520 --> 00:32:55,270 Cool. 659 00:32:55,270 --> 00:32:58,720 >> Så nu er vi ønsker at tilføje en for-løkke her, der er 660 00:32:58,720 --> 00:33:03,225 kommer til at gentage gennem usorteret, eller resten af ​​dette array. 661 00:33:03,225 --> 00:33:05,808 Er der nogen ønsker at give mig en linje kode, der ville gøre det? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- hvad skal vi hernede? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 Hvad kommer til at gå i denne for-løkke? 666 00:33:18,820 --> 00:33:19,465 Ja. 667 00:33:19,465 --> 00:33:21,590 PUBLIKUM: Så vi gerne vil har en anden heltal, 668 00:33:21,590 --> 00:33:25,080 fordi vi kører gennem resten af arrayet i stedet for I, så måske 669 00:33:25,080 --> 00:33:25,760 j. 670 00:33:25,760 --> 00:33:27,301 >> ANDI Peng: Ja, j lyder godt for mig. 671 00:33:27,301 --> 00:33:27,850 Lig? 672 00:33:27,850 --> 00:33:33,930 >> PUBLIKUM: Så ville være i plus 1, fordi du starter på den næste værdi. 673 00:33:33,930 --> 00:33:40,395 Og derefter til end-- det igen, j er mindre end n minus 1, og derefter j ++. 674 00:33:40,395 --> 00:33:41,103 ANDI Peng: Great. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> Og derefter i her, vi kommer til at have at kontrollere, om vores betingelse er opfyldt, 677 00:33:52,750 --> 00:33:53,250 højre? 678 00:33:53,250 --> 00:33:55,740 Fordi du ønsker at ændre minimumsværdi 679 00:33:55,740 --> 00:33:58,700 hvis det er faktisk mindre end hvad du sammenligne det med, ikke? 680 00:33:58,700 --> 00:34:01,146 Så hvad skal vi have i her? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Kontroller at se. 683 00:34:04,897 --> 00:34:06,730 Hvilken type erklæring vi sandsynligvis vil 684 00:34:06,730 --> 00:34:08,389 ti ønsker at bruge, hvis vi ønsker at kontrollere noget? 685 00:34:08,389 --> 00:34:09,360 >> PUBLIKUM: en if-sætning. 686 00:34:09,360 --> 00:34:10,485 >> ANDI Peng: en if-sætning. 687 00:34:10,485 --> 00:34:13,155 Så if-- og hvad der vil være den betingelse, at vi ønsker inde 688 00:34:13,155 --> 00:34:13,988 af vores hvis erklæring? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> PUBLIKUM: Hvis værdien af ​​j er mindre end værdien af ​​jeg-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI Peng: Præcis. 692 00:34:24,600 --> 00:34:27,480 Så if-- så dette array kaldes "array." 693 00:34:27,480 --> 00:34:27,980 Great. 694 00:34:27,980 --> 00:34:30,465 Så hvis array-- hvad var det? 695 00:34:30,465 --> 00:34:31,090 Sig det igen. 696 00:34:31,090 --> 00:34:39,590 >> PUBLIKUM: Hvis vifte-j er mindre end matrix-i, så ville vi ændre min. 697 00:34:39,590 --> 00:34:41,590 Så min ville være j. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI Peng: Giver det mening? 700 00:34:47,249 --> 00:34:48,670 OK. 701 00:34:48,670 --> 00:34:52,929 Og nu hernede, vi faktisk ønsker at gennemføre swap, ikke? 702 00:34:52,929 --> 00:34:58,285 Så husker, i foredrag, at David, når han prøvede at bytte til--, hvad der var 703 00:34:58,285 --> 00:34:59,996 det-- appelsinsaft og milk-- 704 00:34:59,996 --> 00:35:01,150 >> PUBLIKUM: Det var brutto. 705 00:35:01,150 --> 00:35:02,816 >> ANDI Peng: Ja, det var slags brutto. 706 00:35:02,816 --> 00:35:05,310 Men det var en temmelig god koncept demonstrerer tid. 707 00:35:05,310 --> 00:35:08,430 Så tænk på dine værdier her. 708 00:35:08,430 --> 00:35:10,794 Du har fået en matrix på min, en opstilling af i, 709 00:35:10,794 --> 00:35:12,460 eller hvad vi forsøgte at bytte her. 710 00:35:12,460 --> 00:35:15,310 Og du sandsynligvis ikke kan hælde dem ind hinanden på samme tid, ikke? 711 00:35:15,310 --> 00:35:17,180 Så hvad skal vi at brug for at skabe her 712 00:35:17,180 --> 00:35:19,126 for at bytte de værdier korrekt? 713 00:35:19,126 --> 00:35:19,820 >> PUBLIKUM: En midlertidig variabel. 714 00:35:19,820 --> 00:35:21,370 >> ANDI Peng: En midlertidig variabel. 715 00:35:21,370 --> 00:35:22,570 Så lad os gøre int temp. 716 00:35:22,570 --> 00:35:25,681 Se, det ville være et bedre tid at-- whoa, hvad var det? 717 00:35:25,681 --> 00:35:26,180 OK. 718 00:35:26,180 --> 00:35:29,800 Så det ville have været en bedre tid til at navngive variablen "temp". 719 00:35:29,800 --> 00:35:30,730 Så lad os gøre int temp. 720 00:35:30,730 --> 00:35:32,563 Hvad skal vi indstillet temp lig med her? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 PUBLIKUM: Min? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI Peng: Det er lidt tricky. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 Det faktisk betyder ikke noget i sidste ende. 727 00:35:44,880 --> 00:35:47,690 Det er ligegyldigt, hvad rækkefølge, du vælger at bytte i 728 00:35:47,690 --> 00:35:50,862 så længe du gør, at du er holde styr på, hvad du bytte. 729 00:35:50,862 --> 00:35:52,250 >> PUBLIKUM: Det kunne være matrix-i. 730 00:35:52,250 --> 00:35:53,666 >> ANDI Peng: Ja, lad os gøre vifte-i. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 Og hvad er den næste linje kode vi ønsker at have her? 733 00:35:59,305 --> 00:36:00,680 PUBLIKUM: matrix-i lig vifte-j. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI Peng: Og endelig? 736 00:36:08,070 --> 00:36:12,070 PUBLIKUM: matrix-j lig vifte-i. 737 00:36:12,070 --> 00:36:14,525 Publikum: Eller vifte-j ligemænd matrix-temp-- eller temp. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> ANDI Peng: OK. 740 00:36:19,430 --> 00:36:21,510 Så lad os køre dette og se hvis det kommer til at fungere. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Hvor er det der sker? 743 00:36:39,335 --> 00:36:40,210 Åh, det er et problem. 744 00:36:40,210 --> 00:36:44,320 Se, om linje 40, er vi forsøger at bruge matrix-j? 745 00:36:44,320 --> 00:36:47,022 Men hvor kommer j kun eksisterer i? 746 00:36:47,022 --> 00:36:48,402 >> PUBLIKUM: I for-løkken. 747 00:36:48,402 --> 00:36:49,110 ANDI Peng: Right. 748 00:36:49,110 --> 00:36:51,730 Så hvad skal vi gøre? 749 00:36:51,730 --> 00:36:53,170 >> PUBLIKUM: Definer det uden til-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 PUBLIKUM: Ja, jeg tror, ​​du har at bruge en anden if-sætning, ikke? 752 00:37:00,610 --> 00:37:05,230 Så ligesom, hvis minimum-- okay, lad mig tænke. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI peng: Guys, prøv at tage et kig Lad os 755 00:37:09,990 --> 00:37:11,270 se, hvad der er noget, vi kan gøre her? 756 00:37:11,270 --> 00:37:11,811 >> PUBLIKUM: OK. 757 00:37:11,811 --> 00:37:15,900 Så hvis den mindste ikke er lig j-- så hvis minimum er stadig jeg-- 758 00:37:15,900 --> 00:37:17,570 så ville vi ikke have at bytte. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI Peng: Betyder, at lige jeg? 761 00:37:24,712 --> 00:37:25,920 Hvad vil du sige her? 762 00:37:25,920 --> 00:37:30,494 >> PUBLIKUM: Eller yeah, hvis minimum ikke er lig i, ja. 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 ANDI Peng: OK. 765 00:37:40,210 --> 00:37:42,040 Nå det løser, slags, vores problemer. 766 00:37:42,040 --> 00:37:47,265 Men det stadig ikke løser problemet med, hvad der sker, hvis j-- da j 767 00:37:47,265 --> 00:37:49,890 eksisterer ikke uden for det, hvad vil du ønsker vi at gøre med det? 768 00:37:49,890 --> 00:37:50,698 Erklære den udenfor? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Lad os prøve at køre dette. 771 00:38:02,730 --> 00:38:04,435 Uh-oh. 772 00:38:04,435 --> 00:38:06,200 Vores slags virker ikke. 773 00:38:06,200 --> 00:38:10,060 >> Som du kan se, vores indledende matrix havde disse værdier. 774 00:38:10,060 --> 00:38:14,800 Og bagefter det burde have været i 1, 2, 3, 4, 5, 6, 7, 8, 9. 775 00:38:14,800 --> 00:38:15,530 Det virker ikke. 776 00:38:15,530 --> 00:38:16,030 Ahh. 777 00:38:16,030 --> 00:38:17,184 Hvad gør vi? 778 00:38:17,184 --> 00:38:17,850 PUBLIKUM: Debug. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI Peng: Okay, kan vi prøve det. 781 00:38:23,370 --> 00:38:25,030 Vi kan debug. 782 00:38:25,030 --> 00:38:26,042 Zoom ud lidt. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Lad os sætte vores breakpoint. 785 00:38:33,656 --> 00:38:37,280 Lad os gå like-- OK. 786 00:38:37,280 --> 00:38:40,444 >> Så fordi vi allerede ved, at disse linjer, 15 til 22, 787 00:38:40,444 --> 00:38:43,610 er working-- fordi alle jeg gør er bare iteration gennem og printing-- 788 00:38:43,610 --> 00:38:45,406 Jeg kan gå videre og springe det. 789 00:38:45,406 --> 00:38:47,280 Lad os starte ved linje 25. 790 00:38:47,280 --> 00:38:48,712 Oop, lad mig slippe af med det. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> PUBLIKUM: Så breakpoint s hvor debugging starter? 793 00:38:54,057 --> 00:38:54,890 ANDI Peng: Eller stopper. 794 00:38:54,890 --> 00:38:55,670 PUBLIKUM: Eller stopper. 795 00:38:55,670 --> 00:38:55,930 ANDI Peng: Ja. 796 00:38:55,930 --> 00:38:58,640 Du kan indstille flere breakpoints og det kan lige springe fra den ene til den anden. 797 00:38:58,640 --> 00:39:01,590 Men i dette tilfælde ved vi ikke hvor fejlen sker. 798 00:39:01,590 --> 00:39:03,780 Så vi ønsker blot at starte fra toppen og ned. 799 00:39:03,780 --> 00:39:05,020 Yep. 800 00:39:05,020 --> 00:39:05,550 OK. 801 00:39:05,550 --> 00:39:08,460 >> Så denne linje her, kan vi træde til. 802 00:39:08,460 --> 00:39:11,499 Du kan se hernede, vi har et array. 803 00:39:11,499 --> 00:39:13,290 Det er de værdier som er i array'et. 804 00:39:13,290 --> 00:39:16,360 Kan du se, at, hvordan indeks 0, det svarer til value-- oh, 805 00:39:16,360 --> 00:39:17,526 Jeg har tænkt mig at forsøge at zoome ind. 806 00:39:17,526 --> 00:39:20,650 Beklager, det er virkelig svært at see-- på matrix-indeks 0, 807 00:39:20,650 --> 00:39:24,090 Vi har en værdi på 4, og derefter så videre og så videre. 808 00:39:24,090 --> 00:39:25,670 Vi har vores lokale variabler. 809 00:39:25,670 --> 00:39:28,570 Lige nu i er lig med 0, som vi ønsker det skal være. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> Og så lad os holde træde igennem. 812 00:39:33,690 --> 00:39:36,850 Vores minimum er lig med 0, som vi også ønsker det skal være. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 Og så skal vi ind vores anden for loop, hvis matrix-j er mindre end matrix-I, 815 00:39:45,560 --> 00:39:46,380 som var det ikke. 816 00:39:46,380 --> 00:39:48,130 Så kunne du se, hvordan der springes over det? 817 00:39:48,130 --> 00:39:52,430 >> PUBLIKUM: Så skulle det hvis minimum alle at-- bør ikke, at 818 00:39:52,430 --> 00:39:55,424 være inde den første til loop? 819 00:39:55,424 --> 00:39:57,340 ANDI Peng: Nej, fordi du stadig ønsker at teste. 820 00:39:57,340 --> 00:40:00,329 Du ønsker at gøre en sammenligning hver tid, selv efter du har kørt igennem den. 821 00:40:00,329 --> 00:40:02,620 Du behøver ikke bare ønsker at gøre det den første gennemslag. 822 00:40:02,620 --> 00:40:05,240 Du ønsker at gøre det med hver ekstra pass igen. 823 00:40:05,240 --> 00:40:07,198 Så du ønsker at kontrollere for din tilstand indeni. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Så vi bare gå til holde kører igennem her. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Jeg vil give jer et tip. 828 00:40:18,420 --> 00:40:23,910 Det har at gøre med det faktum, at når du tjekker din betingede, 829 00:40:23,910 --> 00:40:26,600 du ikke kontrol for den korrekte indeks. 830 00:40:26,600 --> 00:40:32,510 Så lige nu er du kontrollere for vifte indeks j er mindre end matrix 831 00:40:32,510 --> 00:40:33,970 indeks i. 832 00:40:33,970 --> 00:40:36,580 Men hvad laver du op på begyndelsen af ​​for-løkken? 833 00:40:36,580 --> 00:40:38,260 Er du ikke sætte j lig med jeg? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Ja, så kan vi faktisk forlade debugger her. 836 00:40:45,415 --> 00:40:47,040 Så lad os tage et kig på vores pseudokode. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- vi vil starter ved i er lig med 0. 839 00:40:52,580 --> 00:40:54,760 Vi kommer til at gå op til n minus 1. 840 00:40:54,760 --> 00:40:58,040 Lad os tjekke, vi har denne ret? 841 00:40:58,040 --> 00:40:59,580 Jep, det var rigtigt. 842 00:40:59,580 --> 00:41:02,080 >> Så inde her, vi er vil skabe en minimumsværdi 843 00:41:02,080 --> 00:41:03,630 og sæt, lig med i. 844 00:41:03,630 --> 00:41:04,950 Gjorde vi det? 845 00:41:04,950 --> 00:41:06,270 Jep, gjorde det. 846 00:41:06,270 --> 00:41:10,430 Nu i vores indre for-løkke, er vi vil gøre j lig I n 1 minus. 847 00:41:10,430 --> 00:41:11,950 Gjorde vi det? 848 00:41:11,950 --> 00:41:15,540 Faktisk gjorde vi det. 849 00:41:15,540 --> 00:41:19,922 >> Så dog hvad skal vi sammenligner her? 850 00:41:19,922 --> 00:41:20,925 >> PUBLIKUM: j plus 1. 851 00:41:20,925 --> 00:41:21,716 ANDI Peng: Præcis. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 Og så er du vil ønsker at indstille din minimum svarende til j plus 1 så godt. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Så jeg gik igennem, der virkelig hurtigt. 856 00:41:32,640 --> 00:41:36,190 Har du fyre forstår hvorfor det er j plus 1? 857 00:41:36,190 --> 00:41:36,890 OK. 858 00:41:36,890 --> 00:41:40,700 >> Så i dit array, i dit første passage gennem, 859 00:41:40,700 --> 00:41:44,850 din for-løkke, til int Jeg er lig 0, lad os bare 860 00:41:44,850 --> 00:41:46,740 påtage sig dette er ikke blevet ændret endnu. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 Vi har en bred vifte af helt, blot fire usorterede elementer, ikke? 863 00:41:56,760 --> 00:42:00,760 Så vi vil initialisere jeg lig med 0. 864 00:42:00,760 --> 00:42:03,650 Og jeg vil bare løbe gennem denne løkke. 865 00:42:03,650 --> 00:42:08,560 Og så i den første aflevering, vil vi at initialisere en variabel kaldet "min" 866 00:42:08,560 --> 00:42:11,245 der også er lig med I, fordi vi ikke har en minimumsværdi. 867 00:42:11,245 --> 00:42:12,870 Så det er i øjeblikket lig med 0 så godt. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 Og så vi vil gå igennem. 870 00:42:17,640 --> 00:42:19,270 Og vi ønsker at gentage igen. 871 00:42:19,270 --> 00:42:22,900 Nu da vi har fundet, hvad vores minimum er, vi ønsker at gentage gennem 872 00:42:22,900 --> 00:42:25,190 igen for at se, om det er at sammenligne, ikke? 873 00:42:25,190 --> 00:42:40,440 Så j, her, vil til lige I, som er 0. 874 00:42:40,440 --> 00:42:46,320 Og derefter, hvis matrix j plus jeg, som er den, der er næste forbi, som mindre 875 00:42:46,320 --> 00:42:49,270 end hvad din nuværende minimum værdi, du ønsker at bytte. 876 00:42:49,270 --> 00:42:56,850 >> Så lad os bare sige, at vi har fik, ligesom, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Lige nu, i er lig med 0 og j er lig 0. 878 00:43:01,610 --> 00:43:05,210 Og det er vores mindste værdi. 879 00:43:05,210 --> 00:43:09,950 Hvis vifte-j plus jeg-- så hvis den ene det er efter det vi kigger på 880 00:43:09,950 --> 00:43:13,450 er større end den, før den, det kommer til at blive et minimum. 881 00:43:13,450 --> 00:43:18,120 >> Så her ser vi, at 5 ikke er mindre end det. 882 00:43:18,120 --> 00:43:19,730 Så det kommer til at være 5. 883 00:43:19,730 --> 00:43:23,580 Vi ser, at 1 er mindre end 2, ikke? 884 00:43:23,580 --> 00:43:32,970 Så nu ved vi, at vores minimum er vil være den indeksværdien ved 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Ja? 886 00:43:34,030 --> 00:43:39,170 Og så når du kommer herned, du kan bytte de korrekte værdier. 887 00:43:39,170 --> 00:43:42,610 >> Så når du fyre bare have den j før, var du ikke ser på den ene 888 00:43:42,610 --> 00:43:43,260 efter det. 889 00:43:43,260 --> 00:43:44,520 Du ledte på den samme værdi, som 890 00:43:44,520 --> 00:43:46,290 Derfor er det bare ikke gør noget. 891 00:43:46,290 --> 00:43:49,721 Giver det mening for alle, hvorfor vi havde brug for, at plus 1 er der? 892 00:43:49,721 --> 00:43:50,220 OK. 893 00:43:50,220 --> 00:43:53,345 Lad os nu bare køre igennem det for at gøre sikker på resten af ​​koden er korrekt. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Hvorfor er det der sker? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ah, det er min lige her. 898 00:44:16,364 --> 00:44:17,780 Vi sammenlignede den forkerte værdi. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 Åh nej. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> Oh yeah, hernede var vi bytte de forkerte værdier. 903 00:44:33,482 --> 00:44:34,940 Fordi vi ser på i og j. 904 00:44:34,940 --> 00:44:36,440 Det er dem, vi kontrol. 905 00:44:36,440 --> 00:44:39,160 Vi faktisk ønsker at bytte den minimum det nuværende minimum, 906 00:44:39,160 --> 00:44:40,550 med hvad den ene udenfor er. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 Og som du fyre kan se ned her har vi en sorterede array. 909 00:45:05,402 --> 00:45:07,110 Det havde bare at gøre med det faktum, at når 910 00:45:07,110 --> 00:45:09,350 vi kontrol af værdier, vi sammenligner, 911 00:45:09,350 --> 00:45:11,226 vi ikke leder på de rigtige værdier. 912 00:45:11,226 --> 00:45:13,850 Vi ledte på den samme her, faktisk ikke bytte det. 913 00:45:13,850 --> 00:45:17,135 Du er nødt til at se på en næste til det, og så kan du bytte. 914 00:45:17,135 --> 00:45:19,260 Så det er det, der var slags aflytning vores kode før. 915 00:45:19,260 --> 00:45:22,460 Og hvad jeg gjorde her er alt debugger kunne have gjort for dig 916 00:45:22,460 --> 00:45:23,810 Jeg gjorde det bare på bord, fordi det er nemmere 917 00:45:23,810 --> 00:45:26,320 at se snarere end at forsøge at zoome ind på debugger. 918 00:45:26,320 --> 00:45:29,391 Giver det mening for alle? 919 00:45:29,391 --> 00:45:29,890 Cool. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Okay. 922 00:45:35,410 --> 00:45:41,070 Vi kan gå videre til at tale om asymptotisk notation, som 923 00:45:41,070 --> 00:45:44,580 er bare en fancy måde at sige det runtime af alle disse former. 924 00:45:44,580 --> 00:45:47,650 Så jeg ved David, i foredrag, berørt runtime. 925 00:45:47,650 --> 00:45:52,124 Og han gik igennem hele formel af hvordan man beregner de runtime. 926 00:45:52,124 --> 00:45:53,040 Ingen bekymringer om der. 927 00:45:53,040 --> 00:45:54,660 Hvis du er virkelig nysgerrig om, hvordan det fungerer, 928 00:45:54,660 --> 00:45:55,810 velkommen til at tale med mig efter sektion. 929 00:45:55,810 --> 00:45:57,560 Vi kan gå igennem formlerne sammen. 930 00:45:57,560 --> 00:46:00,689 Men alle du fyre har virkelig ved er, at n kvadreret over 2 931 00:46:00,689 --> 00:46:01,980 er det samme som n potens. 932 00:46:01,980 --> 00:46:04,710 Fordi det største antal, eksponenten, vokser mest. 933 00:46:04,710 --> 00:46:06,590 Og så til vores formål, alt, hvad vi interesserer os 934 00:46:06,590 --> 00:46:09,470 er, at kæmpe nummer, der vokser. 935 00:46:09,470 --> 00:46:13,340 >> Så hvad er den bedste fald runtime af valg Sorter? 936 00:46:13,340 --> 00:46:15,830 Hvis du vil have at gentage gennem en liste 937 00:46:15,830 --> 00:46:18,712 og derefter gentage gennem resten af ​​denne liste, 938 00:46:18,712 --> 00:46:20,420 hvor mange gange er vil du sandsynligvis, 939 00:46:20,420 --> 00:46:24,612 i værste case-- i bedste fald sorry-- løbe igennem? 940 00:46:24,612 --> 00:46:27,070 Måske bedre spørgsmål er at spørge, hvad er det værste tilfælde 941 00:46:27,070 --> 00:46:28,153 runtime af markering slags. 942 00:46:28,153 --> 00:46:29,366 PUBLIKUM: n potens. 943 00:46:29,366 --> 00:46:30,740 ANDI Peng: Det er n kvadreret, højre. 944 00:46:30,740 --> 00:46:36,986 Så en nem måde at tænke på det er ligesom, helst du har to indlejret efter sløjfer, 945 00:46:36,986 --> 00:46:38,110 det kommer til at blive n potens. 946 00:46:38,110 --> 00:46:40,386 Fordi ikke kun er du løber gennem endnu en gang, 947 00:46:40,386 --> 00:46:42,260 du nødt til at gå tilbage rundt og kørt gennem det 948 00:46:42,260 --> 00:46:44,980 endnu en gang inden for hver værdi. 949 00:46:44,980 --> 00:46:48,640 Så i dette tilfælde, er du kører n gange n kvadreret, hvilket is-- undskyld, 950 00:46:48,640 --> 00:46:50,505 n gange n, hvilket svarer til n potens. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> Og sortere er også lidt unikke i den forstand, 953 00:46:56,360 --> 00:46:59,774 at det ikke betyder noget, hvis disse værdier er allerede i orden. 954 00:46:59,774 --> 00:47:01,440 Det er stadig kommer til at køre igennem anyways. 955 00:47:01,440 --> 00:47:03,872 Lad os bare sige det var 1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Uanset om det var i orden, er det stadig ville have løb gennem 957 00:47:07,080 --> 00:47:08,620 og stadig kontrolleres minimumsværdien. 958 00:47:08,620 --> 00:47:10,100 Det ville have gjort samme antal kontroller 959 00:47:10,100 --> 00:47:12,780 hver eneste gang, selv om det faktisk ikke ved noget. 960 00:47:12,780 --> 00:47:16,940 >> Så i dette tilfælde, det bedste og værste runtime faktisk ækvivalente. 961 00:47:16,940 --> 00:47:19,160 Så den forventede runtime udvælgelse sortere, 962 00:47:19,160 --> 00:47:23,790 som vi betegner med symbolet af theta, theta, i dette tilfælde, 963 00:47:23,790 --> 00:47:24,790 ville også n potens. 964 00:47:24,790 --> 00:47:26,480 Alle tre af disse ville blive n potens. 965 00:47:26,480 --> 00:47:29,653 Er alle klar på, hvorfor runtime er n kvadreret? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Okay. 968 00:47:33,980 --> 00:47:39,120 Så jeg vil blot hurtigt løbe gennem resten af ​​den slags. 969 00:47:39,120 --> 00:47:41,137 Algoritmen for boble sort-- huske, 970 00:47:41,137 --> 00:47:43,220 dette var den første David gik over i forelæsning. 971 00:47:43,220 --> 00:47:46,000 Væsentlige, du trin gennem hele listen 972 00:47:46,000 --> 00:47:48,950 og du swap-- du bare sammenligne to ad gangen. 973 00:47:48,950 --> 00:47:51,350 Og hvis man er større, end du bare bytte dem. 974 00:47:51,350 --> 00:47:53,590 Så hvis disse er større, ville du bytte. 975 00:47:53,590 --> 00:47:56,180 Jeg har fået officiel lige her. 976 00:47:56,180 --> 00:47:59,100 >> Så lad os bare sige, at du havde 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Du vil sammenligne 8 og en 6. 978 00:48:00,571 --> 00:48:01,570 Du behøver at bytte dem. 979 00:48:01,570 --> 00:48:02,610 Du ville sammenligne 8 og en 4. 980 00:48:02,610 --> 00:48:03,609 Du behøver at bytte dem. 981 00:48:03,609 --> 00:48:07,000 Hvis du er nødt til at skifte 8 og 2, ændre dem så godt. 982 00:48:07,000 --> 00:48:10,760 Så i sådan en følelse, kan du se, udspiller sig over en lang periode, 983 00:48:10,760 --> 00:48:13,730 hvordan værdier slags boblen til enderne, hvilket er derfor, vi kalder det 984 00:48:13,730 --> 00:48:15,320 boble slags. 985 00:48:15,320 --> 00:48:19,950 >> Vi vil blot løbe igennem igen på vores anden aflevering, og vores tredje aflevering, 986 00:48:19,950 --> 00:48:21,150 og vores fjerde pass. 987 00:48:21,150 --> 00:48:25,820 Væsentlige, boble sortere bare kører indtil du ikke foretager nogen flere swaps. 988 00:48:25,820 --> 00:48:31,109 Så i den forstand, det er bare den generelle pseudokode for det. 989 00:48:31,109 --> 00:48:32,650 Ingen bekymringer, vil disse alle være online. 990 00:48:32,650 --> 00:48:34,990 Vi har ikke til rent faktisk at gå over dette. 991 00:48:34,990 --> 00:48:38,134 >> Vi har lige initialisere en tæller variabel, der starter ved 0. 992 00:48:38,134 --> 00:48:39,800 Og vi gentage gennem hele systemet. 993 00:48:39,800 --> 00:48:43,420 Og hvis én værdi is-- hvis det værdien er større end denne værdi, 994 00:48:43,420 --> 00:48:44,610 du kommer til at bytte dem. 995 00:48:44,610 --> 00:48:46,860 Og så er du bare kommer til at holde ud. 996 00:48:46,860 --> 00:48:47,970 Og du kommer til at tælle. 997 00:48:47,970 --> 00:48:50,845 Og du bare kommer til at holde gør dette, mens tælleren er større 998 00:48:50,845 --> 00:48:53,345 end 0, hvilket betyder, at hver gang du har til at bytte, 999 00:48:53,345 --> 00:48:55,220 du ved, du ønsker at gå tilbage og tjek igen. 1000 00:48:55,220 --> 00:48:59,510 Du ønsker at holde kontrol, indtil du kender at du ikke behøver at bytte længere. 1001 00:48:59,510 --> 00:49:05,570 >> Så hvad er de bedste og værste tilfælde Runtimes til boble slags? 1002 00:49:05,570 --> 00:49:09,300 Og hint-- det er faktisk anderledes fra valg Sorter i den forstand, 1003 00:49:09,300 --> 00:49:11,810 at disse to svar ikke er de samme. 1004 00:49:11,810 --> 00:49:14,709 Tænk over, hvad der ville ske i en sag, hvis den allerede blev sorteret. 1005 00:49:14,709 --> 00:49:16,500 Og tænke over, hvad ville ske, hvis det var 1006 00:49:16,500 --> 00:49:18,372 i det tilfælde, hvor det ikke blev sorteret. 1007 00:49:18,372 --> 00:49:20,580 Og du kan slags køre gennem hvorfor det sker. 1008 00:49:20,580 --> 00:49:22,954 Jeg vil give jer, ligesom, 30 sekunder til at tænke over det. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> OK. 1011 00:49:53,540 --> 00:49:57,462 Er der nogen der har et gæt på, hvad værste tilfælde runtime af boble slags er? 1012 00:49:57,462 --> 00:49:57,962 Ja. 1013 00:49:57,962 --> 00:50:07,810 >> PUBLIKUM: Ville det være, ligesom, n gange n minus 1 eller sådan noget? 1014 00:50:07,810 --> 00:50:10,650 Ligesom, hver gang det kører, det er bare, ligesom, en swap mindre 1015 00:50:10,650 --> 00:50:10,960 at uanset hvad det var. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI Peng: Ja, så du er helt rigtigt. 1017 00:50:12,668 --> 00:50:15,940 Og det er en sag, hvor din Svaret var faktisk mere kompliceret 1018 00:50:15,940 --> 00:50:17,240 end den, vi nødt til at give. 1019 00:50:17,240 --> 00:50:19,772 Så det kommer til at run-- jeg er kommer til at slette alt det her. 1020 00:50:19,772 --> 00:50:20,480 Er alle godt? 1021 00:50:20,480 --> 00:50:21,869 Kan jeg slette det? 1022 00:50:21,869 --> 00:50:22,368 OK. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Du kommer til at løbe gennem n gange den første gang, ikke? 1025 00:50:30,320 --> 00:50:33,200 Og de kommer til at løbe gennem n minus 1 anden gang, ikke? 1026 00:50:33,200 --> 00:50:37,130 Og så er du kommer til at holde gå, n minen 2, et cetera. 1027 00:50:37,130 --> 00:50:40,210 David gjorde det i et foredrag, hvor, hvis du har tilføjet op alle disse værdier, 1028 00:50:40,210 --> 00:50:48,080 du får noget, der er like-- yeah-- over 2, som i det væsentlige blot reducerer 1029 00:50:48,080 --> 00:50:49,784 ned til n potens. 1030 00:50:49,784 --> 00:50:51,700 Du kommer til at få en underlige fraktion derinde. 1031 00:50:51,700 --> 00:50:53,892 Og så bare vide, at n kvadreret altid 1032 00:50:53,892 --> 00:50:55,350 forrang for fraktionen. 1033 00:50:55,350 --> 00:50:58,450 Og så i dette tilfælde, det værste runtime ville blive n potens. 1034 00:50:58,450 --> 00:51:00,210 Hvis det var i faldende orden, tror, ​​du 1035 00:51:00,210 --> 00:51:02,530 nødt til at gøre en swap hver eneste gang. 1036 00:51:02,530 --> 00:51:05,170 >> Hvad ville være potentielt bedste fald runtime? 1037 00:51:05,170 --> 00:51:08,580 Lad os bare sige, hvis listen var allerede i orden, hvad ville runtime være? 1038 00:51:08,580 --> 00:51:09,565 >> PUBLIKUM: n. 1039 00:51:09,565 --> 00:51:10,690 ANDI Peng: Det er n, nøjagtigt. 1040 00:51:10,690 --> 00:51:11,600 Og hvorfor er det n? 1041 00:51:11,600 --> 00:51:13,850 PUBLIKUM: Fordi du bare nødt til at tjekke på hver gang. 1042 00:51:13,850 --> 00:51:14,770 ANDI Peng: Præcis. 1043 00:51:14,770 --> 00:51:17,150 Så på den bedst mulige runtime, Hvis denne liste allerede var 1044 00:51:17,150 --> 00:51:20,270 sorted-- lad os sige 1, 2, 3, 4-- du ville bare gå igennem, vil du tjekke, 1045 00:51:20,270 --> 00:51:21,720 du ville se, åh, de alle panorere. 1046 00:51:21,720 --> 00:51:22,636 Jeg behøvede ikke at bytte. 1047 00:51:22,636 --> 00:51:23,370 Jeg er færdig. 1048 00:51:23,370 --> 00:51:26,500 Så i dette tilfælde, det er bare n eller antallet af trin, du bare 1049 00:51:26,500 --> 00:51:29,870 havde til at kontrollere den første liste. 1050 00:51:29,870 --> 00:51:33,990 >> Og efter vi nu ramt indsættelse sortere, hvor 1051 00:51:33,990 --> 00:51:39,260 algoritmen er væsentlige kløft den i en sorteret og usorteret del. 1052 00:51:39,260 --> 00:51:42,810 Og derefter en efter en, de usorterede værdier er 1053 00:51:42,810 --> 00:51:46,880 indsat i deres passende positioner i begyndelsen af ​​listen. 1054 00:51:46,880 --> 00:51:52,120 >> Så for eksempel, har vi en Liste over 3, 5, 2, 6, 4 igen. 1055 00:51:52,120 --> 00:51:54,750 Vi ved, at det er i øjeblikket usorteret fordi vi har bare 1056 00:51:54,750 --> 00:51:57,030 begyndte at se på det. 1057 00:51:57,030 --> 00:52:00,610 Vi tager et kig og vi ved, at den første værdi sorteres, ikke? 1058 00:52:00,610 --> 00:52:04,190 Hvis du kun kigger på en vifte af størrelse en, du ved, at det er ordnet. 1059 00:52:04,190 --> 00:52:08,230 >> Så vi ved, at andre fire er usorteret. 1060 00:52:08,230 --> 00:52:10,980 Vi går igennem, og vi kan se, at værdi. 1061 00:52:10,980 --> 00:52:11,730 Lad os gå tilbage. 1062 00:52:11,730 --> 00:52:13,130 Se, at værdi af 5? 1063 00:52:13,130 --> 00:52:14,110 Vi tager et kig på det. 1064 00:52:14,110 --> 00:52:15,204 Vi sammenligner det til 3. 1065 00:52:15,204 --> 00:52:17,870 Vi ved, at det er større end 3, så vi ved, at der er sorteret. 1066 00:52:17,870 --> 00:52:22,940 Så vi ved nu, at de to første sorteres og de sidste tre er ikke. 1067 00:52:22,940 --> 00:52:24,270 >> Vi tager et kig på 2. 1068 00:52:24,270 --> 00:52:25,720 Vi først tjekke det med 5. 1069 00:52:25,720 --> 00:52:26,700 Er det mindre end 5? 1070 00:52:26,700 --> 00:52:27,240 Det er ikke. 1071 00:52:27,240 --> 00:52:29,510 Så vi er nødt til at holde kigger ned. 1072 00:52:29,510 --> 00:52:30,940 Så du tjekke 2 off 3. 1073 00:52:30,940 --> 00:52:31,850 Er det mindre end? 1074 00:52:31,850 --> 00:52:32,350 Nej. 1075 00:52:32,350 --> 00:52:35,430 Så du ved en 2 skal indsættes i den forreste og 3 og 5 1076 00:52:35,430 --> 00:52:38,200 begge at blive skubbet ud. 1077 00:52:38,200 --> 00:52:42,190 Gør dette igen med 6 og 4. 1078 00:52:42,190 --> 00:52:48,962 Og vi bare holde kontrol væsentlige, hvor vi lige tjekke, check, check. 1079 00:52:48,962 --> 00:52:51,170 Og indtil det er i den rigtige position, vi slags blot 1080 00:52:51,170 --> 00:52:54,890 indsætte det i den rigtige position, som er, hvor navnet på det kom fra. 1081 00:52:54,890 --> 00:52:59,830 >> Så det er bare den algoritme, pseudokode per se, slags, 1082 00:52:59,830 --> 00:53:04,990 om, hvordan vi ville gennemføre en insertion slags. 1083 00:53:04,990 --> 00:53:05,954 Pseudokode er her. 1084 00:53:05,954 --> 00:53:06,620 Det er alt sammen online. 1085 00:53:06,620 --> 00:53:10,720 Ingen bekymringer, hvis du fyre er forsøger at kopiere det ned. 1086 00:53:10,720 --> 00:53:14,500 Så endnu en gang, samme question-- hvad ville være den bedste og værste runtime 1087 00:53:14,500 --> 00:53:16,120 til indføring slags? 1088 00:53:16,120 --> 00:53:17,750 Det er meget lig det sidste spørgsmål. 1089 00:53:17,750 --> 00:53:20,479 Jeg vil give jer, ligesom, 30 sekunder til at tænke over det så godt. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> OK Er der nogen ønsker at give mig den værste runtime? 1092 00:53:50,071 --> 00:53:50,570 Ja. 1093 00:53:50,570 --> 00:53:51,490 >> PUBLIKUM: n potens. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI Peng: Det er n potens. 1095 00:53:52,573 --> 00:53:53,730 Og hvorfor er det n kvadreret? 1096 00:53:53,730 --> 00:53:57,562 >> PUBLIKUM: Fordi i omvendt rækkefølge, du har 1097 00:53:57,562 --> 00:54:02,619 at gå gennem n gange n, som is-- 1098 00:54:02,619 --> 00:54:03,660 ANDI Peng: Ja, præcis. 1099 00:54:03,660 --> 00:54:06,610 Så samme som i boblen slags. 1100 00:54:06,610 --> 00:54:08,720 Hvis denne liste er i faldende rækkefølge, du er 1101 00:54:08,720 --> 00:54:11,240 nødt til at tjekke først én gang. 1102 00:54:11,240 --> 00:54:13,470 Og derefter med hver ekstra værdi, du er 1103 00:54:13,470 --> 00:54:16,390 nødt til at tjekke det mod hver enkelt værdi, ikke? 1104 00:54:16,390 --> 00:54:20,290 Og så helt, er du nødt til at gøre en n pass gange en anden n passere, som 1105 00:54:20,290 --> 00:54:21,750 er n potens. 1106 00:54:21,750 --> 00:54:22,860 Hvad med den bedste sag? 1107 00:54:22,860 --> 00:54:24,360 Ja. 1108 00:54:24,360 --> 00:54:28,840 >> PUBLIKUM: n minus 1, fordi første er allerede potens. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI Peng: Så tæt på. 1110 00:54:30,270 --> 00:54:31,850 Svaret er faktisk n. 1111 00:54:31,850 --> 00:54:37,189 Fordi mens den første er sorteret, kan det ikke actually-- det 1112 00:54:37,189 --> 00:54:38,980 vi bare lucked, i dette eksempel, at 2 1113 00:54:38,980 --> 00:54:40,930 tilfældigvis det mindste tal. 1114 00:54:40,930 --> 00:54:43,680 Men det vil ikke altid være tilfældet. 1115 00:54:43,680 --> 00:54:48,040 Hvis 2 allerede er sorteret i begyndelsen men du ser og der er en 1 her, 1116 00:54:48,040 --> 00:54:49,144 1 kommer til at støde det. 1117 00:54:49,144 --> 00:54:51,060 Og det kommer til at ende med at blive rumlede anyways. 1118 00:54:51,060 --> 00:54:56,250 >> Så i bedste fald, Det er faktisk bare kommer til at være n. 1119 00:54:56,250 --> 00:54:59,090 Hvis du har 1, 2, 3, 4, 5, 6, 7, 8, er du 1120 00:54:59,090 --> 00:55:00,940 kommer til at løbe gennem at hele listen gang 1121 00:55:00,940 --> 00:55:03,430 at kontrollere, om alt er fint. 1122 00:55:03,430 --> 00:55:07,390 Er alle klar på at køre tider med udvælgelsen så godt? 1123 00:55:07,390 --> 00:55:09,960 Jeg ved, jeg har tænkt mig igennem disse virkelig hurtig. 1124 00:55:09,960 --> 00:55:13,330 Men bare vide, at hvis du kender generelle begreber, skal du være god. 1125 00:55:13,330 --> 00:55:16,070 OK. 1126 00:55:16,070 --> 00:55:19,790 Så jeg vil bare give jer måske, ligesom, et minut til at tale med dine naboer 1127 00:55:19,790 --> 00:55:21,890 på hvilke er blot nogle af de væsentligste forskelle 1128 00:55:21,890 --> 00:55:23,540 mellem disse typer af former. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Vi vil gå over at snart. 1131 00:56:25,570 --> 00:56:26,444 PUBLIKUM: Åh, OK. 1132 00:56:26,444 --> 00:56:27,320 ANDI Peng: Ja. 1133 00:56:27,320 --> 00:56:28,380 OK. 1134 00:56:28,380 --> 00:56:33,420 Cool, lad os træde sammen som en klasse. 1135 00:56:33,420 --> 00:56:34,330 OK. 1136 00:56:34,330 --> 00:56:37,579 Så dette var form for en åbent spørgsmål i den forstand, 1137 00:56:37,579 --> 00:56:39,120 at der er masser af svar på dem. 1138 00:56:39,120 --> 00:56:40,746 Og vi vil gå over nogle af dem kort. 1139 00:56:40,746 --> 00:56:43,411 Jeg ville bare få jer tænke over, hvad differentieret 1140 00:56:43,411 --> 00:56:44,530 alle tre typer af mulige. 1141 00:56:44,530 --> 00:56:47,440 Og jeg hørte også en stor question-- hvad betyder mergesort gøre? 1142 00:56:47,440 --> 00:56:50,110 Store spørgsmål, fordi det er hvad vi dækker næste. 1143 00:56:50,110 --> 00:56:52,850 >> Så mergesort er den en slags, der fungerer 1144 00:56:52,850 --> 00:56:56,100 meget forskelligt fra de andre former. 1145 00:56:56,100 --> 00:56:58,180 Som du fyre kan see-- gjorde David gør det demo 1146 00:56:58,180 --> 00:57:01,130 hvor han havde alle de seje lyde af at se, hvordan fusionere 1147 00:57:01,130 --> 00:57:04,010 sortere løb, ligesom, uendeligt hurtigere end de to andre typer? 1148 00:57:04,010 --> 00:57:04,510 OK. 1149 00:57:04,510 --> 00:57:07,580 Så det er fordi fusionere sortere implementerer at kløft 1150 00:57:07,580 --> 00:57:11,020 og erobre koncept, som vi har talte om en masse i forelæsning. 1151 00:57:11,020 --> 00:57:14,550 I den forstand, at vi kan lide at arbejde smartere, ikke hårdere, når du deler 1152 00:57:14,550 --> 00:57:18,120 og erobre problemer og bryde dem ned, og derefter sætte dem sammen, 1153 00:57:18,120 --> 00:57:19,930 gode ting altid sker. 1154 00:57:19,930 --> 00:57:21,960 >> Så den måde, at fusionere sortere væsentlige værker 1155 00:57:21,960 --> 00:57:24,660 er, at det skiller en usorteret array i halve. 1156 00:57:24,660 --> 00:57:26,500 Og så det har fået to halvdele af arrays. 1157 00:57:26,500 --> 00:57:28,220 Og det bare sorterer de to halvdele. 1158 00:57:28,220 --> 00:57:31,750 Det bare holder dividere i halve, i halvdelen, i halve indtil alt er sorteret 1159 00:57:31,750 --> 00:57:33,680 og derefter rekursivt sætter det hele sammen. 1160 00:57:33,680 --> 00:57:36,550 >> Så det er virkelig abstrakt. 1161 00:57:36,550 --> 00:57:38,750 Så dette er bare en smule af pseudokode. 1162 00:57:38,750 --> 00:57:41,040 Giver det mening i den måde, det kører? 1163 00:57:41,040 --> 00:57:43,870 Så lad os bare sige, at du har en vifte af n elementer, ikke? 1164 00:57:43,870 --> 00:57:45,450 Hvis n er mindre end 2, kan du vende tilbage. 1165 00:57:45,450 --> 00:57:49,040 Fordi du ved, at hvis der er kun én ting, skal det sorteres. 1166 00:57:49,040 --> 00:57:52,600 Else, du sortere venstre halvdel, og så du sortere højre halvdel, 1167 00:57:52,600 --> 00:57:54,140 og så skal du flette. 1168 00:57:54,140 --> 00:57:56,979 >> Så mens der ser virkelig let, i virkeligheden tænker om det er 1169 00:57:56,979 --> 00:58:00,270 slags vanskelig. Fordi du er ligesom, godt, der er slags kører på sig selv. 1170 00:58:00,270 --> 00:58:00,769 Højre? 1171 00:58:00,769 --> 00:58:02,430 Det kører på sig selv. 1172 00:58:02,430 --> 00:58:05,479 Så i den forstand, David rørt ved rekursion i klassen. 1173 00:58:05,479 --> 00:58:07,270 Og det er et koncept Vi vil tale om mere. 1174 00:58:07,270 --> 00:58:11,430 Det er, at dette, disse to linjer her, er faktisk lige programmet 1175 00:58:11,430 --> 00:58:13,860 fortæller det til at køre sig selv med forskellige input. 1176 00:58:13,860 --> 00:58:17,230 Så i stedet for at køre sig i sin helhed n elementer, 1177 00:58:17,230 --> 00:58:20,530 du kan bryde det ned i venstre halvdel og højre halvdel 1178 00:58:20,530 --> 00:58:22,680 og derefter køre den igen. 1179 00:58:22,680 --> 00:58:26,050 >> Og så vil vi se på det visuelt, fordi jeg er en visuel lærende. 1180 00:58:26,050 --> 00:58:27,270 Det virker bedre for mig. 1181 00:58:27,270 --> 00:58:29,890 Så vil vi se på et visuelt eksempel her. 1182 00:58:29,890 --> 00:58:36,237 >> Lad os sige, at vi har et array, seks elementer, 3, 5, 2, 6, 4, 1, ikke er sorteret. 1183 00:58:36,237 --> 00:58:37,820 Okay, der er en masse på denne side. 1184 00:58:37,820 --> 00:58:43,179 Så hvis du fyre kan se på første skridt her, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 du kan opdele det i halve. 1186 00:58:44,220 --> 00:58:45,976 Du har 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Du ved, at disse aren't-- du ved ikke, om de er ordnet eller ej, 1188 00:58:48,850 --> 00:58:52,517 så du holder bryde dem ned, i halve, i halve, i halve, indtil til sidst, 1189 00:58:52,517 --> 00:58:53,600 du kun har et element. 1190 00:58:53,600 --> 00:58:56,790 Og et element altid sorteres, ikke? 1191 00:58:56,790 --> 00:59:01,560 >> Så vi ved, 3, 5, 2, 4, 6, 1, i sig selv, er sorteret. 1192 00:59:01,560 --> 00:59:05,870 Og nu kan vi sætte dem sammen igen. 1193 00:59:05,870 --> 00:59:07,510 Så vi kender den 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Vi sætter dem sammen. 1195 00:59:08,510 --> 00:59:09,617 Vi ved, det er sorterede. 1196 00:59:09,617 --> 00:59:10,450 De 2 er der stadig. 1197 00:59:10,450 --> 00:59:11,830 Vi kan sætte 4 og 6 sammen. 1198 00:59:11,830 --> 00:59:13,996 Vi ved, at der er sorteret, så vi sætte det sammen. 1199 00:59:13,996 --> 00:59:14,940 Og 1 er der. 1200 00:59:14,940 --> 00:59:18,720 >> Og så skal du bare se på disse to halvdele lige her. 1201 00:59:18,720 --> 00:59:21,300 Du har 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Du kan bare sammenligne begyndelsen af ​​alting. 1203 00:59:23,465 --> 00:59:26,340 Fordi du ved, at dette er sorteret og du ved, at der er sorteret. 1204 00:59:26,340 --> 00:59:29,360 Så du behøver ikke engang at sammenligne de 5, skal du blot sammenligne de 3. 1205 00:59:29,360 --> 00:59:32,070 Og 2 er mindre end 3, så du ved 2 skal gå i sidste ende. 1206 00:59:32,070 --> 00:59:33,120 >> Samme ting derovre. 1207 00:59:33,120 --> 00:59:34,740 Den 1 skal gå her. 1208 00:59:34,740 --> 00:59:37,330 Og så når du går til at sætte disse to værdier sammen, 1209 00:59:37,330 --> 00:59:39,950 du ved, at dette sorteres og du ved, at der er sorteret. 1210 00:59:39,950 --> 00:59:43,240 Så den 1 og den 2, 1 er mindre end 2. 1211 00:59:43,240 --> 00:59:45,570 Det fortæller dig, at 1 skal gå på enden af ​​denne 1212 00:59:45,570 --> 00:59:47,480 uden selv ser på 3 eller 5. 1213 00:59:47,480 --> 00:59:50,100 Og så 4, kan du bare check, det går lige i her. 1214 00:59:50,100 --> 00:59:51,480 Du behøver ikke at se på 5. 1215 00:59:51,480 --> 00:59:52,570 Samme ting med 6. 1216 00:59:52,570 --> 00:59:55,860 Du ved, at det 6-- det bare behøver ikke at blive kigget. 1217 00:59:55,860 --> 00:59:57,870 >> Og så på den måde, du er bare spare dig selv 1218 00:59:57,870 --> 00:59:59,526 en masse af trin, når du sammenligner. 1219 00:59:59,526 --> 01:00:02,150 Du behøver ikke at sammenligne hver element mod andre elementer. 1220 01:00:02,150 --> 01:00:05,230 Du skal bare sammenligne med dem at du skal sammenligne det mod. 1221 01:00:05,230 --> 01:00:06,870 Så det er sådan et abstrakt begreb. 1222 01:00:06,870 --> 01:00:10,540 Ingen bekymringer, hvis det ikke helt at ramme dig lige endnu. 1223 01:00:10,540 --> 01:00:14,740 Men generelt er dette hvordan en mergesort fungerer. 1224 01:00:14,740 --> 01:00:17,750 Spørgsmål, hurtige spørgsmål, inden jeg går videre? 1225 01:00:17,750 --> 01:00:18,550 Ja. 1226 01:00:18,550 --> 01:00:22,230 >> PUBLIKUM: Så du siger, at du tager 1, og derefter 4 og 6 1227 01:00:22,230 --> 01:00:23,860 og sætte dem i. 1228 01:00:23,860 --> 01:00:26,800 Så er those-- ikke ikke du kigger på dem 1229 01:00:26,800 --> 01:00:28,544 som separate elementer, ikke som helhed? 1230 01:00:28,544 --> 01:00:29,210 ANDI Peng: Ja. 1231 01:00:29,210 --> 01:00:32,020 Så hvad der sker er, at du dybest set 1232 01:00:32,020 --> 01:00:33,650 skaber en helt ny array. 1233 01:00:33,650 --> 01:00:36,690 Så du ved, at her, jeg har to arrays af størrelse 3, ikke? 1234 01:00:36,690 --> 01:00:39,600 Så du ved, at min sorterede vifte skal have seks elementer. 1235 01:00:39,600 --> 01:00:42,270 Så du bare oprette en nye mængde hukommelse. 1236 01:00:42,270 --> 01:00:44,270 Så du er lidt ligesom være spild af hukommelse, 1237 01:00:44,270 --> 01:00:46,186 men det betyder ikke noget fordi det er så lille. 1238 01:00:46,186 --> 01:00:48,590 Så du ser på 1 og du ser på de 2. 1239 01:00:48,590 --> 01:00:50,770 Og du ved, at 1 er mindre end 2. 1240 01:00:50,770 --> 01:00:53,840 Så du ved, at 1 skulle gå i begyndelsen af ​​alle dem. 1241 01:00:53,840 --> 01:00:55,850 >> Du behøver ikke engang at se på 3 og 5. 1242 01:00:55,850 --> 01:00:57,400 Så du ved 1 går der. 1243 01:00:57,400 --> 01:00:59,300 Så du dybest set hugge 1. 1244 01:00:59,300 --> 01:01:00,370 Det er, ligesom, døde for os. 1245 01:01:00,370 --> 01:01:03,690 Så vi bare have 2, 3, 5, og derefter 4 og 6. 1246 01:01:03,690 --> 01:01:06,270 Og så ved du at, du sammenligne 4 og 2, 1247 01:01:06,270 --> 01:01:07,560 Åh, de 2 skulle gå derind. 1248 01:01:07,560 --> 01:01:09,685 Så du plop de 2 ned, du hugge det ud. 1249 01:01:09,685 --> 01:01:12,060 Så du skal bare have den 3 og 5 i 4 og 6. 1250 01:01:12,060 --> 01:01:14,650 Og du bare holde hakke det ud indtil du lægger dem i array. 1251 01:01:14,650 --> 01:01:17,110 >> PUBLIKUM: Så du er bare altid sammenligne den [uhørligt]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI Peng: Præcis. 1253 01:01:17,710 --> 01:01:19,590 Så i den forstand, er du bare sammenligne det væsentlige, 1254 01:01:19,590 --> 01:01:21,240 ét nummer mod den anden nummer. 1255 01:01:21,240 --> 01:01:22,990 Og fordi du ved, at det er sorteret, du 1256 01:01:22,990 --> 01:01:24,350 behøver ikke at se gennem alle numrene. 1257 01:01:24,350 --> 01:01:25,870 Du skal bare nødt til at se på den første. 1258 01:01:25,870 --> 01:01:27,582 Og så kan du bare plop dem ned, fordi du ved, 1259 01:01:27,582 --> 01:01:29,640 de tilhører, hvor de skal tilhøre. 1260 01:01:29,640 --> 01:01:31,030 Ja. 1261 01:01:31,030 --> 01:01:32,920 Godt spørgsmål. 1262 01:01:32,920 --> 01:01:35,290 >> Og så hvis nogen af ​​jer er lidt ambitiøst, 1263 01:01:35,290 --> 01:01:38,660 velkommen til at se på denne kode. 1264 01:01:38,660 --> 01:01:40,680 Dette er faktisk den fysiske gennemførelse 1265 01:01:40,680 --> 01:01:42,150 af, hvordan vi ville skrive mergesort. 1266 01:01:42,150 --> 01:01:44,070 Og du kan se, det er meget kort. 1267 01:01:44,070 --> 01:01:46,310 Men ideerne bag det er temmelig kompliceret. 1268 01:01:46,310 --> 01:01:50,865 Så hvis du har lyst til at trække det ud i dit hjemmearbejde i aften, er du velkommen til. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> OK. 1271 01:01:54,740 --> 01:01:58,070 Så David også gik over dette i foredrag. 1272 01:01:58,070 --> 01:02:00,660 Hvad er de bedste fald runtime, worst case runtime, 1273 01:02:00,660 --> 01:02:05,680 og de forventede runtime af mergesort? 1274 01:02:05,680 --> 01:02:07,260 Et par sekunder til at tænke. 1275 01:02:07,260 --> 01:02:11,198 Dette er temmelig hårdt, men slags intuitiv, hvis du tænker over det. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Okay. 1278 01:02:23,054 --> 01:02:25,269 >> PUBLIKUM: Er værste fald n log n? 1279 01:02:25,269 --> 01:02:26,060 ANDI Peng: Præcis. 1280 01:02:26,060 --> 01:02:29,380 Og hvorfor er det n log n. 1281 01:02:29,380 --> 01:02:32,230 >> PUBLIKUM: Er det ikke, fordi det bliver eksponentielt hurtigere, 1282 01:02:32,230 --> 01:02:35,390 så det er ligesom en funktion af det i stedet for bare blot at være n 1283 01:02:35,390 --> 01:02:37,529 kvadreret eller noget? 1284 01:02:37,529 --> 01:02:38,320 ANDI Peng: Præcis. 1285 01:02:38,320 --> 01:02:40,750 Så grunden runtime på dette er n log 1286 01:02:40,750 --> 01:02:44,310 n er because-- hvad er du gør i alle disse trin? 1287 01:02:44,310 --> 01:02:46,190 Du bare hakke det på midten, højre? 1288 01:02:46,190 --> 01:02:48,750 Og så når vi laver den log, alt, det gør 1289 01:02:48,750 --> 01:02:53,150 er dividere et problem i halve, i halve, i halve, i flere halvdele. 1290 01:02:53,150 --> 01:02:56,430 Og i den forstand, kan du slags af fjerne den lineære model 1291 01:02:56,430 --> 01:02:57,510 at vi har brugt. 1292 01:02:57,510 --> 01:03:00,254 Fordi når du hugger ting i halve, det er en log. 1293 01:03:00,254 --> 01:03:02,420 Det er bare den matematiske måde at repræsentere det. 1294 01:03:02,420 --> 01:03:06,310 >> Og så til sidst, i slutningen, er du bare at gøre en sidste passage gennem 1295 01:03:06,310 --> 01:03:07,930 at sætte dem alle i orden, ikke? 1296 01:03:07,930 --> 01:03:10,330 Og så hvis du bare nødt til at kontrollere en ting, det er n. 1297 01:03:10,330 --> 01:03:13,420 Og så er du sådan multiplicere de to sammen. 1298 01:03:13,420 --> 01:03:17,660 Så det er ligesom du har fået, at den endelige kontrollere for n hernede med en log over n 1299 01:03:17,660 --> 01:03:18,390 heroppe. 1300 01:03:18,390 --> 01:03:21,060 Og hvis du ganger dem, der er n log n. 1301 01:03:21,060 --> 01:03:26,100 >> Og så det bedste tilfælde og værste tilfælde og forventet er alle n log n. 1302 01:03:26,100 --> 01:03:27,943 Det er også ligesom en anden slags. 1303 01:03:27,943 --> 01:03:30,090 Det er ligesom valg Sorter i den forstand, at det 1304 01:03:30,090 --> 01:03:32,131 er ligegyldigt, hvad din Listen er, det bare at gå 1305 01:03:32,131 --> 01:03:34,801 til at gøre det samme hver eneste gang. 1306 01:03:34,801 --> 01:03:35,300 OK. 1307 01:03:35,300 --> 01:03:39,950 Så som du fyre kan se, selvom den slags, som vi har gået through-- n 1308 01:03:39,950 --> 01:03:41,660 kvadreret, det er ikke meget effektiv. 1309 01:03:41,660 --> 01:03:47,060 Og selv denne n log n er ikke den mest effektive. 1310 01:03:47,060 --> 01:03:49,720 Hvis du fyre er nysgerrige, der er sortere mekanismer 1311 01:03:49,720 --> 01:03:54,310 der er så effektive, at de er næsten væsentlige fladt i runtime. 1312 01:03:54,310 --> 01:03:55,420 >> Du har fået nogle log n s. 1313 01:03:55,420 --> 01:03:58,190 Du har fået nogle log log n s. 1314 01:03:58,190 --> 01:04:00,330 Vi ikke røre dem i denne klasse lige nu. 1315 01:04:00,330 --> 01:04:02,663 Men hvis du fyre er nysgerrige, velkommen til at google, hvad er 1316 01:04:02,663 --> 01:04:04,392 de mest effektive sorteringsmekanismerne. 1317 01:04:04,392 --> 01:04:06,350 Jeg ved det ikke, er der nogle virkelig sjove dem, 1318 01:04:06,350 --> 01:04:09,860 like-- der er nogle virkelig sjove dem, folk gør. 1319 01:04:09,860 --> 01:04:12,210 Og du spekulerer på, hvordan de nogensinde tænkt på det. 1320 01:04:12,210 --> 01:04:15,730 Så google, hvis du har nogle fritid tid, om, hvad er nogle sjove måder 1321 01:04:15,730 --> 01:04:17,730 at people-- samt effektive ways-- mennesker 1322 01:04:17,730 --> 01:04:20,371 har kunnet gennemføre mulige. 1323 01:04:20,371 --> 01:04:20,870 OK. 1324 01:04:20,870 --> 01:04:22,880 Og her er bare en handy lille diagram. 1325 01:04:22,880 --> 01:04:26,850 Jeg kender alle jer, før det quiz 0, vil være i dit værelse sandsynligvis forsøger 1326 01:04:26,850 --> 01:04:27,960 at huske det. 1327 01:04:27,960 --> 01:04:30,940 Så det er rart i der for jer. 1328 01:04:30,940 --> 01:04:37,120 Bare glem ikke logik, der made-- hvorfor disse numre foregik. 1329 01:04:37,120 --> 01:04:39,870 Hvis du altid er faret vild, bare gøre du vide, hvad den slags er. 1330 01:04:39,870 --> 01:04:40,820 Og du kan køre igennem dem i dit sind 1331 01:04:40,820 --> 01:04:42,903 at finde ud af, hvorfor de, svar er disse svar. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Okay. 1334 01:04:47,600 --> 01:04:49,680 Så vi kommer til at bevæge sig på endelig at søge. 1335 01:04:49,680 --> 01:04:51,638 Fordi som dem af jer der har læst pset, 1336 01:04:51,638 --> 01:04:55,175 søgning er også en del af denne uges problem sætter. 1337 01:04:55,175 --> 01:04:57,300 Du vil blive bedt om at gennemføre to typer af søgninger. 1338 01:04:57,300 --> 01:05:00,070 Den ene er en lineær søgning og den ene er en binær søgning. 1339 01:05:00,070 --> 01:05:01,760 >> Så den lineære søgning er forholdsvis let. 1340 01:05:01,760 --> 01:05:04,070 Du ønsker bare at søge element af en liste for at se, om du får det. 1341 01:05:04,070 --> 01:05:05,444 Du skal bare nødt til at gentage gennem. 1342 01:05:05,444 --> 01:05:08,170 Og hvis det er lig med noget, du kan bare returnere den, ikke? 1343 01:05:08,170 --> 01:05:10,890 Men den, som vi er mest interesseret i at tale om 1344 01:05:10,890 --> 01:05:14,550 er binær søgning, højre, som er den opdele og erobre mekanisme, som 1345 01:05:14,550 --> 01:05:18,190 David demonstrerer i forelæsning. 1346 01:05:18,190 --> 01:05:20,810 >> Husk telefonbog eksempel at han bliver ved med at bringe op, 1347 01:05:20,810 --> 01:05:23,960 den, han slags kæmpet en smule på det seneste år, 1348 01:05:23,960 --> 01:05:27,530 hvor man opdele problemet i halve, i halve, i halve, igen og igen, 1349 01:05:27,530 --> 01:05:30,730 indtil du finder det, du leder efter? 1350 01:05:30,730 --> 01:05:33,727 Og du har fået den runtime af, at så godt. 1351 01:05:33,727 --> 01:05:35,810 Og du kan se, er det betydeligt mere effektiv 1352 01:05:35,810 --> 01:05:39,080 end nogen anden type søgning. 1353 01:05:39,080 --> 01:05:41,880 >> Så den måde, at vi ville gå om gennemføre en binær søgning 1354 01:05:41,880 --> 01:05:46,510 er, hvis vi havde en matrix, indeks 0 til 6, syv elementer, 1355 01:05:46,510 --> 01:05:49,790 vi kan se i midten, right-- beklager, hvis vores spørgsmål first-- 1356 01:05:49,790 --> 01:05:53,840 hvis vi ønsker at stille spørgsmålet om, gør arrayet indeholder det element af 7, 1357 01:05:53,840 --> 01:05:56,840 naturligvis være mennesker, og som har sådan en lille matrix, er det nemt for os 1358 01:05:56,840 --> 01:05:58,210 at sige ja. 1359 01:05:58,210 --> 01:06:05,750 Men den måde at gennemføre en binær søgning ville være at se i midten. 1360 01:06:05,750 --> 01:06:08,020 >> Vi ved, at indekset 3 er midten, fordi vi 1361 01:06:08,020 --> 01:06:09,270 ved, at der er syv elementer. 1362 01:06:09,270 --> 01:06:10,670 Hvad 7 divideret med 2? 1363 01:06:10,670 --> 01:06:12,850 Du kan hugge det ekstra 1. 1364 01:06:12,850 --> 01:06:14,850 Du har 3 i midten. 1365 01:06:14,850 --> 01:06:17,590 Så er vifte af 3 lig med 7? 1366 01:06:17,590 --> 01:06:18,900 Det er ikke, vel? 1367 01:06:18,900 --> 01:06:21,050 Men vi kan gøre et par checks. 1368 01:06:21,050 --> 01:06:25,380 Er array af 3 mindre end 7 eller er array af 3 større end 7? 1369 01:06:25,380 --> 01:06:27,240 >> Og vi ved, at det er mindre end 7. 1370 01:06:27,240 --> 01:06:30,259 Så vi ved, at, åh, den skal ikke ligge i venstre halvdel. 1371 01:06:30,259 --> 01:06:32,300 Vi ved, at det skal være i den højre halvdel, ikke? 1372 01:06:32,300 --> 01:06:34,662 Så kan vi bare hugge halvdelen array. 1373 01:06:34,662 --> 01:06:36,370 Vi behøver ikke engang at se på det længere. 1374 01:06:36,370 --> 01:06:38,711 Fordi vi ved, at halvdelen af ​​vores problem-- 1375 01:06:38,711 --> 01:06:41,210 vi ved, at svaret er i højre halvdel af vores problem. 1376 01:06:41,210 --> 01:06:42,580 Så vi bare se på det nu. 1377 01:06:42,580 --> 01:06:44,860 >> Så nu ser vi på det midten af ​​hvad der er tilbage. 1378 01:06:44,860 --> 01:06:46,880 Det indeks 5. 1379 01:06:46,880 --> 01:06:50,200 Vi gør det samme kontrol igen og vi kan se, at det er mindre. 1380 01:06:50,200 --> 01:06:52,050 Så vi ser til venstre for det. 1381 01:06:52,050 --> 01:06:53,430 Og så ser vi, at check. 1382 01:06:53,430 --> 01:06:57,600 Er array værdi på indeks 4 lig med 7? 1383 01:06:57,600 --> 01:06:58,260 Det er. 1384 01:06:58,260 --> 01:07:03,580 Så vi kan vende tilbage sandt, fordi vi fandt værdien i vores liste. 1385 01:07:03,580 --> 01:07:06,738 Er den måde, jeg gik igennem det mening for alle? 1386 01:07:06,738 --> 01:07:08,760 OK. 1387 01:07:08,760 --> 01:07:11,670 Jeg vil give jer måske, ligesom, tre, fire minutter til at finde ud af 1388 01:07:11,670 --> 01:07:13,270 hvordan man pseudokode dette. 1389 01:07:13,270 --> 01:07:18,070 >> Så forestille Jeg bad dig om at skrive en funktion kaldet søgning (), der vendte tilbage 1390 01:07:18,070 --> 01:07:20,640 en værdi, en boolesk værdi, det var sandt eller false-- lignende, 1391 01:07:20,640 --> 01:07:22,970 tilfældet, hvis du har fundet den værdi, falsk, hvis du ikke. 1392 01:07:22,970 --> 01:07:25,230 Og så var bestået i værdi, du 1393 01:07:25,230 --> 01:07:28,410 søgte i værdier, som er den array-- åh, jeg helt sikkert sætte 1394 01:07:28,410 --> 01:07:29,410 at på det forkerte sted. 1395 01:07:29,410 --> 01:07:29,580 OK. 1396 01:07:29,580 --> 01:07:31,829 Anyways, der skal have været til højre for værdier. 1397 01:07:31,829 --> 01:07:36,280 Og derefter int n er antallet af elementer i den opstilling. 1398 01:07:36,280 --> 01:07:39,430 Hvordan ville du gå om at forsøge at pseudokode dette problem i? 1399 01:07:39,430 --> 01:07:41,630 Jeg vil give dig fyre som tre minutter til at gøre det. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Nej, jeg tror, ​​der er only-- Ja, der er en lige heroppe. 1402 01:08:02,595 --> 01:08:03,261 PUBLIKUM: Kan jeg? 1403 01:08:03,261 --> 01:08:04,388 ANDI Peng: Ja, jeg har dig. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 Er det i orden? 1406 01:08:11,050 --> 01:08:12,290 OK, cool. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> OK. 1409 01:10:44,720 --> 01:10:47,630 Alle rigtige gutter, vi er kommer til at tøjle det i. 1410 01:10:47,630 --> 01:10:49,730 OK. 1411 01:10:49,730 --> 01:10:54,020 Så antager vi har fået denne dejlige lille array med n værdier i det. 1412 01:10:54,020 --> 01:10:55,170 Jeg har ikke tegne linjerne. 1413 01:10:55,170 --> 01:10:58,649 Men hvordan ville vi gå om forsøger at skrive dette? 1414 01:10:58,649 --> 01:11:00,440 Er der nogen ønsker at give mig den første linje? 1415 01:11:00,440 --> 01:11:02,814 Hvis du vil give mig første linje i denne pseudokode. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> PUBLIKUM: [uhørligt] 1418 01:11:08,430 --> 01:11:10,138 PUBLIKUM: Du ville have at gentage through-- 1419 01:11:10,138 --> 01:11:11,094 PUBLIKUM: Bare en anden for løkke? 1420 01:11:11,094 --> 01:11:11,760 PUBLIKUM: --for. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI Peng: Så denne ene er lidt tricky. 1423 01:11:17,780 --> 01:11:23,130 Tænk om-- du ønsker at holde kører denne løkke 1424 01:11:23,130 --> 01:11:27,950 igen og igen, indtil hvornår? 1425 01:11:27,950 --> 01:11:30,819 >> PUBLIKUM: Indtil [uhørligt] er lig med denne værdi. 1426 01:11:30,819 --> 01:11:31,610 ANDI Peng: Præcis. 1427 01:11:31,610 --> 01:11:33,900 Så kan du faktisk bare write-- Vi kan endda forenkle det mere. 1428 01:11:33,900 --> 01:11:35,630 Vi kan bare gøre en while-løkke, ikke? 1429 01:11:35,630 --> 01:11:39,380 Så du kan bare have loop-- vi ved, at det er et stykke tid. 1430 01:11:39,380 --> 01:11:42,850 Men for lige nu, jeg skal at sige "loop" - gennem hvad? 1431 01:11:42,850 --> 01:11:46,640 Loop until-- hvad der er vores slutter tilstand? 1432 01:11:46,640 --> 01:11:47,510 Jeg tror, ​​jeg hørte det. 1433 01:11:47,510 --> 01:11:48,530 Jeg hørte nogen sige det. 1434 01:11:48,530 --> 01:11:51,255 >> Publikum: Værdier lig midten. 1435 01:11:51,255 --> 01:11:52,255 ANDI Peng: Sig det igen. 1436 01:11:52,255 --> 01:11:54,470 PUBLIKUM: Eller, indtil værdi, du søger 1437 01:11:54,470 --> 01:11:58,470 for er lig med den midterste værdi. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI Peng: Hvad hvis det ikke er der? 1439 01:12:00,280 --> 01:12:03,113 Hvad hvis den værdi, du søger for er faktisk ikke i dette array? 1440 01:12:03,113 --> 01:12:05,890 PUBLIKUM: Du vender tilbage 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI Peng: Men hvad ønsker vi at loop indtil hvis vi har en tilstand? 1442 01:12:08,850 --> 01:12:09,350 Ja. 1443 01:12:09,350 --> 01:12:11,239 >> PUBLIKUM: Indtil der er kun én værdi? 1444 01:12:11,239 --> 01:12:13,530 ANDI Peng: Du kan loop until-- så du ved, at du er 1445 01:12:13,530 --> 01:12:15,714 vil have en max værdi, ikke? 1446 01:12:15,714 --> 01:12:18,130 Og du ved, at du vil at have en min værdi, ikke? 1447 01:12:18,130 --> 01:12:20,379 Fordi også, det er noget Jeg glemte at sige før, 1448 01:12:20,379 --> 01:12:22,640 at noget, der er kritisk om binær søgning 1449 01:12:22,640 --> 01:12:24,182 er, at dit array allerede er sorteret. 1450 01:12:24,182 --> 01:12:26,973 Fordi der er ingen måde at gøre dette, hvis de er bare tilfældige værdier. 1451 01:12:26,973 --> 01:12:29,190 Du ved ikke, hvis man er større end den anden, ikke? 1452 01:12:29,190 --> 01:12:32,720 >> Så du ved, at din max og dine mins er her, ikke? 1453 01:12:32,720 --> 01:12:35,590 Hvis du kommer til at justere din max i dine minutter og mid-- 1454 01:12:35,590 --> 01:12:38,470 lad os bare antage din mid-værdi er rigtige her-- 1455 01:12:38,470 --> 01:12:43,910 du vil stort set loop indtil din minimum er 1456 01:12:43,910 --> 01:12:47,510 om det samme som dit max, til højre, eller hvis dit max er ikke det samme som din min. 1457 01:12:47,510 --> 01:12:48,040 Højre? 1458 01:12:48,040 --> 01:12:51,340 For når det sker, du ved, at du i sidste ende har ramt den samme værdi. 1459 01:12:51,340 --> 01:12:59,135 Så du ønsker at sløjfe indtil din min er mindre end eller lig at-- UPS, 1460 01:12:59,135 --> 01:13:01,510 ikke mindre end eller lig med den anden vej around-- max er. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Fik at give mening? 1463 01:13:16,160 --> 01:13:18,810 Jeg tog et par forsøger at få denne ret. 1464 01:13:18,810 --> 01:13:21,869 Men loop indtil din max værdi er i det væsentlige næsten mindre 1465 01:13:21,869 --> 01:13:23,410 end eller lig med din minimum, ikke? 1466 01:13:23,410 --> 01:13:25,201 Det er, når du ved at du har konvergeret. 1467 01:13:25,201 --> 01:13:29,290 PUBLIKUM: Hvornår vil din maksimale værdi være mindre end den mindste? 1468 01:13:29,290 --> 01:13:31,040 ANDI Peng: Hvis du holder justere den, hvilket 1469 01:13:31,040 --> 01:13:32,380 er det, vi går at gøre i dette. 1470 01:13:32,380 --> 01:13:33,460 Giver det mening? 1471 01:13:33,460 --> 01:13:35,750 Minimum og max er blot heltal, at vi er nok 1472 01:13:35,750 --> 01:13:39,260 vil ønsker at skabe for at holde styr på, hvor vi leder efter. 1473 01:13:39,260 --> 01:13:41,790 Fordi array eksisterer uanset hvad vi laver. 1474 01:13:41,790 --> 01:13:45,030 Ligesom, vi er ikke rent fysisk hugge array, ikke? 1475 01:13:45,030 --> 01:13:47,261 Vi er bare justere hvor vi leder efter. 1476 01:13:47,261 --> 01:13:48,136 Giver det mening? 1477 01:13:48,136 --> 01:13:48,472 >> Publikum: Ja. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI Peng: OK. 1479 01:13:49,110 --> 01:13:57,090 Så hvis det er betingelsen for vores løkke, hvad vil vi inde i denne løkke? 1480 01:13:57,090 --> 01:13:58,700 Hvad skal vi være der ønsker at gøre? 1481 01:13:58,700 --> 01:14:02,390 Så lige nu, har vi fået en max og en min, til højre, 1482 01:14:02,390 --> 01:14:04,962 formentlig skabt op her et sted. 1483 01:14:04,962 --> 01:14:07,170 Vi kommer til at sikkert gerne at finde en mellemvej, ikke? 1484 01:14:07,170 --> 01:14:08,450 Hvordan skal vi være stand til at finde midten? 1485 01:14:08,450 --> 01:14:09,491 Hvad er mathematical-- 1486 01:14:09,491 --> 01:14:11,079 PUBLIKUM: Max plus min divideret med 2. 1487 01:14:11,079 --> 01:14:11,870 ANDI Peng: Præcis. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Giver det mening? 1490 01:14:21,620 --> 01:14:25,780 Og tror du fyre se, hvorfor vi ikke bare use-- hvorfor vi gjorde dette 1491 01:14:25,780 --> 01:14:27,850 i stedet for at gøre netop n divideret med 2? 1492 01:14:27,850 --> 01:14:30,310 Det er fordi n er en værdi der kommer til at forblive den samme. 1493 01:14:30,310 --> 01:14:30,979 Højre? 1494 01:14:30,979 --> 01:14:34,020 Men som vi justerer vores minimum og maksimale værdier, de kommer til at ændre. 1495 01:14:34,020 --> 01:14:36,040 Og som et resultat, vores midten vil også ændre sig. 1496 01:14:36,040 --> 01:14:37,873 Så det er derfor, vi ønsker at gøre dette her. 1497 01:14:37,873 --> 01:14:38,510 OK. 1498 01:14:38,510 --> 01:14:41,600 >> Og så, nu, vi har fundet our-- ja. 1499 01:14:41,600 --> 01:14:44,270 >> PUBLIKUM: Bare en hurtig question-- når du siger min og max, 1500 01:14:44,270 --> 01:14:46,410 vi antager, at det er allerede ordnet? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI Peng: Ja, det er faktisk en forudsætning for en binær søgning, 1502 01:14:48,400 --> 01:14:49,816 at du er nødt til at vide det er sorteret. 1503 01:14:49,816 --> 01:14:53,660 Hvilket er grunden til sortering, du skriver i dit problem indstillet før din binær søgning. 1504 01:14:53,660 --> 01:14:55,910 OK. 1505 01:14:55,910 --> 01:14:58,876 Så nu, at vi ved, hvor vores midtpunkt er, hvad vil du gøre her? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> PUBLIKUM: Vi ønsker at sammenligne at til den anden. 1508 01:15:04,319 --> 01:15:05,110 ANDI Peng: Præcis. 1509 01:15:05,110 --> 01:15:12,280 Så du kommer til at sammenligne midten til værdi, ikke? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 Og hvad siger det os, når vi sammenligner? 1512 01:15:18,670 --> 01:15:22,226 Hvad ønsker vi at gøre bagefter? 1513 01:15:22,226 --> 01:15:25,389 >> PUBLIKUM: Hvis værdien er større end midten, ønsker vi at skære det ud. 1514 01:15:25,389 --> 01:15:26,180 ANDI Peng: Præcis. 1515 01:15:26,180 --> 01:15:33,940 Så hvis værdien er større end midten, vi er 1516 01:15:33,940 --> 01:15:36,550 vil ønsker at ændre disse minimum og Maxes, ikke? 1517 01:15:36,550 --> 01:15:38,980 Hvad ønsker vi at ændre? 1518 01:15:38,980 --> 01:15:42,145 Så hvis vi kender værdien er et sted herinde, hvad gør du vi ændre? 1519 01:15:42,145 --> 01:15:44,758 Vi ønsker at ændre vores minimum at være midt, højre? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 Og så ellers, hvis det er i denne halvdelen, hvad gør vi ønsker at ændre? 1522 01:15:54,292 --> 01:15:55,306 >> PUBLIKUM: Din maksimum. 1523 01:15:55,306 --> 01:15:55,972 ANDI Peng: Ja. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 Og så er du bare at holde looping, ikke? 1526 01:16:04,680 --> 01:16:08,920 Fordi nu, efter en iteration igennem, du har fået en max her. 1527 01:16:08,920 --> 01:16:10,760 Og så kan du genberegne en mid. 1528 01:16:10,760 --> 01:16:11,990 Og så kan du sammenligne. 1529 01:16:11,990 --> 01:16:14,766 Og du kommer til at holde i gang indtil minutter og Maxes 1530 01:16:14,766 --> 01:16:15,890 har væsentlige konvergeret. 1531 01:16:15,890 --> 01:16:17,890 Og det er, når du ved, at du har ramt i slutningen af ​​det. 1532 01:16:17,890 --> 01:16:20,280 Og enten du har fundet det eller du ikke på dette punkt. 1533 01:16:20,280 --> 01:16:23,170 >> Betyder det mening at alle? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 OK. 1536 01:16:26,770 --> 01:16:27,900 Det er temmelig vigtigt, fordi du har 1537 01:16:27,900 --> 01:16:29,760 at skrive dette i din kode i aften. 1538 01:16:29,760 --> 01:16:32,660 Men du fyre har en temmelig god fornemmelse af, hvad du skal gøre, 1539 01:16:32,660 --> 01:16:34,051 hvilket er godt. 1540 01:16:34,051 --> 01:16:34,550 OK. 1541 01:16:34,550 --> 01:16:38,840 Så vi har fået omkring syv minutter tilbage sektion. 1542 01:16:38,840 --> 01:16:43,170 Så vi kommer til at tale om denne pset at vi vil gøre. 1543 01:16:43,170 --> 01:16:46,410 Så pset er opdelt i to halvdele. 1544 01:16:46,410 --> 01:16:50,230 Den første halvdel involverer gennemføre et fund 1545 01:16:50,230 --> 01:16:54,210 hvor du skriver en lineær søgning, en binær søgning og en sorteringsalgoritme. 1546 01:16:54,210 --> 01:16:56,690 >> Så dette er den første tid i en pset hvor 1547 01:16:56,690 --> 01:17:00,050 vi vil være at give jer, hvad der kaldes fordeling kode, som er kode 1548 01:17:00,050 --> 01:17:02,740 at vi har pre-skrevet, men netop forladt nogle stykker off 1549 01:17:02,740 --> 01:17:04,635 for dig at afslutte skrive. 1550 01:17:04,635 --> 01:17:07,510 Så jer, når man ser på dette kode, kan du få virkelig bange. 1551 01:17:07,510 --> 01:17:08,630 Hvis du lige er lyst, ahh, jeg ved ikke, hvad der er at gøre, 1552 01:17:08,630 --> 01:17:11,670 Jeg ved det ikke, ligesom, der synes så kompliceret, ahh, slappe af. 1553 01:17:11,670 --> 01:17:12,170 Det er ok. 1554 01:17:12,170 --> 01:17:12,930 Læs spec. 1555 01:17:12,930 --> 01:17:16,920 Den spec vil præcist forklare dig hvad alle disse programmer gør. 1556 01:17:16,920 --> 01:17:20,560 >> For eksempel generate.c er et program der vil komme med din pset. 1557 01:17:20,560 --> 01:17:24,060 Du behøver faktisk ikke at røre ved det, men bør du forstå, hvad det gør. 1558 01:17:24,060 --> 01:17:28,550 Og generate.c, alt det gør, er enten at generere tilfældige tal 1559 01:17:28,550 --> 01:17:32,400 eller du kan give det et frø, som en indtegnet nummer, det tager, 1560 01:17:32,400 --> 01:17:34,140 og det genererer flere numre. 1561 01:17:34,140 --> 01:17:37,170 Så der er en bestemt måde at gennemføre generate.c hvor 1562 01:17:37,170 --> 01:17:42,760 kan du bare lave en masse numre for dig at teste dine andre metoder på. 1563 01:17:42,760 --> 01:17:45,900 >> Så hvis du ville, for eksempel teste din fund, 1564 01:17:45,900 --> 01:17:48,970 du ønsker at køre generate.c, generere en masse tal, 1565 01:17:48,970 --> 01:17:50,880 og derefter køre din hjælpere funktion. 1566 01:17:50,880 --> 01:17:53,930 Din hjælpere funktion er, hvor du er rent fysisk at skrive kode. 1567 01:17:53,930 --> 01:17:59,330 Og tænk på hjælpere som et bibliotek fil du skriver, at fund der ringer. 1568 01:17:59,330 --> 01:18:02,950 Og så inden helpers.c, vil du gør søgning og sortering. 1569 01:18:02,950 --> 01:18:06,500 >> Og så er du kommer til at væsentlige bare sætte dem alle sammen. 1570 01:18:06,500 --> 01:18:10,350 Den spec vil fortælle dig, hvordan du sætte det på kommandolinjen. 1571 01:18:10,350 --> 01:18:14,880 Og du vil være i stand til at teste, om ikke din sortere og søge fungerer. 1572 01:18:14,880 --> 01:18:15,870 Cool. 1573 01:18:15,870 --> 01:18:18,720 Har nogen allerede begyndt, og stødt problemer eller spørgsmål 1574 01:18:18,720 --> 01:18:20,520 de har lige nu med dette? 1575 01:18:20,520 --> 01:18:21,020 OK. 1576 01:18:21,020 --> 01:18:21,476 >> PUBLIKUM: Vent. 1577 01:18:21,476 --> 01:18:21,932 Jeg har et spørgsmål. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI Peng: Ja. 1579 01:18:22,844 --> 01:18:28,390 >> PUBLIKUM: Så jeg begyndte at gøre den lineære søgning i helpers.c 1580 01:18:28,390 --> 01:18:29,670 og det var ikke rigtig fungerer. 1581 01:18:29,670 --> 01:18:34,590 Men senere fandt jeg ud af vi bare nødt til at slette det og gøre binær søgning. 1582 01:18:34,590 --> 01:18:36,991 Så betyder det noget, hvis det ikke virker? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI Peng: korte svar er nej. 1585 01:18:41,510 --> 01:18:42,642 Men da vi er not-- 1586 01:18:42,642 --> 01:18:44,350 PUBLIKUM: Men ingen er faktisk kontrol. 1587 01:18:44,350 --> 01:18:46,058 ANDI Peng: Vi er aldrig kommer til at se det. 1588 01:18:46,058 --> 01:18:49,590 Men du sandsynligvis ønsker at gøre sikker på din søgning virker. 1589 01:18:49,590 --> 01:18:51,700 Fordi hvis din lineære søgning ikke virker, 1590 01:18:51,700 --> 01:18:54,410 så chancerne er din binære søgningen er ikke til at arbejde så godt. 1591 01:18:54,410 --> 01:18:56,646 Fordi du har lignende logik i dem begge. 1592 01:18:56,646 --> 01:18:58,020 Og nej, det er faktisk ligegyldigt. 1593 01:18:58,020 --> 01:19:01,300 Så de eneste, du vil vise i er sortering og binær søgning. 1594 01:19:01,300 --> 01:19:02,490 Ja. 1595 01:19:02,490 --> 01:19:06,610 >> Og også, en masse børn var forsøger at kompilere helpers.c. 1596 01:19:06,610 --> 01:19:09,550 Du er faktisk ikke tilladt at gøre det, fordi helpers.c 1597 01:19:09,550 --> 01:19:11,200 ikke har en hovedfunktion. 1598 01:19:11,200 --> 01:19:13,550 Og så bør du kun være faktisk kompilering 1599 01:19:13,550 --> 01:19:18,670 generere og find, fordi find opkald helpers.c og funktionerne i den. 1600 01:19:18,670 --> 01:19:20,790 Så det gør debugging en smerte i butt. 1601 01:19:20,790 --> 01:19:22,422 Men det er, hvad vi skal gøre. 1602 01:19:22,422 --> 01:19:23,880 PUBLIKUM: Du skal bare gøre alle, ikke? 1603 01:19:23,880 --> 01:19:27,290 ANDI Peng: Du kan bare gøre alle så godt, ja. 1604 01:19:27,290 --> 01:19:28,060 OK. 1605 01:19:28,060 --> 01:19:32,570 Så det er det i form af, hvad den pset beder jer alle at gøre. 1606 01:19:32,570 --> 01:19:35,160 Hvis du har spørgsmål, er du velkommen velkommen til at spørge mig efter sektion. 1607 01:19:35,160 --> 01:19:37,580 Jeg vil være her for, ligesom, 20 minutter. 1608 01:19:37,580 --> 01:19:40,500 >> Og yeah, pset s virkelig ikke så slemt. 1609 01:19:40,500 --> 01:19:41,680 Du fyre burde være OK. 1610 01:19:41,680 --> 01:19:43,250 Disse, blot følge retningslinjer. 1611 01:19:43,250 --> 01:19:47,840 Slags har en følelse af, logisk, hvad bør ske, og du vil være fint. 1612 01:19:47,840 --> 01:19:48,690 Må ikke være alt for bange. 1613 01:19:48,690 --> 01:19:50,220 Der er en masse kode allerede skrevet der. 1614 01:19:50,220 --> 01:19:53,011 Må ikke være alt for bange, hvis du ikke gør forstå, hvad alt dette betyder. 1615 01:19:53,011 --> 01:19:54,749 Hvis det er en masse, det er helt fint. 1616 01:19:54,749 --> 01:19:55,790 Og kommer til kontortid. 1617 01:19:55,790 --> 01:19:57,520 Vi hjælper dig med at tage et kig. 1618 01:19:57,520 --> 01:20:00,810 >> PUBLIKUM: Med den ekstra funktioner, vi ser dem op? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI Peng: Ja, de er i koden. 1620 01:20:03,417 --> 01:20:05,750 I spillet af 15, halvdelen af det er allerede skrevet til dig. 1621 01:20:05,750 --> 01:20:09,310 Så disse funktioner er allerede i koden. 1622 01:20:09,310 --> 01:20:12,020 Yep. 1623 01:20:12,020 --> 01:20:12,520 Okay. 1624 01:20:12,520 --> 01:20:14,000 Nå, held og lykke. 1625 01:20:14,000 --> 01:20:15,180 Det er en modbydelig dag. 1626 01:20:15,180 --> 01:20:19,370 Så forhåbentlig jer ikke føler sig alt for dårligt om opholder sig inde og kodning. 1627 01:20:19,370 --> 01:20:22,133