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

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

3
00:00:12,300 --> 00:00:13,890
Velkommen tilbake til del.

4
00:00:13,890 --> 00:00:17,480
Så glad for å se så mange av dere begge her,
og alle som ser på nettet.

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

6
00:00:18,760 --> 00:00:20,920
Så, som vanlig velkommen tilbake.

7
00:00:20,920 --> 00:00:24,360
Jeg håper at dere alle har hatt en fin
helg, full av ro, avslapning.

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

9
00:00:26,026 --> 00:00:27,525
Så, jeg håper du likte utendørs.

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

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

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

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

14
00:00:32,700 --> 00:00:37,350
Så, de fleste av dere burde ha fått en
e-post fra meg om din Scratch PSet,

15
00:00:37,350 --> 00:00:39,920
samt for gradering 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
Pass på å bruke check50 i style50.

19
00:00:45,150 --> 00:00:47,250
Disse er ment å være
ressurser til dere,

20
00:00:47,250 --> 00:00:50,660
å sørge for at du får
så mange poeng som du kan

21
00:00:50,660 --> 00:00:52,390
uten unødvendig å miste dem.

22
00:00:52,390 --> 00:00:54,407
Så, ting som stil
er svært viktig.

23
00:00:54,407 --> 00:00:55,740
Vi kommer til å ta av for det.

24
00:00:55,740 --> 00:00:58,115
Noen av dere har kanskje allerede
lagt merke til at fra PSet.

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

26
00:00:58,920 --> 00:01:01,450
Og check50 er bare en
veldig enkel måte å sørge for at

27
00:01:01,450 --> 00:01:05,050
at vi faktisk tilbake hva
må returneres til brukeren,

28
00:01:05,050 --> 00:01:06,690
og at alt er i brukbar stand.

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

30
00:01:08,690 --> 00:01:12,040
>> På den andre notatet, sørg for at
laste opp ting til riktig mappe.

31
00:01:12,040 --> 00:01:14,470
Det gjør livet mitt bare en
litt vanskeligere

32
00:01:14,470 --> 00:01:18,836
hvis du laster opp PSet 2 inn PSet 1
fordi når jeg laster ned ting,

33
00:01:18,836 --> 00:01:20,085
de ikke laste riktig.

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

35
00:01:21,690 --> 00:01:24,560
Og jeg vet det er litt wonky
i et system for å venne seg til,

36
00:01:24,560 --> 00:01:26,950
men bare være super
forsiktig, hvis bare for meg,

37
00:01:26,950 --> 00:01:30,080
slik at når du får e-post
på som to A.M. og jeg er gradering.

38
00:01:30,080 --> 00:01:33,710
Hvis ikke føre jeg må se
alle rundt for din PSet.

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

40
00:01:34,440 --> 00:01:37,270
>> Jeg vet det er tidlig, men jeg
helt fikk tatt av vakt

41
00:01:37,270 --> 00:01:40,800
av et essay som er grunn denne fredagen, som
mine professorer var bare liker, oh yeah.

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

43
00:01:42,550 --> 00:01:45,780
Så, jeg vet ingen liker
å tenke på midterms,

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

45
00:01:50,620 --> 00:01:53,290
Så, kan det være raskere
enn du forventet er alt.

46
00:01:53,290 --> 00:01:57,510
Slik at du ikke kastet av vakt når
Jeg nevner neste ukes delen som oh,

47
00:01:57,510 --> 00:02:00,560
din quiz neste uke, tenkte jeg
Jeg vil gi deg litt mer

48
00:02:00,560 --> 00:02:01,500
av en heads up nå.

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

50
00:02:02,970 --> 00:02:04,660
>> Så, problemet satt, nummer tre.

51
00:02:04,660 --> 00:02:07,070
Hvordan folk har lest
spec ut av nysgjerrighet?

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 fikk et par.

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

56
00:02:12,320 --> 00:02:13,650
Jeg vet det var vakkert ut.

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
Definitivt etter at du får gjort
i dag lese spec minst

60
00:02:21,010 --> 00:02:25,240
prøve som laster ned
distribusjon kode og kjører

61
00:02:25,240 --> 00:02:27,430
som den første innledende
ting som de ber deg om det.

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

63
00:02:28,681 --> 00:02:32,590
Fordi vi bruker
distribusjon kode og bibliotek

64
00:02:32,590 --> 00:02:36,790
at vi har bare vært using-- --det er bare
andre gang vi har gjort dette PSet,

65
00:02:36,790 --> 00:02:38,650
gale ting kan skje
med apparatet,

66
00:02:38,650 --> 00:02:41,370
og du vil finne at
ute nå versus senere.

67
00:02:41,370 --> 00:02:45,570
>> Fordi hvis det er torsdag kveld, eller det er
Onsdag kveld og for noen grunn

68
00:02:45,570 --> 00:02:48,912
apparatet gjør bare ikke
ønsker å kjøre med biblioteket

69
00:02:48,912 --> 00:02:50,620
eller med distribusjonen
kode, at midler

70
00:02:50,620 --> 00:02:52,309
du kan ikke engang begynne å gjøre kodingen.

71
00:02:52,309 --> 00:02:54,100
Fordi du kan ikke sjekke
for å se om det fungerer.

72
00:02:54,100 --> 00:02:55,975
Ikke skal kunne
å se om det kompilerer.

73
00:02:55,975 --> 00:03:00,500
Du ønsker å ta vare på de som tidlig
uken, når du fortsatt kan sende meg

74
00:03:00,500 --> 00:03:03,100
eller en av de andre TFS,
og vi kan få de fikset.

75
00:03:03,100 --> 00:03:05,410
Fordi de er problemer
som kommer til å stoppe deg

76
00:03:05,410 --> 00:03:07,120
fra å gjøre noen reell fremgang.

77
00:03:07,120 --> 00:03:10,055
Det er ikke som en bug, som
du kan bare slags hoppe 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
apparatet eller distribusjon kode,

80
00:03:13,420 --> 00:03:16,211
du virkelig ønsker å få det tatt
vare på før heller enn senere.

81
00:03:16,211 --> 00:03:20,410
Så selv om du ikke skal faktisk
starte koding, laste ned distribusjon

82
00:03:20,410 --> 00:03:24,040
koden, leser spec, sørg
alt fungerer der.

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

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

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

86
00:03:28,800 --> 00:03:31,410
Og så er du sannsynligvis kommer
å gjøre det akkurat nå ikke sant?

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

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

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

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

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

92
00:03:38,270 --> 00:03:41,700
>> Ansvar for de av
deg på rommet og på nettet.

93
00:03:41,700 --> 00:03:45,437
Jeg kommer til å være å prøve å slå
mellom PowerPoint i apparatet

94
00:03:45,437 --> 00:03:47,270
fordi vi kommer
å være å gjøre noen koding

95
00:03:47,270 --> 00:03:53,630
i dag etter stor etterspørsel av den anonyme
forslag meningsmåling jeg sendte ut i forrige uke.

96
00:03:53,630 --> 00:03:55,480
Så vil vi gjøre noen koding.

97
00:03:55,480 --> 00:03:57,800
Så, hvis dere også vil ha
å fyre opp dine hvitevarer,

98
00:03:57,800 --> 00:04:02,910
og du skal ha fått en e-post
fra meg, med en prøve-fil.

99
00:04:02,910 --> 00:04:04,310
Ta gjerne gjøre det.

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

101
00:04:07,340 --> 00:04:09,970
Det kommer til å hjelpe deg
slags finne ut hvor

102
00:04:09,970 --> 00:04:11,860
ting går galt i koden.

103
00:04:11,860 --> 00:04:15,370
Det er egentlig bare en måte for deg å gå
gjennom koden din så det skjer,

104
00:04:15,370 --> 00:04:19,100
og være i stand til å skrive ut variabler
eller se hva som faktisk skjer

105
00:04:19,100 --> 00:04:22,980
under panseret vers programmet
bare å kjøre, det er som forkastninger,

106
00:04:22,980 --> 00:04:25,030
og du er like, ingen anelse
hva skjedde her.

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

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

109
00:04:29,040 --> 00:04:31,280
Så, er GDB kommer til å hjelpe deg med det.

110
00:04:31,280 --> 00:04:35,240
Også, hvis du bestemmer deg for å
fortsette ja, og ta 61,

111
00:04:35,240 --> 00:04:38,430
det vil virkelig, virkelig være din
beste venn, fordi jeg kan fortelle deg

112
00:04:38,430 --> 00:04:40,840
fordi jeg går gjennom den klassen.

113
00:04:40,840 --> 00:04:43,620
>> Vi kommer til å se på binær
søk, som hvis dere husker

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

115
00:04:47,540 --> 00:04:50,620
Vi kommer til å gjennomføre det, og
vandre gjennom det litt mer,

116
00:04:50,620 --> 00:04:54,650
og så skal vi gjennom fire
forskjellige slags, som er boble,

117
00:04:54,650 --> 00:04:56,285
Utvalg, Innsetting, og flett.

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 nevnte, er en debugger.

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

122
00:05:01,400 --> 00:05:09,370
Og dette er slags stor
ting, de store funksjoner eller kommandoer

123
00:05:09,370 --> 00:05:13,240
som du bruker i løpet av GDB, og jeg vil gå
deg gjennom en demo av det i et sekund.

124
00:05:13,240 --> 00:05:15,360
>> Så, dette er ikke bare
kommer til å bli abstrakt.

125
00:05:15,360 --> 00:05:18,000
Jeg skal prøve og gjøre det så konkret
som mulig for dere.

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

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

128
00:05:22,200 --> 00:05:26,900
representerer en linje i programmet,
eller du kan navngi en funksjon.

129
00:05:26,900 --> 00:05:30,150
Så, hvis du sier bryte hoved,
det vil stoppe på hoved,

130
00:05:30,150 --> 00:05:32,400
og la deg gå gjennom den funksjonen.

131
00:05:32,400 --> 00:05:36,350
>> Likeledes, hvis du har noen ekstern
fungere som Swap eller Cube,

132
00:05:36,350 --> 00:05:38,450
som vi så på i forrige uke.

133
00:05:38,450 --> 00:05:41,780
Hvis du sier bryte en av dem,
når programmet treffer det,

134
00:05:41,780 --> 00:05:44,290
det vil vente på deg til
fortelle den hva du skal gjøre.

135
00:05:44,290 --> 00:05:47,860
Før det vil bare kjøre slik at du
faktisk kunne gå innenfor funksjonen

136
00:05:47,860 --> 00:05:49,020
og se hva som skjer.

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

138
00:05:50,370 --> 00:05:53,515
Så, neste, hopper bare over
neste linje, går over funksjoner.

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

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

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

142
00:05:56,810 --> 00:06:00,530
Så, jeg bare kommer til å kjøre gjennom dem,
men du vil se dem i bruk i en annen.

143
00:06:00,530 --> 00:06:01,810
>> Gå inn i en funksjon.

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

145
00:06:04,170 --> 00:06:07,110
tillate deg å faktisk som om du er
som fysisk stepping inni,

146
00:06:07,110 --> 00:06:10,990
du kan rote med disse variablene, print
ut hva de er, se hva som skjer.

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

148
00:06:12,140 --> 00:06:14,830
Listen vil bokstavelig talt bare skrive
ut rundt koden.

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

150
00:06:17,570 --> 00:06:19,880
eller kanskje du lurer
hva som skjer rundt det,

151
00:06:19,880 --> 00:06:23,790
dette vil bare skrive ut et segment
av liker fem eller seks linjer rundt det.

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

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

154
00:06:27,230 --> 00:06:28,650
>> Skriv ut noen variable.

155
00:06:28,650 --> 00:06:34,590
Så, hvis du har nøkkelen som
i Cæsar, som vi skal se på.

156
00:06:34,590 --> 00:06:36,220
Du kan si Print Key på noe punkt.

157
00:06:36,220 --> 00:06:40,070
Det vil fortelle deg hva verdien er så
det, kanskje et sted på veien,

158
00:06:40,070 --> 00:06:42,070
du overskrev din nøkkel.

159
00:06:42,070 --> 00:06:45,495
Du kan faktisk fortelle at fordi
du kan faktisk observere at verdi.

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

161
00:06:46,500 --> 00:06:48,780
>> I lokalbefolkningen, bare utskrifter
ut din lokale variabler.

162
00:06:48,780 --> 00:06:53,120
Så, når du er innenfor en løkke,
og du bare ønsker å se ut som, oh.

163
00:06:53,120 --> 00:06:54,270
Hva er mitt jeg?

164
00:06:54,270 --> 00:06:57,020
Hva er dette nøkkelverdi
at jeg initial her?

165
00:06:57,020 --> 00:06:58,537
Hva er budskapet på dette punktet?

166
00:06:58,537 --> 00:07:00,370
Det vil bare skrive ut alle
av dem, slik at man

167
00:07:00,370 --> 00:07:04,330
trenger ikke å individuelt
si, Print I. Skriv 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 så Skjerm.

171
00:07:07,700 --> 00:07:10,370
Hva det gjør er som du
gå gjennom programmet,

172
00:07:10,370 --> 00:07:13,980
det vil bare være sikker på at det er
viser noen bestemt variabel

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

174
00:07:14,780 --> 00:07:17,160
Slik at du also-- --det er
slag av en snarvei der

175
00:07:17,160 --> 00:07:19,530
du trenger ikke å holde det gående like, oh.

176
00:07:19,530 --> 00:07:23,150
Print Nøkkel eller Print I. Det bare
vil automatisk gjøre det for deg.

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

178
00:07:25,959 --> 00:07:28,000
Jeg kommer til å prøve og bytte
over til min apparatet.

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

180
00:07:30,200 --> 00:07:31,271
Se om jeg kan gjø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 kommer bare til å speile det.

184
00:07:42,370 --> 00:07:44,530
Det er ingenting gale
på min laptop anyways.

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

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

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

188
00:07:57,030 --> 00:08:01,054
Dette må være denne.

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

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

191
00:08:03,730 --> 00:08:05,120
La oss se om vi kan gjø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 åpenbart sliter
her bare en liten bit,

195
00:08:15,305 --> 00:08:17,995
men vi vil få 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 kommer til å øke 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
Kanskje litt?

203
00:08:32,470 --> 00:08:33,594
Jeg vet det er litt for liten.

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

205
00:08:34,570 --> 00:08:37,530
Du kan ikke helt finne ut
hvordan å gjøre dette større.

206
00:08:37,530 --> 00:08:38,350
Hvis noen vet.

207
00:08:38,350 --> 00:08:40,309
Er det noen som vet hvordan å gjø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 å rulle med den.

210
00:08:42,140 --> 00:08:45,801
Spiller ingen rolle anyways fordi det er bare
det er koden som dere bør

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

212
00:08:46,300 --> 00:08:48,310
>> Hva er mer viktig
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å lite?

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

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

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
Sann Ike.

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

221
00:09:10,880 --> 00:09:11,770
Ut av det.

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 vet når du er i en CS
klasse tekniske problemer

228
00:09:28,220 --> 00:09:32,971
er slags del av the--
Så, la oss fjerne dette.

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

230
00:09:33,470 --> 00:09:38,060
Så, her i seksjonen,
som vi hadde her.

231
00:09:38,060 --> 00:09:40,830
Caesar er en kjørbar fil.

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

233
00:09:41,800 --> 00:09:46,370
Så, er én ting å realisere med GDB
at det fungerer bare på kjørbare filer.

234
00:09:46,370 --> 00:09:48,040
Så, kan du ikke kjøre den på en dotsy.

235
00:09:48,040 --> 00:09:50,532
Du må faktisk gjøre
sikker på at koden kompilerer,

236
00:09:50,532 --> 00:09:51,865
og at det faktisk kan kjø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
kompilere, få det til å kompilere,

239
00:09:56,186 --> 00:09:57,810
slik at du kan slags kjøre gjennom den.

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

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

242
00:10:06,250 --> 00:10:08,240
Jeg har alltid feilstaver Cæsar.

243
00:10:08,240 --> 00:10:11,730
Men du vil være sikker
siden det er en kjørbar,

244
00:10:11,730 --> 00:10:14,210
TIS dot flash slik at
betyr at du kommer

245
00:10:14,210 --> 00:10:19,240
å kjøre CSI du kommer til å kjøre
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å du det, får du
denne typen vrøvl.

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

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

250
00:10:25,750 --> 00:10:28,200
Du trenger egentlig ikke å
bekymre deg for det akkurat nå.

251
00:10:28,200 --> 00:10:31,460
Og som du ser, har vi denne
åpne parentesar, BNP, nære parentesar,

252
00:10:31,460 --> 00:10:34,690
og bare slags ser ut som
vår kommandolinjen, ikke sant?

253
00:10:34,690 --> 00:10:37,010
>> Så, hva vi ønsker å do--
--So, Det første

254
00:10:37,010 --> 00:10:39,570
er vi ønsker å velge
et sted å bryte den.

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

256
00:10:42,332 --> 00:10:44,290
at jeg presentere, at
vi kommer til å finne ut.

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

258
00:10:45,330 --> 00:10:56,350
Det Hva det betyr er at det tar inngangs
Barfoo i store bokstaver, og for noen grunn

259
00:10:56,350 --> 00:11:01,950
det endrer ikke A. Det etterlater bare
det alene, alt annet er riktig,

260
00:11:01,950 --> 00:11:03,980
men den andre bokstaven
En forblir uendret.

261
00:11:03,980 --> 00:11:07,120
Så vi kommer til å prøve og
finne ut hvorfor det er.

262
00:11:07,120 --> 00:11:10,440
Så, det første du vanligvis
ønsker å gjøre når du starter på GDB

263
00:11:10,440 --> 00:11:12,010
er å finne ut hvor du skal bryte den.

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

265
00:11:14,956 --> 00:11:16,330
Vi har bare én funksjon, ikke sant?

266
00:11:16,330 --> 00:11:18,520
Hva var vår funksjon i Cæsar?

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

268
00:11:19,590 --> 00:11:24,350
Det er bare én funksjon, Main sant?

269
00:11:24,350 --> 00:11:26,490
Hoved er en funksjon
for alle programmene dine.

270
00:11:26,490 --> 00:11:29,230
Hvis du ikke har Main, kanskje jeg
være litt bekymret akkurat nå,

271
00:11:29,230 --> 00:11:31,000
men jeg håper dere alle har hatt Hoved der inne.

272
00:11:31,000 --> 00:11:34,150
Så, hva vi kan gjøre er at vi kan
bare bryte Main, bare sånn.

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

274
00:11:35,190 --> 00:11:37,430
Vi setter vår stoppunkt der.

275
00:11:37,430 --> 00:11:42,870
>> Så, nå er det ting å huske Caesar
tar en kommandolinje argument retten

276
00:11:42,870 --> 00:11:45,150
og vi har ikke gjort det noe sted ennå.

277
00:11:45,150 --> 00:11:47,560
Så, hva du gjør er når
du faktisk går til å kjøre

278
00:11:47,560 --> 00:11:51,540
programmet, et program som du er
kjører i GDB som trenger kommandolinje

279
00:11:51,540 --> 00:11:55,010
argumenter, du kommer til innspill
når du først begynner å kjøre den.

280
00:11:55,010 --> 00:11:59,280
Så, i dette tilfelle, gjør vi
Kjør med en nøkkel på tre.

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

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

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

284
00:12:08,480 --> 00:12:12,210
Så hvis dere har all
den filen som jeg sendte ut opp

285
00:12:12,210 --> 00:12:15,100
vil du se at det er som det
første linjen vår viktigste funksjon, ikke sant?

286
00:12:15,100 --> 00:12:17,890
Det er å sjekke for å se om vi har
riktig antall argumenter.

287
00:12:17,890 --> 00:12:20,620
Så, hvis du lurer på
hvis RC er riktig,

288
00:12:20,620 --> 00:12:23,250
du kan gjøre noe akkurat som 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
hva vi forventet, ikke sant?

291
00:12:28,640 --> 00:12:32,010
>> Så kan vi gå neste,
og fortsetter gjennom.

292
00:12:32,010 --> 00:12:33,200
Så har vi noen viktige der.

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

294
00:12:34,260 --> 00:12:37,090
Og vi kan skrive ut vår nøkkel
å sørge for at det er riktig.

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 hva vi forventet.

298
00:12:41,210 --> 00:12:44,810
Så, en ting å realisere
med GDB også, er

299
00:12:44,810 --> 00:12:49,000
at det er ikke før du faktisk treffer
Neste, at linjen som du nettopp så

300
00:12:49,000 --> 00:12:50,720
faktisk er utført.

301
00:12:50,720 --> 00:12:53,870
Så, i dette tilfellet Key
har ikke blitt tildelt ennå.

302
00:12:53,870 --> 00:12:57,050
Så, er Key noen søppel verdi
som du ser på bunnen der.

303
00:12:57,050 --> 00:13:03,680
Negativ $ 120-- --det er en milliard
og noe rare ting riktig?

304
00:13:03,680 --> 00:13:05,340
Det er ikke nøkkelen som vi forventet.

305
00:13:05,340 --> 00:13:10,720
Men hvis vi treffer på Neste, og da er vi
prøv og trykk nøkkel, er det 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 noe
at du er som, vent.

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

309
00:13:15,540 --> 00:13:20,150
hvordan dette ville skje fordi alt jeg ønsker
å gjøre er å tilordne et tall, en variabel,

310
00:13:20,150 --> 00:13:22,900
prøv å treffe Deretter kan du prøve å skrive ut
det igjen, og se om det fungerer.

311
00:13:22,900 --> 00:13:27,830
Fordi det er bare kommer til å utføre og
faktisk tildele noe etter at du har

312
00:13:27,830 --> 00:13:29,340
rammet Neste.

313
00:13:29,340 --> 00:13:30,336
Fornuftig 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 tilfeldig
tall hva betyr det?

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

317
00:13:34,790 --> 00:13:35,710
Det er bare søppel.

318
00:13:35,710 --> 00:13:38,320
Det er bare noe som din
Datamaskinen vil tilfeldig 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å, nå kan vi gå gjennom, og så
nå har vi dette ren tekst GetString.

322
00:13:45,760 --> 00:13:48,600
Så, la meg bare presentere hva
vil skje når vi treffer Neste her.

323
00:13:48,600 --> 00:13:51,320
Vår GDB slags forsvinner, ikke sant?

324
00:13:51,320 --> 00:13:55,720
Det er fordi GetString
er nå å gjennomføre, ikke sant?

325
00:13:55,720 --> 00:14:01,460
Så, når vi så ren tekst lik
GetString, åpne parentesar og parentesar,

326
00:14:01,460 --> 00:14:04,380
og vi slo Deretter har det
faktisk henrettet nå.

327
00:14:04,380 --> 00:14:06,580
Så er det å vente på
oss å legge inn noe.

328
00:14:06,580 --> 00:14:13,560
>> Så, skal vi innspill maten som
er hva det er sviktende som jeg fortalte deg

329
00:14:13,560 --> 00:14:18,020
og som bare sier at det er
ferdig utføring, at den lukkes

330
00:14:18,020 --> 00:14:19,980
brakett betyr at det er
som kommer ut av denne sløyfe.

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

332
00:14:21,170 --> 00:14:25,420
Så kan vi treffer Neste, og nå som jeg er
at du er alle kjent fra keiser,

333
00:14:25,420 --> 00:14:27,260
dette er, hva er denne linjen kommer til å gjøre.

334
00:14:27,260 --> 00:14:32,030
Det er for Int jeg er lik 0, er lik N
Strlen, ren tekst, og deretter

335
00:14:32,030 --> 00:14:33,960
Jeg er mindre enn n, jeg, pluss, pluss.

336
00:14:33,960 --> 00:14:35,210
Hva er denne sløyfen kommer til å gjøre?

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

338
00:14:37,900 --> 00:14:39,160
Åpne meldingen.

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

340
00:14:39,770 --> 00:14:41,330
Så, la oss begynne å gjøre det.

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

342
00:14:47,210 --> 00:14:52,250
Hvis det er en B, det er ren tekst I. Vi
kan få informasjon om våre lokalbefolkningen.

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

344
00:14:53,610 --> 00:14:57,970
Så, er jeg null, og hvis seks, som
vi forventer, og vårt viktigste er tre.

345
00:14:57,970 --> 00:14:59,227
Alt som gir mening, ikke sant?

346
00:14:59,227 --> 00:15:01,310
Disse tallene er alle
nøyaktig hva de skal 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
tilfeldige tall for meg.

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

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: Vel, vi kan check-- --vi
kan prate om det i et sekund.

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

353
00:15:14,110 --> 00:15:15,750
Men du bør være å 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 for vår første,

356
00:15:20,130 --> 00:15:22,080
denne tilstanden bør ta det, ikke sant?

357
00:15:22,080 --> 00:15:27,120
Så, hvis vi treffer Deretter ser vi
at dette Dersom faktisk utfører.

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

359
00:15:29,220 --> 00:15:33,460
denne linjen her, hvor ren tekst jeg
er erstattet med denne aritmetikk,

360
00:15:33,460 --> 00:15:35,720
bare utfører dersom Dersom
betingelsen er riktig rett?

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

362
00:15:36,905 --> 00:15:40,240
>> GDB er bare kommer til å vise deg
ting som faktisk utfører.

363
00:15:40,240 --> 00:15:45,140
Så hvis dette Dersom tilstanden ikke ble oppfylt, er det
bare kommer til å hoppe til neste linje.

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

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

366
00:15:48,510 --> 00:15:51,171
Denne braketten betyr at det er
lukket ut av at sløyfen nå.

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

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

369
00:15:54,760 --> 00:15:56,280
Bare sånn.

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

371
00:15:59,120 --> 00:16:02,575
og vi ser at vår første
brev har endret seg, ikke sant?

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

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

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

375
00:16:08,500 --> 00:16:09,916
Og denne kontrollen skal fungere, ikke sant?

376
00:16:09,916 --> 00:16:12,570
Det er A. Det bør endres
tre bokstaver fremover.

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

378
00:16:14,320 --> 00:16:16,530
Men hvis du legger merke til, vi
få noe annet.

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

380
00:16:17,580 --> 00:16:22,860
Så i dette tilfellet her opp, det fanget
den, og slik at denne linjen utført,

381
00:16:22,860 --> 00:16:28,620
som endret vår B.
Men i dette tilfellet er her,

382
00:16:28,620 --> 00:16:32,860
vi har at det bare hoppet over den,
og gikk til [? L SIFF. ?]

383
00:16:32,860 --> 00:16:34,660
Så noe skjer der.

384
00:16:34,660 --> 00:16:37,780
Hva som er å fortelle deg er at,
vi vet 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 noen se hva våre
Problemet ligger i at linjen?

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

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

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

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 det-- men det er i [uhørbart].

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

393
00:16:55,480 --> 00:16:58,639
>> SPEAKER 4: Det er på større enn
siden hvis du leser det i boken.

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

395
00:16:59,430 --> 00:17:02,620
Så, debugger kunne ikke fortelle
du det, men debugger

396
00:17:02,620 --> 00:17:05,880
kan få deg ned til en linje
som du vet ikke fungerer.

397
00:17:05,880 --> 00:17:09,319
Og noen ganger, når spesielt
senere i semesteret, da

398
00:17:09,319 --> 00:17:12,910
du arbeider med hundre, en
hundre få linjer med kode, og du

399
00:17:12,910 --> 00:17:16,190
vet ikke hvor det er sviktende,
dette er en fin måte å gjøre det.

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

401
00:17:17,900 --> 00:17:18,989
Så, har vi funnet vår bug.

402
00:17:18,989 --> 00:17:21,530
Du kan fikse det i filen,
og deretter kan du kjøre den på nytt,

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

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

405
00:17:24,970 --> 00:17:30,590
Og den største tingen er
Dette kan virke som, OK.

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

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

408
00:17:31,370 --> 00:17:32,744
Du visste det du leter etter.

409
00:17:32,744 --> 00:17:34,910
Så, visste du hva du skal gjøre.

410
00:17:34,910 --> 00:17:39,021
>> GDB kan være super nyttig fordi du
kan skrive ut alle disse tingene som du

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

412
00:17:39,520 --> 00:17:41,160
Det er mye mer nyttig enn printf.

413
00:17:41,160 --> 00:17:43,440
Hvor mange av dere bruker
som printf uttalelser

414
00:17:43,440 --> 00:17:46,200
å finne ut hvor en bug var, ikke sant?

415
00:17:46,200 --> 00:17:48,450
Så, med dette, gjør du ikke
nødt til å holde tilbake,

416
00:17:48,450 --> 00:17:51,139
og liker kommenterer i
Printf, eller kommentere ut,

417
00:17:51,139 --> 00:17:52,930
og finne ut hva
du skal skrive ut.

418
00:17:52,930 --> 00:17:55,670
Dette faktisk bare lar deg
bla gjennom, skrive ut ting

419
00:17:55,670 --> 00:18:00,000
som du kommer gjennom, så kan du
observere hvordan de endrer i sanntid,

420
00:18:00,000 --> 00:18:02,190
som programmet kjører.

421
00:18:02,190 --> 00:18:04,390
>> Og det tar litt
bit av å bli vant til.

422
00:18:04,390 --> 00:18:07,850
Jeg vil sterkt anbefale bare slags
for å være litt frustrert med det

423
00:18:07,850 --> 00:18:08,930
for akkurat nå.

424
00:18:08,930 --> 00:18:13,450
Hvis du tilbringer en time over
neste uke lære å bruke GDB,

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

426
00:18:16,140 --> 00:18:18,750
Og bokstavelig talt. vi forteller
dette til folk hvert år,

427
00:18:18,750 --> 00:18:23,890
og jeg husker da jeg tok
klasse, var jeg liker, jeg vil bli bra.

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

429
00:18:24,700 --> 00:18:27,030
PSet 6 kom på, og jeg var
liker, jeg skal lære

430
00:18:27,030 --> 00:18:29,500
hvordan du bruker GDB fordi jeg ikke
vet hva som skjer her.

431
00:18:29,500 --> 00:18:32,940
>> Så hvis du tar deg tid så
bruke den på mindre programmer

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

433
00:18:35,697 --> 00:18:37,530
gjennom noe sånt
Visionäre, som dette.

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

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

436
00:18:42,850 --> 00:18:45,300
for deg å feilsøke hvis du ønsker.

437
00:18:45,300 --> 00:18:49,300
>> Men hvis du bare tar litt tid å komme
vant til det, bare spille rundt med den,

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

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

440
00:18:52,591 --> 00:18:57,340
må prøve og få hendene skitne
med, før du virkelig forstår det.

441
00:18:57,340 --> 00:19:02,090
Jeg egentlig bare forstått det en gang
Jeg måtte feilsøke ting med det,

442
00:19:02,090 --> 00:19:08,170
og det er mye hyggeligere å ha en idé om
hvordan å feilsøke før heller enn 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 vet det er litt som
et lynkurs i GDB,

446
00:19:12,960 --> 00:19:16,400
og jeg vil definitivt jobbe med å få
disse for å se større neste 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 tilbake til vår PowerPoint.

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

451
00:19:27,194 --> 00:19:28,110
Dette kommer til å fungere?

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 skulle trenge noen av
de igjen, det er på listen.

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

458
00:19:37,160 --> 00:19:40,830
Så Binary Search, som alle
husker den store opptog av David

459
00:19:40,830 --> 00:19:42,259
ripping telefonkataloger i to.

460
00:19:42,259 --> 00:19:44,050
Jeg vet egentlig ikke får
telefonen bøker lenger,

461
00:19:44,050 --> 00:19:46,530
fordi som der gjør du
få telefonen bøker i disse dager?

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

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

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

465
00:19:50,590 --> 00:19:52,464
Er det noen som husker
hvordan Binary Search fungerer?

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

467
00:19:54,380 --> 00:19:55,220
Noen i det hele tatt?

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

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: Du vet når
du ser på hvilken halvdel

470
00:19:58,283 --> 00:20:01,146
det ville være i, Basert på det,
og bli kvitt den andre halvparten.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER en Nettopp.

472
00:20:01,896 --> 00:20:06,290
Så, Binary Search, er det slags a--
--Vi liker å kalle det splitt og hersk.

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

474
00:20:09,170 --> 00:20:11,990
og du vil se om det samsvarer
det du leter etter.

475
00:20:11,990 --> 00:20:15,420
Og hvis det ikke skjer, så du prøver å
finne ut, det kommer til å stå

476
00:20:15,420 --> 00:20:16,450
halvparten eller høyre halvdel.

477
00:20:16,450 --> 00:20:19,325
Så, dette kan være hvis du leter
på noe som er alfabetisert,

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

479
00:20:20,720 --> 00:20:22,750
Betyr 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å, skal vi
se på den første halvdelen.

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

483
00:20:26,450 --> 00:20:28,830
Alt som du kan
null, kan det bli sortert.

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

485
00:20:29,920 --> 00:20:31,260
Du kan bruke binære søk på.

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

487
00:20:32,340 --> 00:20:37,455
Så, noen som husker dette
graf eller hva dette er?

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

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

490
00:20:42,830 --> 00:20:46,230
tar deg til å løse et problem som
du øke antall ting

491
00:20:46,230 --> 00:20:47,090
som du bruker.

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

493
00:20:51,260 --> 00:20:54,560
Hvis N over to, som er litt
bedre, vokser fortsatt super rask.

494
00:20:54,560 --> 00:20:58,360
Og da har vi Logg inn, noe som er
det vi anser Binary Search.

495
00:20:58,360 --> 00:21:03,630
Hvis vi legger merke til, så problemet ditt
blir mye og mye større,

496
00:21:03,630 --> 00:21:06,600
den tiden det tar deg å løse det
egentlig ikke øke så mye.

497
00:21:06,600 --> 00:21:09,010
Det er som sammenlign
her i begynnelsen.

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

499
00:21:10,060 --> 00:21:13,000
Noe her gjør virkelig ikke
Uansett hvilken vi bruker,

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

501
00:21:16,220 --> 00:21:20,010
Du prøver å finne some-- --you're
prøver å finne en nål i en høystakk.

502
00:21:20,010 --> 00:21:21,550
>> Jeg tror du vil ha dette problemet.

503
00:21:21,550 --> 00:21:25,850
Du ønsker denne kompleksiteten, ikke
lineær fordi for alt du

504
00:21:25,850 --> 00:21:30,049
kjenner din skal være å søke gjennom
hver enkelt nål, ting av høy,

505
00:21:30,049 --> 00:21:31,340
prøver å lete etter nålen.

506
00:21:31,340 --> 00:21:34,730
Og det er ikke så gøy etter min mening.

507
00:21:34,730 --> 00:21:35,500
Jeg liker rask.

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

509
00:21:36,620 --> 00:21:40,450
Og så hardtarbeidende studenter deg
gutta er, vet du jobbe smartere,

510
00:21:40,450 --> 00:21:43,010
ikke hardere type ting, hvordan du
kan gjøre opp disse algoritmene.

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

512
00:21:45,110 --> 00:21:47,910
>> Så vi kommer til å gå
gjennom bare en rask eksempel.

513
00:21:47,910 --> 00:21:51,090
Jeg tror dere bør ha
en hånd på Binary Search,

514
00:21:51,090 --> 00:21:54,352
men i tilfelle noen er litt
fuzzy, ønsker å forsterke det,

515
00:21:54,352 --> 00:21:56,310
vi skal bare gå
gjennom et eksempel her.

516
00:21:56,310 --> 00:21:59,490
Så vi leter etter hvis
matrisen inneholder syv.

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

518
00:22:00,540 --> 00:22:06,010
>> Så, er det første vi gjør
ser i midten, ikke sant?

519
00:22:06,010 --> 00:22:09,340
Og også du kommer til å bli koding
Binary Søk på bare et sekund.

520
00:22:09,340 --> 00:22:11,310
Så det kommer til å bli gøy.

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

522
00:22:13,710 --> 00:22:15,501
Har tre lik 7?

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

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 enn
eller større enn syv?

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

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

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

530
00:22:24,570 --> 00:22:25,170
Nice jobb folkens.

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

532
00:22:25,569 --> 00:22:27,360
Jeg føler jeg at jeg burde
ha godteri fordi jeg

533
00:22:27,360 --> 00:22:29,460
ønsker å kaste den ut i verftene.

534
00:22:29,460 --> 00:22:30,270
Det er hva jeg skal gjøre neste uke.

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

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

537
00:22:32,560 --> 00:22:34,690
>> Så kaster vi bort at
første halvår, ikke sant?

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

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

540
00:22:39,325 --> 00:22:41,700
kommer til å være mindre enn hva
vi faktisk leter etter.

541
00:22:41,700 --> 00:22:43,491
Så det er ingen grunn til å
ta hensyn til det.

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

543
00:22:45,120 --> 00:22:48,720
Så nå ser vi på vår høyre side,
og vi ser på midten der borte,

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

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

546
00:22:55,510 --> 00:22:57,470
Større enn hva vi er
på jakt etter, ikke sant?

547
00:22:57,470 --> 00:22:59,860
Så vi kommer til å kaste
bort alt til høyre.

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

549
00:23:00,970 --> 00:23:01,940
Sånn.

550
00:23:01,940 --> 00:23:03,700
Nå er alt vi igjen med er en.

551
00:23:03,700 --> 00:23:07,760
Så vi sjekke, er dette en hva
vi leter etter? det er.

552
00:23:07,760 --> 00:23:08,970
Vi fant det vi ønsket.

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

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

555
00:23:11,690 --> 00:23:12,550
Bilinear søk.

556
00:23:12,550 --> 00:23:15,740
>> Og hvis du legger merke til, vi
hadde sju innganger der.

557
00:23:15,740 --> 00:23:24,320
Det tok oss bare som tre ganger,
men hvis du gjør som en milliard,

558
00:23:24,320 --> 00:23:28,190
dere vet hvor mange skritt det ville
ta hvis vi hadde for fire milliarder ting?

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

560
00:23:29,940 --> 00:23:30,455
Eventuelle gjetninger?

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 skritt for å finne noe
i en fire milliarder

564
00:23:37,110 --> 00:23:39,650
elementsatsen på grunn av krefter to.

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

566
00:23:43,550 --> 00:23:50,430
>> Så ganske sprøtt hvordan du er fortsatt innenfor
som et relativt lite antall skritt

567
00:23:50,430 --> 00:23:52,650
å finne noe i
fire milliarder elementer.

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

569
00:23:55,730 --> 00:23:58,950
så dere kan faktisk
slags se hvordan dette fungerer.

570
00:23:58,950 --> 00:24:01,520
All right, så dere kan kode.

571
00:24:01,520 --> 00:24:04,100
Jeg kommer til å fortelle dere
snakke litt.

572
00:24:04,100 --> 00:24:07,970
Bli kjent med folk rundt deg, som er
hva noen ønsket fra forrige avsnitt.

573
00:24:07,970 --> 00:24:10,280
>> Så bli kjent med menneskene rundt deg.

574
00:24:10,280 --> 00:24:11,305
Snakk for en liten bit.

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

576
00:24:12,580 --> 00:24:15,730
Og alt jeg ønsker fra deg
Gutta er akkurat nå bare

577
00:24:15,730 --> 00:24:17,575
prøve å lage en skisse av 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 jeg ønsker fra dere er at du er
bare kommer til å fylle ut dette mens saken.

583
00:24:29,520 --> 00:24:32,170
Så jeg har satt disse øvre
og nedre grenser som

584
00:24:32,170 --> 00:24:35,250
representerer begynnelsen
og slutten av matrisen.

585
00:24:35,250 --> 00:24:40,440
Og du kommer til å faktisk
sløyfe gjennom og finne ut

586
00:24:40,440 --> 00:24:42,470
hva vi gjør innenfor dette mens loop.

587
00:24:42,470 --> 00:24:45,810
>> Så hvis du kan finne out-- jeg har
et hint det-- hva er de tilfeller

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

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

590
00:24:48,100 --> 00:24:51,560
Så hvis du ønsker å finne ut av
tilfeller vil vi pseudo de

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

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

593
00:24:55,330 --> 00:24:56,788
være litt enklere enn 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å mye kode,
faktisk, som er virkelig kult.

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ørbart]?

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
Det var noe
å finne i midten.

602
00:25:38,595 --> 00:25:39,552
>> STUDENT: Så vi kan bruke 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 må gjøre.

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

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

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

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 finne midten med koden?

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

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

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

614
00:25:58,500 --> 00:25:59,500
INSTRUKTØR: Så n på over 2.

615
00:25:59,500 --> 00:26:05,170
Så én ting å huske er at
øvre og nedre grenser endres.

616
00:26:05,170 --> 00:26:08,110
Vi holder constricting delen
av tabellen vi er ute etter å.

617
00:26:08,110 --> 00:26:11,970
Så n løpet av to vil bare fungere
for det første vi gjør.

618
00:26:11,970 --> 00:26:17,810
Så tar øvre og nedre hensyn,
hvordan kan vi få den midterste element?

619
00:26:17,810 --> 00:26:20,640
Fordi vi ønsker midten
mellom store og små, ikke sant?

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ørbart].

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

624
00:26:26,170 --> 00:26:28,080
>> INSTRUKTØR: Så vi har noen midten.

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

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

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

630
00:26:37,280 --> 00:26:38,560
Dere er på vei.

631
00:26:38,560 --> 00:26:41,400
Så nå som vi har vår
midten, hva vi ønsker å gjøre?

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

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

634
00:26:45,900 --> 00:26:47,734
Du trenger ikke å kode det.

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

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

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

638
00:27:00,310 --> 00:27:10,310
INSTRUKTØR: Så det er pluss fordi du er
finne gjennomsnittet mellom de to

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

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

641
00:27:11,890 --> 00:27:17,370
Så hvis du tenker på dem som slag
for å øke inn fra sidene,

642
00:27:17,370 --> 00:27:21,640
tenker på det som du nærmer deg
midten, vil du liker det.

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

644
00:27:27,150 --> 00:27:31,440
Når du legger dem sammen du
får 12, deler du med 2, er 6.

645
00:27:31,440 --> 00:27:33,726
>> Noen ganger er det vanskelig å
forklare hvorfor det fungerer,

646
00:27:33,726 --> 00:27:35,600
men hvis du jobber gjennom
et eksempel noen ganger,

647
00:27:35,600 --> 00:27:37,962
det vil hjelpe deg å finne ut om
det bør være pluss eller minus.

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

649
00:27:38,846 --> 00:27:40,830
>> STUDENT: [uhørbart]
nøyaktig i midten

650
00:27:40,830 --> 00:27:43,950
hvis de hadde en sak der
det er mye mindre tall

651
00:27:43,950 --> 00:27:45,860
og som en stort antall?

652
00:27:45,860 --> 00:27:49,750
>> INSTRUKTØR: Så alt du trenger
er den midterste av rekken.

653
00:27:49,750 --> 00:27:53,010
Så hvis du hadde en haug med små tall
og deretter en virkelig stort antall

654
00:27:53,010 --> 00:27:54,799
på slutten, spiller det ingen rolle.

655
00:27:54,799 --> 00:27:56,840
Alt som teller er at
de er sortert, du bare

656
00:27:56,840 --> 00:27:59,339
ønsker å se på midten av
matrisen fordi du er fortsatt

657
00:27:59,339 --> 00:28:00,700
slicing problemet i to.

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å nå som vi har
midten, hva skal vi gjøre nå?

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

662
00:28:07,150 --> 00:28:08,150
INSTRUKTØR: Den sammenligne.

663
00:28:08,150 --> 00:28:11,670
Så sammenligne midten 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 her oppe har vi
denne verdien vi ønsker her oppe.

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

668
00:28:22,012 --> 00:28:23,095
Husk dette er en matrise.

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

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

671
00:28:26,970 --> 00:28:29,785
Så vi ønsker å gjøre verdier av midten.

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

673
00:28:32,380 --> 00:28:35,650
Ikke glem om du vil
å sammenligne, dobbel likeverdige.

674
00:28:35,650 --> 00:28:38,250
Du gjør enkelt lik du er
bare kommer til å overføre den,

675
00:28:38,250 --> 00:28:41,090
og da, selvfølgelig, det er
kommer til å være den verdien du vil.

676
00:28:41,090 --> 00:28:42,300
Så ikke gjør det.

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

678
00:28:44,350 --> 00:28:46,460
er lik verdien vi ønsker.

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

680
00:28:47,749 --> 00:28:48,790
Ikke glem tannregulering.

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

682
00:28:50,520 --> 00:28:52,235
Dropbox bør gå unna.

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

684
00:28:54,140 --> 00:28:56,200
Så hva skal vi gjøre i dette tilfellet?

685
00:28:56,200 --> 00:28:59,360
Hvis det er hva vi ønsker å komme tilbake?

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

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

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

689
00:29:03,440 --> 00:29:05,314
>> INSTRUKTØR: Vel, vi
ikke ønsker å skrive ut.

690
00:29:05,314 --> 00:29:08,220
Så dette er en bool her, så vi
ønsker å returnere sant eller usant.

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

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

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

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

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

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

697
00:29:20,805 --> 00:29:22,930
INSTRUKTØR: Så du kunne
returnere null hvis du ville.

698
00:29:22,930 --> 00:29:26,780
Men i dette tilfellet fordi
vår funksjon returnerer en bool,

699
00:29:26,780 --> 00:29:28,962
vi trenger å returnere enten sant eller usant.

700
00:29:28,962 --> 00:29:30,920
STUDENT: Når du er
sier boolsk uttrykk,

701
00:29:30,920 --> 00:29:33,450
kan du sette den lik falsk?

702
00:29:33,450 --> 00:29:39,860
Som hvis jeg ønsker å si, hvis denne tilstanden
ikke er oppfylt, som er øvre lik falsk.

703
00:29:39,860 --> 00:29:42,332
Vil det å forstå hvis du bare
sette falsk på den andre siden?

704
00:29:42,332 --> 00:29:43,040
INSTRUKTØR: Yeah.

705
00:29:43,040 --> 00:29:44,820
Så egentlig hvis du er
noen gang å gjøre noe

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

707
00:29:49,600 --> 00:29:53,850
og det er faktisk dårlig stil til
si lik lik sant eller equals

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

709
00:29:54,840 --> 00:30:00,210
Du ønsker å bruke dette resultatet
så seg selv som sjekken.

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

711
00:30:04,720 --> 00:30:05,860
Ikke hva jeg ønsket.

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

713
00:30:08,150 --> 00:30:09,240
Det var det jeg ønsket.

714
00:30:09,240 --> 00:30:13,205
Så i tilfelle du spør
om noe sånt lagre dette 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 noe sånt som dette.

717
00:30:25,150 --> 00:30:31,922
Og du har hvis er øvre
av noen innspill, og du er

718
00:30:31,922 --> 00:30:33,630
spør om du kan gjøre
noe sånt som dette?

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

720
00:30:35,010 --> 00:30:35,679
Høyre?

721
00:30:35,679 --> 00:30:37,470
STUDENT: Jeg prøvde
å gjøre det [uhørbart].

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

723
00:30:38,450 --> 00:30:39,200
INSTRUKTØR: Høyre.

724
00:30:39,200 --> 00:30:41,197
Så du vil at dette skal være falske, ikke sant?

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

726
00:30:41,780 --> 00:30:45,960
INSTRUKTØR: Så i dette tilfellet deg
vil den skal kjøre hvis det ikke er sant.

727
00:30:45,960 --> 00:30:50,510
Så kule ting du gjør det er dette.

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

729
00:30:52,900 --> 00:30:55,650
Så husk utrops
punkt benekter ting?

730
00:30:55,650 --> 00:30:58,270
Det står [uhørbart] betyr ikke.

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

732
00:31:03,590 --> 00:31:05,740
si at evalueres til
falsk som du vil ha det til.

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

734
00:31:06,790 --> 00:31:09,880
Ikke falske er sant som
betyr dette ville utføre.

735
00:31:09,880 --> 00:31:11,037
Betyr det fornuftig?

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

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å vi kunne bare gå tilbake
sant i dette tilfellet.

741
00:31:16,330 --> 00:31:20,357
Så nå har vi to andre
tilfeller i dette tilfellet.

742
00:31:20,357 --> 00:31:21,565
Hva er våre to andre saker?

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

744
00:31:31,610 --> 00:31:32,900
La oss bare gjøre det på denne måten.

745
00:31:32,900 --> 00:31:40,660
Så la oss starte med annet
hvis verdier ved midten

746
00:31:40,660 --> 00:31:43,230
er mindre enn verdien vi ønsker.

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

748
00:31:47,200 --> 00:31:52,020
Så vår verdi i midten er mindre
enn verdien som vi leter etter.

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

750
00:31:53,765 --> 00:31:56,720
>> Så hvilke bundet gjør du
tror vi vil oppdatere?

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

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

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

754
00:32:01,440 --> 00:32:01,940
Øvre?

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

756
00:32:03,230 --> 00:32:06,470
Så hvilken side av matrisen
skal vi se på?

757
00:32:06,470 --> 00:32:07,500
>> STUDENT: Den nedre.

758
00:32:07,500 --> 00:32:09,750
>> INSTRUKTØR: Vi skal vi
å være ute på venstre.

759
00:32:09,750 --> 00:32:11,120
Så annet hvis liten verdi er mindre.

760
00:32:11,120 --> 00:32:14,730
Så din midterste verdien her
er mindre enn det vi ønsker.

761
00:32:14,730 --> 00:32:17,202
Så vi ønsker å ta
høyre side av vår array.

762
00:32:17,202 --> 00:32:18,910
Så vi kommer til å
oppdatere vår nedre grense.

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

764
00:32:20,210 --> 00:32:23,020
Så vi vil tildele våre lavere.

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

766
00:32:25,221 --> 00:32:26,304
STUDENT: Den midterste verdien?

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

768
00:32:27,446 --> 00:32:28,820
INSTRUKTØR: Så midt value--

769
00:32:28,820 --> 00:32:30,136
STUDENT: Pluss en.

770
00:32:30,136 --> 00:32:31,010
INSTRUKTØR: --plus en.

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

772
00:32:32,300 --> 00:32:34,380
Kan noen fortelle meg hvorfor
har vi at pluss 1?

773
00:32:34,380 --> 00:32:35,730
>> STUDENT: [? Ingen verdi?]
er mer lik det.

774
00:32:35,730 --> 00:32:36,120
>> INSTRUKTØR: Høyre.

775
00:32:36,120 --> 00:32:38,661
Fordi vi allerede vet at
vår midterste verdien er ikke lik

776
00:32:38,661 --> 00:32:42,750
det, og vi ønsker å utelukke det
fra alle senere søk.

777
00:32:42,750 --> 00:32:46,360
Hvis du glemmer at pluss 1, dette
vil gjerne sløyfe på ubestemt tid.

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

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

780
00:32:50,370 --> 00:32:54,780
Så alltid sørge for at du ikke er
inkludert verdien som du bare

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

782
00:32:55,380 --> 00:32:58,530
Så vi tar vare på det med en pluss en.

783
00:32:58,530 --> 00:33:04,840
>> Så nå har vi vår siste vilkåret
som jeg alltid for sikkerhets skyld

784
00:33:04,840 --> 00:33:12,664
du kan sjekke her, annet hvis verdien på
midten er større enn verdien

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 betyr at vi ønsker
den venstre halvdel.

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

789
00:33:21,350 --> 00:33:23,260
Så hvilken skal vi oppdatere?

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 hva er dette som kommer til å like?

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

794
00:33:31,630 --> 00:33:33,690
Middle minus en grunn,
selvfølgelig, vi ønsker

795
00:33:33,690 --> 00:33:38,370
å sørge for at vi ikke er
ser på det midterste verdien på nytt.

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 var det.

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

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

801
00:33:48,190 --> 00:33:51,590
Det er som 10 linjer
kode med hvite felt.

802
00:33:51,590 --> 00:33:57,510
Så veldig kraftig, veldig nyttig, vil du
være å bruke det i en av dine senere psets.

803
00:33:57,510 --> 00:33:59,360
Kanskje ikke denne, 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 deg godt.

807
00:34:02,980 --> 00:34:05,370
Så er det noen som har noen
spørsmål om binære søk?

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

809
00:34:06,196 --> 00:34:09,840
>> STUDENT: Spiller det noen rolle
om din n er partall eller oddetall?

810
00:34:09,840 --> 00:34:10,750
>> INSTRUKTØR: Nei.

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

812
00:34:18,150 --> 00:34:21,600
Så det vil bli et heltall og det vil
slutt sortere gjennom alt.

813
00:34:21,600 --> 00:34:23,909
Så du trenger ikke å bekymre deg for det.

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

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å, fikk dere dette.

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
Lysbildefremvisning.

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
Så som vi snakket om, jeg vet
David nevnte kompleksitet runtimes.

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

824
00:34:44,420 --> 00:34:50,340
>> Så i beste fall, det er bare
en, som vi kaller konstant tid.

825
00:34:50,340 --> 00:34:51,909
Kan noen fortelle meg hvorfor det kan være?

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

827
00:34:52,969 --> 00:34:55,800
Hvilken type scenario ville det innebæ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ørbart] first--

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

832
00:35:00,789 --> 00:35:03,830
INSTRUKTØR: Så midten blir
første elementet som vi kommer til, ikke sant?

833
00:35:03,830 --> 00:35:08,167
Slik at enten en oppstilling av ett eller
uansett hva vi leter etter akkurat

834
00:35:08,167 --> 00:35:09,750
skjer for å være smellkyss dab i midten.

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

836
00:35:11,190 --> 00:35:13,380
Så det er vårt beste fall.

837
00:35:13,380 --> 00:35:17,540
Du kommer inn i reelle problemer, sannsynligvis ikke
kommer til å nå [uhørbart] som ofte.

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

839
00:35:18,667 --> 00:35:19,750
Hva om vår verste fall?

840
00:35:19,750 --> 00:35:21,270
Vår verste fall er log n.

841
00:35:21,270 --> 00:35:25,360
Og det har å gjøre med hele
krefter på to ting som jeg snakket om.

842
00:35:25,360 --> 00:35:30,930
>> Så i verste fall ville det bety
at vi måtte hogge array ned

843
00:35:30,930 --> 00:35:33,270
inntil det var et element av en.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Så vi måtte hogge det ned i halvparten
så mange ganger som vi muligens 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å forutsetninger, ting dere
trenger å vite hvis du noen gang

849
00:35:45,830 --> 00:35:48,050
kommer til å bruke et binært søk.

850
00:35:48,050 --> 00:35:50,680
Dine elementene skal sorteres.

851
00:35:50,680 --> 00:35:53,890
De må sorteres fordi
det er den eneste måten du

852
00:35:53,890 --> 00:35:57,060
kan vite om du er i stand
å kaste ut halvparten av det.

853
00:35:57,060 --> 00:36:00,260
>> Hvis du hadde denne jumbled bag
av tall og du sier,

854
00:36:00,260 --> 00:36:05,380
OK, jeg kommer til å sjekke midten
tall og antall jeg leter etter

855
00:36:05,380 --> 00:36:08,510
er mindre enn det, jeg bare går
å vilkårlig kaste ut den ene halvdelen.

856
00:36:08,510 --> 00:36:11,130
Du ville ikke vite om din
Tallene i den annen halvdel.

857
00:36:11,130 --> 00:36:12,655
Din liste som skal sorteres.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
I tillegg, kan dette være
går videre litt,

860
00:36:16,560 --> 00:36:18,360
men du må ha random access.

861
00:36:18,360 --> 00:36:21,940
Du må være i stand til å bare
gå til det midterste element.

862
00:36:21,940 --> 00:36:25,110
Hvis du har å traversere
gjennom noe

863
00:36:25,110 --> 00:36:28,630
eller det tar deg ekstra trinn
å komme til det midterste element,

864
00:36:28,630 --> 00:36:31,750
det er ikke log n lenger fordi
du legger mer arbeid i det.

865
00:36:31,750 --> 00:36:34,800
Og dette vil gjøre litt
mer fornuftig i to uker,

866
00:36:34,800 --> 00:36:37,950
men jeg bare slags ønsket å forord,
gi dere en idé om hva som er

867
00:36:37,950 --> 00:36:38,999
å komme.

868
00:36:38,999 --> 00:36:40,790
Men de er de to
viktige forutsetninger

869
00:36:40,790 --> 00:36:44,804
at du trenger for en binær liste.

870
00:36:44,804 --> 00:36:45,720
Sørg for at det er sortert.

871
00:36:45,720 --> 00:36:47,920
Det er den store en for
dere akkurat nå.

872
00:36:47,920 --> 00:36:52,170
Og på at vi kan gå inn
resten av våre former.

873
00:36:52,170 --> 00:36:56,444
Så fire sorts-- boble,
innsetting, utvelgelse, og flette.

874
00:36:56,444 --> 00:36:57,485
De er alle slags kule.

875
00:36:57,485 --> 00:37:02,860
Hvis dere velger å ta CS 124,
du vil lære om alle slags former.

876
00:37:02,860 --> 00:37:07,575
Og hvis du er en XKCD fan, det
er en veldig kul tegneserie om

877
00:37:07,575 --> 00:37:11,530
som virkelig ineffektive slag, som jeg
anbefaler deg å gå å se på.

878
00:37:11,530 --> 00:37:16,170
En av dem er som panikk slag, som
er like, oh no, tilbake tilfeldig utvalg.

879
00:37:16,170 --> 00:37:16,991
Shutdown system.

880
00:37:16,991 --> 00:37:17,490
Forlate.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Så nerdete humor er alltid bra.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Så er det noen som husker slag
av som bare en generell idé

885
00:37:25,750 --> 00:37:27,810
av hvordan boble slags fungerer.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Husker du?

888
00:37:32,155 --> 00:37:32,755
>> STUDENT: Yeah.

889
00:37:32,755 --> 00:37:33,970
>> INSTRUKTØR: Gå for det.

890
00:37:33,970 --> 00:37:38,980
>> STUDENT: Så du kommer gjennom og
hvis det er større, så du bytte de to.

891
00:37:38,980 --> 00:37:39,820
>> INSTRUKTØR: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Nettopp.

893
00:37:40,564 --> 00:37:41,730
Så du bare iterere gjennom.

894
00:37:41,730 --> 00:37:43,050
Du sjekker to tall.

895
00:37:43,050 --> 00:37:46,510
Dersom en før er større
enn den etterpå,

896
00:37:46,510 --> 00:37:50,230
du bare bytte dem slik at i
denne måten alle de høyere tall

897
00:37:50,230 --> 00:37:54,990
boble opp mot slutten av listen
og alle lavere tall boble ned.

898
00:37:54,990 --> 00:37:59,355
>> Har han vise dere den kule
lydeffekt sortering video?

899
00:37:59,355 --> 00:38:00,480
Det er litt kult.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Så som Robert sa, algoritmen
at du bare gå gjennom listen,

902
00:38:05,200 --> 00:38:07,930
bytte tilstøtende verdier
hvis de ikke er i orden.

903
00:38:07,930 --> 00:38:10,975
Og så bare terpe
til du ikke gjør noen bytteavtaler.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Så ikke dårlig, ikke sant?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Så vi har bare en rask eksempel her.

908
00:38:16,319 --> 00:38:18,360
Så dette kommer til å sortere
dem i stigende rekkefø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 gjennom det første
tid, ser vi gjennom åtte

911
00:38:23,470 --> 00:38:26,880
og seks er åpenbart ikke
i orden, bytte vi dem.

912
00:38:26,880 --> 00:38:27,985
>> Så se på den neste.

913
00:38:27,985 --> 00:38:29,430
Åtte 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 da åtte og to, bytte dem.

916
00:38:32,530 --> 00:38:33,470
Det vi går.

917
00:38:33,470 --> 00:38:39,519
Så etter din første pass, du
vet at din største antall

918
00:38:39,519 --> 00:38:41,810
kommer til å være hele veien
på toppen fordi det er bare

919
00:38:41,810 --> 00:38:44,210
kommer til å være konstant
større enn alt annet

920
00:38:44,210 --> 00:38:46,810
og det er bare kommer til å boble
opp hele veien til enden der.

921
00:38:46,810 --> 00:38:48,226
Betyr det er fornuftig 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å da vi ser på vår andre pass.

926
00:38:53,920 --> 00:38:54,980
Seks og fire, bryter.

927
00:38:54,980 --> 00:38:55,920
Seks og to, bryter.

928
00:38:55,920 --> 00:38:58,700
Og nå har vi noen få ting i orden.

929
00:38:58,700 --> 00:39:02,240
Så for hver pass som vi
gjør gjennom hele vår liste,

930
00:39:02,240 --> 00:39:06,320
vi vet at sånn mange tall
på slutten vil ha blitt sortert.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Så vi gjør en tredje pass,
som er en swap.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
Og så på vår fjerde
pass, vi har null spor.

935
00:39:15,910 --> 00:39:18,570
Og så vet vi at vår
matrise er blitt sortert.

936
00:39:18,570 --> 00:39:20,900
>> Og det er den store
ting med boble slag.

937
00:39:20,900 --> 00:39:23,720
Vi vet at når vi
har null bytteavtaler, som

938
00:39:23,720 --> 00:39:26,497
betyr at alt
er i fullstendig orden.

939
00:39:26,497 --> 00:39:27,580
Det er slags hvordan vi sjekke.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Så skal vi også å kode boble
sorter som også er ikke så ille.

942
00:39:36,480 --> 00:39:38,120
Ingen av disse er så ille.

943
00:39:38,120 --> 00:39:40,210
Jeg vet at de kan virke litt skremmende.

944
00:39:40,210 --> 00:39:42,124
Jeg vet når jeg tok
klassen, selv når jeg

945
00:39:42,124 --> 00:39:44,290
underviste klassen for
første gang i fjor,

946
00:39:44,290 --> 00:39:46,165
Jeg var ut, hvordan gjør jeg dette?

947
00:39:46,165 --> 00:39:48,540
Det er fornuftig i teorien, men
hvordan gjør vi faktisk gjøre dette?

948
00:39:48,540 --> 00:39:51,420
Det er derfor jeg ønsker også å gå
gjennom koden med dere her.

949
00:39:51,420 --> 00:39:54,915
Så jeg har en pseudokode
for dere denne gangen.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Så bare ha dette i bakhodet når
vi er i ferd med å overgang over.

952
00:39:58,970 --> 00:40:04,210
Så vi har noen teller som
holder orden på våre bytteavtaler,

953
00:40:04,210 --> 00:40:08,370
fordi vi må sørge for
at vi sjekker det.

954
00:40:08,370 --> 00:40:11,830
Og vi iterere hele matrisen
som vi nettopp gjorde med dette eksempelet.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Hvis elementet er større enn før
elementet etter hvor vi er,

957
00:40:17,325 --> 00:40:20,760
vi bytte dem, og vi øke vår
teller fordi så snart vi bytte,

958
00:40:20,760 --> 00:40:23,850
vi ønsker å la vår teller vet det.

959
00:40:23,850 --> 00:40:26,247
Eventuelle spørsmål der ute?

960
00:40:26,247 --> 00:40:27,580
Noe virker morsomt her borte.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
STUDENT: du setter Må telleren til null
hver gang du går gjennom løkken?

963
00:40:32,350 --> 00:40:34,339
Tror ikke du holde det gående
tilbake til null 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å hva skjer er at vi går gjennom her.

966
00:40:39,710 --> 00:40:43,830
Så gjør stund, husk, dette
vil kjøre en gang uten å lykkes.

967
00:40:43,830 --> 00:40:46,480
Så det kommer til å sette
telleren er lik null,

968
00:40:46,480 --> 00:40:48,070
så det kommer til å iterere gjennom.

969
00:40:48,070 --> 00:40:50,590
Som det gjentas gjennom,
det vil oppdatere telleren.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Som den oppdaterer teller, når det er gjort,
når den er kommet til slutten av tabellen,

972
00:40:56,900 --> 00:41:00,830
hvis vår liste ikke er sortert,
telleren vil ha blitt oppdatert.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Så da er det kontrollerer tilstanden og det
sier, OK, er telleren større enn null.

975
00:41:07,150 --> 00:41:09,290
Hvis det er, gjør det igjen.

976
00:41:09,290 --> 00:41:14,340
Du ønsker å tilbakestille slik at når du
går gjennom, er telleren er lik null.

977
00:41:14,340 --> 00:41:18,240
Hvis du går gjennom en sortert
array, endrer ingenting,

978
00:41:18,240 --> 00:41:21,355
dette mislykkes, og du
returnere sortert liste.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Betyr det fornuftig?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
STUDENT: Det er kanskje i en liten bit.

983
00:41:26,356 --> 00:41:27,147
INSTRUKTØR: OK.

984
00:41:27,147 --> 00:41:28,980
Hvis det er noen andre
spørsmål som kommer opp.

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: Hva ville funksjonen
være for å bytte elementene?

988
00:41:33,760 --> 00:41:36,900
>> INSTRUKTØR: Så vi kan faktisk skrive
at hvis vi kommer til akkurat nå.

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 notatet, er Alison kommer
å bytte tilbake til apparatet.

992
00:41:42,155 --> 00:41:43,080
Det kommer til å bli gøy.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
Og vi har våre fint
boble slags ting her.

995
00:41:47,390 --> 00:41:50,800
Så jeg allerede gjorde sykling
gjennom matrisen.

996
00:41:50,800 --> 00:41:53,030
Vi har våre bytteavtaler som
er lik null.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Så vi ønsker å bytte tilstøtende
elementer hvis de er ute av drift.

999
00:41:58,440 --> 00:42:03,020
Så det første vi må
gjør er iterere gjennom vårt utvalg.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Så hvordan tror du vi kan
iterere gjennom vårt utvalg?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Vi har for og jeg er lik 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Vi ønsker jeg å være mindre
enn n minus 1 minus k.

1006
00:42:22,454 --> 00:42:23,870
Og jeg skal forklare det i et sekund.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Så dette er en optimalisering her hvor,
husker hvordan jeg sa etter hvert pass

1009
00:42:32,830 --> 00:42:36,655
gjennom rekke vi
vet at uansett hva som er on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Så etter en pasning vi
vet at dette er sortert.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Etter to passerer vi vet
at alt dette er sortert.

1014
00:42:50,060 --> 00:42:52,750
Etter tre passerer vi
vet det er sortert.

1015
00:42:52,750 --> 00:42:55,620
Så måten jeg itera
gjennom rekke her,

1016
00:42:55,620 --> 00:43:01,090
er det å sørge for å bare gå
gjennom det vi vet er usortert.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
Det er bare en optimalisering.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Du kan skrive det naivt bare
itera gjennom alt,

1021
00:43:08,210 --> 00:43:09,970
det ville bare ta lengre tid.

1022
00:43:09,970 --> 00:43:12,470
Med denne fire sløyfe er det
bare en fin optimalisering

1023
00:43:12,470 --> 00:43:18,460
fordi vi vet at etter hver hele
iterasjon gjennom rekke her,

1024
00:43:18,460 --> 00:43:24,050
som hver hele sløyfe her, vi vet
at ett eller flere av disse elementene

1025
00:43:24,050 --> 00:43:25,760
blir sortert ved enden.

1026
00:43:25,760 --> 00:43:28,294
>> Så vi ikke trenger å bekymre deg om dem.

1027
00:43:28,294 --> 00:43:29,710
Betyr det er fornuftig for alle?

1028
00:43:29,710 --> 00:43:30,950
Den kule lille trikset?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Så i så fall, hvis
vi gjentar gjennom,

1031
00:43:37,270 --> 00:43:50,590
vi vet at vi ønsker å sjekke om
matrise n og n + 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 å sjekke om matrise n
og n pluss en er i orden.

1036
00:43:57,540 --> 00:43:59,520
Så hva kan vi ha det?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
Det kommer til å være noen betinget.

1039
00:44:03,120 --> 00:44:04,220
Det vil være en if.

1040
00:44:04,220 --> 00:44:07,066
>> STUDENT: Hvis matrise n er
mindre enn matrise n pluss 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
Vel, mindre enn eller større enn.

1044
00:44:10,699 --> 00:44:11,615
STUDENT: Større enn.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Så vi ønsker å bytte dem.

1047
00:44:17,620 --> 00:44:18,570
Nettopp.

1048
00:44:18,570 --> 00:44:23,570
Så nå får vi inn hva som er den
mekanisme for å bytte dem?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Så vi gikk gjennom dette kort,
en type swap-funksjonen i forrige uke.

1051
00:44:28,137 --> 00:44:29,595
Er det noen som husker hvordan det fungerte?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Så vi kan ikke bare overføre dem, ikke sant?

1054
00:44:34,950 --> 00:44:36,640
Fordi en av dem vil gå tapt.

1055
00:44:36,640 --> 00:44:41,696
Hvis vi nevnte A er lik B og deretter B
er lik A, alle en plutselig begge

1056
00:44:41,696 --> 00:44:43,150
er bare lik B.

1057
00:44:43,150 --> 00:44:45,720
>> Så det vi trenger å gjøre er vi
har en midlertidig variabel som er

1058
00:44:45,720 --> 00:44:49,055
kommer til å holde en av våre mens
vi er i ferd med å bytte.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Så det vi har er vi vil ha noen int
temp er lik to-- du kan tilordne den

1061
00:44:56,464 --> 00:44:59,130
til hvilken du vil ha, bare
Sørg for å holde styr på it--

1062
00:44:59,130 --> 00:45:01,840
så i dette tilfellet, kommer jeg til å
tilordne den til matrise n pluss 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Så det kommer til å holde uansett
verdien er i den andre blokken

1065
00:45:07,674 --> 00:45:08,590
at vi ser på.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> Og da kan vi gjøre er at vi kan gå
videre og Ny tilordning matrise n pluss 1,

1068
00:45:13,240 --> 00:45:14,990
fordi vi vet at vi
har denne verdien lagret.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Dette er også en av de store
things-- Jeg vet ikke om noen av dere

1071
00:45:19,270 --> 00:45:23,780
hadde problemer der hvis du slår to
linjer med kode plutselig ting fungerte.

1072
00:45:23,780 --> 00:45:25,880
Rekkefølgen er svært viktig i CS.

1073
00:45:25,880 --> 00:45:29,450
Så sørg for at du diagram
ting ut hvis mulig

1074
00:45:29,450 --> 00:45:31,230
med hensyn til hva som faktisk skjer.

1075
00:45:31,230 --> 00:45:34,256
Så nå skal vi
tilordne matrise n pluss 1,

1076
00:45:34,256 --> 00:45:36,005
fordi vi vet at vi
har denne verdien lagret.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> Og vi kan tildele det til matrise
n eller i dette tilfellet i matrisen.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
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å nå har vi overført matrise i
pluss en til lik hva som er i matrisen i.

1084
00:46:01,500 --> 00:46:08,240
Og nå kan vi gå tilbake og
tildele utvalg i til hva?

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

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
Og en siste ting.

1093
00:46:18,640 --> 00:46:21,840
Hvis vi har byttet den nå,
hva trenger vi å gjøre?

1094
00:46:21,840 --> 00:46:23,740
Hva er den ene tingen
som kommer til å fortelle oss

1095
00:46:23,740 --> 00:46:27,542
hvis vi noen gang avslutte dette programmet?

1096
00:46:27,542 --> 00:46:29,250
Hva forteller oss at vi
ha en sortert liste?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Hvis vi ikke utfører noen bytteavtaler, ikke sant?

1099
00:46:33,750 --> 00:46:36,900
Hvis swaps er lik
null ved slutten av denne.

1100
00:46:36,900 --> 00:46:42,975
Så når du utfører en swap, som vi
nettopp gjorde her, vi ønsker å oppdatere bytteavtaler.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
Og jeg vet at det var en
spørsmålet tidligere om kan du

1103
00:46:47,210 --> 00:46:49,689
bruke null eller ett i stedet
av sant eller usant.

1104
00:46:49,689 --> 00:46:50,980
Og det er hva dette gjør her.

1105
00:46:50,980 --> 00:46:52,750
Så dette sier om ikke bytteavtaler.

1106
00:46:52,750 --> 00:47:01,310
Så hvis swaps er null, som er-- jeg alltid
få mine sannheter og mine misoppfatter blandet sammen.

1107
00:47:01,310 --> 00:47:03,960
Vi ønsker oss å evaluere
til sann, 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 null, så er det usant.

1110
00:47:09,630 --> 00:47:12,560
Hvis du benekter det med en
[? bang?] blir det sant.

1111
00:47:12,560 --> 00:47:13,975
Så da denne linjen utfører.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Sannheter og falske og
nuller og enere bli gal.

1114
00:47:17,370 --> 00:47:20,690
Bare hvis du sakte gå
gjennom det vil det være fornuftig.

1115
00:47:20,690 --> 00:47:23,320
Men det er hva denne lille
bit av koden her gjør.

1116
00:47:23,320 --> 00:47:26,490
Så dette sjekker for å se
har vi gjort noen bytteavtaler.

1117
00:47:26,490 --> 00:47:30,054
Så hvis det er noe i tillegg
null, kommer det til å være falsk

1118
00:47:30,054 --> 00:47:31,970
og det hele er
kommer til å kjøre igjen.

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: Hva gjør pause?

1123
00:47:36,000 --> 00:47:38,990
>> INSTRUKTØR: bryte bare
bryter deg ut av loopen.

1124
00:47:38,990 --> 00:47:41,570
Så i dette tilfellet ville det
akkurat som avslutter programmet

1125
00:47:41,570 --> 00:47:43,828
og du ville bare
har din sortert 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 beklager?

1129
00:47:49,010 --> 00:47:52,110
STUDENT: Fordi vi tidligere
brukt skrevet 1 over skrevet null

1130
00:47:52,110 --> 00:47:54,170
å presentere at hvis
som vil fungere eller ikke.

1131
00:47:54,170 --> 00:47:54,878
>> INSTRUKTØR: Yeah.

1132
00:47:54,878 --> 00:47:56,410
Så du kan returnere null eller 1.

1133
00:47:56,410 --> 00:47:58,950
I dette tilfellet, fordi vi er faktisk ikke
gjør noe med funksjonen,

1134
00:47:58,950 --> 00:48:00,150
vi ønsker bare det å bryte.

1135
00:48:00,150 --> 00:48:02,680
Vi har egentlig ikke bryr seg om det.

1136
00:48:02,680 --> 00:48:06,960
Bremsen er også bra hvis
det er brukt for å bryte ut

1137
00:48:06,960 --> 00:48:10,710
av fire sløyfer eller tilstander som
trenger du ikke ønsker å beholde utføring.

1138
00:48:10,710 --> 00:48:12,110
Det tar deg bare ut av dem.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Det er litt av en nyanse ting.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Jeg føler at det er
mye hand waving,

1143
00:48:18,445 --> 00:48:19,740
som du vil lære om dette snart.

1144
00:48:19,740 --> 00:48:20,955
>> Men du vil lære mer 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å gjør alle får boble liksom?

1149
00:48:24,840 --> 00:48:25,550
Ikke så ille.

1150
00:48:25,550 --> 00:48:31,910
Iterere gjennom, bytte ting ved hjelp av en
temp variabel, og vi er alle satt 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
Tilbake til PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Eventuelle spørsmål generelt
om disse så langt?

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ørbart] int main vanligvis.

1162
00:48:45,279 --> 00:48:46,695
Må du ha det for dette?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> INSTRUKTØR: Så vi var bare ute
bare på selve sorteringsalgoritmen.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Hvis du hadde det i løpet av
som et større program,

1167
00:48:56,350 --> 00:48:57,891
du ville ha en int main et sted.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
Avhengig av hvor du
bruker denne algoritmen,

1170
00:49:02,880 --> 00:49:05,860
det ville bestemme hva som er
blir returnert av den.

1171
00:49:05,860 --> 00:49:09,960
Men for vår sak, vi er strengt
å se på hvordan dette faktisk

1172
00:49:09,960 --> 00:49:11,300
iterere gjennom en matrise.

1173
00:49:11,300 --> 00:49:12,570
Så vi trenger ikke bekymre deg om det.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Så vi snakket om best case og
worst case scenarier for binære søk.

1176
00:49:19,830 --> 00:49:22,470
Så det er også viktig å gjøre
at for hver av våre former.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Så hva tror du er den verste
case runtime boble liksom?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Husker dere?

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 betyr at det er
n minus 1 sammenligninger.

1184
00:49:35,070 --> 00:49:40,060
Så en ting å innse er
at på den første iterasjon,

1185
00:49:40,060 --> 00:49:43,360
vi går gjennom, sammenligner vi
disse two-- så det er en.

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å etter en iterasjon vi
allerede har fire sammenligninger.

1189
00:49:55,050 --> 00:49:58,230
Når jeg snakker om runtime og n.

1190
00:49:58,230 --> 00:50:04,680
N representerer antallet sammenligninger
som en funksjon av 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 gjennom, har vi fire.

1194
00:50:08,860 --> 00:50:11,780
Neste gang du vet at vi ikke gjør det
nødt til å ta vare på 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 har den optimalisering
med de fire loop som jeg skrev,

1197
00:50:20,050 --> 00:50:22,750
du ville være å sammenligne her anyways.

1198
00:50:22,750 --> 00:50:26,170
Så du ville ha til å
kjøres gjennom matrisen

1199
00:50:26,170 --> 00:50:34,380
og gjøre n sammenligninger n
ganger, fordi hver gang vi

1200
00:50:34,380 --> 00:50:36,670
kjøre gjennom det vi liksom en ting.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> Og hver gang vi kjører gjennom
rekken, gjør vi n sammenligninger.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Så vår runtime for dette er
faktisk n squared, som

1205
00:50:46,330 --> 00:50:48,400
er mye verre i vår
logge slutten fordi at

1206
00:50:48,400 --> 00:50:51,965
betyr at hvis vi hadde fire
milliarder elementer, er det

1207
00:50:51,965 --> 00:50:55,260
kommer til å ta oss fire milliarder
squared i stedet for 32.

1208
00:50:55,260 --> 00:51:01,240
Så ikke den beste runtime,
men for noen ting,

1209
00:51:01,240 --> 00:51:04,610
du vet, hvis du er innenfor
et visst utvalg av elementer

1210
00:51:04,610 --> 00:51:06,540
boble slags kan være greit å bruke.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Så nå hva som er den beste fall 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: Så en ville
være en sammenligning.

1217
00:51:18,140 --> 00:51:19,114
Høyre.

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 konsept som n
minus 1, har vi en tendens til å bare slippe den av

1223
00:51:26,510 --> 00:51:31,680
og vi bare si n fordi du har
å sammenligne hver av these-- hvert par.

1224
00:51:31,680 --> 00:51:36,470
Derfor ville det være n minus en, som vi
Vi ville bare si er omtrent n.

1225
00:51:36,470 --> 00:51:39,280
Når du arbeider med runtime,
alt er i tilnærmet.

1226
00:51:39,280 --> 00:51:43,860
Så lenge eksponenten er
riktig, er du ganske bra.

1227
00:51:43,860 --> 00:51:45,700
>> Det er hvordan vi forholder oss til det.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Slik at den beste fall er n, som
betyr at listen er allerede sorteres,

1230
00:51:51,780 --> 00:51:54,320
og alt vi gjør er å kjøre gjennom
og sjekk at det er sortert.

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 ser her, vi
bare ha noen flere grafer.

1236
00:52:01,920 --> 00:52:02,660
Så n squared.

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
Mye verre enn n som vi ser, og
mye, mye verre enn log 2n.

1240
00:52:09,730 --> 00:52:12,060
Og da får du også inn logg logger.

1241
00:52:12,060 --> 00:52:18,020
Og du tar 124, få deg inn
som log stjernen, som er like crazy.

1242
00:52:18,020 --> 00:52:20,172
Så hvis du er interessert,
lookup log stjerne.

1243
00:52:20,172 --> 00:52:20,880
Det er litt moro.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Så har vi dette flotte diagrammet.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Bare en heads up, dette er en
fantastisk diagrammet for å ha

1248
00:52:28,720 --> 00:52:31,350
for mid-term fordi vi
lang tid å spørre deg disse tynner.

1249
00:52:31,350 --> 00:52:36,090
Så bare en heads up, har dette på din
mid-term på fin jukselapp

1250
00:52:36,090 --> 00:52:36,616
der.

1251
00:52:36,616 --> 00:52:37,990
Så vi bare så på boble slag.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
Verste tilfelle, n kvadrert, beste fall, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
Og vi kommer til å se på de andre.

1256
00:52:44,950 --> 00:52:47,940
>> Og som du kan se, den eneste
en som virkelig gjør det bra

1257
00:52:47,940 --> 00:52:50,910
er merge sort, som vi skal komme inn på hvorfor.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Så vi kommer til å gå til
neste her-- utvalg slag.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Er det noen som husker hvordan
utvalget slags jobbet?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Gå for det.

1264
00:53:05,700 --> 00:53:08,210
>> STUDENT: I ​​utgangspunktet gå gjennom
en ordre og opprette en ny liste.

1265
00:53:08,210 --> 00:53:11,001
Og akkurat som du setter elementer
inn, sette dem på rett 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: Slik at lydene
mer som innsetting slag.

1268
00:53:14,040 --> 00:53:15,040
Men du er veldig nære.

1269
00:53:15,040 --> 00:53:15,915
De er svært like.

1270
00:53:15,915 --> 00:53:17,440
Selv jeg får dem blandet opp noen ganger.

1271
00:53:17,440 --> 00:53:18,981
Før denne delen jeg var som, 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å hva du vil
gjøre er utvalget sortere,

1275
00:53:24,141 --> 00:53:25,890
måten du kan tenke
om det og hvordan

1276
00:53:25,890 --> 00:53:30,140
Jeg sørge for at jeg prøver ikke å få
dem blandet opp, er den går gjennom

1277
00:53:30,140 --> 00:53:33,280
og det velges
minste tallet og det

1278
00:53:33,280 --> 00:53:36,070
setter at i begynnelsen av listen.

1279
00:53:36,070 --> 00:53:37,730
Den bytter den med det første spot.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
De har faktisk et forbilde for meg.

1282
00:53:45,370 --> 00:53:46,540
Awesome.

1283
00:53:46,540 --> 00:53:50,130
Så bare en måte å tenke på it-- utvalg
sortere, velge den minste verdien.

1284
00:53:50,130 --> 00:53:51,940
Og vi kommer til å
kjøres gjennom et eksempel

1285
00:53:51,940 --> 00:53:55,320
som jeg tror vil hjelpe fordi
Jeg tror visuelle alltid hjelpe.

1286
00:53:55,320 --> 00:53:58,510
Så vi starter ut med noe
som er helt usortert.

1287
00:53:58,510 --> 00:54:00,730
Red vil være usortert,
green vil bli sortert.

1288
00:54:00,730 --> 00:54:02,190
Det vil alle være fornuftig i et sekund.

1289
00:54:02,190 --> 00:54:08,950
>> Så vi går gjennom, og vi iterere
fra begynnelsen til slutten.

1290
00:54:08,950 --> 00:54:12,320
Og vi sier, OK, er to
vår minste tallet.

1291
00:54:12,320 --> 00:54:15,680
Så vi kommer til å ta to og vi kommer
å flytte den til forsiden av vår matrise

1292
00:54:15,680 --> 00:54:17,734
fordi det er den
minste tallet vi har.

1293
00:54:17,734 --> 00:54:19,150
Så det er hva dette gjør her.

1294
00:54:19,150 --> 00:54:20,820
Det er bare kommer til å bytte de to.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Så nå har vi en sortert
del og en usortert del.

1297
00:54:25,450 --> 00:54:27,810
Og hva som er bra å huske
om valg liksom

1298
00:54:27,810 --> 00:54:30,690
er vi bare velge
fra usortert del.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> Den sorterte delen du bare la alene.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> STUDENT: Hvordan vet den hva er
den minste uten å sammenligne det

1303
00:54:38,452 --> 00:54:39,868
til alle andre verdier i matrisen.

1304
00:54:39,868 --> 00:54:41,250
INSTRUKTØR: Det gjør sammenligne det.

1305
00:54:41,250 --> 00:54:42,041
Vi liker hoppet over det.

1306
00:54:42,041 --> 00:54:43,850
Dette er bare generell overordnet.

1307
00:54:43,850 --> 00:54:44,831
Yeah.

1308
00:54:44,831 --> 00:54:47,205
Når vi skriver inn koden jeg er
sikker på at du vil være mer fornøyd.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Men du lagrer denne første
element som den minste.

1311
00:54:53,030 --> 00:54:56,110
Du sammenligne og du
si, OK, er det mindre?

1312
00:54:56,110 --> 00:54:56,660
Ja.

1313
00:54:56,660 --> 00:54:57,460
Beholde den.

1314
00:54:57,460 --> 00:54:58,640
Her er det mindre?

1315
00:54:58,640 --> 00:54:59,660
Nei?

1316
00:54:59,660 --> 00:55:02,510
>> Dette er din minste,
overføre den til din verdi.

1317
00:55:02,510 --> 00:55:06,340
Og du vil bli mye lykkeligere
når vi går gjennom koden.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Så vi går gjennom, vi bytte det, så da
vi ser på dette usortert del.

1320
00:55:13,970 --> 00:55:15,810
Så vi kommer til å velge tre.

1321
00:55:15,810 --> 00:55:18,890
Vi kommer til å sette den på ved
slutten av sorterte parti.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
Og vi bare kommer til å fortsette å gjøre
det, gjør det, og gjør det.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Så dette er vår form for pseudo her.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Vi vil kode det opp her i et sekund.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Men bare noe å gå
gjennom på et høyt nivå.

1330
00:55:37,270 --> 00:55:40,275
Du kommer til å gå fra
Jeg er lik 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 annen optimalisering.

1333
00:55:43,530 --> 00:55:45,020
Ikke bekymre deg for mye om det.

1334
00:55:45,020 --> 00:55:46,620
Så som du sa.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Som Jakob sa, hvordan gjør vi
holde oversikt over hva vår minimum er?

1337
00:55:54,406 --> 00:55:55,030
Hvordan vet vi det?

1338
00:55:55,030 --> 00:55:57,060
Vi må sammenligne
alt i vår liste.

1339
00:55:57,060 --> 00:55:59,600
>> Så minimum lik i.

1340
00:55:59,600 --> 00:56:03,870
Det er bare å si i dette tilfellet
indeksen av minimumsverdien.

1341
00:56:03,870 --> 00:56:07,660
Så da kommer det til å iterere gjennom
og det går fra j i pluss en er lik.

1342
00:56:07,660 --> 00:56:11,420
Så vi vet allerede at
det er vår første elementet.

1343
00:56:11,420 --> 00:56:13,240
Vi trenger ikke å sammenligne det med seg selv.

1344
00:56:13,240 --> 00:56:16,970
Så vi begynner å sammenligne den med neste
en som er grunnen til at det er i pluss 1 til n

1345
00:56:16,970 --> 00:56:20,110
minus en, som er
enden av rekken der.

1346
00:56:20,110 --> 00:56:25,090
Og vi sa at hvis matrise på
j er mindre enn matrise min,

1347
00:56:25,090 --> 00:56:29,200
Da vi overføre der
våre minimums indekser er.

1348
00:56:29,200 --> 00:56:37,470
>> Og hvis min ikke er lik I, som
i hvor var vi tilbake over her.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Så liker når vi først gjorde dette.

1351
00:56:41,790 --> 00:56:49,310
I dette tilfelle, ville det begynne på
null, vil det ende opp med å være to.

1352
00:56:49,310 --> 00:56:53,010
Så min ville ikke lik i i ende.

1353
00:56:53,010 --> 00:56:55,720
Som lar oss få vite at
vi trenger å bytte dem.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Jeg føler meg som et konkret eksempel
vil hjelpe mye mer enn dette.

1356
00:57:00,470 --> 00:57:04,970
Så jeg skal kode dette opp med dere
akkurat nå, og jeg tror det vil bli bedre.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Sorterer en tendens til å fungere på den måten at
det er ofte bedre bare for å se dem.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Så det vi ønsker å gjøre er
vi først ønsker de minste

1361
00:57:17,280 --> 00:57:19,890
elementet i dens posisjon i matrisen.

1362
00:57:19,890 --> 00:57:21,280
Nøyaktig hva Jakob sa.

1363
00:57:21,280 --> 00:57:23,090
Du trenger å lagre som liksom.

1364
00:57:23,090 --> 00:57:25,900
Så vi kommer til å begynne her
iterere over matrisen.

1365
00:57:25,900 --> 00:57:28,970
Vi kommer til å si at det er vår
først en bare for å begynne med.

1366
00:57:28,970 --> 00:57:38,308
Så vi kommer til å ha int
minste er lik matrise på i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Så en ting å legge merke til, hver
gang denne sløyfen utfører,

1369
00:57:45,050 --> 00:57:48,550
vi starter ett skritt videre sammen.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Når vi starter ser vi på dette.

1372
00:57:57,440 --> 00:58:00,840
Neste gang vi iterere gjennom,
vi starter på denne ene

1373
00:58:00,840 --> 00:58:02,680
og tildele det vår minste verdi.

1374
00:58:02,680 --> 00:58:10,450
Så det er svært lik boble slags
der vi vet at etter ett pass,

1375
00:58:10,450 --> 00:58:11,700
Dette siste elementet er sortert.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Med utvalg sortere,
det er akkurat det motsatte.

1378
00:58:15,120 --> 00:58:18,950
>> På hvert pass, vet vi at
den første er sortert.

1379
00:58:18,950 --> 00:58:21,360
Etter den andre pass,
andre vil bli sortert.

1380
00:58:21,360 --> 00:58:26,470
Og som du så med glide eksempler,
vår sortert del bare fortsetter å vokse.

1381
00:58:26,470 --> 00:58:34,020
Så ved å sette vår minste en
til arrays i, alt det gjør

1382
00:58:34,020 --> 00:58:37,340
er sammentrekkende hva
vi ser på slik

1383
00:58:37,340 --> 00:58:40,164
å minimere antall
sammenligninger vi gjør.

1384
00:58:40,164 --> 00:58:41,770
Betyr det fornuftig for alle?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Har du behov for meg å kjøre gjennom det
igjen saktere eller i forskjellige 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 oppbevarer
Verdien på dette punktet,

1392
00:58:55,540 --> 00:58:57,840
men vi ønsker også å lagre indeksen.

1393
00:58:57,840 --> 00:59:01,010
Så vi kommer til å lagre
posisjonen til den minste

1394
00:59:01,010 --> 00:59:02,770
en, som bare kommer til å være i.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Så nå Jacob er fornøyd.

1397
00:59:05,440 --> 00:59:06,870
Vi har ting lagret.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
Og nå trenger vi å se gjennom
usortert del av tabellen.

1400
00:59:11,870 --> 00:59:18,170
Så i dette tilfellet er dette
ville være vår usortert.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
Dette er i.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
OK.

1405
00:59:26,210 --> 00:59:30,040
>> Så hva vi skal gjøre
kommer til å være for en loop.

1406
00:59:30,040 --> 00:59:32,066
Når du trenger å
iterere gjennom en matrise,

1407
00:59:32,066 --> 00:59:33,440
tankene dine kan gå til for en loop.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Så for noen int k
equals-- hva vi mener

1410
00:59:38,090 --> 00:59:39,700
k kommer til å like å starte med?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
Dette er hva vi satt som vår minste
verdi, og vi ønsker å sammenligne det.

1413
00:59:44,766 --> 00:59:47,090
Hva ønsker vi å sammenligne det med?

1414
00:59:47,090 --> 00:59:48,730
Det kommer til å bli denne neste, ikke sant?

1415
00:59:48,730 --> 00:59:53,200
Så vi ønsker k å bli initialisert
å jeg pluss 1 for å starte.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> Og vi ønsker k i dette tilfellet vi
allerede har størrelsen lagret opp her,

1418
01:00:02,800 --> 01:00:03,930
så vi kan bare bruke størrelse.

1419
01:00:03,930 --> 01:00:06,240
Størrelse blir størrelsen av rekken.

1420
01:00:06,240 --> 01:00:09,620
Og vi vil bare
oppdaterer k med én 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å nå må vi finne
det minste elementet her.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Så hvis vi iterere gjennom, vi
ønsker å si, hvis utvalg på k

1427
01:00:31,380 --> 01:00:37,080
er mindre enn vår minste value--
det er her vi er faktisk

1428
01:00:37,080 --> 01:00:42,950
holde styr på hva som er
den minste her--

1429
01:00:42,950 --> 01:00:47,740
Da vi ønsker å tilordne
hva våre minste verdien er.

1430
01:00:47,740 --> 01:00:50,645
>> Dette betyr at, åh, vi er
itera gjennom her.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Uansett hva verdien er her er
ikke vår minste ting.

1433
01:00:53,740 --> 01:00:54,448
Vi vil ikke ha det.

1434
01:00:54,448 --> 01:00:56,100
Vi ønsker å overføre den.

1435
01:00:56,100 --> 01:01:02,050
Så hvis vi reassigning det, hva gjør
du tror kan være i denne koden her?

1436
01:01:02,050 --> 01:01:04,160
Vi ønsker å tilordne
minste og posisjon.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Så hva er minste nå?

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 hva er stillingen nå?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Hva er indeksene for
vår minste verdi?

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å rekke k, k, matche de opp.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Så vi ønsket å overføre det.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
Og så etter at vi fant vår minste,
slik at ved slutten av dette for sløyfen

1454
01:01:39,950 --> 01:01:45,100
her har vi funnet det vår minste
verdien er, slik at vi bare bytte det.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
I dette tilfellet, i likhet si vår
minste verdien er her ute.

1457
01:01:50,816 --> 01:01:51,940
Dette er vår minste verdi.

1458
01:01:51,940 --> 01:01:57,690
>> Vi ønsker bare å bytte det her, som er
hva som swap-funksjonen nederst

1459
01:01:57,690 --> 01:02:01,270
gjorde, som vi nettopp skrev opp
sammen et par minutter siden.

1460
01:02:01,270 --> 01:02:02,775
Så det bør være kjent.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
Og så vil det bare iterere
gjennom inntil den når hele veien

1463
01:02:08,030 --> 01:02:13,100
til slutten, noe som betyr at du
har null elementer som usortert

1464
01:02:13,100 --> 01:02:14,800
og alt annet er blitt sortert.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Fornuftig?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Litt mer konkret?

1469
01:02:19,280 --> 01:02:19,990
Koden hjelp?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> STUDENT: For en størrelse, du aldri
egentlig definere det eller endre det,

1472
01:02:26,410 --> 01:02:27,340
hvordan virker det vet?

1473
01:02:27,340 --> 01:02:32,380
>> INSTRUKTØR: Så en ting til
merke seg her er int størrelse.

1474
01:02:32,380 --> 01:02:35,680
Så vi sier i denne sort-- slags
er en funksjon i dette er det case--

1475
01:02:35,680 --> 01:02:40,770
utvalg sortere, er det vedtatt
i med funksjonen.

1476
01:02:40,770 --> 01:02:43,460
Så hvis det ikke ble vedtatt
i, ville du gjøre noe

1477
01:02:43,460 --> 01:02:47,840
som med lengden av rekken
eller du vil iterere gjennom

1478
01:02:47,840 --> 01:02:49,390
for å finne lengden.

1479
01:02:49,390 --> 01:02:52,680
Men fordi det er gått
i, kan vi bare bruke den.

1480
01:02:52,680 --> 01:02:55,720
Du bare anta at brukeren
ga deg en gyldig størrelse som

1481
01:02:55,720 --> 01:02:57,698
faktisk representerer
en størrelse på 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 dere har noen problemer med disse
eller ønsker mer praksis koding 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 verktøy.

1489
01:03:12,670 --> 01:03:15,040
De har en brikke som
du faktisk kan skrive.

1490
01:03:15,040 --> 01:03:16,180
De gjør pseudokode.

1491
01:03:16,180 --> 01:03:19,310
De har flere videoer og lysbilder
inkludert de jeg bruker her.

1492
01:03:19,310 --> 01:03:23,150
Så hvis du fortsatt føler en
litt uklar, prøve det ut.

1493
01:03:23,150 --> 01:03:25,670
Som alltid, kom snakke med meg, også.

1494
01:03:25,670 --> 01:03:26,320
Spørsmål?

1495
01:03:26,320 --> 01:03:28,611
>> STUDENT: Sier du det
Størrelsen er tidligere definert?

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ørrelse er tidligere definert opp
her i funksjonen erklæringen.

1499
01:03:35,570 --> 01:03:39,060
Så du antar at det er blitt vedtatt i
av brukeren, og for enkelhets skyld,

1500
01:03:39,060 --> 01:03:41,896
vi kommer til å anta at
bruker ga oss riktig størrelse.

1501
01:03:41,896 --> 01:03:43,240
Cool.

1502
01:03:43,240 --> 01:03:44,390
Så det er valg slag.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Folkens, jeg vet at vi lærer mye i dag.

1505
01:03:47,640 --> 01:03:49,710
Det er en tett data for seksjonen.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Så med det, skal vi
å gå til innsetting slag.

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 å gjøre
vår runtime analysen her.

1511
01:04:06,100 --> 01:04:10,190
Så i beste fall
innvilget siden jeg viste deg

1512
01:04:10,190 --> 01:04:11,960
bordet jeg allerede
slags ga den bort.

1513
01:04:11,960 --> 01:04:15,430
Men best case runtime, hva tror vi?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Alt sortert.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N squared.

1518
01:04:22,070 --> 01:04:24,780
Alle som 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: Høyre.

1522
01:04:31,268 --> 01:04:32,540
Du sammenligner gjennom.

1523
01:04:32,540 --> 01:04:35,630
Ved hver iterasjon, til tross
vi minske dette etter en,

1524
01:04:35,630 --> 01:04:38,950
du fortsatt søker gjennom
alt for å finne den minste.

1525
01:04:38,950 --> 01:04:42,390
Så selv om din minste verdien
er her i begynnelsen,

1526
01:04:42,390 --> 01:04:44,710
du fortsatt sammenligner det
mot alt annet

1527
01:04:44,710 --> 01:04:46,550
å sørge for at det er den minste ting.

1528
01:04:46,550 --> 01:04:49,820
Så du vil ende opp med å løpe gjennom
ca n squared ganger.

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 hva er det verste tilfellet?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Også n squared fordi du kommer
som skal gjøre det samme prosedyre.

1534
01:04:57,980 --> 01:05:01,670
Slik at i dette tilfellet, utvelgelse
liksom har noe

1535
01:05:01,670 --> 01:05:04,010
at vi også ringe forventet runtime.

1536
01:05:04,010 --> 01:05:07,400
Så i de andre, vi bare vet
øvre og nedre grense.

1537
01:05:07,400 --> 01:05:11,180
Avhengig av hvor gal vår
Listen er eller hvordan usortert det er,

1538
01:05:11,180 --> 01:05:15,350
de varierer mellom n eller n squared.

1539
01:05:15,350 --> 01:05:16,550
Vi vet ikke.

1540
01:05:16,550 --> 01:05:22,820
>> Men fordi utvalget liksom har samme
verste og beste fall forteller at oss at

1541
01:05:22,820 --> 01:05:25,880
uansett hva slags innspill vi
har, enten det er helt

1542
01:05:25,880 --> 01:05:29,130
sortert eller helt
reversere sortert, det er

1543
01:05:29,130 --> 01:05:30,740
kommer til å ta den samme tidsperiode.

1544
01:05:30,740 --> 01:05:33,760
Så i så fall, hvis du
husker fra bordet vårt,

1545
01:05:33,760 --> 01:05:38,610
det faktisk hadde en verdi som
disse to slags ikke har,

1546
01:05:38,610 --> 01:05:40,390
som er forventet runtime.

1547
01:05:40,390 --> 01:05:43,350
Så vi vet at når
vi kjører valg slag,

1548
01:05:43,350 --> 01:05:45,380
det er garantert å
kjøre en n squared tid.

1549
01:05:45,380 --> 01:05:46,630
Det er ingen variasjon 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, igjen, hvis du ønsker å lære
mer, ta CS 124 i løpet av våren.

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 sett 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å innsetting slag.

1559
01:06:00,930 --> 01:06:03,330
Og jeg sannsynligvis kommer
å fyke gjennom dette.

1560
01:06:03,330 --> 01:06:05,440
Jeg vil ikke ha dere kode det.

1561
01:06:05,440 --> 01:06:06,580
Vi må bare gå gjennom den.

1562
01:06:06,580 --> 01:06:10,500
Så innsetting liksom er snill
av lik valg liksom

1563
01:06:10,500 --> 01:06:14,460
ved at vi har både en usortert
og sortert del av tabellen.

1564
01:06:14,460 --> 01:06:20,260
>> Men hva er annerledes er at
når vi går gjennom en etter en,

1565
01:06:20,260 --> 01:06:24,210
vi bare ta uansett hvor mange
er neste i vår usortert,

1566
01:06:24,210 --> 01:06:28,507
og riktig sortere det
inn i vårt sortert array.

1567
01:06:28,507 --> 01:06:30,090
Det vil være mer fornuftig 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 usortert,
akkurat som med valg slag.

1570
01:06:35,430 --> 01:06:38,740
Og vi kommer til å sortere dette i
stigende rekkefølge som vi har vært.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Så på vår første pass
vi tar den første verdien

1573
01:06:43,340 --> 01:06:46,700
og vi sier, OK, du er
nå i en liste selv.

1574
01:06:46,700 --> 01:06:49,150
>> Fordi du er i en liste
av deg selv, du er sortert.

1575
01:06:49,150 --> 01:06:52,460
Gratulerer med å være den
første element i denne matrise.

1576
01:06:52,460 --> 01:06:54,800
Du er allerede sortert alt på egen hånd.

1577
01:06:54,800 --> 01:06:58,900
Så nå har vi en sortert
og en usortert array.

1578
01:06:58,900 --> 01:07:01,760
Så nå tar vi det første.

1579
01:07:01,760 --> 01:07:05,600
Hva skjer mellom her
og her er at vi sier,

1580
01:07:05,600 --> 01:07:08,890
OK, vi kommer til å se på
første verdien av vår usortert utvalg

1581
01:07:08,890 --> 01:07:13,270
og vi kommer til å legge den i sin
riktig plass i den sorterte array.

1582
01:07:13,270 --> 01:07:21,460
>> Så det vi gjør er tar vi fem og
vi sier, OK, 5 er større enn 3,

1583
01:07:21,460 --> 01:07:24,630
så vi bare sette det riktig
til høyre for den.

1584
01:07:24,630 --> 01:07:25,130
Vi er bra.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Så da går vi videre til vår neste.

1587
01:07:28,420 --> 01:07:29,720
Og vi tar to.

1588
01:07:29,720 --> 01:07:34,330
Vi sier, OK, to er mindre
enn 3, så vi vet at det

1589
01:07:34,330 --> 01:07:36,220
må være på
foran vår liste nå.

1590
01:07:36,220 --> 01:07:41,800
Så det vi gjør er å presse vi 3 og 5 ned
og vi beveger oss to inn i det første sporet.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Så vi bare å sette den inn
riktig sted det skal være.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Så ser vi på vår
neste, og vi sier seks.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 er større enn
alt i vår sorterte array,

1596
01:07:53,620 --> 01:07:56,000
så vi bare merke det på til slutt.

1597
01:07:56,000 --> 01:07:56,960
Og så ser vi på fire.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 er mindre enn 6, er det mindre
enn 5, men det er større enn 3.

1600
01:08:03,020 --> 01:08:06,270
Så vi bare sette ballen opp
midt mellom 3 og 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Så for å gjøre det litt
litt mer konkret,

1603
01:08:10,530 --> 01:08:12,280
her er litt av det
ide om hva som skjedde.

1604
01:08:12,280 --> 01:08:16,430
Så for hver usortert element, vi
bestemme hvor i den sorterte parti

1605
01:08:16,430 --> 01:08:17,090
det er.

1606
01:08:17,090 --> 01:08:20,680
>> Så med tanke på
sortert og usortert,

1607
01:08:20,680 --> 01:08:26,080
vi må traversere gjennom og figur
ut hvor det passer i den sorterte array.

1608
01:08:26,080 --> 01:08:31,460
Og vi setter den ved å forskyve
elementer til høyre for det ned.

1609
01:08:31,460 --> 01:08:34,910
Og da har vi bare fortsette
itera gjennom før vi

1610
01:08:34,910 --> 01:08:39,270
har en helt sortert liste
hvor usortert er nå null

1611
01:08:39,270 --> 01:08:41,720
og sorterte tar opp
helheten av vår liste.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Så, igjen, for å gjøre ting enda
mer konkret, har vi pseudokode.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Så i utgangspunktet for jeg er
lik 0 til minus 1 n,

1616
01:08:52,410 --> 01:08:54,790
det er bare lengden på array.

1617
01:08:54,790 --> 01:09:00,979
Vi har noen element som er lik
den første matrise eller de første indeksene.

1618
01:09:00,979 --> 01:09:03,200
Vi satt j lik.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Så mens j er større enn
null og matrisen, j minus 1

1621
01:09:09,210 --> 01:09:11,660
er større enn den
element, så alt som gjør

1622
01:09:11,660 --> 01:09:17,479
er å sørge for at
din j virkelig representerer

1623
01:09:17,479 --> 01:09:20,010
usortert parti av matrisen.

1624
01:09:20,010 --> 01:09:30,745
>> Så mens det er fortsatt ting
å sortere og j minus én er-- hva

1625
01:09:30,745 --> 01:09:31,840
er element henne?

1626
01:09:31,840 --> 01:09:34,760
J ble aldri definert her.

1627
01:09:34,760 --> 01:09:35,677
Det er litt irriterende.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Anyways.

1630
01:09:36,689 --> 01:09:39,899
Så j minus 1, du sjekker
elementet før det.

1631
01:09:39,899 --> 01:09:46,460
Du sier, OK, er element
før uansett hvor jeg am-- la oss

1632
01:09:46,460 --> 01:09:47,540
faktisk trekke dette ut.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Så la oss si dette er
som på våre andre pass.

1635
01:09:56,830 --> 01:09:59,525
Så jeg kommer til å være lik
til 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 å være lik 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å vår element i dette tilfellet
kommer til å være lik 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
Og vi har noen j som er
kommer til å være lik 1.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Oh, er j dekrementering.

1647
01:10:30,971 --> 01:10:31,720
Det er hva det er.

1648
01:10:31,720 --> 01:10:35,680
Så j er lik i, så hva dette er
sier er at når vi beveger oss fremover,

1649
01:10:35,680 --> 01:10:37,530
vi er bare å sørge for
at vi er ikke over

1650
01:10:37,530 --> 01:10:43,520
indeksere denne måten når vi prøver
å sette ting inn i vårt sortert liste.

1651
01:10:43,520 --> 01:10:49,850
>> Slik at når j er lik 1, og i dette tilfellet
matrise j minus one-- slik matrise j minus 1

1652
01:10:49,850 --> 01:10:54,610
er to i denne case-- hvis det er
større enn elementet,

1653
01:10:54,610 --> 01:10:57,700
så alt dette gjør
er skiftende ting ned.

1654
01:10:57,700 --> 01:11:04,790
Så i dette tilfellet, array j minus én
ville være matrise null, noe som er 2.

1655
01:11:04,790 --> 01:11:08,430
2 ikke er større enn 4,
slik at dette ikke utføres.

1656
01:11:08,430 --> 01:11:11,460
Så skiftet rører seg ikke ned.

1657
01:11:11,460 --> 01:11:18,790
Hva dette her er bare
bevege sortert rekke ned.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
I dette tilfellet faktisk, vi
kunne do-- la oss gjøre dette til tre.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Så hvis vi skal gå gjennom med
dette eksempelet, vi er nå her.

1662
01:11:31,970 --> 01:11:32,740
Dette er sortert.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
Dette er usortert.

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å i er lik 2, så
vår element er lik 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
Og vårt j er lik 2.

1670
01:11:52,270 --> 01:12:00,620
Så vi ser gjennom, og vi
si, OK, er matrise j minus én

1671
01:12:00,620 --> 01:12:03,470
større enn elementets
at vi ser på?

1672
01:12:03,470 --> 01:12:05,540
Og svaret er ja, ikke sant?

1673
01:12:05,540 --> 01:12:11,275
4 er større enn 3, og j
er 2, slik at denne utfører koden.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Så nå hva vi gjør en matrise på
2, så akkurat her, bytter vi dem.

1676
01:12:18,550 --> 01:12:25,620
Så vi bare si, OK, array
2 er nå kommer til å bli tre.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
Og j kommer til å like
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 fryktelig, men
dere skjønner poenget.

1681
01:12:37,200 --> 01:12:38,360
J er nå lik 1.

1682
01:12:38,360 --> 01:12:44,360
Og rekke j er bare kommer til å være
lik våre elementet, som var 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
Jeg slettet noe jeg ikke burde
har eller miswrote noe,

1685
01:12:48,570 --> 01:12:49,910
men dere skjønner poenget.

1686
01:12:49,910 --> 01:12:50,640
>> Det flytter på n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
Og så om dette var, ville det sløyfe
igjen, og det vil si, OK, er j en nå.

1689
01:12:57,960 --> 01:13:00,665
Og rekke j minus 1 er nå to.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Er to mindre enn vår element?

1692
01:13:03,760 --> 01:13:04,540
Nei?

1693
01:13:04,540 --> 01:13:07,970
Det betyr at vi har
satt inn dette elementet

1694
01:13:07,970 --> 01:13:10,110
på riktig sted i vårt sortert array.

1695
01:13:10,110 --> 01:13:14,400
Da kan vi ta dette og vi sier,
OK, er vår sorterte utvalg her.

1696
01:13:14,400 --> 01:13:19,940
Og det ville ta dette nummer 6 og vær
lignende, OK, er 6 færre enn dette nummeret?

1697
01:13:19,940 --> 01:13:20,480
Nei?

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
>> Gjøre det igjen.

1701
01:13:23,530 --> 01:13:24,740
Vi sier 7.

1702
01:13:24,740 --> 01:13:29,010
7 er mindre enn enden
av vår sorterte array?

1703
01:13:29,010 --> 01:13:29,520
Nei.

1704
01:13:29,520 --> 01:13:30,430
Så vi er fine.

1705
01:13:30,430 --> 01:13:32,760
Så dette ville være sortert.

1706
01:13:32,760 --> 01:13:38,610
I utgangspunktet alt dette gjør
det er å si take

1707
01:13:38,610 --> 01:13:42,060
det første elementet
din usortert array,

1708
01:13:42,060 --> 01:13:46,010
finne ut hvor det går
i sortert array.

1709
01:13:46,010 --> 01:13:48,780
Og dette tar bare vare
av bytteavtaler for å gjøre det.

1710
01:13:48,780 --> 01:13:51,300
Du er i utgangspunktet bare bytte
før det er på rett sted.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Det visuelle bildet er at du er
flytte alt ned ved å gjøre det.

1713
01:13:56,990 --> 01:13:59,420
>> Så det er som en halv boble sort-esque.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Sjekk ut studie 50.

1716
01:14:03,420 --> 01:14:06,000
Jeg anbefaler å prøve
å 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 noen spørsmål eller ønsker å
se eksempelkode for en innsetting sortere,

1719
01:14:12,450 --> 01:14:13,750
vennligst gi meg beskjed.

1720
01:14:13,750 --> 01:14:14,500
Jeg er alltid rundt.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Så worst case runtime
og best case runtime.

1723
01:14:20,200 --> 01:14:30,700
Som du fyren så fra bordet jeg allerede
viste deg, det er både n squared og n.

1724
01:14:30,700 --> 01:14:35,590
>> Så snill å gå ut av hva vi snakket
om med våre tidligere former, verste

1725
01:14:35,590 --> 01:14:38,760
case runtime er at hvis
det er helt usortert,

1726
01:14:38,760 --> 01:14:42,530
vi har å sammenligne alle disse n ganger.

1727
01:14:42,530 --> 01:14:47,020
Vi gjør en hel masse sammenligninger
fordi hvis det er i motsatt rekkefølge,

1728
01:14:47,020 --> 01:14:50,360
vi kommer til å si, OK, dette
er den samme, er dette bra,

1729
01:14:50,360 --> 01:14:54,650
og dette vil måtte bli sammenlignet
mot den første til å bli beveget tilbake.

1730
01:14:54,650 --> 01:14:56,710
Og som vi får mot
halen slutten, har vi

1731
01:14:56,710 --> 01:14:59,440
å sammenligne, sammenligne, og
sammenligne mot alt.

1732
01:14:59,440 --> 01:15:03,030
>> Så det ender opp med å bli
ca n squared.

1733
01:15:03,030 --> 01:15:09,510
Hvis det er riktig så du
si, OK, to, du er flink.

1734
01:15:09,510 --> 01:15:11,330
3, du er sammenlignet med 2.

1735
01:15:11,330 --> 01:15:12,310
Du er flink.

1736
01:15:12,310 --> 01:15:14,150
4, du bare sammenligne med halen.

1737
01:15:14,150 --> 01:15:14,990
Du er flink.

1738
01:15:14,990 --> 01:15:17,140
6, sammenlignet med halen, du er fine.

1739
01:15:17,140 --> 01:15:20,870
Så for hvert sted hvis det er allerede
sortert, du gjø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 av n

1742
01:15:26,840 --> 01:15:28,680
squared, har vi ingen forventet runtime.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Det avhenger bare av den
kaos av vår liste der.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
Og igjen, en annen
graf og en annen tabell.

1747
01:15:39,530 --> 01:15:41,170
Så forskjellene mellom sorterer.

1748
01:15:41,170 --> 01:15:44,180
Jeg skal bare bris gjennom, jeg
føler at vi har snakket mye

1749
01:15:44,180 --> 01:15:46,570
om hvordan de alle slags
av variere og koble sammen.

1750
01:15:46,570 --> 01:15:50,564
Så Flettesortering er den siste
Jeg skal kjede dere med.

1751
01:15:50,564 --> 01:15:52,105
Vi har et ganske fargerikt bilde.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Så flette sort er en rekursiv algoritme.

1754
01:15:56,040 --> 01:15:59,910
Så vet dere hva
en rekursiv funksjon er?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Alle som ønsker å si?

1757
01:16:03,320 --> 01:16:04,739
Du ønsker å prøve?

1758
01:16:04,739 --> 01:16:07,280
Så en rekursiv funksjon er bare
en funksjon som kaller seg.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Så hvis dere er kjent
med Fibonacci-sekvensen,

1761
01:16:11,590 --> 01:16:15,670
som er ansett rekursiv fordi
du tar de to foregående

1762
01:16:15,670 --> 01:16:17,530
og legge dem sammen
å få din neste.

1763
01:16:17,530 --> 01:16:21,440
Så rekursive, jeg tenker alltid
av rekursjon som som en spiral

1764
01:16:21,440 --> 01:16:24,430
så du er som spiral ned i den.

1765
01:16:24,430 --> 01:16:27,150
Men det er bare en funksjon
som kaller seg.

1766
01:16:27,150 --> 01:16:32,660
>> Og, faktisk, veldig raskt jeg
kan vise deg hva som ser ut som.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Så rekursive her, hvis vi ser, er dette
den rekursive måte å oppsummere over en tabell.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Så alt vi gjør er
vi har sum funksjon

1771
01:16:47,880 --> 01:16:52,210
sum som tar en størrelse og en matrise.

1772
01:16:52,210 --> 01:16:55,210
Og hvis du legger merke til, størrelse
svekkelser av en hver tid.

1773
01:16:55,210 --> 01:17:00,365
Og alt det gjør er hvis x er lik
zero-- slik at hvis størrelsen av rekken

1774
01:17:00,365 --> 01:17:02,710
er lik zero-- den returnerer null.

1775
01:17:02,710 --> 01:17:10,440
>> Ellers oppsummerer dette
siste element i matrisen,

1776
01:17:10,440 --> 01:17:14,790
og deretter tar en sum av
resten av matrisen.

1777
01:17:14,790 --> 01:17:17,555
Så det er bare å bryte 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, rekursjon,
funksjon som kaller seg selv.

1780
01:17:21,890 --> 01:17:25,740
Hvis det er alt du fikk ut av dette,
det er hva en rekursiv funksjon er.

1781
01:17:25,740 --> 01:17:29,870
Hvis du tar 51, vil du få veldig,
veldig komfortabel med rekursjon.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
Det er virkelig kult.

1784
01:17:32,370 --> 01:17:34,660
Det var fornuftig på som
3 AM en natt ute.

1785
01:17:34,660 --> 01:17:37,900
Og jeg var som, hvorfor
har jeg aldri bruke dette?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Så for merge sort, i utgangspunktet
hva det kommer til å gjøre, er det

1788
01:17:42,430 --> 01:17:45,620
kommer til å bryte det ned, og bryte det
ned før det er bare enkeltelementer.

1789
01:17:45,620 --> 01:17:47,570
Enkeltelementene er enkelt å 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 ett element, er det
allerede vurdert sortert.

1792
01:17:50,760 --> 01:17:53,800
Så på en inngang på n elementer,
hvis n er mindre enn 2,

1793
01:17:53,800 --> 01:17:58,120
bare tilbake fordi det betyr
det er enten 0 eller 1 som vi har sett.

1794
01:17:58,120 --> 01:18:00,050
De anses sorterte elementer.

1795
01:18:00,050 --> 01:18:02,170
>> Ellers bryte den i to.

1796
01:18:02,170 --> 01:18:06,336
Sortere første halvår, sortere den andre
halvparten, og deretter flette dem sammen.

1797
01:18:06,336 --> 01:18:07,460
Hvorfor det heter merge sort.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Så vi har her vi vil sortere disse.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Så vi holder å ha dem
inntil gitterstørrelse er 1.

1802
01:18:17,210 --> 01:18:20,790
Så når det er en, vi bare tilbake
fordi dette er en sortert matrise,

1803
01:18:20,790 --> 01:18:23,940
og dette er en sortert matrise, og det er
en sortert array, er vi alle sortert.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Så det vi gjør er vi
begynne å flette dem sammen.

1806
01:18:29,420 --> 01:18:31,820
>> Så på den måten du kan
tenker om sammenslåing er

1807
01:18:31,820 --> 01:18:36,240
du bare fjerne mindre
antallet av hver av de sub-arrayer

1808
01:18:36,240 --> 01:18:38,330
og bare føye det til fremkom array.

1809
01:18:38,330 --> 01:18:44,290
Så hvis du ser her, når vi har
disse settene har vi 4, 6, og en.

1810
01:18:44,290 --> 01:18:47,280
Når vi ønsker å slå sammen disse,
vi ser på disse to først

1811
01:18:47,280 --> 01:18:50,730
og vi sier, OK, en er mindre,
det går til fronten.

1812
01:18:50,730 --> 01:18:54,330
4 og 6, det er ingenting å sammenligne
det til, bare merke det på til slutt.

1813
01:18:54,330 --> 01:18:58,020
>> Når vi kombinerer disse to, vi bare
ta den mindre av disse to,

1814
01:18:58,020 --> 01:18:59,310
så det er en.

1815
01:18:59,310 --> 01:19:01,690
Og nå tar vi
minste av disse to, så to.

1816
01:19:01,690 --> 01:19:03,330
Minste av disse to, tre.

1817
01:19:03,330 --> 01:19:06,260
Minste av disse to, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Så du bare å trekke av disse.

1819
01:19:08,630 --> 01:19:11,210
Og fordi de har
blitt sortert tidligere,

1820
01:19:11,210 --> 01:19:14,300
du bare har én
sammenlikning hver gang der.

1821
01:19:14,300 --> 01:19:19,610
Så mer kode her, bare representasjon.

1822
01:19:19,610 --> 01:19:24,410
Så du begynner på midten og
du liksom venstre og høyre

1823
01:19:24,410 --> 01:19:26,180
og så du bare flette dem.

1824
01:19:26,180 --> 01:19:30,080
>> Og vi ikke har kode
for flette akkurat her.

1825
01:19:30,080 --> 01:19:34,110
Men, igjen, hvis du går på
studere 50, vil det være der.

1826
01:19:34,110 --> 01:19:36,860
Ellers komme å snakke med meg
Hvis du fortsatt er forvirret.

1827
01:19:36,860 --> 01:19:42,340
Så kult her er at beste fall
verste fall, og forventet runtime

1828
01:19:42,340 --> 01:19:46,250
er alle i log n, der
er langt bedre enn vi har

1829
01:19:46,250 --> 01:19:48,000
sett for resten av våre former.

1830
01:19:48,000 --> 01:19:51,840
Vi har sett n squared
og hva vi faktisk

1831
01:19:51,840 --> 01:19:54,380
får her er n log n, som er flott.

1832
01:19:54,380 --> 01:19:55,830
>> Se på hvor mye bedre det er.

1833
01:19:55,830 --> 01:19:56,780
Slik en fin kurve.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Så mye mer effektiv.

1836
01:20:00,120 --> 01:20:03,510
Hvis du noen gang kan, bruk flette slag.

1837
01:20:03,510 --> 01:20:04,810
Det vil spare deg for tid.

1838
01:20:04,810 --> 01:20:07,670
Så igjen, som vi sa, hvis
du er nede i denne nedre regionen,

1839
01:20:07,670 --> 01:20:09,480
det gjør ikke det
mye av en forskjell.

1840
01:20:09,480 --> 01:20:11,360
Du får opp til tusenvis
og tusenvis av innganger,

1841
01:20:11,360 --> 01:20:13,318
du definitivt vil ha en
mer effektiv algoritme.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
Og, igjen, vår nydelig bord av alt
former som dere har lært i dag.

1844
01:20:19,400 --> 01:20:21,157
>> Så jeg vet det har vært en tett dag.

1845
01:20:21,157 --> 01:20:23,490
Dette er ikke nødvendigvis kommer
å hjelpe deg med din PSet.

1846
01:20:23,490 --> 01:20:28,250
Men jeg vil bare gjøre en ansvarsfraskrivelse
den delen er ikke bare om psets.

1847
01:20:28,250 --> 01:20:31,240
Alt dette materialet er rettferdig
spill for dine midterms.

1848
01:20:31,240 --> 01:20:35,430
Og også hvis du fortsetter med CS,
disse er veldig viktige grunnprinsipper

1849
01:20:35,430 --> 01:20:37,870
som du trenger å vite.

1850
01:20:37,870 --> 01:20:41,700
Så noen dager vil være en
litt mer PSet hjelp,

1851
01:20:41,700 --> 01:20:44,600
men noen uker vil være
mye mer faktiske innholdet

1852
01:20:44,600 --> 01:20:46,600
som kanskje ikke synes super
nyttig for deg akkurat nå,

1853
01:20:46,600 --> 01:20:51,215
men jeg lover hvis du fortsetter
på vil være veldig, veldig nyttig.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Så det er det for seksjonen.

1856
01:20:54,250 --> 01:20:55,250
Ned til ledningen.

1857
01:20:55,250 --> 01:20:56,570
Jeg gjorde det i løpet av ett minutt.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Men det du går.

1860
01:20:58,970 --> 01:21:01,240
Og jeg vil ha donuts eller godteri.

1861
01:21:01,240 --> 01:21:03,464
Er noen allergisk mot
noe, forresten?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Egg og melk.

1864
01:21:05,890 --> 01:21:08,120
Så donuts er et nei?

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
Sjokolade nei?

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

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Vi kommer til å ha
Starburst neste uke da.

1874
01:21:17,045 --> 01:21:18,240
Det er det jeg får.

1875
01:21:18,240 --> 01:21:19,690
Dere har en flott uke.

1876
01:21:19,690 --> 01:21:20,460
Les spec.

1877
01:21:20,460 --> 01:21:22,130
>> La meg vite om du har noen spørsmål.

1878
01:21:22,130 --> 01:21:25,300
PSet to karakterer bør være
ut til deg innen torsdag.

1879
01:21:25,300 --> 01:21:28,320
Hvis du har noen spørsmål
om hvordan jeg gradert noe

1880
01:21:28,320 --> 01:21:32,250
eller hvorfor jeg gradert noe slik jeg
gjorde, vennligst send meg, kom snakke med meg.

1881
01:21:32,250 --> 01:21:34,210
Jeg er litt gal denne
uke, men jeg lover

1882
01:21:34,210 --> 01:21:36,340
Jeg vil fortsatt svare innen 24 timer.

1883
01:21:36,340 --> 01:21:38,240
Så ha en flott uke, alle sammen.

1884
01:21:38,240 --> 01:21:40,090
Lykke til på din PSet.

1885
01:21:40,090 --> 01:21:41,248