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

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

3
00:00:12,300 --> 00:00:13,890
Tervetuloa takaisin osiosta.

4
00:00:13,890 --> 00:00:17,480
Niin iloinen, että niin monet teistä sekä täällä,
ja jokainen, joka tarkkailee verkossa.

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

6
00:00:18,760 --> 00:00:20,920
Joten, kuten tavallista tervetuloa takaisin.

7
00:00:20,920 --> 00:00:24,360
Toivon, että te kaikki oli ihana
viikonloppu, täynnä lepoa, rentoutumista.

8
00:00:24,360 --> 00:00:26,026
Se oli kaunis eilen.

9
00:00:26,026 --> 00:00:27,525
Joten, toivon olet nauttinut ulkona.

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

11
00:00:28,840 --> 00:00:30,610
>> Joten ensimmäinen pari ilmoituksia.

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

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

14
00:00:32,700 --> 00:00:37,350
Niin, suurin osa teistä olisi saanut
sähköposteihin minulle omasta Scratch PSET,

15
00:00:37,350 --> 00:00:39,920
sekä luokittelu- ja PSET 1.

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

17
00:00:41,000 --> 00:00:42,220
Joten, vain pari asiaa.

18
00:00:42,220 --> 00:00:45,150
Muista käyttää check50 vuonna style50.

19
00:00:45,150 --> 00:00:47,250
Näiden on tarkoitus olla
resursseja te,

20
00:00:47,250 --> 00:00:50,660
varmista, että olet saada
niin monta pistettä kuin mahdollista

21
00:00:50,660 --> 00:00:52,390
ilman turhaan menettää ne.

22
00:00:52,390 --> 00:00:54,407
Joten asiat kuten tyyli
ovat erittäin tärkeitä.

23
00:00:54,407 --> 00:00:55,740
Aiomme ottaa pois sitä.

24
00:00:55,740 --> 00:00:58,115
Jotkut teistä saattavat olla jo
huomannut, että teidän PSET.

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

26
00:00:58,920 --> 00:01:01,450
Ja check50 on vain
todella helppo tapa varmistaa

27
00:01:01,450 --> 00:01:05,050
että olemme todella palaamassa mitä
on palautettava käyttäjälle,

28
00:01:05,050 --> 00:01:06,690
ja että kaikki on toimi kunnolla.

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

30
00:01:08,690 --> 00:01:12,040
>> Toisessa huomata, varmista, että
lataamalla asioita oikeaan kansioon.

31
00:01:12,040 --> 00:01:14,470
Se tekee elämästäni juuri
hieman vaikeampaa

32
00:01:14,470 --> 00:01:18,836
jos lataat PSET 2 osaksi PSET 1
koska kun lataan asioita,

33
00:01:18,836 --> 00:01:20,085
ne eivät lataa oikein.

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

35
00:01:21,690 --> 00:01:24,560
Ja tiedän, että se on vähän hutera
järjestelmässä tottua,

36
00:01:24,560 --> 00:01:26,950
mutta vain olla erittäin
varovainen, jos vain minulle,

37
00:01:26,950 --> 00:01:30,080
niin, että kun olet saada sähköposteja
Like 2 A.M. ja olen luokittelu.

38
00:01:30,080 --> 00:01:33,710
Jos ei aiheuta minun täytyy katsoa
kaikki ympäri sinun PSET.

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

40
00:01:34,440 --> 00:01:37,270
>> Tiedän että se on aikaisin, mutta en
täysin sai ottaa kenet

41
00:01:37,270 --> 00:01:40,800
jonka essee, joka on asianmukaisesti tämän perjantaina, että
minun professorit olivat aivan kuten, oh yeah.

42
00:01:40,800 --> 00:01:42,550
Muista, olet
essee takia perjantaina.

43
00:01:42,550 --> 00:01:45,780
Niin, tiedän kukaan ei tykkää
ajatella midterms,

44
00:01:45,780 --> 00:01:50,620
mutta ensimmäinen tietokilpailu on 15. lokakuuta,
joka Lokakuu on tästä viikosta alkaen.

45
00:01:50,620 --> 00:01:53,290
Niin, se voisi olla ennemmin
kuin odotit on kaikki.

46
00:01:53,290 --> 00:01:57,510
Niin että et ole heittänyt pois vartija kun
Mainitsen ensi viikon jaksossa, että oi,

47
00:01:57,510 --> 00:02:00,560
tietokilpailun ensi viikolla, ajattelin
Antaisin teille vähän enemmän

48
00:02:00,560 --> 00:02:01,500
of heads up nyt.

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

50
00:02:02,970 --> 00:02:04,660
>> Joten ongelma asetettu, numero kolme.

51
00:02:04,660 --> 00:02:07,070
Miten ihmiset lukenut
spec uteliaisuudesta?

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

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

54
00:02:09,199 --> 00:02:10,229
Saimme pari.

55
00:02:10,229 --> 00:02:12,320
Eräänlainen alas viime
viikossa, mutta se on OK.

56
00:02:12,320 --> 00:02:13,650
Tiedän, että se oli kaunista.

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

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

59
00:02:16,660 --> 00:02:21,010
Ehdottomasti jälkeen saat tehdä
tänään lukea spec ainakin

60
00:02:21,010 --> 00:02:25,240
kokeile kuten lataamista
jakelu koodi ja käynnissä

61
00:02:25,240 --> 00:02:27,430
kuin ensimmäiseen,
asia, että he pyytävät sinua.

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

63
00:02:28,681 --> 00:02:32,590
Koska käytämme
jakelu koodin ja kirjasto

64
00:02:32,590 --> 00:02:36,790
että olemme vasta using-- --It vain
toinen kerta, kun olemme tehneet tämän PSET,

65
00:02:36,790 --> 00:02:38,650
hulluja asioita voi tapahtua
laitteen kanssa,

66
00:02:38,650 --> 00:02:41,370
ja haluat löytää, että
ulos nyt vai myöhemmin.

67
00:02:41,370 --> 00:02:45,570
>> Koska jos se on torstai-iltana tai sen
Keskiviikkoiltana ja jostain syystä

68
00:02:45,570 --> 00:02:48,912
Laitteen vain ei
haluavat ajaa kirjasto

69
00:02:48,912 --> 00:02:50,620
tai jakeluun
koodia, että välineet

70
00:02:50,620 --> 00:02:52,309
et voi edes alkaa tehdä koodausta.

71
00:02:52,309 --> 00:02:54,100
Koska et voi tarkistaa
nähdä, jos se toimii.

72
00:02:54,100 --> 00:02:55,975
Sinun ei tule pystyä
nähdä, jos se kokoaa.

73
00:02:55,975 --> 00:03:00,500
Haluat huolehtia näiden aikaisin
viikolla, kun voit silti lähettää minulle sähköpostia

74
00:03:00,500 --> 00:03:03,100
tai jonkin muun TF: iä,
ja voimme saada ne kiinteät.

75
00:03:03,100 --> 00:03:05,410
Koska nämä kysymykset
jotka ovat menossa pysäyttää sinut

76
00:03:05,410 --> 00:03:07,120
tekemästä mitään todellista edistystä.

77
00:03:07,120 --> 00:03:10,055
Se ei ole kuin yksi vika, joka
voit vain sellaista ohittaa.

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

79
00:03:10,712 --> 00:03:13,420
Jos sinulla on ongelmia teidän
Laitteen tai jakelu koodi,

80
00:03:13,420 --> 00:03:16,211
Haluatko todella päästä, että otetaan
care of mieluummin ennemmin kuin myöhemmin.

81
00:03:16,211 --> 00:03:20,410
Joten vaikka et aio itse
aloittaa koodaus, lataa jakelu

82
00:03:20,410 --> 00:03:24,040
koodi, lukea spec, varmista
kaikki työskentelee siellä.

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

84
00:03:25,134 --> 00:03:27,675
Jos voit vain tehdä sen, minä
luvata elämänne on helpompaa.

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

86
00:03:28,800 --> 00:03:31,410
Ja niin olet todennäköisesti menossa
tehdä se nyt oikein?

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

88
00:03:32,100 --> 00:03:33,950
Niin, kysyttävää siellä?

89
00:03:33,950 --> 00:03:35,850
Mikä tahansa logistisen asioita?

90
00:03:35,850 --> 00:03:36,910
Jokainen on hyvä?

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

92
00:03:38,270 --> 00:03:41,700
>> Disclaimer niille
te huoneeseen ja verkossa.

93
00:03:41,700 --> 00:03:45,437
Aion yrittää vaihtaa
välillä PowerPoint laite

94
00:03:45,437 --> 00:03:47,270
koska olemme menossa
olla tekemässä joitakin koodaus

95
00:03:47,270 --> 00:03:53,630
tänään suosittu kysynnän anonyymi
ehdotus kysely Lähetin viime viikolla.

96
00:03:53,630 --> 00:03:55,480
Joten, teemme joitakin koodaus.

97
00:03:55,480 --> 00:03:57,800
Joten, jos te myös haluavat
tulipalon up your laitteet,

98
00:03:57,800 --> 00:04:02,910
ja sinun pitäisi saanut sähköpostia
minulta, jossa näytteen tiedosto.

99
00:04:02,910 --> 00:04:04,310
Voit vapaasti tehdä niin.

100
00:04:04,310 --> 00:04:07,340
>> Joten, aiomme puhua
GDB, joka on debuggeri.

101
00:04:07,340 --> 00:04:09,970
Se tulee auttamaan sinua
eräänlainen selvittää missä

102
00:04:09,970 --> 00:04:11,860
asiat ovat menossa pieleen koodissa.

103
00:04:11,860 --> 00:04:15,370
Se on oikeastaan ​​vain tapa, jolla voit astua
läpi koodia, koska se tapahtuu,

104
00:04:15,370 --> 00:04:19,100
ja voi tulostaa muuttujien
tai nähdä mitä todella tapahtuu

105
00:04:19,100 --> 00:04:22,980
konepellin alle jakeet ohjelma
juuri käynnissä, se on kuin faulting,

106
00:04:22,980 --> 00:04:25,030
ja et pidä, ei ole aavistustakaan
mitä juuri tapahtui täällä.

107
00:04:25,030 --> 00:04:26,730
En tiedä, mitä linjaa se epäonnistui.

108
00:04:26,730 --> 00:04:29,040
En tiedä missä se meni pieleen.

109
00:04:29,040 --> 00:04:31,280
Joten, GDB aikoo auttaa sinua siinä.

110
00:04:31,280 --> 00:04:35,240
Lisäksi, jos päätät
jatkaa kyllä, ja ottaa 61,

111
00:04:35,240 --> 00:04:38,430
se todella, todella olla sinun
paras ystävä, koska minä voi kertoa

112
00:04:38,430 --> 00:04:40,840
koska koen, että luokassa.

113
00:04:40,840 --> 00:04:43,620
>> Menemme katsomaan binary
haku, joka jos te muistaa

114
00:04:43,620 --> 00:04:47,540
suuri puhelinluettelo esimerkki
spektaakkeli luokasta.

115
00:04:47,540 --> 00:04:50,620
Tulemme täytäntöön panemiseksi, ja
kävelevän että vähän enemmän,

116
00:04:50,620 --> 00:04:54,650
ja sitten olemme menossa läpi neljä
Erilaisille, jotka ovat Bubble,

117
00:04:54,650 --> 00:04:56,285
Valinta, lisäys, ja Merge.

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

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

120
00:04:58,330 --> 00:05:00,390
Niin, GDB kuten mainitsin, on debuggeri.

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

122
00:05:01,400 --> 00:05:09,370
Ja nämä ovat sellaisia ​​suuria
asioita, iso toimintoja tai komentoja

123
00:05:09,370 --> 00:05:13,240
että käytät sisällä GDB-, ja minä vaellan
läpi demon se toinen.

124
00:05:13,240 --> 00:05:15,360
>> Niin, tämä ei ole vain
tarkoitus jäädä abstrakti.

125
00:05:15,360 --> 00:05:18,000
Yritän tehdä niin konkreettisia
mahdollisimman teitä.

126
00:05:18,000 --> 00:05:19,870
Niin, tauko.

127
00:05:19,870 --> 00:05:22,200
Se tulee joko tauko
kuten jotkut numero, joka

128
00:05:22,200 --> 00:05:26,900
edustaa linjaa oman ohjelman,
tai voit nimetä toiminnon.

129
00:05:26,900 --> 00:05:30,150
Joten, jos sanot rikkoa tärkein,
se pysähtyy tärkein,

130
00:05:30,150 --> 00:05:32,400
ja voit kävellä läpi tämän tehtävän.

131
00:05:32,400 --> 00:05:36,350
>> Samoin jos sinulla on jokin ulkoinen
toimivat kuten Swap tai Cube,

132
00:05:36,350 --> 00:05:38,450
että me katsoimme viime viikolla.

133
00:05:38,450 --> 00:05:41,780
Jos sanot rikkoa yksi niistä,
aina, kun ohjelma osuu, että

134
00:05:41,780 --> 00:05:44,290
se tulee odottaa sinua
kertoa se, mitä tehdä.

135
00:05:44,290 --> 00:05:47,860
Ennen se vain toteuttaa niin sinua
voisi todella astu toiminto

136
00:05:47,860 --> 00:05:49,020
ja katso mitä tapahtuu.

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

138
00:05:50,370 --> 00:05:53,515
Joten seuraavan, vain hyppää yli
seuraavalle riville, menee toimintoja.

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

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

141
00:05:55,560 --> 00:05:56,810
Nämä ovat kaikki hieman abstrakteja.

142
00:05:56,810 --> 00:06:00,530
Joten, olen juuri menossa ajaa niiden läpi,
mutta näet ne käytössä toinen.

143
00:06:00,530 --> 00:06:01,810
>> Astu toimintoa.

144
00:06:01,810 --> 00:06:04,170
Joten kuten sanoin,
kuten swap, se olisi

145
00:06:04,170 --> 00:06:07,110
voit itse kuin jos olet
kuten fyysisesti tehostamalla sisällä,

146
00:06:07,110 --> 00:06:10,990
voit sotkea niitä muuttujia, tulostaa
mitä he ovat, mitä on tekeillä.

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

148
00:06:12,140 --> 00:06:14,830
Luettelo kirjaimellisesti vain tulostaa
ulos ympäröivään koodi.

149
00:06:14,830 --> 00:06:17,570
Joten, jos sellainen unohtaa
missä olet oman ohjelman,

150
00:06:17,570 --> 00:06:19,880
tai mietit
mitä tapahtuu sen ympärillä,

151
00:06:19,880 --> 00:06:23,790
tämä vain tulostaa segmentin
samankaltaisten viisi tai kuusi riviä sen ympärille.

152
00:06:23,790 --> 00:06:26,080
Joten, voit saada suuntautunut
siitä, missä olet.

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

154
00:06:27,230 --> 00:06:28,650
>> Tulosta jokin muuttuja.

155
00:06:28,650 --> 00:06:34,590
Joten, jos sinulla on avain, kuten
Caesar, että me tarkastelemme.

156
00:06:34,590 --> 00:06:36,220
Voit sanoa Tulosta Key missään vaiheessa.

157
00:06:36,220 --> 00:06:40,070
Se kerron teille, mitä arvoa on niin
että ehkä jossain matkan varrella,

158
00:06:40,070 --> 00:06:42,070
sinun korvasi avain.

159
00:06:42,070 --> 00:06:45,495
Voit itse kertoa, että koska
voit itse todeta, että arvo.

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

161
00:06:46,500 --> 00:06:48,780
>> Vuonna paikalliset, vain tulostaa
Anna paikallisia muuttujia.

162
00:06:48,780 --> 00:06:53,120
Joten, milloin olet sisällä silmukan,
ja haluat vain nähdä kuin, oh.

163
00:06:53,120 --> 00:06:54,270
Mikä on minun minä?

164
00:06:54,270 --> 00:06:57,020
Mikä on tämä keskeinen arvo
että minä alustaa täällä?

165
00:06:57,020 --> 00:06:58,537
Mikä on viesti tässä vaiheessa?

166
00:06:58,537 --> 00:07:00,370
Se vain tulostaa kaikki
niistä, jotta voit

167
00:07:00,370 --> 00:07:04,330
ei tarvitse erikseen
sanoa, Print I. Tulosta viesti.

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

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

170
00:07:06,190 --> 00:07:07,700
Ja sitten Näyttö.

171
00:07:07,700 --> 00:07:10,370
Mitä se tekee, on kuin
selata ohjelman

172
00:07:10,370 --> 00:07:13,980
se täytyy vain varmistaa, että se on
näyttänyt tiettyjä muuttuja

173
00:07:13,980 --> 00:07:14,780
joka kohdasta.

174
00:07:14,780 --> 00:07:17,160
Niin että te also-- --it on
eräänlainen oikotie, jossa

175
00:07:17,160 --> 00:07:19,530
sinun ei tarvitse pitää käynnissä kuin, oh.

176
00:07:19,530 --> 00:07:23,150
Tulosta Key tai Tulosta I. Se vain
automaattisesti tehdä sen sinulle.

177
00:07:23,150 --> 00:07:25,959
>> Niin, että aiomme
nähdä, miten tämä menee.

178
00:07:25,959 --> 00:07:28,000
Aion yrittää ja kytkin
yli minun laite.

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

180
00:07:30,200 --> 00:07:31,271
Nähdä, jos voin tehdä tämän.

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

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

183
00:07:40,970 --> 00:07:42,370
Olemme juuri menossa peilata sitä.

184
00:07:42,370 --> 00:07:44,530
Ei ole mitään hullua
minun laptop anyways.

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

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

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

188
00:07:57,030 --> 00:08:01,054
Tämän on oltava tämä.

189
00:08:01,054 --> 00:08:01,795
Se on niin pieni.

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

191
00:08:03,730 --> 00:08:05,120
Katsotaanpa, jos voimme tehdä tämän.

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

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

194
00:08:10,940 --> 00:08:15,305
Alice on ilmeisesti kamppailee
tässä vain vähän,

195
00:08:15,305 --> 00:08:17,995
mutta saamme sen momento.

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

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

198
00:08:22,020 --> 00:08:25,900
Olemme juuri menossa nostaa.

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

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

201
00:08:29,380 --> 00:08:31,679
Voivatko kaikki sellainen nähdä, että?

202
00:08:31,679 --> 00:08:32,470
Ehkä vähän?

203
00:08:32,470 --> 00:08:33,594
Tiedän, se on vähän pieni.

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

205
00:08:34,570 --> 00:08:37,530
Et voi täysin selvittää
miten tämä suurempi.

206
00:08:37,530 --> 00:08:38,350
Jos joku tietää.

207
00:08:38,350 --> 00:08:40,309
Ei kukaan tiedä, miten tehdä se iso?

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

209
00:08:40,932 --> 00:08:42,140
Aiomme roll sitä.

210
00:08:42,140 --> 00:08:45,801
Ei ole väliä muutenkaan, koska se on vain
se koodi, että te pitäisi

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

212
00:08:46,300 --> 00:08:48,310
>> Mikä on tärkeämpää
on päätelaite täällä.

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

214
00:08:52,840 --> 00:08:58,690
Ja meillä on täällä Miksi se on niin pieni?

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

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

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

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

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

220
00:09:09,500 --> 00:09:10,880
Miten tämä on?

221
00:09:10,880 --> 00:09:11,770
Pois sieltä.

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

223
00:09:19,370 --> 00:09:21,810
Onko se parempi kaikille?

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

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

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

227
00:09:25,830 --> 00:09:28,220
>> Tiedät, kun olet CS
luokan teknisiä ongelmia

228
00:09:28,220 --> 00:09:32,971
ovat tavallaan osa the--
Joten, nyt tyhjentää.

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

230
00:09:33,470 --> 00:09:38,060
Niin, täällä jaksossa,
joka meillä oli täällä.

231
00:09:38,060 --> 00:09:40,830
Caesar on suoritettava tiedosto.

232
00:09:40,830 --> 00:09:41,800
Joten tein sen.

233
00:09:41,800 --> 00:09:46,370
Niin, yksi asia on ymmärrettävä kanssa GDB on
että se toimii vain ohjelmatiedostoja.

234
00:09:46,370 --> 00:09:48,040
Joten, et voi käyttää sitä dotsy.

235
00:09:48,040 --> 00:09:50,532
Sinun täytyy itse tehdä
Varmista, että koodi kokoaa,

236
00:09:50,532 --> 00:09:51,865
ja että se voi todella ajaa.

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

238
00:09:52,970 --> 00:09:56,186
>> Joten varmista, että jos se ei
koota, saada se koota,

239
00:09:56,186 --> 00:09:57,810
jotta voit sellaista ajaa sen läpi.

240
00:09:57,810 --> 00:10:04,590
Joten aloittaa GDB, kaikki te teette,
Gloria tyyppi GDB, ja sitten vain

241
00:10:04,590 --> 00:10:06,250
tiedosto, jonka haluat.

242
00:10:06,250 --> 00:10:08,240
Olen aina kirjoitusvirheitä Caesar.

243
00:10:08,240 --> 00:10:11,730
Mutta haluat varmistaa,
koska se on suoritettavan,

244
00:10:11,730 --> 00:10:14,210
TI: n piste flash jotta
tarkoittaa olet menossa

245
00:10:14,210 --> 00:10:19,240
ajaa CSI aiot toteuttaa
Tämän tiedostot joko debugger.

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

247
00:10:19,910 --> 00:10:22,885
Joten, et, että saat
tällainen siansaksaa.

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

249
00:10:24,250 --> 00:10:25,750
Se on vain kaikki asiat noin virheenkorjauksen.

250
00:10:25,750 --> 00:10:28,200
Sinun ei todellakaan tarvitse
murehtia sitä juuri nyt.

251
00:10:28,200 --> 00:10:31,460
Ja kuten näette, meillä on tämä
avoin parens, BKT, lähellä parens,

252
00:10:31,460 --> 00:10:34,690
ja juuri sellainen näyttää
meidän komentoriviltä, ​​eikö?

253
00:10:34,690 --> 00:10:37,010
>> Joten, mitä haluamme do--
--So, Ensimmäinen asia

254
00:10:37,010 --> 00:10:39,570
me haluamme valita
paikka rikkoa sitä.

255
00:10:39,570 --> 00:10:42,332
Niin, siellä on yksi vika
Tässä Caesar ohjelmaan

256
00:10:42,332 --> 00:10:44,290
että esittelen, että
aiomme selvittää.

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

258
00:10:45,330 --> 00:10:56,350
Se Mitä se on se vie tulo
Barfoo kokonaan isoilla kirjaimilla, ja jostain syystä

259
00:10:56,350 --> 00:11:01,950
se ei muuta A. Se vain jää
yksin, on kaikkea muuta oikein,

260
00:11:01,950 --> 00:11:03,980
mutta toinen kirje
Pysyy ennallaan.

261
00:11:03,980 --> 00:11:07,120
Joten, aiomme yrittää
selvittää, miksi näin on.

262
00:11:07,120 --> 00:11:10,440
Joten, ensimmäinen asia mitä yleensä
haluavat tehdä, kun aloitat GDB-

263
00:11:10,440 --> 00:11:12,010
on selvittää, mistä rikkoa sitä.

264
00:11:12,010 --> 00:11:14,956
>> Joten Caesar on melko lyhyt ohjelma.

265
00:11:14,956 --> 00:11:16,330
Meillä on vain yksi toiminto, eikö?

266
00:11:16,330 --> 00:11:18,520
Mikä oli meidän toiminnon Caesar?

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

268
00:11:19,590 --> 00:11:24,350
On vain yksi toiminto, Main oikea?

269
00:11:24,350 --> 00:11:26,490
Tärkein on funktio
kaikki ohjelmat.

270
00:11:26,490 --> 00:11:29,230
Jos sinulla ei ole Main, voisin
olla hieman huolissaan juuri nyt,

271
00:11:29,230 --> 00:11:31,000
mutta toivon teille kaikille oli Main siellä.

272
00:11:31,000 --> 00:11:34,150
Joten, mitä voimme tehdä, on voimme
vain rikkoa Main, noin vain.

273
00:11:34,150 --> 00:11:35,190
Niin, se sanoo, OK.

274
00:11:35,190 --> 00:11:37,430
Asetamme murtuessa ketään.

275
00:11:37,430 --> 00:11:42,870
>> Joten, nyt asia on muistaa Caesar
kestää yhden komentorivillä oikeus

276
00:11:42,870 --> 00:11:45,150
ja emme ole tehneet, että missään vielä.

277
00:11:45,150 --> 00:11:47,560
Joten, mitä tehdä, on, kun
voit itse mennä ajaa

278
00:11:47,560 --> 00:11:51,540
ohjelman, mitään ohjelmaa, joka olet
käynnissä GDB- joka tarvitsee komentoriviltä

279
00:11:51,540 --> 00:11:55,010
argumentteja, aiot syöttää
kun aloitat käynnissä se.

280
00:11:55,010 --> 00:11:59,280
Eli tässä tapauksessa, teemme
Juokse keskeinen kolme.

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

282
00:12:00,770 --> 00:12:02,040
Ja se todella alkaa.

283
00:12:02,040 --> 00:12:08,480
>> Joten, jos näet täällä, meillä on
Jos RC ei ole sama kuin 2.

284
00:12:08,480 --> 00:12:12,210
Joten jos te kaikki on
että tiedosto, joka Lähetin ylös

285
00:12:12,210 --> 00:12:15,100
näet, että se on kuin
Ensimmäinen rivi meidän päätehtävä, eikö?

286
00:12:15,100 --> 00:12:17,890
Se tarkistaa, onko meillä
oikea määrä argumentteja.

287
00:12:17,890 --> 00:12:20,620
Joten, jos mietit
jos RC on oikea,

288
00:12:20,620 --> 00:12:23,250
voit tehdä jotain aivan Tulosta RC.

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

290
00:12:24,380 --> 00:12:28,640
RC on kaksi, joka on
mitä odotimme, eikö?

291
00:12:28,640 --> 00:12:32,010
>> Joten, voimme mennä seuraavaksi,
ja jatkaa kautta.

292
00:12:32,010 --> 00:12:33,200
Niin, meillä on joitakin keskeisiä siellä.

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

294
00:12:34,260 --> 00:12:37,090
Ja voimme painaa läpi keskeiset
varmistaa, että on oikea.

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

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

297
00:12:39,500 --> 00:12:41,210
Ei aivan sitä mitä odotimme.

298
00:12:41,210 --> 00:12:44,810
Niin, yksi asia on ymmärrettävä
GDB myös, on

299
00:12:44,810 --> 00:12:49,000
että se ei ole ennen kuin olet itse osuma
Seuraavaksi tästä, jonka olet juuri nähnyt

300
00:12:49,000 --> 00:12:50,720
on todella toteutettu.

301
00:12:50,720 --> 00:12:53,870
Eli tässä tapauksessa Key
ei ole vielä asetettu.

302
00:12:53,870 --> 00:12:57,050
Niin, Key on joitakin roskat arvo
että näet pohjassa siellä.

303
00:12:57,050 --> 00:13:03,680
Negatiivinen $ 120-- --It miljardista
ja jotain outoa asiat oikein?

304
00:13:03,680 --> 00:13:05,340
Se ei ole avain, että odotimme.

305
00:13:05,340 --> 00:13:10,720
Mutta jos me osuma Seuraava ja sitten me
yrittää Tulosta avain, se on kolme.

306
00:13:10,720 --> 00:13:11,710
>> Jokainen nähdä, että?

307
00:13:11,710 --> 00:13:13,780
Joten, jos saat jotain
että et pidä, odota.

308
00:13:13,780 --> 00:13:15,540
Tämä on täysin
väärin, ja en tiedä

309
00:13:15,540 --> 00:13:20,150
miten tämä tapahtuisi, koska kaikki mitä haluan
tehdä, on antaa numeron, muuttuja,

310
00:13:20,150 --> 00:13:22,900
yrittää osua Seuraavaksi kokeile tulostusta
sen uudelleen, ja katso jos se toimii.

311
00:13:22,900 --> 00:13:27,830
Koska se on vain menossa toteuttaa ja
todella antaa jotain, kun olet

312
00:13:27,830 --> 00:13:29,340
osuma Seuraava.

313
00:13:29,340 --> 00:13:30,336
Järkevää kaikille?

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

315
00:13:30,836 --> 00:13:33,220
>> SPEAKER 2: Kun satunnainen
numerot mitä se tarkoittaa?

316
00:13:33,220 --> 00:13:34,790
>> SPEAKER 1: Se on vain satunnaisesti.

317
00:13:34,790 --> 00:13:35,710
Se on vain roskaa.

318
00:13:35,710 --> 00:13:38,320
Se on vain jotain, että
Tietokone satunnaisesti luovuttaa.

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

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

321
00:13:40,220 --> 00:13:45,760
Joten, nyt voimme liikkua, ja niin
Nyt meillä on tämä pelkkää tekstiä GetString.

322
00:13:45,760 --> 00:13:48,600
Joten, haluan vain esitellä mitä
tapahtuu, kun me osuma Seuraava täällä.

323
00:13:48,600 --> 00:13:51,320
Meidän GDB- sellainen katoaa, eikö?

324
00:13:51,320 --> 00:13:55,720
Tämä johtuu GetString
nyt pystyvät, eikö?

325
00:13:55,720 --> 00:14:01,460
Joten, kun näimme pelkkää tekstiä on yhtä kuin
GetString, avoin parens ja parens,

326
00:14:01,460 --> 00:14:04,380
ja me osuma Seuraavaksi tästä on
toteutettuja nyt.

327
00:14:04,380 --> 00:14:06,580
Niin, se odottaa
meille syöttää jotain.

328
00:14:06,580 --> 00:14:13,560
>> Joten, aiomme syöttää ruokamme joka
on, mitä se ei ole kuten jo sanoin

329
00:14:13,560 --> 00:14:18,020
ja että vain sanoo, että se on
päättynyt täytäntöönpanosta, että suljettu

330
00:14:18,020 --> 00:14:19,980
kiinnike tarkoittaa että se on
poistuminen ulos että silmukka.

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

332
00:14:21,170 --> 00:14:25,420
Joten, voimme lyödä Seuraavaksi ja nyt, koska olen
varma, että olet kaikki tutut Caesar,

333
00:14:25,420 --> 00:14:27,260
tämä on, mitä tämä linja tulee tekemään.

334
00:14:27,260 --> 00:14:32,030
Se on int i on 0, n on
Strlen, pelkkää tekstiä, ja sitten

335
00:14:32,030 --> 00:14:33,960
I on pienempi kuin N, I, plus, plus.

336
00:14:33,960 --> 00:14:35,210
Mikä on tämä silmukka aiot tehdä?

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

338
00:14:37,900 --> 00:14:39,160
Avaa viesti.

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

340
00:14:39,770 --> 00:14:41,330
Joten, nyt alkaa tehdä niin.

341
00:14:41,330 --> 00:14:47,210
>> Joten, jos tämä ehto
täsmää, meidän ensimmäinen?

342
00:14:47,210 --> 00:14:52,250
Jos se on B, se on pelkkää tekstiä I. Me
voivat saada tietoa paikallisia.

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

344
00:14:53,610 --> 00:14:57,970
Joten, minä on nolla, ja jos kuusi, joka
odotamme, ja meidän avain on kolme.

345
00:14:57,970 --> 00:14:59,227
Kaikki tämä järkevää, eikö?

346
00:14:59,227 --> 00:15:01,310
Nämä numerot ovat kaikki
mitä niiden pitäisi olla.

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

348
00:15:02,590 --> 00:15:03,870
Niin, hyräillä?

349
00:15:03,870 --> 00:15:05,620
SPEAKER 3: Olen
satunnaislukuja minun.

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

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: No, voimme check-- --we
voi jutella, että toinen.

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

353
00:15:14,110 --> 00:15:15,750
Mutta sinun pitäisi saada tämä.

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

355
00:15:17,700 --> 00:15:20,130
Joten, jos meillä on pääomaa
B meidän ensimmäinen,

356
00:15:20,130 --> 00:15:22,080
Tämä tila on kiinni se, eikö?

357
00:15:22,080 --> 00:15:27,120
Joten, jos me osuma Seuraavaksi näemme
että tämä olisi tosiasiassa suorittaa.

358
00:15:27,120 --> 00:15:29,220
Koska jos olet seuraavista
pitkin koodissa,

359
00:15:29,220 --> 00:15:33,460
tämä linja täällä, missä tavallinen teksti I
korvataan tämän aritmeettinen,

360
00:15:33,460 --> 00:15:35,720
pannaan täytäntöön ainoastaan, jos Jos
ehto on oikea oikea?

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

362
00:15:36,905 --> 00:15:40,240
>> GDB on vain menossa näyttämään
asioita, jotka ovat tosiasiassa ajetaan.

363
00:15:40,240 --> 00:15:45,140
Joten jos tämä Jos ehto ei täyty, se
juuri menossa siirtyä seuraavalle riville.

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

365
00:15:46,540 --> 00:15:48,510
Niin, meillä on tuo.

366
00:15:48,510 --> 00:15:51,171
Tämä teline tarkoittaa että se
suljettu pois, että silmukka nyt.

367
00:15:51,171 --> 00:15:52,420
Niin, se tulee aloittaa uudelleen.

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

369
00:15:54,760 --> 00:15:56,280
Aivan niin.

370
00:15:56,280 --> 00:15:59,120
Niin, että voimme saada tietoa
meidän paikalliset täällä,

371
00:15:59,120 --> 00:16:02,575
ja me näemme, että ensimmäinen
kirjain on muuttunut, eikö?

372
00:16:02,575 --> 00:16:05,150
Se on nyt E, kuin sen pitäisi olla.

373
00:16:05,150 --> 00:16:07,360
Voimme siis jatkaa.

374
00:16:07,360 --> 00:16:08,500
>> Ja meillä on tämä tarkastus.

375
00:16:08,500 --> 00:16:09,916
Ja tämä tarkistus pitäisi toimia, eikö?

376
00:16:09,916 --> 00:16:12,570
Se on A. Se pitäisi muuttaa
kolme kirjainta eteenpäin.

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

378
00:16:14,320 --> 00:16:16,530
Mutta jos huomaat, me
saada jotain erilaista.

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

380
00:16:17,580 --> 00:16:22,860
Joten tässä tapauksessa täällä, se kiinni
se, ja niin tämä linja toteutetaan,

381
00:16:22,860 --> 00:16:28,620
joka muutti meidän B.
Mutta tässä tapauksessa täällä,

382
00:16:28,620 --> 00:16:32,860
meillä on, että se vain ohitetaan se,
ja meni [? L Siff. ?]

383
00:16:32,860 --> 00:16:34,660
Joten jotain siellä tapahtuu.

384
00:16:34,660 --> 00:16:37,780
Mitä tuo kertoo teille, että,
me tiedämme, että se olisi kiinni täällä,

385
00:16:37,780 --> 00:16:39,200
mutta se ei ole.

386
00:16:39,200 --> 00:16:42,210
Näkeekö kukaan, mitä meidän
Ongelmana on, että linja?

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

388
00:16:45,380 --> 00:16:46,969
Se on hyvin minuutin juttu.

389
00:16:46,969 --> 00:16:48,510
Ja voit myös tarkastella koodia.

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

391
00:16:49,980 --> 00:16:54,940
Se on myös line-- unohtaa, mitä linjaa se on
vuonna there-- mutta se on [kuultavissa].

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

393
00:16:55,480 --> 00:16:58,639
>> SPEAKER 4: Se on suurempi kuin
sivulla, jos olet lukenut sen kirjan.

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

395
00:16:59,430 --> 00:17:02,620
Niin, debuggeri voinut kertoa
teille, mutta debuggeri

396
00:17:02,620 --> 00:17:05,880
voisi saada sinut alas linja
että tiedät ei toimi.

397
00:17:05,880 --> 00:17:09,319
Ja joskus, kun erityisesti
myöhemmin lukukauden, kun

398
00:17:09,319 --> 00:17:12,910
olet tekemisissä sata,
sata muutaman rivin koodia, ja voit

399
00:17:12,910 --> 00:17:16,190
en tiedä missä se ei ole,
tämä on hyvä tapa tehdä se.

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

401
00:17:17,900 --> 00:17:18,989
Niin, löysimme bug.

402
00:17:18,989 --> 00:17:21,530
Voit korjata sen tiedoston,
ja sitten voisi käyttää sitä uudelleen,

403
00:17:21,530 --> 00:17:23,029
ja kaikki toimisi täydellisesti.

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

405
00:17:24,970 --> 00:17:30,590
Ja suurin asia on
tämä voi tuntua, OK.

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

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

408
00:17:31,370 --> 00:17:32,744
Tiesit mitä etsit.

409
00:17:32,744 --> 00:17:34,910
Niin, tiesit mitä tehdä.

410
00:17:34,910 --> 00:17:39,021
>> GDB- voi olla erittäin hyödyllistä, koska olet
voi tulostaa kaikki nämä asiat, jotka olet

411
00:17:39,021 --> 00:17:39,520
ei.

412
00:17:39,520 --> 00:17:41,160
Se on paljon enemmän hyötyä kuin printf.

413
00:17:41,160 --> 00:17:43,440
Kuinka moni teistä käyttää
kuten printf lausunnot

414
00:17:43,440 --> 00:17:46,200
selvittää, missä vika on, eikö?

415
00:17:46,200 --> 00:17:48,450
Niin, tässä, et
täytyy pitää menossa takaisin,

416
00:17:48,450 --> 00:17:51,139
ja haluavat kommentoi
Printf, tai kommentoimalla ulos,

417
00:17:51,139 --> 00:17:52,930
ja selvittää, mitä
kannattaa tulostaa.

418
00:17:52,930 --> 00:17:55,670
Tämä oikeastaan ​​vain voit
selata, tulostaa asiat

419
00:17:55,670 --> 00:18:00,000
koska olet menossa läpi, joten voit
tarkkailla, miten ne muuttuvat reaaliajassa,

420
00:18:00,000 --> 00:18:02,190
koska ohjelma on käynnissä.

421
00:18:02,190 --> 00:18:04,390
>> Ja se vie vähän
hieman totuttelua.

422
00:18:04,390 --> 00:18:07,850
Voin lämpimästi suositella vain eräänlainen
olemisen hieman turhautuneita siihen

423
00:18:07,850 --> 00:18:08,930
juuri nyt.

424
00:18:08,930 --> 00:18:13,450
Jos vietät tunnin aikana
ensi viikolla opetella käyttämään GDB,

425
00:18:13,450 --> 00:18:16,140
säästät itsesi
niin paljon aikaa myöhemmin.

426
00:18:16,140 --> 00:18:18,750
Ja kirjaimellisesti. kerromme
Tämän ihmisiä joka vuosi,

427
00:18:18,750 --> 00:18:23,890
ja muistan, kun otin
luokka, olin kuin, aion olla hieno.

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

429
00:18:24,700 --> 00:18:27,030
PSET 6 tuli ja olin
kuten, aion oppia

430
00:18:27,030 --> 00:18:29,500
miten käyttää GDB- koska en
tietää, mitä täällä tapahtuu.

431
00:18:29,500 --> 00:18:32,940
>> Joten jos otat aikaa niin
käyttää sitä pienempiä ohjelmia

432
00:18:32,940 --> 00:18:35,697
että aiot olla
työskentelevät, kuten työskentely

433
00:18:35,697 --> 00:18:37,530
kautta jotain
Visionare, kuten tämä.

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

435
00:18:38,800 --> 00:18:42,850
Tai jos haluat lisää Käytännössä olen varma
Voisin keksiä buginen ohjelmia,

436
00:18:42,850 --> 00:18:45,300
voit debug jos haluat.

437
00:18:45,300 --> 00:18:49,300
>> Mutta jos vain kestää jonkin aikaa saada
käyttää sitä, vain leikkiä sen kanssa,

438
00:18:49,300 --> 00:18:50,550
se todella toimii hyvin.

439
00:18:50,550 --> 00:18:52,591
Ja se on todella yksi
niitä asioita, jotka juuri

440
00:18:52,591 --> 00:18:57,340
täytyy yrittää ja saada kädet likainen
kanssa, ennen kuin todella ymmärtää se.

441
00:18:57,340 --> 00:19:02,090
Olen oikeastaan ​​vain ymmärtänyt sitä kerran
Jouduin debug asioita sen kanssa,

442
00:19:02,090 --> 00:19:08,170
ja se on paljon mukavampi olla ajatus
miten debug mieluummin ennemmin kuin myöhemmin.

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

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

445
00:19:09,625 --> 00:19:12,960
Tiedän, että on tavallaan kuin
pikakurssin GDB,

446
00:19:12,960 --> 00:19:16,400
ja aion ehdottomasti työskennellä saada
Näiden etsiä isompi ensi kerralla.

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

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

449
00:19:18,280 --> 00:19:20,390
>> Joten, jos menemme takaisin meidän PowerPoint.

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

451
00:19:27,194 --> 00:19:28,110
Onko tämä menossa töihin?

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

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

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

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

456
00:19:31,600 --> 00:19:35,480
Joten, jos joskus tarvitset jotakin
ne uudelleen, siellä on lista.

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

458
00:19:37,160 --> 00:19:40,830
Joten Binäärihaku, jonka kaikki
muistaa suuri spektaakkeli David

459
00:19:40,830 --> 00:19:42,259
repimässä puhelinluetteloita kahtia.

460
00:19:42,259 --> 00:19:44,050
En todellakaan saa
puhelinluetteloita enää,

461
00:19:44,050 --> 00:19:46,530
koska kuten Mistä
saada puhelinluetteloita näinä päivinä?

462
00:19:46,530 --> 00:19:48,220
En todellakaan tiedä.

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

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

465
00:19:50,590 --> 00:19:52,464
Muistaako kukaan
miten Binary Search toimii?

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

467
00:19:54,380 --> 00:19:55,220
Kuka tahansa?

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

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: Tiedätkö milloin
sinä katsot mikä puoli

470
00:19:58,283 --> 00:20:01,146
se olisi sen pohjalta,
ja päästä eroon toinen puoli.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER 1 Täsmälleen.

472
00:20:01,896 --> 00:20:06,290
Joten, Binäärihaku, se on eräänlainen a--
--we haluavat kutsua sitä hajoita ja hallitse.

473
00:20:06,290 --> 00:20:09,170
Joten, mitä voit tehdä on
näytät keskellä,

474
00:20:09,170 --> 00:20:11,990
ja näet, jos se vastaa
mitä etsit.

475
00:20:11,990 --> 00:20:15,420
Ja jos ei, niin yrität
selvittää, se aikoo jättää

476
00:20:15,420 --> 00:20:16,450
puoli tai oikea puoli.

477
00:20:16,450 --> 00:20:19,325
Niin, tämä voisi olla, jos etsit
jotain, joka on aakkosjärjestyksessä,

478
00:20:19,325 --> 00:20:20,720
näet, oh.

479
00:20:20,720 --> 00:20:22,750
Onko Allison tullut ennen M?

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

481
00:20:23,250 --> 00:20:25,030
Joten, aiomme
katsokaa alkupuoliskolla.

482
00:20:25,030 --> 00:20:26,450
>> Tai se voi olla kuin numeroita.

483
00:20:26,450 --> 00:20:28,830
Mitään, että voit
vertaa, se voidaan lajitella.

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

485
00:20:29,920 --> 00:20:31,260
Voit käyttää binary haku.

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

487
00:20:32,340 --> 00:20:37,455
Niin, kukaan muistaa tämä
kaavio tai mitä tämä on?

488
00:20:37,455 --> 00:20:39,520
Se Asymptoottinen monimutkaisuus.

489
00:20:39,520 --> 00:20:42,830
Niin, tämä kuvaaja vain
kuvataan, kuinka kauan se

490
00:20:42,830 --> 00:20:46,230
vie sinua ratkaisemaan ongelman
voit lisätä monia asioita

491
00:20:46,230 --> 00:20:47,090
että käytät.

492
00:20:47,090 --> 00:20:51,260
>> Niin, meillä on N, joka on lineaarinen aika.

493
00:20:51,260 --> 00:20:54,560
Jos N yli kaksi, joka on hieman
parempi, silti kasvaa erittäin nopeasti.

494
00:20:54,560 --> 00:20:58,360
Ja sitten olemme Kirjaudu, joka on
mitä pidämme binäärihaku.

495
00:20:58,360 --> 00:21:03,630
Jos huomaamme, sillä ongelma
saa paljon ja paljon suurempi,

496
00:21:03,630 --> 00:21:06,600
aikaa se vie sinua ratkaisemaan sen
ei oikeastaan ​​lisätä, että paljon.

497
00:21:06,600 --> 00:21:09,010
Se on kuin verrattavissa
täällä alussa.

498
00:21:09,010 --> 00:21:10,060
Olet kuin, OK.

499
00:21:10,060 --> 00:21:13,000
Mitään täällä ei oikeastaan
väliä kumpi käytämme,

500
00:21:13,000 --> 00:21:16,220
mutta saat ulos miljoonaa miljardia.

501
00:21:16,220 --> 00:21:20,010
Yrität löytää some-- --you're
yrittää löytää neulaa heinäsuovasta.

502
00:21:20,010 --> 00:21:21,550
>> Luulen haluat tämän ongelman.

503
00:21:21,550 --> 00:21:25,850
Haluat tätä monimutkaisuutta, ei
lineaarinen koska kaikille teille

504
00:21:25,850 --> 00:21:30,049
tietää gonna hakuja
jokainen yksittäinen neula, asia heinää,

505
00:21:30,049 --> 00:21:31,340
yrittää etsiä neulan.

506
00:21:31,340 --> 00:21:34,730
Ja joka ei ole liian hauskaa mielestäni.

507
00:21:34,730 --> 00:21:35,500
Pidän nopeasti.

508
00:21:35,500 --> 00:21:36,620
Pidän tehokas.

509
00:21:36,620 --> 00:21:40,450
Ja niin ahkera opiskelijaa
kaverit ovat, tiedät työskennellä fiksummin,

510
00:21:40,450 --> 00:21:43,010
ei kovemmin tyyppinen asia, miten
voi keksiä näitä algoritmeja.

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

512
00:21:45,110 --> 00:21:47,910
>> Joten, aiomme kävellä
läpi vain nopea esimerkki.

513
00:21:47,910 --> 00:21:51,090
Mielestäni te pitäisi olla
käsi binäärihaku,

514
00:21:51,090 --> 00:21:54,352
mutta jos joku on hieman
sumea, haluamme vahvistaa sitä,

515
00:21:54,352 --> 00:21:56,310
aiomme vain mennä
läpi esimerkki tästä.

516
00:21:56,310 --> 00:21:59,490
Joten etsimme jos
array sisältää seitsemän.

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

518
00:22:00,540 --> 00:22:06,010
>> Joten ensimmäinen asia mitä teemme on
katso keskellä, eikö?

519
00:22:06,010 --> 00:22:09,340
Ja myös aiot olla koodaus
Binary Etsi vain toinen.

520
00:22:09,340 --> 00:22:11,310
Niin, se tulee olemaan hauskaa.

521
00:22:11,310 --> 00:22:13,710
Joten katsomme
keskellä pieni taulukot 3.

522
00:22:13,710 --> 00:22:15,501
Onko 3 yhtä 7?

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

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

525
00:22:18,670 --> 00:22:19,550
Se on kuusi.

526
00:22:19,550 --> 00:22:21,480
Niin, on se alle
tai suurempi kuin seitsemän?

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

528
00:22:23,080 --> 00:22:23,960
Alle.

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

530
00:22:24,570 --> 00:22:25,170
Mukava työ kaverit.

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

532
00:22:25,569 --> 00:22:27,360
Tunnen Pidän minun pitäisi
karkkia koska en

533
00:22:27,360 --> 00:22:29,460
halua heittää sen ulos metriä.

534
00:22:29,460 --> 00:22:30,270
Se, mitä aion tehdä ensi viikolla.

535
00:22:30,270 --> 00:22:31,436
Se pitää teidät teräviä.

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

537
00:22:32,560 --> 00:22:34,690
>> Joten, me heittää pois, että
alkupuoliskolla, eikö?

538
00:22:34,690 --> 00:22:35,670
se oli alle.

539
00:22:35,670 --> 00:22:39,325
me tiedämme, että kaiken
siitä, että vasemmalla puolella

540
00:22:39,325 --> 00:22:41,700
tulee olemaan pienempi kuin mitä
me todella etsivät.

541
00:22:41,700 --> 00:22:43,491
Joten, ei ole tarvetta
kiinnittää siihen huomiota.

542
00:22:43,491 --> 00:22:45,120
Vain unohtaa sen.

543
00:22:45,120 --> 00:22:48,720
Joten, nyt katsomme meidän oikealla puolella,
ja katsomme keskellä tuolla,

544
00:22:48,720 --> 00:22:50,510
ja nyt se on yhdeksän.

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

546
00:22:55,510 --> 00:22:57,470
Suurempi kuin mitä me olemme
etsimässä, eikö?

547
00:22:57,470 --> 00:22:59,860
Joten, aiomme heittää
pois kaiken oikealle.

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

549
00:23:00,970 --> 00:23:01,940
Niin.

550
00:23:01,940 --> 00:23:03,700
Nyt kaikki olemme jäljelle jää yksi.

551
00:23:03,700 --> 00:23:07,760
Niin voimme tarkistaa, on tämä yksi mitä
etsimme? se on.

552
00:23:07,760 --> 00:23:08,970
Löysimme mitä halusimme.

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

554
00:23:10,440 --> 00:23:11,690
Joten olemme tehneet.

555
00:23:11,690 --> 00:23:12,550
Bilinear Hae.

556
00:23:12,550 --> 00:23:15,740
>> Ja jos huomaat, me
oli seitsemän tuloa siellä.

557
00:23:15,740 --> 00:23:24,320
Se kesti vain meitä kuin kolme kertaa,
mutta jos teet kuten miljardia,

558
00:23:24,320 --> 00:23:28,190
Tiedättekö kuinka monta askelta se olisi
ota, jos meillä olisi neljän miljardin asioita?

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

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

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

562
00:23:32,286 --> 00:23:33,960
Se on 32.

563
00:23:33,960 --> 00:23:37,110
32 vaiheet löytää jotain
vuonna neljän miljardin

564
00:23:37,110 --> 00:23:39,650
alkiotaulukon koska kahden potensseja.

565
00:23:39,650 --> 00:23:43,550
Joten kaksi on 32, on neljä miljardia euroa.

566
00:23:43,550 --> 00:23:50,430
>> Joten ihan hullu miten olet vielä sisällä
kuten melko pieni määrä vaiheita

567
00:23:50,430 --> 00:23:52,650
löytää jotain
neljän miljardin elementtejä.

568
00:23:52,650 --> 00:23:55,730
Niin Komitea suosittelee, että olemme
menossa koodaamaan tämän

569
00:23:55,730 --> 00:23:58,950
joten te voi itse
sellaista nähdä, miten tämä toimii.

570
00:23:58,950 --> 00:24:01,520
Okei, joten te voi koodata.

571
00:24:01,520 --> 00:24:04,100
Aion antaa te
puhua vähän.

572
00:24:04,100 --> 00:24:07,970
Tutustua ihmisiin ympärilläsi, joka on
mitä joku halusi viime jaksossa.

573
00:24:07,970 --> 00:24:10,280
>> Niin saat tietää ihmisiä ympärilläsi.

574
00:24:10,280 --> 00:24:11,305
Puhua vähän.

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

576
00:24:12,580 --> 00:24:15,730
Ja kaikki mitä haluan sinulta
kaverit nyt on vain

577
00:24:15,730 --> 00:24:17,575
yrittää luoda ääriviivat pseudokoodin.

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

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

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

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

582
00:24:23,320 --> 00:24:29,520
Haluan teiltä kaverit on olet
juuri menossa täyttää tässä taas asiassa.

583
00:24:29,520 --> 00:24:32,170
Joten olen ottanut ne ylemmän
ja alarajojen joka

584
00:24:32,170 --> 00:24:35,250
edustavat alussa
ja lopussa meidän array.

585
00:24:35,250 --> 00:24:40,440
Ja aiot todella
silmukan läpi ja selvittää

586
00:24:40,440 --> 00:24:42,470
mitä me teemme tämän, kun silmukka.

587
00:24:42,470 --> 00:24:45,810
>> Joten jos voit selvittää out-- Olen
vihje there-- mitkä ovat tapausten

588
00:24:45,810 --> 00:24:46,640
että meillä on täällä?

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

590
00:24:48,100 --> 00:24:51,560
Joten jos haluat selvittää
tapauksissa me pseudokoodina nämä

591
00:24:51,560 --> 00:24:53,350
ja sitten me itse koodata ne.

592
00:24:53,350 --> 00:24:55,330
Ja se tulee olemaan, minä
ajatella, toivottavasti se tulee

593
00:24:55,330 --> 00:24:56,788
olla hieman helpompaa kuin odotit.

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

595
00:24:57,554 --> 00:25:00,220
Koska se ei ole niin paljon koodia,
oikeastaan, mikä on todella hienoa.

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

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

598
00:25:35,018 --> 00:25:35,893
>> Opiskelija: [kuulumaton]?

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

600
00:25:36,984 --> 00:25:37,650
Ohjaaja: Kyllä.

601
00:25:37,650 --> 00:25:38,595
Siellä oli jotain
löytää keskellä.

602
00:25:38,595 --> 00:25:39,552
>> Opiskelija: Joten voimme käyttää sitä.

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

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

605
00:25:40,603 --> 00:25:42,950
Niin, että ensimmäinen asia, joka meidän täytyy tehdä.

606
00:25:42,950 --> 00:25:44,330
Niin löytää keskellä.

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

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

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

610
00:25:47,770 --> 00:25:55,010
Joten sinulla on idea siitä, miten voisimme
itse löytää keskellä koodilla?

611
00:25:55,010 --> 00:25:55,980
>> Opiskelija: Joo.

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

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

614
00:25:58,500 --> 00:25:59,500
Ohjaaja: Eli n yli 2.

615
00:25:59,500 --> 00:26:05,170
Niin yksi asia on muistaa, että
ylempi ja alempi rajat muuttuvat.

616
00:26:05,170 --> 00:26:08,110
Pidämme constricting osa
array etsimme.

617
00:26:08,110 --> 00:26:11,970
Joten n yli 2 toimii vain
Ensimmäisen mitä teemme.

618
00:26:11,970 --> 00:26:17,810
Joten kun ylempi ja alempi huomioon,
miten voisimme saada, että keski-elementti?

619
00:26:17,810 --> 00:26:20,640
Koska haluamme keskellä
ylemmän ja alemman, eikö?

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

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

622
00:26:22,494 --> 00:26:23,369
>> Opiskelija: [kuulumaton].

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

624
00:26:26,170 --> 00:26:28,080
>> Ohjaaja: Eli meillä on keskellä.

625
00:26:28,080 --> 00:26:32,730
Ja se tulee olemaan ylä- ja alempi yli 2.

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

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

628
00:26:35,690 --> 00:26:36,570
Siellä mennään.

629
00:26:36,570 --> 00:26:37,280
Yksi rivi alaspäin.

630
00:26:37,280 --> 00:26:38,560
Te olette matkalla.

631
00:26:38,560 --> 00:26:41,400
Joten nyt meillä on
keskimmäinen, mitä haluamme tehdä?

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

633
00:26:45,050 --> 00:26:45,900
Vain yleisesti.

634
00:26:45,900 --> 00:26:47,734
Sinun ei tarvitse koodata sitä.

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

636
00:26:48,335 --> 00:26:49,210
Opiskelija: [kuulumaton]?

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

638
00:27:00,310 --> 00:27:10,310
Ohjaaja: Joten se on plussaa, sillä olet
löytää keskimäärin kahden

639
00:27:10,310 --> 00:27:10,810
niistä.

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

641
00:27:11,890 --> 00:27:17,370
Joten jos luulet niitä eräänlaisina
lisätä sisään puolin,

642
00:27:17,370 --> 00:27:21,640
ajattele sitä, kun lähestyt
keskimmäinen, jonka haluat niin.

643
00:27:21,640 --> 00:27:27,150
Joten jos olit kummallakin puolella
keskimmäinen, ja meillä on, kuten 5 ja 7.

644
00:27:27,150 --> 00:27:31,440
Kun lisäät ne yhteen,
saat 12, jaat 2, on 6.

645
00:27:31,440 --> 00:27:33,726
>> Joskus on vaikea
miksi se toimii,

646
00:27:33,726 --> 00:27:35,600
mutta jos työn kautta
Esimerkiksi joskus,

647
00:27:35,600 --> 00:27:37,962
se auttaa sinua selvittää, jos
sen pitäisi olla plus tai miinus.

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

649
00:27:38,846 --> 00:27:40,830
>> Opiskelija: [kuulumaton]
täsmälleen keskellä

650
00:27:40,830 --> 00:27:43,950
jos heillä oli tapaus, jossa
siellä on paljon pienempi määrä

651
00:27:43,950 --> 00:27:45,860
ja kuten yksi suuri numero?

652
00:27:45,860 --> 00:27:49,750
>> Ohjaaja: Eli kaikki mitä tarvitset
on ryhmän keskellä.

653
00:27:49,750 --> 00:27:53,010
Joten jos sinulla on ollut joukko pieniä numeroita
ja sitten yksi todella suuri määrä

654
00:27:53,010 --> 00:27:54,799
lopussa, sillä ei ole väliä.

655
00:27:54,799 --> 00:27:56,840
Tärkeää on, että
he lajiteltu, juuri

656
00:27:56,840 --> 00:27:59,339
halua katsoa keskellä
array koska olet vielä

657
00:27:59,339 --> 00:28:00,700
viipalointi teidän ongelma puoli.

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

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

660
00:28:03,680 --> 00:28:06,430
Joten nyt meillä on
keskellä, mitä teemme seuraavaksi?

661
00:28:06,430 --> 00:28:07,150
>> Opiskelija: Vertaa.

662
00:28:07,150 --> 00:28:08,150
Ohjaaja: vertaa.

663
00:28:08,150 --> 00:28:11,670
Joten vertailla keskeltä value_wanted.

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

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

666
00:28:15,160 --> 00:28:17,950
Niin näet täällä meillä
Tämän arvon haluamme tänne.

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

668
00:28:22,012 --> 00:28:23,095
Muista tämä on jono.

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

670
00:28:24,100 --> 00:28:26,970
Niin keskellä viittaa indeksiin.

671
00:28:26,970 --> 00:28:29,785
Joten haluamme tehdä arvojen keskellä.

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

673
00:28:32,380 --> 00:28:35,650
Älä unohda, jos haluat
vertailla, kaksinkertainen tasavertaisina.

674
00:28:35,650 --> 00:28:38,250
Teet yhden yhtä kuin olet
juuri menossa luovuttamaan sen,

675
00:28:38,250 --> 00:28:41,090
ja sitten tietenkin, se on
olemaan arvoa haluat.

676
00:28:41,090 --> 00:28:42,300
Joten älä tee sitä.

677
00:28:42,300 --> 00:28:44,350
>> Joten aiomme nähdä, jos
arvojen keskellä

678
00:28:44,350 --> 00:28:46,460
on arvoa haluamme.

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

680
00:28:47,749 --> 00:28:48,790
Älä unohda henkselit.

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

682
00:28:50,520 --> 00:28:52,235
Dropbox pitäisi mennä pois.

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

684
00:28:54,140 --> 00:28:56,200
Joten mitä me teemme tässä tapauksessa?

685
00:28:56,200 --> 00:28:59,360
Jos se on mitä me haluamme palata?

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

687
00:29:01,510 --> 00:29:02,626
Yritämme sanoa.

688
00:29:02,626 --> 00:29:03,440
>> Opiskelija: Tulosta pois.

689
00:29:03,440 --> 00:29:05,314
>> Ohjaaja: No, me
halua tulostaa.

690
00:29:05,314 --> 00:29:08,220
Joten tämä on bool täällä, niin me
haluavat palata tosi tai epätosi.

691
00:29:08,220 --> 00:29:12,280
Sanomme, on tämä numero
[? Rra? ?] Niin, jos se on,

692
00:29:12,280 --> 00:29:13,788
me vain palata totta.

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

694
00:29:16,780 --> 00:29:17,760
Jos voin kirjoittaa totta.

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

696
00:29:18,830 --> 00:29:20,805
>> Opiskelija: Miksi et palaa nolla?

697
00:29:20,805 --> 00:29:22,930
Ohjaaja: Joten voi
palauttaa nolla jos halusi.

698
00:29:22,930 --> 00:29:26,780
Mutta tässä tapauksessa, koska
meidän funktio palauttaa bool,

699
00:29:26,780 --> 00:29:28,962
Meidän täytyy palata joko tosi tai epätosi.

700
00:29:28,962 --> 00:29:30,920
Opiskelija: Kun olet
sanoen Boolen lauseke,

701
00:29:30,920 --> 00:29:33,450
voit asettaa sen yhtä väärä?

702
00:29:33,450 --> 00:29:39,860
Kuten jos haluan sanoa, jos tämä ehto
ei täyty, kuten on ylempi on yhtä väärä.

703
00:29:39,860 --> 00:29:42,332
Voiko se ymmärtää, jos vain
laittaa vääriä toisella puolella?

704
00:29:42,332 --> 00:29:43,040
Ohjaaja: Joo.

705
00:29:43,040 --> 00:29:44,820
Joten itse asiassa, jos olet
koskaan tehdä jotain

706
00:29:44,820 --> 00:29:49,600
kuten on ylempi tai alempi,
joka palauttaa true tai false

707
00:29:49,600 --> 00:29:53,850
ja se on todella huono tyyli
vaikkapa yhtä kuin yhtä kuin todellinen tai vertaistensa

708
00:29:53,850 --> 00:29:54,840
on yhtä väärä.

709
00:29:54,840 --> 00:30:00,210
Haluat käyttää tämän tuloksen
niin itse check.

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

711
00:30:04,720 --> 00:30:05,860
Ei ollut mitä halusin.

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

713
00:30:08,150 --> 00:30:09,240
Se mitä halusin.

714
00:30:09,240 --> 00:30:13,205
Joten jos kyseessä kysyt
noin jotain tallentaa C.

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

716
00:30:16,320 --> 00:30:25,150
>> Joten jos meillä on int main (void)
ja jotain tällaista.

717
00:30:25,150 --> 00:30:31,922
Ja sinulla on, jos on ylempi
Joidenkin tulo ja olet

718
00:30:31,922 --> 00:30:33,630
kysytään, voit tehdä
jotain tällaista?

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

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

721
00:30:35,679 --> 00:30:37,470
Opiskelija: Yritin
tehdä sen [kuultavissa].

722
00:30:37,470 --> 00:30:38,450
Koska jos it's--

723
00:30:38,450 --> 00:30:39,200
Ohjaaja: Oikea.

724
00:30:39,200 --> 00:30:41,197
Joten haluat sen olevan väärä, oikea?

725
00:30:41,197 --> 00:30:41,780
Opiskelija: Joo.

726
00:30:41,780 --> 00:30:45,960
Ohjaaja: Joten tässä tapauksessa sinua
haluavat sen toteuttaa, jos se ei ole totta.

727
00:30:45,960 --> 00:30:50,510
Niin cool juttu et siellä on tämä.

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

729
00:30:52,900 --> 00:30:55,650
Joten muistakaa huudahdus
kohta tyhjäksi asioita?

730
00:30:55,650 --> 00:30:58,270
Se sanoo [kuultavissa] tarkoittaa ei.

731
00:30:58,270 --> 00:31:03,590
Joten jos tarkastelemme vain
Tässä osa täällä, olisit

732
00:31:03,590 --> 00:31:05,740
sanovat, että antaa arvon
väärä kuin haluat sen.

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

734
00:31:06,790 --> 00:31:09,880
Ei väärä on totta joka
tarkoittaa tämä toteuttaa.

735
00:31:09,880 --> 00:31:11,037
Onko järkeä?

736
00:31:11,037 --> 00:31:11,620
Opiskelija: Joo.

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

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

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

740
00:31:14,300 --> 00:31:16,330
Joten voisimme vain palata
paikkansa tässä tapauksessa.

741
00:31:16,330 --> 00:31:20,357
Joten nyt meillä on kaksi muuta
tapauksissa tässä asiassa.

742
00:31:20,357 --> 00:31:21,565
Mitkä ovat kaksi muuta tapausta?

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

744
00:31:31,610 --> 00:31:32,900
Haluan vain tehdä se tällä tavalla.

745
00:31:32,900 --> 00:31:40,660
Joten aloittaa muu
Jos arvot keskellä

746
00:31:40,660 --> 00:31:43,230
on pienempi kuin arvo haluamme.

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

748
00:31:47,200 --> 00:31:52,020
Joten meidän keskellä arvo on vähemmän
kuin arvo, että etsimme.

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

750
00:31:53,765 --> 00:31:56,720
>> Joten joka sitoi sinä
ajatella haluamme päivittää?

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

752
00:31:57,870 --> 00:31:58,780
Ylempi tai alempi?

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

754
00:32:01,440 --> 00:32:01,940
Ylä?

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

756
00:32:03,230 --> 00:32:06,470
Niin joka puolella array
aiomme katsot?

757
00:32:06,470 --> 00:32:07,500
>> Opiskelija: alempi.

758
00:32:07,500 --> 00:32:09,750
>> Ohjaaja: Me olemme menossa
olisi katsot vasemmalle.

759
00:32:09,750 --> 00:32:11,120
Joten muuta, jos pikku-arvo on pienempi.

760
00:32:11,120 --> 00:32:14,730
Joten keskimmäinen arvo täällä
on pienempi kuin mitä me haluamme.

761
00:32:14,730 --> 00:32:17,202
Joten haluamme ottaa
oikealla puolella meidän array.

762
00:32:17,202 --> 00:32:18,910
Joten aiomme
Päivitämme alaraja.

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

764
00:32:20,210 --> 00:32:23,020
Niin me siirtää meidän pienempi.

765
00:32:23,020 --> 00:32:25,221
Ja mitä mieltä olette alempi pitäisi olla?

766
00:32:25,221 --> 00:32:26,304
Opiskelija: keskimmäinen arvo?

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

768
00:32:27,446 --> 00:32:28,820
Ohjaaja: Eli keskellä value--

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

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

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

772
00:32:32,300 --> 00:32:34,380
Voiko joku kertoa minulle, miksi
meillä on tuo plus 1?

773
00:32:34,380 --> 00:32:35,730
>> Opiskelija: [? Mitään arvoa?]
on yhtä suuri kuin se.

774
00:32:35,730 --> 00:32:36,120
>> Ohjaaja: Oikea.

775
00:32:36,120 --> 00:32:38,661
Koska me tiedämme jo, että
Meidän keskimmäinen arvo ei ole yhtä kuin

776
00:32:38,661 --> 00:32:42,750
sen ja haluamme jättää sen
kaikista myöhemmistä haut.

777
00:32:42,750 --> 00:32:46,360
Jos unohdat että plus 1, tässä
toivomaa jatkua loputtomiin.

778
00:32:46,360 --> 00:32:49,620
Ja sinun vain takertua
päättymättömään silmukkaan ja sitten sinun segfault

779
00:32:49,620 --> 00:32:50,370
ja asiat menevät huonosti.

780
00:32:50,370 --> 00:32:54,780
Joten varmista aina, että et ole
myös arvo, jota juuri

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

782
00:32:55,380 --> 00:32:58,530
Joten me huolehdimme, että plus 1.

783
00:32:58,530 --> 00:33:04,840
>> Joten nyt meillä on meidän viimeinen ehto
joka olen aina varmuuden vuoksi

784
00:33:04,840 --> 00:33:12,664
voit tarkistaa täällä, muu, jos arvo
keskellä on suurempi kuin arvo

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

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

787
00:33:16,260 --> 00:33:20,230
Tämä tarkoittaa, että haluamme
vasen puoli.

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

789
00:33:21,350 --> 00:33:23,260
Niin kumpi aiomme päivittää?

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

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

792
00:33:25,470 --> 00:33:26,970
Ja mikä on tämä yksi menossa tasa-arvoisia?

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

794
00:33:31,630 --> 00:33:33,690
Lähi miinus 1, koska
Tietenkin me haluamme

795
00:33:33,690 --> 00:33:38,370
varmistaa, että emme ole
katsomalla, että keskimmäinen arvo uudelleen.

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

797
00:33:41,830 --> 00:33:45,110
Ja sitten meillä on.

798
00:33:45,110 --> 00:33:45,610
Siinä kaikki.

799
00:33:45,610 --> 00:33:46,820
Siinä kaikki binäärihaku on.

800
00:33:46,820 --> 00:33:48,190
Se ei ole niin paha, eikö?

801
00:33:48,190 --> 00:33:51,590
Se on kuin 10 riviä
koodia valkoinen tila.

802
00:33:51,590 --> 00:33:57,510
Niin hyvin voimakas, erittäin hyödyllinen, tulet
olla käyttää sitä yhdessä teidän myöhemmin psets.

803
00:33:57,510 --> 00:33:59,360
Ehkä ei tämä yksi, mutta myöhemmin.

804
00:33:59,360 --> 00:34:00,670
Joten oppia se.

805
00:34:00,670 --> 00:34:01,510
Rakastan sitä.

806
00:34:01,510 --> 00:34:02,980
Se kohtelee sinua hyvin.

807
00:34:02,980 --> 00:34:05,370
Joten ei kellään mitään
kysymyksiin Binäärihaku?

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

809
00:34:06,196 --> 00:34:09,840
>> Opiskelija: Onko sillä väliä
onko n on parillinen tai pariton?

810
00:34:09,840 --> 00:34:10,750
>> Ohjaaja: Ei.

811
00:34:10,750 --> 00:34:18,150
Koska heitimme sen keskellä kuin
int, se vain katkaista se.

812
00:34:18,150 --> 00:34:21,600
Joten se pysyy kokonaisluku ja se tulee
lopulta lajitella läpi kaiken.

813
00:34:21,600 --> 00:34:23,909
Joten sinun ei tarvitse huolehtia siitä.

814
00:34:23,909 --> 00:34:24,580
Jokainen hyvä?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
Mahtava.

817
00:34:26,850 --> 00:34:27,919
Cool.

818
00:34:27,919 --> 00:34:30,836
Joten, te sai tämän.

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

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

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

822
00:34:35,719 --> 00:34:43,270
Niin puhuimme, tiedän
David mainittu monimutkaisuus runtimes.

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

824
00:34:44,420 --> 00:34:50,340
>> Joten parhaassa tapauksessa se on vain
yksi, jota kutsumme vakioaikaisia.

825
00:34:50,340 --> 00:34:51,909
Voiko joku kertoa minulle, miksi se voisi olla?

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

827
00:34:52,969 --> 00:34:55,800
Minkälainen skenaario, joka merkitsee?

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
Mm-hm.

830
00:34:58,760 --> 00:34:59,926
>> Opiskelija: [kuulumaton] first--

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

832
00:35:00,789 --> 00:35:03,830
Ohjaaja: Eli keskellä on
Ensimmäinen elementti, että me tulemme, eikö?

833
00:35:03,830 --> 00:35:08,167
Joten joko joukko yhden tai
mitä etsimme juuri

834
00:35:08,167 --> 00:35:09,750
sattuu olemaan Smack DAB keskellä.

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

836
00:35:11,190 --> 00:35:13,380
Niin, että paras asia.

837
00:35:13,380 --> 00:35:17,540
Saat todellisia ongelmia, luultavasti ei
menossa päästä [kuultavissa], että usein.

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

839
00:35:18,667 --> 00:35:19,750
Entä huonoin?

840
00:35:19,750 --> 00:35:21,270
Meidän pahin on log n.

841
00:35:21,270 --> 00:35:25,360
Ja että on tekemistä koko
valtuuksia kaksi asia, että puhuin.

842
00:35:25,360 --> 00:35:30,930
>> Joten pahimmassa tapauksessa se tarkoittaisi
että meidän piti pilkkoa array alas

843
00:35:30,930 --> 00:35:33,270
kunnes se oli osa yksi.

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

845
00:35:34,810 --> 00:35:38,930
Joten meidän piti pilkkoa se alas puoli
niin monta kertaa kuin vain pystyimme.

846
00:35:38,930 --> 00:35:41,430
Siksi se on log n, koska
kun vain jakamalla kahdella.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Joten oletukset, mitä
täytyy tietää, jos olet koskaan

849
00:35:45,830 --> 00:35:48,050
aio käyttää binäärihaku.

850
00:35:48,050 --> 00:35:50,680
Sinun osat on lajiteltava.

851
00:35:50,680 --> 00:35:53,890
Ne on lajiteltu, koska
se on ainoa tapa

852
00:35:53,890 --> 00:35:57,060
voi tietää, jos pystyt
heittää pois puolet siitä.

853
00:35:57,060 --> 00:36:00,260
>> Jos sinulla on ollut tämä sekaisin laukku
numeroita ja sanot,

854
00:36:00,260 --> 00:36:05,380
OK, aion tarkistaa keskellä
numero ja numeron Etsin

855
00:36:05,380 --> 00:36:08,510
on pienempi kuin, että olen juuri menossa
mielivaltaisesti heittää pois puolet.

856
00:36:08,510 --> 00:36:11,130
Ette tiedä, jos
numerot, että toinen puoli.

857
00:36:11,130 --> 00:36:12,655
Sinun luettelo on lajiteltu.

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

859
00:36:14,030 --> 00:36:16,560
Kuten hyvin, tämä voi olla
menee eteenpäin hieman,

860
00:36:16,560 --> 00:36:18,360
mutta sinun täytyy olla random access.

861
00:36:18,360 --> 00:36:21,940
Sinun täytyy pystyä vain
mene, että keskimmäinen osa.

862
00:36:21,940 --> 00:36:25,110
Jos joudut kulkemaan
kautta jotain

863
00:36:25,110 --> 00:36:28,630
tai se vie ylimääräistä vaiheet
päästä että keskimmäinen elementti,

864
00:36:28,630 --> 00:36:31,750
se ei ole log n enää, koska
lisäät enemmän työtä siihen.

865
00:36:31,750 --> 00:36:34,800
Ja tämä tekee hieman
järkevämpää kahden viikon,

866
00:36:34,800 --> 00:36:37,950
mutta olen juuri sellainen halusi esipuhe,
antaa te käsitys siitä, mitä on

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

868
00:36:38,999 --> 00:36:40,790
Mutta nämä ovat kaksi
tärkeimmät olettamukset

869
00:36:40,790 --> 00:36:44,804
että tarvitset binary luettelon.

870
00:36:44,804 --> 00:36:45,720
Varmista, että se on järjestetty.

871
00:36:45,720 --> 00:36:47,920
Se on suuri harppaus
te juuri nyt.

872
00:36:47,920 --> 00:36:52,170
Ja että voimme mennä
loput meidän tapaisena.

873
00:36:52,170 --> 00:36:56,444
Joten neljä sorts-- kupla,
lisäys, valinta, ja yhdistää.

874
00:36:56,444 --> 00:36:57,485
Ne ovat kaikki eräänlainen jäähtyä.

875
00:36:57,485 --> 00:37:02,860
Jos te päätät ottaa CS 124,
opit kaikenlaisia ​​tapaisena.

876
00:37:02,860 --> 00:37:07,575
Ja jos olet XKCD fani, siellä
on todella viileä sarjakuva noin

877
00:37:07,575 --> 00:37:11,530
kuten todella tehoton lajittelee, jonka minä
Suosittelemme sinua menossa katsomaan.

878
00:37:11,530 --> 00:37:16,170
Yksi heistä on kuin paniikki lajitella, joka
on kuin, oh no, palata satunnainen joukko.

879
00:37:16,170 --> 00:37:16,991
Shutdown järjestelmä.

880
00:37:16,991 --> 00:37:17,490
Jätä.

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

882
00:37:19,070 --> 00:37:21,500
Joten Nörttihenkiset huumori on aina hyvä.

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

884
00:37:22,620 --> 00:37:25,750
>> Joten Muistaako kukaan sellaista
samankaltaisten vain yleinen ajatus

885
00:37:25,750 --> 00:37:27,810
miten Kuplalajittelu toimii.

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

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

888
00:37:32,155 --> 00:37:32,755
>> Opiskelija: Joo.

889
00:37:32,755 --> 00:37:33,970
>> Ohjaaja: Tsemppiä.

890
00:37:33,970 --> 00:37:38,980
>> Opiskelija: Eli olet menossa läpi ja
jos se on isompi, niin voit vaihtaa kaksi.

891
00:37:38,980 --> 00:37:39,820
>> Ohjaaja: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Täsmälleen.

893
00:37:40,564 --> 00:37:41,730
Joten sinun tarvitsee vain kerrata läpi.

894
00:37:41,730 --> 00:37:43,050
Voit tarkistaa kaksi numeroa.

895
00:37:43,050 --> 00:37:46,510
Jos yksi ennen on isompi
kuin yksi jälkeenpäin,

896
00:37:46,510 --> 00:37:50,230
juuri vaihtaa niitä siten, että
Tällä tavoin kaikki suuremmat numerot

897
00:37:50,230 --> 00:37:54,990
kupla ylös kohti listan loppuun
ja kaikki pienemmät numerot kupla alas.

898
00:37:54,990 --> 00:37:59,355
>> Oliko hän näyttää te viileä
ääniefektin lajittelu video?

899
00:37:59,355 --> 00:38:00,480
Se on eräänlainen jäähtyä.

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

901
00:38:01,510 --> 00:38:05,200
Niin Robert juuri sanoi, algoritmi
että olet vain selata luetteloa,

902
00:38:05,200 --> 00:38:07,930
vaihtamalla vierekkäisten arvojen
jos ne eivät ole kunnossa.

903
00:38:07,930 --> 00:38:10,975
Ja sitten vain toistavat
kunnes et tee mitään swap.

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

905
00:38:11,990 --> 00:38:12,740
Joten ei paha, vai mitä?

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

907
00:38:14,080 --> 00:38:16,319
Joten meidän on vain nopea esimerkki tästä.

908
00:38:16,319 --> 00:38:18,360
Joten tämä tulee lajitella
ne nousevassa järjestyksessä.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Joten kun käymme läpi ensin
aikaa, katsomme läpi kahdeksan

911
00:38:23,470 --> 00:38:26,880
ja kuusi eivät tietenkään ole
jotta me vaihtaa niitä.

912
00:38:26,880 --> 00:38:27,985
>> Joten katso seuraava.

913
00:38:27,985 --> 00:38:29,430
Kahdeksan ja neljä ei järjestyksessä.

914
00:38:29,430 --> 00:38:30,450
Vaihtaa niitä.

915
00:38:30,450 --> 00:38:32,530
Ja sitten kahdeksan ja kaksi, vaihtaa niitä.

916
00:38:32,530 --> 00:38:33,470
Siellä mennään.

917
00:38:33,470 --> 00:38:39,519
Joten kun ensimmäinen pass, voit
tietää, että eniten

918
00:38:39,519 --> 00:38:41,810
tulee olemaan aina
yläosassa, koska se on vain

919
00:38:41,810 --> 00:38:44,210
olemaan jatkuvasti
suurempi kuin kaikki muu

920
00:38:44,210 --> 00:38:46,810
ja se tekee vain kupla
kaikki loppuun asti siellä.

921
00:38:46,810 --> 00:38:48,226
Onko se järkevää kaikille?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
Cool.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Niin sitten katsomme meidän toinen pass.

926
00:38:53,920 --> 00:38:54,980
Kuusi ja neljä, kytkin.

927
00:38:54,980 --> 00:38:55,920
Kuusi ja kaksi, kytkin.

928
00:38:55,920 --> 00:38:58,700
Ja nyt meillä on muutamia asioita kuntoon.

929
00:38:58,700 --> 00:39:02,240
Joten jokaiselle, että me
tehdä läpi koko listan,

930
00:39:02,240 --> 00:39:06,320
me tiedämme, että niin monta numeroa
lopussa tulee on lajiteltu.

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

932
00:39:07,690 --> 00:39:09,610
Joten teemme kolmasosaa pass,
joka on yksi swap.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
Ja sitten meidän neljäs
pass, meillä on nolla lähtö.

935
00:39:15,910 --> 00:39:18,570
Ja niin me tiedämme, että meidän
array on lajiteltu.

936
00:39:18,570 --> 00:39:20,900
>> Ja se on iso
juttu Kuplalajittelu.

937
00:39:20,900 --> 00:39:23,720
Tiedämme, että kun me
on nolla swap, että

938
00:39:23,720 --> 00:39:26,497
tarkoittaa sitä, että kaikki
on täydellisessä järjestyksessä.

939
00:39:26,497 --> 00:39:27,580
Se on tavallaan kuinka tarkistamme.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Joten olemme myös menossa koodaamaan kupla
Lajittele joka myös ei ole niin paha.

942
00:39:36,480 --> 00:39:38,120
Mikään näistä ei niin paha.

943
00:39:38,120 --> 00:39:40,210
Tiedän, että ne voivat tuntua hieman pelottavalta.

944
00:39:40,210 --> 00:39:42,124
Tiedän, kun otin
luokka, vaikka en

945
00:39:42,124 --> 00:39:44,290
opetti luokka
ensimmäisen kerran viime vuonna,

946
00:39:44,290 --> 00:39:46,165
Olin ihan, miten voin tehdä tämän?

947
00:39:46,165 --> 00:39:48,540
On järkevää teoriassa, mutta
Miten voimme itse tehdä tämän?

948
00:39:48,540 --> 00:39:51,420
Minkä takia haluan myös kävellä
koodin avulla teidän kanssa täällä.

949
00:39:51,420 --> 00:39:54,915
Joten minulla on pseudokoodina
sillä te tällä kertaa.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Joten pitää tämä mielessä, kun
aiomme siirtymisessä.

952
00:39:58,970 --> 00:40:04,210
Joten meillä on laskuri, joka
pitää kirjaa meidän swap,

953
00:40:04,210 --> 00:40:08,370
koska meidän täytyy varmistaa,
että me tarkistaa sitä.

954
00:40:08,370 --> 00:40:11,830
Ja me kerrata koko ryhmän
kuten juuri teimme tässä esimerkissä.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Jos elementti ennen on suurempi kuin
elementin jälkeen, jossa me olemme,

957
00:40:17,325 --> 00:40:20,760
me vaihtaa niitä ja me kasvattaa meidän
counter sillä heti kun me vaihtaa,

958
00:40:20,760 --> 00:40:23,850
haluamme antaa meidän laskuri tietää.

959
00:40:23,850 --> 00:40:26,247
Kysyttävää siellä?

960
00:40:26,247 --> 00:40:27,580
Jotain tuntuu hauska tänne.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
Opiskelija: Haluatko asettaa nollaksi
joka kerta mennä läpi silmukan?

963
00:40:32,350 --> 00:40:34,339
Etkö jatka
takaisin nollaan joka kerta?

964
00:40:34,339 --> 00:40:35,505
Ohjaaja: Ei välttämättä.

965
00:40:35,505 --> 00:40:39,710
Mitä tapahtuu, on käymme läpi täällä.

966
00:40:39,710 --> 00:40:43,830
Niin tehdä, kun, muistakaa, tämä
tulee suorittaa kerran ilman epäonnistua.

967
00:40:43,830 --> 00:40:46,480
Joten se tulee asettaa
laskurin nolla,

968
00:40:46,480 --> 00:40:48,070
sitten se tulee kerrata läpi.

969
00:40:48,070 --> 00:40:50,590
Koska se iteroi kautta,
se päivittää laskuri.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Koska se päivittää vasta, kun se on tehty,
kun se on saavuttanut taulukon loppuun,

972
00:40:56,900 --> 00:41:00,830
Jos lista ei ole lajiteltu,
Laskuri on päivitetty.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Niin sitten se tarkistaa kunnossa ja se
sanoo, OK, on ​​laskuri suurempi kuin nolla.

975
00:41:07,150 --> 00:41:09,290
Jos se on, tee se uudestaan.

976
00:41:09,290 --> 00:41:14,340
Haluatko palauttaa niin, että kun
läpi, laskuri on nolla.

977
00:41:14,340 --> 00:41:18,240
Jos menet läpi lajitellun
array, mikään ei muutu,

978
00:41:18,240 --> 00:41:21,355
tämä epäonnistuu, ja olet
palata lajiteltu luettelo.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Onko se järkevää?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
Opiskelija: Se saattaisi myös hieman.

983
00:41:26,356 --> 00:41:27,147
Ohjaaja: OK.

984
00:41:27,147 --> 00:41:28,980
Jos on olemassa muita
kysymys, joka tulee esille.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Kyllä.

987
00:41:30,680 --> 00:41:33,760
>> Opiskelija: Mikä olisi toiminto
olla vaihtamalla osia?

988
00:41:33,760 --> 00:41:36,900
>> Ohjaaja: Voimme siis itse kirjoittaa
että jos aiomme juuri nyt.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
Cool.

991
00:41:38,300 --> 00:41:42,155
Niin Komitea suosittelee, että Alison on menossa
Vaihda takaisin laitteeseen.

992
00:41:42,155 --> 00:41:43,080
Se tulee olemaan hauskaa.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
Ja meillä on mukavaa
Kuplalajittelu juttu täällä.

995
00:41:47,390 --> 00:41:50,800
Joten olen jo tehnyt pyöräily
kautta array.

996
00:41:50,800 --> 00:41:53,030
Meillä swap
ovat yhtä kuin nolla.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Joten haluamme vaihtaa vieressä
elementit, jos he ovat epäkunnossa.

999
00:41:58,440 --> 00:42:03,020
Joten ensimmäinen asia, joka meidän täytyy
do on kerrata kautta array.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Niin miten luulet voisimme
kerrata kautta array?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Meillä on ja minä yhtä kuin 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Haluamme I olevan vähemmän
kuin n miinus 1 miinus k.

1006
00:42:22,454 --> 00:42:23,870
Niin selitän, että toinen.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Joten tämä on optimointi täällä missä,
Muistan kuinka sanoin välein syöttö

1009
00:42:32,830 --> 00:42:36,655
kautta array me
tietää, että mitä on on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Joten yhden läpisyötön jälkeen me
tietää, että tämä on lajiteltu.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Kahden kulkee tiedämme
että kaikki tämä on lajiteltu.

1014
00:42:50,060 --> 00:42:52,750
Kolmen kulkee meillä
tietää, että on lajiteltu.

1015
00:42:52,750 --> 00:42:55,620
Joten miten olen iteroidessaan
kautta array täällä,

1016
00:42:55,620 --> 00:43:01,090
on se tekee varmasti vain mennä
läpi mitä tiedämme on lajittelemattoman.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
Se on vain optimointia.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Voisit kirjoittaa se sinisilmäisesti vain
iteroidessaan kaiken läpi,

1021
00:43:08,210 --> 00:43:09,970
se vain kestää kauemmin.

1022
00:43:09,970 --> 00:43:12,470
Tämän neljän silmukan se
vain kiva optimointi

1023
00:43:12,470 --> 00:43:18,460
koska tiedämme, että jokaisen täyden
iterointi array täällä,

1024
00:43:18,460 --> 00:43:24,050
kuten jokainen loop täällä, tiedämme
että yksi näistä elementeistä

1025
00:43:24,050 --> 00:43:25,760
ratkeaa lopussa.

1026
00:43:25,760 --> 00:43:28,294
>> Joten meidän ei tarvitse huolehtia niistä.

1027
00:43:28,294 --> 00:43:29,710
Onko se järkevää kaikille?

1028
00:43:29,710 --> 00:43:30,950
Että viileä pikku temppu?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Niin siinä tapauksessa, jos
olemme iteroidessaan kautta,

1031
00:43:37,270 --> 00:43:50,590
me tiedämme, että haluamme tarkistaa, onko
array n ja n + 1 ovat kunnossa.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
OK.

1034
00:43:53,559 --> 00:43:54,600
Joten tässä pseudokoodina.

1035
00:43:54,600 --> 00:43:57,540
Haluamme tarkistaa, jos joukko n
ja n + 1 ovat kunnossa.

1036
00:43:57,540 --> 00:43:59,520
Mikä siis meillä on siellä?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
Se tulee olemaan noin ehdollinen.

1039
00:44:03,120 --> 00:44:04,220
Se on, jos.

1040
00:44:04,220 --> 00:44:07,066
>> Opiskelija: Jos array n on
alle array n + 1.

1041
00:44:07,066 --> 00:44:07,816
Ohjaaja: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
No, vähemmän kuin tai suurempi kuin.

1044
00:44:10,699 --> 00:44:11,615
Opiskelija: Suurempi kuin.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Sitten haluamme vaihtaa niitä.

1047
00:44:17,620 --> 00:44:18,570
Täsmälleen.

1048
00:44:18,570 --> 00:44:23,570
Joten nyt saamme mitä
mekanismi vaihtamalla niitä?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Joten kävimme läpi tämän hetken,
tyyppi swap toiminto viime viikolla.

1051
00:44:28,137 --> 00:44:29,595
Muistaako kukaan, miten se toimi?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Joten emme voi vain siirtää niitä, eikö?

1054
00:44:34,950 --> 00:44:36,640
Koska yksi niistä eksy.

1055
00:44:36,640 --> 00:44:41,696
Jos sanoimme vastaa B ja sitten B
on yhtä suuri, kaikki yhtäkkiä molemmat

1056
00:44:41,696 --> 00:44:43,150
ovat vain yhtä B.

1057
00:44:43,150 --> 00:44:45,720
>> Joten mitä meidän täytyy tehdä, on meillä
on väliaikainen muuttuja, joka on

1058
00:44:45,720 --> 00:44:49,055
aikoo järjestää yhden omistamme taas
olemme parhaillaan vaihtava.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Eli meillä on meillä on joitakin int
Lämpötila on yhtä to-- voit määrittää sen

1061
00:44:56,464 --> 00:44:59,130
kumpi niistä haluamasi, vain
Varmista, että pidät kirjaa it--

1062
00:44:59,130 --> 00:45:01,840
joten tässä tapauksessa, aion
määrittää sen array n + 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Niin että menee pitämään tahansa
arvo on, että toinen lohko

1065
00:45:07,674 --> 00:45:08,590
että me tarkastelemme.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> Ja sitten voimme tehdä on, että voimme mennä
eteenpäin ja siirtää array n + 1,

1068
00:45:13,240 --> 00:45:14,990
sillä me tiedämme, että meillä
on, että arvo tallennetaan.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Tämä on myös yksi iso
things-- En tiedä, jos joku teistä

1071
00:45:19,270 --> 00:45:23,780
oli kysymyksiä, joissa jos vaihdat kaksi
riviä koodia yhtäkkiä asiat toimivat.

1072
00:45:23,780 --> 00:45:25,880
Järjestys on erittäin tärkeää CS.

1073
00:45:25,880 --> 00:45:29,450
Varmista siis kaavio
asiat, jos mahdollista

1074
00:45:29,450 --> 00:45:31,230
siitä, mitä todella tapahtuu.

1075
00:45:31,230 --> 00:45:34,256
Joten nyt olemme menossa
siirtää array n + 1,

1076
00:45:34,256 --> 00:45:36,005
sillä me tiedämme, että meillä
on, että arvo tallennetaan.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> Ja voimme antaa, että joukko
n tai tässä tapauksessa array i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Liian monia muuttujia.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
OK.

1083
00:45:55,470 --> 00:46:01,500
Joten nyt olemme virkamieskierrossa array i
plus 1 suuruiseksi mitä array i.

1084
00:46:01,500 --> 00:46:08,240
Ja nyt voimme mennä takaisin ja
määrittää array i mitä?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Kukaan?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> Opiskelija: 10.

1089
00:46:14,010 --> 00:46:14,680
>> Ohjaaja: 10.

1090
00:46:14,680 --> 00:46:15,180
Täsmälleen.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
Ja viimeinen asia.

1093
00:46:18,640 --> 00:46:21,840
Jos olemme vaihtaneet sen nyt,
Mitä meidän pitää tehdä?

1094
00:46:21,840 --> 00:46:23,740
Mikä yksi asia
että menee kertomaan meille

1095
00:46:23,740 --> 00:46:27,542
Jos joskus lopettaa tämän ohjelman?

1096
00:46:27,542 --> 00:46:29,250
Mikä kertoo meille, että me
on lajiteltu lista?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Jos emme tee mitään swap, eikö?

1099
00:46:33,750 --> 00:46:36,900
Jos swap on yhtä kuin
nolla lopussa.

1100
00:46:36,900 --> 00:46:42,975
Joten kun teet swap, koska me
vain teimme täällä, haluamme päivittää swap.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
Ja tiedän siellä oli
kysymys aiemmin siitä voitte

1103
00:46:47,210 --> 00:46:49,689
käyttää nolla tai yksi sen sijaan
tosi tai epätosi.

1104
00:46:49,689 --> 00:46:50,980
Ja sitähän tämä tekee täällä.

1105
00:46:50,980 --> 00:46:52,750
Joten tämä sanoo, että jos ei swap.

1106
00:46:52,750 --> 00:47:01,310
Joten jos swap on nolla, mikä is-- olen aina
saan totuuksia ja minun falses sekaisin.

1107
00:47:01,310 --> 00:47:03,960
Haluamme voimme arvioida
totta ja se ei ole.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Joten jos se on nolla, niin se on väärä.

1110
00:47:09,630 --> 00:47:12,560
Jos estäisi sen kanssa
[? bang?] siitä tulee totta.

1111
00:47:12,560 --> 00:47:13,975
Niin sitten tämä linja suorittaa.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Totuuksia ja vääriä ja
nollia ja ykkösiä saada hullu.

1114
00:47:17,370 --> 00:47:20,690
Vain jos hitaasti kävellä
kautta se on järkevää.

1115
00:47:20,690 --> 00:47:23,320
Mutta sitähän tämä pieni
vähän koodia täällä tekee.

1116
00:47:23,320 --> 00:47:26,490
Joten tämä tarkistaa,
olemme tehneet mitään swap.

1117
00:47:26,490 --> 00:47:30,054
Joten jos se on mitään lisäksi
nolla, se tulee olemaan vääriä

1118
00:47:30,054 --> 00:47:31,970
ja koko juttu on
menossa suorittaa uudelleen.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
Cool?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> Opiskelija: Mitä tauko tekee?

1123
00:47:36,000 --> 00:47:38,990
>> Ohjaaja: Tauko juuri
taukoja sinua ulos silmukan.

1124
00:47:38,990 --> 00:47:41,570
Joten tässä tapauksessa olisi
vain haluavat lopettaa ohjelman

1125
00:47:41,570 --> 00:47:43,828
ja olisit juuri
pyydä lajiteltu luettelo.

1126
00:47:43,828 --> 00:47:44,536
Opiskelija: Amazing.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
Ohjaaja: Olen pahoillani?

1129
00:47:49,010 --> 00:47:52,110
Opiskelija: Koska aikaisemmin olemme
käytetty kirjallisuutta 1 yli kirjoitettu nolla

1130
00:47:52,110 --> 00:47:54,170
esittää, että jos
joka toimii tai ei.

1131
00:47:54,170 --> 00:47:54,878
>> Ohjaaja: Joo.

1132
00:47:54,878 --> 00:47:56,410
Joten voit palata nolla tai 1.

1133
00:47:56,410 --> 00:47:58,950
Tässä tapauksessa, koska emme ole oikeastaan
tehdä mitään toimintoa,

1134
00:47:58,950 --> 00:48:00,150
me vain haluamme sen murtaa.

1135
00:48:00,150 --> 00:48:02,680
Emme oikeastaan ​​välitä siitä.

1136
00:48:02,680 --> 00:48:06,960
Jarru on myös hyvä, jos
sitä käytetään puhkeamassa

1137
00:48:06,960 --> 00:48:10,710
neljä silmukoita tai ehtoja, jotka
et halua säilyttää täytäntöönpanosta.

1138
00:48:10,710 --> 00:48:12,110
Se vain vie pois niistä.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Se on hieman vivahde asia.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Tunnen siellä
paljon käsi heiluttaa,

1143
00:48:18,445 --> 00:48:19,740
kuten opit tästä pian.

1144
00:48:19,740 --> 00:48:20,955
>> Mutta opit tästä pian.

1145
00:48:20,955 --> 00:48:21,500
Lupaan.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
OK.

1148
00:48:23,170 --> 00:48:24,840
Joten ei kaikki saavat Kuplalajittelu?

1149
00:48:24,840 --> 00:48:25,550
Ei liian huono.

1150
00:48:25,550 --> 00:48:31,910
Kerrata läpi, swap asioita käyttäen
temp muuttuja, ja me kaikki asettaa siellä?

1151
00:48:31,910 --> 00:48:32,960
Cool.

1152
00:48:32,960 --> 00:48:34,080
Mahtava.

1153
00:48:34,080 --> 00:48:34,807
OK.

1154
00:48:34,807 --> 00:48:35,765
Takaisin PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Kaikki kysymykset yleensä
näistä tähän mennessä?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
Cool.

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
Mm-hm.

1161
00:48:43,695 --> 00:48:45,279
>> Opiskelija: [kuulumaton] int main yleensä.

1162
00:48:45,279 --> 00:48:46,695
Onko sinulla olla, että tähän?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> Ohjaaja: Eli olimme vain etsimässä
juuri todellinen lajittelu algoritmi.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Jos sinulla oli se sisällä
kuten suurempaa ohjelmaa,

1167
00:48:56,350 --> 00:48:57,891
olisit int main jonnekin.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
Riippuen siitä, missä olet
käyttää tätä algoritmia,

1170
00:49:02,880 --> 00:49:05,860
se määrittää, mitä
palautetaan sen.

1171
00:49:05,860 --> 00:49:09,960
Mutta meidän tapauksessa olemme tiukasti
katsomalla miten tämä todellisuudessa

1172
00:49:09,960 --> 00:49:11,300
kerrata läpi array.

1173
00:49:11,300 --> 00:49:12,570
Joten emme välitä siitä.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Joten puhuimme parhaassa tapauksessa ja
Pahimmassa tapauksessa skenaarioita binäärihaku.

1176
00:49:19,830 --> 00:49:22,470
Joten se on myös tärkeää tehdä
että jokaisen meidän tapaisena.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Joten mitä luulet on pahin
kyseessä runtime Kuplalajittelu?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Te muistaa?

1181
00:49:30,700 --> 00:49:31,784
>> Opiskelija: N miinus 1.

1182
00:49:31,784 --> 00:49:32,700
Ohjaaja: N miinus 1.

1183
00:49:32,700 --> 00:49:35,070
Niin se tarkoittaa, on olemassa
n miinus 1 vertailuja.

1184
00:49:35,070 --> 00:49:40,060
Niin yksi asia on ymmärrettävä,
että ensimmäistä iterointia,

1185
00:49:40,060 --> 00:49:43,360
käymme läpi, vertaamme
Näiden two-- niin se on 1.

1186
00:49:43,360 --> 00:49:46,685
Nämä kaksi, kolme, neljä.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Joten yhden iteraation me
jo neljä vertailuja.

1189
00:49:55,050 --> 00:49:58,230
Kun puhun runtime ja n.

1190
00:49:58,230 --> 00:50:04,680
N edustaa vertailujen lukumäärä
funktiona kuinka monta elementtiä

1191
00:50:04,680 --> 00:50:05,570
meillä.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Joten käymme läpi, meillä on neljä.

1194
00:50:08,860 --> 00:50:11,780
Seuraavan kerran, kun tiedämme, että meillä ei
täytyy huolehtia tästä.

1195
00:50:11,780 --> 00:50:15,140
Me vertailua,
Näiden kahden, nämä kaksi,

1196
00:50:15,140 --> 00:50:20,050
ja jos meillä ei ole, että optimointi
neljän silmukan, että olen kirjoittanut,

1197
00:50:20,050 --> 00:50:22,750
sinun olisi vertaamalla täällä anyways.

1198
00:50:22,750 --> 00:50:26,170
Joten sinulla olisi
läpi array

1199
00:50:26,170 --> 00:50:34,380
ja tekemään n vertailua n
kertaa, koska joka kerta kun

1200
00:50:34,380 --> 00:50:36,670
sen läpi Lajittelemme yksi asia.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> Ja joka kerta käymme läpi
array, teemme n vertailuja.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Joten meidän runtime tähän on
oikeastaan ​​n potenssiin, joka

1205
00:50:46,330 --> 00:50:48,400
on paljon pahempi meidän
log end koska

1206
00:50:48,400 --> 00:50:51,965
tarkoittaa, että jos meillä oli neljä
miljardia elementtejä, se on

1207
00:50:51,965 --> 00:50:55,260
vie meidät neljään miljardiin
potenssiin sijasta 32.

1208
00:50:55,260 --> 00:51:01,240
Joten ei paras runtime,
mutta joitakin asioita,

1209
00:51:01,240 --> 00:51:04,610
tiedät, jos olet sisällä
tiettyjen elementtien alueen

1210
00:51:04,610 --> 00:51:06,540
Kuplalajittelu voi olla hieno käyttää.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Mitä nyt on paras asia runtime?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
Opiskelija: Zero?

1215
00:51:14,940 --> 00:51:16,420
Tai 1?

1216
00:51:16,420 --> 00:51:18,140
>> Ohjaaja: So 1 olisi
yksi vertailu.

1217
00:51:18,140 --> 00:51:19,114
Oikea.

1218
00:51:19,114 --> 00:51:20,002
>> Opiskelija: N miinus 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> Ohjaaja: Niin, joo.

1221
00:51:22,320 --> 00:51:22,990
Joten n miinus 1.

1222
00:51:22,990 --> 00:51:26,510
Aina kun on käsite, kuten n
miinus 1, meillä on tapana vain pudottaa sen pois

1223
00:51:26,510 --> 00:51:31,680
ja me vain sanoa n, koska olet
vertaamaan kunkin these-- kunkin parin.

1224
00:51:31,680 --> 00:51:36,470
Niin se olisi n miinus 1, jota
olimme vain sanoa on noin n.

1225
00:51:36,470 --> 00:51:39,280
Kun olet tekemisissä runtime,
kaikki on lähentää.

1226
00:51:39,280 --> 00:51:43,860
Niin kauan kuin eksponentti on
oikea, olet aika hyvä.

1227
00:51:43,860 --> 00:51:45,700
>> Näin me käsitellä sitä.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Niin että parhaassa tapauksessa on n, joka
tarkoittaa sitä, että luettelo on jo järjestetty,

1230
00:51:51,780 --> 00:51:54,320
ja kaikki mitä teemme on ajaa läpi
ja tarkista, että se on järjestetty.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
Cool.

1233
00:51:56,855 --> 00:51:57,355
Selvä.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Joten kuten näette täällä, me
vain hieman enemmän kuvaajia.

1236
00:52:01,920 --> 00:52:02,660
Niin n potenssiin.

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
Hauskaa.

1239
00:52:05,120 --> 00:52:09,730
Paljon huonommin kuin N, kun näemme, ja
paljon, paljon pahempi kuin log 2n.

1240
00:52:09,730 --> 00:52:12,060
Ja sitten myös päästä loki lokit.

1241
00:52:12,060 --> 00:52:18,020
Ja otat 124, joudut
kuten log tähti, joka on kuin hullu.

1242
00:52:18,020 --> 00:52:20,172
Joten jos olet kiinnostunut,
lookup log tähti.

1243
00:52:20,172 --> 00:52:20,880
Se on tavallaan hauskaa.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Joten meillä on tämä loistava kaavio.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Vain heads up, tämä
ihana kaavio on

1248
00:52:28,720 --> 00:52:31,350
oman puolivälin koska me
pitkään kysyä näitä ohenee.

1249
00:52:31,350 --> 00:52:36,090
Joten vain heads up, on tämä teidän
puolivälin teidän kiva lunttilappua

1250
00:52:36,090 --> 00:52:36,616
siellä.

1251
00:52:36,616 --> 00:52:37,990
Joten me vain katsoi Kuplalajittelu.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
Pahimmassa tapauksessa n potenssiin, parhaassa tapauksessa n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
Ja olemme menossa katsomaan muita.

1256
00:52:44,950 --> 00:52:47,940
>> Ja kuten näette, vain
joka todella hyvin

1257
00:52:47,940 --> 00:52:50,910
on Lomituslajittelu, joka Pääsemme miksi.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Joten aiomme mennä
seuraava here-- valinta lajitella.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Muistaako kukaan, miten
valinta lajitella toiminut?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Tsemppiä.

1264
00:53:05,700 --> 00:53:08,210
>> Opiskelija: periaatteessa mennä läpi
järjestystä ja luoda uuden listan.

1265
00:53:08,210 --> 00:53:11,001
Ja aivan kuten olet laskemisesta osia
vuonna, laita ne oikeaan paikkaan

1266
00:53:11,001 --> 00:53:11,750
uudessa luettelossa.

1267
00:53:11,750 --> 00:53:14,040
>> Ohjaaja: jotta äänet
enemmän kuin lisäyslajittelu.

1268
00:53:14,040 --> 00:53:15,040
Mutta olet todella lähellä.

1269
00:53:15,040 --> 00:53:15,915
Ne ovat hyvin samankaltaisia.

1270
00:53:15,915 --> 00:53:17,440
Vaikka saan ne sekaisin joskus.

1271
00:53:17,440 --> 00:53:18,981
Ennen tätä jaksoa olin kuin, odota.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
OK.

1274
00:53:20,630 --> 00:53:24,141
Joten mitä haluat
tehdä, on valinta lajitella,

1275
00:53:24,141 --> 00:53:25,890
miten voit ajatella
siitä ja miten

1276
00:53:25,890 --> 00:53:30,140
Varmistan En yritä päästä
niitä sekaisin, on se menee läpi

1277
00:53:30,140 --> 00:53:33,280
ja se valitsee
Pienin määrä ja sen

1278
00:53:33,280 --> 00:53:36,070
tuo, että alussa listasi.

1279
00:53:36,070 --> 00:53:37,730
Se swap sen kanssa, että ensin paikalla.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
He todella ovat esimerkkinä minulle.

1282
00:53:45,370 --> 00:53:46,540
Mahtava.

1283
00:53:46,540 --> 00:53:50,130
Joten vain tapa ajatella it-- valinta
Lajittele, valitse pienin arvo.

1284
00:53:50,130 --> 00:53:51,940
Ja aiomme
ajaa läpi esimerkki

1285
00:53:51,940 --> 00:53:55,320
mielestäni auttaa, koska
Mielestäni grafiikka aina auttaa.

1286
00:53:55,320 --> 00:53:58,510
Joten aloitamme jotain
että on täysin lajittelemattomia.

1287
00:53:58,510 --> 00:54:00,730
Punainen on lajittelemattoman,
vihreä lajitellaan.

1288
00:54:00,730 --> 00:54:02,190
Se kaikki on selvää toisessa.

1289
00:54:02,190 --> 00:54:08,950
>> Joten käymme läpi, ja me kerrata
alusta loppuun.

1290
00:54:08,950 --> 00:54:12,320
Ja me sanomme, OK, 2
meidän pienin numero.

1291
00:54:12,320 --> 00:54:15,680
Niin me otamme 2 ja aiomme
siirtää sen edessä meidän array

1292
00:54:15,680 --> 00:54:17,734
koska se on
Vähiten meillä.

1293
00:54:17,734 --> 00:54:19,150
Niin, että mitä tämä tekee täällä.

1294
00:54:19,150 --> 00:54:20,820
Se on juuri menossa vaihtaa nämä kaksi.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Joten nyt meillä on lajiteltu
osa ja lajittelemattoman osa.

1297
00:54:25,450 --> 00:54:27,810
Ja mikä on hyvä muistaa
Tietoja valinta Lajittele

1298
00:54:27,810 --> 00:54:30,690
on me vain valitsemalla
alkaen lajittelemattomat osa.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> Lajitellut osa vain jättää yksin.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> Opiskelija: Miten se tietää, mitä on
pienin vertaamatta sitä

1303
00:54:38,452 --> 00:54:39,868
joka toinen arvo array.

1304
00:54:39,868 --> 00:54:41,250
Ohjaaja: Se verrata sitä.

1305
00:54:41,250 --> 00:54:42,041
Pidämme ohitetaan se.

1306
00:54:42,041 --> 00:54:43,850
Tämä on vain yleinen yleinen.

1307
00:54:43,850 --> 00:54:44,831
Joo.

1308
00:54:44,831 --> 00:54:47,205
Kun me kirjoittaa koodia olen
varma, että voit olla tyytyväinen.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Mutta tallentaa tämän ensimmäisen
elementti kuin pienin.

1311
00:54:53,030 --> 00:54:56,110
Vertaa ja sinä
sanovat, OK, on ​​se pienempi?

1312
00:54:56,110 --> 00:54:56,660
Kyllä.

1313
00:54:56,660 --> 00:54:57,460
Pidä se.

1314
00:54:57,460 --> 00:54:58,640
Tässä on se pienempi?

1315
00:54:58,640 --> 00:54:59,660
Ei?

1316
00:54:59,660 --> 00:55:02,510
>> Tämä on pienin,
luovuttamaan sen omaan arvoon.

1317
00:55:02,510 --> 00:55:06,340
Ja voit olla paljon onnellisempi
kun käymme läpi koodin.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Joten käymme läpi, me vaihtaa sitä, niin sitten
tarkastelemme tätä lajittelemattoman osaan.

1320
00:55:13,970 --> 00:55:15,810
Joten aiomme valita kolme.

1321
00:55:15,810 --> 00:55:18,890
Aiomme laittaa sen päälle
Lopussa meidän lajitellut osan.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
Ja me vain aio pitää tehdä
että tee sitä, ja näin.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Joten tämä on meidän kaltaisemme pseudokoodin täällä.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Me koodi sen tänne toista.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Mutta vain jotain kävellä
läpi korkealla tasolla.

1330
00:55:37,270 --> 00:55:40,275
Aiot mennä
i on yhtä kuin 0 n miinus 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
Se on toinen optimointi.

1333
00:55:43,530 --> 00:55:45,020
Älä huolehdi liikaa siitä.

1334
00:55:45,020 --> 00:55:46,620
Niin sanoitte.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Kuten Jaakob sanoi, miten me
seurata, mitä meidän pienin on?

1337
00:55:54,406 --> 00:55:55,030
Mistä tiedämme?

1338
00:55:55,030 --> 00:55:57,060
Meidän täytyy vertailla
kaikki listallamme.

1339
00:55:57,060 --> 00:55:59,600
>> Niin vähintään yhtä suuri kuin minä.

1340
00:55:59,600 --> 00:56:03,870
Se on vain sanonta tässä tapauksessa
indeksi meidän pienin arvo.

1341
00:56:03,870 --> 00:56:07,660
Niin sitten se tulee kerrata läpi
ja se menee j on yhtä kuin i + 1.

1342
00:56:07,660 --> 00:56:11,420
Joten me jo tiedämme, että
se on meidän ensimmäinen elementti.

1343
00:56:11,420 --> 00:56:13,240
Emme tarvitse verrata sitä itse.

1344
00:56:13,240 --> 00:56:16,970
Joten alamme vertaamalla sitä seuraava
yksi minkä vuoksi se on i ja 1-n

1345
00:56:16,970 --> 00:56:20,110
miinus 1, joka on
taulukon loppuun siellä.

1346
00:56:20,110 --> 00:56:25,090
Ja me sanoimme jos array
j on pienempi kuin array min,

1347
00:56:25,090 --> 00:56:29,200
sitten siirtää missä
Meidän pienin indeksit.

1348
00:56:29,200 --> 00:56:37,470
>> Ja jos min ei ole yhtä kuin minä, koska
kaupungissa, jossa olimme takaisin tänne.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Niin kuin kun ensin teki tämä yksi.

1351
00:56:41,790 --> 00:56:49,310
Tässä tapauksessa se alkaisi
nolla, se lopulta kaksi.

1352
00:56:49,310 --> 00:56:53,010
Joten min eikö yhdenvertaisen i lopussa.

1353
00:56:53,010 --> 00:56:55,720
Tämä kertoo meille, että
meidän täytyy vaihtaa niitä.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Tunnen konkreettinen esimerkki
auttaa paljon enemmän kuin tämä.

1356
00:57:00,470 --> 00:57:04,970
Niin minä koodata tämän kanssa te
juuri nyt ja mielestäni se tulee olemaan parempi.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Lajittelee yleensä toimi sillä tavalla, että
se on usein parempi vain nähdä niitä.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Joten mitä me haluamme tehdä, on
haluamme ensin pienin

1361
00:57:17,280 --> 00:57:19,890
elementti asemaansa array.

1362
00:57:19,890 --> 00:57:21,280
Mitä Jaakob sanoi.

1363
00:57:21,280 --> 00:57:23,090
Sinun täytyy tallentaa se jotenkin.

1364
00:57:23,090 --> 00:57:25,900
Joten aiomme aloittaa tästä
iteroidessaan rivin yli.

1365
00:57:25,900 --> 00:57:28,970
Aiomme sanoa se on meidän
Ensimmäinen vain aloittaa.

1366
00:57:28,970 --> 00:57:38,308
Joten aiomme olla int
Pienin on yhtä array i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Niin yksi asia huomata, joka
kun tämä silmukka suorittaa,

1369
00:57:45,050 --> 00:57:48,550
Aloitamme askeleen kauempana.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Kun aloitamme katsomme tämän yhden.

1372
00:57:57,440 --> 00:58:00,840
Seuraavan kerran me kerrata läpi,
me aloitamme tällä yhdellä

1373
00:58:00,840 --> 00:58:02,680
ja osoittaa se meidän pienin arvo.

1374
00:58:02,680 --> 00:58:10,450
Joten se on hyvin samankaltainen Kuplalajittelu
jos me tiedämme, että kun yksi pass,

1375
00:58:10,450 --> 00:58:11,700
tämä viimeinen elementti on lajiteltu.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Valinnalla lajitella,
se on juuri päinvastoin.

1378
00:58:15,120 --> 00:58:18,950
>> Joka pass, me tiedämme, että
ensimmäinen lajitellaan.

1379
00:58:18,950 --> 00:58:21,360
Toisen pass,
toinen ratkeaa.

1380
00:58:21,360 --> 00:58:26,470
Ja kuten näit kanssa dia esimerkkejä,
Meidän lajiteltu osa vain kasvaa.

1381
00:58:26,470 --> 00:58:34,020
Niin asettamalla meidän pienin
ja taulukot I, kaikki se tekee

1382
00:58:34,020 --> 00:58:37,340
on rajoittavaa, mitä
etsimme niin

1383
00:58:37,340 --> 00:58:40,164
minimoida
vertailuja teemme.

1384
00:58:40,164 --> 00:58:41,770
Onko järkeä kaikille?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Tarvitaanko minua juoksemaan läpi
taas hitaammin tai eri sanoin?

1387
00:58:46,380 --> 00:58:47,180
Olen onnellinen.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
OK.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> Joten olemme tallentamiseen
arvo tässä vaiheessa,

1392
00:58:55,540 --> 00:58:57,840
mutta haluamme myös säilyttää indeksiin.

1393
00:58:57,840 --> 00:59:01,010
Joten aiomme säilyttää
asema pienimmän

1394
00:59:01,010 --> 00:59:02,770
yksi, joka on juuri menossa olevan i.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Joten nyt Jaakob on tyytyväinen.

1397
00:59:05,440 --> 00:59:06,870
Meillä on asiat tallennetaan.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
Ja nyt meidän täytyy katsoa läpi
lajittelemattomat matriisin osan.

1400
00:59:11,870 --> 00:59:18,170
Joten tässä tapauksessa tämä
olisi meidän lajittelemattomat.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
Tämä on i.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
OK.

1405
00:59:26,210 --> 00:59:30,040
>> Joten mitä me aiomme tehdä
tulee olemaan varten silmukka.

1406
00:59:30,040 --> 00:59:32,066
Kun haluat
kerrata läpi array,

1407
00:59:32,066 --> 00:59:33,440
mielesi voisi mennä varten silmukka.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Joten joidenkin int k
equals-- mitä ajattelemme

1410
00:59:38,090 --> 00:59:39,700
K on menossa sama aloittaa?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
Tämä on mitä me asettaneet pienimmän
arvo ja haluamme verrata sitä.

1413
00:59:44,766 --> 00:59:47,090
Mitä haluamme verrata sitä?

1414
00:59:47,090 --> 00:59:48,730
Se tulee olemaan tämä seuraava, eikö?

1415
00:59:48,730 --> 00:59:53,200
Joten haluamme k alustettavaksi
ja i + 1 aloittaa.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> Ja haluamme k tässä tapauksessa me
jo koko tallennettu tänne,

1418
01:00:02,800 --> 01:00:03,930
joten voimme vain käyttää kokoa.

1419
01:00:03,930 --> 01:00:06,240
Koko on taulukon koko.

1420
01:00:06,240 --> 01:00:09,620
Ja me vain haluamme
päivittää k yhdellä joka kerta.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
Cool.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
Nyt meidän täytyy löytää
pienimmän alkion täällä.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Joten jos me kerrata läpi, me
haluan sanoa, jos array K

1427
01:00:31,380 --> 01:00:37,080
on pienempi kuin meidän pienin value--
tämä on, jos olemme todella

1428
01:00:37,080 --> 01:00:42,950
pitää kirjaa siitä, mitä on
pienin here--

1429
01:00:42,950 --> 01:00:47,740
Sitten haluamme siirtää
mitä meidän pienin arvo on.

1430
01:00:47,740 --> 01:00:50,645
>> Tämä tarkoittaa, että oi, olemme
iteroidessaan kautta täällä.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Mikä tahansa arvo on tässä
ei meidän pienin juttu.

1433
01:00:53,740 --> 01:00:54,448
Emme halua sitä.

1434
01:00:54,448 --> 01:00:56,100
Haluamme siirtää sitä.

1435
01:00:56,100 --> 01:01:02,050
Joten jos me uudelleen kohdentamisesta se, mitä tehdä
luulet voisi olla tässä koodi täällä?

1436
01:01:02,050 --> 01:01:04,160
Haluamme siirtää
Pienin sijaintia.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Niin mikä on pienin nyt?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
Opiskelija: Array k.

1441
01:01:09,130 --> 01:01:09,963
Ohjaaja: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
Ja mikä on nyt tilanteemme?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Mikä indeksit
meidän pienin arvo?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
Se on vain k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Niin joukko K, K, ne vastaavat.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Joten halusimme siirtää sitä.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
Ja sitten kun löysimme meidän pienin,
niin lopussa tämä silmukka

1454
01:01:39,950 --> 01:01:45,100
täällä olemme löytäneet mitä meidän pienin
arvo on, niin me vain vaihtaa sitä.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
Tässä tapauksessa, kuten sanovat meidän
Pienin arvo on täällä.

1457
01:01:50,816 --> 01:01:51,940
Tämä on pienin arvo.

1458
01:01:51,940 --> 01:01:57,690
>> Haluamme vain vaihtaa sitä täällä, joka on
mitä se swap toiminto alareunassa

1459
01:01:57,690 --> 01:02:01,270
teki, jonka me vain kirjoitti ylös
yhdessä pari minuuttia sitten.

1460
01:02:01,270 --> 01:02:02,775
Joten sen pitäisi näyttää tutulta.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
Ja sitten se vain kerrata
läpi, kunnes se saavuttaa koko matkan

1463
01:02:08,030 --> 01:02:13,100
loppuun, mikä tarkoittaa sitä, että
on nolla elementtejä, jotka ovat lajittelemattomia

1464
01:02:13,100 --> 01:02:14,800
ja kaikki muu on lajiteltu.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Järkeä?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Hieman konkreettisemmin?

1469
01:02:19,280 --> 01:02:19,990
Apua?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> Opiskelija: n koon, et koskaan
todella määritellä se tai muuttaa sitä,

1472
01:02:26,410 --> 01:02:27,340
miten se tietää?

1473
01:02:27,340 --> 01:02:32,380
>> Ohjaaja: Eli yksi asia
huomaa täällä on int koko.

1474
01:02:32,380 --> 01:02:35,680
Niin sanomme tässä sort-- Lajittele
on funktio tässä case-- se

1475
01:02:35,680 --> 01:02:40,770
valinta lajitella, se on läpäissyt
in toiminnolla.

1476
01:02:40,770 --> 01:02:43,460
Joten jos se ei mennyt läpi
kaupungissa, tekisit jotain

1477
01:02:43,460 --> 01:02:47,840
kuten pituuden kanssa array
tai voit kerrata läpi

1478
01:02:47,840 --> 01:02:49,390
löytää pituutta.

1479
01:02:49,390 --> 01:02:52,680
Mutta koska se on läpäissyt
vuonna, voimme vain käyttää sitä.

1480
01:02:52,680 --> 01:02:55,720
Sinä vain olettaa, että käyttäjä
antoi sinulle voimassa koko, joka

1481
01:02:55,720 --> 01:02:57,698
todellisuudessa merkitsee
kokoa array.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
Cool?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> Jos teillä on ongelmia näillä
tai haluavat enemmän käytännön koodaus lajittelee

1486
01:03:05,870 --> 01:03:08,050
oman, sinun pitäisi
Siirry study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
Se on työkalu.

1489
01:03:12,670 --> 01:03:15,040
Heillä tarkistin että
voit itse kirjoittaa.

1490
01:03:15,040 --> 01:03:16,180
He tekevät pseudokoodilla.

1491
01:03:16,180 --> 01:03:19,310
Heillä on enemmän videoita ja dioja
mukaan lukien ne, käytän täällä.

1492
01:03:19,310 --> 01:03:23,150
Joten jos olet vielä tunne
hieman sumea, kokeile että ulos.

1493
01:03:23,150 --> 01:03:25,670
Kuten aina, tule puhumaan minulle, liian.

1494
01:03:25,670 --> 01:03:26,320
Kysymys?

1495
01:03:26,320 --> 01:03:28,611
>> Opiskelija: Sanotko
koko on aikaisemmin määritelty?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
Ohjaaja: Kyllä.

1498
01:03:29,900 --> 01:03:35,570
Koko on aikaisemmin määritelty ylös
täällä toiminto ilmoituksen.

1499
01:03:35,570 --> 01:03:39,060
Niin oletat, että se on ohitettu
käyttäjä, ja yksinkertaisuuden vuoksi,

1500
01:03:39,060 --> 01:03:41,896
aiomme olettaa, että
Käyttäjä antoi meille oikean koon.

1501
01:03:41,896 --> 01:03:43,240
Cool.

1502
01:03:43,240 --> 01:03:44,390
Niin, että valinta lajitella.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Kaverit, tiedän olemme oppimisen paljon tänään.

1505
01:03:47,640 --> 01:03:49,710
Se on tiheä tietoja osiosta.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Niin, että aiomme
mennä lisäyslajittelu.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> OK.

1510
01:04:02,510 --> 01:04:06,100
Joten sitä ennen meidän on tehtävä
Meidän runtime analyysi täällä.

1511
01:04:06,100 --> 01:04:10,190
Joten parhaassa tapauksessa,
alkaen myönnetyt Näytin

1512
01:04:10,190 --> 01:04:11,960
taulukossa I jo
Tällainen antoi sen pois.

1513
01:04:11,960 --> 01:04:15,430
Mutta parhaassa tapauksessa runtime, mitä ajattelemme?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Kaikki lajiteltu.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N potenssiin.

1518
01:04:22,070 --> 01:04:24,780
Kellään selitystä
miksi luulet?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> Opiskelija: olet verrataan through--

1521
01:04:30,519 --> 01:04:31,268
Ohjaaja: Oikea.

1522
01:04:31,268 --> 01:04:32,540
Olet verrataan kautta.

1523
01:04:32,540 --> 01:04:35,630
Joka iteraatio, vaikka
me pienentämällä tämä yksi,

1524
01:04:35,630 --> 01:04:38,950
olet vielä hakuja
kaikki löytää pienin.

1525
01:04:38,950 --> 01:04:42,390
Joten vaikka pienin arvo
on tässä alussa,

1526
01:04:42,390 --> 01:04:44,710
olet vielä vertaamalla sitä
vastaan ​​kaikki muu

1527
01:04:44,710 --> 01:04:46,550
varmista, että se on pienin asia.

1528
01:04:46,550 --> 01:04:49,820
Joten voit päätyä kulkee
noin n potenssiin kertaa.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Selvä.

1531
01:04:51,590 --> 01:04:52,785
Ja mitä pahimmassa tapauksessa?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Myös n potenssiin, koska olet menossa
olla tekemässä, että samaa menettelyä.

1534
01:04:57,980 --> 01:05:01,670
Joten tässä tapauksessa valinta
Lajittele on jotain

1535
01:05:01,670 --> 01:05:04,010
että me vaadimme odotettavissa runtime.

1536
01:05:04,010 --> 01:05:07,400
Joten muut, me vain tiedämme
ylä- ja alarajoja.

1537
01:05:07,400 --> 01:05:11,180
Riippuen siitä, kuinka hullu meidän
lista on tai kuinka lajittelemattoman se on,

1538
01:05:11,180 --> 01:05:15,350
ne vaihtelevat välillä n tai n potenssiin.

1539
01:05:15,350 --> 01:05:16,550
Emme tiedä.

1540
01:05:16,550 --> 01:05:22,820
>> Mutta koska valinta lajitella on sama
parhaan ja huonoimman tapauksen, joka kertoo meille, että

1541
01:05:22,820 --> 01:05:25,880
Ei ole väliä, millainen panos me
on, onko se kokonaan

1542
01:05:25,880 --> 01:05:29,130
lajiteltu tai kokonaan
kääntää lajiteltu, se on

1543
01:05:29,130 --> 01:05:30,740
vie saman verran aikaa.

1544
01:05:30,740 --> 01:05:33,760
Niin siinä tapauksessa, jos
Muistan meidän pöytä,

1545
01:05:33,760 --> 01:05:38,610
se todella oli arvo,
Näiden kahden lajittelee ei ole,

1546
01:05:38,610 --> 01:05:40,390
jonka odotetaan runtime.

1547
01:05:40,390 --> 01:05:43,350
Joten me tiedämme, että aina
me juoksemme valinta lajitella,

1548
01:05:43,350 --> 01:05:45,380
se on taattu
ajaa n potenssiin aikaa.

1549
01:05:45,380 --> 01:05:46,630
Ei ole mitään vaihtelua siellä.

1550
01:05:46,630 --> 01:05:47,630
Se on vain odotettavissa.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
Ja taas, jos haluat oppia
enemmän, ota CS 124 keväällä.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Selvä.

1555
01:05:56,712 --> 01:05:57,545
Olemme nähneet tämän.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
Cool.

1558
01:05:59,030 --> 01:06:00,930
Niin lisäyslajittelu.

1559
01:06:00,930 --> 01:06:03,330
Ja olen luultavasti menossa
blaze kautta.

1560
01:06:03,330 --> 01:06:05,440
En ole teitä koodi sen.

1561
01:06:05,440 --> 01:06:06,580
Me vain kävellä sen läpi.

1562
01:06:06,580 --> 01:06:10,500
Joten lisäyslajittelu on eräänlainen
on samanlainen valinta Lajittele

1563
01:06:10,500 --> 01:06:14,460
että meillä on sekä lajittelemattoman
ja lajitellaan osa array.

1564
01:06:14,460 --> 01:06:20,260
>> Mutta mikä on erilaista on se, että
kun käymme läpi yksi kerrallaan,

1565
01:06:20,260 --> 01:06:24,210
me vain ottaa mitä numero
on seuraava meidän lajittelemattoman,

1566
01:06:24,210 --> 01:06:28,507
ja oikein lajitella
meidän lajitellut array.

1567
01:06:28,507 --> 01:06:30,090
Se tulee järkevämpää esimerkin.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Niin kaikki alkaa lajittelemattoman,
Aivan kuten valinta lajitella.

1570
01:06:35,430 --> 01:06:38,740
Ja aiomme järjestää tämän
nousevassa järjestyksessä kuin olemme.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Joten meidän ensimmäinen syöttö
otamme ensimmäisen arvon

1573
01:06:43,340 --> 01:06:46,700
ja sanomme, OK, olet
nyt listan itse.

1574
01:06:46,700 --> 01:06:49,150
>> Koska olet luettelossa
itse, olet lajitellaan.

1575
01:06:49,150 --> 01:06:52,460
Onnittelut siitä, että
Ensimmäinen osa tätä array.

1576
01:06:52,460 --> 01:06:54,800
Olet jo lajiteltu kaikki itse.

1577
01:06:54,800 --> 01:06:58,900
Joten nyt meillä on lajiteltu
ja lajittelemattoman array.

1578
01:06:58,900 --> 01:07:01,760
Joten nyt otamme ensin.

1579
01:07:01,760 --> 01:07:05,600
Mitä tapahtuu välillä täällä
Ja tässä on se, että sanomme,

1580
01:07:05,600 --> 01:07:08,890
OK, olemme menossa katsomaan
Ensimmäinen arvo meidän lajittelemattoman array

1581
01:07:08,890 --> 01:07:13,270
ja aiomme syöttää sitä sen
oikea paikka lajitellut array.

1582
01:07:13,270 --> 01:07:21,460
>> Joten mitä me teemme on otamme 5 ja
sanomme, OK, 5 on suurempi kuin 3,

1583
01:07:21,460 --> 01:07:24,630
joten me vain lisätä se oikea
oikealle että.

1584
01:07:24,630 --> 01:07:25,130
Olemme hyviä.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Niin sitten mennään eteenpäin meidän seuraavaan.

1587
01:07:28,420 --> 01:07:29,720
Ja otamme 2.

1588
01:07:29,720 --> 01:07:34,330
Sanomme, OK, 2 on vähemmän
kuin 3, niin me tiedämme, että se

1589
01:07:34,330 --> 01:07:36,220
on oltava
edessä meidän lista nyt.

1590
01:07:36,220 --> 01:07:41,800
Joten mitä teemme on meidän työntää 3 ja 5 alas
ja siirrymme 2 tuohon ensimmäiseen korttipaikkaan.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Joten me vain työntämällä se
oikea paikka olisi.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Sitten katsomme meidän
seuraava, ja sanomme 6.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 on suurempi kuin
kaikki meidän lajiteltua array,

1596
01:07:53,620 --> 01:07:56,000
joten me vain merkitä sen loppuun.

1597
01:07:56,000 --> 01:07:56,960
Ja sitten katsomme 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 on alle 6, se on vähemmän
kuin 5, mutta se on enemmän kuin 3.

1600
01:08:03,020 --> 01:08:06,270
Joten me vain työnnä se
keskellä välillä 3 ja 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Niin tehdä, että vähän
vähän konkreettisempia,

1603
01:08:10,530 --> 01:08:12,280
tässä eräänlainen
käsitys siitä, mitä tapahtui.

1604
01:08:12,280 --> 01:08:16,430
Joten jokaisen lajittelemattoman elementti, me
määrittää missä lajitellut osan

1605
01:08:16,430 --> 01:08:17,090
se on.

1606
01:08:17,090 --> 01:08:20,680
>> Niin pitää mielessä
lajitellaan ja lajittelemattomat,

1607
01:08:20,680 --> 01:08:26,080
meidän täytyy kulkea läpi ja kuva
missä se sopii lajitellut array.

1608
01:08:26,080 --> 01:08:31,460
Ja me aseta se siirtämällä
elementit oikealle alas.

1609
01:08:31,460 --> 01:08:34,910
Ja sitten me vain pitää
iteroimalla läpi kunnes me

1610
01:08:34,910 --> 01:08:39,270
on täysin lajiteltu lista
jossa lajittelemattomat on nyt nolla

1611
01:08:39,270 --> 01:08:41,720
ja lajitellaan vie
kokonaisuudessaan listallamme.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Joten, jälleen, tehdä asioita vielä
konkreettisempia, meillä pseudokoodit.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Joten pohjimmiltaan i on
yhtä kuin 0-n miinus 1,

1616
01:08:52,410 --> 01:08:54,790
se on vain pituus meidän array.

1617
01:08:54,790 --> 01:09:00,979
Meillä on joitakin elementti, joka on yhtä kuin
ensimmäinen array tai ensimmäinen indeksit.

1618
01:09:00,979 --> 01:09:03,200
Asetimme j yhtä suuri.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Joten vaikka j on suurempi kuin
nolla ja array, j miinus 1

1621
01:09:09,210 --> 01:09:11,660
on suurempi kuin
elementti, niin kaikki mitä teemme

1622
01:09:11,660 --> 01:09:17,479
on varmistaa, että
sinun j edustaa oikeastaan

1623
01:09:17,479 --> 01:09:20,010
lajittelemattomat osa array.

1624
01:09:20,010 --> 01:09:30,745
>> Joten kun vielä on asioita
lajitella ja j miinus yksi is-- mitä

1625
01:09:30,745 --> 01:09:31,840
on osa hänen?

1626
01:09:31,840 --> 01:09:34,760
J ei koskaan määritelty tässä.

1627
01:09:34,760 --> 01:09:35,677
Se on tavallaan ärsyttävää.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Anyways.

1630
01:09:36,689 --> 01:09:39,899
Niin j miinus 1, olet tarkkailun
elementti ennen sitä.

1631
01:09:39,899 --> 01:09:46,460
Sanot, OK, on ​​elementti
ennen kun sillä am-- katsotaanpa

1632
01:09:46,460 --> 01:09:47,540
todella vetää tämän pois.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Joten sanokaamme tämä on
kuten meidän toisella kierroksella.

1635
01:09:56,830 --> 01:09:59,525
Joten en tulee olla yhtä suuri
1, joka on tässä.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Joten i tulee olemaan yhtä suuri kuin 1.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
Tämä olisi 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Selvä.

1642
01:10:16,750 --> 01:10:20,945
Joten meidän elementti tässä tapauksessa
tulee olemaan sama kuin 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
Ja meillä on joitakin j, joka on
olemaan yhtä kuin 1.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Voi j pienentämällä.

1647
01:10:30,971 --> 01:10:31,720
Sitähän se on.

1648
01:10:31,720 --> 01:10:35,680
Joten J on yhtä i, niin mitä tämä on
sanonta on, että kun menemme eteenpäin,

1649
01:10:35,680 --> 01:10:37,530
me vain varmistaa,
että emme ole ohi

1650
01:10:37,530 --> 01:10:43,520
indeksointi tällä tavalla, kun yritämme
lisätä asioita meidän lajiteltu luettelo.

1651
01:10:43,520 --> 01:10:49,850
>> Joten kun j = 1. Tässä tapauksessa ja
array j miinus one-- niin array j miinus 1

1652
01:10:49,850 --> 01:10:54,610
on 2 tässä case-- jos se
suurempi kuin elementin,

1653
01:10:54,610 --> 01:10:57,700
niin kaikki tämä tekee
on siirtymässä asioita alas.

1654
01:10:57,700 --> 01:11:04,790
Joten tässä tapauksessa, array j miinus yksi
olisi array nolla, mikä on 2.

1655
01:11:04,790 --> 01:11:08,430
2 ei ole suurempi kuin 4,
joten tämä ei suorita.

1656
01:11:08,430 --> 01:11:11,460
Joten muutos ei liiku alas.

1657
01:11:11,460 --> 01:11:18,790
Mitä tämä tekee tässä vain
liikuttamalla lajitellut array alas.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
Tässä tapauksessa, itse asiassa, me
voisi do-- Tehdään tästä 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Joten jos olemme kulkea kanssa
Tässä esimerkissä olemme nyt täällä.

1662
01:11:31,970 --> 01:11:32,740
Tämä on lajiteltu.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
Tämä on lajittelemattomat.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
Cool?

1667
01:11:39,860 --> 01:11:46,620
Joten i on yhtä suuri kuin 2, niin
Meidän elementti on yhtä kuin 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
Ja meidän j on 2.

1670
01:11:52,270 --> 01:12:00,620
Joten katsomme läpi ja me
sanovat, OK, on ​​joukko j miinus yksi

1671
01:12:00,620 --> 01:12:03,470
suurempi kuin elementin
että me tarkastelemme?

1672
01:12:03,470 --> 01:12:05,540
Ja vastaus on kyllä, eikö?

1673
01:12:05,540 --> 01:12:11,275
4 on suurempi kuin 3 ja j
on 2, joten tämä koodi suorittaa.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Mitä nyt teemme array
2, niin täällä, me vaihtaa niitä.

1676
01:12:18,550 --> 01:12:25,620
Joten me vain sanoa, OK, array
2 on nyt menossa on 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
Ja j on menossa sama
j miinus 1, joka on 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
Se on kamala, mutta
te saada idea.

1681
01:12:37,200 --> 01:12:38,360
J on nyt yhtä suuri kuin 1.

1682
01:12:38,360 --> 01:12:44,360
Ja joukko J on juuri menossa olevan
yhtä elementtimme, mikä oli 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
Olen poistetaan jotain minun ei pitäisi
on tai miswrote jotain,

1685
01:12:48,570 --> 01:12:49,910
mutta te saada idea.

1686
01:12:49,910 --> 01:12:50,640
>> Se liikkua n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
Ja sitten, jos tämä olisi, se silmukka
uudelleen ja se sanoisi, OK, j on 1 nyt.

1689
01:12:57,960 --> 01:13:00,665
Ja joukko j miinus 1 on nyt 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
On 2 vähemmän kuin meidän elementti?

1692
01:13:03,760 --> 01:13:04,540
Ei?

1693
01:13:04,540 --> 01:13:07,970
Tämä tarkoittaa, että olemme
Lisätään tämä elementti

1694
01:13:07,970 --> 01:13:10,110
oikeaan kohtaan meidän lajitellun array.

1695
01:13:10,110 --> 01:13:14,400
Sitten voimme ottaa tämän ja sanomme,
OK, meidän lajitellun array on täällä.

1696
01:13:14,400 --> 01:13:19,940
Ja se veisi tämän numeron 6 ja olla
kuten, OK, on ​​6 alle tämän numeron?

1697
01:13:19,940 --> 01:13:20,480
Ei?

1698
01:13:20,480 --> 01:13:21,080
Cool.

1699
01:13:21,080 --> 01:13:22,680
Olemme kunnossa.

1700
01:13:22,680 --> 01:13:23,530
>> Tee se uudestaan.

1701
01:13:23,530 --> 01:13:24,740
Sanomme 7.

1702
01:13:24,740 --> 01:13:29,010
On 7 vähemmän kuin lopussa
meidän lajitellut array?

1703
01:13:29,010 --> 01:13:29,520
Ei.

1704
01:13:29,520 --> 01:13:30,430
Joten olemme kunnossa.

1705
01:13:30,430 --> 01:13:32,760
Joten tämä olisi järjestetty.

1706
01:13:32,760 --> 01:13:38,610
Periaatteessa kaikki tämä tekee
on se sanoo take

1707
01:13:38,610 --> 01:13:42,060
Ensimmäinen osa
teidän lajittelemattomat array,

1708
01:13:42,060 --> 01:13:46,010
selvittää, missä se menee
oman lajitellut array.

1709
01:13:46,010 --> 01:13:48,780
Ja tämä vain huolehtii
swap tehdä.

1710
01:13:48,780 --> 01:13:51,300
Olet pohjimmiltaan vain vaihtamalla
kunnes se on oikealla paikalla.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Visuaalinen ilme on että olet
liikkuvat kaiken alas tekemällä niin.

1713
01:13:56,990 --> 01:13:59,420
>> Joten se on kuin puoli Kuplalajittelu-herra.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Tutustu tutkimuksessa 50.

1716
01:14:03,420 --> 01:14:06,000
Olen erittäin suositella yrittää
koodata tämän itse.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Jos sinulla on kysymyksiä tai haluat
Katso näyte koodi lisäyslajittelu,

1719
01:14:12,450 --> 01:14:13,750
kerro minulle.

1720
01:14:13,750 --> 01:14:14,500
Olen aina noin.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Joten pahimmassa tapauksessa runtime
ja parhaassa tapauksessa runtime.

1723
01:14:20,200 --> 01:14:30,700
Kun kaveri näki pöydästä olen jo
osoitti teille, se on sekä n potenssiin ja n.

1724
01:14:30,700 --> 01:14:35,590
>> Joten tavallaan menossa pois, mitä puhuimme
Tietoja meidän edellinen lajittelee, pahin

1725
01:14:35,590 --> 01:14:38,760
tapauksessa runtime on, että jos
se on täysin Lajittelemattomat

1726
01:14:38,760 --> 01:14:42,530
meidän täytyy verrata kaikkia näitä n kertaa.

1727
01:14:42,530 --> 01:14:47,020
Teemme paljon vertailuja
koska jos se on käänteisessä järjestyksessä,

1728
01:14:47,020 --> 01:14:50,360
aiomme sanoa, OK, tämä
on sama, tämä on hyvä,

1729
01:14:50,360 --> 01:14:54,650
ja tämä yksi on verrattava
vastaan ​​ensimmäinen siirrettävä takaisin.

1730
01:14:54,650 --> 01:14:56,710
Ja kun saamme kohti
loppupää, meillä on

1731
01:14:56,710 --> 01:14:59,440
vertailla, vertailla ja
vertautuvat kaiken.

1732
01:14:59,440 --> 01:15:03,030
>> Joten se päätyy
noin n potenssiin.

1733
01:15:03,030 --> 01:15:09,510
Jos se on oikein niin olet
sanovat, OK, 2, olet hyvä.

1734
01:15:09,510 --> 01:15:11,330
3, olet verrattuna 2.

1735
01:15:11,330 --> 01:15:12,310
Olet hyvä.

1736
01:15:12,310 --> 01:15:14,150
4, juuri verrata häntä.

1737
01:15:14,150 --> 01:15:14,990
Olet hyvä.

1738
01:15:14,990 --> 01:15:17,140
6, verrata häntä, olet hieno.

1739
01:15:17,140 --> 01:15:20,870
Joten jokaiselle paikalla, jos se on jo
lajiteltu, teet yhden vertailun.

1740
01:15:20,870 --> 01:15:22,320
Joten se on vain n.

1741
01:15:22,320 --> 01:15:26,840
Ja koska meillä on parhaassa tapauksessa runtime
n: n ja pahimmassa tapauksessa käyntiaika n

1742
01:15:26,840 --> 01:15:28,680
potenssiin, meillä ei ole odotettavissa runtime.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Se vain riippuu siitä,
kaaos lista siellä.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
Ja vielä toinen
kuvaaja ja toinen pöytä.

1747
01:15:39,530 --> 01:15:41,170
Joten erot tapaisena.

1748
01:15:41,170 --> 01:15:44,180
Olen juuri menossa tuulta läpi, minä
tuntuu olemme puhuneet laajasti

1749
01:15:44,180 --> 01:15:46,570
siitä, miten he kaikenlaisia
sekä vaihtelevat ja linkitetään yhteen.

1750
01:15:46,570 --> 01:15:50,564
Joten Lomituslajittelu on viimeinen
Aion pitkästyttää teitä kanssa.

1751
01:15:50,564 --> 01:15:52,105
Meillä on melko värikäs kuva.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Joten Lomituslajittelu on rekursiivinen algoritmi.

1754
01:15:56,040 --> 01:15:59,910
Joten Tiedättekö mitä
rekursiivinen funktio on?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Joku haluaa sanoa?

1757
01:16:03,320 --> 01:16:04,739
Haluatko kokeilla?

1758
01:16:04,739 --> 01:16:07,280
Joten rekursiivinen funktio on vain
funktio, joka kutsuu itseään.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Joten jos te olette tuttuja
kanssa Fibonaccin,

1761
01:16:11,590 --> 01:16:15,670
joka on katsottu rekursiivinen koska
otat kahden edellisen

1762
01:16:15,670 --> 01:16:17,530
ja lisää ne yhdessä
saada seuraavaan.

1763
01:16:17,530 --> 01:16:21,440
Joten rekursiivinen, ajattelen aina
ja rekursio samankaltaisina spiraali

1764
01:16:21,440 --> 01:16:24,430
niin olet kuin kuolinkierteeseen siihen.

1765
01:16:24,430 --> 01:16:27,150
Mutta se on vain toiminto
joka kutsuu itseään.

1766
01:16:27,150 --> 01:16:32,660
>> Ja todella, todella nopeasti I
voi näyttää mitä se näyttää.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Joten rekursiivinen täällä, jos katsomme, tämä on
rekursiivinen tapa esittää yli array.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Niin kaikki mitä teemme on
meillä on summa toiminto

1771
01:16:47,880 --> 01:16:52,210
summa, joka vie koko ja array.

1772
01:16:52,210 --> 01:16:55,210
Ja jos huomaat, koko
pienenee yhdellä joka kerta.

1773
01:16:55,210 --> 01:17:00,365
Ja kaikki se on, jos x on yhtä suuri kuin
zero-- joten jos taulukon koko

1774
01:17:00,365 --> 01:17:02,710
on yhtä suuri kuin zero-- se palaa nolla.

1775
01:17:02,710 --> 01:17:10,440
>> Muuten se kiteyttää tämän
viime alkiota,

1776
01:17:10,440 --> 01:17:14,790
ja sitten otetaan summa
loput array.

1777
01:17:14,790 --> 01:17:17,555
Niin se vain murtaa se alas
pienempiin ja pienempiin ongelmiin.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Pitkä tarina lyhyt, rekursio,
funktio, joka kutsuu itseään.

1780
01:17:21,890 --> 01:17:25,740
Jos se kaikki mitä sinulla ulos tästä,
niinhän rekursiivinen funktio on.

1781
01:17:25,740 --> 01:17:29,870
Jos otat 51, saat hyvin,
erittäin mukava rekursio.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
Se on todella siistiä.

1784
01:17:32,370 --> 01:17:34,660
Se oli järkevää Like
3 AM yhden yön pois.

1785
01:17:34,660 --> 01:17:37,900
Ja olin kuin, miksi
olen koskaan käytä tätä?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Joten Lomituslajittelu, pohjimmiltaan
mitä se aikoo tehdä, on se

1788
01:17:42,430 --> 01:17:45,620
aio rikkoa sen alas ja rikkoa sitä
alaspäin, kunnes se on vain yhden elementtejä.

1789
01:17:45,620 --> 01:17:47,570
Yksittäinen elementit ovat helppo lajitella.

1790
01:17:47,570 --> 01:17:48,070
Näemme, että.

1791
01:17:48,070 --> 01:17:50,760
Jos sinulla on yksi elementti, se on
jo harkinnut lajitellaan.

1792
01:17:50,760 --> 01:17:53,800
Joten tuloon n elementtejä,
jos n on pienempi kuin 2,

1793
01:17:53,800 --> 01:17:58,120
vain palata, koska se tarkoittaa
se on joko 0 tai 1, kuten olemme nähneet.

1794
01:17:58,120 --> 01:18:00,050
Nämä katsotaan lajiteltua elementtejä.

1795
01:18:00,050 --> 01:18:02,170
>> Muuten rikkoa se kahtia.

1796
01:18:02,170 --> 01:18:06,336
Lajitella alkupuoliskolla, järjestää toinen
puoli, ja sitten yhdistää ne yhteen.

1797
01:18:06,336 --> 01:18:07,460
Miksi sitä kutsutaan Lomituslajittelu.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Joten meillä on täällä me järjestellä näitä.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Joten pidämme ottaa heidät
kunnes jonon pituus on 1.

1802
01:18:17,210 --> 01:18:20,790
Joten kun se on 1, me vain palata
koska tämä on lajiteltua array,

1803
01:18:20,790 --> 01:18:23,940
ja tämä on lajitellun array, ja se on
Lajittele array, me kaikki lajiteltu.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Joten mitä sitten teemme, on meillä
alkaa sulautuvat ne yhteen.

1806
01:18:29,420 --> 01:18:31,820
>> Joten miten voit
ajatella yhdistäminen on

1807
01:18:31,820 --> 01:18:36,240
voit vain poistaa pienempiä
määrä kunkin osa paneelit

1808
01:18:36,240 --> 01:18:38,330
ja vain liittää se syntyi jono.

1809
01:18:38,330 --> 01:18:44,290
Joten jos katsot täällä, kun meillä on
Näiden sarjaa meillä on 4, 6, ja 1.

1810
01:18:44,290 --> 01:18:47,280
Kun haluamme yhdistää nämä,
katsomme näiden kahden ensimmäisen

1811
01:18:47,280 --> 01:18:50,730
ja sanomme, OK, 1 on pienempi,
se menee eteen.

1812
01:18:50,730 --> 01:18:54,330
4 ja 6, ei ole mitään verrata
se vain merkitä sitä loppuun.

1813
01:18:54,330 --> 01:18:58,020
>> Kun yhdistämme nämä kaksi, me vain
ottaa pienempi näistä kahdesta,

1814
01:18:58,020 --> 01:18:59,310
joten se on 1.

1815
01:18:59,310 --> 01:19:01,690
Ja nyt otamme
pienempi näistä kahdesta, niin 2.

1816
01:19:01,690 --> 01:19:03,330
Pienempi näistä kahdesta, 3.

1817
01:19:03,330 --> 01:19:06,260
Pienempi näistä kahdesta, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Joten olet vain vetämällä pois nämä.

1819
01:19:08,630 --> 01:19:11,210
Ja koska he ovat
on lajiteltu aiemmin,

1820
01:19:11,210 --> 01:19:14,300
sinulla on vain yksi
Vertailun joka kerta siellä.

1821
01:19:14,300 --> 01:19:19,610
Joten enemmän koodia tässä, juuri edustus.

1822
01:19:19,610 --> 01:19:24,410
Joten aloitat keskeltä ja
voit lajitella vasen ja oikea

1823
01:19:24,410 --> 01:19:26,180
ja sitten vain yhdistää ne.

1824
01:19:26,180 --> 01:19:30,080
>> Ja meillä ei ole koodia
varten yhdistää täällä.

1825
01:19:30,080 --> 01:19:34,110
Mutta jälleen kerran, jos menet
opiskella 50, se on siellä.

1826
01:19:34,110 --> 01:19:36,860
Muuten tulla juttelemaan
Jos olet edelleen sekava.

1827
01:19:36,860 --> 01:19:42,340
Niin cool juttu tässä on, että parhaassa tapauksessa
Pahimmassa tapauksessa, ja odotettavissa runtime

1828
01:19:42,340 --> 01:19:46,250
ovat kaikki log n, joka
on paljon parempi kuin me olet

1829
01:19:46,250 --> 01:19:48,000
nähneet loput meidän tapaisena.

1830
01:19:48,000 --> 01:19:51,840
Olemme nähneet n potenssiin
ja mitä me oikeastaan

1831
01:19:51,840 --> 01:19:54,380
tänne on n log n, joka on suuri.

1832
01:19:54,380 --> 01:19:55,830
>> Katsokaa kuinka paljon parempi se on.

1833
01:19:55,830 --> 01:19:56,780
Tällainen kiva käyrä.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Niin paljon tehokkaampaa.

1836
01:20:00,120 --> 01:20:03,510
Jos joskus voi käyttää Lomituslajittelu.

1837
01:20:03,510 --> 01:20:04,810
Se säästää aikaa.

1838
01:20:04,810 --> 01:20:07,670
Sitten taas, kuten sanoimme, jos
olet alas tässä ala-alueella,

1839
01:20:07,670 --> 01:20:09,480
se ei tee, että
paljon eroa.

1840
01:20:09,480 --> 01:20:11,360
Saat jopa tuhansia
ja tuhansia panoksia,

1841
01:20:11,360 --> 01:20:13,318
et varmasti halua
tehokkaampi algoritmi.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
Ja taas, meidän ihana pöytä kaikista
lajittelee, että te oppinut tänään.

1844
01:20:19,400 --> 01:20:21,157
>> Joten tiedän, että se on ollut tiivis päivä.

1845
01:20:21,157 --> 01:20:23,490
Tämä ei välttämättä mene
auttaa sinua PSET.

1846
01:20:23,490 --> 01:20:28,250
Mutta en vain halua tehdä vastuuvapauslauseke
että osa ei ole vain psets.

1847
01:20:28,250 --> 01:20:31,240
Kaikki tämä materiaali on oikeudenmukainen
peli sinun midterms.

1848
01:20:31,240 --> 01:20:35,430
Ja jos et jatka CS,
nämä ovat todella tärkeitä perustekijöitä

1849
01:20:35,430 --> 01:20:37,870
että sinun pitäisi tietää.

1850
01:20:37,870 --> 01:20:41,700
Joten joinakin päivinä tulee olemaan
hieman PSET apua,

1851
01:20:41,700 --> 01:20:44,600
mutta joitakin viikkoja tulee
paljon enemmän todellista sisältöä

1852
01:20:44,600 --> 01:20:46,600
että ei voi tuntua erittäin
sinulle hyötyä juuri nyt,

1853
01:20:46,600 --> 01:20:51,215
mutta lupaan, jos jatkat
siitä tulee olemaan erittäin, erittäin hyödyllinen.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Niin se on siinä osassa.

1856
01:20:54,250 --> 01:20:55,250
Viime hetkeen saakka.

1857
01:20:55,250 --> 01:20:56,570
Tein sen minuutin kuluessa.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Mutta siellä mennään.

1860
01:20:58,970 --> 01:21:01,240
Ja minulla on munkkeja tai karkkia.

1861
01:21:01,240 --> 01:21:03,464
Onko joku allerginen
mitään, muuten?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Munat ja maito.

1864
01:21:05,890 --> 01:21:08,120
Niin munkkeja on ei?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
OK.

1867
01:21:10,160 --> 01:21:10,770
Selvä.

1868
01:21:10,770 --> 01:21:12,120
Suklaa ei?

1869
01:21:12,120 --> 01:21:12,620
Escape.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starbursts ovat hyviä.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Aiomme olla
Starburst ensi viikolla sitten.

1874
01:21:17,045 --> 01:21:18,240
Se mitä saan.

1875
01:21:18,240 --> 01:21:19,690
Teillä hyvä viikko.

1876
01:21:19,690 --> 01:21:20,460
Lue spec.

1877
01:21:20,460 --> 01:21:22,130
>> Kerrothan, jos sinulla on kysyttävää.

1878
01:21:22,130 --> 01:21:25,300
PSET kahta laatua pitäisi olla
ulos sinulle torstaina.

1879
01:21:25,300 --> 01:21:28,320
Jos sinulla on kysyttävää
miten olen lajitellut jotain

1880
01:21:28,320 --> 01:21:32,250
tai miksi arvostellaan jotain niin kuin minä
ei, lähetä sähköpostia minulle, tule juttelemaan.

1881
01:21:32,250 --> 01:21:34,210
Olen hieman hullu tämä
viikko, mutta lupaan

1882
01:21:34,210 --> 01:21:36,340
Aion silti vastata 24 tunnin kuluessa.

1883
01:21:36,340 --> 01:21:38,240
Niin on hyvä viikko, kaikille.

1884
01:21:38,240 --> 01:21:40,090
Onnea PSET.

1885
01:21:40,090 --> 01:21:41,248