1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> TALARE 1: Hej alla! 3 00:00:12,300 --> 00:00:13,890 Välkommen tillbaka till avsnitt. 4 00:00:13,890 --> 00:00:17,480 Så glad att se så många av er både här, och alla som tittar på nätet. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 Så, som vanligt välkommen tillbaka. 7 00:00:20,920 --> 00:00:24,360 Jag hoppas att ni alla haft en härlig helg, full av vila, avkoppling. 8 00:00:24,360 --> 00:00:26,026 Det var vackert ute igår. 9 00:00:26,026 --> 00:00:27,525 Så, jag hoppas du haft utomhus. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> Så först ett par meddelanden. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Betygs. 14 00:00:32,700 --> 00:00:37,350 Så, de flesta av er bör ha fått en maila mig om din Scratch Pset, 15 00:00:37,350 --> 00:00:39,920 liksom omdöme för Pset 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 Så, bara ett par saker. 18 00:00:42,220 --> 00:00:45,150 Var noga med att använda check50 i style50. 19 00:00:45,150 --> 00:00:47,250 Dessa är tänkta att vara resurser för er killar, 20 00:00:47,250 --> 00:00:50,660 att se till att du får så många poäng som du kan 21 00:00:50,660 --> 00:00:52,390 utan att i onödan förlora dem. 22 00:00:52,390 --> 00:00:54,407 Så saker som stil är mycket viktiga. 23 00:00:54,407 --> 00:00:55,740 Vi kommer att ta bort det. 24 00:00:55,740 --> 00:00:58,115 Några av er kanske redan har märkt att från din Pset. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 Och check50 är bara en riktigt enkelt sätt att se till 27 00:01:01,450 --> 00:01:05,050 att vi faktiskt är åter vad måste returneras till användaren, 28 00:01:05,050 --> 00:01:06,690 och att allt fungerar korrekt. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> På den andra anteckningen, se till att din ladda upp saker till rätt mapp. 31 00:01:12,040 --> 00:01:14,470 Det gör mitt liv bara en Lite svårare 32 00:01:14,470 --> 00:01:18,836 Om du laddar upp Pset 2 i Pset 1 för när jag hämta saker, 33 00:01:18,836 --> 00:01:20,085 de inte hämtas. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 Och jag vet att det är lite wonky i ett system för att vänja sig, 36 00:01:24,560 --> 00:01:26,950 men bara vara super försiktig, om så bara för mig, 37 00:01:26,950 --> 00:01:30,080 så att när du får e-post på liknande 02:00 och jag är betygssättning. 38 00:01:30,080 --> 00:01:33,710 Om inte orsaka jag måste titta runt för din Pset. 39 00:01:33,710 --> 00:01:34,440 Cool. 40 00:01:34,440 --> 00:01:37,270 >> Jag vet att det är tidigt, men jag helt fick tas på sängen 41 00:01:37,270 --> 00:01:40,800 av en uppsats som är på grund denna fredag, som mina professorer var precis som, oh yeah. 42 00:01:40,800 --> 00:01:42,550 Kom ihåg, du har en uppsats beror på fredagen. 43 00:01:42,550 --> 00:01:45,780 Så, jag vet ingen gillar att tänka midterms, 44 00:01:45,780 --> 00:01:50,620 men din första frågesport är den 15 oktober, vilket Oktober börjar denna vecka. 45 00:01:50,620 --> 00:01:53,290 Så kan det vara förr än vad du förväntat är allt. 46 00:01:53,290 --> 00:01:57,510 Så att du inte kastat på sängen när Jag nämner nästa veckas avsnitt som åh, 47 00:01:57,510 --> 00:02:00,560 din quiz nästa vecka, tänkte jag Jag skulle ge dig lite mer 48 00:02:00,560 --> 00:02:01,500 av en huvuden upp nu. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> Så ditt problem inställd, nummer tre. 51 00:02:04,660 --> 00:02:07,070 Hur människor har läst spec av nyfikenhet? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 OK. 54 00:02:09,199 --> 00:02:10,229 Vi fick ett par. 55 00:02:10,229 --> 00:02:12,320 Typ av minskning från förra vecka men det är OK. 56 00:02:12,320 --> 00:02:13,650 Jag vet att det var vackert ute. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 Så Break Out. 59 00:02:16,660 --> 00:02:21,010 Definitivt när du får gjort idag läsa din spec minst 60 00:02:21,010 --> 00:02:25,240 Försök som laddar ner distributions kod och kör 61 00:02:25,240 --> 00:02:27,430 liksom den första initiala sak som de ber dig att. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Eftersom vi använder distributions kod och ett bibliotek 64 00:02:32,590 --> 00:02:36,790 att vi bara har using-- --Det är bara andra gången vi har gjort detta Pset, 65 00:02:36,790 --> 00:02:38,650 galna saker kan hända med apparaten, 66 00:02:38,650 --> 00:02:41,370 och du vill finna att ute nu kontra senare. 67 00:02:41,370 --> 00:02:45,570 >> För om det är torsdag kväll eller är det Onsdag natt och av någon anledning 68 00:02:45,570 --> 00:02:48,912 apparaten bara inte vill köra med biblioteket 69 00:02:48,912 --> 00:02:50,620 eller med fördelningen kod, det betyder 70 00:02:50,620 --> 00:02:52,309 du kan inte ens börja göra kodningen. 71 00:02:52,309 --> 00:02:54,100 Eftersom du inte kan kontrollera för att se om det fungerar. 72 00:02:54,100 --> 00:02:55,975 Din kommer inte att kunna att se om det sammanställer. 73 00:02:55,975 --> 00:03:00,500 Du vill ta hand om dem som i början av veckan, när man fortfarande kan maila mig 74 00:03:00,500 --> 00:03:03,100 eller någon av de andra TF, och vi kan få dem fast. 75 00:03:03,100 --> 00:03:05,410 Eftersom dessa är frågor som kommer att stoppa dig 76 00:03:05,410 --> 00:03:07,120 från att göra några verkliga framsteg. 77 00:03:07,120 --> 00:03:10,055 Det är inte som en bugg, som du kan liksom bara hoppa över. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 Om du har problem med din apparaten eller distributionskoden, 80 00:03:13,420 --> 00:03:16,211 du verkligen vill att sett hand om förr snarare än senare. 81 00:03:16,211 --> 00:03:20,410 Så även om du inte tänker faktiskt börja koda, ladda ner distributionen 82 00:03:20,410 --> 00:03:24,040 kod, läs spec, se till att allt fungerar där. 83 00:03:24,040 --> 00:03:25,134 OK? 84 00:03:25,134 --> 00:03:27,675 Om du bara kan göra det, jag lovar ditt liv kommer att bli lättare. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 Och så du förmodligen kommer att göra det just nu rätt? 87 00:03:31,410 --> 00:03:32,100 OK. 88 00:03:32,100 --> 00:03:33,950 Så, några frågor där? 89 00:03:33,950 --> 00:03:35,850 Any logistiska saker? 90 00:03:35,850 --> 00:03:36,910 Alla är bra? 91 00:03:36,910 --> 00:03:38,270 OK. 92 00:03:38,270 --> 00:03:41,700 >> Disclaimer för de av dig i rummet och på nätet. 93 00:03:41,700 --> 00:03:45,437 Jag kommer att försöka byta mellan PowerPoint i apparaten 94 00:03:45,437 --> 00:03:47,270 eftersom vi kommer att göra lite kodning 95 00:03:47,270 --> 00:03:53,630 idag på allmän begäran av anonyma förslag enkät jag skickade ut förra veckan. 96 00:03:53,630 --> 00:03:55,480 Så kommer vi att göra lite kodning. 97 00:03:55,480 --> 00:03:57,800 Så, om ni också vill att brand upp dina apparater, 98 00:03:57,800 --> 00:04:02,910 och du bör ha fått ett e-postmeddelande från mig, med en exempelfil. 99 00:04:02,910 --> 00:04:04,310 Du får gärna göra det. 100 00:04:04,310 --> 00:04:07,340 >> Så vi kommer att prata om GDB, vilket är en debugger. 101 00:04:07,340 --> 00:04:09,970 Det kommer att hjälpa dig sorts räkna ut var 102 00:04:09,970 --> 00:04:11,860 det går fel i din kod. 103 00:04:11,860 --> 00:04:15,370 Det är egentligen bara ett sätt för dig att kliva genom din kod eftersom det händer, 104 00:04:15,370 --> 00:04:19,100 och kunna skriva ut variabler eller se vad som egentligen händer 105 00:04:19,100 --> 00:04:22,980 under huven verserna ditt program bara kör, det är som faulting, 106 00:04:22,980 --> 00:04:25,030 och du är som, ingen aning vad som just hände här. 107 00:04:25,030 --> 00:04:26,730 Jag vet inte vilken linje det misslyckades på. 108 00:04:26,730 --> 00:04:29,040 Jag vet inte var det gick fel. 109 00:04:29,040 --> 00:04:31,280 Så, GDB kommer att hjälpa dig med det. 110 00:04:31,280 --> 00:04:35,240 Dessutom, om du bestämmer dig för att fortsätter ja, och ta 61, 111 00:04:35,240 --> 00:04:38,430 Det kommer verkligen, verkligen vara din bästa vän, för jag kan berätta för dig 112 00:04:38,430 --> 00:04:40,840 eftersom jag går igenom den klassen. 113 00:04:40,840 --> 00:04:43,620 >> Vi kommer att titta på digital sök, som om ni kommer ihåg 114 00:04:43,620 --> 00:04:47,540 den stora telefonboken exempel skådespel från klass. 115 00:04:47,540 --> 00:04:50,620 Vi kommer att genomföra det, och promenader genom att lite mer, 116 00:04:50,620 --> 00:04:54,650 och sedan ska vi gå igenom fyra olika slag, som är Bubble, 117 00:04:54,650 --> 00:04:56,285 Urval, Insättning, och sammanfoga. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 Cool. 120 00:04:58,330 --> 00:05:00,390 Så, GDB som jag nämnde, är en debugger. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 Och dessa är typ av de stora saker, de stora funktioner eller kommandon 123 00:05:09,370 --> 00:05:13,240 som du använder i GDB, och jag kommer att gå dig genom en demo av den i en sekund. 124 00:05:13,240 --> 00:05:15,360 >> Så detta är inte bara kommer att bo abstrakta. 125 00:05:15,360 --> 00:05:18,000 Jag ska försöka göra det så konkret som möjligt för er. 126 00:05:18,000 --> 00:05:19,870 Så, bryta. 127 00:05:19,870 --> 00:05:22,200 Det ska antingen vara break liknande, några nummer, vilket 128 00:05:22,200 --> 00:05:26,900 representerar en rad i programmet, eller så kan du namnge en funktion. 129 00:05:26,900 --> 00:05:30,150 Så, om du säger break, det kommer att stanna vid huvud, 130 00:05:30,150 --> 00:05:32,400 och låta dig gå igenom den funktionen. 131 00:05:32,400 --> 00:05:36,350 >> Likaså om du har någon extern fungerar som Swap eller Cube, 132 00:05:36,350 --> 00:05:38,450 att vi tittade på i förra veckan. 133 00:05:38,450 --> 00:05:41,780 Om du säger att bryta en av dem, när ditt program slår det, 134 00:05:41,780 --> 00:05:44,290 Det väntar på dig att tala om vad de ska göra. 135 00:05:44,290 --> 00:05:47,860 Innan det kommer bara köra så att du kunde faktiskt steg inuti funktionen 136 00:05:47,860 --> 00:05:49,020 och se vad som händer. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 Så hoppar Nästa strax över nästa rad, går över funktioner. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Step. 141 00:05:55,560 --> 00:05:56,810 Dessa är alla lite abstrakt. 142 00:05:56,810 --> 00:06:00,530 Så, jag ska bara köra igenom dem, men du kommer att se dem i bruk i en sekund. 143 00:06:00,530 --> 00:06:01,810 >> Kliv in i en funktion. 144 00:06:01,810 --> 00:06:04,170 Så när jag sa, som med Swap, skulle det 145 00:06:04,170 --> 00:06:07,110 kan du faktiskt som om du är som fysiskt kliva inne, 146 00:06:07,110 --> 00:06:10,990 du kan bråka med dessa variabler, print reda på vad de är, se vad som händer. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 Lista kommer bokstavligen bara ut ut det omgivande kod. 149 00:06:14,830 --> 00:06:17,570 Så, om du slags glömmer var du är i ditt program, 150 00:06:17,570 --> 00:06:19,880 eller du undrar vad som händer runt omkring, 151 00:06:19,880 --> 00:06:23,790 Detta kommer bara skriva ut ett segment av vilja fem eller sex rader runt den. 152 00:06:23,790 --> 00:06:26,080 Så kan du få orienterad om var du befinner dig. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Skriv några variabel. 155 00:06:28,650 --> 00:06:34,590 Så, om du har nyckeln som i Caesar, som vi ska titta på. 156 00:06:34,590 --> 00:06:36,220 Du kan säga Print Key på någon punkt. 157 00:06:36,220 --> 00:06:40,070 Den ska berätta vad värdet är så att, kanske någonstans på vägen, 158 00:06:40,070 --> 00:06:42,070 Du har skrivit över din nyckel. 159 00:06:42,070 --> 00:06:45,495 Du kan faktiskt säga att eftersom Du kan faktiskt konstatera att värdet. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> I lokalbefolkningen, bara utskrifter ut dina lokala variabler. 162 00:06:48,780 --> 00:06:53,120 Så, när du är i en slinga, och du bara vill se ut som, oh. 163 00:06:53,120 --> 00:06:54,270 Vad är mitt jag? 164 00:06:54,270 --> 00:06:57,020 Vad är detta nyckelvärde att jag initiera här? 165 00:06:57,020 --> 00:06:58,537 Vad är budskapet i detta läge? 166 00:06:58,537 --> 00:07:00,370 Det kommer bara att skriva ut alla av dem, så att du 167 00:07:00,370 --> 00:07:04,330 behöver inte individuellt säga, Print I. ut meddelande. 168 00:07:04,330 --> 00:07:04,970 Skriv Key. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 Och sedan Display. 171 00:07:07,700 --> 00:07:10,370 Vad det gör är som ni stega igenom programmet, 172 00:07:10,370 --> 00:07:13,980 det ska bara se till att det är visar några viss variabel 173 00:07:13,980 --> 00:07:14,780 vid varje punkt. 174 00:07:14,780 --> 00:07:17,160 Så att du also-- --den är typ av en genväg där 175 00:07:17,160 --> 00:07:19,530 du behöver inte hålla på som, oh. 176 00:07:19,530 --> 00:07:23,150 Skriv Key eller Skriv I. Det bara kommer automatiskt att göra det åt dig. 177 00:07:23,150 --> 00:07:25,959 >> Så med det, vi kommer för att se hur det går. 178 00:07:25,959 --> 00:07:28,000 Jag ska försöka och switch över till min apparat. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 Se om jag kan göra det här. 181 00:07:31,271 --> 00:07:31,770 Alla. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 Vi kommer bara att spegla den. 184 00:07:42,370 --> 00:07:44,530 Det finns inget galet på min laptop ändå. 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 OK. 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 Detta måste vara den här. 189 00:08:01,054 --> 00:08:01,795 Den är så liten. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 Låt oss se om vi kan göra det här. 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> OK. 194 00:08:10,940 --> 00:08:15,305 Alice är uppenbarligen kämpar här bara en liten bit, 195 00:08:15,305 --> 00:08:17,995 men vi kommer att få det i en momento. 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 OK. 198 00:08:22,020 --> 00:08:25,900 Vi kommer bara att öka denna. 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 OK. 201 00:08:29,380 --> 00:08:31,679 Kan alla sorts ser det? 202 00:08:31,679 --> 00:08:32,470 Kanske lite? 203 00:08:32,470 --> 00:08:33,594 Jag vet att det är lite små. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 Du kan inte riktigt räkna ut hur man gör det här större. 206 00:08:37,530 --> 00:08:38,350 Om någon vet. 207 00:08:38,350 --> 00:08:40,309 Finns det någon som vet hur man gör det större? 208 00:08:40,309 --> 00:08:40,932 OK. 209 00:08:40,932 --> 00:08:42,140 Vi kommer att rulla med det. 210 00:08:42,140 --> 00:08:45,801 Spelar ingen roll ändå eftersom det är bara det är den kod som ni bör 211 00:08:45,801 --> 00:08:46,300 har. 212 00:08:46,300 --> 00:08:48,310 >> Vad är viktigare är terminalen här. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 Och vi har här Varför är det så liten? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Inställningar. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 Oh. 219 00:09:08,420 --> 00:09:09,500 Sann Ike. 220 00:09:09,500 --> 00:09:10,880 Hur är det? 221 00:09:10,880 --> 00:09:11,770 Av det. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Är det bättre för alla? 224 00:09:21,810 --> 00:09:22,525 OK ,. 225 00:09:22,525 --> 00:09:23,025 Cool. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> Du vet när du är i en CS klass tekniska svårigheter 228 00:09:28,220 --> 00:09:32,971 är typ av en del av the-- Så, låt oss klara detta. 229 00:09:32,971 --> 00:09:33,470 OK. 230 00:09:33,470 --> 00:09:38,060 Så här i avsnittet, som vi hade här. 231 00:09:38,060 --> 00:09:40,830 Caesar är en körbar fil. 232 00:09:40,830 --> 00:09:41,800 Så jag gjorde det. 233 00:09:41,800 --> 00:09:46,370 Så, är en sak att inse med GDB att det fungerar bara på körbara filer. 234 00:09:46,370 --> 00:09:48,040 Så kan du inte köra det på en dotsy. 235 00:09:48,040 --> 00:09:50,532 Du måste faktiskt göra Se till att din kod sammanställer, 236 00:09:50,532 --> 00:09:51,865 och att det faktiskt kan köras. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> Så, se till att om det inte gör det sammanställa, få den att kompilera, 239 00:09:56,186 --> 00:09:57,810 så att du kan slags kör igenom den. 240 00:09:57,810 --> 00:10:04,590 Så, för att starta GDB, allt du gör, Gloria typ GDB, och sedan bara den 241 00:10:04,590 --> 00:10:06,250 fil som du vill. 242 00:10:06,250 --> 00:10:08,240 Jag stavar alltid Caesar. 243 00:10:08,240 --> 00:10:11,730 Men du vill vara säker på eftersom det är en körbar, 244 00:10:11,730 --> 00:10:14,210 ti s dot blixt så att innebär att du kommer 245 00:10:14,210 --> 00:10:19,240 att köra CSI du kommer att köra Detta filer antingen med debugger. 246 00:10:19,240 --> 00:10:19,910 OK. 247 00:10:19,910 --> 00:10:22,885 Så, du gör det, får du denna typ av rotvälska. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 Det är bara allt om debugger. 250 00:10:25,750 --> 00:10:28,200 Du behöver verkligen inte till oroa sig för det just nu. 251 00:10:28,200 --> 00:10:31,460 Och som ni ser har vi denna öppna parens, BNP, nära parens, 252 00:10:31,460 --> 00:10:34,690 och bara typ av ser ut vår kommandorad, eller hur? 253 00:10:34,690 --> 00:10:37,010 >> Så, vad vi vill do-- --So, Det första 254 00:10:37,010 --> 00:10:39,570 är att vi vill välja en plats för att bryta den. 255 00:10:39,570 --> 00:10:42,332 Så det finns ett programfel i detta Caesar programmet 256 00:10:42,332 --> 00:10:44,290 att jag presentera, att vi kommer att ta reda på. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 Det Vad det är det tar ingången Barfoo med stora bokstäver, och av någon anledning 259 00:10:56,350 --> 00:11:01,950 Det ändrar inte A. Det lämnar bara det ensam, är allt annat rätt, 260 00:11:01,950 --> 00:11:03,980 men den andra bokstaven A är oförändrad. 261 00:11:03,980 --> 00:11:07,120 Så vi ska försöka räkna ut varför det är. 262 00:11:07,120 --> 00:11:10,440 Så, det första du normalt vill göra när du börjar på GDB 263 00:11:10,440 --> 00:11:12,010 är räkna ut var att bryta den. 264 00:11:12,010 --> 00:11:14,956 >> Så Caesar är en ganska kort program. 265 00:11:14,956 --> 00:11:16,330 Vi har bara en funktion, eller hur? 266 00:11:16,330 --> 00:11:18,520 Vad var vår funktion i Caesar? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 Det finns bara en funktion, Main rätt? 269 00:11:24,350 --> 00:11:26,490 Main är en funktion för alla dina program. 270 00:11:26,490 --> 00:11:29,230 Om du inte har Main, kanske jag vara lite orolig just nu, 271 00:11:29,230 --> 00:11:31,000 men jag hoppas att ni alla hade huvud där. 272 00:11:31,000 --> 00:11:34,150 Så, vad vi kan göra är att vi kan bara bryta Main, bara så där. 273 00:11:34,150 --> 00:11:35,190 Så står det, OK. 274 00:11:35,190 --> 00:11:37,430 Vi sätter vår brytpunkt där. 275 00:11:37,430 --> 00:11:42,870 >> Så, nu är det sak att komma ihåg Caesar tar en Kommandoradsargumentet rätt 276 00:11:42,870 --> 00:11:45,150 och vi har inte gjort det någonstans än. 277 00:11:45,150 --> 00:11:47,560 Så, vad du gör är när du faktiskt går att köra 278 00:11:47,560 --> 00:11:51,540 programmet, alla program som du är körs i GDB som behöver kommandoraden 279 00:11:51,540 --> 00:11:55,010 argument, du kommer att mata när du börjar köra den. 280 00:11:55,010 --> 00:11:59,280 Så i det här fallet, vi gör Kör med en nyckel av tre. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 Och det kommer faktiskt börja. 283 00:12:02,040 --> 00:12:08,480 >> Så, om ni ser här, vi har Om RC inte är lika med två. 284 00:12:08,480 --> 00:12:12,210 Så om ni har alla den fil som jag skickade ut upp 285 00:12:12,210 --> 00:12:15,100 ser du att det är som första raden våran funktion, eller hur? 286 00:12:15,100 --> 00:12:17,890 Det är kontroll för att se om vi har rätt antal argument. 287 00:12:17,890 --> 00:12:20,620 Så, om du undrar om RC är korrekt, 288 00:12:20,620 --> 00:12:23,250 du kan göra något precis som Print RC. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC är två, vilket är vad vi förväntat oss, eller hur? 291 00:12:28,640 --> 00:12:32,010 >> Så kan vi gå på Nästa, och fortsätter genom. 292 00:12:32,010 --> 00:12:33,200 Så, har vi några viktiga där. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 Och vi kan skriva ut vår nyckel att se till att det är korrekt. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Intressant. 297 00:12:39,500 --> 00:12:41,210 Inte riktigt vad vi förväntat oss. 298 00:12:41,210 --> 00:12:44,810 Så, för en sak att inse med GDB också är 299 00:12:44,810 --> 00:12:49,000 att det inte är förrän du faktiskt hit Därefter att den linje som du just såg 300 00:12:49,000 --> 00:12:50,720 faktiskt exekveras. 301 00:12:50,720 --> 00:12:53,870 Så i det här fallet Key har inte tilldelats ännu. 302 00:12:53,870 --> 00:12:57,050 Så, är nyckeln vissa skräp värde som du ser på botten där. 303 00:12:57,050 --> 00:13:03,680 Negativ $ 120-- --Det är en miljard och något udda saker rätt? 304 00:13:03,680 --> 00:13:05,340 Det är inte nyckeln som vi förväntade oss. 305 00:13:05,340 --> 00:13:10,720 Men om vi träffade på Nästa och sedan vi försök och tryckknapp, det är tre. 306 00:13:10,720 --> 00:13:11,710 >> Alla se det? 307 00:13:11,710 --> 00:13:13,780 Så, om du får något att du är som, vänta. 308 00:13:13,780 --> 00:13:15,540 Detta är helt fel, och jag vet inte 309 00:13:15,540 --> 00:13:20,150 Hur detta skulle hända eftersom allt jag vill ha göra är att tilldela ett nummer, en variabel, 310 00:13:20,150 --> 00:13:22,900 försöka slå Därefter försöker skriva ut det igen, och se om det fungerar. 311 00:13:22,900 --> 00:13:27,830 Eftersom det är bara att köra och faktiskt tilldela något efter dig 312 00:13:27,830 --> 00:13:29,340 hit Nästa. 313 00:13:29,340 --> 00:13:30,336 Vettigt att alla? 314 00:13:30,336 --> 00:13:30,836 Uh huh? 315 00:13:30,836 --> 00:13:33,220 >> TALARE 2: När du random siffror vad betyder det? 316 00:13:33,220 --> 00:13:34,790 >> TALARE 1: Det är bara slumpmässigt. 317 00:13:34,790 --> 00:13:35,710 Det är bara skräp. 318 00:13:35,710 --> 00:13:38,320 Det är bara något som din Datorn kommer att slumpmässigt tilldela. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 Cool. 321 00:13:40,220 --> 00:13:45,760 Så, nu kan vi gå igenom, och så Nu har vi denna klartext getString. 322 00:13:45,760 --> 00:13:48,600 Så, låt mig bara presentera vad kommer att hända när vi träffar Next här. 323 00:13:48,600 --> 00:13:51,320 Vår GDB slags försvinner, eller hur? 324 00:13:51,320 --> 00:13:55,720 Det beror getString Nu utför, eller hur? 325 00:13:55,720 --> 00:14:01,460 Så när vi såg klartext lika GetString, öppna parens och parens, 326 00:14:01,460 --> 00:14:04,380 och vi drabbades Därefter har det faktiskt utförs nu. 327 00:14:04,380 --> 00:14:06,580 Så är det att vänta på oss att mata in något. 328 00:14:06,580 --> 00:14:13,560 >> Så vi kommer att mata våra livsmedel som är vad det inte som jag sa 329 00:14:13,560 --> 00:14:18,020 och som bara säger att det är körts, att den slutna 330 00:14:18,020 --> 00:14:19,980 Fästet gör att det är att komma ut i nämnda slinga. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 Så kan vi träffa på Nästa, och nu, när jag är att du är alla bekanta från Caesar, 333 00:14:25,420 --> 00:14:27,260 Detta är, vad är denna linje kommer att göra. 334 00:14:27,260 --> 00:14:32,030 Det är för Int I är lika med 0, lika med N Strlen, vanlig text, och sedan 335 00:14:32,030 --> 00:14:33,960 Jag är mindre än n, jag, plus, plus. 336 00:14:33,960 --> 00:14:35,210 Vad är denna slinga ska göra? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Öppna ditt meddelande. 339 00:14:39,160 --> 00:14:39,770 Cool. 340 00:14:39,770 --> 00:14:41,330 Så, låt oss börja göra det. 341 00:14:41,330 --> 00:14:47,210 >> Så, bör detta tillstånd matcha, för vår första? 342 00:14:47,210 --> 00:14:52,250 Om det är ett B, det är ren text I. Vi kan få information om våra lokalbefolkningen. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 Så, är jag noll, och om sex, vilket Vi förväntar oss, och vår nyckel är tre. 345 00:14:57,970 --> 00:14:59,227 Allt som vettigt, eller hur? 346 00:14:59,227 --> 00:15:01,310 Dessa siffror är alla exakt vad de borde vara. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 Så, hum? 349 00:15:03,870 --> 00:15:05,620 TALARE 3: Jag har slumptal för gruvan. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 SPEAKER 1: Tja, kan vi check-- --Vi kan prata om det på en sekund. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 Men du bör vara att få detta. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 Så, om vi har ett kapital B för vår första, 356 00:15:20,130 --> 00:15:22,080 detta villkor ska fånga den, eller hur? 357 00:15:22,080 --> 00:15:27,120 Så om vi slog Därefter ser vi att denna Om faktiskt utför. 358 00:15:27,120 --> 00:15:29,220 För om du följer tillsammans i din kod, 359 00:15:29,220 --> 00:15:33,460 denna linje här, där klartext I skall ersättas med denna aritmetik, 360 00:15:33,460 --> 00:15:35,720 endast körs om Om tillståndet är korrekt rätt? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB kommer bara att visa dig saker som faktiskt utför. 363 00:15:40,240 --> 00:15:45,140 Så om detta Om villkoret inte uppfylldes, det bara att hoppa till nästa rad. 364 00:15:45,140 --> 00:15:46,540 OK? 365 00:15:46,540 --> 00:15:48,510 Så har vi det. 366 00:15:48,510 --> 00:15:51,171 Detta fäste betyder att det är stängd ur denna loop nu. 367 00:15:51,171 --> 00:15:52,420 Så det kommer att börja igen. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Bara så där. 370 00:15:56,280 --> 00:15:59,120 Så att vi kan få info om våra lokalbefolkningen här, 371 00:15:59,120 --> 00:16:02,575 och vi ser att vår första brev har förändrats, eller hur? 372 00:16:02,575 --> 00:16:05,150 Det är nu ett E, som det ska vara. 373 00:16:05,150 --> 00:16:07,360 Så kan vi fortsätta på. 374 00:16:07,360 --> 00:16:08,500 >> Och vi har denna kontroll. 375 00:16:08,500 --> 00:16:09,916 Och denna kontroll bör fungera, eller hur? 376 00:16:09,916 --> 00:16:12,570 Det är A. Det bör ändras tre bokstäver framåt. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 Men om du märker, vi få något annat. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 Så i detta fall här uppe, fångade den det, och så denna linje avrättades, 381 00:16:22,860 --> 00:16:28,620 som modifierats vår B. Men, i detta fallet här, 382 00:16:28,620 --> 00:16:32,860 Vi har att det bara hoppade över det, och gick till [? L SIFF. ?] 383 00:16:32,860 --> 00:16:34,660 Så något händer där. 384 00:16:34,660 --> 00:16:37,780 Vad som är att berätta är att, Vi vet att den ska hinna hit, 385 00:16:37,780 --> 00:16:39,200 men det är det inte. 386 00:16:39,200 --> 00:16:42,210 Kan någon se vad vår Problemet ligger i den linjen? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 Det är en mycket liten sak. 389 00:16:46,969 --> 00:16:48,510 Och du kan även titta på din kod. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 Det är också line-- glömma vad linjen är det i there-- men det är i [OHÖRBAR]. 392 00:16:54,940 --> 00:16:55,480 Ja? 393 00:16:55,480 --> 00:16:58,639 >> TALARE 4: Det är på mer än sida om du läser det i boken. 394 00:16:58,639 --> 00:16:59,430 TALARE 1: Exakt. 395 00:16:59,430 --> 00:17:02,620 Så, debugger kunde inte berätta du det, men det debugger 396 00:17:02,620 --> 00:17:05,880 kan få dig ner till en linje som du vet fungerar inte. 397 00:17:05,880 --> 00:17:09,319 Och ibland, när speciellt senare på terminen, när 398 00:17:09,319 --> 00:17:12,910 du arbetar med ett hundratal, en hundra några rader kod, och du 399 00:17:12,910 --> 00:17:16,190 vet inte var det är inte, Detta är ett bra sätt att göra det. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 Så hittade vi vår bugg. 402 00:17:18,989 --> 00:17:21,530 Du kan fixa det i filen, och då kan du köra den igen, 403 00:17:21,530 --> 00:17:23,029 och allt skulle fungera perfekt. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 Och det största är Detta kan tyckas, OK. 406 00:17:30,590 --> 00:17:31,090 Yeah. 407 00:17:31,090 --> 00:17:31,370 Cool. 408 00:17:31,370 --> 00:17:32,744 Du visste vad du letar efter. 409 00:17:32,744 --> 00:17:34,910 Så, du visste vad du ska göra. 410 00:17:34,910 --> 00:17:39,021 >> GDB kan vara super bra eftersom du kan skriva ut alla dessa saker som du 411 00:17:39,021 --> 00:17:39,520 skulle inte. 412 00:17:39,520 --> 00:17:41,160 Det är mycket mer användbar än printf. 413 00:17:41,160 --> 00:17:43,440 Hur många av er använder liknande printf Information 414 00:17:43,440 --> 00:17:46,200 att räkna ut var en bugg var, eller hur? 415 00:17:46,200 --> 00:17:48,450 Så med detta, behöver du inte måste hålla gå tillbaka, 416 00:17:48,450 --> 00:17:51,139 och gillar kommentera i Printf eller kommentera bort, 417 00:17:51,139 --> 00:17:52,930 och räkna ut vad du ska skriva ut. 418 00:17:52,930 --> 00:17:55,670 Detta egentligen bara ger dig möjlighet att gå igenom, skriva ut saker 419 00:17:55,670 --> 00:18:00,000 när du går igenom, så kan du observera hur de förändras i realtid, 420 00:18:00,000 --> 00:18:02,190 som ditt program körs. 421 00:18:02,190 --> 00:18:04,390 >> Och det tar lite lite tid att vänja sig. 422 00:18:04,390 --> 00:18:07,850 Jag rekommenderar starkt bara typ av att vara lite frustrerad med det 423 00:18:07,850 --> 00:18:08,930 för just nu. 424 00:18:08,930 --> 00:18:13,450 Om du tillbringar en timme över nästa vecka att lära sig använda GDB, 425 00:18:13,450 --> 00:18:16,140 du kommer att rädda dig själv så mycket tid längre fram. 426 00:18:16,140 --> 00:18:18,750 Och bokstavligt. Vi berättar detta till människor varje år, 427 00:18:18,750 --> 00:18:23,890 och jag minns när jag tog klass, var jag vill, jag kommer att bli bra. 428 00:18:23,890 --> 00:18:24,700 Nej. 429 00:18:24,700 --> 00:18:27,030 Pset 6 kom och jag var liksom, jag ska lära 430 00:18:27,030 --> 00:18:29,500 hur man använder GDB eftersom jag inte veta vad som händer här. 431 00:18:29,500 --> 00:18:32,940 >> Så om du tar dig tid så använda den på mindre program 432 00:18:32,940 --> 00:18:35,697 att du kommer att vara arbetar med, som att jobba 433 00:18:35,697 --> 00:18:37,530 igenom något liknande Visionäre, som den här. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 Eller om du vill ha extra praxis, jag är säker på Jag kunde komma på buggiga program, 436 00:18:42,850 --> 00:18:45,300 för dig att felsöka om du vill. 437 00:18:45,300 --> 00:18:49,300 >> Men om du bara tar lite tid att komma van vid det, bara leka med den, 438 00:18:49,300 --> 00:18:50,550 Det kommer verkligen att tjäna dig väl. 439 00:18:50,550 --> 00:18:52,591 Och det är verkligen en av de saker som du bara 440 00:18:52,591 --> 00:18:57,340 måste försöka, och få händerna smutsiga med, innan man verkligen förstår det. 441 00:18:57,340 --> 00:19:02,090 Jag verkligen bara förstod det en gång Jag var tvungen att felsöka saker med den, 442 00:19:02,090 --> 00:19:08,170 och det är mycket trevligare att ha en uppfattning om hur man felsöka förr snarare än senare. 443 00:19:08,170 --> 00:19:08,850 OK. 444 00:19:08,850 --> 00:19:09,625 Cool. 445 00:19:09,625 --> 00:19:12,960 Jag vet att det är ungefär som en snabbkurs i GDB, 446 00:19:12,960 --> 00:19:16,400 och jag kommer definitivt att arbeta på att få dessa för att se större nästa gång. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 Cool. 449 00:19:18,280 --> 00:19:20,390 >> Så om vi går tillbaka till vår PowerPoint. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 Kommer detta att fungera? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 AWH. 454 00:19:30,210 --> 00:19:31,101 Ja. 455 00:19:31,101 --> 00:19:31,600 OK. 456 00:19:31,600 --> 00:19:35,480 Så, om du någonsin behöver någon av dem igen, det finns i listan. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 Så Binary Search, som alla minns den stora skådespel av David 459 00:19:40,830 --> 00:19:42,259 rippning telefonböcker i hälften. 460 00:19:42,259 --> 00:19:44,050 Jag vet inte riktigt får telefonböcker längre, 461 00:19:44,050 --> 00:19:46,530 eftersom som var gör du få telefonböcker nuförtiden? 462 00:19:46,530 --> 00:19:48,220 Jag vet faktiskt inte. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 Binary Search. 465 00:19:50,590 --> 00:19:52,464 Kommer någon ihåg hur Binary Search fungerar? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Någon alls? 468 00:19:55,220 --> 00:19:56,325 Yeah? 469 00:19:56,325 --> 00:19:58,283 SPEAKER 5: Du vet när man tittar på vilken halvlek 470 00:19:58,283 --> 00:20:01,146 det skulle vara i, Baserat på detta, och bli av med den andra hälften. 471 00:20:01,146 --> 00:20:01,896 >> SPEAKER 1 Exakt. 472 00:20:01,896 --> 00:20:06,290 Så, Binary Search, är det slags en-- --Vi vill kalla det söndra och härska. 473 00:20:06,290 --> 00:20:09,170 Så, vad du ska göra är du ser i mitten, 474 00:20:09,170 --> 00:20:11,990 och du får se om det matchar vad du letar efter. 475 00:20:11,990 --> 00:20:15,420 Och om det inte gör det, då du försöker räkna ut, kommer det att vara kvar 476 00:20:15,420 --> 00:20:16,450 hälften eller den högra halvan. 477 00:20:16,450 --> 00:20:19,325 Så kan det vara om du letar på något som är alfabetiskt, 478 00:20:19,325 --> 00:20:20,720 du ser, oh. 479 00:20:20,720 --> 00:20:22,750 Har Allison kommer före M? 480 00:20:22,750 --> 00:20:23,250 Ja. 481 00:20:23,250 --> 00:20:25,030 Så, ska vi titta på den första halvleken. 482 00:20:25,030 --> 00:20:26,450 >> Eller det kan vara som med siffror. 483 00:20:26,450 --> 00:20:28,830 Allt som du kan jämföra, kan det sorteras. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 Du kan använda binär sökning på. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 Så, någon som minns detta graf eller vad det här är? 488 00:20:37,455 --> 00:20:39,520 Det är Asymptotic komplexitet. 489 00:20:39,520 --> 00:20:42,830 Så, detta diagram bara beskriver hur lång tid det 490 00:20:42,830 --> 00:20:46,230 tar dig att lösa ett problem som du ökar antalet saker 491 00:20:46,230 --> 00:20:47,090 som du använder. 492 00:20:47,090 --> 00:20:51,260 >> Så vi har N, som är linjär tid. 493 00:20:51,260 --> 00:20:54,560 Om N över två, som är något bättre, växer fortfarande supersnabb. 494 00:20:54,560 --> 00:20:58,360 Och sedan har vi Login, vilket är vad vi anser Binary Search. 495 00:20:58,360 --> 00:21:03,630 Om vi ​​märker, eftersom ditt problem blir mycket och mycket större, 496 00:21:03,630 --> 00:21:06,600 den tid det tar att lösa det egentligen inte ökar så mycket. 497 00:21:06,600 --> 00:21:09,010 Det är som jämförbara här i början. 498 00:21:09,010 --> 00:21:10,060 Du är som, OK. 499 00:21:10,060 --> 00:21:13,000 Allt här egentligen inte Oavsett vilken som vi använder, 500 00:21:13,000 --> 00:21:16,220 men du får ut till en miljon, en miljard. 501 00:21:16,220 --> 00:21:20,010 Du försöker hitta some-- --you're att försöka hitta en nål i en höstack. 502 00:21:20,010 --> 00:21:21,550 >> Jag tror att du vill ha det här problemet. 503 00:21:21,550 --> 00:21:25,850 Du vill ha denna komplexitet, inte linjär grund för allt du 504 00:21:25,850 --> 00:21:30,049 vet din gonna söka igenom varje enskild nål, ting av hö, 505 00:21:30,049 --> 00:21:31,340 försöker leta efter din nål. 506 00:21:31,340 --> 00:21:34,730 Och det är inte alltför roligt i min mening. 507 00:21:34,730 --> 00:21:35,500 Jag gillar snabbt. 508 00:21:35,500 --> 00:21:36,620 Jag gillar effektiv. 509 00:21:36,620 --> 00:21:40,450 Och så hårt arbetande studenter Er killar är, vet du arbeta smartare, 510 00:21:40,450 --> 00:21:43,010 inte hårdare typ sak, hur man kan kompensera dessa algoritmer. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> Så vi kommer att gå genom bara ett snabbt exempel. 513 00:21:47,910 --> 00:21:51,090 Jag tycker att ni borde ha en hand på Binary Search, 514 00:21:51,090 --> 00:21:54,352 men om någon är lite fuzzy, vill förstärka det, 515 00:21:54,352 --> 00:21:56,310 vi ska bara gå genom ett exempel här. 516 00:21:56,310 --> 00:21:59,490 Så vi söker om arrayen innehåller sju. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> Så, är första vi gör titta i mitten, eller hur? 519 00:22:06,010 --> 00:22:09,340 Och även du kommer att kunna koda Binär sökning på bara en sekund. 520 00:22:09,340 --> 00:22:11,310 Så det kommer att bli kul. 521 00:22:11,310 --> 00:22:13,710 Så vi tittar på mitten små arrayer 3. 522 00:22:13,710 --> 00:22:15,501 Betyder tre lika 7? 523 00:22:15,501 --> 00:22:16,000 Inte. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 Det är sex. 526 00:22:19,550 --> 00:22:21,480 Så, är det mindre än eller större än sju? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Mindre än. 529 00:22:23,960 --> 00:22:24,570 Ja. 530 00:22:24,570 --> 00:22:25,170 Fina jobb killar. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 Jag känner att jag gillar jag borde ha godis eftersom jag 533 00:22:27,360 --> 00:22:29,460 vill kasta ut den i varven. 534 00:22:29,460 --> 00:22:30,270 Det är vad jag kommer att göra nästa vecka. 535 00:22:30,270 --> 00:22:31,436 Det kommer att hålla er vassa. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> Så vi kasta bort det första halvlek, eller hur? 538 00:22:34,690 --> 00:22:35,670 det var mindre än. 539 00:22:35,670 --> 00:22:39,325 Vi vet att allt på den vänstra sidan 540 00:22:39,325 --> 00:22:41,700 kommer att vara mindre än vad vi är faktiskt ute efter. 541 00:22:41,700 --> 00:22:43,491 Så det finns ingen anledning att uppmärksamma det. 542 00:22:43,491 --> 00:22:45,120 Bara glöm det. 543 00:22:45,120 --> 00:22:48,720 Så, nu tittar vi på vår högra sida, och vi ser i mitten där borta, 544 00:22:48,720 --> 00:22:50,510 och nu är det nio. 545 00:22:50,510 --> 00:22:55,510 Så, 9 är-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Större än vad vi är söker, eller hur? 547 00:22:57,470 --> 00:22:59,860 Så vi kommer att kasta bort allt till höger. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Gillar det. 550 00:23:01,940 --> 00:23:03,700 Nu är alla vi kvar med är en. 551 00:23:03,700 --> 00:23:07,760 Så vi kolla, detta är en vad Vi är ute efter? det är. 552 00:23:07,760 --> 00:23:08,970 Vi hittade vad vi ville ha. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 Så vi är klara. 555 00:23:11,690 --> 00:23:12,550 Bilinjär Search. 556 00:23:12,550 --> 00:23:15,740 >> Och om du märker, vi hade sju ingångar där. 557 00:23:15,740 --> 00:23:24,320 Det tog oss bara som tre gånger, men om du gör som en miljard, 558 00:23:24,320 --> 00:23:28,190 ni vet hur många steg det skulle ta om vi hade fyra miljarder saker? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Any gissningar? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 Det är 32. 563 00:23:33,960 --> 00:23:37,110 32 steg för att hitta något i en fyra miljarder 564 00:23:37,110 --> 00:23:39,650 elementgrupp på grund av potenser av två. 565 00:23:39,650 --> 00:23:43,550 Så två är att 32, är att fyra miljarder. 566 00:23:43,550 --> 00:23:50,430 >> Så ganska galet hur du fortfarande inom som ett tämligen litet antal steg 567 00:23:50,430 --> 00:23:52,650 hitta något i fyra miljarder element. 568 00:23:52,650 --> 00:23:55,730 Så på denna anmärkning, vi är kommer att koda detta 569 00:23:55,730 --> 00:23:58,950 så ni kan faktiskt typ av se hur detta fungerar. 570 00:23:58,950 --> 00:24:01,520 Okej, så ni kan koda. 571 00:24:01,520 --> 00:24:04,100 Jag kommer att låta er prata lite. 572 00:24:04,100 --> 00:24:07,970 Lär känna människor runt omkring dig, vilket är vad någon ville från förra avsnittet. 573 00:24:07,970 --> 00:24:10,280 >> Så lär känna människorna omkring dig. 574 00:24:10,280 --> 00:24:11,305 Prata om lite. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 Och allt jag vill ha av dig killar är just nu bara 577 00:24:15,730 --> 00:24:17,575 försöka skapa en översikt av pseudokod. 578 00:24:17,575 --> 00:24:18,075 OK? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 Oj. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 Allt jag vill ha av er är att du är bara att fylla i denna stund fallet. 583 00:24:29,520 --> 00:24:32,170 Så jag har ställt dessa övre och undre gränser som 584 00:24:32,170 --> 00:24:35,250 representerar början och slutet av vår samling. 585 00:24:35,250 --> 00:24:40,440 Och du ska faktiskt loopa igenom och räkna ut 586 00:24:40,440 --> 00:24:42,470 vad vi gör i denna stund slinga. 587 00:24:42,470 --> 00:24:45,810 >> Så om du kan lista out-- jag har en ledtråd there-- vilka är de fall 588 00:24:45,810 --> 00:24:46,640 som vi har här? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 Så om du vill ta reda på fall kommer vi pseudokod dem 591 00:24:51,560 --> 00:24:53,350 och sedan ska vi faktiskt koda dem. 592 00:24:53,350 --> 00:24:55,330 Och det kommer att bli, jag tänker, förhoppningsvis det ska 593 00:24:55,330 --> 00:24:56,788 vara lite enklare än du förväntar dig. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 För det är inte så mycket kod, faktiskt, vilket är riktigt coolt. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Mm-hm? 598 00:25:35,018 --> 00:25:35,893 >> STUDENTEN [OHÖRBAR]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 INSTRUKTÖR: Ja. 601 00:25:37,650 --> 00:25:38,595 Det var något att hitta i mitten. 602 00:25:38,595 --> 00:25:39,552 >> STUDENT: Så vi kan använda det. 603 00:25:39,552 --> 00:25:39,770 OK. 604 00:25:39,770 --> 00:25:40,603 >> INSTRUKTÖR: Perfect. 605 00:25:40,603 --> 00:25:42,950 Så det är det första vi måste göra. 606 00:25:42,950 --> 00:25:44,330 Så hitta mitten. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Stor. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 Så har du en idé om hur vi kan faktiskt hitta mitten med koden? 611 00:25:55,010 --> 00:25:55,980 >> STUDENT: Ja. 612 00:25:55,980 --> 00:25:57,000 n över 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 INSTRUKTÖR: Så n över 2. 615 00:25:59,500 --> 00:26:05,170 Så en sak att komma ihåg är att din övre och undre gränser förändras. 616 00:26:05,170 --> 00:26:08,110 Vi håller bromsande delen av arrayen som vi är ute efter att. 617 00:26:08,110 --> 00:26:11,970 Så n över 2 fungerar bara för det första vi gör. 618 00:26:11,970 --> 00:26:17,810 Så tar övre och nedre i beaktande, Hur kan vi få det mellersta elementet? 619 00:26:17,810 --> 00:26:20,640 Eftersom vi vill i mitten mellan övre och nedre, eller hur? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Mm-hm? 622 00:26:22,494 --> 00:26:23,369 >> STUDENTEN [OHÖRBAR]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> INSTRUKTÖR: Så vi har lite mitten. 625 00:26:28,080 --> 00:26:32,730 Och det ska vara övre plus lägre än 2. 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 Grymt. 628 00:26:35,690 --> 00:26:36,570 Det gå vi. 629 00:26:36,570 --> 00:26:37,280 En rad nedåt. 630 00:26:37,280 --> 00:26:38,560 Ni är på väg. 631 00:26:38,560 --> 00:26:41,400 Så nu när vi har vår mitten, vad vill vi göra? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Bara i allmänhet. 634 00:26:45,900 --> 00:26:47,734 Du behöver inte att koda den. 635 00:26:47,734 --> 00:26:48,335 Ja. 636 00:26:48,335 --> 00:26:49,210 STUDENTEN [OHÖRBAR]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 INSTRUKTÖR: Så det är plus för att du är hitta medelvärdet mellan de två 639 00:27:10,310 --> 00:27:10,810 av dem. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 Så om du tänker på dem som slag att öka in från sidorna, 642 00:27:17,370 --> 00:27:21,640 tänk på det när du närmar dig mitten, du vill så. 643 00:27:21,640 --> 00:27:27,150 Så om du var på vardera sidan av mitten, och vi har som 5 och 7. 644 00:27:27,150 --> 00:27:31,440 När du lägger ihop dem dig få 12, delar du med 2, är 6. 645 00:27:31,440 --> 00:27:33,726 >> Ibland är det svårt att förklara varför det fungerar, 646 00:27:33,726 --> 00:27:35,600 men om du arbetar igenom ett exempel ibland, 647 00:27:35,600 --> 00:27:37,962 det hjälper dig att räkna ut om det bör vara plus eller minus. 648 00:27:37,962 --> 00:27:38,846 Ja. 649 00:27:38,846 --> 00:27:40,830 >> STUDENTEN [OHÖRBAR] exakt i mitten 650 00:27:40,830 --> 00:27:43,950 om de hade ett fall där det finns en hel del mindre antal 651 00:27:43,950 --> 00:27:45,860 och som en stort antal? 652 00:27:45,860 --> 00:27:49,750 >> INSTRUKTÖR: Så allt du behöver är i mitten av uppsättningen. 653 00:27:49,750 --> 00:27:53,010 Så om du hade ett gäng små siffror och sedan en riktigt stor mängd 654 00:27:53,010 --> 00:27:54,799 i slutet, det spelar ingen roll. 655 00:27:54,799 --> 00:27:56,840 Det avgörande är att de är sorterade, du bara 656 00:27:56,840 --> 00:27:59,339 vill titta på mitten av arrayen eftersom du fortfarande 657 00:27:59,339 --> 00:28:00,700 skivning ditt problem i hälften. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 Cool. 660 00:28:03,680 --> 00:28:06,430 Så nu när vi har mitt, vad gör vi nu? 661 00:28:06,430 --> 00:28:07,150 >> STUDENTEN Jämför. 662 00:28:07,150 --> 00:28:08,150 INSTRUKTÖR: Den jämföra. 663 00:28:08,150 --> 00:28:11,670 Så jämför mitten till value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 Cool. 666 00:28:15,160 --> 00:28:17,950 Så ni ser här uppe har vi detta värde som vi vill ha här uppe. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Kom ihåg att detta är en array. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 Så mitt hänvisar till index. 671 00:28:26,970 --> 00:28:29,785 Så vi vill göra värden på mitten. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Glöm inte om du vill att jämföra, dubbla jämlikar. 674 00:28:35,650 --> 00:28:38,250 Du gör enda lika är du bara kommer att dela ut det, 675 00:28:38,250 --> 00:28:41,090 och sedan, naturligtvis, är det kommer att vara det värde du vill ha. 676 00:28:41,090 --> 00:28:42,300 Så gör inte det. 677 00:28:42,300 --> 00:28:44,350 >> Så vi kommer att se om värdena vid mitten 678 00:28:44,350 --> 00:28:46,460 är lika med värdet vi vill ha. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Glöm inte dina hängslen. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox bör försvinna. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 Så vad gör vi i det här fallet? 685 00:28:56,200 --> 00:28:59,360 Om det är vad vi vill återvända? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 Vi försöker säga. 688 00:29:02,626 --> 00:29:03,440 >> STUDENT: Skriv ut. 689 00:29:03,440 --> 00:29:05,314 >> INSTRUKTÖR: Tja, vi vill inte skriva ut. 690 00:29:05,314 --> 00:29:08,220 Så det här är en bool här, så vi vill returnera sant eller falskt. 691 00:29:08,220 --> 00:29:12,280 Vi säger, är detta nummer en [? RRA? ?] Så om det är, 692 00:29:12,280 --> 00:29:13,788 vi tillbaka bara sant. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 Om jag kan stava sant. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> STUDENT: Varför skulle du inte returnera noll? 697 00:29:20,805 --> 00:29:22,930 INSTRUKTÖR: Så du kunde returnera noll om du ville. 698 00:29:22,930 --> 00:29:26,780 Men i detta fall eftersom vår funktion returnerar en bool, 699 00:29:26,780 --> 00:29:28,962 Vi behöver gå tillbaka antingen sant eller falskt. 700 00:29:28,962 --> 00:29:30,920 STUDENT: När du är säger boolska uttrycket, 701 00:29:30,920 --> 00:29:33,450 kan du ställa in den lika med falskt? 702 00:29:33,450 --> 00:29:39,860 Som om jag vill säga, om detta villkor inte uppfylls, som är övre lika falskt. 703 00:29:39,860 --> 00:29:42,332 Kommer det att förstå om du bara sätta falskt på andra sidan? 704 00:29:42,332 --> 00:29:43,040 INSTRUKTÖR: Ja. 705 00:29:43,040 --> 00:29:44,820 Så egentligen om du är någonsin göra något 706 00:29:44,820 --> 00:29:49,600 som är övre eller lägre, som returnerar sant eller falskt 707 00:29:49,600 --> 00:29:53,850 och det är faktiskt dålig stil till säg lika lika sant eller jämlikar 708 00:29:53,850 --> 00:29:54,840 lika falskt. 709 00:29:54,840 --> 00:30:00,210 Du vill använda detta resultat som själv som din check. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Inte vad jag ville. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 Det är vad jag ville ha. 714 00:30:09,240 --> 00:30:13,205 Så i fallet med du frågar om något liknande spara i c. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> Så om vi har int main (void) och ungefär så här. 717 00:30:25,150 --> 00:30:31,922 Och du har om är övre av lite input och du är 718 00:30:31,922 --> 00:30:33,630 frågar om du kan göra ungefär så här? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Rätt? 721 00:30:35,679 --> 00:30:37,470 STUDENT: Jag försökte att göra det [OHÖRBAR]. 722 00:30:37,470 --> 00:30:38,450 För om it's-- 723 00:30:38,450 --> 00:30:39,200 INSTRUKTÖR: Rätt. 724 00:30:39,200 --> 00:30:41,197 Så du vill att detta ska vara falska, eller hur? 725 00:30:41,197 --> 00:30:41,780 STUDENT: Ja. 726 00:30:41,780 --> 00:30:45,960 INSTRUKTÖR: Så i detta fall du vill att den ska köra om det inte är sant. 727 00:30:45,960 --> 00:30:50,510 Så cool sak du gör det finns det. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 Så minns utrop punkt förnekar saker? 730 00:30:55,650 --> 00:30:58,270 Det står [OHÖRBAR] betyder inte. 731 00:30:58,270 --> 00:31:03,590 Så om vi tittar på just denna del här, skulle du 732 00:31:03,590 --> 00:31:05,740 säger att utvärderas till falsk som du vill. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Inte falskt är sant, som innebär detta skulle exekvera. 735 00:31:09,880 --> 00:31:11,037 Är det vettigt? 736 00:31:11,037 --> 00:31:11,620 STUDENT: Ja. 737 00:31:11,620 --> 00:31:12,453 INSTRUKTÖR: Awesome. 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 OK. 740 00:31:14,300 --> 00:31:16,330 Så vi kunde bara tillbaka sant i detta fall. 741 00:31:16,330 --> 00:31:20,357 Så nu har vi två andra fall i det här fallet. 742 00:31:20,357 --> 00:31:21,565 Vilka är våra två andra fall? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Låt oss bara göra det här sättet. 745 00:31:32,900 --> 00:31:40,660 Så låt oss börja med annat Om värden på mitten 746 00:31:40,660 --> 00:31:43,230 är mindre än det värde som vi vill ha. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 Så vårt värde i mitten är mindre än det värde som vi letar efter. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> Så som bundet gör du tror att vi vill uppdatera? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Övre eller nedre? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Övre? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 Så vilken sida av matrisen kommer vi att titta på? 757 00:32:06,470 --> 00:32:07,500 >> STUDENTEN Den lägre. 758 00:32:07,500 --> 00:32:09,750 >> INSTRUKTÖR: Vi kommer vi att titta till vänster. 759 00:32:09,750 --> 00:32:11,120 Så annars om litet värde är lägre. 760 00:32:11,120 --> 00:32:14,730 Så din mittersta värdet här är mindre än vad vi vill. 761 00:32:14,730 --> 00:32:17,202 Så vi vill ta höger sida av vår array. 762 00:32:17,202 --> 00:32:18,910 Så vi kommer att uppdatera vår nedre gräns. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 Så vi ska överlåta vår lägre. 765 00:32:23,020 --> 00:32:25,221 Och vad tror du lägre borde vara? 766 00:32:25,221 --> 00:32:26,304 STUDENT: Det mittersta värdet? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 INSTRUKTÖR: Så mitt value-- 769 00:32:28,820 --> 00:32:30,136 STUDENT: Plus 1. 770 00:32:30,136 --> 00:32:31,010 INSTRUKTÖR: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Kan någon berätta för mig varför vi har det plus 1? 773 00:32:34,380 --> 00:32:35,730 >> STUDENT: [? Inget värde?] är lika med den. 774 00:32:35,730 --> 00:32:36,120 >> INSTRUKTÖR: Rätt. 775 00:32:36,120 --> 00:32:38,661 Eftersom vi redan vet att vår mittersta värdet inte är lika med 776 00:32:38,661 --> 00:32:42,750 det och vi vill utesluta det från alla efterföljande sökningar. 777 00:32:42,750 --> 00:32:46,360 Om du glömmer att plus 1, detta kommer att gilla slinga på obestämd tid. 778 00:32:46,360 --> 00:32:49,620 Och du kommer bara att fångas i en oändlig loop och då kommer du segfault 779 00:32:49,620 --> 00:32:50,370 och det går dåligt. 780 00:32:50,370 --> 00:32:54,780 Så alltid se till att du inte är inklusive det värde som du bara 781 00:32:54,780 --> 00:32:55,380 såg på. 782 00:32:55,380 --> 00:32:58,530 Så vi tar hand om det med ett plus 1. 783 00:32:58,530 --> 00:33:04,840 >> Så nu har vi vår sista villkoret som jag alltid för säkerhets skull 784 00:33:04,840 --> 00:33:12,664 Du kan kolla här, annars om värdet på mitten är större än värdet 785 00:33:12,664 --> 00:33:13,163 vi vill ha. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 Det betyder att vi vill den vänstra halvan. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 Så som man ska vi uppdatera? 790 00:33:23,260 --> 00:33:23,760 Övre. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 Och vad är det här man ska vara lika? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 USA minus en grund, Naturligtvis vill vi 795 00:33:33,690 --> 00:33:38,370 att se till att vi inte är titta på det mittersta värdet igen. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 Och så har vi det. 798 00:33:45,110 --> 00:33:45,610 Det var allt. 799 00:33:45,610 --> 00:33:46,820 Det är allt binär sökning är. 800 00:33:46,820 --> 00:33:48,190 Det är inte så illa, eller hur? 801 00:33:48,190 --> 00:33:51,590 Det är som 10 rader kod med blanktecken. 802 00:33:51,590 --> 00:33:57,510 Så mycket kraftfull, mycket användbar, kommer du att använda den i en av dina senare psets. 803 00:33:57,510 --> 00:33:59,360 Kanske inte den här, men senare. 804 00:33:59,360 --> 00:34:00,670 Så lär det. 805 00:34:00,670 --> 00:34:01,510 Älskar det. 806 00:34:01,510 --> 00:34:02,980 Den kommer att behandla dig väl. 807 00:34:02,980 --> 00:34:05,370 Så är det någon som har någon frågor om binär sökning? 808 00:34:05,370 --> 00:34:06,196 Ja. 809 00:34:06,196 --> 00:34:09,840 >> STUDENT: Spelar det någon roll om din n är jämnt eller udda? 810 00:34:09,840 --> 00:34:10,750 >> INSTRUKTÖR: Nej. 811 00:34:10,750 --> 00:34:18,150 Eftersom vi kastade den till mitten som en int, kommer det bara korta av den. 812 00:34:18,150 --> 00:34:21,600 Så det kommer att förbli ett heltal och det kommer småningom sortera igenom allt. 813 00:34:21,600 --> 00:34:23,909 Så du behöver inte oroa dig för det. 814 00:34:23,909 --> 00:34:24,580 Alla bra? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 Grymt. 817 00:34:26,850 --> 00:34:27,919 Cool. 818 00:34:27,919 --> 00:34:30,836 Så, ni fick detta. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Bildspel. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 Så när vi talade om, jag vet David nämnts komplexitetsdrifttider. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> Så i bästa fall är det bara en, som vi kallar konstant tid. 825 00:34:50,340 --> 00:34:51,909 Kan någon berätta för mig varför det kan vara? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 Vilken typ av scenario som skulle innebära? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Mm-hm. 830 00:34:58,760 --> 00:34:59,926 >> STUDENTEN [OHÖRBAR] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 INSTRUKTÖR: Så mitten är den första element som vi kommer till, eller hur? 833 00:35:03,830 --> 00:35:08,167 Så antingen en matris med en eller vad vi letar efter just 834 00:35:08,167 --> 00:35:09,750 råkar vara smack dab i mitten. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 Så det är vårt bästa fall. 837 00:35:13,380 --> 00:35:17,540 Du får till verkliga problem, förmodligen inte kommer att nå [OHÖRBAR] så ofta. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 Hur är vår värsta fall? 840 00:35:19,750 --> 00:35:21,270 Vår värsta fall är log n. 841 00:35:21,270 --> 00:35:25,360 Och det har att göra med det hela befogenheter två sak som jag talade om. 842 00:35:25,360 --> 00:35:30,930 >> Så i värsta fall skulle det innebära att vi var tvungna att hugga arrayen ner 843 00:35:30,930 --> 00:35:33,270 tills det var en del av en. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 Så vi var tvungna att hugga ner det i hälften så många gånger som vi möjligen kunde. 846 00:35:38,930 --> 00:35:41,430 Det är därför det är log n eftersom du bara hålla dividera med två. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 Så antaganden, saker du behöver veta om du någonsin 849 00:35:45,830 --> 00:35:48,050 kommer att använda en binär sökning. 850 00:35:48,050 --> 00:35:50,680 Dina element måste sorteras. 851 00:35:50,680 --> 00:35:53,890 De måste sorteras, eftersom det är det enda sättet du 852 00:35:53,890 --> 00:35:57,060 kan veta om du kan att kasta ut hälften av det. 853 00:35:57,060 --> 00:36:00,260 >> Om du hade denna rörig väska av siffror och du säger, 854 00:36:00,260 --> 00:36:05,380 OK, jag ska kolla mitt nummer och numret jag letar efter 855 00:36:05,380 --> 00:36:08,510 är mindre än så, jag ska bara godtyckligt kasta ut hälften. 856 00:36:08,510 --> 00:36:11,130 Du skulle inte veta om din nummer i den andra halvan. 857 00:36:11,130 --> 00:36:12,655 Din lista måste sorteras. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 Vad bra, kan detta vara går framåt en liten bit, 860 00:36:16,560 --> 00:36:18,360 men du måste ha direktåtkomst. 861 00:36:18,360 --> 00:36:21,940 Du måste kunna bara gå till den mellersta del. 862 00:36:21,940 --> 00:36:25,110 Om du måste korsa genom något 863 00:36:25,110 --> 00:36:28,630 eller så tar du extra steg att komma till den mellersta del, 864 00:36:28,630 --> 00:36:31,750 det är inte log n längre eftersom du lägger mer arbete i den. 865 00:36:31,750 --> 00:36:34,800 Och detta kommer att göra en liten mer meningsfullt i två veckor, 866 00:36:34,800 --> 00:36:37,950 men jag bara typ av ville förord, ge er en uppfattning om vad som är 867 00:36:37,950 --> 00:36:38,999 att komma. 868 00:36:38,999 --> 00:36:40,790 Men de är de två viktiga antaganden 869 00:36:40,790 --> 00:36:44,804 som du behöver för en binär lista. 870 00:36:44,804 --> 00:36:45,720 Se till att den är sorterade. 871 00:36:45,720 --> 00:36:47,920 Det är den stora en för ni just nu. 872 00:36:47,920 --> 00:36:52,170 Och på att vi kan gå in i resten av våra slag. 873 00:36:52,170 --> 00:36:56,444 Så fyra sorts-- bubbla, insättning, urval och sammanslagning. 874 00:36:56,444 --> 00:36:57,485 De är alla ganska häftigt. 875 00:36:57,485 --> 00:37:02,860 Om ni väljer att ta CS 124, du kommer att lära dig om alla möjliga slag. 876 00:37:02,860 --> 00:37:07,575 Och om du är en XKCD fan, det är en riktigt cool serie om 877 00:37:07,575 --> 00:37:11,530 gillar verkligen ineffektiva slag, som jag starkt rekommendera att du ska titta på. 878 00:37:11,530 --> 00:37:16,170 En av dem är som panik sortera, vilket är som, åh nej, tillbaka slumpvis rad. 879 00:37:16,170 --> 00:37:16,991 Avstängning systemet. 880 00:37:16,991 --> 00:37:17,490 Lämna. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 Så geeky humor är alltid bra. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> Så är det någon som minns snäll av som bara en allmän uppfattning 885 00:37:25,750 --> 00:37:27,810 hur bubbla sortera fungerar. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 Ni minns? 888 00:37:32,155 --> 00:37:32,755 >> STUDENT: Ja. 889 00:37:32,755 --> 00:37:33,970 >> INSTRUKTÖR: Gå för det. 890 00:37:33,970 --> 00:37:38,980 >> STUDENT: Så du går igenom och om det är större, då du byter de två. 891 00:37:38,980 --> 00:37:39,820 >> INSTRUKTÖR: Mm-hm. 892 00:37:39,820 --> 00:37:40,564 Exakt. 893 00:37:40,564 --> 00:37:41,730 Så du bara iterera igenom. 894 00:37:41,730 --> 00:37:43,050 Du kontrollerar två nummer. 895 00:37:43,050 --> 00:37:46,510 Om man tidigare är större än en efteråt, 896 00:37:46,510 --> 00:37:50,230 du bara byta dem så att i detta sätt alla de högre siffror 897 00:37:50,230 --> 00:37:54,990 bubbla upp mot slutet av listan och alla lägre siffror bubbla ner. 898 00:37:54,990 --> 00:37:59,355 >> Har han visa er den svala ljudeffekt sortering video? 899 00:37:59,355 --> 00:38:00,480 Det är ganska häftigt. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 Så när Robert sa bara, algoritmen att du bara stega genom listan, 902 00:38:05,200 --> 00:38:07,930 byta intilliggande värdena om de inte är i ordning. 903 00:38:07,930 --> 00:38:10,975 Och sedan bara fortsätta att upprepa tills du inte gör några swappar. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 Så inte illa, eller hur? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 Så vi har bara en snabb exempel här. 908 00:38:16,319 --> 00:38:18,360 Så detta kommer att sortera dem i stigande ordning. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 Så när vi går igenom den första tid, ser vi till åtta 911 00:38:23,470 --> 00:38:26,880 och sex är uppenbarligen inte i ordning, vi byta dem. 912 00:38:26,880 --> 00:38:27,985 >> Så titta på nästa. 913 00:38:27,985 --> 00:38:29,430 Åtta och fyra inte är i ordning. 914 00:38:29,430 --> 00:38:30,450 Byta dem. 915 00:38:30,450 --> 00:38:32,530 Och sedan åtta och två, byta dem. 916 00:38:32,530 --> 00:38:33,470 Det gå vi. 917 00:38:33,470 --> 00:38:39,519 Så efter din första passet, du vet att din största antalet 918 00:38:39,519 --> 00:38:41,810 kommer att vara hela vägen upptill eftersom det är bara 919 00:38:41,810 --> 00:38:44,210 kommer att vara ständigt större än allt annat 920 00:38:44,210 --> 00:38:46,810 och det är bara att bubbla upp hela vägen till slutet där. 921 00:38:46,810 --> 00:38:48,226 Är det vettigt att alla? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 Cool. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> Så då tittar vi på vår andra passet. 926 00:38:53,920 --> 00:38:54,980 Sex och fyra, switch. 927 00:38:54,980 --> 00:38:55,920 Sex och två, switch. 928 00:38:55,920 --> 00:38:58,700 Och nu har vi ett par saker i ordning. 929 00:38:58,700 --> 00:39:02,240 Så för varje pass som vi gör genom hela vår lista, 930 00:39:02,240 --> 00:39:06,320 Vi vet att som så många siffror I slutet kommer har sorterats. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 Så vi gör ett tredje pass, som är en swap. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 Och sedan på vår fjärde passera, vi har noll slots. 935 00:39:15,910 --> 00:39:18,570 Och så vi vet att vår array har sorterats. 936 00:39:18,570 --> 00:39:20,900 >> Och det är den stora sak med bubbel sort. 937 00:39:20,900 --> 00:39:23,720 Vi vet att när vi har noll swappar, att 938 00:39:23,720 --> 00:39:26,497 innebär att allt är i fullständig ordning. 939 00:39:26,497 --> 00:39:27,580 Det är typ hur vi kontrollerar. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 Så vi kommer också att koda bubbla slag som också är inte så illa. 942 00:39:36,480 --> 00:39:38,120 Ingen av dessa är så illa. 943 00:39:38,120 --> 00:39:40,210 Jag vet att de kan verka lite skrämmande. 944 00:39:40,210 --> 00:39:42,124 Jag vet när jag tog klassen, även när jag 945 00:39:42,124 --> 00:39:44,290 undervisade klassen för första gången förra året, 946 00:39:44,290 --> 00:39:46,165 Jag var ut, hur gör jag detta? 947 00:39:46,165 --> 00:39:48,540 Det är vettigt i teorin, men hur ska vi egentligen göra det? 948 00:39:48,540 --> 00:39:51,420 Det är därför jag vill också gå genom kod med er här. 949 00:39:51,420 --> 00:39:54,915 Så jag har en pseudo för er den här gången. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 Så bara ha detta i åtanke när vi håller på att övergången över. 952 00:39:58,970 --> 00:40:04,210 Så vi har några räknare som håller reda på våra swappar, 953 00:40:04,210 --> 00:40:08,370 eftersom vi måste se till att vi kollar det. 954 00:40:08,370 --> 00:40:11,830 Och vi upprepa hela uppsättningen som vi gjorde just med detta exempel. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 Om elementet innan är större än elementet efter var vi är på, 957 00:40:17,325 --> 00:40:20,760 Vi byter dem och vi öka vår räknare eftersom så snart vi byta, 958 00:40:20,760 --> 00:40:23,850 Vi vill låta vår räknare vet. 959 00:40:23,850 --> 00:40:26,247 Några frågor där? 960 00:40:26,247 --> 00:40:27,580 Något verkar roligt här. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 STUDENT: Har du ställa räkneverket noll varje gång du går genom öglan? 963 00:40:32,350 --> 00:40:34,339 Vill du inte fortsätta tillbaka till noll varje gång? 964 00:40:34,339 --> 00:40:35,505 INSTRUKTÖR: Inte nödvändigtvis. 965 00:40:35,505 --> 00:40:39,710 Så vad som händer är att vi går igenom här. 966 00:40:39,710 --> 00:40:43,830 Så gör samtidigt, kom ihåg, detta kommer att utföra en gång utan att misslyckas. 967 00:40:43,830 --> 00:40:46,480 Så det kommer att ställa in räknaren är lika med noll, 968 00:40:46,480 --> 00:40:48,070 då det kommer att iterera igenom. 969 00:40:48,070 --> 00:40:50,590 Som det itererar igenom, det kommer att uppdatera räknaren. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 Som det uppdateras räknaren, när det är gjort, när det har nått slutet av arrayen, 972 00:40:56,900 --> 00:41:00,830 Om vår lista inte har sorterats, räknaren har uppdaterats. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> Så då är det en kontroll utförs och det säger, OK, är räknaren är större än noll. 975 00:41:07,150 --> 00:41:09,290 Om det är, gör det igen. 976 00:41:09,290 --> 00:41:14,340 Du vill återställa så att när du går igenom, är räknaren är lika med noll. 977 00:41:14,340 --> 00:41:18,240 Om du går igenom en sorterad array, förändrar ingenting, 978 00:41:18,240 --> 00:41:21,355 detta misslyckas, och du returnera den sorterade listan. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Är det vettigt? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 STUDENT: Det kanske i lite. 983 00:41:26,356 --> 00:41:27,147 INSTRUKTÖR: OK. 984 00:41:27,147 --> 00:41:28,980 Om det finns någon annan fråga som kommer upp. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Ja. 987 00:41:30,680 --> 00:41:33,760 >> STUDENTEN Vad skulle funktionen vara för att byta element? 988 00:41:33,760 --> 00:41:36,900 >> INSTRUKTÖR: Så vi kan faktiskt skriva att om vi ska just nu. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 Cool. 991 00:41:38,300 --> 00:41:42,155 Så på att observera, är Alison går för att växla tillbaka till apparaten. 992 00:41:42,155 --> 00:41:43,080 Det kommer att bli kul. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 Och vi har vår trevliga bubbla sortera sak här. 995 00:41:47,390 --> 00:41:50,800 Så jag gjorde redan cykling genom uppsättningen. 996 00:41:50,800 --> 00:41:53,030 Vi har våra swappar som är lika med noll. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 Så vi vill byta intilliggande element om de är ur funktion. 999 00:41:58,440 --> 00:42:03,020 Så det första måste vi gör är iterera igenom vår samling. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> Så hur tycker du att vi kanske iterera genom vår array? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 Vi har för och jag är lika med 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 Vi vill att jag ska vara mindre än n minus 1 minus k. 1006 00:42:22,454 --> 00:42:23,870 Och jag ska förklara det på en sekund. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 Så detta är en optimering här där, minns hur jag sa efter varje pass 1009 00:42:32,830 --> 00:42:36,655 genom uppsättningen vi vet att vad som än är on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> Så efter ett pass vi vet att detta är sorterad. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 Efter två passager vi vet att allt detta är sorterad. 1014 00:42:50,060 --> 00:42:52,750 Efter tre passager vi vet som är sorterade. 1015 00:42:52,750 --> 00:42:55,620 Så långt jag iteration genom uppsättningen här, 1016 00:42:55,620 --> 00:43:01,090 är det att se till att bara gå genom vad vi vet är osorterat. 1017 00:43:01,090 --> 00:43:01,644 OK? 1018 00:43:01,644 --> 00:43:02,810 Det är bara en optimering. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 Du kan skriva det naivt bara iterera igenom allt, 1021 00:43:08,210 --> 00:43:09,970 Det skulle bara ta längre tid. 1022 00:43:09,970 --> 00:43:12,470 Med denna fyra slinga är det bara en trevlig optimering 1023 00:43:12,470 --> 00:43:18,460 eftersom vi vet att efter varje helt iteration genom uppsättningen här, 1024 00:43:18,460 --> 00:43:24,050 som varje hel slinga här, vi vet att en av dessa komponenter 1025 00:43:24,050 --> 00:43:25,760 kommer att sorteras i slutet. 1026 00:43:25,760 --> 00:43:28,294 >> Så vi behöver inte oroa dig för dem. 1027 00:43:28,294 --> 00:43:29,710 Är det vettigt att alla? 1028 00:43:29,710 --> 00:43:30,950 Den coola lilla trick? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 Så i så fall, om vi iterera igenom, 1031 00:43:37,270 --> 00:43:50,590 vi vet att vi vill kontrollera om array n och n plus 1 är i ordning. 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 OK. 1034 00:43:53,559 --> 00:43:54,600 Så här är pseudokod. 1035 00:43:54,600 --> 00:43:57,540 Vi vill kolla om array n och n plus 1 är i ordning. 1036 00:43:57,540 --> 00:43:59,520 Så vad kan vi ha det? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 Det kommer att bli lite villkor. 1039 00:44:03,120 --> 00:44:04,220 Det kommer att bli en om. 1040 00:44:04,220 --> 00:44:07,066 >> STUDENT: Om matris n är mindre än array n plus 1. 1041 00:44:07,066 --> 00:44:07,816 INSTRUKTÖR: Mm-hm. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 Tja, mindre än eller större än. 1044 00:44:10,699 --> 00:44:11,615 STUDENT: Större än. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Då vill vi att byta dem. 1047 00:44:17,620 --> 00:44:18,570 Exakt. 1048 00:44:18,570 --> 00:44:23,570 Så nu får vi in ​​vad är det mekanism för att byta dem? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 Så vi gick igenom det här en kort stund, en typ av swap-funktion förra veckan. 1051 00:44:28,137 --> 00:44:29,595 Finns det någon som minns hur det fungerade? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 Så vi kan inte bara överlåta dem, eller hur? 1054 00:44:34,950 --> 00:44:36,640 Eftersom en av dem kommer att gå vilse. 1055 00:44:36,640 --> 00:44:41,696 Om vi ​​sagt A är lika med B och sedan B är lika med A, alla en plötslig båda av dem 1056 00:44:41,696 --> 00:44:43,150 är bara lika med B. 1057 00:44:43,150 --> 00:44:45,720 >> Så vad vi har att göra är att vi har en temporär variabel som är 1058 00:44:45,720 --> 00:44:49,055 kommer att hålla en av våra stund vi är i färd med att byta. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 Så vad vi har är att vi ska ha lite int temp är lika att-- du kan tilldela den 1061 00:44:56,464 --> 00:44:59,130 till vilken du vill, bara se till att du hålla reda på det-- 1062 00:44:59,130 --> 00:45:01,840 så i det här fallet, kommer jag att tilldela den till array n plus 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 Så det kommer att innehåla värde i det andra blocket 1065 00:45:07,674 --> 00:45:08,590 att vi tittar på. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> Och då vi kan göra är att vi kan gå framåt och tilldela array n plus 1, 1068 00:45:13,240 --> 00:45:14,990 eftersom vi vet att vi har detta värde lagras. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 Detta är också en av de stora saker-- Jag vet inte om någon av er 1071 00:45:19,270 --> 00:45:23,780 hade frågor där om du byter två kodrader plötsligt saker fungerade. 1072 00:45:23,780 --> 00:45:25,880 Order är mycket viktigt i CS. 1073 00:45:25,880 --> 00:45:29,450 Så se till att du diagram saker ut om det är möjligt 1074 00:45:29,450 --> 00:45:31,230 om vad som faktiskt händer. 1075 00:45:31,230 --> 00:45:34,256 Så nu ska vi överlåta array n plus 1, 1076 00:45:34,256 --> 00:45:36,005 eftersom vi vet att vi har detta värde lagras. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> Och vi kan tilldela till array n eller i detta fall array i. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 För många variabler. 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 OK. 1083 00:45:55,470 --> 00:46:01,500 Så nu har vi tilldelas array i plus 1 till lika vad som finns i arrayen i. 1084 00:46:01,500 --> 00:46:08,240 Och nu kan vi gå tillbaka och tilldela array i vad? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Någon? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> STUDENTEN 10. 1089 00:46:14,010 --> 00:46:14,680 >> INSTRUKTÖR: 10. 1090 00:46:14,680 --> 00:46:15,180 Exakt. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 Och en sista sak. 1093 00:46:18,640 --> 00:46:21,840 Om vi ​​har bytt det nu, Vad behöver vi göra? 1094 00:46:21,840 --> 00:46:23,740 Vad är en sak det kommer att berätta 1095 00:46:23,740 --> 00:46:27,542 om vi någonsin avsluta det här programmet? 1096 00:46:27,542 --> 00:46:29,250 Vad säger oss att vi har en sorterad lista? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 Om vi ​​inte utför några swappar, eller hur? 1099 00:46:33,750 --> 00:46:36,900 Om swappar är lika med noll vid slutet av denna. 1100 00:46:36,900 --> 00:46:42,975 Så varje gång du gör en swap, som vi just gjorde här, vi vill uppdatera swappar. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 Och jag vet att det fanns en fråga tidigare om kan du 1103 00:46:47,210 --> 00:46:49,689 använda noll eller ett i stället av sant eller falskt. 1104 00:46:49,689 --> 00:46:50,980 Och det är vad det gör här. 1105 00:46:50,980 --> 00:46:52,750 Så detta säger om inte swappar. 1106 00:46:52,750 --> 00:47:01,310 Så om swappar är noll, som är-- jag alltid få mina sanningar och mina falses blandas ihop. 1107 00:47:01,310 --> 00:47:03,960 Vi vill att vi ska utvärdera till true, och det är inte. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 Så om det är noll, då är det falskt. 1110 00:47:09,630 --> 00:47:12,560 Om du förnekar det med en [? bang?] blir det sant. 1111 00:47:12,560 --> 00:47:13,975 Så då denna linje körs. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Sanningar och falska och nollor och ettor blir galen. 1114 00:47:17,370 --> 00:47:20,690 Bara om du sakta gå igenom det kommer det att vara meningsfullt. 1115 00:47:20,690 --> 00:47:23,320 Men det är vad denna lilla bit kod här gör. 1116 00:47:23,320 --> 00:47:26,490 Så detta kontrollerar för att se Vi har gjort några swappar. 1117 00:47:26,490 --> 00:47:30,054 Så om det är något annat än noll, det kommer att vara falsk 1118 00:47:30,054 --> 00:47:31,970 och det hela är kommer att exekvera på nytt. 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 Cool? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> STUDENTEN Vad gör break göra? 1123 00:47:36,000 --> 00:47:38,990 >> INSTRUKTÖR: Bryt bara bryter dig ut ur loopen. 1124 00:47:38,990 --> 00:47:41,570 Så i detta fall att det skulle precis som avslutar programmet 1125 00:47:41,570 --> 00:47:43,828 och du skulle bara har din sorterad lista. 1126 00:47:43,828 --> 00:47:44,536 STUDENT: Amazing. 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 INSTRUKTÖR: Jag är ledsen? 1129 00:47:49,010 --> 00:47:52,110 STUDENT: Eftersom vi tidigare används skrivit 1 över skriven noll 1130 00:47:52,110 --> 00:47:54,170 att presentera att om det kommer att fungera eller inte. 1131 00:47:54,170 --> 00:47:54,878 >> INSTRUKTÖR: Ja. 1132 00:47:54,878 --> 00:47:56,410 Så du kan returnera noll eller 1. 1133 00:47:56,410 --> 00:47:58,950 I det här fallet, eftersom vi är faktiskt inte gör något med funktionen, 1134 00:47:58,950 --> 00:48:00,150 Vi vill bara att det ska gå sönder. 1135 00:48:00,150 --> 00:48:02,680 Vi vet inte riktigt bryr sig om det. 1136 00:48:02,680 --> 00:48:06,960 Brake är också bra om den används för att bryta ut 1137 00:48:06,960 --> 00:48:10,710 av fyra slingor eller villkor som du inte vill behålla utföra. 1138 00:48:10,710 --> 00:48:12,110 Det tar bara dig ur dem. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 Det är lite av en nyans sak. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 Det känns som det finns en hel del för hand vinka, 1143 00:48:18,445 --> 00:48:19,740 som du kommer att lära dig mer om detta snart. 1144 00:48:19,740 --> 00:48:20,955 >> Men du kommer att lära dig mer om detta snart. 1145 00:48:20,955 --> 00:48:21,500 Jag lovar. 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 OK. 1148 00:48:23,170 --> 00:48:24,840 Så gör alla får bubbla sortera? 1149 00:48:24,840 --> 00:48:25,550 Inte så illa. 1150 00:48:25,550 --> 00:48:31,910 Iterera igenom, swap saker med en temp variabel, och vi är allt klart där? 1151 00:48:31,910 --> 00:48:32,960 Cool. 1152 00:48:32,960 --> 00:48:34,080 Grymt. 1153 00:48:34,080 --> 00:48:34,807 OK. 1154 00:48:34,807 --> 00:48:35,765 Tillbaka till PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Eventuella frågor i allmänhet om dessa så långt? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 Cool. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Mm-hm. 1161 00:48:43,695 --> 00:48:45,279 >> STUDENTEN [OHÖRBAR] int main oftast. 1162 00:48:45,279 --> 00:48:46,695 Måste man ha det för detta? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> INSTRUKTÖR: Så vi bara ute precis vid den faktiska sorteringsalgoritm. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 Om du hade det inom som ett större program, 1167 00:48:56,350 --> 00:48:57,891 du skulle ha en int main någonstans. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 Beroende på var du använda denna algoritm, 1170 00:49:02,880 --> 00:49:05,860 Det skulle avgöra vad som är som returneras av den. 1171 00:49:05,860 --> 00:49:09,960 Men för vårt fall, vi är strikt titta på hur fungerar det egentligen 1172 00:49:09,960 --> 00:49:11,300 iterera genom en matris. 1173 00:49:11,300 --> 00:49:12,570 Så vi behöver inte oroa dig för det. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> Så vi pratade om bästa fall och värsta tänkbara scenarier för binär sökning. 1176 00:49:19,830 --> 00:49:22,470 Så det är också viktigt att göra att för var och en av våra slag. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 Så vad tror du är det värsta fall runtime bubbla slag? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 Ni minns? 1181 00:49:30,700 --> 00:49:31,784 >> STUDENT: N minus 1. 1182 00:49:31,784 --> 00:49:32,700 INSTRUKTÖR: N minus 1. 1183 00:49:32,700 --> 00:49:35,070 Så det innebär att det finns n minus 1 jämförelser. 1184 00:49:35,070 --> 00:49:40,060 Så en sak att inse är att på den första iterationen, 1185 00:49:40,060 --> 00:49:43,360 vi går igenom, vi jämför dessa two-- så det är 1. 1186 00:49:43,360 --> 00:49:46,685 Dessa två, tre, fyra. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 Så efter en iteration vi redan har fyra jämförelser. 1189 00:49:55,050 --> 00:49:58,230 När jag pratar om körtid och n. 1190 00:49:58,230 --> 00:50:04,680 N representerar antalet jämförelser som en funktion av hur många element 1191 00:50:04,680 --> 00:50:05,570 vi har. 1192 00:50:05,570 --> 00:50:06,430 OK? 1193 00:50:06,430 --> 00:50:08,860 >> Så vi går igenom, vi har fyra. 1194 00:50:08,860 --> 00:50:11,780 Nästa gång du vet gör vi inte måste ta hand om detta. 1195 00:50:11,780 --> 00:50:15,140 Vi jämför dessa två, dessa två, dessa två, 1196 00:50:15,140 --> 00:50:20,050 och om vi inte hade att optimering med fyra slinga som jag skrev, 1197 00:50:20,050 --> 00:50:22,750 du skulle jämföra in här ändå. 1198 00:50:22,750 --> 00:50:26,170 Så du skulle behöva köra igenom arrayen 1199 00:50:26,170 --> 00:50:34,380 och göra N jämförelser n gånger, eftersom varje gång vi 1200 00:50:34,380 --> 00:50:36,670 köra igenom det vi sorterar en sak. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> Och varje gång vi kör igenom arrayen, vi gör n jämförelser. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 Så vår runtime för detta är faktiskt n kvadrat, vilket 1205 00:50:46,330 --> 00:50:48,400 är mycket värre i vår log slutet eftersom det 1206 00:50:48,400 --> 00:50:51,965 innebär om vi hade fyra miljarder element, det 1207 00:50:51,965 --> 00:50:55,260 kommer att ta oss fyra miljarder kvadrat i stället för 32. 1208 00:50:55,260 --> 00:51:01,240 Så inte den bästa runtime, men för vissa saker, 1209 00:51:01,240 --> 00:51:04,610 du vet, om du är inom ett visst antal element 1210 00:51:04,610 --> 00:51:06,540 bubbla slag kan vara bra att använda. 1211 00:51:06,540 --> 00:51:07,530 >> OK. 1212 00:51:07,530 --> 00:51:12,290 Så nu vad är det bästa fallet runtime? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 STUDENTEN Zero? 1215 00:51:14,940 --> 00:51:16,420 Eller 1? 1216 00:51:16,420 --> 00:51:18,140 >> INSTRUKTÖR: So 1 skulle vara en jämförelse. 1217 00:51:18,140 --> 00:51:19,114 Höger. 1218 00:51:19,114 --> 00:51:20,002 >> STUDENT: N minus 1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> INSTRUKTÖR: Så, ja. 1221 00:51:22,320 --> 00:51:22,990 Så n minus 1. 1222 00:51:22,990 --> 00:51:26,510 När du har ett koncept som n minus 1, tenderar vi att bara släppa det 1223 00:51:26,510 --> 00:51:31,680 och vi bara säga n för att du har att jämföra var och en av these-- varje par. 1224 00:51:31,680 --> 00:51:36,470 Så det skulle vara n minus 1, som vi Vi skulle bara vilja säga är ungefär n. 1225 00:51:36,470 --> 00:51:39,280 När du arbetar med runtime, allt är i approximerar. 1226 00:51:39,280 --> 00:51:43,860 Så länge exponenten är korrekt, du är ganska bra. 1227 00:51:43,860 --> 00:51:45,700 >> Det är hur vi hanterar den. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 Så att det bästa fallet är n, vilken innebär att listan redan är sorterad, 1230 00:51:51,780 --> 00:51:54,320 och allt vi gör drivs via och kontrollera att den är sorterade. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 Cool. 1233 00:51:56,855 --> 00:51:57,355 Okej. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 Så som ni ser här, vi bara har några fler grafer. 1236 00:52:01,920 --> 00:52:02,660 Så n kvadrat. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Fun. 1239 00:52:05,120 --> 00:52:09,730 Mycket värre än n som vi ser, och mycket, mycket värre än log 2n. 1240 00:52:09,730 --> 00:52:12,060 Och då får du också in i logg stockar. 1241 00:52:12,060 --> 00:52:18,020 Och du tar 124, får du in som log stjärnan, som är som galen. 1242 00:52:18,020 --> 00:52:20,172 Så om du är intresserad, lookup log stjärna. 1243 00:52:20,172 --> 00:52:20,880 Det är ganska kul. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 Så vi har denna stora diagrammet. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Bara en huvuden upp, detta är en underbart diagrammet att ha 1248 00:52:28,720 --> 00:52:31,350 för din halva tiden eftersom vi lång tid att ställa dig dessa tunnar. 1249 00:52:31,350 --> 00:52:36,090 Så bara en huvuden upp, har detta på din halva tiden på din fina fusklapp 1250 00:52:36,090 --> 00:52:36,616 där. 1251 00:52:36,616 --> 00:52:37,990 Så vi bara tittade på bubblan slag. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 I värsta fall, n kvadrat, bästa fall, n. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 Och vi kommer att titta på de andra. 1256 00:52:44,950 --> 00:52:47,940 >> Och som ni kan se, den enda en som verkligen gör bra 1257 00:52:47,940 --> 00:52:50,910 är merge sort, som vi kommer att få in på varför. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 Så vi kommer att gå till nästa här-- val slag. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Finns det någon som minns hur urval sorterar fungerat? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Gå för det. 1264 00:53:05,700 --> 00:53:08,210 >> STUDENT: I ​​grund och botten gå igenom en beställning och skapa en ny lista. 1265 00:53:08,210 --> 00:53:11,001 Och precis som du sätter element i, lägg dem på rätt plats 1266 00:53:11,001 --> 00:53:11,750 i den nya listan. 1267 00:53:11,750 --> 00:53:14,040 >> INSTRUKTÖR: Så det låter mer som inför slag. 1268 00:53:14,040 --> 00:53:15,040 Men du är riktigt nära. 1269 00:53:15,040 --> 00:53:15,915 De är mycket lika. 1270 00:53:15,915 --> 00:53:17,440 Även jag får dem blandas ihop ibland. 1271 00:53:17,440 --> 00:53:18,981 Innan detta avsnitt jag var som, vänta. 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 OK. 1274 00:53:20,630 --> 00:53:24,141 Så vad du vill do är urval sortera, 1275 00:53:24,141 --> 00:53:25,890 det sätt du kan tänka dig om det och hur 1276 00:53:25,890 --> 00:53:30,140 Jag ser till att jag försöker att inte få dem blandas ihop, är det går igenom 1277 00:53:30,140 --> 00:53:33,280 och väljer den minsta antalet och det 1278 00:53:33,280 --> 00:53:36,070 sätter det i början av din lista. 1279 00:53:36,070 --> 00:53:37,730 Det byter det med den första platsen. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 De har faktiskt en förebild för mig. 1282 00:53:45,370 --> 00:53:46,540 Grymt. 1283 00:53:46,540 --> 00:53:50,130 Så bara ett sätt att tänka på det-- urval sortera, välja det minsta värdet. 1284 00:53:50,130 --> 00:53:51,940 Och vi kommer att köra igenom ett exempel 1285 00:53:51,940 --> 00:53:55,320 som jag tror kommer att hjälpa eftersom Jag tror visuella alltid hjälpa. 1286 00:53:55,320 --> 00:53:58,510 Så vi börjar med något som är helt osorterat. 1287 00:53:58,510 --> 00:54:00,730 Rött är osorterade, gröna kommer att sorteras. 1288 00:54:00,730 --> 00:54:02,190 Det kommer allt vettigt i en sekund. 1289 00:54:02,190 --> 00:54:08,950 >> Så vi går igenom och vi iterera från början till slut. 1290 00:54:08,950 --> 00:54:12,320 Och vi säger, OK, 2 är vår minsta antalet. 1291 00:54:12,320 --> 00:54:15,680 Så vi kommer att ta två och vi kommer att flytta den till framsidan av vår array 1292 00:54:15,680 --> 00:54:17,734 eftersom det är den minsta antalet har vi. 1293 00:54:17,734 --> 00:54:19,150 Så det är vad det gör här. 1294 00:54:19,150 --> 00:54:20,820 Det är bara att byta dessa två. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 Så nu har vi en sortering del och en osorterad del. 1297 00:54:25,450 --> 00:54:27,810 Och vad som är bra att komma ihåg om urval sorterar 1298 00:54:27,810 --> 00:54:30,690 är vi bara välja från osorterade delen. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> Den sorterade delen du bara lämna ensam. 1301 00:54:34,527 --> 00:54:35,660 Mm-hm? 1302 00:54:35,660 --> 00:54:38,452 >> STUDENT: Hur fungerar det vet vad som är de minsta utan att jämföra 1303 00:54:38,452 --> 00:54:39,868 till varje annat värde i arrayen. 1304 00:54:39,868 --> 00:54:41,250 INSTRUKTÖR: Det gör det jämföra det. 1305 00:54:41,250 --> 00:54:42,041 Vi gillar hoppade över det. 1306 00:54:42,041 --> 00:54:43,850 Detta är bara allmänt övergripande. 1307 00:54:43,850 --> 00:54:44,831 Yeah. 1308 00:54:44,831 --> 00:54:47,205 När vi skriver koden är jag säker på att du kommer att bli mer nöjda. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 Men du lagrar denna första elementet som den minsta. 1311 00:54:53,030 --> 00:54:56,110 Du jämföra och du säger, OK, det är mindre? 1312 00:54:56,110 --> 00:54:56,660 Ja. 1313 00:54:56,660 --> 00:54:57,460 Håll det. 1314 00:54:57,460 --> 00:54:58,640 Här är det mindre? 1315 00:54:58,640 --> 00:54:59,660 Nej? 1316 00:54:59,660 --> 00:55:02,510 >> Detta är din minsta, tilldela den till ditt värde. 1317 00:55:02,510 --> 00:55:06,340 Och du kommer att bli mycket lyckligare När vi går igenom koden. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 Så vi går igenom, vi byta den, så då vi ser på detta osorterade delen. 1320 00:55:13,970 --> 00:55:15,810 Så vi kommer att välja tre. 1321 00:55:15,810 --> 00:55:18,890 Vi kommer att sätta upp det på vid I slutet av vår sorterade delen. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 Och vi ska bara fortsätta göra att göra det, och göra det. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 Så det här är vår typ av pseudokod här. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 Vi ska koda upp det här på en sekund. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 Men bara något att gå igenom på en hög nivå. 1330 00:55:37,270 --> 00:55:40,275 Du kommer att gå från i är lika med 0 till n minus 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 Det är en annan optimering. 1333 00:55:43,530 --> 00:55:45,020 Oroa dig inte för mycket om det. 1334 00:55:45,020 --> 00:55:46,620 Så som ni sa. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 Som Jakob sa, hur gör vi hålla reda på vad vår minsta är? 1337 00:55:54,406 --> 00:55:55,030 Hur vet vi det? 1338 00:55:55,030 --> 00:55:57,060 Vi måste jämföra allt i vår lista. 1339 00:55:57,060 --> 00:55:59,600 >> Så minimum är lika i. 1340 00:55:59,600 --> 00:56:03,870 Det är bara att säga i det här fallet index för vår minsta värde. 1341 00:56:03,870 --> 00:56:07,660 Så då det kommer att iterera igenom och det går från j är lika med i plus 1. 1342 00:56:07,660 --> 00:56:11,420 Så vi vet redan att det är vår första elementet. 1343 00:56:11,420 --> 00:56:13,240 Vi behöver inte jämföra det med sig själv. 1344 00:56:13,240 --> 00:56:16,970 Så vi börjar jämföra det till nästa en som är varför det är i plus 1 till n 1345 00:56:16,970 --> 00:56:20,110 minus 1, vilket är den slutet av arrayen där. 1346 00:56:20,110 --> 00:56:25,090 Och vi sa att om array på j är mindre än array min, 1347 00:56:25,090 --> 00:56:29,200 sedan omtilldela vi där våra lägsta index är. 1348 00:56:29,200 --> 00:56:37,470 >> Och om min är inte lika med I, såsom i där vi var tillbaka hit. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 Så som när vi först gjorde detta. 1351 00:56:41,790 --> 00:56:49,310 I detta fall skulle det börja på noll, skulle det hamna två. 1352 00:56:49,310 --> 00:56:53,010 Så min skulle inte lika i till slut. 1353 00:56:53,010 --> 00:56:55,720 Det låter oss veta att vi behöver byta dem. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 Jag känner mig som ett konkret exempel kommer att bidra mycket mer än detta. 1356 00:57:00,470 --> 00:57:04,970 Så jag ska koda upp detta med er just nu och jag tror det blir bättre. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Sorterar tenderar att arbeta på det sättet i det Det är ofta bättre bara för att se dem. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 Så vad vi vill göra är att vi först vill ha den minsta 1361 00:57:17,280 --> 00:57:19,890 element i sin position i arrayen. 1362 00:57:19,890 --> 00:57:21,280 Exakt vad Jakob sade. 1363 00:57:21,280 --> 00:57:23,090 Du måste lagra den på något sätt. 1364 00:57:23,090 --> 00:57:25,900 Så vi kommer att börja här iteration över arrayen. 1365 00:57:25,900 --> 00:57:28,970 Vi kommer att säga att det är vår första bara för att börja med. 1366 00:57:28,970 --> 00:57:38,308 Så vi kommer att ha int minsta är lika med array på i. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> Så en sak att lägga märke till, varje tid denna slinga exekverar, 1369 00:57:45,050 --> 00:57:48,550 Vi börjar ett steg längre fram. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 När vi börjar vi tittar på detta. 1372 00:57:57,440 --> 00:58:00,840 Nästa gång vi iterera igenom, vi börjar på den här 1373 00:58:00,840 --> 00:58:02,680 och tilldela det vår minsta värde. 1374 00:58:02,680 --> 00:58:10,450 Så det är mycket lik bubbla sortera där vi vet att efter ett pass, 1375 00:58:10,450 --> 00:58:11,700 denna sista elementet sorteras. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 Med valet sortera, Det är precis tvärtom. 1378 00:58:15,120 --> 00:58:18,950 >> Vid varje pass, vet vi att den första sorteras. 1379 00:58:18,950 --> 00:58:21,360 Efter det andra passet, det andra kommer att sorteras. 1380 00:58:21,360 --> 00:58:26,470 Och som du såg med glid exemplen, våra sorterade delen blir bara växer. 1381 00:58:26,470 --> 00:58:34,020 Så genom att sätta vår minsta till arrayer i, allt det gör 1382 00:58:34,020 --> 00:58:37,340 är bromsande vad vi tittar på så 1383 00:58:37,340 --> 00:58:40,164 för att minimera antalet jämförelser vi gör. 1384 00:58:40,164 --> 00:58:41,770 Betyder det vettigt för alla? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Vill du att jag ska gå igenom det åter långsammare eller i olika ord? 1387 00:58:46,380 --> 00:58:47,180 Jag är glad att. 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 OK. 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> Så vi förvarar värde vid denna punkt, 1392 00:58:55,540 --> 00:58:57,840 men vi vill också lagra index. 1393 00:58:57,840 --> 00:59:01,010 Så vi kommer att lagra positionen för det minsta 1394 00:59:01,010 --> 00:59:02,770 en, som just kommer att vara i. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 Så nu Jacob är uppfyllt. 1397 00:59:05,440 --> 00:59:06,870 Vi har saker som lagras. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 Och nu måste vi titta igenom den osorterade del av matrisen. 1400 00:59:11,870 --> 00:59:18,170 Så i detta fall skulle vara vår osorterat. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 Detta är i. 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 OK. 1405 00:59:26,210 --> 00:59:30,040 >> Så vad vi ska göra kommer att vara för en slinga. 1406 00:59:30,040 --> 00:59:32,066 Närhelst du behöver iterera genom en matris, 1407 00:59:32,066 --> 00:59:33,440 ditt sinne kunde gå till för en slinga. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 Så för vissa int k equals-- vad vi tänker 1410 00:59:38,090 --> 00:59:39,700 k kommer att vara lika till att börja med? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 Detta är vad vi satt som vår minsta värde och vi vill jämföra den. 1413 00:59:44,766 --> 00:59:47,090 Vad vill vi jämföra det med? 1414 00:59:47,090 --> 00:59:48,730 Det kommer att vara så här nästa, eller hur? 1415 00:59:48,730 --> 00:59:53,200 Så vi vill k initieras till i plus 1 för att starta. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> Och vi vill ha k vi i detta fall redan har storlek lagrat upp här, 1418 01:00:02,800 --> 01:00:03,930 så vi kan bara använda storlek. 1419 01:00:03,930 --> 01:00:06,240 Storlek att vara storleken på matrisen. 1420 01:00:06,240 --> 01:00:09,620 Och vi bara vill uppdatera k med ett varje gång. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 Cool. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 Så nu måste vi hitta det minsta elementet här. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 Så om vi iterera igenom, vi vill säga, om array på k 1427 01:00:31,380 --> 01:00:37,080 är mindre än vår minsta value-- det är där vi faktiskt 1428 01:00:37,080 --> 01:00:42,950 hålla reda på vad som är den minsta här-- 1429 01:00:42,950 --> 01:00:47,740 då vill vi att omplacera vad vår minsta värdet är. 1430 01:00:47,740 --> 01:00:50,645 >> Detta innebär att, åh, vi är iterera igenom här. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Oavsett värdet här är inte vårt minsta sak. 1433 01:00:53,740 --> 01:00:54,448 Vi vill inte ha det. 1434 01:00:54,448 --> 01:00:56,100 Vi vill dela ut det. 1435 01:00:56,100 --> 01:01:02,050 Så om vi omplacera den, vad gör du tror kan vara i denna kod här? 1436 01:01:02,050 --> 01:01:04,160 Vi vill tilldela minsta och placering. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 Så vad är minsta nu? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 STUDENTEN Array k. 1441 01:01:09,130 --> 01:01:09,963 INSTRUKTÖR: Array k. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 Och vad är läget nu? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 Vad är de index i vår minsta värde? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 Det är bara k. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 Så array k, k, matchar de upp. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 Så vi ville att omplacera det. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 Och sedan när vi hittat vår minsta, så vid slutet av denna för slingan 1454 01:01:39,950 --> 01:01:45,100 här har vi hittat vad vår minsta värdet är, så vi bara byta den. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 I detta fall, liksom säga vår minsta värdet är här ute. 1457 01:01:50,816 --> 01:01:51,940 Detta är vår minsta värde. 1458 01:01:51,940 --> 01:01:57,690 >> Vi vill bara byta den här, som är vad det swap-funktion i botten 1459 01:01:57,690 --> 01:02:01,270 gjorde, som vi just skrev upp ihop ett par minuter sedan. 1460 01:02:01,270 --> 01:02:02,775 Så det ska se bekanta. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 Och då kommer det bara iterera igenom tills den når hela vägen 1463 01:02:08,030 --> 01:02:13,100 till slutet, vilket innebär att du har noll element som osorterade 1464 01:02:13,100 --> 01:02:14,800 och allt annat har sorterats. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Vettigt? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 Lite mer konkret? 1469 01:02:19,280 --> 01:02:19,990 Koden hjälp? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> STUDENT: För en storlek, du aldrig verkligen definiera det eller ändra det, 1472 01:02:26,410 --> 01:02:27,340 hur går det vet? 1473 01:02:27,340 --> 01:02:32,380 >> INSTRUKTÖR: Så en sak till märker upp här är int storlek. 1474 01:02:32,380 --> 01:02:35,680 Så vi säger i denna sort-- sort är en funktion i det här case-- det är 1475 01:02:35,680 --> 01:02:40,770 val sortera, det passerade in med funktionen. 1476 01:02:40,770 --> 01:02:43,460 Så om det inte skickades in, skulle du göra något 1477 01:02:43,460 --> 01:02:47,840 liknande med längden av uppsättningen eller skulle du iterera igenom 1478 01:02:47,840 --> 01:02:49,390 att hitta längden. 1479 01:02:49,390 --> 01:02:52,680 Men eftersom det är passerat i, kan vi bara använda den. 1480 01:02:52,680 --> 01:02:55,720 Du tar bara att användaren gav dig en giltig storlek som 1481 01:02:55,720 --> 01:02:57,698 faktiskt representerar en storlek på din array. 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 Cool? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> Om ni har några problem med dessa eller vill ha mer praxis kodning sorterar 1486 01:03:05,870 --> 01:03:08,050 på egen hand, bör du gå till study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 Det är ett verktyg. 1489 01:03:12,670 --> 01:03:15,040 De har en pjäs som Du kan faktiskt skriva. 1490 01:03:15,040 --> 01:03:16,180 De gör pseudokod. 1491 01:03:16,180 --> 01:03:19,310 De har fler videor och diabilder inklusive de som jag använder här. 1492 01:03:19,310 --> 01:03:23,150 Så om du fortfarande känner dig lite luddigt, prova att. 1493 01:03:23,150 --> 01:03:25,670 Som alltid, kom prata med mig också. 1494 01:03:25,670 --> 01:03:26,320 Fråga? 1495 01:03:26,320 --> 01:03:28,611 >> STUDENT: Säger du det Storleken är som tidigare definierats? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 INSTRUKTÖR: Ja. 1498 01:03:29,900 --> 01:03:35,570 Storleken tidigare definierats upp här i funktionsdeklarationen. 1499 01:03:35,570 --> 01:03:39,060 Så du antar att det har gått i av användaren, och för enkelhets skull, 1500 01:03:39,060 --> 01:03:41,896 vi kommer att anta att Användaren gav oss rätt storlek. 1501 01:03:41,896 --> 01:03:43,240 Cool. 1502 01:03:43,240 --> 01:03:44,390 Så det är val slag. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Killar, jag vet att vi lär oss en hel dag. 1505 01:03:47,640 --> 01:03:49,710 Det är en tät uppgifter för avdelning. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 Så med detta kommer vi för att gå till insättnings sort. 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> OK. 1510 01:04:02,510 --> 01:04:06,100 Så innan vi måste göra vår runtime analys här. 1511 01:04:06,100 --> 01:04:10,190 Så i bästa fall beviljats ​​sedan jag visade dig 1512 01:04:10,190 --> 01:04:11,960 tabellen jag redan slags gav det bort. 1513 01:04:11,960 --> 01:04:15,430 Men bästa fall runtime, vad tror vi? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Allt sorteras. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N i kvadrat. 1518 01:04:22,070 --> 01:04:24,780 Någon har en förklaring för varför du tror? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> STUDENT: Du jämföra through-- 1521 01:04:30,519 --> 01:04:31,268 INSTRUKTÖR: Rätt. 1522 01:04:31,268 --> 01:04:32,540 Du jämför igenom. 1523 01:04:32,540 --> 01:04:35,630 Vid varje iteration, trots att vi nedräkning detta efter en, 1524 01:04:35,630 --> 01:04:38,950 du fortfarande söka igenom allt för att hitta den minsta. 1525 01:04:38,950 --> 01:04:42,390 Så även om din minsta värde är här i början, 1526 01:04:42,390 --> 01:04:44,710 du fortfarande jämföra det mot allt annat 1527 01:04:44,710 --> 01:04:46,550 att se till att det är det minsta. 1528 01:04:46,550 --> 01:04:49,820 Så du kommer att sluta som löper genom ca n kvadrat gånger. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 Okej. 1531 01:04:51,590 --> 01:04:52,785 Och vad är det värsta? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Också n kvadrat eftersom du kommer att göra det samma procedur. 1534 01:04:57,980 --> 01:05:01,670 Så i detta fall, val sortera har något 1535 01:05:01,670 --> 01:05:04,010 som vi kallar också förväntade runtime. 1536 01:05:04,010 --> 01:05:07,400 Så i de andra, vi vet bara de övre och undre gränser. 1537 01:05:07,400 --> 01:05:11,180 Beroende på hur galen vår Listan är eller hur osorterat det är, 1538 01:05:11,180 --> 01:05:15,350 de varierar mellan n eller n kvadrat. 1539 01:05:15,350 --> 01:05:16,550 Vi vet inte. 1540 01:05:16,550 --> 01:05:22,820 >> Men eftersom valet sort har samma värsta och bästa fall, berättar att för oss att 1541 01:05:22,820 --> 01:05:25,880 oavsett vilken typ av input vi ha, oavsett om det är helt 1542 01:05:25,880 --> 01:05:29,130 sorterat eller fullständigt vända sorteras, det är 1543 01:05:29,130 --> 01:05:30,740 kommer att ta lika lång tid. 1544 01:05:30,740 --> 01:05:33,760 Så i så fall, om du minns från vårt bord, 1545 01:05:33,760 --> 01:05:38,610 det faktiskt hade ett värde som dessa två typer har inte, 1546 01:05:38,610 --> 01:05:40,390 vilket är förväntat runtime. 1547 01:05:40,390 --> 01:05:43,350 Så vi vet att när Vi kör val sortera, 1548 01:05:43,350 --> 01:05:45,380 det är garanterat köra en n kvadrerade tid. 1549 01:05:45,380 --> 01:05:46,630 Det finns ingen variation där. 1550 01:05:46,630 --> 01:05:47,630 Det är bara väntat. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 Och, återigen, om du vill lära dig mer, ta CS 124 under våren. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 Okej. 1555 01:05:56,712 --> 01:05:57,545 Vi har sett den här. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 Cool. 1558 01:05:59,030 --> 01:06:00,930 Så insättnings slag. 1559 01:06:00,930 --> 01:06:03,330 Och jag kommer nog att flamma igenom detta. 1560 01:06:03,330 --> 01:06:05,440 Jag kommer inte att ha er koda den. 1561 01:06:05,440 --> 01:06:06,580 Vi ska bara gå igenom det. 1562 01:06:06,580 --> 01:06:10,500 Så insättnings slag är snäll av liknande val Sortera 1563 01:06:10,500 --> 01:06:14,460 i att vi har både en osorterad och sorteras del av matrisen. 1564 01:06:14,460 --> 01:06:20,260 >> Men vad är annorlunda är att när vi går igenom en efter en, 1565 01:06:20,260 --> 01:06:24,210 vi bara ta de nummer är nästa i vår osorterade, 1566 01:06:24,210 --> 01:06:28,507 och korrekt sortera in i vår sorterade arrayen. 1567 01:06:28,507 --> 01:06:30,090 Det kommer att vara bättre med ett exempel. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 Så allt börjar som osorterat, precis som med val slag. 1570 01:06:35,430 --> 01:06:38,740 Och vi kommer att lösa detta på stigande ordning som vi har varit. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 Så på vår första passet Vi tar det första värdet 1573 01:06:43,340 --> 01:06:46,700 och vi säger, OK, du är nu i en lista själv. 1574 01:06:46,700 --> 01:06:49,150 >> Eftersom du är i en lista själv, du är sorterade. 1575 01:06:49,150 --> 01:06:52,460 Grattis för att vara första elementet i arrayen. 1576 01:06:52,460 --> 01:06:54,800 Du är redan sorterade allt på egen hand. 1577 01:06:54,800 --> 01:06:58,900 Så nu har vi en sortering och en osorterad array. 1578 01:06:58,900 --> 01:07:01,760 Så nu tar vi det första. 1579 01:07:01,760 --> 01:07:05,600 Vad händer mellan här och här är det vi säger, 1580 01:07:05,600 --> 01:07:08,890 OK, vi kommer att titta på första värdet av vår osorterade array 1581 01:07:08,890 --> 01:07:13,270 och vi kommer att mata in den i dess rätt ställe i den sorterade arrayen. 1582 01:07:13,270 --> 01:07:21,460 >> Så vad vi gör är tar vi 5 och vi säger, OK, 5 är större än 3, 1583 01:07:21,460 --> 01:07:24,630 så vi bara sätta in den rätt till höger om denna. 1584 01:07:24,630 --> 01:07:25,130 Vi är bra. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 Så då går vi vidare till vår nästa. 1587 01:07:28,420 --> 01:07:29,720 Och vi tar 2. 1588 01:07:29,720 --> 01:07:34,330 Vi säger, OK, 2 är mindre än 3, så vi vet att det 1589 01:07:34,330 --> 01:07:36,220 behöver vara vid framför vår lista nu. 1590 01:07:36,220 --> 01:07:41,800 Så vad vi gör är att vi trycker 3 och 5 ner och vi går 2 i det första facket. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 Så vi bara sätter in det i rätt plats det ska vara. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Då vi tittar på vår nästa en, och vi säger 6. 1595 01:07:49,470 --> 01:07:53,620 OK, är 6 större än allt i vårt sorterade arrayen, 1596 01:07:53,620 --> 01:07:56,000 så vi bara tagga det till slutet. 1597 01:07:56,000 --> 01:07:56,960 Och så tittar vi på 4. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 4 är mindre än 6, är det mindre än 5 men det är större än 3. 1600 01:08:03,020 --> 01:08:06,270 Så vi bara sätta in den rätt in mitten mellan 3 och 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 Så för att göra det lite lite mer konkret, 1603 01:08:10,530 --> 01:08:12,280 här är typ av uppfattning om vad som hände. 1604 01:08:12,280 --> 01:08:16,430 Så för varje osorterade element, vi bestämma var i den sorterade delen 1605 01:08:16,430 --> 01:08:17,090 det är. 1606 01:08:17,090 --> 01:08:20,680 >> Så med tanke på sorterade och osorterade, 1607 01:08:20,680 --> 01:08:26,080 vi har att passera genom och figur på var den passar i den sorterade arrayen. 1608 01:08:26,080 --> 01:08:31,460 Och vi för in den genom att flytta element till höger om den. 1609 01:08:31,460 --> 01:08:34,910 Och då är vi bara hålla iterera igenom tills vi 1610 01:08:34,910 --> 01:08:39,270 ha en helt sorterade listan där osorterade nu är noll 1611 01:08:39,270 --> 01:08:41,720 och sorterade tar upp helhet på vår lista. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 Så, återigen, att göra saker ännu mer konkret, vi har pseudokod. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> Så i princip för i är lika med 0 till n minus 1, 1616 01:08:52,410 --> 01:08:54,790 det är bara längden på vår array. 1617 01:08:54,790 --> 01:09:00,979 Vi har en del inslag som är lika med den första uppsättningen eller de första indexen. 1618 01:09:00,979 --> 01:09:03,200 Vi sätter j lika med den. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 Så medan j är större än noll och matrisen, j minus ett 1621 01:09:09,210 --> 01:09:11,660 är större än den element, så allt som gör 1622 01:09:11,660 --> 01:09:17,479 är att se till att din j verkligen representerar 1623 01:09:17,479 --> 01:09:20,010 den osorterade delen av matrisen. 1624 01:09:20,010 --> 01:09:30,745 >> Så medan det finns fortfarande saker att sortera och j minus ett är-- vad 1625 01:09:30,745 --> 01:09:31,840 är elementet henne? 1626 01:09:31,840 --> 01:09:34,760 J var aldrig definieras här. 1627 01:09:34,760 --> 01:09:35,677 Det är typ av irriterande. 1628 01:09:35,677 --> 01:09:36,176 OK. 1629 01:09:36,176 --> 01:09:36,689 Anyways. 1630 01:09:36,689 --> 01:09:39,899 Så j minus 1, du kontrollerar elementet innan det. 1631 01:09:39,899 --> 01:09:46,460 Du säger, OK, är elementet innan vart jag am-- låt oss 1632 01:09:46,460 --> 01:09:47,540 faktiskt dra ut denna. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 Så låt oss säga att detta är som på våra andra passet. 1635 01:09:56,830 --> 01:09:59,525 Så jag kommer att vara lika till 1, vilket är här. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> Så jag kommer att vara lika med 1. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 Detta skulle vara 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 Okej. 1642 01:10:16,750 --> 01:10:20,945 Så vår del i detta ärende kommer att vara lika med 4. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 Och vi har några j som är kommer att vara lika med ett. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 Åh, är j nedräkning. 1647 01:10:30,971 --> 01:10:31,720 Det är vad det är. 1648 01:10:31,720 --> 01:10:35,680 Så j är lika med i, så vad det här är säger är att när vi går framåt, 1649 01:10:35,680 --> 01:10:37,530 vi bara att se att vi inte är över 1650 01:10:37,530 --> 01:10:43,520 indexera det här sättet när vi försöker att sätta saker i vår sorterade listan. 1651 01:10:43,520 --> 01:10:49,850 >> Så när j är lika med 1 i detta fall och array j minus en-- så array j minus 1 1652 01:10:49,850 --> 01:10:54,610 är 2 i denna case-- om det är som är större än elementets, 1653 01:10:54,610 --> 01:10:57,700 då allt detta gör skiftar ner saker. 1654 01:10:57,700 --> 01:11:04,790 Så i detta fall, array j minus ett vore array noll, vilket är 2. 1655 01:11:04,790 --> 01:11:08,430 2 inte är större än 4, så detta inte köra. 1656 01:11:08,430 --> 01:11:11,460 Så övergången inte rör sig nedåt. 1657 01:11:11,460 --> 01:11:18,790 Vad detta innebär här är bara flytta din sorterade arrayen ner. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 I det här fallet, faktiskt, vi kunde do-- låt oss göra detta 3. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 Så om vi ska gå igenom med Detta exempel är vi nu här. 1662 01:11:31,970 --> 01:11:32,740 Detta är sorterad. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 Detta är osorterade. 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 Cool? 1667 01:11:39,860 --> 01:11:46,620 Så i är lika med 2, så vår del är lika med 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 Och vår j är lika med 2. 1670 01:11:52,270 --> 01:12:00,620 Så vi tittar igenom och vi säger, OK, är array j minus en 1671 01:12:00,620 --> 01:12:03,470 större än elementet att vi tittar på? 1672 01:12:03,470 --> 01:12:05,540 Och svaret är ja, hur? 1673 01:12:05,540 --> 01:12:11,275 4 är större än 3 och j är 2, så den här koden körs. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> Så nu vad vi gör en matris på 2, så just här, vi byta dem. 1676 01:12:18,550 --> 01:12:25,620 Så vi bara säga, OK, array vid 2 kommer nu att bli 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 Och j kommer att vara lika j minus 1, vilket är ett. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 Det är hemskt, men ni får idén. 1681 01:12:37,200 --> 01:12:38,360 J är nu lika med 1. 1682 01:12:38,360 --> 01:12:44,360 Och array j bara kommer att bli lika med vår del, vilket var 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 Jag raderade något jag inte borde har eller miswrote något, 1685 01:12:48,570 --> 01:12:49,910 men ni förstår tanken. 1686 01:12:49,910 --> 01:12:50,640 >> Det rör sig med n. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 Och sedan om det fanns, skulle det loop igen och det skulle säga, OK, är j 1 nu. 1689 01:12:57,960 --> 01:13:00,665 Och array j minus 1 är nu 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 Är 2 mindre än vår del? 1692 01:13:03,760 --> 01:13:04,540 Nej? 1693 01:13:04,540 --> 01:13:07,970 Det innebär att vi har insatt detta element 1694 01:13:07,970 --> 01:13:10,110 på rätt plats i vårt sorterade arrayen. 1695 01:13:10,110 --> 01:13:14,400 Då kan vi ta detta och vi säger, OK, är vår sorterade arrayen här. 1696 01:13:14,400 --> 01:13:19,940 Och det skulle ta detta nummer 6 och vara liknande, OK, är 6 färre än detta antal? 1697 01:13:19,940 --> 01:13:20,480 Nej? 1698 01:13:20,480 --> 01:13:21,080 Cool. 1699 01:13:21,080 --> 01:13:22,680 Vi är bra. 1700 01:13:22,680 --> 01:13:23,530 >> Gör det igen. 1701 01:13:23,530 --> 01:13:24,740 Vi säger 7. 1702 01:13:24,740 --> 01:13:29,010 Är 7 färre än i slutet av våra sorterade arrayen? 1703 01:13:29,010 --> 01:13:29,520 Nej. 1704 01:13:29,520 --> 01:13:30,430 Så vi är bra. 1705 01:13:30,430 --> 01:13:32,760 Så detta skulle sorteras. 1706 01:13:32,760 --> 01:13:38,610 I princip allt detta gör det säger take 1707 01:13:38,610 --> 01:13:42,060 den första delen av din osorterat array, 1708 01:13:42,060 --> 01:13:46,010 räkna ut var det går i ditt sorterade arrayen. 1709 01:13:46,010 --> 01:13:48,780 Och detta bara tar hand av swappar för att göra det. 1710 01:13:48,780 --> 01:13:51,300 Du är i princip bara byta tills det är på rätt plats. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 Den visuella bilden är att du är flytta ned allt genom att göra det. 1713 01:13:56,990 --> 01:13:59,420 >> Så det är som en halv bubbla sort-esque. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Kolla undersökning 50. 1716 01:14:03,420 --> 01:14:06,000 Jag rekommenderar starkt försöker att koda detta på egen hand. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 Om du har några frågor eller om du vill se exempelkod för en insättnings sortera, 1719 01:14:12,450 --> 01:14:13,750 låt mig veta. 1720 01:14:13,750 --> 01:14:14,500 Jag är alltid runt. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 Så värsta fall runtime och bästa fall runtime. 1723 01:14:20,200 --> 01:14:30,700 Som ni killen såg från bordet jag redan visade dig, det är både n kvadrat och n. 1724 01:14:30,700 --> 01:14:35,590 >> Så snäll att gå ut med vad vi pratade om med våra tidigare slag, värst 1725 01:14:35,590 --> 01:14:38,760 fall runtime är att om det är helt osorterade, 1726 01:14:38,760 --> 01:14:42,530 vi har att jämföra alla dessa n gånger. 1727 01:14:42,530 --> 01:14:47,020 Vi gör en hel del jämförelser eftersom om det är i omvänd ordning, 1728 01:14:47,020 --> 01:14:50,360 vi ska säga, OK, detta är densamma, är det bra, 1729 01:14:50,360 --> 01:14:54,650 och här måste jämföras mot den första en att flyttas tillbaka. 1730 01:14:54,650 --> 01:14:56,710 Och när vi får in mot svansen slutet, vi har 1731 01:14:56,710 --> 01:14:59,440 att jämföra, jämföra och jämföra mot allt. 1732 01:14:59,440 --> 01:15:03,030 >> Så det slutar som ungefär n kvadrat. 1733 01:15:03,030 --> 01:15:09,510 Om det stämmer så har du säger, OK, 2, du är bra. 1734 01:15:09,510 --> 01:15:11,330 3, du är jämfört med 2. 1735 01:15:11,330 --> 01:15:12,310 Du är bra. 1736 01:15:12,310 --> 01:15:14,150 4, du bara jämför med svansen. 1737 01:15:14,150 --> 01:15:14,990 Du är bra. 1738 01:15:14,990 --> 01:15:17,140 6, jämför med svansen, du är bra. 1739 01:15:17,140 --> 01:15:20,870 Så för varje plats om det redan sorterade, du gjorde en jämförelse. 1740 01:15:20,870 --> 01:15:22,320 Så det är bara n. 1741 01:15:22,320 --> 01:15:26,840 Och eftersom vi har en bästa fall runtime n och ett värsta runtime n 1742 01:15:26,840 --> 01:15:28,680 kvadrat, har vi ingen förväntad körtid. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> Det beror bara på kaos på vår lista där. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 Och återigen, en annan graf och en annan tabell. 1747 01:15:39,530 --> 01:15:41,170 Så skillnader mellan sorter. 1748 01:15:41,170 --> 01:15:44,180 Jag kommer bara att knäppa genom, jag känns som vi har pratat utför 1749 01:15:44,180 --> 01:15:46,570 om hur de alla typer av att variera och länka samman. 1750 01:15:46,570 --> 01:15:50,564 Så Merge sort är den sista Jag ska tråka ut er med. 1751 01:15:50,564 --> 01:15:52,105 Vi har en ganska färgstark bild. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 Så samman slag är en rekursiv algoritm. 1754 01:15:56,040 --> 01:15:59,910 Så gör ni vet vad en rekursiv funktion är? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Någon vill säga? 1757 01:16:03,320 --> 01:16:04,739 Vill du prova? 1758 01:16:04,739 --> 01:16:07,280 Så en rekursiv funktion är bara en funktion som kallar sig. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 Så om ni känner med Fibonacci-sekvensen, 1761 01:16:11,590 --> 01:16:15,670 som har bedömts rekursiv eftersom du tar de två föregående 1762 01:16:15,670 --> 01:16:17,530 och lägga ihop dem att få din nästa. 1763 01:16:17,530 --> 01:16:21,440 Så rekursiv, tror jag alltid av rekursion som likt en spiral 1764 01:16:21,440 --> 01:16:24,430 så du är som spiral ner i den. 1765 01:16:24,430 --> 01:16:27,150 Men det är bara en funktion som kallar sig. 1766 01:16:27,150 --> 01:16:32,660 >> Och, faktiskt, riktigt snabbt jag kan visa dig vad som ser ut som. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 Så rekursiv här, om vi ser, är detta den rekursiva sättet att summera över en array. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 Så allt vi gör är Vi har sum funktion 1771 01:16:47,880 --> 01:16:52,210 summa som tar en storlek och en array. 1772 01:16:52,210 --> 01:16:55,210 Och om du märker, storlek minskningar av en varje gång. 1773 01:16:55,210 --> 01:17:00,365 Och allt det gör är om x är lika med zero-- så om storleken på matrisen 1774 01:17:00,365 --> 01:17:02,710 är lika med zero-- den returnerar noll. 1775 01:17:02,710 --> 01:17:10,440 >> Annars summerar detta sista elementet i arrayen, 1776 01:17:10,440 --> 01:17:14,790 och sedan tar en summa resten av matrisen. 1777 01:17:14,790 --> 01:17:17,555 Så det är bara att bryta ner i mindre och mindre problem. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Lång historia kort, rekursion, funktion som kallar sig. 1780 01:17:21,890 --> 01:17:25,740 Om det är allt du fick ut av detta, det är vad en rekursiv funktion är. 1781 01:17:25,740 --> 01:17:29,870 Om du tar 51, du kommer att få mycket, mycket bekväma med rekursion. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 Det är verkligen häftigt. 1784 01:17:32,370 --> 01:17:34,660 Det var meningsfullt på liknande 03:00 en natt. 1785 01:17:34,660 --> 01:17:37,900 Och jag var som, varför har jag aldrig detta? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> Så för merge sort, i princip Vad det kommer att göra är att det är 1788 01:17:42,430 --> 01:17:45,620 kommer att bryta ner det och bryta ner tills det är bara enskilda element. 1789 01:17:45,620 --> 01:17:47,570 De enskilda delarna är lätta att sortera. 1790 01:17:47,570 --> 01:17:48,070 Vi ser att. 1791 01:17:48,070 --> 01:17:50,760 Om du har en del, det är redan som sorteras. 1792 01:17:50,760 --> 01:17:53,800 Så på en ingång av n element, om n är mindre än 2, 1793 01:17:53,800 --> 01:17:58,120 bara tillbaka eftersom det betyder det är antingen 0 eller 1 som vi har sett. 1794 01:17:58,120 --> 01:18:00,050 De som anses sorterade element. 1795 01:18:00,050 --> 01:18:02,170 >> Annars bryter den på mitten. 1796 01:18:02,170 --> 01:18:06,336 Sortera första halvlek, sortera den andra hälften, och sedan sammanfoga dem tillsammans. 1797 01:18:06,336 --> 01:18:07,460 Varför det kallas merge sort. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 Så vi har här vi ska sortera dessa. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 Så vi fortsätter att ha dem tills matrisstorlek är 1. 1802 01:18:17,210 --> 01:18:20,790 Så när det är 1, vi bara tillbaka eftersom detta är en sorterad array, 1803 01:18:20,790 --> 01:18:23,940 och detta är en sorterad array, och det är en sorterad array, vi alla sorterade. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 Så vad vi gör är att vi börja slå samman dem tillsammans. 1806 01:18:29,420 --> 01:18:31,820 >> Så hur kan du tycker om sammanslagning är 1807 01:18:31,820 --> 01:18:36,240 du bara ta bort den mindre antal av vardera av underuppsättningar 1808 01:18:36,240 --> 01:18:38,330 och bara lägga den till framkommit arrayen. 1809 01:18:38,330 --> 01:18:44,290 Så om du tittar här, när vi har dessa uppsättningar vi har 4, 6 och 1. 1810 01:18:44,290 --> 01:18:47,280 När vi vill sammanfoga dessa, vi tittar på dessa två första 1811 01:18:47,280 --> 01:18:50,730 och vi säger, OK, 1 är mindre, Det går till fronten. 1812 01:18:50,730 --> 01:18:54,330 4 och 6, det finns inget att jämföra det, bara tagga den på till slutet. 1813 01:18:54,330 --> 01:18:58,020 >> När vi kombinerar dessa två, vi bara ta den mindre en av dessa två, 1814 01:18:58,020 --> 01:18:59,310 så det är 1. 1815 01:18:59,310 --> 01:19:01,690 Och nu tar vi mindre av dessa två, så 2. 1816 01:19:01,690 --> 01:19:03,330 Mindre av dessa två, 3. 1817 01:19:03,330 --> 01:19:06,260 Mindre av dessa två, fyra, fem, sex. 1818 01:19:06,260 --> 01:19:08,630 Så du bara dra av dessa. 1819 01:19:08,630 --> 01:19:11,210 Och eftersom de har sorterats tidigare, 1820 01:19:11,210 --> 01:19:14,300 Du har bara en Jämförelsen varje gång. 1821 01:19:14,300 --> 01:19:19,610 Så mer kod här, bara representation. 1822 01:19:19,610 --> 01:19:24,410 Så du börjar på mitten och du sorterar vänster och höger 1823 01:19:24,410 --> 01:19:26,180 och då du bara slå ihop dem. 1824 01:19:26,180 --> 01:19:30,080 >> Och vi har inte kod för samman just här. 1825 01:19:30,080 --> 01:19:34,110 Men, återigen, om du går på studera 50, det ska vara där. 1826 01:19:34,110 --> 01:19:36,860 Annars kommer prata med mig om du fortfarande förvirrad. 1827 01:19:36,860 --> 01:19:42,340 Så cool sak här är att i bästa fall, värsta fall, och förväntade runtime 1828 01:19:42,340 --> 01:19:46,250 är alla i log n, vilken är mycket bättre än vi har 1829 01:19:46,250 --> 01:19:48,000 sett för resten av våra slag. 1830 01:19:48,000 --> 01:19:51,840 Vi har sett n kvadrat och vad vi faktiskt 1831 01:19:51,840 --> 01:19:54,380 ta sig hit är n log n, vilket är bra. 1832 01:19:54,380 --> 01:19:55,830 >> Titta på hur mycket bättre det är. 1833 01:19:55,830 --> 01:19:56,780 En sådan fin kurva. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 Så mycket mer effektivt. 1836 01:20:00,120 --> 01:20:03,510 Om du någonsin kan, användning samman slag. 1837 01:20:03,510 --> 01:20:04,810 Det kommer att spara tid. 1838 01:20:04,810 --> 01:20:07,670 Då igen, som sagt, om du är i detta nedre regionen, 1839 01:20:07,670 --> 01:20:09,480 Det gör inte det mycket av en skillnad. 1840 01:20:09,480 --> 01:20:11,360 Du får upp till tusentals och tusentals insatsvaror, 1841 01:20:11,360 --> 01:20:13,318 du absolut vill ha en mer effektiv algoritm. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 Och, återigen, vår fina tabell över alla sorterar att ni lärt idag. 1844 01:20:19,400 --> 01:20:21,157 >> Så jag vet att det har varit en tät dag. 1845 01:20:21,157 --> 01:20:23,490 Detta är inte nödvändigtvis kommer för att hjälpa dig med din pset. 1846 01:20:23,490 --> 01:20:28,250 Men jag vill bara göra en ansvarsfriskrivning det avsnittet handlar inte bara om psets. 1847 01:20:28,250 --> 01:20:31,240 Allt detta material är rättvist spel för dina midterms. 1848 01:20:31,240 --> 01:20:35,430 Och även om du fortsätter med CS, dessa är verkligen viktiga fundamenta 1849 01:20:35,430 --> 01:20:37,870 att du skulle behöva veta. 1850 01:20:37,870 --> 01:20:41,700 Så vissa dagar kommer att vara en lite mer pset hjälp, 1851 01:20:41,700 --> 01:20:44,600 men några veckor kommer att vara mycket mer faktiska innehållet 1852 01:20:44,600 --> 01:20:46,600 som kanske inte verkar super användbart för dig just nu, 1853 01:20:46,600 --> 01:20:51,215 men jag lovar om du fortsätter på kommer att bli mycket, mycket användbart. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> Så det är det för avsnitt. 1856 01:20:54,250 --> 01:20:55,250 Ner till viran. 1857 01:20:55,250 --> 01:20:56,570 Jag gjorde det inom en minut. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 Men där du går. 1860 01:20:58,970 --> 01:21:01,240 Och jag kommer att ha munkar eller godis. 1861 01:21:01,240 --> 01:21:03,464 Är någon allergisk mot något, förresten? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Ägg och mjölk. 1864 01:21:05,890 --> 01:21:08,120 Så munkar är ett nej? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 OK. 1867 01:21:10,160 --> 01:21:10,770 Okej. 1868 01:21:10,770 --> 01:21:12,120 Choklad nej? 1869 01:21:12,120 --> 01:21:12,620 Starburst. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starbursts är bra. 1872 01:21:14,670 --> 01:21:15,170 OK. 1873 01:21:15,170 --> 01:21:17,045 Vi kommer att ha Starburst nästa vecka då. 1874 01:21:17,045 --> 01:21:18,240 Det är vad jag får. 1875 01:21:18,240 --> 01:21:19,690 Ni har en bra vecka. 1876 01:21:19,690 --> 01:21:20,460 Läs din spec. 1877 01:21:20,460 --> 01:21:22,130 >> Låt mig veta om du har några frågor. 1878 01:21:22,130 --> 01:21:25,300 Pset två kvaliteter bör vara ut till dig av torsdagen. 1879 01:21:25,300 --> 01:21:28,320 Om du har några frågor om hur jag graderade något 1880 01:21:28,320 --> 01:21:32,250 eller varför jag graderade något som jag gjorde, vänligen maila mig, kom prata med mig. 1881 01:21:32,250 --> 01:21:34,210 Jag är lite galen ut vecka, men jag lovar 1882 01:21:34,210 --> 01:21:36,340 Jag kommer fortfarande att svara inom 24 timmar. 1883 01:21:36,340 --> 01:21:38,240 Så ha en bra vecka, alla. 1884 01:21:38,240 --> 01:21:40,090 Lycka till på din pset. 1885 01:21:40,090 --> 01:21:41,248