1
00:00:00,000 --> 00:00:11,100

2
00:00:11,100 --> 00:00:12,300
>> SPEAKER 1: Hey iedereen!

3
00:00:12,300 --> 00:00:13,890
Welkom terug bij sectie.

4
00:00:13,890 --> 00:00:17,480
Zo blij om hier zo velen van jullie beiden te zien,
en iedereen wie let online.

5
00:00:17,480 --> 00:00:18,760

6
00:00:18,760 --> 00:00:20,920
Dus, zoals gebruikelijk welkom terug.

7
00:00:20,920 --> 00:00:24,360
Ik hoop dat jullie allemaal een mooie
weekend, vol rust, ontspanning.

8
00:00:24,360 --> 00:00:26,026
Het was prachtig gisteren.

9
00:00:26,026 --> 00:00:27,525
Dus, ik hoop dat je genoten hebt van het buitenleven.

10
00:00:27,525 --> 00:00:28,840

11
00:00:28,840 --> 00:00:30,610
>> Dus eerst een paar mededelingen.

12
00:00:30,610 --> 00:00:31,920

13
00:00:31,920 --> 00:00:32,700
Grading.

14
00:00:32,700 --> 00:00:37,350
Dus, de meeste van jullie moeten hebben gekregen van een
e-mail van mij over uw Scratch Pset,

15
00:00:37,350 --> 00:00:39,920
evenals Beoordeling voor Pset 1.

16
00:00:39,920 --> 00:00:41,000

17
00:00:41,000 --> 00:00:42,220
Dus, gewoon een paar dingen.

18
00:00:42,220 --> 00:00:45,150
Zorg ervoor dat u check50 gebruiken in style50.

19
00:00:45,150 --> 00:00:47,250
Deze zijn bedoeld om te worden
middelen voor jullie,

20
00:00:47,250 --> 00:00:50,660
om ervoor te zorgen dat je krijgt
zo veel punten als je kunt

21
00:00:50,660 --> 00:00:52,390
zonder ze onnodig verlies.

22
00:00:52,390 --> 00:00:54,407
Dus, dingen als stijl
zijn zeer belangrijk.

23
00:00:54,407 --> 00:00:55,740
We gaan af te nemen voor het.

24
00:00:55,740 --> 00:00:58,115
Sommigen van u misschien al
gemerkt dat uit je Pset.

25
00:00:58,115 --> 00:00:58,920

26
00:00:58,920 --> 00:01:01,450
En check50 is slechts een
heel gemakkelijke manier om ervoor te zorgen

27
00:01:01,450 --> 00:01:05,050
dat we eigenlijk zijn terug wat
moet worden teruggegeven aan de gebruiker,

28
00:01:05,050 --> 00:01:06,690
en dat alles naar behoren werkt.

29
00:01:06,690 --> 00:01:08,690

30
00:01:08,690 --> 00:01:12,040
>> Op de tweede nota, zorg ervoor dat uw
het uploaden van dingen naar de juiste map.

31
00:01:12,040 --> 00:01:14,470
Het maakt mijn leven net een
beetje moeilijker

32
00:01:14,470 --> 00:01:18,836
als je Pset 2 uploaden naar Pset 1
want als ik dingen downloaden

33
00:01:18,836 --> 00:01:20,085
ze niet goed te downloaden.

34
00:01:20,085 --> 00:01:21,690

35
00:01:21,690 --> 00:01:24,560
En ik weet dat het een beetje wankel
in een systeem te wennen,

36
00:01:24,560 --> 00:01:26,950
maar gewoon super zijn
voorzichtig, al was het maar voor mij,

37
00:01:26,950 --> 00:01:30,080
zodat wanneer je krijgt e-mails
op als 02:00 en ik ben het sorteren.

38
00:01:30,080 --> 00:01:33,710
Zo niet veroorzaken ik moet kijken
rondom voor uw Pset.

39
00:01:33,710 --> 00:01:34,440
Cool.

40
00:01:34,440 --> 00:01:37,270
>> Ik weet dat het vroeg, maar ik
totaal werd overrompeld

41
00:01:37,270 --> 00:01:40,800
door een essay dat is vanwege deze vrijdag, dat
Mijn docenten waren net als, oh ja.

42
00:01:40,800 --> 00:01:42,550
Vergeet niet, je hebt een
essay verschuldigd op vrijdag.

43
00:01:42,550 --> 00:01:45,780
Dus, ik weet niemand houdt
na te denken over tentamens,

44
00:01:45,780 --> 00:01:50,620
maar uw eerste quiz is op 15 oktober,
die oktober wordt vanaf deze week.

45
00:01:50,620 --> 00:01:53,290
Dus, zou het eerder zijn
dan je verwacht is alles.

46
00:01:53,290 --> 00:01:57,510
Dus dat je niet gegooid off guard wanneer
Ik noem sectie van volgende week dat oh,

47
00:01:57,510 --> 00:02:00,560
je test volgende week, dacht ik
Ik zou je een beetje meer te geven

48
00:02:00,560 --> 00:02:01,500
van een heads up nu.

49
00:02:01,500 --> 00:02:02,970

50
00:02:02,970 --> 00:02:04,660
>> Dus, uw probleem te stellen, nummer drie.

51
00:02:04,660 --> 00:02:07,070
Hoe mensen hebben gelezen de
spec uit nieuwsgierigheid?

52
00:02:07,070 --> 00:02:08,560

53
00:02:08,560 --> 00:02:09,199
OK.

54
00:02:09,199 --> 00:02:10,229
We kregen een paar.

55
00:02:10,229 --> 00:02:12,320
Soort lager dan vorig
week, maar dat is OK.

56
00:02:12,320 --> 00:02:13,650
Ik weet dat het was prachtig uit.

57
00:02:13,650 --> 00:02:15,120

58
00:02:15,120 --> 00:02:16,660
Dus Break Out.

59
00:02:16,660 --> 00:02:21,010
Zeker nadat je gedaan te krijgen
vandaag lees je spec tenminste

60
00:02:21,010 --> 00:02:25,240
proberen, zoals het downloaden
verdeelsleutel en hardlopen

61
00:02:25,240 --> 00:02:27,430
net als de eerste voorletter
ding dat ze je vragen om.

62
00:02:27,430 --> 00:02:28,681

63
00:02:28,681 --> 00:02:32,590
Omdat we gebruik maken
verdeelsleutel en een bibliotheek

64
00:02:32,590 --> 00:02:36,790
dat we alleen using-- --Het is slechts
de tweede keer dat we dit Pset gedaan,

65
00:02:36,790 --> 00:02:38,650
gekke dingen kunnen gebeuren
met uw apparaat,

66
00:02:38,650 --> 00:02:41,370
en je wilt weten dat
out nu versus later.

67
00:02:41,370 --> 00:02:45,570
>> Want als het is donderdagavond of het is
Woensdagavond en om wat voor reden

68
00:02:45,570 --> 00:02:48,912
uw apparaat doet gewoon niet
wilt uitvoeren met de bibliotheek

69
00:02:48,912 --> 00:02:50,620
of de verdeling
code, dat betekent

70
00:02:50,620 --> 00:02:52,309
kun je niet eens beginnen met het doen van de codering.

71
00:02:52,309 --> 00:02:54,100
Want je kunt niet controleren
om te zien of het werkt.

72
00:02:54,100 --> 00:02:55,975
Je niet gaat kunnen
te zien of het compileert.

73
00:02:55,975 --> 00:03:00,500
U wilt de zorg van hen vroeg in te nemen
de week, wanneer je nog steeds kunt e-mail me

74
00:03:00,500 --> 00:03:03,100
of één van de andere TF,
en we kunnen krijgen die vast.

75
00:03:03,100 --> 00:03:05,410
Want dat zijn zaken
die gaan om je te stoppen

76
00:03:05,410 --> 00:03:07,120
van het maken van een echte vooruitgang.

77
00:03:07,120 --> 00:03:10,055
Het is niet als een bug, dat
kun je gewoon een soort van overslaan.

78
00:03:10,055 --> 00:03:10,712

79
00:03:10,712 --> 00:03:13,420
Als u problemen met uw
apparaat of de verdeelsleutel,

80
00:03:13,420 --> 00:03:16,211
je echt wilt krijgen dat genomen
zorg van eerder vroeger dan later.

81
00:03:16,211 --> 00:03:20,410
Dus zelfs als je niet echt Gaat
begin te coderen, te downloaden van de distributie

82
00:03:20,410 --> 00:03:24,040
code, lees de spec, zorg ervoor dat
Alles is er werken.

83
00:03:24,040 --> 00:03:25,134
OK?

84
00:03:25,134 --> 00:03:27,675
Als je dat kan doen, ik
beloof jullie levens zal het makkelijker zijn.

85
00:03:27,675 --> 00:03:28,800

86
00:03:28,800 --> 00:03:31,410
En dus ben je waarschijnlijk gaat
om het nu goed te doen?

87
00:03:31,410 --> 00:03:32,100
OK.

88
00:03:32,100 --> 00:03:33,950
Dus, vragen daar?

89
00:03:33,950 --> 00:03:35,850
Elke logistieke dingen?

90
00:03:35,850 --> 00:03:36,910
Iedereen is goed?

91
00:03:36,910 --> 00:03:38,270
OK.

92
00:03:38,270 --> 00:03:41,700
>> Disclaimer voor die van
u in de kamer en online.

93
00:03:41,700 --> 00:03:45,437
Ik ga proberen om te schakelen
tussen PowerPoint in het toestel

94
00:03:45,437 --> 00:03:47,270
want we gaan
te doen van wat codering

95
00:03:47,270 --> 00:03:53,630
vandaag op veler verzoek van de anonieme
suggestie poll Ik stuurde vorige week.

96
00:03:53,630 --> 00:03:55,480
Dus, zullen we doen wat codering.

97
00:03:55,480 --> 00:03:57,800
Dus, als jullie ook willen
om vuur van uw apparatuur,

98
00:03:57,800 --> 00:04:02,910
en je moet een e-mail hebben gekregen
van mij, met een voorbeeld bestand.

99
00:04:02,910 --> 00:04:04,310
Aarzel dan niet om dat te doen.

100
00:04:04,310 --> 00:04:07,340
>> Dus, we gaan om te praten over
GDB, een debugger.

101
00:04:07,340 --> 00:04:09,970
Het gaat om u te helpen
soort uitzoeken waar

102
00:04:09,970 --> 00:04:11,860
dingen mis gaan in de code.

103
00:04:11,860 --> 00:04:15,370
Het is eigenlijk gewoon een manier voor u om stap
door je code als het gebeurt,

104
00:04:15,370 --> 00:04:19,100
en in staat zijn om uit te printen variabelen
of zien wat er daadwerkelijk gebeurt

105
00:04:19,100 --> 00:04:22,980
onder de motorkap verzen uw programma
alleen rennen, het is net vastgelopen,

106
00:04:22,980 --> 00:04:25,030
en je bent zoals, geen idee
wat hier gebeurde gewoon.

107
00:04:25,030 --> 00:04:26,730
Ik weet niet welke lijn is fout.

108
00:04:26,730 --> 00:04:29,040
Ik weet niet waar het mis ging.

109
00:04:29,040 --> 00:04:31,280
Dus, GDB gaat om u te helpen met dat.

110
00:04:31,280 --> 00:04:35,240
Ook, als u besluit om
verder ja, en neem 61,

111
00:04:35,240 --> 00:04:38,430
het zal echt, echt uw
beste vriend, want ik kan u vertellen

112
00:04:38,430 --> 00:04:40,840
want ik ga door die klasse.

113
00:04:40,840 --> 00:04:43,620
>> We gaan kijken naar binaire
zoeken, die als jullie herinneren

114
00:04:43,620 --> 00:04:47,540
het grote telefoonboek voorbeeld
spektakel van klasse.

115
00:04:47,540 --> 00:04:50,620
We zullen de uitvoering van die, en
wandelen door dat een klein beetje meer,

116
00:04:50,620 --> 00:04:54,650
en dan gaan we door middel van vier
verschillende soorten, die Bubble zijn,

117
00:04:54,650 --> 00:04:56,285
Selectie, Insertion, en samenvoegen.

118
00:04:56,285 --> 00:04:57,830

119
00:04:57,830 --> 00:04:58,330
Cool.

120
00:04:58,330 --> 00:05:00,390
Dus, GDB zoals ik al zei, is een debugger.

121
00:05:00,390 --> 00:05:01,400

122
00:05:01,400 --> 00:05:09,370
En dit zijn soort van de grote
dingen, de grote functies of opdrachten

123
00:05:09,370 --> 00:05:13,240
dat u binnen GDB gebruiken, en ik zal lopen
u door middel van een demo van het in een tweede.

124
00:05:13,240 --> 00:05:15,360
>> Dit is dus niet alleen
ga abstract blijven.

125
00:05:15,360 --> 00:05:18,000
Ik zal proberen en maak het zo concreet
mogelijk te maken voor jullie.

126
00:05:18,000 --> 00:05:19,870
Dus, breken.

127
00:05:19,870 --> 00:05:22,200
Het zal ofwel pauze
zoals, een getal, dat

128
00:05:22,200 --> 00:05:26,900
vertegenwoordigt een lijn in uw programma,
of u kunt een functie noemen.

129
00:05:26,900 --> 00:05:30,150
Dus, als je zegt breken belangrijkste,
het zal stoppen bij de belangrijkste,

130
00:05:30,150 --> 00:05:32,400
en laat je door die functie te lopen.

131
00:05:32,400 --> 00:05:36,350
>> Evenzo, als je een aantal externe
functioneren zoals Swap of Cube,

132
00:05:36,350 --> 00:05:38,450
dat hebben we gekeken naar de afgelopen week.

133
00:05:38,450 --> 00:05:41,780
Als je zegt dat breekt een van die,
wanneer uw programma raakt dat,

134
00:05:41,780 --> 00:05:44,290
het zal wachten tot je
vertellen wat ze moeten doen.

135
00:05:44,290 --> 00:05:47,860
Voordat het net zal uitvoeren, zodat u
eigenlijk kon stappen binnen de functie

136
00:05:47,860 --> 00:05:49,020
en zie wat er gebeurt.

137
00:05:49,020 --> 00:05:50,370

138
00:05:50,370 --> 00:05:53,515
Dus, de volgende, net slaat over de
volgende regel, gaat over functies.

139
00:05:53,515 --> 00:05:54,730

140
00:05:54,730 --> 00:05:55,560
Step.

141
00:05:55,560 --> 00:05:56,810
Dit zijn allemaal kleine abstract.

142
00:05:56,810 --> 00:06:00,530
Dus, ik ben gewoon gaan lopen via hen,
maar zie je ze in gebruik in een tweede.

143
00:06:00,530 --> 00:06:01,810
>> Stap in een functie.

144
00:06:01,810 --> 00:06:04,170
Dus zoals ik al zei,
zoals met Swap, het zou

145
00:06:04,170 --> 00:06:07,110
kunt u eigenlijk alsof je
als fysiek binnenstappen,

146
00:06:07,110 --> 00:06:10,990
je kan knoeien met die variabelen, afdrukken
wat ze zijn, zien wat er gaande is.

147
00:06:10,990 --> 00:06:12,140

148
00:06:12,140 --> 00:06:14,830
Lijst zal letterlijk gewoon uitprinten
uit de omliggende code.

149
00:06:14,830 --> 00:06:17,570
Dus, als je soort vergeten
waar je bent in je programma,

150
00:06:17,570 --> 00:06:19,880
of je je afvraagt
wat er omheen,

151
00:06:19,880 --> 00:06:23,790
dit zal alleen maar afdrukken van een segment
van willen vijf of zes lijnen omheen.

152
00:06:23,790 --> 00:06:26,080
Dus, kun je gericht te krijgen
over waar je bent.

153
00:06:26,080 --> 00:06:27,230

154
00:06:27,230 --> 00:06:28,650
>> Print enkele variabele.

155
00:06:28,650 --> 00:06:34,590
Dus, als je de sleutel als
in Caesar, dat zullen we kijken naar.

156
00:06:34,590 --> 00:06:36,220
U kunt afdrukken Key op elk punt te zeggen.

157
00:06:36,220 --> 00:06:40,070
Het zal u vertellen wat de waarde is zo
dat, misschien ergens langs de weg,

158
00:06:40,070 --> 00:06:42,070
u uw sleutel overschreven.

159
00:06:42,070 --> 00:06:45,495
Je kunt eigenlijk zeggen dat, omdat
je kunt eigenlijk zien dat waarde.

160
00:06:45,495 --> 00:06:46,500

161
00:06:46,500 --> 00:06:48,780
>> In de lokale bevolking, net prints
uw lokale variabelen.

162
00:06:48,780 --> 00:06:53,120
Dus, wanneer je binnen een lus,
en je wil gewoon om te zien, zoals, oh.

163
00:06:53,120 --> 00:06:54,270
Wat is mijn ik?

164
00:06:54,270 --> 00:06:57,020
Wat is deze kernwaarde
dat ik hier te initialiseren?

165
00:06:57,020 --> 00:06:58,537
Wat is de boodschap op dit punt?

166
00:06:58,537 --> 00:07:00,370
Het zal gewoon allemaal af te drukken
van hen, zodat u

167
00:07:00,370 --> 00:07:04,330
niet individueel hoeft te
zeggen, Print I. Print Message.

168
00:07:04,330 --> 00:07:04,970
Print Key.

169
00:07:04,970 --> 00:07:06,190

170
00:07:06,190 --> 00:07:07,700
En vervolgens op Beeldscherm.

171
00:07:07,700 --> 00:07:10,370
Wat dat doet is als je
stap voor stap door het programma,

172
00:07:10,370 --> 00:07:13,980
het zal alleen maar ervoor te zorgen dat het
het weergeven van sommige bepaalde variabele

173
00:07:13,980 --> 00:07:14,780
op elk punt.

174
00:07:14,780 --> 00:07:17,160
Zodat u also-- --Het is
soort van een snelkoppeling waar

175
00:07:17,160 --> 00:07:19,530
je hoeft niet te blijven gaan zoals, oh.

176
00:07:19,530 --> 00:07:23,150
Print Key of Print I. Het net
zal automatisch het voor je doen.

177
00:07:23,150 --> 00:07:25,959
>> Dus, met dat, we gaan
om te zien hoe dit gaat.

178
00:07:25,959 --> 00:07:28,000
Ik ga proberen en switch
naar mijn toestel.

179
00:07:28,000 --> 00:07:30,200

180
00:07:30,200 --> 00:07:31,271
Kijken of ik dit kan doen.

181
00:07:31,271 --> 00:07:31,770
All.

182
00:07:31,770 --> 00:07:40,970

183
00:07:40,970 --> 00:07:42,370
We gaan gewoon om het te spiegelen.

184
00:07:42,370 --> 00:07:44,530
Er is niets gek
op mijn laptop anyways.

185
00:07:44,530 --> 00:07:49,600

186
00:07:49,600 --> 00:07:50,100
OK.

187
00:07:50,100 --> 00:07:57,030

188
00:07:57,030 --> 00:08:01,054
Dit moet deze.

189
00:08:01,054 --> 00:08:01,795
Het is zo klein.

190
00:08:01,795 --> 00:08:03,730

191
00:08:03,730 --> 00:08:05,120
Laten we eens kijken of we dit kunnen doen.

192
00:08:05,120 --> 00:08:09,970

193
00:08:09,970 --> 00:08:10,940
>> OK.

194
00:08:10,940 --> 00:08:15,305
Alice is uiteraard worstelen
hier maar een klein beetje,

195
00:08:15,305 --> 00:08:17,995
maar we zullen het krijgen in een momento.

196
00:08:17,995 --> 00:08:20,810

197
00:08:20,810 --> 00:08:22,020
OK.

198
00:08:22,020 --> 00:08:25,900
We gaan enkel deze te verhogen.

199
00:08:25,900 --> 00:08:28,770

200
00:08:28,770 --> 00:08:29,380
OK.

201
00:08:29,380 --> 00:08:31,679
Kan iedereen soort dat gezien?

202
00:08:31,679 --> 00:08:32,470
Misschien een klein beetje?

203
00:08:32,470 --> 00:08:33,594
Ik weet dat het een beetje klein.

204
00:08:33,594 --> 00:08:34,570

205
00:08:34,570 --> 00:08:37,530
Je kan niet helemaal achterhalen
hoe deze groter te maken.

206
00:08:37,530 --> 00:08:38,350
Als iemand weet.

207
00:08:38,350 --> 00:08:40,309
Weet iemand hoe je het groter te maken?

208
00:08:40,309 --> 00:08:40,932
OK.

209
00:08:40,932 --> 00:08:42,140
We gaan om te rollen met het.

210
00:08:42,140 --> 00:08:45,801
Heeft anyways niet uit want het is gewoon
dat is de code die jullie moeten

211
00:08:45,801 --> 00:08:46,300
hebben.

212
00:08:46,300 --> 00:08:48,310
>> Wat is belangrijker
is de terminal hier.

213
00:08:48,310 --> 00:08:52,840

214
00:08:52,840 --> 00:08:58,690
En we hebben hier Waarom is het zo klein?

215
00:08:58,690 --> 00:09:02,325

216
00:09:02,325 --> 00:09:02,825
Instellingen.

217
00:09:02,825 --> 00:09:07,920

218
00:09:07,920 --> 00:09:08,420
Oh.

219
00:09:08,420 --> 00:09:09,500
True Ike.

220
00:09:09,500 --> 00:09:10,880
Hoe is dit?

221
00:09:10,880 --> 00:09:11,770
Daar weg.

222
00:09:11,770 --> 00:09:19,370

223
00:09:19,370 --> 00:09:21,810
Is dat beter voor iedereen?

224
00:09:21,810 --> 00:09:22,525
OK ,.

225
00:09:22,525 --> 00:09:23,025
Cool.

226
00:09:23,025 --> 00:09:25,830

227
00:09:25,830 --> 00:09:28,220
>> Je weet dat wanneer je in een CS
class technische problemen

228
00:09:28,220 --> 00:09:32,971
zijn een soort van een deel van the--
Dus, laten we dit te wissen.

229
00:09:32,971 --> 00:09:33,470
OK.

230
00:09:33,470 --> 00:09:38,060
Dus, hier in doorsnede,
die we hier hadden.

231
00:09:38,060 --> 00:09:40,830
Caesar is een uitvoerbaar bestand.

232
00:09:40,830 --> 00:09:41,800
Dus ik maakte het.

233
00:09:41,800 --> 00:09:46,370
Dus, een ding om te beseffen met GDB is
dat het werkt alleen uitvoerbare bestanden.

234
00:09:46,370 --> 00:09:48,040
Dus, kun je niet draaien op een Dotsy.

235
00:09:48,040 --> 00:09:50,532
Je moet eigenlijk maken
zeker van zijn dat je code compileert,

236
00:09:50,532 --> 00:09:51,865
en dat daadwerkelijk kan worden uitgevoerd.

237
00:09:51,865 --> 00:09:52,970

238
00:09:52,970 --> 00:09:56,186
>> Dus, zorg ervoor dat als het niet
compileren, krijgen om te compileren,

239
00:09:56,186 --> 00:09:57,810
zodat u kunt soort er doorheen lopen.

240
00:09:57,810 --> 00:10:04,590
Dus, om GDB beginnen, alles wat je doet,
Gloria soort GDB, en dan gewoon de

241
00:10:04,590 --> 00:10:06,250
bestand dat u wilt.

242
00:10:06,250 --> 00:10:08,240
Ik misspell altijd Caesar.

243
00:10:08,240 --> 00:10:11,730
Maar je wilt er zeker van
want het is een uitvoerbaar,

244
00:10:11,730 --> 00:10:14,210
dot flash ti's zodat
betekent dat je gaat

245
00:10:14,210 --> 00:10:19,240
te lopen CSI je gaat om uit te voeren
deze bestanden ofwel met de debugger.

246
00:10:19,240 --> 00:10:19,910
OK.

247
00:10:19,910 --> 00:10:22,885
Dus, heb je dat, dan krijg je
dit soort onzin.

248
00:10:22,885 --> 00:10:24,250

249
00:10:24,250 --> 00:10:25,750
Het is gewoon allemaal dingen over debugger.

250
00:10:25,750 --> 00:10:28,200
Je hoeft niet echt te
zorgen te maken over het nu.

251
00:10:28,200 --> 00:10:31,460
En zoals je ziet, hebben we dit
geopend parens, BBP, dicht parens,

252
00:10:31,460 --> 00:10:34,690
en gewoon een soort eruit ziet
onze command line, toch?

253
00:10:34,690 --> 00:10:37,010
>> Dus, wat we willen doen--
-SO, Het eerste wat

254
00:10:37,010 --> 00:10:39,570
is dat we willen kiezen
een plek om het te breken.

255
00:10:39,570 --> 00:10:42,332
Er is dus een bug
in deze Caesar programma

256
00:10:42,332 --> 00:10:44,290
dat ik te introduceren, dat
we gaan om uit te vinden.

257
00:10:44,290 --> 00:10:45,330

258
00:10:45,330 --> 00:10:56,350
Het Wat het wel is duurt de input
Barfoo in hoofdletters, en om wat voor reden

259
00:10:56,350 --> 00:11:01,950
het niet A. veranderen Het laat gewoon
het alleen, Klopt alles anders,

260
00:11:01,950 --> 00:11:03,980
maar de tweede letter
Een ongewijzigd.

261
00:11:03,980 --> 00:11:07,120
Dus, we gaan proberen
erachter te komen waarom dat zo is.

262
00:11:07,120 --> 00:11:10,440
Dus, het eerste wat je meestal
wilt doen wanneer je begint op GDB

263
00:11:10,440 --> 00:11:12,010
is erachter te komen waar het te breken.

264
00:11:12,010 --> 00:11:14,956
>> Dus Caesar is een vrij kort programma.

265
00:11:14,956 --> 00:11:16,330
We hebben slechts één functie, toch?

266
00:11:16,330 --> 00:11:18,520
Wat was onze functie in Caesar?

267
00:11:18,520 --> 00:11:19,590

268
00:11:19,590 --> 00:11:24,350
Er is maar één functie, Main toch?

269
00:11:24,350 --> 00:11:26,490
Belangrijkste is een functie
voor al uw programma's.

270
00:11:26,490 --> 00:11:29,230
Als je niet hoefde Main, zou ik
zijn een beetje ongerust nu,

271
00:11:29,230 --> 00:11:31,000
maar ik hoop dat jullie allemaal Hoofd gehad daar.

272
00:11:31,000 --> 00:11:34,150
Dus, wat we kunnen doen is dat we kunnen
gewoon breken Main, net als dat.

273
00:11:34,150 --> 00:11:35,190
Dus, zegt het, OK.

274
00:11:35,190 --> 00:11:37,430
We zetten onze breekpunt één daar.

275
00:11:37,430 --> 00:11:42,870
>> Zo, nu het ding om te onthouden is Caesar
duurt een command line argument rechts

276
00:11:42,870 --> 00:11:45,150
en we hebben nog ergens dat niet gedaan.

277
00:11:45,150 --> 00:11:47,560
Dus, wat je doet is wanneer
u ook daadwerkelijk te gaan uitvoeren

278
00:11:47,560 --> 00:11:51,540
het programma, een programma dat je bent
lopen in GDB dat opdrachtregel nodig

279
00:11:51,540 --> 00:11:55,010
argumenten, je gaat om input
wanneer u voor het eerst begint te lopen is.

280
00:11:55,010 --> 00:11:59,280
Dus, in dit geval, doen wij
Draaien met een sleutel van de drie.

281
00:11:59,280 --> 00:12:00,770

282
00:12:00,770 --> 00:12:02,040
En het zal daadwerkelijk beginnen.

283
00:12:02,040 --> 00:12:08,480
>> Dus, als je hier ziet, hebben wij
Als RC niet gelijk is aan 2.

284
00:12:08,480 --> 00:12:12,210
Dus als jullie nog allemaal
dat bestand dat ik stuurde up

285
00:12:12,210 --> 00:12:15,100
je zult zien dat dat is net als de
eerste regel van onze belangrijkste functie, toch?

286
00:12:15,100 --> 00:12:17,890
Het is te controleren om te zien of we hebben
het juiste aantal argumenten.

287
00:12:17,890 --> 00:12:20,620
Dus, als je je afvraagt
Als RC juist is,

288
00:12:20,620 --> 00:12:23,250
kun je iets net zoals Print RC doen.

289
00:12:23,250 --> 00:12:24,380

290
00:12:24,380 --> 00:12:28,640
RC is twee, wat
wat we hadden verwacht, toch?

291
00:12:28,640 --> 00:12:32,010
>> Dus, kunnen we gaan Next,
en verder door.

292
00:12:32,010 --> 00:12:33,200
Dus, we hebben een aantal belangrijke daar.

293
00:12:33,200 --> 00:12:34,260

294
00:12:34,260 --> 00:12:37,090
En we kunnen onze key uitprinten
om ervoor te zorgen dat klopt.

295
00:12:37,090 --> 00:12:38,380

296
00:12:38,380 --> 00:12:39,500
Interessant.

297
00:12:39,500 --> 00:12:41,210
Niet helemaal wat we verwacht hadden.

298
00:12:41,210 --> 00:12:44,810
Dus, een ding om te beseffen
met GDB ook is

299
00:12:44,810 --> 00:12:49,000
dat het niet tot u eigenlijk hit
Vervolgens, dat de lijn die je net zag

300
00:12:49,000 --> 00:12:50,720
wordt daadwerkelijk uitgevoerd.

301
00:12:50,720 --> 00:12:53,870
Dus, in dit geval Key
is nog niet toegewezen.

302
00:12:53,870 --> 00:12:57,050
Dus, Key is garbage waarde
dat zie je op de bodem daar.

303
00:12:57,050 --> 00:13:03,680
Negatieve $ 120-- --Het's een miljard
en iets wat vreemde dingen toch?

304
00:13:03,680 --> 00:13:05,340
Het is niet de sleutel die we verwacht hadden.

305
00:13:05,340 --> 00:13:10,720
Maar als we hit Volgende en we
proberen en Print-toets, het is drie.

306
00:13:10,720 --> 00:13:11,710
>> Iedereen ziet dat?

307
00:13:11,710 --> 00:13:13,780
Dus, als je iets te krijgen
dat je net als, wacht.

308
00:13:13,780 --> 00:13:15,540
Dit is volkomen
verkeerd, en ik weet het niet

309
00:13:15,540 --> 00:13:20,150
hoe dit zou gebeuren, want alles wat ik wil
te doen is een nummer, een variabele,

310
00:13:20,150 --> 00:13:22,900
proberen te raken Vervolgens probeer af te drukken
het weer, en kijk of dat werkt.

311
00:13:22,900 --> 00:13:27,830
Want het gaat alleen om uit te voeren en
eigenlijk na je iets toe te wijzen

312
00:13:27,830 --> 00:13:29,340
hit Volgende.

313
00:13:29,340 --> 00:13:30,336
Zinvol zijn voor iedereen?

314
00:13:30,336 --> 00:13:30,836
Uh huh?

315
00:13:30,836 --> 00:13:33,220
>> SPEAKER 2: Wanneer u willekeurig
nummers wat betekent dat?

316
00:13:33,220 --> 00:13:34,790
>> SPEAKER 1: Het is gewoon willekeurig.

317
00:13:34,790 --> 00:13:35,710
Het is gewoon afval.

318
00:13:35,710 --> 00:13:38,320
Het is gewoon iets dat je
computer zal willekeurig toe te wijzen.

319
00:13:38,320 --> 00:13:39,721

320
00:13:39,721 --> 00:13:40,220
Cool.

321
00:13:40,220 --> 00:13:45,760
Zo, nu kunnen we door middel van bewegen, en dus
nu hebben we deze platte tekst GetString.

322
00:13:45,760 --> 00:13:48,600
Dus, laat me introduceren wat
zal gebeuren wanneer we hit Volgende hier.

323
00:13:48,600 --> 00:13:51,320
Onze GDB soort verdwijnt, toch?

324
00:13:51,320 --> 00:13:55,720
Dat komt omdat GetString
wordt nu uitvoeren, toch?

325
00:13:55,720 --> 00:14:01,460
Dus, toen we zagen platte tekst is gelijk aan
GetString open parens en parens,

326
00:14:01,460 --> 00:14:04,380
en we raken Next, dat heeft
nu daadwerkelijk zijn uitgevoerd.

327
00:14:04,380 --> 00:14:06,580
Dus, het is het wachten op
ons invoer iets.

328
00:14:06,580 --> 00:14:13,560
>> Dus, we gaan om input ons eten die
is wat het is niet zoals ik het u gezegd

329
00:14:13,560 --> 00:14:18,020
en dat alleen maar zegt dat het
afgewerkt uitvoeren, dat de gesloten

330
00:14:18,020 --> 00:14:19,980
beugel betekent dat het
verlaten uit die lus.

331
00:14:19,980 --> 00:14:21,170

332
00:14:21,170 --> 00:14:25,420
Dus, kunnen we hit Volgende, en nu, zoals ik ben
ervoor dat je zijn allemaal bekend van Caesar,

333
00:14:25,420 --> 00:14:27,260
Dit is, wat is deze lijn gaan doen.

334
00:14:27,260 --> 00:14:32,030
Het is voor Int I gelijk is aan 0, N gelijk
Strlen, platte tekst, en dan

335
00:14:32,030 --> 00:14:33,960
I is kleiner dan n, I, plus, plus.

336
00:14:33,960 --> 00:14:35,210
Wat is deze lus gaat doen?

337
00:14:35,210 --> 00:14:37,900

338
00:14:37,900 --> 00:14:39,160
Open uw bericht.

339
00:14:39,160 --> 00:14:39,770
Cool.

340
00:14:39,770 --> 00:14:41,330
Dus, laten we beginnen met dat te doen.

341
00:14:41,330 --> 00:14:47,210
>> Dus, moet deze voorwaarde
overeenkomen, voor onze eerste?

342
00:14:47,210 --> 00:14:52,250
Als het een B, het is platte tekst I. We
u informatie over onze lokale bevolking te krijgen.

343
00:14:52,250 --> 00:14:53,610

344
00:14:53,610 --> 00:14:57,970
Dus, I nul en indien zes die
we verwachten, en onze sleutel is drie.

345
00:14:57,970 --> 00:14:59,227
Al die zin te maken, toch?

346
00:14:59,227 --> 00:15:01,310
Die alle cijfers
precies wat ze moeten zijn.

347
00:15:01,310 --> 00:15:02,590

348
00:15:02,590 --> 00:15:03,870
Dus, neuriën?

349
00:15:03,870 --> 00:15:05,620
SPEAKER 3: Ik heb
willekeurige getallen voor de mijne.

350
00:15:05,620 --> 00:15:09,156

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: Nou, we kunnen --we check--
kunnen chatten over dat in een tweede.

352
00:15:12,030 --> 00:15:14,110

353
00:15:14,110 --> 00:15:15,750
Maar je moet het krijgen van deze.

354
00:15:15,750 --> 00:15:17,700

355
00:15:17,700 --> 00:15:20,130
Dus, als we een hoofdstad
B onze eerste,

356
00:15:20,130 --> 00:15:22,080
deze voorwaarde moet vangen, toch?

357
00:15:22,080 --> 00:15:27,120
Dus, als we geraakt Vervolgens zien we
dat dit Als daadwerkelijk uitvoert.

358
00:15:27,120 --> 00:15:29,220
Want als je na
langs in de code,

359
00:15:29,220 --> 00:15:33,460
deze lijn hier, waar platte tekst I
wordt vervangen door deze rekenkundige,

360
00:15:33,460 --> 00:15:35,720
alleen uitgevoerd wanneer de If
Voorwaarde is juist toch?

361
00:15:35,720 --> 00:15:36,905

362
00:15:36,905 --> 00:15:40,240
>> GDB is alleen maar om te laten zien
dingen die daadwerkelijk worden uitgevoerd.

363
00:15:40,240 --> 00:15:45,140
Dus als dit Als voorwaarde niet is voldaan, is het
gewoon om naar de volgende regel.

364
00:15:45,140 --> 00:15:46,540
OK?

365
00:15:46,540 --> 00:15:48,510
Dus, we hebben dat.

366
00:15:48,510 --> 00:15:51,171
Deze beugel betekent dat het
gesloten uit die lus nu.

367
00:15:51,171 --> 00:15:52,420
Dus, het gaat om opnieuw te beginnen.

368
00:15:52,420 --> 00:15:54,760

369
00:15:54,760 --> 00:15:56,280
Net als dat.

370
00:15:56,280 --> 00:15:59,120
Dus, dat we informatie kunnen krijgen
over onze locals hier,

371
00:15:59,120 --> 00:16:02,575
en we zien dat onze eerste
brief is veranderd, toch?

372
00:16:02,575 --> 00:16:05,150
Het is nu een E, zoals het hoort.

373
00:16:05,150 --> 00:16:07,360
Dus, kunnen we verder.

374
00:16:07,360 --> 00:16:08,500
>> En we hebben deze controle.

375
00:16:08,500 --> 00:16:09,916
En deze controle zou moeten werken, toch?

376
00:16:09,916 --> 00:16:12,570
Het is A. Er wordt gewijzigd
drie brieven naar voren.

377
00:16:12,570 --> 00:16:14,320

378
00:16:14,320 --> 00:16:16,530
Maar als je merkt, we
krijg je iets anders.

379
00:16:16,530 --> 00:16:17,580

380
00:16:17,580 --> 00:16:22,860
Dus in dit geval hier, het gevangen
het, en dus is deze lijn uitgevoerd,

381
00:16:22,860 --> 00:16:28,620
die onze B. gemodificeerd
Maar hier casu

382
00:16:28,620 --> 00:16:32,860
we hebben dat het gewoon overgeslagen,
en ging naar de [? L siff. ?]

383
00:16:32,860 --> 00:16:34,660
Dus iets aan de hand is daar.

384
00:16:34,660 --> 00:16:37,780
Wat dat vertelt je dat,
we weten dat het hier zou moeten vangen,

385
00:16:37,780 --> 00:16:39,200
maar het is niet.

386
00:16:39,200 --> 00:16:42,210
Kan iedereen zien wat onze
probleem is in die lijn?

387
00:16:42,210 --> 00:16:45,380

388
00:16:45,380 --> 00:16:46,969
Het is een zeer minute ding.

389
00:16:46,969 --> 00:16:48,510
En je zou ook kunnen kijken naar uw code.

390
00:16:48,510 --> 00:16:49,980

391
00:16:49,980 --> 00:16:54,940
Het is ook line-- vergeten welke lijn het is
in er-- maar het is in de [onverstaanbaar].

392
00:16:54,940 --> 00:16:55,480
Ja?

393
00:16:55,480 --> 00:16:58,639
>> SPEAKER 4: Het is op de meer dan
pagina als je het gelezen in het boek.

394
00:16:58,639 --> 00:16:59,430
SPEAKER 1: Precies.

395
00:16:59,430 --> 00:17:02,620
Ja, kan de debugger niet vertellen
je dat, maar de debugger

396
00:17:02,620 --> 00:17:05,880
kon u neer op een lijn
waarvan u weet dat niet functioneert.

397
00:17:05,880 --> 00:17:09,319
En soms, als bijzonder
later in het semester, toen

398
00:17:09,319 --> 00:17:12,910
je te maken hebt met een honderdtal, een
honderd paar regels code, en je

399
00:17:12,910 --> 00:17:16,190
weet niet waar het is niet,
dit is een geweldige manier om het te doen.

400
00:17:16,190 --> 00:17:17,900

401
00:17:17,900 --> 00:17:18,989
Dus vonden we onze bug.

402
00:17:18,989 --> 00:17:21,530
U kunt het probleem te verhelpen in uw bestand,
en dan kon je weer lopen,

403
00:17:21,530 --> 00:17:23,029
en alles zou perfect werken.

404
00:17:23,029 --> 00:17:24,970

405
00:17:24,970 --> 00:17:30,590
En het grootste ding is
Dit kan lijken, OK.

406
00:17:30,590 --> 00:17:31,090
Yeah.

407
00:17:31,090 --> 00:17:31,370
Cool.

408
00:17:31,370 --> 00:17:32,744
Je wist wat je zoekt.

409
00:17:32,744 --> 00:17:34,910
Dus, je wist wat te doen.

410
00:17:34,910 --> 00:17:39,021
>> GDB kan zijn super handig omdat je
kunnen al deze dingen uit te printen die je

411
00:17:39,021 --> 00:17:39,520
zou niet.

412
00:17:39,520 --> 00:17:41,160
Het is veel nuttiger dan printf.

413
00:17:41,160 --> 00:17:43,440
Hoeveel van jullie gebruiken
zoals printf statements

414
00:17:43,440 --> 00:17:46,200
om erachter te komen waar een bug was, toch?

415
00:17:46,200 --> 00:17:48,450
Dus, met dit, je doet niet
moeten terug gaan houden,

416
00:17:48,450 --> 00:17:51,139
en graag commentaar in
Printf, of commentaar uit,

417
00:17:51,139 --> 00:17:52,930
en erachter te komen wat
moet u het afdrukken.

418
00:17:52,930 --> 00:17:55,670
Dit eigenlijk alleen maar kunt u
stap door een afdruk van de dingen

419
00:17:55,670 --> 00:18:00,000
als je gaat door, zo kunt u
observeren hoe ze veranderen in real-time,

420
00:18:00,000 --> 00:18:02,190
als je programma draait.

421
00:18:02,190 --> 00:18:04,390
>> En het vergt wel een beetje
beetje wennen.

422
00:18:04,390 --> 00:18:07,850
Ik zou gewoon een soort bevelen
van het zijn een beetje gefrustreerd met het

423
00:18:07,850 --> 00:18:08,930
voor nu.

424
00:18:08,930 --> 00:18:13,450
Als je een uurtje over de
volgende week leren hoe te GDB gebruiken,

425
00:18:13,450 --> 00:18:16,140
je bespaart jezelf
zoveel tijd later.

426
00:18:16,140 --> 00:18:18,750
En letterlijk. we vertellen
Dit om mensen per jaar,

427
00:18:18,750 --> 00:18:23,890
en ik herinner me toen ik de
klasse, was ik net, ik zal wel goed zijn.

428
00:18:23,890 --> 00:18:24,700
Nee

429
00:18:24,700 --> 00:18:27,030
Pset 6 kwam op en ik was
als, ik ga leren

430
00:18:27,030 --> 00:18:29,500
hoe GDB gebruiken omdat ik niet
weten wat er aan de hand hier.

431
00:18:29,500 --> 00:18:32,940
>> Dus als je de tijd dus neem
gebruik het op kleinere programma's

432
00:18:32,940 --> 00:18:35,697
dat je gaat om te zijn
werken aan, zoals het werken

433
00:18:35,697 --> 00:18:37,530
door iets als
Visionare, zoals deze.

434
00:18:37,530 --> 00:18:38,800

435
00:18:38,800 --> 00:18:42,850
Of als u extra oefening wilt, ik ben er zeker van
Ik kon komen met buggy's,

436
00:18:42,850 --> 00:18:45,300
voor u om te debuggen als je wilt.

437
00:18:45,300 --> 00:18:49,300
>> Maar als je gewoon wat tijd nemen om te krijgen
aan gewend, net om te spelen met het,

438
00:18:49,300 --> 00:18:50,550
het zal je echt goed van dienst zijn.

439
00:18:50,550 --> 00:18:52,591
En het is echt een van
die dingen die je gewoon

440
00:18:52,591 --> 00:18:57,340
moeten proberen, en krijg je handen vuil
met, voordat je echt begrijpen.

441
00:18:57,340 --> 00:19:02,090
Ik begreep het pas een keer
Ik moest debug dingen mee,

442
00:19:02,090 --> 00:19:08,170
en het is veel leuker om een ​​idee te hebben
hoe eerder vroeger dan later te debuggen.

443
00:19:08,170 --> 00:19:08,850
OK.

444
00:19:08,850 --> 00:19:09,625
Cool.

445
00:19:09,625 --> 00:19:12,960
Ik weet dat is een soort van
een spoedcursus in GDB,

446
00:19:12,960 --> 00:19:16,400
en ik zal zeker werken aan het verkrijgen van
deze groter volgende keer kijken.

447
00:19:16,400 --> 00:19:17,590

448
00:19:17,590 --> 00:19:18,280
Cool.

449
00:19:18,280 --> 00:19:20,390
>> Dus, als we terug gaan naar onze PowerPoint.

450
00:19:20,390 --> 00:19:27,194

451
00:19:27,194 --> 00:19:28,110
Gaat dit werken?

452
00:19:28,110 --> 00:19:29,711

453
00:19:29,711 --> 00:19:30,210
AWH.

454
00:19:30,210 --> 00:19:31,101
Ja.

455
00:19:31,101 --> 00:19:31,600
OK.

456
00:19:31,600 --> 00:19:35,480
Dus, als je ooit een van nodig
die weer is er de lijst.

457
00:19:35,480 --> 00:19:37,160

458
00:19:37,160 --> 00:19:40,830
Dus Binary Search, waarbij iedereen
herinnert zich de grote spektakel van David

459
00:19:40,830 --> 00:19:42,259
rippen telefoonboeken doormidden.

460
00:19:42,259 --> 00:19:44,050
Ik heb niet echt het
telefoon boeken meer,

461
00:19:44,050 --> 00:19:46,530
want zoals waar moet je
krijgen de telefoon boeken deze dagen?

462
00:19:46,530 --> 00:19:48,220
Ik weet het echt niet.

463
00:19:48,220 --> 00:19:49,840

464
00:19:49,840 --> 00:19:50,590
De Binary Search.

465
00:19:50,590 --> 00:19:52,464
Herinnert iemand zich
hoe Binary Search werkt?

466
00:19:52,464 --> 00:19:54,380

467
00:19:54,380 --> 00:19:55,220
Wie dan ook?

468
00:19:55,220 --> 00:19:56,325
Yeah?

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: Je weet wanneer
je kijkt naar waar de helft

470
00:19:58,283 --> 00:20:01,146
het in zou zijn, op basis van dat,
en zich te ontdoen van de andere helft.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER 1 Precies.

472
00:20:01,896 --> 00:20:06,290
Dus, Binary Search, het is een soort van a--
--we graag noemen het verdeel en heers.

473
00:20:06,290 --> 00:20:09,170
Dus, wat je zult doen is
je kijkt in het midden,

474
00:20:09,170 --> 00:20:11,990
en je zult zien of het overeenkomt
wat u zoekt.

475
00:20:11,990 --> 00:20:15,420
En als dat niet het geval, dan probeer je
erachter te komen, het gaat om te worden overgelaten

476
00:20:15,420 --> 00:20:16,450
de helft of de rechter helft.

477
00:20:16,450 --> 00:20:19,325
Dus, zou dit zijn als u op zoek bent
naar iets dat is gealfabetiseerd,

478
00:20:19,325 --> 00:20:20,720
zie je, oh.

479
00:20:20,720 --> 00:20:22,750
Heeft Allison komt voor M?

480
00:20:22,750 --> 00:20:23,250
Ja.

481
00:20:23,250 --> 00:20:25,030
Dus, we gaan
kijk naar de eerste helft.

482
00:20:25,030 --> 00:20:26,450
>> Of het kan worden als met getallen.

483
00:20:26,450 --> 00:20:28,830
Alles wat je kunt
vergelijken, kan worden gesorteerd.

484
00:20:28,830 --> 00:20:29,920

485
00:20:29,920 --> 00:20:31,260
U kunt binaire zoekopdracht op te gebruiken.

486
00:20:31,260 --> 00:20:32,340

487
00:20:32,340 --> 00:20:37,455
Dus, iedereen die dit niet vergeten
grafiek of wat dit is?

488
00:20:37,455 --> 00:20:39,520
Het is Asymptotische Complexiteit.

489
00:20:39,520 --> 00:20:42,830
Dus, deze grafiek net
beschrijft hoe lang het

490
00:20:42,830 --> 00:20:46,230
neemt je mee naar een probleem op te lossen als
u het aantal dingen te verhogen

491
00:20:46,230 --> 00:20:47,090
dat u gebruikt.

492
00:20:47,090 --> 00:20:51,260
>> We hebben dus N is lineaire tijd.

493
00:20:51,260 --> 00:20:54,560
Als N over twee, die enigszins is
beter, nog steeds groeit super snel.

494
00:20:54,560 --> 00:20:58,360
En dan hebben we inloggen, dat is
wat wij als Binary Search.

495
00:20:58,360 --> 00:21:03,630
Als we merken, als je probleem
krijgt veel en veel groter,

496
00:21:03,630 --> 00:21:06,600
de tijd die het u kost om het op te lossen
niet echt te verhogen dat veel.

497
00:21:06,600 --> 00:21:09,010
Het is net als vergelijkbare
hier in het begin.

498
00:21:09,010 --> 00:21:10,060
Je bent net, OK.

499
00:21:10,060 --> 00:21:13,000
Alles wat hier niet echt
uit welke we gebruiken,

500
00:21:13,000 --> 00:21:16,220
maar je uit tot een miljoen, een miljard.

501
00:21:16,220 --> 00:21:20,010
Je probeert some-- --you're vinden
proberen om een ​​naald in een hooiberg te vinden.

502
00:21:20,010 --> 00:21:21,550
>> Ik denk dat je dit probleem wilt.

503
00:21:21,550 --> 00:21:25,850
U wilt deze complexiteit niet
lineair, want voor alles wat je

504
00:21:25,850 --> 00:21:30,049
weet je gaat wel op zoek door middel van
elke individuele naald, ding van hooi,

505
00:21:30,049 --> 00:21:31,340
proberen te kijken voor je naald.

506
00:21:31,340 --> 00:21:34,730
En dat is niet zo leuk in mijn mening.

507
00:21:34,730 --> 00:21:35,500
Ik hou van snel.

508
00:21:35,500 --> 00:21:36,620
Ik hou van efficiënt.

509
00:21:36,620 --> 00:21:40,450
En als hardwerkende studenten je
jongens zijn, weet je slimmer werken,

510
00:21:40,450 --> 00:21:43,010
niet harder soort ding, hoe je
kunnen maken van deze algoritmen.

511
00:21:43,010 --> 00:21:45,110

512
00:21:45,110 --> 00:21:47,910
>> Dus, we gaan wandelen
door slechts een snel voorbeeld.

513
00:21:47,910 --> 00:21:51,090
Ik denk dat jullie moeten hebben
een hand op Binary Search,

514
00:21:51,090 --> 00:21:54,352
maar in het geval iemand is een beetje
fuzzy, willen versterken,

515
00:21:54,352 --> 00:21:56,310
we gaan gewoon gaan
door middel van een voorbeeld hier.

516
00:21:56,310 --> 00:21:59,490
Dus zijn we op zoek naar als
de array bevat zeven.

517
00:21:59,490 --> 00:22:00,540

518
00:22:00,540 --> 00:22:06,010
>> Dus, het eerste wat we doen is
kijk in het midden, toch?

519
00:22:06,010 --> 00:22:09,340
En ook dat je gaat worden codering
Binary Zoek in slechts een seconde.

520
00:22:09,340 --> 00:22:11,310
Dus het gaat leuk worden.

521
00:22:11,310 --> 00:22:13,710
Dus we kijken in de
midden kleine arrays 3.

522
00:22:13,710 --> 00:22:15,501
Heeft 3 gelijk 7?

523
00:22:15,501 --> 00:22:16,000
Doet dat niet.

524
00:22:16,000 --> 00:22:18,670

525
00:22:18,670 --> 00:22:19,550
Het is zes.

526
00:22:19,550 --> 00:22:21,480
Dus, is het minder dan
of meer dan zeven?

527
00:22:21,480 --> 00:22:23,080

528
00:22:23,080 --> 00:22:23,960
Minder dan.

529
00:22:23,960 --> 00:22:24,570
Ja.

530
00:22:24,570 --> 00:22:25,170
Nice job guys.

531
00:22:25,170 --> 00:22:25,569

532
00:22:25,569 --> 00:22:27,360
Ik voel Graag zou
hebben snoep omdat ik

533
00:22:27,360 --> 00:22:29,460
willen het uit te gooien in de werven.

534
00:22:29,460 --> 00:22:30,270
Het is wat ik ga volgende week doen.

535
00:22:30,270 --> 00:22:31,436
Het houdt je jongens scherp.

536
00:22:31,436 --> 00:22:32,560

537
00:22:32,560 --> 00:22:34,690
>> Dus, gooien we weg, dat
eerste helft, toch?

538
00:22:34,690 --> 00:22:35,670
het was minder dan.

539
00:22:35,670 --> 00:22:39,325
we weten dat alles
op die linkerkant

540
00:22:39,325 --> 00:22:41,700
zal minder zijn dan wat
we zijn eigenlijk op zoek naar.

541
00:22:41,700 --> 00:22:43,491
Dus, er is geen noodzaak om
aandacht aan te besteden.

542
00:22:43,491 --> 00:22:45,120
Vergeet het dan maar.

543
00:22:45,120 --> 00:22:48,720
Zo, nu kijken we naar onze rechterhand,
en we kijken naar het midden daar,

544
00:22:48,720 --> 00:22:50,510
en nu is het negen.

545
00:22:50,510 --> 00:22:55,510
Dus, 9 is-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
Groter dan wat we
op zoek naar, toch?

547
00:22:57,470 --> 00:22:59,860
Dus, we gaan gooien
alles weg naar rechts.

548
00:22:59,860 --> 00:23:00,970

549
00:23:00,970 --> 00:23:01,940
Als dat.

550
00:23:01,940 --> 00:23:03,700
Nu, zijn allemaal vertrokken we met één.

551
00:23:03,700 --> 00:23:07,760
Dus we controleren, is dit een wat
we zoeken? is.

552
00:23:07,760 --> 00:23:08,970
We vonden wat we wilden.

553
00:23:08,970 --> 00:23:10,440

554
00:23:10,440 --> 00:23:11,690
Dus we zijn klaar.

555
00:23:11,690 --> 00:23:12,550
Bilineaire Search.

556
00:23:12,550 --> 00:23:15,740
>> En als u merkt, we
had zeven ingangen daar.

557
00:23:15,740 --> 00:23:24,320
Het kostte ons slechts als drie keer,
maar als je aan het doen bent als een miljard,

558
00:23:24,320 --> 00:23:28,190
jullie weten hoeveel stappen het zou
nemen als we hadden 4000000000 dingen?

559
00:23:28,190 --> 00:23:29,940

560
00:23:29,940 --> 00:23:30,455
Elke gissingen?

561
00:23:30,455 --> 00:23:32,286

562
00:23:32,286 --> 00:23:33,960
Het is 32.

563
00:23:33,960 --> 00:23:37,110
32 stappen om iets te vinden
in een 4000000000

564
00:23:37,110 --> 00:23:39,650
element scala vanwege machten van twee.

565
00:23:39,650 --> 00:23:43,550
Dus twee om 32 is vier miljard dollar.

566
00:23:43,550 --> 00:23:50,430
>> Dus behoorlijk gek hoe je bent nog steeds binnen
als een vrij klein aantal stappen

567
00:23:50,430 --> 00:23:52,650
iets in te
4000000000 elementen.

568
00:23:52,650 --> 00:23:55,730
Dus op die opmerking, we zijn
gaat deze code

569
00:23:55,730 --> 00:23:58,950
dus jullie kunnen eigenlijk
soort te zien hoe dit werkt.

570
00:23:58,950 --> 00:24:01,520
Oké, dus jullie kunnen coderen.

571
00:24:01,520 --> 00:24:04,100
Ik ga jullie laten
praten voor een klein beetje.

572
00:24:04,100 --> 00:24:07,970
Krijgen om mensen om je heen weet, dat is
wat iemand wilde van vorige paragraaf.

573
00:24:07,970 --> 00:24:10,280
>> Dus maak je de mensen om je heen te leren kennen.

574
00:24:10,280 --> 00:24:11,305
Praat voor een klein beetje.

575
00:24:11,305 --> 00:24:12,580

576
00:24:12,580 --> 00:24:15,730
En alles wat ik van je wil
jongens is nu net

577
00:24:15,730 --> 00:24:17,575
proberen om een ​​overzicht van pseudocode creëren.

578
00:24:17,575 --> 00:24:18,075
OK?

579
00:24:18,075 --> 00:24:20,825

580
00:24:20,825 --> 00:24:21,325
Whoa.

581
00:24:21,325 --> 00:24:23,320

582
00:24:23,320 --> 00:24:29,520
Alles wat ik wil van jullie is dat je
gewoon gaan in dit geval, terwijl in te vullen.

583
00:24:29,520 --> 00:24:32,170
Dus ik heb deze bovenste set
en ondergrenzen die

584
00:24:32,170 --> 00:24:35,250
vertegenwoordigen het begin
en het einde van ons aanbod.

585
00:24:35,250 --> 00:24:40,440
En je gaat eigenlijk
lus door en uitzoeken

586
00:24:40,440 --> 00:24:42,470
wat we doen binnen deze while lus.

587
00:24:42,470 --> 00:24:45,810
>> Dus als je kunt achterhalen out-- Ik heb
een hint er-- wat zijn de gevallen

588
00:24:45,810 --> 00:24:46,640
dat we hier?

589
00:24:46,640 --> 00:24:48,100

590
00:24:48,100 --> 00:24:51,560
Dus als je wilt achterhalen van de
gevallen zullen wij pseudocode die

591
00:24:51,560 --> 00:24:53,350
en dan gaan we daadwerkelijk coderen hen.

592
00:24:53,350 --> 00:24:55,330
En het gaat worden, ik
denken, hopelijk het zal

593
00:24:55,330 --> 00:24:56,788
een beetje makkelijker dan je verwacht.

594
00:24:56,788 --> 00:24:57,554

595
00:24:57,554 --> 00:25:00,220
Want het is niet zo veel code,
eigenlijk, dat is echt cool.

596
00:25:00,220 --> 00:25:34,110

597
00:25:34,110 --> 00:25:35,018
>> Mm-hm?

598
00:25:35,018 --> 00:25:35,893
>> STUDENT: [onverstaanbaar]?

599
00:25:35,893 --> 00:25:36,984

600
00:25:36,984 --> 00:25:37,650
INSTRUCTEUR: Ja.

601
00:25:37,650 --> 00:25:38,595
Er was iets
te vinden in het midden.

602
00:25:38,595 --> 00:25:39,552
>> STUDENT: Dus kunnen we dat gebruiken.

603
00:25:39,552 --> 00:25:39,770
OK.

604
00:25:39,770 --> 00:25:40,603
>> INSTRUCTEUR: Perfect.

605
00:25:40,603 --> 00:25:42,950
Dus dat is het eerste wat we moeten doen.

606
00:25:42,950 --> 00:25:44,330
Dus vind het midden.

607
00:25:44,330 --> 00:25:45,415

608
00:25:45,415 --> 00:25:45,915
Grote.

609
00:25:45,915 --> 00:25:47,770

610
00:25:47,770 --> 00:25:55,010
Dus heb je een idee van hoe we zouden kunnen
het midden met code eigenlijk vinden?

611
00:25:55,010 --> 00:25:55,980
>> STUDENT: Ja.

612
00:25:55,980 --> 00:25:57,000
n meer dan 2?

613
00:25:57,000 --> 00:25:58,500

614
00:25:58,500 --> 00:25:59,500
INSTRUCTEUR: Zo n meer dan 2.

615
00:25:59,500 --> 00:26:05,170
Dus een ding om te onthouden is dat
je bovenste en onderste grenzen veranderen.

616
00:26:05,170 --> 00:26:08,110
We blijven vernauwen de kant
van de array zijn we op zoek naar.

617
00:26:08,110 --> 00:26:11,970
Dus n meer dan 2 zal alleen werken
voor het eerste wat we doen.

618
00:26:11,970 --> 00:26:17,810
Zodat het nemen van de bovenste en onderste in aanmerking,
hoe kunnen we dat midden element?

619
00:26:17,810 --> 00:26:20,640
Omdat we willen dat het midden
tussen de bovenste en onderste, toch?

620
00:26:20,640 --> 00:26:21,730

621
00:26:21,730 --> 00:26:22,494
Mm-hm?

622
00:26:22,494 --> 00:26:23,369
>> STUDENT: [onverstaanbaar].

623
00:26:23,369 --> 00:26:26,170

624
00:26:26,170 --> 00:26:28,080
>> INSTRUCTEUR: Dus we hebben een aantal midden.

625
00:26:28,080 --> 00:26:32,730
En het zal de bovenste plus lager dan 2 zijn.

626
00:26:32,730 --> 00:26:34,740

627
00:26:34,740 --> 00:26:35,690
Awesome.

628
00:26:35,690 --> 00:26:36,570
Daar gaan we.

629
00:26:36,570 --> 00:26:37,280
Eén regel omlaag.

630
00:26:37,280 --> 00:26:38,560
Jullie zijn op weg.

631
00:26:38,560 --> 00:26:41,400
Dus nu hebben we onze
midden, wat willen we doen?

632
00:26:41,400 --> 00:26:45,050

633
00:26:45,050 --> 00:26:45,900
Gewoon in het algemeen.

634
00:26:45,900 --> 00:26:47,734
Je hoeft het niet te coderen.

635
00:26:47,734 --> 00:26:48,335
Ja.

636
00:26:48,335 --> 00:26:49,210
STUDENT: [onverstaanbaar]?

637
00:26:49,210 --> 00:27:00,310

638
00:27:00,310 --> 00:27:10,310
INSTRUCTEUR: Dus het is plus omdat je
het vinden van het gemiddelde tussen de twee

639
00:27:10,310 --> 00:27:10,810
daarvan.

640
00:27:10,810 --> 00:27:11,890

641
00:27:11,890 --> 00:27:17,370
Dus als je denkt dat ze als soort
verhogen vanaf de zijkanten,

642
00:27:17,370 --> 00:27:21,640
over nadenkt als je aanpak
het midden, je wilt als dat.

643
00:27:21,640 --> 00:27:27,150
Als je aan beide zijden van de
midden, en we hebben net 5 en 7.

644
00:27:27,150 --> 00:27:31,440
Als je ze bij elkaar optelt u
krijg 12, je delen door 2, is 6.

645
00:27:31,440 --> 00:27:33,726
>> Soms is het moeilijk om
uitleggen waarom dat werkt,

646
00:27:33,726 --> 00:27:35,600
maar als je door te werken
Een voorbeeld soms

647
00:27:35,600 --> 00:27:37,962
het zal u helpen erachter te komen of
Moet plus of min zijn.

648
00:27:37,962 --> 00:27:38,846
Ja.

649
00:27:38,846 --> 00:27:40,830
>> STUDENT: [onverstaanbaar]
precies in het midden

650
00:27:40,830 --> 00:27:43,950
als ze een geval waarin
er is een hoop kleinere aantallen

651
00:27:43,950 --> 00:27:45,860
en als een groot aantal?

652
00:27:45,860 --> 00:27:49,750
>> INSTRUCTEUR: Dus alles wat je nodig hebt
is het midden van de array.

653
00:27:49,750 --> 00:27:53,010
Dus als je een bos van kleine aantallen hadden
en dan een heel groot aantal

654
00:27:53,010 --> 00:27:54,799
op het einde, het maakt niet uit.

655
00:27:54,799 --> 00:27:56,840
Het enige dat telt is dat
ze gesorteerd zijn, je gewoon

656
00:27:56,840 --> 00:27:59,339
willen kijken naar het midden van
de array, omdat je nog steeds

657
00:27:59,339 --> 00:28:00,700
het snijden van uw probleem in de helft.

658
00:28:00,700 --> 00:28:03,020

659
00:28:03,020 --> 00:28:03,680
Cool.

660
00:28:03,680 --> 00:28:06,430
Dus nu hebben we de
midden, wat moeten we nu doen?

661
00:28:06,430 --> 00:28:07,150
>> STUDENT: Vergelijk.

662
00:28:07,150 --> 00:28:08,150
INSTRUCTEUR: Het vergelijken.

663
00:28:08,150 --> 00:28:11,670
Dus vergelijken midden om value_wanted.

664
00:28:11,670 --> 00:28:14,300

665
00:28:14,300 --> 00:28:15,160
Cool.

666
00:28:15,160 --> 00:28:17,950
Zo zie je hier boven hebben wij
deze waarde willen we hier.

667
00:28:17,950 --> 00:28:22,012

668
00:28:22,012 --> 00:28:23,095
Vergeet niet dat dit een array.

669
00:28:23,095 --> 00:28:24,100

670
00:28:24,100 --> 00:28:26,970
Dus midden verwijst naar de index.

671
00:28:26,970 --> 00:28:29,785
Dus we willen de waarden van de middenklasse te doen.

672
00:28:29,785 --> 00:28:32,380

673
00:28:32,380 --> 00:28:35,650
Vergeet niet als je wilt
te vergelijken, dubbel is.

674
00:28:35,650 --> 00:28:38,250
Je doet enkel gelijk je bent
gewoon gaan om het opnieuw toewijzen,

675
00:28:38,250 --> 00:28:41,090
en dan, natuurlijk, het is
gaat om de waarde die u wilt zijn.

676
00:28:41,090 --> 00:28:42,300
Dus doe dat niet.

677
00:28:42,300 --> 00:28:44,350
>> Dus we gaan om te zien of
de waarden in het midden

678
00:28:44,350 --> 00:28:46,460
is gelijk aan de waarde die we willen.

679
00:28:46,460 --> 00:28:47,749

680
00:28:47,749 --> 00:28:48,790
Vergeet je bretels.

681
00:28:48,790 --> 00:28:50,520

682
00:28:50,520 --> 00:28:52,235
Dropbox zou weggaan.

683
00:28:52,235 --> 00:28:54,140

684
00:28:54,140 --> 00:28:56,200
Dus wat doen we in dit geval?

685
00:28:56,200 --> 00:28:59,360
Als het is wat we willen terugkeren?

686
00:28:59,360 --> 00:29:01,510

687
00:29:01,510 --> 00:29:02,626
We proberen te zeggen.

688
00:29:02,626 --> 00:29:03,440
>> STUDENT: Print uit.

689
00:29:03,440 --> 00:29:05,314
>> INSTRUCTEUR: Nou, we
wil niet af te drukken.

690
00:29:05,314 --> 00:29:08,220
Dus dit is een bool hier, dus we
willen waar of onwaar terug.

691
00:29:08,220 --> 00:29:12,280
We zeggen, is dit aantal
een [? RRA? ?] Dus als het,

692
00:29:12,280 --> 00:29:13,788
we hebben net weer het waar.

693
00:29:13,788 --> 00:29:16,780

694
00:29:16,780 --> 00:29:17,760
Als ik kan spellen waar.

695
00:29:17,760 --> 00:29:18,830

696
00:29:18,830 --> 00:29:20,805
>> STUDENT: Waarom zou je niet nul terug te keren?

697
00:29:20,805 --> 00:29:22,930
INSTRUCTEUR: Dus je kon
nul terug te keren als je wilde.

698
00:29:22,930 --> 00:29:26,780
Maar in dit geval, omdat
onze functie retourneert een bool,

699
00:29:26,780 --> 00:29:28,962
we nodig hebben om waar of onwaar terug.

700
00:29:28,962 --> 00:29:30,920
STUDENT: Wanneer je bent
zeggen boolean expressie,

701
00:29:30,920 --> 00:29:33,450
kan je het gelijk instellen op false?

702
00:29:33,450 --> 00:29:39,860
Net als ik wil zeggen, als deze voorwaarde
niet is voldaan, zoals is bovenste gelijk vals.

703
00:29:39,860 --> 00:29:42,332
Zal het te begrijpen als je gewoon
zet vals aan de andere kant?

704
00:29:42,332 --> 00:29:43,040
INSTRUCTEUR: Yeah.

705
00:29:43,040 --> 00:29:44,820
Dus eigenlijk als je
ooit iets te doen

706
00:29:44,820 --> 00:29:49,600
zoals is boven- of lager is,
dat waar of onwaar retourneert

707
00:29:49,600 --> 00:29:53,850
en het is eigenlijk slecht stijl aan
zeg gelijk gelijk waar of gelijken

708
00:29:53,850 --> 00:29:54,840
gelijk aan vals.

709
00:29:54,840 --> 00:30:00,210
U wilt dat resultaat gebruiken
zo zelf als uw cheque.

710
00:30:00,210 --> 00:30:04,720

711
00:30:04,720 --> 00:30:05,860
Niet wat ik wilde.

712
00:30:05,860 --> 00:30:08,150

713
00:30:08,150 --> 00:30:09,240
Dat is wat ik wilde.

714
00:30:09,240 --> 00:30:13,205
Dus in het geval van je vraagt
over iets als sla dit in c.

715
00:30:13,205 --> 00:30:16,320

716
00:30:16,320 --> 00:30:25,150
>> Dus als we int main (void)
en iets als dit.

717
00:30:25,150 --> 00:30:31,922
En je hebt als is boven-
van wat input en je bent

718
00:30:31,922 --> 00:30:33,630
de vraag of u kunt doen
zoiets als dit?

719
00:30:33,630 --> 00:30:35,010

720
00:30:35,010 --> 00:30:35,679
Right?

721
00:30:35,679 --> 00:30:37,470
STUDENT: Ik probeerde
om het te doen [onverstaanbaar].

722
00:30:37,470 --> 00:30:38,450
Want als it's--

723
00:30:38,450 --> 00:30:39,200
INSTRUCTEUR: Right.

724
00:30:39,200 --> 00:30:41,197
Dus je wilt deze vals te zijn, toch?

725
00:30:41,197 --> 00:30:41,780
STUDENT: Ja.

726
00:30:41,780 --> 00:30:45,960
INSTRUCTEUR: Dus in dit geval je
wil dat het uit te voeren als het niet waar is.

727
00:30:45,960 --> 00:30:50,510
Dus de koele ding je doet er dit.

728
00:30:50,510 --> 00:30:52,900

729
00:30:52,900 --> 00:30:55,650
Dus onthoud uitroepteken
punt ontkent dingen?

730
00:30:55,650 --> 00:30:58,270
Het zegt [onverstaanbaar] betekent niet.

731
00:30:58,270 --> 00:31:03,590
Dus als we kijken naar slechts
dit deel hier, zou je

732
00:31:03,590 --> 00:31:05,740
zeggen dat evalueert naar
valse zoals u dat wilt.

733
00:31:05,740 --> 00:31:06,790

734
00:31:06,790 --> 00:31:09,880
Niet vals is waar die
betekent dit zou uitvoeren.

735
00:31:09,880 --> 00:31:11,037
Heeft dat zin?

736
00:31:11,037 --> 00:31:11,620
STUDENT: Ja.

737
00:31:11,620 --> 00:31:12,453
INSTRUCTEUR: Awesome.

738
00:31:12,453 --> 00:31:13,800

739
00:31:13,800 --> 00:31:14,300
OK.

740
00:31:14,300 --> 00:31:16,330
Dus we konden gewoon terug
geldt in dit geval.

741
00:31:16,330 --> 00:31:20,357
Dus nu hebben we twee andere
gevallen in dit geval.

742
00:31:20,357 --> 00:31:21,565
Wat zijn onze twee andere gevallen?

743
00:31:21,565 --> 00:31:31,610

744
00:31:31,610 --> 00:31:32,900
Laten we het gewoon doen het op deze manier.

745
00:31:32,900 --> 00:31:40,660
Dus laten we beginnen met het andere
als waarden in het midden

746
00:31:40,660 --> 00:31:43,230
kleiner is dan de waarde die we willen.

747
00:31:43,230 --> 00:31:47,200

748
00:31:47,200 --> 00:31:52,020
Dus onze waarde in het midden is minder
dan de waarde die we zoeken.

749
00:31:52,020 --> 00:31:53,765

750
00:31:53,765 --> 00:31:56,720
>> Dus die gebonden je doet
denk dat we willen updaten?

751
00:31:56,720 --> 00:31:57,870

752
00:31:57,870 --> 00:31:58,780
Bovenste of onderste?

753
00:31:58,780 --> 00:32:01,440

754
00:32:01,440 --> 00:32:01,940
Upper?

755
00:32:01,940 --> 00:32:03,230

756
00:32:03,230 --> 00:32:06,470
Dus welke kant van de matrix
gaan we op zoek naar?

757
00:32:06,470 --> 00:32:07,500
>> STUDENT: De onderste.

758
00:32:07,500 --> 00:32:09,750
>> INSTRUCTEUR: We gaan we
te kijken naar de linkerkant.

759
00:32:09,750 --> 00:32:11,120
Dus anders als weinig waarde is minder.

760
00:32:11,120 --> 00:32:14,730
Dus je middelste waarde hier
is minder dan wat we willen.

761
00:32:14,730 --> 00:32:17,202
Dus we willen het nemen
rechterzijde van onze array.

762
00:32:17,202 --> 00:32:18,910
Dus we gaan
werken onze ondergrens.

763
00:32:18,910 --> 00:32:20,210

764
00:32:20,210 --> 00:32:23,020
Dus we onze lagere toewijzen.

765
00:32:23,020 --> 00:32:25,221
En wat denk je dat lager zou moeten zijn?

766
00:32:25,221 --> 00:32:26,304
STUDENT: De middelste waarde?

767
00:32:26,304 --> 00:32:27,446

768
00:32:27,446 --> 00:32:28,820
INSTRUCTEUR: Dus het midden value--

769
00:32:28,820 --> 00:32:30,136
STUDENT: Plus 1.

770
00:32:30,136 --> 00:32:31,010
INSTRUCTEUR: --plus 1.

771
00:32:31,010 --> 00:32:32,300

772
00:32:32,300 --> 00:32:34,380
Kan iemand mij vertellen waarom
we hebben dat plus 1?

773
00:32:34,380 --> 00:32:35,730
>> STUDENT: [? Geen waarde?]
is gelijk aan.

774
00:32:35,730 --> 00:32:36,120
>> INSTRUCTEUR: Right.

775
00:32:36,120 --> 00:32:38,661
Omdat we weten al dat
onze middelste waarde niet gelijk is aan

776
00:32:38,661 --> 00:32:42,750
het en we willen het uitsluiten
Uit latere zoekopdrachten.

777
00:32:42,750 --> 00:32:46,360
Als je dat plus 1, dit vergeet
zal voor onbepaalde tijd willen lus.

778
00:32:46,360 --> 00:32:49,620
En je zult gewoon in een gevangen worden
oneindige lus en dan zul je segfault

779
00:32:49,620 --> 00:32:50,370
en dingen slecht gaan.

780
00:32:50,370 --> 00:32:54,780
Dus altijd voor zorgen dat je niet
inbegrip van de waarde die u zojuist

781
00:32:54,780 --> 00:32:55,380
gekeken.

782
00:32:55,380 --> 00:32:58,530
Dus we zorgen dat met een plus 1.

783
00:32:58,530 --> 00:33:04,840
>> Dus nu hebben we onze laatste voorwaarde
die ik altijd voor de zekerheid

784
00:33:04,840 --> 00:33:12,664
U kunt hier controleren, anders als waarde op
het midden groter is dan de waarde

785
00:33:12,664 --> 00:33:13,163
we willen.

786
00:33:13,163 --> 00:33:16,260

787
00:33:16,260 --> 00:33:20,230
Dat betekent dat we willen
de linker helft.

788
00:33:20,230 --> 00:33:21,350

789
00:33:21,350 --> 00:33:23,260
Dus die ene gaan we updaten?

790
00:33:23,260 --> 00:33:23,760
Upper.

791
00:33:23,760 --> 00:33:25,470

792
00:33:25,470 --> 00:33:26,970
En wat is dit één gaan evenaren?

793
00:33:26,970 --> 00:33:31,630

794
00:33:31,630 --> 00:33:33,690
Midden minus 1 omdat,
natuurlijk, we willen

795
00:33:33,690 --> 00:33:38,370
om ervoor te zorgen dat we niet
kijken naar dat middelste waarde weer.

796
00:33:38,370 --> 00:33:41,830

797
00:33:41,830 --> 00:33:45,110
En dan hebben we het.

798
00:33:45,110 --> 00:33:45,610
Dat is het.

799
00:33:45,610 --> 00:33:46,820
Dat is alles binair zoeken is.

800
00:33:46,820 --> 00:33:48,190
Het is niet zo slecht, toch?

801
00:33:48,190 --> 00:33:51,590
Het is als 10 regels van
code met witte ruimte.

802
00:33:51,590 --> 00:33:57,510
Dus zeer krachtig, zeer nuttig, je wil
worden met behulp van het in een van je later psets.

803
00:33:57,510 --> 00:33:59,360
Misschien niet deze, maar later.

804
00:33:59,360 --> 00:34:00,670
Dus leer het.

805
00:34:00,670 --> 00:34:01,510
Love it.

806
00:34:01,510 --> 00:34:02,980
Het zal je goed behandelen.

807
00:34:02,980 --> 00:34:05,370
Dus heeft iemand enig hebben
vragen over binary search?

808
00:34:05,370 --> 00:34:06,196
Ja.

809
00:34:06,196 --> 00:34:09,840
>> STUDENT: Maakt het uit
of je n even of oneven?

810
00:34:09,840 --> 00:34:10,750
>> INSTRUCTEUR: No.

811
00:34:10,750 --> 00:34:18,150
Omdat we wierp het naar het midden als
een int, zal het alleen maar afgekapt.

812
00:34:18,150 --> 00:34:21,600
Dus het een integer zal blijven en het zal
uiteindelijk sorteren door alles.

813
00:34:21,600 --> 00:34:23,909
U hoeft zich dus geen zorgen te maken over dat.

814
00:34:23,909 --> 00:34:24,580
Iedereen goed?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
Awesome.

817
00:34:26,850 --> 00:34:27,919
Cool.

818
00:34:27,919 --> 00:34:30,836
Dus, jullie hebben dit.

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
Slideshow.

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
Dus als we het over hadden, weet ik
David genoemde complexiteit looptijden.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> Dus in het beste geval, het is gewoon
, waar we constante tijd noemen.

825
00:34:50,340 --> 00:34:51,909
Kan iemand mij vertellen waarom dat zou kunnen zijn?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
Wat voor soort scenario zou dat inhouden?

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
Mm-hm.

830
00:34:58,760 --> 00:34:59,926
>> STUDENT: [onverstaanbaar] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
INSTRUCTEUR: Dus het midden zijn de
eerste element dat we komen om, toch?

833
00:35:03,830 --> 00:35:08,167
Dus ofwel een array van één of
wat we ook op zoek bent naar net

834
00:35:08,167 --> 00:35:09,750
gebeurt er precies in het midden zijn.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Dus dat is onze best case.

837
00:35:13,380 --> 00:35:17,540
U krijgt in de echte problemen, waarschijnlijk niet
zal bereiken [onverstaanbaar] dat vaak.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Hoe zit het met onze ergste geval?

840
00:35:19,750 --> 00:35:21,270
Onze slechtste geval is log n.

841
00:35:21,270 --> 00:35:25,360
En dat heeft te maken met de hele
machten van twee ding dat ik over sprak.

842
00:35:25,360 --> 00:35:30,930
>> Dus in het slechtste geval zou betekenen
dat we moesten de array omhakken

843
00:35:30,930 --> 00:35:33,270
totdat het een element van één.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Dus moesten we het neer te hakken in de helft
zo vaak als we maar konden.

846
00:35:38,930 --> 00:35:41,430
Dat is waarom het log n omdat
je gewoon blijven delen door twee.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Dus aannames, dingen die je
moet weten als je ooit

849
00:35:45,830 --> 00:35:48,050
ga een binary search gebruiken.

850
00:35:48,050 --> 00:35:50,680
Uw elementen moeten worden gesorteerd.

851
00:35:50,680 --> 00:35:53,890
Ze moeten gesorteerd worden, omdat
dat is de enige manier waarop je

852
00:35:53,890 --> 00:35:57,060
kan weten als je in staat bent
te gooien de helft van het.

853
00:35:57,060 --> 00:36:00,260
>> Als je dit door elkaar gegooid zak had
van nummers en je zegt,

854
00:36:00,260 --> 00:36:05,380
OK, ik ga naar het midden te controleren
nummer en het nummer Ik ben op zoek naar

855
00:36:05,380 --> 00:36:08,510
is minder dan dat, ik ben gewoon gaan
om willekeurig gooien de helft.

856
00:36:08,510 --> 00:36:11,130
Je zou het niet weten of uw
getallen in de andere helft.

857
00:36:11,130 --> 00:36:12,655
Uw lijst gesorteerd moet worden.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
Als goed, kan dit
verder te gaan een beetje,

860
00:36:16,560 --> 00:36:18,360
maar je moet random access hebben.

861
00:36:18,360 --> 00:36:21,940
Je moet in staat zijn om gewoon
naar die tussenstuk.

862
00:36:21,940 --> 00:36:25,110
Als je moet doorkruisen
door iets

863
00:36:25,110 --> 00:36:28,630
of kost het je extra stappen
dat tussenstuk te krijgen,

864
00:36:28,630 --> 00:36:31,750
het is niet meer, omdat log n
je bent meer werk toe te voegen in.

865
00:36:31,750 --> 00:36:34,800
En dit zal een beetje te maken
meer zin in twee weken,

866
00:36:34,800 --> 00:36:37,950
maar ik gewoon een soort van wilde inleiden,
geven jullie een idee van wat er

867
00:36:37,950 --> 00:36:38,999
komen.

868
00:36:38,999 --> 00:36:40,790
Maar dat zijn de twee
belangrijke aannames

869
00:36:40,790 --> 00:36:44,804
die je nodig hebt voor een binaire lijst.

870
00:36:44,804 --> 00:36:45,720
Zorg ervoor dat het is opgelost.

871
00:36:45,720 --> 00:36:47,920
Dat is de grote voor
jullie nu.

872
00:36:47,920 --> 00:36:52,170
En op dat we kunnen gaan in
de rest van onze soort.

873
00:36:52,170 --> 00:36:56,444
Dus vier sorts-- bubble,
inbrengen, selectie, en merge.

874
00:36:56,444 --> 00:36:57,485
Ze zijn allemaal wel cool.

875
00:36:57,485 --> 00:37:02,860
Als jullie besluiten om CS 124 te nemen,
leer je over allerlei soorten.

876
00:37:02,860 --> 00:37:07,575
En als je een XKCD fan, er
is een echt cool strip over

877
00:37:07,575 --> 00:37:11,530
hou echt ineffectief soorten, die ik
raden u gaan kijken.

878
00:37:11,530 --> 00:37:16,170
Eén van hen is als paniek soort, die
is als, oh nee, terug willekeurige array.

879
00:37:16,170 --> 00:37:16,991
Shutdown systeem.

880
00:37:16,991 --> 00:37:17,490
Verlaat.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Dus geeky humor is altijd goed.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Dus heeft iemand herinneren soort
van als slechts een algemeen idee

885
00:37:25,750 --> 00:37:27,810
hoe bubble sort werkt.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Herinnert u zich?

888
00:37:32,155 --> 00:37:32,755
>> STUDENT: Ja.

889
00:37:32,755 --> 00:37:33,970
>> INSTRUCTEUR: Go for it.

890
00:37:33,970 --> 00:37:38,980
>> STUDENT: Dus je gaat door en
als het is groter, dan wisselen de twee.

891
00:37:38,980 --> 00:37:39,820
>> INSTRUCTEUR: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Precies.

893
00:37:40,564 --> 00:37:41,730
Dus je gewoon doorlopen.

894
00:37:41,730 --> 00:37:43,050
Je controleert twee nummers.

895
00:37:43,050 --> 00:37:46,510
Als de vorige groter
dan die daarna,

896
00:37:46,510 --> 00:37:50,230
je ze gewoon verwisselen, zodat in
Zo alle hogere nummers

897
00:37:50,230 --> 00:37:54,990
bubble tegen het einde van de lijst
en al de lagere aantallen bubble naar beneden.

898
00:37:54,990 --> 00:37:59,355
>> Heeft hij laten zien dat jullie de koele
geluidseffect sorteren video?

899
00:37:59,355 --> 00:38:00,480
Het is wel cool.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Dus zoals Robert al zei, het algoritme
dat je gewoon door de lijst,

902
00:38:05,200 --> 00:38:07,930
omwisselen van de aangrenzende waarden
als ze niet in orde is.

903
00:38:07,930 --> 00:38:10,975
En dan gewoon blijven herhalen
totdat je geen swaps maken.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Dus niet slecht, toch?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Dus we hebben gewoon een snelle voorbeeld hier.

908
00:38:16,319 --> 00:38:18,360
Dus dit gaat te sorteren
ze in oplopende volgorde.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Dus toen we door de eerste
tijd, we kijken door middel van acht

911
00:38:23,470 --> 00:38:26,880
en zes zijn uiteraard niet
in orde is, wisselen we ze.

912
00:38:26,880 --> 00:38:27,985
>> Dus kijk naar de volgende.

913
00:38:27,985 --> 00:38:29,430
Acht en vier niet in orde.

914
00:38:29,430 --> 00:38:30,450
Ze te verwisselen.

915
00:38:30,450 --> 00:38:32,530
En dan acht en twee, ruil ze.

916
00:38:32,530 --> 00:38:33,470
Daar gaan we.

917
00:38:33,470 --> 00:38:39,519
Dus na je eerste pas, je
weten dat uw grootste aantal

918
00:38:39,519 --> 00:38:41,810
zal de manier
aan de top, want het is gewoon

919
00:38:41,810 --> 00:38:44,210
zal voortdurend
groter dan al het andere

920
00:38:44,210 --> 00:38:46,810
en het is gewoon te borrelen
up helemaal tot het einde daar.

921
00:38:46,810 --> 00:38:48,226
Is dat zinvol is voor iedereen?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
Cool.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Dus dan kijken we naar onze tweede pass.

926
00:38:53,920 --> 00:38:54,980
Zes en vier, switch.

927
00:38:54,980 --> 00:38:55,920
Zes en twee, switch.

928
00:38:55,920 --> 00:38:58,700
En nu hebben we een paar dingen in orde.

929
00:38:58,700 --> 00:39:02,240
Dus voor iedere pas die we
maken door middel van onze hele lijst,

930
00:39:02,240 --> 00:39:06,320
we weten dat als dat veel nummers
eind zal zijn gesorteerd.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Dus we doen een derde pas,
dat is een swap.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
En dan op onze vierde
passeren, we hebben nul slots.

935
00:39:15,910 --> 00:39:18,570
En zo weten we dat onze
serie is gesorteerd.

936
00:39:18,570 --> 00:39:20,900
>> En dat is het grote
ding met bubble sort.

937
00:39:20,900 --> 00:39:23,720
We weten dat wanneer we
hebben nul swaps, dat

938
00:39:23,720 --> 00:39:26,497
betekent dat alles
is volledig in orde.

939
00:39:26,497 --> 00:39:27,580
Het is een soort van hoe we controleren.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Dus we gaan ook bubble coderen
soort die ook niet zo slecht.

942
00:39:36,480 --> 00:39:38,120
Geen van deze zijn zo slecht.

943
00:39:38,120 --> 00:39:40,210
Ik weet dat ze kan lijken een beetje eng.

944
00:39:40,210 --> 00:39:42,124
Ik weet dat toen ik
de klas, zelfs wanneer ik

945
00:39:42,124 --> 00:39:44,290
onderwees de klasse voor
de eerste keer vorig jaar,

946
00:39:44,290 --> 00:39:46,165
Ik was als, hoe kan ik dit doen?

947
00:39:46,165 --> 00:39:48,540
Het is zinvol in theorie, maar
hoe kunnen we eigenlijk doen?

948
00:39:48,540 --> 00:39:51,420
Dat is waarom ik wil ook lopen
door middel van code met jullie hier.

949
00:39:51,420 --> 00:39:54,915
Dus ik heb een pseudocode
voor jullie deze keer.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Dus gewoon dit in gedachten te houden als
we gaan dan de overgang.

952
00:39:58,970 --> 00:40:04,210
Dus we hebben een aantal teller die
houdt onze swaps,

953
00:40:04,210 --> 00:40:08,370
want we moeten ervoor zorgen
dat we controleren dat.

954
00:40:08,370 --> 00:40:11,830
En we herhalen het hele array
zoals we net hebben gedaan met dit voorbeeld.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Indien het element vóór groter is dan
het element na waar we aan,

957
00:40:17,325 --> 00:40:20,760
we ze te verwisselen en we verhogen ons
teller want zodra we ruilen,

958
00:40:20,760 --> 00:40:23,850
willen we laten onze balie weten dat.

959
00:40:23,850 --> 00:40:26,247
Heeft u vragen daar?

960
00:40:26,247 --> 00:40:27,580
Iets lijkt grappig hier.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
STUDENT: Heeft u de teller op nul te zetten
elke keer als je door de lus?

963
00:40:32,350 --> 00:40:34,339
Hoef je niet te gaan
terug naar elke keer nul?

964
00:40:34,339 --> 00:40:35,505
INSTRUCTEUR: Niet per se.

965
00:40:35,505 --> 00:40:39,710
Dus wat er gebeurt is dat we hier gaan door.

966
00:40:39,710 --> 00:40:43,830
Dus doen terwijl, denk eraan, dit
zal een keer uit te voeren zonder falen.

967
00:40:43,830 --> 00:40:46,480
Dus het gaat om het stellen
teller gelijk aan nul,

968
00:40:46,480 --> 00:40:48,070
dan dat het gaat om door te herhalen.

969
00:40:48,070 --> 00:40:50,590
Als het doorloopt,
het zal teller updaten.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Zoals het een bijwerking teller, wanneer het klaar is,
wanneer het aan het einde van de array,

972
00:40:56,900 --> 00:41:00,830
als onze lijst niet zijn gesorteerd,
teller zal zijn bijgewerkt.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Dus dan wordt de toestand en het
zegt, OK, is teller groter dan nul.

975
00:41:07,150 --> 00:41:09,290
Als het is, doe het opnieuw.

976
00:41:09,290 --> 00:41:14,340
U wilt dus dat wanneer je reset
doorlopen, teller gelijk aan nul.

977
00:41:14,340 --> 00:41:18,240
Als je door een gesorteerde
array, niets verandert,

978
00:41:18,240 --> 00:41:21,355
dit niet lukt, en je
de terugkeer van de gesorteerde lijst.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Is dat zinvol?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
STUDENT: Het zou in een klein beetje.

983
00:41:26,356 --> 00:41:27,147
INSTRUCTEUR: OK.

984
00:41:27,147 --> 00:41:28,980
Als er een andere
vraag die omhoog komt.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Ja.

987
00:41:30,680 --> 00:41:33,760
>> STUDENT: Wat zou de functie
zijn voor het omwisselen van de elementen?

988
00:41:33,760 --> 00:41:36,900
>> INSTRUCTEUR: Dus we kunnen eigenlijk schrijven
dat als we gaan nu rechts.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
Cool.

991
00:41:38,300 --> 00:41:42,155
Dus op deze nota, is Alison gaat
terug naar het apparaat schakelen.

992
00:41:42,155 --> 00:41:43,080
Het zal leuk zijn.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
En we hebben onze mooie
bubble sort ding hier.

995
00:41:47,390 --> 00:41:50,800
Dus ik al fietsen deed
door de matrix.

996
00:41:50,800 --> 00:41:53,030
We hebben onze swaps die
gelijk aan nul.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Dus we willen ruilen aangrenzende
elementen als ze niet in orde.

999
00:41:58,440 --> 00:42:03,020
Dus het eerste wat we moeten
do wordt doorlopen ons aanbod.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Dus hoe denk je dat we misschien
doorlopen van ons aanbod?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
We hebben voor en i gelijk is aan 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
We willen dat ik minder te zijn
dan n min 1 min k.

1006
00:42:22,454 --> 00:42:23,870
En ik zal uitleggen dat in een tweede.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Dus dit is een optimalisatie hier, waar,
herinneren hoe ik zei na elke pas

1009
00:42:32,830 --> 00:42:36,655
door de array we
weten dat wat er ook on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Dus na één pas we
weten dat dit wordt gesorteerd.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Na twee passen we weten
dit alles wordt gesorteerd.

1014
00:42:50,060 --> 00:42:52,750
Na drie passen we
weten dat er gesorteerd worden.

1015
00:42:52,750 --> 00:42:55,620
Dus de manier waarop ik ben itereren
hier door de matrix,

1016
00:42:55,620 --> 00:43:01,090
wordt het is en zorg ervoor dat alleen gaan
door wat we weten is ongesorteerd.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
Dat is gewoon een optimalisatie.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Je zou het naïef te schrijven gewoon
itereren door alles heen,

1021
00:43:08,210 --> 00:43:09,970
het zou alleen maar langer duren.

1022
00:43:09,970 --> 00:43:12,470
Met deze vier lus is het
gewoon een leuke optimalisatie

1023
00:43:12,470 --> 00:43:18,460
omdat we weten dat er na elke volle
iteratie door de array hier,

1024
00:43:18,460 --> 00:43:24,050
zoals elke volle loop hier, we weten
dat één van deze elementen

1025
00:43:24,050 --> 00:43:25,760
wordt gesorteerd eind.

1026
00:43:25,760 --> 00:43:28,294
>> We hoeven dus geen zorgen te maken over die.

1027
00:43:28,294 --> 00:43:29,710
Is dat zinvol is voor iedereen?

1028
00:43:29,710 --> 00:43:30,950
Die koele trucje?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Dus in dat geval, als
we iteratie,

1031
00:43:37,270 --> 00:43:50,590
we weten dat we willen controleren of
array-n en n + 1 in orde zijn.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
OK.

1034
00:43:53,559 --> 00:43:54,600
Dus hier is de pseudocode.

1035
00:43:54,600 --> 00:43:57,540
We willen om te controleren of serie n
en n plus 1 in orde zijn.

1036
00:43:57,540 --> 00:43:59,520
Dus wat kunnen we daar?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
Het zal een aantal voorwaarden worden gekoppeld.

1039
00:44:03,120 --> 00:44:04,220
Het zal een if.

1040
00:44:04,220 --> 00:44:07,066
>> STUDENT: Als scala n
minder dan scala n plus 1.

1041
00:44:07,066 --> 00:44:07,816
INSTRUCTEUR: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
Wel, kleiner of groter dan.

1044
00:44:10,699 --> 00:44:11,615
STUDENT: Groter dan.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Dan willen we ze te verwisselen.

1047
00:44:17,620 --> 00:44:18,570
Precies.

1048
00:44:18,570 --> 00:44:23,570
Dus nu komen we in wat is het
mechanisme voor swapping hen?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Dus gingen we door middel van dit kort,
een soort swap functie vorige week.

1051
00:44:28,137 --> 00:44:29,595
Heeft iemand nog hoe het werkte?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Dus we kunnen niet zomaar opnieuw toewijzen hen, toch?

1054
00:44:34,950 --> 00:44:36,640
Omdat één van hen zal verdwalen.

1055
00:44:36,640 --> 00:44:41,696
Als we zeiden A is gelijk aan B en vervolgens B
gelijk is aan A, alle ineens beiden

1056
00:44:41,696 --> 00:44:43,150
zijn gelijk aan B.

1057
00:44:43,150 --> 00:44:45,720
>> Dus wat we moeten doen is dat we
een tijdelijke variabele die

1058
00:44:45,720 --> 00:44:49,055
gaat een van ons, terwijl houden
we zijn in het proces van swappen.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Dus wat we hebben is dat we u een aantal int hebben
temp is gelijk to-- je het kan toewijzen

1061
00:44:56,464 --> 00:44:59,130
aan welke u wilt, gewoon
zorg ervoor dat u spoor van het-- houden

1062
00:44:59,130 --> 00:45:01,840
dus in dit geval, ik ga
toewijzen aan array-n plus 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Dus dat gaat houden wat
waarde in die tweede blok

1065
00:45:07,674 --> 00:45:08,590
dat we naar kijken.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> En dan kunnen we doen is dat we kunnen gaan
vooruit en ken scala n plus 1,

1068
00:45:13,240 --> 00:45:14,990
omdat we weten dat we
hebben dat opgeslagen waarde.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Dit is een van de grote
things-- Ik weet niet of iemand van jullie

1071
00:45:19,270 --> 00:45:23,780
had problemen waar als je twee schakelen
regels code plotseling dingen werkten.

1072
00:45:23,780 --> 00:45:25,880
Volgorde is zeer belangrijk in CS.

1073
00:45:25,880 --> 00:45:29,450
Dus zorg ervoor dat je diagram
dingen uit, indien mogelijk

1074
00:45:29,450 --> 00:45:31,230
als om wat er daadwerkelijk gebeurt.

1075
00:45:31,230 --> 00:45:34,256
Dus nu gaan we naar
toewijzen scala n plus 1,

1076
00:45:34,256 --> 00:45:36,005
omdat we weten dat we
hebben dat opgeslagen waarde.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> En we kunnen toewijzen die array
n of in dit geval serie i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Te veel variabelen.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
OK.

1083
00:45:55,470 --> 00:46:01,500
Dus nu hebben we opnieuw toegewezen reeks i
plus 1 te evenaren wat er in reeks i.

1084
00:46:01,500 --> 00:46:08,240
En nu kunnen we terug te gaan en
toewijzen scala ik aan wat?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Anyone?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> STUDENT: 10.

1089
00:46:14,010 --> 00:46:14,680
>> INSTRUCTEUR: 10.

1090
00:46:14,680 --> 00:46:15,180
Precies.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
En een laatste ding.

1093
00:46:18,640 --> 00:46:21,840
Als we het nu hebben verwisseld,
wat hebben we nodig om te doen?

1094
00:46:21,840 --> 00:46:23,740
Wat is het een ding
dat gaat ons vertellen

1095
00:46:23,740 --> 00:46:27,542
als we ooit dit programma te beëindigen?

1096
00:46:27,542 --> 00:46:29,250
Wat vertelt ons dat we
hebben een gesorteerde lijst?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Als we geen swaps uit te voeren, toch?

1099
00:46:33,750 --> 00:46:36,900
Als swaps is gelijk aan
nul aan het einde van deze.

1100
00:46:36,900 --> 00:46:42,975
Dus wanneer je een swap uit te voeren, zoals we
gewoon hier deden, we willen swaps updaten.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
En ik weet dat er een
vraag eerder over dan kunt u

1103
00:46:47,210 --> 00:46:49,689
Gebruik nul of één plaats
van waar of onwaar.

1104
00:46:49,689 --> 00:46:50,980
En dat is wat dit hier doet.

1105
00:46:50,980 --> 00:46:52,750
Dus dit zegt als niet swaps.

1106
00:46:52,750 --> 00:47:01,310
Dus als swaps is nul, wat ik altijd is--
krijg mijn waarheden en mijn falses door elkaar.

1107
00:47:01,310 --> 00:47:03,960
We willen ons om te evalueren
om waar en het is niet.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Dus als het nul is, dan is het vals.

1110
00:47:09,630 --> 00:47:12,560
Als je het ontkennen met een
[? bang?] het waar wordt.

1111
00:47:12,560 --> 00:47:13,975
Dus dan is deze lijn voert.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Waarheden en valse en
nullen en enen gek.

1114
00:47:17,370 --> 00:47:20,690
Net als je langzaam lopen
doorheen het zal zinvol.

1115
00:47:20,690 --> 00:47:23,320
Maar dat is wat deze kleine
stukje code hier doet.

1116
00:47:23,320 --> 00:47:26,490
Dus dit controleert
hebben we gedaan elke swaps.

1117
00:47:26,490 --> 00:47:30,054
Dus als het even wat naast
nul, het gaat vals te zijn

1118
00:47:30,054 --> 00:47:31,970
en de hele zaak is
gaat opnieuw uit.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
Cool?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> STUDENT: Wat doet break doen?

1123
00:47:36,000 --> 00:47:38,990
>> INSTRUCTEUR: Break net
breekt u uit de lus.

1124
00:47:38,990 --> 00:47:41,570
Dus in dit geval zou
net als het einde van het programma

1125
00:47:41,570 --> 00:47:43,828
en je zou gewoon
hebben uw gesorteerde lijst.

1126
00:47:43,828 --> 00:47:44,536
STUDENT: Amazing.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
INSTRUCTEUR: Het spijt me?

1129
00:47:49,010 --> 00:47:52,110
STUDENT: Omdat we eerder
gebruikte geschreven 1 overschreven nul

1130
00:47:52,110 --> 00:47:54,170
presenteren dat als
dat zal niet werken of niet.

1131
00:47:54,170 --> 00:47:54,878
>> INSTRUCTEUR: Yeah.

1132
00:47:54,878 --> 00:47:56,410
Dus u kunt nul of 1 terug te keren.

1133
00:47:56,410 --> 00:47:58,950
In dit geval, omdat we niet echt
iets te doen met de functie,

1134
00:47:58,950 --> 00:48:00,150
we willen gewoon het te breken.

1135
00:48:00,150 --> 00:48:02,680
We niet echt zorgen over.

1136
00:48:02,680 --> 00:48:06,960
Rem is ook goed als
het wordt gebruikt voor het breken uit

1137
00:48:06,960 --> 00:48:10,710
vier lussen of condities die
u niet wilt behouden uitvoeren.

1138
00:48:10,710 --> 00:48:12,110
Het kost je gewoon van hen.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Het is een beetje een nuance ding.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Ik heb het gevoel alsof er
veel wuivende hand,

1143
00:48:18,445 --> 00:48:19,740
als je leert over dit binnenkort.

1144
00:48:19,740 --> 00:48:20,955
>> Maar leer je over dit binnenkort.

1145
00:48:20,955 --> 00:48:21,500
Ik beloof het.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
OK.

1148
00:48:23,170 --> 00:48:24,840
Dus doet iedereen krijgt bubble sort?

1149
00:48:24,840 --> 00:48:25,550
Niet al te slecht.

1150
00:48:25,550 --> 00:48:31,910
Doorloopt, swap dingen met behulp van een
temp variabele, en we zijn er allemaal ingesteld?

1151
00:48:31,910 --> 00:48:32,960
Cool.

1152
00:48:32,960 --> 00:48:34,080
Awesome.

1153
00:48:34,080 --> 00:48:34,807
OK.

1154
00:48:34,807 --> 00:48:35,765
Terug naar de PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Heeft u vragen in het algemeen
over deze tot nu toe?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
Cool.

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
Mm-hm.

1161
00:48:43,695 --> 00:48:45,279
>> STUDENT: [onverstaanbaar] int main meestal.

1162
00:48:45,279 --> 00:48:46,695
Heeft u te hebben dat voor dit?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> INSTRUCTEUR: Dus we waren gewoon op zoek
alleen op de eigenlijke sorteren algoritme.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Als je het had binnen
als een groter programma,

1167
00:48:56,350 --> 00:48:57,891
zou je een int main ergens hebben.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
Afhankelijk van waar u
Gebruik algoritme,

1170
00:49:02,880 --> 00:49:05,860
het zou bepalen wat er
wordt geretourneerd door het.

1171
00:49:05,860 --> 00:49:09,960
Maar voor ons geval, we zijn strikt
kijken naar hoe werkt dit eigenlijk

1172
00:49:09,960 --> 00:49:11,300
doorlopen van een array.

1173
00:49:11,300 --> 00:49:12,570
Dus we hebben geen zorgen over te maken.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Dus hadden we het over het beste geval en
worst-case scenario's voor binary search.

1176
00:49:19,830 --> 00:49:22,470
Dus het is ook belangrijk om te doen
dat voor elk van onze soorten.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Dus wat denk je dat is het ergste
Bij runtime van bubble sort?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Jullie herinneren?

1181
00:49:30,700 --> 00:49:31,784
>> STUDENT: N min 1.

1182
00:49:31,784 --> 00:49:32,700
INSTRUCTEUR: N min 1.

1183
00:49:32,700 --> 00:49:35,070
Dus dat betekent dat er
n minus 1 vergelijkingen.

1184
00:49:35,070 --> 00:49:40,060
Dus een ding om te beseffen is
dat op de eerste iteratie,

1185
00:49:40,060 --> 00:49:43,360
we gaan door, we vergelijken
deze two-- dus dat is 1.

1186
00:49:43,360 --> 00:49:46,685
Deze twee, drie, vier.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Dus na een iteratie we
al vier vergelijkingen.

1189
00:49:55,050 --> 00:49:58,230
Toen ik het over runtime en n.

1190
00:49:58,230 --> 00:50:04,680
N het aantal vergelijkingen
als functie van het aantal elementen

1191
00:50:04,680 --> 00:50:05,570
we hebben.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Dus doorlopen we, hebben we vier.

1194
00:50:08,860 --> 00:50:11,780
De volgende keer dat je weet dat we dat niet doen
moeten zorgen voor dit.

1195
00:50:11,780 --> 00:50:15,140
We vergelijken deze twee,
beide deze twee,

1196
00:50:15,140 --> 00:50:20,050
en als we niet hebben dat optimalisatie
met de vier lus die ik heb geschreven,

1197
00:50:20,050 --> 00:50:22,750
je zou hier een vergelijking in anyways.

1198
00:50:22,750 --> 00:50:26,170
Dus je zou moeten
lopen door de array

1199
00:50:26,170 --> 00:50:34,380
en maak n vergelijkingen n
tijden, want elke keer als we

1200
00:50:34,380 --> 00:50:36,670
er doorheen lopen we eigenlijk een ding.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> En elke keer als we lopen door
de array, maken we n vergelijkingen.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Dus onze runtime hiervoor is
eigenlijk n kwadraat, die

1205
00:50:46,330 --> 00:50:48,400
is veel erger in onze
inloggen end want dat

1206
00:50:48,400 --> 00:50:51,965
betekent dat als we hadden vier
miljard elementen, het

1207
00:50:51,965 --> 00:50:55,260
gaat ons 4000000000
kwadraat ipv 32.

1208
00:50:55,260 --> 00:51:01,240
Dus niet de beste runtime,
maar voor sommige dingen,

1209
00:51:01,240 --> 00:51:04,610
weet je, als je binnen
een bepaald bereik van elementen

1210
00:51:04,610 --> 00:51:06,540
bubble sort kan zijn prima te gebruiken.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Dus nu wat is de beste case runtime?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
STUDENT: Zero?

1215
00:51:14,940 --> 00:51:16,420
Of 1?

1216
00:51:16,420 --> 00:51:18,140
>> INSTRUCTEUR: Dus 1 zou
één vergelijking.

1217
00:51:18,140 --> 00:51:19,114
Right.

1218
00:51:19,114 --> 00:51:20,002
>> STUDENT: N min 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> INSTRUCTEUR: Dus, ja.

1221
00:51:22,320 --> 00:51:22,990
Zo n minus 1.

1222
00:51:22,990 --> 00:51:26,510
Wanneer heb je een concept als n
minus 1, hebben we de neiging om gewoon deze inleveren

1223
00:51:26,510 --> 00:51:31,680
en we gewoon zeggen n omdat je
elk van these-- elk paar vergelijken.

1224
00:51:31,680 --> 00:51:36,470
Zo zou n minus 1, welke we
we gewoon zou zeggen dat is ongeveer n.

1225
00:51:36,470 --> 00:51:39,280
Wanneer je te maken hebt met runtime,
alles is in bij benadering.

1226
00:51:39,280 --> 00:51:43,860
Zolang de exponent
correct, je bent behoorlijk goed.

1227
00:51:43,860 --> 00:51:45,700
>> Dat is hoe we omgaan met het.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Zodat het beste geval is n, dat
betekent dat de lijst al is gesorteerd,

1230
00:51:51,780 --> 00:51:54,320
en alles wat we doen wordt gerund door
en controleer of het is opgelost.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
Cool.

1233
00:51:56,855 --> 00:51:57,355
Prima.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Dus zoals je hier ziet, we
gewoon wat meer grafieken.

1236
00:52:01,920 --> 00:52:02,660
Zo n kwadraat.

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
Fun.

1239
00:52:05,120 --> 00:52:09,730
Veel slechter dan n zoals we zien, en
veel, veel erger dan log 2n.

1240
00:52:09,730 --> 00:52:12,060
En dan krijg je ook in logboek logboeken.

1241
00:52:12,060 --> 00:52:18,020
En je 124 nemen, krijg je in
als log ster, die is als een gek.

1242
00:52:18,020 --> 00:52:20,172
Dus als je geïnteresseerd bent,
lookup log ster.

1243
00:52:20,172 --> 00:52:20,880
Het is wel leuk.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Dus we hebben deze grote grafiek.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Gewoon een heads up, dit een
prachtige grafiek om te hebben

1248
00:52:28,720 --> 00:52:31,350
voor de middellange termijn, omdat we
lang om u te vragen deze dunner.

1249
00:52:31,350 --> 00:52:36,090
Dus gewoon een heads up, heb dit op uw
tussenbalans op uw mooie spiekbriefje

1250
00:52:36,090 --> 00:52:36,616
daar.

1251
00:52:36,616 --> 00:52:37,990
Dus we keken naar bubble sort.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
Worst case, n kwadraat, best case, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
En we gaan kijken naar de anderen.

1256
00:52:44,950 --> 00:52:47,940
>> En zoals je kunt zien, de enige
een die echt goed doet

1257
00:52:47,940 --> 00:52:50,910
is merge soort, die we zullen krijgen in waarom.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Dus we gaan naar de
volgende hier-- selectie sorteren.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Heeft iemand nog hoe
selectie sorteren gewerkt?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Ga ervoor.

1264
00:53:05,700 --> 00:53:08,210
>> STUDENT: In principe gaan door
een bestelling en maak een nieuwe lijst.

1265
00:53:08,210 --> 00:53:11,001
En net als je het aantrekken elementen
in, leg ze op de juiste plaats

1266
00:53:11,001 --> 00:53:11,750
in de nieuwe lijst.

1267
00:53:11,750 --> 00:53:14,040
>> INSTRUCTEUR: Dus dat geluiden
meer als insertion sort.

1268
00:53:14,040 --> 00:53:15,040
Maar je bent echt dichtbij.

1269
00:53:15,040 --> 00:53:15,915
Ze zijn zeer vergelijkbaar.

1270
00:53:15,915 --> 00:53:17,440
Zelfs ik ze door elkaar soms.

1271
00:53:17,440 --> 00:53:18,981
Voordat deze sectie Ik was als, wacht.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
OK.

1274
00:53:20,630 --> 00:53:24,141
Dus wat je wilt
doen is selectie sorteren,

1275
00:53:24,141 --> 00:53:25,890
de manier waarop je kunt bedenken
over en de weg

1276
00:53:25,890 --> 00:53:30,140
Ik zorg ervoor dat ik probeer niet te krijgen
ze door elkaar, is gaat het door

1277
00:53:30,140 --> 00:53:33,280
en selecteert de
kleinste getal en het

1278
00:53:33,280 --> 00:53:36,070
zet dat aan het begin van uw lijst.

1279
00:53:36,070 --> 00:53:37,730
Hij ruilt het met die eerste plek.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
Ze hebben eigenlijk een voorbeeld voor mij.

1282
00:53:45,370 --> 00:53:46,540
Awesome.

1283
00:53:46,540 --> 00:53:50,130
Dus gewoon een manier om te denken van het-- selectie
sorteren, selecteert u de kleinste waarde.

1284
00:53:50,130 --> 00:53:51,940
En we gaan
Onderstaand voorbeeld van

1285
00:53:51,940 --> 00:53:55,320
dat ik denk dat zal helpen, want
Ik denk visuals altijd helpen.

1286
00:53:55,320 --> 00:53:58,510
Dus we beginnen met iets
dat is volkomen ongesorteerd.

1287
00:53:58,510 --> 00:54:00,730
Red zal ongesorteerd zijn,
groen worden gesorteerd.

1288
00:54:00,730 --> 00:54:02,190
Het zal allemaal zin in een tweede.

1289
00:54:02,190 --> 00:54:08,950
>> Dus gaan we door en we herhalen
van het begin tot het einde.

1290
00:54:08,950 --> 00:54:12,320
En we zeggen, OK, 2 is
onze kleinste getal.

1291
00:54:12,320 --> 00:54:15,680
Dus we gaan nemen 2 en we gaan
om het te verplaatsen naar de voorkant van ons aanbod

1292
00:54:15,680 --> 00:54:17,734
want het is de
kleinste getal hebben we.

1293
00:54:17,734 --> 00:54:19,150
Dus dat is wat dit hier doet.

1294
00:54:19,150 --> 00:54:20,820
Het gaat gewoon om te wisselen die twee.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Dus nu hebben we een gesorteerde
deel en een ongesorteerd deel.

1297
00:54:25,450 --> 00:54:27,810
En wat is goed om te onthouden
over selectie sorteren

1298
00:54:27,810 --> 00:54:30,690
is dat we alleen selecteren
uit het ongesorteerde deel.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> De gesorteerde deel je gewoon laat staan.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> STUDENT: Hoe weet het wat is
de kleinste zonder het te vergelijken

1303
00:54:38,452 --> 00:54:39,868
elke andere waarde in de array.

1304
00:54:39,868 --> 00:54:41,250
INSTRUCTEUR: Het doet vergelijken.

1305
00:54:41,250 --> 00:54:42,041
Wij willen overgeslagen.

1306
00:54:42,041 --> 00:54:43,850
Dit is gewoon algemeen algemeen.

1307
00:54:43,850 --> 00:54:44,831
Yeah.

1308
00:54:44,831 --> 00:54:47,205
Wanneer we de code schrijven ben ik
zeker dat je meer tevreden.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Maar je deze eerst op te slaan
element als kleinste.

1311
00:54:53,030 --> 00:54:56,110
U vergelijkt en je
zeggen, OK, is het kleiner?

1312
00:54:56,110 --> 00:54:56,660
Ja.

1313
00:54:56,660 --> 00:54:57,460
Keep it.

1314
00:54:57,460 --> 00:54:58,640
Hier is het kleiner?

1315
00:54:58,640 --> 00:54:59,660
Nee?

1316
00:54:59,660 --> 00:55:02,510
>> Dit is uw kleinste,
toewijzen aan uw waarde.

1317
00:55:02,510 --> 00:55:06,340
En je zult veel gelukkiger zijn
toen we door de code.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Dus we gaan door, ruilen we het, dus dan
we kijken naar deze ongesorteerd deel.

1320
00:55:13,970 --> 00:55:15,810
Dus we gaan naar drie te selecteren.

1321
00:55:15,810 --> 00:55:18,890
We gaan om het aan te zetten op
het einde van onze gesorteerde gedeelte.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
En we gaan gewoon blijven doen
dat, om dat te doen, en dat doen.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Dus dit is onze soort pseudocode hier.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
We zullen het coderen hier in een tweede.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Maar gewoon iets om te lopen
door op een hoog niveau.

1330
00:55:37,270 --> 00:55:40,275
Je gaat om te gaan van
i gelijk is aan 0 tot n minus 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
Dat is een andere optimalisatie.

1333
00:55:43,530 --> 00:55:45,020
Niet te veel zorgen over te maken.

1334
00:55:45,020 --> 00:55:46,620
Dus zoals je zei.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Zoals Jacob zei, hoe doen we
bijhouden wat onze minimum is?

1337
00:55:54,406 --> 00:55:55,030
Hoe weten we dat?

1338
00:55:55,030 --> 00:55:57,060
We moeten vergelijken
alles in onze lijst.

1339
00:55:57,060 --> 00:55:59,600
>> Dus minimum is gelijk aan i.

1340
00:55:59,600 --> 00:56:03,870
Het is gewoon te zeggen in dit geval
de index van onze minimale waarde.

1341
00:56:03,870 --> 00:56:07,660
Dus dan is dat het gaat om door te herhalen
en het gaat van j i gelijk plus 1.

1342
00:56:07,660 --> 00:56:11,420
Dus we weten al dat
dat is onze eerste element.

1343
00:56:11,420 --> 00:56:13,240
We hoeven niet te vergelijken met zichzelf.

1344
00:56:13,240 --> 00:56:16,970
Dus beginnen te vergelijken met de volgende
een die is waarom het i plus 1 tot n

1345
00:56:16,970 --> 00:56:20,110
minus 1, die de
einde van de array zijn.

1346
00:56:20,110 --> 00:56:25,090
En we zeiden dat als array
j is dan matrix min,

1347
00:56:25,090 --> 00:56:29,200
vervolgens toewijzen we waar
onze minimale indices is.

1348
00:56:29,200 --> 00:56:37,470
>> Als min niet gelijk i, zoals
in waar waren we terug over hier.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Dus als toen we voor het eerst deed dit één.

1351
00:56:41,790 --> 00:56:49,310
In dit geval zou het beginnen
nul, het zou uiteindelijk op twee.

1352
00:56:49,310 --> 00:56:53,010
Zo min zou niet gelijk ik in het einde.

1353
00:56:53,010 --> 00:56:55,720
Dat laat ons weten dat
we nodig hebben om ze te verwisselen.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Ik voel me als een concreet voorbeeld
zal veel meer dan dit te helpen.

1356
00:57:00,470 --> 00:57:04,970
Dus ik zal deze code met jullie
op dit moment en ik denk dat het zal beter zijn.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Soorten hebben de neiging om op die manier in die werken
is het vaak beter gewoon om ze te zien.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Dus wat we willen doen is
we willen eerst de kleinste

1361
00:57:17,280 --> 00:57:19,890
element in zijn positie in de array.

1362
00:57:19,890 --> 00:57:21,280
Precies wat Jacob zei.

1363
00:57:21,280 --> 00:57:23,090
Je moet een of andere manier op te slaan dat.

1364
00:57:23,090 --> 00:57:25,900
Dus we gaan hier beginnen
itereren over de array.

1365
00:57:25,900 --> 00:57:28,970
We gaan om te zeggen dat het onze
eerste net beginnen.

1366
00:57:28,970 --> 00:57:38,308
Dus we gaan int hebben
kleinste is gelijk aan scala aan i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Dus een ding om op te merken, elke
tijd deze lus wordt uitgevoerd,

1369
00:57:45,050 --> 00:57:48,550
starten we een stap verder mee.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Wanneer we beginnen we kijken naar deze.

1372
00:57:57,440 --> 00:58:00,840
De volgende keer dat we doorlopen,
we beginnen bij deze ene

1373
00:58:00,840 --> 00:58:02,680
en toe te wijzen onze kleinste waarde.

1374
00:58:02,680 --> 00:58:10,450
Dus het is zeer vergelijkbaar met bubble sort
waarvan we weten dat na één passage,

1375
00:58:10,450 --> 00:58:11,700
dit laatste element wordt gesorteerd.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Met selectie sorteren,
het is juist het tegenovergestelde.

1378
00:58:15,120 --> 00:58:18,950
>> Bij elke pas, weten we dat
de eerste wordt gesorteerd.

1379
00:58:18,950 --> 00:58:21,360
Na de tweede pas, de
zal tweede gesorteerd worden.

1380
00:58:21,360 --> 00:58:26,470
En als je zag met de glijbaan voorbeelden,
onze naargelang deel maar door blijft groeien.

1381
00:58:26,470 --> 00:58:34,020
Dus door het instellen van onze kleinste
arrays ik, alles wat het aan het doen is

1382
00:58:34,020 --> 00:58:37,340
beperkt het wat
we kijken naar zo

1383
00:58:37,340 --> 00:58:40,164
het nummer minimaliseren
van vergelijkingen die we maken.

1384
00:58:40,164 --> 00:58:41,770
Is dat zinvol voor iedereen?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Hou je me nodig hebt om te draaien door die
weer langzamer of in andere woorden?

1387
00:58:46,380 --> 00:58:47,180
Ik ben blij om.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
OK.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> Dus we zijn het opslaan van de
waarde op dit punt,

1392
00:58:55,540 --> 00:58:57,840
maar we willen ook de index op te slaan.

1393
00:58:57,840 --> 00:59:01,010
Dus we gaan naar de winkel
positie van de kleinste

1394
00:59:01,010 --> 00:59:02,770
één, die net gaat i zijn.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Dus nu Jacob is tevreden.

1397
00:59:05,440 --> 00:59:06,870
We hebben dingen opgeslagen.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
En nu moeten we kijken door
het ongesorteerde deel van de array.

1400
00:59:11,870 --> 00:59:18,170
Dus in dit geval is dit
zou onze ongesorteerd zijn.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
Dit is i.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
OK.

1405
00:59:26,210 --> 00:59:30,040
>> Dus wat we gaan doen
zal voor een lus.

1406
00:59:30,040 --> 00:59:32,066
Wanneer u maar wilt
doorloopt een array,

1407
00:59:32,066 --> 00:59:33,440
je geest kon gaan voor een lus.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Dus voor sommige int k
equals-- wat vinden we

1410
00:59:38,090 --> 00:59:39,700
k zal gelijk beginnen?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
Dit is wat we als onze kleinste
waarde en we willen om het te vergelijken.

1413
00:59:44,766 --> 00:59:47,090
Wat willen we te vergelijken met?

1414
00:59:47,090 --> 00:59:48,730
Het gaat om deze volgende, toch?

1415
00:59:48,730 --> 00:59:53,200
Dus we willen k te worden geïnitialiseerd
i plus 1 beginnen.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> En we willen dat k in dit geval hebben we
al hebben de grootte hier opgeslagen up,

1418
01:00:02,800 --> 01:00:03,930
dus we kunnen gewoon gebruik maken van de grootte.

1419
01:00:03,930 --> 01:00:06,240
Maat zijnde de grootte van de matrix.

1420
01:00:06,240 --> 01:00:09,620
En we willen gewoon
bijwerken k telkens met één.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
Cool.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
Dus nu moeten we vinden
het kleinste element hier.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Dus als we doorlopen, we
willen zeggen, als array k

1427
01:00:31,380 --> 01:00:37,080
is minder dan onze kleinste value--
dit is waar we eigenlijk

1428
01:00:37,080 --> 01:00:42,950
het bijhouden van wat er
de kleinste hier--

1429
01:00:42,950 --> 01:00:47,740
dan willen we toewijzen
wat onze kleinste waarde is.

1430
01:00:47,740 --> 01:00:50,645
>> Dit betekent dat, oh, we zijn
iteratie hier.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Wat waarde hier
niet onze kleinste ding.

1433
01:00:53,740 --> 01:00:54,448
We willen het niet.

1434
01:00:54,448 --> 01:00:56,100
We willen deze grond.

1435
01:00:56,100 --> 01:01:02,050
Dus als we het opnieuw toewijzen van het, wat doen
je denkt misschien in deze code hier?

1436
01:01:02,050 --> 01:01:04,160
We willen toewijzen
kleinste en positie.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Dus wat is het kleinste nu?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
STUDENT: Array k.

1441
01:01:09,130 --> 01:01:09,963
INSTRUCTEUR: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
En wat is de positie nu?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Wat is de indices van
onze kleinste waarde?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
Het is gewoon k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Dus scala k, k, ze met elkaar overeenkomen.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Dus wilden we opnieuw toekennen.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
En dan na vonden we onze kleinste,
zodat aan het einde van deze lus

1454
01:01:39,950 --> 01:01:45,100
hier hebben we gevonden wat onze kleinste
waarde is, dus we wisselen het gewoon.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
In dit geval, net als zeggen dat onze
kleinste waarde is hier.

1457
01:01:50,816 --> 01:01:51,940
Dit is onze kleinste waarde.

1458
01:01:51,940 --> 01:01:57,690
>> We willen alleen maar om het hier te ruilen, dat is
wat dat swap-functie op de bodem

1459
01:01:57,690 --> 01:02:01,270
deed, die we zojuist schreef
samen een paar minuten geleden.

1460
01:02:01,270 --> 01:02:02,775
Dus het zal geen groot probleem.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
En dan zal het alleen maar herhalen
door tot het helemaal bereikt

1463
01:02:08,030 --> 01:02:13,100
aan het einde, waardoor u
hebben nul elementen die ongesorteerde

1464
01:02:13,100 --> 01:02:14,800
en alles is gesorteerd.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Zinvol?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Een beetje meer concreet?

1469
01:02:19,280 --> 01:02:19,990
De code helpen?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> STUDENT: Voor een grootte, die u nooit
echt het definiëren of wijzigen,

1472
01:02:26,410 --> 01:02:27,340
hoe weet het?

1473
01:02:27,340 --> 01:02:32,380
>> INSTRUCTEUR: Dus een ding om
merken hier is int size.

1474
01:02:32,380 --> 01:02:35,680
Dus we zeggen in dit sort-- soort
is een functie in deze case-- het

1475
01:02:35,680 --> 01:02:40,770
selectie soort, het is voorbij
met de functie.

1476
01:02:40,770 --> 01:02:43,460
Dus als het niet is overgegaan
in, zou je iets doen

1477
01:02:43,460 --> 01:02:47,840
zoals de lengte van de array
of zou je via herhalen

1478
01:02:47,840 --> 01:02:49,390
de lengte vinden.

1479
01:02:49,390 --> 01:02:52,680
Maar omdat het is voorbij
in, kunnen we gewoon gebruiken.

1480
01:02:52,680 --> 01:02:55,720
U aanvaardt alleen dat de gebruiker
gaf je een geldig formaat dat

1481
01:02:55,720 --> 01:02:57,698
vertegenwoordigt eigenlijk
een grootte van uw array.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
Cool?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> Als jullie problemen hebt met deze
of wilt u meer praktijk codering soorten

1486
01:03:05,870 --> 01:03:08,050
op uw eigen, moet u
ga naar study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
Het is een hulpmiddel.

1489
01:03:12,670 --> 01:03:15,040
Ze hebben een checker dat
kan je eigenlijk schrijven.

1490
01:03:15,040 --> 01:03:16,180
Ze doen pseudocode.

1491
01:03:16,180 --> 01:03:19,310
Zij hebben meer video's en dia's
inclusief degenen die ik hier gebruik.

1492
01:03:19,310 --> 01:03:23,150
Dus als je nog steeds het gevoel een
beetje wazig, probeer dat uit.

1493
01:03:23,150 --> 01:03:25,670
Zoals altijd, kom met me praten, ook.

1494
01:03:25,670 --> 01:03:26,320
Vraag?

1495
01:03:26,320 --> 01:03:28,611
>> STUDENT: Bedoel je dat de
maat is eerder gedefinieerd?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
INSTRUCTEUR: Ja.

1498
01:03:29,900 --> 01:03:35,570
Grootte is eerder gedefinieerde up
hier in de functie declaratie.

1499
01:03:35,570 --> 01:03:39,060
Zodat u ervan uitgaan dat het is aangenomen in
door de gebruiker, en voor het gemak,

1500
01:03:39,060 --> 01:03:41,896
we gaan ervan uit dat de
gebruiker gaf ons de juiste maat.

1501
01:03:41,896 --> 01:03:43,240
Cool.

1502
01:03:43,240 --> 01:03:44,390
Dus dat is selectie sorteren.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Jongens, ik weet dat we veel leren vandaag.

1505
01:03:47,640 --> 01:03:49,710
Het is een dichte gegevens voor sectie.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Dus met dat gaan we
naar insertion sort.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> OK.

1510
01:04:02,510 --> 01:04:06,100
Dus voordat dat we moeten doen
onze runtime analyse hier.

1511
01:04:06,100 --> 01:04:10,190
Dus in het beste geval,
verleend, omdat ik je liet zien

1512
01:04:10,190 --> 01:04:11,960
de tafel heb ik al
soort gaf het weg.

1513
01:04:11,960 --> 01:04:15,430
Maar het beste geval runtime, wat vinden we?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Alles gesorteerd worden.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N kwadraat.

1518
01:04:22,070 --> 01:04:24,780
Iedereen heeft een verklaring
waarom je denkt?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> STUDENT: je vergelijkt through--

1521
01:04:30,519 --> 01:04:31,268
INSTRUCTEUR: Right.

1522
01:04:31,268 --> 01:04:32,540
Je vergelijkt door.

1523
01:04:32,540 --> 01:04:35,630
Bij elke iteratie, hoewel
we decrementing dit door één,

1524
01:04:35,630 --> 01:04:38,950
je bent nog steeds op zoek door middel van
alles tot in de kleinste een te vinden.

1525
01:04:38,950 --> 01:04:42,390
Dus zelfs als uw kleinste waarde
is hier aan het begin,

1526
01:04:42,390 --> 01:04:44,710
je bent het nog steeds te vergelijken
tegen al het andere

1527
01:04:44,710 --> 01:04:46,550
om ervoor te zorgen dat het de kleinste ding.

1528
01:04:46,550 --> 01:04:49,820
Dus zul je uiteindelijk doorheen
ongeveer n kwadraat tijden.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Prima.

1531
01:04:51,590 --> 01:04:52,785
En wat is het ergste geval?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Ook n kwadraat want je gaat
te doen, dat dezelfde procedure.

1534
01:04:57,980 --> 01:05:01,670
Dus in dit geval, selectie
heeft een soort iets

1535
01:05:01,670 --> 01:05:04,010
dat we ook bellen verwachte runtime.

1536
01:05:04,010 --> 01:05:07,400
Dus in de anderen, we weten gewoon
de bovenste en onderste grenzen.

1537
01:05:07,400 --> 01:05:11,180
Afhankelijk van hoe gek onze
lijst is of hoe ongesorteerd het is,

1538
01:05:11,180 --> 01:05:15,350
ze variëren tussen n en n kwadraat.

1539
01:05:15,350 --> 01:05:16,550
We weten het niet.

1540
01:05:16,550 --> 01:05:22,820
>> Maar omdat selectie soort heeft dezelfde
slechtste en het beste geval, dat ons vertelt dat

1541
01:05:22,820 --> 01:05:25,880
het maakt niet uit wat voor soort input die we
hebben, of het nu helemaal

1542
01:05:25,880 --> 01:05:29,130
gesorteerde of volledig
achteruit naargelang, het is

1543
01:05:29,130 --> 01:05:30,740
naar dezelfde hoeveelheid tijd.

1544
01:05:30,740 --> 01:05:33,760
Dus in dat geval, als je
herinneren uit onze tafel,

1545
01:05:33,760 --> 01:05:38,610
het eigenlijk had een waarde
deze twee soorten niet hebben,

1546
01:05:38,610 --> 01:05:40,390
die verwacht runtime.

1547
01:05:40,390 --> 01:05:43,350
Zodat we weten dat wanneer
we lopen selectie sorteren,

1548
01:05:43,350 --> 01:05:45,380
het is gegarandeerd om
uitvoeren van een n kwadraat tijd.

1549
01:05:45,380 --> 01:05:46,630
Er is geen variatie zijn.

1550
01:05:46,630 --> 01:05:47,630
Het is gewoon te verwachten.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
En, nogmaals, als je wilt leren
meer, neem CS 124 in het voorjaar.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Prima.

1555
01:05:56,712 --> 01:05:57,545
We hebben dit gezien.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
Cool.

1558
01:05:59,030 --> 01:06:00,930
Dus insertion sort.

1559
01:06:00,930 --> 01:06:03,330
En ik ga waarschijnlijk
ontbrandde nu doorheen.

1560
01:06:03,330 --> 01:06:05,440
Ik wil niet dat jullie het coderen.

1561
01:06:05,440 --> 01:06:06,580
We zullen gewoon doorheen lopen.

1562
01:06:06,580 --> 01:06:10,500
Dus insertion sort is een soort
van vergelijkbaar selectie sorteren

1563
01:06:10,500 --> 01:06:14,460
dat we zowel ongesorteerd
en gesorteerd deel van de array.

1564
01:06:14,460 --> 01:06:20,260
>> Maar wat is er anders is dat
als we door een voor een,

1565
01:06:20,260 --> 01:06:24,210
we gewoon nemen wat het aantal
is de volgende in onze ongesorteerd,

1566
01:06:24,210 --> 01:06:28,507
en correct sorteren van het
in onze gesorteerde array.

1567
01:06:28,507 --> 01:06:30,090
Het zal meer zin te maken met een voorbeeld.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Dus alles begint als ongesorteerd,
net als met de selectie sorteren.

1570
01:06:35,430 --> 01:06:38,740
En we gaan deze te sorteren
oplopende volgorde, zoals we zijn geweest.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Dus op onze eerste pas
We nemen de eerste waarde

1573
01:06:43,340 --> 01:06:46,700
en wij zeggen, OK, je bent
nu in een lijst door uzelf.

1574
01:06:46,700 --> 01:06:49,150
>> Omdat je in een lijst
door jezelf, je gesorteerd worden.

1575
01:06:49,150 --> 01:06:52,460
Proficiat voor het zijn de
eerste element in de array.

1576
01:06:52,460 --> 01:06:54,800
Je bent al al naargelang op uw eigen.

1577
01:06:54,800 --> 01:06:58,900
Dus nu hebben we een gesorteerde
en een ongesorteerde array.

1578
01:06:58,900 --> 01:07:01,760
Dus nu nemen we de eerste.

1579
01:07:01,760 --> 01:07:05,600
Wat gebeurt er tussen hier
en hier is dat we zeggen,

1580
01:07:05,600 --> 01:07:08,890
OK, we gaan kijken naar de
eerste waarde van onze ongesorteerde reeks

1581
01:07:08,890 --> 01:07:13,270
en we gaan invoeren in zijn
juiste plaats in de gesorteerde array.

1582
01:07:13,270 --> 01:07:21,460
>> Dus wat we doen is nemen we 5 en
we zeggen, OK, 5 groter is dan 3,

1583
01:07:21,460 --> 01:07:24,630
dus voegen we het precies goed
naar rechts daarvan.

1584
01:07:24,630 --> 01:07:25,130
We zijn goed.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Dus dan gaan we op naar onze volgende.

1587
01:07:28,420 --> 01:07:29,720
En we nemen 2.

1588
01:07:29,720 --> 01:07:34,330
Wij zeggen, OK, 2 minder
dan 3, dus we weten dat het

1589
01:07:34,330 --> 01:07:36,220
moet op de
voorkant van onze lijst nu.

1590
01:07:36,220 --> 01:07:41,800
Dus wat we doen is dat we duwen 3 en 5 naar beneden
en we bewegen 2 in die eerste sleuf.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Dus we zijn gewoon deze in
de juiste plaats het zou moeten zijn.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Dan kijken we naar onze
volgende, en we zeggen 6.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 is groter dan
alles in ons gesorteerde array,

1596
01:07:53,620 --> 01:07:56,000
dus we taggen het op tot het einde.

1597
01:07:56,000 --> 01:07:56,960
En dan kijken we naar 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 kleiner dan 6, is het minder
dan 5 maar het is groter dan 3.

1600
01:08:03,020 --> 01:08:06,270
Dus we steken het gewoon recht in
het midden tussen 3 en 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Zo te maken dat een beetje
beetje meer concreet,

1603
01:08:10,530 --> 01:08:12,280
hier is een soort van de
idee van wat er gebeurd is.

1604
01:08:12,280 --> 01:08:16,430
Dus voor elk ongesorteerd element, we
bepalen waar in de gesorteerde gedeelte

1605
01:08:16,430 --> 01:08:17,090
is.

1606
01:08:17,090 --> 01:08:20,680
>> Dus rekening houdend met de
gesorteerd en ongesorteerd,

1607
01:08:20,680 --> 01:08:26,080
we moeten doorkruisen door en figuur
waar het in de gesorteerde array past.

1608
01:08:26,080 --> 01:08:31,460
En we voegen er door het verschuiven van de
elementen rechts van beneden.

1609
01:08:31,460 --> 01:08:34,910
En dan houden we gewoon
itereren door tot we

1610
01:08:34,910 --> 01:08:39,270
hebben een volledig gesorteerde lijst
waar ongesorteerd is nu nul

1611
01:08:39,270 --> 01:08:41,720
en gesorteerde neemt de
totaliteit van onze lijst.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Dus, nogmaals, om dingen nog te maken
meer concreet, we hebben pseudocode.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Dus eigenlijk voor i is
gelijk aan 0 tot n minus 1,

1616
01:08:52,410 --> 01:08:54,790
dat is gewoon de lengte van ons aanbod.

1617
01:08:54,790 --> 01:09:00,979
We hebben een element dat gelijk is
de eerste array of de eerste indices.

1618
01:09:00,979 --> 01:09:03,200
We j gelijk aan die.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Dus terwijl j groter is dan
nul en de array, j minus 1

1621
01:09:09,210 --> 01:09:11,660
groter is dan de
element, dus alles wat het doen

1622
01:09:11,660 --> 01:09:17,479
is ervoor te zorgen dat
je j echt vertegenwoordigt

1623
01:09:17,479 --> 01:09:20,010
het ongesorteerde deel van de array.

1624
01:09:20,010 --> 01:09:30,745
>> Dus terwijl er nog steeds dingen
te sorteren en j min één is-- wat

1625
01:09:30,745 --> 01:09:31,840
is het element van haar?

1626
01:09:31,840 --> 01:09:34,760
J werd hier nooit gedefinieerd.

1627
01:09:34,760 --> 01:09:35,677
Het is een beetje vervelend.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Anyways.

1630
01:09:36,689 --> 01:09:39,899
Dus j minus 1, u controleren bent
het element voordat het.

1631
01:09:39,899 --> 01:09:46,460
Je zegt, OK, is het element
voordat waar ik am-- laten

1632
01:09:46,460 --> 01:09:47,540
eigenlijk trekken dit uit.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Dus laten we zeggen dat dit
zoals op onze tweede pass.

1635
01:09:56,830 --> 01:09:59,525
Dus ik zal gelijk zijn
1, welke hier.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Dus ik zal gelijk aan 1 zijn.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
Dit zou 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Prima.

1642
01:10:16,750 --> 01:10:20,945
Dus onze element in dit geval
gaat gelijk aan 4 is.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
En we hebben een aantal j dat is
gaan gelijk aan 1 zijn.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Oh, j wordt decrementing.

1647
01:10:30,971 --> 01:10:31,720
Dat is wat het is.

1648
01:10:31,720 --> 01:10:35,680
Dus j is gelijk aan i, dus wat is dit
gezegde is dat als we vooruit,

1649
01:10:35,680 --> 01:10:37,530
we zijn gewoon om ervoor te zorgen
dat we niet meer dan

1650
01:10:37,530 --> 01:10:43,520
indexeren op deze manier wanneer we proberen
om dingen in te voegen in onze gesorteerde lijst.

1651
01:10:43,520 --> 01:10:49,850
>> Dus wanneer j gelijk is aan 1 in dit geval
array-j minus een-- zo scala j minus 1

1652
01:10:49,850 --> 01:10:54,610
2 is in dit case-- als dat is
groter dan het element,

1653
01:10:54,610 --> 01:10:57,700
dan dit alles doet
verschuift dingen naar beneden.

1654
01:10:57,700 --> 01:11:04,790
Dus in dit geval, array j min één
zou scala nul, dat is 2 te zijn.

1655
01:11:04,790 --> 01:11:08,430
2 niet groter is dan 4,
zodat deze niet wordt uitgevoerd.

1656
01:11:08,430 --> 01:11:11,460
Dus de verschuiving niet beweegt naar beneden.

1657
01:11:11,460 --> 01:11:18,790
Wat dit doet is vaak precies
het verplaatsen van uw gesorteerde array naar beneden.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
In dit geval, eigenlijk, we
kon doen-- laten we deze 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Dus als we om door te lopen met
dit voorbeeld zijn we nu hier.

1662
01:11:31,970 --> 01:11:32,740
Dit wordt gesorteerd.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
Dit is ongesorteerd.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
Cool?

1667
01:11:39,860 --> 01:11:46,620
Dus ik gelijk aan 2, dus
onze element gelijk aan 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
En onze j gelijk is aan 2.

1670
01:11:52,270 --> 01:12:00,620
Dus we kijken door en wij
zeggen, OK, is het scala j min één

1671
01:12:00,620 --> 01:12:03,470
groter dan het element
dat we naar kijken?

1672
01:12:03,470 --> 01:12:05,540
En het antwoord is ja, toch?

1673
01:12:05,540 --> 01:12:11,275
4 is groter dan 3 en j
is 2, dus deze code wordt uitgevoerd.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Dus nu doen we een scala aan
2, dus hier, ruilen we ze.

1676
01:12:18,550 --> 01:12:25,620
Dus we gewoon zeggen, OK, array
2 is zal meer 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
En j gaat evenaren
j minus 1, die 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
Dat is verschrikkelijk, maar
jullie krijgen het idee.

1681
01:12:37,200 --> 01:12:38,360
J is nu gelijk aan 1.

1682
01:12:38,360 --> 01:12:44,360
En de vele j is gewoon gaat worden
gelijk aan ons element, waarvan 4 was.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
Ik gewist iets wat ik niet zou moeten
hebben of miswrote iets,

1685
01:12:48,570 --> 01:12:49,910
maar jullie krijgen het idee.

1686
01:12:49,910 --> 01:12:50,640
>> Het bewegen op n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
En dan als dit, het zou lus
weer en het zou zeggen, OK, j is 1 nu.

1689
01:12:57,960 --> 01:13:00,665
En de vele j minus 1 is nu 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Is 2 minder dan onze element?

1692
01:13:03,760 --> 01:13:04,540
Nee?

1693
01:13:04,540 --> 01:13:07,970
Dat betekent dat we hebben
ingevoegd dit element

1694
01:13:07,970 --> 01:13:10,110
in de juiste plaats in onze gesorteerde array.

1695
01:13:10,110 --> 01:13:14,400
Dan kunnen we hier rekening en wij zeggen,
OK, onze gesorteerde array is hier.

1696
01:13:14,400 --> 01:13:19,940
En het zou dit nummer 6 te nemen en
als, OK, is 6 minder dan dit aantal?

1697
01:13:19,940 --> 01:13:20,480
Nee?

1698
01:13:20,480 --> 01:13:21,080
Cool.

1699
01:13:21,080 --> 01:13:22,680
We zijn prima.

1700
01:13:22,680 --> 01:13:23,530
>> Doe het opnieuw.

1701
01:13:23,530 --> 01:13:24,740
We zeggen 7.

1702
01:13:24,740 --> 01:13:29,010
7 minder dan het einde
van onze gesorteerde array?

1703
01:13:29,010 --> 01:13:29,520
Nee

1704
01:13:29,520 --> 01:13:30,430
Dus we zijn prima.

1705
01:13:30,430 --> 01:13:32,760
Dus dit zou worden geregeld.

1706
01:13:32,760 --> 01:13:38,610
In principe al dit doet
wordt het zegt take

1707
01:13:38,610 --> 01:13:42,060
het eerste element van
uw ongesorteerde array,

1708
01:13:42,060 --> 01:13:46,010
erachter te komen waar het gaat
in uw gesorteerde array.

1709
01:13:46,010 --> 01:13:48,780
En dit duurt slechts zorg
van swaps om dat te doen.

1710
01:13:48,780 --> 01:13:51,300
Je bent eigenlijk gewoon omwisselen
totdat het op de juiste plek.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Het visuele beeld is dat je bent
verplaatsen alles naar beneden door dat te doen.

1713
01:13:56,990 --> 01:13:59,420
>> Dus het is net half bubble sort-esque.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Check out studie 50.

1716
01:14:03,420 --> 01:14:06,000
Ik beveel het proberen
Om deze code op uw eigen.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Als u problemen hebt of u wilt
zie voorbeeldcode voor een insertion sort,

1719
01:14:12,450 --> 01:14:13,750
laat het me weten.

1720
01:14:13,750 --> 01:14:14,500
Ik ben altijd in de buurt.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Dus ergste geval runtime
en best case runtime.

1723
01:14:20,200 --> 01:14:30,700
Zoals je man zag van de tafel heb ik al
liet u, het is zowel n kwadraat en n.

1724
01:14:30,700 --> 01:14:35,590
>> Dus soort afgaan van wat we gesproken
over met onze vorige soorten, slechtste

1725
01:14:35,590 --> 01:14:38,760
Bij runtime is dat als
het is volkomen ongesorteerd,

1726
01:14:38,760 --> 01:14:42,530
we al deze n maal vergelijken.

1727
01:14:42,530 --> 01:14:47,020
We doen een heleboel vergelijkingen
want als het in omgekeerde volgorde,

1728
01:14:47,020 --> 01:14:50,360
we gaan zeggen, OK, dit
hetzelfde is dit goed,

1729
01:14:50,360 --> 01:14:54,650
en deze zal moeten worden vergeleken
tegen de eerste worden terugbewogen.

1730
01:14:54,650 --> 01:14:56,710
En als we in de richting van
de staart, hebben we

1731
01:14:56,710 --> 01:14:59,440
te vergelijken, vergelijken en
vergelijk tegen alles.

1732
01:14:59,440 --> 01:15:03,030
>> Het eindigt zo omhoog het zijn
ongeveer n kwadraat.

1733
01:15:03,030 --> 01:15:09,510
Als het correct is dan moet je
zeggen, OK, 2, je bent goed.

1734
01:15:09,510 --> 01:15:11,330
3, je bent in vergelijking met 2.

1735
01:15:11,330 --> 01:15:12,310
Je bent goed.

1736
01:15:12,310 --> 01:15:14,150
4, je gewoon vergelijken met de staart.

1737
01:15:14,150 --> 01:15:14,990
Je bent goed.

1738
01:15:14,990 --> 01:15:17,140
6, te vergelijken met de staart, je boete.

1739
01:15:17,140 --> 01:15:20,870
Dus voor elke plek als het al
naargelang, je maakt een vergelijking.

1740
01:15:20,870 --> 01:15:22,320
Dus het is gewoon n.

1741
01:15:22,320 --> 01:15:26,840
En omdat we een best case runtime
n en een worst case batterijduur van n

1742
01:15:26,840 --> 01:15:28,680
kwadraat, we hebben geen verwachte runtime.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Het is maar net de
chaos van onze lijst daar.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
En nogmaals, een andere
grafiek en een andere tafel.

1747
01:15:39,530 --> 01:15:41,170
Dat verschillen tussen soorten.

1748
01:15:41,170 --> 01:15:44,180
Ik ga gewoon door wind, I
het gevoel dat we uitvoerig hebben gesproken

1749
01:15:44,180 --> 01:15:46,570
over hoe ze allerlei
van verschillen en het aan elkaar koppelen.

1750
01:15:46,570 --> 01:15:50,564
Dus samenvoegen soort is de laatste
Ik zal vervelen jullie met.

1751
01:15:50,564 --> 01:15:52,105
We hebben een mooi kleurrijk beeld.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Dus samenvoegen soort is een recursief algoritme.

1754
01:15:56,040 --> 01:15:59,910
Dus doen jullie weten wat
een recursieve functie is?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Iedereen willen zeggen?

1757
01:16:03,320 --> 01:16:04,739
Je wilt proberen?

1758
01:16:04,739 --> 01:16:07,280
Dus een recursieve functie is enkel
een functie die zichzelf aanroept.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Dus als jullie zijn vertrouwd
met de Fibonacci-reeks,

1761
01:16:11,590 --> 01:16:15,670
dat is recursieve omdat geacht
neemt u de vorige twee

1762
01:16:15,670 --> 01:16:17,530
en voeg ze samen
naar uw volgende te krijgen.

1763
01:16:17,530 --> 01:16:21,440
Dus recursieve, denk ik altijd
van recursie als als een spiraal

1764
01:16:21,440 --> 01:16:24,430
dus je bent zoals neerwaartse spiraal erin.

1765
01:16:24,430 --> 01:16:27,150
Maar het is gewoon een functie
dat noemt zichzelf.

1766
01:16:27,150 --> 01:16:32,660
>> En, eigenlijk, heel snel ik
kan je laten zien hoe dat eruit ziet.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Hier dus recursieve, als we kijken, is dit
de recursieve manier om samen te vatten over een array.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Dus alles wat we doen is
we hebben som functie

1771
01:16:47,880 --> 01:16:52,210
bedrag dat een omvang en een array neemt.

1772
01:16:52,210 --> 01:16:55,210
En als u merkt, de grootte
verlaagt telkens met één.

1773
01:16:55,210 --> 01:17:00,365
En alles wat het doet is als x gelijk aan
zero-- dus als de grootte van de matrix

1774
01:17:00,365 --> 01:17:02,710
is gelijk aan zero-- het nul terugkeert.

1775
01:17:02,710 --> 01:17:10,440
>> Anders is dit vat
laatste element van de array,

1776
01:17:10,440 --> 01:17:14,790
en neemt vervolgens een bedrag van
de rest van de matrix.

1777
01:17:14,790 --> 01:17:17,555
Dus het is gewoon het af te breken
in steeds kleinere problemen.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Lang verhaal kort, recursie,
functie die zichzelf aanroept.

1780
01:17:21,890 --> 01:17:25,740
Als dat is alles wat je hebt uit deze,
dat is wat een recursieve functie is.

1781
01:17:25,740 --> 01:17:29,870
Als u 51 nemen, zul je zeer te krijgen,
zeer comfortabel met recursie.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
Het is echt cool.

1784
01:17:32,370 --> 01:17:34,660
Het was logisch om als
03:00 een avondje uit.

1785
01:17:34,660 --> 01:17:37,900
En ik was als, waarom
heb ik dit nooit gebruiken?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Dus voor merge sort, in principe
wat het gaat doen, is het

1788
01:17:42,430 --> 01:17:45,620
om dat af te breken en breken
naar beneden totdat het is gewoon losse elementen.

1789
01:17:45,620 --> 01:17:47,570
De afzonderlijke elementen zijn gemakkelijk te sorteren.

1790
01:17:47,570 --> 01:17:48,070
We zien dat.

1791
01:17:48,070 --> 01:17:50,760
Als je er een element, het is
al beschouwd gesorteerde.

1792
01:17:50,760 --> 01:17:53,800
Zo op een ingang van n elementen,
Als n kleiner is dan 2,

1793
01:17:53,800 --> 01:17:58,120
gewoon terug omdat die middelen
het is ofwel 0 of 1 zoals we hebben gezien.

1794
01:17:58,120 --> 01:18:00,050
Die worden beschouwd als gesorteerde elementen.

1795
01:18:00,050 --> 01:18:02,170
>> Anders breekt het in tweeën.

1796
01:18:02,170 --> 01:18:06,336
Sorteer de eerste helft, sorteert de tweede
de helft, en dan ze samenvoegen.

1797
01:18:06,336 --> 01:18:07,460
Daarom heet het merge sort.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
We hebben hier dus we zullen deze afstand.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Dus houden we het hebben van hen
totdat de array size is 1.

1802
01:18:17,210 --> 01:18:20,790
Dus als het 1, we hebben net weer
omdat dit een gesorteerde array,

1803
01:18:20,790 --> 01:18:23,940
en dit is een gesorteerde array en dat is
een gesorteerde array, we zijn allemaal opgelost.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Dus dan wat we doen is dat we
beginnen ze te groeperen.

1806
01:18:29,420 --> 01:18:31,820
>> Dus de manier waarop u kunt
denken over samenvoeging is

1807
01:18:31,820 --> 01:18:36,240
je gewoon verwijderen van de kleinere
van elk van de sub-arrays

1808
01:18:36,240 --> 01:18:38,330
en gewoon voeg deze toe aan het ontstaan ​​array.

1809
01:18:38,330 --> 01:18:44,290
Dus als je hier kijkt, als we
deze sets wij 4, 6, en 1.

1810
01:18:44,290 --> 01:18:47,280
Als we willen deze samenvoegen,
we kijken naar deze eerste twee

1811
01:18:47,280 --> 01:18:50,730
en wij zeggen, OK, 1 is kleiner,
het naar voren.

1812
01:18:50,730 --> 01:18:54,330
4 en 6, er is niets om te vergelijken
het aan, gewoon een label met het hoofd tot het einde.

1813
01:18:54,330 --> 01:18:58,020
>> Toen we combineren deze twee, we hebben net
neem de kleinere van de twee,

1814
01:18:58,020 --> 01:18:59,310
dus het is 1.

1815
01:18:59,310 --> 01:19:01,690
En nu nemen we de
kleinste van deze twee, dus 2.

1816
01:19:01,690 --> 01:19:03,330
Kleinste van deze twee, 3.

1817
01:19:03,330 --> 01:19:06,260
Kleinste van deze twee, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Dus je bent gewoon te trekken uit deze.

1819
01:19:08,630 --> 01:19:11,210
En omdat ze hebben
eerder gesorteerd,

1820
01:19:11,210 --> 01:19:14,300
je hoeft alleen één
vergelijking elke keer daar.

1821
01:19:14,300 --> 01:19:19,610
Dus meer code hier, net vertegenwoordiging.

1822
01:19:19,610 --> 01:19:24,410
Dus je begint in het midden en
u sorteert links en rechts

1823
01:19:24,410 --> 01:19:26,180
en dan moet je gewoon samen te voegen die.

1824
01:19:26,180 --> 01:19:30,080
>> En we hebben geen code hebben
voor het samenvoegen hier.

1825
01:19:30,080 --> 01:19:34,110
Maar, nogmaals, als je verder gaat
studeren 50, het zal er zijn.

1826
01:19:34,110 --> 01:19:36,860
Anders kom met me praten
als je nog steeds in de war.

1827
01:19:36,860 --> 01:19:42,340
Zo gaaf ding hier is dat het beste geval,
slechtste geval, en verwachte runtime

1828
01:19:42,340 --> 01:19:46,250
zijn allemaal in log n, die
is veel beter dan we hebben

1829
01:19:46,250 --> 01:19:48,000
gezien de rest van onze soorten.

1830
01:19:48,000 --> 01:19:51,840
We hebben gezien n kwadraat
en wat we eigenlijk

1831
01:19:51,840 --> 01:19:54,380
krijgen hier is n log n, wat geweldig is.

1832
01:19:54,380 --> 01:19:55,830
>> Kijk eens hoeveel beter dat is.

1833
01:19:55,830 --> 01:19:56,780
Zo'n mooie curve.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Zo veel efficiënter.

1836
01:20:00,120 --> 01:20:03,510
Als je ooit kunt, gebruik samenvoegen soort.

1837
01:20:03,510 --> 01:20:04,810
Het bespaart u tijd.

1838
01:20:04,810 --> 01:20:07,670
Dan weer, zoals we al zeiden, als
je naar beneden bent in deze lagere regio,

1839
01:20:07,670 --> 01:20:09,480
het niet maken dat
veel van een verschil.

1840
01:20:09,480 --> 01:20:11,360
U krijgt tot duizenden
en duizenden ingangen,

1841
01:20:11,360 --> 01:20:13,318
u zeker wilt een
efficiënter algoritme.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
En, nogmaals, onze mooie tafel van alle
soorten die jullie vandaag geleerd.

1844
01:20:19,400 --> 01:20:21,157
>> Dus ik weet dat het een dichte dag.

1845
01:20:21,157 --> 01:20:23,490
Dit is niet per se te gaan
om u te helpen met uw pset.

1846
01:20:23,490 --> 01:20:28,250
Maar ik wil gewoon een disclaimer maken
die sectie is niet alleen over psets.

1847
01:20:28,250 --> 01:20:31,240
Al dit materiaal is eerlijk
spel voor je tentamens.

1848
01:20:31,240 --> 01:20:35,430
En ook als je verder met CS,
deze zijn echt belangrijke fundamenten

1849
01:20:35,430 --> 01:20:37,870
die je zou moeten weten.

1850
01:20:37,870 --> 01:20:41,700
Dus een paar dagen zal er een
weinig meer PSET hulp,

1851
01:20:41,700 --> 01:20:44,600
maar een paar weken zal zijn
veel meer daadwerkelijke inhoud

1852
01:20:44,600 --> 01:20:46,600
dat lijkt misschien niet super
nuttig voor u op dit moment,

1853
01:20:46,600 --> 01:20:51,215
maar ik beloof als u doorgaat
op zal zeer, zeer nuttig.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Dus dat is het voor sectie.

1856
01:20:54,250 --> 01:20:55,250
Down to the wire.

1857
01:20:55,250 --> 01:20:56,570
Ik deed het binnen een minuut.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Maar daar ga je.

1860
01:20:58,970 --> 01:21:01,240
En ik zal donuts of snoep hebben.

1861
01:21:01,240 --> 01:21:03,464
Is er iemand allergisch voor
wat dan ook, door de manier waarop?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Eieren en melk.

1864
01:21:05,890 --> 01:21:08,120
Dus donuts zijn een no?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
OK.

1867
01:21:10,160 --> 01:21:10,770
Prima.

1868
01:21:10,770 --> 01:21:12,120
Chocolade no?

1869
01:21:12,120 --> 01:21:12,620
Starburst.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starbursts zijn goed.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
We gaan te hebben
Starburst volgende week dan.

1874
01:21:17,045 --> 01:21:18,240
Dat is wat ik krijg.

1875
01:21:18,240 --> 01:21:19,690
Jullie hebben een geweldige week.

1876
01:21:19,690 --> 01:21:20,460
Lees je spec.

1877
01:21:20,460 --> 01:21:22,130
>> Laat me weten als je vragen hebt.

1878
01:21:22,130 --> 01:21:25,300
Pset twee kwaliteiten moeten zijn
aan u door donderdag.

1879
01:21:25,300 --> 01:21:28,320
Als u vragen heeft
over hoe ik graded iets

1880
01:21:28,320 --> 01:21:32,250
of waarom ik graded iets de manier waarop ik
heeft, stuur een email naar mij, kom met me praten.

1881
01:21:32,250 --> 01:21:34,210
Ik ben een beetje gek dit
week, maar ik beloof

1882
01:21:34,210 --> 01:21:36,340
Ik zal nog steeds antwoorden binnen 24 uur.

1883
01:21:36,340 --> 01:21:38,240
Dus hebben een geweldige week, iedereen.

1884
01:21:38,240 --> 01:21:40,090
Veel succes op je pset.

1885
01:21:40,090 --> 01:21:41,248