1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Oglejmo si neke izbire, algoritem

2
00:00:09,980 --> 00:00:12,800
za sprejetje seznama številk in njihovo razvrščanje.

3
00:00:12,800 --> 00:00:15,750
Algoritem, se spomnite, je le korak-po-korak

4
00:00:15,750 --> 00:00:18,370
Postopek za dokončanje opravila.

5
00:00:18,370 --> 00:00:21,470
Osnovna ideja neke izbire je razdeliti

6
00:00:21,470 --> 00:00:23,390
naš seznam na dva dela -

7
00:00:23,390 --> 00:00:26,810
razporejene del in del razvrščeni.

8
00:00:26,810 --> 00:00:30,200
Na vsakem koraku algoritma je število preselil iz

9
00:00:30,200 --> 00:00:33,800
neprebrani del na izločen del, dokler sčasoma

10
00:00:33,800 --> 00:00:35,880
Celoten seznam je urejen.

11
00:00:35,880 --> 00:00:38,510
Torej, tukaj je seznam šestih številk -

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

13
00:00:44,010 --> 00:00:47,680
Zdaj je celoten seznam šteje nesortirani.

14
00:00:47,680 --> 00:00:51,770
Čeprav se številka 16, kot je že bilo v njegovo pravilno

15
00:00:51,770 --> 00:00:56,040
mesto, naš algoritem ne more vedeti, da dokler

16
00:00:56,040 --> 00:00:57,980
Celoten seznam je urejen.

17
00:00:57,980 --> 00:01:01,355
Torej bomo upoštevali vsako številko, ki se nerazvrščeno dokler ne razvrstite

18
00:01:01,355 --> 00:01:03,800
ga sami.

19
00:01:03,800 --> 00:01:06,890
Vemo, da želimo, da seznam, ki bo v naraščajočem vrstnem redu.

20
00:01:06,890 --> 00:01:10,200
Torej bomo želeli zgraditi urejen del našega seznama

21
00:01:10,200 --> 00:01:13,280
od leve proti desni, najmanjšega do največjega.

22
00:01:13,280 --> 00:01:17,970
Da bi to dosegli, bomo morali najti najnižjo neurejen element

23
00:01:17,970 --> 00:01:21,350
in ga na koncu razvrščenih dela.

24
00:01:21,350 --> 00:01:25,370
Ker se ta seznam ni urejen, je edini način za to je, da

25
00:01:25,370 --> 00:01:29,330
poglej vsak element v nesortiranih dela, se spomnimo

26
00:01:29,330 --> 00:01:32,010
kateri element je najnižja in primerjavo

27
00:01:32,010 --> 00:01:33,770
Vsak element za to.

28
00:01:33,770 --> 00:01:36,150
Torej bomo prvi pogled na 23 let.

29
00:01:36,150 --> 00:01:38,650
To je prvi element, ki smo jih videli, zato smo se bom zapomnila

30
00:01:38,650 --> 00:01:40,050
to je minimum.

31
00:01:40,050 --> 00:01:42,320
Nato bomo pogledali 42.

32
00:01:42,320 --> 00:01:46,720
42 je večje od 23, tako da je še vedno 23 najnižji.

33
00:01:46,720 --> 00:01:51,210
Nato je 4, ki je manj kot 23, tako da boste zapomnili 4

34
00:01:51,210 --> 00:01:52,880
kot novi minimum.

35
00:01:52,880 --> 00:01:56,380
Naslednja je 16, ki je večja od 4, zato 4

36
00:01:56,380 --> 00:01:57,980
je še vedno najnižja.

37
00:01:57,980 --> 00:02:03,670
8 je večja od 4 in 15 je večje od 4, 4, tako mora biti

38
00:02:03,670 --> 00:02:05,980
najmanjši neprebrani element.

39
00:02:05,980 --> 00:02:09,350
Torej, čeprav so ljudje lahko takoj videli, da je 4

40
00:02:09,350 --> 00:02:12,300
minimalni element, naš algoritem potrebuje, da pogled na

41
00:02:12,300 --> 00:02:15,710
Vsak element razvrščeni tudi po tem, ko smo ugotovili, 4 - je

42
00:02:15,710 --> 00:02:16,860
Najmanjša element.

43
00:02:16,860 --> 00:02:19,900
Torej, zdaj, ko smo ugotovili najmanjšo element, 4, bomo želeli

44
00:02:19,900 --> 00:02:23,410
premakniti v izločen del seznama.

45
00:02:23,410 --> 00:02:27,320
Ker je to prvi korak, to pomeni, da želimo postaviti na 4

46
00:02:27,320 --> 00:02:29,680
začetek seznama.

47
00:02:29,680 --> 00:02:33,040
Zdaj 23 je na začetku seznama, tako da

48
00:02:33,040 --> 00:02:36,080
kaj je swap 4 in 23.

49
00:02:36,080 --> 00:02:38,870
Torej, zdaj je naš seznam izgleda takole.

50
00:02:38,870 --> 00:02:42,710
Vemo, da mora biti 4 na njegovo končno lokacijo, saj je

51
00:02:42,710 --> 00:02:45,890
tako je najmanjši element in element na začetku

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

53
00:02:46,960 --> 00:02:50,650
Torej to pomeni, da ne bomo kdaj morali premakniti še enkrat.

54
00:02:50,650 --> 00:02:53,910
Torej ponovite postopek dodati še en element za

55
00:02:53,910 --> 00:02:55,910
razporejene del seznama.

56
00:02:55,910 --> 00:02:58,950
Vemo, da nam ni treba gledati na 4, saj je

57
00:02:58,950 --> 00:03:00,000
že urejeno.

58
00:03:00,000 --> 00:03:03,540
Torej, lahko začnemo na 42, ki jih bomo spominjali, kot

59
00:03:03,540 --> 00:03:05,290
Najmanjša element.

60
00:03:05,290 --> 00:03:08,700
Torej, naslednjič bomo pogled na 23, kar je manj kot 42, tako da smo

61
00:03:08,700 --> 00:03:11,620
zapomni 23 je nova najnižja.

62
00:03:11,620 --> 00:03:14,870
Nato smo videli 16, ki je manj kot 23, tako da

63
00:03:14,870 --> 00:03:16,800
16 je nova najnižja.

64
00:03:16,800 --> 00:03:19,720
Zdaj gledamo na 8, kar je manj kot 16, tako da

65
00:03:19,720 --> 00:03:21,130
8 je nova najnižja.

66
00:03:21,130 --> 00:03:25,900
In na koncu 8 je manj kot 15, tako da vemo, da je minimalno 8

67
00:03:25,900 --> 00:03:27,780
neprebrani element.

68
00:03:27,780 --> 00:03:30,660
Torej to pomeni, da je treba priložiti 8 do razporejene

69
00:03:30,660 --> 00:03:32,450
Del seznama.

70
00:03:32,450 --> 00:03:35,990
Zdaj 4 je edini element, razporejene, zato želimo, da se

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

72
00:03:38,410 --> 00:03:41,920
Ker 42 je prvi element v nesortiranih del

73
00:03:41,920 --> 00:03:47,260
Seznam bomo želeli, da bi zamenjali 42 in 8.

74
00:03:47,260 --> 00:03:49,680
Torej, zdaj je naš seznam izgleda takole.

75
00:03:49,680 --> 00:03:53,830
4 in 8 predstavljajo urejen del seznama, in

76
00:03:53,830 --> 00:03:56,440
ostale številke predstavljajo unsorted

77
00:03:56,440 --> 00:03:58,260
Del seznama.

78
00:03:58,260 --> 00:04:00,630
Torej, kaj je še z drugo ponovitev.

79
00:04:00,630 --> 00:04:03,850
Začeli smo s 23 tokrat, saj nam ni treba gledati

80
00:04:03,850 --> 00:04:05,770
4 in 8 več, ker oni '

81
00:04:05,770 --> 00:04:07,660
že urejeno.

82
00:04:07,660 --> 00:04:10,270
16 je manj kot 23, tako da boste zapomnili

83
00:04:10,270 --> 00:04:12,070
16 kot novi minimum.

84
00:04:12,070 --> 00:04:18,149
16 je manj kot 42, vendar 15 je manj kot 16, tako da mora biti 15

85
00:04:18,149 --> 00:04:20,480
Najmanjša neprebrani element.

86
00:04:20,480 --> 00:04:24,580
Torej, zdaj smo želeli, da bi zamenjali 15 in 23 do

87
00:04:24,580 --> 00:04:26,310
nam ta seznam.

88
00:04:26,310 --> 00:04:30,500
Urejen del seznama je sestavljen iz 4, 8 in 15, ter

89
00:04:30,500 --> 00:04:33,210
Ti elementi so še vedno nesortirano.

90
00:04:33,210 --> 00:04:36,900
Vendar je prav tako se zgodi, da se naslednji neprebrani element, 16,

91
00:04:36,900 --> 00:04:38,480
je že urejeno.

92
00:04:38,480 --> 00:04:42,060
Vendar pa ni način za naš algoritem vedeti, da 16

93
00:04:42,060 --> 00:04:45,230
je že v svojem pravem mestu, zato moramo še

94
00:04:45,230 --> 00:04:47,870
ponovite natanko isti postopek.

95
00:04:47,870 --> 00:04:53,750
Tako vidimo, da je 16 manj kot 42, in 16, je manj kot 23, tako da

96
00:04:53,750 --> 00:04:56,230
16 mora biti najmanj element.

97
00:04:56,230 --> 00:04:59,010
Nemogoče je, da bi zamenjali ta element sam s sabo, tako da smo lahko

98
00:04:59,010 --> 00:05:01,780
preprosto pustite na tej lokaciji.

99
00:05:01,780 --> 00:05:04,660
Zato se moramo še eno podajo našega algoritma.

100
00:05:04,660 --> 00:05:09,370
42 je več kot 23, tako da mora biti 23

101
00:05:09,370 --> 00:05:10,970
Najmanjša neprebrani element.

102
00:05:10,970 --> 00:05:17,410
Ko bomo zamenjali 23 in 42, smo na koncu z naš končni

103
00:05:17,410 --> 00:05:18,530
razporejene seznam -

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

105
00:05:23,390 --> 00:05:26,830
Vemo 42 mora biti na pravem mestu, saj je

106
00:05:26,830 --> 00:05:30,210
Edini element levo, in da je izbira vrste.

107
00:05:30,210 --> 00:05:32,100
Pojdimo zdaj formalizirati svoj algoritem z nekaterimi

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

109
00:05:34,540 --> 00:05:37,760
Na liniji, lahko vidimo, da se moramo vključiti v

110
00:05:37,760 --> 00:05:39,530
vsak element seznama.

111
00:05:39,530 --> 00:05:42,150
Razen zadnjega elementa, saj je 1 element

112
00:05:42,150 --> 00:05:44,230
Seznam je že urejeno.

113
00:05:44,230 --> 00:05:48,100
Na liniji, menimo, da je prvi del nerazvrščenih

114
00:05:48,100 --> 00:05:51,080
del seznama, ki je minimalna, tako kot smo z našimi

115
00:05:51,080 --> 00:05:53,750
Na primer, da imamo kaj za primerjati.

116
00:05:53,750 --> 00:05:57,260
Linija 3 se prične drugo zanko, v kateri smo Ponovil več

117
00:05:57,260 --> 00:05:59,170
vsak neprebrani element.

118
00:05:59,170 --> 00:06:02,150
Vemo, da ko sem iteracij, razvrščenih del

119
00:06:02,150 --> 00:06:05,330
na našem seznamu, mora imeti i elementi v njih od vsakega koraka

120
00:06:05,330 --> 00:06:06,890
razvrsti enega elementa.

121
00:06:06,890 --> 00:06:11,770
Torej je treba prvi neprebrani element v položaju, jaz plus 1.

122
00:06:11,770 --> 00:06:15,440
Na liniji 4 primerjamo trenutni element na minimum

123
00:06:15,440 --> 00:06:17,750
Element, ki smo jih videli do sedaj.

124
00:06:17,750 --> 00:06:20,560
Če je trenutna element je manjša od minimalne

125
00:06:20,560 --> 00:06:23,870
element, potem ne pozabite trenutni element kot nova

126
00:06:23,870 --> 00:06:26,250
najmanj na liniji 5.

127
00:06:26,250 --> 00:06:29,900
Končno, na progah, 6 in 7, smo zamenjali vsaj

128
00:06:29,900 --> 00:06:33,080
element s prvim nesortiranih element, s čimer

129
00:06:33,080 --> 00:06:36,990
jo dodali v izločen del seznama.

130
00:06:36,990 --> 00:06:40,030
Ko imamo algoritem, pomembno vprašanje vprašati

131
00:06:40,030 --> 00:06:43,370
sebe kot programerjev je, kako dolgo je to trajalo?

132
00:06:43,370 --> 00:06:46,970
Mi bomo najprej vprašati vprašanje, kako dolgo traja, da za to

133
00:06:46,970 --> 00:06:50,070
algoritem za vožnjo v najslabšem primeru?

134
00:06:50,070 --> 00:06:51,640
Recall mi predstavlja to delovanje

135
00:06:51,640 --> 00:06:55,060
tokrat z velikim O zapisu.

136
00:06:55,060 --> 00:06:58,650
Za določitev najnižje neurejen element, smo

137
00:06:58,650 --> 00:07:01,880
v bistvu je za primerjavo vsak element v seznamu

138
00:07:01,880 --> 00:07:04,040
vsak drugi element v seznamu.

139
00:07:04,040 --> 00:07:08,430
Intuitivno, to zveni kot O kvadrat delovanje n.

140
00:07:08,430 --> 00:07:12,050
Če pogledamo na našem psevdokod, imamo tudi ugnezdena znotraj zanke

141
00:07:12,050 --> 00:07:14,420
drugega kroga, ki dejansko zveni kot O

142
00:07:14,420 --> 00:07:16,480
za kvadratni delovanje n.

143
00:07:16,480 --> 00:07:19,250
Vendar ne pozabite, da nam ni treba pogledati čez

144
00:07:19,250 --> 00:07:23,460
Celoten seznam pri določanju minimalnega neurejen element?

145
00:07:23,460 --> 00:07:26,600
Ko bomo vedeli, da je bil razvrščen 4, na primer, nismo

146
00:07:26,600 --> 00:07:28,170
treba pogledati še enkrat.

147
00:07:28,170 --> 00:07:31,020
Torej, ali to nižje teče čas?

148
00:07:31,020 --> 00:07:34,510
Za naš seznam dolžine 6, smo morali narediti 5

149
00:07:34,510 --> 00:07:37,990
primerjave za prvi element, štiri primerjave za

150
00:07:37,990 --> 00:07:40,750
Drugi element, in tako naprej.

151
00:07:40,750 --> 00:07:44,690
To pomeni, da je skupno število korakov je vsota

152
00:07:44,690 --> 00:07:49,160
Množica celih števil od 1 do dolžine seznama minus 1.

153
00:07:49,160 --> 00:07:51,005
Mi lahko predstavlja to s seštevanjem.

154
00:07:57,980 --> 00:07:59,910
Mi ne bo šel v summations tukaj.

155
00:07:59,910 --> 00:08:04,900
Vendar se je izkazalo, da je ta vsota enaka n-krat

156
00:08:04,900 --> 00:08:07,540
n minus 1 več kot 2.

157
00:08:07,540 --> 00:08:14,220
Ali enakovredno n kvadrat več kot 2 minus n čez 2.

158
00:08:14,220 --> 00:08:18,860
Ko govorimo o asimptotične runtime, to n kvadrat izraz

159
00:08:18,860 --> 00:08:22,070
bo prevladovala ta izraz n.

160
00:08:22,070 --> 00:08:27,850
Torej, izbira je nekako O izmed n kvadrat.

161
00:08:27,850 --> 00:08:31,460
Spomnimo, da je v našem primeru, izbor sort še vedno potrebna

162
00:08:31,460 --> 00:08:33,850
preveri, če je število, ki je bil že razporejene

163
00:08:33,850 --> 00:08:35,450
potrebno premakniti.

164
00:08:35,450 --> 00:08:38,929
To pomeni, da če bi tekel izbiro vrste kot je že

165
00:08:38,929 --> 00:08:43,070
razporejene seznam, bi bilo potrebno enako število korakov, kot je

166
00:08:43,070 --> 00:08:46,340
bi med vožnjo na popolnoma nesortiranih seznama.

167
00:08:46,340 --> 00:08:51,470
Torej, izbira sort je najboljši primer uspešnost n kvadrat,

168
00:08:51,470 --> 00:08:56,820
ki jih predstavljajo z omega n kvadrat.

169
00:08:56,820 --> 00:08:58,600
In to je to za neke izbire.

170
00:08:58,600 --> 00:09:00,630
Samo eden od mnogih algoritmov smo lahko

171
00:09:00,630 --> 00:09:02,390
uporabite za razvrščanje seznama.

172
00:09:02,390 --> 00:09:05,910
Moje ime je Tommy, in to je cs50.