1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] Tommy: Se pou nou pran yon gade nan kalite seleksyon, yon algorithm

2
00:00:09,980 --> 00:00:12,800
pou pran yon lis nimewo ak Fouye yo.

3
00:00:12,800 --> 00:00:15,750
Yon algorithm, sonje, se senpleman yon etap-pa-etap

4
00:00:15,750 --> 00:00:18,370
pwosedi pou reyalize yon travay.

5
00:00:18,370 --> 00:00:21,470
Lide a debaz dèyè sòt seleksyon se divize

6
00:00:21,470 --> 00:00:23,390
lis nou an nan de pòsyon -

7
00:00:23,390 --> 00:00:26,810
yon pòsyon klase epi yon pòsyon klase.

8
00:00:26,810 --> 00:00:30,200
Nan chak etap nan algorithm la, se yon nimewo te deplase soti nan la

9
00:00:30,200 --> 00:00:33,800
klase pòsyon pòsyon nan Ranje jouk evantyèlman a

10
00:00:33,800 --> 00:00:35,880
se tout lis Ranje.

11
00:00:35,880 --> 00:00:38,510
Se konsa, isit la nan yon lis nan sis nimewo -

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

13
00:00:44,010 --> 00:00:47,680
Dwa koulye a, se lis la tout antye konsidere kòm klase.

14
00:00:47,680 --> 00:00:51,770
Menm si yon nimewo tankou 16 ka deja dwe nan kòrèk li yo

15
00:00:51,770 --> 00:00:56,040
kote, algorithm nou an ki gen okenn jan pou konnen sa jouk lè a

16
00:00:56,040 --> 00:00:57,980
se tout lis Ranje.

17
00:00:57,980 --> 00:01:01,355
Se konsa, nou pral konsidere chak nimewo yo dwe klase jiskaske nou sòt

18
00:01:01,355 --> 00:01:03,800
li tèt nou.

19
00:01:03,800 --> 00:01:06,890
Nou konnen nou vle lis la yo dwe nan Ascending lòd.

20
00:01:06,890 --> 00:01:10,200
Se konsa, nou pral vle bati pòsyon nan Ranje nan lis nou an

21
00:01:10,200 --> 00:01:13,280
de goch a dwat, pi piti pi gwo.

22
00:01:13,280 --> 00:01:17,970
Pou fè sa, nou pral bezwen jwenn minimòm eleman nan klase

23
00:01:17,970 --> 00:01:21,350
li mete l 'nan fen a nan pòsyon an Ranje.

24
00:01:21,350 --> 00:01:25,370
Depi lis sa a pa se Klase, wout la sèlman nan fè sa se

25
00:01:25,370 --> 00:01:29,330
gade nan chak eleman nan pòsyon klase, sonje

26
00:01:29,330 --> 00:01:32,010
ki eleman se pi ba a ak konpare

27
00:01:32,010 --> 00:01:33,770
chak eleman ak sa yo ki.

28
00:01:33,770 --> 00:01:36,150
Se konsa, nou pral premye gade nan 23 an.

29
00:01:36,150 --> 00:01:38,650
Sa a se eleman nan premye nou te wè, se konsa nou pral sonje

30
00:01:38,650 --> 00:01:40,050
li kòm minimòm la.

31
00:01:40,050 --> 00:01:42,320
Next n ap gade 42.

32
00:01:42,320 --> 00:01:46,720
42 se pi gwo pase 23, se konsa 23 se toujou minimòm la.

33
00:01:46,720 --> 00:01:51,210
Next se 4 a ki se mwens pase 23, se konsa nou pral sonje 4

34
00:01:51,210 --> 00:01:52,880
kòm minimòm nan nouvo.

35
00:01:52,880 --> 00:01:56,380
Next se 16 ki se pi gwo pase 4, ki fè 4

36
00:01:56,380 --> 00:01:57,980
se toujou minimòm la.

37
00:01:57,980 --> 00:02:03,670
8 se pi gwo pase 4, ak 15 se pi gwo pase 4, ki fè 4 yo dwe

38
00:02:03,670 --> 00:02:05,980
pi piti eleman ki klase.

39
00:02:05,980 --> 00:02:09,350
Se konsa, menm si tankou moun nou ka imedyatman wè ke 4 se

40
00:02:09,350 --> 00:02:12,300
eleman minimòm-nan, algorithm nou an bezwen fè yon gade nan

41
00:02:12,300 --> 00:02:15,710
chak eleman nan klase, menm apre nou te jwenn 4 an -

42
00:02:15,710 --> 00:02:16,860
minimòm eleman.

43
00:02:16,860 --> 00:02:19,900
Se konsa, kounye a ke nou te jwenn eleman minimòm-nan, 4, nou pral vle

44
00:02:19,900 --> 00:02:23,410
pou avanse pou li nan pòsyon nan Ranje nan lis la.

45
00:02:23,410 --> 00:02:27,320
Depi sa a se premye etap la, sa vle di nou vle mete 4 nan

46
00:02:27,320 --> 00:02:29,680
nan konmansman an nan lis la.

47
00:02:29,680 --> 00:02:33,040
Kounye a, 23 se nan kòmansman an nan lis la, se konsa

48
00:02:33,040 --> 00:02:36,080
kite a swap 4 an ak 23 an.

49
00:02:36,080 --> 00:02:38,870
Se konsa, kounye a lis nou an sanble tankou sa a.

50
00:02:38,870 --> 00:02:42,710
Nou konnen ke 4 yo dwe nan kote final li yo, paske li se

51
00:02:42,710 --> 00:02:45,890
tou de eleman ki pi piti a ak eleman ki nan kòmansman an

52
00:02:45,890 --> 00:02:46,960
nan lis la.

53
00:02:46,960 --> 00:02:50,650
Se konsa, sa sa vle di ke nou pa janm bezwen pou avanse pou li ankò.

54
00:02:50,650 --> 00:02:53,910
Se konsa, kite a repete pwosesis sa a ajoute yon lòt eleman nan

55
00:02:53,910 --> 00:02:55,910
Ranje pòsyon nan lis la.

56
00:02:55,910 --> 00:02:58,950
Nou konnen nou pa bezwen fè yon gade nan 4 a, paske li nan

57
00:02:58,950 --> 00:03:00,000
deja klase.

58
00:03:00,000 --> 00:03:03,540
Se konsa, nou kapab kòmanse nan 42 an, ki nou pral sonje kòm la

59
00:03:03,540 --> 00:03:05,290
minimòm eleman.

60
00:03:05,290 --> 00:03:08,700
Se konsa, pwochen n ap gade 23 la ki se mwens pase 42, konsa nou

61
00:03:08,700 --> 00:03:11,620
sonje 23 se minimòm nan nouvo.

62
00:03:11,620 --> 00:03:14,870
Next nou wè 16 la ki se mwens pase 23, se konsa

63
00:03:14,870 --> 00:03:16,800
16 se minimòm nan nouvo.

64
00:03:16,800 --> 00:03:19,720
Koulye a, nou gade nan 8 la ki se mwens pase 16, se konsa

65
00:03:19,720 --> 00:03:21,130
8 se minimòm nan nouvo.

66
00:03:21,130 --> 00:03:25,900
Epi finalman 8 se mwens pase 15, se konsa nou konnen ke 8 se yon minimòm

67
00:03:25,900 --> 00:03:27,780
klase eleman.

68
00:03:27,780 --> 00:03:30,660
Se konsa, sa vle di nou ta dwe tache 8 a Ranje a

69
00:03:30,660 --> 00:03:32,450
pòsyon nan lis la.

70
00:03:32,450 --> 00:03:35,990
Kounye a, 4 se eleman ki sèlman Ranje, se konsa nou vle mete

71
00:03:35,990 --> 00:03:38,410
pwochen an 8 a 4 an.

72
00:03:38,410 --> 00:03:41,920
Depi 42 se eleman ki an premye nan pòsyon ki klase nan la

73
00:03:41,920 --> 00:03:47,260
lis, nou pral vle swap 42 an ak 8 la.

74
00:03:47,260 --> 00:03:49,680
Se konsa, kounye a lis nou an sanble tankou sa a.

75
00:03:49,680 --> 00:03:53,830
4 ak 8 reprezante pòsyon nan Ranje nan lis la, ak nan

76
00:03:53,830 --> 00:03:56,440
ki rete nimewo reprezante klase nan

77
00:03:56,440 --> 00:03:58,260
pòsyon nan lis la.

78
00:03:58,260 --> 00:04:00,630
Se konsa, kite a kontinye ak yon lòt iterasyon.

79
00:04:00,630 --> 00:04:03,850
Nou kòmanse avèk 23 tan sa a, depi nou pa bezwen gade

80
00:04:03,850 --> 00:04:05,770
4 an ak 8 nan ankò paske yo te

81
00:04:05,770 --> 00:04:07,660
te deja klase.

82
00:04:07,660 --> 00:04:10,270
16 se mwens pase 23, se konsa nou pral sonje

83
00:04:10,270 --> 00:04:12,070
16 kòm minimòm nan nouvo.

84
00:04:12,070 --> 00:04:18,149
16 se mwens pase 42, men 15 gen mwens pase 16, se konsa 15 yo dwe

85
00:04:18,149 --> 00:04:20,480
minimòm eleman nan klase.

86
00:04:20,480 --> 00:04:24,580
Se konsa, kounye a nou vle swap 15 an ak 23 an

87
00:04:24,580 --> 00:04:26,310
ba nou lis sa a.

88
00:04:26,310 --> 00:04:30,500
Pòsyon nan Ranje nan lis la konsiste de 4 8, ak 15, ak

89
00:04:30,500 --> 00:04:33,210
eleman sa yo se toujou klase.

90
00:04:33,210 --> 00:04:36,900
Men, li jis pou rive nan pwochen fèt eleman nan klase, 16,

91
00:04:36,900 --> 00:04:38,480
deja klase.

92
00:04:38,480 --> 00:04:42,060
Sepandan, gen nan pa gen fason pou algorithm nou konnen ke 16

93
00:04:42,060 --> 00:04:45,230
se deja nan kote kòrèk li yo, pou nou toujou bezwen

94
00:04:45,230 --> 00:04:47,870
repete egzakteman menm pwosesis yo.

95
00:04:47,870 --> 00:04:53,750
Se konsa, nou wè ke 16 se mwens pase 42, ak 16 se mwens pase 23, se konsa

96
00:04:53,750 --> 00:04:56,230
16 dwe eleman nan minimòm.

97
00:04:56,230 --> 00:04:59,010
Li nan enposib swap sa a eleman ak pwòp tèt li, se konsa nou kapab

98
00:04:59,010 --> 00:05:01,780
tou senpleman kite li nan sa a kote.

99
00:05:01,780 --> 00:05:04,660
Se konsa, nou bezwen youn plis pas nan algorithm nou an.

100
00:05:04,660 --> 00:05:09,370
42 se pi gran pase 23, se konsa 23 yo dwe a

101
00:05:09,370 --> 00:05:10,970
minimòm eleman klase.

102
00:05:10,970 --> 00:05:17,410
Yon fwa nou boukante 23 an ak 42 an, nou fini ak final nou an

103
00:05:17,410 --> 00:05:18,530
Ranje lis -

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

105
00:05:23,390 --> 00:05:26,830
Nou konnen 42 yo dwe an plas ki kòrèk la depi li nan la

106
00:05:26,830 --> 00:05:30,210
sèlman eleman ki rete, e sa a, se sòt seleksyon.

107
00:05:30,210 --> 00:05:32,100
Se pou nou kounye a formalizra algorithm nou an ak kèk

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

109
00:05:34,540 --> 00:05:37,760
Sou liy youn, nou ka wè ke nou bezwen entegre sou

110
00:05:37,760 --> 00:05:39,530
chak eleman nan lis la.

111
00:05:39,530 --> 00:05:42,150
Eksepte eleman an dènye, depi eleman nan 1

112
00:05:42,150 --> 00:05:44,230
lis la deja klase.

113
00:05:44,230 --> 00:05:48,100
Sou liy de, nou konsidere eleman an premye nan klase nan

114
00:05:48,100 --> 00:05:51,080
pòsyon nan lis la yo dwe minimòm lan, kòm nou te fè sa avèk nou

115
00:05:51,080 --> 00:05:53,750
egzanp, pou nou gen yon bagay yo konpare ak.

116
00:05:53,750 --> 00:05:57,260
Liy twa kòmanse yon riban dezyèm nan ki nou repekte sou

117
00:05:57,260 --> 00:05:59,170
chak eleman klase.

118
00:05:59,170 --> 00:06:02,150
Nou konnen ke apre mwen fin itérations, pòsyon nan Ranje

119
00:06:02,150 --> 00:06:05,330
nan lis nou an dwe gen mwen eleman nan li depi chak etap

120
00:06:05,330 --> 00:06:06,890
kalite yon sèl eleman.

121
00:06:06,890 --> 00:06:11,770
Se konsa, premye eleman ki klase yo dwe nan pozisyon mwen plis 1.

122
00:06:11,770 --> 00:06:15,440
Sou liy kat, nou konpare eleman aktyèl la minimòm la

123
00:06:15,440 --> 00:06:17,750
eleman ke nou te wè byen lwen tèlman.

124
00:06:17,750 --> 00:06:20,560
Si eleman aktyèl la se pi piti pase minimòm nan

125
00:06:20,560 --> 00:06:23,870
eleman, Lè sa a, nou chonje eleman aktyèl la kòm nouvo a

126
00:06:23,870 --> 00:06:26,250
minimòm sou liy senk.

127
00:06:26,250 --> 00:06:29,900
Finalman, sou liy sis ak sèt, nou boukante minimòm la

128
00:06:29,900 --> 00:06:33,080
eleman ak eleman nan premye klase, kidonk

129
00:06:33,080 --> 00:06:36,990
ajoute li nan pòsyon nan Ranje nan lis la.

130
00:06:36,990 --> 00:06:40,030
Yon fwa nou gen yon algorithm, yon kesyon ki enpòtan nan mande

131
00:06:40,030 --> 00:06:43,370
tèt nou kòm pwogramasyon se konbyen tan t 'ki pran?

132
00:06:43,370 --> 00:06:46,970
Nou pral premye mande kesyon an konbyen tan li pran pou sa a

133
00:06:46,970 --> 00:06:50,070
algorithm nan kouri nan ka ki pi mal la?

134
00:06:50,070 --> 00:06:51,640
Rapèl nou reprezante sa a kouri

135
00:06:51,640 --> 00:06:55,060
tan ak notasyon gwo O.

136
00:06:55,060 --> 00:06:58,650
Yo nan lòd yo detèmine minimòm eleman nan klase, nou

137
00:06:58,650 --> 00:07:01,880
esansyèlman te gen yo konpare chak eleman nan lis la

138
00:07:01,880 --> 00:07:04,040
chak eleman lòt nan lis la.

139
00:07:04,040 --> 00:07:08,430
Intuitivement, sa a son tankou yon O de operasyon okib n.

140
00:07:08,430 --> 00:07:12,050
Gade nan pseudocode nou an, nou menm tou nou gen yon riban pare solèy andedan

141
00:07:12,050 --> 00:07:14,420
yon lòt bouk yo, ki tout bon son tankou yon O

142
00:07:14,420 --> 00:07:16,480
pou n operasyon okib.

143
00:07:16,480 --> 00:07:19,250
Sepandan, sonje ke nou pa t 'bezwen gade sou la

144
00:07:19,250 --> 00:07:23,460
tout lis lè y ap detèmine minimòm eleman nan klase?

145
00:07:23,460 --> 00:07:26,600
Yon fwa nou te konnen ki te 4 nan Ranje, pou egzanp, nou pa t '

146
00:07:26,600 --> 00:07:28,170
bezwen gade l 'ankò.

147
00:07:28,170 --> 00:07:31,020
Se konsa, sa a pi ba tan an kouri?

148
00:07:31,020 --> 00:07:34,510
Pou lis nou an longè, 6, nou bezwen fè senk

149
00:07:34,510 --> 00:07:37,990
konparezon pou eleman a an premye, kat konparezon pou

150
00:07:37,990 --> 00:07:40,750
eleman, dezyèm lan, ak sou sa.

151
00:07:40,750 --> 00:07:44,690
Sa vle di ke kantite total etap a se sòm total

152
00:07:44,690 --> 00:07:49,160
nonm antye relatif yo nan 1 rive nan longè nan lis la mwens 1.

153
00:07:49,160 --> 00:07:51,005
Nou ka reprezante sa a ak yon somasyon.

154
00:07:57,980 --> 00:07:59,910
Nou pa pral antre summations isit la.

155
00:07:59,910 --> 00:08:04,900
Men, li sanble ke sa a somasyon ki egal a n fwa

156
00:08:04,900 --> 00:08:07,540
n mwens 1 sou 2.

157
00:08:07,540 --> 00:08:14,220
Oswa équivalant, n Squared plis pase 2 mwens n plis pase 2.

158
00:08:14,220 --> 00:08:18,860
Lè w ap pale sou ègzekutabl asenptotik, sa a n tèm okib

159
00:08:18,860 --> 00:08:22,070
ki pral domine tèm sa a n.

160
00:08:22,070 --> 00:08:27,850
Se konsa, sòt seleksyon se O nan n okib.

161
00:08:27,850 --> 00:08:31,460
Sonje byen, nan egzanp nou an, sòt seleksyon toujou bezwen

162
00:08:31,460 --> 00:08:33,850
tcheke si yon nimewo ki te deja klase

163
00:08:33,850 --> 00:08:35,450
bezwen brannen l '.

164
00:08:35,450 --> 00:08:38,929
Se konsa, sa vle di ke si nou kouri sòt seleksyon sou plis pase yon deja

165
00:08:38,929 --> 00:08:43,070
Ranje lis, li ta mande pou menm kantite etap kòm li

166
00:08:43,070 --> 00:08:46,340
ta lè kouri sou yon lis konplètman klase.

167
00:08:46,340 --> 00:08:51,470
Se konsa, sòt seleksyon an gen yon pèfòmans pi bon nan ka okib n,

168
00:08:51,470 --> 00:08:56,820
ki nou reprezante ak Omega n okib.

169
00:08:56,820 --> 00:08:58,600
Epi sa a, li pou sòt seleksyon.

170
00:08:58,600 --> 00:09:00,630
Jis youn nan algoritm yo anpil nou kapab

171
00:09:00,630 --> 00:09:02,390
sèvi ak sòt yon lis.

172
00:09:02,390 --> 00:09:05,910
Non mwen se Tommy, e sa se cs50.