1 00:00:00,000 --> 00:00:03,332 >> [Speel van musiek] 2 00:00:03,332 --> 00:00:06,490 >> ANDI Peng: Welkom by week 3 van artikel. 3 00:00:06,490 --> 00:00:09,550 Dankie, julle ouens, vir alle komende hierdie vroeër begin tyd vandag. 4 00:00:09,550 --> 00:00:11,466 Ons het 'n mooi, bietjie het intieme groep van vandag. 5 00:00:11,466 --> 00:00:14,570 So hopelik sal ons kry afwerking, miskien, vroeg, 6 00:00:14,570 --> 00:00:15,780 'n bietjie vroeg vandag. 7 00:00:15,780 --> 00:00:22,057 So vinnig, net 'n paar aankondiging vir die agenda van vandag. 8 00:00:22,057 --> 00:00:23,890 Voordat ons begin, ons is gaan net oor te gaan 9 00:00:23,890 --> 00:00:28,910 paar kort logistieke probleme, pset vrae, debrief, dinge soos dat. 10 00:00:28,910 --> 00:00:30,250 En dan sal ons duik reg in. 11 00:00:30,250 --> 00:00:34,710 Ons sal 'n debugger genoem GDB om te gebruik begin debunking ons kode, wat David 12 00:00:34,710 --> 00:00:36,550 verduidelik in lesing die ander dag. 13 00:00:36,550 --> 00:00:39,420 Ons gaan oor die vier tipes van spesies. 14 00:00:39,420 --> 00:00:42,310 Ons gaan oor hulle redelik vinnig sedert hulle is redelik intensief. 15 00:00:42,310 --> 00:00:45,710 Maar weet dat al die skyfies en bronkode is altyd online. 16 00:00:45,710 --> 00:00:50,810 So voel vry, op jou insae, om terug te gaan en 'n blik op dit. 17 00:00:50,810 --> 00:00:53,930 >> Ons sal deurgaan asimptotiese notasie, wat 18 00:00:53,930 --> 00:00:55,944 is net 'n fancy manier sê "Runtimes," 19 00:00:55,944 --> 00:00:58,360 waar ons die groot O, wat David verduidelik in lesing. 20 00:00:58,360 --> 00:01:01,550 En ons het ook Omega, wat is die ondergrens runtime. 21 00:01:01,550 --> 00:01:06,450 En ons sal 'n bietjie meer praat in-diepte oor hoe die werk. 22 00:01:06,450 --> 00:01:10,160 En laastens, sal ons gaan oor binêre soek, omdat 'n klomp van julle wat reeds 23 00:01:10,160 --> 00:01:15,190 loer na jou psets waarskynlik weet dat dit is 'n vraag wat in jou pset. 24 00:01:15,190 --> 00:01:17,470 So jy sal gelukkig wees dat ons dek dit vandag. 25 00:01:17,470 --> 00:01:20,610 >> En laastens, per jou artikel terugvoer, ek het eintlik 26 00:01:20,610 --> 00:01:23,000 links ongeveer 15 minute by die einde net gaan oor 27 00:01:23,000 --> 00:01:27,730 logistiek van pset3, enige vrae het, miskien 'n bietjie van leiding, as jy wil, 28 00:01:27,730 --> 00:01:28,990 voordat ons begin programmering. 29 00:01:28,990 --> 00:01:30,890 So kom ons probeer om te kry deur middel van die materiaal redelik vinnig. 30 00:01:30,890 --> 00:01:33,880 En dan kan ons spandeer tyd neem meer vrae vir die pset. 31 00:01:33,880 --> 00:01:35,230 OK. 32 00:01:35,230 --> 00:01:39,570 >> Vinnig, so net 'n paar aankondigings voordat ons begin vandag. 33 00:01:39,570 --> 00:01:45,410 Eerstens, welkom om te maak dit deur twee van jou psets. 34 00:01:45,410 --> 00:01:49,432 Ek het 'n blik op your-- ja, laat kry 'n rondte van applous vir daardie een. 35 00:01:49,432 --> 00:01:51,140 Eintlik was ek regtig, regtig beïndruk. 36 00:01:51,140 --> 00:01:55,800 Ek gegradeer die eerste pset vir julle verlede week en julle het ongelooflik. 37 00:01:55,800 --> 00:01:58,290 >> Styl was op punt Behalwe vir 'n paar opmerkings. 38 00:01:58,290 --> 00:02:00,660 Maak seker dat jy is altyd kommentaar jou kode. 39 00:02:00,660 --> 00:02:03,040 Maar jou psets was op punt. 40 00:02:03,040 --> 00:02:05,549 En hou dit op. 41 00:02:05,549 --> 00:02:08,090 En dit is goed vir die padskraper om sien dat julle ouens is besig 42 00:02:08,090 --> 00:02:10,704 in soveel moeite in jou styl en jou ontwerp in jou kode 43 00:02:10,704 --> 00:02:12,120 wat ons graag vir jou om te sien. 44 00:02:12,120 --> 00:02:16,450 So ek verby langs my dankbaarheid vir die res van die Tas. 45 00:02:16,450 --> 00:02:19,210 >> Daar is egter 'n paar debrief vrae 46 00:02:19,210 --> 00:02:22,010 Ek wil net om te gaan oor wat sou beide my lewe te maak 47 00:02:22,010 --> 00:02:24,900 en 'n baie van die ander Tas se lewens 'n bietjie makliker te maak. 48 00:02:24,900 --> 00:02:28,220 Eerstens, het ek opgemerk afgelope week-- hoeveel van julle 49 00:02:28,220 --> 00:02:32,301 loop al check50 op jou kode voordat jy stuur? 50 00:02:32,301 --> 00:02:32,800 OK. 51 00:02:32,800 --> 00:02:36,690 So almal moet check50 doen, because-- n secret-- ons eintlik 52 00:02:36,690 --> 00:02:41,540 hardloop check50 as deel van ons korrektheid skrifte vir die toets van jou kode. 53 00:02:41,540 --> 00:02:45,480 So as jou kode faal check50, in alle waarskynlikheid, 54 00:02:45,480 --> 00:02:47,570 dit is waarskynlik gaan om misluk ons ​​tjek as well. 55 00:02:47,570 --> 00:02:49,320 Soms het jy ouens het die regte antwoorde. 56 00:02:49,320 --> 00:02:52,200 Soos in gulsig, sommige van jy het die regte nommers, 57 00:02:52,200 --> 00:02:53,960 jy net druk 'n paar ekstra dinge. 58 00:02:53,960 --> 00:02:55,940 En dat ekstra dinge eintlik versuim die tjek, 59 00:02:55,940 --> 00:02:58,440 omdat die rekenaar nie regtig weet wat dit soek. 60 00:02:58,440 --> 00:03:00,981 En so sal dit net loop deur, sien dat jou uitset nie 61 00:03:00,981 --> 00:03:03,810 ooreenstem met wat ons verwag die antwoord te wees, en merk dit is verkeerd. 62 00:03:03,810 --> 00:03:06,560 >> En ek weet wat gebeur het in sommige van jou gevalle hierdie week. 63 00:03:06,560 --> 00:03:09,870 So het ek terug gegaan en met die hand hergradeer almal se kode. 64 00:03:09,870 --> 00:03:12,780 In die toekoms al is, asseblief, asseblief maak seker 65 00:03:12,780 --> 00:03:14,570 dat jy ' check 50 op jou kode. 66 00:03:14,570 --> 00:03:17,970 Want dit is soort van 'n pyn vir die TA hê om terug te gaan en die hand regrade 67 00:03:17,970 --> 00:03:21,197 elke enkele pset vir elke enkele, klein gemis byvoorbeeld. 68 00:03:21,197 --> 00:03:22,530 So ek het nie neem af enige punte. 69 00:03:22,530 --> 00:03:25,210 Ek dink ek het dalk af een of twee vir ontwerp. 70 00:03:25,210 --> 00:03:27,710 In die toekoms al is, as jy versuim check50, 71 00:03:27,710 --> 00:03:31,330 punte sal geneem word af vir korrektheid. 72 00:03:31,330 --> 00:03:35,020 >> Verder is psets weens Vrydae op die middag. 73 00:03:35,020 --> 00:03:38,990 Ek dink daar is 'n sewe minute laat grasietydperk dat ons jou gee. 74 00:03:38,990 --> 00:03:42,434 Per Harvard tyd, is hulle toegelaat om sewe minute laat om alles. 75 00:03:42,434 --> 00:03:44,350 So hier by Yale, sal ons voldoen aan wat as goed. 76 00:03:44,350 --> 00:03:47,910 Maar pretty much op 00:07, as jou pset is nie in, 77 00:03:47,910 --> 00:03:49,720 dit gaan so laat gemerk word. 78 00:03:49,720 --> 00:03:53,160 En so terwyl dit gemerk so laat, die TA-- Ek is 79 00:03:53,160 --> 00:03:54,870 nog gaan word gradering jou psets. 80 00:03:54,870 --> 00:03:56,760 So sal jy nog steeds sien 'n graad verskyn. 81 00:03:56,760 --> 00:03:58,820 Maar weet dat by die einde van die semester, 82 00:03:58,820 --> 00:04:02,270 al laat psets sal net outomaties zeroed deur die rekenaar. 83 00:04:02,270 --> 00:04:04,490 >> Ons doen dit vir twee redes. 84 00:04:04,490 --> 00:04:09,220 Een, soms kry ons verskoon, soos verskonings dekaan se 85 00:04:09,220 --> 00:04:10,762 later op dat ek nie weet nie oor nie. 86 00:04:10,762 --> 00:04:13,761 So ons wil om seker te maak ons ​​gradering alles net in geval, soos, ek is 87 00:04:13,761 --> 00:04:15,080 ontbreek verskoning van die dekaan. 88 00:04:15,080 --> 00:04:17,000 En tweedens, hou in gedagte, kan jy nog steeds 89 00:04:17,000 --> 00:04:19,370 drop een pset dat volle omvang punte. 90 00:04:19,370 --> 00:04:21,430 En so het ons graag graad al jou psets net 91 00:04:21,430 --> 00:04:24,730 om seker te maak dat jou omvang se daar en jy hulle probeer. 92 00:04:24,730 --> 00:04:29,150 So selfs al is dit laat, sal jy nog steeds kry krediet vir omvang punte, dink ek. 93 00:04:29,150 --> 00:04:33,730 >> So moraal van die storie is, maak seker dat jou psets in op tyd. 94 00:04:33,730 --> 00:04:38,350 En as hulle nie in op tyd, weet dat dit is nie groot nie. 95 00:04:38,350 --> 00:04:41,678 Ja, voor ek aanbeweeg, nie almal het enige vrae oor pset terugvoer? 96 00:04:41,678 --> 00:04:42,178 Ja. 97 00:04:42,178 --> 00:04:43,630 >> GEHOOR: Het jy sê ons kan daal een van die psets? 98 00:04:43,630 --> 00:04:44,296 >> ANDI Peng: Ja. 99 00:04:44,296 --> 00:04:47,050 So is daar nege psets algehele in die loop van die semester. 100 00:04:47,050 --> 00:04:50,610 En as jy omvang points-- so omvang is net, 101 00:04:50,610 --> 00:04:53,567 pretty much, jy probeer die probleem is jy om in die tyd, 102 00:04:53,567 --> 00:04:56,150 jy wys dat jy het gedemonstreer het jy die spec te lees. 103 00:04:56,150 --> 00:04:57,191 Dit is pretty much omvang. 104 00:04:57,191 --> 00:04:59,370 En as jy die vervulling omvang punte, ons 105 00:04:59,370 --> 00:05:03,360 kan die laagste daal een uit volle omvang. 106 00:05:03,360 --> 00:05:06,790 So dit is in jou voordeel wees om voltooi en probeer om elke pset. 107 00:05:06,790 --> 00:05:10,320 >> Selfs indien geen van upload-- hulle werk, laai hulle almal. 108 00:05:10,320 --> 00:05:13,711 En dan sal ons hopelik in staat wees om gee jou 'n paar van die punte terug. 109 00:05:13,711 --> 00:05:14,210 Koel. 110 00:05:14,210 --> 00:05:16,780 Enige ander vrae? 111 00:05:16,780 --> 00:05:17,840 Groot. 112 00:05:17,840 --> 00:05:21,960 >> Tweedens, kantoor hours-- 'n paar vinnige notas oor kantoorure. 113 00:05:21,960 --> 00:05:24,300 So die eerste, kom vroeg in die week. 114 00:05:24,300 --> 00:05:26,909 Niemand is ooit op kantoorure, Maandag. 115 00:05:26,909 --> 00:05:28,700 Christabel gekom om kantoorure laaste nag. 116 00:05:28,700 --> 00:05:29,691 Ja, Christabel. 117 00:05:29,691 --> 00:05:32,190 En wat het ons op kantoor uur gisteraand, Christabel? 118 00:05:32,190 --> 00:05:33,020 >> GEHOOR: Ons het roomys. 119 00:05:33,020 --> 00:05:36,160 >> ANDI Peng: So dit is reg, ons het roomys by kantoorure laaste nag. 120 00:05:36,160 --> 00:05:39,390 Terwyl ek nie kan belowe dat ons sal roomys by kantoorure het 121 00:05:39,390 --> 00:05:43,230 elke week, wat ek kan belowe is dat daar aansienlik sal 'n 122 00:05:43,230 --> 00:05:45,380 beter student TA verhouding. 123 00:05:45,380 --> 00:05:47,650 Soos ligitieme, dit is soos 00:57. 124 00:05:47,650 --> 00:05:50,350 AANGESIEN kontrasteer wat saam met Donderdag, het jy ongeveer 150 het 125 00:05:50,350 --> 00:05:52,830 regtig beklemtoon kinders en geen roomys. 126 00:05:52,830 --> 00:05:55,360 En dit is net nie produktief vir enigiemand. 127 00:05:55,360 --> 00:05:58,730 So moraal van die storie is, kom vroeg om kantoorure en goeie dinge 128 00:05:58,730 --> 00:06:00,310 sal gebeur. 129 00:06:00,310 --> 00:06:02,110 >> Ook, kom voorbereid om vrae te vra. 130 00:06:02,110 --> 00:06:03,200 Jy weet? 131 00:06:03,200 --> 00:06:05,420 Ongeag van watter Tas, ek dink, is gesê, 132 00:06:05,420 --> 00:06:10,710 Ons het die afgelope tyd 'n paar studente wat kom op Donderdag by, soos, 10:50 133 00:06:10,710 --> 00:06:15,100 nie die spec gelees om soos my help, help my. 134 00:06:15,100 --> 00:06:18,200 Ongelukkig op daardie punt, is daar nie veel wat ons kan doen om jou te help. 135 00:06:18,200 --> 00:06:19,590 So asseblief, kom vroeg in die week. 136 00:06:19,590 --> 00:06:22,040 Kom vroeg om kantoorure. 137 00:06:22,040 --> 00:06:23,350 Kom voorbereid om vrae te vra. 138 00:06:23,350 --> 00:06:25,310 Maak seker dat jy, as 'n student, is waar 139 00:06:25,310 --> 00:06:27,620 wat jy nodig het om dit te wees dat die Tas kan lei jou langs, 140 00:06:27,620 --> 00:06:32,850 en dit is wat kantoorure moet word toegeken vir. 141 00:06:32,850 --> 00:06:37,380 >> Tweedens, so ek weet professore hou om ons te verras met toetse. 142 00:06:37,380 --> 00:06:39,439 Ek het 'n professor diegene soos, hey, op die pad, 143 00:06:39,439 --> 00:06:41,230 onthou dat akademiese trimester jy het die volgende Maandag. 144 00:06:41,230 --> 00:06:42,855 Ja, ek het nie geweet oor wat akademiese trimester. 145 00:06:42,855 --> 00:06:45,630 So ek gaan wees dat TA wat herinner u alles wat quiz 146 00:06:45,630 --> 00:06:47,270 0--, want jy weet, ons is CS. 147 00:06:47,270 --> 00:06:50,730 Nou dat ons gedoen het skikkings, kry jy Daarom is dit quiz 0, nie te toets 1, eh? 148 00:06:50,730 --> 00:06:51,320 OK. 149 00:06:51,320 --> 00:06:52,490 O, ek het 'n paar chuckles op daardie een. 150 00:06:52,490 --> 00:06:53,120 OK. 151 00:06:53,120 --> 00:06:59,710 >> So quiz 0 sal wees 14 Oktober as jy in die artikel Maandag-Woensdag 152 00:06:59,710 --> 00:07:02,920 en 15 Oktober as jy in die artikel Dinsdag-Donderdag. 153 00:07:02,920 --> 00:07:05,630 Dit geld nie vir dié van julle by Harvard 154 00:07:05,630 --> 00:07:10,350 wat- ek dink jy sal al wees neem jou vasvrae op die 14. 155 00:07:10,350 --> 00:07:13,560 >> So ja, volgende week, as David, in lesing gaan, 156 00:07:13,560 --> 00:07:15,747 ja, so daaroor quiz volgende week, julle almal 157 00:07:15,747 --> 00:07:17,580 sal nie geskok omdat jy het artikel 158 00:07:17,580 --> 00:07:19,664 en jy weet dat jou quiz 0 is in twee weke. 159 00:07:19,664 --> 00:07:21,580 En ons sal review het sessies en alles. 160 00:07:21,580 --> 00:07:26,360 So geen bekommernisse oor wat bang vir wat. 161 00:07:26,360 --> 00:07:29,890 Enige vrae before-- enige vrae Glad rakende logistieke probleme, 162 00:07:29,890 --> 00:07:32,591 gradering, kantoorure, afdelings? 163 00:07:32,591 --> 00:07:33,090 Ja. 164 00:07:33,090 --> 00:07:35,100 >> GEHOOR: So het die quiz is gaan wees tydens lesing? 165 00:07:35,100 --> 00:07:35,766 >> ANDI Peng: Ja. 166 00:07:35,766 --> 00:07:39,460 So het die quiz, dink ek, is 60 minute toegeken in daardie tydgleuf 167 00:07:39,460 --> 00:07:42,240 dat jy net sal neem in die lesingsaal. 168 00:07:42,240 --> 00:07:44,810 So jy hoef nie om in te kom op, soos, 'n ewekansige 07:00. 169 00:07:44,810 --> 00:07:46,140 Dit is alles goed. 170 00:07:46,140 --> 00:07:47,100 Ja. 171 00:07:47,100 --> 00:07:50,060 Koel. 172 00:07:50,060 --> 00:07:50,840 >> Alles reg. 173 00:07:50,840 --> 00:07:54,330 So ons gaan stel 'n konsep om jou 174 00:07:54,330 --> 00:08:00,760 hierdie week dat Dawid reeds soort van aangeraak in lesing die afgelope week. 175 00:08:00,760 --> 00:08:02,010 Dit is bekend as GDB. 176 00:08:02,010 --> 00:08:05,570 En hoe baie van julle, terwyl dit in die loop van die skryf van jou psets, 177 00:08:05,570 --> 00:08:09,981 het opgemerk 'n groot knoppie wat sê "Debug" op die top van jou IDE? 178 00:08:09,981 --> 00:08:10,480 OK. 179 00:08:10,480 --> 00:08:13,770 So nou gaan ons eintlik kry om opschommelen die geheim van wat dit eintlik knoppie 180 00:08:13,770 --> 00:08:14,270 doen nie. 181 00:08:14,270 --> 00:08:16,790 En ek waarborg jou, dit is 'n mooi, mooi ding. 182 00:08:16,790 --> 00:08:20,740 >> So tot nou toe, dink ek daar is twee dinge 183 00:08:20,740 --> 00:08:23,320 studente het gewoonlik nie doen wanneer debugging psets. 184 00:08:23,320 --> 00:08:27,635 Een, hulle óf voeg in printf () - so elke paar lyne, 185 00:08:27,635 --> 00:08:29,760 voeg hulle by in 'n printf () - O, wat is hierdie veranderlike? 186 00:08:29,760 --> 00:08:32,551 O, wat is hierdie veranderlike now-- en jy soort van sien die vordering 187 00:08:32,551 --> 00:08:33,940 van die kode soos dit loop. 188 00:08:33,940 --> 00:08:37,030 Of die tweede metode kinders doen, is dat hulle net skryf die hele ding 189 00:08:37,030 --> 00:08:38,610 en dan gaan soos hierdie aan die einde. 190 00:08:38,610 --> 00:08:39,970 Hopelik werk dit. 191 00:08:39,970 --> 00:08:44,851 Ek waarborg jou, GDB is beter as beide van die metodes. 192 00:08:44,851 --> 00:08:45,350 Ja. 193 00:08:45,350 --> 00:08:46,980 So dit sal jou nuwe beste vriend wees. 194 00:08:46,980 --> 00:08:51,780 Want dit is 'n pragtige ding wat visueel vertoon beide 195 00:08:51,780 --> 00:08:54,850 wat jou kode doen op 'n spesifieke punt 196 00:08:54,850 --> 00:08:57,486 asook wat al jou veranderlikes dra, 197 00:08:57,486 --> 00:08:59,610 soos wat hulle waardes is, op daardie spesifieke punt. 198 00:08:59,610 --> 00:09:02,670 En op hierdie manier, kan jy regtig stel inspeksiepunte in jou kode. 199 00:09:02,670 --> 00:09:04,350 Jy kan hardloop deur lyn deur die lyn. 200 00:09:04,350 --> 00:09:07,324 En GDB sal net vir jy, vertoon vir jou, 201 00:09:07,324 --> 00:09:09,490 wat al jou veranderlikes is, wat doen hulle, 202 00:09:09,490 --> 00:09:10,656 wat gaan aan in die kode. 203 00:09:10,656 --> 00:09:13,240 En in so 'n manier, dit is soveel makliker om te sien 204 00:09:13,240 --> 00:09:17,120 wat gebeur in plaas van printf-ing of die skryf van jou stellings. 205 00:09:17,120 --> 00:09:19,160 >> So sal ons 'n voorbeeld van dit later te doen. 206 00:09:19,160 --> 00:09:20,660 So dit lyk 'n bietjie abstrak. 207 00:09:20,660 --> 00:09:23,490 Geen sorge, sal ons voorbeelde te doen. 208 00:09:23,490 --> 00:09:29,170 En so in wese, die drie grootste, mees gebruikte funksies wat jy nodig het in GDB 209 00:09:29,170 --> 00:09:32,500 is die Volgende, stap oor, en stap in knoppies. 210 00:09:32,500 --> 00:09:34,860 Ek gaan aan die hoof oor daar eintlik nou. 211 00:09:34,860 --> 00:09:40,930 >> So kan julle sien dat al of moet ek in 'n bietjie zoom? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 In die rug, kan jy sien dat? 214 00:09:44,470 --> 00:09:45,730 Ek moet in zoom? 215 00:09:45,730 --> 00:09:46,480 Net 'n klein bietjie? 216 00:09:46,480 --> 00:09:49,390 OK, cool. 217 00:09:49,390 --> 00:09:50,280 Daar gaan ons. 218 00:09:50,280 --> 00:09:50,960 OK. 219 00:09:50,960 --> 00:09:57,000 >> So ek het, hier, my implementering vir gulsig. 220 00:09:57,000 --> 00:10:01,430 En terwyl baie van julle ouens het gulsig in while lus form-- dat 221 00:10:01,430 --> 00:10:04,890 is 'n baie aanvaarbare manier om dit te doen it-- ander manier om dit te doen is om net te 222 00:10:04,890 --> 00:10:06,280 verdeel in die modulo. 223 00:10:06,280 --> 00:10:09,290 Want dan kan jy jou waarde en dan jou res. 224 00:10:09,290 --> 00:10:11,150 En dan kan jy net voeg dit alles saam. 225 00:10:11,150 --> 00:10:13,390 Is die logika van wat ek doen hier sin maak vir almal, 226 00:10:13,390 --> 00:10:14,117 voordat ons begin? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 Soort van? 229 00:10:17,980 --> 00:10:18,710 Koel. 230 00:10:18,710 --> 00:10:19,210 Groot. 231 00:10:19,210 --> 00:10:21,290 Dit is 'n mooi stuk sexy van die kode, sou ek sê. 232 00:10:21,290 --> 00:10:23,502 Soos ek gesê het, David, in lesings, na 'n rukkie, 233 00:10:23,502 --> 00:10:25,960 jy sal al begin sien kode as iets wat mooi. 234 00:10:25,960 --> 00:10:29,950 En soms wanneer jy sien 'n pragtige kode, dit is so 'n wonderlike gevoel. 235 00:10:29,950 --> 00:10:35,410 >> So egter terwyl hierdie kode is baie mooi, beteken dit nie behoorlik werk nie. 236 00:10:35,410 --> 00:10:37,750 So laat hardloop check50 op hierdie punt. 237 00:10:37,750 --> 00:10:39,440 Check 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 Is dat pset2? 241 00:10:44,990 --> 00:10:46,870 Ja. 242 00:10:46,870 --> 00:10:47,520 O, 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 So loop ons check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> En as julle hier kan sien, dit is die versuim 'n paar van die gevalle. 248 00:11:07,170 --> 00:11:10,165 En vir 'n paar van julle, in die Natuurlik doen jou probleem stelle, 249 00:11:10,165 --> 00:11:11,110 jy soos, ah, waarom is dit nie werk nie. 250 00:11:11,110 --> 00:11:13,318 Hoekom is dit die werk vir 'n paar waardes, maar nie vir ander nie? 251 00:11:13,318 --> 00:11:17,760 Wel, GDB gaan om jou te help figuur hoekom diegene insette is nie werk nie. 252 00:11:17,760 --> 00:11:18,320 >> OK. 253 00:11:18,320 --> 00:11:21,640 So laat ons sien, een van die tjeks Ek was nie in check50 254 00:11:21,640 --> 00:11:24,920 was die insette waarde van 0,41. 255 00:11:24,920 --> 00:11:27,830 So die korrekte antwoord wat moet jy kry is 'n 4. 256 00:11:27,830 --> 00:11:33,090 Maar in plaas wat ek uit te druk is die 3-n, wat is verkeerd. 257 00:11:33,090 --> 00:11:36,190 So laat ons net hierdie hand loop, net seker te maak dat check50 werk. 258 00:11:36,190 --> 00:11:36,940 Kom ons doen ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Oeps, ek het om te gulsig te maak. 261 00:11:43,340 --> 00:11:43,840 Daar gaan ons. 262 00:11:43,840 --> 00:11:44,381 Nou ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Hoeveel verskuldig is? 265 00:11:47,670 --> 00:11:49,550 Kom ons doen 0,41. 266 00:11:49,550 --> 00:11:52,590 En yep, sien ons hier dat dit uitdruk 3 267 00:11:52,590 --> 00:11:55,160 wanneer die korrekte antwoord, in werklikheid, moet 4. 268 00:11:55,160 --> 00:12:01,460 So laat ingaan GDB en sien hoe ons kan gaan van hierdie probleem. 269 00:12:01,460 --> 00:12:03,992 >> So die eerste stap in altyd ontfouting jou kode 270 00:12:03,992 --> 00:12:05,950 is om 'n breekpunt te stel, of 'n punt waar jy 271 00:12:05,950 --> 00:12:09,079 wil hê dat die rekenaar of die debugger om te begin kyk. 272 00:12:09,079 --> 00:12:11,120 So as jy nie regtig weet wat jou probleem is, 273 00:12:11,120 --> 00:12:14,670 Gewoonlik is die tipiese ding wil ons doen, is om ons breekpunt stel by die hoof. 274 00:12:14,670 --> 00:12:18,520 So as jy ouens kan sien nie rooi knoppie net daar, 275 00:12:18,520 --> 00:12:22,860 yep, wat my opstel van 'n breekpunt vir die belangrikste funksie. 276 00:12:22,860 --> 00:12:24,130 Ek wat klik. 277 00:12:24,130 --> 00:12:26,130 >> En dan kan ek na my Debug knoppie. 278 00:12:26,130 --> 00:12:27,036 Ek getref dat die knoppie. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Laat my terug zoom uit as ek kan. 281 00:12:36,555 --> 00:12:38,020 Daar gaan ons. 282 00:12:38,020 --> 00:12:40,730 Dus het ons hier, 'n paneel aan die regterkant. 283 00:12:40,730 --> 00:12:43,680 Ek is jammer, ouens in die rug, het jy kan nie regtig sien baie goed. 284 00:12:43,680 --> 00:12:49,090 Maar in wese, al hierdie reg paneel doen 285 00:12:49,090 --> 00:12:53,130 is die dop van beide die uitgelig lyn, wat is die reël van die kode 286 00:12:53,130 --> 00:12:56,640 dat die rekenaar tans aktief is, sowel as al jou veranderlikes 287 00:12:56,640 --> 00:12:57,600 af hier. 288 00:12:57,600 --> 00:13:00,487 >> So jy het sent, munte, n, alle verklaarde om verskillende dinge 289 00:13:00,487 --> 00:13:01,070 op hierdie punt. 290 00:13:01,070 --> 00:13:04,850 Geen sorge, want ons het nie eintlik geïnisialiseer hulle nog enige veranderlikes. 291 00:13:04,850 --> 00:13:07,200 So in jou rekenaar, jou rekenaar is net sien, 292 00:13:07,200 --> 00:13:14,376 oh, 32767 was die laaste gebruikte funksie van daardie geheue spasie in my rekenaar. 293 00:13:14,376 --> 00:13:16,000 En so dit is waar sent tans. 294 00:13:16,000 --> 00:13:19,360 Maar geen dat sodra jy die kode uit te voer, dit moet geïnitialiseerd geword. 295 00:13:19,360 --> 00:13:24,110 >> So laat deurgaan, lyn deur lyn, wat gaan hier aan. 296 00:13:24,110 --> 00:13:25,350 OK. 297 00:13:25,350 --> 00:13:29,400 So hier is die drie knoppies wat ek net verduidelik. 298 00:13:29,400 --> 00:13:34,090 Jy het die drama, of die funksie Run, knoppie, jy het die stap oor knoppie, 299 00:13:34,090 --> 00:13:36,600 en jy het ook die Stap in knoppie. 300 00:13:36,600 --> 00:13:41,260 En wese, al drie van hulle net gaan deur jou kode 301 00:13:41,260 --> 00:13:42,690 en doen verskillende dinge. 302 00:13:42,690 --> 00:13:45,680 >> So tipies, wanneer jy ontfouting, Ons wil nie net getref speel, 303 00:13:45,680 --> 00:13:47,930 omdat Play sal net loop jou kode om die einde van dit. 304 00:13:47,930 --> 00:13:49,070 En dan sal jy nie eintlik weet wat jou probleem 305 00:13:49,070 --> 00:13:51,432 is nie, tensy jy verskeie inbreekpunt stel. 306 00:13:51,432 --> 00:13:53,890 As jy verskeie inbreekpunt stel, Dit sal net outomaties 307 00:13:53,890 --> 00:13:56,030 hardloop van een breekpunt, na die volgende, na die volgende. 308 00:13:56,030 --> 00:13:58,030 Maar in hierdie geval het ons het net dat die een, want ons 309 00:13:58,030 --> 00:13:59,970 wil ons pad werk van bo af na onder. 310 00:13:59,970 --> 00:14:04,830 So ons gaan om dit te ignoreer knoppie nou vir die doel van hierdie program. 311 00:14:04,830 --> 00:14:08,230 >> So het die stap oor funksie net stappe oor elke enkele lyn 312 00:14:08,230 --> 00:14:11,510 en vertel jou wat die rekenaar doen. 313 00:14:11,510 --> 00:14:14,630 Die Stap in funksie gaan in die werklike funksie 314 00:14:14,630 --> 00:14:16,000 dit is op jou lyn van die kode. 315 00:14:16,000 --> 00:14:19,070 So byvoorbeeld, soos printf (), dit is 'n funksie, reg? 316 00:14:19,070 --> 00:14:21,980 As ek wou fisies stap in die printf () funksie, 317 00:14:21,980 --> 00:14:25,610 Ek sou eintlik gaan in die stuk Poskode waar printf () is geskryf en sien 318 00:14:25,610 --> 00:14:26,730 wat gaan aan daar. 319 00:14:26,730 --> 00:14:29,924 >> Maar tipies veronderstel ons dat die kode wat ons gee jou werk. 320 00:14:29,924 --> 00:14:31,340 Ons aanvaar die printf () werk. 321 00:14:31,340 --> 00:14:33,170 Ons aanvaar dat GetInt () werk. 322 00:14:33,170 --> 00:14:35,170 So daar is geen behoefte om stap in daardie funksies. 323 00:14:35,170 --> 00:14:37,170 Maar as daar funksies dat jy jouself skryf 324 00:14:37,170 --> 00:14:39,060 wat jy wil om te kyk uit te vind wat aangaan, 325 00:14:39,060 --> 00:14:41,200 jy wil om te stap in daardie funksie. 326 00:14:41,200 --> 00:14:43,940 >> So nou het ons net gaan om te stap oor hierdie stuk van die kode. 327 00:14:43,940 --> 00:14:44,485 So laat ons sien. 328 00:14:44,485 --> 00:14:46,547 Ag, druk, "O Hai, hoe veel verandering verskuldig is? " 329 00:14:46,547 --> 00:14:47,130 Ons gee nie om. 330 00:14:47,130 --> 00:14:49,830 Ons weet dat werk, sodat ons stap oor dit. 331 00:14:49,830 --> 00:14:53,290 >> So n, wat is ons float dat ons het initialized-- of declared-- 332 00:14:53,290 --> 00:14:56,810 by die top, ons is nou gelykstaande dat GetFloat (). 333 00:14:56,810 --> 00:14:57,810 So laat stap oor dit. 334 00:14:57,810 --> 00:14:59,580 En ons sien by die onderkant hier, die program 335 00:14:59,580 --> 00:15:03,360 is waarna my om insette 'n waarde. 336 00:15:03,360 --> 00:15:08,580 So laat die invoer van die waarde wat ons wil hê hier toets, wat 0,41. 337 00:15:08,580 --> 00:15:09,160 Groot. 338 00:15:09,160 --> 00:15:12,780 >> So nou n-- doen julle ouens sien hier by die bottom-- dit 339 00:15:12,780 --> 00:15:15,140 stored-- omdat ons het nog nie afgerond, dit is 340 00:15:15,140 --> 00:15:19,540 gestoor in hierdie soos reuse float wat 0,4099999996, 341 00:15:19,540 --> 00:15:22,550 wat naby genoeg is om ons doeleindes, reg nou, om 0.41. 342 00:15:22,550 --> 00:15:26,090 En dan sal ons sien later op, soos ons voortgaan versterking oor die program, 343 00:15:26,090 --> 00:15:29,850 ná hier, het N geword afgeronde en sent geword 41. 344 00:15:29,850 --> 00:15:30,350 Groot. 345 00:15:30,350 --> 00:15:32,230 So weet ons dat ons werk afronding se. 346 00:15:32,230 --> 00:15:34,700 Ons weet dat ons die korrekte aantal sent, 347 00:15:34,700 --> 00:15:36,990 sodat ons weet dat dit is nie regtig die probleem. 348 00:15:36,990 --> 00:15:40,050 >> So ons voortgaan versterking in hierdie program. 349 00:15:40,050 --> 00:15:40,900 Ons gaan hier. 350 00:15:40,900 --> 00:15:46,139 En so na hierdie lyn van die kode, ons moet weet hoeveel kwartale ons het. 351 00:15:46,139 --> 00:15:46,680 Ons stap oor. 352 00:15:46,680 --> 00:15:52,040 En jy sien ons, in werklikheid, het 'n kwartaal, want ons het afgetrek 25 353 00:15:52,040 --> 00:15:53,790 van ons aanvanklike waarde van 41. 354 00:15:53,790 --> 00:15:55,890 En ons het 16 links vir ons sent. 355 00:15:55,890 --> 00:15:58,830 >> Maak almal verstaan ​​hoe die program is versterking deur middel van 356 00:15:58,830 --> 00:16:02,980 en waarom sent het nou '16 en waarom, nou, munte geword 1? 357 00:16:02,980 --> 00:16:04,610 Is almal wat volg logika? 358 00:16:04,610 --> 00:16:05,110 Koel. 359 00:16:05,110 --> 00:16:07,860 So as van hierdie punt, die werkende program se, reg? 360 00:16:07,860 --> 00:16:09,797 Ons weet dit is presies doen wat ons wil hê dit moet. 361 00:16:09,797 --> 00:16:11,880 En ons het nie eintlik het om uit te druk, o, wat 362 00:16:11,880 --> 00:16:14,430 is sent op hierdie punt, Wat is munte op hierdie punt. 363 00:16:14,430 --> 00:16:17,170 >> Ons gaan voort om deur die program. 364 00:16:17,170 --> 00:16:18,100 Stap oor. 365 00:16:18,100 --> 00:16:18,620 Koel. 366 00:16:18,620 --> 00:16:19,700 Ons gaan oor dimes. 367 00:16:19,700 --> 00:16:20,200 Groot. 368 00:16:20,200 --> 00:16:22,367 Ons sien dat dit geneem af $ 0,10 vir 'n sent. 369 00:16:22,367 --> 00:16:23,450 En nou het ons twee muntstukke. 370 00:16:23,450 --> 00:16:25,260 Dit is korrek. 371 00:16:25,260 --> 00:16:31,555 >> Ons gaan oor pennies en ons sien wat ons het oorgebly sent. 372 00:16:31,555 --> 00:16:32,680 Hmm, dit is vreemd. 373 00:16:32,680 --> 00:16:37,540 Hier by die program, was ek veronderstel my pennies het afgetrek. 374 00:16:37,540 --> 00:16:39,400 Miskien was ek net nie doen dat die lyn regs. 375 00:16:39,400 --> 00:16:42,190 En helaas, kan jy sien hier, want ons weet 376 00:16:42,190 --> 00:16:44,360 dat ons versterking deur lyne 32 en 33, 377 00:16:44,360 --> 00:16:50,560 dit is waar ons program onbehoorlik het veranderlikes hardloop. 378 00:16:50,560 --> 00:16:55,136 So kan ons kyk en sien, o, Ek trek sent hier, 379 00:16:55,136 --> 00:16:57,010 maar ek is nie eintlik toe te voeg tot my munt waarde. 380 00:16:57,010 --> 00:16:57,860 Ek is toe te voeg tot sent. 381 00:16:57,860 --> 00:17:00,234 En ek wil nie te voeg aan sent, ek wil toe te voeg tot muntstukke. 382 00:17:00,234 --> 00:17:05,420 So as ons verander muntstukke, ons het 'n werkende program. 383 00:17:05,420 --> 00:17:06,730 Ek kan check50 hardloop. 384 00:17:06,730 --> 00:17:11,063 Jy kan net verlaat uit GDB reg hier en dan weer hardloop check50. 385 00:17:11,063 --> 00:17:11,938 Ek kon dit net doen. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Ek moet gulsig te maak. 388 00:17:18,480 --> 00:17:19,940 0,41. 389 00:17:19,940 --> 00:17:22,819 En hier is dit druk uit die regte antwoord. 390 00:17:22,819 --> 00:17:26,569 >> So as julle kan sien, GDB is 'n baie kragtige instrument 391 00:17:26,569 --> 00:17:29,940 wanneer ons so veel kode gaan en so baie veranderlikes 392 00:17:29,940 --> 00:17:32,510 dat dit moeilik is vir ons, as 'n mens, om tred te hou. 393 00:17:32,510 --> 00:17:35,360 Die rekenaar in die GDB debugger, het die vermoë 394 00:17:35,360 --> 00:17:37,020 om tred te hou van alles te hou. 395 00:17:37,020 --> 00:17:40,480 Ek weet, in Visionaire, julle waarskynlik dalk 'n segmentering foute getref 396 00:17:40,480 --> 00:17:43,150 omdat jy hardloop buite perke van jou skikking. 397 00:17:43,150 --> 00:17:46,510 In die voorbeeld van die keiser en dis presies wat ek hier geïmplementeer. 398 00:17:46,510 --> 00:17:50,060 >> So ek het vergeet om te kyk vir wat sal gebeur as ek 399 00:17:50,060 --> 00:17:52,510 het nie twee command line argumente. 400 00:17:52,510 --> 00:17:53,880 Ek het net nie sit in daardie tjek. 401 00:17:53,880 --> 00:17:57,380 En so as ek hardloop Debug-- ek my breekpunt daar regs. 402 00:17:57,380 --> 00:17:58,055 Ek hardloop Debug. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> OK. 405 00:18:16,550 --> 00:18:17,050 Ja. 406 00:18:17,050 --> 00:18:20,350 So eintlik GDB was veronderstel het my vertel daar 407 00:18:20,350 --> 00:18:22,300 was 'n segmentering skuld daar. 408 00:18:22,300 --> 00:18:24,883 Ek weet nie wat aangaan reg daar, maar toe ek gehardloop het, 409 00:18:24,883 --> 00:18:25,590 dit werk nie. 410 00:18:25,590 --> 00:18:29,410 Wanneer jy reëls van die kode deur te hardloop en GDB dalk net skielik ophou op jou, 411 00:18:29,410 --> 00:18:31,540 optrek en kyk wat die rooi fout. 412 00:18:31,540 --> 00:18:33,930 Dit sal jou vertel, hey, jy het 'n segmentering skuld, 413 00:18:33,930 --> 00:18:38,550 wat beteken dat jy probeer om toegang ruimte in 'n skikking wat nie bestaan ​​het nie. 414 00:18:38,550 --> 00:18:39,050 Ja. 415 00:18:39,050 --> 00:18:43,280 >> So in die volgende probleem stel hierdie week, julle ouens 416 00:18:43,280 --> 00:18:45,600 sal waarskynlik 'n baie veranderlikes rond dryf. 417 00:18:45,600 --> 00:18:48,560 Jy gaan nie om seker te wees wat beteken hulle almal op 'n sekere punt. 418 00:18:48,560 --> 00:18:53,560 So GDB sal jy regtig help in die uitzoeken wat hulle almal gelyk 419 00:18:53,560 --> 00:18:55,940 en in staat is om visueel sien. 420 00:18:55,940 --> 00:19:01,995 Is daar iemand verwar oor hoe enige van wat werk? 421 00:19:01,995 --> 00:19:02,495 Koel. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Alles reg. 424 00:19:10,620 --> 00:19:14,260 So na dit, ons is gaan na regs duik 425 00:19:14,260 --> 00:19:17,562 in vier verskillende tipes van spesies vir hierdie week. 426 00:19:17,562 --> 00:19:19,520 Hoeveel van julle, in die eerste van alles, voordat ons begin, 427 00:19:19,520 --> 00:19:23,020 die hele spec vir pset3 gelees het? 428 00:19:23,020 --> 00:19:23,824 OK. 429 00:19:23,824 --> 00:19:24,740 Ek is trots op julle. 430 00:19:24,740 --> 00:19:29,110 Dit is soos die helfte van die klas, wat aansienlik meer as die vorige keer. 431 00:19:29,110 --> 00:19:33,950 >> So dit is 'n groot, want toe ons praat oor die inhoud 432 00:19:33,950 --> 00:19:36,170 in lecture-- of jammer, in section-- Ek hou 433 00:19:36,170 --> 00:19:38,210 'n baie wat verband hou terug na wat die pset is 434 00:19:38,210 --> 00:19:40,210 en hoe jy wil implementeer wat in jou pset. 435 00:19:40,210 --> 00:19:42,400 So as jy kom met lees die spec, sal dit 436 00:19:42,400 --> 00:19:45,510 wees 'n baie makliker vir jou om te verstaan wat ek praat as ek sê, 437 00:19:45,510 --> 00:19:48,720 oh hey, dit kan 'n baie wees goeie plek om hierdie soort te implementeer. 438 00:19:48,720 --> 00:19:52,870 So diegene van julle wat lees die spec weet dat, as deel van jou pset, 439 00:19:52,870 --> 00:19:54,900 jy gaan hê om skryf 'n tipe soort. 440 00:19:54,900 --> 00:19:58,670 So kan dit baie nuttig wees vir 'n klomp van julle vandag. 441 00:19:58,670 --> 00:20:01,760 >> So ons sal begin met, wese, die mees eenvoudige tipe 442 00:20:01,760 --> 00:20:04,580 van aard, die seleksie soort. 443 00:20:04,580 --> 00:20:06,800 Die tipiese algoritme vir hoe ons wil gaan oor hierdie 444 00:20:06,800 --> 00:20:10,460 is-- Dawid het deur middel van hierdie alles in lesing, so ek sal vinnig beweeg saam 445 00:20:10,460 --> 00:20:13,900 here-- is in wese, jy het 'n verskeidenheid van waardes. 446 00:20:13,900 --> 00:20:17,170 En dan vind jy die kleinste ongesorteerde waarde 447 00:20:17,170 --> 00:20:20,200 en jy ruil wat waarde met die eerste ongesorteerde waarde. 448 00:20:20,200 --> 00:20:22,700 En dan moet jy net aanhou herhaal met die res van jou lys. 449 00:20:22,700 --> 00:20:25,740 >> En hier is 'n visuele verduideliking van hoe dit sal werk. 450 00:20:25,740 --> 00:20:30,460 So byvoorbeeld, as ons begin met 'n verskeidenheid van vyf elemente, indeks 451 00:20:30,460 --> 00:20:35,910 0-4, met 3, 5, 2, 6, en 4 waardes geplaas in die array-- so reg nou, 452 00:20:35,910 --> 00:20:38,530 ons net gaan om te aanvaar dat hulle is almal ongesorteerde 453 00:20:38,530 --> 00:20:41,130 want ons het nie anders getoets. 454 00:20:41,130 --> 00:20:44,130 >> So hoe 'n seleksie soort sou werk is dat dit sou eerste 455 00:20:44,130 --> 00:20:46,800 loop deur die geheel van die ongesorteerde skikking. 456 00:20:46,800 --> 00:20:49,120 Dit sou kies uit die kleinste waarde. 457 00:20:49,120 --> 00:20:51,750 In hierdie geval, 3, reg nou, is die kleinste. 458 00:20:51,750 --> 00:20:52,680 Dit raak tot 5. 459 00:20:52,680 --> 00:20:55,620 Nee, 5 is nie groter than-- of jammer, is nie minder nie than-- 3. 460 00:20:55,620 --> 00:20:57,779 So is die minimum waarde is nog steeds 3. 461 00:20:57,779 --> 00:20:58,695 En dan kry jy 2. 462 00:20:58,695 --> 00:21:00,990 Die rekenaar sien, o, 2 is minder as 3. 463 00:21:00,990 --> 00:21:02,750 2 moet nou die minimum waarde wees. 464 00:21:02,750 --> 00:21:06,630 En so 2 swaps met daardie eerste waarde. 465 00:21:06,630 --> 00:21:10,702 >> So na een pas, het ons inderdaad sien dat die 2 en die 3 is omgeruil. 466 00:21:10,702 --> 00:21:13,910 En ons is maar net gaan om voort te gaan doen dit weer met die res van die skikking. 467 00:21:13,910 --> 00:21:17,660 So ons gaan net loop deur die laaste vier indekse van die skikking. 468 00:21:17,660 --> 00:21:20,670 Ons sal sien dat 3 is die volgende minimum waarde. 469 00:21:20,670 --> 00:21:23,240 So ons gaan ruil dit met 4. 470 00:21:23,240 --> 00:21:26,900 En dan is ons net gaan om te hou loop deur totdat uiteindelik, het jy 471 00:21:26,900 --> 00:21:33,730 kry om 'n gesorteerde skikking waarin 2, 3, 4, 5, en 6 is almal gesorteer. 472 00:21:33,730 --> 00:21:37,530 Verstaan ​​almal die logika van hoe 'n seleksie soort werk? 473 00:21:37,530 --> 00:21:39,669 >> Jy moet net 'n soort van 'n minimum waarde. 474 00:21:39,669 --> 00:21:41,210 Jy hou van wat dit is. 475 00:21:41,210 --> 00:21:45,170 En wanneer jy dit vind, jy het dit te ruil met die eerste waarde in die array-- 476 00:21:45,170 --> 00:21:48,740 of, nie die eerste value-- die volgende waarde in die skikking. 477 00:21:48,740 --> 00:21:50,150 Koel. 478 00:21:50,150 --> 00:21:55,460 >> So as julle soort gesien van 'n kort blik, 479 00:21:55,460 --> 00:21:58,450 Ons gaan hierdie pseudokode uit. 480 00:21:58,450 --> 00:22:02,510 So as jy ouens in die rug wil vorm 'n groep, almal by 'n tafel 481 00:22:02,510 --> 00:22:06,170 kan 'n bietjie vennoot vorm, ek gaan om julle ouens soos drie minute te gee 482 00:22:06,170 --> 00:22:08,190 net praat deur middel van die logika, in Engels, 483 00:22:08,190 --> 00:22:14,161 hoe ons in staat kan wees om te implementeer pseudokode om 'n seleksie soort skryf. 484 00:22:14,161 --> 00:22:14,910 En daar is lekkergoed. 485 00:22:14,910 --> 00:22:16,118 Kom asseblief en kry lekkergoed. 486 00:22:16,118 --> 00:22:19,520 As jy in die rug en jy wil lekkergoed, kan ek gooi candy aan jou. 487 00:22:19,520 --> 00:22:22,850 Eintlik doen you-- cool. 488 00:22:22,850 --> 00:22:23,552 Jammer. 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 >> So as ons wil, as 'n klas, skryf pseudokode 493 00:25:27,140 --> 00:25:30,466 hoe 'n mens kan nader hierdie probleem, net voel vry. 494 00:25:30,466 --> 00:25:32,340 Ek sal net gaan rond en, in orde is, vra groepe 495 00:25:32,340 --> 00:25:35,065 vir die volgende lyn van wat ons moet doen. 496 00:25:35,065 --> 00:25:37,840 So as jy ouens wil begin af, wat is die eerste ding wat 497 00:25:37,840 --> 00:25:40,600 om te doen wanneer jy probeer om te implementeer 'n manier om hierdie program te los 498 00:25:40,600 --> 00:25:43,480 om 'n lys selektief sorteer? 499 00:25:43,480 --> 00:25:46,349 Laat ons net ons aanvaar het 'n skikking, alles reg? 500 00:25:46,349 --> 00:25:49,088 >> GEHOOR: Jy wil 'n paar te skep soort van [onhoorbaar] dat jy 501 00:25:49,088 --> 00:25:50,420 loop deur jou hele skikking. 502 00:25:50,420 --> 00:25:51,128 >> ANDI Peng: Right. 503 00:25:51,128 --> 00:25:54,100 So jy gaan wil Itereer deur elke ruimte, reg? 504 00:25:54,100 --> 00:26:05,490 So, groot. 505 00:26:05,490 --> 00:26:08,600 As jy ouens wil my gee volgende line-- ja, in die rug. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> GEHOOR: Check hulle alles vir die kleinste. 508 00:26:13,290 --> 00:26:14,248 >> ANDI Peng: Daar gaan ons. 509 00:26:14,248 --> 00:26:17,438 So ons wil om deur te gaan en kyk na sien wat die minimum waarde is, reg? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Ek gaan afkort dat "min." 512 00:26:24,840 --> 00:26:27,658 Wat doen jy ouens wil doen na jy die minimum waarde gevind het? 513 00:26:27,658 --> 00:26:28,533 >> GEHOOR: [onhoorbaar] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI Peng: So jy gaan om te wil skakel dit met die eerste van wat skikking, 516 00:26:33,150 --> 00:26:33,650 reg? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 Dit is die begin, ek gaan om te sê. 519 00:26:46,850 --> 00:26:47,220 Alles reg. 520 00:26:47,220 --> 00:26:50,386 So nou dat jy het omgeruil die eerste een, doen wat jy wil doen nadat dit? 521 00:26:50,386 --> 00:26:54,840 So nou weet ons dat hierdie een hier moet die kleinste waarde wees, reg? 522 00:26:54,840 --> 00:26:58,310 Dan moet jy 'n bykomende rus van die skikking wat ongesorteerde. 523 00:26:58,310 --> 00:27:01,569 So wat jy wil hê om hier te doen, as jy ouens wil vir my die volgende reël te gee? 524 00:27:01,569 --> 00:27:04,610 GEHOOR: So dan wil hê jy moet Itereer deur die res van die skikking. 525 00:27:04,610 --> 00:27:05,276 ANDI Peng: Ja. 526 00:27:05,276 --> 00:27:09,857 En so wat beteken iterating deur soort impliseer ons sal waarskynlik nodig? 527 00:27:09,857 --> 00:27:10,440 Watter tipe of-- 528 00:27:10,440 --> 00:27:12,057 >> GEHOOR: Ag, 'n addisionele veranderlike? 529 00:27:12,057 --> 00:27:13,890 ANDI Peng: Waarskynlik 'n ander vir lus, reg? 530 00:27:13,890 --> 00:27:28,914 So ons waarskynlik gaan om te wil through-- wonderlik om Itereer. 531 00:27:28,914 --> 00:27:31,830 En dan moet jy gaan om terug te gaan en check waarskynlik die minimum weer 532 00:27:31,830 --> 00:27:32,100 reg? 533 00:27:32,100 --> 00:27:34,975 En jy gaan hou herhaal hierdie, omdat die loops net gaan 534 00:27:34,975 --> 00:27:36,010 hou hardloop, reg? 535 00:27:36,010 --> 00:27:39,190 >> So as julle kan sien, het ons net 'n algemene pseudokode 536 00:27:39,190 --> 00:27:41,480 hoe ons wil hierdie program te kyk. 537 00:27:41,480 --> 00:27:46,646 Dit iteraat hier, wat doen ons tipies nodig om te skryf in ons kode 538 00:27:46,646 --> 00:27:49,270 as ons wil Itereer deur 'n skikking, watter tipe struktuur? 539 00:27:49,270 --> 00:27:51,030 Ek dink Christabel reeds hierdie gesê tevore. 540 00:27:51,030 --> 00:27:51,500 >> GEHOOR: 'n lus. 541 00:27:51,500 --> 00:27:52,160 >> ANDI Peng: 'n lus? 542 00:27:52,160 --> 00:27:52,770 Presies. 543 00:27:52,770 --> 00:27:56,060 So is dit waarskynlik gaan 'n lus vir. 544 00:27:56,060 --> 00:27:59,240 Wat is 'n tjek hier gaan om te impliseer? 545 00:27:59,240 --> 00:28:02,536 Tipies, as jy wil om te kyk as iets is iets else-- 546 00:28:02,536 --> 00:28:03,270 >> GEHOOR: As. 547 00:28:03,270 --> 00:28:06,790 >> ANDI Peng: 'n as, reg? 548 00:28:06,790 --> 00:28:10,790 En dan is die ruil hier, sal ons gaan oor later, want David 549 00:28:10,790 --> 00:28:12,770 het deur dat lesing as well. 550 00:28:12,770 --> 00:28:14,580 En dan die tweede iteraat implies-- 551 00:28:14,580 --> 00:28:15,120 >> GEHOOR: Nog lus. 552 00:28:15,120 --> 00:28:16,745 >> ANDI Peng: --another lus, presies. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 So as ons kyk op hierdie reg, ons 555 00:28:22,000 --> 00:28:24,680 kan sien dat ons is waarskynlik gaan 'n geneste lus nodig 556 00:28:24,680 --> 00:28:28,330 met 'n voorwaardelike verklaring daar en dan 'n werklike stuk kode wat 557 00:28:28,330 --> 00:28:31,360 gaan om die waardes te ruil. 558 00:28:31,360 --> 00:28:35,980 So ek het net oor die algemeen geskryf 'n pseudokode kode hier. 559 00:28:35,980 --> 00:28:38,910 En dan is ons eintlik gaan fisies, as 'n klas, 560 00:28:38,910 --> 00:28:40,700 probeer om te implementeer dit vandag. 561 00:28:40,700 --> 00:28:42,486 Kom ons gaan terug na hierdie 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 Hoekom is dit not-- daar is dit. 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 Jammer, laat ek probeer in 'n bietjie meer te zoom. 568 00:28:57,500 --> 00:28:59,310 Daar gaan ons. 569 00:28:59,310 --> 00:29:05,060 Al wat ek hier doen, is wat ek gemaak het 'n program genaamd "seleksie / sort.c." 570 00:29:05,060 --> 00:29:10,860 Ek het 'n verskeidenheid van nege geskep waardes, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 Tans as wat jy kan sien, is hulle geordende. 572 00:29:14,370 --> 00:29:17,880 N gaan die aantal wees dat vertel jy die bedrag van waardes 573 00:29:17,880 --> 00:29:18,920 jy in jou skikking. 574 00:29:18,920 --> 00:29:20,670 In hierdie geval, het ons nege waardes. 575 00:29:20,670 --> 00:29:23,760 En ek het net 'n lus vir die hier wat word vertoon die ongesorteerde skikking. 576 00:29:23,760 --> 00:29:28,370 >> En aan die einde, het ek ook 'n vir lus wat net druk dit weer uit. 577 00:29:28,370 --> 00:29:32,070 So teoreties, as hierdie program korrek werk, aan die einde, 578 00:29:32,070 --> 00:29:35,670 jy moet sien vir 'n gedrukte lus waarin 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 is almal korrek in orde is. 580 00:29:39,310 --> 00:29:43,410 >> So het ons ons pseudokode het hier. 581 00:29:43,410 --> 00:29:46,090 Is daar iemand wat wil aan- Ek is net gaan om te gaan vra vir volunteers-- 582 00:29:46,090 --> 00:29:49,540 my vertel presies wat om te tik as ons wil, eerste, net Itereer 583 00:29:49,540 --> 00:29:52,840 deur die begin van hierdie reeks? 584 00:29:52,840 --> 00:29:55,204 Wat is die reël van die kode Ek is waarskynlik gaan hier nodig? 585 00:29:55,204 --> 00:29:56,990 >> GEHOOR: [onhoorbaar] 586 00:29:56,990 --> 00:29:59,010 >> ANDI Peng: Ja, voel gratis aan- jammer, jy 587 00:29:59,010 --> 00:30:02,318 hoef nie te up-- gevoel staan vry om jou stem te verhef 'n bietjie. 588 00:30:02,318 --> 00:30:08,190 >> GEHOOR: Vir int i gelyk 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI Peng: Ja, goed. 590 00:30:10,690 --> 00:30:15,220 >> GEHOOR: i is minder as array lengte. 591 00:30:15,220 --> 00:30:19,630 >> ANDI Peng: So hou in omgee hier, want ons 592 00:30:19,630 --> 00:30:23,060 nie 'n funksie nie daardie vertel ons die lengte van 'n skikking, 593 00:30:23,060 --> 00:30:25,790 Ons het reeds 'n waarde dat stoor. 594 00:30:25,790 --> 00:30:27,920 Reg? 595 00:30:27,920 --> 00:30:31,010 Nog 'n ding om te hou in mind-- in 'n skikking 596 00:30:31,010 --> 00:30:33,940 nege waardes, wat die indekse? 597 00:30:33,940 --> 00:30:38,720 Laat ons net sê dit was array 0-3. 598 00:30:38,720 --> 00:30:41,500 Jy sien dat die laaste indeks is eintlik 3. 599 00:30:41,500 --> 00:30:45,530 Dit is nie 4, selfs al is daar vier waardes in die skikking. 600 00:30:45,530 --> 00:30:49,866 >> So hier het ons baie versigtig te wees van wat ons toestand vir die lengte 601 00:30:49,866 --> 00:30:50,490 gaan wees. 602 00:30:50,490 --> 00:30:51,948 >> GEHOOR: Sou dit nie n minus 1? 603 00:30:51,948 --> 00:30:54,440 ANDI Peng: Dit gaan N minus 1, presies. 604 00:30:54,440 --> 00:30:57,379 Maak dit sin, waarom dit is n minus 1, almal? 605 00:30:57,379 --> 00:30:58,920 Dit is omdat skikkings is nul-geïndekseer. 606 00:30:58,920 --> 00:31:02,010 Hulle begin by 0 en aanloop tot N minus 1. 607 00:31:02,010 --> 00:31:03,210 Ja, dit is 'n bietjie lastig. 608 00:31:03,210 --> 00:31:03,730 OK. 609 00:31:03,730 --> 00:31:05,929 En toe-- 610 00:31:05,929 --> 00:31:08,054 GEHOOR: Isnt'1 dat reeds versorg al is, 611 00:31:08,054 --> 00:31:11,400 deur net sê nie "minder as of gelyk aan "en net sê" minder as? " 612 00:31:11,400 --> 00:31:13,108 >> ANDI Peng: Dit is 'n regtig 'n goeie vraag. 613 00:31:13,108 --> 00:31:13,630 So, ja. 614 00:31:13,630 --> 00:31:17,410 Maar ook, die manier waarop ons die implementering van die kontrole reg 615 00:31:17,410 --> 00:31:19,120 wat jy nodig het om twee waardes te vergelyk. 616 00:31:19,120 --> 00:31:21,009 So wat jy eintlik wil laat die "na" leeg. 617 00:31:21,009 --> 00:31:23,050 Want as jy vergelyk hierdie een, jy gaan nie 618 00:31:23,050 --> 00:31:25,530 iets nadat dit te vergelyk met, reg? 619 00:31:25,530 --> 00:31:27,460 Ja. 620 00:31:27,460 --> 00:31:29,297 So i ++. 621 00:31:29,297 --> 00:31:30,380 Kom ons voeg ons in hakies. 622 00:31:30,380 --> 00:31:30,880 Oeps. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Groot. 625 00:31:34,710 --> 00:31:39,117 So het ons die begin van ons buitenste lus. 626 00:31:39,117 --> 00:31:41,450 So nou waarskynlik wil ons skep 'n veranderlike vir die behoud van 627 00:31:41,450 --> 00:31:43,085 spoor van die kleinste waarde, reg? 628 00:31:43,085 --> 00:31:45,751 Is daar iemand wat my wil die gee lyn van kode wat dit sou doen? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Wat moet ons as ons gaan om iets wil stoor? 631 00:31:53,570 --> 00:31:55,047 >> Reg. 632 00:31:55,047 --> 00:31:57,630 Miskien 'n beter naam vir daardie sou be-- "temp" heeltemal works-- 633 00:31:57,630 --> 00:32:00,655 miskien 'n meer gepaste naam sou wees, As ons wil hê dat die kleinste value-- 634 00:32:00,655 --> 00:32:01,624 >> GEHOOR: Min. 635 00:32:01,624 --> 00:32:02,790 ANDI Peng: min, is daar gaan ons. 636 00:32:02,790 --> 00:32:05,230 min sal goed wees. 637 00:32:05,230 --> 00:32:08,340 En so hier is, wat ons doen dit wil inisialiseer om? 638 00:32:08,340 --> 00:32:09,620 Dit is 'n bietjie lastig. 639 00:32:09,620 --> 00:32:13,580 Want nou by die begin van hierdie reeks, 640 00:32:13,580 --> 00:32:15,730 jy nie gekyk na enigiets, reg? 641 00:32:15,730 --> 00:32:19,200 So, wat outomaties as ons is net op i gelyk 0, 642 00:32:19,200 --> 00:32:22,302 wat wil ons inisialiseer ons eerste minimum waarde? 643 00:32:22,302 --> 00:32:22,802 GEHOOR: i. 644 00:32:22,802 --> 00:32:24,790 ANDI Peng: i, presies. 645 00:32:24,790 --> 00:32:27,040 Christabel, waarom wil ons om dit te inisialiseer om i? 646 00:32:27,040 --> 00:32:28,510 >> GEHOOR: Omdat, goed, ons begin met 0. 647 00:32:28,510 --> 00:32:31,660 So, want ons het niks om te vergelyk dit is die minimum sal uiteindelik '0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI Peng: Presies. 649 00:32:32,451 --> 00:32:34,400 So sy is presies reg. 650 00:32:34,400 --> 00:32:36,780 Want ons het nie eintlik gekyk na enigiets nie, 651 00:32:36,780 --> 00:32:38,680 Ons weet nie wat ons minimum waarde is. 652 00:32:38,680 --> 00:32:41,960 Ons wil net inisialiseer dit i, wat tans, is hier. 653 00:32:41,960 --> 00:32:44,750 En as ons voortgaan om hierdie verskeidenheid te beweeg af, 654 00:32:44,750 --> 00:32:48,122 ons sal sien dat met elke addisionele pas, i vermeerderings. 655 00:32:48,122 --> 00:32:49,830 En so op daardie punt, i is waarskynlik gaan 656 00:32:49,830 --> 00:32:52,329 wil tot die minimum te wees, want dit gaan alles wees 657 00:32:52,329 --> 00:32:54,520 is die begin van die ongesorteerde skikking. 658 00:32:54,520 --> 00:32:55,270 Koel. 659 00:32:55,270 --> 00:32:58,720 >> So nou wil ons voeg 'n lus vir die wat hier 660 00:32:58,720 --> 00:33:03,225 gaan Itereer deur die ongesorteerde, of die res van hierdie skikking. 661 00:33:03,225 --> 00:33:05,808 Is daar iemand wat my wil gee 'n lyn van kode wat dit sou doen? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- wat doen ons hier nodig het af? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 Wat gaan om te gaan in hierdie lus? 666 00:33:18,820 --> 00:33:19,465 Ja. 667 00:33:19,465 --> 00:33:21,590 GEHOOR: So ons wil wil 'n ander heelgetal, 668 00:33:21,590 --> 00:33:25,080 want ons loop deur die res van die skikking in plaas van die i, so miskien 669 00:33:25,080 --> 00:33:25,760 j. 670 00:33:25,760 --> 00:33:27,301 >> ANDI Peng: Ja, j klink goed vir my. 671 00:33:27,301 --> 00:33:27,850 Gelyk? 672 00:33:27,850 --> 00:33:33,930 >> GEHOOR: So sal ek plus 1, want jy begin by die volgende waarde. 673 00:33:33,930 --> 00:33:40,395 En dan na die end-- dit weer, j is minder as N minus 1, en dan j ++. 674 00:33:40,395 --> 00:33:41,103 ANDI Peng: Groot. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> En dan hier, ons gaan om te wil om te kyk om te sien of ons toestand nagekom word nie, 677 00:33:52,750 --> 00:33:53,250 reg? 678 00:33:53,250 --> 00:33:55,740 Want jy wil verander die minimum waarde 679 00:33:55,740 --> 00:33:58,700 As dit is eintlik kleiner as wat jy dit te vergelyk met, reg? 680 00:33:58,700 --> 00:34:01,146 So, wat gaan ons wil hier? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Kyk om te sien. 683 00:34:04,897 --> 00:34:06,730 Watter tipe verklaring ons waarskynlik gaan 684 00:34:06,730 --> 00:34:08,389 ti wil gebruik as ons iets wil gaan? 685 00:34:08,389 --> 00:34:09,360 >> GEHOOR: 'n verklaring as. 686 00:34:09,360 --> 00:34:10,485 >> ANDI Peng: 'n verklaring as. 687 00:34:10,485 --> 00:34:13,155 So if-- en wat gaan wees die voorwaarde dat ons wil binnekant 688 00:34:13,155 --> 00:34:13,988 van ons as stelling? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> GEHOOR: As die waarde van j minder is as die waarde van i-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI Peng: Presies. 692 00:34:24,600 --> 00:34:27,480 So if-- so hierdie verskeidenheid is die sogenaamde "skikking." 693 00:34:27,480 --> 00:34:27,980 Groot. 694 00:34:27,980 --> 00:34:30,465 So as array-- wat was dit? 695 00:34:30,465 --> 00:34:31,090 Sê dat die weer. 696 00:34:31,090 --> 00:34:39,590 >> GEHOOR: As array-j is minder as array-i, dan sou ons die min verander. 697 00:34:39,590 --> 00:34:41,590 So die min sou j wees. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI Peng: Maak dit sin? 700 00:34:47,249 --> 00:34:48,670 OK. 701 00:34:48,670 --> 00:34:52,929 En nou hier, ons eintlik wil die swap implementeer, reg? 702 00:34:52,929 --> 00:34:58,285 So onthou, in lesing, wat Dawid toe Hy het probeer om the-- wat wissel 703 00:34:58,285 --> 00:34:59,996 it-- lemoensap en milk-- 704 00:34:59,996 --> 00:35:01,150 >> GEHOOR: Dit was die bruto. 705 00:35:01,150 --> 00:35:02,816 >> ANDI Peng: Ja, dit was soort van die bruto. 706 00:35:02,816 --> 00:35:05,310 Maar dit was 'n baie goeie konsep toon tyd. 707 00:35:05,310 --> 00:35:08,430 So dink jou waardes hier. 708 00:35:08,430 --> 00:35:10,794 Jy het 'n verskeidenheid het van min, 'n verskeidenheid van i, 709 00:35:10,794 --> 00:35:12,460 of wat ook al ons probeer om hier te ruil. 710 00:35:12,460 --> 00:35:15,310 En jy waarskynlik kan hulle nie gooi in mekaar op dieselfde tyd, reg? 711 00:35:15,310 --> 00:35:17,180 So wat gaan ons nodig om hier te skep 712 00:35:17,180 --> 00:35:19,126 om die waardes korrek te ruil? 713 00:35:19,126 --> 00:35:19,820 >> GEHOOR: 'n tydelike veranderlike. 714 00:35:19,820 --> 00:35:21,370 >> ANDI Peng: 'n tydelike veranderlike. 715 00:35:21,370 --> 00:35:22,570 So kom ons doen int temp. 716 00:35:22,570 --> 00:35:25,681 Kyk, dit sou 'n beter tyd aan- whoa, wat was dit? 717 00:35:25,681 --> 00:35:26,180 OK. 718 00:35:26,180 --> 00:35:29,800 So dit 'n beter sou gewees het tyd om die veranderlike "temp." noem 719 00:35:29,800 --> 00:35:30,730 So kom ons doen int temp. 720 00:35:30,730 --> 00:35:32,563 Wat gaan ons stel temp gelyk aan hier? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 GEHOOR: Min? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI Peng: Dit is 'n bietjie lastig. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 Dit maak eintlik nie saak nie in die einde. 727 00:35:44,880 --> 00:35:47,690 Dit maak nie saak wat volgorde wat jy wil om te ruil in 728 00:35:47,690 --> 00:35:50,862 so lank as wat jy maak seker dat jy dop van wat jy uitruiling. 729 00:35:50,862 --> 00:35:52,250 >> GEHOOR: Dit kan array-i wees. 730 00:35:52,250 --> 00:35:53,666 >> ANDI Peng: Ja, kom ons doen array-i. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 En dan Wat is die volgende lyn van die kode wat ons hier wil hê? 733 00:35:59,305 --> 00:36:00,680 GEHOOR: array-i gelyk array-j. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI Peng: En laastens? 736 00:36:08,070 --> 00:36:12,070 GEHOOR: array-j gelyk array-i. 737 00:36:12,070 --> 00:36:14,525 GEHOOR: Of array-j gelykes array-temp-- of, 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 So laat hierdie hardloop en sien As dit gaan om te werk. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Waar is dit gebeur? 743 00:36:39,335 --> 00:36:40,210 O, dit is 'n probleem. 744 00:36:40,210 --> 00:36:44,320 Kyk, op die lyn 40, ons is probeer om array-j gebruik? 745 00:36:44,320 --> 00:36:47,022 Maar waar kom j slegs bestaan ​​in? 746 00:36:47,022 --> 00:36:48,402 >> GEHOOR: In die lus. 747 00:36:48,402 --> 00:36:49,110 ANDI Peng: Right. 748 00:36:49,110 --> 00:36:51,730 So, wat gaan ons doen? 749 00:36:51,730 --> 00:36:53,170 >> GEHOOR: Definieer dit buite the-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 GEHOOR: Ja, ek dink jy het na 'n ander gebruik as verklaring, reg? 752 00:37:00,610 --> 00:37:05,230 Dus, net soos, as die minimum-- Alle reg, laat my dink. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI Peng: Guys, probeer om 'n blik Kom ons neem 755 00:37:09,990 --> 00:37:11,270 sien, wat is iets wat ons kan hier doen? 756 00:37:11,270 --> 00:37:11,811 >> GEHOOR: OK. 757 00:37:11,811 --> 00:37:15,900 So as die minimum nie gelyk j-- so as die minimum is nog i-- 758 00:37:15,900 --> 00:37:17,570 dan sou ons nie hoef te ruil. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI Peng: Is dit gelyk i? 761 00:37:24,712 --> 00:37:25,920 Wat wil jy hier sê? 762 00:37:25,920 --> 00:37:30,494 >> GEHOOR: Of ja, as die minimum nie gelyk 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 Goed dat lost, soort, ons probleme. 766 00:37:42,040 --> 00:37:47,265 Maar wat nog los nie die probleem van wat gebeur as j-- sedert j 767 00:37:47,265 --> 00:37:49,890 bestaan ​​nie buite dit, wat wil jy ons om te doen met dit? 768 00:37:49,890 --> 00:37:50,698 Verklaar dat dit buite? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Kom ons probeer om hierdie. 771 00:38:02,730 --> 00:38:04,435 Uh Oh. 772 00:38:04,435 --> 00:38:06,200 Ons soort werk nie. 773 00:38:06,200 --> 00:38:10,060 >> Soos jy, ons eerste kan sien array het daardie waardes. 774 00:38:10,060 --> 00:38:14,800 En daarna sal dit moet hê was in 1, 2, 3, 4, 5, 6, 7, 8, 9. 775 00:38:14,800 --> 00:38:15,530 Dit werk nie. 776 00:38:15,530 --> 00:38:16,030 Ahh. 777 00:38:16,030 --> 00:38:17,184 Wat doen ons? 778 00:38:17,184 --> 00:38:17,850 GEHOOR: Debug. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI Peng: Alle reg, kan ons probeer dit. 781 00:38:23,370 --> 00:38:25,030 Ons kan ontfout. 782 00:38:25,030 --> 00:38:26,042 Zoom uit 'n bietjie. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Kom ons stel ons breekpunt. 785 00:38:33,656 --> 00:38:37,280 Kom ons gaan like-- OK. 786 00:38:37,280 --> 00:38:40,444 >> So, omdat ons reeds weet dat hierdie lyne, 15 deur 22, 787 00:38:40,444 --> 00:38:43,610 is working-- want al wat ek doen is net iterating deur en printing-- 788 00:38:43,610 --> 00:38:45,406 Ek kan voortgaan en slaan dit. 789 00:38:45,406 --> 00:38:47,280 Kom ons begin by lyn 25. 790 00:38:47,280 --> 00:38:48,712 Oop, laat my ontslae te raak van daardie. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> GEHOOR: So het die breekpunt se waar die ontfouting begin? 793 00:38:54,057 --> 00:38:54,890 ANDI Peng: of stop. 794 00:38:54,890 --> 00:38:55,670 GEHOOR: of stop. 795 00:38:55,670 --> 00:38:55,930 ANDI Peng: Ja. 796 00:38:55,930 --> 00:38:58,640 Jy kan verskeie inbreekpunt stel en dit kan net spring van die een na die ander. 797 00:38:58,640 --> 00:39:01,590 Maar in hierdie geval weet ons nie waar die fout gebeur. 798 00:39:01,590 --> 00:39:03,780 So wil ons net begin van die top-down. 799 00:39:03,780 --> 00:39:05,020 Yep. 800 00:39:05,020 --> 00:39:05,550 OK. 801 00:39:05,550 --> 00:39:08,460 >> So hierdie lyn hier, kan ons ingryp. 802 00:39:08,460 --> 00:39:11,499 Jy kan hier af sien, ons het 'n skikking. 803 00:39:11,499 --> 00:39:13,290 Dit is die waardes wat in die skikking. 804 00:39:13,290 --> 00:39:16,360 Het jy sien dat, hoe indeks 0, dit ooreenstem met die value-- oh, 805 00:39:16,360 --> 00:39:17,526 Ek gaan probeer om in te zoom. 806 00:39:17,526 --> 00:39:20,650 Jammer, dit is regtig hard om see-- op array indeks 0, 807 00:39:20,650 --> 00:39:24,090 ons het 'n waarde van 4 en dan so meer en so aan. 808 00:39:24,090 --> 00:39:25,670 Ons het ons plaaslike veranderlikes. 809 00:39:25,670 --> 00:39:28,570 Nou i is gelyk aan 0, wat ons wil hê dit moet wees. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> En so laat ons hou versterking deur middel van. 812 00:39:33,690 --> 00:39:36,850 Ons minimum is gelyk aan 0, wat ons wil dit ook te wees. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 En dan gaan ons ons tweede vir lus, as array-j is minder as array-i, 815 00:39:45,560 --> 00:39:46,380 wat dit was nie. 816 00:39:46,380 --> 00:39:48,130 So het jy sien hoe wat oorgeslaan oor dit? 817 00:39:48,130 --> 00:39:52,430 >> GEHOOR: So moet die as minimum, almal that-- behoort dit nie 818 00:39:52,430 --> 00:39:55,424 wees binne die eerste lus? 819 00:39:55,424 --> 00:39:57,340 ANDI Peng: Nee, want jy nog steeds wil om te toets. 820 00:39:57,340 --> 00:40:00,329 Jy wil 'n vergelyking doen elke tyd, selfs nadat jy deur dit uit te voer. 821 00:40:00,329 --> 00:40:02,620 Jy wil nie net om dit te doen op die eerste pass-through. 822 00:40:02,620 --> 00:40:05,240 Jy wil om dit te doen met elke bykomende pass weer. 823 00:40:05,240 --> 00:40:07,198 So jy wil om te kyk vir jou toestand binne. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 So ons is maar net gaan hou hardloop deur hier. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Ek gee jou 'n wenk ouens. 828 00:40:18,420 --> 00:40:23,910 Dit het te doen met die feit dat wanneer jy keur van jou afhanklik is, 829 00:40:23,910 --> 00:40:26,600 jy nie die nagaan vir die korrekte indeks. 830 00:40:26,600 --> 00:40:32,510 So nou is jy kontrole vir verskeidenheid indeks van j is minder as array 831 00:40:32,510 --> 00:40:33,970 indeks van i. 832 00:40:33,970 --> 00:40:36,580 Maar wat doen jy by die begin van die lus? 833 00:40:36,580 --> 00:40:38,260 Is jy nie die opstel van j gelyk aan i? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Ja, so ons kan eintlik verlaat hier die debugger. 836 00:40:45,415 --> 00:40:47,040 So laat ons neem 'n blik op ons pseudokode. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- ons gaan begin by i gelyk 0. 839 00:40:52,580 --> 00:40:54,760 Ons gaan om te gaan om n minus 1. 840 00:40:54,760 --> 00:40:58,040 Kom ons kyk, het ons het dit reg? 841 00:40:58,040 --> 00:40:59,580 Yep, dit is reg. 842 00:40:59,580 --> 00:41:02,080 >> So dan binnekant hier, ons is gaan 'n minimum waarde te skep 843 00:41:02,080 --> 00:41:03,630 en stel wat gelyk is aan i. 844 00:41:03,630 --> 00:41:04,950 Het ons dit doen? 845 00:41:04,950 --> 00:41:06,270 Yep, het dit gedoen. 846 00:41:06,270 --> 00:41:10,430 Nou in ons innerlike lus, ons is gaan j doen is gelyk aan i om n 1 minus. 847 00:41:10,430 --> 00:41:11,950 Het ons dit doen? 848 00:41:11,950 --> 00:41:15,540 Inderdaad, ons het dit gedoen. 849 00:41:15,540 --> 00:41:19,922 >> So egter, wat ons hier te vergelyk? 850 00:41:19,922 --> 00:41:20,925 >> GEHOOR: j plus 1. 851 00:41:20,925 --> 00:41:21,716 ANDI Peng: Presies. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 En dan moet jy gaan om te wil stel jou minimum gelyk aan j plus 1 as well. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 So ek het deur dit regtig vinnig. 856 00:41:32,640 --> 00:41:36,190 Het jy ouens verstaan Daarom is dit j plus 1? 857 00:41:36,190 --> 00:41:36,890 OK. 858 00:41:36,890 --> 00:41:40,700 >> So in jou skikking, in jou eerste deurgaan 859 00:41:40,700 --> 00:41:44,850 jou lus vir int i gelyk 0, laat ons net 860 00:41:44,850 --> 00:41:46,740 neem aan dit is nog nie verander nie. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 Ons het 'n verskeidenheid van, heeltemal, net vier ongesorteerde elemente, reg? 863 00:41:56,760 --> 00:42:00,760 So wil ons inisialiseer i gelyk aan 0. 864 00:42:00,760 --> 00:42:03,650 En ek gaan net hardloop deur middel van hierdie lus. 865 00:42:03,650 --> 00:42:08,560 En so in die eerste slaag, gaan ons om 'n veranderlike genaamd "min" inisialiseer 866 00:42:08,560 --> 00:42:11,245 wat ook gelyk i, want Ons het nie 'n minimum waarde. 867 00:42:11,245 --> 00:42:12,870 So dit is tans gelyk aan 0 as well. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 En dan gaan ons om deur te gaan. 870 00:42:17,640 --> 00:42:19,270 En ons wil weer Itereer. 871 00:42:19,270 --> 00:42:22,900 Nou dat ons het gevind wat ons minimum is, wil ons deur Itereer 872 00:42:22,900 --> 00:42:25,190 weer om te sien of dit vergelyk, reg? 873 00:42:25,190 --> 00:42:40,440 So j, hier, gaan gelyke i, wat is 0. 874 00:42:40,440 --> 00:42:46,320 En dan as array j plus i, wat is die een wat volgende kom oor, as minder 875 00:42:46,320 --> 00:42:49,270 as wat jou huidige minimum waarde is, wat jy wil ruil. 876 00:42:49,270 --> 00:42:56,850 >> So laat ons net sê ons het het, soos, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Nou, i is gelyk aan 0 en j is gelyk aan 0. 878 00:43:01,610 --> 00:43:05,210 En dit is ons minimum waarde. 879 00:43:05,210 --> 00:43:09,950 As array-j plus i-- so as die een dit is na die een wat ons is op soek na 880 00:43:09,950 --> 00:43:13,450 is groter as die een voor dit, dit gaan tot die minimum te word. 881 00:43:13,450 --> 00:43:18,120 >> So hier sien ons dat 5 is nie minder nie as dit. 882 00:43:18,120 --> 00:43:19,730 So dit gaan nie 5. 883 00:43:19,730 --> 00:43:23,580 Ons sien dat 1 is minder as 2, reg? 884 00:43:23,580 --> 00:43:32,970 So nou weet ons dat ons minimum is gaan die indeks waarde by 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Ja? 886 00:43:34,030 --> 00:43:39,170 En dan wanneer jy hier sit, kan jy ruil die korrekte waardes. 887 00:43:39,170 --> 00:43:42,610 >> So wanneer jy ouens was net met die j voor, was jy nie op soek na die een 888 00:43:42,610 --> 00:43:43,260 nadat dit. 889 00:43:43,260 --> 00:43:44,520 Jy is op soek na dieselfde waarde, wat 890 00:43:44,520 --> 00:43:46,290 Daarom het hulle dit net nie om iets te doen. 891 00:43:46,290 --> 00:43:49,721 Maak dit sin om almal, waarom ons dat daar plus 1 nodig? 892 00:43:49,721 --> 00:43:50,220 OK. 893 00:43:50,220 --> 00:43:53,345 Nou laat net loop deur dit te maak seker dat die res van die kode korrek is. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Hoekom is dit gebeur? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ag, dit is die min hier. 898 00:44:16,364 --> 00:44:17,780 Ons was die verkeerde waarde vergelyk. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 Ag nee. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> O ja, hier af was ons uitruiling die verkeerde waardes as well. 903 00:44:33,482 --> 00:44:34,940 Want ons is op soek na i en j. 904 00:44:34,940 --> 00:44:36,440 Dit is die mense wat ons nagaan is. 905 00:44:36,440 --> 00:44:39,160 Ons het eintlik wil hê dat die ruil minimum, die huidige minimum, 906 00:44:39,160 --> 00:44:40,550 met alles wat die mens buite is. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 En as julle kan sien af hier het ons 'n gesorteerde skikking. 909 00:45:05,402 --> 00:45:07,110 Dit het net te doen met die feit dat wanneer 910 00:45:07,110 --> 00:45:09,350 ons die beheer van die waardes wat ons is te vergelyk, 911 00:45:09,350 --> 00:45:11,226 ons was nie op soek na die regte waardes. 912 00:45:11,226 --> 00:45:13,850 Ons is op soek na dieselfde een hier, nie eintlik uitruiling dit. 913 00:45:13,850 --> 00:45:17,135 Jy het om te kyk na die volgende een om dit en dan kan jy ruil. 914 00:45:17,135 --> 00:45:19,260 So dit is wat was soort van afluister ons kode tevore. 915 00:45:19,260 --> 00:45:22,460 En wat ek gedoen het hier is alles die debugger kon gedoen het vir jou 916 00:45:22,460 --> 00:45:23,810 Ek het dit net op die raad, want dit is makliker 917 00:45:23,810 --> 00:45:26,320 eerder as om te probeer sien om in te zoem op die debugger. 918 00:45:26,320 --> 00:45:29,391 Maak dit sin om almal? 919 00:45:29,391 --> 00:45:29,890 Koel. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Alles reg. 922 00:45:35,410 --> 00:45:41,070 Ons kan aanbeweeg na praat asimptotiese notasie, wat 923 00:45:41,070 --> 00:45:44,580 is net 'n fancy manier om te sê die Runtimes van al hierdie vorme. 924 00:45:44,580 --> 00:45:47,650 So ek weet Dawid in lesing aangeraak Runtimes. 925 00:45:47,650 --> 00:45:52,124 En hy het deur die hele formule hoe om die Runtimes bereken. 926 00:45:52,124 --> 00:45:53,040 Geen bekommernisse oor dit. 927 00:45:53,040 --> 00:45:54,660 As jy regtig nuuskierig op hoe dit werk, 928 00:45:54,660 --> 00:45:55,810 voel vry om my te praat na artikel. 929 00:45:55,810 --> 00:45:57,560 Ons kan loop deur die formules saam. 930 00:45:57,560 --> 00:46:00,689 Maar al wat jy ouens het regtig weet, is dat n kwadraat oor 2 931 00:46:00,689 --> 00:46:01,980 is dieselfde ding as N kwadraat. 932 00:46:01,980 --> 00:46:04,710 Omdat die grootste getal, die eksponent, groei die meeste. 933 00:46:04,710 --> 00:46:06,590 En so is dit vir ons doeleindes, al wat ons omgee 934 00:46:06,590 --> 00:46:09,470 is dat reuse getal wat groei. 935 00:46:09,470 --> 00:46:13,340 >> So, wat is die beste geval runtime van seleksie soort? 936 00:46:13,340 --> 00:46:15,830 As jy gaan om om Itereer deur 'n lys 937 00:46:15,830 --> 00:46:18,712 en dan Itereer deur die res van die lys, 938 00:46:18,712 --> 00:46:20,420 hoeveel keer is gaan jy waarskynlik 939 00:46:20,420 --> 00:46:24,612 in die ergste case-- in die beste geval, sorry-- deur loop? 940 00:46:24,612 --> 00:46:27,070 Dalk is dit die beter vraag is vra, wat is die ergste geval 941 00:46:27,070 --> 00:46:28,153 runtime van seleksie soort. 942 00:46:28,153 --> 00:46:29,366 GEHOOR: N kwadraat. 943 00:46:29,366 --> 00:46:30,740 ANDI Peng: Dit is N kwadraat, reg. 944 00:46:30,740 --> 00:46:36,986 So 'n maklike manier om te dink dit is soos, enige tyd wat jy twee geneste lusse vir het, 945 00:46:36,986 --> 00:46:38,110 dit gaan n word kwadraat. 946 00:46:38,110 --> 00:46:40,386 Want nie net is jy loop deur weer 947 00:46:40,386 --> 00:46:42,260 jy het om terug te gaan rond en gaan deur dit 948 00:46:42,260 --> 00:46:44,980 weer binne vir elke waarde. 949 00:46:44,980 --> 00:46:48,640 So in daardie geval, jy hardloop N keer n vierkant, wat jammer is--, 950 00:46:48,640 --> 00:46:50,505 N tye N, wat gelyk N kwadraat. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> En sorteer is ook 'n bietjie uniek in die sin 953 00:46:56,360 --> 00:46:59,774 dat dit maak nie saak of dit waardes is reeds in orde is. 954 00:46:59,774 --> 00:47:01,440 Dit is nog steeds gaan om te loop deur anyways. 955 00:47:01,440 --> 00:47:03,872 Laat ons net sê dit was 1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Ongeag of dit nie was in orde, sou dit nog steeds het gehardloop deur 957 00:47:07,080 --> 00:47:08,620 en nog steeds kyk na die minimum waarde. 958 00:47:08,620 --> 00:47:10,100 Dit sou gemaak het die dieselfde aantal tjeks 959 00:47:10,100 --> 00:47:12,780 elke keer, selfs al is dit het nie eintlik enigiets te raak. 960 00:47:12,780 --> 00:47:16,940 >> So in so 'n geval, die beste en slegste Runtimes is eintlik ekwivalent. 961 00:47:16,940 --> 00:47:19,160 So die verwagte runtime seleksie soort, 962 00:47:19,160 --> 00:47:23,790 wat ons aanwys deur die simbool van theta, theta, in hierdie geval, 963 00:47:23,790 --> 00:47:24,790 ook N vierkantig. 964 00:47:24,790 --> 00:47:26,480 Al drie hierdie sou N vierkantig. 965 00:47:26,480 --> 00:47:29,653 Is almal duidelik waarom die runtime is N kwadraat? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Alles reg. 968 00:47:33,980 --> 00:47:39,120 So ek gaan net om vinnig te hardloop deur die res van die spesies. 969 00:47:39,120 --> 00:47:41,137 Die algoritme vir borrel sort-- onthou, 970 00:47:41,137 --> 00:47:43,220 dit was die eerste een Dawid het oor in lesing. 971 00:47:43,220 --> 00:47:46,000 Wese, jy stap deur die hele lys 972 00:47:46,000 --> 00:47:48,950 en jy jy net swap-- Vergelyk twee op 'n tyd. 973 00:47:48,950 --> 00:47:51,350 En as 'n mens is 'n groter, as jy net ruil hulle. 974 00:47:51,350 --> 00:47:53,590 So as dit is groter, sou jy te ruil. 975 00:47:53,590 --> 00:47:56,180 Ek het die amptelike het hier. 976 00:47:56,180 --> 00:47:59,100 >> So laat ons net sê jy het 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Jy wil vergelyk met die 8 en 'n 6. 978 00:48:00,571 --> 00:48:01,570 Wat jy nodig het om dit te ruil. 979 00:48:01,570 --> 00:48:02,610 Jy sal die 8 en 'n 4 te vergelyk. 980 00:48:02,610 --> 00:48:03,609 Wat jy nodig het om dit te ruil. 981 00:48:03,609 --> 00:48:07,000 As jy moet ruil die 8 en die 2, verander dit net so goed. 982 00:48:07,000 --> 00:48:10,760 So in so 'n sin, kan jy sien, gespeel oor 'n lang tydperk van die tyd, 983 00:48:10,760 --> 00:48:13,730 hoe die waardes soort borrel om die einde, wat is die rede waarom ons noem dit 984 00:48:13,730 --> 00:48:15,320 borrel soort. 985 00:48:15,320 --> 00:48:19,950 >> Ons wil net loop deur weer aan ons tweede slaag, en ons derde slaag, 986 00:48:19,950 --> 00:48:21,150 en ons vierde pass. 987 00:48:21,150 --> 00:48:25,820 Wese, borrelsortering net loop totdat jy nie meer swaps te maak. 988 00:48:25,820 --> 00:48:31,109 So in daardie sin, dit is net die algemene pseudokode vir dit. 989 00:48:31,109 --> 00:48:32,650 Geen sorge, dit sal alle online wees. 990 00:48:32,650 --> 00:48:34,990 Ons hoef nie te eintlik gaan oor hierdie. 991 00:48:34,990 --> 00:48:38,134 >> Ons inisialiseer net 'n toonbank veranderlike wat begin by 0. 992 00:48:38,134 --> 00:48:39,800 En ons Itereer deur die hele skikking. 993 00:48:39,800 --> 00:48:43,420 En as een waarde is-- as dit waarde is groter as wat waarde, 994 00:48:43,420 --> 00:48:44,610 jy gaan om dit te ruil. 995 00:48:44,610 --> 00:48:46,860 En dan is jy net gaan om voort te gaan. 996 00:48:46,860 --> 00:48:47,970 En jy gaan om te tel. 997 00:48:47,970 --> 00:48:50,845 En jy net gaan om te hou doen dit terwyl die toonbank is groter 998 00:48:50,845 --> 00:48:53,345 as 0, wat beteken dat elke keer as jy moet ruil, 999 00:48:53,345 --> 00:48:55,220 jy weet jy wil gaan terug en kyk weer. 1000 00:48:55,220 --> 00:48:59,510 Jy wil nagaan hou totdat jy weet dat jy nie meer hoef te ruil. 1001 00:48:59,510 --> 00:49:05,570 >> So, wat is die beste en die ergste geval Runtimes vir borrelsortering? 1002 00:49:05,570 --> 00:49:09,300 En dit is eintlik verskillende hint-- van seleksie soort in die sin 1003 00:49:09,300 --> 00:49:11,810 dat hierdie twee antwoorde is nie dieselfde nie. 1004 00:49:11,810 --> 00:49:14,709 Dink oor wat sou gebeur in 'n geval as dit was reeds gesorteer. 1005 00:49:14,709 --> 00:49:16,500 En dink oor wat sou gebeur as dit was 1006 00:49:16,500 --> 00:49:18,372 in die geval waar dit was nie gesorteer. 1007 00:49:18,372 --> 00:49:20,580 En jy kan soort van loop deur waarom dit gebeur. 1008 00:49:20,580 --> 00:49:22,954 Ek gee jou ouens, soos, 30 sekondes om te dink oor dit. 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 Is daar iemand het 'n raaiskoot na wat die ergste geval runtime van borrel soort is? 1012 00:49:57,462 --> 00:49:57,962 Ja. 1013 00:49:57,962 --> 00:50:07,810 >> GEHOOR: sou dit wees, soos, n keer N minus 1 of iets soos dit? 1014 00:50:07,810 --> 00:50:10,650 Soos elke keer as dit loop, dit is net soos een omruil minder 1015 00:50:10,650 --> 00:50:10,960 dat alles wat dit was nie. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI Peng: Ja, so jy heeltemal reg. 1017 00:50:12,668 --> 00:50:15,940 En dit is 'n saak waarin jou antwoord was eintlik meer kompleks 1018 00:50:15,940 --> 00:50:17,240 as die een wat ons nodig het om te gee. 1019 00:50:17,240 --> 00:50:19,772 So dit gaan run-- Ek is gaan dit alles hier te vee. 1020 00:50:19,772 --> 00:50:20,480 Is almal goed? 1021 00:50:20,480 --> 00:50:21,869 Kan ek hierdie vee? 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 Jy gaan om te loop deur n keer die eerste keer, reg? 1025 00:50:30,320 --> 00:50:33,200 En hulle gaan om te loop deur N minus 1 die tweede keer, reg? 1026 00:50:33,200 --> 00:50:37,130 En dan moet jy gaan hou gaan, n myn 2, ensovoorts. 1027 00:50:37,130 --> 00:50:40,210 David het dit in 'n lesing, waar, as jy opgetel al daardie waardes, 1028 00:50:40,210 --> 00:50:48,080 jy iets wat ons kry like-- yeah-- meer as 2, wat in wese net verminder 1029 00:50:48,080 --> 00:50:49,784 af na N kwadraat. 1030 00:50:49,784 --> 00:50:51,700 Jy gaan 'n te kry weird fraksie daar. 1031 00:50:51,700 --> 00:50:53,892 En so weet net dat die N kwadraat altyd 1032 00:50:53,892 --> 00:50:55,350 voorrang bo die breuk. 1033 00:50:55,350 --> 00:50:58,450 En so in hierdie geval, die ergste runtime sou N vierkantig. 1034 00:50:58,450 --> 00:51:00,210 As dit was in dalende orde, dink jy 1035 00:51:00,210 --> 00:51:02,530 'n ruil elke keer te maak. 1036 00:51:02,530 --> 00:51:05,170 >> Wat sou, potensieel, die beste geval runtime? 1037 00:51:05,170 --> 00:51:08,580 Laat ons net sê, as die lys was reeds in orde is, wat sal die runtime wees? 1038 00:51:08,580 --> 00:51:09,565 >> GEHOOR: n. 1039 00:51:09,565 --> 00:51:10,690 ANDI Peng: Dis N, presies. 1040 00:51:10,690 --> 00:51:11,600 En waarom is dit n? 1041 00:51:11,600 --> 00:51:13,850 GEHOOR: Omdat jy net het om te kyk na elke keer. 1042 00:51:13,850 --> 00:51:14,770 ANDI Peng: Presies. 1043 00:51:14,770 --> 00:51:17,150 So in die beste moontlike runtime, As hierdie lys was reeds 1044 00:51:17,150 --> 00:51:20,270 sorted-- kom ons sê 1, 2, 3, 4-- jy wil net deur te gaan, sou jy kyk, 1045 00:51:20,270 --> 00:51:21,720 jy sou sien, o, hulle almal pan uit. 1046 00:51:21,720 --> 00:51:22,636 Ek het nie te ruil. 1047 00:51:22,636 --> 00:51:23,370 Ek is klaar. 1048 00:51:23,370 --> 00:51:26,500 So in daardie geval, dit is net n of die aantal stappe jy net 1049 00:51:26,500 --> 00:51:29,870 het in die eerste lys om seker te maak. 1050 00:51:29,870 --> 00:51:33,990 >> En ná, het ons nou getref invoeging soort, waar 1051 00:51:33,990 --> 00:51:39,260 die algoritme is in wese te verdeel dit in 'n gesorteerde en ongesorteerde gedeelte. 1052 00:51:39,260 --> 00:51:42,810 En dan een vir een, die ongesorteerde waardes 1053 00:51:42,810 --> 00:51:46,880 ingevoeg in hul toepaslike posisies in die begin van die lys. 1054 00:51:46,880 --> 00:51:52,120 >> So byvoorbeeld, het ons 'n lys van 3, 5, 2, 6, 4 weer. 1055 00:51:52,120 --> 00:51:54,750 Ons weet dat dit tans ongesorteerde, want ons het net 1056 00:51:54,750 --> 00:51:57,030 begin soek na dit. 1057 00:51:57,030 --> 00:52:00,610 Ons neem 'n blik en ons weet dat die eerste waarde is gesorteer, reg? 1058 00:52:00,610 --> 00:52:04,190 As jy net op soek na 'n verskeidenheid van grootte een, jy weet dat dit gesorteer. 1059 00:52:04,190 --> 00:52:08,230 >> So dan weet ons dat die ander vier is ongesorteerde. 1060 00:52:08,230 --> 00:52:10,980 Ons gaan deur en sien ons dat waarde. 1061 00:52:10,980 --> 00:52:11,730 Kom ons gaan terug. 1062 00:52:11,730 --> 00:52:13,130 Sien dat waarde van 5? 1063 00:52:13,130 --> 00:52:14,110 Ons neem 'n blik op dit. 1064 00:52:14,110 --> 00:52:15,204 Ons vergelyk dit met 3. 1065 00:52:15,204 --> 00:52:17,870 Ons weet dat dit is groter as 3, so ons weet dat dit is gesorteer. 1066 00:52:17,870 --> 00:52:22,940 So weet ons nou dat die eerste twee gesorteer en die laaste drie is nie. 1067 00:52:22,940 --> 00:52:24,270 >> Ons neem 'n blik op 2. 1068 00:52:24,270 --> 00:52:25,720 Ons gaan dit eers met 5. 1069 00:52:25,720 --> 00:52:26,700 Is dit minder as 5? 1070 00:52:26,700 --> 00:52:27,240 Dit is nie. 1071 00:52:27,240 --> 00:52:29,510 So het ons om aan te hou kyk neer. 1072 00:52:29,510 --> 00:52:30,940 Dan gaan jy 2 af 3. 1073 00:52:30,940 --> 00:52:31,850 Is dit minder as? 1074 00:52:31,850 --> 00:52:32,350 Geen. 1075 00:52:32,350 --> 00:52:35,430 So jy weet 'n 2 moet ingevoeg in die voorste en 3 en 5 1076 00:52:35,430 --> 00:52:38,200 beide moet word uitgestoot. 1077 00:52:38,200 --> 00:52:42,190 Doen dit weer met 6 en 4. 1078 00:52:42,190 --> 00:52:48,962 En ons het net hou keur wese, waar ons gaan net, kyk, kyk. 1079 00:52:48,962 --> 00:52:51,170 En totdat dit in die regte posisie, ons soort van net 1080 00:52:51,170 --> 00:52:54,890 plaas dit in die regte posisie, en dit is waar die naam van dit kom uit. 1081 00:52:54,890 --> 00:52:59,830 >> So dit is net die algoritme, pseudokode per se, soort van, 1082 00:52:59,830 --> 00:53:04,990 oor hoe ons sal implementeer 'n invoeging soort. 1083 00:53:04,990 --> 00:53:05,954 Pseudokode is hier. 1084 00:53:05,954 --> 00:53:06,620 Dit is alles aanlyn. 1085 00:53:06,620 --> 00:53:10,720 Geen bekommernisse as jy ouens is probeer om hierdie afskryf. 1086 00:53:10,720 --> 00:53:14,500 So weereens dieselfde question-- wat sou die beste en die ergste Runtimes wees 1087 00:53:14,500 --> 00:53:16,120 vir opname soort? 1088 00:53:16,120 --> 00:53:17,750 Dit is baie soortgelyk aan die laaste vraag. 1089 00:53:17,750 --> 00:53:20,479 Ek gee jou ouens, soos, 30 sekondes om te dink oor hierdie goed. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> OK Is daar iemand wil gee my die ergste runtime? 1092 00:53:50,071 --> 00:53:50,570 Ja. 1093 00:53:50,570 --> 00:53:51,490 >> GEHOOR: N kwadraat. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI Peng: Dit is N kwadraat. 1095 00:53:52,573 --> 00:53:53,730 En hoekom is dit N kwadraat? 1096 00:53:53,730 --> 00:53:57,562 >> GEHOOR: Want in omgekeerde volgorde, jy het 1097 00:53:57,562 --> 00:54:02,619 om te gaan deur n keer n, wat is-- 1098 00:54:02,619 --> 00:54:03,660 ANDI Peng: Ja, presies. 1099 00:54:03,660 --> 00:54:06,610 So dieselfde as in die borrel soort. 1100 00:54:06,610 --> 00:54:08,720 As hierdie lys is in dalende orde, is jy 1101 00:54:08,720 --> 00:54:11,240 gaan hê om eerste keer te kyk. 1102 00:54:11,240 --> 00:54:13,470 En dan met elke addisionele waarde, is jy 1103 00:54:13,470 --> 00:54:16,390 gaan hê om dit teen elke enkele waarde nie, reg? 1104 00:54:16,390 --> 00:54:20,290 En so geheel en al, jy gaan maak 'n N pass keer 'n ander N slaag, wat 1105 00:54:20,290 --> 00:54:21,750 is N kwadraat. 1106 00:54:21,750 --> 00:54:22,860 Wat van die beste geval? 1107 00:54:22,860 --> 00:54:24,360 Ja. 1108 00:54:24,360 --> 00:54:28,840 >> GEHOOR: N minus 1, want die eerste een is reeds in 'n vierkant. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI Peng: So, naby. 1110 00:54:30,270 --> 00:54:31,850 Die antwoord is eintlik n. 1111 00:54:31,850 --> 00:54:37,189 Want terwyl die eerste een is gesorteer, kan dit nie actually-- dit 1112 00:54:37,189 --> 00:54:38,980 ons het net lucked uit, in wat byvoorbeeld dat 2 1113 00:54:38,980 --> 00:54:40,930 gebeur met die kleinste getal wees. 1114 00:54:40,930 --> 00:54:43,680 Maar dat die saak nie altyd sal wees. 1115 00:54:43,680 --> 00:54:48,040 As 2 reeds gesorteer in die begin maar jy lyk en daar is 'n 1 hier, 1116 00:54:48,040 --> 00:54:49,144 die 1 gaan dit stamp. 1117 00:54:49,144 --> 00:54:51,060 En dit gaan aan die einde up wat anyways gestamp. 1118 00:54:51,060 --> 00:54:56,250 >> So in die beste geval, dit is eintlik net gaan om n wees. 1119 00:54:56,250 --> 00:54:59,090 As jy het 1, 2, 3, 4, 5, 6, 7, 8, is jy 1120 00:54:59,090 --> 00:55:00,940 gaan om te loop deur dat die hele lys keer 1121 00:55:00,940 --> 00:55:03,430 om te kyk om te sien of alles fyn se. 1122 00:55:03,430 --> 00:55:07,390 Is almal duidelik hardloop tye van seleksie as goed? 1123 00:55:07,390 --> 00:55:09,960 Ek weet ek gaan deur hierdie baie vinnig. 1124 00:55:09,960 --> 00:55:13,330 Maar net weet dat as jy weet wat die algemene konsepte, moet jy goed wees. 1125 00:55:13,330 --> 00:55:16,070 OK. 1126 00:55:16,070 --> 00:55:19,790 So ek sal net gee julle miskien, soos, 'n minuut om jou bure te praat 1127 00:55:19,790 --> 00:55:21,890 op wat net 'n paar van die belangrikste verskille 1128 00:55:21,890 --> 00:55:23,540 tussen hierdie tipes van spesies. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Ons sal gaan oor wat binnekort. 1131 00:56:25,570 --> 00:56:26,444 GEHOOR: O, OK. 1132 00:56:26,444 --> 00:56:27,320 ANDI Peng: Ja. 1133 00:56:27,320 --> 00:56:28,380 OK. 1134 00:56:28,380 --> 00:56:33,420 Cool, laat herbelê as 'n klas. 1135 00:56:33,420 --> 00:56:34,330 OK. 1136 00:56:34,330 --> 00:56:37,579 So dit was soort van 'n ope vraag in die sin 1137 00:56:37,579 --> 00:56:39,120 dat daar is baie van die antwoorde op hulle. 1138 00:56:39,120 --> 00:56:40,746 En ons sal oor kortliks gaan sommige van hulle. 1139 00:56:40,746 --> 00:56:43,411 Ek wou net om jou te ouens dink oor wat onderskei 1140 00:56:43,411 --> 00:56:44,530 al drie tipes van spesies. 1141 00:56:44,530 --> 00:56:47,440 En ek hoor, ook 'n groot question-- wat beteken fuseren soort doen? 1142 00:56:47,440 --> 00:56:50,110 Groot vraag, want dit is wat ons oor die volgende. 1143 00:56:50,110 --> 00:56:52,850 >> So saamsmelt soort is die een soort wat funksies 1144 00:56:52,850 --> 00:56:56,100 baie verskillend van die ander soorte. 1145 00:56:56,100 --> 00:56:58,180 As julle ouens kan see-- het Dawid doen demo 1146 00:56:58,180 --> 00:57:01,130 waar hy al die cool geluide van sien hoe saamsmelt 1147 00:57:01,130 --> 00:57:04,010 sorteer gehardloop, soos, oneindig vinniger as die ander twee tipes? 1148 00:57:04,010 --> 00:57:04,510 OK. 1149 00:57:04,510 --> 00:57:07,580 So dit is omdat merge soort implemente wat verdeel 1150 00:57:07,580 --> 00:57:11,020 en oorwin konsep wat ons het gepraat oor 'n baie in lesing. 1151 00:57:11,020 --> 00:57:14,550 In daardie sin dat ons wil werk slimmer, nie harder, wanneer jy verdeel 1152 00:57:14,550 --> 00:57:18,120 en oorwin probleme, en verbreek hulle af, en dan sit hulle saam, 1153 00:57:18,120 --> 00:57:19,930 goeie dinge altyd gebeur nie. 1154 00:57:19,930 --> 00:57:21,960 >> So die manier wat saamsmelt werk soort wese 1155 00:57:21,960 --> 00:57:24,660 is dat dit 'n verdeel ongesorteerde verskeidenheid in die helfte. 1156 00:57:24,660 --> 00:57:26,500 En dan is dit het twee helftes van skikkings. 1157 00:57:26,500 --> 00:57:28,220 En dit net sorteer die twee helftes. 1158 00:57:28,220 --> 00:57:31,750 Dit hou net verdeel in die helfte, in helfte, in die helfte tot alles is gesorteer 1159 00:57:31,750 --> 00:57:33,680 en dan rekursief sit dit alles saam. 1160 00:57:33,680 --> 00:57:36,550 >> So dit is regtig abstrakte. 1161 00:57:36,550 --> 00:57:38,750 So dit is net 'n bietjie van pseudokode. 1162 00:57:38,750 --> 00:57:41,040 Maak dit sin in die manier waarop dit bestuur? 1163 00:57:41,040 --> 00:57:43,870 So laat ons net sê jy het 'n verskeidenheid van n elemente, reg? 1164 00:57:43,870 --> 00:57:45,450 As n is minder as 2, kan jy terugkeer. 1165 00:57:45,450 --> 00:57:49,040 Omdat julle weet dat as daar net een ding, moet dit gesorteer. 1166 00:57:49,040 --> 00:57:52,600 Anders, jy die linker helfte sorteer, en dan kan jy die regter helfte sorteer, 1167 00:57:52,600 --> 00:57:54,140 en dan sal jy saam te smelt. 1168 00:57:54,140 --> 00:57:56,979 >> Dus, terwyl dit lyk regtig maklik, in werklikheid, dink oor dit 1169 00:57:56,979 --> 00:58:00,270 soort moeilik. Omdat jy soos, Wel, dit is soort van loop op sigself. 1170 00:58:00,270 --> 00:58:00,769 Reg? 1171 00:58:00,769 --> 00:58:02,430 Dit loop op sigself. 1172 00:58:02,430 --> 00:58:05,479 So in daardie sin, David aangeraak op rekursie in die klas. 1173 00:58:05,479 --> 00:58:07,270 En dit is 'n konsep sal ons praat oor meer. 1174 00:58:07,270 --> 00:58:11,430 Dit is dat hierdie, hierdie twee lyne hier, eintlik net die program 1175 00:58:11,430 --> 00:58:13,860 vertel dit aan homself te hardloop met verskillende insette. 1176 00:58:13,860 --> 00:58:17,230 So eerder as self hardloop met die geheel van n elemente, 1177 00:58:17,230 --> 00:58:20,530 jy kan dit af te breek in die linkerhelfte en die regter helfte 1178 00:58:20,530 --> 00:58:22,680 en weer hardloop dit dan. 1179 00:58:22,680 --> 00:58:26,050 >> En dan sal ons kyk na dit visueel, want ek is 'n visuele leerder. 1180 00:58:26,050 --> 00:58:27,270 Dit werk vir my beter. 1181 00:58:27,270 --> 00:58:29,890 So sal ons kyk na 'n visuele voorbeeld hier. 1182 00:58:29,890 --> 00:58:36,237 >> Kom ons sê ons het 'n skikking, ses elemente, 3, 5, 2, 6, 4, 1, nie gesorteer. 1183 00:58:36,237 --> 00:58:37,820 Alle reg, daar is 'n baie op hierdie bladsy. 1184 00:58:37,820 --> 00:58:43,179 So as jy ouens kan kyk na die eerste stap hier, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 jy kan dit verdeel in die helfte. 1186 00:58:44,220 --> 00:58:45,976 Jy het 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Jy weet dat hierdie aren't-- jy weet nie of hulle is gesorteer is of nie, 1188 00:58:48,850 --> 00:58:52,517 sodat jy hou breek hulle af, in die helfte, in die helfte, in die helfte, totdat uiteindelik, 1189 00:58:52,517 --> 00:58:53,600 jy net een element. 1190 00:58:53,600 --> 00:58:56,790 En een element is altyd gesorteer, reg? 1191 00:58:56,790 --> 00:59:01,560 >> So ons weet dat 3, 5, 2, 4, 6, 1, deur hulself, gesorteer. 1192 00:59:01,560 --> 00:59:05,870 En nou kan ons hulle saam terug. 1193 00:59:05,870 --> 00:59:07,510 So ons weet die 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Ons het die saam. 1195 00:59:08,510 --> 00:59:09,617 Ons weet dit is gesorteer. 1196 00:59:09,617 --> 00:59:10,450 Die 2 se nog steeds daar. 1197 00:59:10,450 --> 00:59:11,830 Ons kan die 4 en die 6 saam te stel. 1198 00:59:11,830 --> 00:59:13,996 Ons weet dat dit is gesorteer, sodat ons sit dit saam. 1199 00:59:13,996 --> 00:59:14,940 En die 1 is daar. 1200 00:59:14,940 --> 00:59:18,720 >> En dan moet jy net kyk na hierdie twee helftes hier. 1201 00:59:18,720 --> 00:59:21,300 Jy het die 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Jy kan net vergelyk die begin van alles. 1203 00:59:23,465 --> 00:59:26,340 Omdat jy weet dat dit is gesorteer en jy weet dat dit is gesorteer. 1204 00:59:26,340 --> 00:59:29,360 So dan het jy nie eens hoef te vergelyk die 5, jy net vergelyk die 3. 1205 00:59:29,360 --> 00:59:32,070 En die 2 is minder as 3, so jy weet 2 moet gaan in die einde. 1206 00:59:32,070 --> 00:59:33,120 >> Dieselfde ding daar. 1207 00:59:33,120 --> 00:59:34,740 Die 1 moet hier gaan. 1208 00:59:34,740 --> 00:59:37,330 En dan wanneer jy gaan om te sit daardie twee waardes bymekaar 1209 00:59:37,330 --> 00:59:39,950 jy weet dat dit gesorteer en jy weet dat wat gesorteer. 1210 00:59:39,950 --> 00:59:43,240 So dan is die 1 en die 2, die 1 is minder as 2. 1211 00:59:43,240 --> 00:59:45,570 Dit vertel jou dat die 1 moet gaan op die einde van hierdie 1212 00:59:45,570 --> 00:59:47,480 sonder om selfs na 3 of 5. 1213 00:59:47,480 --> 00:59:50,100 En dan is die 4, kan jy net kyk, dit gaan reg in hier. 1214 00:59:50,100 --> 00:59:51,480 Jy hoef nie te kyk na die 5. 1215 00:59:51,480 --> 00:59:52,570 Dieselfde ding met die 6. 1216 00:59:52,570 --> 00:59:55,860 Jy weet dat die 6-- is dit net hoef nie te kyk. 1217 00:59:55,860 --> 00:59:57,870 >> En so op dié manier, jy is net jouself spaar 1218 00:59:57,870 --> 00:59:59,526 'n baie stappe wanneer jy vergelyk. 1219 00:59:59,526 --> 01:00:02,150 Jy hoef nie elke vergelyk element teen ander elemente. 1220 01:00:02,150 --> 01:00:05,230 Jy vergelyk net teen die kinders wat jy nodig het om dit te vergelyk. 1221 01:00:05,230 --> 01:00:06,870 So dit is soort van 'n abstrakte konsep. 1222 01:00:06,870 --> 01:00:10,540 Geen bekommernisse as dit nie heel slaan jy nog reg is. 1223 01:00:10,540 --> 01:00:14,740 Maar oor die algemeen, is dit hoe 'n merge soort werk. 1224 01:00:14,740 --> 01:00:17,750 Vrae, vinnige vrae, voordat ek aanbeweeg? 1225 01:00:17,750 --> 01:00:18,550 Ja. 1226 01:00:18,550 --> 01:00:22,230 >> GEHOOR: So jy sê dat jy te neem die 1, en dan die 4 en die 6 1227 01:00:22,230 --> 01:00:23,860 en sit dit in. 1228 01:00:23,860 --> 01:00:26,800 So is nie those-- is nie jy kyk na hulle 1229 01:00:26,800 --> 01:00:28,544 as afsonderlike elemente, nie as die geheel? 1230 01:00:28,544 --> 01:00:29,210 ANDI Peng: Ja. 1231 01:00:29,210 --> 01:00:32,020 So wat gebeur is dat jy basies 1232 01:00:32,020 --> 01:00:33,650 skep 'n splinternuwe reeks. 1233 01:00:33,650 --> 01:00:36,690 So jy weet dat hier, ek het twee skikkings grootte 3, reg? 1234 01:00:36,690 --> 01:00:39,600 So jy weet dat my gesorteerde skikking moet tot ses elemente. 1235 01:00:39,600 --> 01:00:42,270 Sodat jy net skep 'n nuwe bedrag van die geheue. 1236 01:00:42,270 --> 01:00:44,270 So jy soort van soos om verkwistende van die geheue, 1237 01:00:44,270 --> 01:00:46,186 maar dit maak nie saak want dit is so klein. 1238 01:00:46,186 --> 01:00:48,590 So jy kyk na die 1 en jy kyk na die 2. 1239 01:00:48,590 --> 01:00:50,770 En jy weet dat die 1 is minder as 2. 1240 01:00:50,770 --> 01:00:53,840 So jy weet dat 1 in te gaan die begin van al daardie. 1241 01:00:53,840 --> 01:00:55,850 >> Jy hoef nie eens te kyk na die 3 en die 5. 1242 01:00:55,850 --> 01:00:57,400 So weet jy 1 daar gaan. 1243 01:00:57,400 --> 01:00:59,300 Dan moet jy basies afkap die 1. 1244 01:00:59,300 --> 01:01:00,370 Dit is, soos, dood vir ons. 1245 01:01:00,370 --> 01:01:03,690 Dan het ons net 2, 3, 5, en dan 4 en 6. 1246 01:01:03,690 --> 01:01:06,270 En dan moet jy weet dat jy vergelyk die 4 en die 2, 1247 01:01:06,270 --> 01:01:07,560 O, die 2 moet in daarheen te gaan. 1248 01:01:07,560 --> 01:01:09,685 So jy plop die 2 af, het jy dit afkap. 1249 01:01:09,685 --> 01:01:12,060 So dan is jy net die 3 en die 5 in die 4 en die 6. 1250 01:01:12,060 --> 01:01:14,650 En jy hou net kap dit af totdat jy sit hulle in die skikking. 1251 01:01:14,650 --> 01:01:17,110 >> GEHOOR: So jy net altyd is vergelyk die [onhoorbaar]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI Peng: Presies. 1253 01:01:17,710 --> 01:01:19,590 So in daardie sin, is jy net vergelyk, in wese, 1254 01:01:19,590 --> 01:01:21,240 een getal teen die ander getal. 1255 01:01:21,240 --> 01:01:22,990 En omdat jy weet dat dit gesorteer jy 1256 01:01:22,990 --> 01:01:24,350 hoef nie te kyk deur al die getalle. 1257 01:01:24,350 --> 01:01:25,870 Jy hoef net te kyk na die eerste een. 1258 01:01:25,870 --> 01:01:27,582 En dan kan jy net plop hulle af, want jy weet 1259 01:01:27,582 --> 01:01:29,640 hulle hoort waar hulle nodig het om te behoort. 1260 01:01:29,640 --> 01:01:31,030 Ja. 1261 01:01:31,030 --> 01:01:32,920 Goeie vraag. 1262 01:01:32,920 --> 01:01:35,290 >> En dan as iemand van julle is 'n bietjie ambisieus, 1263 01:01:35,290 --> 01:01:38,660 voel vry om te kyk na hierdie kode. 1264 01:01:38,660 --> 01:01:40,680 Dit is eintlik die fisiese implementering 1265 01:01:40,680 --> 01:01:42,150 hoe ons merge soort sou skryf. 1266 01:01:42,150 --> 01:01:44,070 En jy kan sien, is dit 'n baie kort. 1267 01:01:44,070 --> 01:01:46,310 Maar die idees agter dit is redelik kompleks. 1268 01:01:46,310 --> 01:01:50,865 So as jy voel soos teken dit uit in jou huiswerk vanaand, voel vry om. 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 En Dawid het ook oor hierdie in lesing. 1272 01:01:58,070 --> 01:02:00,660 Wat is die beste geval Runtimes, ergste geval Runtimes, 1273 01:02:00,660 --> 01:02:05,680 en die verwagte Runtimes van merge soort? 1274 01:02:05,680 --> 01:02:07,260 'N Paar sekondes om te dink. 1275 01:02:07,260 --> 01:02:11,198 Dit is baie moeilik, maar soort van intuïtief as jy daaroor dink. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Alles reg. 1278 01:02:23,054 --> 01:02:25,269 >> GEHOOR: Is die ergste geval N log n? 1279 01:02:25,269 --> 01:02:26,060 ANDI Peng: Presies. 1280 01:02:26,060 --> 01:02:29,380 En hoekom is dit N teken n. 1281 01:02:29,380 --> 01:02:32,230 >> GEHOOR: Is dit nie omdat dit raak eksponensieel vinniger, 1282 01:02:32,230 --> 01:02:35,390 so dit is soos 'n funksie van die in plaas van net bloot N 1283 01:02:35,390 --> 01:02:37,529 kwadraat of iets? 1284 01:02:37,529 --> 01:02:38,320 ANDI Peng: Presies. 1285 01:02:38,320 --> 01:02:40,750 So die rede waarom die runtime op hierdie N log 1286 01:02:40,750 --> 01:02:44,310 N is because-- wat is jy doen in al hierdie stappe? 1287 01:02:44,310 --> 01:02:46,190 Jy is net kap dit in die helfte, reg? 1288 01:02:46,190 --> 01:02:48,750 En so wanneer ons doen die teken, al wat dit doen 1289 01:02:48,750 --> 01:02:53,150 is 'n probleem te verdeel in die helfte, in die helfte, in die helfte, in meer helftes. 1290 01:02:53,150 --> 01:02:56,430 En in daardie sin, kan jy soort van elimineer die lineêre model 1291 01:02:56,430 --> 01:02:57,510 dat ons het al met behulp. 1292 01:02:57,510 --> 01:03:00,254 Want as jy kap dinge in die helfte, dit is 'n log. 1293 01:03:00,254 --> 01:03:02,420 Dit is net die wiskundige manier wat dit. 1294 01:03:02,420 --> 01:03:06,310 >> En dan uiteindelik, aan die einde, jy is net om 'n laaste aangee deur 1295 01:03:06,310 --> 01:03:07,930 almal van hulle in orde te bring, reg? 1296 01:03:07,930 --> 01:03:10,330 En so as jy net kyk een ding, dit is n. 1297 01:03:10,330 --> 01:03:13,420 En so is jy soort die twee bymekaar te vermenigvuldig. 1298 01:03:13,420 --> 01:03:17,660 So dit is soos jy dat die finale het kyk vir N down hier met 'n log van N 1299 01:03:17,660 --> 01:03:18,390 hier. 1300 01:03:18,390 --> 01:03:21,060 En as jy vermenigvuldig hulle, dit is n teken n. 1301 01:03:21,060 --> 01:03:26,100 >> En so het die beste geval en die ergste geval en verwag almal n teken n. 1302 01:03:26,100 --> 01:03:27,943 Dit is ook 'n ander soort soos. 1303 01:03:27,943 --> 01:03:30,090 Dit is soos seleksie soort in die sin dat dit 1304 01:03:30,090 --> 01:03:32,131 maak nie saak wat jou lys is, is dit net gaan 1305 01:03:32,131 --> 01:03:34,801 om dieselfde ding te doen elke keer. 1306 01:03:34,801 --> 01:03:35,300 OK. 1307 01:03:35,300 --> 01:03:39,950 So as julle kan sien, selfs al die soort wat ons through-- N gegaan het 1308 01:03:39,950 --> 01:03:41,660 kwadraat, dit is nie baie doeltreffend nie. 1309 01:03:41,660 --> 01:03:47,060 En selfs hierdie N log N is nie die mees doeltreffende. 1310 01:03:47,060 --> 01:03:49,720 As jy ouens is nuuskierig, daar is soort meganismes 1311 01:03:49,720 --> 01:03:54,310 wat so doeltreffend dat hulle is byna wese plat in runtime. 1312 01:03:54,310 --> 01:03:55,420 >> Jy het 'n paar log N se. 1313 01:03:55,420 --> 01:03:58,190 Jy het 'n paar log log N se. 1314 01:03:58,190 --> 01:04:00,330 Ons het nie op hulle raak in hierdie klas nou. 1315 01:04:00,330 --> 01:04:02,663 Maar as jy ouens is nuuskierig, voel vry om Google wat is 1316 01:04:02,663 --> 01:04:04,392 die mees doeltreffende sorteer meganismes. 1317 01:04:04,392 --> 01:04:06,350 Ek weet nie, is daar 'n paar baie snaakse kinders, 1318 01:04:06,350 --> 01:04:09,860 like-- daar is 'n paar baie snaaks dié wat mense maak. 1319 01:04:09,860 --> 01:04:12,210 En jy wonder hoe hulle ooit daaraan gedink nie. 1320 01:04:12,210 --> 01:04:15,730 So Google, as jy 'n paar ekstra tyd op, wat is 'n paar snaakse maniere 1321 01:04:15,730 --> 01:04:17,730 dat people-- asook doeltreffende ways-- mense 1322 01:04:17,730 --> 01:04:20,371 in staat was om allerhande implementeer. 1323 01:04:20,371 --> 01:04:20,870 OK. 1324 01:04:20,870 --> 01:04:22,880 En hier is net 'n handige klein grafiek. 1325 01:04:22,880 --> 01:04:26,850 Ek weet almal van julle, voordat die quiz 0, sal wees in jou kamer waarskynlik probeer 1326 01:04:26,850 --> 01:04:27,960 om te onthou dat. 1327 01:04:27,960 --> 01:04:30,940 So dit is lekker daar vir julle. 1328 01:04:30,940 --> 01:04:37,120 Net nie die logika wat made-- vergeet waarom dié nommers is wat plaasvind. 1329 01:04:37,120 --> 01:04:39,870 As jy altyd verloor het, maak net seker dat jy weet wat die vorme is. 1330 01:04:39,870 --> 01:04:40,820 En jy kan deur middel van hardloop hulle in jou gedagtes 1331 01:04:40,820 --> 01:04:42,903 om uit te vind waarom diegene antwoorde is die antwoorde. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Alles reg. 1334 01:04:47,600 --> 01:04:49,680 So ons gaan om te beweeg op, uiteindelik, om te soek. 1335 01:04:49,680 --> 01:04:51,638 Want soos dié van julle wat die pset gelees het, 1336 01:04:51,638 --> 01:04:55,175 soek is ook deel van probleem hierdie week se stel. 1337 01:04:55,175 --> 01:04:57,300 Jy sal gevra word om te implementeer twee tipes navrae. 1338 01:04:57,300 --> 01:05:00,070 Een is 'n lineêre soek en een is 'n binêre soek. 1339 01:05:00,070 --> 01:05:01,760 >> So die lineêre soek is redelik maklik. 1340 01:05:01,760 --> 01:05:04,070 Jy wil net om te soek element van 'n lys om te sien of jy dit kry. 1341 01:05:04,070 --> 01:05:05,444 Jy moet net om deur te Itereer. 1342 01:05:05,444 --> 01:05:08,170 En as dit gelyk iets jy kan net terug nie, reg? 1343 01:05:08,170 --> 01:05:10,890 Maar die een wat ons die meeste belangstel in praat oor 1344 01:05:10,890 --> 01:05:14,550 is binêre soek, regs, wat is die verdeel en oorwin meganisme wat 1345 01:05:14,550 --> 01:05:18,190 David is bewys in lesing. 1346 01:05:18,190 --> 01:05:20,810 >> Onthou die telefoon boek byvoorbeeld dat hy hou die opvoeding, 1347 01:05:20,810 --> 01:05:23,960 die een wat hy soort van gesukkel 'n bietjie op die afgelope jaar, 1348 01:05:23,960 --> 01:05:27,530 waar jy die probleem verdeel in die helfte, in die helfte, in die helfte, weer en weer, 1349 01:05:27,530 --> 01:05:30,730 totdat jy kry wat jy soek? 1350 01:05:30,730 --> 01:05:33,727 En jy het die runtime van wat as goed. 1351 01:05:33,727 --> 01:05:35,810 En jy kan sien, is dit aansienlik meer doeltreffende 1352 01:05:35,810 --> 01:05:39,080 as enige ander tipe search. 1353 01:05:39,080 --> 01:05:41,880 >> So die manier waarop ons te werk sal gaan implementering van 'n binêre soek 1354 01:05:41,880 --> 01:05:46,510 is, as ons het 'n skikking, indeks 0-6, sewe elemente, 1355 01:05:46,510 --> 01:05:49,790 ons kan kyk in die middel, right-- Jammer, as ons vraag first-- 1356 01:05:49,790 --> 01:05:53,840 As ons wil hê dat die vraag vra, doen die skikking bevat die element van 7, 1357 01:05:53,840 --> 01:05:56,840 natuurlik, om die mens, en met so 'n klein verskeidenheid, is dit maklik vir ons 1358 01:05:56,840 --> 01:05:58,210 om te sê ja. 1359 01:05:58,210 --> 01:06:05,750 Maar die manier om 'n binêre implementeer soek sal wees om te kyk in die middel. 1360 01:06:05,750 --> 01:06:08,020 >> Ons weet dat indeks 3 is die middel, omdat ons 1361 01:06:08,020 --> 01:06:09,270 weet daar is sewe elemente. 1362 01:06:09,270 --> 01:06:10,670 Wat 7 gedeel deur 2? 1363 01:06:10,670 --> 01:06:12,850 Jy kan afkap daardie ekstra 1. 1364 01:06:12,850 --> 01:06:14,850 Jy het 3 in die middel. 1365 01:06:14,850 --> 01:06:17,590 So is verskeidenheid van 3 tot 7 gelyk? 1366 01:06:17,590 --> 01:06:18,900 Dit is nie, reg? 1367 01:06:18,900 --> 01:06:21,050 Maar ons kan 'n paar tjeks te doen. 1368 01:06:21,050 --> 01:06:25,380 Is verskeidenheid van 3 minder as 7 of is verskeidenheid van 3 groter as 7? 1369 01:06:25,380 --> 01:06:27,240 >> En ons weet dat dit is minder as 7. 1370 01:06:27,240 --> 01:06:30,259 So weet ons dat, oh, moet dit nie in die linker helfte. 1371 01:06:30,259 --> 01:06:32,300 Ons weet dat dit moet wees in die regter helfte, reg? 1372 01:06:32,300 --> 01:06:34,662 So kan ons net afkap helfte van die skikking. 1373 01:06:34,662 --> 01:06:36,370 Ons het nie eens ' kyk na dit nie. 1374 01:06:36,370 --> 01:06:38,711 Omdat ons weet dat die helfte van ons problem-- 1375 01:06:38,711 --> 01:06:41,210 ons weet dat die antwoord is in die regter helfte van ons probleem. 1376 01:06:41,210 --> 01:06:42,580 So ons net kyk na wat nou. 1377 01:06:42,580 --> 01:06:44,860 >> So nou kyk ons ​​na die middel van wat oorbly. 1378 01:06:44,860 --> 01:06:46,880 Dit indeks 5. 1379 01:06:46,880 --> 01:06:50,200 Ons doen dieselfde tjek weer en ons sien dat dit is kleiner. 1380 01:06:50,200 --> 01:06:52,050 So ons kyk na die links van daardie. 1381 01:06:52,050 --> 01:06:53,430 En dan sien ons dat tjek. 1382 01:06:53,430 --> 01:06:57,600 Is die skikking waarde op indeks 4 gelyk aan 7? 1383 01:06:57,600 --> 01:06:58,260 Dit is. 1384 01:06:58,260 --> 01:07:03,580 So kan ons ware terugkeer, want Ons het gevind dat die waarde in ons lys. 1385 01:07:03,580 --> 01:07:06,738 Is die manier wat ek het deur dit sin maak om almal? 1386 01:07:06,738 --> 01:07:08,760 OK. 1387 01:07:08,760 --> 01:07:11,670 Ek sal julle miskien gee, soos, drie, vier minute om uit te vind 1388 01:07:11,670 --> 01:07:13,270 Hoe om hierdie pseudokode in. 1389 01:07:13,270 --> 01:07:18,070 >> So dink ek jou gevra om 'n skrywe funksie genoem soek () wat omgedraai 1390 01:07:18,070 --> 01:07:20,640 'n waarde, 'n Boolese waarde, dit was waar of false-- soos, 1391 01:07:20,640 --> 01:07:22,970 waar as jy gevind dat die waarde, valse as jy nie het nie. 1392 01:07:22,970 --> 01:07:25,230 En dan was jy geslaag in die waarde wat jy 1393 01:07:25,230 --> 01:07:28,410 soek na waardes, wat is die array-- o, ek het beslis sit 1394 01:07:28,410 --> 01:07:29,410 wat op die verkeerde plek. 1395 01:07:29,410 --> 01:07:29,580 OK. 1396 01:07:29,580 --> 01:07:31,829 In elk geval, wat moet het aan die regterkant van waardes is. 1397 01:07:31,829 --> 01:07:36,280 En dan int n die aantal elemente in daardie skikking. 1398 01:07:36,280 --> 01:07:39,430 Hoe sou jy te werk gaan probeer dat die probleem in pseudokode? 1399 01:07:39,430 --> 01:07:41,630 Ek sal julle ouens soos gee drie minute om dit te doen. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Nee, ek dink daar is only-- ja, daar is een reg hier. 1402 01:08:02,595 --> 01:08:03,261 GEHOOR: Kan ek? 1403 01:08:03,261 --> 01:08:04,388 ANDI Peng: Ja, ek het jou. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 Is dat werkende? 1406 01:08:11,050 --> 01:08:12,290 OK, cool. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> OK. 1409 01:10:44,720 --> 01:10:47,630 Alle regte ouens, ons is gaan om dit in toom. 1410 01:10:47,630 --> 01:10:49,730 OK. 1411 01:10:49,730 --> 01:10:54,020 So aanvaar ons het hierdie pragtige gekry bietjie verskeidenheid met n waardes in. 1412 01:10:54,020 --> 01:10:55,170 Ek het nie die lyne te trek. 1413 01:10:55,170 --> 01:10:58,649 Maar hoe sou ons gaan oor probeer om hierdie te skryf? 1414 01:10:58,649 --> 01:11:00,440 Is daar iemand wat wil gee my die eerste reël? 1415 01:11:00,440 --> 01:11:02,814 As jy wil om my te gee die eerste reël van hierdie pseudokode. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> GEHOOR: [onhoorbaar] 1418 01:11:08,430 --> 01:11:10,138 GEHOOR: Jy wil hê om through-- Itereer 1419 01:11:10,138 --> 01:11:11,094 GEHOOR: Net nog lus? 1420 01:11:11,094 --> 01:11:11,760 GEHOOR: --for. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI Peng: So hierdie een is 'n bietjie lastig. 1423 01:11:17,780 --> 01:11:23,130 Dink about-- jy wil hou die loop van hierdie lus 1424 01:11:23,130 --> 01:11:27,950 oor en oor weer tot wanneer? 1425 01:11:27,950 --> 01:11:30,819 >> GEHOOR: Totdat die [onhoorbaar] waarde is gelyk aan die waarde. 1426 01:11:30,819 --> 01:11:31,610 ANDI Peng: Presies. 1427 01:11:31,610 --> 01:11:33,900 Sodat jy kan eintlik net write-- ons kan selfs vereenvoudig meer. 1428 01:11:33,900 --> 01:11:35,630 Ons kan net nie 'n while lus, reg? 1429 01:11:35,630 --> 01:11:39,380 Sodat jy kan net loop-- ons weet dat dit 'n rukkie. 1430 01:11:39,380 --> 01:11:42,850 Maar vir nou, ek gaan deur wat - om te "loop" sê? 1431 01:11:42,850 --> 01:11:46,640 Loop until-- wat ons eindig toestand? 1432 01:11:46,640 --> 01:11:47,510 Ek dink ek het dit gehoor. 1433 01:11:47,510 --> 01:11:48,530 Ek het gehoor iemand sê dit. 1434 01:11:48,530 --> 01:11:51,255 >> GEHOOR: Waardes gelyk middel. 1435 01:11:51,255 --> 01:11:52,255 ANDI Peng: Sê dit weer. 1436 01:11:52,255 --> 01:11:54,470 GEHOOR: Of totdat die waarde wat jy soek 1437 01:11:54,470 --> 01:11:58,470 vir is gelyk aan die middelste waarde. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI Peng: Wat as dit nie daar? 1439 01:12:00,280 --> 01:12:03,113 Wat as die waarde wat jy op soek is vir nie eintlik in hierdie reeks? 1440 01:12:03,113 --> 01:12:05,890 GEHOOR: Jy terugkeer 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI Peng: Maar wat wil ons lus totdat as ons 'n toestand? 1442 01:12:08,850 --> 01:12:09,350 Ja. 1443 01:12:09,350 --> 01:12:11,239 >> GEHOOR: Tot daar net een waarde? 1444 01:12:11,239 --> 01:12:13,530 ANDI Peng: Jy kan loop until-- sodat jy weet dat jy 1445 01:12:13,530 --> 01:12:15,714 gaan 'n maksimum waarde, reg? 1446 01:12:15,714 --> 01:12:18,130 En jy weet dat jy gaan om 'n min waarde, reg? 1447 01:12:18,130 --> 01:12:20,379 Omdat ook dit is iets Ek het vergeet om voor te sê, 1448 01:12:20,379 --> 01:12:22,640 dat iets wat krities oor binêre soek 1449 01:12:22,640 --> 01:12:24,182 is dat jou array reeds gesorteer. 1450 01:12:24,182 --> 01:12:26,973 Want daar is geen manier om dit te doen hierdie as hulle is net random waardes. 1451 01:12:26,973 --> 01:12:29,190 Jy weet nie of die een is groter as die ander, reg? 1452 01:12:29,190 --> 01:12:32,720 >> So jy weet dat jou maksimum en jou min is hier, reg? 1453 01:12:32,720 --> 01:12:35,590 As jy gaan om te pas jou maksimum in jou min en die mid-- 1454 01:12:35,590 --> 01:12:38,470 laat ons net aanvaar jou mid waarde is reg here-- 1455 01:12:38,470 --> 01:12:43,910 jy gaan basies lus totdat jou minimum is 1456 01:12:43,910 --> 01:12:47,510 ongeveer dieselfde as jou maksimum, regs, of as jou maksimum is nie dieselfde as jou min. 1457 01:12:47,510 --> 01:12:48,040 Reg? 1458 01:12:48,040 --> 01:12:51,340 Want as dit gebeur, moet jy weet dat jy uiteindelik het getref dieselfde waarde. 1459 01:12:51,340 --> 01:12:59,135 So jy wil loop totdat jou min minder as of gelyk aan- oops, 1460 01:12:59,135 --> 01:13:01,510 nie minder as of gelyk aan, die ander manier around-- Max is. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Het dit sin maak? 1463 01:13:16,160 --> 01:13:18,810 Ek het 'n paar drieë wat reg te kry. 1464 01:13:18,810 --> 01:13:21,869 Maar lus totdat jou maksimum waarde is in wese byna minder 1465 01:13:21,869 --> 01:13:23,410 as of gelyk aan jou minimum, reg? 1466 01:13:23,410 --> 01:13:25,201 Dit is wanneer jy weet wat jy geconvergeerde. 1467 01:13:25,201 --> 01:13:29,290 GEHOOR: Wanneer sal jou maksimum waarde minder as die minimum wees? 1468 01:13:29,290 --> 01:13:31,040 ANDI Peng: As jy hou aanpassing dit, wat 1469 01:13:31,040 --> 01:13:32,380 is wat ons gaan om te doen in hierdie. 1470 01:13:32,380 --> 01:13:33,460 Maak wat sin maak? 1471 01:13:33,460 --> 01:13:35,750 Minimum en maksimum is net heelgetalle dat ons waarskynlik 1472 01:13:35,750 --> 01:13:39,260 gaan wil skep om aan te hou spoor van waar ons is op soek na. 1473 01:13:39,260 --> 01:13:41,790 Omdat die skikking bestaan ongeag van wat ons doen. 1474 01:13:41,790 --> 01:13:45,030 Soos ons is nie eintlik fisies afkap die skikking, reg? 1475 01:13:45,030 --> 01:13:47,261 Ons is net die aanpassing waar ons is op soek na. 1476 01:13:47,261 --> 01:13:48,136 Maak wat sin maak? 1477 01:13:48,136 --> 01:13:48,472 >> GEHOOR: Ja. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI Peng: OK. 1479 01:13:49,110 --> 01:13:57,090 So as dit is die toestand van ons lus, wat wil ons binnekant van hierdie lus? 1480 01:13:57,090 --> 01:13:58,700 Wat gaan ons te wil doen? 1481 01:13:58,700 --> 01:14:02,390 So nou, ons het 'n maksimum en 'n min, regs, 1482 01:14:02,390 --> 01:14:04,962 waarskynlik geskep hier iewers. 1483 01:14:04,962 --> 01:14:07,170 Ons gaan waarskynlik wil om 'n middel, reg te kry? 1484 01:14:07,170 --> 01:14:08,450 Hoe gaan ons te wees in staat wees om die middel te vind? 1485 01:14:08,450 --> 01:14:09,491 Wat is die mathematical-- 1486 01:14:09,491 --> 01:14:11,079 GEHOOR: Max plus min gedeel deur 2. 1487 01:14:11,079 --> 01:14:11,870 ANDI Peng: Presies. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Maak wat sin maak? 1490 01:14:21,620 --> 01:14:25,780 En moenie julle sien waarom ons het nie net use-- hoekom ons dit gedoen het 1491 01:14:25,780 --> 01:14:27,850 in plaas van om net N gedeel deur 2? 1492 01:14:27,850 --> 01:14:30,310 Dit is omdat 'n waarde is N wat gaan om dieselfde te bly. 1493 01:14:30,310 --> 01:14:30,979 Reg? 1494 01:14:30,979 --> 01:14:34,020 Maar soos ons pas ons minimum en maksimum waardes, gaan hulle om te verander. 1495 01:14:34,020 --> 01:14:36,040 En as 'n gevolg, ons middelste gaan ook verander. 1496 01:14:36,040 --> 01:14:37,873 So dit is waarom ons wil hierdie reg hier doen. 1497 01:14:37,873 --> 01:14:38,510 OK. 1498 01:14:38,510 --> 01:14:41,600 >> En dan, noudat ons het our-- gevind ja. 1499 01:14:41,600 --> 01:14:44,270 >> GEHOOR: Net 'n vinnige question-- wanneer jy sê min en max, 1500 01:14:44,270 --> 01:14:46,410 ons die veronderstelling dat dit is reeds gesorteer? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI Peng: Ja, dit is eintlik 'n voorvereiste vir 'n binêre soek, 1502 01:14:48,400 --> 01:14:49,816 dat jy weet dit is gesorteer. 1503 01:14:49,816 --> 01:14:53,660 Wat is die rede waarom soort, jy skryf in jou probleem voor jou binêre soek. 1504 01:14:53,660 --> 01:14:55,910 OK. 1505 01:14:55,910 --> 01:14:58,876 So nou dat ons weet waar ons middelpunt is, wat wil jy hier doen? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> GEHOOR: Ons wil om te vergelyk dat die ander een nie. 1508 01:15:04,319 --> 01:15:05,110 ANDI Peng: Presies. 1509 01:15:05,110 --> 01:15:12,280 So jy gaan om te vergelyk mid waarde, reg? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 En wat beteken dat vertel ons wanneer ons dit vergelyk? 1512 01:15:18,670 --> 01:15:22,226 Wat wil ons daarna doen? 1513 01:15:22,226 --> 01:15:25,389 >> GEHOOR: Indien die waarde is groter as die middel, wil ons dit uit te roei. 1514 01:15:25,389 --> 01:15:26,180 ANDI Peng: Presies. 1515 01:15:26,180 --> 01:15:33,940 So as die waarde is groter as die middel, ons is 1516 01:15:33,940 --> 01:15:36,550 gaan wil hierdie verander minimum en maxes, reg? 1517 01:15:36,550 --> 01:15:38,980 Wat wil ons verander? 1518 01:15:38,980 --> 01:15:42,145 So as ons weet wat die waarde is iewers hier, wat jy doen ons om te verander? 1519 01:15:42,145 --> 01:15:44,758 Ons wil ons verander minimum tot middel wees, reg? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 En dan anders, as dit in hierdie helfte, wat wil ons verander? 1522 01:15:54,292 --> 01:15:55,306 >> GEHOOR: Jou maksimum. 1523 01:15:55,306 --> 01:15:55,972 ANDI Peng: Ja. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 En dan is jy net gaan hou herhaling, reg? 1526 01:16:04,680 --> 01:16:08,920 Want nou, na een iterasie deur, het jy 'n maksimum het hier. 1527 01:16:08,920 --> 01:16:10,760 En dan kan jy 'n mid herbereken. 1528 01:16:10,760 --> 01:16:11,990 En dan kan jy vergelyk. 1529 01:16:11,990 --> 01:16:14,766 En jy gaan om voort te gaan totdat die mins en die maxes 1530 01:16:14,766 --> 01:16:15,890 het in wese geconvergeerde. 1531 01:16:15,890 --> 01:16:17,890 En dit is wanneer jy weet dat jy die einde van dit het getref. 1532 01:16:17,890 --> 01:16:20,280 En óf jy het dit gevind of jy het nie op daardie punt. 1533 01:16:20,280 --> 01:16:23,170 >> Maak dit sin om almal? 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 Dit is redelik belangrik, want jy het 1537 01:16:27,900 --> 01:16:29,760 om te skryf in jou kode vanaand. 1538 01:16:29,760 --> 01:16:32,660 Maar julle ouens het 'n goeie sin van wat jy moet doen, 1539 01:16:32,660 --> 01:16:34,051 wat goed is. 1540 01:16:34,051 --> 01:16:34,550 OK. 1541 01:16:34,550 --> 01:16:38,840 So ons het ongeveer sewe minute oor artikel. 1542 01:16:38,840 --> 01:16:43,170 So ons gaan om te praat oor hierdie pset dat ons sal moet doen. 1543 01:16:43,170 --> 01:16:46,410 So die pset is verdeel in twee helftes. 1544 01:16:46,410 --> 01:16:50,230 Die eerste helfte behels implementering van 'n vonds 1545 01:16:50,230 --> 01:16:54,210 waarin jy 'n lineêre soek skryf, 'n binêre soek, en 'n sorteer algoritme. 1546 01:16:54,210 --> 01:16:56,690 >> So dit is die eerste keer in 'n pset waar 1547 01:16:56,690 --> 01:17:00,050 ons sal gee jou ouens wat genoem verspreiding kode, wat is die kode 1548 01:17:00,050 --> 01:17:02,740 dat ons pre-geskrewe, maar net links 'n paar stukkies af 1549 01:17:02,740 --> 01:17:04,635 vir jou om met skryf. 1550 01:17:04,635 --> 01:17:07,510 So julle ouens, as jy kyk na hierdie kode, kan jy regtig bang. 1551 01:17:07,510 --> 01:17:08,630 As jy net wil, ahh, ek weet nie wat dit doen, 1552 01:17:08,630 --> 01:17:11,670 Ek weet nie, soos, wat lyk asof dit so ingewikkeld, ahh, ontspan. 1553 01:17:11,670 --> 01:17:12,170 Dit is OK. 1554 01:17:12,170 --> 01:17:12,930 Lees die spec. 1555 01:17:12,930 --> 01:17:16,920 Die spec sal presies aan jou te verduidelik wat al hierdie programme doen. 1556 01:17:16,920 --> 01:17:20,560 >> Byvoorbeeld, is 'n program generate.c wat sal kom met jou pset. 1557 01:17:20,560 --> 01:17:24,060 Jy hoef nie eintlik om dit aan te raak nie, maar jy moet verstaan ​​wat dit doen. 1558 01:17:24,060 --> 01:17:28,550 En generate.c, al is dit te doen, is óf genereer ewekansige getalle 1559 01:17:28,550 --> 01:17:32,400 of jy kan dit gee 'n saad, soos 'n voorafgereëlde getal wat dit neem, 1560 01:17:32,400 --> 01:17:34,140 en dit genereer meer getalle. 1561 01:17:34,140 --> 01:17:37,170 So is daar 'n spesifieke manier om implementeer generate.c waarin 1562 01:17:37,170 --> 01:17:42,760 jy kan net 'n klomp van die nommers vir jou om jou ander metodes te toets op. 1563 01:17:42,760 --> 01:17:45,900 >> So as jy wil, vir Byvoorbeeld, toets jou vonds, 1564 01:17:45,900 --> 01:17:48,970 jy wil generate.c hardloop, genereer 'n klomp van die nommers, 1565 01:17:48,970 --> 01:17:50,880 en dan loop jou helpers funksie. 1566 01:17:50,880 --> 01:17:53,930 Jou helpers funksie is waar jy is eintlik fisies kode skryf. 1567 01:17:53,930 --> 01:17:59,330 En dink aan helpers as 'n biblioteek lêer jy skryf dit vind roep. 1568 01:17:59,330 --> 01:18:02,950 En so binne helpers.c, sal jy doen die soek en sorteer. 1569 01:18:02,950 --> 01:18:06,500 >> En dan gaan jy in wese net sit hulle almal saam. 1570 01:18:06,500 --> 01:18:10,350 Die spec sal jou vertel hoe om sit dit op die command line. 1571 01:18:10,350 --> 01:18:14,880 En jy sal in staat wees om te toets of nie jou soort en soek werk. 1572 01:18:14,880 --> 01:18:15,870 Koel. 1573 01:18:15,870 --> 01:18:18,720 Het iemand al begin en teëgekom probleme of vrae 1574 01:18:18,720 --> 01:18:20,520 hulle nou met hierdie? 1575 01:18:20,520 --> 01:18:21,020 OK. 1576 01:18:21,020 --> 01:18:21,476 >> GEHOOR: wag. 1577 01:18:21,476 --> 01:18:21,932 Ek het 'n vraag. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI Peng: Ja. 1579 01:18:22,844 --> 01:18:28,390 >> GEHOOR: So ek begin doen die lineêre soektog in helpers.c 1580 01:18:28,390 --> 01:18:29,670 en dit was nie regtig werk. 1581 01:18:29,670 --> 01:18:34,590 Maar dan later, het ek uitgevind het ons net het om dit te verwyder en te doen binêre soek. 1582 01:18:34,590 --> 01:18:36,991 So maak dit saak as dit nie werk nie? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI Peng: Kort antwoord is nee. 1585 01:18:41,510 --> 01:18:42,642 Maar aangesien ons not-- 1586 01:18:42,642 --> 01:18:44,350 GEHOOR: Maar niemand se eintlik nagaan. 1587 01:18:44,350 --> 01:18:46,058 ANDI Peng Ons is nooit gaan om te sien dat. 1588 01:18:46,058 --> 01:18:49,590 Maar jy waarskynlik wil om te maak seker dat jou werk soek. 1589 01:18:49,590 --> 01:18:51,700 Want as jou lineêre soek nie werk nie, 1590 01:18:51,700 --> 01:18:54,410 dan is die kans is jou binêre soek gaan nie so goed werk. 1591 01:18:54,410 --> 01:18:56,646 Aangesien u soortgelyke het logika in beide van hulle. 1592 01:18:56,646 --> 01:18:58,020 En nee, dit maak nie regtig saak nie. 1593 01:18:58,020 --> 01:19:01,300 So die enigste jy draai in is soort en binêre soek. 1594 01:19:01,300 --> 01:19:02,490 Ja. 1595 01:19:02,490 --> 01:19:06,610 >> En ook, 'n baie van die kinders was probeer om helpers.c saam te stel. 1596 01:19:06,610 --> 01:19:09,550 Jy is nie eintlik toegelaat om dit te doen, want helpers.c 1597 01:19:09,550 --> 01:19:11,200 het nie 'n hooffunksie. 1598 01:19:11,200 --> 01:19:13,550 En so moet jy net wees eintlik die opstel 1599 01:19:13,550 --> 01:19:18,670 genereer en vind, want oproepe vind helpers.c en die funksies binne dit. 1600 01:19:18,670 --> 01:19:20,790 So wat maak debugging 'n pyn in die boude. 1601 01:19:20,790 --> 01:19:22,422 Maar dit is wat ons moet doen. 1602 01:19:22,422 --> 01:19:23,880 GEHOOR: Jy maak almal net, reg? 1603 01:19:23,880 --> 01:19:27,290 ANDI Peng: Jy kan net maak al so goed, ja. 1604 01:19:27,290 --> 01:19:28,060 OK. 1605 01:19:28,060 --> 01:19:32,570 So wat is dit in terme van wat die pset vra julle almal om te doen. 1606 01:19:32,570 --> 01:19:35,160 As jy enige vrae het, voel vry om my te vra na artikel. 1607 01:19:35,160 --> 01:19:37,580 Ek sal hier wees vir, soos, 20 minute. 1608 01:19:37,580 --> 01:19:40,500 >> En ja, die pset se regtig nie so sleg nie. 1609 01:19:40,500 --> 01:19:41,680 Julle moet OK. 1610 01:19:41,680 --> 01:19:43,250 Hierdie, volg riglyne. 1611 01:19:43,250 --> 01:19:47,840 Soort het 'n gevoel van, logies, wat behoort te gebeur en jy sal goed wees. 1612 01:19:47,840 --> 01:19:48,690 Moenie te bang wees nie. 1613 01:19:48,690 --> 01:19:50,220 Daar is 'n baie van die kode reeds daar geskryf is. 1614 01:19:50,220 --> 01:19:53,011 Moenie te bang wees nie as jy dit nie doen nie verstaan ​​wat dit alles beteken. 1615 01:19:53,011 --> 01:19:54,749 As dit is 'n baie, dit is heeltemal fyn. 1616 01:19:54,749 --> 01:19:55,790 En kom na kantoorure. 1617 01:19:55,790 --> 01:19:57,520 Ons sal jou help om 'n blik te neem. 1618 01:19:57,520 --> 01:20:00,810 >> GEHOOR: Met die ekstra funksies, moet ons diegene up? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI Peng: Ja, dit is in die kode. 1620 01:20:03,417 --> 01:20:05,750 In die spel van die 15, die helfte van dit is reeds vir jou geskryf. 1621 01:20:05,750 --> 01:20:09,310 So daardie funksies is reeds in die kode. 1622 01:20:09,310 --> 01:20:12,020 Yep. 1623 01:20:12,020 --> 01:20:12,520 Alles reg. 1624 01:20:12,520 --> 01:20:14,000 Wel, die beste van geluk. 1625 01:20:14,000 --> 01:20:15,180 Dit is 'n gruwel dag. 1626 01:20:15,180 --> 01:20:19,370 So hopelik julle ouens nie te voel sleg oor bly binne en kodering. 1627 01:20:19,370 --> 01:20:22,133