1 00:00:00,000 --> 00:00:03,332 >> [MUSIC SPILLE] 2 00:00:03,332 --> 00:00:06,490 >> ANDI PENG: Velkommen til uke tre av seksjonen. 3 00:00:06,490 --> 00:00:09,550 Takk, dere, for alle kommende til dette tidligere starttid i dag. 4 00:00:09,550 --> 00:00:11,466 Vi har fått en fin, liten intim gruppe i dag. 5 00:00:11,466 --> 00:00:14,570 Så forhåpentligvis vil vi få til finish, kanskje, tidlig, 6 00:00:14,570 --> 00:00:15,780 litt tidlig i dag. 7 00:00:15,780 --> 00:00:22,057 Så fort, bare noen kunngjøringer for agendaen i dag. 8 00:00:22,057 --> 00:00:23,890 Før vi begynner, er vi kommer til å bare gå over 9 00:00:23,890 --> 00:00:28,910 noen korte logistiske problemer, PSet spørsmål, debrief, sånne ting. 10 00:00:28,910 --> 00:00:30,250 Og så skal vi stupe rett i. 11 00:00:30,250 --> 00:00:34,710 Vi vil bruke en debugger kalt GDB til starte avslørte vår kode, som David 12 00:00:34,710 --> 00:00:36,550 forklart i forelesning her om dagen. 13 00:00:36,550 --> 00:00:39,420 Vi vil gå over fire typer former. 14 00:00:39,420 --> 00:00:42,310 Vi vil gå over dem ganske raskt siden de er ganske intensiv. 15 00:00:42,310 --> 00:00:45,710 Men vet at alle skinnene og Kildekoden er alltid online. 16 00:00:45,710 --> 00:00:50,810 Så gjerne, ved gjennomlesing, til gå tilbake og ta en titt på det. 17 00:00:50,810 --> 00:00:53,930 >> Vi vil gå gjennom asymptotisk notasjon, som 18 00:00:53,930 --> 00:00:55,944 er bare en fancy måte si "kjøretidsfiler," 19 00:00:55,944 --> 00:00:58,360 hvor vi har den store O, som David forklart i forelesningen. 20 00:00:58,360 --> 00:01:01,550 Og vi har også Omega, som er den nedre grense kjøring. 21 00:01:01,550 --> 00:01:06,450 Og vi skal snakke litt mer inngående om hvordan de arbeidet. 22 00:01:06,450 --> 00:01:10,160 Og til slutt, vil vi gå over binære søk, fordi mange av dere som allerede har 23 00:01:10,160 --> 00:01:15,190 kikket på dine psets vet sikkert at det er et spørsmål som er i din PSet. 24 00:01:15,190 --> 00:01:17,470 Så du vil alle være fornøyd at vi dette i dag dekker. 25 00:01:17,470 --> 00:01:20,610 >> Og til slutt, per din § tilbakemeldinger, jeg faktisk 26 00:01:20,610 --> 00:01:23,000 forlot ca 15 minutter ved slutt å bare gå over 27 00:01:23,000 --> 00:01:27,730 logistikken pset3, spørsmål, kanskje litt veiledning, om du vil, 28 00:01:27,730 --> 00:01:28,990 før vi begynner programmering. 29 00:01:28,990 --> 00:01:30,890 Så la oss prøve å komme gjennom materialet ganske raskt. 30 00:01:30,890 --> 00:01:33,880 Og så kan vi bruke litt tid tar flere spørsmål for PSet. 31 00:01:33,880 --> 00:01:35,230 OK. 32 00:01:35,230 --> 00:01:39,570 >> Raskt, slik at bare noen få kunngjøringer før vi starter i dag. 33 00:01:39,570 --> 00:01:45,410 For det første, velkommen til å gjøre det gjennom to av dine psets. 34 00:01:45,410 --> 00:01:49,432 Jeg tok en titt på your-- yeah, la oss få en runde med applaus for at ett. 35 00:01:49,432 --> 00:01:51,140 Egentlig var jeg virkelig, virkelig imponert. 36 00:01:51,140 --> 00:01:55,800 Jeg gradert første PSet for dere forrige uke, og dere gjorde utrolig. 37 00:01:55,800 --> 00:01:58,290 >> Stilen var på punktet foruten noen kommentarer. 38 00:01:58,290 --> 00:02:00,660 Sørg for at du alltid er kommenterer koden din. 39 00:02:00,660 --> 00:02:03,040 Men dine psets var på punktet. 40 00:02:03,040 --> 00:02:05,549 Og holde det opp. 41 00:02:05,549 --> 00:02:08,090 Og det er bra for grader til se at dere setter 42 00:02:08,090 --> 00:02:10,704 i så mye innsats i din stil og design i koden 43 00:02:10,704 --> 00:02:12,120 at vi ønsker for deg å se. 44 00:02:12,120 --> 00:02:16,450 Så jeg passerer langs min takknemlighet for resten av TAS. 45 00:02:16,450 --> 00:02:19,210 >> Men det er en Noen utspørrings spørsmål 46 00:02:19,210 --> 00:02:22,010 Jeg vil bare gå over at ville gjøre både livet mitt 47 00:02:22,010 --> 00:02:24,900 og mange av de andre TAs liv litt lettere. 48 00:02:24,900 --> 00:02:28,220 For det første, jeg har lagt merke til dette forbi week-- hvor mange av dere 49 00:02:28,220 --> 00:02:32,301 har kjørt check50 på koden din før du sender inn? 50 00:02:32,301 --> 00:02:32,800 OK. 51 00:02:32,800 --> 00:02:36,690 Så alle bør gjøre check50, because-- en secret-- vi faktisk 52 00:02:36,690 --> 00:02:41,540 kjøre check50 som en del av vår korrekthet skript for å teste koden din. 53 00:02:41,540 --> 00:02:45,480 Så hvis koden er sviktende check50, i all sannsynlighet, 54 00:02:45,480 --> 00:02:47,570 det er trolig kommer til å mislykkes vår sjekk også. 55 00:02:47,570 --> 00:02:49,320 Noen ganger dere har de riktige svarene. 56 00:02:49,320 --> 00:02:52,200 Som, i grådige, noen av du har de riktige tallene, 57 00:02:52,200 --> 00:02:53,960 du bare skrive ut noen ekstra ting. 58 00:02:53,960 --> 00:02:55,940 Og som ekstra ting faktisk svikter sjekk, 59 00:02:55,940 --> 00:02:58,440 fordi datamaskinen ikke egentlig vet hva det er på jakt etter. 60 00:02:58,440 --> 00:03:00,981 Og så det vil bare kjøre gjennom, ser at utskriftene ikke 61 00:03:00,981 --> 00:03:03,810 samsvarer med hva vi forventer svaret å være, og merk det er galt. 62 00:03:03,810 --> 00:03:06,560 >> Og jeg vet at har skjedd i noen av sakene denne uken. 63 00:03:06,560 --> 00:03:09,870 Så jeg gikk tilbake og manuelt regraded alles kode. 64 00:03:09,870 --> 00:03:12,780 I fremtiden skjønt, please, please sørge 65 00:03:12,780 --> 00:03:14,570 at du kjører sjekke 50 på koden din. 66 00:03:14,570 --> 00:03:17,970 Fordi det er litt vondt for TA å måtte gå tilbake og manuelt regrade 67 00:03:17,970 --> 00:03:21,197 hver eneste PSet for hver enkelt, lite savnet eksempel. 68 00:03:21,197 --> 00:03:22,530 Så jeg fikk ikke ta av noen poeng. 69 00:03:22,530 --> 00:03:25,210 Jeg tror jeg tok av kanskje én eller to for design. 70 00:03:25,210 --> 00:03:27,710 I fremtiden om, hvis du er sviktende check50, 71 00:03:27,710 --> 00:03:31,330 punktene vil bli tatt off for korrekthet. 72 00:03:31,330 --> 00:03:35,020 >> Videre psets er skyldes fredager på formiddagen. 73 00:03:35,020 --> 00:03:38,990 Jeg tror det er en syv minutters sent gyldighetsperiode som vi gir deg. 74 00:03:38,990 --> 00:03:42,434 Per Harvard tid, er de lov til å være sju minutter for sent til alt. 75 00:03:42,434 --> 00:03:44,350 Så her ved Yale, vil vi holder seg til det også. 76 00:03:44,350 --> 00:03:47,910 Men ganske mye, på 12:07, hvis PSet ikke er i, 77 00:03:47,910 --> 00:03:49,720 det kommer til å merkes så sent. 78 00:03:49,720 --> 00:03:53,160 Og så lenge det er merket så sent, den TA-- jeg er 79 00:03:53,160 --> 00:03:54,870 fortsatt kommer til å bli gradering dine psets. 80 00:03:54,870 --> 00:03:56,760 Så vil du fortsatt se en karakter vises. 81 00:03:56,760 --> 00:03:58,820 Men vet at på slutten av semesteret, 82 00:03:58,820 --> 00:04:02,270 alle sent psets vil bare være automatisk nullet av datamaskinen. 83 00:04:02,270 --> 00:04:04,490 >> Vi gjør dette av to grunner. 84 00:04:04,490 --> 00:04:09,220 En, noen ganger får vi unnskyldt, som Deans unnskyldninger, 85 00:04:09,220 --> 00:04:10,762 senere at jeg ikke vet om ennå. 86 00:04:10,762 --> 00:04:13,761 Så vi ønsker å sørge for at vi gradering alt bare i tilfelle, som jeg er 87 00:04:13,761 --> 00:04:15,080 mangler en dekan unnskyldning. 88 00:04:15,080 --> 00:04:17,000 Og for det andre, holde i sinn, kan du fortsatt 89 00:04:17,000 --> 00:04:19,370 droppe en PSet som har full omfang poeng. 90 00:04:19,370 --> 00:04:21,430 Og så liker vi å gradere alle dine psets bare 91 00:04:21,430 --> 00:04:24,730 å sørge for at omfanget er der og du prøver dem. 92 00:04:24,730 --> 00:04:29,150 Så selv om det er sent, vil du likevel få kreditt for omfang poeng, tror jeg. 93 00:04:29,150 --> 00:04:33,730 >> Så moralen i historien er, gjøre for at psets er på gang. 94 00:04:33,730 --> 00:04:38,350 Og hvis de ikke er i på-tiden, vet at det er ikke bra. 95 00:04:38,350 --> 00:04:41,678 Ja, før jeg går videre, er det noen som har spørsmål om PSet tilbakemeldinger? 96 00:04:41,678 --> 00:04:42,178 Yeah. 97 00:04:42,178 --> 00:04:43,630 >> PUBLIKUM: Visste du si vi kan slippe en av de psets? 98 00:04:43,630 --> 00:04:44,296 >> ANDI PENG: Yeah. 99 00:04:44,296 --> 00:04:47,050 Så det er ni psets generelle i løpet av semesteret. 100 00:04:47,050 --> 00:04:50,610 Og hvis du har omfanget points-- så omfanget er bare, 101 00:04:50,610 --> 00:04:53,567 ganske mye, er du forsøker problem, er du setter i gang, 102 00:04:53,567 --> 00:04:56,150 er du viser at du har demonstrert du har lest spec. 103 00:04:56,150 --> 00:04:57,191 Det er ganske mye omfang. 104 00:04:57,191 --> 00:04:59,370 Og hvis du oppfyller omfang poeng, vi 105 00:04:59,370 --> 00:05:03,360 kan slippe den laveste en ut av full omfang. 106 00:05:03,360 --> 00:05:06,790 Så det er i din fordel å fullføre og prøve hver PSet. 107 00:05:06,790 --> 00:05:10,320 >> Selv upload-- hvis ingen av dem arbeid, laste dem alle. 108 00:05:10,320 --> 00:05:13,711 Og da vil vi forhåpentligvis kunne gi deg noen av disse punktene tilbake. 109 00:05:13,711 --> 00:05:14,210 Kjølig. 110 00:05:14,210 --> 00:05:16,780 Eventuelle andre spørsmål? 111 00:05:16,780 --> 00:05:17,840 Flott. 112 00:05:17,840 --> 00:05:21,960 >> Dernest kontor timer-- noen raske notater om kontortiden. 113 00:05:21,960 --> 00:05:24,300 Så først, kom tidlig i uken. 114 00:05:24,300 --> 00:05:26,909 Ingen er noensinne på kontortid på mandager. 115 00:05:26,909 --> 00:05:28,700 Christ kom til kontortid i går kveld. 116 00:05:28,700 --> 00:05:29,691 Ja, Christ. 117 00:05:29,691 --> 00:05:32,190 Og hva gjorde vi har på kontoret timer i går kveld, Christ? 118 00:05:32,190 --> 00:05:33,020 >> PUBLIKUM: Vi hadde iskrem. 119 00:05:33,020 --> 00:05:36,160 >> ANDI PENG: Så det er riktig, hadde vi iskrem på kontortiden i går kveld. 120 00:05:36,160 --> 00:05:39,390 Selv om jeg ikke kan love deg at vi vil ha iskrem på kontortid 121 00:05:39,390 --> 00:05:43,230 hver uke, det kan jeg love deg er at det vil være en betydelig 122 00:05:43,230 --> 00:05:45,380 bedre student til TA ratio. 123 00:05:45,380 --> 00:05:47,650 Som legit, er det som 12:57. 124 00:05:47,650 --> 00:05:50,350 Mens, kontrast at med Torsdag, har du ca 150 125 00:05:50,350 --> 00:05:52,830 veldig stresset barn og ingen iskrem. 126 00:05:52,830 --> 00:05:55,360 Og det er bare ikke produktivt for alle. 127 00:05:55,360 --> 00:05:58,730 Så moralen i historien er, kom tidlig til arbeidstid og gode ting 128 00:05:58,730 --> 00:06:00,310 vil skje. 129 00:06:00,310 --> 00:06:02,110 >> Også kommer forberedt til å stille spørsmål. 130 00:06:02,110 --> 00:06:03,200 Du vet? 131 00:06:03,200 --> 00:06:05,420 Uansett hva TAs, jeg tror, ​​har vært å si, 132 00:06:05,420 --> 00:06:10,710 Vi har fått et par studenter som kommer inn på torsdag på, som, 10:50 133 00:06:10,710 --> 00:06:15,100 ikke å ha lest spec være som å hjelpe meg, hjelpe meg. 134 00:06:15,100 --> 00:06:18,200 Dessverre på det punktet, det er ikke mye vi kan gjøre for å hjelpe deg. 135 00:06:18,200 --> 00:06:19,590 Så kan du komme tidlig i uken. 136 00:06:19,590 --> 00:06:22,040 Kom tidlig for å kontortid. 137 00:06:22,040 --> 00:06:23,350 Kom forberedt på å stille spørsmål. 138 00:06:23,350 --> 00:06:25,310 Sørg for at du som en student, er der 139 00:06:25,310 --> 00:06:27,620 du må være slik at TAs kan veilede deg langs, 140 00:06:27,620 --> 00:06:32,850 Som er hva kontortid burde bli tildelt for. 141 00:06:32,850 --> 00:06:37,380 >> For det andre, så jeg vet professorer liker å overraske oss med tester. 142 00:06:37,380 --> 00:06:39,439 Jeg hadde en professor dem liker, yo, forresten, 143 00:06:39,439 --> 00:06:41,230 husk at deleksamen du har neste mandag. 144 00:06:41,230 --> 00:06:42,855 Ja, jeg visste ikke om at deleksamen. 145 00:06:42,855 --> 00:06:45,630 Så jeg kommer til å være at TA som minner deg alt som quiz 146 00:06:45,630 --> 00:06:47,270 0-- fordi, du vet, vi er CS. 147 00:06:47,270 --> 00:06:50,730 Nå som vi har gjort arrays, får du hvorfor det er quiz 0, ikke quiz en, eh? 148 00:06:50,730 --> 00:06:51,320 OK. 149 00:06:51,320 --> 00:06:52,490 Åh, jeg fikk noen humrer på den. 150 00:06:52,490 --> 00:06:53,120 OK. 151 00:06:53,120 --> 00:06:59,710 >> Så quiz 0 vil være 14 oktober hvis du er i mandag-onsdag seksjon 152 00:06:59,710 --> 00:07:02,920 og oktober 15 Hvis du er i tirsdag-torsdag delen. 153 00:07:02,920 --> 00:07:05,630 Dette gjelder ikke for de av dere ved Harvard 154 00:07:05,630 --> 00:07:10,350 who-- Jeg tror du vil alle være ta dine quizer på den 14. 155 00:07:10,350 --> 00:07:13,560 >> Så ja, neste uke, hvis David, i foredrag, går, 156 00:07:13,560 --> 00:07:15,747 yeah, så om det quiz neste uke, dere alle 157 00:07:15,747 --> 00:07:17,580 vil ikke bli sjokkert fordi du kom til seksjon 158 00:07:17,580 --> 00:07:19,664 og du vet at din quiz 0 er i to uker. 159 00:07:19,664 --> 00:07:21,580 Og vi vil ha en vurdering økter og alt. 160 00:07:21,580 --> 00:07:26,360 Så ingen bekymringer om å være redd for det. 161 00:07:26,360 --> 00:07:29,890 Eventuelle spørsmål before-- spørsmål på alle om logistiske problemer, 162 00:07:29,890 --> 00:07:32,591 gradering, kontortid, seksjoner? 163 00:07:32,591 --> 00:07:33,090 Yeah. 164 00:07:33,090 --> 00:07:35,100 >> PUBLIKUM: Så quiz er kommer til å være under forelesning? 165 00:07:35,100 --> 00:07:35,766 >> ANDI PENG: Yeah. 166 00:07:35,766 --> 00:07:39,460 Så quiz, tror jeg, er 60 minutt tildelt i den tidsluke 167 00:07:39,460 --> 00:07:42,240 at du bare ta i forelesningssalen. 168 00:07:42,240 --> 00:07:44,810 Så du trenger ikke å komme i på, som en tilfeldig 07:00. 169 00:07:44,810 --> 00:07:46,140 Det er alt bra. 170 00:07:46,140 --> 00:07:47,100 Yeah. 171 00:07:47,100 --> 00:07:50,060 Kjølig. 172 00:07:50,060 --> 00:07:50,840 >> Greit. 173 00:07:50,840 --> 00:07:54,330 Så vi kommer til å introdusere et konsept for deg 174 00:07:54,330 --> 00:08:00,760 denne uken at David har allerede slag av berørt i foredraget denne siste uken. 175 00:08:00,760 --> 00:08:02,010 Det kalles GDB. 176 00:08:02,010 --> 00:08:05,570 Og hvor mange av dere, mens i I løpet av å skrive dine psets, 177 00:08:05,570 --> 00:08:09,981 har lagt merke til en stor knapp som sier "Debug" på toppen av din IDE? 178 00:08:09,981 --> 00:08:10,480 OK. 179 00:08:10,480 --> 00:08:13,770 Så nå skal vi faktisk får til å grave opp mysterium hva den knappen faktisk 180 00:08:13,770 --> 00:08:14,270 gjør. 181 00:08:14,270 --> 00:08:16,790 Og jeg kan garantere deg, det er en vakker, vakker ting. 182 00:08:16,790 --> 00:08:20,740 >> Så frem til nå, tror jeg det har vært to ting 183 00:08:20,740 --> 00:08:23,320 studenter har vært typisk gjør når debugging psets. 184 00:08:23,320 --> 00:08:27,635 En, de enten legge i printf () - så noen få linjer, 185 00:08:27,635 --> 00:08:29,760 de legger i en printf () - oh, hva er denne variabelen? 186 00:08:29,760 --> 00:08:32,551 Oh, hva er denne variabelen now-- og du slags se progresjon 187 00:08:32,551 --> 00:08:33,940 av koden din som det går. 188 00:08:33,940 --> 00:08:37,030 Eller den andre metoden barna gjør er at de bare skrive hele greia 189 00:08:37,030 --> 00:08:38,610 og deretter gå slik på slutten. 190 00:08:38,610 --> 00:08:39,970 Forhåpentligvis fungerer det. 191 00:08:39,970 --> 00:08:44,851 Jeg kan garantere deg, er GDB bedre enn begge disse metoder. 192 00:08:44,851 --> 00:08:45,350 Yeah. 193 00:08:45,350 --> 00:08:46,980 Så dette blir din nye bestevenn. 194 00:08:46,980 --> 00:08:51,780 Fordi det er en vakker ting som visuelt viser både 195 00:08:51,780 --> 00:08:54,850 hva koden gjør på et bestemt punkt 196 00:08:54,850 --> 00:08:57,486 samt hva alle dine variabler er bærer, 197 00:08:57,486 --> 00:08:59,610 som hva deres verdier er, på det bestemt punkt. 198 00:08:59,610 --> 00:09:02,670 Og på denne måten, kan du virkelig sette stoppunkter i koden din. 199 00:09:02,670 --> 00:09:04,350 Du kan kjøre gjennom linje for linje. 200 00:09:04,350 --> 00:09:07,324 Og GDB vil bare ha for du, som vises for deg, 201 00:09:07,324 --> 00:09:09,490 hva alle variabler er, hva de gjør, 202 00:09:09,490 --> 00:09:10,656 hva som skjer i koden. 203 00:09:10,656 --> 00:09:13,240 Og på en slik måte, er det så mye lettere å se 204 00:09:13,240 --> 00:09:17,120 hva som skjer i stedet for printf-ing eller skrive ned dine uttalelser. 205 00:09:17,120 --> 00:09:19,160 >> Så vi vil gjøre et eksempel på dette senere. 206 00:09:19,160 --> 00:09:20,660 Så dette virker litt abstrakt. 207 00:09:20,660 --> 00:09:23,490 Ingen grunn til bekymring, vil vi gjøre eksempler. 208 00:09:23,490 --> 00:09:29,170 Og så egentlig, de tre største, mest brukte funksjonene du trenger i GDB 209 00:09:29,170 --> 00:09:32,500 er den neste, Step over, og skrittet inn knapper. 210 00:09:32,500 --> 00:09:34,860 Jeg kommer til å gå over der, faktisk, akkurat nå. 211 00:09:34,860 --> 00:09:40,930 >> Så kan dere alle se at eller skal jeg zoome inn litt? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 I ryggen, kan du se det? 214 00:09:44,470 --> 00:09:45,730 Bør jeg zoome inn? 215 00:09:45,730 --> 00:09:46,480 Bare en liten bit? 216 00:09:46,480 --> 00:09:49,390 Ok kult. 217 00:09:49,390 --> 00:09:50,280 Det vi går. 218 00:09:50,280 --> 00:09:50,960 OK. 219 00:09:50,960 --> 00:09:57,000 >> Så jeg har, her, min implementering for grådig. 220 00:09:57,000 --> 00:10:01,430 Og mens mange av dere skrev grådig i mens loop form-- at 221 00:10:01,430 --> 00:10:04,890 er en helt akseptabel måte å gjøre det-- en annen måte å gjøre det på er å rett og slett 222 00:10:04,890 --> 00:10:06,280 dele i modulo. 223 00:10:06,280 --> 00:10:09,290 Fordi da kan du ha din verdi og deretter ha resten. 224 00:10:09,290 --> 00:10:11,150 Og da kan du bare legger det hele sammen. 225 00:10:11,150 --> 00:10:13,390 Har logikken i hva jeg gjør her være fornuftig for alle, 226 00:10:13,390 --> 00:10:14,117 før vi begynner? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 På en måte? 229 00:10:17,980 --> 00:10:18,710 Kjølig. 230 00:10:18,710 --> 00:10:19,210 Flott. 231 00:10:19,210 --> 00:10:21,290 Det er en ganske sexy stykke kode, vil jeg si. 232 00:10:21,290 --> 00:10:23,502 Som jeg sa, David, i forelesning, etter en stund, 233 00:10:23,502 --> 00:10:25,960 du vil alle begynne å se koden som noe som er vakkert. 234 00:10:25,960 --> 00:10:29,950 Og noen ganger når du ser vakker kode, det er slik en fantastisk følelse. 235 00:10:29,950 --> 00:10:35,410 >> Så imidlertid mens denne koden er veldig vakkert, det fungerer ikke som den skal. 236 00:10:35,410 --> 00:10:37,750 Så la oss kjøre check50 på dette. 237 00:10:37,750 --> 00:10:39,440 Sjekk 50 20-- oop. 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 Er det pset2? 241 00:10:44,990 --> 00:10:46,870 Yeah. 242 00:10:46,870 --> 00:10:47,520 Oh, pset1. 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 OK. 245 00:10:52,890 --> 00:10:53,900 Så vi kjører check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> Og som dere kan se her, det er sviktende et par tilfeller. 248 00:11:07,170 --> 00:11:10,165 Og for noen av dere, i løpet av å gjøre dine oppgavesett, 249 00:11:10,165 --> 00:11:11,110 du er som, ah, hvorfor er det ikke fungerer. 250 00:11:11,110 --> 00:11:13,318 Hvorfor er det å jobbe for noen verdier, men ikke for andre? 251 00:11:13,318 --> 00:11:17,760 Vel, GDB kommer til å hjelpe deg figuren ut hvorfor disse inngangene ikke fungerer. 252 00:11:17,760 --> 00:11:18,320 >> OK. 253 00:11:18,320 --> 00:11:21,640 Så la oss se, en av de sjekker jeg mislykkes i check50 254 00:11:21,640 --> 00:11:24,920 var inngangsverdien på 0,41. 255 00:11:24,920 --> 00:11:27,830 Så det riktige svaret som du bør få er en 4. 256 00:11:27,830 --> 00:11:33,090 Men i stedet hva jeg skriver ut er 3-n, som er feil. 257 00:11:33,090 --> 00:11:36,190 Så la oss bare kjøre dette manuelt, bare sørge for at check50 fungerer. 258 00:11:36,190 --> 00:11:36,940 La oss gjøre ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Oops, jeg må gjøre grådig. 261 00:11:43,340 --> 00:11:43,840 Det vi går. 262 00:11:43,840 --> 00:11:44,381 Nå ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Hvor mye er skyldte? 265 00:11:47,670 --> 00:11:49,550 La oss gjøre 0,41. 266 00:11:49,550 --> 00:11:52,590 Og ja, vi ser her at det å gi ut tre 267 00:11:52,590 --> 00:11:55,160 når det riktige svaret, faktisk, bør være fire. 268 00:11:55,160 --> 00:12:01,460 Så la oss gå inn GDB og se hvordan vi kan gå om å fikse dette problemet. 269 00:12:01,460 --> 00:12:03,992 >> Så det første trinnet i alltid debugging koden 270 00:12:03,992 --> 00:12:05,950 er å sette et stoppunkt, eller et punkt der du 271 00:12:05,950 --> 00:12:09,079 vil datamaskinen eller debugger for å begynne å se på. 272 00:12:09,079 --> 00:12:11,120 Så hvis du ikke virkelig vet hva problemet er, 273 00:12:11,120 --> 00:12:14,670 vanligvis, den typiske ting vi ønsker å gjøre er å sette vår stoppunkt på hoved. 274 00:12:14,670 --> 00:12:18,520 Så hvis dere kan se dette røde knappen til høyre der, 275 00:12:18,520 --> 00:12:22,860 Jepp, det var meg å sette en bruddpunkt for den viktigste funksjonen. 276 00:12:22,860 --> 00:12:24,130 Jeg klikker det. 277 00:12:24,130 --> 00:12:26,130 >> Og så kan jeg gå opp til min Debug-knappen. 278 00:12:26,130 --> 00:12:27,036 Jeg traff den knappen. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 La meg zoome ut igjen hvis jeg kan. 281 00:12:36,555 --> 00:12:38,020 Det vi går. 282 00:12:38,020 --> 00:12:40,730 Så vi har, her, et panel på høyre side. 283 00:12:40,730 --> 00:12:43,680 Jeg beklager, gutta i ryggen, du kan egentlig ikke se veldig bra. 284 00:12:43,680 --> 00:12:49,090 Men i hovedsak, alt denne retten panel gjør 285 00:12:49,090 --> 00:12:53,130 er å holde styr på både uthevet linje, som er den linje med kode 286 00:12:53,130 --> 00:12:56,640 at datamaskinen kjører for øyeblikket, samt alle dine variabler 287 00:12:56,640 --> 00:12:57,600 her nede. 288 00:12:57,600 --> 00:13:00,487 >> Så du har fått cent, mynter, n, alle erklærte til forskjellige ting 289 00:13:00,487 --> 00:13:01,070 På dette punktet. 290 00:13:01,070 --> 00:13:04,850 Ingen grunn til bekymring, fordi vi har faktisk ikke initialisert dem til noen variabler ennå. 291 00:13:04,850 --> 00:13:07,200 Så i datamaskinen, din Datamaskinen er bare å se, 292 00:13:07,200 --> 00:13:14,376 oh, 32767 var det sist brukte funksjonen av at minne i datamaskinen min. 293 00:13:14,376 --> 00:13:16,000 Og så det er der cent i dag. 294 00:13:16,000 --> 00:13:19,360 Men no at når du kjører koden, Det bør bli initialisert. 295 00:13:19,360 --> 00:13:24,110 >> Så la oss gå gjennom, linje for linje, hva som skjer her. 296 00:13:24,110 --> 00:13:25,350 OK. 297 00:13:25,350 --> 00:13:29,400 Så her oppe er de tre knapper som jeg nettopp forklart. 298 00:13:29,400 --> 00:13:34,090 Du har Play, eller Run-funksjonen, knappen, har du gå over knappen, 299 00:13:34,090 --> 00:13:36,600 og du har også steget inn knappen. 300 00:13:36,600 --> 00:13:41,260 Og egentlig, alle tre dem bare gå gjennom koden din 301 00:13:41,260 --> 00:13:42,690 og gjøre forskjellige ting. 302 00:13:42,690 --> 00:13:45,680 >> Så typisk, når du er feilsøking, vi ønsker ikke å bare trykke Play, 303 00:13:45,680 --> 00:13:47,930 fordi Play vil bare kjøre koden til slutten av den. 304 00:13:47,930 --> 00:13:49,070 Og da vil du faktisk ikke vet hva problemet 305 00:13:49,070 --> 00:13:51,432 er mindre du stille inn flere stoppunkter. 306 00:13:51,432 --> 00:13:53,890 Hvis du angir flere stoppunkter, det vil bare automatisk 307 00:13:53,890 --> 00:13:56,030 løpe fra en stoppunkt, til den neste, til den neste. 308 00:13:56,030 --> 00:13:58,030 Men i dette tilfellet har vi bare at en, fordi vi 309 00:13:58,030 --> 00:13:59,970 ønsker å jobbe oss fra toppen og ned til bunnen. 310 00:13:59,970 --> 00:14:04,830 Så vi kommer til å ignorere den knappen akkurat nå for anvendelsen av dette programmet. 311 00:14:04,830 --> 00:14:08,230 >> Så Step over funksjonen bare skritter over hver enkelt linje 312 00:14:08,230 --> 00:14:11,510 og forteller deg hva datamaskinen gjør. 313 00:14:11,510 --> 00:14:14,630 Step inn funksjon går inn i selve funksjonen 314 00:14:14,630 --> 00:14:16,000 som er på linje med kode. 315 00:14:16,000 --> 00:14:19,070 Så for eksempel, som printf (), som er en funksjon, ikke sant? 316 00:14:19,070 --> 00:14:21,980 Hvis jeg ønsket å fysisk trinn inn i printf () -funksjonen, 317 00:14:21,980 --> 00:14:25,610 Jeg vil faktisk gå inn i stykke koden der printf () ble skrevet og se 318 00:14:25,610 --> 00:14:26,730 hva som skjer der. 319 00:14:26,730 --> 00:14:29,924 >> Men typisk, antar vi at koden som vi gi deg fungerer. 320 00:14:29,924 --> 00:14:31,340 Vi antar at printf () fungerer. 321 00:14:31,340 --> 00:14:33,170 Vi antar at GetInt () fungerer. 322 00:14:33,170 --> 00:14:35,170 Så det er ingen grunn til å gå inn i disse funksjonene. 323 00:14:35,170 --> 00:14:37,170 Men hvis det er funksjoner som du skriver selv 324 00:14:37,170 --> 00:14:39,060 som du ønsker å sjekke ut hva som skjer, 325 00:14:39,060 --> 00:14:41,200 du ønsker å gå inn i denne funksjonen. 326 00:14:41,200 --> 00:14:43,940 >> Så akkurat nå er vi bare nødt å gå over denne del av koden. 327 00:14:43,940 --> 00:14:44,485 Så la oss se. 328 00:14:44,485 --> 00:14:46,547 Oh, print, "Oh hai, hvordan mye endring er skyldte? " 329 00:14:46,547 --> 00:14:47,130 Vi bryr oss ikke. 330 00:14:47,130 --> 00:14:49,830 Vi vet at fungerer, så vi gå over det. 331 00:14:49,830 --> 00:14:53,290 >> Så n, som er vår flåte som vi har initialized-- eller declared-- 332 00:14:53,290 --> 00:14:56,810 opp på toppen, er vi nå tilsvarende som i GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Så la oss gå over det. 334 00:14:57,810 --> 00:14:59,580 Og vi ser på bunn her, programmet 335 00:14:59,580 --> 00:15:03,360 tilskynder meg for å legge inn en verdi. 336 00:15:03,360 --> 00:15:08,580 Så la oss innspill verdien vi ønsker for å teste her, som er 0,41. 337 00:15:08,580 --> 00:15:09,160 Flott. 338 00:15:09,160 --> 00:15:12,780 >> Så nå N- gjør dere se her, på bottom-- det er 339 00:15:12,780 --> 00:15:15,140 stored-- fordi vi har ikke rundet ennå, er det 340 00:15:15,140 --> 00:15:19,540 som er lagret i dette som gigant flåte som er ,4099999996, 341 00:15:19,540 --> 00:15:22,550 som er nær nok til vår formål, akkurat nå, til 0,41. 342 00:15:22,550 --> 00:15:26,090 Og så får vi se senere, som vi fortsette å tråkke over programmet, 343 00:15:26,090 --> 00:15:29,850 etter her, har n blitt avrundet og øre har blitt 41. 344 00:15:29,850 --> 00:15:30,350 Flott. 345 00:15:30,350 --> 00:15:32,230 Så vi vet at vår avrunding arbeidsgruppe. 346 00:15:32,230 --> 00:15:34,700 Vi vet at vi har riktig antall cent, 347 00:15:34,700 --> 00:15:36,990 så vi vet at det er egentlig ikke problemet. 348 00:15:36,990 --> 00:15:40,050 >> Så vi fortsetter å tråkke på i dette programmet. 349 00:15:40,050 --> 00:15:40,900 Vi går her. 350 00:15:40,900 --> 00:15:46,139 Og så etter denne linjen med kode, vi bør vite hvor mange kvartalene vi har. 351 00:15:46,139 --> 00:15:46,680 Vi går over. 352 00:15:46,680 --> 00:15:52,040 Og du ser vi, faktisk, har en kvartal fordi vi har trukket 25 353 00:15:52,040 --> 00:15:53,790 fra vår opprinnelige verdi av 41. 354 00:15:53,790 --> 00:15:55,890 Og vi har 16 venstre for våre cent. 355 00:15:55,890 --> 00:15:58,830 >> Har alle forstår hvordan programmet er å tråkke gjennom 356 00:15:58,830 --> 00:16:02,980 og hvorfor cent har nå blitt 16 og hvorfor, nå, mynter har blitt en? 357 00:16:02,980 --> 00:16:04,610 Er alle etter den logikken? 358 00:16:04,610 --> 00:16:05,110 Kjølig. 359 00:16:05,110 --> 00:16:07,860 Slik som i dette punkt, Programmets arbeids, ikke sant? 360 00:16:07,860 --> 00:16:09,797 Vi vet at det gjør akkurat hva vi vil. 361 00:16:09,797 --> 00:16:11,880 Og vi gjorde faktisk ikke må skrive ut, oh, hva 362 00:16:11,880 --> 00:16:14,430 er cents på dette punktet, hva er mynter på dette punktet. 363 00:16:14,430 --> 00:16:17,170 >> Vi fortsetter å gå gjennom programmet. 364 00:16:17,170 --> 00:16:18,100 Tråkke over. 365 00:16:18,100 --> 00:16:18,620 Kjølig. 366 00:16:18,620 --> 00:16:19,700 Vi går over dimes. 367 00:16:19,700 --> 00:16:20,200 Flott. 368 00:16:20,200 --> 00:16:22,367 Vi ser at det er tatt off $ 0,10 for en krone. 369 00:16:22,367 --> 00:16:23,450 Og nå har vi to mynter. 370 00:16:23,450 --> 00:16:25,260 Det er riktig. 371 00:16:25,260 --> 00:16:31,555 >> Vi går over pennies og vi ser at vi har fått til overs cent. 372 00:16:31,555 --> 00:16:32,680 Hmm, det er rart. 373 00:16:32,680 --> 00:16:37,540 Her oppe på programmet, skulle jeg å ha trukket mine pennies. 374 00:16:37,540 --> 00:16:39,400 Kanskje jeg var bare ikke gjør at linjen rett. 375 00:16:39,400 --> 00:16:42,190 Og akk, kan du se her, fordi vi vet 376 00:16:42,190 --> 00:16:44,360 at vi er stepping gjennom linjene 32 og 33, 377 00:16:44,360 --> 00:16:50,560 det er der vårt program feilaktig hadde variabler kjøre. 378 00:16:50,560 --> 00:16:55,136 Så vi kan se og se, oh, Jeg trekke cents her, 379 00:16:55,136 --> 00:16:57,010 men jeg er faktisk ikke legge til min myntverdi. 380 00:16:57,010 --> 00:16:57,860 Jeg legger til cent. 381 00:16:57,860 --> 00:17:00,234 Og jeg ønsker ikke å legge til cents, jeg vil legge til mynter. 382 00:17:00,234 --> 00:17:05,420 Så hvis vi endre det til mynter, vi har et arbeidsprogram. 383 00:17:05,420 --> 00:17:06,730 Jeg kan kjøre check50. 384 00:17:06,730 --> 00:17:11,063 Du kan bare gå ut av GDB rett her og deretter kjøre check50 igjen. 385 00:17:11,063 --> 00:17:11,938 Jeg kunne bare gjøre dette. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Jeg må gjøre grådig. 388 00:17:18,480 --> 00:17:19,940 0,41. 389 00:17:19,940 --> 00:17:22,819 Og her er det utskrift ut det rette svaret. 390 00:17:22,819 --> 00:17:26,569 >> Så som dere kan se, GDB er et veldig kraftig verktøy 391 00:17:26,569 --> 00:17:29,940 for når vi har så mye kode skjer og så mange variabler 392 00:17:29,940 --> 00:17:32,510 at det er vanskelig for oss, som et menneske, for å holde styr på. 393 00:17:32,510 --> 00:17:35,360 Datamaskinen, i GDB debugger, har evnen 394 00:17:35,360 --> 00:17:37,020 å holde styr på alt. 395 00:17:37,020 --> 00:17:40,480 Jeg vet, i Visionaire, dere sannsynligvis kan ha truffet noen segmentering feil 396 00:17:40,480 --> 00:17:43,150 fordi du kjører utenfor banen for ditt array. 397 00:17:43,150 --> 00:17:46,510 I eksempelet med Cæsar, det er akkurat det jeg har implementert her. 398 00:17:46,510 --> 00:17:50,060 >> Så jeg glemte å se etter hva som ville skje hvis jeg 399 00:17:50,060 --> 00:17:52,510 hadde ikke to kommandolinjeargumenter. 400 00:17:52,510 --> 00:17:53,880 Jeg hadde ikke bare sette i at innsjekking. 401 00:17:53,880 --> 00:17:57,380 Og så hvis jeg kjører Debug-- satt jeg min stoppunkt til høyre der. 402 00:17:57,380 --> 00:17:58,055 Jeg kjører Debug. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> OK. 405 00:18:16,550 --> 00:18:17,050 Yeah. 406 00:18:17,050 --> 00:18:20,350 Så egentlig, GDB skulle å ha fortalt meg det 407 00:18:20,350 --> 00:18:22,300 var en segmentering feil der. 408 00:18:22,300 --> 00:18:24,883 Jeg vet ikke hva som skjedde rett der, men når jeg kjørte den, 409 00:18:24,883 --> 00:18:25,590 det var i arbeid. 410 00:18:25,590 --> 00:18:29,410 Når du kjører linjer med kode gjennom og GDB kanskje bare plutselig slutte på deg, 411 00:18:29,410 --> 00:18:31,540 gå opp og se hva den røde feilen er. 412 00:18:31,540 --> 00:18:33,930 Det skal fortelle deg, hei, du hadde en segmentering feil, 413 00:18:33,930 --> 00:18:38,550 noe som betyr at du prøvde å få tilgang plass i en matrise som ikke eksisterte. 414 00:18:38,550 --> 00:18:39,050 Yeah. 415 00:18:39,050 --> 00:18:43,280 >> Så i det neste problemet satt denne uken, dere 416 00:18:43,280 --> 00:18:45,600 vil trolig ha mye variabler som flyter rundt. 417 00:18:45,600 --> 00:18:48,560 Du kommer ikke til å være sikker på hva de betyr på et visst punkt. 418 00:18:48,560 --> 00:18:53,560 Så GDB vil virkelig hjelpe deg i å finne ut hva de er alle tilsvar 419 00:18:53,560 --> 00:18:55,940 og å være i stand til å se at visuelt. 420 00:18:55,940 --> 00:19:01,995 Er noen forvirret på hvordan noe av det arbeidet? 421 00:19:01,995 --> 00:19:02,495 Kjølig. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Greit. 424 00:19:10,620 --> 00:19:14,260 Så etter det, er vi kommer til å stupe rett 425 00:19:14,260 --> 00:19:17,562 inn er fire forskjellige typer former for denne uken. 426 00:19:17,562 --> 00:19:19,520 Hvor mange av dere, først av alt, før vi begynner, 427 00:19:19,520 --> 00:19:23,020 har lest hele spec for pset3? 428 00:19:23,020 --> 00:19:23,824 OK. 429 00:19:23,824 --> 00:19:24,740 Jeg er stolt av dere. 430 00:19:24,740 --> 00:19:29,110 Det er som halvparten av klassen, som er betydelig mer enn forrige gang. 431 00:19:29,110 --> 00:19:33,950 >> Så det er flott, fordi når vi snakker om innholdet 432 00:19:33,950 --> 00:19:36,170 i lecture-- eller sorry, i section-- Jeg liker 433 00:19:36,170 --> 00:19:38,210 å forholde seg mye av det tilbake til hva PSet er 434 00:19:38,210 --> 00:19:40,210 og hvordan du vil implementere det i din PSet. 435 00:19:40,210 --> 00:19:42,400 Så hvis du kommer med lese spec, det vil 436 00:19:42,400 --> 00:19:45,510 være mye lettere for deg å forstå hva jeg snakker om når jeg sier, 437 00:19:45,510 --> 00:19:48,720 oh hei, dette kan være en virkelig godt sted å implementere denne typen. 438 00:19:48,720 --> 00:19:52,870 Så de av dere som har lest spec vet det, som en del av PSet, 439 00:19:52,870 --> 00:19:54,900 du er nødt til å skrive en type slag. 440 00:19:54,900 --> 00:19:58,670 Så dette kan være svært nyttig for mange av dere i dag. 441 00:19:58,670 --> 00:20:01,760 >> Så vi vil begynne med, hovedsak, den mest enkel type 442 00:20:01,760 --> 00:20:04,580 sortering, valg liksom. 443 00:20:04,580 --> 00:20:06,800 Den typiske algoritme for hvordan vi skulle gå om dette 444 00:20:06,800 --> 00:20:10,460 er-- David gikk gjennom alle disse i forelesning, så jeg vil raskt flytte sammen 445 00:20:10,460 --> 00:20:13,900 her-- er egentlig, du har en rekke verdier. 446 00:20:13,900 --> 00:20:17,170 Og så finner du den minste usortert verdi 447 00:20:17,170 --> 00:20:20,200 og du bytte denne verdien med den første usortert verdi. 448 00:20:20,200 --> 00:20:22,700 Og så du bare terpe med resten av listen. 449 00:20:22,700 --> 00:20:25,740 >> Og her er en visuell forklaring av hvordan det ville fungere. 450 00:20:25,740 --> 00:20:30,460 Så for eksempel, hvis vi skulle starte med en rekke av fem elementer, index 451 00:20:30,460 --> 00:20:35,910 0 til 4, med 3, 5, 2, 6, 4 og verdiene plasseres i array-- så akkurat nå, 452 00:20:35,910 --> 00:20:38,530 vi bare kommer til å anta at de er alle usortert 453 00:20:38,530 --> 00:20:41,130 fordi vi har ikke testet noe annet. 454 00:20:41,130 --> 00:20:44,130 >> Så hvordan et utvalg slags ville arbeid er at det ville først 455 00:20:44,130 --> 00:20:46,800 kjøre gjennom helheten av usortert array. 456 00:20:46,800 --> 00:20:49,120 Det ville plukke ut den minste verdien. 457 00:20:49,120 --> 00:20:51,750 I dette tilfellet, 3, høyre nå, er den minste. 458 00:20:51,750 --> 00:20:52,680 Det blir til fem. 459 00:20:52,680 --> 00:20:55,620 Nope, fem er ikke større than-- eller beklager, er ikke mindre than-- tre. 460 00:20:55,620 --> 00:20:57,779 Så minimumsverdien er fortsatt tre. 461 00:20:57,779 --> 00:20:58,695 Og så får du til to. 462 00:20:58,695 --> 00:21:00,990 Datamaskinen ser, oh, to er mindre enn tre. 463 00:21:00,990 --> 00:21:02,750 2, må nå være minimumsverdi. 464 00:21:02,750 --> 00:21:06,630 Og så 2 swaps med at første verdien. 465 00:21:06,630 --> 00:21:10,702 >> Så etter ett pass, trenger vi faktisk se at 2 og 3 er byttet. 466 00:21:10,702 --> 00:21:13,910 Og vi bare kommer til å fortsette å gjøre dette igjen med resten av matrisen. 467 00:21:13,910 --> 00:21:17,660 Så vi kommer til å bare kjøre gjennom de siste fire indekser i rekken. 468 00:21:17,660 --> 00:21:20,670 Vi får se at tre er neste minimumsverdi. 469 00:21:20,670 --> 00:21:23,240 Så vi kommer til å bytte det med fire. 470 00:21:23,240 --> 00:21:26,900 Og da er vi bare kommer til å fortsette kjører gjennom til slutt, du 471 00:21:26,900 --> 00:21:33,730 få til en sortert array i hvilken 2, 3, 4, 5, og 6 er sortert. 472 00:21:33,730 --> 00:21:37,530 Har alle forstå logikken av hvordan et utvalg slags jobber? 473 00:21:37,530 --> 00:21:39,669 >> Du har bare en slags fra en minimumsverdi. 474 00:21:39,669 --> 00:21:41,210 Du holder styr på hva det er. 475 00:21:41,210 --> 00:21:45,170 Og når du finner den, bytte du det med den første verdien i array-- 476 00:21:45,170 --> 00:21:48,740 eller, ikke den første value-- neste verdi i matrisen. 477 00:21:48,740 --> 00:21:50,150 Kjølig. 478 00:21:50,150 --> 00:21:55,460 >> Så som dere slags så fra et kort glimt, 479 00:21:55,460 --> 00:21:58,450 vi kommer til å pseudo ut dette. 480 00:21:58,450 --> 00:22:02,510 Så hvis dere i ryggen vil danne en gruppe, alle på et bord 481 00:22:02,510 --> 00:22:06,170 kan danne en liten partner, jeg kommer å gi dere som tre minutter 482 00:22:06,170 --> 00:22:08,190 å bare snakke gjennom logikken, på engelsk, 483 00:22:08,190 --> 00:22:14,161 om hvordan vi kan være i stand til å gjennomføre pseudokode for å skrive et utvalg sort. 484 00:22:14,161 --> 00:22:14,910 Og det er godteri. 485 00:22:14,910 --> 00:22:16,118 Kom opp og få godteri. 486 00:22:16,118 --> 00:22:19,520 Hvis du er i ryggen, og du vil godteri, kan jeg kaste godteri på deg. 487 00:22:19,520 --> 00:22:22,850 Egentlig gjør you-- kult. 488 00:22:22,850 --> 00:22:23,552 Åh unnskyld. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 OK. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Så hvis vi har lyst til, som en klasse, skrive pseudo 493 00:25:27,140 --> 00:25:30,466 for hvordan en kan nærme seg dette problemet, bare du gjerne. 494 00:25:30,466 --> 00:25:32,340 Jeg vil bare gå rundt og, i orden, spør grupper 495 00:25:32,340 --> 00:25:35,065 for den neste linje hva vi bør gjøre. 496 00:25:35,065 --> 00:25:37,840 Så hvis dere ønsker å starte off, hva er det første 497 00:25:37,840 --> 00:25:40,600 å gjøre når du prøver å implementere en måte å løse dette programmet 498 00:25:40,600 --> 00:25:43,480 selektivt sortere en liste? 499 00:25:43,480 --> 00:25:46,349 La oss bare anta at vi har en rekke, ok? 500 00:25:46,349 --> 00:25:49,088 >> PUBLIKUM: Du ønsker å lage noen liksom [uhørbart] at du er 501 00:25:49,088 --> 00:25:50,420 kjører gjennom hele klyngen. 502 00:25:50,420 --> 00:25:51,128 >> ANDI PENG: Høyre. 503 00:25:51,128 --> 00:25:54,100 Så du kommer til å ønske å reagere gjennom hver plass, ikke sant? 504 00:25:54,100 --> 00:26:05,490 Så stor. 505 00:26:05,490 --> 00:26:08,600 Hvis dere ønsker å gi meg neste line-- yeah, i ryggen. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> PUBLIKUM: Sjekk dem alt etter de minste. 508 00:26:13,290 --> 00:26:14,248 >> ANDI PENG: Det vi går. 509 00:26:14,248 --> 00:26:17,438 Så vi ønsker å gå gjennom og kontrollere se hva minimumsverdien er, ikke sant? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Jeg kommer til å forkorte det til "min." 512 00:26:24,840 --> 00:26:27,658 Hva gjør dere vil gjøre etter du har funnet den laveste verdien? 513 00:26:27,658 --> 00:26:28,533 >> PUBLIKUM: [uhørbart] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI PENG: Så du kommer til å ønske å slår den med den første av den oppstillingen, 516 00:26:33,150 --> 00:26:33,650 ikke sant? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 Det er begynnelsen, jeg kommer til å si. 519 00:26:46,850 --> 00:26:47,220 Greit. 520 00:26:47,220 --> 00:26:50,386 Så nå som du har byttet den første en, hva vil du gjøre etter det? 521 00:26:50,386 --> 00:26:54,840 Så nå vet vi at denne her må være den minste verdien, ikke sant? 522 00:26:54,840 --> 00:26:58,310 Da har du en ekstra hvile i matrisen som er usortert. 523 00:26:58,310 --> 00:27:01,569 Så hva du ønsker å gjøre her, hvis du Gutta ønsker å gi meg neste linje? 524 00:27:01,569 --> 00:27:04,610 PUBLIKUM: Så da du ønsker å reagere gjennom resten av matrisen. 525 00:27:04,610 --> 00:27:05,276 ANDI PENG: Yeah. 526 00:27:05,276 --> 00:27:09,857 Og så hva betyr gjentakelse gjennom en slags innebære vi må sikkert? 527 00:27:09,857 --> 00:27:10,440 Hvilken type of-- 528 00:27:10,440 --> 00:27:12,057 >> PUBLIKUM: Oh, en ekstra variabel? 529 00:27:12,057 --> 00:27:13,890 ANDI PENG: Sannsynligvis en annen for loop, ikke sant? 530 00:27:13,890 --> 00:27:28,914 Så vi sannsynligvis kommer til å ønske å veksle through-- stor. 531 00:27:28,914 --> 00:27:31,830 Og så kommer du til å gå tilbake og sannsynligvis kontrollere minimum igjen, 532 00:27:31,830 --> 00:27:32,100 ikke sant? 533 00:27:32,100 --> 00:27:34,975 Og du kommer til å terpe dette, fordi sløyfene bare kommer 534 00:27:34,975 --> 00:27:36,010 å holde i gang, ikke sant? 535 00:27:36,010 --> 00:27:39,190 >> Så som dere kan se, vi bare har en generell pseudo 536 00:27:39,190 --> 00:27:41,480 av hvordan vi vil at dette programmet skal se ut. 537 00:27:41,480 --> 00:27:46,646 Dette iterere her, hva gjør vi vanligvis trenger å skrive i vårt kode 538 00:27:46,646 --> 00:27:49,270 hvis vi ønsker å iterere gjennom en array, hva slags struktur? 539 00:27:49,270 --> 00:27:51,030 Jeg tror Christ allerede har sagt dette før. 540 00:27:51,030 --> 00:27:51,500 >> PUBLIKUM: En for loop. 541 00:27:51,500 --> 00:27:52,160 >> ANDI PENG: A for loop? 542 00:27:52,160 --> 00:27:52,770 Nettopp. 543 00:27:52,770 --> 00:27:56,060 Så dette er trolig kommer til å være en for loop. 544 00:27:56,060 --> 00:27:59,240 Hva er en sjekk her kommer til å innebære? 545 00:27:59,240 --> 00:28:02,536 Vanligvis, hvis du ønsker å sjekke hvis noe er noe else-- 546 00:28:02,536 --> 00:28:03,270 >> PUBLIKUM: If. 547 00:28:03,270 --> 00:28:06,790 >> ANDI PENG: An om, ikke sant? 548 00:28:06,790 --> 00:28:10,790 Og så swap her, vil vi gå over senere, fordi David 549 00:28:10,790 --> 00:28:12,770 gikk gjennom det i foredraget også. 550 00:28:12,770 --> 00:28:14,580 Og deretter den andre itera implies-- 551 00:28:14,580 --> 00:28:15,120 >> PUBLIKUM: Another for loop. 552 00:28:15,120 --> 00:28:16,745 >> ANDI PENG: --another for loop, akkurat. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Så hvis vi ser på dette riktig, vi 555 00:28:22,000 --> 00:28:24,680 kan se at vi er trolig kommer til å trenge en nestet for loop 556 00:28:24,680 --> 00:28:28,330 med et betinget utsagn der og deretter en faktisk stykke kode som er 557 00:28:28,330 --> 00:28:31,360 kommer til å bytte verdier. 558 00:28:31,360 --> 00:28:35,980 Så jeg har bare generelt skrevet en pseudokode her. 559 00:28:35,980 --> 00:28:38,910 Og da er vi faktisk kommer til fysisk, som en klasse, 560 00:28:38,910 --> 00:28:40,700 prøve å gjennomføre dette i dag. 561 00:28:40,700 --> 00:28:42,486 La oss gå tilbake til denne IDE. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> UH oh. 564 00:28:50,230 --> 00:28:51,754 Hvorfor er det not-- det det er. 565 00:28:51,754 --> 00:28:52,253 OK. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Sorry, la meg prøve å zoome inn litt mer. 568 00:28:57,500 --> 00:28:59,310 Det vi går. 569 00:28:59,310 --> 00:29:05,060 Alt jeg gjør her er at jeg har opprettet et program som heter "valg / sort.c." 570 00:29:05,060 --> 00:29:10,860 Jeg har opprettet en rekke av ni verdier, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 Tiden, som du kan se, de er uordnet. 572 00:29:14,370 --> 00:29:17,880 n kommer til å være nummer som forteller deg hvor mye verdier 573 00:29:17,880 --> 00:29:18,920 du har i array. 574 00:29:18,920 --> 00:29:20,670 I dette tilfellet har vi ni verdier. 575 00:29:20,670 --> 00:29:23,760 Og jeg har nettopp fått en for loop her som skriver ut usortert array. 576 00:29:23,760 --> 00:29:28,370 >> Og på slutten, jeg har også fått en for loop som bare skriver den ut igjen. 577 00:29:28,370 --> 00:29:32,070 Så teoretisk, dersom dette programmet fungerer som den skal, på slutten, 578 00:29:32,070 --> 00:29:35,670 du burde se en trykt for loop hvori 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 er alle på riktig måte for. 580 00:29:39,310 --> 00:29:43,410 >> Så vi har fått vår pseudo her. 581 00:29:43,410 --> 00:29:46,090 Ønsker noen to-- jeg bare kommer til å gå be om volunteers-- 582 00:29:46,090 --> 00:29:49,540 fortelle meg nøyaktig hva du skal skrive om vi vil, først, bare iterere 583 00:29:49,540 --> 00:29:52,840 ved begynnelsen av denne array? 584 00:29:52,840 --> 00:29:55,204 Hva er kodelinje jeg er sannsynligvis kommer til å trenge her? 585 00:29:55,204 --> 00:29:56,990 >> PUBLIKUM: [uhørbart] 586 00:29:56,990 --> 00:29:59,010 >> ANDI PENG: Ja, føler gratis to-- beklager, du 587 00:29:59,010 --> 00:30:02,318 trenger ikke å stå opp-- følelse fritt til å heve stemmen litt. 588 00:30:02,318 --> 00:30:08,190 >> PUBLIKUM: For int i lik 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI PENG: Ja, bra. 590 00:30:10,690 --> 00:30:15,220 >> PUBLIKUM: Jeg er mindre enn utvalg lengde. 591 00:30:15,220 --> 00:30:19,630 >> ANDI PENG: Så holde i tankene her, fordi vi 592 00:30:19,630 --> 00:30:23,060 ikke har en funksjon som forteller oss hvor lang en matrise, 593 00:30:23,060 --> 00:30:25,790 vi allerede har en verdi som lagrer det. 594 00:30:25,790 --> 00:30:27,920 Høyre? 595 00:30:27,920 --> 00:30:31,010 En annen ting å huske i mind-- i en matrise 596 00:30:31,010 --> 00:30:33,940 av ni verdier, hva er indekser? 597 00:30:33,940 --> 00:30:38,720 La oss bare si denne matrisen var 0 til 3. 598 00:30:38,720 --> 00:30:41,500 Du ser at den siste Indeksen er faktisk tre. 599 00:30:41,500 --> 00:30:45,530 Det er ikke fire, selv om det er fire verdier i matrisen. 600 00:30:45,530 --> 00:30:49,866 >> Så her må vi være veldig forsiktig av det vår tilstand for lengden 601 00:30:49,866 --> 00:30:50,490 kommer til å være. 602 00:30:50,490 --> 00:30:51,948 >> PUBLIKUM: Ville det ikke være n minus 1? 603 00:30:51,948 --> 00:30:54,440 ANDI PENG: Det kommer n minus en, akkurat. 604 00:30:54,440 --> 00:30:57,379 Gjør det fornuftig, hvorfor det er n minus en, alle? 605 00:30:57,379 --> 00:30:58,920 Det er fordi arrays er null-indeksert. 606 00:30:58,920 --> 00:31:02,010 De starter på 0 og kjøre opp til n minus en. 607 00:31:02,010 --> 00:31:03,210 Ja, det er litt vanskelig. 608 00:31:03,210 --> 00:31:03,730 OK. 609 00:31:03,730 --> 00:31:05,929 Og så-- 610 00:31:05,929 --> 00:31:08,054 PUBLIKUM: Isnt'1 at allerede tatt vare på selv, 611 00:31:08,054 --> 00:31:11,400 ved å bare ikke si "mindre enn eller lik "og bare si" mindre enn? " 612 00:31:11,400 --> 00:31:13,108 >> ANDI PENG: Det er en veldig godt spørsmål. 613 00:31:13,108 --> 00:31:13,630 Så, ja. 614 00:31:13,630 --> 00:31:17,410 Men også, slik at vi er implementere sjekker høyre, 615 00:31:17,410 --> 00:31:19,120 må du sammenligne to verdier. 616 00:31:19,120 --> 00:31:21,009 Slik at du faktisk ønsker å la "til" tom. 617 00:31:21,009 --> 00:31:23,050 Fordi hvis du sammenligner denne, er du ikke kommer 618 00:31:23,050 --> 00:31:25,530 har noe etter det å sammenligne med, ikke sant? 619 00:31:25,530 --> 00:31:27,460 Yeah. 620 00:31:27,460 --> 00:31:29,297 Så i ++. 621 00:31:29,297 --> 00:31:30,380 La oss legge våre parentes i. 622 00:31:30,380 --> 00:31:30,880 Uff da. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Flott. 625 00:31:34,710 --> 00:31:39,117 Så vi har i begynnelsen av vår ytre loop. 626 00:31:39,117 --> 00:31:41,450 Så nå er vi sannsynligvis vil opprette en variabel for å holde 627 00:31:41,450 --> 00:31:43,085 spor av den minste verdien, ikke sant? 628 00:31:43,085 --> 00:31:45,751 Ønsker noen å gi meg kodelinje som ville gjøre det? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Hva trenger vi hvis vi skal å ønske å lagre noe? 631 00:31:53,570 --> 00:31:55,047 >> Høyre. 632 00:31:55,047 --> 00:31:57,630 Kanskje et bedre navn for det ville be-- "temp" helt works-- 633 00:31:57,630 --> 00:32:00,655 kanskje en mer treffende navnet ville bli, hvis vi ønsker den minste value-- 634 00:32:00,655 --> 00:32:01,624 >> PUBLIKUM: Min. 635 00:32:01,624 --> 00:32:02,790 ANDI PENG: min, der vi går. 636 00:32:02,790 --> 00:32:05,230 min ville være bra. 637 00:32:05,230 --> 00:32:08,340 Og så her, hva gjør vi ønsker å initialisere den til? 638 00:32:08,340 --> 00:32:09,620 Dette er litt vanskelig. 639 00:32:09,620 --> 00:32:13,580 Fordi akkurat nå på begynnelsen av denne matrisen, 640 00:32:13,580 --> 00:32:15,730 du ikke har sett på noe, ikke sant? 641 00:32:15,730 --> 00:32:19,200 Så hva, automatisk, hvis vi er bare på i lik 0, 642 00:32:19,200 --> 00:32:22,302 hva ønsker vi å initial vår første minimumsverdi til? 643 00:32:22,302 --> 00:32:22,802 PUBLIKUM: i. 644 00:32:22,802 --> 00:32:24,790 ANDI PENG: i, akkurat. 645 00:32:24,790 --> 00:32:27,040 Christ, hvorfor vi ønsker initialisere det til jeg? 646 00:32:27,040 --> 00:32:28,510 >> PUBLIKUM: Fordi, vel, vi begynner med 0. 647 00:32:28,510 --> 00:32:31,660 Så fordi vi har ingenting å sammenligne det til, vil minimum ende opp som 0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI PENG: Nettopp. 649 00:32:32,451 --> 00:32:34,400 Så hun er helt riktig. 650 00:32:34,400 --> 00:32:36,780 Fordi vi har faktisk ikke sett på noe ennå, 651 00:32:36,780 --> 00:32:38,680 vi vet ikke hva vår minimumsverdi er. 652 00:32:38,680 --> 00:32:41,960 Vi ønsker å bare initialisere den til Jeg, som i dag, er rett her. 653 00:32:41,960 --> 00:32:44,750 Og som vi fortsetter å flytte ned denne matrisen, 654 00:32:44,750 --> 00:32:48,122 vi vil se at med hver ekstra pass, intervaller i. 655 00:32:48,122 --> 00:32:49,830 Og så på det punktet, Jeg er trolig kommer 656 00:32:49,830 --> 00:32:52,329 å ønske å være minimum, fordi det kommer til å bli hva 657 00:32:52,329 --> 00:32:54,520 er i begynnelsen av usortert array. 658 00:32:54,520 --> 00:32:55,270 Kjølig. 659 00:32:55,270 --> 00:32:58,720 >> Så nå ønsker vi å legge til en for loop her som er 660 00:32:58,720 --> 00:33:03,225 kommer til å iterere gjennom usorterte, eller resten av denne matrisen. 661 00:33:03,225 --> 00:33:05,808 Ønsker noen å gi meg en kodelinje som ville gjøre det? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- hva trenger vi her nede? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 Hva kommer til å gå i dette for loop? 666 00:33:18,820 --> 00:33:19,465 Yeah. 667 00:33:19,465 --> 00:33:21,590 PUBLIKUM: Så vi ønsker å har et annet heltall, 668 00:33:21,590 --> 00:33:25,080 fordi vi kjører gjennom resten i matrisen i stedet for den i, så kanskje 669 00:33:25,080 --> 00:33:25,760 j. 670 00:33:25,760 --> 00:33:27,301 >> ANDI PENG: Ja, høres j bra for meg. 671 00:33:27,301 --> 00:33:27,850 Er lik? 672 00:33:27,850 --> 00:33:33,930 >> PUBLIKUM: Så vil være i pluss 1, fordi du starter på neste verdi. 673 00:33:33,930 --> 00:33:40,395 Og deretter til den end-- så igjen, er j mindre enn n minus en, og deretter j ++. 674 00:33:40,395 --> 00:33:41,103 ANDI PENG: Great. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> Og så i her, vi kommer til å ønske å sjekke for å se om vår vilkåret er oppfylt, 677 00:33:52,750 --> 00:33:53,250 ikke sant? 678 00:33:53,250 --> 00:33:55,740 Fordi du ønsker å endre den laveste verdien 679 00:33:55,740 --> 00:33:58,700 hvis det er faktisk mindre enn hva du sammenligner det til, ikke sant? 680 00:33:58,700 --> 00:34:01,146 Så hva skal vi ønsker her inne? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Sjekk for å se. 683 00:34:04,897 --> 00:34:06,730 Hva slags statement vi sannsynligvis kommer 684 00:34:06,730 --> 00:34:08,389 ti vil bruke hvis vi ønsker å sjekke noe? 685 00:34:08,389 --> 00:34:09,360 >> PUBLIKUM: En hvis setningen. 686 00:34:09,360 --> 00:34:10,485 >> ANDI PENG: An hvis setningen. 687 00:34:10,485 --> 00:34:13,155 Så if-- og hva som kommer til å være betingelse av at vi ønsker inne 688 00:34:13,155 --> 00:34:13,988 av vår hvis setningen? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> PUBLIKUM: Hvis verdien av j er mindre enn verdien av I-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI PENG: Nettopp. 692 00:34:24,600 --> 00:34:27,480 Så if-- så denne matrisen kalles "array". 693 00:34:27,480 --> 00:34:27,980 Flott. 694 00:34:27,980 --> 00:34:30,465 Så hvis array-- hva var det? 695 00:34:30,465 --> 00:34:31,090 Si det igjen. 696 00:34:31,090 --> 00:34:39,590 >> PUBLIKUM: Hvis matrise-j er mindre enn matrise-i, så vi ville endre min. 697 00:34:39,590 --> 00:34:41,590 Så min ville være j. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI PENG: Betyr det fornuftig? 700 00:34:47,249 --> 00:34:48,670 OK. 701 00:34:48,670 --> 00:34:52,929 Og nå her nede, vi faktisk ønsker å gjennomføre swap, ikke sant? 702 00:34:52,929 --> 00:34:58,285 Så husker, i foredrag, som David, når han prøvde å bytte the-- hva som var 703 00:34:58,285 --> 00:34:59,996 it-- appelsinjuice og milk-- 704 00:34:59,996 --> 00:35:01,150 >> PUBLIKUM: Det var ekkelt. 705 00:35:01,150 --> 00:35:02,816 >> ANDI PENG: Ja, det var litt ekkelt. 706 00:35:02,816 --> 00:35:05,310 Men det var en ganske god konsept demonstrere tid. 707 00:35:05,310 --> 00:35:08,430 Så tenk på dine verdier her. 708 00:35:08,430 --> 00:35:10,794 Du har fått en rekke av min, en rekke i, 709 00:35:10,794 --> 00:35:12,460 eller hva vi prøvde å bytte her. 710 00:35:12,460 --> 00:35:15,310 Og har du sannsynligvis ikke kan helle dem inn hverandre samtidig, til høyre? 711 00:35:15,310 --> 00:35:17,180 Så hva skal vi til å trenge for å lage her 712 00:35:17,180 --> 00:35:19,126 for å bytte verdiene riktig? 713 00:35:19,126 --> 00:35:19,820 >> PUBLIKUM: En midlertidig variabel. 714 00:35:19,820 --> 00:35:21,370 >> ANDI PENG: En midlertidig variabel. 715 00:35:21,370 --> 00:35:22,570 Så la oss gjøre int temp. 716 00:35:22,570 --> 00:35:25,681 Se, dette ville være en bedre tid to-- Jøss, hva var det? 717 00:35:25,681 --> 00:35:26,180 OK. 718 00:35:26,180 --> 00:35:29,800 Så dette ville ha vært en bedre tid for å nevne variabelen "temp." 719 00:35:29,800 --> 00:35:30,730 Så la oss gjøre int temp. 720 00:35:30,730 --> 00:35:32,563 Hva skal vi satt temp lik her? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 PUBLIKUM: Min? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI PENG: Det er litt vanskelig. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 Det faktisk ikke saken i slutten. 727 00:35:44,880 --> 00:35:47,690 Det spiller ingen rolle hva For du velger å bytte i 728 00:35:47,690 --> 00:35:50,862 så lenge du gjør at du er holde styr på hva du bytte. 729 00:35:50,862 --> 00:35:52,250 >> PUBLIKUM: Det kan være matrise-i. 730 00:35:52,250 --> 00:35:53,666 >> ANDI PENG: Ja, la oss gjøre matrise-i. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 Og så hva er neste linje av koden vi ønsker å ha her? 733 00:35:59,305 --> 00:36:00,680 PUBLIKUM: array-i er lik matrise-j. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI PENG: Og til slutt? 736 00:36:08,070 --> 00:36:12,070 PUBLIKUM: array-j matrise-i er lik. 737 00:36:12,070 --> 00:36:14,525 Målgruppe: Eller matrise-j equals matrise-temp-- eller temp. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> ANDI PENG: OK. 740 00:36:19,430 --> 00:36:21,510 Så la oss kjøre dette og se hvis det kommer til å fungere. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Hvor er det som skjer? 743 00:36:39,335 --> 00:36:40,210 Å, det er et problem. 744 00:36:40,210 --> 00:36:44,320 Se, på linje 40, vi er prøver å bruke matrise-j? 745 00:36:44,320 --> 00:36:47,022 Men hvor kommer j bare eksistere i? 746 00:36:47,022 --> 00:36:48,402 >> PUBLIKUM: I for loop. 747 00:36:48,402 --> 00:36:49,110 ANDI PENG: Høyre. 748 00:36:49,110 --> 00:36:51,730 Så hva skal vi gjøre? 749 00:36:51,730 --> 00:36:53,170 >> PUBLIKUM: Definer det utenfor the-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 PUBLIKUM: Ja, jeg tror du har å bruke en annen hvis setningen, ikke sant? 752 00:37:00,610 --> 00:37:05,230 Så som, hvis minimum-- all right, la meg tenke. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI Peng: Guys, prøv å ta en titt La oss 755 00:37:09,990 --> 00:37:11,270 se, hva er det noe vi kan gjøre her? 756 00:37:11,270 --> 00:37:11,811 >> PUBLIKUM: OK. 757 00:37:11,811 --> 00:37:15,900 Så hvis minimum er ikke lik j-- så hvis minimum er fortsatt I-- 758 00:37:15,900 --> 00:37:17,570 da vi ikke ville ha til å bytte. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI PENG: Betyr det like jeg? 761 00:37:24,712 --> 00:37:25,920 Hva ønsker du å si her? 762 00:37:25,920 --> 00:37:30,494 >> PUBLIKUM: Eller ja, hvis minimum er ikke lik i, ja. 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 ANDI PENG: OK. 765 00:37:40,210 --> 00:37:42,040 Vel det løser, type, våre problemer. 766 00:37:42,040 --> 00:37:47,265 Men som fortsatt ikke løser problemet med hva som skjer hvis j-- siden j 767 00:37:47,265 --> 00:37:49,890 ikke eksisterer utenfor det, hva du vi ønsker å gjøre med det? 768 00:37:49,890 --> 00:37:50,698 Erklære den utenfor? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 La oss prøve å kjøre dette. 771 00:38:02,730 --> 00:38:04,435 UH oh. 772 00:38:04,435 --> 00:38:06,200 Vår liksom ikke fungerer. 773 00:38:06,200 --> 00:38:10,060 >> Som du kan se, vår første matrise hadde disse verdiene. 774 00:38:10,060 --> 00:38:14,800 Og etterpå det skal ha vært i en, to, tre, fire, fem, seks, syv, åtte, ni. 775 00:38:14,800 --> 00:38:15,530 Den funker ikke. 776 00:38:15,530 --> 00:38:16,030 Ahh. 777 00:38:16,030 --> 00:38:17,184 Hva skal vi gjøre? 778 00:38:17,184 --> 00:38:17,850 PUBLIKUM: Debug. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI PENG: Greit, kan vi prøve det. 781 00:38:23,370 --> 00:38:25,030 Vi kan feilsøke. 782 00:38:25,030 --> 00:38:26,042 Zoome ut litt. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 La oss sette vår stoppunkt. 785 00:38:33,656 --> 00:38:37,280 La oss gå like-- OK. 786 00:38:37,280 --> 00:38:40,444 >> Så fordi vi allerede vet at disse linjene, 15 gjennom 22, 787 00:38:40,444 --> 00:38:43,610 er working-- fordi alt jeg gjør er bare itera gjennom og printing-- 788 00:38:43,610 --> 00:38:45,406 Jeg kan gå videre og hoppe over dette. 789 00:38:45,406 --> 00:38:47,280 La oss starte på linje 25. 790 00:38:47,280 --> 00:38:48,712 Oop, la meg bli kvitt det. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> PUBLIKUM: Så stoppunkt er hvor debugging starter? 793 00:38:54,057 --> 00:38:54,890 ANDI PENG: Eller stopper. 794 00:38:54,890 --> 00:38:55,670 PUBLIKUM: Eller stopper. 795 00:38:55,670 --> 00:38:55,930 ANDI PENG: Yeah. 796 00:38:55,930 --> 00:38:58,640 Du kan sette flere stoppunkt og Det kan bare hoppe fra den ene til den andre. 797 00:38:58,640 --> 00:39:01,590 Men i dette tilfellet vet vi ikke der skjer det feil. 798 00:39:01,590 --> 00:39:03,780 Så vi bare ønsker å starte fra toppen og ned. 799 00:39:03,780 --> 00:39:05,020 Jepp. 800 00:39:05,020 --> 00:39:05,550 OK. 801 00:39:05,550 --> 00:39:08,460 >> Så denne linjen her, kan vi gå inn. 802 00:39:08,460 --> 00:39:11,499 Du kan se her nede, vi har en matrise. 803 00:39:11,499 --> 00:39:13,290 De er de verdier som befinner seg på matrisen. 804 00:39:13,290 --> 00:39:16,360 Ser du det, hvordan indeksen 0, det tilsvarer value-- oh, 805 00:39:16,360 --> 00:39:17,526 Jeg kommer til å prøve å zoome inn. 806 00:39:17,526 --> 00:39:20,650 Beklager, det er virkelig vanskelig til see-- på tabellindekser 0, 807 00:39:20,650 --> 00:39:24,090 vi har en verdi på 4 og da så videre og så videre. 808 00:39:24,090 --> 00:39:25,670 Vi har våre lokale variabler. 809 00:39:25,670 --> 00:39:28,570 Akkurat nå jeg er lik 0, som vi ønsker den skal være. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> Og så la oss holde tråkke gjennom. 812 00:39:33,690 --> 00:39:36,850 Våre minimum er lik 0, som vi også ønsker den skal være. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 Og så går vi inn vår andre for loop, hvis matrise-j er mindre enn matrise-i, 815 00:39:45,560 --> 00:39:46,380 som ikke var det. 816 00:39:46,380 --> 00:39:48,130 Så fikk du se hvordan som hoppet over det? 817 00:39:48,130 --> 00:39:52,430 >> PUBLIKUM: Så skal den hvis minimum, alt at-- bør ikke at 818 00:39:52,430 --> 00:39:55,424 være inne i den første for loop? 819 00:39:55,424 --> 00:39:57,340 ANDI PENG: Nei, fordi du fortsatt ønsker å teste. 820 00:39:57,340 --> 00:40:00,329 Du ønsker å gjøre en sammenligning hver tid, selv etter at du har kjørt gjennom den. 821 00:40:00,329 --> 00:40:02,620 Du trenger ikke bare ønsker å gjøre det på første pass-through. 822 00:40:02,620 --> 00:40:05,240 Du ønsker å gjøre det med hver ekstra pass igjen. 823 00:40:05,240 --> 00:40:07,198 Så du ønsker å se etter din tilstand inne. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Så vi skal bare fortsette å kjøre gjennom her. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Jeg skal gi dere et hint. 828 00:40:18,420 --> 00:40:23,910 Det har å gjøre med det faktum at når du sjekker din betinget, 829 00:40:23,910 --> 00:40:26,600 du ikke sjekker for riktig indeksen. 830 00:40:26,600 --> 00:40:32,510 Så akkurat nå er du sjekker for rekke indeks over j er mindre enn utvalg 831 00:40:32,510 --> 00:40:33,970 indeks over i. 832 00:40:33,970 --> 00:40:36,580 Men hva gjør du opp på begynnelsen av for loop? 833 00:40:36,580 --> 00:40:38,260 Er du ikke sette j lik jeg? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Ja, så vi kan faktisk avslutte debugger her. 836 00:40:45,415 --> 00:40:47,040 Så la oss ta en titt på vår pseudokode. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- vi kommer til å starter på jeg er lik 0. 839 00:40:52,580 --> 00:40:54,760 Vi kommer til å gå opp til n minus en. 840 00:40:54,760 --> 00:40:58,040 La oss sjekke, vi har det riktig? 841 00:40:58,040 --> 00:40:59,580 Jepp, det var rett. 842 00:40:59,580 --> 00:41:02,080 >> Så da inne her, vi er kommer til å lage en minimumsverdi 843 00:41:02,080 --> 00:41:03,630 og sette det lik i. 844 00:41:03,630 --> 00:41:04,950 Gjorde vi det? 845 00:41:04,950 --> 00:41:06,270 Jepp, gjorde det. 846 00:41:06,270 --> 00:41:10,430 Nå i vårt indre for loop, vi er kommer til å gjøre j lik jeg til n minus en. 847 00:41:10,430 --> 00:41:11,950 Gjorde vi det? 848 00:41:11,950 --> 00:41:15,540 Ja, vi gjorde det. 849 00:41:15,540 --> 00:41:19,922 >> Så imidlertid hva vi sammenligner her? 850 00:41:19,922 --> 00:41:20,925 >> PUBLIKUM: j pluss 1. 851 00:41:20,925 --> 00:41:21,716 ANDI PENG: Nettopp. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 Og så kommer du til å ønske å sette minst en lik j + 1 tillegg. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Så jeg gikk gjennom som virkelig raskt. 856 00:41:32,640 --> 00:41:36,190 Har dere forstår hvorfor det er j pluss en? 857 00:41:36,190 --> 00:41:36,890 OK. 858 00:41:36,890 --> 00:41:40,700 >> Så i arrayet, i din første går gjennom, 859 00:41:40,700 --> 00:41:44,850 din for loop, for int jeg er lik 0, la oss bare 860 00:41:44,850 --> 00:41:46,740 anta at dette har ikke blitt endret ennå. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 Vi har en rekke, helt, bare fire usorterte elementer, ikke sant? 863 00:41:56,760 --> 00:42:00,760 Så vi ønsker å initial jeg lik 0. 864 00:42:00,760 --> 00:42:03,650 Og jeg kommer til å like kjøre gjennom denne sløyfen. 865 00:42:03,650 --> 00:42:08,560 Og så i den første pass, skal vi å klargjøre en variabel kalt "min" 866 00:42:08,560 --> 00:42:11,245 som også er lik i, fordi vi ikke har en minimumsverdi. 867 00:42:11,245 --> 00:42:12,870 Så det er for tiden lik 0 i tillegg. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 Og så kommer vi til å gå gjennom. 870 00:42:17,640 --> 00:42:19,270 Og vi ønsker å reagere igjen. 871 00:42:19,270 --> 00:42:22,900 Nå som vi har funnet hva vår minimum er, vi ønsker å iterere gjennom 872 00:42:22,900 --> 00:42:25,190 på nytt for å se om det er å sammenligne, ikke sant? 873 00:42:25,190 --> 00:42:40,440 Så j, her kommer til lik i, som er 0. 874 00:42:40,440 --> 00:42:46,320 Og så hvis matrisen j pluss jeg, som er den som er neste over, som mindre 875 00:42:46,320 --> 00:42:49,270 enn hva din nåværende minste verdien er, du ønsker å bytte. 876 00:42:49,270 --> 00:42:56,850 >> Så la oss bare si at vi har fikk, som, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Akkurat nå er jeg lik 0 og j er lik 0. 878 00:43:01,610 --> 00:43:05,210 Og det er vår minimumsverdien. 879 00:43:05,210 --> 00:43:09,950 Hvis matrise-j pluss I-- så hvis den ene det er etter det vi ser på 880 00:43:09,950 --> 00:43:13,450 er større enn den før det, det kommer til å bli minimum. 881 00:43:13,450 --> 00:43:18,120 >> Så her ser vi at 5 ikke er mindre enn det. 882 00:43:18,120 --> 00:43:19,730 Så det kommer til å være fem. 883 00:43:19,730 --> 00:43:23,580 Vi ser at en er mindre enn to, ikke sant? 884 00:43:23,580 --> 00:43:32,970 Så nå vet vi at vår minste er kommer til å være indeksverdien på 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Yeah? 886 00:43:34,030 --> 00:43:39,170 Og så når du kommer ned hit, du kan bytte de riktige verdiene. 887 00:43:39,170 --> 00:43:42,610 >> Så når dere var bare å ha det j før, ble du ikke ser på den ene 888 00:43:42,610 --> 00:43:43,260 etter den. 889 00:43:43,260 --> 00:43:44,520 Du var ute på den samme verdi, som 890 00:43:44,520 --> 00:43:46,290 er grunnen til at det rett og slett ikke å gjøre noe. 891 00:43:46,290 --> 00:43:49,721 Betyr det fornuftig for alle, hvorfor vi trengte som pluss en det? 892 00:43:49,721 --> 00:43:50,220 OK. 893 00:43:50,220 --> 00:43:53,345 La oss nå bare kjøre gjennom det å gjøre at resten av koden er korrekt. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Hvorfor er det som skjer? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ah, det er min rett her. 898 00:44:16,364 --> 00:44:17,780 Vi var sammenligne feil verdi. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 Å nei. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> Oh yeah, her nede var vi bytte feil verdier også. 903 00:44:33,482 --> 00:44:34,940 Fordi vi var ute på i og j. 904 00:44:34,940 --> 00:44:36,440 De er de vi sjekker. 905 00:44:36,440 --> 00:44:39,160 Vi har faktisk ønsker å bytte minimum, den nåværende minimum, 906 00:44:39,160 --> 00:44:40,550 med hva den ene utenfor er. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 Og som dere kan se ned her har vi en sortert array. 909 00:45:05,402 --> 00:45:07,110 Det hadde bare å gjøre med det faktum at når 910 00:45:07,110 --> 00:45:09,350 vi sjekket den verdier vi sammenligne, 911 00:45:09,350 --> 00:45:11,226 Vi var ikke ute på de rette verdiene. 912 00:45:11,226 --> 00:45:13,850 Vi var ute på den samme her, faktisk ikke bytte den. 913 00:45:13,850 --> 00:45:17,135 Du må se på den ene siden til det og deretter kan du bytte. 914 00:45:17,135 --> 00:45:19,260 Så det er det var slags avlytting vår kode før. 915 00:45:19,260 --> 00:45:22,460 Og hva jeg gjorde her er alt debugger kunne ha gjort for deg 916 00:45:22,460 --> 00:45:23,810 Jeg bare gjorde det på bord, fordi det er enklere 917 00:45:23,810 --> 00:45:26,320 å se heller enn å prøve for å zoome inn på debugger. 918 00:45:26,320 --> 00:45:29,391 Betyr det fornuftig for alle? 919 00:45:29,391 --> 00:45:29,890 Kjølig. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Greit. 922 00:45:35,410 --> 00:45:41,070 Vi kan gå videre til å snakke om asymptotisk notasjon, som 923 00:45:41,070 --> 00:45:44,580 er bare en fancy måte å si det runtimes av alle disse former. 924 00:45:44,580 --> 00:45:47,650 Så jeg vet David, i foredrag, berørt runtimes. 925 00:45:47,650 --> 00:45:52,124 Og han gikk gjennom hele formel hvordan å beregne kjøretider. 926 00:45:52,124 --> 00:45:53,040 Ingen bekymringer om at. 927 00:45:53,040 --> 00:45:54,660 Hvis du er virkelig nysgjerrig på hvordan det fungerer, 928 00:45:54,660 --> 00:45:55,810 gjerne snakke med meg etter pkt. 929 00:45:55,810 --> 00:45:57,560 Vi kan gå gjennom formlene sammen. 930 00:45:57,560 --> 00:46:00,689 Men alle dere må virkelig vet er at n squared vel 2 931 00:46:00,689 --> 00:46:01,980 er det samme som n squared. 932 00:46:01,980 --> 00:46:04,710 Fordi det største antallet, eksponenten, vokser mest. 933 00:46:04,710 --> 00:46:06,590 Og så for vårt formål, alt vi bryr oss om 934 00:46:06,590 --> 00:46:09,470 er det gigantiske tall som er økende. 935 00:46:09,470 --> 00:46:13,340 >> Så hva er den beste saken runtime av utvalget slag? 936 00:46:13,340 --> 00:46:15,830 Hvis du kommer til å ha å iterere gjennom en liste 937 00:46:15,830 --> 00:46:18,712 og deretter iterere gjennom resten av den listen, 938 00:46:18,712 --> 00:46:20,420 hvor mange ganger er Skal du sannsynligvis, 939 00:46:20,420 --> 00:46:24,612 i verste case-- i beste fall sorry-- kjøre gjennom? 940 00:46:24,612 --> 00:46:27,070 Kanskje bedre spørsmål er å spørre, hva er det verste tilfellet 941 00:46:27,070 --> 00:46:28,153 runtime av utvalget slag. 942 00:46:28,153 --> 00:46:29,366 PUBLIKUM: n squared. 943 00:46:29,366 --> 00:46:30,740 ANDI PENG: Det er n squared, ikke sant. 944 00:46:30,740 --> 00:46:36,986 Så en enkel måte å tenke på dette er like, helst du har to nestet for løkker, 945 00:46:36,986 --> 00:46:38,110 det kommer til å bli n squared. 946 00:46:38,110 --> 00:46:40,386 Fordi ikke bare er du går gjennom nok en gang, 947 00:46:40,386 --> 00:46:42,260 du må gå tilbake rundt og kjøre gjennom det 948 00:46:42,260 --> 00:46:44,980 nok en gang inne for hver verdi. 949 00:46:44,980 --> 00:46:48,640 Så i så fall kjører du n ganger n squared, som er-- beklager, 950 00:46:48,640 --> 00:46:50,505 n ganger n, noe som tilsvarer n squared. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> Og sort er også litt unik i den forstand 953 00:46:56,360 --> 00:46:59,774 at det ikke spiller noen rolle om disse Verdiene er allerede i orden. 954 00:46:59,774 --> 00:47:01,440 Det er fortsatt kommer til å kjøre gjennom anyways. 955 00:47:01,440 --> 00:47:03,872 La oss bare si at dette var en, to, tre, fire. 956 00:47:03,872 --> 00:47:07,080 Uavhengig av hvorvidt det var i rekkefølge, ville det fortsatt ha løp gjennom 957 00:47:07,080 --> 00:47:08,620 og likevel kontrollert minimumsverdien. 958 00:47:08,620 --> 00:47:10,100 Det ville ha gjort samme antall kontroller 959 00:47:10,100 --> 00:47:12,780 hver gang, selv om det faktisk ikke røre noe. 960 00:47:12,780 --> 00:47:16,940 >> Slik at i et slikt tilfelle, det beste og verste runtimes er faktisk tilsvarende. 961 00:47:16,940 --> 00:47:19,160 Så den forventede runtime av utvalget sortere, 962 00:47:19,160 --> 00:47:23,790 som vi utpeke med symbolet av theta, theta, i dette tilfellet 963 00:47:23,790 --> 00:47:24,790 vil også bli n squared. 964 00:47:24,790 --> 00:47:26,480 Alle tre av disse ville bli n squared. 965 00:47:26,480 --> 00:47:29,653 Er alle klare på hvorfor runtime er n squared? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Greit. 968 00:47:33,980 --> 00:47:39,120 Så jeg skal bare raskt kjøre gjennom resten av den slags. 969 00:47:39,120 --> 00:47:41,137 Algoritmen for boble sort-- huske, 970 00:47:41,137 --> 00:47:43,220 Dette var den første David gikk over i forelesning. 971 00:47:43,220 --> 00:47:46,000 Hovedsak, du går gjennom hele listen 972 00:47:46,000 --> 00:47:48,950 og du swap-- du bare sammenligne to om gangen. 973 00:47:48,950 --> 00:47:51,350 Og hvis man er større, enn du bare bytte dem. 974 00:47:51,350 --> 00:47:53,590 Så hvis disse er større, vil du bytte. 975 00:47:53,590 --> 00:47:56,180 Jeg har offisielt her. 976 00:47:56,180 --> 00:47:59,100 >> Så la oss bare si at du hadde 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Du vil sammenligne åtte og en 6. 978 00:48:00,571 --> 00:48:01,570 Du trenger for å bytte dem. 979 00:48:01,570 --> 00:48:02,610 Du vil sammenligne åtte og en 4. 980 00:48:02,610 --> 00:48:03,609 Du trenger for å bytte dem. 981 00:48:03,609 --> 00:48:07,000 Hvis du må bytte den 8 og 2, endre dem også. 982 00:48:07,000 --> 00:48:10,760 Så i en slik følelse, kan du se, spilles ut over en lang tidsperiode, 983 00:48:10,760 --> 00:48:13,730 hvordan verdiene slags boble til endene, noe som er grunnen til at vi kaller det 984 00:48:13,730 --> 00:48:15,320 boble slag. 985 00:48:15,320 --> 00:48:19,950 >> Vi ville bare kjøre gjennom på nytt på vår andre pass, og vår tredje pass, 986 00:48:19,950 --> 00:48:21,150 og vår fjerde runden. 987 00:48:21,150 --> 00:48:25,820 Hovedsak, boble liksom bare renner til du ikke gjør noen flere bytteavtaler. 988 00:48:25,820 --> 00:48:31,109 Så i den forstand, dette er bare den generelle pseudokode for det. 989 00:48:31,109 --> 00:48:32,650 Ingen grunn til bekymring, disse vil alle være online. 990 00:48:32,650 --> 00:48:34,990 Vi trenger ikke å faktisk gå over dette. 991 00:48:34,990 --> 00:48:38,134 >> Vi bare initial en teller variabel som starter på 0. 992 00:48:38,134 --> 00:48:39,800 Og vi iterere gjennom hele array. 993 00:48:39,800 --> 00:48:43,420 Og hvis en verdi er-- om dette verdien er større enn denne verdien, 994 00:48:43,420 --> 00:48:44,610 du kommer til å bytte dem. 995 00:48:44,610 --> 00:48:46,860 Og da er du bare kommer til å holde det gående. 996 00:48:46,860 --> 00:48:47,970 Og du kommer til å telle. 997 00:48:47,970 --> 00:48:50,845 Og du bare kommer til å fortsette å gjøre dette mens telleren er større 998 00:48:50,845 --> 00:48:53,345 enn 0, hvilket betyr at hver gang du må bytte, 999 00:48:53,345 --> 00:48:55,220 du vet at du vil gå tilbake og sjekke igjen. 1000 00:48:55,220 --> 00:48:59,510 Du ønsker å holde kontroll før du vet at du ikke trenger å bytte lenger. 1001 00:48:59,510 --> 00:49:05,570 >> Så hva er det beste og verste case tider for boble liksom? 1002 00:49:05,570 --> 00:49:09,300 Og hint-- dette er faktisk annerledes fra utvalget slag i den forstand 1003 00:49:09,300 --> 00:49:11,810 at disse to svarene er ikke det samme. 1004 00:49:11,810 --> 00:49:14,709 Tenk på hva som ville skje i en sak dersom det var allerede sortert. 1005 00:49:14,709 --> 00:49:16,500 Og tenke på hva ville skje hvis det var 1006 00:49:16,500 --> 00:49:18,372 i det tilfelle hvor det ikke ble sortert. 1007 00:49:18,372 --> 00:49:20,580 Og du kan slags kjøre gjennom hvorfor det skjer. 1008 00:49:20,580 --> 00:49:22,954 Jeg skal gi dere, liker, 30 sekunder på å tenke på det. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> OK. 1011 00:49:53,540 --> 00:49:57,462 Har noen en gjetning på hva worst case runtime av boble typen er? 1012 00:49:57,462 --> 00:49:57,962 Yeah. 1013 00:49:57,962 --> 00:50:07,810 >> PUBLIKUM: Ville det være, som, n ganger n minus 1 eller noe sånt? 1014 00:50:07,810 --> 00:50:10,650 Liker, hver gang det kjøres, det er bare, som, en swap mindre 1015 00:50:10,650 --> 00:50:10,960 at uansett hva det var. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI PENG: Ja, så du er helt rett. 1017 00:50:12,668 --> 00:50:15,940 Og dette er en sak der din Svaret var faktisk mer komplisert 1018 00:50:15,940 --> 00:50:17,240 enn det vi trenger for å gi. 1019 00:50:17,240 --> 00:50:19,772 Så det kommer til å run-- jeg er kommer til å slette alt dette her. 1020 00:50:19,772 --> 00:50:20,480 Er alle gode? 1021 00:50:20,480 --> 00:50:21,869 Kan jeg slette denne? 1022 00:50:21,869 --> 00:50:22,368 OK. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Du kommer til å kjøre gjennom n ganger den første gangen, ikke sant? 1025 00:50:30,320 --> 00:50:33,200 Og de kommer til å kjøre gjennom n minus en annen gang, ikke sant? 1026 00:50:33,200 --> 00:50:37,130 Og så kommer dere til å holde kommer, n min 2, et cetera. 1027 00:50:37,130 --> 00:50:40,210 David gjorde dette i et foredrag, hvor, hvis du har lagt opp alle disse verdiene, 1028 00:50:40,210 --> 00:50:48,080 du får noe som er like-- yeah-- over 2, som i det vesentlige bare reduserer 1029 00:50:48,080 --> 00:50:49,784 ned til n squared. 1030 00:50:49,784 --> 00:50:51,700 Du kommer til å få en rare brøkdel der inne. 1031 00:50:51,700 --> 00:50:53,892 Og så bare vet at n squared alltid 1032 00:50:53,892 --> 00:50:55,350 forrang brøkdel. 1033 00:50:55,350 --> 00:50:58,450 Og så i dette tilfellet, det verste runtime ville bli n squared. 1034 00:50:58,450 --> 00:51:00,210 Hvis det var i synkende rekkefølge, tror du 1035 00:51:00,210 --> 00:51:02,530 har å gjøre en swap hver eneste gang. 1036 00:51:02,530 --> 00:51:05,170 >> Hva ville være, potensielt, beste fall runtime? 1037 00:51:05,170 --> 00:51:08,580 La oss bare si, hvis listen var allerede i orden, hva ville runtime være? 1038 00:51:08,580 --> 00:51:09,565 >> PUBLIKUM: n. 1039 00:51:09,565 --> 00:51:10,690 ANDI PENG: Det er n, akkurat. 1040 00:51:10,690 --> 00:51:11,600 Og hvorfor er det n? 1041 00:51:11,600 --> 00:51:13,850 PUBLIKUM: Fordi du bare må sjekke på hver gang. 1042 00:51:13,850 --> 00:51:14,770 ANDI PENG: Nettopp. 1043 00:51:14,770 --> 00:51:17,150 Så på best mulig runtime, Hvis denne listen var allerede 1044 00:51:17,150 --> 00:51:20,270 sorted-- la oss si 1, 2, 3, 4-- deg ville bare gå gjennom, ville du sjekker, 1045 00:51:20,270 --> 00:51:21,720 du ville se, oh, de alle panorere. 1046 00:51:21,720 --> 00:51:22,636 Jeg trengte ikke å bytte. 1047 00:51:22,636 --> 00:51:23,370 Jeg er ferdig. 1048 00:51:23,370 --> 00:51:26,500 Så i dette tilfellet, er det bare n eller antall skritt du bare 1049 00:51:26,500 --> 00:51:29,870 måtte sjekke inn den første listen. 1050 00:51:29,870 --> 00:51:33,990 >> Og etter vi nå treffer innsetting sortere, der 1051 00:51:33,990 --> 00:51:39,260 algoritmen er vesentlig å skille det inn i en sortert og usortert del. 1052 00:51:39,260 --> 00:51:42,810 Og så en etter en, de usorterte verdiene er 1053 00:51:42,810 --> 00:51:46,880 satt inn i deres aktuelle posisjoner i begynnelsen av listen. 1054 00:51:46,880 --> 00:51:52,120 >> Så for eksempel, har vi en listen 3, 5, 2, 6, 4 på nytt. 1055 00:51:52,120 --> 00:51:54,750 Vi vet at det er i dag usortert fordi vi har bare 1056 00:51:54,750 --> 00:51:57,030 begynte å se på det. 1057 00:51:57,030 --> 00:52:00,610 Vi tar en titt og vi vet at den første verdien er sortert, ikke sant? 1058 00:52:00,610 --> 00:52:04,190 Hvis du bare ser på en rekke størrelse ett, vet du at det er sortert. 1059 00:52:04,190 --> 00:52:08,230 >> Så da vet vi at andre fire er usortert. 1060 00:52:08,230 --> 00:52:10,980 Vi går gjennom, og vi ser at verdien. 1061 00:52:10,980 --> 00:52:11,730 La oss gå tilbake. 1062 00:52:11,730 --> 00:52:13,130 Se at verdien av 5? 1063 00:52:13,130 --> 00:52:14,110 Vi tar en titt på den. 1064 00:52:14,110 --> 00:52:15,204 Vi sammenligne det med tre. 1065 00:52:15,204 --> 00:52:17,870 Vi vet at det er større enn 3, så vi vet at det er sortert. 1066 00:52:17,870 --> 00:52:22,940 Så nå vet vi at de to første sorteres og de tre siste er det ikke. 1067 00:52:22,940 --> 00:52:24,270 >> Vi tar en titt på to. 1068 00:52:24,270 --> 00:52:25,720 Vi først sjekke det med fem. 1069 00:52:25,720 --> 00:52:26,700 Det er mindre enn 5? 1070 00:52:26,700 --> 00:52:27,240 Det er ikke. 1071 00:52:27,240 --> 00:52:29,510 Så vi må holde utkikk ned. 1072 00:52:29,510 --> 00:52:30,940 Så du sjekke to av tre. 1073 00:52:30,940 --> 00:52:31,850 Er det mindre enn? 1074 00:52:31,850 --> 00:52:32,350 Nei. 1075 00:52:32,350 --> 00:52:35,430 Så du vet en 2 må settes inn i den fremre og 3 og 5 1076 00:52:35,430 --> 00:52:38,200 begge må bli skjøvet ut. 1077 00:52:38,200 --> 00:52:42,190 Gjøre dette igjen med 6 og 4. 1078 00:52:42,190 --> 00:52:48,962 Og vi bare fortsette å se hovedsak, der vi bare sjekke, sjekk, sjekk. 1079 00:52:48,962 --> 00:52:51,170 Og før det er i riktig posisjon, vi slags bare 1080 00:52:51,170 --> 00:52:54,890 sett det inn i riktig posisjon, som er der navnet på den kom fra. 1081 00:52:54,890 --> 00:52:59,830 >> Så det er bare algoritmen, pseudokode per se, type, 1082 00:52:59,830 --> 00:53:04,990 om hvordan vi skulle gjennomføre et innførings sort. 1083 00:53:04,990 --> 00:53:05,954 Pseudokode er her. 1084 00:53:05,954 --> 00:53:06,620 Det handler online. 1085 00:53:06,620 --> 00:53:10,720 Ingen grunn til bekymring hvis dere er prøver å kopiere dette ned. 1086 00:53:10,720 --> 00:53:14,500 Så igjen, samme question-- hva ville være den beste og verste runtimes 1087 00:53:14,500 --> 00:53:16,120 for innsetting slag? 1088 00:53:16,120 --> 00:53:17,750 Det er svært lik den siste spørsmålet. 1089 00:53:17,750 --> 00:53:20,479 Jeg skal gi dere, liker, 30 sekunder på å tenke på dette også. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> OK Er det noen som ønsker å gi meg det verste runtime? 1092 00:53:50,071 --> 00:53:50,570 Yeah. 1093 00:53:50,570 --> 00:53:51,490 >> PUBLIKUM: n squared. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI PENG: Det er n squared. 1095 00:53:52,573 --> 00:53:53,730 Og hvorfor er det n squared? 1096 00:53:53,730 --> 00:53:57,562 >> PUBLIKUM: Fordi i omvendt rekkefølge, har du 1097 00:53:57,562 --> 00:54:02,619 for å gå gjennom n ganger n, som er-- 1098 00:54:02,619 --> 00:54:03,660 ANDI PENG: Ja, akkurat. 1099 00:54:03,660 --> 00:54:06,610 Så samme som i boblen slag. 1100 00:54:06,610 --> 00:54:08,720 Hvis denne listen er i synkende rekkefølge, er du 1101 00:54:08,720 --> 00:54:11,240 nødt til å sjekke første gang. 1102 00:54:11,240 --> 00:54:13,470 Og deretter med hver tilleggsverdi, er du 1103 00:54:13,470 --> 00:54:16,390 nødt til å sjekke det mot hver enkelt verdi, ikke sant? 1104 00:54:16,390 --> 00:54:20,290 Og så helt, du kommer til å gjøre En N pass ganger en annen n pass, som 1105 00:54:20,290 --> 00:54:21,750 er n squared. 1106 00:54:21,750 --> 00:54:22,860 Hva om den beste saken? 1107 00:54:22,860 --> 00:54:24,360 Yeah. 1108 00:54:24,360 --> 00:54:28,840 >> PUBLIKUM: n minus en, fordi første er allerede squared. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI PENG: Så nær. 1110 00:54:30,270 --> 00:54:31,850 Svaret er faktisk n. 1111 00:54:31,850 --> 00:54:37,189 Fordi mens den første er sorteres, kan det ikke det actually-- 1112 00:54:37,189 --> 00:54:38,980 vi bare lucked ut, i som eksempel at to 1113 00:54:38,980 --> 00:54:40,930 tilfeldigvis var det minste tallet. 1114 00:54:40,930 --> 00:54:43,680 Men det vil ikke alltid være tilfelle. 1115 00:54:43,680 --> 00:54:48,040 Hvis to allerede er sortert i begynnelsen men du ser, og det er en en her, 1116 00:54:48,040 --> 00:54:49,144 1 kommer til å støte den. 1117 00:54:49,144 --> 00:54:51,060 Og det kommer til å ende opp med å bli dunket anyways. 1118 00:54:51,060 --> 00:54:56,250 >> Så i beste fall det er faktisk bare skal være n. 1119 00:54:56,250 --> 00:54:59,090 Hvis du har en, to, tre, 4, 5, 6, 7, 8, er du 1120 00:54:59,090 --> 00:55:00,940 kommer til å kjøre gjennom at hele listen en gang 1121 00:55:00,940 --> 00:55:03,430 for å sjekke om alt er i orden. 1122 00:55:03,430 --> 00:55:07,390 Er alle klare på løping tider utvalg så vel? 1123 00:55:07,390 --> 00:55:09,960 Jeg vet at jeg kommer gjennom disse virkelig fort. 1124 00:55:09,960 --> 00:55:13,330 Men bare vet at hvis du kjenner generelle konsepter, bør du være god. 1125 00:55:13,330 --> 00:55:16,070 OK. 1126 00:55:16,070 --> 00:55:19,790 Så jeg vil bare gi dere kanskje, som, et minutt til å snakke med dine naboer 1127 00:55:19,790 --> 00:55:21,890 på hva som er bare noen av de viktigste forskjellene 1128 00:55:21,890 --> 00:55:23,540 mellom disse typer slag. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Vi vil gå over det snart. 1131 00:56:25,570 --> 00:56:26,444 PUBLIKUM: Oh, OK. 1132 00:56:26,444 --> 00:56:27,320 ANDI PENG: Yeah. 1133 00:56:27,320 --> 00:56:28,380 OK. 1134 00:56:28,380 --> 00:56:33,420 Cool, la oss reconvene som klasse. 1135 00:56:33,420 --> 00:56:34,330 OK. 1136 00:56:34,330 --> 00:56:37,579 Så dette var litt av en åpent spørsmål i den forstand 1137 00:56:37,579 --> 00:56:39,120 at det er mange svar på dem. 1138 00:56:39,120 --> 00:56:40,746 Og vi vil gå over noen av dem kort. 1139 00:56:40,746 --> 00:56:43,411 Jeg ville bare komme dere tenke på hva differensiert 1140 00:56:43,411 --> 00:56:44,530 alle tre typer slag. 1141 00:56:44,530 --> 00:56:47,440 Og jeg har hørt, også, en stor question-- hva betyr fusjonere slags gjøre? 1142 00:56:47,440 --> 00:56:50,110 Stort spørsmål, fordi det er hva vi dekker neste. 1143 00:56:50,110 --> 00:56:52,850 >> Så fusjonere typen er en sort som fungerer 1144 00:56:52,850 --> 00:56:56,100 veldig forskjellig fra de andre former. 1145 00:56:56,100 --> 00:56:58,180 Som dere kan see-- gjorde David som demo 1146 00:56:58,180 --> 00:57:01,130 hvor han hadde alle de kule lyder av å se hvordan flette 1147 00:57:01,130 --> 00:57:04,010 slags løp, som, uendelig raskere enn de to andre typer? 1148 00:57:04,010 --> 00:57:04,510 OK. 1149 00:57:04,510 --> 00:57:07,580 Så det er fordi flettingen sorter implementerer at skillet 1150 00:57:07,580 --> 00:57:11,020 og erobre konsept som vi har snakket om mye i forelesning. 1151 00:57:11,020 --> 00:57:14,550 I den forstand at vi liker å jobbe smartere, ikke hardere, når du deler 1152 00:57:14,550 --> 00:57:18,120 og erobre problemer, og bryte dem ned, og deretter sette dem sammen, 1153 00:57:18,120 --> 00:57:19,930 gode ting alltid skje. 1154 00:57:19,930 --> 00:57:21,960 >> Så måten fusjonere sorter hovedsak fungerer 1155 00:57:21,960 --> 00:57:24,660 er at det skiller en usortert array i halvparten. 1156 00:57:24,660 --> 00:57:26,500 Og så er det nødt to halvdeler av arrays. 1157 00:57:26,500 --> 00:57:28,220 Og det bare sorterer de to halvdelene. 1158 00:57:28,220 --> 00:57:31,750 Det holder bare å dele i to, i halvparten, i to før alt er sortert 1159 00:57:31,750 --> 00:57:33,680 og deretter rekursivt setter det hele sammen. 1160 00:57:33,680 --> 00:57:36,550 >> Så det er egentlig abstrakte. 1161 00:57:36,550 --> 00:57:38,750 Så dette er bare litt av pseudokode. 1162 00:57:38,750 --> 00:57:41,040 Betyr det fornuftig i måten den kjører? 1163 00:57:41,040 --> 00:57:43,870 Så la oss bare si at du har en utvalg av n elementer, ikke sant? 1164 00:57:43,870 --> 00:57:45,450 Hvis n er mindre enn 2, kan du gå tilbake. 1165 00:57:45,450 --> 00:57:49,040 Fordi du vet at hvis det er bare én ting, må det være sortert. 1166 00:57:49,040 --> 00:57:52,600 Else, du sortere venstre halvdel, og deretter sortere høyre halvdel, 1167 00:57:52,600 --> 00:57:54,140 og deretter flette. 1168 00:57:54,140 --> 00:57:56,979 >> Så mens det ser veldig lett, i virkeligheten, tenker det er 1169 00:57:56,979 --> 00:58:00,270 slags vanskelig. Fordi du er som, vel, det er slags kjører på seg selv. 1170 00:58:00,270 --> 00:58:00,769 Høyre? 1171 00:58:00,769 --> 00:58:02,430 Det kjører på seg selv. 1172 00:58:02,430 --> 00:58:05,479 Så i den forstand, rørte David ved rekursjon i klassen. 1173 00:58:05,479 --> 00:58:07,270 Og det er et konsept vi skal snakke om mer. 1174 00:58:07,270 --> 00:58:11,430 Det er som dette, disse to linjene her, er faktisk akkurat det programmet 1175 00:58:11,430 --> 00:58:13,860 fortelle den til å kjøre seg selv med forskjellig inngang. 1176 00:58:13,860 --> 00:58:17,230 Så i stedet for å kjøre selv med helheten av n elementer, 1177 00:58:17,230 --> 00:58:20,530 du kan bryte det ned i venstre halvdel og høyre halvdel 1178 00:58:20,530 --> 00:58:22,680 og deretter kjøre den på nytt. 1179 00:58:22,680 --> 00:58:26,050 >> Og så får vi se på det visuelt, fordi jeg er en visuell elev. 1180 00:58:26,050 --> 00:58:27,270 Det fungerer bedre for meg. 1181 00:58:27,270 --> 00:58:29,890 Så skal vi se på et visuelt eksempel her. 1182 00:58:29,890 --> 00:58:36,237 >> La oss si at vi har en matrise, seks elementer, 3, 5, 2, 6, 4, 1, ikke sortert. 1183 00:58:36,237 --> 00:58:37,820 Greit, det er mye på denne siden. 1184 00:58:37,820 --> 00:58:43,179 Så hvis dere kan se på første trinn her, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 du kan dele den i to. 1186 00:58:44,220 --> 00:58:45,976 Du har 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Du vet at disse aren't-- deg vet ikke om de er sortert eller ikke, 1188 00:58:48,850 --> 00:58:52,517 så du holder bryte dem ned, i to, i to, i to, til slutt, 1189 00:58:52,517 --> 00:58:53,600 du bare har ett element. 1190 00:58:53,600 --> 00:58:56,790 Og ett element er alltid sortert, ikke sant? 1191 00:58:56,790 --> 00:59:01,560 >> Så vi vet at 3, 5, 2, 4, 6, 1, av seg selv, er sortert. 1192 00:59:01,560 --> 00:59:05,870 Og nå kan vi sette dem sammen igjen. 1193 00:59:05,870 --> 00:59:07,510 Så vi vet at 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Vi setter dem sammen. 1195 00:59:08,510 --> 00:59:09,617 Vi vet at det er sortert. 1196 00:59:09,617 --> 00:59:10,450 De 2 er fortsatt der. 1197 00:59:10,450 --> 00:59:11,830 Vi kan sette 4 og 6 sammen. 1198 00:59:11,830 --> 00:59:13,996 Vi vet at det er sortert, så vi sette det sammen. 1199 00:59:13,996 --> 00:59:14,940 Og en er der. 1200 00:59:14,940 --> 00:59:18,720 >> Og så kan du bare se på disse to halvdeler her. 1201 00:59:18,720 --> 00:59:21,300 Du har 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Du kan bare sammenligne begynnelsen av alt. 1203 00:59:23,465 --> 00:59:26,340 Fordi du vet at dette er sortert og du vet at det er sortert. 1204 00:59:26,340 --> 00:59:29,360 Så da kan du ikke engang å sammenligne 5, du bare sammenligne 3. 1205 00:59:29,360 --> 00:59:32,070 Og 2 er mindre enn 3, så Kjenner du to må gå til slutt. 1206 00:59:32,070 --> 00:59:33,120 >> Samme om det. 1207 00:59:33,120 --> 00:59:34,740 Den en må gå her. 1208 00:59:34,740 --> 00:59:37,330 Og så når du går for å sette disse to verdier sammen, 1209 00:59:37,330 --> 00:59:39,950 du vet at dette er sortert og du vet at det er sortert. 1210 00:59:39,950 --> 00:59:43,240 Så da en og 2, at en er mindre enn 2. 1211 00:59:43,240 --> 00:59:45,570 Som forteller deg at en skal gå på slutten av denne 1212 00:59:45,570 --> 00:59:47,480 uten å se på tre eller fem. 1213 00:59:47,480 --> 00:59:50,100 Og så fire, kan du bare sjekk, det går rett inn her. 1214 00:59:50,100 --> 00:59:51,480 Du trenger ikke å se på fem. 1215 00:59:51,480 --> 00:59:52,570 Samme med den 6. 1216 00:59:52,570 --> 00:59:55,860 Du vet at 6-- det bare trenger ikke å bli sett. 1217 00:59:55,860 --> 00:59:57,870 >> Og så på den måten, er du bare spare deg 1218 00:59:57,870 --> 00:59:59,526 mange skritt når du sammenligner. 1219 00:59:59,526 --> 01:00:02,150 Du trenger ikke å sammenligne hver elementet mot andre elementer. 1220 01:00:02,150 --> 01:00:05,230 Du bare sammenligne mot de at du trenger å sammenligne den mot. 1221 01:00:05,230 --> 01:00:06,870 Så det er på en måte et abstrakt begrep. 1222 01:00:06,870 --> 01:00:10,540 Ingen grunn til bekymring hvis det ikke er ganske treffer deg rett ennå. 1223 01:00:10,540 --> 01:00:14,740 Men generelt, er dette hvordan et flette slags jobber. 1224 01:00:14,740 --> 01:00:17,750 Spørsmål, raske spørsmål, før jeg går videre? 1225 01:00:17,750 --> 01:00:18,550 Yeah. 1226 01:00:18,550 --> 01:00:22,230 >> PUBLIKUM: Så du sier at du tar 1, og deretter 4, og 6 1227 01:00:22,230 --> 01:00:23,860 og sette dem i. 1228 01:00:23,860 --> 01:00:26,800 Så er those-- ikke er ikke du ser på dem 1229 01:00:26,800 --> 01:00:28,544 som separate elementer, ikke som helhet? 1230 01:00:28,544 --> 01:00:29,210 ANDI PENG: Yeah. 1231 01:00:29,210 --> 01:00:32,020 Så hva som skjer er at du i utgangspunktet 1232 01:00:32,020 --> 01:00:33,650 oppretter en helt ny rekke. 1233 01:00:33,650 --> 01:00:36,690 Så du vet det, her har jeg to matriser av størrelse 3, ikke sant? 1234 01:00:36,690 --> 01:00:39,600 Så du vet at min sorterte utvalg må ha seks elementer. 1235 01:00:39,600 --> 01:00:42,270 Så du bare lage en ny mengde minne. 1236 01:00:42,270 --> 01:00:44,270 Så du er typen som være sløsing av hukommelse, 1237 01:00:44,270 --> 01:00:46,186 men det spiller ingen rolle fordi det er så liten. 1238 01:00:46,186 --> 01:00:48,590 Så du ser på en og du ser på to. 1239 01:00:48,590 --> 01:00:50,770 Og du vet at en er mindre enn to. 1240 01:00:50,770 --> 01:00:53,840 Så du vet at en bør gå i I begynnelsen av alle disse. 1241 01:00:53,840 --> 01:00:55,850 >> Du trenger ikke engang å se på 3 og 5. 1242 01:00:55,850 --> 01:00:57,400 Så du vet en går der. 1243 01:00:57,400 --> 01:00:59,300 Da har du i utgangspunktet hogge av en. 1244 01:00:59,300 --> 01:01:00,370 Det er, som døde for oss. 1245 01:01:00,370 --> 01:01:03,690 Så vi må bare 2, 3, 5, og deretter 4 og 6. 1246 01:01:03,690 --> 01:01:06,270 Og da vet du at du sammenligne 4 og 2, 1247 01:01:06,270 --> 01:01:07,560 oh, to bør gå inn der. 1248 01:01:07,560 --> 01:01:09,685 Så du slenger den to ned, du hogge det av. 1249 01:01:09,685 --> 01:01:12,060 Så da er det bare 3 og 5 i fire og seks. 1250 01:01:12,060 --> 01:01:14,650 Og du bare holde hakking den av før du setter dem i rekken. 1251 01:01:14,650 --> 01:01:17,110 >> PUBLIKUM: Så du er bare alltid sammenligne [uhørbart]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI PENG: Nettopp. 1253 01:01:17,710 --> 01:01:19,590 Så i den forstand, er du bare sammenligne, i hovedsak, 1254 01:01:19,590 --> 01:01:21,240 en rekke mot den andre nummer. 1255 01:01:21,240 --> 01:01:22,990 Og fordi du vet at det er sortert, du 1256 01:01:22,990 --> 01:01:24,350 trenger ikke å se gjennom alle tallene. 1257 01:01:24,350 --> 01:01:25,870 Du må bare se på den første. 1258 01:01:25,870 --> 01:01:27,582 Og så kan du bare slenger dem ned, fordi du vet 1259 01:01:27,582 --> 01:01:29,640 de hører hvor de trenger å tilhøre. 1260 01:01:29,640 --> 01:01:31,030 Yeah. 1261 01:01:31,030 --> 01:01:32,920 Godt spørsmål. 1262 01:01:32,920 --> 01:01:35,290 >> Og så hvis noen av dere er litt ambisiøst, 1263 01:01:35,290 --> 01:01:38,660 gjerne se på denne koden. 1264 01:01:38,660 --> 01:01:40,680 Dette er faktisk fysisk implementering 1265 01:01:40,680 --> 01:01:42,150 av hvordan vi skulle skrive merge sort. 1266 01:01:42,150 --> 01:01:44,070 Og du kan se, det er svært kort. 1267 01:01:44,070 --> 01:01:46,310 Men ideene bak det er ganske komplisert. 1268 01:01:46,310 --> 01:01:50,865 Så hvis du har lyst til å trekke ut dette i lekser i kveld, gjerne. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> OK. 1271 01:01:54,740 --> 01:01:58,070 Så David også gikk over dette i foredraget. 1272 01:01:58,070 --> 01:02:00,660 Hva er den beste saken runtimes, verst tenkelige kjøretider, 1273 01:02:00,660 --> 01:02:05,680 og de forventede driftstider av merge sort? 1274 01:02:05,680 --> 01:02:07,260 Et par sekunder til å tenke. 1275 01:02:07,260 --> 01:02:11,198 Dette er ganske vanskelig, men slags intuitive hvis du tenker på det. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Greit. 1278 01:02:23,054 --> 01:02:25,269 >> PUBLIKUM: Er det verste tilfellet n log n? 1279 01:02:25,269 --> 01:02:26,060 ANDI PENG: Nettopp. 1280 01:02:26,060 --> 01:02:29,380 Og hvorfor er det n log n. 1281 01:02:29,380 --> 01:02:32,230 >> PUBLIKUM: Er ikke det fordi det blir eksponentielt raskere, 1282 01:02:32,230 --> 01:02:35,390 så det er som en funksjon av at i stedet for bare bare å være n 1283 01:02:35,390 --> 01:02:37,529 squared eller noe? 1284 01:02:37,529 --> 01:02:38,320 ANDI PENG: Nettopp. 1285 01:02:38,320 --> 01:02:40,750 Så grunnen til at runtime på dette er n log 1286 01:02:40,750 --> 01:02:44,310 n er because-- hva er du gjør i alle disse trinnene? 1287 01:02:44,310 --> 01:02:46,190 Du bare hakke den i to, ikke sant? 1288 01:02:46,190 --> 01:02:48,750 Og så når vi gjør det logg, alt som det gjør 1289 01:02:48,750 --> 01:02:53,150 er å dele et problem i to, i to, i to, i flere omganger. 1290 01:02:53,150 --> 01:02:56,430 Og i den forstand, kan du snill av eliminere den lineære modellen 1291 01:02:56,430 --> 01:02:57,510 at vi har brukt. 1292 01:02:57,510 --> 01:03:00,254 Fordi når du hogge ting i halvparten, er det en logg. 1293 01:03:00,254 --> 01:03:02,420 Det er bare den matematiske måte å representere det. 1294 01:03:02,420 --> 01:03:06,310 >> Og så til slutt, på slutten, er du bare å lage en siste pasning gjennom 1295 01:03:06,310 --> 01:03:07,930 å sette dem alle i orden, ikke sant? 1296 01:03:07,930 --> 01:03:10,330 Og så hvis du bare nødt til å sjekke en ting, er at n. 1297 01:03:10,330 --> 01:03:13,420 Og så er du slags å multiplisere de to sammen. 1298 01:03:13,420 --> 01:03:17,660 Så det er som du har fått det endelige sjekk for n ned her med en logg over n 1299 01:03:17,660 --> 01:03:18,390 opp her. 1300 01:03:18,390 --> 01:03:21,060 Og hvis du multiplisere dem, som er n log n. 1301 01:03:21,060 --> 01:03:26,100 >> Og så den best case og worst saken og forventet er alle n log n. 1302 01:03:26,100 --> 01:03:27,943 Det er også som en annen sort. 1303 01:03:27,943 --> 01:03:30,090 Det er som utvalget sort i den forstand at den 1304 01:03:30,090 --> 01:03:32,131 spiller ingen rolle hva din Listen er, det bare kommer 1305 01:03:32,131 --> 01:03:34,801 å gjøre det samme hver eneste gang. 1306 01:03:34,801 --> 01:03:35,300 OK. 1307 01:03:35,300 --> 01:03:39,950 Så som dere kan se, selv om den slags som vi har gått through-- n 1308 01:03:39,950 --> 01:03:41,660 squared, det er ikke veldig effektivt. 1309 01:03:41,660 --> 01:03:47,060 Og selv dette n log n er ikke den mest effektive. 1310 01:03:47,060 --> 01:03:49,720 Hvis dere er nysgjerrige, det er liksom mekanismer 1311 01:03:49,720 --> 01:03:54,310 som er så effektive at de er nesten tilnærmet flat i runtime. 1312 01:03:54,310 --> 01:03:55,420 >> Du har fått noen log n-tallet. 1313 01:03:55,420 --> 01:03:58,190 Du har fått noen log log n-tallet. 1314 01:03:58,190 --> 01:04:00,330 Vi vil ikke berøre dem i denne klassen akkurat nå. 1315 01:04:00,330 --> 01:04:02,663 Men hvis dere er nysgjerrige, gjerne google, hva er 1316 01:04:02,663 --> 01:04:04,392 den mest effektive sorteringsmekanismer. 1317 01:04:04,392 --> 01:04:06,350 Jeg vet ikke, det er noen virkelig morsomme seg, 1318 01:04:06,350 --> 01:04:09,860 like-- det er noen virkelig morsomme seg som folk gjør. 1319 01:04:09,860 --> 01:04:12,210 Og du lurer på hvordan de noen gang tenkt på det. 1320 01:04:12,210 --> 01:04:15,730 Så google, hvis du har litt fritid tid, på, hva er noen morsomme måter 1321 01:04:15,730 --> 01:04:17,730 at people-- samt effektive ways-- mennesker 1322 01:04:17,730 --> 01:04:20,371 har vært i stand til å gjennomføre sorterer. 1323 01:04:20,371 --> 01:04:20,870 OK. 1324 01:04:20,870 --> 01:04:22,880 Og her er bare en hendig liten diagram. 1325 01:04:22,880 --> 01:04:26,850 Jeg vet alt om deg, før det quiz 0, vil være i rommet ditt sannsynligvis prøver 1326 01:04:26,850 --> 01:04:27,960 å huske det. 1327 01:04:27,960 --> 01:04:30,940 Så det er hyggelig der for dere. 1328 01:04:30,940 --> 01:04:37,120 Bare ikke glem den logikken som made-- hvorfor disse tallene ble forekommende. 1329 01:04:37,120 --> 01:04:39,870 Hvis du alltid er tapt, bare sørg at du vet hva slags er. 1330 01:04:39,870 --> 01:04:40,820 Og du kan kjøre gjennom dem i tankene dine 1331 01:04:40,820 --> 01:04:42,903 å finne ut hvorfor de Svarene er disse svarene. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Greit. 1334 01:04:47,600 --> 01:04:49,680 Så vi kommer til å flytte på, til slutt, for å søke. 1335 01:04:49,680 --> 01:04:51,638 Fordi som de av dere som har lest den PSet, 1336 01:04:51,638 --> 01:04:55,175 søking er også en del av denne ukens problem setter. 1337 01:04:55,175 --> 01:04:57,300 Du vil bli bedt om å gjennomføre to typer søk. 1338 01:04:57,300 --> 01:05:00,070 Den ene er en lineær søk og en er en binær søk. 1339 01:05:00,070 --> 01:05:01,760 >> Så den lineære søk er ganske enkelt. 1340 01:05:01,760 --> 01:05:04,070 Du bare vil søke element av en liste for å se om du får det. 1341 01:05:04,070 --> 01:05:05,444 Du trenger bare å iterere gjennom. 1342 01:05:05,444 --> 01:05:08,170 Og hvis det er lik noe, du kan bare returnere det, ikke sant? 1343 01:05:08,170 --> 01:05:10,890 Men det som vi er mest interessert i å snakke om 1344 01:05:10,890 --> 01:05:14,550 er binært søk, til høyre, som er den splitt og hersk mekanisme som 1345 01:05:14,550 --> 01:05:18,190 David ble demonstrere i forelesningen. 1346 01:05:18,190 --> 01:05:20,810 >> Husk telefonboken eksempel at han holder å bringe opp, 1347 01:05:20,810 --> 01:05:23,960 den som han slags slet litt på det siste året, 1348 01:05:23,960 --> 01:05:27,530 hvor du dele problemet i to, i to, i to, igjen og igjen, 1349 01:05:27,530 --> 01:05:30,730 til du finner det du leter etter? 1350 01:05:30,730 --> 01:05:33,727 Og du har fått runtime av det også. 1351 01:05:33,727 --> 01:05:35,810 Og du kan se, er det betydelig mer effektiv 1352 01:05:35,810 --> 01:05:39,080 enn noen annen type søk. 1353 01:05:39,080 --> 01:05:41,880 >> Så den måten at vi skulle gå om implementere en binær søk 1354 01:05:41,880 --> 01:05:46,510 er, hvis vi hadde en matrise, indeks 0-6, syv elementer 1355 01:05:46,510 --> 01:05:49,790 vi kan se i midten, right-- sorry, hvis våre spørsmål first-- 1356 01:05:49,790 --> 01:05:53,840 hvis vi ønsker å stille spørsmålet om, gjør matrisen inneholde element av 7, 1357 01:05:53,840 --> 01:05:56,840 selvsagt, som mennesker, og som har et så lite utvalg, er det lett for oss 1358 01:05:56,840 --> 01:05:58,210 å si ja. 1359 01:05:58,210 --> 01:06:05,750 Men den måten å implementere en binær søk ville være å se i midten. 1360 01:06:05,750 --> 01:06:08,020 >> Vi vet at indeksen 3 er midten, fordi vi 1361 01:06:08,020 --> 01:06:09,270 vet er det syv elementer. 1362 01:06:09,270 --> 01:06:10,670 Hva syv delt på 2? 1363 01:06:10,670 --> 01:06:12,850 Du kan hogge av den ekstra en. 1364 01:06:12,850 --> 01:06:14,850 Du har tre i midten. 1365 01:06:14,850 --> 01:06:17,590 Derfor er utvalget av 3 lik 7? 1366 01:06:17,590 --> 01:06:18,900 Det er ikke, ikke sant? 1367 01:06:18,900 --> 01:06:21,050 Men vi kan gjøre et par sjekker. 1368 01:06:21,050 --> 01:06:25,380 Er utvalg av tre mindre enn 7 eller er matrise av tre som er større enn 7? 1369 01:06:25,380 --> 01:06:27,240 >> Og vi vet at det er mindre enn syv. 1370 01:06:27,240 --> 01:06:30,259 Så vi vet at, oh, må det ikke være i venstre halvdel. 1371 01:06:30,259 --> 01:06:32,300 Vi vet at det må være i høyre halvdel, ikke sant? 1372 01:06:32,300 --> 01:06:34,662 Så vi kan bare hogge av halve array. 1373 01:06:34,662 --> 01:06:36,370 Vi trenger ikke engang å se på det lenger. 1374 01:06:36,370 --> 01:06:38,711 Fordi vi vet at halvparten av vår problem-- 1375 01:06:38,711 --> 01:06:41,210 vi vet at svaret er i høyre halvdel av vårt problem. 1376 01:06:41,210 --> 01:06:42,580 Så vi bare se på det nå. 1377 01:06:42,580 --> 01:06:44,860 >> Så nå ser vi på midten av det som er igjen. 1378 01:06:44,860 --> 01:06:46,880 At indeksen 5. 1379 01:06:46,880 --> 01:06:50,200 Vi gjør det samme sjekken på nytt og vi ser at det er mindre. 1380 01:06:50,200 --> 01:06:52,050 Så vi ser til venstre for det. 1381 01:06:52,050 --> 01:06:53,430 Og så ser vi at sjekken. 1382 01:06:53,430 --> 01:06:57,600 Er array verdi på indeks 4 lik 7? 1383 01:06:57,600 --> 01:06:58,260 Det er. 1384 01:06:58,260 --> 01:07:03,580 Så vi kan returnere sant, fordi vi fant verdien i vår liste. 1385 01:07:03,580 --> 01:07:06,738 Har den måten jeg gikk gjennom det fornuftig for alle? 1386 01:07:06,738 --> 01:07:08,760 OK. 1387 01:07:08,760 --> 01:07:11,670 Jeg skal gi dere kanskje, som, tre, fire minutter på å finne ut 1388 01:07:11,670 --> 01:07:13,270 hvordan pseudokode dette i. 1389 01:07:13,270 --> 01:07:18,070 >> Så tenk jeg ba deg om å skrive en funksjon kalt søk () som returneres 1390 01:07:18,070 --> 01:07:20,640 en verdi, en boolsk verdi, det var sant eller false-- lignende, 1391 01:07:20,640 --> 01:07:22,970 sant hvis du fant den verdi, usann hvis du ikke gjorde det. 1392 01:07:22,970 --> 01:07:25,230 Og da du var vedtatt i verdien du 1393 01:07:25,230 --> 01:07:28,410 var ute etter i verdier, som er array-- oh, jeg definitivt sette 1394 01:07:28,410 --> 01:07:29,410 som på feil sted. 1395 01:07:29,410 --> 01:07:29,580 OK. 1396 01:07:29,580 --> 01:07:31,829 Anyways, som bør ha vært til høyre av verdier. 1397 01:07:31,829 --> 01:07:36,280 Og deretter int n er antallet av elementene i den oppstillingen. 1398 01:07:36,280 --> 01:07:39,430 Hvordan vil du gå om å prøve til pseudo det problemet i? 1399 01:07:39,430 --> 01:07:41,630 Jeg skal gi dere liker tre minutter å gjøre det. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Nei, jeg tror det er only-- Ja, det er en rett opp her. 1402 01:08:02,595 --> 01:08:03,261 PUBLIKUM: Kan jeg? 1403 01:08:03,261 --> 01:08:04,388 ANDI PENG: Ja, jeg har deg. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 Er at arbeiderklassen? 1406 01:08:11,050 --> 01:08:12,290 Ok kult. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> OK. 1409 01:10:44,720 --> 01:10:47,630 Greit folkens, vi er kommer til å tøyle den i. 1410 01:10:47,630 --> 01:10:49,730 OK. 1411 01:10:49,730 --> 01:10:54,020 Så antar vi har fått denne herlige lite utvalg med n verdier i den. 1412 01:10:54,020 --> 01:10:55,170 Jeg visste ikke trekke linjene. 1413 01:10:55,170 --> 01:10:58,649 Men hvordan skulle vi gå om prøver å skrive dette? 1414 01:10:58,649 --> 01:11:00,440 Er det noen som ønsker å gi meg den første linjen? 1415 01:11:00,440 --> 01:11:02,814 Hvis du ønsker å gi meg første linje av denne pseudokode. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> PUBLIKUM: [uhørbart] 1418 01:11:08,430 --> 01:11:10,138 PUBLIKUM: Du ønsker å veksle through-- 1419 01:11:10,138 --> 01:11:11,094 PUBLIKUM: Bare en annen for loop? 1420 01:11:11,094 --> 01:11:11,760 PUBLIKUM: --Barnespill. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI PENG: Så dette er litt vanskelig. 1423 01:11:17,780 --> 01:11:23,130 Tenk om-- du ønsker å holde kjører denne sløyfen 1424 01:11:23,130 --> 01:11:27,950 om og om igjen til da? 1425 01:11:27,950 --> 01:11:30,819 >> PUBLIKUM: Inntil [uhørbart] verdi er lik denne verdien. 1426 01:11:30,819 --> 01:11:31,610 ANDI PENG: Nettopp. 1427 01:11:31,610 --> 01:11:33,900 Så du kan faktisk bare write-- Vi kan også forenkle det mer. 1428 01:11:33,900 --> 01:11:35,630 Vi kan bare gjøre en stund loop, ikke sant? 1429 01:11:35,630 --> 01:11:39,380 Så du kan bare ha loop-- vi vet at det er en stund. 1430 01:11:39,380 --> 01:11:42,850 Men for akkurat nå, jeg skal å si "loop" - gjennom hva? 1431 01:11:42,850 --> 01:11:46,640 Loop until-- hva er vår slutter tilstand? 1432 01:11:46,640 --> 01:11:47,510 Jeg tror jeg hørte det. 1433 01:11:47,510 --> 01:11:48,530 Jeg hørte noen si det. 1434 01:11:48,530 --> 01:11:51,255 >> Målgruppe: Verdier tilsvarer midten. 1435 01:11:51,255 --> 01:11:52,255 ANDI PENG: Si det igjen. 1436 01:11:52,255 --> 01:11:54,470 PUBLIKUM: Eller, inntil verdien du søker 1437 01:11:54,470 --> 01:11:58,470 for er lik middelverdien. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI PENG: Hva om det ikke er der? 1439 01:12:00,280 --> 01:12:03,113 Hva hvis verdien du søker for er faktisk ikke i denne matrisen? 1440 01:12:03,113 --> 01:12:05,890 PUBLIKUM: Du går tilbake 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI PENG: Men hva gjør vi ønsker å løkke til hvis vi har en tilstand? 1442 01:12:08,850 --> 01:12:09,350 Yeah. 1443 01:12:09,350 --> 01:12:11,239 >> PUBLIKUM: Inntil det er bare én verdi? 1444 01:12:11,239 --> 01:12:13,530 ANDI PENG: Du kan sløyfe until-- slik at du vet at du er 1445 01:12:13,530 --> 01:12:15,714 kommer til å ha en maks verdi, ikke sant? 1446 01:12:15,714 --> 01:12:18,130 Og du vet at du kommer å ha en min verdi, ikke sant? 1447 01:12:18,130 --> 01:12:20,379 Fordi også, det er noe Jeg glemte å si før, 1448 01:12:20,379 --> 01:12:22,640 som noe som er kritisk om binære søk 1449 01:12:22,640 --> 01:12:24,182 er at klyngen er allerede sortert. 1450 01:12:24,182 --> 01:12:26,973 Fordi det er ingen måte å gjøre dette hvis de er bare tilfeldige verdier. 1451 01:12:26,973 --> 01:12:29,190 Du vet ikke om man er større enn den andre, ikke sant? 1452 01:12:29,190 --> 01:12:32,720 >> Så du vet at din max og dine min er her, ikke sant? 1453 01:12:32,720 --> 01:12:35,590 Hvis du kommer til å være å justere din max i dine minutter og mid-- 1454 01:12:35,590 --> 01:12:38,470 la oss bare anta din mid verdi er riktig her-- 1455 01:12:38,470 --> 01:12:43,910 du kommer til utgangspunktet løkke til minimum din er 1456 01:12:43,910 --> 01:12:47,510 omtrent det samme som max, høyre eller hvis max er ikke det samme som min. 1457 01:12:47,510 --> 01:12:48,040 Høyre? 1458 01:12:48,040 --> 01:12:51,340 Fordi når det skjer, vet du at du har til slutt treffer den samme verdien. 1459 01:12:51,340 --> 01:12:59,135 Så du ønsker å sløyfe inntil min er mindre enn eller lik to-- oops, 1460 01:12:59,135 --> 01:13:01,510 ikke er mindre enn eller lik den andre veien around-- max er. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Visste at fornuftig? 1463 01:13:16,160 --> 01:13:18,810 Jeg tok et par prøver å få det riktig. 1464 01:13:18,810 --> 01:13:21,869 Men løkke til din max verdi er egentlig nesten mindre 1465 01:13:21,869 --> 01:13:23,410 enn eller lik minimum din, ikke sant? 1466 01:13:23,410 --> 01:13:25,201 Det er da du vet at du har konvergert. 1467 01:13:25,201 --> 01:13:29,290 PUBLIKUM: Når ville ditt maksimale verdien være mindre enn den minste? 1468 01:13:29,290 --> 01:13:31,040 ANDI PENG: Hvis du holder å justere det, som 1469 01:13:31,040 --> 01:13:32,380 er hva vi skal til å gjøre i dette. 1470 01:13:32,380 --> 01:13:33,460 Gir det mening? 1471 01:13:33,460 --> 01:13:35,750 Minimum og max er bare heltall som vi er trolig 1472 01:13:35,750 --> 01:13:39,260 kommer til å ønske å lage for å holde styr på hvor vi leter. 1473 01:13:39,260 --> 01:13:41,790 Fordi matrisen eksisterer uansett hva vi gjør. 1474 01:13:41,790 --> 01:13:45,030 Liker, vi er faktisk ikke fysisk hakking av tabellen, ikke sant? 1475 01:13:45,030 --> 01:13:47,261 Vi er bare å justere hvor vi ser. 1476 01:13:47,261 --> 01:13:48,136 Gir det mening? 1477 01:13:48,136 --> 01:13:48,472 >> PUBLIKUM: Yeah. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI PENG: OK. 1479 01:13:49,110 --> 01:13:57,090 Så hvis det er en forutsetning for vår loop, hva gjør vi ønsker innsiden av denne loop? 1480 01:13:57,090 --> 01:13:58,700 Hva skal vi være som ønsker å gjøre? 1481 01:13:58,700 --> 01:14:02,390 Så akkurat nå, har vi en max og en min, høyre, 1482 01:14:02,390 --> 01:14:04,962 trolig skapt her oppe et sted. 1483 01:14:04,962 --> 01:14:07,170 Vi skal sannsynligvis ha å finne en middelvei, ikke sant? 1484 01:14:07,170 --> 01:14:08,450 Hvordan skal vi være i stand til å finne midten? 1485 01:14:08,450 --> 01:14:09,491 Hva er mathematical-- 1486 01:14:09,491 --> 01:14:11,079 PUBLIKUM: Max pluss min delt på to. 1487 01:14:11,079 --> 01:14:11,870 ANDI PENG: Nettopp. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Gir det mening? 1490 01:14:21,620 --> 01:14:25,780 Og gjør dere se hvorfor vi ikke bare use-- hvorfor vi gjorde dette 1491 01:14:25,780 --> 01:14:27,850 i stedet for å gjøre nettopp n delt på 2? 1492 01:14:27,850 --> 01:14:30,310 Det er fordi n er en verdi som kommer til å bli det samme. 1493 01:14:30,310 --> 01:14:30,979 Høyre? 1494 01:14:30,979 --> 01:14:34,020 Men som vi justere vår minimum og maksimumsverdier, de kommer til å endre seg. 1495 01:14:34,020 --> 01:14:36,040 Og som et resultat, våre middel kommer til å endre også. 1496 01:14:36,040 --> 01:14:37,873 Så det er derfor vi ønsker å gjøre dette her. 1497 01:14:37,873 --> 01:14:38,510 OK. 1498 01:14:38,510 --> 01:14:41,600 >> Og så, nå som Vi har funnet our-- ja. 1499 01:14:41,600 --> 01:14:44,270 >> PUBLIKUM: Bare en rask question-- når du sier min og max, 1500 01:14:44,270 --> 01:14:46,410 er vi antar at det er allerede sortert? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI PENG: Ja, det er faktisk en Forutsetningen for en binær søk, 1502 01:14:48,400 --> 01:14:49,816 at du må vite det er sortert. 1503 01:14:49,816 --> 01:14:53,660 Som er grunnen sortere, skrive deg i din oppgavesettet før binære søk. 1504 01:14:53,660 --> 01:14:55,910 OK. 1505 01:14:55,910 --> 01:14:58,876 Så nå som vi vet hvor våre midtpunkt er, hva ønsker du å gjøre her? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> PUBLIKUM: Vi ønsker å sammenligne som til den andre. 1508 01:15:04,319 --> 01:15:05,110 ANDI PENG: Nettopp. 1509 01:15:05,110 --> 01:15:12,280 Så du kommer til å sammenligne midten til verdi, ikke sant? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 Og hva som forteller oss når vi sammenligner? 1512 01:15:18,670 --> 01:15:22,226 Hva ønsker vi å gjøre etterpå? 1513 01:15:22,226 --> 01:15:25,389 >> PUBLIKUM: Hvis verdien er større enn på midten, vi ønsker å kutte den av. 1514 01:15:25,389 --> 01:15:26,180 ANDI PENG: Nettopp. 1515 01:15:26,180 --> 01:15:33,940 Så hvis verdien er større enn på midten, er vi 1516 01:15:33,940 --> 01:15:36,550 kommer til å ønske å endre disse minimum og maxes, ikke sant? 1517 01:15:36,550 --> 01:15:38,980 Hva ønsker vi å endre? 1518 01:15:38,980 --> 01:15:42,145 Så hvis vi kjenner verdien er et sted her inne, hva gjør du vi å endre? 1519 01:15:42,145 --> 01:15:44,758 Vi ønsker å endre vår minimum for å være midten, ikke sant? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 Og så annet, hvis det er i denne halvparten, hva vi ønsker å endre? 1522 01:15:54,292 --> 01:15:55,306 >> PUBLIKUM: Din maksimale. 1523 01:15:55,306 --> 01:15:55,972 ANDI PENG: Yeah. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 Og da er du bare kommer å holde looping, ikke sant? 1526 01:16:04,680 --> 01:16:08,920 Fordi nå, etter en iterasjon gjennom, har du en maks her. 1527 01:16:08,920 --> 01:16:10,760 Og så kan du beregne en mid. 1528 01:16:10,760 --> 01:16:11,990 Og så kan du sammenligne. 1529 01:16:11,990 --> 01:16:14,766 Og du kommer til å holde det gående inntil min og maxes 1530 01:16:14,766 --> 01:16:15,890 har i hovedsak sammenfallende. 1531 01:16:15,890 --> 01:16:17,890 Og det er da du vet at du har truffet på slutten av den. 1532 01:16:17,890 --> 01:16:20,280 Og enten du har funnet det eller du ikke har på det tidspunktet. 1533 01:16:20,280 --> 01:16:23,170 >> Betyr dette fornuftig for alle? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 OK. 1536 01:16:26,770 --> 01:16:27,900 Dette er ganske viktig, fordi du vil ha 1537 01:16:27,900 --> 01:16:29,760 å skrive dette i koden din i kveld. 1538 01:16:29,760 --> 01:16:32,660 Men dere har en ganske god følelse av hva du bør gjøre, 1539 01:16:32,660 --> 01:16:34,051 noe som er bra. 1540 01:16:34,051 --> 01:16:34,550 OK. 1541 01:16:34,550 --> 01:16:38,840 Så vi har fått om lag sju minutter igjen delen. 1542 01:16:38,840 --> 01:16:43,170 Så vi kommer til å snakke om dette PSet at vi skal gjøre. 1543 01:16:43,170 --> 01:16:46,410 Så PSet er delt inn i to halvdeler. 1544 01:16:46,410 --> 01:16:50,230 Den første halvdelen innebærer implementere et funn 1545 01:16:50,230 --> 01:16:54,210 der du skriver en lineær søk, en binære søk, og en sorteringsalgoritme. 1546 01:16:54,210 --> 01:16:56,690 >> Så dette er den første tid i en PSet der 1547 01:16:56,690 --> 01:17:00,050 vi vil være å gi dere det som kalles fordeling kode, som er kode 1548 01:17:00,050 --> 01:17:02,740 at vi har pre-skrevet, men bare igjen noen stykker av 1549 01:17:02,740 --> 01:17:04,635 for deg å fullføre skriftlig. 1550 01:17:04,635 --> 01:17:07,510 Så dere, når du ser på dette kode, kan du bli virkelig redd. 1551 01:17:07,510 --> 01:17:08,630 Hvis du bare vil, ahh, jeg vet ikke hva det gjør, 1552 01:17:08,630 --> 01:17:11,670 Jeg vet ikke, liker, virker det som så komplisert, ahh, slappe av. 1553 01:17:11,670 --> 01:17:12,170 Det er greit. 1554 01:17:12,170 --> 01:17:12,930 Les spec. 1555 01:17:12,930 --> 01:17:16,920 Spesifikasjonen vil forklare deg nøyaktig hva alle disse programmene gjør. 1556 01:17:16,920 --> 01:17:20,560 >> For eksempel, er generate.c et program som vil komme med din PSet. 1557 01:17:20,560 --> 01:17:24,060 Du trenger faktisk ikke å røre det, men du bør forstå hva det gjør. 1558 01:17:24,060 --> 01:17:28,550 Og generate.c, er alt den gjør enten å generere slumptall 1559 01:17:28,550 --> 01:17:32,400 eller du kan gi den et frø, som en avtalt antall at det tar, 1560 01:17:32,400 --> 01:17:34,140 og det genererer flere tall. 1561 01:17:34,140 --> 01:17:37,170 Så det er en bestemt måte å implementere generate.c der 1562 01:17:37,170 --> 01:17:42,760 du kan bare gjøre en haug med tall Her kan du teste dine andre metoder på. 1563 01:17:42,760 --> 01:17:45,900 >> Så hvis du ville, for eksempel teste funn, 1564 01:17:45,900 --> 01:17:48,970 du ønsker å kjøre generate.c, generere en haug med tall, 1565 01:17:48,970 --> 01:17:50,880 og deretter kjøre hjelpere funksjon. 1566 01:17:50,880 --> 01:17:53,930 Din hjelpere funksjonen er der du er faktisk fysisk å skrive kode. 1567 01:17:53,930 --> 01:17:59,330 Og tenk på hjelpere som en bibliotekfilen du skriver at funn som ringer. 1568 01:17:59,330 --> 01:18:02,950 Og så innen helpers.c, vil du gjør søking og sortering. 1569 01:18:02,950 --> 01:18:06,500 >> Og så kommer dere til hovedsak bare sette dem alle sammen. 1570 01:18:06,500 --> 01:18:10,350 Spec vil fortelle deg hvordan du sette det på kommandolinjen. 1571 01:18:10,350 --> 01:18:14,880 Og du vil være i stand til å teste hvorvidt ikke din sortere og søke jobber. 1572 01:18:14,880 --> 01:18:15,870 Kjølig. 1573 01:18:15,870 --> 01:18:18,720 Har noen allerede startet og oppstått problemer eller spørsmål 1574 01:18:18,720 --> 01:18:20,520 de har akkurat nå med dette? 1575 01:18:20,520 --> 01:18:21,020 OK. 1576 01:18:21,020 --> 01:18:21,476 >> PUBLIKUM: Vent. 1577 01:18:21,476 --> 01:18:21,932 Jeg har et spørsmål. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI PENG: Yeah. 1579 01:18:22,844 --> 01:18:28,390 >> PUBLIKUM: Så jeg begynte å gjøre den lineære søk i helpers.c 1580 01:18:28,390 --> 01:18:29,670 og det var egentlig ikke fungerer. 1581 01:18:29,670 --> 01:18:34,590 Men så senere, jeg fant ut at vi bare måtte slette det og gjøre binære søk. 1582 01:18:34,590 --> 01:18:36,991 Så gjør det noe hvis det ikke fungerer? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI PENG: korte svaret er nei. 1585 01:18:41,510 --> 01:18:42,642 Men siden vi er not-- 1586 01:18:42,642 --> 01:18:44,350 PUBLIKUM: Men ingen er faktisk sjekker. 1587 01:18:44,350 --> 01:18:46,058 ANDI PENG: Vi er aldri kommer til å se det. 1588 01:18:46,058 --> 01:18:49,590 Men du sannsynligvis ønske å gjøre at søket fungerer. 1589 01:18:49,590 --> 01:18:51,700 Fordi hvis din lineær søk fungerer ikke, 1590 01:18:51,700 --> 01:18:54,410 så sjansene er din binære søket er ikke til å fungere så bra. 1591 01:18:54,410 --> 01:18:56,646 Fordi du har lignende Logikken i begge. 1592 01:18:56,646 --> 01:18:58,020 Og nei, det spiller egentlig ingen rolle. 1593 01:18:58,020 --> 01:19:01,300 Så de eneste som vil slå i er liksom og binært søk. 1594 01:19:01,300 --> 01:19:02,490 Yeah. 1595 01:19:02,490 --> 01:19:06,610 >> Og også, mange av barna var prøver å kompilere helpers.c. 1596 01:19:06,610 --> 01:19:09,550 Du er faktisk ikke tillatt å gjøre det, fordi helpers.c 1597 01:19:09,550 --> 01:19:11,200 ikke har en hovedfunksjon. 1598 01:19:11,200 --> 01:19:13,550 Og så du bør bare være faktisk kompilering 1599 01:19:13,550 --> 01:19:18,670 generere og finne, fordi finne samtaler helpers.c og funksjonene i den. 1600 01:19:18,670 --> 01:19:20,790 Så det gjør debugging en smerte i baken. 1601 01:19:20,790 --> 01:19:22,422 Men det er det vi må gjøre. 1602 01:19:22,422 --> 01:19:23,880 PUBLIKUM: Du bare gjøre alt, ikke sant? 1603 01:19:23,880 --> 01:19:27,290 ANDI PENG: Du kan bare gjøre alt så vel, ja. 1604 01:19:27,290 --> 01:19:28,060 OK. 1605 01:19:28,060 --> 01:19:32,570 Så det er det i forhold til hva den PSet ber dere alle til å gjøre. 1606 01:19:32,570 --> 01:19:35,160 Hvis du har spørsmål, føler fri til å spørre meg etter pkt. 1607 01:19:35,160 --> 01:19:37,580 Jeg vil være her for, liker, 20 minutter. 1608 01:19:37,580 --> 01:19:40,500 >> Og ja, de PSet s egentlig ikke så ille. 1609 01:19:40,500 --> 01:19:41,680 Dere bør være OK. 1610 01:19:41,680 --> 01:19:43,250 Disse, bare følg retningslinjer. 1611 01:19:43,250 --> 01:19:47,840 Type har en følelse av, logisk, hva bør skje, og du blir fin. 1612 01:19:47,840 --> 01:19:48,690 Ikke vær for redd. 1613 01:19:48,690 --> 01:19:50,220 Det er mye kode allerede skrevet der. 1614 01:19:50,220 --> 01:19:53,011 Ikke vær for redd hvis du ikke forstå hva alt dette betyr. 1615 01:19:53,011 --> 01:19:54,749 Hvis det er mye, det er helt greit. 1616 01:19:54,749 --> 01:19:55,790 Og kommer til kontortid. 1617 01:19:55,790 --> 01:19:57,520 Vi hjelper deg å ta en titt. 1618 01:19:57,520 --> 01:20:00,810 >> PUBLIKUM: Med den ekstra funksjoner, ser vi dem opp? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI PENG: Ja, de er i koden. 1620 01:20:03,417 --> 01:20:05,750 I spillet 15, halvparten av det er allerede skrevet for deg. 1621 01:20:05,750 --> 01:20:09,310 Så disse funksjonene er allerede i koden. 1622 01:20:09,310 --> 01:20:12,020 Jepp. 1623 01:20:12,020 --> 01:20:12,520 Greit. 1624 01:20:12,520 --> 01:20:14,000 Vel, lykke til. 1625 01:20:14,000 --> 01:20:15,180 Det er en motbydelig dag. 1626 01:20:15,180 --> 01:20:19,370 Så forhåpentligvis dere ikke føler for dårlig om bor inne og koding. 1627 01:20:19,370 --> 01:20:22,133