1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] Tommy: Imos dar un ollo tipo de selección, un algoritmo

2
00:00:09,980 --> 00:00:12,800
para a toma de unha lista de números e clasificándose os.

3
00:00:12,800 --> 00:00:15,750
Un algoritmo, lembre, é simplemente un paso a paso

4
00:00:15,750 --> 00:00:18,370
procedemento para realizar unha tarefa.

5
00:00:18,370 --> 00:00:21,470
A idea básica detrás do tipo de selección é dividir

6
00:00:21,470 --> 00:00:23,390
nosa lista en dúas partes -

7
00:00:23,390 --> 00:00:26,810
unha parte ordenada e unha porción indiferenciados.

8
00:00:26,810 --> 00:00:30,200
En cada etapa do algoritmo, un número é movido a partir da

9
00:00:30,200 --> 00:00:33,800
parte indiferenciados para a porción clasificados ata, finalmente, o

10
00:00:33,800 --> 00:00:35,880
completa está clasificada.

11
00:00:35,880 --> 00:00:38,510
Entón aquí está a lista de seis números -

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

13
00:00:44,010 --> 00:00:47,680
Agora toda a lista é considerada sen clasificación.

14
00:00:47,680 --> 00:00:51,770
Aínda que un número como 16 xa pode estar na súa correcta

15
00:00:51,770 --> 00:00:56,040
situación, o noso algoritmo ten ningunha forma de saber que ata o

16
00:00:56,040 --> 00:00:57,980
completa está clasificada.

17
00:00:57,980 --> 00:01:01,355
Entón, imos considerar cada número a ser triados ata clasificar

18
00:01:01,355 --> 00:01:03,800
nós mesmos.

19
00:01:03,800 --> 00:01:06,890
Nós sabemos que queremos a lista para estar en orde crecente.

20
00:01:06,890 --> 00:01:10,200
Entón, nós imos querer construír a parte ordenada da nosa lista

21
00:01:10,200 --> 00:01:13,280
de esquerda a dereita, a menor para o maior.

22
00:01:13,280 --> 00:01:17,970
Para iso, imos ter que atopar o elemento mínimo indiferenciados

23
00:01:17,970 --> 00:01:21,350
e poñelas no fin da porción clasificada.

24
00:01:21,350 --> 00:01:25,370
Como esta lista non está ordenada, a única forma de facelo é

25
00:01:25,370 --> 00:01:29,330
mirar para cada elemento na porción non separados, lembrando

26
00:01:29,330 --> 00:01:32,010
que elemento é a máis baixa e comparando

27
00:01:32,010 --> 00:01:33,770
Cada elemento que.

28
00:01:33,770 --> 00:01:36,150
Entón, imos ollar primeiro para o 23.

29
00:01:36,150 --> 00:01:38,650
Este é o primeiro elemento que temos visto, por iso imos lembrar

30
00:01:38,650 --> 00:01:40,050
como mínimo.

31
00:01:40,050 --> 00:01:42,320
A continuación, imos ollar para 42.

32
00:01:42,320 --> 00:01:46,720
42 é maior que 23, entón 23 é aínda o mínimo.

33
00:01:46,720 --> 00:01:51,210
O seguinte é o 4, que é inferior a 23, así que imos lembrar 4

34
00:01:51,210 --> 00:01:52,880
como o novo mínimo.

35
00:01:52,880 --> 00:01:56,380
A continuación é 16, que é maior que 4, entón 4

36
00:01:56,380 --> 00:01:57,980
aínda é o mínimo.

37
00:01:57,980 --> 00:02:03,670
8 é maior que 4 e 15 é maior que 4, entón 4 debe ser

38
00:02:03,670 --> 00:02:05,980
menor elemento indiferenciado.

39
00:02:05,980 --> 00:02:09,350
Así, aínda que, como seres humanos, podemos ver inmediatamente que 4 é

40
00:02:09,350 --> 00:02:12,300
o elemento mínimo, o algoritmo precisa de ollar para

41
00:02:12,300 --> 00:02:15,710
Cada elemento indiferenciado, mesmo despois de ter atopado a 4 - o

42
00:02:15,710 --> 00:02:16,860
elemento mínimo.

43
00:02:16,860 --> 00:02:19,900
Polo tanto, agora que atopamos o elemento mínimo, 4, imos querer

44
00:02:19,900 --> 00:02:23,410
para movela na porción da lista ordenada.

45
00:02:23,410 --> 00:02:27,320
Unha vez que este é o primeiro paso, isto significa que queren pór en 4

46
00:02:27,320 --> 00:02:29,680
o inicio da lista.

47
00:02:29,680 --> 00:02:33,040
Nese momento 23 é, no inicio da lista, de modo

48
00:02:33,040 --> 00:02:36,080
Imos cambiar o 4 eo 23.

49
00:02:36,080 --> 00:02:38,870
Entón, agora a nosa lista parecida con esta.

50
00:02:38,870 --> 00:02:42,710
Sabemos que 4 ha de ser na súa posición final, xa que é

51
00:02:42,710 --> 00:02:45,890
tanto o elemento máis pequeno eo elemento no inicio

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

53
00:02:46,960 --> 00:02:50,650
Entón iso significa que non precisa moverse de novo.

54
00:02:50,650 --> 00:02:53,910
Entón, imos repetir este proceso para engadir un elemento para a

55
00:02:53,910 --> 00:02:55,910
parcela clasificada na lista.

56
00:02:55,910 --> 00:02:58,950
Nós sabemos que non precisamos de ollar para o 4, xa que é

57
00:02:58,950 --> 00:03:00,000
xa están clasificados.

58
00:03:00,000 --> 00:03:03,540
Así, podemos comezar no 42, que vai lembrar de como a

59
00:03:03,540 --> 00:03:05,290
elemento mínimo.

60
00:03:05,290 --> 00:03:08,700
Entón, a próxima imos ollar para o 23, que é menor que 42, entón nós

61
00:03:08,700 --> 00:03:11,620
lembrar 23 é o novo mínimo.

62
00:03:11,620 --> 00:03:14,870
A continuación, vemos a 16 que é inferior a 23, para

63
00:03:14,870 --> 00:03:16,800
16 é o novo mínimo.

64
00:03:16,800 --> 00:03:19,720
Agora imos examinar o 8 que é menos do que 16, entón

65
00:03:19,720 --> 00:03:21,130
8 é o novo mínimo.

66
00:03:21,130 --> 00:03:25,900
E finalmente 8 é inferior a 15, polo que sabemos que 8 é un mínimo

67
00:03:25,900 --> 00:03:27,780
elemento indiferenciado.

68
00:03:27,780 --> 00:03:30,660
Entón iso significa que debemos engadir 8 ao ordenadas

69
00:03:30,660 --> 00:03:32,450
porción da lista.

70
00:03:32,450 --> 00:03:35,990
Agora 4 é o único elemento clasificados, por iso queremos poñer

71
00:03:35,990 --> 00:03:38,410
o próximo día 8 para o 4.

72
00:03:38,410 --> 00:03:41,920
Unha vez que 42 é o primeiro elemento na porción non separados do

73
00:03:41,920 --> 00:03:47,260
lista, imos querer cambiar o 42 eo 8.

74
00:03:47,260 --> 00:03:49,680
Entón, agora a nosa lista parecida con esta.

75
00:03:49,680 --> 00:03:53,830
4 e 8 representan a parcela clasificada da lista, eo

76
00:03:53,830 --> 00:03:56,440
números restantes representan a indiferenciados

77
00:03:56,440 --> 00:03:58,260
porción da lista.

78
00:03:58,260 --> 00:04:00,630
Entón, imos continuar con outro iteração.

79
00:04:00,630 --> 00:04:03,850
Comezamos con 23 desta vez, xa que non precisa de ollar para

80
00:04:03,850 --> 00:04:05,770
o 4 eo 8 máis, porque eles teñen

81
00:04:05,770 --> 00:04:07,660
xa foron clasificados.

82
00:04:07,660 --> 00:04:10,270
16 é menor que 23, polo tanto, nós lembraremos

83
00:04:10,270 --> 00:04:12,070
16, como o novo mínimo.

84
00:04:12,070 --> 00:04:18,149
16 é menor que 42, pero 15 é menor que 16, entón debe ser 15

85
00:04:18,149 --> 00:04:20,480
o elemento mínimo indiferenciados.

86
00:04:20,480 --> 00:04:24,580
Entón, agora queremos trocar os 15 e os 23 a

87
00:04:24,580 --> 00:04:26,310
dar esta lista.

88
00:04:26,310 --> 00:04:30,500
A porción da lista ordenada é constituída por 4, 8 e 15, e

89
00:04:30,500 --> 00:04:33,210
estes elementos están aínda sen clasificación.

90
00:04:33,210 --> 00:04:36,900
Pero acontece que o próximo elemento indiferenciado, 16,

91
00:04:36,900 --> 00:04:38,480
xa está clasificado.

92
00:04:38,480 --> 00:04:42,060
Con todo, non hai ningunha maneira para o noso algoritmo para saber que 16

93
00:04:42,060 --> 00:04:45,230
xa está no seu lugar correcto, entón aínda necesitamos

94
00:04:45,230 --> 00:04:47,870
repetir exactamente o mesmo proceso.

95
00:04:47,870 --> 00:04:53,750
Polo tanto, vemos que 16 é menos de 42, e 16 é menor que 23, entón

96
00:04:53,750 --> 00:04:56,230
16 debe ser o elemento mínimo.

97
00:04:56,230 --> 00:04:59,010
É imposible cambiar ese elemento con el mesmo, para que poidamos

98
00:04:59,010 --> 00:05:01,780
simplemente deixar lo no local.

99
00:05:01,780 --> 00:05:04,660
Entón necesitamos un paso máis do noso algoritmo.

100
00:05:04,660 --> 00:05:09,370
42 é maior que 23, entón 23 debe ser o

101
00:05:09,370 --> 00:05:10,970
indiferenciados elemento mínimo.

102
00:05:10,970 --> 00:05:17,410
Unha vez que cambiar os 23 e os 42, imos acabar coa nosa final

103
00:05:17,410 --> 00:05:18,530
Lista de clasificados -

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

105
00:05:23,390 --> 00:05:26,830
Sabemos 42 debe estar no lugar correcto, xa que é o

106
00:05:26,830 --> 00:05:30,210
único elemento á esquerda, e que é unha especie de selección.

107
00:05:30,210 --> 00:05:32,100
Imos agora formalizar o noso algoritmo con algún

108
00:05:32,100 --> 00:05:34,540
pseudocódigo.

109
00:05:34,540 --> 00:05:37,760
Nunha liña, podemos ver que necesitamos integrar máis

110
00:05:37,760 --> 00:05:39,530
Cada elemento da lista.

111
00:05:39,530 --> 00:05:42,150
Excepto o último elemento, xa que o elemento 1

112
00:05:42,150 --> 00:05:44,230
Lista xa está clasificado.

113
00:05:44,230 --> 00:05:48,100
Na liña dous, consideramos que o primeiro elemento da unsorted

114
00:05:48,100 --> 00:05:51,080
parte da lista para ser o mínimo, como fixemos coa nosa

115
00:05:51,080 --> 00:05:53,750
exemplo, de xeito que temos algo para comparar.

116
00:05:53,750 --> 00:05:57,260
Liña de tres comeza unha segunda volta na que iterar

117
00:05:57,260 --> 00:05:59,170
Cada elemento indiferenciado.

118
00:05:59,170 --> 00:06:02,150
Sabemos que, despois de iterações, a parte clasificada

119
00:06:02,150 --> 00:06:05,330
da nosa lista debe ter i elementos nel desde cada paso

120
00:06:05,330 --> 00:06:06,890
tipo dun elemento.

121
00:06:06,890 --> 00:06:11,770
Así, o primeiro elemento unsorted debe estar na posición i + 1.

122
00:06:11,770 --> 00:06:15,440
Na liña de catro, comparamos o elemento actual mínimo

123
00:06:15,440 --> 00:06:17,750
elemento que vimos ata agora.

124
00:06:17,750 --> 00:06:20,560
Se o elemento de corrente é menor que o mínimo

125
00:06:20,560 --> 00:06:23,870
elemento, entón lembre-se o elemento actual como a nova

126
00:06:23,870 --> 00:06:26,250
mínima na liña cinco.

127
00:06:26,250 --> 00:06:29,900
Finalmente, en liñas seis e sete, trocamos o mínimo

128
00:06:29,900 --> 00:06:33,080
elemento co primeiro elemento non separados, así

129
00:06:33,080 --> 00:06:36,990
engadindo-á porción da lista ordenada.

130
00:06:36,990 --> 00:06:40,030
Unha vez que temos un algoritmo, unha importante causa de pedir

131
00:06:40,030 --> 00:06:43,370
nós como programadores é canto tempo leva?

132
00:06:43,370 --> 00:06:46,970
Imos primeiro facer a pregunta canto tempo leva para esa

133
00:06:46,970 --> 00:06:50,070
algoritmo para realizar no peor caso?

134
00:06:50,070 --> 00:06:51,640
Recordo que representan esta carreira

135
00:06:51,640 --> 00:06:55,060
tempo con notación O grande.

136
00:06:55,060 --> 00:06:58,650
A fin de determinar o elemento mínimo indiferenciados, nós

137
00:06:58,650 --> 00:07:01,880
tiña esencialmente para comparar cada elemento da lista de

138
00:07:01,880 --> 00:07:04,040
todos os outros elementos da lista.

139
00:07:04,040 --> 00:07:08,430
Intuitivamente, isto soa como un O de n operación cadrado.

140
00:07:08,430 --> 00:07:12,050
Mirando para o noso pseudocódigo, tamén temos un loop aninhado

141
00:07:12,050 --> 00:07:14,420
outro ciclo, que en realidade soa como un O

142
00:07:14,420 --> 00:07:16,480
operación de n ao cadrado.

143
00:07:16,480 --> 00:07:19,250
Con todo, lembre que nós non precisamos de ollar sobre o

144
00:07:19,250 --> 00:07:23,460
completa para determinar o elemento mínimo indiferenciados?

145
00:07:23,460 --> 00:07:26,600
Unha vez que sabía que o 4 foi clasificada, por exemplo, non

146
00:07:26,600 --> 00:07:28,170
Debe ollar para el de novo.

147
00:07:28,170 --> 00:07:31,020
Así menor o tempo de execución?

148
00:07:31,020 --> 00:07:34,510
Para a nosa lista de lonxitude 6, é necesario facer cinco

149
00:07:34,510 --> 00:07:37,990
comparacións para o primeiro elemento, catro comparacións para

150
00:07:37,990 --> 00:07:40,750
o segundo elemento, e así por diante.

151
00:07:40,750 --> 00:07:44,690
Isto significa que o número total de pasos é igual á suma de

152
00:07:44,690 --> 00:07:49,160
os números enteiros de 1 ata a lonxitude da lista de menos 1.

153
00:07:49,160 --> 00:07:51,005
Podemos representar iso con un sumatorio.

154
00:07:57,980 --> 00:07:59,910
Non imos entrar en somatórios aquí.

155
00:07:59,910 --> 00:08:04,900
Pero acontece que esa suma é igual a n veces

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

157
00:08:07,540 --> 00:08:14,220
Ou equivalentemente, n ao cadrado máis 2 menos n máis de 2.

158
00:08:14,220 --> 00:08:18,860
Cando se fala en tempo de execución assintótico, este término n ao cadrado

159
00:08:18,860 --> 00:08:22,070
vai dominar este término n.

160
00:08:22,070 --> 00:08:27,850
Entón tipo de selección é o de n ao cadrado.

161
00:08:27,850 --> 00:08:31,460
Lembre que no noso exemplo, tipo de selección aínda precisaba

162
00:08:31,460 --> 00:08:33,850
comprobar se un número que xa foi clasificada

163
00:08:33,850 --> 00:08:35,450
necesaria para ser movido.

164
00:08:35,450 --> 00:08:38,929
Entón isto significa que, se correu tipo de selección sobre unha xa

165
00:08:38,929 --> 00:08:43,070
Lista clasificada, sería necesario o mesmo número de pasos, unha vez que

166
00:08:43,070 --> 00:08:46,340
faría ao atropelar unha lista completamente indiferenciado.

167
00:08:46,340 --> 00:08:51,470
Entón tipo de selección ten un rendemento mellor caso de n ao cadrado,

168
00:08:51,470 --> 00:08:56,820
que representamos con omega n ao cadrado.

169
00:08:56,820 --> 00:08:58,600
E é que polo tipo de selección.

170
00:08:58,600 --> 00:09:00,630
Só un dos moitos algoritmos que podemos

171
00:09:00,630 --> 00:09:02,390
usar para clasificar a lista.

172
00:09:02,390 --> 00:09:05,910
O meu nome é Tommy, e este é o CS50.