1
00:00:00,000 --> 00:00:03,332
>> [Muziek]

2
00:00:03,332 --> 00:00:06,490
>> ANDI Peng: Welkom in week 3 van de sectie.

3
00:00:06,490 --> 00:00:09,550
Bedankt, jongens, voor alle komende
deze vroegste starttijd vandaag.

4
00:00:09,550 --> 00:00:11,466
We hebben een mooi, klein gekregen
intieme groep vandaag.

5
00:00:11,466 --> 00:00:14,570
Dus hopelijk krijgen
afwerking, misschien, vroeg,

6
00:00:14,570 --> 00:00:15,780
een beetje vroeg vandaag.

7
00:00:15,780 --> 00:00:22,057
Zo snel, slechts enkele
aankondigingen voor de agenda van vandaag.

8
00:00:22,057 --> 00:00:23,890
Voordat we beginnen, we zijn
zomaar over te gaan

9
00:00:23,890 --> 00:00:28,910
enkele korte logistieke problemen, PSET
vragen, debriefing, dat soort dingen.

10
00:00:28,910 --> 00:00:30,250
En dan gaan we duiken recht in.

11
00:00:30,250 --> 00:00:34,710
We zullen een debugger genaamd GDB te gebruiken
start ontmaskeren van onze code, die David

12
00:00:34,710 --> 00:00:36,550
uitgelegd in lezing de andere dag.

13
00:00:36,550 --> 00:00:39,420
We gaan over de vier types van soorten.

14
00:00:39,420 --> 00:00:42,310
We gaan over hen vrij snel
omdat ze behoorlijk intensief.

15
00:00:42,310 --> 00:00:45,710
Maar weet dat alle glijbanen en
broncode zijn altijd online.

16
00:00:45,710 --> 00:00:50,810
Dus voel je vrij, op uw inzage, om
ga terug en neem een ​​kijkje op dat.

17
00:00:50,810 --> 00:00:53,930
>> We gaan door
asymptotische notatie, waarbij

18
00:00:53,930 --> 00:00:55,944
is gewoon een mooie manier
van te zeggen "runtimes,"

19
00:00:55,944 --> 00:00:58,360
waar we de grote O, die
David legde in collegezaal.

20
00:00:58,360 --> 00:01:01,550
En we hebben ook Omega, die
is de ondergrens runtime.

21
00:01:01,550 --> 00:01:06,450
En we zullen een beetje meer te praten
diepgaande over hoe die werken.

22
00:01:06,450 --> 00:01:10,160
En tot slot, gaan we over binaire zoeken,
omdat veel van jullie die al

23
00:01:10,160 --> 00:01:15,190
wierp een blik op uw psets waarschijnlijk dat
dat is een vraag die in uw PSET.

24
00:01:15,190 --> 00:01:17,470
Dus je zult al blij zijn
die wij dekken dit vandaag.

25
00:01:17,470 --> 00:01:20,610
>> En tot slot, je per
sectie feedback, ik eigenlijk

26
00:01:20,610 --> 00:01:23,000
vertrokken ongeveer 15 minuten bij
het einde tot iets meer dan gaan

27
00:01:23,000 --> 00:01:27,730
logistiek van pset3, vragen,
misschien een beetje begeleiding, zo u wilt,

28
00:01:27,730 --> 00:01:28,990
voordat we beginnen met het programmeren.

29
00:01:28,990 --> 00:01:30,890
Dus laten we proberen te krijgen door middel van
het materiaal vrij snel.

30
00:01:30,890 --> 00:01:33,880
En dan kunnen we wat tijd doorbrengen
het nemen van meer vragen voor de PSET.

31
00:01:33,880 --> 00:01:35,230
OK.

32
00:01:35,230 --> 00:01:39,570
>> Snel, dus gewoon een paar
aankondigingen voordat we beginnen vandaag.

33
00:01:39,570 --> 00:01:45,410
Ten eerste, van harte welkom om te maken
het door twee van uw psets.

34
00:01:45,410 --> 00:01:49,432
Ik nam een ​​kijkje op uw-- ja, laten we
krijgt een applaus voor die ene.

35
00:01:49,432 --> 00:01:51,140
Eigenlijk was ik echt,
echt onder de indruk.

36
00:01:51,140 --> 00:01:55,800
Ik ingedeeld de eerste PSET voor jullie
vorige week en dat jullie deed ongelooflijk.

37
00:01:55,800 --> 00:01:58,290
>> Stijl was op punt
naast een paar opmerkingen.

38
00:01:58,290 --> 00:02:00,660
Zorg ervoor dat je altijd
commentaar uw code.

39
00:02:00,660 --> 00:02:03,040
Maar je psets waren over punt.

40
00:02:03,040 --> 00:02:05,549
En keep it up.

41
00:02:05,549 --> 00:02:08,090
En het is goed voor de grader aan
zie dat jullie zetten

42
00:02:08,090 --> 00:02:10,704
in zo veel moeite in uw stijl
en uw ontwerp in uw code

43
00:02:10,704 --> 00:02:12,120
dat we graag voor u om te zien.

44
00:02:12,120 --> 00:02:16,450
Dus ik ben passeren langs mijn dank
voor de rest van het TA.

45
00:02:16,450 --> 00:02:19,210
>> Er zijn echter een
paar debrief vragen

46
00:02:19,210 --> 00:02:22,010
Ik wil alleen maar gaan over dat
zou zowel mijn leven

47
00:02:22,010 --> 00:02:24,900
en veel van de andere
TA 'leeft een stuk makkelijker.

48
00:02:24,900 --> 00:02:28,220
Ten eerste, heb ik gemerkt dit
afgelopen week-- hoeveel van jullie

49
00:02:28,220 --> 00:02:32,301
hebben gelopen check50 op
uw code voordat u indienen?

50
00:02:32,301 --> 00:02:32,800
OK.

51
00:02:32,800 --> 00:02:36,690
Dus iedereen moet check50 moeten doen,
because-- een secret-- we eigenlijk

52
00:02:36,690 --> 00:02:41,540
gerund check50 als onderdeel van onze juistheid
scripts voor het testen van uw code.

53
00:02:41,540 --> 00:02:45,480
Dus als je code is niet
check50, naar alle waarschijnlijkheid,

54
00:02:45,480 --> 00:02:47,570
het is waarschijnlijk gaan om
mislukken onze check ook.

55
00:02:47,570 --> 00:02:49,320
Soms jullie
hebben de juiste antwoorden.

56
00:02:49,320 --> 00:02:52,200
Zoals, in gulzig, sommige
je hebt de juiste nummers,

57
00:02:52,200 --> 00:02:53,960
je gewoon uitprinten wat extra spullen.

58
00:02:53,960 --> 00:02:55,940
En die extra dingen
eigenlijk niet de cheque,

59
00:02:55,940 --> 00:02:58,440
omdat de computer niet
echt weten wat het zoekt.

60
00:02:58,440 --> 00:03:00,981
En zo zal het gewoon doorlopen,
zien dat uw output niet

61
00:03:00,981 --> 00:03:03,810
overeenkomen met wat we verwachten dat het antwoord
te zijn, en markeer het is verkeerd.

62
00:03:03,810 --> 00:03:06,560
>> En ik weet dat er in
sommige van uw gevallen deze week.

63
00:03:06,560 --> 00:03:09,870
Dus ging ik terug en handmatig
herindeling ieders code.

64
00:03:09,870 --> 00:03:12,780
In de toekomst echter,
alsjeblieft, alsjeblieft zorg ervoor dat

65
00:03:12,780 --> 00:03:14,570
dat je draait
Controleer 50 op uw code.

66
00:03:14,570 --> 00:03:17,970
Want het is een soort van een pijn voor de TA
te hebben om terug te gaan en handmatig opnieuw sorteren

67
00:03:17,970 --> 00:03:21,197
elke PSET voor elke
single, weinig gemist bijvoorbeeld.

68
00:03:21,197 --> 00:03:22,530
Dus ik niet opstijgen geen punten.

69
00:03:22,530 --> 00:03:25,210
Ik denk dat ik duurde misschien af
één of twee voor het ontwerp.

70
00:03:25,210 --> 00:03:27,710
In de toekomst echter, als
je bent niet check50,

71
00:03:27,710 --> 00:03:31,330
punten genomen
off voor de correctheid.

72
00:03:31,330 --> 00:03:35,020
>> Bovendien zijn psets
wijten vrijdag op de middag.

73
00:03:35,020 --> 00:03:38,990
Ik denk dat er een zeven minuten
laat aflossingsvrije periode dat wij u.

74
00:03:38,990 --> 00:03:42,434
Per Harvard tijd, ze mogen
zeven minuten te laat om alles.

75
00:03:42,434 --> 00:03:44,350
Dus hier in Yale, zullen we
zich te houden aan dat ook.

76
00:03:44,350 --> 00:03:47,910
Maar vrij veel, om 12:07,
als je PSET niet in,

77
00:03:47,910 --> 00:03:49,720
het gaat zo laat worden gemarkeerd.

78
00:03:49,720 --> 00:03:53,160
En dus terwijl het wordt gemarkeerd
zo laat de TA-- ik ben

79
00:03:53,160 --> 00:03:54,870
nog steeds worden de indeling van uw psets.

80
00:03:54,870 --> 00:03:56,760
Dus je zult nog steeds een cijfer verschijnen.

81
00:03:56,760 --> 00:03:58,820
Echter, weet dat bij
het einde van het semester,

82
00:03:58,820 --> 00:04:02,270
Alle late psets zal gewoon worden
automatisch op nul gezet door de computer.

83
00:04:02,270 --> 00:04:04,490
>> We doen dit om twee redenen.

84
00:04:04,490 --> 00:04:09,220
Eén, soms krijgen we
verontschuldigd, zoals excuses decaan,

85
00:04:09,220 --> 00:04:10,762
later dat ik niet weten nog niet.

86
00:04:10,762 --> 00:04:13,761
Dus we willen ervoor zorgen dat we de indeling
alles voor het geval, zoals, ik ben

87
00:04:13,761 --> 00:04:15,080
ontbrekende excuus van een decaan.

88
00:04:15,080 --> 00:04:17,000
En ten tweede, houden
mind, kunt u nog steeds

89
00:04:17,000 --> 00:04:19,370
laat een PSET dat
heeft volledige scope punten.

90
00:04:19,370 --> 00:04:21,430
En dus we willen kwaliteit
al uw psets net

91
00:04:21,430 --> 00:04:24,730
om ervoor te zorgen dat uw scope's
er zijn en je ze proberen.

92
00:04:24,730 --> 00:04:29,150
Dus zelfs als het laat, zult u nog steeds
krediet voor scope punten, denk ik.

93
00:04:29,150 --> 00:04:33,730
>> Dus moraal van het verhaal is, maken
ervoor dat uw psets in on-time.

94
00:04:33,730 --> 00:04:38,350
En als ze niet op tijd,
weten dat het niet geweldig.

95
00:04:38,350 --> 00:04:41,678
Ja, voordat ik verder gaan, heeft iemand
Voor vragen over PSET feedback?

96
00:04:41,678 --> 00:04:42,178
Ja.

97
00:04:42,178 --> 00:04:43,630
>> PUBLIEK: Heb je zeggen dat we
kan dalen een van de psets?

98
00:04:43,630 --> 00:04:44,296
>> ANDI PENG: Ja.

99
00:04:44,296 --> 00:04:47,050
Dus er is negen psets algehele
in de loop van het semester.

100
00:04:47,050 --> 00:04:50,610
En als je scope
points-- dus scope is gewoon,

101
00:04:50,610 --> 00:04:53,567
vrij veel, probeer je het
probleem, brengt u in de tijd,

102
00:04:53,567 --> 00:04:56,150
je laten zien dat je hebt
gedemonstreerd heb je de spec lezen.

103
00:04:56,150 --> 00:04:57,191
Dat is vrij veel ruimte.

104
00:04:57,191 --> 00:04:59,370
En als je het vervullen
scope punten, we

105
00:04:59,370 --> 00:05:03,360
kan de laagste dalen
een op de volledige reikwijdte.

106
00:05:03,360 --> 00:05:06,790
Dus dat is in uw voordeel
voltooien en probeer elke PSET.

107
00:05:06,790 --> 00:05:10,320
>> Zelfs upload-- als geen van
hen werken, upload ze allemaal.

108
00:05:10,320 --> 00:05:13,711
En dan zullen we hopelijk in staat zijn om
geven u een aantal van deze punten terug.

109
00:05:13,711 --> 00:05:14,210
Cool.

110
00:05:14,210 --> 00:05:16,780
Een andere vragen?

111
00:05:16,780 --> 00:05:17,840
Grote.

112
00:05:17,840 --> 00:05:21,960
>> Ten tweede kantoor hours-- een paar
snelle notities over kantooruren.

113
00:05:21,960 --> 00:05:24,300
Dus eerst, komt in het begin van de week.

114
00:05:24,300 --> 00:05:26,909
Niemand is ooit
spreekuur op maandag.

115
00:05:26,909 --> 00:05:28,700
Christabel kwam
kantooruren gisteravond.

116
00:05:28,700 --> 00:05:29,691
Ja, Christabel.

117
00:05:29,691 --> 00:05:32,190
En wat hebben we op het kantoor
uur gisteravond, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> PUBLIEK: We hadden ijs.

119
00:05:33,020 --> 00:05:36,160
>> ANDI PENG: Dus dat klopt, we hadden
ijs op het kantoor uur gisteravond.

120
00:05:36,160 --> 00:05:39,390
Terwijl ik je niet kan beloven dat
we zullen ijs bij kantooruren

121
00:05:39,390 --> 00:05:43,230
elke week, wat ik je kan beloven
is dat er aanzienlijk zal een

122
00:05:43,230 --> 00:05:45,380
betere student TA ratio.

123
00:05:45,380 --> 00:05:47,650
Net als legit, het is 3-1.

124
00:05:47,650 --> 00:05:50,350
Overwegende, dat contrast met
Donderdag, heb je ongeveer 150 kreeg

125
00:05:50,350 --> 00:05:52,830
echt gestrest kinderen en geen ijs.

126
00:05:52,830 --> 00:05:55,360
En het is gewoon niet productief voor iedereen.

127
00:05:55,360 --> 00:05:58,730
Dus moraal van het verhaal is, kom vroeg
aan kantooruren en goede dingen

128
00:05:58,730 --> 00:06:00,310
zal gebeuren.

129
00:06:00,310 --> 00:06:02,110
>> Ook kom bereid om vragen te stellen.

130
00:06:02,110 --> 00:06:03,200
Weet je?

131
00:06:03,200 --> 00:06:05,420
Ongeacht wat TA, I
denken, hebben gezegd,

132
00:06:05,420 --> 00:06:10,710
we hebben het krijgen van een paar studenten
die komen donderdag om, zoals, 10:50

133
00:06:10,710 --> 00:06:15,100
niet de spec gelezen
het zijn als help me, help me.

134
00:06:15,100 --> 00:06:18,200
Helaas is op dat moment, is er
niet veel wat we kunnen doen om u te helpen.

135
00:06:18,200 --> 00:06:19,590
Dus kom vroeg in de week.

136
00:06:19,590 --> 00:06:22,040
Kom vroeg om kantooruren.

137
00:06:22,040 --> 00:06:23,350
Kom bereid om vragen te stellen.

138
00:06:23,350 --> 00:06:25,310
Zorg ervoor dat u, als
een student, zijn de plaatsen waar

139
00:06:25,310 --> 00:06:27,620
je nodig hebt om, zodat het zijn
TA kunt u langs,

140
00:06:27,620 --> 00:06:32,850
dat is wat de kantooruren
moet worden toegewezen voor.

141
00:06:32,850 --> 00:06:37,380
>> Ten tweede, dus ik weet professoren
willen ons verrassen met testen.

142
00:06:37,380 --> 00:06:39,439
Ik had een professor die
als, yo, door de manier,

143
00:06:39,439 --> 00:06:41,230
vergeet niet dat midterm
heb je volgende week maandag.

144
00:06:41,230 --> 00:06:42,855
Ja, ik wist niet over dat midterm.

145
00:06:42,855 --> 00:06:45,630
Dus ik ga dat TA
die u eraan herinnert dat alles quiz

146
00:06:45,630 --> 00:06:47,270
0-- omdat, weet je, we CS.

147
00:06:47,270 --> 00:06:50,730
Nu dat we hebben gedaan arrays, krijg je
waarom het quiz 0, geen quiz 1, eh?

148
00:06:50,730 --> 00:06:51,320
OK.

149
00:06:51,320 --> 00:06:52,490
Oh, ik heb een aantal grinnikt op die ene.

150
00:06:52,490 --> 00:06:53,120
OK.

151
00:06:53,120 --> 00:06:59,710
>> Dus quiz 0 zal 14 oktober als
je bent in de sectie maandag-woensdag

152
00:06:59,710 --> 00:07:02,920
en 15 oktober als je in
de sectie dinsdag-donderdag.

153
00:07:02,920 --> 00:07:05,630
Dit geldt niet voor
degenen onder u aan de Harvard

154
00:07:05,630 --> 00:07:10,350
who-- Ik denk dat je allemaal
het nemen van uw quizzen op de 14e.

155
00:07:10,350 --> 00:07:13,560
>> Dus ja, volgende week, als
David, in collegezaal, gaat,

156
00:07:13,560 --> 00:07:15,747
ja, zo ongeveer dat
quiz volgende week jullie allemaal

157
00:07:15,747 --> 00:07:17,580
zal niet geschokt omdat
u sectie kwam

158
00:07:17,580 --> 00:07:19,664
en je weet dat je
quiz 0 is in twee weken.

159
00:07:19,664 --> 00:07:21,580
En we zullen beoordeling hebben
sessies en alles.

160
00:07:21,580 --> 00:07:26,360
Dus geen zorgen over
bang voor.

161
00:07:26,360 --> 00:07:29,890
Voor vragen before-- vragen
helemaal met betrekking tot logistieke problemen,

162
00:07:29,890 --> 00:07:32,591
sorteren, kantooruren, secties?

163
00:07:32,591 --> 00:07:33,090
Ja.

164
00:07:33,090 --> 00:07:35,100
>> Publiek: Dus de quiz is
gaat worden tijdens de les?

165
00:07:35,100 --> 00:07:35,766
>> ANDI PENG: Ja.

166
00:07:35,766 --> 00:07:39,460
Dus de quiz, denk ik, is 60
minuten toegewezen in dat tijdslot

167
00:07:39,460 --> 00:07:42,240
dat je gewoon zult nemen
in de collegezaal.

168
00:07:42,240 --> 00:07:44,810
Dus je hoeft niet te komen
op, zoals een willekeurige 07:00.

169
00:07:44,810 --> 00:07:46,140
Het is al goed.

170
00:07:46,140 --> 00:07:47,100
Ja.

171
00:07:47,100 --> 00:07:50,060
Cool.

172
00:07:50,060 --> 00:07:50,840
>> Prima.

173
00:07:50,840 --> 00:07:54,330
Dus we gaan
invoering van een concept voor u

174
00:07:54,330 --> 00:08:00,760
deze week dat David heeft al soort
van aangestipt in college afgelopen week.

175
00:08:00,760 --> 00:08:02,010
Het heet GDB.

176
00:08:02,010 --> 00:08:05,570
En hoeveel van jullie, terwijl in
de loop van het schrijven van uw psets,

177
00:08:05,570 --> 00:08:09,981
gemerkt hebben een grote knop die zegt
"Debug" op de bovenkant van uw IDE?

178
00:08:09,981 --> 00:08:10,480
OK.

179
00:08:10,480 --> 00:08:13,770
Dus nu gaan we eigenlijk naar ontgraven
het mysterie van wat die knop eigenlijk

180
00:08:13,770 --> 00:08:14,270
doet.

181
00:08:14,270 --> 00:08:16,790
En ik garandeer je, het is een
mooi, mooi ding.

182
00:08:16,790 --> 00:08:20,740
>> Dus tot nu toe, denk ik
er is al twee dingen

183
00:08:20,740 --> 00:08:23,320
studenten zijn doorgaans
doet bij het oplossen psets.

184
00:08:23,320 --> 00:08:27,635
Eén, ze ofwel voegen in
printf () - dus elke paar regels,

185
00:08:27,635 --> 00:08:29,760
ze voegen in een printf () -
oh, wat is dit variabel?

186
00:08:29,760 --> 00:08:32,551
Oh, wat is dit variabel now--
en u soort zien de progressie

187
00:08:32,551 --> 00:08:33,940
van de code als het loopt.

188
00:08:33,940 --> 00:08:37,030
Of de tweede methode kinderen doen is
dat ze gewoon schrijven de hele zaak

189
00:08:37,030 --> 00:08:38,610
en ga dan als volgt aan het eind.

190
00:08:38,610 --> 00:08:39,970
Hopelijk werkt het.

191
00:08:39,970 --> 00:08:44,851
Ik garandeer u, GDB is beter
dan deze beide methoden.

192
00:08:44,851 --> 00:08:45,350
Ja.

193
00:08:45,350 --> 00:08:46,980
Dus dit zal uw nieuwe beste vriend.

194
00:08:46,980 --> 00:08:51,780
Want het is een mooi ding
die visueel geeft zowel

195
00:08:51,780 --> 00:08:54,850
wat uw code doet
op een specifiek punt

196
00:08:54,850 --> 00:08:57,486
en wat al uw
variabelen dragen,

197
00:08:57,486 --> 00:08:59,610
als wat hun waarden zijn,
op dat specifieke moment.

198
00:08:59,610 --> 00:09:02,670
En op deze manier, kan je echt
set breakpoints in de code.

199
00:09:02,670 --> 00:09:04,350
U kunt lopen door lijn per lijn.

200
00:09:04,350 --> 00:09:07,324
En GDB zal gewoon voor
u, weergegeven voor u,

201
00:09:07,324 --> 00:09:09,490
wat al uw variabelen
zijn, wat doen ze,

202
00:09:09,490 --> 00:09:10,656
wat er in de code.

203
00:09:10,656 --> 00:09:13,240
En zodanig, dat het
zo veel makkelijker om te zien

204
00:09:13,240 --> 00:09:17,120
wat er gebeurt in plaats van printf-ing
of het schrijven van uw uitspraken.

205
00:09:17,120 --> 00:09:19,160
>> Dus we een voorbeeld van dit later te doen.

206
00:09:19,160 --> 00:09:20,660
Dus dit lijkt een beetje abstract.

207
00:09:20,660 --> 00:09:23,490
Geen zorgen, we zullen voorbeelden doen.

208
00:09:23,490 --> 00:09:29,170
En zo wezen, de drie grootste,
meest gebruikte functies die je nodig hebt in GDB

209
00:09:29,170 --> 00:09:32,500
zijn de volgende, stap over,
en Stap in knoppen.

210
00:09:32,500 --> 00:09:34,860
Ik ga over het hoofd
er eigenlijk nu.

211
00:09:34,860 --> 00:09:40,930
>> Zodat jullie allemaal te zien dat
of moet ik een beetje zoomen?

212
00:09:40,930 --> 00:09:43,220

213
00:09:43,220 --> 00:09:44,470
In de rug, zie je dat?

214
00:09:44,470 --> 00:09:45,730
Moet ik te vergroten?

215
00:09:45,730 --> 00:09:46,480
Gewoon een klein beetje?

216
00:09:46,480 --> 00:09:49,390
OK, cool.

217
00:09:49,390 --> 00:09:50,280
Daar gaan we.

218
00:09:50,280 --> 00:09:50,960
OK.

219
00:09:50,960 --> 00:09:57,000
>> Dus ik heb, hier, mijn
implementatie voor hebberig.

220
00:09:57,000 --> 00:10:01,430
En terwijl veel van jullie schreef
hebzuchtige in while lus form-- dat

221
00:10:01,430 --> 00:10:04,890
is een perfect aanvaardbare manier te doen
het-- een andere manier om het te doen is om gewoon

222
00:10:04,890 --> 00:10:06,280
verdelen de modulo.

223
00:10:06,280 --> 00:10:09,290
Want dan kunt u uw
waarde en dan heb je rest.

224
00:10:09,290 --> 00:10:11,150
En dan kun je gewoon
Voeg het allemaal samen.

225
00:10:11,150 --> 00:10:13,390
Doet de logica van wat ik doe
hier zin om iedereen,

226
00:10:13,390 --> 00:10:14,117
voordat we beginnen?

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
Cool.

230
00:10:18,710 --> 00:10:19,210
Grote.

231
00:10:19,210 --> 00:10:21,290
Het is een vrij sexy stuk
van de code, zou ik zeggen.

232
00:10:21,290 --> 00:10:23,502
Zoals ik al zei, David, in
lezing, na een tijdje,

233
00:10:23,502 --> 00:10:25,960
u zult beginnen te zien code
als iets dat is prachtig.

234
00:10:25,960 --> 00:10:29,950
En soms als je ziet mooie
code, het is zo'n heerlijk gevoel.

235
00:10:29,950 --> 00:10:35,410
>> Dus Maar hoewel deze code is erg
mooi, is het niet goed werkt.

236
00:10:35,410 --> 00:10:37,750
Dus laten we lopen check50 op dit punt.

237
00:10:37,750 --> 00:10:39,440
Controleer 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
Oh, pset1.

243
00:10:47,520 --> 00:10:50,970

244
00:10:50,970 --> 00:10:52,890
OK.

245
00:10:52,890 --> 00:10:53,900
Dus we lopen check50.

246
00:10:53,900 --> 00:11:01,550

247
00:11:01,550 --> 00:11:07,170
>> En zoals jullie hier kunt zien,
het is niet een paar gevallen.

248
00:11:07,170 --> 00:11:10,165
En voor sommigen van u, in de
loop van het doen van uw probleem sets,

249
00:11:10,165 --> 00:11:11,110
je bent zoals, ah, waarom is het niet werkt.

250
00:11:11,110 --> 00:11:13,318
Waarom is het werken voor een aantal
waarden, maar niet voor anderen?

251
00:11:13,318 --> 00:11:17,760
Nou, GDB gaat helpen u figuur
waarom die inputs werkten niet.

252
00:11:17,760 --> 00:11:18,320
>> OK.

253
00:11:18,320 --> 00:11:21,640
Dus laten we zien, één van de
cheques Ik was niet in check50

254
00:11:21,640 --> 00:11:24,920
was de invoerwaarde van 0,41.

255
00:11:24,920 --> 00:11:27,830
Dus het juiste antwoord dat
moet u krijgt een 4.

256
00:11:27,830 --> 00:11:33,090
Maar wat ik printen
is de 3-n, dat is onjuist.

257
00:11:33,090 --> 00:11:36,190
Dus laten we dit handmatig uitvoeren, net
Zorg ervoor dat check50 werkt.

258
00:11:36,190 --> 00:11:36,940
Laten we het doen ./greedy.

259
00:11:36,940 --> 00:11:40,130

260
00:11:40,130 --> 00:11:43,340
Oeps, ik hebberig te maken.

261
00:11:43,340 --> 00:11:43,840
Daar gaan we.

262
00:11:43,840 --> 00:11:44,381
Nu ./greedy.

263
00:11:44,381 --> 00:11:46,950

264
00:11:46,950 --> 00:11:47,670
>> Hoeveel is te danken?

265
00:11:47,670 --> 00:11:49,550
Laten we het doen 0,41.

266
00:11:49,550 --> 00:11:52,590
En yep, zien we hier
dat het uitvoeren van 3

267
00:11:52,590 --> 00:11:55,160
wanneer het juiste antwoord,
in feite moet worden 4.

268
00:11:55,160 --> 00:12:01,460
Dus laten we voeren GDB en zien hoe we
kan gaan over de vaststelling van dit probleem.

269
00:12:01,460 --> 00:12:03,992
>> Dus de eerste stap in
altijd debuggen uw code

270
00:12:03,992 --> 00:12:05,950
is een breekpunt,
of een punt waarop u

271
00:12:05,950 --> 00:12:09,079
wil dat de computer of de
debugger te gaan kijken naar.

272
00:12:09,079 --> 00:12:11,120
Dus als je niet echt
weet wat je probleem is,

273
00:12:11,120 --> 00:12:14,670
meestal, de typische ding willen we
doen is om ons breekpunt op hoofd.

274
00:12:14,670 --> 00:12:18,520
Dus als jullie dit zien
rode knop daar,

275
00:12:18,520 --> 00:12:22,860
yep, dat was me het instellen van een
breekpunt voor de belangrijkste functie.

276
00:12:22,860 --> 00:12:24,130
Ik die klik.

277
00:12:24,130 --> 00:12:26,130
>> En dan kan ik gaan tot mijn Debug knop.

278
00:12:26,130 --> 00:12:27,036
Ik raakte die knop.

279
00:12:27,036 --> 00:12:31,710

280
00:12:31,710 --> 00:12:36,555
Laat me opnieuw uit als ik kan.

281
00:12:36,555 --> 00:12:38,020
Daar gaan we.

282
00:12:38,020 --> 00:12:40,730
Dus we hebben, hier, een paneel aan de rechterkant.

283
00:12:40,730 --> 00:12:43,680
Het spijt me, jongens in de rug, je
kan niet echt heel goed.

284
00:12:43,680 --> 00:12:49,090
Maar in wezen alle
deze rechter paneel doet

285
00:12:49,090 --> 00:12:53,130
is het bijhouden van zowel het gemarkeerde
lijn, dat is de regel code

286
00:12:53,130 --> 00:12:56,640
de computer momenteel actief is,
alsmede alle variabelen

287
00:12:56,640 --> 00:12:57,600
Hieronder.

288
00:12:57,600 --> 00:13:00,487
>> Dus je hebt cent, munten, n,
alle aangegeven verschillende dingen

289
00:13:00,487 --> 00:13:01,070
Op dit moment.

290
00:13:01,070 --> 00:13:04,850
Geen zorgen, want we hebben niet echt
geïnitialiseerd ze nog enige variabelen.

291
00:13:04,850 --> 00:13:07,200
Dus in uw computer, uw
computer is gewoon te zien,

292
00:13:07,200 --> 00:13:14,376
oh, 32767 was de laatst gebruikte functie
van die geheugenruimte in mijn computer.

293
00:13:14,376 --> 00:13:16,000
En dat is waar cent momenteel is.

294
00:13:16,000 --> 00:13:19,360
Maar niet dat als je eenmaal de code uitvoert,
Moet geïnitialiseerd worden.

295
00:13:19,360 --> 00:13:24,110
>> Dus laten we gaan door, lijn door
lijn, wat is hier aan de hand.

296
00:13:24,110 --> 00:13:25,350
OK.

297
00:13:25,350 --> 00:13:29,400
Dus hier zijn de drie
knoppen die ik net uitgelegd.

298
00:13:29,400 --> 00:13:34,090
Je hebt de Play of de functie Run,
knop, heb je de stap op de knop,

299
00:13:34,090 --> 00:13:36,600
en je hebt ook de Stap in knop.

300
00:13:36,600 --> 00:13:41,260
En wezen alledrie
ze gewoon gaan door de code

301
00:13:41,260 --> 00:13:42,690
en doe verschillende dingen.

302
00:13:42,690 --> 00:13:45,680
>> Dus meestal, als je het debuggen,
we willen niet gewoon op Play,

303
00:13:45,680 --> 00:13:47,930
want Play zal gewoon lopen
code voor het einde van het.

304
00:13:47,930 --> 00:13:49,070
En dan zul je niet echt
weet wat je probleem

305
00:13:49,070 --> 00:13:51,432
is tenzij u meerdere breakpoints.

306
00:13:51,432 --> 00:13:53,890
Als u meerdere breekpunten ingesteld,
het zal gewoon automatisch

307
00:13:53,890 --> 00:13:56,030
van het ene breekpunt,
naar de volgende, naar de volgende.

308
00:13:56,030 --> 00:13:58,030
Maar in dit geval we hebben
alleen dat ene, omdat we

309
00:13:58,030 --> 00:13:59,970
willen onze manier van werken
van boven naar beneden naar beneden.

310
00:13:59,970 --> 00:14:04,830
Dus we gaan naar die knop te negeren
op dit moment voor het doel van dit programma.

311
00:14:04,830 --> 00:14:08,230
>> Dus de stap over functie net
stappen op elke lijn

312
00:14:08,230 --> 00:14:11,510
en vertelt je wat
de computer aan het doen is.

313
00:14:11,510 --> 00:14:14,630
De Stap in functie gaat
in de eigenlijke functie

314
00:14:14,630 --> 00:14:16,000
dat is op uw lijn van de code.

315
00:14:16,000 --> 00:14:19,070
Dus bijvoorbeeld, zoals printf (),
dat is een functie, toch?

316
00:14:19,070 --> 00:14:21,980
Als ik wilde fysiek stap
in de printf () functie,

317
00:14:21,980 --> 00:14:25,610
Ik zou eigenlijk gaan in het stuk
code waar de printf () werd geschreven en zien

318
00:14:25,610 --> 00:14:26,730
wat gebeurt er daar.

319
00:14:26,730 --> 00:14:29,924
>> Maar meestal, gaan we ervan uit dat
de code die wij geven u werkt.

320
00:14:29,924 --> 00:14:31,340
We veronderstellen dat de printf () werkt.

321
00:14:31,340 --> 00:14:33,170
We nemen aan dat getInt () werkt.

322
00:14:33,170 --> 00:14:35,170
Dus er is geen noodzaak om
stap in die functies.

323
00:14:35,170 --> 00:14:37,170
Maar als er functies
dat je jezelf schrijven

324
00:14:37,170 --> 00:14:39,060
dat u wilt controleren
wat er gaande is,

325
00:14:39,060 --> 00:14:41,200
je zou willen stappen
in die functie.

326
00:14:41,200 --> 00:14:43,940
>> Dus nu zijn we gewoon gaan
stap over dit stukje code.

327
00:14:43,940 --> 00:14:44,485
Dus laten we zien.

328
00:14:44,485 --> 00:14:46,547
Oh, print, "Oh hai, hoe
veel verandering is te danken? "

329
00:14:46,547 --> 00:14:47,130
Kan ons niet schelen.

330
00:14:47,130 --> 00:14:49,830
We weten dat het werkt,
zodat we stap over het.

331
00:14:49,830 --> 00:14:53,290
>> Zo n, dat is onze float dat
we hebben initialized-- of declared--

332
00:14:53,290 --> 00:14:56,810
op de top, we zijn nu
gelijk dat voor GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Dus laten we stap over dat.

334
00:14:57,810 --> 00:14:59,580
En we zien in de
bodem hier het programma

335
00:14:59,580 --> 00:15:03,360
wordt gevraagd mij het invoeren van een waarde.

336
00:15:03,360 --> 00:15:08,580
Dus laten we het invoeren van de waarde die we willen
hier testen, wat 0,41.

337
00:15:08,580 --> 00:15:09,160
Grote.

338
00:15:09,160 --> 00:15:12,780
>> Dus nu N-- doen jullie zien
Hier, op de bottom-- het

339
00:15:12,780 --> 00:15:15,140
stored-- omdat we
nog niet afgerond, is het

340
00:15:15,140 --> 00:15:19,540
opgeslagen in deze als reusachtige
float dat is ,4099999996,

341
00:15:19,540 --> 00:15:22,550
die dicht genoeg bij onze
doeleinden, nu, tot 0,41.

342
00:15:22,550 --> 00:15:26,090
En dan zullen we zien later, zoals we
blijven intensivering over het programma,

343
00:15:26,090 --> 00:15:29,850
na hier, is n geworden
afgeronde en centen is geworden 41.

344
00:15:29,850 --> 00:15:30,350
Grote.

345
00:15:30,350 --> 00:15:32,230
Dus we weten dat het werk van onze afronding's.

346
00:15:32,230 --> 00:15:34,700
We weten dat we de
juiste aantal centen,

347
00:15:34,700 --> 00:15:36,990
dus we weten dat dat
niet echt het probleem.

348
00:15:36,990 --> 00:15:40,050
>> Dus we blijven een stap
in dit programma.

349
00:15:40,050 --> 00:15:40,900
Wij gaan hier.

350
00:15:40,900 --> 00:15:46,139
En dus na deze regel code, we
moeten weten hoeveel kwartalen we hebben.

351
00:15:46,139 --> 00:15:46,680
We stap over.

352
00:15:46,680 --> 00:15:52,040
En je ziet wat we doen, in feite, hebben een
kwartaal want we hebben afgetrokken 25

353
00:15:52,040 --> 00:15:53,790
Aanbevolen beginwaarde van 41.

354
00:15:53,790 --> 00:15:55,890
En we hebben 16 links voor onze centen.

355
00:15:55,890 --> 00:15:58,830
>> Heeft iedereen begrijpen hoe
het programma is doorlopen

356
00:15:58,830 --> 00:16:02,980
en waarom cent is nu uitgegroeid tot 16
en waarom, nu, munten is geworden 1?

357
00:16:02,980 --> 00:16:04,610
Is iedereen na die logica?

358
00:16:04,610 --> 00:16:05,110
Cool.

359
00:16:05,110 --> 00:16:07,860
Dus vanaf dit punt, de
werkprogramma's, toch?

360
00:16:07,860 --> 00:16:09,797
We weten dat het precies doet
wat we willen dat het.

361
00:16:09,797 --> 00:16:11,880
En we hebben niet echt
hebben om uit te printen, oh, wat

362
00:16:11,880 --> 00:16:14,430
is cent op dit punt,
wat munten op dit punt.

363
00:16:14,430 --> 00:16:17,170
>> We blijven gaan door het programma.

364
00:16:17,170 --> 00:16:18,100
Overstappen.

365
00:16:18,100 --> 00:16:18,620
Cool.

366
00:16:18,620 --> 00:16:19,700
We gaan over dubbeltjes.

367
00:16:19,700 --> 00:16:20,200
Grote.

368
00:16:20,200 --> 00:16:22,367
We zien dat het is genomen
off $ 0,10 voor een dubbeltje.

369
00:16:22,367 --> 00:16:23,450
En nu hebben we twee munten.

370
00:16:23,450 --> 00:16:25,260
Dat is correct.

371
00:16:25,260 --> 00:16:31,555
>> We gaan over centen en we zien
dat we hebben overgebleven cent.

372
00:16:31,555 --> 00:16:32,680
Hmm, dat is vreemd.

373
00:16:32,680 --> 00:16:37,540
Hier op het programma, moest ik
mijn centen te hebben afgetrokken.

374
00:16:37,540 --> 00:16:39,400
Misschien was ik gewoon niet
doen die lijn recht.

375
00:16:39,400 --> 00:16:42,190
En helaas, kunt u zien
hier, omdat we weten

376
00:16:42,190 --> 00:16:44,360
dat we de intensivering
via leidingen 32 en 33,

377
00:16:44,360 --> 00:16:50,560
dat is waar ons programma
onjuist had variabelen lopen.

378
00:16:50,560 --> 00:16:55,136
Dus we kunnen kijken en zien, oh,
Ik aftrekken cent hier,

379
00:16:55,136 --> 00:16:57,010
maar ik ben niet echt
toevoegen aan mijn muntwaarde.

380
00:16:57,010 --> 00:16:57,860
Ik ben toe te voegen aan cent.

381
00:16:57,860 --> 00:17:00,234
En ik wil niet toe te voegen aan
cent, ik wil toevoegen aan munten.

382
00:17:00,234 --> 00:17:05,420
Dus als we dat veranderen om munten,
we hebben een werkprogramma.

383
00:17:05,420 --> 00:17:06,730
Ik kan check50 draaien.

384
00:17:06,730 --> 00:17:11,063
Je kunt gewoon afsluiten van GDB recht
hier en dan weer rennen check50.

385
00:17:11,063 --> 00:17:11,938
Ik kan dit gewoon doen.

386
00:17:11,938 --> 00:17:14,822

387
00:17:14,822 --> 00:17:18,480
Ik moet hebberig te maken.

388
00:17:18,480 --> 00:17:19,940
0,41.

389
00:17:19,940 --> 00:17:22,819
En hier, het is druk
het juiste antwoord.

390
00:17:22,819 --> 00:17:26,569
>> Dus zoals jullie kunnen zien, GDB
is echt een krachtig instrument

391
00:17:26,569 --> 00:17:29,940
want als we hebben zo veel code
gaande en zoveel variabelen

392
00:17:29,940 --> 00:17:32,510
dat het moeilijk is voor ons, als
een mens, bij te houden.

393
00:17:32,510 --> 00:17:35,360
De computer, in de GDB
debugger, heeft het vermogen

394
00:17:35,360 --> 00:17:37,020
te houden van alles.

395
00:17:37,020 --> 00:17:40,480
Ik weet het, in Visionaire, jullie waarschijnlijk
kunnen sommige segmentatie fouten hebben geraakt

396
00:17:40,480 --> 00:17:43,150
omdat je loopt
uit grenzen van de array.

397
00:17:43,150 --> 00:17:46,510
In het voorbeeld van Caesar, dat is
precies wat ik heb hier geïmplementeerd.

398
00:17:46,510 --> 00:17:50,060
>> Dus ik vergat om te controleren op
wat er zou gebeuren als ik

399
00:17:50,060 --> 00:17:52,510
niet twee commandoregel argumenten.

400
00:17:52,510 --> 00:17:53,880
Ik wist alleen niet in dat het inchecken.

401
00:17:53,880 --> 00:17:57,380
En dus als ik zonder Debug-- ik
mijn breekpunt daar rechts.

402
00:17:57,380 --> 00:17:58,055
Ik run 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
Dus eigenlijk, GDB werd verondersteld
hebben me daar verteld

407
00:18:20,350 --> 00:18:22,300
was een segmentation fault daar.

408
00:18:22,300 --> 00:18:24,883
Ik weet niet wat er gaande was
daar, maar toen ik liep,

409
00:18:24,883 --> 00:18:25,590
het werkte.

410
00:18:25,590 --> 00:18:29,410
Als je regels code doorlopen en
GDB zou zomaar ineens stoppen op je,

411
00:18:29,410 --> 00:18:31,540
omhoog gaan en kijk wat de rode fout is.

412
00:18:31,540 --> 00:18:33,930
Het zal je vertellen, hey, je
had een segmentation fault,

413
00:18:33,930 --> 00:18:38,550
wat betekent dat je geprobeerd om toegang te krijgen
ruimte in een array die niet bestonden.

414
00:18:38,550 --> 00:18:39,050
Ja.

415
00:18:39,050 --> 00:18:43,280
>> Dus in het volgende probleem
zet deze week, jullie

416
00:18:43,280 --> 00:18:45,600
zal waarschijnlijk een heleboel
variabelen rondzweven.

417
00:18:45,600 --> 00:18:48,560
Je gaat niet om zeker te zijn wat
ze betekenen allemaal op een bepaald punt.

418
00:18:48,560 --> 00:18:53,560
Dus GDB zal je echt helpen bij het uitzoeken
wat ze allemaal gelijk

419
00:18:53,560 --> 00:18:55,940
en in staat om visueel te zien.

420
00:18:55,940 --> 00:19:01,995
Is er iemand in de war over hoe
elk van die werkzaam was?

421
00:19:01,995 --> 00:19:02,495
Cool.

422
00:19:02,495 --> 00:19:10,121

423
00:19:10,121 --> 00:19:10,620
Prima.

424
00:19:10,620 --> 00:19:14,260
Dus na dat, we zijn
ga naar rechts duiken

425
00:19:14,260 --> 00:19:17,562
in vier verschillende
types van soorten voor deze week.

426
00:19:17,562 --> 00:19:19,520
Hoeveel van jullie, de eerste
van al, voordat we beginnen,

427
00:19:19,520 --> 00:19:23,020
het hele spec voor pset3 hebt gelezen?

428
00:19:23,020 --> 00:19:23,824
OK.

429
00:19:23,824 --> 00:19:24,740
Ik ben trots op jullie.

430
00:19:24,740 --> 00:19:29,110
Dat is hetzelfde als de helft van de klas, die
is aanzienlijk meer dan de vorige keer.

431
00:19:29,110 --> 00:19:33,950
>> Dus dat is geweldig, want als
we praten over de inhoud

432
00:19:33,950 --> 00:19:36,170
in lecture-- of sorry,
in section-- Ik hou

433
00:19:36,170 --> 00:19:38,210
een hoop die betrekking
terug naar wat het is PSET

434
00:19:38,210 --> 00:19:40,210
en hoe je wilt
implementeren dat u in uw PSET.

435
00:19:40,210 --> 00:19:42,400
Dus als je komt met
lees de specificatie, het zal

436
00:19:42,400 --> 00:19:45,510
een stuk makkelijker voor u om te begrijpen
waar ik het over heb als ik zeg,

437
00:19:45,510 --> 00:19:48,720
oh ja, dit zou een echt
goede plek om dit soort uit te voeren.

438
00:19:48,720 --> 00:19:52,870
Dus degenen onder u die hebben gelezen van de
spec weten dat, als onderdeel van uw PSET,

439
00:19:52,870 --> 00:19:54,900
je gaat te hebben om
brief type soort.

440
00:19:54,900 --> 00:19:58,670
Dus dit kan zeer nuttig zijn
voor veel van jullie vandaag.

441
00:19:58,670 --> 00:20:01,760
>> Dus we zullen beginnen met,
in wezen de meest eenvoudige soort

442
00:20:01,760 --> 00:20:04,580
van sorteren, de selectie sorteren.

443
00:20:04,580 --> 00:20:06,800
De typische algoritme voor
hoe we zouden gaan over dit

444
00:20:06,800 --> 00:20:10,460
is-- David ging door deze all in
lezing, dus ik zal snel bewegen langs

445
00:20:10,460 --> 00:20:13,900
hier-- is in wezen, je
hebben een scala van waarden.

446
00:20:13,900 --> 00:20:17,170
En dan vind je het
kleinste ongesorteerd waarde

447
00:20:17,170 --> 00:20:20,200
en je swap die waarde met
de eerste ongesorteerde waarde.

448
00:20:20,200 --> 00:20:22,700
En dan moet je gewoon blijven herhalen
met de rest van de lijst.

449
00:20:22,700 --> 00:20:25,740
>> En hier is een visuele verklaring
hoe dat zou werken.

450
00:20:25,740 --> 00:20:30,460
Dus bijvoorbeeld, als we beginnen
met een serie van vijf elementen, index

451
00:20:30,460 --> 00:20:35,910
0-4, met 3, 5, 2, 6 en 4 waarden
geplaatst in de array-- zo goed nu,

452
00:20:35,910 --> 00:20:38,530
we gaan gewoon om te veronderstellen
dat ze allemaal ongesorteerd

453
00:20:38,530 --> 00:20:41,130
omdat we anders niet getest.

454
00:20:41,130 --> 00:20:44,130
>> Dus hoe een selectie soort zou
werk is dat het zou eerst

455
00:20:44,130 --> 00:20:46,800
lopen door het geheel
van de ongesorteerde array.

456
00:20:46,800 --> 00:20:49,120
Het zou halen uit de kleinste waarde.

457
00:20:49,120 --> 00:20:51,750
In dit geval 3, rechts
Nu is het kleinst.

458
00:20:51,750 --> 00:20:52,680
Het wordt om 5.

459
00:20:52,680 --> 00:20:55,620
Nope, 5 niet groter than--
of sorry, niet minder than-- 3.

460
00:20:55,620 --> 00:20:57,779
Zodat de minimale waarde is nog steeds 3.

461
00:20:57,779 --> 00:20:58,695
En dan krijg je 2.

462
00:20:58,695 --> 00:21:00,990
De computer ziet, oh, 2 minder dan 3.

463
00:21:00,990 --> 00:21:02,750
2 moet nu de minimale waarde.

464
00:21:02,750 --> 00:21:06,630
En zo 2 swaps met die eerste waarde.

465
00:21:06,630 --> 00:21:10,702
>> Dus na één keer, we inderdaad zien
de 2 en 3 zijn verwisseld.

466
00:21:10,702 --> 00:21:13,910
En we gaan gewoon te blijven doen
dit opnieuw met de rest van de matrix.

467
00:21:13,910 --> 00:21:17,660
Dus we gaan gewoon doorlopen
de laatste vier indexen van de array.

468
00:21:17,660 --> 00:21:20,670
We zullen zien dat er 3 is
de volgende minimale waarde.

469
00:21:20,670 --> 00:21:23,240
Dus we gaan om te wisselen die met 4.

470
00:21:23,240 --> 00:21:26,900
En dan zijn we gewoon gaan houden
loopt door tot uiteindelijk je

471
00:21:26,900 --> 00:21:33,730
krijgen een gesorteerde array waarin
2, 3, 4, 5 en 6 zijn allemaal gesorteerd.

472
00:21:33,730 --> 00:21:37,530
Heeft iedereen begrijpt de logica
van hoe een selectie soort werkt?

473
00:21:37,530 --> 00:21:39,669
>> Je hoeft alleen maar een soort
van een minimale waarde.

474
00:21:39,669 --> 00:21:41,210
Je bent het bijhouden van wat dat is.

475
00:21:41,210 --> 00:21:45,170
En wanneer je het te vinden, je swap
de eerste waarde in de array--

476
00:21:45,170 --> 00:21:48,740
of, niet de eerste value--
de volgende waarde in de matrix.

477
00:21:48,740 --> 00:21:50,150
Cool.

478
00:21:50,150 --> 00:21:55,460
>> Zodat jullie soort
zag vanuit een korte blik,

479
00:21:55,460 --> 00:21:58,450
we gaan dit pseudo-out.

480
00:21:58,450 --> 00:22:02,510
Dus als jullie in de rug willen
vormen een groep, iedereen aan tafel

481
00:22:02,510 --> 00:22:06,170
kan een beetje partner te vormen, ga ik
u jongens als drie minuten geven

482
00:22:06,170 --> 00:22:08,190
om gewoon door te praten
de logica in het Engels,

483
00:22:08,190 --> 00:22:14,161
hoe kunnen we in staat zijn om uit te voeren
pseudocode om een ​​selectie soort schrijven.

484
00:22:14,161 --> 00:22:14,910
En er is snoep.

485
00:22:14,910 --> 00:22:16,118
Kom op en krijgen snoep.

486
00:22:16,118 --> 00:22:19,520
Als je in de rug en je wilt
snoep, kan ik gooi snoep op jou.

487
00:22:19,520 --> 00:22:22,850
Eigenlijk doe u-- cool.

488
00:22:22,850 --> 00:22:23,552
Oh sorry.

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
>> Dus als we zouden willen, als
Een cursus volgen, schrijven pseudocode

493
00:25:27,140 --> 00:25:30,466
hoe men zou kunnen benaderen
dit probleem, maar voel je vrij.

494
00:25:30,466 --> 00:25:32,340
Ik kom net rond gaan en,
in orde, vraag groepen

495
00:25:32,340 --> 00:25:35,065
voor de volgende regel
wat we moeten doen.

496
00:25:35,065 --> 00:25:37,840
Dus als jullie willen beginnen
off, wat is het eerste wat

497
00:25:37,840 --> 00:25:40,600
te doen als je probeert om
uitvoering van een manier om dit programma te lossen

498
00:25:40,600 --> 00:25:43,480
om een ​​lijst selectief sorteren?

499
00:25:43,480 --> 00:25:46,349
Laten we aannemen dat we
hebben een scala, oké?

500
00:25:46,349 --> 00:25:49,088
>> PUBLIEK: U wilt wat te creëren
soort [onverstaanbaar] dat je

501
00:25:49,088 --> 00:25:50,420
door je hele reeks.

502
00:25:50,420 --> 00:25:51,128
>> ANDI Peng: Recht.

503
00:25:51,128 --> 00:25:54,100
Dus je gaat te willen herhalen
door elke ruimte, toch?

504
00:25:54,100 --> 00:26:05,490
Zo goed.

505
00:26:05,490 --> 00:26:08,600
Als jullie mij willen het geven
volgende line-- ja, in de rug.

506
00:26:08,600 --> 00:26:11,414

507
00:26:11,414 --> 00:26:13,290
>> PUBLIEK: Check ze
Alle voor de kleinste.

508
00:26:13,290 --> 00:26:14,248
>> ANDI Peng: Daar gaan we.

509
00:26:14,248 --> 00:26:17,438
Dus we willen om door te gaan en te controleren om
zien wat de minimale waarde is, toch?

510
00:26:17,438 --> 00:26:22,110

511
00:26:22,110 --> 00:26:24,840
Ik ga om te korten, dat op "min."

512
00:26:24,840 --> 00:26:27,658
Wat willen jullie doen na
u de minimale waarde hebt gevonden?

513
00:26:27,658 --> 00:26:28,533
>> PUBLIEK: [onverstaanbaar]

514
00:26:28,533 --> 00:26:29,942

515
00:26:29,942 --> 00:26:33,150
ANDI PENG: Dus je gaat te willen
schakelaar met de eerste van die array,

516
00:26:33,150 --> 00:26:33,650
toch?

517
00:26:33,650 --> 00:26:45,120

518
00:26:45,120 --> 00:26:46,850
Dat is het begin, ik ga zeggen.

519
00:26:46,850 --> 00:26:47,220
Prima.

520
00:26:47,220 --> 00:26:50,386
Dus nu dat u hebt verwisseld de eerste
één, wat wil je doen na dat?

521
00:26:50,386 --> 00:26:54,840
Dus nu weten we dat dit hier
moet de kleinste waarde, toch?

522
00:26:54,840 --> 00:26:58,310
Dan moet je een extra rust
van de matrix die ongesorteerde.

523
00:26:58,310 --> 00:27:01,569
Dus wat je hier wilt doen, als je
jongens willen me de volgende regel te geven?

524
00:27:01,569 --> 00:27:04,610
Publiek: Dus dan wil je herhalen
gedurende de rest van de matrix.

525
00:27:04,610 --> 00:27:05,276
ANDI PENG: Ja.

526
00:27:05,276 --> 00:27:09,857
En dus wat maakt iteratie door middel van
soort impliceren we zullen waarschijnlijk nodig?

527
00:27:09,857 --> 00:27:10,440
Wat voor soort--

528
00:27:10,440 --> 00:27:12,057
>> PUBLIEK: Oh, een extra variabele?

529
00:27:12,057 --> 00:27:13,890
ANDI PENG: Waarschijnlijk
een andere lus, toch?

530
00:27:13,890 --> 00:27:28,914
Dus we waarschijnlijk te willen
through-- geweldig om te herhalen.

531
00:27:28,914 --> 00:27:31,830
En dan zul je om terug te gaan en
Controleer waarschijnlijk het minimum weer,

532
00:27:31,830 --> 00:27:32,100
toch?

533
00:27:32,100 --> 00:27:34,975
En je gaat blijven herhalen
Dit, omdat de lussen gewoon

534
00:27:34,975 --> 00:27:36,010
te blijven draaien, toch?

535
00:27:36,010 --> 00:27:39,190
>> Dus zoals jullie kunnen zien, we
gewoon een algemene pseudocode

536
00:27:39,190 --> 00:27:41,480
van hoe we willen dit programma te kijken.

537
00:27:41,480 --> 00:27:46,646
Dit herhalen hier, wat doen we
meestal nodig om te schrijven in onze code

538
00:27:46,646 --> 00:27:49,270
als we willen doorlopen van een
array, wat voor soort structuur?

539
00:27:49,270 --> 00:27:51,030
Ik denk Christabel
dit al eerder gezegd.

540
00:27:51,030 --> 00:27:51,500
>> PUBLIEK: Een lus.

541
00:27:51,500 --> 00:27:52,160
>> ANDI Peng: een lus?

542
00:27:52,160 --> 00:27:52,770
Precies.

543
00:27:52,770 --> 00:27:56,060
Dus dit is waarschijnlijk
gaan een voor lus.

544
00:27:56,060 --> 00:27:59,240
Wat is een check hier gaan betekenen?

545
00:27:59,240 --> 00:28:02,536
Typisch, als u wilt controleren
als er iets is iets else--

546
00:28:02,536 --> 00:28:03,270
>> Publiek: Als.

547
00:28:03,270 --> 00:28:06,790
>> ANDI Peng: Een als, toch?

548
00:28:06,790 --> 00:28:10,790
En dan de swap Hier zullen we
ga dan later, omdat David

549
00:28:10,790 --> 00:28:12,770
ging door die in collegezaal ook.

550
00:28:12,770 --> 00:28:14,580
En dan de tweede iterate implies--

551
00:28:14,580 --> 00:28:15,120
>> PUBLIEK: Nog een lus.

552
00:28:15,120 --> 00:28:16,745
>> ANDI Peng: --another lus, precies.

553
00:28:16,745 --> 00:28:19,870

554
00:28:19,870 --> 00:28:22,000
Dus als we kijken
Dit kunnen we

555
00:28:22,000 --> 00:28:24,680
kan zien dat we waarschijnlijk
gaan naar een geneste lus nodig

556
00:28:24,680 --> 00:28:28,330
met een voorwaardelijke instructie daar
en dan een echte stukje code dat is

557
00:28:28,330 --> 00:28:31,360
gaat om de waarden te wisselen.

558
00:28:31,360 --> 00:28:35,980
Dus ik heb net over het algemeen geschreven
een pseudocode code hier.

559
00:28:35,980 --> 00:28:38,910
En dan zijn we eigenlijk gaan
fysiek als klasse,

560
00:28:38,910 --> 00:28:40,700
proberen om de uitvoering van deze vandaag.

561
00:28:40,700 --> 00:28:42,486
Laten we terug gaan naar deze IDE.

562
00:28:42,486 --> 00:28:49,243

563
00:28:49,243 --> 00:28:50,230
>> Oh Oh.

564
00:28:50,230 --> 00:28:51,754
Waarom is dat niet-- daar is.

565
00:28:51,754 --> 00:28:52,253
OK.

566
00:28:52,253 --> 00:28:55,834

567
00:28:55,834 --> 00:28:57,500
Sorry, laat me proberen een beetje meer te zoomen.

568
00:28:57,500 --> 00:28:59,310
Daar gaan we.

569
00:28:59,310 --> 00:29:05,060
Alles wat ik hier doe is ik heb gemaakt
een programma genaamd "selectie / sort.c."

570
00:29:05,060 --> 00:29:10,860
Ik heb een serie van negen gecreëerd
waarden, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Op dit moment, als je kunt
zie, zij zijn ongeordende.

572
00:29:14,370 --> 00:29:17,880
n gaat het getal dat
vertelt u het bedrag van de waarden

573
00:29:17,880 --> 00:29:18,920
je hebt in je array.

574
00:29:18,920 --> 00:29:20,670
In dit geval hebben we negen waarden.

575
00:29:20,670 --> 00:29:23,760
En ik heb net een lus hier
dat drukt de ongesorteerde array.

576
00:29:23,760 --> 00:29:28,370
>> En aan het eind, heb ik ook nog een voor
lus die gewoon wordt afgedrukt weer uit.

577
00:29:28,370 --> 00:29:32,070
Dus in theorie, als dit programma
correct werkt, aan het eind,

578
00:29:32,070 --> 00:29:35,670
je moet zien lus een gedrukte
waarin 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 zijn allemaal correct in orde.

580
00:29:39,310 --> 00:29:43,410
>> Dus hebben we onze pseudocode kregen hier.

581
00:29:43,410 --> 00:29:46,090
Wil iemand to-- Ik ben gewoon
ga vragen volunteers--

582
00:29:46,090 --> 00:29:49,540
Vertel me precies wat te typen als
we willen, eerst, enkel herhalen

583
00:29:49,540 --> 00:29:52,840
door middel van het begin van deze serie?

584
00:29:52,840 --> 00:29:55,204
Wat is de lijn van code die ik ben
waarschijnlijk zal hier nodig?

585
00:29:55,204 --> 00:29:56,990
>> PUBLIEK: [onverstaanbaar]

586
00:29:56,990 --> 00:29:59,010
>> ANDI Peng: Ja, voelen
gratis to-- sorry, u

587
00:29:59,010 --> 00:30:02,318
hoeven niet te up-- gevoel staan
vrij om uw stem te verheffen een beetje.

588
00:30:02,318 --> 00:30:08,190
>> Publiek: voor int i gelijk 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI Peng: Ja, goed.

590
00:30:10,690 --> 00:30:15,220
>> Publiek: i minder dan matrix lengte.

591
00:30:15,220 --> 00:30:19,630
>> ANDI Peng: Dus houd in
erg hier, omdat we

592
00:30:19,630 --> 00:30:23,060
geen functie hebben die
vertelt de lengte van een array,

593
00:30:23,060 --> 00:30:25,790
hebben we al een
waarde die opgeslagen.

594
00:30:25,790 --> 00:30:27,920
Rechts?

595
00:30:27,920 --> 00:30:31,010
Een ander ding te houden
in mind-- in een array

596
00:30:31,010 --> 00:30:33,940
van de negen waarden, wat zijn de indexen?

597
00:30:33,940 --> 00:30:38,720
Laten we zeggen dat deze array was 0-3.

598
00:30:38,720 --> 00:30:41,500
Je ziet dat de laatste
index is eigenlijk 3.

599
00:30:41,500 --> 00:30:45,530
Het is niet 4, ook al is er
vier waarden in de matrix.

600
00:30:45,530 --> 00:30:49,866
>> Dus hier, we moeten heel voorzichtig zijn
wat onze voorwaarde voor de lengte

601
00:30:49,866 --> 00:30:50,490
wordt.

602
00:30:50,490 --> 00:30:51,948
>> Publiek: Zou het niet n min 1?

603
00:30:51,948 --> 00:30:54,440
ANDI PENG: Het gaat
n minus 1, precies.

604
00:30:54,440 --> 00:30:57,379
Is dat zinvol is, waarom
het n minus 1, iedereen?

605
00:30:57,379 --> 00:30:58,920
Het is omdat arrays zijn zero-geïndexeerd.

606
00:30:58,920 --> 00:31:02,010
Ze beginnen bij 0 en aanloop naar n min 1.

607
00:31:02,010 --> 00:31:03,210
Ja, het is een beetje lastig.

608
00:31:03,210 --> 00:31:03,730
OK.

609
00:31:03,730 --> 00:31:05,929
En dan--

610
00:31:05,929 --> 00:31:08,054
PUBLIEK: Isnt'1 dat
al voor gezorgd hoewel,

611
00:31:08,054 --> 00:31:11,400
door gewoon niet te zeggen "kleiner dan of
gelijk aan "en gewoon zeggen" minder dan? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI PENG: Dat is een
echt goede vraag.

613
00:31:13,108 --> 00:31:13,630
Ja dus.

614
00:31:13,630 --> 00:31:17,410
Maar ook de manier waarop we
de uitvoering van de controle op juiste,

615
00:31:17,410 --> 00:31:19,120
je nodig hebt om twee waarden te vergelijken.

616
00:31:19,120 --> 00:31:21,009
Zodat je eigenlijk wilt
Laat de "om" leeg.

617
00:31:21,009 --> 00:31:23,050
Want als je het vergelijkt
deze, je bent niet van plan

618
00:31:23,050 --> 00:31:25,530
iets na
te vergelijken met, toch?

619
00:31:25,530 --> 00:31:27,460
Ja.

620
00:31:27,460 --> 00:31:29,297
Dus i ++.

621
00:31:29,297 --> 00:31:30,380
We voegen onze beugels in.

622
00:31:30,380 --> 00:31:30,880
Whoops.

623
00:31:30,880 --> 00:31:33,950

624
00:31:33,950 --> 00:31:34,710
Grote.

625
00:31:34,710 --> 00:31:39,117
Dus we hebben het begin
onze buitenste lus.

626
00:31:39,117 --> 00:31:41,450
Dus nu waarschijnlijk willen we
creëren van een variabele voor het houden

627
00:31:41,450 --> 00:31:43,085
spoor van de kleinste waarde, toch?

628
00:31:43,085 --> 00:31:45,751
Wil iemand mij geven
regel code die dat zou doen?

629
00:31:45,751 --> 00:31:48,700

630
00:31:48,700 --> 00:31:53,570
Wat hebben we nodig als we gaan
te willen om iets op te slaan?

631
00:31:53,570 --> 00:31:55,047
>> Rechts.

632
00:31:55,047 --> 00:31:57,630
Misschien een betere naam voor die
zou be-- "temp" totaal works--

633
00:31:57,630 --> 00:32:00,655
misschien een meer toepasselijke naam zou zijn,
Als we willen dat de kleinste value--

634
00:32:00,655 --> 00:32:01,624
>> Publiek: Min.

635
00:32:01,624 --> 00:32:02,790
ANDI Peng: min, daar gaan we.

636
00:32:02,790 --> 00:32:05,230
min zou goed zijn.

637
00:32:05,230 --> 00:32:08,340
En dus even, wat doen we
wil het initialiseren aan?

638
00:32:08,340 --> 00:32:09,620
Dit is een beetje lastig.

639
00:32:09,620 --> 00:32:13,580
Want nu op de
begin van deze matrix,

640
00:32:13,580 --> 00:32:15,730
je niet hebben gekeken naar iets, toch?

641
00:32:15,730 --> 00:32:19,200
Dus wat, automatisch, als
we zijn gewoon op i gelijk is aan 0,

642
00:32:19,200 --> 00:32:22,302
wat willen we initialiseren
onze eerste minimale waarde?

643
00:32:22,302 --> 00:32:22,802
Publiek: i.

644
00:32:22,802 --> 00:32:24,790
ANDI Peng: Ik, precies.

645
00:32:24,790 --> 00:32:27,040
Christabel, waarom willen we
om het initialiseren te i?

646
00:32:27,040 --> 00:32:28,510
>> Publiek: Omdat, goed,
we beginnen met 0.

647
00:32:28,510 --> 00:32:31,660
Dus omdat we hebben niets te vergelijken
het aan de minimum wordt uiteindelijk op 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI PENG: Precies.

649
00:32:32,451 --> 00:32:34,400
Dus ze is precies goed.

650
00:32:34,400 --> 00:32:36,780
Omdat we eigenlijk niet
keek nog niets,

651
00:32:36,780 --> 00:32:38,680
we weten niet wat onze minimale waarde is.

652
00:32:38,680 --> 00:32:41,960
We willen gewoon initialiseren aan
i, die, op dit moment, is hier.

653
00:32:41,960 --> 00:32:44,750
En als we doorgaan met
deze array naar beneden,

654
00:32:44,750 --> 00:32:48,122
we zullen zien dat, met elkaar
aanvullende pas, ik verhoogt.

655
00:32:48,122 --> 00:32:49,830
En dus op dat punt,
i gaat waarschijnlijk

656
00:32:49,830 --> 00:32:52,329
te willen tot het minimum te zijn,
omdat het gaat om wat dan ook

657
00:32:52,329 --> 00:32:54,520
is het begin van het ongesorteerde array.

658
00:32:54,520 --> 00:32:55,270
Cool.

659
00:32:55,270 --> 00:32:58,720
>> Dus nu willen we voegen
een lus hier dat is

660
00:32:58,720 --> 00:33:03,225
zal doorlopen de
ongesorteerd, of de rest van deze array.

661
00:33:03,225 --> 00:33:05,808
Wil iemand mij een te geven
regel code die dat zou doen?

662
00:33:05,808 --> 00:33:08,870

663
00:33:08,870 --> 00:33:11,330
Hint-- wat hebben we hier nodig beneden?

664
00:33:11,330 --> 00:33:17,320

665
00:33:17,320 --> 00:33:18,820
Wat is er te gaan in deze lus?

666
00:33:18,820 --> 00:33:19,465
Ja.

667
00:33:19,465 --> 00:33:21,590
Publiek: Dus we zouden willen
een andere integer,

668
00:33:21,590 --> 00:33:25,080
want we lopen door de rest
van de matrix in plaats van de i, dus misschien

669
00:33:25,080 --> 00:33:25,760
j.

670
00:33:25,760 --> 00:33:27,301
>> ANDI Peng: Ja, j klinkt goed voor mij.

671
00:33:27,301 --> 00:33:27,850
Evenaart?

672
00:33:27,850 --> 00:33:33,930
>> Publiek: Dus zou ik plus 1, omdat
je begint bij de volgende waarde.

673
00:33:33,930 --> 00:33:40,395
En vervolgens naar de end-- Nogmaals, j
minder dan n minus 1, en dan j ++.

674
00:33:40,395 --> 00:33:41,103
ANDI Peng: Grote.

675
00:33:41,103 --> 00:33:48,510

676
00:33:48,510 --> 00:33:52,750
>> En dan hier, we gaan te willen
om te controleren om te zien of onze voorwaarde is voldaan,

677
00:33:52,750 --> 00:33:53,250
toch?

678
00:33:53,250 --> 00:33:55,740
Omdat je wilt
veranderen de minimale waarde

679
00:33:55,740 --> 00:33:58,700
als het is eigenlijk kleiner dan wat
je bent te vergelijken met, toch?

680
00:33:58,700 --> 00:34:01,146
Dus wat gaan we willen hier?

681
00:34:01,146 --> 00:34:04,160

682
00:34:04,160 --> 00:34:04,897
Controleren om te zien.

683
00:34:04,897 --> 00:34:06,730
Wat voor soort statement
zijn we waarschijnlijk gaan

684
00:34:06,730 --> 00:34:08,389
ti wilt gebruiken als we
iets willen controleren?

685
00:34:08,389 --> 00:34:09,360
>> Publiek: Een if statement.

686
00:34:09,360 --> 00:34:10,485
>> ANDI Peng: Een if statement.

687
00:34:10,485 --> 00:34:13,155
Dus if-- en wat gaat worden
de voorwaarde dat we willen binnen

688
00:34:13,155 --> 00:34:13,988
van onze if?

689
00:34:13,988 --> 00:34:18,255

690
00:34:18,255 --> 00:34:22,960
>> AUDIENCE: Als de waarde van j
kleiner is dan de waarde van I--

691
00:34:22,960 --> 00:34:24,600
>> ANDI PENG: Precies.

692
00:34:24,600 --> 00:34:27,480
Zo if-- zodat deze array wordt "matrix".

693
00:34:27,480 --> 00:34:27,980
Grote.

694
00:34:27,980 --> 00:34:30,465
Dus als array-- wat was dat?

695
00:34:30,465 --> 00:34:31,090
Zeg dat nog eens.

696
00:34:31,090 --> 00:34:39,590
>> Doelgroep: Als serie-j is minder dan
matrix-i, dan zouden we het min veranderen.

697
00:34:39,590 --> 00:34:41,590
Dus de min j zou zijn.

698
00:34:41,590 --> 00:34:44,590

699
00:34:44,590 --> 00:34:47,249
>> ANDI Peng: Is dat logisch?

700
00:34:47,249 --> 00:34:48,670
OK.

701
00:34:48,670 --> 00:34:52,929
En nu hier beneden, we eigenlijk
willen de swap uit te voeren, toch?

702
00:34:52,929 --> 00:34:58,285
Zo herinneren, in collegezaal, dat David, toen
hij probeerde te the-- wat swap

703
00:34:58,285 --> 00:34:59,996
het-- sinaasappelsap en milk--

704
00:34:59,996 --> 00:35:01,150
>> PUBLIEK: Dat was walgelijk.

705
00:35:01,150 --> 00:35:02,816
>> ANDI Peng: Ja, dat was een soort van de bruto.

706
00:35:02,816 --> 00:35:05,310
Maar het was een vrij goede
Het concept demonstreren tijd.

707
00:35:05,310 --> 00:35:08,430
Dus denk aan uw waarden hier.

708
00:35:08,430 --> 00:35:10,794
Je hebt een scala gekregen
van min, een matrix van i,

709
00:35:10,794 --> 00:35:12,460
of wat we probeerden om hier te wisselen.

710
00:35:12,460 --> 00:35:15,310
En u waarschijnlijk kunt ze niet giet het in
elkaar tegelijkertijd, toch?

711
00:35:15,310 --> 00:35:17,180
Dus wat gaan we
nodig hebben om hier te creëren

712
00:35:17,180 --> 00:35:19,126
teneinde de waarden correct ruilen?

713
00:35:19,126 --> 00:35:19,820
>> PUBLIEK: Een tijdelijke variabele.

714
00:35:19,820 --> 00:35:21,370
>> ANDI Peng: een tijdelijke variabele.

715
00:35:21,370 --> 00:35:22,570
Dus laten we het doen int temp.

716
00:35:22,570 --> 00:35:25,681
Zie, zou dit een beter
tijd to-- whoa, wat was dat?

717
00:35:25,681 --> 00:35:26,180
OK.

718
00:35:26,180 --> 00:35:29,800
Dus dit een beter zou zijn geweest
tijd om de variabele "temp." noemen

719
00:35:29,800 --> 00:35:30,730
Dus laten we het doen int temp.

720
00:35:30,730 --> 00:35:32,563
Wat gaan we
set temp gelijk naar hier?

721
00:35:32,563 --> 00:35:34,752

722
00:35:34,752 --> 00:35:35,335
PUBLIEK: Min?

723
00:35:35,335 --> 00:35:38,508

724
00:35:38,508 --> 00:35:39,716
ANDI PENG: Het is een beetje lastig.

725
00:35:39,716 --> 00:35:43,110

726
00:35:43,110 --> 00:35:44,880
Het maakt eigenlijk niet uit in het einde.

727
00:35:44,880 --> 00:35:47,690
Het maakt niet uit wat
Om u ervoor kiest om te wisselen in

728
00:35:47,690 --> 00:35:50,862
zolang je ervoor zorgen dat je bent
het bijhouden van wat je ruilt.

729
00:35:50,862 --> 00:35:52,250
>> Publiek: Het kon serie-i zijn.

730
00:35:52,250 --> 00:35:53,666
>> ANDI Peng: Ja, laten we serie-i.

731
00:35:53,666 --> 00:35:55,950

732
00:35:55,950 --> 00:35:59,305
En wat is dan de volgende regel
van de code die we hier willen hebben?

733
00:35:59,305 --> 00:36:00,680
PUBLIEK: serie-i is gelijk aan serie-j.

734
00:36:00,680 --> 00:36:07,154

735
00:36:07,154 --> 00:36:08,070
ANDI Peng: En tot slot?

736
00:36:08,070 --> 00:36:12,070
PUBLIEK: serie-j is gelijk aan serie-i.

737
00:36:12,070 --> 00:36:14,525
PUBLIEK: Of serie-j gelijken
matrix-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
Dus laten we dit uitvoeren en zien
als het gaat werken.

741
00:36:21,510 --> 00:36:37,520

742
00:36:37,520 --> 00:36:39,335
Waar is dat gebeurt?

743
00:36:39,335 --> 00:36:40,210
Oh, dat is een probleem.

744
00:36:40,210 --> 00:36:44,320
Zie, op lijn 40, we zijn
proberen array-j gebruiken?

745
00:36:44,320 --> 00:36:47,022
Maar waar komt j bestaan ​​alleen in?

746
00:36:47,022 --> 00:36:48,402
>> PUBLIEK: In de lus.

747
00:36:48,402 --> 00:36:49,110
ANDI Peng: Recht.

748
00:36:49,110 --> 00:36:51,730
Dus wat gaan we doen?

749
00:36:51,730 --> 00:36:53,170
>> Publiek: Definieer het buiten the--

750
00:36:53,170 --> 00:36:57,777

751
00:36:57,777 --> 00:37:00,610
Publiek: Ja, ik denk dat je moet
naar een ander te gebruiken als statement, toch?

752
00:37:00,610 --> 00:37:05,230
Dus als, als de minimum--
Oké, laat me denken.

753
00:37:05,230 --> 00:37:08,170

754
00:37:08,170 --> 00:37:09,990
>> ANDI Peng: Jongens, probeer
om een ​​kijkje te laten we

755
00:37:09,990 --> 00:37:11,270
zie, wat is iets wat we kunnen doen hier?

756
00:37:11,270 --> 00:37:11,811
>> Publiek: OK.

757
00:37:11,811 --> 00:37:15,900
Dus als het minimum niet gelijk
j-- dus als het minimum is nog I--

758
00:37:15,900 --> 00:37:17,570
dan zouden we niet hoeven te wisselen.

759
00:37:17,570 --> 00:37:22,450

760
00:37:22,450 --> 00:37:24,712
>> ANDI Peng: Is dat gelijk i?

761
00:37:24,712 --> 00:37:25,920
Wat wil je hier te zeggen?

762
00:37:25,920 --> 00:37:30,494
>> PUBLIEK: Of ja, als de
minimum niet gelijk ik, 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
Nou dat oplost, soort, onze problemen.

766
00:37:42,040 --> 00:37:47,265
Maar dat nog steeds niet het oplossen van de
probleem van wat er gebeurt als j-- sinds j

767
00:37:47,265 --> 00:37:49,890
niet bestaan ​​doet daarbuiten, wat
wil je dat we doen?

768
00:37:49,890 --> 00:37:50,698
Verklaar het buiten?

769
00:37:50,698 --> 00:37:59,410

770
00:37:59,410 --> 00:38:02,730
Laten we proberen het uitvoeren van deze.

771
00:38:02,730 --> 00:38:04,435
Oh Oh.

772
00:38:04,435 --> 00:38:06,200
Onze soort werkt niet.

773
00:38:06,200 --> 00:38:10,060
>> Zoals u, onze eerste kan zien
matrix had die waarden.

774
00:38:10,060 --> 00:38:14,800
En daarna zou moeten hebben
is in 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
Het werkt niet.

776
00:38:15,530 --> 00:38:16,030
Ahh.

777
00:38:16,030 --> 00:38:17,184
Wat doen we?

778
00:38:17,184 --> 00:38:17,850
Publiek: Debug.

779
00:38:17,850 --> 00:38:21,787

780
00:38:21,787 --> 00:38:23,370
ANDI Peng: Oké, kunnen we proberen dat.

781
00:38:23,370 --> 00:38:25,030
We kunnen debuggen.

782
00:38:25,030 --> 00:38:26,042
Uitzoomen een beetje.

783
00:38:26,042 --> 00:38:31,177

784
00:38:31,177 --> 00:38:33,656
Laten we stellen onze breekpunt.

785
00:38:33,656 --> 00:38:37,280
Laten we gaan like-- OK.

786
00:38:37,280 --> 00:38:40,444
>> Omdat we weten al dat
deze lijnen 15 tot 22,

787
00:38:40,444 --> 00:38:43,610
zijn working-- omdat alles wat ik doe is
gewoon itereren door en printing--

788
00:38:43,610 --> 00:38:45,406
Ik kan gaan en overslaan.

789
00:38:45,406 --> 00:38:47,280
Laten we beginnen op lijn 25.

790
00:38:47,280 --> 00:38:48,712
Oop, laat me te ontdoen van.

791
00:38:48,712 --> 00:38:51,598

792
00:38:51,598 --> 00:38:54,057
>> Publiek: Dus het breekpunt's
waar de debuggen begint?

793
00:38:54,057 --> 00:38:54,890
ANDI Peng: of stopt.

794
00:38:54,890 --> 00:38:55,670
Publiek: of stopt.

795
00:38:55,670 --> 00:38:55,930
ANDI PENG: Ja.

796
00:38:55,930 --> 00:38:58,640
U kunt meerdere breakpoints instellen en
kan slechts van de ene naar de andere.

797
00:38:58,640 --> 00:39:01,590
Maar in dit geval weten we niet
waar de fout gebeurt.

798
00:39:01,590 --> 00:39:03,780
Dus we willen gewoon
starten van boven naar beneden.

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
>> Dus deze lijn hier, kunnen we ingrijpen.

802
00:39:08,460 --> 00:39:11,499
U kunt hier naar beneden te zien,
we hebben een array.

803
00:39:11,499 --> 00:39:13,290
Dat zijn de waarden
die in de array.

804
00:39:13,290 --> 00:39:16,360
Zie je dat, hoe index 0, is het
komt overeen met de value-- oh,

805
00:39:16,360 --> 00:39:17,526
Ik ga proberen om in te zoomen.

806
00:39:17,526 --> 00:39:20,650
Sorry, het is echt moeilijk
om see-- bij array-index 0,

807
00:39:20,650 --> 00:39:24,090
We hebben een waarde van 4 en
Vervolgens enzovoort, enzovoort.

808
00:39:24,090 --> 00:39:25,670
We hebben onze lokale variabelen.

809
00:39:25,670 --> 00:39:28,570
Nu i is gelijk aan
0, wat we willen dat het is.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> En zo laten we doorlopen.

812
00:39:33,690 --> 00:39:36,850
De minimum gelijk is aan 0,
die we willen ook dat het is.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
En dan gaan we onze tweede voor
lus, als matrix-j minder dan matrix-i,

815
00:39:45,560 --> 00:39:46,380
waarvan zij niet.

816
00:39:46,380 --> 00:39:48,130
Dus heb je zien hoe
dat overgeslagen dat?

817
00:39:48,130 --> 00:39:52,430
>> Publiek: Dus moet het als
minimum, alle dat-- moet niet dat

818
00:39:52,430 --> 00:39:55,424
zijn in de eerste lus?

819
00:39:55,424 --> 00:39:57,340
ANDI Peng: Nee, want
je nog wilt testen.

820
00:39:57,340 --> 00:40:00,329
U wilt een vergelijking elke doen
tijd, zelfs nadat je door het uit te voeren.

821
00:40:00,329 --> 00:40:02,620
Je hoeft niet alleen willen doen
op de eerste doorvoer.

822
00:40:02,620 --> 00:40:05,240
U wilt doen met
elke extra pas weer.

823
00:40:05,240 --> 00:40:07,198
Dus u wilt controleren
je conditie binnen.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Dus we gaan gewoon
blijven draaien door middel van hier.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Ik geef je jongens een hint.

828
00:40:18,420 --> 00:40:23,910
Het heeft te maken met het feit dat bij
je bent het controleren van uw voorwaardelijk,

829
00:40:23,910 --> 00:40:26,600
je bent niet controleren
de juiste index.

830
00:40:26,600 --> 00:40:32,510
Dus nu je controleren op
scala index van j minder dan scala

831
00:40:32,510 --> 00:40:33,970
index van de i.

832
00:40:33,970 --> 00:40:36,580
Maar wat doe je bij
het begin van de lus?

833
00:40:36,580 --> 00:40:38,260
Bent u niet instellen j gelijk aan i?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Ja, dus we kunnen eigenlijk
verlaat hier de debugger.

836
00:40:45,415 --> 00:40:47,040
Dus laten we eens een kijkje op onze pseudocode.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
Voor-- we gaan
beginnen bij i gelijk is aan 0.

839
00:40:52,580 --> 00:40:54,760
We gaan om te gaan tot n min 1.

840
00:40:54,760 --> 00:40:58,040
Laten we eens kijken, hadden we dat toch?

841
00:40:58,040 --> 00:40:59,580
Yep, dat was juist.

842
00:40:59,580 --> 00:41:02,080
>> Dus dan in hier, we zijn
naar een minimumwaarde creëren

843
00:41:02,080 --> 00:41:03,630
en stel dat gelijk is aan i.

844
00:41:03,630 --> 00:41:04,950
Hebben we dat doen?

845
00:41:04,950 --> 00:41:06,270
Yep, dat deed.

846
00:41:06,270 --> 00:41:10,430
Nu in onze innerlijke lus, we zijn
ga j doen gelijk ik tot n 1 min.

847
00:41:10,430 --> 00:41:11,950
Hebben we dat doen?

848
00:41:11,950 --> 00:41:15,540
Inderdaad, we deden dat.

849
00:41:15,540 --> 00:41:19,922
>> Dus maar wat we hier te vergelijken?

850
00:41:19,922 --> 00:41:20,925
>> PUBLIEK: j plus 1.

851
00:41:20,925 --> 00:41:21,716
ANDI PENG: Precies.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
En dan zul je wilt instellen
uw minimale gelijk aan j plus 1 ook.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Dus ik ging door dat heel snel.

856
00:41:32,640 --> 00:41:36,190
Doen jullie begrijpen
waarom het j plus 1?

857
00:41:36,190 --> 00:41:36,890
OK.

858
00:41:36,890 --> 00:41:40,700
>> Dus in Matrix
uw eerste passage door,

859
00:41:40,700 --> 00:41:44,850
uw lus, voor int
i gelijk is aan 0, laten we gewoon

860
00:41:44,850 --> 00:41:46,740
neem aan dat dit is nog niet veranderd.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
We hebben een scala van volledig,
slechts vier ongesorteerde elementen, toch?

863
00:41:56,760 --> 00:42:00,760
Dus we willen initialiseren i gelijk is aan 0.

864
00:42:00,760 --> 00:42:03,650
En ik zal net
lopen door deze lus.

865
00:42:03,650 --> 00:42:08,560
En zo in de eerste pas, we gaan
een variabele genaamd "min" initialiseren

866
00:42:08,560 --> 00:42:11,245
die ook gelijk is aan i, omdat
we hebben niet een minimale waarde.

867
00:42:11,245 --> 00:42:12,870
Dus dat is momenteel gelijk aan 0 als goed.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
En dan gaan we door te gaan.

870
00:42:17,640 --> 00:42:19,270
En we willen weer herhalen.

871
00:42:19,270 --> 00:42:22,900
Nu dat we hebben gevonden wat onze minimale
is, willen we door middel van herhalen

872
00:42:22,900 --> 00:42:25,190
opnieuw om te zien of het is te vergelijken, toch?

873
00:42:25,190 --> 00:42:40,440
Dus j, hier gaat
gelijke i, die 0.

874
00:42:40,440 --> 00:42:46,320
En dan als serie j plus i, die
is degene die het volgende over, als minder

875
00:42:46,320 --> 00:42:49,270
dan wat uw huidige minimum
waarde is, je wilt ruilen.

876
00:42:49,270 --> 00:42:56,850
>> Dus laten we gewoon zeggen dat we hebben
gekregen, zoals, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Nu, i is gelijk aan
0 en j gelijk is aan 0.

878
00:43:01,610 --> 00:43:05,210
En dat is onze minimale waarde.

879
00:43:05,210 --> 00:43:09,950
Als serie-J plus Ik-- dus als degene
dat is na de ene we kijken naar

880
00:43:09,950 --> 00:43:13,450
groter is dan de vorige is,
het gaat om het minimum te worden.

881
00:43:13,450 --> 00:43:18,120
>> Dus hier zien we dat 5
niet minder dan dat.

882
00:43:18,120 --> 00:43:19,730
Dus het gaat niet 5.

883
00:43:19,730 --> 00:43:23,580
We zien dat 1 minder dan 2, toch?

884
00:43:23,580 --> 00:43:32,970
Dus nu weten we dat onze minimum
naar de indexwaarde worden op 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Ja?

886
00:43:34,030 --> 00:43:39,170
En dan als je hier beneden,
U kunt wisselen de juiste waarden.

887
00:43:39,170 --> 00:43:42,610
>> Dus als je jongens gewoon hadden de j
eerder, was je niet kijken naar de ene

888
00:43:42,610 --> 00:43:43,260
na.

889
00:43:43,260 --> 00:43:44,520
Je was op zoek naar
dezelfde waarde,

890
00:43:44,520 --> 00:43:46,290
is de reden waarom het was gewoon niet iets te doen.

891
00:43:46,290 --> 00:43:49,721
Heeft dat zin om iedereen,
waarom we dat plus 1 is er nodig?

892
00:43:49,721 --> 00:43:50,220
OK.

893
00:43:50,220 --> 00:43:53,345
Laten we nu gewoon lopen door het te laten
of de rest van de code correct is.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Waarom is dat gebeurd?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, het is de min hier.

898
00:44:16,364 --> 00:44:17,780
We waren de verkeerde waarde te vergelijken.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
O nee.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Oh ja, hier beneden waren we
omwisselen van de verkeerde waarden ook.

903
00:44:33,482 --> 00:44:34,940
Want we waren op zoek naar i en j.

904
00:44:34,940 --> 00:44:36,440
Dat zijn degenen die we het controleren waren.

905
00:44:36,440 --> 00:44:39,160
We eigenlijk willen de swap
minimum, de huidige minimum,

906
00:44:39,160 --> 00:44:40,550
met wat degene buitenkant is.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
En zoals jullie kunnen zien neer
Hier hebben we een gesorteerde array.

909
00:45:05,402 --> 00:45:07,110
Het had gewoon te maken met
dat bij

910
00:45:07,110 --> 00:45:09,350
we waren het de
waarden waren we vergelijken,

911
00:45:09,350 --> 00:45:11,226
we waren niet op zoek naar de juiste waarden.

912
00:45:11,226 --> 00:45:13,850
We waren op zoek naar het zelfde
hier, eigenlijk niet te verwisselen.

913
00:45:13,850 --> 00:45:17,135
Je moet kijken naar de ene naast
aan het en dan kan je wisselen.

914
00:45:17,135 --> 00:45:19,260
Dus dat is wat voor soort
afluisteren onze code voor.

915
00:45:19,260 --> 00:45:22,460
En wat ik deed hier is alles
de debugger had kunnen doen voor u

916
00:45:22,460 --> 00:45:23,810
Ik deed het alleen op de
boord, want het is makkelijker

917
00:45:23,810 --> 00:45:26,320
eerder te zien dan te proberen
om in te zoomen op de debugger.

918
00:45:26,320 --> 00:45:29,391
Heeft dat zin om iedereen?

919
00:45:29,391 --> 00:45:29,890
Cool.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Prima.

922
00:45:35,410 --> 00:45:41,070
We kunnen overgaan tot het over
asymptotische notatie, waarbij

923
00:45:41,070 --> 00:45:44,580
is gewoon een mooie manier om te zeggen de
runtimes al deze soorten.

924
00:45:44,580 --> 00:45:47,650
Dus ik weet dat David, in collegezaal,
aangeroerd runtimes.

925
00:45:47,650 --> 00:45:52,124
En hij ging door de hele formule
hoe de runtimes berekenen.

926
00:45:52,124 --> 00:45:53,040
Geen zorgen over dat.

927
00:45:53,040 --> 00:45:54,660
Als je echt nieuwsgierig
over hoe dat werkt,

928
00:45:54,660 --> 00:45:55,810
voel je vrij om me te praten na sectie.

929
00:45:55,810 --> 00:45:57,560
We kunnen wandelen door
de formules elkaar.

930
00:45:57,560 --> 00:46:00,689
Maar alles wat je jongens hebben echt
weten is dat n kwadraat meer dan 2

931
00:46:00,689 --> 00:46:01,980
is hetzelfde als n kwadraat.

932
00:46:01,980 --> 00:46:04,710
Omdat de meeste,
de exponent, groeit de.

933
00:46:04,710 --> 00:46:06,590
En dus voor onze doeleinden,
alles wat we zorg over

934
00:46:06,590 --> 00:46:09,470
is dat gigantische nummer dat groeit.

935
00:46:09,470 --> 00:46:13,340
>> Dus wat is het beste geval
runtime van selectie sorteren?

936
00:46:13,340 --> 00:46:15,830
Als je gaat te hebben
te herhalen door een lijst

937
00:46:15,830 --> 00:46:18,712
en dan doorloopt
de rest van die lijst,

938
00:46:18,712 --> 00:46:20,420
hoe vaak zijn
ga je waarschijnlijk,

939
00:46:20,420 --> 00:46:24,612
in het ergste case-- in de
beste geval sorry-- doorlopen?

940
00:46:24,612 --> 00:46:27,070
Misschien is de betere vraag is
om te vragen, wat is het ergste geval

941
00:46:27,070 --> 00:46:28,153
runtime van de selectie sorteren.

942
00:46:28,153 --> 00:46:29,366
Publiek: n kwadraat.

943
00:46:29,366 --> 00:46:30,740
ANDI PENG: Het is n kwadraat, rechts.

944
00:46:30,740 --> 00:46:36,986
Dus een eenvoudige manier te denken van dit is als,
elke keer als je twee geneste lussen te hebben,

945
00:46:36,986 --> 00:46:38,110
het gaat om n worden kwadraat.

946
00:46:38,110 --> 00:46:40,386
Want niet alleen bent u
loopt door nogmaals,

947
00:46:40,386 --> 00:46:42,260
je hebt om terug te gaan
rond en lopen er doorheen

948
00:46:42,260 --> 00:46:44,980
nogmaals binnen voor elke waarde.

949
00:46:44,980 --> 00:46:48,640
Dus in dat geval, je loopt n
tijden n kwadraat, die droevig is--,

950
00:46:48,640 --> 00:46:50,505
n keer n, die gelijk aan n kwadraat.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> En sorteren is ook een beetje
uniek in de zin

953
00:46:56,360 --> 00:46:59,774
dat het niet uitmaakt of deze
waarden zijn reeds ter.

954
00:46:59,774 --> 00:47:01,440
Het is nog steeds te lopen door anyways.

955
00:47:01,440 --> 00:47:03,872
Laten we zeggen dat dit was 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Ongeacht of het in
orde, zou het nog liep door

957
00:47:07,080 --> 00:47:08,620
en nog steeds controleerde de minimale waarde.

958
00:47:08,620 --> 00:47:10,100
Het zou hebben gemaakt van de
hetzelfde aantal controles

959
00:47:10,100 --> 00:47:12,780
elke keer, zelfs als het
niet daadwerkelijk iets aan te raken.

960
00:47:12,780 --> 00:47:16,940
>> Dus in zo'n geval de beste en slechtste
runtimes zijn eigenlijk gelijk.

961
00:47:16,940 --> 00:47:19,160
Zodat de verwachte runtime
van de selectie sorteren,

962
00:47:19,160 --> 00:47:23,790
die we aanduiden met het symbool
van theta, theta, in casu

963
00:47:23,790 --> 00:47:24,790
zou ook n te rijmen.

964
00:47:24,790 --> 00:47:26,480
Alle drie van deze zou worden n kwadraat.

965
00:47:26,480 --> 00:47:29,653
Is iedereen duidelijk waarom
de runtime is n kwadraat?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Prima.

968
00:47:33,980 --> 00:47:39,120
Dus ik ga gewoon om snel te draaien
de rest van de soort.

969
00:47:39,120 --> 00:47:41,137
Het algoritme voor
bubble sort-- herinneren,

970
00:47:41,137 --> 00:47:43,220
Dit was de eerste
David ging in collegezaal.

971
00:47:43,220 --> 00:47:46,000
In wezen, je stap
door de hele lijst

972
00:47:46,000 --> 00:47:48,950
en je je gewoon swap--
vergelijken twee tegelijk.

973
00:47:48,950 --> 00:47:51,350
En als men is groter,
dan je gewoon ruilen hen.

974
00:47:51,350 --> 00:47:53,590
Dus als deze groter zijn, zou je ruilen.

975
00:47:53,590 --> 00:47:56,180
Ik heb officiële kreeg hier.

976
00:47:56,180 --> 00:47:59,100
>> Dus laten we gewoon zeggen dat je had 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Je zou vergelijken met de 8 en een 6.

978
00:48:00,571 --> 00:48:01,570
Je nodig hebt om ze te ruilen.

979
00:48:01,570 --> 00:48:02,610
Je zou de 8 en een 4 te vergelijken.

980
00:48:02,610 --> 00:48:03,609
Je nodig hebt om ze te ruilen.

981
00:48:03,609 --> 00:48:07,000
Als je moet wisselen van de 8 en
de 2, veranderen ze ook.

982
00:48:07,000 --> 00:48:10,760
Dus in zo'n gevoel, kunt u zien,
gespeeld over een lange periode van tijd,

983
00:48:10,760 --> 00:48:13,730
hoe de waarden soort zeepbel
de uiteinden, dat is waarom we noemen het

984
00:48:13,730 --> 00:48:15,320
bubble sort.

985
00:48:15,320 --> 00:48:19,950
>> We zouden alleen lopen door weer
onze tweede pas, en onze derde pas,

986
00:48:19,950 --> 00:48:21,150
en onze vierde pass.

987
00:48:21,150 --> 00:48:25,820
In wezen, bubble sort gewoon loopt
totdat je niet meer swaps te maken.

988
00:48:25,820 --> 00:48:31,109
Dus in die zin, dit is gewoon
de algemene pseudocode voor.

989
00:48:31,109 --> 00:48:32,650
Geen zorgen, deze zullen alle online zijn.

990
00:48:32,650 --> 00:48:34,990
We hoeven niet te eigenlijk gaan over dit.

991
00:48:34,990 --> 00:48:38,134
>> We initialiseren gewoon een teller
variabele die begint bij 0.

992
00:48:38,134 --> 00:48:39,800
En wij herhalen door de gehele array.

993
00:48:39,800 --> 00:48:43,420
Als één waarde is-- indien
waarde groter is dan die waarde,

994
00:48:43,420 --> 00:48:44,610
je gaat om ze te ruilen.

995
00:48:44,610 --> 00:48:46,860
En dan ben je gewoon
gaat om door te gaan.

996
00:48:46,860 --> 00:48:47,970
En je gaat tellen.

997
00:48:47,970 --> 00:48:50,845
En je bent gewoon te blijven doen
dit terwijl de teller groter

998
00:48:50,845 --> 00:48:53,345
dan 0, waardoor
elke keer dat je hoeft te wisselen,

999
00:48:53,345 --> 00:48:55,220
je weet dat je wilt gaan
terug en controleer opnieuw.

1000
00:48:55,220 --> 00:48:59,510
U wilt controle houden totdat je weet
dat je niet meer hoeft te wisselen.

1001
00:48:59,510 --> 00:49:05,570
>> Dus wat zijn de beste en slechtste
case runtimes voor bubble sort?

1002
00:49:05,570 --> 00:49:09,300
En dit is eigenlijk anders hint--
van de selectie sorteren in de zin

1003
00:49:09,300 --> 00:49:11,810
dat deze twee antwoorden zijn niet hetzelfde.

1004
00:49:11,810 --> 00:49:14,709
Denk na over wat er zou gebeuren in
een geval als het was al opgelost.

1005
00:49:14,709 --> 00:49:16,500
En na te denken over wat
zou er gebeuren als het was

1006
00:49:16,500 --> 00:49:18,372
in het geval waarin het werd niet gesorteerd.

1007
00:49:18,372 --> 00:49:20,580
En je kunt soort lopen
door middel van de reden waarom dat gebeurt.

1008
00:49:20,580 --> 00:49:22,954
Ik geef je jongens, als, 30
seconden over nadenken.

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
Heeft iemand een gok naar wat de
ergste geval looptijd van bubble sort is?

1012
00:49:57,462 --> 00:49:57,962
Ja.

1013
00:49:57,962 --> 00:50:07,810
>> Publiek: zou het zijn, als, n keer
n minus 1 of iets dergelijks?

1014
00:50:07,810 --> 00:50:10,650
Zoals, elke keer dat het draait,
het is gewoon, zoals, een swap minder

1015
00:50:10,650 --> 00:50:10,960
dat wat het ook was.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI Peng: Ja, dus
je helemaal gelijk.

1017
00:50:12,668 --> 00:50:15,940
En dit is een geval waarin uw
antwoord was eigenlijk meer complexe

1018
00:50:15,940 --> 00:50:17,240
dan degene die we nodig hebben om te geven.

1019
00:50:17,240 --> 00:50:19,772
Dus het gaat om run-- ik ben
ga dit hier allemaal te wissen.

1020
00:50:19,772 --> 00:50:20,480
Is iedereen goed?

1021
00:50:20,480 --> 00:50:21,869
Kan ik dit verwijderen?

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
Je gaat lopen door n
keer de eerste keer, toch?

1025
00:50:30,320 --> 00:50:33,200
En ze gaan lopen door
n minus 1 de tweede keer, toch?

1026
00:50:33,200 --> 00:50:37,130
En dan zul je te houden
gaan, n mijne 2, et cetera.

1027
00:50:37,130 --> 00:50:40,210
David deed dit in een lezing, waarbij,
als je opgeteld al die waarden,

1028
00:50:40,210 --> 00:50:48,080
je iets dat is te krijgen like-- yeah--
dan 2, dat in wezen alleen vermindert

1029
00:50:48,080 --> 00:50:49,784
tot aan n kwadraat.

1030
00:50:49,784 --> 00:50:51,700
Je gaat naar een krijgen
raar fractie daar.

1031
00:50:51,700 --> 00:50:53,892
En dus weet alleen dat
n het kwadraat altijd

1032
00:50:53,892 --> 00:50:55,350
heeft voorrang boven de fractie.

1033
00:50:55,350 --> 00:50:58,450
Dus in dit geval, de slechtste
runtime zou n worden kwadraat.

1034
00:50:58,450 --> 00:51:00,210
Als het in afnemende
orde, denk, u

1035
00:51:00,210 --> 00:51:02,530
moet je een swap elke keer te maken.

1036
00:51:02,530 --> 00:51:05,170
>> Wat zou zijn, mogelijk,
het beste geval runtime?

1037
00:51:05,170 --> 00:51:08,580
Laten we maar zeggen, als de lijst was al
in orde, wat zou de runtime zijn?

1038
00:51:08,580 --> 00:51:09,565
>> Publiek: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI PENG: Het is n, precies.

1040
00:51:10,690 --> 00:51:11,600
En waarom is het n?

1041
00:51:11,600 --> 00:51:13,850
Publiek: Omdat je gewoon
hebben om te controleren op elke keer.

1042
00:51:13,850 --> 00:51:14,770
ANDI PENG: Precies.

1043
00:51:14,770 --> 00:51:17,150
Dus in de best mogelijke runtime,
Als deze lijst was al

1044
00:51:17,150 --> 00:51:20,270
sorted-- laten we zeggen 1, 2, 3, 4-- u
zou gewoon door te gaan, zou u controleren,

1045
00:51:20,270 --> 00:51:21,720
je zou zien, oh, ze allemaal de pan uit.

1046
00:51:21,720 --> 00:51:22,636
Ik hoefde niet te verwisselen.

1047
00:51:22,636 --> 00:51:23,370
Ik ben klaar.

1048
00:51:23,370 --> 00:51:26,500
Dus in dat geval, het is gewoon n
of het aantal stappen dat je gewoon

1049
00:51:26,500 --> 00:51:29,870
hadden in de eerste lijst controleren.

1050
00:51:29,870 --> 00:51:33,990
>> En na, hebben we nu hit
insertion sort, waarbij

1051
00:51:33,990 --> 00:51:39,260
het algoritme is in essentie te verdelen
het in een gesorteerde en ongesorteerde deel.

1052
00:51:39,260 --> 00:51:42,810
En vervolgens een voor een,
de gesorteerde waarden

1053
00:51:42,810 --> 00:51:46,880
ingevoegd in de juiste
posities in het begin van de lijst.

1054
00:51:46,880 --> 00:51:52,120
>> Dus bijvoorbeeld, hebben we een
lijst 3, 5, 2, 6, 4 weer.

1055
00:51:52,120 --> 00:51:54,750
We weten dat het momenteel
ongesorteerde want we hebben net

1056
00:51:54,750 --> 00:51:57,030
begon te kijken naar het.

1057
00:51:57,030 --> 00:52:00,610
We nemen een kijkje en we weten dat
de eerste waarde wordt gesorteerd, toch?

1058
00:52:00,610 --> 00:52:04,190
Als je alleen kijkt naar een reeks van
grootte een, weet je dat het is opgelost.

1059
00:52:04,190 --> 00:52:08,230
>> Dus dan weten we dat de
andere vier zijn ongesorteerd.

1060
00:52:08,230 --> 00:52:10,980
We gaan door en zien we die waarde.

1061
00:52:10,980 --> 00:52:11,730
Laten we terug gaan.

1062
00:52:11,730 --> 00:52:13,130
Zie je die waarde van 5?

1063
00:52:13,130 --> 00:52:14,110
We nemen een kijkje bij het.

1064
00:52:14,110 --> 00:52:15,204
We vergelijken met 3.

1065
00:52:15,204 --> 00:52:17,870
We weten dat het groter is dan
3, dus we weten dat dat is opgelost.

1066
00:52:17,870 --> 00:52:22,940
We weten nu dat de eerste twee
worden gesorteerd en de laatste drie zijn niet.

1067
00:52:22,940 --> 00:52:24,270
>> We nemen een kijkje op 2.

1068
00:52:24,270 --> 00:52:25,720
We controleren eerst met 5.

1069
00:52:25,720 --> 00:52:26,700
Is het minder dan 5?

1070
00:52:26,700 --> 00:52:27,240
Het is niet.

1071
00:52:27,240 --> 00:52:29,510
Dus moeten we blijven zoeken naar beneden.

1072
00:52:29,510 --> 00:52:30,940
Dan kijk je 2 uit 3.

1073
00:52:30,940 --> 00:52:31,850
Is het minder dan?

1074
00:52:31,850 --> 00:52:32,350
Nee.

1075
00:52:32,350 --> 00:52:35,430
Dus je weet dat een 2 moet worden gestoken
in de voorste en 3 en 5

1076
00:52:35,430 --> 00:52:38,200
beide moeten worden geduwd.

1077
00:52:38,200 --> 00:52:42,190
Doe dit opnieuw met 6 en 4.

1078
00:52:42,190 --> 00:52:48,962
En we blijven controleren wezen,
waar we maar eens kijken, check, check.

1079
00:52:48,962 --> 00:52:51,170
En totdat het in de juiste
positie, we soort van slechts

1080
00:52:51,170 --> 00:52:54,890
plaatst u deze in de juiste positie,
dat is waar de naam van het vandaan kwam.

1081
00:52:54,890 --> 00:52:59,830
>> Dus dat is gewoon het algoritme,
pseudocode per se, een soort van,

1082
00:52:59,830 --> 00:53:04,990
over hoe we zouden implementeren
een insertie soort.

1083
00:53:04,990 --> 00:53:05,954
Pseudocode is hier.

1084
00:53:05,954 --> 00:53:06,620
Het is allemaal online.

1085
00:53:06,620 --> 00:53:10,720
Geen zorgen als jullie zijn
proberen om dit te kopiëren naar beneden.

1086
00:53:10,720 --> 00:53:14,500
Dus nogmaals, wat hetzelfde question--
zou de beste en slechtste runtimes worden

1087
00:53:14,500 --> 00:53:16,120
voor het inbrengen soort?

1088
00:53:16,120 --> 00:53:17,750
Het is zeer vergelijkbaar met de laatste vraag.

1089
00:53:17,750 --> 00:53:20,479
Ik geef je jongens, als, 30
seconden na te denken over dit zo goed.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK Heeft iemand willen
geef mij het ergste runtime?

1092
00:53:50,071 --> 00:53:50,570
Ja.

1093
00:53:50,570 --> 00:53:51,490
>> Publiek: n kwadraat.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI Peng: Het is n kwadraat.

1095
00:53:52,573 --> 00:53:53,730
En waarom is het n kwadraat?

1096
00:53:53,730 --> 00:53:57,562
>> Publiek: Omdat in
omgekeerde volgorde, je hebt

1097
00:53:57,562 --> 00:54:02,619
om te gaan door n keer n, dat is--

1098
00:54:02,619 --> 00:54:03,660
ANDI Peng: Ja, precies.

1099
00:54:03,660 --> 00:54:06,610
Dus hetzelfde als in de bubble sort.

1100
00:54:06,610 --> 00:54:08,720
Als deze lijst is in
aflopende volgorde, je bent

1101
00:54:08,720 --> 00:54:11,240
gaat te hebben om de eerste keer te controleren.

1102
00:54:11,240 --> 00:54:13,470
En vervolgens bij elke
toegevoegde waarde, je bent

1103
00:54:13,470 --> 00:54:16,390
gaat te hebben om het te controleren tegen
elke waarde, toch?

1104
00:54:16,390 --> 00:54:20,290
En zo totaal, je gaat maken
een n pas keer een ander n pas, die

1105
00:54:20,290 --> 00:54:21,750
is n kwadraat.

1106
00:54:21,750 --> 00:54:22,860
Hoe zit het met het beste geval?

1107
00:54:22,860 --> 00:54:24,360
Ja.

1108
00:54:24,360 --> 00:54:28,840
>> PUBLIEK: n minus 1, omdat de
eerste reeds kwadraat.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI Peng: Dus, in de buurt.

1110
00:54:30,270 --> 00:54:31,850
Het antwoord is eigenlijk n.

1111
00:54:31,850 --> 00:54:37,189
Want terwijl de eerste is
gesorteerd, kan zij niet actually--

1112
00:54:37,189 --> 00:54:38,980
we hadden geluk, in
dat bijvoorbeeld dat 2

1113
00:54:38,980 --> 00:54:40,930
is er gebeurd met het kleinste getal.

1114
00:54:40,930 --> 00:54:43,680
Maar dat niet altijd het geval zal zijn.

1115
00:54:43,680 --> 00:54:48,040
Als 2 al naargelang het begin
maar je kijkt en er is een 1 hier,

1116
00:54:48,040 --> 00:54:49,144
de 1 gaat om het lijf.

1117
00:54:49,144 --> 00:54:51,060
En het zal eindigen
omhoog wordt gestoten anyways.

1118
00:54:51,060 --> 00:54:56,250
>> Dus in het beste geval,
het is eigenlijk gewoon te n zijn.

1119
00:54:56,250 --> 00:54:59,090
Als je 1, 2, 3,
4, 5, 6, 7, 8, je bent

1120
00:54:59,090 --> 00:55:00,940
gaan lopen door
dat hele lijst ooit

1121
00:55:00,940 --> 00:55:03,430
om te controleren om te zien of alles goed is.

1122
00:55:03,430 --> 00:55:07,390
Is iedereen duidelijk running
tijden van de selectie ook?

1123
00:55:07,390 --> 00:55:09,960
Ik weet dat ik ga door
deze echt snel.

1124
00:55:09,960 --> 00:55:13,330
Maar weet gewoon dat als je weet dat de
algemene begrippen, moet je goed zijn.

1125
00:55:13,330 --> 00:55:16,070
OK.

1126
00:55:16,070 --> 00:55:19,790
Dus ik geef jullie misschien, als,
een minuut om je buren te praten

1127
00:55:19,790 --> 00:55:21,890
op wat er net zijn enkele
van de belangrijkste verschillen

1128
00:55:21,890 --> 00:55:23,540
tussen deze soorten van soorten.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
We zullen dan gaan dat binnenkort.

1131
00:56:25,570 --> 00:56:26,444
PUBLIEK: Oh, 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, laten we opnieuw bijeen als een klasse.

1135
00:56:33,420 --> 00:56:34,330
OK.

1136
00:56:34,330 --> 00:56:37,579
Dus dit was een soort van een
open vraag in die zin

1137
00:56:37,579 --> 00:56:39,120
dat er veel antwoorden op hen.

1138
00:56:39,120 --> 00:56:40,746
En we zullen meer dan in het kort te gaan een aantal van hen.

1139
00:56:40,746 --> 00:56:43,411
Ik wilde alleen maar om jullie te krijgen
denken over wat gedifferentieerd

1140
00:56:43,411 --> 00:56:44,530
alle drie de soorten.

1141
00:56:44,530 --> 00:56:47,440
En ik hoorde, ook een grote
question-- wat doet samenvoegen soort doen?

1142
00:56:47,440 --> 00:56:50,110
Grote vraag, want dat is
wat we met betrekking tot de volgende.

1143
00:56:50,110 --> 00:56:52,850
>> Dus samenvoegen sorteren is de
een soort die functies

1144
00:56:52,850 --> 00:56:56,100
zeer verschillend van de andere soorten.

1145
00:56:56,100 --> 00:56:58,180
Zoals jullie kunnen see--
David deed dat doen demo

1146
00:56:58,180 --> 00:57:01,130
waar hij had al de koele
geluiden te zien hoe samenvoegen

1147
00:57:01,130 --> 00:57:04,010
soort liep, als, oneindig
sneller dan de andere twee typen?

1148
00:57:04,010 --> 00:57:04,510
OK.

1149
00:57:04,510 --> 00:57:07,580
Dus dat is omdat samenvoegen
soort implementeert die kloof

1150
00:57:07,580 --> 00:57:11,020
en heers concept dat we hebben
sprak over een veel in collegezaal.

1151
00:57:11,020 --> 00:57:14,550
In die zin dat we graag werken
slimmer, niet harder, als je verdelen

1152
00:57:14,550 --> 00:57:18,120
en heers problemen, en breken ze
naar beneden, en dan zet ze samen,

1153
00:57:18,120 --> 00:57:19,930
goede dingen altijd gebeuren.

1154
00:57:19,930 --> 00:57:21,960
>> Dus de manier waarop die fuseren
werkt soort wezen

1155
00:57:21,960 --> 00:57:24,660
dat het verdeelt een
ongesorteerde array in de helft.

1156
00:57:24,660 --> 00:57:26,500
En dan het heeft twee helften van arrays.

1157
00:57:26,500 --> 00:57:28,220
En het gewoon sorteert die twee helften.

1158
00:57:28,220 --> 00:57:31,750
Het houdt gewoon te verdelen in de helft, in
de helft, in de helft tot alles is gesorteerd

1159
00:57:31,750 --> 00:57:33,680
en vervolgens recursief
zet het allemaal samen.

1160
00:57:33,680 --> 00:57:36,550
>> Dus dat is heel abstract.

1161
00:57:36,550 --> 00:57:38,750
Dus dit is gewoon een beetje pseudocode.

1162
00:57:38,750 --> 00:57:41,040
Heeft dat zin in
de manier waarop het draait?

1163
00:57:41,040 --> 00:57:43,870
Dus laten we gewoon zeggen dat je een
matrix van n elementen, toch?

1164
00:57:43,870 --> 00:57:45,450
Als n minder dan 2, kunt u terugkeren.

1165
00:57:45,450 --> 00:57:49,040
Omdat je weet dat als er
maar één ding moet worden opgelost.

1166
00:57:49,040 --> 00:57:52,600
Anders, je de linker helft te sorteren,
en dan heb je de juiste helft te sorteren,

1167
00:57:52,600 --> 00:57:54,140
en dan samen te voegen.

1168
00:57:54,140 --> 00:57:56,979
>> Dus terwijl dat ziet er echt gemakkelijk,
in werkelijkheid, het denken over het

1169
00:57:56,979 --> 00:58:00,270
soort moeilijk. Omdat je net als,
Nou, dat is soort die op zichzelf.

1170
00:58:00,270 --> 00:58:00,769
Rechts?

1171
00:58:00,769 --> 00:58:02,430
Het draait zichzelf.

1172
00:58:02,430 --> 00:58:05,479
Dus in die zin, David geraakt
op recursie in de klas.

1173
00:58:05,479 --> 00:58:07,270
En dat is een concept
we praten over meer.

1174
00:58:07,270 --> 00:58:11,430
Het is dat deze twee lijnen
hier is eigenlijk gewoon het programma

1175
00:58:11,430 --> 00:58:13,860
vertel het aan zichzelf te voeren
met verschillende input.

1176
00:58:13,860 --> 00:58:17,230
Dus in plaats van zelf lopen met
het geheel van n elementen,

1177
00:58:17,230 --> 00:58:20,530
je kunt breken in de
linkerhelft en de rechterhelft

1178
00:58:20,530 --> 00:58:22,680
en weer voer het dan.

1179
00:58:22,680 --> 00:58:26,050
>> En dan zullen we kijken naar het visueel,
want ik ben een visuele leerling.

1180
00:58:26,050 --> 00:58:27,270
Het werkt beter voor mij.

1181
00:58:27,270 --> 00:58:29,890
Dus we zullen kijken naar een visueel voorbeeld hier.

1182
00:58:29,890 --> 00:58:36,237
>> Laten we zeggen dat we een array, zes
elementen, 3, 5, 2, 6, 4, 1, niet gesorteerd.

1183
00:58:36,237 --> 00:58:37,820
Oké, er is een heleboel op deze pagina.

1184
00:58:37,820 --> 00:58:43,179
Dus als jullie kunt kijken naar de
eerste stap hier, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
je kunt het in tweeën.

1186
00:58:44,220 --> 00:58:45,976
Je hebt 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
U weet dat deze aren't-- u
weet niet of ze naargelang of niet,

1188
00:58:48,850 --> 00:58:52,517
dus je blijft breken ze naar beneden, in de helft,
in de helft, in half, totdat uiteindelijk,

1189
00:58:52,517 --> 00:58:53,600
u slechts één element.

1190
00:58:53,600 --> 00:58:56,790
En één element wordt altijd gesorteerd zijn, toch?

1191
00:58:56,790 --> 00:59:01,560
>> We weten dat 3, 5, 2, 4, 6,
1, op zichzelf, worden gesorteerd.

1192
00:59:01,560 --> 00:59:05,870
En nu kunnen we ze samen terug.

1193
00:59:05,870 --> 00:59:07,510
Zodat we weten dat de 3, 5.

1194
00:59:07,510 --> 00:59:08,510
We zetten die samen.

1195
00:59:08,510 --> 00:59:09,617
We weten dat is gesorteerd.

1196
00:59:09,617 --> 00:59:10,450
De 2 is er nog steeds.

1197
00:59:10,450 --> 00:59:11,830
We kunnen de 4 en de 6 in elkaar gezet.

1198
00:59:11,830 --> 00:59:13,996
We weten dat dat is gesorteerd
zodat we dat samen.

1199
00:59:13,996 --> 00:59:14,940
En 1 er.

1200
00:59:14,940 --> 00:59:18,720
>> En dan moet je gewoon kijkt naar
deze twee helften hier.

1201
00:59:18,720 --> 00:59:21,300
U heeft de 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Je kunt gewoon vergelijken met de
begin van alles.

1203
00:59:23,465 --> 00:59:26,340
Omdat je weet dat dit wordt gesorteerd
en je weet dat dat is opgelost.

1204
00:59:26,340 --> 00:59:29,360
Dus dan hoef je niet eens hoeft te
vergelijk 5, je gewoon vergelijken met de 3.

1205
00:59:29,360 --> 00:59:32,070
En 2 kleiner is dan 3, zodat
weet je 2 moet gaan in het einde.

1206
00:59:32,070 --> 00:59:33,120
>> Hetzelfde daar.

1207
00:59:33,120 --> 00:59:34,740
De 1 moet hier gaan.

1208
00:59:34,740 --> 00:59:37,330
En dan als je gaat zetten
deze twee waarden elkaar,

1209
00:59:37,330 --> 00:59:39,950
je weet dat dit wordt gesorteerd en
je weet dat die wordt gesorteerd.

1210
00:59:39,950 --> 00:59:43,240
Dus dan de 1 en de
2, het 1 minder is dan 2.

1211
00:59:43,240 --> 00:59:45,570
Dat vertelt u dat het 1
moet gaan aan het einde van deze

1212
00:59:45,570 --> 00:59:47,480
zonder zelfs maar te kijken naar 3 of 5.

1213
00:59:47,480 --> 00:59:50,100
En dan de 4, kunt u gewoon
controleren, gaat het recht hier.

1214
00:59:50,100 --> 00:59:51,480
Je hoeft niet te kijken naar de 5.

1215
00:59:51,480 --> 00:59:52,570
Hetzelfde met de 6.

1216
00:59:52,570 --> 00:59:55,860
U weet dat de 6-- het gewoon
niet moeten worden bekeken.

1217
00:59:55,860 --> 00:59:57,870
>> En zo op die manier, je bent
gewoon jezelf te besparen

1218
00:59:57,870 --> 00:59:59,526
veel trappen als je vergelijkt.

1219
00:59:59,526 --> 01:00:02,150
Je hoeft niet elke vergelijken
element tegen andere elementen.

1220
01:00:02,150 --> 01:00:05,230
U vergelijkt alleen tegen degenen
dat je nodig hebt om het te vergelijken tegen.

1221
01:00:05,230 --> 01:00:06,870
Dus dat is een soort van een abstract begrip.

1222
01:00:06,870 --> 01:00:10,540
Geen zorgen als het niet
heel raken jullie nog recht.

1223
01:00:10,540 --> 01:00:14,740
Maar over het algemeen is dit
hoe een merge soort werkt.

1224
01:00:14,740 --> 01:00:17,750
Vragen, korte vragen,
voordat ik verder gaan?

1225
01:00:17,750 --> 01:00:18,550
Ja.

1226
01:00:18,550 --> 01:00:22,230
>> Publiek: Dus u zegt dat u
het 1, en de 4 en de 6

1227
01:00:22,230 --> 01:00:23,860
en zet ze in.

1228
01:00:23,860 --> 01:00:26,800
Dus niet those-- niet
u op zoek naar hen

1229
01:00:26,800 --> 01:00:28,544
als afzonderlijke elementen, niet als geheel?

1230
01:00:28,544 --> 01:00:29,210
ANDI PENG: Ja.

1231
01:00:29,210 --> 01:00:32,020
Dus wat er gebeurt
is dat je in principe

1232
01:00:32,020 --> 01:00:33,650
zijn het creëren van een nieuwe array.

1233
01:00:33,650 --> 01:00:36,690
Zodat u weet dat hier, ik heb
twee series van maat 3, rechts?

1234
01:00:36,690 --> 01:00:39,600
Zodat u weet dat mijn gesorteerde array
moet zes elementen.

1235
01:00:39,600 --> 01:00:42,270
Dus je gewoon een
nieuwe hoeveelheid geheugen.

1236
01:00:42,270 --> 01:00:44,270
Dus je bent een soort van
waarbij verspilling van het geheugen,

1237
01:00:44,270 --> 01:00:46,186
maar dat doet er niet toe
omdat het zo klein is.

1238
01:00:46,186 --> 01:00:48,590
Dus je kijkt naar de 1
en je kijkt naar de 2.

1239
01:00:48,590 --> 01:00:50,770
En je weet dat het 1 minder dan 2.

1240
01:00:50,770 --> 01:00:53,840
Zodat u weet dat 1 op moet gaan
Begin al deze.

1241
01:00:53,840 --> 01:00:55,850
>> Je hoeft niet eens nodig om
kijken naar de 3 en 5.

1242
01:00:55,850 --> 01:00:57,400
Dus je weet 1 gaat daar.

1243
01:00:57,400 --> 01:00:59,300
Dan moet je in principe afhakken van de 1.

1244
01:00:59,300 --> 01:01:00,370
Het is, net als, dood voor ons.

1245
01:01:00,370 --> 01:01:03,690
Dan hebben we slechts 2,
3, 5, en 4 en 6.

1246
01:01:03,690 --> 01:01:06,270
En dan weet je dat je
vergelijk 4 en 2,

1247
01:01:06,270 --> 01:01:07,560
oh, de 2 moet er naartoe te gaan.

1248
01:01:07,560 --> 01:01:09,685
Dus je plop de 2 naar beneden, je afhakken.

1249
01:01:09,685 --> 01:01:12,060
Dus dan hoef je alleen maar de 3
en 5 in de 4 en 6.

1250
01:01:12,060 --> 01:01:14,650
En je gewoon blijven hakken het uit
totdat je ze in de array.

1251
01:01:14,650 --> 01:01:17,110
>> Publiek: Dus je bent altijd
vergelijken van de [onhoorbaar]

1252
01:01:17,110 --> 01:01:17,710
>> ANDI PENG: Precies.

1253
01:01:17,710 --> 01:01:19,590
Dus in die zin, je bent
gewoon vergelijken, wezen,

1254
01:01:19,590 --> 01:01:21,240
een aantal tegen elkaar getal.

1255
01:01:21,240 --> 01:01:22,990
En omdat je weet
dat het sorteren, u

1256
01:01:22,990 --> 01:01:24,350
hoeft niet te kijken door
alle nummers.

1257
01:01:24,350 --> 01:01:25,870
Je hoeft alleen maar te kijken naar de eerste.

1258
01:01:25,870 --> 01:01:27,582
En dan kun je gewoon plop
ze naar beneden, want je weet

1259
01:01:27,582 --> 01:01:29,640
ze behoren waar ze moeten behoren.

1260
01:01:29,640 --> 01:01:31,030
Ja.

1261
01:01:31,030 --> 01:01:32,920
Goede vraag.

1262
01:01:32,920 --> 01:01:35,290
>> En als iemand van jullie
zijn een beetje ambitieus,

1263
01:01:35,290 --> 01:01:38,660
voel je vrij om te kijken naar deze code.

1264
01:01:38,660 --> 01:01:40,680
Dit is eigenlijk de
fysieke implementatie

1265
01:01:40,680 --> 01:01:42,150
hoe we merge soort zou schrijven.

1266
01:01:42,150 --> 01:01:44,070
En u kunt zien, het is erg kort.

1267
01:01:44,070 --> 01:01:46,310
Maar de ideeën achter
Het zijn vrij complex.

1268
01:01:46,310 --> 01:01:50,865
Dus als je het gevoel dat het tekenen dit uit
in je huiswerk vanavond, voel je vrij 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
David ging ook meer dan dit in het college.

1272
01:01:58,070 --> 01:02:00,660
Wat zijn de beste case
runtimes, slechtste geval runtimes,

1273
01:02:00,660 --> 01:02:05,680
en de verwachte looptijden van merge soort?

1274
01:02:05,680 --> 01:02:07,260
Een paar seconden na te denken.

1275
01:02:07,260 --> 01:02:11,198
Dit is vrij moeilijk, maar soort
intuïtief als je erover nadenkt.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Prima.

1278
01:02:23,054 --> 01:02:25,269
>> Publiek: Is het ergste geval n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI PENG: Precies.

1280
01:02:26,060 --> 01:02:29,380
En waarom is het n log n.

1281
01:02:29,380 --> 01:02:32,230
>> Publiek: Is het niet omdat het
exponentieel sneller,

1282
01:02:32,230 --> 01:02:35,390
dus het is als een functie van die
plaats van simpelweg n

1283
01:02:35,390 --> 01:02:37,529
kwadraat of zoiets?

1284
01:02:37,529 --> 01:02:38,320
ANDI PENG: Precies.

1285
01:02:38,320 --> 01:02:40,750
Dus de reden waarom de
runtime op dit n log

1286
01:02:40,750 --> 01:02:44,310
n because-- wat bent u
doet in al deze stappen?

1287
01:02:44,310 --> 01:02:46,190
Je bent gewoon hakken het in de helft, toch?

1288
01:02:46,190 --> 01:02:48,750
En dus toen we doen het
log, alles wat het doet

1289
01:02:48,750 --> 01:02:53,150
is een probleem verdelen in tweeën,
in de helft, in de helft, meer helften.

1290
01:02:53,150 --> 01:02:56,430
En in die zin, kan je soort
elimineren van het lineaire model

1291
01:02:56,430 --> 01:02:57,510
die we hebben gebruikt.

1292
01:02:57,510 --> 01:03:00,254
Want als je hakken
dingen in de helft, het is een log.

1293
01:03:00,254 --> 01:03:02,420
Dat is gewoon de wiskundige
manier vertegenwoordigen.

1294
01:03:02,420 --> 01:03:06,310
>> En dan eindelijk, op het einde, je bent
gewoon het maken van een laatste passage door

1295
01:03:06,310 --> 01:03:07,930
om ze allemaal op orde te krijgen, toch?

1296
01:03:07,930 --> 01:03:10,330
En dus als je gewoon
controleren een ding, dat is n.

1297
01:03:10,330 --> 01:03:13,420
En dus je bent soort
bij elkaar te vermenigvuldigen.

1298
01:03:13,420 --> 01:03:17,660
Dus het is alsof je die laatste heb
controleren n hier beneden met een log van n

1299
01:03:17,660 --> 01:03:18,390
hier boven.

1300
01:03:18,390 --> 01:03:21,060
En als je vermenigvuldigen
hen, dat is n log n.

1301
01:03:21,060 --> 01:03:26,100
>> En zo het beste geval en slechtste
zaak en verwacht zijn alle n log n.

1302
01:03:26,100 --> 01:03:27,943
Het is ook als een andere soort.

1303
01:03:27,943 --> 01:03:30,090
Het is als een soort selectie
in die zin dat

1304
01:03:30,090 --> 01:03:32,131
maakt niet uit wat uw
lijst is, het is gewoon

1305
01:03:32,131 --> 01:03:34,801
om hetzelfde te doen elke keer weer.

1306
01:03:34,801 --> 01:03:35,300
OK.

1307
01:03:35,300 --> 01:03:39,950
Dus zoals jullie kunnen zien, ook al
het soort dat we through-- n gegaan

1308
01:03:39,950 --> 01:03:41,660
kwadraat, het is niet erg efficiënt.

1309
01:03:41,660 --> 01:03:47,060
En zelfs dit n log n
niet het meest efficiënt.

1310
01:03:47,060 --> 01:03:49,720
Als jullie zijn nieuwsgierig,
er is een soort mechanismen

1311
01:03:49,720 --> 01:03:54,310
die zo efficiënt dat ze zijn
bijna wezen vlak in runtime.

1312
01:03:54,310 --> 01:03:55,420
>> Je hebt een aantal log n's.

1313
01:03:55,420 --> 01:03:58,190
Je hebt een aantal log log n's.

1314
01:03:58,190 --> 01:04:00,330
We niet op hen te raken
in deze klasse nu.

1315
01:04:00,330 --> 01:04:02,663
Maar als jullie zijn nieuwsgierig,
voel je vrij om google, wat is

1316
01:04:02,663 --> 01:04:04,392
de meest efficiënte sorteermechanismen.

1317
01:04:04,392 --> 01:04:06,350
Ik weet het niet, er zijn
sommige echt grappig degenen,

1318
01:04:06,350 --> 01:04:09,860
like-- er is wat werkelijk
grappig degenen die mensen maken.

1319
01:04:09,860 --> 01:04:12,210
En vraag je je af hoe ze
ooit gedacht.

1320
01:04:12,210 --> 01:04:15,730
Zodat Google, als je wat vrije
tijd, op, wat zijn sommige grappige manieren

1321
01:04:15,730 --> 01:04:17,730
dat people-- alsook
efficiënte ways-- mensen

1322
01:04:17,730 --> 01:04:20,371
hebben kunnen allerlei voeren geweest.

1323
01:04:20,371 --> 01:04:20,870
OK.

1324
01:04:20,870 --> 01:04:22,880
En hier is gewoon een handige kleine grafiek.

1325
01:04:22,880 --> 01:04:26,850
Ik weet dat u allen, daarvoor quiz 0,
zal in uw kamer waarschijnlijk proberen

1326
01:04:26,850 --> 01:04:27,960
te onthouden dat.

1327
01:04:27,960 --> 01:04:30,940
Dus dat is leuk in er voor jullie.

1328
01:04:30,940 --> 01:04:37,120
Gewoon niet de logica die made-- vergeten
waarom deze nummers werden voorkomen.

1329
01:04:37,120 --> 01:04:39,870
Als je altijd verloren, maar zorg
dat u weet wat de soort zijn.

1330
01:04:39,870 --> 01:04:40,820
En je kunt doorlopen
ze in je geest

1331
01:04:40,820 --> 01:04:42,903
om erachter te komen waarom deze
antwoorden die antwoorden.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Prima.

1334
01:04:47,600 --> 01:04:49,680
Dus we gaan verhuizen
op slot te zoeken.

1335
01:04:49,680 --> 01:04:51,638
Want die van u
die PSET hebben gelezen,

1336
01:04:51,638 --> 01:04:55,175
zoeken is ook deel uit van
probleem van deze week zet.

1337
01:04:55,175 --> 01:04:57,300
U wordt gevraagd uit te voeren
twee soorten zoekopdrachten.

1338
01:04:57,300 --> 01:05:00,070
Een daarvan is een lineair zoeken en
een is een binair zoeken.

1339
01:05:00,070 --> 01:05:01,760
>> Dus het lineair zoeken is vrij eenvoudig.

1340
01:05:01,760 --> 01:05:04,070
Je wil gewoon om te zoeken element
van een lijst om te zien als je het krijgen.

1341
01:05:04,070 --> 01:05:05,444
Je hoeft alleen maar om door te herhalen.

1342
01:05:05,444 --> 01:05:08,170
Als deze gelijk is iets,
je kunt gewoon terug, toch?

1343
01:05:08,170 --> 01:05:10,890
Maar degene die we het meest
geïnteresseerd in het praten over

1344
01:05:10,890 --> 01:05:14,550
binair zoeken, rechts, hetgeen de
verdeel en het mechanisme te veroveren die

1345
01:05:14,550 --> 01:05:18,190
David werd demonstreren in collegezaal.

1346
01:05:18,190 --> 01:05:20,810
>> Vergeet niet het telefoonboek voorbeeld
dat hij blijft de opvoeding,

1347
01:05:20,810 --> 01:05:23,960
de een dat hij soort van worstelde
een beetje aan het afgelopen jaar,

1348
01:05:23,960 --> 01:05:27,530
waar u het probleem te verdelen in de helft,
in de helft, in de helft, opnieuw en opnieuw,

1349
01:05:27,530 --> 01:05:30,730
totdat je vindt wat je zoekt?

1350
01:05:30,730 --> 01:05:33,727
En je hebt de
runtime van dat ook.

1351
01:05:33,727 --> 01:05:35,810
En u kunt zien, het is
aanzienlijk efficiënter

1352
01:05:35,810 --> 01:05:39,080
dan elke andere vorm van zoeken.

1353
01:05:39,080 --> 01:05:41,880
>> Dus de manier waarop we zouden gaan over
implementeren van een binaire zoekopdracht

1354
01:05:41,880 --> 01:05:46,510
is, als we hadden een array,
index 0-6, zeven elementen,

1355
01:05:46,510 --> 01:05:49,790
we kunnen kijken in het midden, right--
sorry, als onze vraag first--

1356
01:05:49,790 --> 01:05:53,840
als we willen dat de vraag te stellen, doet
de array bevat het element 7,

1357
01:05:53,840 --> 01:05:56,840
Uiteraard zijn mensen, en met
zo'n kleine serie, het is gemakkelijk voor ons

1358
01:05:56,840 --> 01:05:58,210
om ja te zeggen.

1359
01:05:58,210 --> 01:06:05,750
Maar de weg naar een binaire implementeren
zoek zou zijn om te kijken in het midden.

1360
01:06:05,750 --> 01:06:08,020
>> We weten dat de index 3
het midden, omdat we

1361
01:06:08,020 --> 01:06:09,270
weet dat er zeven elementen.

1362
01:06:09,270 --> 01:06:10,670
Wat 7 gedeeld door 2?

1363
01:06:10,670 --> 01:06:12,850
U kunt afhakken die extra 1.

1364
01:06:12,850 --> 01:06:14,850
Je hebt 3 in het midden.

1365
01:06:14,850 --> 01:06:17,590
Zo is reeks 3 gelijk aan 7?

1366
01:06:17,590 --> 01:06:18,900
Het klopt niet?

1367
01:06:18,900 --> 01:06:21,050
Maar we kunnen een aantal controles te doen.

1368
01:06:21,050 --> 01:06:25,380
Is matrix van 3 minder dan 7 of
reeks 3 is groter dan 7?

1369
01:06:25,380 --> 01:06:27,240
>> En we weten dat het is minder dan 7.

1370
01:06:27,240 --> 01:06:30,259
Dus we weten dat, oh, het moet
niet in de linker helft.

1371
01:06:30,259 --> 01:06:32,300
We weten dat het moet
in de rechter helft, toch?

1372
01:06:32,300 --> 01:06:34,662
Dus we kunnen gewoon afhakken de helft van de array.

1373
01:06:34,662 --> 01:06:36,370
We hebben niet eens aan
kijken meer.

1374
01:06:36,370 --> 01:06:38,711
Omdat we weten dat
de helft van onze probleem--

1375
01:06:38,711 --> 01:06:41,210
We weten dat het antwoord in
de rechterhelft van ons probleem.

1376
01:06:41,210 --> 01:06:42,580
Dus we alleen kijken naar dat nu.

1377
01:06:42,580 --> 01:06:44,860
>> Dus nu kijken we naar de
midden van wat er over is.

1378
01:06:44,860 --> 01:06:46,880
Die index 5.

1379
01:06:46,880 --> 01:06:50,200
Wij doen het zelfde check weer
en we zien dat het kleiner.

1380
01:06:50,200 --> 01:06:52,050
Dus we kijken aan de linkerkant van dat.

1381
01:06:52,050 --> 01:06:53,430
En dan zien we dat het inchecken.

1382
01:06:53,430 --> 01:06:57,600
Is de array waarde bij
index 4 gelijk aan 7?

1383
01:06:57,600 --> 01:06:58,260
Het is.

1384
01:06:58,260 --> 01:07:03,580
Dus we kunnen echt terug, omdat
vonden we de waarde in onze lijst.

1385
01:07:03,580 --> 01:07:06,738
Doet de manier waarop ik ging door
dat zinvol voor iedereen?

1386
01:07:06,738 --> 01:07:08,760
OK.

1387
01:07:08,760 --> 01:07:11,670
Ik zal jullie misschien te geven, zoals,
drie, vier minuten te achterhalen

1388
01:07:11,670 --> 01:07:13,270
hoe dit pseudocode in.

1389
01:07:13,270 --> 01:07:18,070
>> Dus stel ik u gevraagd een schrijven
functie genaamd search () die terug

1390
01:07:18,070 --> 01:07:20,640
een waarde, een Booleaanse waarde,
dat waar was of false-- zoals,

1391
01:07:20,640 --> 01:07:22,970
waar als je vond het
waarde false als je dat niet deed.

1392
01:07:22,970 --> 01:07:25,230
En dan was je
aangenomen in de waarde die u

1393
01:07:25,230 --> 01:07:28,410
zochten naar waarden, die
is de array-- oh, ik zeker zet

1394
01:07:28,410 --> 01:07:29,410
dat op de verkeerde plaats.

1395
01:07:29,410 --> 01:07:29,580
OK.

1396
01:07:29,580 --> 01:07:31,829
Anyways, dat zou moeten hebben
rechts van waarden geweest.

1397
01:07:31,829 --> 01:07:36,280
En dan int n is het aantal
elementen in de matrix.

1398
01:07:36,280 --> 01:07:39,430
Hoe zou u over het proberen
dat probleem in pseudocode?

1399
01:07:39,430 --> 01:07:41,630
Ik zal u kerels zoals geven
drie minuten om dat te doen.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Nee, ik denk dat er only--
ja, er is een recht hier.

1402
01:08:02,595 --> 01:08:03,261
Publiek: Kan ik?

1403
01:08:03,261 --> 01:08:04,388
ANDI Peng: Ja, ik heb je.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Is dat werken?

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
Oké jongens, we zijn
gaan om het te beteugelen.

1410
01:10:47,630 --> 01:10:49,730
OK.

1411
01:10:49,730 --> 01:10:54,020
Neem dus we hebben dit prachtige gekregen
kleine array met n-waarden in.

1412
01:10:54,020 --> 01:10:55,170
Ik heb niet de lijnen te tekenen.

1413
01:10:55,170 --> 01:10:58,649
Maar hoe zouden we gaan over het
proberen om dit te schrijven?

1414
01:10:58,649 --> 01:11:00,440
Wil iemand
geef mij de eerste lijn?

1415
01:11:00,440 --> 01:11:02,814
Als je me wilt het geven
eerste regel van deze pseudocode.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> PUBLIEK: [onverstaanbaar]

1418
01:11:08,430 --> 01:11:10,138
Publiek: Je zou willen
naar through-- herhalen

1419
01:11:10,138 --> 01:11:11,094
PUBLIEK: Gewoon weer een lus?

1420
01:11:11,094 --> 01:11:11,760
Publiek: --Voor.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI PENG: Dus dit is een beetje lastig.

1423
01:11:17,780 --> 01:11:23,130
Denk about-- je wilt
te blijven draaien deze lus

1424
01:11:23,130 --> 01:11:27,950
over en weer tot wanneer?

1425
01:11:27,950 --> 01:11:30,819
>> Publiek: Totdat de [onverstaanbaar]
gelijk is aan die waarde.

1426
01:11:30,819 --> 01:11:31,610
ANDI PENG: Precies.

1427
01:11:31,610 --> 01:11:33,900
Dus je kunt eigenlijk alleen maar write--
kunnen we zelfs vereenvoudigen meer.

1428
01:11:33,900 --> 01:11:35,630
We kunnen gewoon een tijdje loop, toch?

1429
01:11:35,630 --> 01:11:39,380
Dus je kunt gewoon loop--
we weten dat het een tijdje.

1430
01:11:39,380 --> 01:11:42,850
Maar voor nu, ga ik
door wat - naar "loop" zeggen?

1431
01:11:42,850 --> 01:11:46,640
Loop until-- wat
onze eindigend toestand?

1432
01:11:46,640 --> 01:11:47,510
Ik denk dat ik het hoorde.

1433
01:11:47,510 --> 01:11:48,530
Ik hoorde iemand zeggen.

1434
01:11:48,530 --> 01:11:51,255
>> PUBLIEK: Waarden gelijk midden.

1435
01:11:51,255 --> 01:11:52,255
ANDI Peng: Zeg het nog eens.

1436
01:11:52,255 --> 01:11:54,470
PUBLIEK: Of, totdat de
waarde die u zoekt

1437
01:11:54,470 --> 01:11:58,470
is het gelijk aan de middenwaarde.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI Peng: Wat als het er niet in?

1439
01:12:00,280 --> 01:12:03,113
Wat als de waarde die u zoekt
voor is eigenlijk niet in deze serie?

1440
01:12:03,113 --> 01:12:05,890
PUBLIEK: U keert terug 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI Peng: Maar wat willen we
lus totdat als we een aandoening?

1442
01:12:08,850 --> 01:12:09,350
Ja.

1443
01:12:09,350 --> 01:12:11,239
>> Publiek: Totdat er maar één waarde?

1444
01:12:11,239 --> 01:12:13,530
ANDI Peng: U kunt loop
until-- zodat je weet dat je bent

1445
01:12:13,530 --> 01:12:15,714
gaan naar een maximale waarde hebben, toch?

1446
01:12:15,714 --> 01:12:18,130
En je weet dat je gaat
een min waarde, recht?

1447
01:12:18,130 --> 01:12:20,379
Want ook dat is iets
Ik vergat te zeggen vóór,

1448
01:12:20,379 --> 01:12:22,640
dat iets dat
kritisch over binaire zoekopdracht

1449
01:12:22,640 --> 01:12:24,182
is dat array al wordt gesorteerd.

1450
01:12:24,182 --> 01:12:26,973
Want er is geen manier van doen
Dit als ze gewoon willekeurige waarden.

1451
01:12:26,973 --> 01:12:29,190
Je weet niet of men is
groter dan de andere, toch?

1452
01:12:29,190 --> 01:12:32,720
>> Zodat je weet dat je max en
uw minuten zijn hier, toch?

1453
01:12:32,720 --> 01:12:35,590
Als je gaat worden het aanpassen
uw maximum in uw minuten en de mid--

1454
01:12:35,590 --> 01:12:38,470
laten we gewoon aannemen je
mid waarde is gelijk hier--

1455
01:12:38,470 --> 01:12:43,910
je gaat in principe
lus totdat uw minimum

1456
01:12:43,910 --> 01:12:47,510
ongeveer hetzelfde als uw maximum, recht, of
als je max is niet hetzelfde als uw min.

1457
01:12:47,510 --> 01:12:48,040
Rechts?

1458
01:12:48,040 --> 01:12:51,340
Want als dat gebeurt, weet je dat
je uiteindelijk hebt geraakt dezelfde waarde.

1459
01:12:51,340 --> 01:12:59,135
Dus je wilt loop totdat je min
is kleiner dan of gelijk to-- oops,

1460
01:12:59,135 --> 01:13:01,510
ten hoogste,
andersom around-- max.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Wist dat zinvol?

1463
01:13:16,160 --> 01:13:18,810
Ik nam een ​​paar pogingen om dat recht te krijgen.

1464
01:13:18,810 --> 01:13:21,869
Maar loop tot je maximale waarde
in wezen bijna kleiner

1465
01:13:21,869 --> 01:13:23,410
dan of gelijk aan uw minimum, toch?

1466
01:13:23,410 --> 01:13:25,201
Dat is wanneer je weet
die je hebt geconvergeerd.

1467
01:13:25,201 --> 01:13:29,290
PUBLIEK: Wanneer zou uw maximale
waarde van minder dan het minimum?

1468
01:13:29,290 --> 01:13:31,040
ANDI Peng: Als je blijft
vast, waarin

1469
01:13:31,040 --> 01:13:32,380
is wat we gaan
te doen dit.

1470
01:13:32,380 --> 01:13:33,460
Slaat dat ergens op?

1471
01:13:33,460 --> 01:13:35,750
Minimum en maximum zijn
integers dat we waarschijnlijk

1472
01:13:35,750 --> 01:13:39,260
gaat te willen creëren om te houden
bij waar we naar op zoek.

1473
01:13:39,260 --> 01:13:41,790
Omdat de array bestaat
ongeacht wat we doen.

1474
01:13:41,790 --> 01:13:45,030
Zoals, we zijn niet fysiek
afhakken van de array, toch?

1475
01:13:45,030 --> 01:13:47,261
We zijn gewoon aanpassen
waar we op zoek bent.

1476
01:13:47,261 --> 01:13:48,136
Slaat dat ergens op?

1477
01:13:48,136 --> 01:13:48,472
>> Publiek: Ja.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI Peng: OK.

1479
01:13:49,110 --> 01:13:57,090
Dus als dat is de voorwaarde voor onze loop,
wat willen we binnenkant van deze lijn?

1480
01:13:57,090 --> 01:13:58,700
Wat gaan we te willen doen?

1481
01:13:58,700 --> 01:14:02,390
Dus nu, we hebben
een max en een min, rechts,

1482
01:14:02,390 --> 01:14:04,962
Waarschijnlijk gemaakt hier ergens.

1483
01:14:04,962 --> 01:14:07,170
We gaan waarschijnlijk willen
een midden, rechts vinden?

1484
01:14:07,170 --> 01:14:08,450
Hoe gaan we om
in staat om het midden te vinden?

1485
01:14:08,450 --> 01:14:09,491
Wat is de mathematical--

1486
01:14:09,491 --> 01:14:11,079
PUBLIEK: Max plus min gedeeld door 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI PENG: Precies.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Slaat dat ergens op?

1490
01:14:21,620 --> 01:14:25,780
En doen jullie zien waarom we
niet alleen use-- waarom we dit deden

1491
01:14:25,780 --> 01:14:27,850
in plaats van het doen van slechts n gedeeld door 2?

1492
01:14:27,850 --> 01:14:30,310
Het is omdat n is een waarde
dat zal hetzelfde blijven.

1493
01:14:30,310 --> 01:14:30,979
Rechts?

1494
01:14:30,979 --> 01:14:34,020
Maar als we passen onze minimale en
maximale waarden, ze gaan veranderen.

1495
01:14:34,020 --> 01:14:36,040
En als resultaat, onze middelbare
zal ook veranderen.

1496
01:14:36,040 --> 01:14:37,873
Dus dat is waarom we willen
om dit recht te doen hier.

1497
01:14:37,873 --> 01:14:38,510
OK.

1498
01:14:38,510 --> 01:14:41,600
>> En dan, nu
we hebben our-- gevonden ja.

1499
01:14:41,600 --> 01:14:44,270
>> PUBLIEK: Even een question--
als je zegt min en max,

1500
01:14:44,270 --> 01:14:46,410
gaan we ervan uit dat
het is al naargelang?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI Peng: Ja, dat is eigenlijk een
Voorwaarde voor een binary search,

1502
01:14:48,400 --> 01:14:49,816
dat je moet weten dat het opgelost.

1503
01:14:49,816 --> 01:14:53,660
Dat is waarom soort, schrijf u in uw
probleem ingesteld voordat uw binaire zoekopdracht.

1504
01:14:53,660 --> 01:14:55,910
OK.

1505
01:14:55,910 --> 01:14:58,876
Dus nu we weten waar onze middelpunt
wordt, wat wil je hier doen?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> PUBLIEK: We willen vergelijken
dat voor het andere.

1508
01:15:04,319 --> 01:15:05,110
ANDI PENG: Precies.

1509
01:15:05,110 --> 01:15:12,280
Dus je gaat vergelijken
medio aan waarde, toch?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
En wat betekent dat vertellen
ons als we vergelijken?

1512
01:15:18,670 --> 01:15:22,226
Wat willen we daarna doen?

1513
01:15:22,226 --> 01:15:25,389
>> Publiek: Als de waarde groter is
dan het midden, willen we er afgesneden.

1514
01:15:25,389 --> 01:15:26,180
ANDI PENG: Precies.

1515
01:15:26,180 --> 01:15:33,940
Als de waarde groter is
dan het midden, we zijn

1516
01:15:33,940 --> 01:15:36,550
gaat willen deze veranderen
minimum en Maxes, toch?

1517
01:15:36,550 --> 01:15:38,980
Wat willen we veranderen?

1518
01:15:38,980 --> 01:15:42,145
Dus als we weten wat de waarde is ergens
hier, wat je doen we om te veranderen?

1519
01:15:42,145 --> 01:15:44,758
We willen onze veranderen
minimaal tot medio te zijn, toch?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
En dan anders, als het in deze
de helft, wat willen we veranderen?

1522
01:15:54,292 --> 01:15:55,306
>> Publiek: Uw maximum.

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 ben je gewoon
te houden looping, toch?

1526
01:16:04,680 --> 01:16:08,920
Want nu, na één iteratie
door middel van, heb je een max kreeg hier.

1527
01:16:08,920 --> 01:16:10,760
En dan kun je een mid herberekenen.

1528
01:16:10,760 --> 01:16:11,990
En dan kun je vergelijken.

1529
01:16:11,990 --> 01:16:14,766
En je gaat om door te gaan
totdat de min en Maxes

1530
01:16:14,766 --> 01:16:15,890
hebben in wezen geconvergeerd.

1531
01:16:15,890 --> 01:16:17,890
En dat is als je weet dat
u het einde van het hebt getroffen.

1532
01:16:17,890 --> 01:16:20,280
En of je hebt het gevonden
of je hebt niet op dat punt.

1533
01:16:20,280 --> 01:16:23,170
>> Betekent dit zinvol om iedereen?

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 erg belangrijk,
want je hebt

1537
01:16:27,900 --> 01:16:29,760
om dit te schrijven in de code vanavond.

1538
01:16:29,760 --> 01:16:32,660
Maar jullie hebben een redelijk goed
gevoel van wat je 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
Dus we hebben ongeveer zeven
minuten over sectie.

1542
01:16:38,840 --> 01:16:43,170
Dus we gaan praten over
Dit PSET dat we moeten doen.

1543
01:16:43,170 --> 01:16:46,410
Dus de PSET verdeeld in twee helften.

1544
01:16:46,410 --> 01:16:50,230
De eerste helft betreft
implementeren van een vondst

1545
01:16:50,230 --> 01:16:54,210
waar je een lineair zoeken te schrijven, een
binary search, en een sorteer-algoritme.

1546
01:16:54,210 --> 01:16:56,690
>> Dit is dus het eerste
tijd in een PSET, waar

1547
01:16:56,690 --> 01:17:00,050
geven we jullie wat heet
verdeelsleutel, die code

1548
01:17:00,050 --> 01:17:02,740
die we hebben pre-geschreven,
maar net vertrokken sommige stukken af

1549
01:17:02,740 --> 01:17:04,635
voor u om te schrijven beëindigen.

1550
01:17:04,635 --> 01:17:07,510
Dus jullie, als je kijkt naar deze
code, zou je echt bang.

1551
01:17:07,510 --> 01:17:08,630
Als je gewoon wilt, ahh, ik
weet niet wat dat doet,

1552
01:17:08,630 --> 01:17:11,670
Ik weet het niet, als, dat lijkt
zo ingewikkeld, ahh, ontspannen.

1553
01:17:11,670 --> 01:17:12,170
Het is ok.

1554
01:17:12,170 --> 01:17:12,930
Lees de spec.

1555
01:17:12,930 --> 01:17:16,920
De spec zal precies uitleggen
Wat al deze programma's aan het doen zijn.

1556
01:17:16,920 --> 01:17:20,560
>> Bijvoorbeeld, generate.c een programma
die zal komen met uw PSET.

1557
01:17:20,560 --> 01:17:24,060
Je hoeft niet echt aan te raken, maar
u moet begrijpen wat het doet.

1558
01:17:24,060 --> 01:17:28,550
En generate.c, alles wat het doet is
of het genereren van willekeurige getallen

1559
01:17:28,550 --> 01:17:32,400
of u kunt het een zaadje, zoals een
afgesproken aantal dat nodig is,

1560
01:17:32,400 --> 01:17:34,140
en genereert meer nummers.

1561
01:17:34,140 --> 01:17:37,170
Dus er is een specifieke manier om
implementeren generate.c waarin

1562
01:17:37,170 --> 01:17:42,760
u kunt gewoon een stelletje getallen
voor u om uw andere methodes te testen op.

1563
01:17:42,760 --> 01:17:45,900
>> Dus als je wilde, voor
Zo test je vondst,

1564
01:17:45,900 --> 01:17:48,970
je zou willen generate.c lopen,
genereren een heleboel nummers,

1565
01:17:48,970 --> 01:17:50,880
en voer uw helpers functie.

1566
01:17:50,880 --> 01:17:53,930
Uw helpers functie is waar je bent
daadwerkelijk fysiek schrijven van code.

1567
01:17:53,930 --> 01:17:59,330
En denk aan helpers als een bibliotheek bestand
je schrijft dat de vondst roept.

1568
01:17:59,330 --> 01:18:02,950
En zo binnen helpers.c, zult u
doen het zoeken en sorteren.

1569
01:18:02,950 --> 01:18:06,500
>> En dan zul je in wezen
zet ze allemaal samen.

1570
01:18:06,500 --> 01:18:10,350
De spec zal u vertellen hoe u
zet dat op de opdrachtregel.

1571
01:18:10,350 --> 01:18:14,880
En je zult in staat zijn om te testen of
niet je sorteren en zoeken werken.

1572
01:18:14,880 --> 01:18:15,870
Cool.

1573
01:18:15,870 --> 01:18:18,720
Heeft iemand al begonnen en
ondervonden problemen of vragen

1574
01:18:18,720 --> 01:18:20,520
ze nu hebben met dit?

1575
01:18:20,520 --> 01:18:21,020
OK.

1576
01:18:21,020 --> 01:18:21,476
>> Publiek: Wacht.

1577
01:18:21,476 --> 01:18:21,932
Ik heb een vraag.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI PENG: Ja.

1579
01:18:22,844 --> 01:18:28,390
>> Publiek: Dus ik begon te doen
het lineair zoeken in helpers.c

1580
01:18:28,390 --> 01:18:29,670
en het was niet echt aan het werk.

1581
01:18:29,670 --> 01:18:34,590
Maar dan later, vond ik dat we gewoon
hebben om het te schrappen en te doen binaire zoeken.

1582
01:18:34,590 --> 01:18:36,991
Dus maakt het uit als het niet werkt?

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 aangezien we niet--

1586
01:18:42,642 --> 01:18:44,350
Publiek: Maar niemand
eigenlijk controleren.

1587
01:18:44,350 --> 01:18:46,058
ANDI PENG: We zijn nooit
gaan om te zien dat.

1588
01:18:46,058 --> 01:18:49,590
Maar wilt u waarschijnlijk te maken
ervoor dat uw zoekopdracht werkt.

1589
01:18:49,590 --> 01:18:51,700
Want als je lineaire
search werkt niet,

1590
01:18:51,700 --> 01:18:54,410
dan is de kans groot dat uw binaire
zoek gaat niet zo goed werkt.

1591
01:18:54,410 --> 01:18:56,646
Want je hebt gelijk
logica beiden.

1592
01:18:56,646 --> 01:18:58,020
En nee, het maakt eigenlijk niet uit.

1593
01:18:58,020 --> 01:19:01,300
Dus de enige die je draaien
in zijn soort en binaire zoeken.

1594
01:19:01,300 --> 01:19:02,490
Ja.

1595
01:19:02,490 --> 01:19:06,610
>> En ook veel kinderen waren
proberen helpers.c stellen.

1596
01:19:06,610 --> 01:19:09,550
Je bent niet echt toegestaan
te doen, omdat helpers.c

1597
01:19:09,550 --> 01:19:11,200
heeft geen hoofdfunctie.

1598
01:19:11,200 --> 01:19:13,550
En dus moet je alleen
zijn eigenlijk het samenstellen

1599
01:19:13,550 --> 01:19:18,670
genereren en te vinden, want gesprekken vinden
helpers.c en de functies daarbinnen.

1600
01:19:18,670 --> 01:19:20,790
Dus dat maakt het debuggen
een pijn in de kont.

1601
01:19:20,790 --> 01:19:22,422
Maar dat is wat we moeten doen.

1602
01:19:22,422 --> 01:19:23,880
PUBLIEK: U maken allemaal gewoon, toch?

1603
01:19:23,880 --> 01:19:27,290
ANDI Peng: je kunt gewoon
maken allemaal zo goed, ja.

1604
01:19:27,290 --> 01:19:28,060
OK.

1605
01:19:28,060 --> 01:19:32,570
Dus dat is het in termen van wat
de PSET vraagt ​​u allen te doen.

1606
01:19:32,570 --> 01:19:35,160
Als u vragen hebt, voel
vrij om te vragen na sectie.

1607
01:19:35,160 --> 01:19:37,580
Ik zal er zijn voor, zoals, 20 minuten.

1608
01:19:37,580 --> 01:19:40,500
>> En ja, de PSET's
echt niet zo slecht.

1609
01:19:40,500 --> 01:19:41,680
Jullie moeten zijn OK.

1610
01:19:41,680 --> 01:19:43,250
Deze, volg gewoon richtlijnen.

1611
01:19:43,250 --> 01:19:47,840
Soort hebben een gevoel van, logisch, wat
dient te gebeuren en je komt wel goed.

1612
01:19:47,840 --> 01:19:48,690
Wees niet te bang zijn.

1613
01:19:48,690 --> 01:19:50,220
Er is veel van de code
er al geschreven.

1614
01:19:50,220 --> 01:19:53,011
Wees niet te bang zijn als je dat niet doet
begrijpen wat dat allemaal betekent.

1615
01:19:53,011 --> 01:19:54,749
Als het een stuk, het is helemaal prima.

1616
01:19:54,749 --> 01:19:55,790
En kom naar de kantooruren.

1617
01:19:55,790 --> 01:19:57,520
Wij helpen u een kijkje nemen.

1618
01:19:57,520 --> 01:20:00,810
>> Publiek: Met de extra
functies, kijken we die op?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI Peng: Ja, dat zijn in de code.

1620
01:20:03,417 --> 01:20:05,750
In het spel van 15 de helft van
het is al voor u geschreven.

1621
01:20:05,750 --> 01:20:09,310
Dus deze functies zijn
reeds in de code.

1622
01:20:09,310 --> 01:20:12,020
Yep.

1623
01:20:12,020 --> 01:20:12,520
Prima.

1624
01:20:12,520 --> 01:20:14,000
Nou, beste van geluk.

1625
01:20:14,000 --> 01:20:15,180
Het is een walgelijk dag.

1626
01:20:15,180 --> 01:20:19,370
Dus hopelijk jullie niet te voelen
slecht over het verblijf binnen en codering.

1627
01:20:19,370 --> 01:20:22,133