1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Anem a fer una ullada a l'ordenació per selecció, un algorisme

2
00:00:09,980 --> 00:00:12,800
per a la presa d'una llista de nombres i classificar-les.

3
00:00:12,800 --> 00:00:15,750
Un algorisme, recordi, és simplement un pas a pas

4
00:00:15,750 --> 00:00:18,370
procediment per dur a terme una tasca.

5
00:00:18,370 --> 00:00:21,470
La idea bàsica darrere de l'ordenació per selecció és dividir

6
00:00:21,470 --> 00:00:23,390
la llista en dues parts -

7
00:00:23,390 --> 00:00:26,810
una porció ordenats i una porció sense classificar.

8
00:00:26,810 --> 00:00:30,200
A cada pas de l'algorisme, un nombre es mou des de la

9
00:00:30,200 --> 00:00:33,800
Unsorted porció a la porció ordenats fins que finalment la

10
00:00:33,800 --> 00:00:35,880
tota la llista s'organitza.

11
00:00:35,880 --> 00:00:38,510
Així que aquí hi ha una llista de sis números -

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

13
00:00:44,010 --> 00:00:47,680
En aquest moment tota la llista es considera sense ordenar.

14
00:00:47,680 --> 00:00:51,770
Tot i que un nombre com 16 pot estar ja en la seva correcta

15
00:00:51,770 --> 00:00:56,040
ubicació, el nostre algorisme no té manera de saber que fins que el

16
00:00:56,040 --> 00:00:57,980
tota la llista s'organitza.

17
00:00:57,980 --> 00:01:01,355
Així que considerarem cada nombre que es Unsorted fins d'ordenar

18
00:01:01,355 --> 00:01:03,800
nosaltres mateixos.

19
00:01:03,800 --> 00:01:06,890
Sabem que volem que la llista sigui en ordre ascendent.

20
00:01:06,890 --> 00:01:10,200
Així que anem a voler construir la porció ordenada de la nostra llista

21
00:01:10,200 --> 00:01:13,280
d'esquerra a dreta, el més petit al més gran.

22
00:01:13,280 --> 00:01:17,970
Per fer-ho, haurem de trobar l'element mínim sense classificar

23
00:01:17,970 --> 00:01:21,350
i el situen a l'extrem de la part ordenats.

24
00:01:21,350 --> 00:01:25,370
Atès que aquesta llista no està ordenada, l'única manera de fer-ho és

25
00:01:25,370 --> 00:01:29,330
veure tots els elements de la part sense classificar, recordant

26
00:01:29,330 --> 00:01:32,010
quin element és el més baix i comparant

27
00:01:32,010 --> 00:01:33,770
cada element a això.

28
00:01:33,770 --> 00:01:36,150
Així que el primer que veurem el 23.

29
00:01:36,150 --> 00:01:38,650
Aquest és el primer element que hem vist, així que vaig a recordar

30
00:01:38,650 --> 00:01:40,050
com el mínim.

31
00:01:40,050 --> 00:01:42,320
A continuació veurem 42.

32
00:01:42,320 --> 00:01:46,720
42 és més gran que 23, de manera que 23 continua sent el mínim.

33
00:01:46,720 --> 00:01:51,210
El següent és el 4, que està a menys de 23, així que recordarem 4

34
00:01:51,210 --> 00:01:52,880
com el nou mínim.

35
00:01:52,880 --> 00:01:56,380
Següent és 16, que és major que 4, de manera 4

36
00:01:56,380 --> 00:01:57,980
encara és el mínim.

37
00:01:57,980 --> 00:02:03,670
8 és major que 4, i 15 és major que 4, per la qual cosa ha de ser 4

38
00:02:03,670 --> 00:02:05,980
l'element més petit sense classificar.

39
00:02:05,980 --> 00:02:09,350
Així que tot i que com a éssers humans podem veure immediatament que el 4 és

40
00:02:09,350 --> 00:02:12,300
l'element mínim, el nostre algorisme té a veure

41
00:02:12,300 --> 00:02:15,710
cada element sense classificar, fins i tot després que hagis trobat el 4 - el

42
00:02:15,710 --> 00:02:16,860
element mínim.

43
00:02:16,860 --> 00:02:19,900
Així que ara que hem trobat l'element mínim, 4, anem a voler

44
00:02:19,900 --> 00:02:23,410
per moure'ls a la part de la llista ordenada.

45
00:02:23,410 --> 00:02:27,320
Atès que aquest és el primer pas, això vol dir que volem posar 4 a

46
00:02:27,320 --> 00:02:29,680
el principi de la llista.

47
00:02:29,680 --> 00:02:33,040
En aquest moment 23 es troba al principi de la llista, de manera

48
00:02:33,040 --> 00:02:36,080
canviarem el 4 i 23 de la.

49
00:02:36,080 --> 00:02:38,870
Així que ara la llista són aquestes.

50
00:02:38,870 --> 00:02:42,710
Sabem que 4 ha d'estar en la seva ubicació final, perquè és

51
00:02:42,710 --> 00:02:45,890
tant l'element més petit i l'element al principi

52
00:02:45,890 --> 00:02:46,960
de la llista.

53
00:02:46,960 --> 00:02:50,650
Així que això significa que no sempre hagi de moure de nou.

54
00:02:50,650 --> 00:02:53,910
Així que repetirem aquest procés per afegir un element més a la

55
00:02:53,910 --> 00:02:55,910
ordenats part de la llista.

56
00:02:55,910 --> 00:02:58,950
Sabem que no hem de mirar a la 4, perquè és

57
00:02:58,950 --> 00:03:00,000
ja ordenats.

58
00:03:00,000 --> 00:03:03,540
Així que podem començar en el 42, que recordarem com el

59
00:03:03,540 --> 00:03:05,290
element mínim.

60
00:03:05,290 --> 00:03:08,700
Així que la propera veurem el 23, que és inferior a 42, de manera que

61
00:03:08,700 --> 00:03:11,620
Recordo 23 és el nou mínim.

62
00:03:11,620 --> 00:03:14,870
A continuació veiem el 16 que és menor que 23, per

63
00:03:14,870 --> 00:03:16,800
16 és el nou mínim.

64
00:03:16,800 --> 00:03:19,720
Ara ens fixem en el 8, que és menys de 16, de manera

65
00:03:19,720 --> 00:03:21,130
8 és el nou mínim.

66
00:03:21,130 --> 00:03:25,900
I finalment 8 és menor que 15, pel que sabem que 8 és un mínim

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

68
00:03:27,780 --> 00:03:30,660
Així que això significa que hauríem d'afegir 8 al ordenar

69
00:03:30,660 --> 00:03:32,450
part de la llista.

70
00:03:32,450 --> 00:03:35,990
En aquest moment 4 és l'únic element classificat, pel que volem col · locar

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

72
00:03:38,410 --> 00:03:41,920
Atès que 42 és el primer element en la part no seleccionada de la

73
00:03:41,920 --> 00:03:47,260
llista, anem a voler canviar el 42 i el 8.

74
00:03:47,260 --> 00:03:49,680
Així que ara la llista són aquestes.

75
00:03:49,680 --> 00:03:53,830
4 i 8 representen la part ordenada de la llista, i el

76
00:03:53,830 --> 00:03:56,440
nombres restants representen la Unsorted

77
00:03:56,440 --> 00:03:58,260
part de la llista.

78
00:03:58,260 --> 00:04:00,630
Així que continuarem amb una altra iteració.

79
00:04:00,630 --> 00:04:03,850
Comencem amb 23 aquesta vegada, ja que no cal buscar en

80
00:04:03,850 --> 00:04:05,770
el 4 i el 8 ja perquè no tenen

81
00:04:05,770 --> 00:04:07,660
ja s'ha solucionat.

82
00:04:07,660 --> 00:04:10,270
16 és menor que 23, pel que recordarà

83
00:04:10,270 --> 00:04:12,070
16 com el nou mínim.

84
00:04:12,070 --> 00:04:18,149
16 és menor que 42, però 15 és menor que 16, per la qual cosa ha de ser 15

85
00:04:18,149 --> 00:04:20,480
l'element Unsorted mínim.

86
00:04:20,480 --> 00:04:24,580
Així que ara volem intercanviar el 15 i el 23 de

87
00:04:24,580 --> 00:04:26,310
ens donen aquesta llista.

88
00:04:26,310 --> 00:04:30,500
La part ordenada de la llista es compon de 4, 8 i 15, i

89
00:04:30,500 --> 00:04:33,210
aquests elements estan encara sense classificar.

90
00:04:33,210 --> 00:04:36,900
Però dóna la casualitat que el següent element sense classificar, 16,

91
00:04:36,900 --> 00:04:38,480
ja està ordenat.

92
00:04:38,480 --> 00:04:42,060
No obstant això, no hi ha manera que el nostre algorisme per saber que el 16 per

93
00:04:42,060 --> 00:04:45,230
ja es troba en la seva ubicació correcta, de manera que encara hem de

94
00:04:45,230 --> 00:04:47,870
repetir exactament el mateix procés.

95
00:04:47,870 --> 00:04:53,750
Així veiem que 16 és menor que 42, i 16 és menor que 23, per

96
00:04:53,750 --> 00:04:56,230
16 ha de ser l'element mínim.

97
00:04:56,230 --> 00:04:59,010
És impossible canviar aquest element amb si mateix, perquè puguem

98
00:04:59,010 --> 00:05:01,780
simplement deixi en aquest lloc.

99
00:05:01,780 --> 00:05:04,660
Així que hem de passar un més del nostre algorisme.

100
00:05:04,660 --> 00:05:09,370
42 és més gran que 23, per la qual cosa ha de ser el 23

101
00:05:09,370 --> 00:05:10,970
element Unsorted mínim.

102
00:05:10,970 --> 00:05:17,410
Quan canviï el 23 i 42 de la, acabem amb el nostre últim

103
00:05:17,410 --> 00:05:18,530
llista ordenada -

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

105
00:05:23,390 --> 00:05:26,830
Sabem 42 ha d'estar en el lloc correcte, ja que és la

106
00:05:26,830 --> 00:05:30,210
únic element a l'esquerra, i que és una espècie de selecció.

107
00:05:30,210 --> 00:05:32,100
Ara anem a formalitzar nostre algorisme amb alguns

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

109
00:05:34,540 --> 00:05:37,760
En la línia un, podem veure que necessitem per integrar més

110
00:05:37,760 --> 00:05:39,530
cada element de la llista.

111
00:05:39,530 --> 00:05:42,150
Excepte l'últim element, ja que l'element 1

112
00:05:42,150 --> 00:05:44,230
llista ja està ordenada.

113
00:05:44,230 --> 00:05:48,100
En la segona línia, considerem que el primer element de la Unsorted

114
00:05:48,100 --> 00:05:51,080
part de la llista per ser el mínim, com ho vam fer amb la nostra

115
00:05:51,080 --> 00:05:53,750
exemple, així que tenim alguna cosa per comparar.

116
00:05:53,750 --> 00:05:57,260
La línia tres s'inicia un segon bucle en què iterar sobre

117
00:05:57,260 --> 00:05:59,170
cada element sense classificar.

118
00:05:59,170 --> 00:06:02,150
Sabem que després d'i iteracions, la porció ordenats

119
00:06:02,150 --> 00:06:05,330
de la llista ha de tenir i elements en ella, ja que cada pas

120
00:06:05,330 --> 00:06:06,890
classe un element.

121
00:06:06,890 --> 00:06:11,770
De manera que l'element no seleccionats ha d'estar en la posició i + 1.

122
00:06:11,770 --> 00:06:15,440
En la línia quatre, es compara aquest element al mínim

123
00:06:15,440 --> 00:06:17,750
element que hem vist fins ara.

124
00:06:17,750 --> 00:06:20,560
Si l'element actual és menor que el mínim

125
00:06:20,560 --> 00:06:23,870
element, llavors recordem aquest element com la nova

126
00:06:23,870 --> 00:06:26,250
mínim en la línia cinc.

127
00:06:26,250 --> 00:06:29,900
Finalment, en les línies sis i set, canviem el mínim

128
00:06:29,900 --> 00:06:33,080
element amb l'element sense classificar primer, de manera

129
00:06:33,080 --> 00:06:36,990
afegir a la porció de la llista ordenada.

130
00:06:36,990 --> 00:06:40,030
Quan tenim un algorisme, un tema crític

131
00:06:40,030 --> 00:06:43,370
nosaltres de programador fa temps em portarà?

132
00:06:43,370 --> 00:06:46,970
En primer lloc, vaig a fer la pregunta quant de temps es necessita perquè aquesta

133
00:06:46,970 --> 00:06:50,070
algoritme per executar-se en el pitjor dels casos?

134
00:06:50,070 --> 00:06:51,640
Recordem que representem aquesta carrera

135
00:06:51,640 --> 00:06:55,060
temps amb la notació O gran.

136
00:06:55,060 --> 00:06:58,650
Per tal de determinar l'element Unsorted mínim, es

137
00:06:58,650 --> 00:07:01,880
essencialment havien de comparar cada element de la llista per

138
00:07:01,880 --> 00:07:04,040
cada altre element a la llista.

139
00:07:04,040 --> 00:07:08,430
Intuïtivament, això sona com una junta d'operació núm al quadrat.

140
00:07:08,430 --> 00:07:12,050
Quant al nostre pseudocodi, també tenim un bucle niat dins

141
00:07:12,050 --> 00:07:14,420
altre bucle, que en realitat sona com una junta

142
00:07:14,420 --> 00:07:16,480
d'operació n al quadrat.

143
00:07:16,480 --> 00:07:19,250
No obstant això, recordeu que no hi havia necessitat de mirar per sobre de la

144
00:07:19,250 --> 00:07:23,460
llista completa per determinar l'element Unsorted mínim?

145
00:07:23,460 --> 00:07:26,600
Quan vam saber que el 4 es classifiquen, per exemple, no ens

146
00:07:26,600 --> 00:07:28,170
necessitem veure de nou.

147
00:07:28,170 --> 00:07:31,020
El mateix passa amb aquest menor és el temps d'execució?

148
00:07:31,020 --> 00:07:34,510
Per a la nostra llista de longitud 6, havíem de fer cinc

149
00:07:34,510 --> 00:07:37,990
comparacions per al primer element, quatre comparacions per

150
00:07:37,990 --> 00:07:40,750
el segon element, i així successivament.

151
00:07:40,750 --> 00:07:44,690
Això significa que el nombre total de passos és la suma dels

152
00:07:44,690 --> 00:07:49,160
els nombres enters d'1 a la longitud de la llista menys 1.

153
00:07:49,160 --> 00:07:51,005
Podem representar això amb una suma.

154
00:07:57,980 --> 00:07:59,910
No entrarem en sumes aquí.

155
00:07:59,910 --> 00:08:04,900
Però resulta que aquesta suma és igual a n vegades

156
00:08:04,900 --> 00:08:07,540
n menys 1 sobre 2.

157
00:08:07,540 --> 00:08:14,220
O de forma equivalent, en al quadrat sobre 2 menys n sobre 2.

158
00:08:14,220 --> 00:08:18,860
Quan es parla de temps d'execució asimptòtic, aquest terme al quadrat n

159
00:08:18,860 --> 00:08:22,070
va a dominar aquest terme n.

160
00:08:22,070 --> 00:08:27,850
Així tipus de selecció és O de n al quadrat.

161
00:08:27,850 --> 00:08:31,460
Recordem que en el nostre exemple, classificar selecció segueix sent necessari per

162
00:08:31,460 --> 00:08:33,850
comprovar si un nombre que ja es va solucionar

163
00:08:33,850 --> 00:08:35,450
necessària per ser mogut.

164
00:08:35,450 --> 00:08:38,929
Així que això vol dir que si ens trobem amb una mena de selecció sobre ja

165
00:08:38,929 --> 00:08:43,070
llista ordenada, es requeriria el mateix nombre de passos com es

166
00:08:43,070 --> 00:08:46,340
ho faria quan s'executa sobre una llista completament sense classificar.

167
00:08:46,340 --> 00:08:51,470
Així que tipus de selecció té un acompliment millor dels casos quadrat de n,

168
00:08:51,470 --> 00:08:56,820
que representem amb omega n al quadrat.

169
00:08:56,820 --> 00:08:58,600
I això és tot per tipus de selecció.

170
00:08:58,600 --> 00:09:00,630
Només un dels molts algoritmes que puguem

171
00:09:00,630 --> 00:09:02,390
utilitzar per ordenar una llista.

172
00:09:02,390 --> 00:09:05,910
El meu nom és Tommy, i això és CS50.