1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Katsotaanpa katsomaan valikoima lajitella, algoritmi

2
00:00:09,980 --> 00:00:12,800
ottaa listan numeroiden ja lajittelusta.

3
00:00:12,800 --> 00:00:15,750
Algoritmi, muistan, on yksinkertaisesti askel-askeleelta

4
00:00:15,750 --> 00:00:18,370
menettely toteutuksessa tehtävä.

5
00:00:18,370 --> 00:00:21,470
Perusajatuksena valinta tavallaan on jakaa

6
00:00:21,470 --> 00:00:23,390
lista kahteen osaan -

7
00:00:23,390 --> 00:00:26,810
lajitellaan osa ja lajittelemattoman osan.

8
00:00:26,810 --> 00:00:30,200
Jokaisessa vaiheessa algoritmi, numero siirretään

9
00:00:30,200 --> 00:00:33,800
lajittelemattoman annoksena järjestetty osaan, kunnes lopulta

10
00:00:33,800 --> 00:00:35,880
koko lista on lajiteltu.

11
00:00:35,880 --> 00:00:38,510
Joten tässä on luettelo kuusi numeroa -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, ja 15.

13
00:00:44,010 --> 00:00:47,680
Juuri nyt koko lista pidetään lajittelematta.

14
00:00:47,680 --> 00:00:51,770
Vaikka useita kuten 16 voi jo olla oikeassa

15
00:00:51,770 --> 00:00:56,040
sijainnin, algoritmi ei voi mitenkään tietää, että ennen

16
00:00:56,040 --> 00:00:57,980
koko lista on lajiteltu.

17
00:00:57,980 --> 00:01:01,355
Joten me miettiä jokaisen numeron lajittelemattomana kunnes lajitella

18
00:01:01,355 --> 00:01:03,800
sen itse.

19
00:01:03,800 --> 00:01:06,890
Me tiedämme, että haluamme luetteloa olla nousevassa järjestyksessä.

20
00:01:06,890 --> 00:01:10,200
Joten me haluamme rakentaa lajiteltu osa meidän listan

21
00:01:10,200 --> 00:01:13,280
vasemmalta oikealle, pienimmästä suurimpaan.

22
00:01:13,280 --> 00:01:17,970
Voit tehdä, että meidän täytyy löytää minimi lajittelemattoman elementti

23
00:01:17,970 --> 00:01:21,350
ja laita se lopussa lajiteltu osan.

24
00:01:21,350 --> 00:01:25,370
Koska luettelo ei ole lajiteltu, ainoa tapa tehdä se on

25
00:01:25,370 --> 00:01:29,330
näyttää jokaisen elementin lajittelemattoman osassa, muistaen

26
00:01:29,330 --> 00:01:32,010
joka elementti on alhaisin ja vertaamalla

27
00:01:32,010 --> 00:01:33,770
jokainen elementti siihen.

28
00:01:33,770 --> 00:01:36,150
Joten me ensin katsoa 23.

29
00:01:36,150 --> 00:01:38,650
Tämä on ensimmäinen osa olemme nähneet, niin me muistaa

30
00:01:38,650 --> 00:01:40,050
se minimi.

31
00:01:40,050 --> 00:01:42,320
Seuraavaksi tutustumme 42.

32
00:01:42,320 --> 00:01:46,720
42 on suurempi kuin 23, niin 23 on edelleen pienin.

33
00:01:46,720 --> 00:01:51,210
Seuraavaksi on 4, joka on vähemmän kuin 23, joten muistamme 4

34
00:01:51,210 --> 00:01:52,880
uutena minimi.

35
00:01:52,880 --> 00:01:56,380
Seuraava on 16, joka on suurempi kuin 4, niin 4

36
00:01:56,380 --> 00:01:57,980
on edelleen pienin.

37
00:01:57,980 --> 00:02:03,670
8 on suurempi kuin 4, ja 15 on suurempi kuin 4, niin 4 on oltava

38
00:02:03,670 --> 00:02:05,980
pienin lajittelemattoman elementti.

39
00:02:05,980 --> 00:02:09,350
Joten vaikka ihmisinä voimme heti nähdä, että 4 on

40
00:02:09,350 --> 00:02:12,300
pienin elementti, meidän algoritmi tarvitsee katsoa

41
00:02:12,300 --> 00:02:15,710
jokainen lajittelemattoman elementti, vaikka olemme löytäneet 4 -

42
00:02:15,710 --> 00:02:16,860
pienin alkio.

43
00:02:16,860 --> 00:02:19,900
Joten nyt olemme huomanneet pienin alkio, 4, me haluamme

44
00:02:19,900 --> 00:02:23,410
siirtää sen lajiteltu osan luettelossa.

45
00:02:23,410 --> 00:02:27,320
Koska tämä on ensimmäinen askel, tämä tarkoittaa sitä, emme halua laittaa 4:

46
00:02:27,320 --> 00:02:29,680
listan alkuun.

47
00:02:29,680 --> 00:02:33,040
Tällä hetkellä 23 on alussa luettelossa, joten

48
00:02:33,040 --> 00:02:36,080
Katsotaanpa vaihtaa 4 ja 23.

49
00:02:36,080 --> 00:02:38,870
Joten nyt lista näyttää tältä.

50
00:02:38,870 --> 00:02:42,710
Tiedämme, että 4 on sen lopullisessa sijainnin, koska se on

51
00:02:42,710 --> 00:02:45,890
sekä pienintä elementin ja elementin alussa

52
00:02:45,890 --> 00:02:46,960
luettelon.

53
00:02:46,960 --> 00:02:50,650
Tämä tarkoittaa, että meidän ei koskaan tarvitse siirtää uudelleen.

54
00:02:50,650 --> 00:02:53,910
Joten toistan tämän prosessin lisätä toisen elementin

55
00:02:53,910 --> 00:02:55,910
lajiteltu osan luettelosta.

56
00:02:55,910 --> 00:02:58,950
Me tiedämme, että meidän ei tarvitse katsoa 4, koska se on

57
00:02:58,950 --> 00:03:00,000
jo lajiteltu.

58
00:03:00,000 --> 00:03:03,540
Joten voimme aloittaa 42, jonka me muistan

59
00:03:03,540 --> 00:03:05,290
pienin alkio.

60
00:03:05,290 --> 00:03:08,700
Joten seuraavan me tarkastelemme 23, joka on alle 42, joten

61
00:03:08,700 --> 00:03:11,620
Muistan 23 on uusi minimi.

62
00:03:11,620 --> 00:03:14,870
Seuraava näemme 16, joka on pienempi kuin 23, niin

63
00:03:14,870 --> 00:03:16,800
16 on uusi minimi.

64
00:03:16,800 --> 00:03:19,720
Nyt tarkastelemme 8, joka on pienempi kuin 16, niin

65
00:03:19,720 --> 00:03:21,130
8 on uusi minimi.

66
00:03:21,130 --> 00:03:25,900
Ja lopuksi 8 on pienempi kuin 15, niin tiedetään, että 8 on vähimmäismäärä

67
00:03:25,900 --> 00:03:27,780
lajittelemattoman elementti.

68
00:03:27,780 --> 00:03:30,660
Joten se tarkoittaa, että meidän pitäisi liittää 8 lajiteltu

69
00:03:30,660 --> 00:03:32,450
osan luettelosta.

70
00:03:32,450 --> 00:03:35,990
Juuri nyt 4 on ainoa lajiteltu elementti, joten haluamme sijoittaa

71
00:03:35,990 --> 00:03:38,410
8 vieressä 4.

72
00:03:38,410 --> 00:03:41,920
Koska 42 on ensimmäinen osa lajittelemattoman osa

73
00:03:41,920 --> 00:03:47,260
lista, me haluamme vaihtaa 42 ja 8.

74
00:03:47,260 --> 00:03:49,680
Joten nyt lista näyttää tältä.

75
00:03:49,680 --> 00:03:53,830
4 ja 8 edustavat lajiteltu osan luettelosta, ja

76
00:03:53,830 --> 00:03:56,440
loput numerot edustavat lajittelemattoman

77
00:03:56,440 --> 00:03:58,260
osan luettelosta.

78
00:03:58,260 --> 00:04:00,630
Joten jatka toisen iteraation.

79
00:04:00,630 --> 00:04:03,850
Aloitamme 23 tällä kertaa, koska meidän ei tarvitse katsoa

80
00:04:03,850 --> 00:04:05,770
4 ja 8 enää, koska he ovat

81
00:04:05,770 --> 00:04:07,660
jo lajiteltu.

82
00:04:07,660 --> 00:04:10,270
16 on alle 23, niin me muistaa

83
00:04:10,270 --> 00:04:12,070
16 uudeksi minimi.

84
00:04:12,070 --> 00:04:18,149
16 on pienempi kuin 42, mutta 15 on pienempi kuin 16, niin 15 on oltava

85
00:04:18,149 --> 00:04:20,480
minimi lajittelemattoman elementti.

86
00:04:20,480 --> 00:04:24,580
Joten nyt haluamme vaihtaa 15 ja 23

87
00:04:24,580 --> 00:04:26,310
meille tämä luettelo.

88
00:04:26,310 --> 00:04:30,500
Lajiteltu osa luettelo koostuu 4, 8 ja 15, ja

89
00:04:30,500 --> 00:04:33,210
Nämä elementit ovat edelleen lajittelematta.

90
00:04:33,210 --> 00:04:36,900
Mutta se vain niin, että seuraava lajittelemattoman elementti, 16,

91
00:04:36,900 --> 00:04:38,480
on jo järjestetty.

92
00:04:38,480 --> 00:04:42,060
Kuitenkaan ei ole mitään keinoa, jolla algoritmin tietää, että 16

93
00:04:42,060 --> 00:04:45,230
on jo sen oikeaan paikkaan, joten tarvitsemme vielä

94
00:04:45,230 --> 00:04:47,870
toistaa täsmälleen saman prosessin.

95
00:04:47,870 --> 00:04:53,750
Niin näemme, että 16 on pienempi kuin 42, ja 16 on pienempi kuin 23, niin

96
00:04:53,750 --> 00:04:56,230
16 on oltava vähintään elementti.

97
00:04:56,230 --> 00:04:59,010
On mahdotonta vaihtaa tätä elementtiä itsensä kanssa, joten voimme

98
00:04:59,010 --> 00:05:01,780
jätä se tähän paikkaan.

99
00:05:01,780 --> 00:05:04,660
Joten tarvitsemme yhden pass meidän algoritmin.

100
00:05:04,660 --> 00:05:09,370
42 on suurempi kuin 23, niin 23 on oltava

101
00:05:09,370 --> 00:05:10,970
vähintään lajittelemattoman elementti.

102
00:05:10,970 --> 00:05:17,410
Kun me vaihtaa 23 ja 42, päädymme meidän lopullinen

103
00:05:17,410 --> 00:05:18,530
lajiteltu lista -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
Tiedämme 42 on oltava oikeassa paikassa, sillä se on

106
00:05:26,830 --> 00:05:30,210
Ainoa jäljellä, ja se valinta lajitella.

107
00:05:30,210 --> 00:05:32,100
Katsotaanpa nyt virallistaa meidän algoritmi joitakin

108
00:05:32,100 --> 00:05:34,540
pseudokoodi.

109
00:05:34,540 --> 00:05:37,760
Linjalla yksi, voimme nähdä, että meidän täytyy integroida yli

110
00:05:37,760 --> 00:05:39,530
jokainen elementti luettelosta.

111
00:05:39,530 --> 00:05:42,150
Paitsi viimeinen elementti, koska 1 elementti

112
00:05:42,150 --> 00:05:44,230
lista on jo järjestetty.

113
00:05:44,230 --> 00:05:48,100
Linjalla kaksi, pidämme ensimmäinen osa lajittelemattoman

114
00:05:48,100 --> 00:05:51,080
osa luettelo on minimi, kuten teimme kanssa

115
00:05:51,080 --> 00:05:53,750
Esimerkiksi, joten meillä on jotain verrata.

116
00:05:53,750 --> 00:05:57,260
Linjalla kolme alkaa toisen silmukan, jossa me iteroida yli

117
00:05:57,260 --> 00:05:59,170
jokainen lajittelemattoman elementti.

118
00:05:59,170 --> 00:06:02,150
Tiedämme, että kun olen iteraation, lajiteltu osa

119
00:06:02,150 --> 00:06:05,330
meidän Luettelossa on oltava i elementtejä sitä, koska kussakin vaiheessa

120
00:06:05,330 --> 00:06:06,890
lajittelee yksi elementti.

121
00:06:06,890 --> 00:06:11,770
Joten ensimmäinen lajittelemattoman elementin tulee olla asennossa I plus 1.

122
00:06:11,770 --> 00:06:15,440
On line neljä vertaamme nykyistä elementin minimi

123
00:06:15,440 --> 00:06:17,750
elementti, että olemme nähneet tähän mennessä.

124
00:06:17,750 --> 00:06:20,560
Jos nykyinen tekijä on pienempi kuin pienimmän

125
00:06:20,560 --> 00:06:23,870
elementti, niin me muistamme alkion uutena

126
00:06:23,870 --> 00:06:26,250
vähintään linjalla viisi.

127
00:06:26,250 --> 00:06:29,900
Lopuksi linjat kuusi ja seitsemän, me vaihtaa vähintään

128
00:06:29,900 --> 00:06:33,080
elementti ensimmäinen lajittelemattoman elementti, mikä

129
00:06:33,080 --> 00:06:36,990
lisäämällä se lajitellaan osan luettelosta.

130
00:06:36,990 --> 00:06:40,030
Kun meillä on algoritmi, tärkeää kysyä

131
00:06:40,030 --> 00:06:43,370
itsemme ohjelmoijat on kuinka kauan kesti, että kestää?

132
00:06:43,370 --> 00:06:46,970
Meillä tulee ensin kysyä, kuinka kauan se kestää tämän

133
00:06:46,970 --> 00:06:50,070
algoritmi ajaa pahimmassa tapauksessa?

134
00:06:50,070 --> 00:06:51,640
Muistan me edustamme tätä käynnissä

135
00:06:51,640 --> 00:06:55,060
aika iso O notaatio.

136
00:06:55,060 --> 00:06:58,650
Jotta voitaisiin määrittää minimi lajittelemattoman elementti, me

137
00:06:58,650 --> 00:07:01,880
lähinnä oli vertailla jokainen alkio luettelossa

138
00:07:01,880 --> 00:07:04,040
joka toinen elementti luettelossa.

139
00:07:04,040 --> 00:07:08,430
Intuitiivisesti tämä kuulostaa O n neliö toiminnan.

140
00:07:08,430 --> 00:07:12,050
Tarkasteltaessa meidän pseudokoodilla, meillä on myös silmukka sisäkkäin

141
00:07:12,050 --> 00:07:14,420
toinen silmukka, joka todellakin kuulostaa O

142
00:07:14,420 --> 00:07:16,480
n squared toimintaa.

143
00:07:16,480 --> 00:07:19,250
Muista kuitenkin, että emme tarvitse etsiä yli

144
00:07:19,250 --> 00:07:23,460
koko lista määritettäessä minimi lajittelemattoman elementti?

145
00:07:23,460 --> 00:07:26,600
Kun tiesimme, että 4 oli lajiteltu Esimerkiksi emme

146
00:07:26,600 --> 00:07:28,170
täytyy katsoa sitä uudelleen.

147
00:07:28,170 --> 00:07:31,020
Joten tämä pienempi käyntiaika?

148
00:07:31,020 --> 00:07:34,510
Meidän luettelo pituus 6 tarvitsimme tehdä viisi

149
00:07:34,510 --> 00:07:37,990
vertailuja ensimmäisen elementin, neljä vertailuja

150
00:07:37,990 --> 00:07:40,750
toinen elementti, ja niin edelleen.

151
00:07:40,750 --> 00:07:44,690
Tämä tarkoittaa sitä, että vaiheiden kokonaismäärä on summa

152
00:07:44,690 --> 00:07:49,160
kokonaisluvut 1 listan pituus miinus 1.

153
00:07:49,160 --> 00:07:51,005
Voimme edustaa tämän kanssa summattu.

154
00:07:57,980 --> 00:07:59,910
Emme aio mennä summaussarjojen tänne.

155
00:07:59,910 --> 00:08:04,900
Mutta se osoittautuu, että tämä summattu on yhtä kuin n kertaa

156
00:08:04,900 --> 00:08:07,540
n miinus 1 yli 2.

157
00:08:07,540 --> 00:08:14,220
Tai vastaavasti, n potenssiin yli 2 miinus n. yli 2.

158
00:08:14,220 --> 00:08:18,860
Kun puhutaan asymptoottinen runtime, tämä n potenssiin termi

159
00:08:18,860 --> 00:08:22,070
tulee hallitsemaan tätä n. aikavälillä.

160
00:08:22,070 --> 00:08:27,850
Joten valinta tavallaan on O n neliö.

161
00:08:27,850 --> 00:08:31,460
Muistutan, että meidän esimerkissä valinta lajitella tarvitaan edelleen

162
00:08:31,460 --> 00:08:33,850
tarkista onko numero, joka on jo järjestetty

163
00:08:33,850 --> 00:08:35,450
tarpeen siirtää.

164
00:08:35,450 --> 00:08:38,929
Joten se tarkoittaa, että jos me juoksi valinta Lajittele yli jo

165
00:08:38,929 --> 00:08:43,070
järjestetty luettelo, se vaatisi sama määrä vaiheita kuin se

166
00:08:43,070 --> 00:08:46,340
olisi ajettaessa täysin lajittelemattoman luettelosta.

167
00:08:46,340 --> 00:08:51,470
Joten valinta sort on parhaassa tapauksessa suorituskyvyn n potenssiin,

168
00:08:51,470 --> 00:08:56,820
jota edustavat Omega n neliö.

169
00:08:56,820 --> 00:08:58,600
Ja se on siinä valinnassa tavallaan.

170
00:08:58,600 --> 00:09:00,630
Vain yksi monista algoritmien voimme

171
00:09:00,630 --> 00:09:02,390
järjestellä luettelon.

172
00:09:02,390 --> 00:09:05,910
Nimeni on Tommy, ja tämä on cs50.