1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Vamos dar uma olhada tipo de seleção, um algoritmo

2
00:00:09,980 --> 00:00:12,800
para a tomada de uma lista de números e classificando-os.

3
00:00:12,800 --> 00:00:15,750
Um algoritmo, lembre-se, é simplesmente um passo-a-passo

4
00:00:15,750 --> 00:00:18,370
procedimento para realizar uma tarefa.

5
00:00:18,370 --> 00:00:21,470
A idéia básica por trás do tipo de seleção é dividir

6
00:00:21,470 --> 00:00:23,390
nossa lista em duas partes -

7
00:00:23,390 --> 00:00:26,810
uma parte ordenada e uma porção indiferenciados.

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

9
00:00:30,200 --> 00:00:33,800
parte indiferenciados para a porção classificados até, eventualmente, o

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

11
00:00:35,880 --> 00:00:38,510
Então aqui está uma 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 sem classificação.

14
00:00:47,680 --> 00:00:51,770
Mesmo que um número como 16 já pode estar em sua correcta

15
00:00:51,770 --> 00:00:56,040
localização, nosso algoritmo tem nenhuma maneira de saber que até o

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

17
00:00:57,980 --> 00:01:01,355
Então, vamos considerar cada número a ser triados até classificar

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 em ordem crescente.

20
00:01:06,890 --> 00:01:10,200
Então, nós vamos querer construir a parte ordenada da nossa lista

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

22
00:01:13,280 --> 00:01:17,970
Para isso, vamos precisar de encontrar o elemento mínimo indiferenciados

23
00:01:17,970 --> 00:01:21,350
e colocá-lo no fim da porção classificada.

24
00:01:21,350 --> 00:01:25,370
Como esta lista não está ordenada, a única maneira de fazer isso é

25
00:01:25,370 --> 00:01:29,330
olhar para cada elemento na porção não separados, lembrando

26
00:01:29,330 --> 00:01:32,010
qual elemento é a mais baixa e comparando

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

28
00:01:33,770 --> 00:01:36,150
Então, vamos olhar primeiro para o 23.

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

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

31
00:01:40,050 --> 00:01:42,320
Em seguida, vamos olhar para 42.

32
00:01:42,320 --> 00:01:46,720
42 é maior do que 23, então 23 é ainda o mínimo.

33
00:01:46,720 --> 00:01:51,210
O próximo é o 4, que é inferior a 23, por isso vamos 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
Em seguida é 16, que é maior do que 4, então 4

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

37
00:01:57,980 --> 00:02:03,670
8 é maior do que 4, e 15 é maior do que 4, então 4 deve ser

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

39
00:02:05,980 --> 00:02:09,350
Assim, mesmo que, como seres humanos, podemos ver imediatamente que 4 é

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

41
00:02:12,300 --> 00:02:15,710
cada elemento indiferenciado, mesmo depois de ter encontrado a 4 - o

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

43
00:02:16,860 --> 00:02:19,900
Portanto, agora que nós encontramos o elemento mínimo, 4, vamos querer

44
00:02:19,900 --> 00:02:23,410
para movê-la para dentro da porção da lista ordenada.

45
00:02:23,410 --> 00:02:27,320
Uma vez que este é o primeiro passo, isso significa que queremos colocar em 4

46
00:02:27,320 --> 00:02:29,680
o início da lista.

47
00:02:29,680 --> 00:02:33,040
Nesse momento 23 é, no início da lista, de modo

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

49
00:02:36,080 --> 00:02:38,870
Então, agora a nossa lista parecida com esta.

50
00:02:38,870 --> 00:02:42,710
Sabemos que 4 tem de ser na sua posição final, uma vez que é

51
00:02:42,710 --> 00:02:45,890
tanto o elemento mais pequeno eo elemento no início

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

53
00:02:46,960 --> 00:02:50,650
Então isso significa que não precise mover novamente.

54
00:02:50,650 --> 00:02:53,910
Então, vamos repetir esse processo para adicionar mais um elemento para a

55
00:02:53,910 --> 00:02:55,910
parcela classificada da lista.

56
00:02:55,910 --> 00:02:58,950
Nós sabemos que não precisamos de olhar para o 4, porque é

57
00:02:58,950 --> 00:03:00,000
já estão classificados.

58
00:03:00,000 --> 00:03:03,540
Assim, podemos começar no 42, que vai se 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ão, da próxima vamos olhar para o 23, que é menor do que 42, então 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
Em seguida, vemos a 16 que é inferior a 23, de modo

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

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

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, de modo que sabemos que 8 é um mínimo

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

68
00:03:27,780 --> 00:03:30,660
Então isso significa que devemos acrescentar 8 ao ordenadas

69
00:03:30,660 --> 00:03:32,450
porção da lista.

70
00:03:32,450 --> 00:03:35,990
Agora 4 é o único elemento classificados, por isso queremos colocar

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

72
00:03:38,410 --> 00:03:41,920
Uma vez que 42 é o primeiro elemento na porção não separados do

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

74
00:03:47,260 --> 00:03:49,680
Então, agora a nossa lista parecida com esta.

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

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

77
00:03:56,440 --> 00:03:58,260
porção da lista.

78
00:03:58,260 --> 00:04:00,630
Então, vamos continuar com outro iteração.

79
00:04:00,630 --> 00:04:03,850
Começamos com 23 desta vez, já que não precisa de olhar para

80
00:04:03,850 --> 00:04:05,770
o 4 eo 8 mais, porque eles têm

81
00:04:05,770 --> 00:04:07,660
já foram classificados.

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

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

84
00:04:12,070 --> 00:04:18,149
16 é menor do que 42, mas 15 é menor do que 16, então deve 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ão, agora queremos trocar os 15 e os 23 a

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

88
00:04:26,310 --> 00:04:30,500
A porção da lista ordenada é constituída por 4, 8 e 15, e

89
00:04:30,500 --> 00:04:33,210
esses elementos estão ainda sem classificação.

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

91
00:04:36,900 --> 00:04:38,480
já está classificado.

92
00:04:38,480 --> 00:04:42,060
No entanto, não há nenhuma maneira para o nosso algoritmo para saber que 16

93
00:04:42,060 --> 00:04:45,230
já está em seu local correto, então ainda precisamos

94
00:04:45,230 --> 00:04:47,870
repetir exatamente o mesmo processo.

95
00:04:47,870 --> 00:04:53,750
Portanto, vemos que 16 é menos de 42, e 16 é menor que 23, então

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

97
00:04:56,230 --> 00:04:59,010
É impossível trocar esse elemento com ele mesmo, para que possamos

98
00:04:59,010 --> 00:05:01,780
simplesmente deixá-lo no local.

99
00:05:01,780 --> 00:05:04,660
Então precisamos de uma passagem mais do nosso algoritmo.

100
00:05:04,660 --> 00:05:09,370
42 é maior que 23, então 23 deve ser o

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

102
00:05:10,970 --> 00:05:17,410
Uma vez que trocar os 23 e os 42, vamos acabar com nossa final

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

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 deve estar no lugar correto, já que é o

106
00:05:26,830 --> 00:05:30,210
único elemento à esquerda, e que é uma espécie de seleção.

107
00:05:30,210 --> 00:05:32,100
Vamos agora formalizar o nosso algoritmo com algum

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

109
00:05:34,540 --> 00:05:37,760
Em uma linha, podemos ver que precisamos integrar mais

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, uma vez que o elemento 1

112
00:05:42,150 --> 00:05:44,230
lista já está classificado.

113
00:05:44,230 --> 00:05:48,100
Na linha dois, 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 fizemos com a nossa

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

116
00:05:53,750 --> 00:05:57,260
Linha de três começa uma segunda volta em 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, depois de iterações, a parte classificada

119
00:06:02,150 --> 00:06:05,330
da nossa lista deve ter i elementos nele desde cada passo

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

121
00:06:06,890 --> 00:06:11,770
Assim, o primeiro elemento unsorted deve estar na posição i + 1.

122
00:06:11,770 --> 00:06:15,440
Na linha de quatro, comparamos o elemento atual para o mínimo

123
00:06:15,440 --> 00:06:17,750
elemento que temos visto até agora.

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

125
00:06:20,560 --> 00:06:23,870
elemento, então lembre-se o elemento atual como o novo

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

127
00:06:26,250 --> 00:06:29,900
Finalmente, em linhas seis e sete, trocamos o mínimo

128
00:06:29,900 --> 00:06:33,080
elemento com o primeiro elemento não separados, assim

129
00:06:33,080 --> 00:06:36,990
adicionando-a a porção da lista ordenada.

130
00:06:36,990 --> 00:06:40,030
Uma vez que temos um algoritmo, uma importante causa de pedir

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

132
00:06:43,370 --> 00:06:46,970
Vamos primeiro fazer a pergunta quanto tempo leva para essa

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

134
00:06:50,070 --> 00:06:51,640
Lembro que representam esta corrida

135
00:06:51,640 --> 00:06:55,060
tempo com notação O grande.

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

137
00:06:58,650 --> 00:07:01,880
tinha essencialmente 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, isso soa como um O de n operação quadrado.

140
00:07:08,430 --> 00:07:12,050
Olhando para o nosso pseudocódigo, também temos um loop aninhado

141
00:07:12,050 --> 00:07:14,420
outro ciclo, que na verdade soa como um O

142
00:07:14,420 --> 00:07:16,480
operação de n ao quadrado.

143
00:07:16,480 --> 00:07:19,250
No entanto, lembre-se que nós não precisamos de olhar sobre o

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

145
00:07:23,460 --> 00:07:26,600
Uma vez que sabia que o 4 foi classificada, por exemplo, nós não

146
00:07:26,600 --> 00:07:28,170
precisa olhar para ele de novo.

147
00:07:28,170 --> 00:07:31,020
Então isso menor o tempo de execução?

148
00:07:31,020 --> 00:07:34,510
Para a nossa lista de comprimento 6, é necessário fazer cinco

149
00:07:34,510 --> 00:07:37,990
comparações para o primeiro elemento, quatro comparações para

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

151
00:07:40,750 --> 00:07:44,690
Isso significa que o número total de passos é igual à soma de

152
00:07:44,690 --> 00:07:49,160
os números inteiros de 1 até o comprimento da lista de menos 1.

153
00:07:49,160 --> 00:07:51,005
Podemos representar isso com um somatório.

154
00:07:57,980 --> 00:07:59,910
Nós não vamos entrar em somatórios aqui.

155
00:07:59,910 --> 00:08:04,900
Mas acontece que essa soma é igual a n vezes

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 quadrado mais 2 menos n mais de 2.

158
00:08:14,220 --> 00:08:18,860
Quando se fala em tempo de execução assintótico, este termo n ao quadrado

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

160
00:08:22,070 --> 00:08:27,850
Então tipo de seleção é O de n ao quadrado.

161
00:08:27,850 --> 00:08:31,460
Lembre-se que no nosso exemplo, tipo de seleção ainda precisava

162
00:08:31,460 --> 00:08:33,850
verificar se um número que já foi classificada

163
00:08:33,850 --> 00:08:35,450
necessária para ser movido.

164
00:08:35,450 --> 00:08:38,929
Então isso significa que, se correu tipo de seleção sobre uma já

165
00:08:38,929 --> 00:08:43,070
lista classificada, seria necessário o mesmo número de passos, uma vez que

166
00:08:43,070 --> 00:08:46,340
faria ao atropelar uma lista completamente indiferenciado.

167
00:08:46,340 --> 00:08:51,470
Então tipo de seleção tem um desempenho melhor caso de n ao quadrado,

168
00:08:51,470 --> 00:08:56,820
que representamos com ômega n ao quadrado.

169
00:08:56,820 --> 00:08:58,600
E é isso por tipo de seleção.

170
00:08:58,600 --> 00:09:00,630
Apenas um dos muitos algoritmos que podemos

171
00:09:00,630 --> 00:09:02,390
usar para classificar uma lista.

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