1
00:00:00,000 --> 00:00:03,332
>> [MUSIK SPELA]

2
00:00:03,332 --> 00:00:06,490
>> ANDI PENG: Välkommen till vecka 3 i avsnitt.

3
00:00:06,490 --> 00:00:09,550
Tack, ni, för alla kommande
till detta tidigare starttid idag.

4
00:00:09,550 --> 00:00:11,466
Vi har en fin, lite
intim grupp idag.

5
00:00:11,466 --> 00:00:14,570
Så förhoppningsvis kommer vi till
finish, kanske, tidigt,

6
00:00:14,570 --> 00:00:15,780
lite tidigt idag.

7
00:00:15,780 --> 00:00:22,057
Så snabbt, bara några
meddelanden till dagordning i dag.

8
00:00:22,057 --> 00:00:23,890
Innan vi börjar, vi är
kommer att bara gå över

9
00:00:23,890 --> 00:00:28,910
några korta logistiska frågor, pset
frågor, utfråga, sånt.

10
00:00:28,910 --> 00:00:30,250
Och sedan ska vi dyka rätt i.

11
00:00:30,250 --> 00:00:34,710
Vi kommer att använda en avlusare kallas GDB till
börja avslöja vår kod, som David

12
00:00:34,710 --> 00:00:36,550
förklaras i föreläsning häromdagen.

13
00:00:36,550 --> 00:00:39,420
Vi kommer att gå igenom de fyra typer av slag.

14
00:00:39,420 --> 00:00:42,310
Vi kommer att gå igenom dem ganska snabbt
eftersom de är ganska intensiv.

15
00:00:42,310 --> 00:00:45,710
Men vet att alla bilder och
källkod är alltid online.

16
00:00:45,710 --> 00:00:50,810
Så känn dig fri på din läsning, till
gå tillbaka och ta en titt på det.

17
00:00:50,810 --> 00:00:53,930
>> Vi ska gå igenom
asymptotisk notation, som

18
00:00:53,930 --> 00:00:55,944
är bara ett fint sätt
att säga "drifttider"

19
00:00:55,944 --> 00:00:58,360
där vi har den stora O, som
David förklaras i föreläsning.

20
00:00:58,360 --> 00:01:01,550
Och vi har också Omega, som
är den nedre gränsen körning.

21
00:01:01,550 --> 00:01:06,450
Och vi kommer att prata lite mer
djupgående om hur de arbete.

22
00:01:06,450 --> 00:01:10,160
Och slutligen, kommer vi att gå över binär sökning,
eftersom en hel del av er som redan har

23
00:01:10,160 --> 00:01:15,190
sneglade på dina psets vet förmodligen att
det är en fråga som är i pset.

24
00:01:15,190 --> 00:01:17,470
Så du kommer alla vara glad
som vi täcker denna dag.

25
00:01:17,470 --> 00:01:20,610
>> Och slutligen, per din
avsnitt feedback, jag faktiskt

26
00:01:20,610 --> 00:01:23,000
vänster ca 15 minuter vid
slutet för att bara gå över

27
00:01:23,000 --> 00:01:27,730
logistiken för pset3, frågor,
kanske lite vägledning, om ni så vill,

28
00:01:27,730 --> 00:01:28,990
innan vi börja programmera.

29
00:01:28,990 --> 00:01:30,890
Så låt oss försöka få igenom
materialet ganska snabbt.

30
00:01:30,890 --> 00:01:33,880
Och då kan vi tillbringa lite tid
ta fler frågor för pset.

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

32
00:01:35,230 --> 00:01:39,570
>> Snabbt, så det är bara ett fåtal
meddelanden innan vi börjar idag.

33
00:01:39,570 --> 00:01:45,410
För det första, välkommen att göra
det genom två av dina psets.

34
00:01:45,410 --> 00:01:49,432
Jag tog en titt på your-- ja, låt oss
få en applåd för att en.

35
00:01:49,432 --> 00:01:51,140
Faktiskt, jag var riktigt,
verkligen imponerad.

36
00:01:51,140 --> 00:01:55,800
Jag graderade första pset för er
förra veckan och ni gjorde otroligt.

37
00:01:55,800 --> 00:01:58,290
>> Style var på punkt
förutom några kommentarer.

38
00:01:58,290 --> 00:02:00,660
Se till att du alltid
kommentera din kod.

39
00:02:00,660 --> 00:02:03,040
Men dina psets var på punkt.

40
00:02:03,040 --> 00:02:05,549
Och hålla den.

41
00:02:05,549 --> 00:02:08,090
Och det är bra för grader till
se att ni sätter

42
00:02:08,090 --> 00:02:10,704
i så mycket ansträngning i din stil
och din design i din kod

43
00:02:10,704 --> 00:02:12,120
att vi skulle vilja för dig att se.

44
00:02:12,120 --> 00:02:16,450
Så jag passerar längs min tacksamhet
för resten av TAS.

45
00:02:16,450 --> 00:02:19,210
>> Men det finns en
några utfråga frågor

46
00:02:19,210 --> 00:02:22,010
Jag vill bara gå över den
skulle göra både mitt liv

47
00:02:22,010 --> 00:02:24,900
och en hel del av den andra
Resebyråerna liv lite lättare.

48
00:02:24,900 --> 00:02:28,220
För det första har jag märkt detta
Tidigare week-- hur många av er

49
00:02:28,220 --> 00:02:32,301
har varit igång check50 på
din kod innan du skickar?

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

51
00:02:32,800 --> 00:02:36,690
Så alla borde göra check50,
because-- en secret-- vi faktiskt

52
00:02:36,690 --> 00:02:41,540
köra check50 som en del av vår riktighet
skript för att testa din kod.

53
00:02:41,540 --> 00:02:45,480
Så om din kod misslyckas
check50, med all sannolikhet,

54
00:02:45,480 --> 00:02:47,570
det förmodligen kommer att
misslyckas vår kontroll samt.

55
00:02:47,570 --> 00:02:49,320
Ibland ni
har de rätta svaren.

56
00:02:49,320 --> 00:02:52,200
Liksom i girig, en del av
du har rätt nummer,

57
00:02:52,200 --> 00:02:53,960
du bara skriva ut lite extra grejer.

58
00:02:53,960 --> 00:02:55,940
Och det extra grejer
faktiskt misslyckas kontrollen,

59
00:02:55,940 --> 00:02:58,440
eftersom datorn inte
riktigt vet vad det är du letar efter.

60
00:02:58,440 --> 00:03:00,981
Och så kommer det att bara köra igenom,
se till att utskrifterna inte

61
00:03:00,981 --> 00:03:03,810
matchar vad vi förväntar oss svaret
att vara, och markera det är fel.

62
00:03:03,810 --> 00:03:06,560
>> Och jag vet som hände i
några av dina ärenden denna vecka.

63
00:03:06,560 --> 00:03:09,870
Så jag gick tillbaka och manuellt
omklassificerade allas kod.

64
00:03:09,870 --> 00:03:12,780
I framtiden om,
snälla, vänligen se

65
00:03:12,780 --> 00:03:14,570
att du kör
kontrollera 50 på din kod.

66
00:03:14,570 --> 00:03:17,970
Eftersom det är lite av en smärta för TA
att behöva gå tillbaka och manuellt omklassificering

67
00:03:17,970 --> 00:03:21,197
varenda pset för varje
singel, lite missade exempel.

68
00:03:21,197 --> 00:03:22,530
Så jag tog bort några poäng.

69
00:03:22,530 --> 00:03:25,210
Jag tror att jag tog fart kanske
en eller två för design.

70
00:03:25,210 --> 00:03:27,710
I framtiden men om
du inte check50,

71
00:03:27,710 --> 00:03:31,330
punkter kommer att tas
off för korrekthet.

72
00:03:31,330 --> 00:03:35,020
>> Vidare psets är
på grund fredagar kl.

73
00:03:35,020 --> 00:03:38,990
Jag tror att det finns en sju minuters
sen grace period som vi ger dig.

74
00:03:38,990 --> 00:03:42,434
Per Harvard tid, de är tillåtet att
sju minuter sent till allt.

75
00:03:42,434 --> 00:03:44,350
Så här vid Yale, vi ska
ansluta sig till det också.

76
00:03:44,350 --> 00:03:47,910
Men ganska mycket, på 0:07,
Om din pset inte är i,

77
00:03:47,910 --> 00:03:49,720
det kommer att märkas så sent.

78
00:03:49,720 --> 00:03:53,160
Och så även om det är märkt
så sent, det TA-- jag

79
00:03:53,160 --> 00:03:54,870
fortfarande kommer att klassificera dina psets.

80
00:03:54,870 --> 00:03:56,760
Så du fortfarande se en klass visas.

81
00:03:56,760 --> 00:03:58,820
Men vet att vid
I slutet av terminen,

82
00:03:58,820 --> 00:04:02,270
alla sena psets kommer bara vara
automatiskt nollställs av datorn.

83
00:04:02,270 --> 00:04:04,490
>> Vi gör detta av två skäl.

84
00:04:04,490 --> 00:04:09,220
En, ibland får vi
ursäktas, liksom prostens ursäkter,

85
00:04:09,220 --> 00:04:10,762
senare att jag inte vet om ännu.

86
00:04:10,762 --> 00:04:13,761
Så vi vill se till att vi ska klassificera
allt bara i fall som jag är

87
00:04:13,761 --> 00:04:15,080
saknade en dekanus ursäkt.

88
00:04:15,080 --> 00:04:17,000
Och för det andra, kom
sinne, kan du fortfarande

89
00:04:17,000 --> 00:04:19,370
släppa en pset som
har full omfattning poäng.

90
00:04:19,370 --> 00:04:21,430
Och så vi vilja klass
alla dina psets bara

91
00:04:21,430 --> 00:04:24,730
att se till att din oscilloskops
där och du försöker dem.

92
00:04:24,730 --> 00:04:29,150
Så även om det är sent, kommer du fortfarande
få kredit för räckvidd punkter, tror jag.

93
00:04:29,150 --> 00:04:33,730
>> Så Sensmoralen i historien är, gör
att dina psets är i tid.

94
00:04:33,730 --> 00:04:38,350
Och om de inte är i på-tid,
vet att det inte är bra.

95
00:04:38,350 --> 00:04:41,678
Ja, innan jag går vidare, någon som har
frågor om pset synpunkter?

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

97
00:04:42,178 --> 00:04:43,630
>> PUBLIK: Sa du att vi
kan släppa en av de psets?

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

99
00:04:44,296 --> 00:04:47,050
Så det finns nio psets övergripande
under loppet av terminen.

100
00:04:47,050 --> 00:04:50,610
Och om du har räckvidd
points-- så räckvidd är bara,

101
00:04:50,610 --> 00:04:53,567
ganska mycket, är du försöker den
problem, du sätter i tid,

102
00:04:53,567 --> 00:04:56,150
visar du att du har
visade du har läst spec.

103
00:04:56,150 --> 00:04:57,191
Det är ganska mycket utrymme.

104
00:04:57,191 --> 00:04:59,370
Och om du uppfyller
scope punkter, vi

105
00:04:59,370 --> 00:05:03,360
kan släppa lägsta
en av fritt spelrum.

106
00:05:03,360 --> 00:05:06,790
Så det är i din fördel att
fylla i och prova varje pset.

107
00:05:06,790 --> 00:05:10,320
>> Även upload-- om ingen av
dem att fungera, ladda upp dem alla.

108
00:05:10,320 --> 00:05:13,711
Och sedan kommer vi förhoppningsvis att kunna
ge er några av dessa punkter tillbaka.

109
00:05:13,711 --> 00:05:14,210
Häftigt.

110
00:05:14,210 --> 00:05:16,780
Alla andra frågor?

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

112
00:05:17,840 --> 00:05:21,960
>> För det andra hours-- några kontor
snabba anteckningar om kontorstid.

113
00:05:21,960 --> 00:05:24,300
Så först, kom i början av veckan.

114
00:05:24,300 --> 00:05:26,909
Ingen är någonsin på
kontorstid på måndagar.

115
00:05:26,909 --> 00:05:28,700
Christabel kom till
kontorstid i natt.

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

117
00:05:29,691 --> 00:05:32,190
Och vad gjorde vi har på kontoret
timmar i natt, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> PUBLIK: Vi hade Glass.

119
00:05:33,020 --> 00:05:36,160
>> ANDI PENG: Så det är rätt, vi hade
Glass på kontorstid i går kväll.

120
00:05:36,160 --> 00:05:39,390
Även om jag inte kan lova er att
Vi kommer att ha glass på kontorstid

121
00:05:39,390 --> 00:05:43,230
varje vecka, vad jag kan lova dig
är att det kommer att finnas en signifikant

122
00:05:43,230 --> 00:05:45,380
bättre elev TA förhållande.

123
00:05:45,380 --> 00:05:47,650
Liksom legit, det är som 3-1.

124
00:05:47,650 --> 00:05:50,350
Medan kontrast som med
Torsdag, har du ca 150

125
00:05:50,350 --> 00:05:52,830
verkligen stressade barn och ingen Glass.

126
00:05:52,830 --> 00:05:55,360
Och det är inte produktivt för någon.

127
00:05:55,360 --> 00:05:58,730
Så Sensmoralen i historien är, kom tidigt
till kontorstid och bra saker

128
00:05:58,730 --> 00:06:00,310
kommer att hända.

129
00:06:00,310 --> 00:06:02,110
>> Dessutom kommer beredd att ställa frågor.

130
00:06:02,110 --> 00:06:03,200
Du vet?

131
00:06:03,200 --> 00:06:05,420
Oavsett vad resebyråerna, jag
tror, ​​har sagt,

132
00:06:05,420 --> 00:06:10,710
Vi har fått ett par studenter
som kommer på torsdag på, liksom, 10:50

133
00:06:10,710 --> 00:06:15,100
inte ha läst spec
vara som hjälp mig, hjälp mig.

134
00:06:15,100 --> 00:06:18,200
Tyvärr vid denna tidpunkt, det finns
inte mycket vi kan göra för att hjälpa dig.

135
00:06:18,200 --> 00:06:19,590
Så kom gärna i början av veckan.

136
00:06:19,590 --> 00:06:22,040
Kom tidigt till kontorstid.

137
00:06:22,040 --> 00:06:23,350
Kom beredd att ställa frågor.

138
00:06:23,350 --> 00:06:25,310
Se till att du, som
en student, är där

139
00:06:25,310 --> 00:06:27,620
du måste vara så att
Resebyråerna kan guida dig längs,

140
00:06:27,620 --> 00:06:32,850
vilket är vad kontorstid
bör tilldelas för.

141
00:06:32,850 --> 00:06:37,380
>> För det andra, så jag vet professorer
gillar att överraska oss med tester.

142
00:06:37,380 --> 00:06:39,439
Jag hade en professor som
som, omslag, förresten,

143
00:06:39,439 --> 00:06:41,230
kom ihåg att halva tiden
du har nästa måndag.

144
00:06:41,230 --> 00:06:42,855
Ja, jag visste inte om det midterm.

145
00:06:42,855 --> 00:06:45,630
Så jag kommer att vara att TA
som påminner dig allt frågesport

146
00:06:45,630 --> 00:06:47,270
0-- eftersom du vet, vi är CS.

147
00:06:47,270 --> 00:06:50,730
Nu när vi har gjort uppsättningar, får du
varför det är quiz 0, inte quiz 1, va?

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

149
00:06:51,320 --> 00:06:52,490
Åh, jag fick några skratt på att en.

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

151
00:06:53,120 --> 00:06:59,710
>> Så quiz 0 blir 14 oktober om
du är i måndag-onsdag sektionen

152
00:06:59,710 --> 00:07:02,920
och 15 oktober om du är i
tisdag-torsdag avsnitt.

153
00:07:02,920 --> 00:07:05,630
Detta gäller inte för
de av er vid Harvard

154
00:07:05,630 --> 00:07:10,350
who-- Jag tror att du kommer alla vara
ta dina frågesporter på den 14: e.

155
00:07:10,350 --> 00:07:13,560
>> Så ja, nästa vecka, om
David, i föreläsning, går,

156
00:07:13,560 --> 00:07:15,747
Ja, så om det
quiz nästa vecka, ni alla

157
00:07:15,747 --> 00:07:17,580
kommer inte bli chockad eftersom
du kom till avsnitt

158
00:07:17,580 --> 00:07:19,664
och du vet att din
quiz 0 i två veckor.

159
00:07:19,664 --> 00:07:21,580
Och vi ska ha recension
sessioner och allt.

160
00:07:21,580 --> 00:07:26,360
Så ingen oro
vara rädd för det.

161
00:07:26,360 --> 00:07:29,890
Eventuella frågor before-- frågor
på alla som rör logistiska problem,

162
00:07:29,890 --> 00:07:32,591
betygs, kontorstid, avsnitt?

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

164
00:07:33,090 --> 00:07:35,100
>> PUBLIK: Så testet är
kommer att vara under föreläsning?

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

166
00:07:35,766 --> 00:07:39,460
Så frågesport, tror jag, är 60
minuter tilldelade i denna tidslucka

167
00:07:39,460 --> 00:07:42,240
att du bara tar
i föreläsningssalen.

168
00:07:42,240 --> 00:07:44,810
Så du behöver inte komma in
på, som en slumpmässig 07:00.

169
00:07:44,810 --> 00:07:46,140
Allt är bra.

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

171
00:07:47,100 --> 00:07:50,060
Häftigt.

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

173
00:07:50,840 --> 00:07:54,330
Så vi kommer att
införa ett koncept för dig

174
00:07:54,330 --> 00:08:00,760
den här veckan att David har redan slag
av berörs i föreläsning i förra veckan.

175
00:08:00,760 --> 00:08:02,010
Det kallas GDB.

176
00:08:02,010 --> 00:08:05,570
Och hur många av er, medan
Under skriva dina psets,

177
00:08:05,570 --> 00:08:09,981
har märkt en stor knapp som säger
"Debug" på toppen av din IDE?

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

179
00:08:10,480 --> 00:08:13,770
Så nu ska vi faktiskt får gräva
mysterium vad den knappen faktiskt

180
00:08:13,770 --> 00:08:14,270
gör.

181
00:08:14,270 --> 00:08:16,790
Och jag garanterar dig, det är en
vacker, vacker sak.

182
00:08:16,790 --> 00:08:20,740
>> Så fram till nu, tror jag
Det har varit två saker

183
00:08:20,740 --> 00:08:23,320
studenter har varit typiskt
gör när felsökning psets.

184
00:08:23,320 --> 00:08:27,635
En, de antingen lägga in
printf () - så var några rader,

185
00:08:27,635 --> 00:08:29,760
de lägger i en printf () -
åh, vad är denna variabel?

186
00:08:29,760 --> 00:08:32,551
Åh, vad är denna variabel now--
och du typ av se progressionen

187
00:08:32,551 --> 00:08:33,940
av din kod som körs.

188
00:08:33,940 --> 00:08:37,030
Eller den andra metoden barn gör är
att de bara skriver det hela

189
00:08:37,030 --> 00:08:38,610
och sedan gå så här i slutet.

190
00:08:38,610 --> 00:08:39,970
Förhoppningsvis fungerar det.

191
00:08:39,970 --> 00:08:44,851
Jag garanterar dig, är bättre GDB
än båda dessa metoder.

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

193
00:08:45,350 --> 00:08:46,980
Så det här kommer att vara din nya bästa vän.

194
00:08:46,980 --> 00:08:51,780
Eftersom det är en vacker sak
som visuellt visar både

195
00:08:51,780 --> 00:08:54,850
vad din kod gör
vid en specifik punkt

196
00:08:54,850 --> 00:08:57,486
liksom vad alla dina
variabler bärande,

197
00:08:57,486 --> 00:08:59,610
precis vad deras värderingar är,
vid denna punkt.

198
00:08:59,610 --> 00:09:02,670
Och på det här sättet, kan du verkligen
ange brytpunkter i koden.

199
00:09:02,670 --> 00:09:04,350
Du kan gå igenom rad för rad.

200
00:09:04,350 --> 00:09:07,324
Och GDB kommer bara för
dig, visas för dig,

201
00:09:07,324 --> 00:09:09,490
vad alla dina variabler
är, vad de gör,

202
00:09:09,490 --> 00:09:10,656
vad som händer i koden.

203
00:09:10,656 --> 00:09:13,240
Och på ett sådant sätt, är det
så mycket lättare att se

204
00:09:13,240 --> 00:09:17,120
vad som händer i stället för printf-ing
eller skriva ner dina uttalanden.

205
00:09:17,120 --> 00:09:19,160
>> Så vi kommer att göra ett exempel på detta senare.

206
00:09:19,160 --> 00:09:20,660
Så detta verkar lite abstrakt.

207
00:09:20,660 --> 00:09:23,490
Inga bekymmer, ska vi göra exempel.

208
00:09:23,490 --> 00:09:29,170
Och så i huvudsak, de tre största,
mest använda funktioner som du behöver i GDB

209
00:09:29,170 --> 00:09:32,500
är nästa, steg över,
och Kliv in knapparna.

210
00:09:32,500 --> 00:09:34,860
Jag kommer att gå över
där, faktiskt, just nu.

211
00:09:34,860 --> 00:09:40,930
>> Så kan ni alla se att
eller ska jag in i en bit?

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

213
00:09:43,220 --> 00:09:44,470
I ryggen, kan du se det?

214
00:09:44,470 --> 00:09:45,730
Ska jag zooma in?

215
00:09:45,730 --> 00:09:46,480
Bara lite?

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

217
00:09:49,390 --> 00:09:50,280
Det går vi.

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

219
00:09:50,960 --> 00:09:57,000
>> Så jag har här, min
genomförande för giriga.

220
00:09:57,000 --> 00:10:01,430
Och medan en hel del av er skrev
giriga i while-slinga form-- att

221
00:10:01,430 --> 00:10:04,890
är ett fullt godtagbart sätt att göra
det-- ett annat sätt att göra det är att helt enkelt

222
00:10:04,890 --> 00:10:06,280
dela i modulo.

223
00:10:06,280 --> 00:10:09,290
För då kan du ha din
värde och sedan har din resten.

224
00:10:09,290 --> 00:10:11,150
Och då kan du bara
lägga ihop allt.

225
00:10:11,150 --> 00:10:13,390
Har logiken i det jag gör
här vettigt för alla,

226
00:10:13,390 --> 00:10:14,117
innan vi börjar?

227
00:10:14,117 --> 00:10:16,760

228
00:10:16,760 --> 00:10:17,980
Ungefär?

229
00:10:17,980 --> 00:10:18,710
Häftigt.

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

231
00:10:19,210 --> 00:10:21,290
Det är en ganska sexig pjäs
kod, skulle jag säga.

232
00:10:21,290 --> 00:10:23,502
Som jag sa, David, i
föreläsning, efter en stund,

233
00:10:23,502 --> 00:10:25,960
ni kommer att börja se kod
som något som är vackert.

234
00:10:25,960 --> 00:10:29,950
Och ibland när du ser vackra
kod, är det en underbar känsla.

235
00:10:29,950 --> 00:10:35,410
>> Så dock medan denna kod är mycket
vacker, det fungerar inte på rätt sätt.

236
00:10:35,410 --> 00:10:37,750
Så låt oss köra check50 på detta.

237
00:10:37,750 --> 00:10:39,440
Kontrollera 50 20-- oop.

238
00:10:39,440 --> 00:10:43,221

239
00:10:43,221 --> 00:10:43,720
2?

240
00:10:43,720 --> 00:10:44,990
Är det pset2?

241
00:10:44,990 --> 00:10:46,870
Yeah.

242
00:10:46,870 --> 00:10:47,520
Åh, pset1.

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

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

245
00:10:52,890 --> 00:10:53,900
Så vi kör check50.

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

247
00:11:01,550 --> 00:11:07,170
>> Och som ni kan se här,
det är inte ett par fall.

248
00:11:07,170 --> 00:11:10,165
Och för vissa av er, i
kurs för att göra dina problem uppsättningar,

249
00:11:10,165 --> 00:11:11,110
du är som, ah, varför det inte fungerar.

250
00:11:11,110 --> 00:11:13,318
Varför det fungerar för vissa
värden men inte för andra?

251
00:11:13,318 --> 00:11:17,760
Tja, GDB kommer att hjälpa dig att räkna
varför dessa ingångar inte fungerade.

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

253
00:11:18,320 --> 00:11:21,640
Så låt oss se, en av de
checkar jag misslyckas i check50

254
00:11:21,640 --> 00:11:24,920
var ingångsvärdet på 0,41.

255
00:11:24,920 --> 00:11:27,830
Så det rätta svaret att
Du bör få en fyra.

256
00:11:27,830 --> 00:11:33,090
Men i stället vad jag skriva ut
Detta är ett 3-n, som är felaktig.

257
00:11:33,090 --> 00:11:36,190
Så låt oss bara köra manuellt, bara
se till att check50 fungerar.

258
00:11:36,190 --> 00:11:36,940
Låt oss göra ./greedy.

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

260
00:11:40,130 --> 00:11:43,340
Oops, jag måste göra giriga.

261
00:11:43,340 --> 00:11:43,840
Det går vi.

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

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

264
00:11:46,950 --> 00:11:47,670
>> Hur mycket är skyldig?

265
00:11:47,670 --> 00:11:49,550
Låt oss göra 0,41.

266
00:11:49,550 --> 00:11:52,590
Och japp, ser vi här
att det är utmatning 3

267
00:11:52,590 --> 00:11:55,160
När det rätta svaret,
i själva verket borde vara fyra.

268
00:11:55,160 --> 00:12:01,460
Så låt oss gå in GDB och se hur vi
kan gå om fastställande av det här problemet.

269
00:12:01,460 --> 00:12:03,992
>> Så det första steget i
alltid felsökning din kod

270
00:12:03,992 --> 00:12:05,950
är att sätta en brytpunkt,
eller en punkt där du

271
00:12:05,950 --> 00:12:09,079
vill att datorn eller
debugger för att börja titta på.

272
00:12:09,079 --> 00:12:11,120
Så om du inte riktigt
vet vad ditt problem är,

273
00:12:11,120 --> 00:12:14,670
vanligtvis, den typiska sak som vi vill
göra är att ställa vår brytpunkt vid huvud.

274
00:12:14,670 --> 00:12:18,520
Så om ni kan se här
röda knappen just där,

275
00:12:18,520 --> 00:12:22,860
Japp, det var inställningen mig
brytpunkt för huvudfunktionen.

276
00:12:22,860 --> 00:12:24,130
Jag klickar på den.

277
00:12:24,130 --> 00:12:26,130
>> Och då kan jag gå upp till min Debug knappen.

278
00:12:26,130 --> 00:12:27,036
Jag slog den knappen.

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

280
00:12:31,710 --> 00:12:36,555
Låt mig in igen om jag kan.

281
00:12:36,555 --> 00:12:38,020
Det går vi.

282
00:12:38,020 --> 00:12:40,730
Så vi har här, en panel till höger.

283
00:12:40,730 --> 00:12:43,680
Jag är ledsen, killar i ryggen, du
kan inte riktigt se riktigt bra.

284
00:12:43,680 --> 00:12:49,090
Men i huvudsak alla
denna högra panelen gör

285
00:12:49,090 --> 00:12:53,130
är att hålla reda på både den markerade
linje, som är den kodrad

286
00:12:53,130 --> 00:12:56,640
att datorn är igång,
liksom alla dina variabler

287
00:12:56,640 --> 00:12:57,600
här nere.

288
00:12:57,600 --> 00:13:00,487
>> Så du har fått cent, mynt, n,
alla förklarats olika saker

289
00:13:00,487 --> 00:13:01,070
vid denna punkt.

290
00:13:01,070 --> 00:13:04,850
Inga problem, eftersom vi inte har faktiskt
initieras dem till några variabler än.

291
00:13:04,850 --> 00:13:07,200
Så i datorn,
dator är bara att se,

292
00:13:07,200 --> 00:13:14,376
åh, 32767 var den senast använda funktionen
av det minnesutrymme i min dator.

293
00:13:14,376 --> 00:13:16,000
Och så det är där cent för närvarande är.

294
00:13:16,000 --> 00:13:19,360
Men ingen att när du kör koden,
Det bör bli initierad.

295
00:13:19,360 --> 00:13:24,110
>> Så låt oss gå igenom, rad för
linje, vad som händer här.

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

297
00:13:25,350 --> 00:13:29,400
Så här uppe är de tre
knappar som jag förklarade bara.

298
00:13:29,400 --> 00:13:34,090
Du har Play eller Kör funktionen,
knappen, har du steg över knappen,

299
00:13:34,090 --> 00:13:36,600
och du har också steget in knappen.

300
00:13:36,600 --> 00:13:41,260
Och i huvudsak, alla tre
dem bara gå igenom din kod

301
00:13:41,260 --> 00:13:42,690
och göra olika saker.

302
00:13:42,690 --> 00:13:45,680
>> Så typiskt, när du felsökning,
Vi vill inte bara trycka Play,

303
00:13:45,680 --> 00:13:47,930
eftersom Play kommer bara köra
koden till slutet av det.

304
00:13:47,930 --> 00:13:49,070
Och då kommer du faktiskt inte
vet vad ditt problem

305
00:13:49,070 --> 00:13:51,432
är om du ställer in flera brytpunkter.

306
00:13:51,432 --> 00:13:53,890
Om du ställer in flera brytpunkter,
Det kommer bara automatiskt

307
00:13:53,890 --> 00:13:56,030
löpa från en brytpunkt,
till nästa, till nästa.

308
00:13:56,030 --> 00:13:58,030
Men i detta fall vi har
bara att man, eftersom vi

309
00:13:58,030 --> 00:13:59,970
vill arbeta vårt sätt
uppifrån ned till botten.

310
00:13:59,970 --> 00:14:04,830
Så vi kommer att ignorera den knappen
just nu för detta program.

311
00:14:04,830 --> 00:14:08,230
>> Så Step over funktion bara
steg över varje enda rad

312
00:14:08,230 --> 00:14:11,510
och talar om för dig vad
datorn gör.

313
00:14:11,510 --> 00:14:14,630
Step in funktionen går
i själva funktionen

314
00:14:14,630 --> 00:14:16,000
det är på din kodrad.

315
00:14:16,000 --> 00:14:19,070
Så till exempel, som printf (),
som är en funktion, eller hur?

316
00:14:19,070 --> 00:14:21,980
Om jag ville fysiskt steg
in printf () -funktionen,

317
00:14:21,980 --> 00:14:25,610
Jag skulle faktiskt gå in i bit
koden där printf () skrevs och se

318
00:14:25,610 --> 00:14:26,730
vad som händer där.

319
00:14:26,730 --> 00:14:29,924
>> Men typiskt, antar vi att
den kod som vi ger dig fungerar.

320
00:14:29,924 --> 00:14:31,340
Vi antar printf () fungerar.

321
00:14:31,340 --> 00:14:33,170
Vi antar att getInt () fungerar.

322
00:14:33,170 --> 00:14:35,170
Så det finns ingen anledning att
kliva in i dessa funktioner.

323
00:14:35,170 --> 00:14:37,170
Men om det finns funktioner
att du skriver själv

324
00:14:37,170 --> 00:14:39,060
som du vill kontrollera
reda på vad som händer,

325
00:14:39,060 --> 00:14:41,200
du skulle vilja steg
i denna funktion.

326
00:14:41,200 --> 00:14:43,940
>> Så just nu vi ska bara
att kliva över denna del av koden.

327
00:14:43,940 --> 00:14:44,485
Så låt oss se.

328
00:14:44,485 --> 00:14:46,547
Åh, skriva ut, "Oh hai, hur
mycket förändring är skyldig? "

329
00:14:46,547 --> 00:14:47,130
Vi bryr oss inte.

330
00:14:47,130 --> 00:14:49,830
Vi vet att det fungerar,
så vi kliver över den.

331
00:14:49,830 --> 00:14:53,290
>> Så n, som är vår flottör som
vi har initialized-- eller declared--

332
00:14:53,290 --> 00:14:56,810
upp på toppen, vi är nu
equaling att till getFloat ().

333
00:14:56,810 --> 00:14:57,810
Så låt oss kliva över det.

334
00:14:57,810 --> 00:14:59,580
Och vi ser på
botten här, programmet

335
00:14:59,580 --> 00:15:03,360
är vilket fick mig att mata in ett värde.

336
00:15:03,360 --> 00:15:08,580
Så låt oss mata in värde som vi vill
till testet här, vilket är 0,41.

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

338
00:15:09,160 --> 00:15:12,780
>> Så nu n-- gör ni se
här, vid bottom-- det är

339
00:15:12,780 --> 00:15:15,140
stored-- eftersom vi
har inte rundade ännu, är det

340
00:15:15,140 --> 00:15:19,540
lagras i detta som jätte
flottör som är 0,4099999996,

341
00:15:19,540 --> 00:15:22,550
som är tillräckligt nära vår
ändamål, just nu, till 0,41.

342
00:15:22,550 --> 00:15:26,090
Och sedan får vi se senare, när vi
fortsätta kliva över programmet,

343
00:15:26,090 --> 00:15:29,850
efter här, har n blivit
rundade och cent har blivit 41.

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

345
00:15:30,350 --> 00:15:32,230
Så vi vet att vår avrundning fungerar.

346
00:15:32,230 --> 00:15:34,700
Vi vet att vi har
rätt antal cent,

347
00:15:34,700 --> 00:15:36,990
så vi vet att det är
inte riktigt problemet.

348
00:15:36,990 --> 00:15:40,050
>> Så vi fortsätter att kliva
om i det här programmet.

349
00:15:40,050 --> 00:15:40,900
Vi går här.

350
00:15:40,900 --> 00:15:46,139
Och så efter den här kodraden, vi
bör veta hur många kvartal vi har.

351
00:15:46,139 --> 00:15:46,680
Vi kliver över.

352
00:15:46,680 --> 00:15:52,040
Och ni ser vi, i själva verket har en
kvartal eftersom vi har subtraheras 25

353
00:15:52,040 --> 00:15:53,790
från vår initiala värdet av 41.

354
00:15:53,790 --> 00:15:55,890
Och vi har 16 kvar för våra cent.

355
00:15:55,890 --> 00:15:58,830
>> Förstår alla hur
programmet stega igenom

356
00:15:58,830 --> 00:16:02,980
och varför cent har nu blivit 16
och varför nu, mynt har blivit en?

357
00:16:02,980 --> 00:16:04,610
Är alla som följer logiken?

358
00:16:04,610 --> 00:16:05,110
Häftigt.

359
00:16:05,110 --> 00:16:07,860
Så från och med denna punkt,
programmets arbete, rätt?

360
00:16:07,860 --> 00:16:09,797
Vi vet att det gör exakt
vad vi vill.

361
00:16:09,797 --> 00:16:11,880
Och det gjorde vi faktiskt inte
måste skriva ut, åh, vad

362
00:16:11,880 --> 00:16:14,430
är cent på denna punkt,
Vad är mynt på denna punkt.

363
00:16:14,430 --> 00:16:17,170
>> Vi fortsätter att gå igenom programmet.

364
00:16:17,170 --> 00:16:18,100
Kliva över.

365
00:16:18,100 --> 00:16:18,620
Häftigt.

366
00:16:18,620 --> 00:16:19,700
Vi går över Dimes.

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

368
00:16:20,200 --> 00:16:22,367
Vi ser att det har tagit
rabatt $ 0,10 för en krona.

369
00:16:22,367 --> 00:16:23,450
Och nu har vi två mynt.

370
00:16:23,450 --> 00:16:25,260
Det stämmer.

371
00:16:25,260 --> 00:16:31,555
>> Vi går över pennies och vi ser
att vi har kvar över cent.

372
00:16:31,555 --> 00:16:32,680
Hmm, det är konstigt.

373
00:16:32,680 --> 00:16:37,540
Här uppe på programmet, skulle jag
ha dras mina slantar.

374
00:16:37,540 --> 00:16:39,400
Kanske jag var bara inte
gör den linjen till höger.

375
00:16:39,400 --> 00:16:42,190
Och tyvärr, kan du se
här, eftersom vi vet

376
00:16:42,190 --> 00:16:44,360
att vi trappar
genom ledningarna 32 och 33,

377
00:16:44,360 --> 00:16:50,560
det är där vårt program
felaktigt hade variabler springa.

378
00:16:50,560 --> 00:16:55,136
Så vi kan se och se, oh,
Jag subtrahera cent här,

379
00:16:55,136 --> 00:16:57,010
men jag är faktiskt inte
lägga till min myntvärde.

380
00:16:57,010 --> 00:16:57,860
Jag lägger till cent.

381
00:16:57,860 --> 00:17:00,234
Och jag vill inte lägga till
cent, jag vill lägga till mynt.

382
00:17:00,234 --> 00:17:05,420
Så om vi ändrar det till mynt,
Vi har ett arbetsprogram.

383
00:17:05,420 --> 00:17:06,730
Jag kan köra check50.

384
00:17:06,730 --> 00:17:11,063
Du kan bara stänga av GDB rätt
här och kör sedan check50 igen.

385
00:17:11,063 --> 00:17:11,938
Jag kan bara göra detta.

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

387
00:17:14,822 --> 00:17:18,480
Jag måste göra giriga.

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

389
00:17:19,940 --> 00:17:22,819
Och här är det utskrift
ut det rätta svaret.

390
00:17:22,819 --> 00:17:26,569
>> Så när ni kan se, GDB
är ett riktigt kraftfullt verktyg

391
00:17:26,569 --> 00:17:29,940
för när vi har så mycket kod
pågår och så många variabler

392
00:17:29,940 --> 00:17:32,510
att det är svårt för oss, som
en människa, för att hålla reda på.

393
00:17:32,510 --> 00:17:35,360
Datorn, i GDB
debugger, har förmågan

394
00:17:35,360 --> 00:17:37,020
att hålla reda på allt.

395
00:17:37,020 --> 00:17:40,480
Jag vet, i Visionaire, ni förmodligen
kanske har drabbat vissa segmente fel

396
00:17:40,480 --> 00:17:43,150
eftersom du kör
out of bounds på din array.

397
00:17:43,150 --> 00:17:46,510
I exemplet på Caesar, det är
exakt vad jag har implementerat här.

398
00:17:46,510 --> 00:17:50,060
>> Så jag glömde att kontrollera
vad som skulle hända om jag

399
00:17:50,060 --> 00:17:52,510
behövde två kommandoradsargumenten.

400
00:17:52,510 --> 00:17:53,880
Jag bara inte sätta i denna kontroll.

401
00:17:53,880 --> 00:17:57,380
Och så om jag kör Debug-- jag in
min brytpunkt till höger där.

402
00:17:57,380 --> 00:17:58,055
Jag kör Debug.

403
00:17:58,055 --> 00:18:15,880

404
00:18:15,880 --> 00:18:16,550
>> OK.

405
00:18:16,550 --> 00:18:17,050
Yeah.

406
00:18:17,050 --> 00:18:20,350
Så egentligen var GDB tänkt
ha sagt mig det

407
00:18:20,350 --> 00:18:22,300
var en segmentering fel där.

408
00:18:22,300 --> 00:18:24,883
Jag vet inte vad som pågår
just där, men när jag körde det,

409
00:18:24,883 --> 00:18:25,590
Det fungerade.

410
00:18:25,590 --> 00:18:29,410
När du kör rader kod genom och
GDB kanske bara plötsligt sluta på dig,

411
00:18:29,410 --> 00:18:31,540
gå upp och se vad den röda felet är.

412
00:18:31,540 --> 00:18:33,930
Det kommer att berätta för er, hej, du
hade en segmentering fel,

413
00:18:33,930 --> 00:18:38,550
vilket innebär att du försökte komma åt
utrymme i en matris som inte existerade.

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

415
00:18:39,050 --> 00:18:43,280
>> Så i nästa problem
som denna vecka, ni

416
00:18:43,280 --> 00:18:45,600
kommer troligen att ha en hel del
variabler som flyter runt.

417
00:18:45,600 --> 00:18:48,560
Du kommer inte att vara säker på vad
de alla betyder vid en viss punkt.

418
00:18:48,560 --> 00:18:53,560
Så GDB kommer verkligen att hjälpa dig att räkna
reda på vad de är alla lika

419
00:18:53,560 --> 00:18:55,940
och att kunna se att visuellt.

420
00:18:55,940 --> 00:19:01,995
Är det någon förvirrad om hur
något av det fungerade?

421
00:19:01,995 --> 00:19:02,495
Häftigt.

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

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

424
00:19:10,620 --> 00:19:14,260
Så efter att vi
kommer att dyka rätt

425
00:19:14,260 --> 00:19:17,562
i är fyra olika
typer av slag för den här veckan.

426
00:19:17,562 --> 00:19:19,520
Hur många av er, första
av allt, innan vi börjar,

427
00:19:19,520 --> 00:19:23,020
har läst hela spec för pset3?

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

429
00:19:23,824 --> 00:19:24,740
Jag är stolt över er.

430
00:19:24,740 --> 00:19:29,110
Det är som att hälften av klassen, som
är betydligt mer än förra gången.

431
00:19:29,110 --> 00:19:33,950
>> Så det är bra, för när
vi talar om innehållet

432
00:19:33,950 --> 00:19:36,170
i lecture-- eller ledsen,
i section-- Jag gillar

433
00:19:36,170 --> 00:19:38,210
att relatera en hel del som
tillbaka till vad pset är

434
00:19:38,210 --> 00:19:40,210
och hur du vill
genomföra detta i din pset.

435
00:19:40,210 --> 00:19:42,400
Så om du kommer att ha
läs spec, det ska

436
00:19:42,400 --> 00:19:45,510
vara mycket lättare för dig att förstå
vad jag talar om när jag säger,

437
00:19:45,510 --> 00:19:48,720
oh hey, kan detta vara en riktigt
bra ställe för att genomföra den här typen.

438
00:19:48,720 --> 00:19:52,870
Så de av er som har läst
spec vet att som en del av pset,

439
00:19:52,870 --> 00:19:54,900
du kommer att behöva
skriva ett typ av sortering.

440
00:19:54,900 --> 00:19:58,670
Så detta kan vara till stor hjälp
för många av er idag.

441
00:19:58,670 --> 00:20:01,760
>> Så vi ska börja med,
huvudsak den mest enkel typ

442
00:20:01,760 --> 00:20:04,580
av sortering, val slag.

443
00:20:04,580 --> 00:20:06,800
Den typiska algoritm för
hur vi skulle gå om detta

444
00:20:06,800 --> 00:20:10,460
är-- David gick igenom alla dessa i
föreläsning, så jag ska snabbt röra sig längs

445
00:20:10,460 --> 00:20:13,900
här-- är i huvudsak, du
har en matris av värden.

446
00:20:13,900 --> 00:20:17,170
Och sedan hittar
minsta osorterade värde

447
00:20:17,170 --> 00:20:20,200
och du byta detta värde med
den första osorterade värde.

448
00:20:20,200 --> 00:20:22,700
Och då du bara fortsätta att upprepa
med resten av din lista.

449
00:20:22,700 --> 00:20:25,740
>> Och här är en visuell förklaring
av hur det skulle fungera.

450
00:20:25,740 --> 00:20:30,460
Så till exempel, om vi skulle börja
med en uppsättning av fem element, index

451
00:20:30,460 --> 00:20:35,910
0 till 4, med 3, 5, 2, 6, och 4 värden
placeras i array-- så just nu,

452
00:20:35,910 --> 00:20:38,530
Vi kommer bara att anta
att de är alla osorterade

453
00:20:38,530 --> 00:20:41,130
eftersom vi har inte testat något annat.

454
00:20:41,130 --> 00:20:44,130
>> Så hur ett urval sortera skulle
arbete är att det skulle först

455
00:20:44,130 --> 00:20:46,800
gå igenom helheten
av osorterade array.

456
00:20:46,800 --> 00:20:49,120
Det skulle plocka ut det minsta värdet.

457
00:20:49,120 --> 00:20:51,750
I detta fall 3, höger
nu, är den minsta.

458
00:20:51,750 --> 00:20:52,680
Det blir till 5.

459
00:20:52,680 --> 00:20:55,620
Nix, 5 inte är större than--
eller ledsen, inte mindre than-- 3.

460
00:20:55,620 --> 00:20:57,779
Så det minsta värdet är fortfarande 3.

461
00:20:57,779 --> 00:20:58,695
Och sedan får du 2.

462
00:20:58,695 --> 00:21:00,990
Datorn ser, oh, två är mindre än 3.

463
00:21:00,990 --> 00:21:02,750
2 måste nu vara det minsta värdet.

464
00:21:02,750 --> 00:21:06,630
Och så 2 swappar med det första värdet.

465
00:21:06,630 --> 00:21:10,702
>> Så efter ett pass, vi verkligen ser
att 2 och 3 byts.

466
00:21:10,702 --> 00:21:13,910
Och vi ska bara fortsätta att göra
detta igen med resten av matrisen.

467
00:21:13,910 --> 00:21:17,660
Så vi kommer att bara köra igenom
de sista fyra index i uppsättningen.

468
00:21:17,660 --> 00:21:20,670
Vi ser att 3 är
nästa minimivärdet.

469
00:21:20,670 --> 00:21:23,240
Så vi kommer att byta det med fyra.

470
00:21:23,240 --> 00:21:26,900
Och då vi bara kommer att hålla
löper genom tills slutligen du

471
00:21:26,900 --> 00:21:33,730
komma till en sorterad array där
2, 3, 4, 5, och 6 är alla sorterade.

472
00:21:33,730 --> 00:21:37,530
Har alla förstå logiken
om hur ett val Sortera fungerar?

473
00:21:37,530 --> 00:21:39,669
>> Du har bara någon sorts
av ett minimivärde.

474
00:21:39,669 --> 00:21:41,210
Du hålla reda på vad det är.

475
00:21:41,210 --> 00:21:45,170
Och när du hittar det, byta du det
med det första värdet i array--

476
00:21:45,170 --> 00:21:48,740
eller inte första value--
nästa värde i arrayen.

477
00:21:48,740 --> 00:21:50,150
Häftigt.

478
00:21:50,150 --> 00:21:55,460
>> Så när ni slags
såg från en kort glimt,

479
00:21:55,460 --> 00:21:58,450
vi kommer att pseudokod detta.

480
00:21:58,450 --> 00:22:02,510
Så om ni i ryggen vill
bilda en grupp, alla vid ett bord

481
00:22:02,510 --> 00:22:06,170
kan bilda en liten partner, jag kommer
för att ge dig killar som tre minuter

482
00:22:06,170 --> 00:22:08,190
att bara prata igenom
logiken, på engelska,

483
00:22:08,190 --> 00:22:14,161
hur vi skulle kunna genomföra
pseudokod att skriva ett urval slag.

484
00:22:14,161 --> 00:22:14,910
Och det finns godis.

485
00:22:14,910 --> 00:22:16,118
Kom upp och få godis.

486
00:22:16,118 --> 00:22:19,520
Om du är i ryggen och du vill
godis, kan jag kasta godis på dig.

487
00:22:19,520 --> 00:22:22,850
Egentligen gör du-- cool.

488
00:22:22,850 --> 00:22:23,552
Åh förlåt.

489
00:22:23,552 --> 00:22:26,751

490
00:22:26,751 --> 00:22:27,250
OK.

491
00:22:27,250 --> 00:25:23,880

492
00:25:23,880 --> 00:25:27,140
>> Så om vi vill, som
en klass, skriv pseudokod

493
00:25:27,140 --> 00:25:30,466
hur man kan närma sig
detta problem, bara välkommen.

494
00:25:30,466 --> 00:25:32,340
Jag ska bara gå runt och,
i ordning, frågar grupper

495
00:25:32,340 --> 00:25:35,065
för nästa rad av
vad vi borde göra.

496
00:25:35,065 --> 00:25:37,840
Så om ni vill starta
off, vad är det första

497
00:25:37,840 --> 00:25:40,600
att göra när du försöker
implementera ett sätt att lösa det här programmet

498
00:25:40,600 --> 00:25:43,480
att selektivt sortera en lista?

499
00:25:43,480 --> 00:25:46,349
Låt oss bara antar vi
har en matris, okej?

500
00:25:46,349 --> 00:25:49,088
>> PUBLIK: Du vill skapa några
sorts [OHÖRBAR] att du är

501
00:25:49,088 --> 00:25:50,420
som löper genom hela din samling.

502
00:25:50,420 --> 00:25:51,128
>> ANDI PENG: Rätt.

503
00:25:51,128 --> 00:25:54,100
Så du kommer att vilja upprepa
genom varje utrymme, eller hur?

504
00:25:54,100 --> 00:26:05,490
Så bra.

505
00:26:05,490 --> 00:26:08,600
Om ni vill ge mig
Nästa line-- ja, i ryggen.

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

507
00:26:11,414 --> 00:26:13,290
>> PUBLIK: Kontrollera dem
allt för de minsta.

508
00:26:13,290 --> 00:26:14,248
>> ANDI PENG: Det gå vi.

509
00:26:14,248 --> 00:26:17,438
Så vi vill gå igenom och kontrollera
se vad det minsta värdet är, eller hur?

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

511
00:26:22,110 --> 00:26:24,840
Jag kommer att förkorta det till "min."

512
00:26:24,840 --> 00:26:27,658
Vad vill ni göra efter
du har hittat det lägsta värdet?

513
00:26:27,658 --> 00:26:28,533
>> PUBLIK: [OHÖRBAR]

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

515
00:26:29,942 --> 00:26:33,150
ANDI PENG: Så du kommer att vilja
slå på den med den första i nämnda matris,

516
00:26:33,150 --> 00:26:33,650
höger?

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

518
00:26:45,120 --> 00:26:46,850
Det är början, jag kommer att säga.

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

520
00:26:47,220 --> 00:26:50,386
Så nu när du har bytt den första
en, vad vill du göra efter det?

521
00:26:50,386 --> 00:26:54,840
Så nu vet vi att detta här
måste vara det minsta värdet, eller hur?

522
00:26:54,840 --> 00:26:58,310
Då har du en ytterligare vila
av matrisen som är osorterade.

523
00:26:58,310 --> 00:27:01,569
Så vad du vill göra här, om du
killar vill ge mig nästa rad?

524
00:27:01,569 --> 00:27:04,610
PUBLIK: Så då du vill iterera
genom återstoden av uppsättningen.

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

526
00:27:05,276 --> 00:27:09,857
Och så vad iterera genom
sorts innebära att vi kommer förmodligen att behöva?

527
00:27:09,857 --> 00:27:10,440
Vilken typ of--

528
00:27:10,440 --> 00:27:12,057
>> Målgrupp: Åh, en ytterligare rörlig?

529
00:27:12,057 --> 00:27:13,890
ANDI PENG: Förmodligen
en annan för loop, eller hur?

530
00:27:13,890 --> 00:27:28,914
Så vi förmodligen kommer att vilja
att iterera through-- stor.

531
00:27:28,914 --> 00:27:31,830
Och då du kommer att gå tillbaka och
förmodligen kontrollera minsta igen,

532
00:27:31,830 --> 00:27:32,100
höger?

533
00:27:32,100 --> 00:27:34,975
Och du kommer att fortsätta att upprepa
detta, eftersom slingorna bara gå

534
00:27:34,975 --> 00:27:36,010
att hålla igång, eller hur?

535
00:27:36,010 --> 00:27:39,190
>> Så när ni kan se, vi
bara ha en allmän pseudokod

536
00:27:39,190 --> 00:27:41,480
om hur vi vill att det här programmet ska se ut.

537
00:27:41,480 --> 00:27:46,646
Denna iterate här, vad gör vi
vanligtvis måste skriva i vår kod

538
00:27:46,646 --> 00:27:49,270
Om vi ​​vill att iterera genom ett
matris, vilken typ av struktur?

539
00:27:49,270 --> 00:27:51,030
Jag tror Christabel
redan sagt det förut.

540
00:27:51,030 --> 00:27:51,500
>> PUBLIK: A för loop.

541
00:27:51,500 --> 00:27:52,160
>> ANDI PENG: A för loop?

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

543
00:27:52,770 --> 00:27:56,060
Så det här är förmodligen
kommer att vara en for-loop.

544
00:27:56,060 --> 00:27:59,240
Vad är en check här kommer att innebära?

545
00:27:59,240 --> 00:28:02,536
Normalt, om du vill kontrollera
om något är något else--

546
00:28:02,536 --> 00:28:03,270
>> PUBLIK: If.

547
00:28:03,270 --> 00:28:06,790
>> ANDI PENG: An om, eller hur?

548
00:28:06,790 --> 00:28:10,790
Och sedan swap här, vi ska
gå över senare, eftersom David

549
00:28:10,790 --> 00:28:12,770
gick igenom det i föreläsning också.

550
00:28:12,770 --> 00:28:14,580
Och sedan den andra iterate implies--

551
00:28:14,580 --> 00:28:15,120
>> PUBLIK: Another for-loop.

552
00:28:15,120 --> 00:28:16,745
>> ANDI PENG: --another for-loop, exakt.

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

554
00:28:19,870 --> 00:28:22,000
Så om vi letar
på detta på rätt sätt, vi

555
00:28:22,000 --> 00:28:24,680
kan se att vi är förmodligen
kommer att behöva en kapslad för loop

556
00:28:24,680 --> 00:28:28,330
med en villkorlig uppgift i det
och sedan en verklig bit kod som är

557
00:28:28,330 --> 00:28:31,360
kommer att byta värden.

558
00:28:31,360 --> 00:28:35,980
Så jag har bara allmänt skrivit
en pseudokoden här.

559
00:28:35,980 --> 00:28:38,910
Och sedan vi faktiskt kommer
fysiskt, som klass,

560
00:28:38,910 --> 00:28:40,700
försöka genomföra detta i dag.

561
00:28:40,700 --> 00:28:42,486
Låt oss gå tillbaka till denna IDE.

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

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

564
00:28:50,230 --> 00:28:51,754
Varför är det inte-- det är det.

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

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

567
00:28:55,834 --> 00:28:57,500
Tyvärr, låt mig försöka zooma in lite mer.

568
00:28:57,500 --> 00:28:59,310
Det går vi.

569
00:28:59,310 --> 00:29:05,060
Allt jag gör här är att jag har skapat
ett program som heter "urval / sort.c."

570
00:29:05,060 --> 00:29:10,860
Jag har skapat en rad nio
värden, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
För närvarande, som du kan
se, de är oordnad.

572
00:29:14,370 --> 00:29:17,880
n kommer att vara det antal som
säger mängden av värden

573
00:29:17,880 --> 00:29:18,920
du har i din samling.

574
00:29:18,920 --> 00:29:20,670
I det här fallet har vi nio värden.

575
00:29:20,670 --> 00:29:23,760
Och jag har precis fått en for-loop här
som skriver ut osorterade array.

576
00:29:23,760 --> 00:29:28,370
>> Och i slutet, har jag också fått en för
loop som bara skriver ut den igen.

577
00:29:28,370 --> 00:29:32,070
Så teoretiskt, om programmet
fungerar korrekt, i slutet,

578
00:29:32,070 --> 00:29:35,670
bör du se en tryckt for-loop
i vilken en, två, tre, fyra, fem, sex, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 är alla korrekt i ordning.

580
00:29:39,310 --> 00:29:43,410
>> Så vi har fått vår pseudokod här.

581
00:29:43,410 --> 00:29:46,090
Finns det någon som vill att-- jag bara
kommer att gå be om volunteers--

582
00:29:46,090 --> 00:29:49,540
berätta exakt vad jag ska skriva om
Vi vill i första hand bara iterera

583
00:29:49,540 --> 00:29:52,840
genom början av denna samling?

584
00:29:52,840 --> 00:29:55,204
Vad är kodraden jag
förmodligen kommer att behöva här?

585
00:29:55,204 --> 00:29:56,990
>> PUBLIK: [OHÖRBAR]

586
00:29:56,990 --> 00:29:59,010
>> ANDI PENG: Ja, känner
gratis att-- ledsen, du

587
00:29:59,010 --> 00:30:02,318
behöver inte stå up-- känsla
fri att höja rösten lite.

588
00:30:02,318 --> 00:30:08,190
>> PUBLIK: För int i lika 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI PENG: Ja, bra.

590
00:30:10,690 --> 00:30:15,220
>> PUBLIK: i är mindre än array längd.

591
00:30:15,220 --> 00:30:19,630
>> ANDI PENG: Så kom
sinne här, eftersom vi

592
00:30:19,630 --> 00:30:23,060
inte har en funktion som
berättar längden på en array,

593
00:30:23,060 --> 00:30:25,790
vi redan har en
värde som lagrar det.

594
00:30:25,790 --> 00:30:27,920
Höger?

595
00:30:27,920 --> 00:30:31,010
En annan sak att hålla
i mind-- i en gruppering

596
00:30:31,010 --> 00:30:33,940
nio värden, vilka är index?

597
00:30:33,940 --> 00:30:38,720
Låt oss bara säga denna uppsättning var 0-3.

598
00:30:38,720 --> 00:30:41,500
Du ser att den sista
index är faktiskt tre.

599
00:30:41,500 --> 00:30:45,530
Det är inte 4, även om det finns
fyra värdena i gruppen.

600
00:30:45,530 --> 00:30:49,866
>> Så här måste vi vara mycket försiktiga
av vad vårt villkor för längden

601
00:30:49,866 --> 00:30:50,490
det kommer bli.

602
00:30:50,490 --> 00:30:51,948
>> PUBLIK: Skulle det inte vara n minus 1?

603
00:30:51,948 --> 00:30:54,440
ANDI PENG: Det kommer
n minus 1, exakt.

604
00:30:54,440 --> 00:30:57,379
Låter det vettigt, varför
Det är n minus 1, alla?

605
00:30:57,379 --> 00:30:58,920
Det beror på arrayer är noll indexeras.

606
00:30:58,920 --> 00:31:02,010
De börjar på 0 och köra upp till n minus 1.

607
00:31:02,010 --> 00:31:03,210
Ja, det är lite knepigt.

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

609
00:31:03,730 --> 00:31:05,929
Och då--

610
00:31:05,929 --> 00:31:08,054
PUBLIK: Isnt'1 som
redan tagit hand om men,

611
00:31:08,054 --> 00:31:11,400
genom att bara inte säga "mindre än eller
lika med "och bara säga" mindre än? "

612
00:31:11,400 --> 00:31:13,108
>> ANDI PENG: Det är en
riktigt bra fråga.

613
00:31:13,108 --> 00:31:13,630
Så ja.

614
00:31:13,630 --> 00:31:17,410
Men också, det sätt som vi är
genomförandet av kontroll höger,

615
00:31:17,410 --> 00:31:19,120
du behöver för att jämföra två värden.

616
00:31:19,120 --> 00:31:21,009
Så du verkligen vill
lämna "till" tom.

617
00:31:21,009 --> 00:31:23,050
För om du jämför
här, du kommer inte

618
00:31:23,050 --> 00:31:25,530
har något efter det
att jämföra med, eller hur?

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

620
00:31:27,460 --> 00:31:29,297
Så jag ++.

621
00:31:29,297 --> 00:31:30,380
Låt oss lägga våra parentes.

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

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

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

625
00:31:34,710 --> 00:31:39,117
Så vi har början
av vår yttre slinga.

626
00:31:39,117 --> 00:31:41,450
Så nu vill vi förmodligen
skapa en variabel för att hålla

627
00:31:41,450 --> 00:31:43,085
reda på det minsta värdet, eller hur?

628
00:31:43,085 --> 00:31:45,751
Finns det någon som vill ge mig
kodrad som skulle göra det?

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

630
00:31:48,700 --> 00:31:53,570
Vad behöver vi om vi ska
att vilja lagra något?

631
00:31:53,570 --> 00:31:55,047
>> Höger.

632
00:31:55,047 --> 00:31:57,630
Kanske ett bättre namn för att
skulle be-- "temp" helt works--

633
00:31:57,630 --> 00:32:00,655
kanske en mer passande namnet skulle vara,
om vi vill att minsta value--

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

635
00:32:01,624 --> 00:32:02,790
ANDI PENG: min, det går vi.

636
00:32:02,790 --> 00:32:05,230
min skulle vara bra.

637
00:32:05,230 --> 00:32:08,340
Och så här, vad gör vi
vill initiera den till?

638
00:32:08,340 --> 00:32:09,620
Detta är lite knepigt.

639
00:32:09,620 --> 00:32:13,580
Eftersom just nu på
i början av denna array,

640
00:32:13,580 --> 00:32:15,730
du inte har tittat på något, eller hur?

641
00:32:15,730 --> 00:32:19,200
Så vad, automatiskt, om
vi är bara på i lika med 0,

642
00:32:19,200 --> 00:32:22,302
Vad vill vi initiera
vår första minimivärde till?

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

644
00:32:22,802 --> 00:32:24,790
ANDI Peng: Jag, precis.

645
00:32:24,790 --> 00:32:27,040
Christabel, varför vill vi
att initiera det i?

646
00:32:27,040 --> 00:32:28,510
>> Målgrupp: Jo, ja,
Vi börjar med 0.

647
00:32:28,510 --> 00:32:31,660
Så eftersom vi har inget att jämföra
det kommer minst hamna 0.

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

649
00:32:32,451 --> 00:32:34,400
Så hon är exakt rätt.

650
00:32:34,400 --> 00:32:36,780
Eftersom vi har faktiskt inte
tittat på något ännu,

651
00:32:36,780 --> 00:32:38,680
vi vet inte vad vår minimivärde är.

652
00:32:38,680 --> 00:32:41,960
Vi vill bara initiera den till
i, som för närvarande är just här.

653
00:32:41,960 --> 00:32:44,750
Och när vi fortsätter att
flytta ner denna uppsättning,

654
00:32:44,750 --> 00:32:48,122
vi får se att med varje
extra pass, jag ökar.

655
00:32:48,122 --> 00:32:49,830
Och så på den punkten,
Jag är förmodligen kommer

656
00:32:49,830 --> 00:32:52,329
att vilja vara det minsta,
eftersom det kommer att bli allt

657
00:32:52,329 --> 00:32:54,520
är början av osorterade array.

658
00:32:54,520 --> 00:32:55,270
Häftigt.

659
00:32:55,270 --> 00:32:58,720
>> Så nu vill vi att lägga
en for-loop här som är

660
00:32:58,720 --> 00:33:03,225
kommer att iterera igenom
osorterade, eller resten av denna samling.

661
00:33:03,225 --> 00:33:05,808
Finns det någon som vill ge mig en
kodrad som skulle göra det?

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

663
00:33:08,870 --> 00:33:11,330
Hint-- vad behöver vi här nere?

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

665
00:33:17,320 --> 00:33:18,820
Vad kommer att gå i detta för loop?

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

667
00:33:19,465 --> 00:33:21,590
PUBLIK: Så vi skulle vilja
har en annan heltal,

668
00:33:21,590 --> 00:33:25,080
eftersom vi kör igenom resten
av matris i stället för den i:, så kanske

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

670
00:33:25,760 --> 00:33:27,301
>> ANDI PENG: Ja, låter j bra för mig.

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

672
00:33:27,850 --> 00:33:33,930
>> PUBLIK: Så skulle vara i plus 1, eftersom
du börjar på nästa värde.

673
00:33:33,930 --> 00:33:40,395
Och sedan till end-- så igen, j
mindre än n minus 1, och sedan j ++.

674
00:33:40,395 --> 00:33:41,103
ANDI PENG: Great.

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

676
00:33:48,510 --> 00:33:52,750
>> Och sedan i här, vi kommer att vilja
att kontrollera om våra villkor är uppfyllt,

677
00:33:52,750 --> 00:33:53,250
höger?

678
00:33:53,250 --> 00:33:55,740
Eftersom du vill
ändra det minsta värdet

679
00:33:55,740 --> 00:33:58,700
om det är faktiskt mindre än vad
du jämför det till, eller hur?

680
00:33:58,700 --> 00:34:01,146
Så vad ska vi ha här?

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

682
00:34:04,160 --> 00:34:04,897
Kontrollera att se.

683
00:34:04,897 --> 00:34:06,730
Vilken typ av uttalande
vi förmodligen kommer

684
00:34:06,730 --> 00:34:08,389
ti vill använda om vi
vill kontrollera något?

685
00:34:08,389 --> 00:34:09,360
>> PUBLIK: En if-sats.

686
00:34:09,360 --> 00:34:10,485
>> ANDI PENG: En if-sats.

687
00:34:10,485 --> 00:34:13,155
Så if-- och vad som kommer att bli
under förutsättning att vi vill ha inne

688
00:34:13,155 --> 00:34:13,988
av vår if?

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

690
00:34:18,255 --> 00:34:22,960
>> PUBLIK: Om värdet på j
är mindre än värdet av I--

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

692
00:34:24,600 --> 00:34:27,480
Så if-- så denna array kallas "array."

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

694
00:34:27,980 --> 00:34:30,465
Så om array-- vad var det?

695
00:34:30,465 --> 00:34:31,090
Säga det igen.

696
00:34:31,090 --> 00:34:39,590
>> Publik: Om matris-j är mindre än
array-i, då skulle vi ändra min.

697
00:34:39,590 --> 00:34:41,590
Så min skulle vara j.

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

699
00:34:44,590 --> 00:34:47,249
>> ANDI PENG: Låter det vettigt?

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

701
00:34:48,670 --> 00:34:52,929
Och nu här nere, vi faktiskt
vill genomföra swap, eller hur?

702
00:34:52,929 --> 00:34:58,285
Så minns i föreläsning, att David, när
han försökte byta the-- vad var

703
00:34:58,285 --> 00:34:59,996
det-- apelsinjuice och milk--

704
00:34:59,996 --> 00:35:01,150
>> PUBLIK: Det var brutto.

705
00:35:01,150 --> 00:35:02,816
>> ANDI PENG: Ja, det var typ av brutto.

706
00:35:02,816 --> 00:35:05,310
Men det var en ganska bra
koncept som visar tiden.

707
00:35:05,310 --> 00:35:08,430
Så tänk på dina värden här.

708
00:35:08,430 --> 00:35:10,794
Du har en array
av min, en matris av i,

709
00:35:10,794 --> 00:35:12,460
eller vad vi försökte byta här.

710
00:35:12,460 --> 00:35:15,310
Och du förmodligen inte kan hälla dem i
varandra på samma gång, eller hur?

711
00:35:15,310 --> 00:35:17,180
Så vad ska vi
att behöva skapa här

712
00:35:17,180 --> 00:35:19,126
För att byta värden på rätt sätt?

713
00:35:19,126 --> 00:35:19,820
>> PUBLIK: En temporär variabel.

714
00:35:19,820 --> 00:35:21,370
>> ANDI Peng: En temporär variabel.

715
00:35:21,370 --> 00:35:22,570
Så låt oss göra int temp.

716
00:35:22,570 --> 00:35:25,681
Se detta skulle vara en bättre
tid att-- whoa, vad var det?

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

718
00:35:26,180 --> 00:35:29,800
Så detta skulle ha varit en bättre
tid att namnge variabeln "temp."

719
00:35:29,800 --> 00:35:30,730
Så låt oss göra int temp.

720
00:35:30,730 --> 00:35:32,563
Vad ska vi
inställd temp lika med här?

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

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

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

724
00:35:38,508 --> 00:35:39,716
ANDI PENG: Det är lite knepigt.

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

726
00:35:43,110 --> 00:35:44,880
Det faktiskt ingen roll i slutändan.

727
00:35:44,880 --> 00:35:47,690
Det spelar ingen roll vad
ordning du väljer att byta in

728
00:35:47,690 --> 00:35:50,862
så länge du gör att du är
hålla reda på vad du byta.

729
00:35:50,862 --> 00:35:52,250
>> Publik: Det kan vara matris-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI PENG: Ja, låt oss göra array-i.

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

732
00:35:55,950 --> 00:35:59,305
Och vad är nästa rad
kod vi vill ha här?

733
00:35:59,305 --> 00:36:00,680
PUBLIK: array-i lika array-j.

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

735
00:36:07,154 --> 00:36:08,070
ANDI PENG: Och slutligen?

736
00:36:08,070 --> 00:36:12,070
PUBLIK: array-j är lika med array-i.

737
00:36:12,070 --> 00:36:14,525
Målgrupp: Eller array-j jämlikar
matris-temp-- eller, temp.

738
00:36:14,525 --> 00:36:17,135

739
00:36:17,135 --> 00:36:19,430
>> ANDI PENG: OK.

740
00:36:19,430 --> 00:36:21,510
Så låt oss köra det här och se
om det kommer att fungera.

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

742
00:36:37,520 --> 00:36:39,335
Var är det som händer?

743
00:36:39,335 --> 00:36:40,210
Åh, det är ett problem.

744
00:36:40,210 --> 00:36:44,320
Se på rad 40, vi är
försöker använda array-j?

745
00:36:44,320 --> 00:36:47,022
Men varifrån kommer j finns bara i?

746
00:36:47,022 --> 00:36:48,402
>> PUBLIK: I for-slingan.

747
00:36:48,402 --> 00:36:49,110
ANDI PENG: Rätt.

748
00:36:49,110 --> 00:36:51,730
Så vad ska vi göra?

749
00:36:51,730 --> 00:36:53,170
>> PUBLIK: Definiera det utanför the--

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

751
00:36:57,777 --> 00:37:00,610
Målgrupp: Ja, jag antar att du har
att använda en annan if-sats, eller hur?

752
00:37:00,610 --> 00:37:05,230
Så liknande, om minimum--
okej, låt mig tänka.

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

754
00:37:08,170 --> 00:37:09,990
>> ANDI Peng: Killar, försök
att ta en titt Låt oss

755
00:37:09,990 --> 00:37:11,270
se, vad är något som vi kan göra här?

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

757
00:37:11,811 --> 00:37:15,900
Så om minimi inte är lika
j-- så om den minsta är fortfarande jag--

758
00:37:15,900 --> 00:37:17,570
då skulle vi inte behöva byta.

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

760
00:37:22,450 --> 00:37:24,712
>> ANDI PENG: Betyder det lika i?

761
00:37:24,712 --> 00:37:25,920
Vad vill du säga här?

762
00:37:25,920 --> 00:37:30,494
>> PUBLIK: Eller ja, om
minimi inte är lika i, ja.

763
00:37:30,494 --> 00:37:39,627

764
00:37:39,627 --> 00:37:40,210
ANDI PENG: OK.

765
00:37:40,210 --> 00:37:42,040
Tja det löser, typ av våra problem.

766
00:37:42,040 --> 00:37:47,265
Men som fortfarande inte löser
problemet med vad som händer om j-- sedan j

767
00:37:47,265 --> 00:37:49,890
existerar inte utanför den, vad
vill du att vi vill göra med det?

768
00:37:49,890 --> 00:37:50,698
Förklara det utanför?

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

770
00:37:59,410 --> 00:38:02,730
Låt oss försöka köra detta.

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

772
00:38:04,435 --> 00:38:06,200
Vår typ fungerar inte.

773
00:38:06,200 --> 00:38:10,060
>> Som ni kan se, vår första
array hade dessa värden.

774
00:38:10,060 --> 00:38:14,800
Och efteråt borde ha
varit i en, två, tre, fyra, fem, sex, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
Dess inte fungerar.

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

777
00:38:16,030 --> 00:38:17,184
Vad gör vi?

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

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

780
00:38:21,787 --> 00:38:23,370
ANDI PENG: Okej, kan vi prova det.

781
00:38:23,370 --> 00:38:25,030
Vi kan felsöka.

782
00:38:25,030 --> 00:38:26,042
Zooma ut en bit.

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

784
00:38:31,177 --> 00:38:33,656
Låt oss ställa vår brytpunkt.

785
00:38:33,656 --> 00:38:37,280
Låt oss gå like-- OK.

786
00:38:37,280 --> 00:38:40,444
>> Så eftersom vi redan vet att
dessa rader, 15 till 22,

787
00:38:40,444 --> 00:38:43,610
är working-- eftersom allt jag gör är
bara iteration genom och printing--

788
00:38:43,610 --> 00:38:45,406
Jag kan gå vidare och hoppa över det.

789
00:38:45,406 --> 00:38:47,280
Låt oss börja på linje 25.

790
00:38:47,280 --> 00:38:48,712
Oop, låt mig få bli av med det.

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

792
00:38:51,598 --> 00:38:54,057
>> PUBLIK: Så brytpunkten är
där felsökning börjar?

793
00:38:54,057 --> 00:38:54,890
ANDI PENG: Eller stannar.

794
00:38:54,890 --> 00:38:55,670
PUBLIK: Eller stannar.

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

796
00:38:55,930 --> 00:38:58,640
Du kan ställa in flera brytpunkter och
den kan bara hoppa från en till den andra.

797
00:38:58,640 --> 00:39:01,590
Men i detta fall vi inte vet
där felet händer.

798
00:39:01,590 --> 00:39:03,780
Så vi vill bara
börja från toppen och nedåt.

799
00:39:03,780 --> 00:39:05,020
Japp.

800
00:39:05,020 --> 00:39:05,550
OK.

801
00:39:05,550 --> 00:39:08,460
>> Så här linjen här, kan vi kliva in.

802
00:39:08,460 --> 00:39:11,499
Du kan se här nere,
vi har en matris.

803
00:39:11,499 --> 00:39:13,290
De är de värden
som är i gruppen.

804
00:39:13,290 --> 00:39:16,360
Ser du det, hur index 0, det
motsvarar value-- oh,

805
00:39:16,360 --> 00:39:17,526
Jag ska försöka att zooma in.

806
00:39:17,526 --> 00:39:20,650
Tyvärr, det är verkligen svårt
att see-- vid fältindex 0,

807
00:39:20,650 --> 00:39:24,090
vi har ett värde av 4 och
då så vidare och så vidare.

808
00:39:24,090 --> 00:39:25,670
Vi har våra lokala variabler.

809
00:39:25,670 --> 00:39:28,570
Just nu jag är lika med
0, som vi vill att det ska vara.

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

811
00:39:31,540 --> 00:39:33,690
>> Och så låt oss hålla stega igenom.

812
00:39:33,690 --> 00:39:36,850
Vår minsta är lika med 0,
som vi vill också att det ska vara.

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

814
00:39:39,470 --> 00:39:45,560
Och sedan går vi vår andra för
slinga, om matris-j är mindre än matris-i,

815
00:39:45,560 --> 00:39:46,380
vilket det inte var.

816
00:39:46,380 --> 00:39:48,130
Så såg du hur
som hoppade över det?

817
00:39:48,130 --> 00:39:52,430
>> PUBLIK: Så bör if
minimum, allt that-- bör inte det

818
00:39:52,430 --> 00:39:55,424
vara inne den första för loop?

819
00:39:55,424 --> 00:39:57,340
ANDI PENG: Nej, eftersom
du fortfarande vill testa.

820
00:39:57,340 --> 00:40:00,329
Du vill göra en jämförelse varje
tid, även efter att du kör igenom den.

821
00:40:00,329 --> 00:40:02,620
Du vill inte bara göra det
på den första genomslaget.

822
00:40:02,620 --> 00:40:05,240
Du vill göra det med
varje extra pass igen.

823
00:40:05,240 --> 00:40:07,198
Så du vill söka efter
ditt tillstånd inuti.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Så vi ska bara
hålla igång igenom här.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Jag ska ge er en ledtråd.

828
00:40:18,420 --> 00:40:23,910
Det har att göra med det faktum att när
du kontrollera din villkorligt,

829
00:40:23,910 --> 00:40:26,600
du inte kontrollera
för rätt index.

830
00:40:26,600 --> 00:40:32,510
Så just nu är du kontroll av
array index för j är mindre än array

831
00:40:32,510 --> 00:40:33,970
index på i.

832
00:40:33,970 --> 00:40:36,580
Men vad gör du uppe på
början av for-slingan?

833
00:40:36,580 --> 00:40:38,260
Är du inte ställa j lika med i?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Ja, så kan vi faktiskt
avsluta debugger här.

836
00:40:45,415 --> 00:40:47,040
Så låt oss ta en titt på vår pseudokod.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- vi ska
börjar på i lika med 0.

839
00:40:52,580 --> 00:40:54,760
Vi kommer att gå upp till n minus 1.

840
00:40:54,760 --> 00:40:58,040
Låt oss kolla, vi har det rätt?

841
00:40:58,040 --> 00:40:59,580
Japp, det var rätt.

842
00:40:59,580 --> 00:41:02,080
>> Så då inne här, vi är
kommer att skapa ett minimivärde

843
00:41:02,080 --> 00:41:03,630
och uppsättning som är lika med i.

844
00:41:03,630 --> 00:41:04,950
Gjorde vi göra det?

845
00:41:04,950 --> 00:41:06,270
Japp, gjorde det.

846
00:41:06,270 --> 00:41:10,430
Nu i vår inre for-loop, vi är
kommer att göra j lika i till n minus 1.

847
00:41:10,430 --> 00:41:11,950
Gjorde vi göra det?

848
00:41:11,950 --> 00:41:15,540
I själva verket gjorde vi det.

849
00:41:15,540 --> 00:41:19,922
>> Så dock vad vi jämföra här?

850
00:41:19,922 --> 00:41:20,925
>> PUBLIK: j plus 1.

851
00:41:20,925 --> 00:41:21,716
ANDI PENG: Exakt.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
Och då du kommer att vilja ställa
din minsta lika med j plus 1 också.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Så jag gick igenom det riktigt snabbt.

856
00:41:32,640 --> 00:41:36,190
Gör ni förstå
varför det är j plus 1?

857
00:41:36,190 --> 00:41:36,890
OK.

858
00:41:36,890 --> 00:41:40,700
>> Så i din samling, i
din första passera,

859
00:41:40,700 --> 00:41:44,850
din för loop, för int
Jag är lika med 0, låt oss bara

860
00:41:44,850 --> 00:41:46,740
antar att det har inte ändrats ännu.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Vi har en matris med, helt,
bara fyra osorterade element, eller hur?

863
00:41:56,760 --> 00:42:00,760
Så vi vill initiera jag lika med 0.

864
00:42:00,760 --> 00:42:03,650
Och jag kommer att bara
köra igenom detta slinga.

865
00:42:03,650 --> 00:42:08,560
Och så i det första passet, kommer vi
att initiera en variabel som heter "min"

866
00:42:08,560 --> 00:42:11,245
som också är lika med i, eftersom
vi har inte ett minimivärde.

867
00:42:11,245 --> 00:42:12,870
Så det är för närvarande lika med 0 också.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
Och då kommer vi att gå igenom.

870
00:42:17,640 --> 00:42:19,270
Och vi vill iterera igen.

871
00:42:19,270 --> 00:42:22,900
Nu när vi har hittat vad vår lägsta
vill säga, vi vill iterera genom

872
00:42:22,900 --> 00:42:25,190
igen för att se om det är en jämförelse, eller hur?

873
00:42:25,190 --> 00:42:40,440
Så j, här, kommer
till lika i, som är 0.

874
00:42:40,440 --> 00:42:46,320
Och sedan om array j plus i, som
är den som är nästa över, som mindre

875
00:42:46,320 --> 00:42:49,270
än vad din nuvarande minimi
värde är, du vill byta.

876
00:42:49,270 --> 00:42:56,850
>> Så låt oss bara säga att vi har
fick, liksom, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Just nu är jag lika med
0 och j är lika med 0.

878
00:43:01,610 --> 00:43:05,210
Och det är vår minimivärde.

879
00:43:05,210 --> 00:43:09,950
Om matris-j plus jag-- så om en
det är efter den vi tittar på

880
00:43:09,950 --> 00:43:13,450
är större än den föregående,
det kommer att bli ett minimum.

881
00:43:13,450 --> 00:43:18,120
>> Så här ser vi att 5
inte mindre än så.

882
00:43:18,120 --> 00:43:19,730
Så det kommer att vara 5.

883
00:43:19,730 --> 00:43:23,580
Vi ser att en är mindre än 2, eller hur?

884
00:43:23,580 --> 00:43:32,970
Så nu vet vi att vår minsta är
kommer att vara indexvärdet vid 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Yeah?

886
00:43:34,030 --> 00:43:39,170
Och sedan när du kommer ner hit,
du kan byta korrekta värden.

887
00:43:39,170 --> 00:43:42,610
>> Så när ni var bara med j
innan, var du inte tittar på en

888
00:43:42,610 --> 00:43:43,260
efter det.

889
00:43:43,260 --> 00:43:44,520
Du tittar på
samma värde, vilket

890
00:43:44,520 --> 00:43:46,290
Därför bara inte gjorde någonting.

891
00:43:46,290 --> 00:43:49,721
Innebär det vettigt att alla,
varför vi behövde det plus en där?

892
00:43:49,721 --> 00:43:50,220
OK.

893
00:43:50,220 --> 00:43:53,345
Nu ska vi bara gå igenom den för att göra
Se till att resten av koden är korrekt.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Varför är det som händer?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, det är min rätt här.

898
00:44:16,364 --> 00:44:17,780
Vi jämförde fel värde.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Å nej.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Oh ja, här nere var vi
byta fel värden.

903
00:44:33,482 --> 00:44:34,940
Eftersom vi tittar på i och j.

904
00:44:34,940 --> 00:44:36,440
De är de som vi checkar.

905
00:44:36,440 --> 00:44:39,160
Vi vill faktiskt att byta
minimum, den nuvarande lägsta,

906
00:44:39,160 --> 00:44:40,550
med vad det utanför är.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
Och som ni kan se ner
Här har vi en sorterad array.

909
00:45:05,402 --> 00:45:07,110
Det hade bara att göra med
det faktum att när

910
00:45:07,110 --> 00:45:09,350
vi kontrollera
värderingar vi jämföra,

911
00:45:09,350 --> 00:45:11,226
Vi var inte ute på de rätta värderingarna.

912
00:45:11,226 --> 00:45:13,850
Vi letade på samma en
här, faktiskt inte byta det.

913
00:45:13,850 --> 00:45:17,135
Du måste titta på en nästa
till det och sedan kan du byta.

914
00:45:17,135 --> 00:45:19,260
Så det är vad som var typ av
buggning vår kod innan.

915
00:45:19,260 --> 00:45:22,460
Och vad jag gjorde här är allt
debugger kunde ha gjort för dig

916
00:45:22,460 --> 00:45:23,810
Jag gjorde bara det på
ombord, eftersom det är lättare

917
00:45:23,810 --> 00:45:26,320
att se stället för att försöka
för att zooma in på debugger.

918
00:45:26,320 --> 00:45:29,391
Innebär det vettigt att alla?

919
00:45:29,391 --> 00:45:29,890
Häftigt.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Okej.

922
00:45:35,410 --> 00:45:41,070
Vi kan gå vidare till att tala om
asymptotisk notation, som

923
00:45:41,070 --> 00:45:44,580
är bara ett finare sätt att säga
drifttider av alla dessa typer.

924
00:45:44,580 --> 00:45:47,650
Så jag vet David, i föreläsning,
berört drifttider.

925
00:45:47,650 --> 00:45:52,124
Och han gick igenom hela formeln
av hur man beräknar drifttider.

926
00:45:52,124 --> 00:45:53,040
Inga bekymmer om det.

927
00:45:53,040 --> 00:45:54,660
Om du är riktigt nyfiken
om hur det fungerar,

928
00:45:54,660 --> 00:45:55,810
gärna prata med mig efter avsnitt.

929
00:45:55,810 --> 00:45:57,560
Vi kan gå igenom
formlerna tillsammans.

930
00:45:57,560 --> 00:46:00,689
Men alla ni måste verkligen
vet är att n kvadrat över 2

931
00:46:00,689 --> 00:46:01,980
är samma sak som n kvadrat.

932
00:46:01,980 --> 00:46:04,710
Eftersom det största antalet,
exponenten, växer mest.

933
00:46:04,710 --> 00:46:06,590
Och så för våra syften,
allt vi bryr oss om

934
00:46:06,590 --> 00:46:09,470
är det jätte siffra som växer.

935
00:46:09,470 --> 00:46:13,340
>> Så vad är det bästa fall
runtime urvals sort?

936
00:46:13,340 --> 00:46:15,830
Om du ska ha
att iterera igenom en lista

937
00:46:15,830 --> 00:46:18,712
och sedan iterera genom
resten av denna förteckning,

938
00:46:18,712 --> 00:46:20,420
hur många gånger är
ni förmodligen,

939
00:46:20,420 --> 00:46:24,612
i värsta case-- i
bästa fall sorry-- gå igenom?

940
00:46:24,612 --> 00:46:27,070
Kanske bättre fråga är
att fråga, vad är det värsta fallet

941
00:46:27,070 --> 00:46:28,153
runtime selektions slag.

942
00:46:28,153 --> 00:46:29,366
PUBLIK: n kvadrat.

943
00:46:29,366 --> 00:46:30,740
ANDI PENG: Det n kvadrat, höger.

944
00:46:30,740 --> 00:46:36,986
Så ett enkelt sätt att tänka på detta är,
varje gång du har två kapslade loopar,

945
00:46:36,986 --> 00:46:38,110
det kommer att bli n kvadrat.

946
00:46:38,110 --> 00:46:40,386
Eftersom inte bara är du
löper genom ytterligare en gång,

947
00:46:40,386 --> 00:46:42,260
du måste gå tillbaka
runt och köra igenom det

948
00:46:42,260 --> 00:46:44,980
återigen insidan för varje värde.

949
00:46:44,980 --> 00:46:48,640
Så i detta fall, du kör n
gånger n kvadrat, som är-- ledsen,

950
00:46:48,640 --> 00:46:50,505
n gånger n, vilket är lika med n kvadrat.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> Och sortera är också lite
unikt i den meningen

953
00:46:56,360 --> 00:46:59,774
att det spelar ingen roll om dessa
värden är redan i sin ordning.

954
00:46:59,774 --> 00:47:01,440
Det är fortfarande kommer att köra igenom ändå.

955
00:47:01,440 --> 00:47:03,872
Låt oss bara säga att detta var en, två, tre, fyra.

956
00:47:03,872 --> 00:47:07,080
Oavsett huruvida det var i
ordning, det fortfarande skulle ha gick igenom

957
00:47:07,080 --> 00:47:08,620
och fortfarande kontrolleras minimivärdet.

958
00:47:08,620 --> 00:47:10,100
Det skulle ha gjort
samma antal kontroller

959
00:47:10,100 --> 00:47:12,780
varje gång, även om det
faktiskt inte röra någonting.

960
00:47:12,780 --> 00:47:16,940
>> Så i ett sådant fall, det bästa och sämsta
drifttider är faktiskt likvärdiga.

961
00:47:16,940 --> 00:47:19,160
Så förväntade runtime
selektions sortera,

962
00:47:19,160 --> 00:47:23,790
som vi betecknar med symbolen
theta, theta, i detta fall,

963
00:47:23,790 --> 00:47:24,790
skulle också vara n kvadrat.

964
00:47:24,790 --> 00:47:26,480
Alla tre av dessa skulle vara n kvadrat.

965
00:47:26,480 --> 00:47:29,653
Är alla klara över varför
runtime är n kvadrat?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Okej.

968
00:47:33,980 --> 00:47:39,120
Så jag ska bara snabbt köra
genom resten av slag.

969
00:47:39,120 --> 00:47:41,137
Algoritmen för
bubbla sort-- ihåg,

970
00:47:41,137 --> 00:47:43,220
Detta var den första
David gick över i föreläsning.

971
00:47:43,220 --> 00:47:46,000
I huvudsak, steg du
igenom hela listan

972
00:47:46,000 --> 00:47:48,950
och du swap-- du just
jämföra två åt gången.

973
00:47:48,950 --> 00:47:51,350
Och om man är större,
än du bara byta dem.

974
00:47:51,350 --> 00:47:53,590
Så om dessa är större, skulle du byta.

975
00:47:53,590 --> 00:47:56,180
Jag har officiellt här.

976
00:47:56,180 --> 00:47:59,100
>> Så låt oss bara säga att du hade 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Du skulle jämföra 8 och 6.

978
00:48:00,571 --> 00:48:01,570
Du skulle behöva byta dem.

979
00:48:01,570 --> 00:48:02,610
Du skulle jämföra 8 och 4.

980
00:48:02,610 --> 00:48:03,609
Du skulle behöva byta dem.

981
00:48:03,609 --> 00:48:07,000
Om du måste byta 8 och
2, ändra dem också.

982
00:48:07,000 --> 00:48:10,760
Så i en sådan känsla, kan du se,
spelas ut under en lång tidsperiod,

983
00:48:10,760 --> 00:48:13,730
hur värden typ av bubbla till
ändarna, som är därför vi kallar det

984
00:48:13,730 --> 00:48:15,320
bubbelsortering.

985
00:48:15,320 --> 00:48:19,950
>> Vi skulle bara köra igenom igen på
vår andra pass, och vår tredje passet,

986
00:48:19,950 --> 00:48:21,150
och vår fjärde cykeln.

987
00:48:21,150 --> 00:48:25,820
I huvudsak, bubbelsortering bara körs
tills du inte göra några fler swappar.

988
00:48:25,820 --> 00:48:31,109
Så i den meningen är det bara
den allmänna pseudokod för den.

989
00:48:31,109 --> 00:48:32,650
Inga bekymmer, kommer alla dessa vara online.

990
00:48:32,650 --> 00:48:34,990
Vi behöver inte faktiskt gå över detta.

991
00:48:34,990 --> 00:48:38,134
>> Vi initiera bara en räknare
variabel som börjar på 0.

992
00:48:38,134 --> 00:48:39,800
Och vi iterera igenom hela uppsättningen.

993
00:48:39,800 --> 00:48:43,420
Och om ett värde är-- om detta
värdet är större än detta värde,

994
00:48:43,420 --> 00:48:44,610
du kommer att byta dem.

995
00:48:44,610 --> 00:48:46,860
Och då är du bara
kommer att fortsätta.

996
00:48:46,860 --> 00:48:47,970
Och du kommer att räkna.

997
00:48:47,970 --> 00:48:50,845
Och du ska bara fortsätta göra
detta medan räknaren är större

998
00:48:50,845 --> 00:48:53,345
än 0, vilket innebär att
varje gång du måste byta,

999
00:48:53,345 --> 00:48:55,220
du vet att du vill gå
tillbaka och kontrollera igen.

1000
00:48:55,220 --> 00:48:59,510
Du vill behålla kontrollen tills du vet
att du inte behöver byta längre.

1001
00:48:59,510 --> 00:49:05,570
>> Så vad är det bästa och sämsta
fall runtimes för bubbelsortering?

1002
00:49:05,570 --> 00:49:09,300
Och hint-- detta är faktiskt annorlunda
från val slag i den mening

1003
00:49:09,300 --> 00:49:11,810
att dessa två svar är inte samma sak.

1004
00:49:11,810 --> 00:49:14,709
Tänk på vad som skulle hända i
ett ärende om det var redan för sortering.

1005
00:49:14,709 --> 00:49:16,500
Och tänk på vad
skulle hända om det var

1006
00:49:16,500 --> 00:49:18,372
i det fall där det inte var sorteras.

1007
00:49:18,372 --> 00:49:20,580
Och du kan slags kör
genom varför det händer.

1008
00:49:20,580 --> 00:49:22,954
Jag ska ge er, som, 30
sekunder för att tänka på det.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> OK.

1011
00:49:53,540 --> 00:49:57,462
Har någon en gissning på vad
värsta fall runtime av bubbelsortering är?

1012
00:49:57,462 --> 00:49:57,962
Yeah.

1013
00:49:57,962 --> 00:50:07,810
>> PUBLIK: Skulle det vara, något liknande, n gånger
n minus 1 eller nåt sånt?

1014
00:50:07,810 --> 00:50:10,650
Liksom varje gång det körs,
det är bara, som en swap mindre

1015
00:50:10,650 --> 00:50:10,960
att vad det var.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI PENG: Ja, så
du är helt rätt.

1017
00:50:12,668 --> 00:50:15,940
Och detta är ett fall där din
Svaret var faktiskt mer komplex

1018
00:50:15,940 --> 00:50:17,240
än den vi måste ge.

1019
00:50:17,240 --> 00:50:19,772
Så det kommer att run-- jag
kommer att radera allt det här.

1020
00:50:19,772 --> 00:50:20,480
Är alla bra?

1021
00:50:20,480 --> 00:50:21,869
Kan jag ta bort det?

1022
00:50:21,869 --> 00:50:22,368
OK.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Du kommer att gå igenom n
gånger den första gången, eller hur?

1025
00:50:30,320 --> 00:50:33,200
Och de kommer att gå igenom
n minus 1 andra gången, eller hur?

1026
00:50:33,200 --> 00:50:37,130
Och då du kommer att hålla
gå, n gruvan 2, et cetera.

1027
00:50:37,130 --> 00:50:40,210
David gjorde detta i en föreläsning, där,
Om du har lagt upp alla dessa värden,

1028
00:50:40,210 --> 00:50:48,080
du får något som är like-- yeah--
över 2, som i huvudsak bara minskar

1029
00:50:48,080 --> 00:50:49,784
ned till n kvadrat.

1030
00:50:49,784 --> 00:50:51,700
Du kommer att få en
konstig fraktion där.

1031
00:50:51,700 --> 00:50:53,892
Och så vet bara att
n kvadrat alltid

1032
00:50:53,892 --> 00:50:55,350
företräde framför fraktionen.

1033
00:50:55,350 --> 00:50:58,450
Och så i detta fall, det värsta
runtime skulle n kvadrat.

1034
00:50:58,450 --> 00:51:00,210
Om det var i fallande
ordning, tror du

1035
00:51:00,210 --> 00:51:02,530
måste göra en swap varenda gång.

1036
00:51:02,530 --> 00:51:05,170
>> Vad skulle vara potentiellt
bästa fall runtime?

1037
00:51:05,170 --> 00:51:08,580
Låt oss bara säga, om listan var redan
i ordning, vad skulle runtime vara?

1038
00:51:08,580 --> 00:51:09,565
>> PUBLIK: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI PENG: Det är n, precis.

1040
00:51:10,690 --> 00:51:11,600
Och varför är det n?

1041
00:51:11,600 --> 00:51:13,850
PUBLIK: Eftersom du bara
måste kolla på varje gång.

1042
00:51:13,850 --> 00:51:14,770
ANDI PENG: Exakt.

1043
00:51:14,770 --> 00:51:17,150
Så i bästa möjliga runtime,
Om denna lista var redan

1044
00:51:17,150 --> 00:51:20,270
sorted-- låt oss säga 1, 2, 3, 4-- du
skulle bara gå igenom, vill du kolla,

1045
00:51:20,270 --> 00:51:21,720
du skulle se, oh, alla panorera.

1046
00:51:21,720 --> 00:51:22,636
Jag behövde inte byta.

1047
00:51:22,636 --> 00:51:23,370
Jag är färdig.

1048
00:51:23,370 --> 00:51:26,500
Så i så fall är det bara n
eller antalet steg du bara

1049
00:51:26,500 --> 00:51:29,870
hade att checka in den första listan.

1050
00:51:29,870 --> 00:51:33,990
>> Och efter vi nu hit
insättningssortering, där

1051
00:51:33,990 --> 00:51:39,260
algoritmen är i huvudsak att dividera
det i en sorterad och osorterade delen.

1052
00:51:39,260 --> 00:51:42,810
Och sedan en efter en,
de osorterade värden är

1053
00:51:42,810 --> 00:51:46,880
insatt i deras fall
positioner i början av listan.

1054
00:51:46,880 --> 00:51:52,120
>> Så till exempel, vi har en
lista över 3, 5, 2, 6, 4 igen.

1055
00:51:52,120 --> 00:51:54,750
Vi vet att det är för närvarande
osorterade eftersom vi har bara

1056
00:51:54,750 --> 00:51:57,030
började titta på det.

1057
00:51:57,030 --> 00:52:00,610
Vi tar en titt och vi vet att
det första värdet sorteras, eller hur?

1058
00:52:00,610 --> 00:52:04,190
Om du bara tittar på en rad
storlek en, vet du att det är för sortering.

1059
00:52:04,190 --> 00:52:08,230
>> Så då vet vi att
övriga fyra är osorterade.

1060
00:52:08,230 --> 00:52:10,980
Vi går igenom och vi ser detta värde.

1061
00:52:10,980 --> 00:52:11,730
Låt oss gå tillbaka.

1062
00:52:11,730 --> 00:52:13,130
Se till att värdet på 5?

1063
00:52:13,130 --> 00:52:14,110
Vi tar en titt på det.

1064
00:52:14,110 --> 00:52:15,204
Vi jämför det med tre.

1065
00:52:15,204 --> 00:52:17,870
Vi vet att det är större än
3, så vi vet att det är för sortering.

1066
00:52:17,870 --> 00:52:22,940
Så vi vet nu att de två första
sorteras och de tre sista är det inte.

1067
00:52:22,940 --> 00:52:24,270
>> Vi tar en titt på 2.

1068
00:52:24,270 --> 00:52:25,720
Vi kollar först den med 5.

1069
00:52:25,720 --> 00:52:26,700
Är det mindre än 5?

1070
00:52:26,700 --> 00:52:27,240
Jag är inte.

1071
00:52:27,240 --> 00:52:29,510
Så vi måste hålla tittar ner.

1072
00:52:29,510 --> 00:52:30,940
Då kan du kontrollera 2 st 3.

1073
00:52:30,940 --> 00:52:31,850
Är det mindre än?

1074
00:52:31,850 --> 00:52:32,350
Nej.

1075
00:52:32,350 --> 00:52:35,430
Så du vet en 2 måste införas
in i den främre och 3 och 5

1076
00:52:35,430 --> 00:52:38,200
båda måste skjutas ut.

1077
00:52:38,200 --> 00:52:42,190
Gör detta igen med 6 och 4.

1078
00:52:42,190 --> 00:52:48,962
Och vi håller bara kontrollera i huvudsak
där vi checkar bara, check, check.

1079
00:52:48,962 --> 00:52:51,170
Och tills det är i rätt
läge, vi slags bara

1080
00:52:51,170 --> 00:52:54,890
in den i rätt position,
som är där namnet på det kom från.

1081
00:52:54,890 --> 00:52:59,830
>> Så det är bara algoritmen,
pseudokod per se, typ av,

1082
00:52:59,830 --> 00:53:04,990
om hur vi skulle genomföra
ett insättningssortering.

1083
00:53:04,990 --> 00:53:05,954
Pseudokod är här.

1084
00:53:05,954 --> 00:53:06,620
Det handlar på nätet.

1085
00:53:06,620 --> 00:53:10,720
Inga bekymmer om ni är
försöker kopiera ner det.

1086
00:53:10,720 --> 00:53:14,500
Så återigen, samma question-- vad
skulle vara det bästa och sämsta drifttider

1087
00:53:14,500 --> 00:53:16,120
för insättningssortering?

1088
00:53:16,120 --> 00:53:17,750
Det är mycket lik den sista frågan.

1089
00:53:17,750 --> 00:53:20,479
Jag ska ge er, som, 30
sekunder att tänka på detta också.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK Finns det någon som vill
ge mig det värsta runtime?

1092
00:53:50,071 --> 00:53:50,570
Yeah.

1093
00:53:50,570 --> 00:53:51,490
>> PUBLIK: n kvadrat.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI PENG: Det n kvadrat.

1095
00:53:52,573 --> 00:53:53,730
Och varför är det n kvadrat?

1096
00:53:53,730 --> 00:53:57,562
>> PUBLIK: För i
omvänd ordning, har du

1097
00:53:57,562 --> 00:54:02,619
att gå igenom n gånger n, som är--

1098
00:54:02,619 --> 00:54:03,660
ANDI PENG: Ja, exakt.

1099
00:54:03,660 --> 00:54:06,610
Så samma sak som i bubbelsortering.

1100
00:54:06,610 --> 00:54:08,720
Om denna lista är i
fallande ordning, du är

1101
00:54:08,720 --> 00:54:11,240
kommer att behöva kontrollera först en gång.

1102
00:54:11,240 --> 00:54:13,470
Och sedan med varje
mervärde, du är

1103
00:54:13,470 --> 00:54:16,390
kommer att behöva kontrollera den mot
varenda värde, eller hur?

1104
00:54:16,390 --> 00:54:20,290
Och så helt och hållet, du kommer att göra
En N passtider annan n passera, som

1105
00:54:20,290 --> 00:54:21,750
är N i kvadrat.

1106
00:54:21,750 --> 00:54:22,860
Hur är det bästa fall?

1107
00:54:22,860 --> 00:54:24,360
Yeah.

1108
00:54:24,360 --> 00:54:28,840
>> Publik: n minus 1, eftersom
första är redan i kvadrat.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI PENG: Så nära.

1110
00:54:30,270 --> 00:54:31,850
Svaret är faktiskt n.

1111
00:54:31,850 --> 00:54:37,189
Eftersom medan den första är
sorteras, kan det inte actually-- det

1112
00:54:37,189 --> 00:54:38,980
vi bara lucked i
det exemplet, att 2

1113
00:54:38,980 --> 00:54:40,930
råkade vara det minsta antalet.

1114
00:54:40,930 --> 00:54:43,680
Men det kommer inte alltid att vara fallet.

1115
00:54:43,680 --> 00:54:48,040
Om två redan sorterats i början
men du ser ut och det finns en 1 här,

1116
00:54:48,040 --> 00:54:49,144
1 kommer att stöta den.

1117
00:54:49,144 --> 00:54:51,060
Och det kommer att sluta
ändan stötte ändå.

1118
00:54:51,060 --> 00:54:56,250
>> Så i bästa fall,
det är faktiskt bara kommer att bli n.

1119
00:54:56,250 --> 00:54:59,090
Om du har en, två, tre,
4, 5, 6, 7, 8, är du

1120
00:54:59,090 --> 00:55:00,940
kommer att gå igenom
att hela listan så snart

1121
00:55:00,940 --> 00:55:03,430
att kontrollera att se om allt är bra.

1122
00:55:03,430 --> 00:55:07,390
Är alla klara för löpning
tider val samt?

1123
00:55:07,390 --> 00:55:09,960
Jag vet att jag går igenom
Dessa riktigt snabbt.

1124
00:55:09,960 --> 00:55:13,330
Men bara vet att om du vet
allmänna begrepp, bör du vara bra.

1125
00:55:13,330 --> 00:55:16,070
OK.

1126
00:55:16,070 --> 00:55:19,790
Så jag ska bara ge er kanske, liksom,
en minut att prata med dina grannar

1127
00:55:19,790 --> 00:55:21,890
om vad som är bara några
av de viktigaste skillnaderna

1128
00:55:21,890 --> 00:55:23,540
mellan dessa typer av slag.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Vi kommer att gå igenom det snart.

1131
00:56:25,570 --> 00:56:26,444
Målgrupp: Åh, OK.

1132
00:56:26,444 --> 00:56:27,320
ANDI PENG: Ja.

1133
00:56:27,320 --> 00:56:28,380
OK.

1134
00:56:28,380 --> 00:56:33,420
Cool, låt oss träffas igen som en klass.

1135
00:56:33,420 --> 00:56:34,330
OK.

1136
00:56:34,330 --> 00:56:37,579
Så det här var typ av en
öppen fråga i den meningen

1137
00:56:37,579 --> 00:56:39,120
att det finns massor av svar på dem.

1138
00:56:39,120 --> 00:56:40,746
Och vi kommer att gå igenom några av dem kortfattat.

1139
00:56:40,746 --> 00:56:43,411
Jag ville bara få er
tänka på vad differentierade

1140
00:56:43,411 --> 00:56:44,530
alla tre typer av slag.

1141
00:56:44,530 --> 00:56:47,440
Och jag hörde också en stor
question-- vad merge sort göra?

1142
00:56:47,440 --> 00:56:50,110
Bra fråga, eftersom det är
vad vi täcker nästa.

1143
00:56:50,110 --> 00:56:52,850
>> Så merge sort är den
en sort som fungerar

1144
00:56:52,850 --> 00:56:56,100
mycket annorlunda än de andra sorter.

1145
00:56:56,100 --> 00:56:58,180
Som ni kan see--
gjorde David göra det demo

1146
00:56:58,180 --> 00:57:01,130
där han hade alla coola
tongångar se hur samman

1147
00:57:01,130 --> 00:57:04,010
sortera sprang, liksom, oändligt
snabbare än de andra två typerna?

1148
00:57:04,010 --> 00:57:04,510
OK.

1149
00:57:04,510 --> 00:57:07,580
Så det beror på sammanslagning
sortera implementerar att klyftan

1150
00:57:07,580 --> 00:57:11,020
och erövra koncept som vi har
talade om en hel del i föreläsning.

1151
00:57:11,020 --> 00:57:14,550
I den meningen att vi tycker om att arbeta
smartare, inte hårdare, när du dela

1152
00:57:14,550 --> 00:57:18,120
och erövra problem, och bryta dem
ner, och sedan sätta ihop dem,

1153
00:57:18,120 --> 00:57:19,930
bra saker alltid hända.

1154
00:57:19,930 --> 00:57:21,960
>> Så det sätt som går samman
sortera väsentligen fungerar

1155
00:57:21,960 --> 00:57:24,660
är att den delar ett
osorterade array i hälften.

1156
00:57:24,660 --> 00:57:26,500
Och sedan har fått två halvor av matriser.

1157
00:57:26,500 --> 00:57:28,220
Och det bara sorterar dessa två halvor.

1158
00:57:28,220 --> 00:57:31,750
Det håller bara dela på mitten, i
hälften i hälften tills allt sorteras

1159
00:57:31,750 --> 00:57:33,680
och sedan rekursivt
sätter ihop allt.

1160
00:57:33,680 --> 00:57:36,550
>> Så det är egentligen abstrakt.

1161
00:57:36,550 --> 00:57:38,750
Så det här är bara en bit av pseudokod.

1162
00:57:38,750 --> 00:57:41,040
Betyder det vettigt i
så det är igång?

1163
00:57:41,040 --> 00:57:43,870
Så låt oss bara säga att du har en
uppsättning av n element, eller hur?

1164
00:57:43,870 --> 00:57:45,450
Om n är mindre än 2, kan du återvända.

1165
00:57:45,450 --> 00:57:49,040
Eftersom du vet att om det finns
bara en sak, måste det sorteras.

1166
00:57:49,040 --> 00:57:52,600
Annars, du sortera den vänstra halvan,
och sedan sortera högra halvan,

1167
00:57:52,600 --> 00:57:54,140
och sedan samman.

1168
00:57:54,140 --> 00:57:56,979
>> Så medan det ser riktigt enkelt,
i verkligheten, att tänka på det är

1169
00:57:56,979 --> 00:58:00,270
typ av svårt. Eftersom du är som,
ja, det är typ att köra på sig själv.

1170
00:58:00,270 --> 00:58:00,769
Höger?

1171
00:58:00,769 --> 00:58:02,430
Det körs på sig själv.

1172
00:58:02,430 --> 00:58:05,479
Så i den meningen, David rörde
vid rekursion i klassen.

1173
00:58:05,479 --> 00:58:07,270
Och det är ett koncept
Vi ska tala om mer.

1174
00:58:07,270 --> 00:58:11,430
Det är att detta, dessa två linjer
här är faktiskt bara programmet

1175
00:58:11,430 --> 00:58:13,860
säga till den att köra själv
med olika indata.

1176
00:58:13,860 --> 00:58:17,230
Så i stället för att köra själv med
helheten av n element,

1177
00:58:17,230 --> 00:58:20,530
Du kan dela upp det i den
vänstra halvan och den högra halvan

1178
00:58:20,530 --> 00:58:22,680
och sedan köra den igen.

1179
00:58:22,680 --> 00:58:26,050
>> Och då kommer vi att titta på det visuellt,
eftersom jag är en visuell inlärare.

1180
00:58:26,050 --> 00:58:27,270
Det fungerar bättre för mig.

1181
00:58:27,270 --> 00:58:29,890
Så ska vi titta på ett visuellt exempel här.

1182
00:58:29,890 --> 00:58:36,237
>> Låt oss säga att vi har en matris, sex
delar, 3, 5, 2, 6, 4, 1, inte sortering.

1183
00:58:36,237 --> 00:58:37,820
Okej, det finns en hel del på den här sidan.

1184
00:58:37,820 --> 00:58:43,179
Så om ni kan titta på
första steget här, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
du kan dela den på mitten.

1186
00:58:44,220 --> 00:58:45,976
Du har 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Du vet att dessa aren't-- dig
vet inte om de är sorterade eller inte,

1188
00:58:48,850 --> 00:58:52,517
så du håller bryta ner dem i hälften,
på mitten, på mitten, tills slutligen,

1189
00:58:52,517 --> 00:58:53,600
du bara har ett element.

1190
00:58:53,600 --> 00:58:56,790
Och en del är alltid sorteras, eller hur?

1191
00:58:56,790 --> 00:59:01,560
>> Så vi vet att 3, 5, 2, 4, 6,
1, av sig själva, sorteras.

1192
00:59:01,560 --> 00:59:05,870
Och nu kan vi sätta tillbaka dem tillsammans.

1193
00:59:05,870 --> 00:59:07,510
Så vi vet 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Vi sätter dem tillsammans.

1195
00:59:08,510 --> 00:59:09,617
Vi vet att det är sorteras.

1196
00:59:09,617 --> 00:59:10,450
De 2 är fortfarande där.

1197
00:59:10,450 --> 00:59:11,830
Vi kan sätta 4 och 6 tillsammans.

1198
00:59:11,830 --> 00:59:13,996
Vi vet att det är sorteras,
så vi satte det tillsammans.

1199
00:59:13,996 --> 00:59:14,940
Och ett är där.

1200
00:59:14,940 --> 00:59:18,720
>> Och sedan bara titta på
Dessa två halvor här.

1201
00:59:18,720 --> 00:59:21,300
Du har 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Du kan bara jämföra
i början av allt.

1203
00:59:23,465 --> 00:59:26,340
Eftersom du vet att detta är sorterad
och du vet att det är för sortering.

1204
00:59:26,340 --> 00:59:29,360
Så då du inte ens
jämföra 5, du bara jämföra tre.

1205
00:59:29,360 --> 00:59:32,070
Och 2 är mindre än 3, så
du vet två måste gå i slutändan.

1206
00:59:32,070 --> 00:59:33,120
>> Samma sak om det.

1207
00:59:33,120 --> 00:59:34,740
1 måste gå här.

1208
00:59:34,740 --> 00:59:37,330
Och sedan när du går att sätta
dessa två värden tillsammans,

1209
00:59:37,330 --> 00:59:39,950
du vet att detta sorteras och
du vet att det sorteras.

1210
00:59:39,950 --> 00:59:43,240
Så då 1 och
2, den 1 är mindre än två.

1211
00:59:43,240 --> 00:59:45,570
Som talar om att 1
bör gå på slutet av denna

1212
00:59:45,570 --> 00:59:47,480
utan att ens titta på 3 eller 5.

1213
00:59:47,480 --> 00:59:50,100
Och sedan 4, kan du bara
kontrollera, det går rätt här.

1214
00:59:50,100 --> 00:59:51,480
Du behöver inte titta på 5.

1215
00:59:51,480 --> 00:59:52,570
Samma sak med 6.

1216
00:59:52,570 --> 00:59:55,860
Du vet att det 6-- det bara
behöver inte ses.

1217
00:59:55,860 --> 00:59:57,870
>> Och så på det sättet, är du
bara spara dig

1218
00:59:57,870 --> 00:59:59,526
en hel del steg när du jämför.

1219
00:59:59,526 --> 01:00:02,150
Du behöver inte jämföra alla
elementet mot andra element.

1220
01:00:02,150 --> 01:00:05,230
Du jämför bara mot de
att du måste jämföra den mot.

1221
01:00:05,230 --> 01:00:06,870
Så det är typ av ett abstrakt begrepp.

1222
01:00:06,870 --> 01:00:10,540
Inga bekymmer om det inte är
helt träffa dig rätt ännu.

1223
01:00:10,540 --> 01:00:14,740
Men generellt är detta
hur en sammanslagning sort fungerar.

1224
01:00:14,740 --> 01:00:17,750
Frågor, snabba frågor,
innan jag går vidare?

1225
01:00:17,750 --> 01:00:18,550
Yeah.

1226
01:00:18,550 --> 01:00:22,230
>> PUBLIK: Så du sa att du tar
den 1, och sedan 4 och 6

1227
01:00:22,230 --> 01:00:23,860
och sätta dem i.

1228
01:00:23,860 --> 01:00:26,800
Så är inte those-- inte
du tittar på dem

1229
01:00:26,800 --> 01:00:28,544
som separata delar, inte som helhet?

1230
01:00:28,544 --> 01:00:29,210
ANDI PENG: Ja.

1231
01:00:29,210 --> 01:00:32,020
Så vad som händer
är att du i princip

1232
01:00:32,020 --> 01:00:33,650
skapar en helt ny uppsättning.

1233
01:00:33,650 --> 01:00:36,690
Så du vet att här har jag
två uppsättningar av storlek 3, eller hur?

1234
01:00:36,690 --> 01:00:39,600
Så du vet att min sorterade arrayen
måste ha sex element.

1235
01:00:39,600 --> 01:00:42,270
Så du bara skapa en
ny mängd minne.

1236
01:00:42,270 --> 01:00:44,270
Så du är ungefär som
är slöseri med minne,

1237
01:00:44,270 --> 01:00:46,186
men det spelar ingen roll
eftersom det är så liten.

1238
01:00:46,186 --> 01:00:48,590
Så du tittar på en
och du tittar på 2.

1239
01:00:48,590 --> 01:00:50,770
Och du vet att en är mindre än 2.

1240
01:00:50,770 --> 01:00:53,840
Så du vet att en bör gå i
början av alla dem.

1241
01:00:53,840 --> 01:00:55,850
>> Du behöver inte ens behöver
titta på 3 och 5.

1242
01:00:55,850 --> 01:00:57,400
Så du vet en går där.

1243
01:00:57,400 --> 01:00:59,300
Då du i princip hugga bort en.

1244
01:00:59,300 --> 01:01:00,370
Det är, som, död för oss.

1245
01:01:00,370 --> 01:01:03,690
Sedan har vi bara två,
3, 5 och sedan 4 och 6.

1246
01:01:03,690 --> 01:01:06,270
Och då vet du att du
jämföra 4 och 2,

1247
01:01:06,270 --> 01:01:07,560
åh, två bör gå in där.

1248
01:01:07,560 --> 01:01:09,685
Så du plopp 2 ner, du hackar den.

1249
01:01:09,685 --> 01:01:12,060
Så då du bara har 3
och 5 i 4 och 6.

1250
01:01:12,060 --> 01:01:14,650
Och du bara hålla hugga bort
tills du lägger dem i gruppen.

1251
01:01:14,650 --> 01:01:17,110
>> PUBLIK: Så du är bara alltid
jämföra [OHÖRBAR]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI PENG: Exakt.

1253
01:01:17,710 --> 01:01:19,590
Så i den meningen, du är
bara jämföra, i huvudsak,

1254
01:01:19,590 --> 01:01:21,240
ett antal mot den andra nummer.

1255
01:01:21,240 --> 01:01:22,990
Och eftersom du vet
att det är sorteras, du

1256
01:01:22,990 --> 01:01:24,350
behöver inte titta igenom
alla nummer.

1257
01:01:24,350 --> 01:01:25,870
Du behöver bara titta på den första.

1258
01:01:25,870 --> 01:01:27,582
Och då kan du bara plopp
ner dem, eftersom du vet

1259
01:01:27,582 --> 01:01:29,640
de tillhör där de behöver tillhöra.

1260
01:01:29,640 --> 01:01:31,030
Yeah.

1261
01:01:31,030 --> 01:01:32,920
Bra fråga.

1262
01:01:32,920 --> 01:01:35,290
>> Och sedan om någon av er
är lite ambitiöst,

1263
01:01:35,290 --> 01:01:38,660
gärna att titta på denna kod.

1264
01:01:38,660 --> 01:01:40,680
Detta är faktiskt den
fysiska genomförandet

1265
01:01:40,680 --> 01:01:42,150
om hur vi skulle skriva merge sort.

1266
01:01:42,150 --> 01:01:44,070
Och du kan se, det är mycket kort.

1267
01:01:44,070 --> 01:01:46,310
Men idéerna bakom
det är ganska komplex.

1268
01:01:46,310 --> 01:01:50,865
Så om du känner för att dra ut detta
i dina läxor ikväll, gärna.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> OK.

1271
01:01:54,740 --> 01:01:58,070
Och David gick också över detta i föreläsning.

1272
01:01:58,070 --> 01:02:00,660
Vilka är de bästa fall
drifttider, värsta fall drifttider,

1273
01:02:00,660 --> 01:02:05,680
och de förväntade drifttider för merge sort?

1274
01:02:05,680 --> 01:02:07,260
Ett par sekunder att tänka.

1275
01:02:07,260 --> 01:02:11,198
Detta är ganska svårt, men typ av
intuitiv om man tänker på det.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Okej.

1278
01:02:23,054 --> 01:02:25,269
>> PUBLIK: Är det värsta fallet n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI PENG: Exakt.

1280
01:02:26,060 --> 01:02:29,380
Och varför är det n log n.

1281
01:02:29,380 --> 01:02:32,230
>> PUBLIK: Är inte det eftersom det
blir exponentiellt snabbare,

1282
01:02:32,230 --> 01:02:35,390
så det är som en funktion av den
i stället för att bara helt enkelt vara n

1283
01:02:35,390 --> 01:02:37,529
kvadrat eller något?

1284
01:02:37,529 --> 01:02:38,320
ANDI PENG: Exakt.

1285
01:02:38,320 --> 01:02:40,750
Så anledningen till att
runtime på detta är n log

1286
01:02:40,750 --> 01:02:44,310
n är because-- vad är du
gör i alla dessa steg?

1287
01:02:44,310 --> 01:02:46,190
Du är bara hugga den på mitten, eller hur?

1288
01:02:46,190 --> 01:02:48,750
Och så när vi gör det
logga, allt som det gör

1289
01:02:48,750 --> 01:02:53,150
splittrar ett problem i halv,
på mitten, på mitten, i fler halvor.

1290
01:02:53,150 --> 01:02:56,430
Och i det avseendet, kan du snäll
av eliminera den linjära modellen

1291
01:02:56,430 --> 01:02:57,510
att vi har använt.

1292
01:02:57,510 --> 01:03:00,254
För när du hugger
saker i hälften, det är en logg.

1293
01:03:00,254 --> 01:03:02,420
Det är bara den matematiska
sätt att representera det.

1294
01:03:02,420 --> 01:03:06,310
>> Och slutligen, i slutet, du är
bara göra en sista passage genom

1295
01:03:06,310 --> 01:03:07,930
att sätta dem alla i ordning, eller hur?

1296
01:03:07,930 --> 01:03:10,330
Och så om du bara behöver
kolla en sak, det är n.

1297
01:03:10,330 --> 01:03:13,420
Och så du är typ av
multiplicera de två tillsammans.

1298
01:03:13,420 --> 01:03:17,660
Så det är som du har fått den slutliga
kontrollera n här nere med en logg över n

1299
01:03:17,660 --> 01:03:18,390
Här uppe.

1300
01:03:18,390 --> 01:03:21,060
Och om du multiplicera
dem, som är n log n.

1301
01:03:21,060 --> 01:03:26,100
>> Och så det bästa fallet och sämsta
fallet och förväntat är alla n log n.

1302
01:03:26,100 --> 01:03:27,943
Det är också som en annan sort.

1303
01:03:27,943 --> 01:03:30,090
Det är som val Sortera
i den meningen att den

1304
01:03:30,090 --> 01:03:32,131
spelar ingen roll vad din
listan är, det är bara att gå

1305
01:03:32,131 --> 01:03:34,801
att göra samma sak varje gång.

1306
01:03:34,801 --> 01:03:35,300
OK.

1307
01:03:35,300 --> 01:03:39,950
Så när ni kan se, även om
den typ som vi har gått through-- n

1308
01:03:39,950 --> 01:03:41,660
kvadrat, det är inte mycket effektiv.

1309
01:03:41,660 --> 01:03:47,060
Och även denna n log n är
inte det mest effektiva.

1310
01:03:47,060 --> 01:03:49,720
Om ni är nyfikna,
det finns sorteringsmekanismer

1311
01:03:49,720 --> 01:03:54,310
som är så effektiva att de är
nästan i huvudsak plana när runtime.

1312
01:03:54,310 --> 01:03:55,420
>> Du har några log n-talet.

1313
01:03:55,420 --> 01:03:58,190
Du har lite log log n-talet.

1314
01:03:58,190 --> 01:04:00,330
Vi rör inte på dem
i denna klass just nu.

1315
01:04:00,330 --> 01:04:02,663
Men om ni är nyfikna,
gärna google, vad är

1316
01:04:02,663 --> 01:04:04,392
de mest effektiva sorteringsmekanismer.

1317
01:04:04,392 --> 01:04:06,350
Jag vet inte, det finns
några riktigt roliga sådana,

1318
01:04:06,350 --> 01:04:09,860
like-- det finns några riktigt
roliga sådana som människor gör.

1319
01:04:09,860 --> 01:04:12,210
Och du undrar hur de
någonsin tänkt på det.

1320
01:04:12,210 --> 01:04:15,730
Så google, om du har några extra
tid, på, vad är några roliga sätt

1321
01:04:15,730 --> 01:04:17,730
som people-- samt
effektiva ways-- människor

1322
01:04:17,730 --> 01:04:20,371
har kunnat genomföra slag.

1323
01:04:20,371 --> 01:04:20,870
OK.

1324
01:04:20,870 --> 01:04:22,880
Och här är bara en behändig liten diagram.

1325
01:04:22,880 --> 01:04:26,850
Jag vet allt om dig, innan det frågesport 0,
kommer att vara i ditt rum förmodligen försöker

1326
01:04:26,850 --> 01:04:27,960
att memorera det.

1327
01:04:27,960 --> 01:04:30,940
Så det är trevligt där för er.

1328
01:04:30,940 --> 01:04:37,120
Glöm bara inte logiken som made--
varför dessa siffror var inträffar.

1329
01:04:37,120 --> 01:04:39,870
Om du alltid förlorat, bara göra
att du vet vad slag är.

1330
01:04:39,870 --> 01:04:40,820
Och du kan köra igenom
dem i ditt sinne

1331
01:04:40,820 --> 01:04:42,903
ta reda på varför de
Svaren är dessa svar.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Okej.

1334
01:04:47,600 --> 01:04:49,680
Så vi kommer att flytta
på, slutligen sökning.

1335
01:04:49,680 --> 01:04:51,638
På grund som de av er
som har läst pset,

1336
01:04:51,638 --> 01:04:55,175
sökning är också en del av
veckans problem sätter.

1337
01:04:55,175 --> 01:04:57,300
Du kommer att bli ombedd att genomföra
två typer av sökningar.

1338
01:04:57,300 --> 01:05:00,070
Den ena är en linjär sökning och
en är en binär sökning.

1339
01:05:00,070 --> 01:05:01,760
>> Så den linjära sökningen är ganska lätt.

1340
01:05:01,760 --> 01:05:04,070
Du vill bara att söka elementet
en lista för att se om du får det.

1341
01:05:04,070 --> 01:05:05,444
Du behöver bara iterera igenom.

1342
01:05:05,444 --> 01:05:08,170
Och om det är lika med något,
du kan bara lämna tillbaka den, eller hur?

1343
01:05:08,170 --> 01:05:10,890
Men det som vi är mest
intresserade av att prata om

1344
01:05:10,890 --> 01:05:14,550
är binär sökning, höger, som är den
söndra och härska mekanism som

1345
01:05:14,550 --> 01:05:18,190
David demonstrerade i föreläsning.

1346
01:05:18,190 --> 01:05:20,810
>> Kom ihåg telefonboken exempel
att han håller föra upp,

1347
01:05:20,810 --> 01:05:23,960
den som han slags kämpade
lite på det senaste året,

1348
01:05:23,960 --> 01:05:27,530
där du dela upp problemet i en halv,
i halv, i halv, om och om igen,

1349
01:05:27,530 --> 01:05:30,730
tills du hittar vad du letar efter?

1350
01:05:30,730 --> 01:05:33,727
Och du har fått
runtime av det också.

1351
01:05:33,727 --> 01:05:35,810
Och du kan se, är det
betydligt effektivare

1352
01:05:35,810 --> 01:05:39,080
än någon annan typ av sökning.

1353
01:05:39,080 --> 01:05:41,880
>> Så det sätt som vi skulle gå om
implementering av en binär sökning

1354
01:05:41,880 --> 01:05:46,510
är, om vi hade en matris,
index 0-6, sju element,

1355
01:05:46,510 --> 01:05:49,790
vi kan se i mitten, right--
ledsen, om vår fråga first--

1356
01:05:49,790 --> 01:05:53,840
om vi vill ställa frågan om, gör
arrayen innehåller beståndsdelen av 7,

1357
01:05:53,840 --> 01:05:56,840
naturligtvis, att vara människor, och som har
en så liten samling, är det lätt för oss

1358
01:05:56,840 --> 01:05:58,210
att säga ja.

1359
01:05:58,210 --> 01:06:05,750
Men sättet att implementera ett binärt
sökningen skulle vara att titta i mitten.

1360
01:06:05,750 --> 01:06:08,020
>> Vi vet att index 3 är
i mitten, eftersom vi

1361
01:06:08,020 --> 01:06:09,270
vet att det finns sju element.

1362
01:06:09,270 --> 01:06:10,670
Vad 7 delat med 2?

1363
01:06:10,670 --> 01:06:12,850
Du kan hugga av den extra 1.

1364
01:06:12,850 --> 01:06:14,850
Du har tre i mitten.

1365
01:06:14,850 --> 01:06:17,590
Så är uppsättning av 3 lika med 7?

1366
01:06:17,590 --> 01:06:18,900
Det är inte, eller hur?

1367
01:06:18,900 --> 01:06:21,050
Men vi kan göra ett par av kontroller.

1368
01:06:21,050 --> 01:06:25,380
Är uppsättning av tre mindre än 7 eller
är samling av tre större än 7?

1369
01:06:25,380 --> 01:06:27,240
>> Och vi vet att det är mindre än 7.

1370
01:06:27,240 --> 01:06:30,259
Så vi vet att, åh, måste det
inte vara i den vänstra halvan.

1371
01:06:30,259 --> 01:06:32,300
Vi vet att det måste vara
i den högra halvan, eller hur?

1372
01:06:32,300 --> 01:06:34,662
Så vi kan bara hugga av halva uppsättningen.

1373
01:06:34,662 --> 01:06:36,370
Vi behöver inte ens till
titta på det längre.

1374
01:06:36,370 --> 01:06:38,711
Eftersom vi vet att
halv av vår problem--

1375
01:06:38,711 --> 01:06:41,210
vi vet att svaret är
den högra halvan av vårt problem.

1376
01:06:41,210 --> 01:06:42,580
Så vi bara tittar på det nu.

1377
01:06:42,580 --> 01:06:44,860
>> Så nu tittar vi på
mitten av vad som finns kvar.

1378
01:06:44,860 --> 01:06:46,880
Det index 5.

1379
01:06:46,880 --> 01:06:50,200
Vi gör samma kontroll igen
och vi ser att det är mindre.

1380
01:06:50,200 --> 01:06:52,050
Så vi se till vänster av det.

1381
01:06:52,050 --> 01:06:53,430
Och sedan ser vi att check.

1382
01:06:53,430 --> 01:06:57,600
Är arrayen värdet vid
index 4 är lika med 7?

1383
01:06:57,600 --> 01:06:58,260
Det är.

1384
01:06:58,260 --> 01:07:03,580
Så vi kan återkomma sant, eftersom
vi hittade värdet i vår lista.

1385
01:07:03,580 --> 01:07:06,738
Har det sätt som jag gick igenom
det vettigt för alla?

1386
01:07:06,738 --> 01:07:08,760
OK.

1387
01:07:08,760 --> 01:07:11,670
Jag ska ge er kanske, liksom,
tre, fyra minuter att räkna ut

1388
01:07:11,670 --> 01:07:13,270
hur pseudo detta.

1389
01:07:13,270 --> 01:07:18,070
>> Så tänk jag bad dig att skriva en
funktion som kallas sökning () som återvände

1390
01:07:18,070 --> 01:07:20,640
ett värde, ett booleskt värde,
det var sant eller false-- liknande,

1391
01:07:20,640 --> 01:07:22,970
true om du hittat
värde, falskt om så inte är fallet.

1392
01:07:22,970 --> 01:07:25,230
Och så var
antogs i det värde som du

1393
01:07:25,230 --> 01:07:28,410
letade efter i värden, som
är array-- åh, jag definitivt sätta

1394
01:07:28,410 --> 01:07:29,410
att på fel plats.

1395
01:07:29,410 --> 01:07:29,580
OK.

1396
01:07:29,580 --> 01:07:31,829
Iaf, bör den ha
varit till höger om värden.

1397
01:07:31,829 --> 01:07:36,280
Och sedan int n är antalet
element i den arrayen.

1398
01:07:36,280 --> 01:07:39,430
Hur skulle du gå om att försöka
att pseudo det problemet in?

1399
01:07:39,430 --> 01:07:41,630
Jag ska ge er killar som
tre minuter att göra det.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Nej, jag tror att det finns only--
Ja, det finns en rätt upp här.

1402
01:08:02,595 --> 01:08:03,261
PUBLIK: Kan jag?

1403
01:08:03,261 --> 01:08:04,388
ANDI PENG: Ja, jag har dig.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Är det fungerar?

1406
01:08:11,050 --> 01:08:12,290
OK bra.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> OK.

1409
01:10:44,720 --> 01:10:47,630
Okej killar, vi är
kommer att tygla den.

1410
01:10:47,630 --> 01:10:49,730
OK.

1411
01:10:49,730 --> 01:10:54,020
Så antar vi har denna härliga
liten samling med n värden i det.

1412
01:10:54,020 --> 01:10:55,170
Jag ville inte dra linjerna.

1413
01:10:55,170 --> 01:10:58,649
Men hur skulle vi gå om
försöker att skriva detta?

1414
01:10:58,649 --> 01:11:00,440
Finns det någon som vill
ge mig den första raden?

1415
01:11:00,440 --> 01:11:02,814
Om du vill ge mig
första raden i denna pseudokod.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> PUBLIK: [OHÖRBAR]

1418
01:11:08,430 --> 01:11:10,138
PUBLIK: Du skulle vilja
att iterera through--

1419
01:11:10,138 --> 01:11:11,094
PUBLIK: Just another för loop?

1420
01:11:11,094 --> 01:11:11,760
PUBLIK: --Barnspel.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI PENG: Så här är lite knepigt.

1423
01:11:17,780 --> 01:11:23,130
Tänk about-- du vill
att hålla igång denna loop

1424
01:11:23,130 --> 01:11:27,950
om och om igen tills när?

1425
01:11:27,950 --> 01:11:30,819
>> PUBLIK: Tills [OHÖRBAR]
värde är lika med detta värde.

1426
01:11:30,819 --> 01:11:31,610
ANDI PENG: Exakt.

1427
01:11:31,610 --> 01:11:33,900
Så du kan faktiskt bara write--
Vi kan även förenkla den mer.

1428
01:11:33,900 --> 01:11:35,630
Vi kan bara göra en while-slinga, eller hur?

1429
01:11:35,630 --> 01:11:39,380
Så du kan bara ha loop--
Vi vet att det är ett tag.

1430
01:11:39,380 --> 01:11:42,850
Men just nu, jag kommer
att säga "loop" - genom vad?

1431
01:11:42,850 --> 01:11:46,640
Loop until-- vad som är
vår sinande tillstånd?

1432
01:11:46,640 --> 01:11:47,510
Jag tror att jag hörde det.

1433
01:11:47,510 --> 01:11:48,530
Jag hörde någon säga det.

1434
01:11:48,530 --> 01:11:51,255
>> Målgrupp: Värden lika mitten.

1435
01:11:51,255 --> 01:11:52,255
ANDI PENG: Säg det igen.

1436
01:11:52,255 --> 01:11:54,470
Målgrupp: Eller tills
värde du söker

1437
01:11:54,470 --> 01:11:58,470
för är lika med det mittersta värdet.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI PENG: Vad händer om det inte är i det?

1439
01:12:00,280 --> 01:12:03,113
Vad händer om det värde du söker
finns inte faktiskt i denna samling?

1440
01:12:03,113 --> 01:12:05,890
PUBLIK: Du kommer tillbaka 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI PENG: Men vad vi vill
slinga tills om vi har ett tillstånd?

1442
01:12:08,850 --> 01:12:09,350
Yeah.

1443
01:12:09,350 --> 01:12:11,239
>> PUBLIK: Tills det finns bara ett värde?

1444
01:12:11,239 --> 01:12:13,530
ANDI PENG: Du kan loop
until-- så att du vet att du är

1445
01:12:13,530 --> 01:12:15,714
kommer att ha en maxvärde, eller hur?

1446
01:12:15,714 --> 01:12:18,130
Och du vet att du kommer
att ha en min värde, eller hur?

1447
01:12:18,130 --> 01:12:20,379
Eftersom också, det är något
Jag glömde att säga innan,

1448
01:12:20,379 --> 01:12:22,640
att något som är
kritiska binär sökning

1449
01:12:22,640 --> 01:12:24,182
är att din samling redan sorteras.

1450
01:12:24,182 --> 01:12:26,973
Eftersom det finns inget sätt att göra
detta om de är bara slumpmässiga värden.

1451
01:12:26,973 --> 01:12:29,190
Du vet inte om man är
större än den andra, eller hur?

1452
01:12:29,190 --> 01:12:32,720
>> Så du vet att din max och
dina mins är här, eller hur?

1453
01:12:32,720 --> 01:12:35,590
Om du kommer att justera
ditt max i dina minuter och mid--

1454
01:12:35,590 --> 01:12:38,470
låt oss bara anta din
mitten värde är rätt här--

1455
01:12:38,470 --> 01:12:43,910
du kommer att i grund och botten
slinga tills din minsta är

1456
01:12:43,910 --> 01:12:47,510
ungefär samma som ditt max, höger, eller
Om din max är inte detsamma som din min.

1457
01:12:47,510 --> 01:12:48,040
Höger?

1458
01:12:48,040 --> 01:12:51,340
För när det händer, vet du att
du har så småningom träffa samma värde.

1459
01:12:51,340 --> 01:12:59,135
Så du vill loop tills min
är mindre än eller lika att-- oops,

1460
01:12:59,135 --> 01:13:01,510
inte är mindre än eller lika med,
åt andra hållet around-- max är.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Gjorde det vettigt?

1463
01:13:16,160 --> 01:13:18,810
Jag tog några försök att få det rätt.

1464
01:13:18,810 --> 01:13:21,869
Men slinga tills maxvärdet
är i huvudsak nästan mindre

1465
01:13:21,869 --> 01:13:23,410
än eller lika med din minsta, eller hur?

1466
01:13:23,410 --> 01:13:25,201
Det är när du vet
att du har närmat sig varandra.

1467
01:13:25,201 --> 01:13:29,290
PUBLIK: När skulle din högsta
värde vara mindre än den minsta?

1468
01:13:29,290 --> 01:13:31,040
ANDI PENG: Om du håller
anpassa den som

1469
01:13:31,040 --> 01:13:32,380
är vad vi kommer
att göra detta.

1470
01:13:32,380 --> 01:13:33,460
Betyder det vettigt?

1471
01:13:33,460 --> 01:13:35,750
Minsta och max är bara
heltal som vi förmodligen

1472
01:13:35,750 --> 01:13:39,260
kommer att vilja skapa för att hålla
reda på var vi letar.

1473
01:13:39,260 --> 01:13:41,790
Eftersom arrayen existerar
oavsett vad vi gör.

1474
01:13:41,790 --> 01:13:45,030
Precis, vi är inte rent fysiskt
hugga av arrayen, eller hur?

1475
01:13:45,030 --> 01:13:47,261
Vi har precis justering
där vi letar.

1476
01:13:47,261 --> 01:13:48,136
Betyder det vettigt?

1477
01:13:48,136 --> 01:13:48,472
>> PUBLIK: Ja.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI PENG: OK.

1479
01:13:49,110 --> 01:13:57,090
Så om det är en förutsättning för vår slinga,
Vad vill vi insidan av denna loop?

1480
01:13:57,090 --> 01:13:58,700
Vad ska vi kommer att vilja göra?

1481
01:13:58,700 --> 01:14:02,390
Så just nu har vi
max och min, höger,

1482
01:14:02,390 --> 01:14:04,962
förmodligen skapat här uppe någonstans.

1483
01:14:04,962 --> 01:14:07,170
Vi ska förmodligen vill
att hitta en medelväg, eller hur?

1484
01:14:07,170 --> 01:14:08,450
Hur ska vi vara
kunna hitta mitten?

1485
01:14:08,450 --> 01:14:09,491
Vad är mathematical--

1486
01:14:09,491 --> 01:14:11,079
PUBLIK: Max plus min dividerat med två.

1487
01:14:11,079 --> 01:14:11,870
ANDI PENG: Exakt.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Betyder det vettigt?

1490
01:14:21,620 --> 01:14:25,780
Och ni se varför vi
inte bara use-- varför vi gjorde detta

1491
01:14:25,780 --> 01:14:27,850
istället för att göra just n delat med 2?

1492
01:14:27,850 --> 01:14:30,310
Det beror på n är ett värde
det kommer att förbli densamma.

1493
01:14:30,310 --> 01:14:30,979
Höger?

1494
01:14:30,979 --> 01:14:34,020
Men när vi anpassar vår minsta och
maxvärden, kommer de att förändras.

1495
01:14:34,020 --> 01:14:36,040
Och som ett resultat, våra middle
kommer att förändras.

1496
01:14:36,040 --> 01:14:37,873
Så det är därför vi vill
att göra denna rätt här.

1497
01:14:37,873 --> 01:14:38,510
OK.

1498
01:14:38,510 --> 01:14:41,600
>> Och sedan, nu när
vi har hittat our-- ja.

1499
01:14:41,600 --> 01:14:44,270
>> PUBLIK: Bara en snabb question--
när du säger min och max,

1500
01:14:44,270 --> 01:14:46,410
Vi antar att
det är redan sorteras?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI PENG: Ja, det är faktiskt en
förutsättning för en binär sökning,

1502
01:14:48,400 --> 01:14:49,816
att du måste veta det sorteras.

1503
01:14:49,816 --> 01:14:53,660
Vilket är varför sort, du skriver i ditt
problem in innan din binär sökning.

1504
01:14:53,660 --> 01:14:55,910
OK.

1505
01:14:55,910 --> 01:14:58,876
Så nu när vi vet var vår mittpunkt
är, vad vill du göra här?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> PUBLIK: Vi vill jämföra
att till den andra en.

1508
01:15:04,319 --> 01:15:05,110
ANDI PENG: Exakt.

1509
01:15:05,110 --> 01:15:12,280
Så du kommer att jämföra
mitten till värde, eller hur?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
Och vad säger det
oss när vi jämför?

1512
01:15:18,670 --> 01:15:22,226
Vad vill vi göra efteråt?

1513
01:15:22,226 --> 01:15:25,389
>> PUBLIK: Om värdet är större
än mitten, vi vill skära bort det.

1514
01:15:25,389 --> 01:15:26,180
ANDI PENG: Exakt.

1515
01:15:26,180 --> 01:15:33,940
Så om värdet är större
än mitten, vi är

1516
01:15:33,940 --> 01:15:36,550
kommer att vilja ändra dessa
minimum och maxar, eller hur?

1517
01:15:36,550 --> 01:15:38,980
Vad vill vi förändra?

1518
01:15:38,980 --> 01:15:42,145
Så om vi vet värdet är någonstans
här, vad gör du vi ändra?

1519
01:15:42,145 --> 01:15:44,758
Vi vill förändra vår
minimum för att vara i mitten, eller hur?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
Och sedan andra, om det är i detta
halvt, vad vi vill förändra?

1522
01:15:54,292 --> 01:15:55,306
>> PUBLIK: Din maximum.

1523
01:15:55,306 --> 01:15:55,972
ANDI PENG: Ja.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
Och då du bara gå
att hålla looping, eller hur?

1526
01:16:04,680 --> 01:16:08,920
För nu, efter en iteration
igenom, har du en max här.

1527
01:16:08,920 --> 01:16:10,760
Och då kan du räkna en mitten.

1528
01:16:10,760 --> 01:16:11,990
Och då kan du jämföra.

1529
01:16:11,990 --> 01:16:14,766
Och du kommer att fortsätta
tills minuter och de maxes

1530
01:16:14,766 --> 01:16:15,890
i allt väsentligt konvergerat.

1531
01:16:15,890 --> 01:16:17,890
Och det är när du vet att
du har drabbats i slutet av den.

1532
01:16:17,890 --> 01:16:20,280
Och antingen du har hittat den
eller om du har inte på den punkten.

1533
01:16:20,280 --> 01:16:23,170
>> Innebär detta vettigt för alla?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
OK.

1536
01:16:26,770 --> 01:16:27,900
Detta är ganska viktigt,
eftersom du har

1537
01:16:27,900 --> 01:16:29,760
att skriva detta i din kod i kväll.

1538
01:16:29,760 --> 01:16:32,660
Men ni har en ganska bra
känsla för vad du ska göra,

1539
01:16:32,660 --> 01:16:34,051
vilket är bra.

1540
01:16:34,051 --> 01:16:34,550
OK.

1541
01:16:34,550 --> 01:16:38,840
Så vi har omkring sju
minuter kvar avsnitt.

1542
01:16:38,840 --> 01:16:43,170
Så vi kommer att tala om
detta pset att vi ska göra.

1543
01:16:43,170 --> 01:16:46,410
Så pset är uppdelad i två halvor.

1544
01:16:46,410 --> 01:16:50,230
Den första halvan involverar
genomföra en Sök

1545
01:16:50,230 --> 01:16:54,210
där du skriver en linjär sökning, en
binär sökning och en sorteringsalgoritm.

1546
01:16:54,210 --> 01:16:56,690
>> Så det här är den första
tid i en pset där

1547
01:16:56,690 --> 01:17:00,050
vi kommer att ge er vad som kallas
distributions kod, som är koden

1548
01:17:00,050 --> 01:17:02,740
att vi har redan skrivna,
men bara lämnat vissa delar av

1549
01:17:02,740 --> 01:17:04,635
för dig att avsluta skriva.

1550
01:17:04,635 --> 01:17:07,510
Så ni, när man tittar på det här
koden, kan du bli riktigt rädd.

1551
01:17:07,510 --> 01:17:08,630
Om du bara vill, ahh, jag
vet inte vad det gör,

1552
01:17:08,630 --> 01:17:11,670
Jag vet inte, som verkar som
så komplicerat, ahh, slappna av.

1553
01:17:11,670 --> 01:17:12,170
Det är ok.

1554
01:17:12,170 --> 01:17:12,930
Läs spec.

1555
01:17:12,930 --> 01:17:16,920
Spec kommer att förklara för dig exakt
vad alla dessa program gör.

1556
01:17:16,920 --> 01:17:20,560
>> Exempelvis är generate.c ett program
som kommer med din pset.

1557
01:17:20,560 --> 01:17:24,060
Du behöver faktiskt inte röra det, men
bör du förstå vad det gör.

1558
01:17:24,060 --> 01:17:28,550
Och generate.c, är allt den gör
antingen generera slumptal

1559
01:17:28,550 --> 01:17:32,400
eller så kan du ge det ett frö, som en
uppgjort nummer som det tar,

1560
01:17:32,400 --> 01:17:34,140
och det genererar fler nummer.

1561
01:17:34,140 --> 01:17:37,170
Så det finns ett särskilt sätt att
genomföra generate.c där

1562
01:17:37,170 --> 01:17:42,760
Du kan bara göra en massa siffror
för dig att testa dina andra metoder på.

1563
01:17:42,760 --> 01:17:45,900
>> Så om du ville, för
exempel testa din hitta,

1564
01:17:45,900 --> 01:17:48,970
du skulle vilja köra generate.c,
generera en massa siffror,

1565
01:17:48,970 --> 01:17:50,880
och sedan köra din hjälpare funktion.

1566
01:17:50,880 --> 01:17:53,930
Din medhjälpare funktion är där du är
faktiskt fysiskt skriva kod.

1567
01:17:53,930 --> 01:17:59,330
Och tänk på medhjälpare som ett bibliotek fil
du skriver att fyndet ringer.

1568
01:17:59,330 --> 01:18:02,950
Och det inom helpers.c, kommer du
gör sökning och sortering.

1569
01:18:02,950 --> 01:18:06,500
>> Och då du kommer att väsentligen
bara sätta dem alla tillsammans.

1570
01:18:06,500 --> 01:18:10,350
Spec kommer att berätta hur man
lägga det på kommandoraden.

1571
01:18:10,350 --> 01:18:14,880
Och du kommer att kunna testa om
inte din typ och söka fungerar.

1572
01:18:14,880 --> 01:18:15,870
Häftigt.

1573
01:18:15,870 --> 01:18:18,720
Har någon redan börjat och
stött på problem eller frågor

1574
01:18:18,720 --> 01:18:20,520
De har just nu med detta?

1575
01:18:20,520 --> 01:18:21,020
OK.

1576
01:18:21,020 --> 01:18:21,476
>> PUBLIK: Vänta.

1577
01:18:21,476 --> 01:18:21,932
Jag har en fråga.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI PENG: Ja.

1579
01:18:22,844 --> 01:18:28,390
>> PUBLIK: Så jag började göra
den linjära sökning i helpers.c

1580
01:18:28,390 --> 01:18:29,670
och det var inte riktigt fungerar.

1581
01:18:29,670 --> 01:18:34,590
Men senare, fick jag veta att vi bara
måste ta bort det och göra binär sökning.

1582
01:18:34,590 --> 01:18:36,991
Så spelar det någon roll om det inte fungerar?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI PENG: korta svaret är nej.

1585
01:18:41,510 --> 01:18:42,642
Men eftersom vi är inte--

1586
01:18:42,642 --> 01:18:44,350
PUBLIK: Men ingen är
faktiskt kontroll.

1587
01:18:44,350 --> 01:18:46,058
ANDI PENG: Vi är aldrig
kommer att se det.

1588
01:18:46,058 --> 01:18:49,590
Men du förmodligen vill göra
Kontrollera din sökning fungerar.

1589
01:18:49,590 --> 01:18:51,700
För om din linjära
sökning inte fungerar,

1590
01:18:51,700 --> 01:18:54,410
då är chansen din binära
sökning kommer inte att fungera lika bra.

1591
01:18:54,410 --> 01:18:56,646
Eftersom du har liknande
logik i dem båda.

1592
01:18:56,646 --> 01:18:58,020
Och nej, det spelar egentligen ingen roll.

1593
01:18:58,020 --> 01:19:01,300
Så de enda du ska vända
i är typ och binär sökning.

1594
01:19:01,300 --> 01:19:02,490
Yeah.

1595
01:19:02,490 --> 01:19:06,610
>> Och även en hel del barn var
försöker kompilera helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Du faktiskt inte tillåtet
att göra det, eftersom helpers.c

1597
01:19:09,550 --> 01:19:11,200
inte har en huvudfunktion.

1598
01:19:11,200 --> 01:19:13,550
Och så du bör endast
vara faktiskt sammanställa

1599
01:19:13,550 --> 01:19:18,670
generera och hitta, eftersom hitta samtal
helpers.c och funktioner inom det.

1600
01:19:18,670 --> 01:19:20,790
Så det gör felsökning
en smärta i baken.

1601
01:19:20,790 --> 01:19:22,422
Men det är vad vi måste göra.

1602
01:19:22,422 --> 01:19:23,880
PUBLIK: Du gör precis allt, eller hur?

1603
01:19:23,880 --> 01:19:27,290
ANDI PENG: Du kan bara
göra allt också, ja.

1604
01:19:27,290 --> 01:19:28,060
OK.

1605
01:19:28,060 --> 01:19:32,570
Så det är det i termer av vad
den pset ber er alla att göra.

1606
01:19:32,570 --> 01:19:35,160
Om du har några frågor är du välkommen
fri att fråga mig efter avsnitt.

1607
01:19:35,160 --> 01:19:37,580
Jag kommer att vara här i ungefär 20 minuter.

1608
01:19:37,580 --> 01:19:40,500
>> Och Ja, PSET s
verkligen inte så illa.

1609
01:19:40,500 --> 01:19:41,680
Ni borde vara OK.

1610
01:19:41,680 --> 01:19:43,250
Dessa, följ bara riktlinjer.

1611
01:19:43,250 --> 01:19:47,840
Typ av har en känsla av, logiskt, vad
bör hända och du kommer att bli bra.

1612
01:19:47,840 --> 01:19:48,690
Inte vara alltför rädd.

1613
01:19:48,690 --> 01:19:50,220
Det finns en hel del kod
redan skrivit där.

1614
01:19:50,220 --> 01:19:53,011
Inte vara alltför rädd om du inte
förstå vad allt detta betyder.

1615
01:19:53,011 --> 01:19:54,749
Om det är en hel del, det är helt bra.

1616
01:19:54,749 --> 01:19:55,790
Och komma till kontorstid.

1617
01:19:55,790 --> 01:19:57,520
Vi hjälper dig att ta en titt.

1618
01:19:57,520 --> 01:20:00,810
>> PUBLIK: Med extra
funktioner, ser vi de upp?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI PENG: Ja, de är i koden.

1620
01:20:03,417 --> 01:20:05,750
I spelet 15, halv av
Det är redan skriven för dig.

1621
01:20:05,750 --> 01:20:09,310
Så dessa funktioner är
redan i koden.

1622
01:20:09,310 --> 01:20:12,020
Japp.

1623
01:20:12,020 --> 01:20:12,520
Okej.

1624
01:20:12,520 --> 01:20:14,000
Tja, lycka till.

1625
01:20:14,000 --> 01:20:15,180
Det är en motbjudande dag.

1626
01:20:15,180 --> 01:20:19,370
Så förhoppningsvis ni inte känner sig alltför
illa om vistas inne och kodning.

1627
01:20:19,370 --> 01:20:22,133