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

2
00:00:11,100 --> 00:00:12,300
>> SPEAKER 1: Hej alle!

3
00:00:12,300 --> 00:00:13,890
Velkommen tilbage til afsnittet.

4
00:00:13,890 --> 00:00:17,480
Så glad for at se så mange af jer både her,
og alle, der er at se online.

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

6
00:00:18,760 --> 00:00:20,920
Så som sædvanlig velkommen tilbage.

7
00:00:20,920 --> 00:00:24,360
Jeg håber, at alle havde en dejlig
weekend, fuld af hvile, afslapning.

8
00:00:24,360 --> 00:00:26,026
Det var smukt ud i går.

9
00:00:26,026 --> 00:00:27,525
Så jeg håber du har nydt udendørs.

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

11
00:00:28,840 --> 00:00:30,610
>> Så først et par meddelelser.

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

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

14
00:00:32,700 --> 00:00:37,350
Så de fleste af jer bør har fået en
e-mail fra mig om din Scratch Pset,

15
00:00:37,350 --> 00:00:39,920
samt Vurdering af Pset 1.

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

17
00:00:41,000 --> 00:00:42,220
Så bare et par ting.

18
00:00:42,220 --> 00:00:45,150
Vær sikker på at bruge check50 i style50.

19
00:00:45,150 --> 00:00:47,250
Disse er beregnet til at være
ressourcer til jer,

20
00:00:47,250 --> 00:00:50,660
at sikre, at du får
så mange point som du kan

21
00:00:50,660 --> 00:00:52,390
uden unødigt at miste dem.

22
00:00:52,390 --> 00:00:54,407
Så ting som stil
er meget vigtige.

23
00:00:54,407 --> 00:00:55,740
Vi kommer til at tage ud for det.

24
00:00:55,740 --> 00:00:58,115
Nogle af jer har måske allerede
bemærket, at fra din Pset.

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

26
00:00:58,920 --> 00:01:01,450
Og check50 er bare en
rigtig nem måde at sikre,

27
00:01:01,450 --> 00:01:05,050
at vi faktisk er returnering hvad
skal returneres til brugeren,

28
00:01:05,050 --> 00:01:06,690
og at alt virker korrekt.

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

30
00:01:08,690 --> 00:01:12,040
>> På den anden note, så sørg for din
uploade ting til den rigtige mappe.

31
00:01:12,040 --> 00:01:14,470
Det gør mit liv bare en
lidt sværere

32
00:01:14,470 --> 00:01:18,836
hvis du uploader Pset 2 ind Pset 1
fordi når jeg downloader ting,

33
00:01:18,836 --> 00:01:20,085
de ikke downloader korrekt.

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

35
00:01:21,690 --> 00:01:24,560
Og jeg ved, det er lidt wonky
i et system til at vænne sig til,

36
00:01:24,560 --> 00:01:26,950
men blot være super
forsigtig, hvis det kun for mig,

37
00:01:26,950 --> 00:01:30,080
så når du får e-mails
på ligesom 2:00 og jeg er sortering.

38
00:01:30,080 --> 00:01:33,710
Hvis ikke forårsage jeg nødt til at se
hele vejen rundt for din Pset.

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

40
00:01:34,440 --> 00:01:37,270
>> Jeg ved det er tidligt, men jeg
helt fik taget off guard

41
00:01:37,270 --> 00:01:40,800
af et essay, der er på grund af denne fredag, at
mine professorer var ligesom, oh yeah.

42
00:01:40,800 --> 00:01:42,550
Husk, du har en
essay forfalder på fredag.

43
00:01:42,550 --> 00:01:45,780
Så jeg kender ingen kan lide
at tænke midterms,

44
00:01:45,780 --> 00:01:50,620
men din første quiz er den 15. oktober
som oktober starter i denne uge.

45
00:01:50,620 --> 00:01:53,290
Så kan det være hurtigere
end du regnede med, er alt.

46
00:01:53,290 --> 00:01:57,510
Så du er ikke smidt ud vagt, når
Jeg nævner næste uges afsnit, der åh,

47
00:01:57,510 --> 00:02:00,560
din quiz i næste uge, tænkte jeg
Jeg ville give dig en lille smule mere

48
00:02:00,560 --> 00:02:01,500
af en hoveder op nu.

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

50
00:02:02,970 --> 00:02:04,660
>> Så dit problem sæt, nummer tre.

51
00:02:04,660 --> 00:02:07,070
Hvordan folk har læst
spec ud af nysgerrighed?

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

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

54
00:02:09,199 --> 00:02:10,229
Vi fik et par.

55
00:02:10,229 --> 00:02:12,320
Slags ned fra sidste
uge, men det er OK.

56
00:02:12,320 --> 00:02:13,650
Jeg ved, det var smukt ud.

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

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

59
00:02:16,660 --> 00:02:21,010
Bestemt efter du få gjort
i dag læse din spec mindst

60
00:02:21,010 --> 00:02:25,240
prøv gerne downloade
fordeling kode og drift

61
00:02:25,240 --> 00:02:27,430
ligesom den første indledende
ting, de beder dig til.

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

63
00:02:28,681 --> 00:02:32,590
Fordi vi bruger
fordeling kode og et bibliotek

64
00:02:32,590 --> 00:02:36,790
at vi kun har været using-- --Det er kun
anden gang vi har gjort dette Pset,

65
00:02:36,790 --> 00:02:38,650
skøre ting kan ske
med dit apparat,

66
00:02:38,650 --> 00:02:41,370
og du ønsker at finde,
ud nu versus senere.

67
00:02:41,370 --> 00:02:45,570
>> For hvis det er torsdag aften, eller det er
Onsdag nat og nogle grunde

68
00:02:45,570 --> 00:02:48,912
apparatet bare ikke
ønsker at køre med biblioteket

69
00:02:48,912 --> 00:02:50,620
eller med fordelingen
kode, som midler

70
00:02:50,620 --> 00:02:52,309
du kan ikke engang begynde at gøre kodningen.

71
00:02:52,309 --> 00:02:54,100
Fordi du ikke kan kontrollere
for at se, om det virker.

72
00:02:54,100 --> 00:02:55,975
Din ikke gonna være i stand
at se, om det kompilerer.

73
00:02:55,975 --> 00:03:00,500
Du ønsker at tage sig af dem, tidligt i
uge, når man stadig kan e-maile mig

74
00:03:00,500 --> 00:03:03,100
eller en af ​​de andre TF'er,
og vi kan få dem rettet.

75
00:03:03,100 --> 00:03:05,410
Fordi disse er spørgsmål
der kommer til at stoppe dig

76
00:03:05,410 --> 00:03:07,120
fra at gøre reelle fremskridt.

77
00:03:07,120 --> 00:03:10,055
Det er ikke ligesom en bug, at
du kan bare slags springe over.

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

79
00:03:10,712 --> 00:03:13,420
Hvis du har problemer med din
apparat eller distribution kode,

80
00:03:13,420 --> 00:03:16,211
du virkelig ønsker at få det taget
pleje af hellere før end senere.

81
00:03:16,211 --> 00:03:20,410
Så selvom du ikke gonna faktisk
starte kodning, hente distributionen

82
00:03:20,410 --> 00:03:24,040
kode, kan du læse spec, sørg
alt arbejder der.

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

84
00:03:25,134 --> 00:03:27,675
Hvis du bare kan gøre det, jeg
lover jeres liv vil blive lettere.

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

86
00:03:28,800 --> 00:03:31,410
Og så er du sandsynligvis vil
at gøre det lige nu rigtigt?

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

88
00:03:32,100 --> 00:03:33,950
Så eventuelle spørgsmål der?

89
00:03:33,950 --> 00:03:35,850
Eventuelle logistiske ting?

90
00:03:35,850 --> 00:03:36,910
Alle er godt?

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

92
00:03:38,270 --> 00:03:41,700
>> Ansvarsfraskrivelse for dem af
du i værelset og online.

93
00:03:41,700 --> 00:03:45,437
Jeg har tænkt mig at forsøge at skifte
mellem PowerPoint i apparatet

94
00:03:45,437 --> 00:03:47,270
fordi vi kommer
at være at gøre nogle kodning

95
00:03:47,270 --> 00:03:53,630
dag ved populære efterspørgsel af den anonyme
forslag meningsmåling jeg sendte ud i sidste uge.

96
00:03:53,630 --> 00:03:55,480
Så vil vi gøre nogle kodning.

97
00:03:55,480 --> 00:03:57,800
Så hvis du fyre vil også
at fyre op dine apparater,

98
00:03:57,800 --> 00:04:02,910
og du bør have fået en e-mail
fra mig, med en prøve-fil.

99
00:04:02,910 --> 00:04:04,310
Du er velkommen til at gøre det.

100
00:04:04,310 --> 00:04:07,340
>> Så vi kommer til at tale om
GDB, som er en debugger.

101
00:04:07,340 --> 00:04:09,970
Det kommer til at hjælpe dig
slags regne ud, hvor

102
00:04:09,970 --> 00:04:11,860
tingene går galt i din kode.

103
00:04:11,860 --> 00:04:15,370
Det er egentlig bare en måde for dig at træde
gennem din kode som det sker,

104
00:04:15,370 --> 00:04:19,100
og være i stand til at udskrive variabler
eller se, hvad der faktisk sker

105
00:04:19,100 --> 00:04:22,980
under kølerhjelmen vers dit program
bare kører, det er ligesom forkastning,

106
00:04:22,980 --> 00:04:25,030
og du er ligesom, ingen idé
hvad der lige skete her.

107
00:04:25,030 --> 00:04:26,730
Jeg ved ikke, hvilken linje det mislykkedes på.

108
00:04:26,730 --> 00:04:29,040
Jeg ved ikke, hvor det gik galt.

109
00:04:29,040 --> 00:04:31,280
Så er GDB vil hjælpe dig med det.

110
00:04:31,280 --> 00:04:35,240
Også, hvis du beslutter dig for at
fortsætte ja, og tage 61,

111
00:04:35,240 --> 00:04:38,430
det vil virkelig, virkelig være din
bedste ven, fordi jeg kan fortælle dig

112
00:04:38,430 --> 00:04:40,840
fordi jeg går igennem denne klasse.

113
00:04:40,840 --> 00:04:43,620
>> Vi kommer til at se på binær
søg, som, hvis du fyre huske

114
00:04:43,620 --> 00:04:47,540
den store telefonbog eksempel
skue fra klassen.

115
00:04:47,540 --> 00:04:50,620
Vi vil gennemførelsen af ​​denne, og
walking gennem at en lille smule mere,

116
00:04:50,620 --> 00:04:54,650
og så vil vi gennem fire
forskellige slags, der er Bubble,

117
00:04:54,650 --> 00:04:56,285
Udvælgelse, indsættelse og sammenfletning.

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

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

120
00:04:58,330 --> 00:05:00,390
Så GDB som jeg nævnte, er en debugger.

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

122
00:05:01,400 --> 00:05:09,370
Og disse er slags af de store
ting, de store funktioner eller kommandoer

123
00:05:09,370 --> 00:05:13,240
at du bruger i GDB, og jeg vil gå
dig gennem en demo af det i en anden.

124
00:05:13,240 --> 00:05:15,360
>> Så det er ikke bare
vil bo abstrakt.

125
00:05:15,360 --> 00:05:18,000
Jeg vil prøve og gøre det så konkret
som muligt for jer.

126
00:05:18,000 --> 00:05:19,870
Så bryde.

127
00:05:19,870 --> 00:05:22,200
Det vil enten være pause
lignende, et tal, som

128
00:05:22,200 --> 00:05:26,900
repræsenterer en linje i dit program,
eller du kan navngive en funktion.

129
00:05:26,900 --> 00:05:30,150
Så hvis du siger bryde main,
det vil stoppe ved main,

130
00:05:30,150 --> 00:05:32,400
og lade dig gå gennem denne funktion.

131
00:05:32,400 --> 00:05:36,350
>> Ligeledes, hvis du har nogle eksterne
fungerer som Swap eller Cube,

132
00:05:36,350 --> 00:05:38,450
at vi kiggede på i sidste uge.

133
00:05:38,450 --> 00:05:41,780
Hvis du siger bryder en af ​​dem,
når dit program rammer, at

134
00:05:41,780 --> 00:05:44,290
det vil vente på dig til
fortælle det, hvad de skal gøre.

135
00:05:44,290 --> 00:05:47,860
Før det bare vil køre, så du
faktisk kunne trin inde i funktion

136
00:05:47,860 --> 00:05:49,020
og se, hvad der foregår.

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

138
00:05:50,370 --> 00:05:53,515
Så næste, bare springer over
næste linje, går over funktioner.

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

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

141
00:05:55,560 --> 00:05:56,810
Disse er alle lidt abstrakt.

142
00:05:56,810 --> 00:06:00,530
Så vil jeg bare at køre gennem dem,
men du vil se dem i brug i en anden.

143
00:06:00,530 --> 00:06:01,810
>> Træd ind i en funktion.

144
00:06:01,810 --> 00:06:04,170
Så som jeg sagde,
gerne med Swap, ville det

145
00:06:04,170 --> 00:06:07,110
giver dig mulighed for rent faktisk som hvis du er
ligesom fysisk stepping inde,

146
00:06:07,110 --> 00:06:10,990
du kan rod med de variabler, print
ud af, hvad de er, se, hvad der foregår.

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

148
00:06:12,140 --> 00:06:14,830
Listen vil bogstaveligt talt bare udskrive
den omgivende kode.

149
00:06:14,830 --> 00:06:17,570
Så hvis du slags glemmer
hvor du er i dit program,

150
00:06:17,570 --> 00:06:19,880
eller du spekulerer
hvad der foregår omkring det,

151
00:06:19,880 --> 00:06:23,790
dette vil bare udskrive et segment
af lide fem eller seks linjer omkring det.

152
00:06:23,790 --> 00:06:26,080
Så kan du få orienteret
om, hvor du er.

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

154
00:06:27,230 --> 00:06:28,650
>> Udskriv nogle variabel.

155
00:06:28,650 --> 00:06:34,590
Så hvis du har nøglen ligesom
i Cæsar, at vi vil se på.

156
00:06:34,590 --> 00:06:36,220
Du kan sige Print Key på noget tidspunkt.

157
00:06:36,220 --> 00:06:40,070
Det vil fortælle dig, hvad værdien er så
at, måske et eller andet sted langs vejen,

158
00:06:40,070 --> 00:06:42,070
du har overskrevet din nøgle.

159
00:06:42,070 --> 00:06:45,495
Man kan faktisk sige at fordi
du rent faktisk kan se, at værdien.

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

161
00:06:46,500 --> 00:06:48,780
>> I de lokale, bare udskrifter
din lokale variabler.

162
00:06:48,780 --> 00:06:53,120
Så når du er inden for en løkke,
og du blot ønsker at se ud, oh.

163
00:06:53,120 --> 00:06:54,270
Hvad er min jeg?

164
00:06:54,270 --> 00:06:57,020
Hvad er denne nøgle værdi
at jeg initialisere her?

165
00:06:57,020 --> 00:06:58,537
Hvad er budskabet på dette punkt?

166
00:06:58,537 --> 00:07:00,370
Det vil bare udskrive alle
af dem, så man

167
00:07:00,370 --> 00:07:04,330
behøver ikke at individuelt
sige, 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
Og derefter vise.

171
00:07:07,700 --> 00:07:10,370
Hvad det gør, er, som du
trin gennem programmet,

172
00:07:10,370 --> 00:07:13,980
det vil bare sørge for, at det er
vise nogle bestemte variable

173
00:07:13,980 --> 00:07:14,780
på hvert punkt.

174
00:07:14,780 --> 00:07:17,160
Så du also-- --Det er
slags en genvej, hvor

175
00:07:17,160 --> 00:07:19,530
du behøver ikke at holde ud ligesom, oh.

176
00:07:19,530 --> 00:07:23,150
Print Key eller Udskriv I. Det bare
vil automatisk gøre det for dig.

177
00:07:23,150 --> 00:07:25,959
>> Så med dette, vil vi
at se, hvordan det går.

178
00:07:25,959 --> 00:07:28,000
Jeg har tænkt mig at prøve og skifte
over til mit apparat.

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

180
00:07:30,200 --> 00:07:31,271
Se om jeg kan gøre dette.

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

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

183
00:07:40,970 --> 00:07:42,370
Vi bare at spejle det.

184
00:07:42,370 --> 00:07:44,530
Der er ikke noget vanvittigt
på min bærbare computer 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
Dette skal være denne.

189
00:08:01,054 --> 00:08:01,795
Det er så lille.

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

191
00:08:03,730 --> 00:08:05,120
Lad os se om vi kan gøre dette.

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 er naturligvis kæmper
her bare en lille smule,

195
00:08:15,305 --> 00:08:17,995
men vi får det i en momento.

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

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

198
00:08:22,020 --> 00:08:25,900
Vi er bare nødt til at øge dette.

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 alle slags se det?

202
00:08:31,679 --> 00:08:32,470
Måske en lille smule?

203
00:08:32,470 --> 00:08:33,594
Jeg ved det er lidt lille.

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

205
00:08:34,570 --> 00:08:37,530
Du kan ikke helt finde ud af
hvordan man kan gøre denne større.

206
00:08:37,530 --> 00:08:38,350
Hvis nogen kender.

207
00:08:38,350 --> 00:08:40,309
Er der nogen vide, hvordan man kan gøre det større?

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

209
00:08:40,932 --> 00:08:42,140
Vi kommer til at rulle med det.

210
00:08:42,140 --> 00:08:45,801
Betyder ikke noget anyways fordi det er bare
det er den kode, som du fyre bør

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

212
00:08:46,300 --> 00:08:48,310
>> Hvad er mere vigtigt
er terminalen her.

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

214
00:08:52,840 --> 00:08:58,690
Og vi har her Hvorfor er det så lille?

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

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

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
Ægte Ike.

220
00:09:09,500 --> 00:09:10,880
Hvordan er det?

221
00:09:10,880 --> 00:09:11,770
Ud derfra.

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

223
00:09:19,370 --> 00:09:21,810
Er det bedre for alle?

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

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

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

227
00:09:25,830 --> 00:09:28,220
>> Du ved, når du er i en CS
klasse tekniske vanskeligheder

228
00:09:28,220 --> 00:09:32,971
er form af en del af til--
Så lad os klare dette.

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

230
00:09:33,470 --> 00:09:38,060
Så, lige her i afsnittet,
som vi havde her.

231
00:09:38,060 --> 00:09:40,830
Cæsar er en eksekverbar fil.

232
00:09:40,830 --> 00:09:41,800
Så jeg gjorde det.

233
00:09:41,800 --> 00:09:46,370
Så én ting at indse med GDB er
at det kun virker på eksekverbare filer.

234
00:09:46,370 --> 00:09:48,040
Så kan du ikke køre det på en Dotsy.

235
00:09:48,040 --> 00:09:50,532
Du er nødt til rent faktisk at gøre
sikker på, at din kode kompilerer,

236
00:09:50,532 --> 00:09:51,865
og at det faktisk kan køres.

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

238
00:09:52,970 --> 00:09:56,186
>> Så sørg for, at hvis det ikke gør
kompilere, få det til at kompilere,

239
00:09:56,186 --> 00:09:57,810
så man kan slags løbe igennem den.

240
00:09:57,810 --> 00:10:04,590
Så for at starte GDB, alt hvad du gør,
Gloria typen GDB, og så bare det

241
00:10:04,590 --> 00:10:06,250
fil, du ønsker.

242
00:10:06,250 --> 00:10:08,240
Jeg altid staver Cæsar.

243
00:10:08,240 --> 00:10:11,730
Men du vil være sikker
da det er en eksekverbar fil,

244
00:10:11,730 --> 00:10:14,210
TI dot flash, så
betyder, at du går

245
00:10:14,210 --> 00:10:19,240
at køre CSI du kommer til at eksekvere
dette filer enten med debugger.

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

247
00:10:19,910 --> 00:10:22,885
Så behøver du det, får du
denne slags volapyk.

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

249
00:10:24,250 --> 00:10:25,750
Det er bare alle ting om debugger.

250
00:10:25,750 --> 00:10:28,200
Du behøver ikke virkelig nødt til at
bekymre dig om det lige nu.

251
00:10:28,200 --> 00:10:31,460
Og som du kan se, har vi denne
åbne Parens, BNP, tæt parens,

252
00:10:31,460 --> 00:10:34,690
og bare slags ligner
vores kommandolinjen, right?

253
00:10:34,690 --> 00:10:37,010
>> Så, hvad vi ønsker at do--
--So, Den første ting

254
00:10:37,010 --> 00:10:39,570
er vi ønsker at vælge
et sted at bryde den.

255
00:10:39,570 --> 00:10:42,332
Så der er en bug
i dette Caesar program

256
00:10:42,332 --> 00:10:44,290
at jeg præsentere, at
vi kommer til at finde ud af.

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

258
00:10:45,330 --> 00:10:56,350
Det, hvad det gør, er det tager input
Barfoo i alle kasketter, og en eller anden grund

259
00:10:56,350 --> 00:11:01,950
det ændrer ikke A. Det bare efterlader
det alene, er alt andet korrekt,

260
00:11:01,950 --> 00:11:03,980
men det andet bogstav
A forbliver uændret.

261
00:11:03,980 --> 00:11:07,120
Så vi vil forsøge at
regne ud, hvorfor det er.

262
00:11:07,120 --> 00:11:10,440
Så den første ting du typisk
ønsker at gøre, når du starter på GDB

263
00:11:10,440 --> 00:11:12,010
er at finde ud af, hvor at bryde den.

264
00:11:12,010 --> 00:11:14,956
>> Så Cæsar er en temmelig korte program.

265
00:11:14,956 --> 00:11:16,330
Vi skal bare have én funktion, right?

266
00:11:16,330 --> 00:11:18,520
Hvad var vores funktion i Cæsar?

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

268
00:11:19,590 --> 00:11:24,350
Der er kun én funktion, Main right?

269
00:11:24,350 --> 00:11:26,490
Main er en funktion
for alle dine programmer.

270
00:11:26,490 --> 00:11:29,230
Hvis du ikke har Main, jeg måske
være lidt bekymret lige nu,

271
00:11:29,230 --> 00:11:31,000
men jeg håber du alle havde Main derinde.

272
00:11:31,000 --> 00:11:34,150
Så, hvad vi kan gøre, er at vi kan
bare bryde Main, ligesom det.

273
00:11:34,150 --> 00:11:35,190
Så det siger OK.

274
00:11:35,190 --> 00:11:37,430
Vi sætter vores breakpoint der.

275
00:11:37,430 --> 00:11:42,870
>> Så, nu de ting at huske er Cæsar
tager én kommandolinje argument højre

276
00:11:42,870 --> 00:11:45,150
og vi har ikke gjort at overalt endnu.

277
00:11:45,150 --> 00:11:47,560
Så hvad du skal gøre er, når
du rent faktisk går til at køre

278
00:11:47,560 --> 00:11:51,540
programmet, ethvert program, du er
kører i GDB, der skal kommandolinjen

279
00:11:51,540 --> 00:11:55,010
argumenter, er du nødt til at indtaste
når du først begynder at køre det.

280
00:11:55,010 --> 00:11:59,280
Så i dette tilfælde, gør vi
Kør med en nøgle på tre.

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

282
00:12:00,770 --> 00:12:02,040
Og det vil faktisk begynde.

283
00:12:02,040 --> 00:12:08,480
>> Så hvis du ser her, har vi
Hvis RC ikke er lig med 2.

284
00:12:08,480 --> 00:12:12,210
Så hvis du fyre har alle
denne fil, som jeg sendte ud op

285
00:12:12,210 --> 00:12:15,100
du vil se, at det er ligesom
første linje vores vigtigste funktion, right?

286
00:12:15,100 --> 00:12:17,890
Det er kontrol for at se, om vi har
det korrekte antal argumenter.

287
00:12:17,890 --> 00:12:20,620
Så hvis du spekulerer
hvis RC er korrekt,

288
00:12:20,620 --> 00:12:23,250
du kan gøre noget ligesom Print RC.

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

290
00:12:24,380 --> 00:12:28,640
RC er to, som er
hvad vi forventede, ikke?

291
00:12:28,640 --> 00:12:32,010
>> Så kan vi gå næste,
og fortsætter igennem.

292
00:12:32,010 --> 00:12:33,200
Så vi har nogle nøgle der.

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

294
00:12:34,260 --> 00:12:37,090
Og vi kan udskrive vores nøgle
at sørge for, det er korrekt.

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
Ikke helt hvad vi forventede.

298
00:12:41,210 --> 00:12:44,810
Så én ting indse
med GDB også er

299
00:12:44,810 --> 00:12:49,000
at det ikke er indtil du faktisk ramt
Dernæst at den linje, som du lige har set

300
00:12:49,000 --> 00:12:50,720
faktisk udføres.

301
00:12:50,720 --> 00:12:53,870
Så i dette tilfælde Key
er ikke blevet tildelt endnu.

302
00:12:53,870 --> 00:12:57,050
Så Key er nogle skrald værdi
som du kan se på bunden der.

303
00:12:57,050 --> 00:13:03,680
Negativ $ 120-- --Det er en milliard
og noget mærkeligt ting rigtigt?

304
00:13:03,680 --> 00:13:05,340
Det er ikke den nøgle, som vi forventede.

305
00:13:05,340 --> 00:13:10,720
Men hvis vi ramt Næste og derefter vi
prøv og Print-tast, det er tre.

306
00:13:10,720 --> 00:13:11,710
>> Alle se det?

307
00:13:11,710 --> 00:13:13,780
Så hvis du får noget
at du er ligesom, vent.

308
00:13:13,780 --> 00:13:15,540
Dette er helt
forkert, og jeg kender ikke

309
00:13:15,540 --> 00:13:20,150
hvordan dette vil ske, fordi alt, hvad jeg ønsker
at gøre, er at tildele et nummer, en variabel,

310
00:13:20,150 --> 00:13:22,900
forsøge at ramme Dernæst prøv at udskrive
det igen, og se om det virker.

311
00:13:22,900 --> 00:13:27,830
Fordi det kun kommer til at udføre og
faktisk tildele noget efter dig

312
00:13:27,830 --> 00:13:29,340
hit Næste.

313
00:13:29,340 --> 00:13:30,336
Mening for alle?

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

315
00:13:30,836 --> 00:13:33,220
>> SPEAKER 2: Når du tilfældig
numre hvad betyder det?

316
00:13:33,220 --> 00:13:34,790
>> SPEAKER 1: Det er bare tilfældigt.

317
00:13:34,790 --> 00:13:35,710
Det er bare skrald.

318
00:13:35,710 --> 00:13:38,320
Det er bare noget, som din
Computeren vil tilfældigt tildele.

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

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

321
00:13:40,220 --> 00:13:45,760
Så nu kan vi bevæger os igennem, og så
nu har vi denne klartekst getString.

322
00:13:45,760 --> 00:13:48,600
Så lad mig blot introducere hvad
vil ske, når vi ramt Næste her.

323
00:13:48,600 --> 00:13:51,320
Vores GDB slags forsvinder, right?

324
00:13:51,320 --> 00:13:55,720
Det er fordi getString
nu udfører, right?

325
00:13:55,720 --> 00:14:01,460
Så når vi så almindelig tekst lig
GetString, åbne parens og Parens,

326
00:14:01,460 --> 00:14:04,380
og vi ramt Dernæst der har
faktisk udføres nu.

327
00:14:04,380 --> 00:14:06,580
Så det venter
os til input noget.

328
00:14:06,580 --> 00:14:13,560
>> Så vi kommer til at indtaste vores fødevarer, som
er, hvad det er ikke, som jeg fortalte dig

329
00:14:13,560 --> 00:14:18,020
og der bare siger, at det er
færdig udførelse, at den er lukket

330
00:14:18,020 --> 00:14:19,980
beslag betyder det er
afslutter ud af denne løkke.

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

332
00:14:21,170 --> 00:14:25,420
Så kan vi ramt på Næste, og nu, da jeg er
sikker på at du kender alle fra Cæsar,

333
00:14:25,420 --> 00:14:27,260
dette er, hvad er denne linje vil gøre.

334
00:14:27,260 --> 00:14:32,030
Det er for Int Jeg er lig med 0, N er lig
StrLen, almindelig tekst, og derefter

335
00:14:32,030 --> 00:14:33,960
I er mindre end n, I, plus, plus.

336
00:14:33,960 --> 00:14:35,210
Hvad er denne løkke gøre?

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

338
00:14:37,900 --> 00:14:39,160
Åbn din besked.

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

340
00:14:39,770 --> 00:14:41,330
Så lad os begynde at gøre det.

341
00:14:41,330 --> 00:14:47,210
>> Så bør denne betingelse
matche, for vores første?

342
00:14:47,210 --> 00:14:52,250
Hvis det er en B, det er almindelig tekst I. Vi
kan få information om vores lokale.

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

344
00:14:53,610 --> 00:14:57,970
Så I er nul, og hvis seks, hvilket
vi forventer, og vores nøgle er tre.

345
00:14:57,970 --> 00:14:59,227
Alle, der giver mening, right?

346
00:14:59,227 --> 00:15:01,310
Disse tal er alle
præcis, hvad de burde være.

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

348
00:15:02,590 --> 00:15:03,870
Så nynne?

349
00:15:03,870 --> 00:15:05,620
SPEAKER 3: Jeg har
tilfældige tal til mine.

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

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: Nå, kan vi check-- --Vi
kan chatte om det i en anden.

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

353
00:15:14,110 --> 00:15:15,750
Men du skal være at få dette.

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

355
00:15:17,700 --> 00:15:20,130
Så hvis vi har en kapital
B til vores første,

356
00:15:20,130 --> 00:15:22,080
denne betingelse bør fange det, right?

357
00:15:22,080 --> 00:15:27,120
Så hvis vi ramte Dernæst ser vi
at denne Hvis faktisk udfører.

358
00:15:27,120 --> 00:15:29,220
Fordi hvis du følger
sammen i din kode,

359
00:15:29,220 --> 00:15:33,460
denne linje her, hvor almindelig tekst jeg
erstattes med denne aritmetiske,

360
00:15:33,460 --> 00:15:35,720
kun udfører hvis If
betingelse er korrekt ret?

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

362
00:15:36,905 --> 00:15:40,240
>> GDB er kun vil vise dig
ting, der rent faktisk udfører.

363
00:15:40,240 --> 00:15:45,140
Så hvis denne Hvis betingelsen ikke er opfyldt, er det
bare at springe til den næste linje.

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

365
00:15:46,540 --> 00:15:48,510
Så vi har der.

366
00:15:48,510 --> 00:15:51,171
Dette beslag betyder det er
lukket ud af den løkke nu.

367
00:15:51,171 --> 00:15:52,420
Så det kommer til at starte igen.

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

369
00:15:54,760 --> 00:15:56,280
Ligesom det.

370
00:15:56,280 --> 00:15:59,120
Så at vi kan få info
om vores lokale her,

371
00:15:59,120 --> 00:16:02,575
og vi kan se, at vores første
brev har ændret sig, right?

372
00:16:02,575 --> 00:16:05,150
Det er nu en E, som det burde være.

373
00:16:05,150 --> 00:16:07,360
Så kan vi fortsætte på.

374
00:16:07,360 --> 00:16:08,500
>> Og vi har denne kontrol.

375
00:16:08,500 --> 00:16:09,916
Og denne kontrol bør arbejde, right?

376
00:16:09,916 --> 00:16:12,570
Det er A. Det bør ændres
tre bogstaver fremad.

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

378
00:16:14,320 --> 00:16:16,530
Men hvis du bemærker, at vi
få noget andet.

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

380
00:16:17,580 --> 00:16:22,860
Så i dette tilfælde op her, det er fanget
det, og så denne linje udføres,

381
00:16:22,860 --> 00:16:28,620
som ændret vores B.
Men i dette tilfælde her,

382
00:16:28,620 --> 00:16:32,860
har vi at det bare sprunget over det,
og gik til [? L Siff. ?]

383
00:16:32,860 --> 00:16:34,660
Så noget der foregår dér.

384
00:16:34,660 --> 00:16:37,780
Hvad der er at fortælle dig er, at,
vi ved, at det skal fange her,

385
00:16:37,780 --> 00:16:39,200
men det er ikke.

386
00:16:39,200 --> 00:16:42,210
Kan nogen se, hvad vores
problemet er i denne linje?

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

388
00:16:45,380 --> 00:16:46,969
Det er en meget lille ting.

389
00:16:46,969 --> 00:16:48,510
Og du kan også se på din kode.

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

391
00:16:49,980 --> 00:16:54,940
Det er også line-- glemme, hvilken linje det er
i there-- men det er i [uhørligt].

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

393
00:16:55,480 --> 00:16:58,639
>> SPEAKER 4: Det er på mere end
side, hvis man læser det i bogen.

394
00:16:58,639 --> 00:16:59,430
SPEAKER 1: Præcis.

395
00:16:59,430 --> 00:17:02,620
Så kunne debugger ikke fortælle
Dem, men debugger

396
00:17:02,620 --> 00:17:05,880
kunne få dig ned til en linje
at du ved, fungerer ikke.

397
00:17:05,880 --> 00:17:09,319
Og nogle gange, når især
senere i semestret, når

398
00:17:09,319 --> 00:17:12,910
du beskæftiger sig med en hundrede, en
hundrede par linjer kode, og du

399
00:17:12,910 --> 00:17:16,190
ved ikke, hvor det er ikke,
dette er en fantastisk måde at gøre det.

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

401
00:17:17,900 --> 00:17:18,989
Så fandt vi vores fejl.

402
00:17:18,989 --> 00:17:21,530
Du kan ordne det i din fil,
og så kunne du køre det igen,

403
00:17:21,530 --> 00:17:23,029
og alt ville fungere perfekt.

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

405
00:17:24,970 --> 00:17:30,590
Og den største ting er
dette kan synes som, OK.

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

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

408
00:17:31,370 --> 00:17:32,744
Du vidste, hvad du leder efter.

409
00:17:32,744 --> 00:17:34,910
Så du vidste, hvad de skal gøre.

410
00:17:34,910 --> 00:17:39,021
>> GDB kan være super nyttige, fordi du
kan udskrive alle disse ting, som du

411
00:17:39,021 --> 00:17:39,520
ville ikke.

412
00:17:39,520 --> 00:17:41,160
Det er meget mere nyttigt end printf.

413
00:17:41,160 --> 00:17:43,440
Hvor mange af jer bruger
ligesom printf udsagn

414
00:17:43,440 --> 00:17:46,200
at regne ud, hvor en fejl var, right?

415
00:17:46,200 --> 00:17:48,450
Så med dette, behøver du ikke
nødt til at holde tilbage,

416
00:17:48,450 --> 00:17:51,139
og gerne kommentere på
Printf, eller kommentere ud,

417
00:17:51,139 --> 00:17:52,930
og regne ud, hvad
du skal udskrive.

418
00:17:52,930 --> 00:17:55,670
Dette faktisk bare giver dig mulighed for at
gå gennem udskrive ting

419
00:17:55,670 --> 00:18:00,000
som du går igennem, så kan du
observere, hvordan de ændrer i realtid,

420
00:18:00,000 --> 00:18:02,190
som dit program kører.

421
00:18:02,190 --> 00:18:04,390
>> Og det tager lidt
lidt getting bruges til.

422
00:18:04,390 --> 00:18:07,850
Jeg vil meget anbefale bare lidt
af at være lidt frustreret over det

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

424
00:18:08,930 --> 00:18:13,450
Hvis du tilbringe en time i løbet af
næste uge at lære at bruge GDB,

425
00:18:13,450 --> 00:18:16,140
du vil spare dig selv
så meget tid senere.

426
00:18:16,140 --> 00:18:18,750
Og bogstaveligt. vi fortæller
dette mennesker hvert år,

427
00:18:18,750 --> 00:18:23,890
og jeg kan huske, da jeg tog
klasse, jeg var ligesom, jeg vil være fint.

428
00:18:23,890 --> 00:18:24,700
Nej.

429
00:18:24,700 --> 00:18:27,030
Pset 6 kom, og jeg var
ligesom, Jeg skal lære

430
00:18:27,030 --> 00:18:29,500
hvordan man bruger GDB fordi jeg ikke
vide, hvad der foregår her.

431
00:18:29,500 --> 00:18:32,940
>> Så hvis du tager dig tid så
bruge det på mindre programmer

432
00:18:32,940 --> 00:18:35,697
at du kommer til at være
arbejder på, at arbejde

433
00:18:35,697 --> 00:18:37,530
gennem noget lignende
Visionare, som denne.

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

435
00:18:38,800 --> 00:18:42,850
Eller hvis du ønsker ekstra praksis, er jeg sikker
Jeg kunne komme op med buggy programmer

436
00:18:42,850 --> 00:18:45,300
for dig at fejlsøge, hvis du gerne vil.

437
00:18:45,300 --> 00:18:49,300
>> Men hvis du bare tage lidt tid at få
vant til det, bare lege med det,

438
00:18:49,300 --> 00:18:50,550
det virkelig vil tjene dig godt.

439
00:18:50,550 --> 00:18:52,591
Og det er virkelig en af
de ting, som du bare

440
00:18:52,591 --> 00:18:57,340
nødt til at prøve, og få dine hænder beskidte
med, før du virkelig forstår det.

441
00:18:57,340 --> 00:19:02,090
Jeg har egentlig kun forstod det engang
Jeg havde til at fejlrette ting med det,

442
00:19:02,090 --> 00:19:08,170
og det er meget pænere at have en idé om
hvordan man debug hellere før end senere.

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
Jeg ved, det er lidt ligesom
et lynkursus i GDB,

446
00:19:12,960 --> 00:19:16,400
og jeg vil helt sikkert arbejde på at få
disse til at se større næste gang.

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

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

449
00:19:18,280 --> 00:19:20,390
>> Så hvis vi går tilbage til vores PowerPoint.

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

451
00:19:27,194 --> 00:19:28,110
Er det at gå på arbejde?

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

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

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

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

456
00:19:31,600 --> 00:19:35,480
Så hvis du nogensinde brug for nogen af
dem igen, der er på listen.

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

458
00:19:37,160 --> 00:19:40,830
Så binær søgning, som alle
husker den store forestilling af David

459
00:19:40,830 --> 00:19:42,259
ripping telefonbøger i halve.

460
00:19:42,259 --> 00:19:44,050
Jeg kan ikke rigtig få den
telefonbøger længere,

461
00:19:44,050 --> 00:19:46,530
fordi ligesom hvor vil du
få telefonbøger i disse dage?

462
00:19:46,530 --> 00:19:48,220
Jeg virkelig ikke kender.

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

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

465
00:19:50,590 --> 00:19:52,464
Er der nogen der kan huske
hvordan binær søgning Works?

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

467
00:19:54,380 --> 00:19:55,220
Nogen overhovedet?

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

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: Du ved, når
man ser på, hvor halvdelen

470
00:19:58,283 --> 00:20:01,146
det ville være i, på grundlag af denne,
og slippe af med den anden halvdel.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER 1 Præcis.

472
00:20:01,896 --> 00:20:06,290
Så binær søgning, det er lidt en--
--Vi lide at kalde det splitte og erobre.

473
00:20:06,290 --> 00:20:09,170
Så, hvad du skal gøre, er
du vil se i midten,

474
00:20:09,170 --> 00:20:11,990
og du vil se, om det passer
hvad du leder efter.

475
00:20:11,990 --> 00:20:15,420
Og hvis det ikke gør, så du forsøger at
regne ud, er det vil blive overladt

476
00:20:15,420 --> 00:20:16,450
halvdelen eller den højre halvdel.

477
00:20:16,450 --> 00:20:19,325
Så kan det være, hvis du søger
på noget, der er ordnet alfabetisk,

478
00:20:19,325 --> 00:20:20,720
du ser, oh.

479
00:20:20,720 --> 00:20:22,750
Er Allison kommer før M?

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

481
00:20:23,250 --> 00:20:25,030
Så vi kommer til at
se på den første halvdel.

482
00:20:25,030 --> 00:20:26,450
>> Eller det kan være ligesom med tal.

483
00:20:26,450 --> 00:20:28,830
Alt, hvad du kan
sammenligne det kan sorteres.

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

485
00:20:29,920 --> 00:20:31,260
Du kan bruge binær søgning på.

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

487
00:20:32,340 --> 00:20:37,455
Så nogen huske denne
graf eller hvad det er?

488
00:20:37,455 --> 00:20:39,520
Det er Asymptotisk kompleksitet.

489
00:20:39,520 --> 00:20:42,830
Så denne graf bare
beskriver hvor lang tid det

490
00:20:42,830 --> 00:20:46,230
tager dig med at løse et problem, som
du øge antallet af ting

491
00:20:46,230 --> 00:20:47,090
at du bruger.

492
00:20:47,090 --> 00:20:51,260
>> Så vi har N, hvilket er lineær tid.

493
00:20:51,260 --> 00:20:54,560
Hvis N over to, hvilket er lidt
bedre, stadig vokser super hurtigt.

494
00:20:54,560 --> 00:20:58,360
Og så har vi login, hvilket er
hvad vi anser binær søgning.

495
00:20:58,360 --> 00:21:03,630
Hvis vi opdager, da dit problem
får langt og meget større,

496
00:21:03,630 --> 00:21:06,600
den tid det tager dig at løse det
egentlig ikke stige så meget.

497
00:21:06,600 --> 00:21:09,010
Det er ligesom sammenlignelige
her i begyndelsen.

498
00:21:09,010 --> 00:21:10,060
Du er ligesom, OK.

499
00:21:10,060 --> 00:21:13,000
Noget her egentlig ikke
uanset hvilken en vi bruger,

500
00:21:13,000 --> 00:21:16,220
men du får ud til en million, en milliard.

501
00:21:16,220 --> 00:21:20,010
Du forsøger at finde some-- --you're
forsøger at finde en nål i en høstak.

502
00:21:20,010 --> 00:21:21,550
>> Jeg tror, ​​du ønsker dette problem.

503
00:21:21,550 --> 00:21:25,850
Du ønsker denne kompleksitet, ikke
lineær fordi til alle jer

504
00:21:25,850 --> 00:21:30,049
kender din gonna være at søge gennem
hver enkelt nål, ting af hø,

505
00:21:30,049 --> 00:21:31,340
forsøger at lede efter nålen.

506
00:21:31,340 --> 00:21:34,730
Og det er ikke alt for sjovt i min udtalelse.

507
00:21:34,730 --> 00:21:35,500
Jeg kan lide hurtig.

508
00:21:35,500 --> 00:21:36,620
Jeg kan lide effektiv.

509
00:21:36,620 --> 00:21:40,450
Og som hårdtarbejdende studerende dig
fyre er, du ved arbejde smartere,

510
00:21:40,450 --> 00:21:43,010
ikke hårdere type ting, hvordan du
kan gøre op disse algoritmer.

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

512
00:21:45,110 --> 00:21:47,910
>> Så vi kommer til at gå
gennem blot et hurtigt eksempel.

513
00:21:47,910 --> 00:21:51,090
Jeg tror du fyre bør have
en hånd på binær søgning,

514
00:21:51,090 --> 00:21:54,352
men hvis nogen er lidt
fuzzy, ønsker at styrke det,

515
00:21:54,352 --> 00:21:56,310
vi kommer til at bare gå
gennem et eksempel her.

516
00:21:56,310 --> 00:21:59,490
Så er vi på udkig efter hvis
arrayet indeholder syv.

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

518
00:22:00,540 --> 00:22:06,010
>> Så første ting, vi gør, er
ser i midten, højre?

519
00:22:06,010 --> 00:22:09,340
Og også du vil være kodning
Binary Søg på bare et sekund.

520
00:22:09,340 --> 00:22:11,310
Så det kommer til at være sjovt.

521
00:22:11,310 --> 00:22:13,710
Så vi ser i den
midterste små arrays 3.

522
00:22:13,710 --> 00:22:15,501
Er 3 lig 7?

523
00:22:15,501 --> 00:22:16,000
Ikke gør.

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

525
00:22:18,670 --> 00:22:19,550
Det er seks.

526
00:22:19,550 --> 00:22:21,480
Så er det mindre end
eller større end syv?

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

528
00:22:23,080 --> 00:22:23,960
Mindre end.

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

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

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

532
00:22:25,569 --> 00:22:27,360
Jeg føler, jeg kan lide, jeg skulle
have slik, fordi jeg

533
00:22:27,360 --> 00:22:29,460
ønsker at smide det ud i værfterne.

534
00:22:29,460 --> 00:22:30,270
Det er, hvad jeg vil gøre i næste uge.

535
00:22:30,270 --> 00:22:31,436
Det vil holde jer skarpe.

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

537
00:22:32,560 --> 00:22:34,690
>> Så vi smider væk,
første halvdel, right?

538
00:22:34,690 --> 00:22:35,670
det var mindre end.

539
00:22:35,670 --> 00:22:39,325
Vi ved, at alt
på den venstre side

540
00:22:39,325 --> 00:22:41,700
vil være mindre end hvad
vi faktisk på udkig efter.

541
00:22:41,700 --> 00:22:43,491
Så der er ingen grund til at
opmærksomme på det.

542
00:22:43,491 --> 00:22:45,120
Bare glem det.

543
00:22:45,120 --> 00:22:48,720
Så nu ser vi på vores højre side,
og vi ser på midten derovre,

544
00:22:48,720 --> 00:22:50,510
og nu er det ni.

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

546
00:22:55,510 --> 00:22:57,470
Større end hvad vi er
leder efter, right?

547
00:22:57,470 --> 00:22:59,860
Så vi kommer til at kaste
alt væk til højre.

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

549
00:23:00,970 --> 00:23:01,940
Ligesom det.

550
00:23:01,940 --> 00:23:03,700
Nu er alt vi tilbage med er en.

551
00:23:03,700 --> 00:23:07,760
Så vi kontrollere, er denne ene hvad
vi leder efter? det er.

552
00:23:07,760 --> 00:23:08,970
Vi fandt hvad vi ønskede.

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

554
00:23:10,440 --> 00:23:11,690
Så vi er færdig.

555
00:23:11,690 --> 00:23:12,550
Bilineær Search.

556
00:23:12,550 --> 00:23:15,740
>> Og hvis du bemærker, at vi
havde syv indgange der.

557
00:23:15,740 --> 00:23:24,320
Det tog os kun som tre gange,
men hvis du laver ligesom en milliard,

558
00:23:24,320 --> 00:23:28,190
du fyre ved, hvor mange skridt det ville
tage, hvis vi havde fire milliarder ting?

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

560
00:23:29,940 --> 00:23:30,455
Nogen gæt?

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

562
00:23:32,286 --> 00:23:33,960
Det er 32.

563
00:23:33,960 --> 00:23:37,110
32 trin til at finde noget
i en fire milliarder

564
00:23:37,110 --> 00:23:39,650
elementopstillingen grund af beføjelser to.

565
00:23:39,650 --> 00:23:43,550
Så to er til 32, er til fire milliarder.

566
00:23:43,550 --> 00:23:50,430
>> Så temmelig vanvittigt, hvordan du er stadig inden for
som et forholdsvis lille antal trin

567
00:23:50,430 --> 00:23:52,650
at finde noget i
fire milliarder elementer.

568
00:23:52,650 --> 00:23:55,730
Så på dette notat, er vi
kommer til at kode dette

569
00:23:55,730 --> 00:23:58,950
så du fyre kan faktisk
slags se, hvordan det virker.

570
00:23:58,950 --> 00:24:01,520
Okay, så du fyre kan kode.

571
00:24:01,520 --> 00:24:04,100
Jeg har tænkt mig at lade dig fyre
tale om en lille smule.

572
00:24:04,100 --> 00:24:07,970
Få at vide folk omkring dig, som er
hvad nogen ønskede fra sidste afsnit.

573
00:24:07,970 --> 00:24:10,280
>> Så få at vide de mennesker omkring dig.

574
00:24:10,280 --> 00:24:11,305
Tal for en lille smule.

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

576
00:24:12,580 --> 00:24:15,730
Og alt, hvad jeg ønsker fra dig
fyre lige nu er bare

577
00:24:15,730 --> 00:24:17,575
forsøge at skabe et omrids af pseudokode.

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
Alt hvad jeg ønsker fra jer er, du er
bare kommer til at fylde i denne case.

583
00:24:29,520 --> 00:24:32,170
Så jeg har sat disse øvre
og nedre grænser, som

584
00:24:32,170 --> 00:24:35,250
repræsenterer begyndelsen
og slutningen af ​​vores array.

585
00:24:35,250 --> 00:24:40,440
Og du kommer til at faktisk
loop igennem og finde ud af

586
00:24:40,440 --> 00:24:42,470
hvad vi laver i denne while-løkke.

587
00:24:42,470 --> 00:24:45,810
>> Så hvis du kan regne out-- jeg har
en antydning there-- hvad er de tilfælde,

588
00:24:45,810 --> 00:24:46,640
at vi her?

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

590
00:24:48,100 --> 00:24:51,560
Så hvis du ønsker at finde ud af
tilfælde vil vi pseudokode dem

591
00:24:51,560 --> 00:24:53,350
og så vil vi faktisk kode dem.

592
00:24:53,350 --> 00:24:55,330
Og det kommer til at være, jeg
tror, ​​forhåbentlig det vil

593
00:24:55,330 --> 00:24:56,788
være lidt nemmere, end du forventer.

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

595
00:24:57,554 --> 00:25:00,220
Fordi det er ikke så meget kode,
faktisk, som er virkelig 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: [uhørligt]?

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

600
00:25:36,984 --> 00:25:37,650
Instruktør: Ja.

601
00:25:37,650 --> 00:25:38,595
Der var noget
at finde i midten.

602
00:25:38,595 --> 00:25:39,552
>> STUDENT: Så vi kan bruge det.

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

604
00:25:39,770 --> 00:25:40,603
>> Instruktør: Perfect.

605
00:25:40,603 --> 00:25:42,950
Så det er det første, vi skal gøre.

606
00:25:42,950 --> 00:25:44,330
Så find midten.

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

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

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

610
00:25:47,770 --> 00:25:55,010
Så har du en idé om, hvordan vi kan
faktisk finde midten med koden?

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

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

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

614
00:25:58,500 --> 00:25:59,500
Instruktør: Så n over 2.

615
00:25:59,500 --> 00:26:05,170
Så én ting at huske er, at
din øvre og nedre grænser ændres.

616
00:26:05,170 --> 00:26:08,110
Vi holder snærende den del
af array, vi leder til.

617
00:26:08,110 --> 00:26:11,970
Så n over 2 vil kun arbejde
for det første, vi gør.

618
00:26:11,970 --> 00:26:17,810
Så tager øvre og nedre højde,
hvordan kan vi få det midterste element?

619
00:26:17,810 --> 00:26:20,640
Fordi vi ønsker den midterste
mellem øvre og nedre, højre?

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: [uhørligt].

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

624
00:26:26,170 --> 00:26:28,080
>> Instruktør: Så har vi nogle midten.

625
00:26:28,080 --> 00:26:32,730
Og det vil være øvre plus lavere over 2.

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
Der vi går.

629
00:26:36,570 --> 00:26:37,280
En linje ned.

630
00:26:37,280 --> 00:26:38,560
Du fyre er på vej.

631
00:26:38,560 --> 00:26:41,400
Så nu, at vi har vores
midten, hvad ønsker vi at gøre?

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

633
00:26:45,050 --> 00:26:45,900
Bare i almindelighed.

634
00:26:45,900 --> 00:26:47,734
Du behøver ikke at kode det.

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

636
00:26:48,335 --> 00:26:49,210
STUDENT: [uhørligt]?

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

638
00:27:00,310 --> 00:27:10,310
Instruktør: Så det er plus, fordi du er
finde gennemsnittet mellem de to

639
00:27:10,310 --> 00:27:10,810
af dem.

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

641
00:27:11,890 --> 00:27:17,370
Så hvis du tænker på dem som en slags
af stigende fra siderne,

642
00:27:17,370 --> 00:27:21,640
tænker over det, når du nærmer
midten, du ønsker sådan.

643
00:27:21,640 --> 00:27:27,150
Så hvis du var på hver side af
midten, og vi har ligesom 5 og 7.

644
00:27:27,150 --> 00:27:31,440
Når du tilføjer dem sammen du
få 12, du dividere med 2, er 6.

645
00:27:31,440 --> 00:27:33,726
>> Nogle gange er det svært at
forklare, hvorfor det virker,

646
00:27:33,726 --> 00:27:35,600
men hvis du arbejder gennem
et eksempel undertiden,

647
00:27:35,600 --> 00:27:37,962
det vil hjælpe dig med at finde ud af, om
det bør være plus eller minus.

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

649
00:27:38,846 --> 00:27:40,830
>> STUDENT: [uhørligt]
præcis i midten

650
00:27:40,830 --> 00:27:43,950
hvis de havde en sag, hvor
der er en masse mindre tal

651
00:27:43,950 --> 00:27:45,860
og ligesom et stort antal?

652
00:27:45,860 --> 00:27:49,750
>> Instruktør: Så alt hvad du har brug for
er midten af ​​arrayet.

653
00:27:49,750 --> 00:27:53,010
Så hvis du havde en masse små tal
og derefter en virkelig stort antal

654
00:27:53,010 --> 00:27:54,799
i slutningen, er det ligegyldigt.

655
00:27:54,799 --> 00:27:56,840
Alt, der betyder noget, er, at
de er sorteret, du bare

656
00:27:56,840 --> 00:27:59,339
ønsker at se på midten af
array fordi du stadig

657
00:27:59,339 --> 00:28:00,700
udskæring dit problem i halve.

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

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

660
00:28:03,680 --> 00:28:06,430
Så nu, at vi har den
midten, hvad gør vi nu?

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

662
00:28:07,150 --> 00:28:08,150
Instruktør: The sammenligne.

663
00:28:08,150 --> 00:28:11,670
Så sammenligne midten til value_wanted.

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

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

666
00:28:15,160 --> 00:28:17,950
Så du ser op her har vi
denne værdi, vi ønsker her.

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

668
00:28:22,012 --> 00:28:23,095
Husk dette er et array.

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

670
00:28:24,100 --> 00:28:26,970
Så midten refererer til indekset.

671
00:28:26,970 --> 00:28:29,785
Så vi ønsker at gøre værdier for midten.

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

673
00:28:32,380 --> 00:28:35,650
Glem ikke, hvis du ønsker
at sammenligne, dobbelt ligemænd.

674
00:28:35,650 --> 00:28:38,250
Du gør enkelt lig du er
bare at overflytte det,

675
00:28:38,250 --> 00:28:41,090
og så selvfølgelig, det er
vil være den værdi, du ønsker.

676
00:28:41,090 --> 00:28:42,300
Så du skal ikke gøre det.

677
00:28:42,300 --> 00:28:44,350
>> Så vi kommer til at se, om
værdierne ved midten

678
00:28:44,350 --> 00:28:46,460
er lig med den værdi, vi ønsker.

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

680
00:28:47,749 --> 00:28:48,790
Glem ikke dine seler.

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

682
00:28:50,520 --> 00:28:52,235
Dropbox skal gå væk.

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

684
00:28:54,140 --> 00:28:56,200
Så hvad gør vi i dette tilfælde?

685
00:28:56,200 --> 00:28:59,360
Hvis det er, hvad vi ønsker at vende tilbage?

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

687
00:29:01,510 --> 00:29:02,626
Vi prøver at sige.

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

689
00:29:03,440 --> 00:29:05,314
>> Instruktør: Godt, vi
ikke ønsker at udskrive fra.

690
00:29:05,314 --> 00:29:08,220
Så dette er en bool her, så vi
ønsker at vende tilbage sande eller falske.

691
00:29:08,220 --> 00:29:12,280
Vi siger, er dette tal
en [? RRA? ?] Så hvis det er

692
00:29:12,280 --> 00:29:13,788
vi bare returnere det sandt.

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

694
00:29:16,780 --> 00:29:17,760
Hvis jeg kan stave rigtigt.

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

696
00:29:18,830 --> 00:29:20,805
>> STUDENT: Hvorfor ville du ikke returnere nul?

697
00:29:20,805 --> 00:29:22,930
Instruktør: Så du kunne
returnere nul, hvis du ville.

698
00:29:22,930 --> 00:29:26,780
Men i dette tilfælde, fordi
vores funktion returnerer en bool,

699
00:29:26,780 --> 00:29:28,962
vi nødt til at vende tilbage til enten sande eller falske.

700
00:29:28,962 --> 00:29:30,920
STUDENT: Når du er
siger boolean udtryk,

701
00:29:30,920 --> 00:29:33,450
kan du indstille det lig med falsk?

702
00:29:33,450 --> 00:29:39,860
Ligesom hvis jeg ønsker at sige, at hvis denne betingelse
ikke er opfyldt, ligesom er øverste lig falsk.

703
00:29:39,860 --> 00:29:42,332
Vil det forstå, hvis du bare
sætte falsk på den anden side?

704
00:29:42,332 --> 00:29:43,040
Instruktør: Ja.

705
00:29:43,040 --> 00:29:44,820
Så rent faktisk, hvis du er
nogensinde at gøre noget

706
00:29:44,820 --> 00:29:49,600
som er øvre eller lavere,
som returnerer sandt eller falsk

707
00:29:49,600 --> 00:29:53,850
og det er faktisk dårlig stil til
sige lig lig sandt eller ligestillede

708
00:29:53,850 --> 00:29:54,840
lig med falsk.

709
00:29:54,840 --> 00:30:00,210
Du ønsker at bruge dette resultat
da selv som din check.

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

711
00:30:04,720 --> 00:30:05,860
Ikke hvad jeg ønskede.

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

713
00:30:08,150 --> 00:30:09,240
Det er, hvad jeg ønskede.

714
00:30:09,240 --> 00:30:13,205
Så i tilfælde af du spørger
om noget lignende gemme denne i c.

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

716
00:30:16,320 --> 00:30:25,150
>> Så hvis vi har int main (void)
og noget som dette.

717
00:30:25,150 --> 00:30:31,922
Og du har, hvis er øvre
af nogle input, og du er

718
00:30:31,922 --> 00:30:33,630
spørger, om du kan gøre
noget som dette?

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: Jeg prøvede
at gøre det [uhørligt].

722
00:30:37,470 --> 00:30:38,450
Fordi hvis it's--

723
00:30:38,450 --> 00:30:39,200
Instruktør: Right.

724
00:30:39,200 --> 00:30:41,197
Så du ønsker dette at være falsk, right?

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

726
00:30:41,780 --> 00:30:45,960
Instruktør: Så i dette tilfælde dig
ønsker det til at udføre, hvis det ikke er sandt.

727
00:30:45,960 --> 00:30:50,510
Så cool ting du gør der er dette.

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

729
00:30:52,900 --> 00:30:55,650
Så husk udråbstegn
punkt negerer ting?

730
00:30:55,650 --> 00:30:58,270
Den siger [uhørligt] betyder ikke.

731
00:30:58,270 --> 00:31:03,590
Så hvis vi ser på bare
denne del her, ville du

732
00:31:03,590 --> 00:31:05,740
sige, der evalueres til
falsk som du ønsker det.

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

734
00:31:06,790 --> 00:31:09,880
Ikke falsk er sandt som
betyder dette ville udføre.

735
00:31:09,880 --> 00:31:11,037
Giver det mening?

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

737
00:31:11,620 --> 00:31:12,453
Instruktør: Awesome.

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

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

740
00:31:14,300 --> 00:31:16,330
Så kunne vi bare tilbage
sand i dette tilfælde.

741
00:31:16,330 --> 00:31:20,357
Så nu har vi to andre
tilfælde i denne sag.

742
00:31:20,357 --> 00:31:21,565
Hvad er vores to andre sager?

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

744
00:31:31,610 --> 00:31:32,900
Lad os bare gøre det på denne måde.

745
00:31:32,900 --> 00:31:40,660
Så lad os starte med andet
hvis værdier i midten

746
00:31:40,660 --> 00:31:43,230
er mindre end den værdi, vi ønsker.

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

748
00:31:47,200 --> 00:31:52,020
Så vores værdi i midten er mindre
end den værdi, som vi leder efter.

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

750
00:31:53,765 --> 00:31:56,720
>> Så som bundet gør du
tror, ​​at vi ønsker at opdatere?

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

752
00:31:57,870 --> 00:31:58,780
Øvre eller lavere?

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
Så hvilken side af opstillingen
vil vi se på?

757
00:32:06,470 --> 00:32:07,500
>> STUDENT: Jo lavere.

758
00:32:07,500 --> 00:32:09,750
>> Instruktør: Vi skal vi
at se til venstre.

759
00:32:09,750 --> 00:32:11,120
Så ellers hvis ringe værdi er mindre.

760
00:32:11,120 --> 00:32:14,730
Så din midterste værdi her
er mindre end hvad vi ønsker.

761
00:32:14,730 --> 00:32:17,202
Så vi ønsker at tage
højre side af vores array.

762
00:32:17,202 --> 00:32:18,910
Så vi kommer til at
opdatere vores nedre grænse.

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

764
00:32:20,210 --> 00:32:23,020
Så vi vil overflytte vores lavere.

765
00:32:23,020 --> 00:32:25,221
Og hvad tror du lavere bør være?

766
00:32:25,221 --> 00:32:26,304
STUDENT: Den midterste værdi?

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

768
00:32:27,446 --> 00:32:28,820
Instruktør: Så den midterste value--

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

770
00:32:30,136 --> 00:32:31,010
Instruktør: --plus 1.

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

772
00:32:32,300 --> 00:32:34,380
Kan nogen fortælle mig, hvorfor
vi har den plus 1?

773
00:32:34,380 --> 00:32:35,730
>> STUDENT: [? Ingen værdi?]
er mere lig det.

774
00:32:35,730 --> 00:32:36,120
>> Instruktør: Right.

775
00:32:36,120 --> 00:32:38,661
Fordi vi allerede ved, at
vores midterste værdi ikke er lig med

776
00:32:38,661 --> 00:32:42,750
det, og vi ønsker at udelukke det
fra alle efterfølgende søgninger.

777
00:32:42,750 --> 00:32:46,360
Hvis du glemmer at plus 1, dette
vil gerne loop på ubestemt tid.

778
00:32:46,360 --> 00:32:49,620
Og du vil bare blive fanget i en
uendelig løkke og så vil du segfault

779
00:32:49,620 --> 00:32:50,370
og tingene går dårligt.

780
00:32:50,370 --> 00:32:54,780
Så altid sørge for at du ikke er
herunder den værdi, du bare

781
00:32:54,780 --> 00:32:55,380
kiggede på.

782
00:32:55,380 --> 00:32:58,530
Så tager vi os af det med et plus 1.

783
00:32:58,530 --> 00:33:04,840
>> Så nu har vi vores sidste betingelse
som jeg altid for en sikkerheds skyld

784
00:33:04,840 --> 00:33:12,664
du kan tjekke her, ellers hvis værdi på
midten er større end værdien

785
00:33:12,664 --> 00:33:13,163
vi ønsker.

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

787
00:33:16,260 --> 00:33:20,230
Det betyder, at vi ønsker
den venstre halvdel hånd.

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

789
00:33:21,350 --> 00:33:23,260
Så hvilken en skal vi til at opdatere?

790
00:33:23,260 --> 00:33:23,760
Øvre.

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

792
00:33:25,470 --> 00:33:26,970
Og hvad er denne ene kommer til at svare?

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

794
00:33:31,630 --> 00:33:33,690
Midten minus 1, fordi
selvfølgelig, vi ønsker

795
00:33:33,690 --> 00:33:38,370
at sikre, at vi ikke er
ser på det midterste værdi igen.

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

797
00:33:41,830 --> 00:33:45,110
Og så har vi det.

798
00:33:45,110 --> 00:33:45,610
Det er det.

799
00:33:45,610 --> 00:33:46,820
Det er alt binær søgning er.

800
00:33:46,820 --> 00:33:48,190
Det er ikke så slemt, right?

801
00:33:48,190 --> 00:33:51,590
Det er ligesom 10 linier
kode med hvide rum.

802
00:33:51,590 --> 00:33:57,510
Så meget kraftfuld, meget nyttigt, vil du
være at bruge det i en af ​​dine senere psets.

803
00:33:57,510 --> 00:33:59,360
Måske ikke denne ene, men senere.

804
00:33:59,360 --> 00:34:00,670
Så lære det.

805
00:34:00,670 --> 00:34:01,510
Elsker det.

806
00:34:01,510 --> 00:34:02,980
Det vil behandle dig godt.

807
00:34:02,980 --> 00:34:05,370
Så nogen der har nogen
spørgsmål om binær søgning?

808
00:34:05,370 --> 00:34:06,196
Ja.

809
00:34:06,196 --> 00:34:09,840
>> STUDENT: Betyder det noget,
om din n er lige eller ulige?

810
00:34:09,840 --> 00:34:10,750
>> Instruktør: Nej.

811
00:34:10,750 --> 00:34:18,150
Fordi vi kastede det til midten som
en int, vil det bare afkorte det.

812
00:34:18,150 --> 00:34:21,600
Så det vil forblive et heltal, og det vil
sidst sortere gennem alt.

813
00:34:21,600 --> 00:34:23,909
Så du behøver ikke at bekymre dig om det.

814
00:34:23,909 --> 00:34:24,580
Alle godt?

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
Så du fyre fik dette.

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
Så som vi talte om, jeg kender
David nævnte kompleksitet runtime.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> Så i bedste fald, det er bare
én, som vi kalder konstant tid.

825
00:34:50,340 --> 00:34:51,909
Kan nogen fortælle mig, hvorfor det kunne være?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
Hvilken type scenarie ville det indebære?

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: [uhørligt] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
Instruktør: Så midten er den
første element, som vi kommer til, ikke?

833
00:35:03,830 --> 00:35:08,167
Så enten et array af en eller
uanset hvad vi leder efter bare

834
00:35:08,167 --> 00:35:09,750
sker for at være smack dab i midten.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Så det er vores bedste tilfælde.

837
00:35:13,380 --> 00:35:17,540
Du får ind i reelle problemer, sandsynligvis ikke
kommer til at nå [uhørligt] så ofte.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Hvad med vores værste fald?

840
00:35:19,750 --> 00:35:21,270
Vores værste fald er log n.

841
00:35:21,270 --> 00:35:25,360
Og der har at gøre med det hele
beføjelser to ting, som jeg talte om.

842
00:35:25,360 --> 00:35:30,930
>> Så i værste fald ville det betyde
at vi måtte hugge array ned

843
00:35:30,930 --> 00:35:33,270
indtil det var et element af en.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Så vi var nødt til at hugge den ned i halve
så mange gange som vi overhovedet kunne.

846
00:35:38,930 --> 00:35:41,430
Det er derfor det er log n fordi
du bare holde dividere med to.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Så antagelser, ting du
har brug for at vide, hvis du nogensinde

849
00:35:45,830 --> 00:35:48,050
vil bruge en binær søgning.

850
00:35:48,050 --> 00:35:50,680
Dine elementer skal sorteres.

851
00:35:50,680 --> 00:35:53,890
De skal sorteres, fordi
det er den eneste måde, du

852
00:35:53,890 --> 00:35:57,060
kan vide, hvis du er i stand
at smide halvdelen af ​​det.

853
00:35:57,060 --> 00:36:00,260
>> Hvis du havde denne rodet taske
af numre og du siger,

854
00:36:00,260 --> 00:36:05,380
OK, jeg har tænkt mig at kontrollere den midterste
og nummeret jeg leder efter

855
00:36:05,380 --> 00:36:08,510
er mindre end det, vil jeg bare
til vilkårligt at smide den ene halvdel.

856
00:36:08,510 --> 00:36:11,130
Du ville ikke vide, om din
numre i den anden halvdel.

857
00:36:11,130 --> 00:36:12,655
Din liste skal sorteres.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
Samt, kan dette være
går videre en lille smule,

860
00:36:16,560 --> 00:36:18,360
men du skal have random access.

861
00:36:18,360 --> 00:36:21,940
Du skal være i stand til bare
gå til denne midterste element.

862
00:36:21,940 --> 00:36:25,110
Hvis du har til at krydse
gennem noget

863
00:36:25,110 --> 00:36:28,630
eller det tager dig ekstra trin
for at komme til det midterste element,

864
00:36:28,630 --> 00:36:31,750
det er ikke log n længere, fordi
du tilføjer mere arbejde i det.

865
00:36:31,750 --> 00:36:34,800
Og det vil gøre en lille
mere mening om to uger,

866
00:36:34,800 --> 00:36:37,950
men jeg bare slags ønskede at indlede,
giver jer en idé om, hvad der er

867
00:36:37,950 --> 00:36:38,999
at komme.

868
00:36:38,999 --> 00:36:40,790
Men det er de to
vigtige forudsætninger

869
00:36:40,790 --> 00:36:44,804
at du har brug for en binær listen.

870
00:36:44,804 --> 00:36:45,720
Sørg for, at det er sorteret.

871
00:36:45,720 --> 00:36:47,920
Det er den store én for
jer lige nu.

872
00:36:47,920 --> 00:36:52,170
Og der kan vi gå ind i
resten af ​​vores slags.

873
00:36:52,170 --> 00:36:56,444
Så fire sorts-- boble,
indsættelse, udvælgelse, og smelter sammen.

874
00:36:56,444 --> 00:36:57,485
De er alle slags cool.

875
00:36:57,485 --> 00:37:02,860
Hvis du fyre beslutter at tage CS 124,
vil du lære om alle mulige slags.

876
00:37:02,860 --> 00:37:07,575
Og hvis du er en xkcd fan, der
er en virkelig cool tegneserie om

877
00:37:07,575 --> 00:37:11,530
ligesom virkelig ineffektive slags, som jeg
anbefales du vil se på.

878
00:37:11,530 --> 00:37:16,170
En af dem er som panik slags, som
er ligesom, åh nej, tilbage tilfældig array.

879
00:37:16,170 --> 00:37:16,991
Shutdown system.

880
00:37:16,991 --> 00:37:17,490
Efterlad.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Så nørdede humor er altid godt.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Så er der nogen huske slags
ligesom bare en generel idé

885
00:37:25,750 --> 00:37:27,810
hvordan boble slags fungerer.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Kan du huske?

888
00:37:32,155 --> 00:37:32,755
>> STUDENT: Ja.

889
00:37:32,755 --> 00:37:33,970
>> Instruktør: Go for it.

890
00:37:33,970 --> 00:37:38,980
>> STUDENT: Så du går igennem, og
hvis det er større, så bytte dig de to.

891
00:37:38,980 --> 00:37:39,820
>> Instruktør: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Præcis.

893
00:37:40,564 --> 00:37:41,730
Så du bare gentage gennem.

894
00:37:41,730 --> 00:37:43,050
Du tjekker to numre.

895
00:37:43,050 --> 00:37:46,510
Hvis en før er større
end den bagefter,

896
00:37:46,510 --> 00:37:50,230
du bare bytte dem, så i
denne måde alle de højere tal

897
00:37:50,230 --> 00:37:54,990
boble op mod slutningen af ​​listen
og alle lavere numre boble ned.

898
00:37:54,990 --> 00:37:59,355
>> Har han vise dig fyre den kølige
lydeffekt sortering video?

899
00:37:59,355 --> 00:38:00,480
Det er lidt cool.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Så som Robert sagde bare, algoritmen
at du bare gå gennem listen,

902
00:38:05,200 --> 00:38:07,930
swapping tilstødende værdier
hvis de ikke er i orden.

903
00:38:07,930 --> 00:38:10,975
Og så bare med at gentage
indtil du ikke gør nogen swaps.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Så ikke dårligt, right?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Så vi bare have en hurtig eksempel her.

908
00:38:16,319 --> 00:38:18,360
Så dette kommer til at sortere
dem i stigende rækkefølge.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Så når vi går gennem den første
tid, vi ser gennem otte

911
00:38:23,470 --> 00:38:26,880
og seks er naturligvis ikke
i orden, vi bytte dem.

912
00:38:26,880 --> 00:38:27,985
>> Så kig på den næste.

913
00:38:27,985 --> 00:38:29,430
Otte og fire ikke i orden.

914
00:38:29,430 --> 00:38:30,450
Bytte dem.

915
00:38:30,450 --> 00:38:32,530
Og så otte og to, bytte dem.

916
00:38:32,530 --> 00:38:33,470
Der vi går.

917
00:38:33,470 --> 00:38:39,519
Så efter dit første pass, du
vide, at din største antal

918
00:38:39,519 --> 00:38:41,810
vil være hele vejen
i toppen, fordi det er bare

919
00:38:41,810 --> 00:38:44,210
kommer til at være konstant
større end alt andet

920
00:38:44,210 --> 00:38:46,810
og det bare at gå til boble
op hele vejen til enden der.

921
00:38:46,810 --> 00:38:48,226
Er der giver mening for alle?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
Cool.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Så ser vi på vores andet gennemløb.

926
00:38:53,920 --> 00:38:54,980
Switch seks og fire.

927
00:38:54,980 --> 00:38:55,920
Switch seks og to.

928
00:38:55,920 --> 00:38:58,700
Og nu har vi et par ting i orden.

929
00:38:58,700 --> 00:39:02,240
Så for hver pass, som vi
gøre gennem hele vores liste,

930
00:39:02,240 --> 00:39:06,320
vi ved, at ligesom at mange numre
ved udgangen vil være blevet sorteret.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Så vi gør en tredje aflevering,
som er en swap.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
Og derefter på vores fjerde
passere, vi har nul slots.

935
00:39:15,910 --> 00:39:18,570
Og så ved vi, at vores
array er blevet sorteret.

936
00:39:18,570 --> 00:39:20,900
>> Og det er den store
ting med boble slags.

937
00:39:20,900 --> 00:39:23,720
Vi ved, at når vi
have nul swaps, at

938
00:39:23,720 --> 00:39:26,497
betyder, at alt
er i fuldstændig orden.

939
00:39:26,497 --> 00:39:27,580
Det er lidt, hvordan vi kontrollere.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Så vi vil også kode boble
sortere som også er ikke så slemt.

942
00:39:36,480 --> 00:39:38,120
Ingen af ​​disse er så slemt.

943
00:39:38,120 --> 00:39:40,210
Jeg ved, at de kan virke lidt skræmmende.

944
00:39:40,210 --> 00:39:42,124
Jeg ved, når jeg tog
klassen, selv når jeg

945
00:39:42,124 --> 00:39:44,290
underviste klassen for
første gang sidste år,

946
00:39:44,290 --> 00:39:46,165
Jeg var ligesom, hvordan gør jeg det?

947
00:39:46,165 --> 00:39:48,540
Det giver mening i teorien, men
hvordan gør vi egentlig det?

948
00:39:48,540 --> 00:39:51,420
Hvilket er grunden til jeg ønsker også at gå
gennem kode med jer her.

949
00:39:51,420 --> 00:39:54,915
Så jeg har en pseudokode
til jer denne gang.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Så bare holde dette i tankerne, som
vi er ved at skifte i løbet.

952
00:39:58,970 --> 00:40:04,210
Så vi har nogle tæller,
holder styr på vores swaps,

953
00:40:04,210 --> 00:40:08,370
fordi vi er nødt til at sørge for,
at vi tjekker det.

954
00:40:08,370 --> 00:40:11,830
Og vi gentage hele systemet
som vi lige gjorde med dette eksempel.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Hvis elementet før er større end
elementet efter hvor vi er på,

957
00:40:17,325 --> 00:40:20,760
vi bytte dem, og vi tilvækst vores
tæller fordi så snart vi bytte,

958
00:40:20,760 --> 00:40:23,850
Vi ønsker at lade vores tæller vide.

959
00:40:23,850 --> 00:40:26,247
Eventuelle spørgsmål dér?

960
00:40:26,247 --> 00:40:27,580
Noget virker sjovt herovre.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
STUDENT: Mener du indstille tælleren til nul
hver gang du går gennem løkken?

963
00:40:32,350 --> 00:40:34,339
Må ikke du holde ud
tilbage til nul hver gang?

964
00:40:34,339 --> 00:40:35,505
Instruktør: Ikke nødvendigvis.

965
00:40:35,505 --> 00:40:39,710
Så hvad sker der, er vi går igennem her.

966
00:40:39,710 --> 00:40:43,830
Så gør samtidig, husk, dette
vil køre en gang uden at fejle.

967
00:40:43,830 --> 00:40:46,480
Så det kommer til at indstille
tæller lig med nul,

968
00:40:46,480 --> 00:40:48,070
så det kommer til at gentage gennem.

969
00:40:48,070 --> 00:40:50,590
Som det gennemløber,
det vil opdatere tæller.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Som den opdaterer tæller, når det er gjort,
når det er nået til slutningen af ​​arrayet,

972
00:40:56,900 --> 00:41:00,830
hvis vores liste ikke er sorteret,
Tælleren er blevet opdateret.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Så kontrollerer det tilstanden og det
siger, OK, er tælleren større end nul.

975
00:41:07,150 --> 00:41:09,290
Hvis det er, gøre det igen.

976
00:41:09,290 --> 00:41:14,340
Du ønsker at nulstille, så når du
gå igennem, tælleren er lig med nul.

977
00:41:14,340 --> 00:41:18,240
Hvis du går gennem en sorteret
array, ændrer intet,

978
00:41:18,240 --> 00:41:21,355
dette mislykkes, og du
returnere sorteret liste.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Giver det mening?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
STUDENT: Det kunne i en lille smule.

983
00:41:26,356 --> 00:41:27,147
Instruktør: OK.

984
00:41:27,147 --> 00:41:28,980
Hvis der er en anden
spørgsmål, der kommer op.

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: Hvad ville den funktion
være for at bytte de elementer?

988
00:41:33,760 --> 00:41:36,900
>> Instruktør: Så vi kan faktisk skrive
at hvis vi kommer til lige nu.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
Cool.

991
00:41:38,300 --> 00:41:42,155
Så på dette notat, er Alison går
at skifte tilbage til apparatet.

992
00:41:42,155 --> 00:41:43,080
Det kommer til at være sjovt.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
Og vi har vores dejlige
Boblesortering ting her.

995
00:41:47,390 --> 00:41:50,800
Så jeg gjorde allerede cykling
gennem array.

996
00:41:50,800 --> 00:41:53,030
Vi har vores swaps, som
er lig med nul.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Så vi ønsker at bytte tilstødende
elementer, hvis de er ude af drift.

999
00:41:58,440 --> 00:42:03,020
Så den første ting, vi er nødt til at
gør, er gentage gennem vores array.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Så hvordan tror du, vi måske
gentage gennem vores array?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Vi har for, og jeg er lig med 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Vi ønsker jeg at være mindre
end n minus 1 minus k.

1006
00:42:22,454 --> 00:42:23,870
Og jeg vil forklare, at i en anden.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Så dette er en optimering her, hvor
huske, hvordan jeg sagde efter hver pass

1009
00:42:32,830 --> 00:42:36,655
gennem array vi
vide, at uanset hvad er on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Så efter en pass vi
ved, at dette er sorteret.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Efter to gennemløb ved vi
at alt dette er sorteret.

1014
00:42:50,060 --> 00:42:52,750
Efter tre passerer vi
ved, at der sorteres.

1015
00:42:52,750 --> 00:42:55,620
Så den måde jeg iteration
gennem array her,

1016
00:42:55,620 --> 00:43:01,090
er det at sikre, at kun gå
gennem hvad vi ved er usorteret.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
Det er bare en optimering.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Du kunne skrive det naivt bare
iteration gennem alt,

1021
00:43:08,210 --> 00:43:09,970
det ville bare tage længere tid.

1022
00:43:09,970 --> 00:43:12,470
Med denne fire loop er det
bare en dejlig optimering

1023
00:43:12,470 --> 00:43:18,460
fordi vi ved, at efter hver hele
iteration gennem array her,

1024
00:43:18,460 --> 00:43:24,050
ligesom hver fuld løkke her, vi kender
at en flere af disse elementer

1025
00:43:24,050 --> 00:43:25,760
vil blive sorteret i slutningen.

1026
00:43:25,760 --> 00:43:28,294
>> Så vi behøver ikke at bekymre sig om dem.

1027
00:43:28,294 --> 00:43:29,710
Er der giver mening for alle?

1028
00:43:29,710 --> 00:43:30,950
Denne cool lille trick?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Så i dette tilfælde, hvis
vi iteration igennem,

1031
00:43:37,270 --> 00:43:50,590
vi ved, at vi ønsker at kontrollere, om
matrix n og n plus 1 er i orden.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
OK.

1034
00:43:53,559 --> 00:43:54,600
Så her er pseudokode.

1035
00:43:54,600 --> 00:43:57,540
Vi ønsker at kontrollere, om opstilling n
og n plus 1 er i orden.

1036
00:43:57,540 --> 00:43:59,520
Så hvad kunne vi have der?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
Det kommer til at være nogle betingede.

1039
00:44:03,120 --> 00:44:04,220
Det vil være en hvis.

1040
00:44:04,220 --> 00:44:07,066
>> STUDENT: Hvis matrix n er
mindre end matrix n plus 1.

1041
00:44:07,066 --> 00:44:07,816
Instruktør: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
Nå, mindre end eller større end.

1044
00:44:10,699 --> 00:44:11,615
STUDENT: Større end.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Så vi ønsker at bytte dem.

1047
00:44:17,620 --> 00:44:18,570
Præcis.

1048
00:44:18,570 --> 00:44:23,570
Så nu vi kommer ind, hvad der er den
mekanisme til at bytte dem?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Så vi gik gennem dette kort,
en type swap funktion i sidste uge.

1051
00:44:28,137 --> 00:44:29,595
Er der nogen der kan huske, hvordan det fungerede?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Så vi kan ikke bare forflytte dem, right?

1054
00:44:34,950 --> 00:44:36,640
Fordi en af ​​dem vil gå tabt.

1055
00:44:36,640 --> 00:44:41,696
Hvis vi sagde A er lig med B, og derefter B
er lig med A, alle pludselig begge

1056
00:44:41,696 --> 00:44:43,150
er blot lig med B.

1057
00:44:43,150 --> 00:44:45,720
>> Så hvad vi skal gøre, er vi
have en midlertidig variabel, der er

1058
00:44:45,720 --> 00:44:49,055
kommer til at holde en af ​​vores mens
vi er i færd med at bytte.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Så hvad vi har, er vi får nogle int
temp er lig at-- du kan tildele det

1061
00:44:56,464 --> 00:44:59,130
til den, du vil, bare
Sørg for at holde styr på it--

1062
00:44:59,130 --> 00:45:01,840
så i dette tilfælde, vil jeg
tildele den til matrix n plus 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Så det kommer til at holde, hvad
værdi i denne anden blok

1065
00:45:07,674 --> 00:45:08,590
at vi kigger på.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> Og så vi kan gøre, er at vi kan gå
fremad, og tildel matrix n plus 1,

1068
00:45:13,240 --> 00:45:14,990
fordi vi ved, at vi
har denne værdi lagres.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Dette er også en af ​​de store
things-- Jeg ved ikke, om nogen af ​​jer

1071
00:45:19,270 --> 00:45:23,780
havde spørgsmål, hvor, hvis du skifter to
kodelinjer pludselig tingene fungerede.

1072
00:45:23,780 --> 00:45:25,880
For er meget vigtigt i CS.

1073
00:45:25,880 --> 00:45:29,450
Så sørg for at diagram
ting ud hvis det er muligt

1074
00:45:29,450 --> 00:45:31,230
om, hvad der faktisk sker.

1075
00:45:31,230 --> 00:45:34,256
Så nu vil vi
overflytte matrix n plus 1,

1076
00:45:34,256 --> 00:45:36,005
fordi vi ved, at vi
har denne værdi lagres.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> Og vi kan tildele den pågældende til opstilling
n eller i dette tilfælde matrix i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Alt for mange variabler.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
OK.

1083
00:45:55,470 --> 00:46:01,500
Så nu har vi omplaceret opstilling i
plus 1 til lige hvad der er i matrix i.

1084
00:46:01,500 --> 00:46:08,240
Og nu kan vi gå tilbage og
tildele matrix i hvad?

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
>> Instruktør: 10.

1090
00:46:14,680 --> 00:46:15,180
Præcis.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
Og en sidste ting.

1093
00:46:18,640 --> 00:46:21,840
Hvis vi har byttet det nu,
hvad skal vi gøre?

1094
00:46:21,840 --> 00:46:23,740
Hvad er den ene ting
der kommer til at fortælle os

1095
00:46:23,740 --> 00:46:27,542
hvis vi nogensinde afslutte dette program?

1096
00:46:27,542 --> 00:46:29,250
Hvad fortæller os, at vi
har en sorteret liste?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Hvis vi ikke udfører nogen swaps, right?

1099
00:46:33,750 --> 00:46:36,900
Hvis swaps er lig med
nul ved udgangen af ​​dette.

1100
00:46:36,900 --> 00:46:42,975
Så når du udfører en swap, da vi
bare gjorde her, vi ønsker at opdatere swaps.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
Og jeg ved, at der var en
spørgsmål tidligere om du kan

1103
00:46:47,210 --> 00:46:49,689
bruge nul eller én i stedet
af sande eller falske.

1104
00:46:49,689 --> 00:46:50,980
Og det er, hvad dette betyder her.

1105
00:46:50,980 --> 00:46:52,750
Så det siger hvis ikke swaps.

1106
00:46:52,750 --> 00:47:01,310
Så hvis swaps er nul, hvilket is-- jeg altid
få mine sandheder og mine falses blandet op.

1107
00:47:01,310 --> 00:47:03,960
Vi vil have os til at vurdere
til sand, og det er det ikke.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Så hvis det er nul, så er det falsk.

1110
00:47:09,630 --> 00:47:12,560
Hvis du negere det med en
[? bang?] bliver det sandt.

1111
00:47:12,560 --> 00:47:13,975
Så denne linje udfører.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Sandheder og falske og
nuller og ettaller får vanvittigt.

1114
00:47:17,370 --> 00:47:20,690
Bare hvis du langsomt gå
gennem det det vil give mening.

1115
00:47:20,690 --> 00:47:23,320
Men det er, hvad denne lille
bit kode her gør.

1116
00:47:23,320 --> 00:47:26,490
Så det kontrollerer,
har vi gjort nogen swaps.

1117
00:47:26,490 --> 00:47:30,054
Så hvis det er noget udover
nul, går det at være falsk

1118
00:47:30,054 --> 00:47:31,970
og det hele er
kommer til at udføre igen.

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: Hvad betyder break gøre?

1123
00:47:36,000 --> 00:47:38,990
>> Instruktør: Break bare
bryder dig ud af løkken.

1124
00:47:38,990 --> 00:47:41,570
Så i dette tilfælde ville det
bare gerne afslutte programmet

1125
00:47:41,570 --> 00:47:43,828
og du ville bare
har din sorteret liste.

1126
00:47:43,828 --> 00:47:44,536
STUDENT: Amazing.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
Instruktør: Jeg er ked af?

1129
00:47:49,010 --> 00:47:52,110
STUDENT: Da vi tidligere
anvendte skrevet 1 overskrevet nul

1130
00:47:52,110 --> 00:47:54,170
at præsentere, at hvis
der vil arbejde eller ej.

1131
00:47:54,170 --> 00:47:54,878
>> Instruktør: Ja.

1132
00:47:54,878 --> 00:47:56,410
Så du kan returnere nul eller 1.

1133
00:47:56,410 --> 00:47:58,950
I dette tilfælde, fordi vi er faktisk ikke
gør noget med den funktion,

1134
00:47:58,950 --> 00:48:00,150
vi bare vil have det til at knække.

1135
00:48:00,150 --> 00:48:02,680
Vi har ikke virkelig bekymrer sig om det.

1136
00:48:02,680 --> 00:48:06,960
Bremse er også godt, hvis
det bruges til at bryde ud

1137
00:48:06,960 --> 00:48:10,710
af fire løkker eller tilstande,
du ikke ønsker at beholde udførelse.

1138
00:48:10,710 --> 00:48:12,110
Det bare tager dig ud af dem.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Det er lidt af en nuance ting.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Jeg føler som om der er
en masse af hånd viftende,

1143
00:48:18,445 --> 00:48:19,740
ligesom du vil lære om dette snart.

1144
00:48:19,740 --> 00:48:20,955
>> Men du vil lære om dette snart.

1145
00:48:20,955 --> 00:48:21,500
Jeg lover.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
OK.

1148
00:48:23,170 --> 00:48:24,840
Så gør alle komme Boblesortering?

1149
00:48:24,840 --> 00:48:25,550
Ikke alt for dårlig.

1150
00:48:25,550 --> 00:48:31,910
Kør igennem, swap ting ved hjælp af en
temp variabel, og vi er alle indstillet der?

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
Tilbage til PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Eventuelle spørgsmål i almindelighed
om disse hidtil?

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: [uhørligt] int main normalt.

1162
00:48:45,279 --> 00:48:46,695
Har du nødt til at have, at for denne?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> Instruktør: Så blev vi bare at kigge
netop på det faktiske sortering algoritme.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Hvis du havde det inden for
ligesom et større program,

1167
00:48:56,350 --> 00:48:57,891
du ville have en int main eller andet sted.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
Afhængig af hvor du
bruge denne algoritme,

1170
00:49:02,880 --> 00:49:05,860
det ville bestemme, hvad der er
bliver returneret af den.

1171
00:49:05,860 --> 00:49:09,960
Men for vores sag, vi er strengt
se på, hvordan gør dette faktisk

1172
00:49:09,960 --> 00:49:11,300
gentage gennem et array.

1173
00:49:11,300 --> 00:49:12,570
Så vi behøver ikke bekymre dig om det.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Så vi talte om bedste fald og
værst tænkelige scenarier for binær søgning.

1176
00:49:19,830 --> 00:49:22,470
Så det er også vigtigt at gøre
at for hver af vores slags.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Så hvad tror du er den værste
tilfælde runtime af boble slags?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Du fyre huske?

1181
00:49:30,700 --> 00:49:31,784
>> STUDENT: N minus 1.

1182
00:49:31,784 --> 00:49:32,700
Instruktør: N minus 1.

1183
00:49:32,700 --> 00:49:35,070
Så det betyder, at der er
n minus 1 sammenligninger.

1184
00:49:35,070 --> 00:49:40,060
Så én ting at indse, er
at den første iteration,

1185
00:49:40,060 --> 00:49:43,360
vi går igennem, vi sammenligner
disse to-- så det er 1.

1186
00:49:43,360 --> 00:49:46,685
Disse to, tre, fire.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Så efter en iteration vi
allerede har fire sammenligninger.

1189
00:49:55,050 --> 00:49:58,230
Når jeg taler om runtime og n.

1190
00:49:58,230 --> 00:50:04,680
N repræsenterer antallet af sammenligninger
som en funktion af, hvor mange elementer

1191
00:50:04,680 --> 00:50:05,570
vi har.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Så vi går igennem, har vi fire.

1194
00:50:08,860 --> 00:50:11,780
Næste gang du ved, at vi ikke gør det
nødt til at tage sig af dette.

1195
00:50:11,780 --> 00:50:15,140
Vi sammenligner disse to,
disse to, disse to,

1196
00:50:15,140 --> 00:50:20,050
og hvis vi ikke havde denne optimering
med fire løkke, som jeg skrev,

1197
00:50:20,050 --> 00:50:22,750
du ville være at sammenligne med her anyways.

1198
00:50:22,750 --> 00:50:26,170
Så du ville have til
løber gennem arrayet

1199
00:50:26,170 --> 00:50:34,380
og foretage sammenligninger n n
gange, fordi hver gang vi

1200
00:50:34,380 --> 00:50:36,670
løber gennem det vi slags én ting.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> Og hver gang vi kører gennem
array, gør vi n sammenligninger.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Så vores runtime til dette er
faktisk n kvadreret, som

1205
00:50:46,330 --> 00:50:48,400
er langt værre i vores
log ende, fordi der

1206
00:50:48,400 --> 00:50:51,965
betyder, at hvis vi havde fire
milliard elementer, det er

1207
00:50:51,965 --> 00:50:55,260
kommer til at tage os fire milliarder
kvadreret i stedet for 32.

1208
00:50:55,260 --> 00:51:01,240
Så ikke den bedste runtime,
men for nogle ting,

1209
00:51:01,240 --> 00:51:04,610
du ved, hvis du er inden for
et bestemt interval af elementer

1210
00:51:04,610 --> 00:51:06,540
Boblesortering kan være fint at bruge.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Så nu, hvad er den bedste fald 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
Eller 1?

1216
00:51:16,420 --> 00:51:18,140
>> Instruktør: So 1 ville
være en sammenligning.

1217
00:51:18,140 --> 00:51:19,114
Højre.

1218
00:51:19,114 --> 00:51:20,002
>> STUDENT: N minus 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> Instruktør: Så, ja.

1221
00:51:22,320 --> 00:51:22,990
Så n minus 1.

1222
00:51:22,990 --> 00:51:26,510
Når du har et begreb som n
minus 1, er vi tilbøjelige til bare aflevere den

1223
00:51:26,510 --> 00:51:31,680
og vi bare sige n fordi du har
at sammenligne hver af these-- hvert par.

1224
00:51:31,680 --> 00:51:36,470
Så det ville være n minus 1, som vi
vi ville bare sige er ca n.

1225
00:51:36,470 --> 00:51:39,280
Når du har at gøre med runtime,
alt er i tilnærmede.

1226
00:51:39,280 --> 00:51:43,860
Så længe eksponenten er
korrekt, er du temmelig godt.

1227
00:51:43,860 --> 00:51:45,700
>> Det er, hvordan vi skal håndtere det.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Således at bedste fald er n, som
betyder, at listen allerede er sorteret,

1230
00:51:51,780 --> 00:51:54,320
og alle vi gøre er at køre igennem
og kontrollér, at det er sorteret.

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

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Så som du kan se her, vi
bare have nogle flere grafer.

1236
00:52:01,920 --> 00:52:02,660
Så n potens.

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
Meget værre end n, som vi ser, og
meget, meget værre end log 2n.

1240
00:52:09,730 --> 00:52:12,060
Og så skal du også komme ind log logs.

1241
00:52:12,060 --> 00:52:18,020
Og du tager 124, få dig ind
ligesom log stjerne, som er som en sindssyg.

1242
00:52:18,020 --> 00:52:20,172
Så hvis du er interesseret,
opslag log stjerne.

1243
00:52:20,172 --> 00:52:20,880
Det er lidt sjov.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Så vi har denne store diagram.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Bare en hoveder op, dette en
vidunderlige diagram til at have

1248
00:52:28,720 --> 00:52:31,350
for din midtvejs, fordi vi
lang tid at spørge dig disse tynd.

1249
00:52:31,350 --> 00:52:36,090
Så bare en heads up, har dette på din
midtvejs på din pæne snyde ark

1250
00:52:36,090 --> 00:52:36,616
der.

1251
00:52:36,616 --> 00:52:37,990
Så vi kiggede bare på boble slags.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
Worst case, n kvadreret, bedste fald, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
Og vi kommer til at se på de andre.

1256
00:52:44,950 --> 00:52:47,940
>> Og som du kan se, er den eneste
en, der virkelig gør godt

1257
00:52:47,940 --> 00:52:50,910
er Mergesort, som vi vil komme ind på hvorfor.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Så vi kommer til at gå til
næste her-- udvælgelse slags.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Er der nogen der kan huske, hvordan
udvælgelse sortere arbejdet?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Gå efter det.

1264
00:53:05,700 --> 00:53:08,210
>> STUDENT: Dybest set gå gennem
en ordre og oprette en ny liste.

1265
00:53:08,210 --> 00:53:11,001
Og lige som du lægger elementer
i, læg dem på rette sted

1266
00:53:11,001 --> 00:53:11,750
i den nye liste.

1267
00:53:11,750 --> 00:53:14,040
>> Instruktør: Så at lyde
mere ligesom insertion slags.

1268
00:53:14,040 --> 00:53:15,040
Men du er virkelig tæt.

1269
00:53:15,040 --> 00:53:15,915
De er meget ens.

1270
00:53:15,915 --> 00:53:17,440
Selv jeg får dem blandet op nogle gange.

1271
00:53:17,440 --> 00:53:18,981
Før dette afsnit vil jeg var ligesom, vent.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
OK.

1274
00:53:20,630 --> 00:53:24,141
Så hvad du vil
gøre, er udvælgelse sortere,

1275
00:53:24,141 --> 00:53:25,890
den måde, du kan tænke
om det, og den måde,

1276
00:53:25,890 --> 00:53:30,140
Jeg sørge for jeg forsøger ikke at få
dem blandet op, er det går gennem

1277
00:53:30,140 --> 00:53:33,280
og vælger den
mindste antal og det

1278
00:53:33,280 --> 00:53:36,070
sætter det i begyndelsen af ​​din liste.

1279
00:53:36,070 --> 00:53:37,730
Det bytter den med den første plet.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
De har faktisk et eksempel for mig.

1282
00:53:45,370 --> 00:53:46,540
Awesome.

1283
00:53:46,540 --> 00:53:50,130
Så bare en måde at tænke på it-- udvælgelse
sortere, vælge den mindste værdi.

1284
00:53:50,130 --> 00:53:51,940
Og vi vil
løber gennem et eksempel

1285
00:53:51,940 --> 00:53:55,320
at jeg tror vil hjælpe, fordi
Jeg tror visuals altid hjælpe.

1286
00:53:55,320 --> 00:53:58,510
Så vi starter ud med noget
der er helt usorteret.

1287
00:53:58,510 --> 00:54:00,730
Red vil være usorteret,
grøn vil blive sorteret.

1288
00:54:00,730 --> 00:54:02,190
Det vil alle give mening i en anden.

1289
00:54:02,190 --> 00:54:08,950
>> Så vi går igennem, og vi gentage
fra begyndelsen til slutningen.

1290
00:54:08,950 --> 00:54:12,320
Og vi siger, OK, 2 er
vores mindste antal.

1291
00:54:12,320 --> 00:54:15,680
Så vi kommer til at tage 2, og vi vil
at flytte det til den forreste del af vores matrix

1292
00:54:15,680 --> 00:54:17,734
fordi det er den
mindste antal vi har.

1293
00:54:17,734 --> 00:54:19,150
Så det er, hvad dette gør her.

1294
00:54:19,150 --> 00:54:20,820
Det er bare at bytte de to.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Så nu har vi en ordnet
del og en usorteret del.

1297
00:54:25,450 --> 00:54:27,810
Og hvad der er godt at huske
om udvælgelse slags

1298
00:54:27,810 --> 00:54:30,690
er vi kun vælge
fra usorteret del.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> Den sorterede del du blot lade alene.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> STUDENT: Hvordan fungerer det ved, hvad er
den mindste uden at sammenligne det

1303
00:54:38,452 --> 00:54:39,868
til hver anden værdi i array.

1304
00:54:39,868 --> 00:54:41,250
Instruktør: Det gør sammenligne det.

1305
00:54:41,250 --> 00:54:42,041
Vi gerne sprunget over det.

1306
00:54:42,041 --> 00:54:43,850
Det er bare helt overordnet.

1307
00:54:43,850 --> 00:54:44,831
Ja.

1308
00:54:44,831 --> 00:54:47,205
Når vi skriver koden jeg
sikker på, du vil være mere tilfredse.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Men du gemme denne første
element som den mindste.

1311
00:54:53,030 --> 00:54:56,110
Du sammenligner og du
sige, OK, er det mindre?

1312
00:54:56,110 --> 00:54:56,660
Ja.

1313
00:54:56,660 --> 00:54:57,460
Hold det.

1314
00:54:57,460 --> 00:54:58,640
Her er det mindre?

1315
00:54:58,640 --> 00:54:59,660
Nej?

1316
00:54:59,660 --> 00:55:02,510
>> Dette er din mindste,
overflytte det til din værdi.

1317
00:55:02,510 --> 00:55:06,340
Og du vil blive meget lykkeligere
når vi går igennem koden.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Så vi går igennem, vi bytte den, ja så
vi ser på dette usorteret portion.

1320
00:55:13,970 --> 00:55:15,810
Så vi kommer til at vælge tre ud.

1321
00:55:15,810 --> 00:55:18,890
Vi kommer til at sætte det på i
slutningen af ​​vores sorterede portion.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
Og vi bare at holde gør
at gøre det, og gør det.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Så dette er vores slags pseudokode her.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Vi vil kode det op her i en anden.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Men bare noget at gå
igennem på et højt niveau.

1330
00:55:37,270 --> 00:55:40,275
Du kommer til at gå fra
i er lig 0 til n minus 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
Det er en anden optimering.

1333
00:55:43,530 --> 00:55:45,020
Må ikke bekymre dig for meget om det.

1334
00:55:45,020 --> 00:55:46,620
Så som du sagde.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Som Jakob sagde, hvordan gør vi
holde styr på, hvad vores minimum er?

1337
00:55:54,406 --> 00:55:55,030
Hvordan kan vi vide?

1338
00:55:55,030 --> 00:55:57,060
Vi nødt til at sammenligne
alt i vores liste.

1339
00:55:57,060 --> 00:55:59,600
>> Så minimum lig i.

1340
00:55:59,600 --> 00:56:03,870
Det er bare at sige i denne sag
indekset for vores minimumsværdi.

1341
00:56:03,870 --> 00:56:07,660
Så det kommer til at gentage gennem
og det går fra j lig i plus 1.

1342
00:56:07,660 --> 00:56:11,420
Så vi ved allerede, at
det er vores første element.

1343
00:56:11,420 --> 00:56:13,240
Vi behøver ikke at sammenligne det med sig selv.

1344
00:56:13,240 --> 00:56:16,970
Så begynder vi sammenligne det med det næste
en, der er grunden til det er jeg plus 1 til n

1345
00:56:16,970 --> 00:56:20,110
minus 1, som er
ende af formationen der.

1346
00:56:20,110 --> 00:56:25,090
Og vi sagde, at hvis arrayet på
j er mindre end matrix min,

1347
00:56:25,090 --> 00:56:29,200
så vi overflytte hvor
vores minimumskrav indeks er.

1348
00:56:29,200 --> 00:56:37,470
>> Og hvis min ikke er lig med I, som
i hvor vi var tilbage herovre.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Så gerne, når vi først gjorde dette ene.

1351
00:56:41,790 --> 00:56:49,310
I dette tilfælde vil det starte ved
nul, vil det ende med at blive to.

1352
00:56:49,310 --> 00:56:53,010
Så min ville ikke lige jeg i sidste ende.

1353
00:56:53,010 --> 00:56:55,720
Der lader os vide, at
vi er nødt til at bytte dem.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Jeg føler mig som et konkret eksempel
vil bidrage meget mere end dette.

1356
00:57:00,470 --> 00:57:04,970
Så jeg vil kode det op med jer
lige nu, og jeg tror, ​​det vil være bedre.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Sorterer tendens til at arbejde på den måde i det
Det er ofte bedre bare at se dem.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Så hvad vi ønsker at gøre, er
vi først vil have den mindste

1361
00:57:17,280 --> 00:57:19,890
element i sin position i opstillingen.

1362
00:57:19,890 --> 00:57:21,280
Præcis hvad Jacob sagde.

1363
00:57:21,280 --> 00:57:23,090
Du er nødt til at gemme, på en måde.

1364
00:57:23,090 --> 00:57:25,900
Så vi kommer til at starte her
iteration over array.

1365
00:57:25,900 --> 00:57:28,970
Vi kommer til at sige, det er vores
første blot til at begynde med.

1366
00:57:28,970 --> 00:57:38,308
Så vi er nødt til int
mindste er lig med matrix ved jeg.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Så én ting at bemærke, hver
gang denne løkke udfører,

1369
00:57:45,050 --> 00:57:48,550
vi starter et skridt længere henne.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Når vi starter vi ser på denne ene.

1372
00:57:57,440 --> 00:58:00,840
Næste gang vi gentage gennem,
vi starter på denne ene

1373
00:58:00,840 --> 00:58:02,680
og tildele det vores mindste værdi.

1374
00:58:02,680 --> 00:58:10,450
Så det er meget lig Boblesortering
hvor vi ved, at efter en aflevering,

1375
00:58:10,450 --> 00:58:11,700
Dette sidste element er sorteret.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Med udvælgelse sortere,
det er lige det modsatte.

1378
00:58:15,120 --> 00:58:18,950
>> Ved hver pass, vi ved, at
den første er sorteret.

1379
00:58:18,950 --> 00:58:21,360
Efter den anden passage, den
anden vil blive sorteret.

1380
00:58:21,360 --> 00:58:26,470
Og som du så med slide eksempler
vores sorteres portion bare vokser.

1381
00:58:26,470 --> 00:58:34,020
Så ved at sætte vores mindste
til arrays i, alt det gør

1382
00:58:34,020 --> 00:58:37,340
er snærende hvad
vi kigger på, så

1383
00:58:37,340 --> 00:58:40,164
at minimere antallet
sammenligninger vi laver.

1384
00:58:40,164 --> 00:58:41,770
Giver det mening for alle?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Har du brug for mig til at løbe gennem det
igen langsommere eller i forskellige ord?

1387
00:58:46,380 --> 00:58:47,180
Jeg er glad for.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
OK.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> Så vi opbevare
værdi på dette punkt,

1392
00:58:55,540 --> 00:58:57,840
men vi ønsker også at gemme indekset.

1393
00:58:57,840 --> 00:59:01,010
Så vi kommer til at gemme
position af de mindste

1394
00:59:01,010 --> 00:59:02,770
én, der bare kommer til at være i.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Så nu Jacob er tilfreds.

1397
00:59:05,440 --> 00:59:06,870
Vi har ting, der er gemt.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
Og nu er vi nødt til at se igennem
den usorterede del af array.

1400
00:59:11,870 --> 00:59:18,170
Så i dette tilfælde
ville være vores usorteret.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
Det er jeg.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
OK.

1405
00:59:26,210 --> 00:59:30,040
>> Så hvad vi skal gøre
kommer til at være for en løkke.

1406
00:59:30,040 --> 00:59:32,066
Når du skal
gentage gennem et array,

1407
00:59:32,066 --> 00:59:33,440
dit sind kan gå til for en løkke.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Så for nogle int k
equals-- hvad tror vi

1410
00:59:38,090 --> 00:59:39,700
k vil lig at starte med?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
Dette er, hvad vi har sat som vores mindste
værdi, og vi ønsker at sammenligne det.

1413
00:59:44,766 --> 00:59:47,090
Hvad ønsker vi at sammenligne det til?

1414
00:59:47,090 --> 00:59:48,730
Det kommer til at være den næste ene, right?

1415
00:59:48,730 --> 00:59:53,200
Så vi ønsker k skal initialiseres
til i plus 1 for at starte.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> Og vi vil k vi i dette tilfælde
allerede har størrelse gemt op her,

1418
01:00:02,800 --> 01:00:03,930
så vi kan bare bruge størrelse.

1419
01:00:03,930 --> 01:00:06,240
Størrelse er størrelsen af ​​array.

1420
01:00:06,240 --> 01:00:09,620
Og vi ønsker blot at
opdatere k med en hver gang.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
Cool.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
Så nu er vi nødt til at finde
det mindste element her.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Så hvis vi gennemløber, vi
ønsker at sige, hvis matrix ved k

1427
01:00:31,380 --> 01:00:37,080
er mindre end vores mindste value--
dette er, hvor vi er faktisk

1428
01:00:37,080 --> 01:00:42,950
holde styr på, hvad der er
den mindste her--

1429
01:00:42,950 --> 01:00:47,740
så vi ønsker at overflytte
hvad vores mindste værdi.

1430
01:00:47,740 --> 01:00:50,645
>> Det betyder, at, åh, vi er
iteration igennem her.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Uanset værdien her er
ikke vores mindste ting.

1433
01:00:53,740 --> 01:00:54,448
Vi vil ikke have det.

1434
01:00:54,448 --> 01:00:56,100
Vi ønsker at overflytte det.

1435
01:00:56,100 --> 01:01:02,050
Så hvis vi omfordeling det, hvad gør
du tror kunne være i denne kode?

1436
01:01:02,050 --> 01:01:04,160
Vi ønsker at overflytte
mindste og position.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Så hvad er mindste 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
Instruktør: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
Og hvad er position nu?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Hvad er indekserne for
vores mindste værdi?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
Det er bare k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Så matrix k, k, de passer sammen.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Så vi ønskede at tilknytte den.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
Og så efter vi fandt vores mindste,
så i slutningen af ​​denne for-løkke

1454
01:01:39,950 --> 01:01:45,100
her har vi fundet, hvad vores mindste
værdi, så vi bare bytte det.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
I dette tilfælde, ligesom sige vores
mindste værdi er herude.

1457
01:01:50,816 --> 01:01:51,940
Dette er vores mindste værdi.

1458
01:01:51,940 --> 01:01:57,690
>> Vi ønsker blot at bytte det her, som er
hvad det swap funktion nederst

1459
01:01:57,690 --> 01:02:01,270
gjorde, som vi lige har skrevet op
sammen et par minutter siden.

1460
01:02:01,270 --> 01:02:02,775
Så det burde virke bekendt.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
Og så vil det bare gentage
igennem, indtil den når hele vejen

1463
01:02:08,030 --> 01:02:13,100
til enden, hvilket betyder at man
har nul elementer, usorterede

1464
01:02:13,100 --> 01:02:14,800
og alt andet er blevet sorteret.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Mening?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Lidt mere konkret?

1469
01:02:19,280 --> 01:02:19,990
Koden hjælp?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> STUDENT: For en størrelse, du aldrig
virkelig definere det eller ændre det,

1472
01:02:26,410 --> 01:02:27,340
hvordan ser det vide?

1473
01:02:27,340 --> 01:02:32,380
>> Instruktør: Så én ting at
mærke op her er int størrelse.

1474
01:02:32,380 --> 01:02:35,680
Så vi siger i denne sort-- slags
er en funktion i denne case-- det

1475
01:02:35,680 --> 01:02:40,770
udvælgelse slags, er det gået
i med funktionen.

1476
01:02:40,770 --> 01:02:43,460
Så hvis det ikke blev passeret
i, ville du gøre noget

1477
01:02:43,460 --> 01:02:47,840
ligesom med længden af ​​array
eller du ville gentage gennem

1478
01:02:47,840 --> 01:02:49,390
at finde længden.

1479
01:02:49,390 --> 01:02:52,680
Men fordi det er bestået
i, kan vi bare bruge det.

1480
01:02:52,680 --> 01:02:55,720
Du skal bare antage, at brugeren
gav dig en gyldig størrelse,

1481
01:02:55,720 --> 01:02:57,698
faktisk repræsenterer
en størrelse på dit 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
>> Hvis du fyre har nogen problemer med disse
eller ønsker mere praksis kodning sorterer

1486
01:03:05,870 --> 01:03:08,050
på egen hånd, bør du
gå til study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
Det er et værktøj.

1489
01:03:12,670 --> 01:03:15,040
De har en brik, der
du kan faktisk skrive.

1490
01:03:15,040 --> 01:03:16,180
De gør pseudokode.

1491
01:03:16,180 --> 01:03:19,310
De har flere videoer og dias
herunder dem, jeg bruger her.

1492
01:03:19,310 --> 01:03:23,150
Så hvis du stadig føler en
lidt fuzzy, prøv det ud.

1493
01:03:23,150 --> 01:03:25,670
Som altid, kommer tale med mig, også.

1494
01:03:25,670 --> 01:03:26,320
Spørgsmål?

1495
01:03:26,320 --> 01:03:28,611
>> STUDENT: Siger du, at det
størrelse er tidligere defineret?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
Instruktør: Ja.

1498
01:03:29,900 --> 01:03:35,570
Størrelsen tidligere defineret op
her i funktionen erklæring.

1499
01:03:35,570 --> 01:03:39,060
Så du antager, at det er blevet vedtaget i
af brugeren, og for nemheds skyld,

1500
01:03:39,060 --> 01:03:41,896
vi kommer til at antage, at den
bruger gav os den rigtige størrelse.

1501
01:03:41,896 --> 01:03:43,240
Cool.

1502
01:03:43,240 --> 01:03:44,390
Så det er udvælgelse slags.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Gutter, jeg ved, at vi er ved at lære en masse i dag.

1505
01:03:47,640 --> 01:03:49,710
Det er en tæt data for afsnit.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Så med dette, vil vi
at gå til indsættelse slags.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> OK.

1510
01:04:02,510 --> 01:04:06,100
Så før at vi har at gøre
vores runtime analyse her.

1511
01:04:06,100 --> 01:04:10,190
Så i bedste fald,
ydet siden jeg viste dig

1512
01:04:10,190 --> 01:04:11,960
tabellen jeg allerede
slags gav det væk.

1513
01:04:11,960 --> 01:04:15,430
Men bedste fald runtime, hvad mener vi?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Alt sorteres.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N potens.

1518
01:04:22,070 --> 01:04:24,780
Nogen der har en forklaring
for hvorfor du tror?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> STUDENT: du sammenligner through--

1521
01:04:30,519 --> 01:04:31,268
Instruktør: Right.

1522
01:04:31,268 --> 01:04:32,540
Du sammenligner igennem.

1523
01:04:32,540 --> 01:04:35,630
Ved hver iteration, selvom
vi decrementing dette ved en,

1524
01:04:35,630 --> 01:04:38,950
du stadig søge gennem
alt for at finde den mindste.

1525
01:04:38,950 --> 01:04:42,390
Så selvom din mindste værdi
er her i begyndelsen,

1526
01:04:42,390 --> 01:04:44,710
du stadig sammenligne det
mod alt andet

1527
01:04:44,710 --> 01:04:46,550
at sikre, at det er den mindste ting.

1528
01:04:46,550 --> 01:04:49,820
Så du ender med at løbe igennem
ca n kvadreret gange.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Ok.

1531
01:04:51,590 --> 01:04:52,785
Og hvad er det værste tilfælde?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Også n kvadreret fordi du vil
at gøre det samme procedure.

1534
01:04:57,980 --> 01:05:01,670
Så i dette tilfælde, udvælgelse
slags har noget

1535
01:05:01,670 --> 01:05:04,010
at vi også kalder forventet runtime.

1536
01:05:04,010 --> 01:05:07,400
Så i de andre, vi bare vide
de øvre og nedre grænser.

1537
01:05:07,400 --> 01:05:11,180
Afhængigt af, hvordan crazy vores
listen er eller hvor usorteret det er,

1538
01:05:11,180 --> 01:05:15,350
de varierer mellem n eller n potens.

1539
01:05:15,350 --> 01:05:16,550
Vi ved det ikke.

1540
01:05:16,550 --> 01:05:22,820
>> Men fordi valg Sorter har samme
værste og bedste fald, der fortæller os, at

1541
01:05:22,820 --> 01:05:25,880
uanset hvilken type af input, vi
have, uanset om det er helt

1542
01:05:25,880 --> 01:05:29,130
sorteret eller helt
omvendt sorteret, er det

1543
01:05:29,130 --> 01:05:30,740
kommer til at tage den samme mængde tid.

1544
01:05:30,740 --> 01:05:33,760
Så i dette tilfælde, hvis du
husker fra vores bord,

1545
01:05:33,760 --> 01:05:38,610
det faktisk havde en værdi,
disse to former ikke har,

1546
01:05:38,610 --> 01:05:40,390
som forventes runtime.

1547
01:05:40,390 --> 01:05:43,350
Så vi ved, at når
vi kører udvælgelse sortere,

1548
01:05:43,350 --> 01:05:45,380
det er garanteret til
køre en n kvadrerede tid.

1549
01:05:45,380 --> 01:05:46,630
Der er ingen variation der.

1550
01:05:46,630 --> 01:05:47,630
Det er bare forventet.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
Og igen, hvis du ønsker at lære
mere, tage CS 124 i foråret.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Ok.

1555
01:05:56,712 --> 01:05:57,545
Vi har set denne ene.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
Cool.

1558
01:05:59,030 --> 01:06:00,930
Så insertion slags.

1559
01:06:00,930 --> 01:06:03,330
Og jeg sandsynligvis vil
at blaze gennem dette.

1560
01:06:03,330 --> 01:06:05,440
Jeg vil ikke have jer kode det.

1561
01:06:05,440 --> 01:06:06,580
Vi vil bare gå igennem det.

1562
01:06:06,580 --> 01:06:10,500
Så Indsættelsessortering er venlig
af tilsvarende selektion slags

1563
01:06:10,500 --> 01:06:14,460
i, at vi har både en usorteret
og sorteret del af array'et.

1564
01:06:14,460 --> 01:06:20,260
>> Men hvad der er anderledes, er, at
som vi går igennem én efter én,

1565
01:06:20,260 --> 01:06:24,210
vi bare tage, hvad nummer
er næste i vores usorteret,

1566
01:06:24,210 --> 01:06:28,507
og korrekt sortere det
ind i vores sorterede array.

1567
01:06:28,507 --> 01:06:30,090
Det vil give mere mening med et eksempel.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Så alt starter som usorteret,
ligesom med udvælgelse slags.

1570
01:06:35,430 --> 01:06:38,740
Og vi kommer til at sortere dette i
stigende rækkefølge, som vi har været.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Så på vores første pass
vi tager den første værdi

1573
01:06:43,340 --> 01:06:46,700
og vi siger, OK, du er
nu på en liste ved dig selv.

1574
01:06:46,700 --> 01:06:49,150
>> Fordi du er på en liste
ved dig selv, du er sorteret.

1575
01:06:49,150 --> 01:06:52,460
Tillykke til at være den
første element i denne matrix.

1576
01:06:52,460 --> 01:06:54,800
Du er allerede ordnet alt på egen hånd.

1577
01:06:54,800 --> 01:06:58,900
Så nu har vi en ordnet
og en usorteret array.

1578
01:06:58,900 --> 01:07:01,760
Så nu tager vi det første.

1579
01:07:01,760 --> 01:07:05,600
Hvad sker der mellem her
og her er, at vi siger,

1580
01:07:05,600 --> 01:07:08,890
OK, vi kommer til at se på
første værdi af vores usorteret matrix

1581
01:07:08,890 --> 01:07:13,270
og vi kommer til at indtaste det i sin
korrekte sted i den sorterede array.

1582
01:07:13,270 --> 01:07:21,460
>> Så det, vi gør, er vi tager 5 og
vi siger, OK, 5 er større end 3,

1583
01:07:21,460 --> 01:07:24,630
så vi bare indsætte det rigtige
til højre for denne.

1584
01:07:24,630 --> 01:07:25,130
Vi er gode.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Så går vi videre til vores næste.

1587
01:07:28,420 --> 01:07:29,720
Og vi tager 2.

1588
01:07:29,720 --> 01:07:34,330
Vi siger, OK, 2 er mindre
end 3, så vi ved, at det

1589
01:07:34,330 --> 01:07:36,220
skal være på
foran vores liste nu.

1590
01:07:36,220 --> 01:07:41,800
Så hvad vi gør, er vi skubber 3 og 5 ned
og vi bevæger 2 ind i den første spalte.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Så vi bare at indsætte den i
det rigtige sted, det bør være.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Så ser vi på vores
næste, og vi siger 6.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 er større end
alt i vores sorterede array,

1596
01:07:53,620 --> 01:07:56,000
så vi bare mærke det på enden.

1597
01:07:56,000 --> 01:07:56,960
Og så ser vi på 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 er mindre end 6, er det mindre
end 5, men det er større end 3.

1600
01:08:03,020 --> 01:08:06,270
Så vi bare indsætte den helt ud
midt mellem 3 og 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Så for at gøre det lidt
lidt mere konkret,

1603
01:08:10,530 --> 01:08:12,280
Her er lidt af det
idé om, hvad der skete.

1604
01:08:12,280 --> 01:08:16,430
Så for hver usorteret element, vi
bestemme, hvor i den sorterede portion

1605
01:08:16,430 --> 01:08:17,090
det er.

1606
01:08:17,090 --> 01:08:20,680
>> Så under hensyntagen til den
sorteret og usorteret,

1607
01:08:20,680 --> 01:08:26,080
Vi er nødt til at krydse gennem og figur
ud af, hvor det passer ind i den sorterede array.

1608
01:08:26,080 --> 01:08:31,460
Og vi indsætter det ved at flytte
elementer til højre for det ned.

1609
01:08:31,460 --> 01:08:34,910
Og så har vi bare holde
iteration igennem, indtil vi

1610
01:08:34,910 --> 01:08:39,270
har en helt sorteret liste
hvor usorteret er nu nul

1611
01:08:39,270 --> 01:08:41,720
og sorterede fylder
helhed af vores liste.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Så igen, for at gøre tingene selv
mere konkret, har vi pseudokode.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Så dybest set, for jeg er
lig med 0 til n minus 1,

1616
01:08:52,410 --> 01:08:54,790
det er bare længden af ​​vores array.

1617
01:08:54,790 --> 01:09:00,979
Vi har et element, der er lig med
den første matrix eller de første indeks.

1618
01:09:00,979 --> 01:09:03,200
Vi satte j svarende til det.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Så mens j er større end
nul, og array, j minus 1

1621
01:09:09,210 --> 01:09:11,660
er større end
element, så alt det der gør

1622
01:09:11,660 --> 01:09:17,479
er at sikre, at
Deres j virkelig repræsenterer

1623
01:09:17,479 --> 01:09:20,010
usorteret del af array.

1624
01:09:20,010 --> 01:09:30,745
>> Så mens der er stadig ting
at sortere og j minus én is-- hvad

1625
01:09:30,745 --> 01:09:31,840
er det element hende?

1626
01:09:31,840 --> 01:09:34,760
J blev aldrig defineret her.

1627
01:09:34,760 --> 01:09:35,677
Det er lidt irriterende.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Alligevel.

1630
01:09:36,689 --> 01:09:39,899
Så j minus 1, er du tjekker
elementet før det.

1631
01:09:39,899 --> 01:09:46,460
Du siger, OK, er det element,
før hvor jeg am-- lad os

1632
01:09:46,460 --> 01:09:47,540
faktisk trække det ud.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Så lad os sige det er
ligesom på vores andet gennemløb.

1635
01:09:56,830 --> 01:09:59,525
Så jeg kommer til at være lig
1, som er her.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Så jeg kommer til at være lig med 1.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
Dette ville være 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Ok.

1642
01:10:16,750 --> 01:10:20,945
Så vores element i denne sag
vil være lig 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
Og vi har nogle j, der er
vil være lig med 1.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Åh, er j decrementing.

1647
01:10:30,971 --> 01:10:31,720
Det er, hvad det er.

1648
01:10:31,720 --> 01:10:35,680
Så j er lig med i, så hvad det er
siger er, at når vi bevæger os fremad,

1649
01:10:35,680 --> 01:10:37,530
vi bare sørge for
at vi er ikke ovre

1650
01:10:37,530 --> 01:10:43,520
indeksere denne måde, når vi prøver
at indsætte ting ind i vores sorteret liste.

1651
01:10:43,520 --> 01:10:49,850
>> Så når j er lig med 1 i denne sag, og
matrix j minus en-- så matrix j minus 1

1652
01:10:49,850 --> 01:10:54,610
er 2 i denne case-- hvis det er
større end det element,

1653
01:10:54,610 --> 01:10:57,700
så alt dette gør
er ved at flytte tingene ned.

1654
01:10:57,700 --> 01:11:04,790
Så i dette tilfælde, matrix j minus én
ville være opstilling nul, hvilket er 2.

1655
01:11:04,790 --> 01:11:08,430
2 ikke er større end 4,
så det betyder ikke udføre.

1656
01:11:08,430 --> 01:11:11,460
Så skiftet ikke bevæger sig ned.

1657
01:11:11,460 --> 01:11:18,790
Hvad dette betyder her er bare
flytte din sorterede række ned.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
I dette tilfælde faktisk, vi
kunne do-- lad os gøre dette 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Så hvis vi skal gå igennem med
dette eksempel, er vi nu her.

1662
01:11:31,970 --> 01:11:32,740
Dette er sorteret.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
Dette er usorteret.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
Cool?

1667
01:11:39,860 --> 01:11:46,620
Så jeg er lig med 2, så
vores element er lig med 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
Og vores j er lig med 2.

1670
01:11:52,270 --> 01:12:00,620
Så vi ser igennem, og vi
sige, OK, er matrix j minus én

1671
01:12:00,620 --> 01:12:03,470
større end elementet
at vi kigger på?

1672
01:12:03,470 --> 01:12:05,540
Og svaret er ja, right?

1673
01:12:05,540 --> 01:12:11,275
4 er større end 3 og j
er 2, så denne kode udfører.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Så nu, hvad vi gør et array på
2, så lige her, vi bytte dem.

1676
01:12:18,550 --> 01:12:25,620
Så vi bare sige, OK, matrix
ved 2 er der nu kommer til at være 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
Og j vil være lig
j minus 1, som er 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
Det er forfærdeligt, men
jer får den idé.

1681
01:12:37,200 --> 01:12:38,360
J er nu lig med 1.

1682
01:12:38,360 --> 01:12:44,360
Og array j er bare at være
svarende til vores element, som var 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
Jeg slettet noget skulle jeg ikke
har eller miswrote noget,

1685
01:12:48,570 --> 01:12:49,910
men du fyre får den idé.

1686
01:12:49,910 --> 01:12:50,640
>> Det bevæger sig n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
Og derefter, hvis dette var, ville det loop
igen, og det vil sige, OK, j er 1 nu.

1689
01:12:57,960 --> 01:13:00,665
Og array j minus 1 er nu 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Er 2 mindre end vores element?

1692
01:13:03,760 --> 01:13:04,540
Nej?

1693
01:13:04,540 --> 01:13:07,970
Det betyder, at vi har
indsat dette element

1694
01:13:07,970 --> 01:13:10,110
i det rigtige sted i vores sorterede array.

1695
01:13:10,110 --> 01:13:14,400
Så kan vi tage dette, og vi siger,
OK, vores sorterede array er her.

1696
01:13:14,400 --> 01:13:19,940
Og det ville tage dette nummer 6 og være
ligesom, OK, er 6 mindre end dette antal?

1697
01:13:19,940 --> 01:13:20,480
Nej?

1698
01:13:20,480 --> 01:13:21,080
Cool.

1699
01:13:21,080 --> 01:13:22,680
Vi er fine.

1700
01:13:22,680 --> 01:13:23,530
>> Gøre det igen.

1701
01:13:23,530 --> 01:13:24,740
Vi siger 7.

1702
01:13:24,740 --> 01:13:29,010
Er 7 mindre end i slutningen
vores sorterede array?

1703
01:13:29,010 --> 01:13:29,520
Nej.

1704
01:13:29,520 --> 01:13:30,430
Så vi er fint.

1705
01:13:30,430 --> 01:13:32,760
Så det ville blive sorteret.

1706
01:13:32,760 --> 01:13:38,610
Dybest set alt dette gør
Det siger take

1707
01:13:38,610 --> 01:13:42,060
det første element i
usorteret array,

1708
01:13:42,060 --> 01:13:46,010
regne ud, hvor det går
i dit sorterede array.

1709
01:13:46,010 --> 01:13:48,780
Og dette blot tager sig
af swaps til at gøre det.

1710
01:13:48,780 --> 01:13:51,300
Du er dybest set bare bytte
indtil det er på det rigtige sted.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Den visuelle billede er, at du er
bevæger sig alt ned ved at gøre det.

1713
01:13:56,990 --> 01:13:59,420
>> Så det er ligesom halv Boblesortering-esque.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Tjek undersøgelse 50.

1716
01:14:03,420 --> 01:14:06,000
Jeg anbefaler stærkt, forsøger
at kode dette på egen hånd.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Hvis du har nogen spørgsmål eller du ønsker at
se prøve kode for en Indsættelsessortering,

1719
01:14:12,450 --> 01:14:13,750
så lad mig det vide.

1720
01:14:13,750 --> 01:14:14,500
Jeg er altid rundt.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Så worst case runtime
og bedste fald runtime.

1723
01:14:20,200 --> 01:14:30,700
Som du guy så fra bordet jeg allerede
viste dig, er det både n kvadreret og n.

1724
01:14:30,700 --> 01:14:35,590
>> Så venlig at gå ud over, hvad vi talte
omkring med vores tidligere sorterer, værst

1725
01:14:35,590 --> 01:14:38,760
tilfælde runtime er, at hvis
Det er helt usorterede,

1726
01:14:38,760 --> 01:14:42,530
vi nødt til at sammenligne alle disse n gange.

1727
01:14:42,530 --> 01:14:47,020
Vi gør en hel masse sammenligninger
fordi hvis det er i omvendt rækkefølge,

1728
01:14:47,020 --> 01:14:50,360
vi kommer til at sige, OK, dette
er den samme, det er godt,

1729
01:14:50,360 --> 01:14:54,650
og dette skal sammenlignes
mod den første til at blive flyttet tilbage.

1730
01:14:54,650 --> 01:14:56,710
Og da vi kommer hen
enden, har vi

1731
01:14:56,710 --> 01:14:59,440
at sammenligne, sammenligne og
sammenligne mod alt.

1732
01:14:59,440 --> 01:15:03,030
>> Så det ender med at blive
ca n potens.

1733
01:15:03,030 --> 01:15:09,510
Hvis det er korrekt, så du
sige, OK, 2, du er god.

1734
01:15:09,510 --> 01:15:11,330
3, du er i forhold til 2.

1735
01:15:11,330 --> 01:15:12,310
Du er god.

1736
01:15:12,310 --> 01:15:14,150
4, skal du blot sammenligne med halen.

1737
01:15:14,150 --> 01:15:14,990
Du er god.

1738
01:15:14,990 --> 01:15:17,140
6, sammenligne med halen, er du fint.

1739
01:15:17,140 --> 01:15:20,870
Så for hver plet, hvis det allerede er
sorteres, du gør en sammenligning.

1740
01:15:20,870 --> 01:15:22,320
Så det er bare n.

1741
01:15:22,320 --> 01:15:26,840
Og fordi vi har et best case runtime
n og en worst case runtime n

1742
01:15:26,840 --> 01:15:28,680
kvadreret, har vi ingen forventede runtime.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Det bare afhænger af
kaos på vores liste der.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
Og igen, en anden
graf og en anden tabel.

1747
01:15:39,530 --> 01:15:41,170
Så forskelle mellem slags.

1748
01:15:41,170 --> 01:15:44,180
Jeg skal bare til at brise gennem, jeg
føle, at vi har talt udførligt

1749
01:15:44,180 --> 01:15:46,570
om, hvordan de alle slags
af variere og linke sammen.

1750
01:15:46,570 --> 01:15:50,564
Så Mergesort er den sidste
Jeg skal kede jer med.

1751
01:15:50,564 --> 01:15:52,105
Vi har en temmelig farverigt billede.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Så Mergesort er en rekursiv algoritme.

1754
01:15:56,040 --> 01:15:59,910
Så tror du fyre vide, hvad
en rekursiv funktion er?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Enhver, der ønsker at sige?

1757
01:16:03,320 --> 01:16:04,739
Du ønsker at prøve?

1758
01:16:04,739 --> 01:16:07,280
Så en rekursiv funktion er kun
en funktion, der kalder sig selv.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Så hvis du fyre kender
med Fibonacci-sekvens,

1761
01:16:11,590 --> 01:16:15,670
der er anses for rekursiv fordi
du tager de to foregående

1762
01:16:15,670 --> 01:16:17,530
og tilføje dem sammen
at få din næste.

1763
01:16:17,530 --> 01:16:21,440
Så rekursive, jeg tror altid
rekursion som som en spiral

1764
01:16:21,440 --> 01:16:24,430
så du er ligesom en spiral ned i den.

1765
01:16:24,430 --> 01:16:27,150
Men det er bare en funktion
der kalder sig.

1766
01:16:27,150 --> 01:16:32,660
>> Og faktisk, virkelig hurtigt jeg
kan vise dig, hvad der ligner.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Så rekursive her, hvis vi ser, det er
rekursive måde at opsummere over en array.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Så alt, hvad vi gør, er
vi har funktion sum

1771
01:16:47,880 --> 01:16:52,210
sum, der tager en størrelse og et array.

1772
01:16:52,210 --> 01:16:55,210
Og hvis du bemærker, størrelse
formindskelser af en hver gang.

1773
01:16:55,210 --> 01:17:00,365
Og alt det gør er, hvis x er lig med
zero-- så hvis størrelsen af ​​array

1774
01:17:00,365 --> 01:17:02,710
er lig med zero-- det returnerer nul.

1775
01:17:02,710 --> 01:17:10,440
>> Ellers summerer dette
sidste element i arrayet,

1776
01:17:10,440 --> 01:17:14,790
og derefter tager en sum af
resten af ​​arrayet.

1777
01:17:14,790 --> 01:17:17,555
Så det er bare at bryde det ned
i mindre og mindre problemer.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Lang historie kort, rekursion,
funktion, der kalder sig selv.

1780
01:17:21,890 --> 01:17:25,740
Hvis det er alt, hvad du fik ud af dette,
det er, hvad en rekursiv funktion er.

1781
01:17:25,740 --> 01:17:29,870
Hvis du tager 51, vil du få meget,
meget komfortabel med rekursion.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
Det er virkelig cool.

1784
01:17:32,370 --> 01:17:34,660
Det gav mening på ligesom
03:00 en nat ud.

1785
01:17:34,660 --> 01:17:37,900
Og jeg var ligesom, hvorfor
har jeg aldrig bruge dette?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Så for Mergesort, dybest set
hvad det kommer til at gøre, er at det er

1788
01:17:42,430 --> 01:17:45,620
kommer til at bryde det ned og bryde det
ned, indtil det er bare enkelte elementer.

1789
01:17:45,620 --> 01:17:47,570
De enkelte elementer er let at sortere.

1790
01:17:47,570 --> 01:17:48,070
Vi ser, at.

1791
01:17:48,070 --> 01:17:50,760
Hvis du har et element, det er
allerede overvejet sorteres.

1792
01:17:50,760 --> 01:17:53,800
Så på en indgang af n elementer,
hvis n er mindre end 2,

1793
01:17:53,800 --> 01:17:58,120
bare vende tilbage, fordi det betyder
det er enten 0 eller 1, som vi har set.

1794
01:17:58,120 --> 01:18:00,050
De anses sorterede elementer.

1795
01:18:00,050 --> 01:18:02,170
>> Ellers bryde det i halve.

1796
01:18:02,170 --> 01:18:06,336
Sorter første halvdel, sortere det andet
halve, og derefter flette dem sammen.

1797
01:18:06,336 --> 01:18:07,460
Hvorfor det hedder Mergesort.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Så vi har her vi skal sortere disse.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Så vi holder have dem
indtil array-størrelse er 1.

1802
01:18:17,210 --> 01:18:20,790
Så når det er 1, vi bare tilbage
fordi dette er en sorterede array,

1803
01:18:20,790 --> 01:18:23,940
og dette er en sorterede array, og det er
en sorteret array, vi alle sorteret.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Så hvad vi gør, er vi
begynde at sammenlægge dem sammen.

1806
01:18:29,420 --> 01:18:31,820
>> Så den måde, du kan
tænke sammenlægning er

1807
01:18:31,820 --> 01:18:36,240
du bare fjerne den mindre
antal af hver af de sub arrays

1808
01:18:36,240 --> 01:18:38,330
og bare tilføje det til opstået array.

1809
01:18:38,330 --> 01:18:44,290
Så hvis du ser her, når vi har
disse sæt har vi 4, 6 og 1.

1810
01:18:44,290 --> 01:18:47,280
Når vi ønsker at fusionere disse,
vi ser på disse to første

1811
01:18:47,280 --> 01:18:50,730
og vi siger, OK, 1 er mindre,
det går til fronten.

1812
01:18:50,730 --> 01:18:54,330
4 og 6, der er intet at sammenligne
det til, bare tag det på til enden.

1813
01:18:54,330 --> 01:18:58,020
>> Når vi kombinerer disse to, vi bare
tage den mindste af disse to,

1814
01:18:58,020 --> 01:18:59,310
så det er 1.

1815
01:18:59,310 --> 01:19:01,690
Og nu tager vi
mindste af disse to, så 2.

1816
01:19:01,690 --> 01:19:03,330
Mindste af disse to, 3.

1817
01:19:03,330 --> 01:19:06,260
Mindste af disse to, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Så du bare trække ud disse.

1819
01:19:08,630 --> 01:19:11,210
Og fordi de har
blevet sorteret tidligere,

1820
01:19:11,210 --> 01:19:14,300
du bare har én
sammenligning, hver gang der.

1821
01:19:14,300 --> 01:19:19,610
Så mere kode her, bare repræsentation.

1822
01:19:19,610 --> 01:19:24,410
Så du starter på midten og
du sortere venstre og højre

1823
01:19:24,410 --> 01:19:26,180
og så skal du bare flette dem.

1824
01:19:26,180 --> 01:19:30,080
>> Og vi har ikke kode
for fusionere lige her.

1825
01:19:30,080 --> 01:19:34,110
Men igen, hvis du går på
studere 50, vil det være der.

1826
01:19:34,110 --> 01:19:36,860
Ellers kommer tale med mig
hvis du stadig forvirret.

1827
01:19:36,860 --> 01:19:42,340
Så cool ting her er, at bedste fald
worst case, og forventede driftstid

1828
01:19:42,340 --> 01:19:46,250
er alle i log n, som
er langt bedre, end vi har

1829
01:19:46,250 --> 01:19:48,000
ses for resten af ​​vores slags.

1830
01:19:48,000 --> 01:19:51,840
Vi har set n kvadreret
og hvad vi rent faktisk

1831
01:19:51,840 --> 01:19:54,380
får her er n log n, som er fantastisk.

1832
01:19:54,380 --> 01:19:55,830
>> Se på, hvor meget bedre det er.

1833
01:19:55,830 --> 01:19:56,780
Sådan en nice kurve.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Så meget mere effektiv.

1836
01:20:00,120 --> 01:20:03,510
Hvis du nogensinde kan, brug Mergesort.

1837
01:20:03,510 --> 01:20:04,810
Det vil spare dig tid.

1838
01:20:04,810 --> 01:20:07,670
Så igen, da vi sagde, hvis
du ned i denne lavere region,

1839
01:20:07,670 --> 01:20:09,480
det gør ikke, at
meget af en forskel.

1840
01:20:09,480 --> 01:20:11,360
Du får op til flere tusinde
og tusindvis af input,

1841
01:20:11,360 --> 01:20:13,318
du helt sikkert vil have en
mere effektiv algoritme.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
Og igen, vores dejlige tabel over alle
slags, der du fyre lært i dag.

1844
01:20:19,400 --> 01:20:21,157
>> Så jeg ved, det har været en tæt dag.

1845
01:20:21,157 --> 01:20:23,490
Dette er ikke nødvendigvis vil
at hjælpe dig med din pset.

1846
01:20:23,490 --> 01:20:28,250
Men jeg vil bare gøre en erklæring om ansvarsfraskrivelse
dette afsnit handler ikke kun om psets.

1847
01:20:28,250 --> 01:20:31,240
Alt dette materiale er fair
spil til dine midterms.

1848
01:20:31,240 --> 01:20:35,430
Og også hvis du fortsætte med CS,
disse er virkelig vigtige nøgletal

1849
01:20:35,430 --> 01:20:37,870
at du behøver at vide.

1850
01:20:37,870 --> 01:20:41,700
Så nogle dage vil være en
lidt mere pset hjælp,

1851
01:20:41,700 --> 01:20:44,600
men nogle uger vil være
meget mere faktiske indhold

1852
01:20:44,600 --> 01:20:46,600
der måske ikke synes super
nyttige for dig lige nu,

1853
01:20:46,600 --> 01:20:51,215
men jeg lover, hvis du fortsætter
på vil være meget, meget nyttig.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Så det er det for sektionen.

1856
01:20:54,250 --> 01:20:55,250
Ned til ledningen.

1857
01:20:55,250 --> 01:20:56,570
Jeg gjorde det inden for et minut.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Men der du går.

1860
01:20:58,970 --> 01:21:01,240
Og jeg vil have donuts eller slik.

1861
01:21:01,240 --> 01:21:03,464
Er der nogen allergisk over for
noget, ved den måde?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Æg og mælk.

1864
01:21:05,890 --> 01:21:08,120
Så donuts er et nej?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
OK.

1867
01:21:10,160 --> 01:21:10,770
Ok.

1868
01:21:10,770 --> 01:21:12,120
Chokolade nej?

1869
01:21:12,120 --> 01:21:12,620
Starburst.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starbursts er god.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Vi bliver nødt til
Starburst næste uge derefter.

1874
01:21:17,045 --> 01:21:18,240
Det er, hvad jeg får.

1875
01:21:18,240 --> 01:21:19,690
Du fyre har en stor uge.

1876
01:21:19,690 --> 01:21:20,460
Læs din spec.

1877
01:21:20,460 --> 01:21:22,130
>> Lad mig vide, hvis du har spørgsmål.

1878
01:21:22,130 --> 01:21:25,300
Pset to karakterer skal være
ud til dig af torsdag.

1879
01:21:25,300 --> 01:21:28,320
Hvis du har spørgsmål
om hvordan jeg sorterede noget

1880
01:21:28,320 --> 01:21:32,250
eller hvorfor jeg sorterede noget den måde, jeg
gjorde, så skriv til mig, kom tale med mig.

1881
01:21:32,250 --> 01:21:34,210
Jeg er lidt crazy dette
uge, men jeg lover

1882
01:21:34,210 --> 01:21:36,340
Jeg vil stadig svare inden for 24 timer.

1883
01:21:36,340 --> 01:21:38,240
Så har en stor uge, alle.

1884
01:21:38,240 --> 01:21:40,090
Held og lykke på din pset.

1885
01:21:40,090 --> 01:21:41,248