1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Vamos a echar un vistazo a la ordenación por selección, un algoritmo

2
00:00:09,980 --> 00:00:12,800
para la toma de una lista de números y clasificarlas.

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

4
00:00:15,750 --> 00:00:18,370
procedimiento para llevar a cabo una tarea.

5
00:00:18,370 --> 00:00:21,470
La idea básica detrás de la ordenación por selección es dividir

6
00:00:21,470 --> 00:00:23,390
la lista en dos partes -

7
00:00:23,390 --> 00:00:26,810
una porción ordenados y una porción sin clasificar.

8
00:00:26,810 --> 00:00:30,200
En cada paso del algoritmo, un número se mueve desde la

9
00:00:30,200 --> 00:00:33,800
unsorted porción a la porción ordenados hasta que finalmente la

10
00:00:33,800 --> 00:00:35,880
toda la lista está ordenada.

11
00:00:35,880 --> 00:00:38,510
Así que aquí está una lista de seis números -

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

13
00:00:44,010 --> 00:00:47,680
En este momento toda la lista se considera sin ordenar.

14
00:00:47,680 --> 00:00:51,770
A pesar de que un número como 16 puede estar ya en su correcta

15
00:00:51,770 --> 00:00:56,040
ubicación, nuestro algoritmo no tiene manera de saber que hasta que el

16
00:00:56,040 --> 00:00:57,980
toda la lista está ordenada.

17
00:00:57,980 --> 00:01:01,355
Así que vamos a considerar cada número que se unsorted hasta que ordenar

18
00:01:01,355 --> 00:01:03,800
nosotros mismos.

19
00:01:03,800 --> 00:01:06,890
Sabemos que queremos que la lista sea en orden ascendente.

20
00:01:06,890 --> 00:01:10,200
Así que vamos a querer construir la porción ordenada de nuestra lista

21
00:01:10,200 --> 00:01:13,280
de izquierda a derecha, el más pequeño al más grande.

22
00:01:13,280 --> 00:01:17,970
Para hacerlo, tendremos que encontrar el elemento mínimo sin clasificar

23
00:01:17,970 --> 00:01:21,350
y lo sitúan en el extremo de la parte ordenados.

24
00:01:21,350 --> 00:01:25,370
Dado que esta lista no está ordenada, la única manera de hacerlo es

25
00:01:25,370 --> 00:01:29,330
ver todos los elementos de la parte sin clasificar, recordando

26
00:01:29,330 --> 00:01:32,010
qué elemento es el más bajo y comparando

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

28
00:01:33,770 --> 00:01:36,150
Así que lo primero que veremos el 23.

29
00:01:36,150 --> 00:01:38,650
Este es el primer elemento que hemos visto, así que voy a recordar

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

31
00:01:40,050 --> 00:01:42,320
A continuación vamos a ver 42.

32
00:01:42,320 --> 00:01:46,720
42 es mayor que 23, por lo que 23 sigue siendo el mínimo.

33
00:01:46,720 --> 00:01:51,210
El siguiente es el 4, que está a menos de 23, así que vamos a recordar 4

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

35
00:01:52,880 --> 00:01:56,380
Siguiente es 16, que es mayor que 4, de modo 4

36
00:01:56,380 --> 00:01:57,980
todavía es el mínimo.

37
00:01:57,980 --> 00:02:03,670
8 es mayor que 4, y 15 es mayor que 4, por lo que debe ser 4

38
00:02:03,670 --> 00:02:05,980
el elemento más pequeño sin clasificar.

39
00:02:05,980 --> 00:02:09,350
Así que a pesar de que como seres humanos podemos ver inmediatamente que el 4 es

40
00:02:09,350 --> 00:02:12,300
el elemento mínimo, nuestro algoritmo tiene que ver

41
00:02:12,300 --> 00:02:15,710
cada elemento sin clasificar, incluso después de que hayas encontrado el 4 - el

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

43
00:02:16,860 --> 00:02:19,900
Así que ahora que hemos encontrado el elemento mínimo, 4, vamos a querer

44
00:02:19,900 --> 00:02:23,410
para moverlo a la parte de la lista ordenada.

45
00:02:23,410 --> 00:02:27,320
Dado que este es el primer paso, esto significa que queremos poner 4 en

46
00:02:27,320 --> 00:02:29,680
el principio de la lista.

47
00:02:29,680 --> 00:02:33,040
En este momento 23 se encuentra al principio de la lista, por lo

48
00:02:33,040 --> 00:02:36,080
vamos a cambiar el 4 y 23 de la.

49
00:02:36,080 --> 00:02:38,870
Así que ahora la lista se parece a esto.

50
00:02:38,870 --> 00:02:42,710
Sabemos que 4 debe estar en su ubicación final, porque es

51
00:02:42,710 --> 00:02:45,890
tanto el elemento más pequeño y el elemento al principio

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

53
00:02:46,960 --> 00:02:50,650
Así que esto significa que no siempre tenga que moverse de nuevo.

54
00:02:50,650 --> 00:02:53,910
Así que vamos a repetir este proceso para agregar un elemento más a la

55
00:02:53,910 --> 00:02:55,910
ordenados parte de la lista.

56
00:02:55,910 --> 00:02:58,950
Sabemos que no tenemos que mirar a la 4, porque es

57
00:02:58,950 --> 00:03:00,000
ya ordenados.

58
00:03:00,000 --> 00:03:03,540
Así que podemos empezar en el 42, que vamos a recordar como el

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

60
00:03:05,290 --> 00:03:08,700
Así que la próxima veremos el 23, que es inferior a 42, por lo que

61
00:03:08,700 --> 00:03:11,620
Recuerdo 23 es el nuevo mínimo.

62
00:03:11,620 --> 00:03:14,870
A continuación vemos el 16 que es menor que 23, por lo

63
00:03:14,870 --> 00:03:16,800
16 es el nuevo mínimo.

64
00:03:16,800 --> 00:03:19,720
Ahora nos fijamos en el 8, que es menos de 16, por lo

65
00:03:19,720 --> 00:03:21,130
8 es el nuevo mínimo.

66
00:03:21,130 --> 00:03:25,900
Y finalmente 8 es menor que 15, por lo que sabemos que 8 es un mínimo

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

68
00:03:27,780 --> 00:03:30,660
Así que eso significa que deberíamos añadir 8 al ordenar

69
00:03:30,660 --> 00:03:32,450
parte de la lista.

70
00:03:32,450 --> 00:03:35,990
En este momento 4 es el único elemento clasificado, por lo que queremos colocar

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

72
00:03:38,410 --> 00:03:41,920
Dado que 42 es el primer elemento en la parte no seleccionada de la

73
00:03:41,920 --> 00:03:47,260
lista, vamos a querer cambiar el 42 y el 8.

74
00:03:47,260 --> 00:03:49,680
Así que ahora la lista se parece a esto.

75
00:03:49,680 --> 00:03:53,830
4 y 8 representan la parte ordenada de la lista, y el

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

77
00:03:56,440 --> 00:03:58,260
parte de la lista.

78
00:03:58,260 --> 00:04:00,630
Así que vamos a continuar con otra iteración.

79
00:04:00,630 --> 00:04:03,850
Empezamos con 23 esta vez, ya que no es necesario buscar en

80
00:04:03,850 --> 00:04:05,770
el 4 y el 8 ya porque no tienen

81
00:04:05,770 --> 00:04:07,660
ya se ha solucionado.

82
00:04:07,660 --> 00:04:10,270
16 es menor que 23, por lo que va a recordar

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

84
00:04:12,070 --> 00:04:18,149
16 es menor que 42, pero 15 es menor que 16, por lo que debe ser 15

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

86
00:04:20,480 --> 00:04:24,580
Así que ahora queremos intercambiar el 15 y el 23 de

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

88
00:04:26,310 --> 00:04:30,500
La parte ordenada de la lista se compone de 4, 8 y 15, y

89
00:04:30,500 --> 00:04:33,210
estos elementos están aún sin clasificar.

90
00:04:33,210 --> 00:04:36,900
Pero da la casualidad de que el siguiente elemento sin clasificar, 16,

91
00:04:36,900 --> 00:04:38,480
ya está ordenado.

92
00:04:38,480 --> 00:04:42,060
Sin embargo, no hay manera de que nuestro algoritmo para saber que el 16 por

93
00:04:42,060 --> 00:04:45,230
ya se encuentra en su ubicación correcta, por lo que todavía tenemos que

94
00:04:45,230 --> 00:04:47,870
repetir exactamente el mismo proceso.

95
00:04:47,870 --> 00:04:53,750
Así vemos que 16 es menor que 42, y 16 es menor que 23, por lo

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

97
00:04:56,230 --> 00:04:59,010
Es imposible cambiar este elemento consigo mismo, para que podamos

98
00:04:59,010 --> 00:05:01,780
simplemente deje en este lugar.

99
00:05:01,780 --> 00:05:04,660
Así que tenemos que pasar uno más de nuestro algoritmo.

100
00:05:04,660 --> 00:05:09,370
42 es mayor que 23, por lo que debe ser el 23

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

102
00:05:10,970 --> 00:05:17,410
Una vez que cambie el 23 y 42 de la, acabamos con nuestro último

103
00:05:17,410 --> 00:05:18,530
lista 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
Sabemos 42 debe estar en el lugar correcto, ya que es la

106
00:05:26,830 --> 00:05:30,210
único elemento a la izquierda, y que es una especie de selección.

107
00:05:30,210 --> 00:05:32,100
Ahora vamos a formalizar nuestro algoritmo con algunos

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

109
00:05:34,540 --> 00:05:37,760
En la línea uno, podemos ver que necesitamos para integrar más

110
00:05:37,760 --> 00:05:39,530
cada elemento de la lista.

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

112
00:05:42,150 --> 00:05:44,230
lista ya está ordenada.

113
00:05:44,230 --> 00:05:48,100
En la segunda línea, consideramos que el primer elemento de la unsorted

114
00:05:48,100 --> 00:05:51,080
parte de la lista para ser el mínimo, como lo hicimos con nuestra

115
00:05:51,080 --> 00:05:53,750
ejemplo, así que tenemos algo para comparar.

116
00:05:53,750 --> 00:05:57,260
La línea tres se inicia un segundo bucle en el que iterar sobre

117
00:05:57,260 --> 00:05:59,170
cada elemento sin clasificar.

118
00:05:59,170 --> 00:06:02,150
Sabemos que después de i iteraciones, la porción ordenados

119
00:06:02,150 --> 00:06:05,330
de la lista debe tener i elementos en ella, ya que cada paso

120
00:06:05,330 --> 00:06:06,890
clase un elemento.

121
00:06:06,890 --> 00:06:11,770
De modo que el elemento no seleccionados debe estar en la posición i + 1.

122
00:06:11,770 --> 00:06:15,440
En la línea cuatro, se compara el elemento actual al mínimo

123
00:06:15,440 --> 00:06:17,750
elemento que hemos visto hasta ahora.

124
00:06:17,750 --> 00:06:20,560
Si el elemento actual es menor que el mínimo

125
00:06:20,560 --> 00:06:23,870
elemento, entonces recordamos el elemento actual como la nueva

126
00:06:23,870 --> 00:06:26,250
mínimo en la línea cinco.

127
00:06:26,250 --> 00:06:29,900
Por último, en las líneas seis y siete, cambiamos el mínimo

128
00:06:29,900 --> 00:06:33,080
elemento con el elemento sin clasificar primero, de tal modo

129
00:06:33,080 --> 00:06:36,990
añadir a la porción de la lista ordenada.

130
00:06:36,990 --> 00:06:40,030
Una vez que tenemos un algoritmo, una pregunta importante

131
00:06:40,030 --> 00:06:43,370
nosotros como programadores se cuanto tiempo me llevará?

132
00:06:43,370 --> 00:06:46,970
En primer lugar, voy a hacer la pregunta ¿cuánto tiempo se necesita para que esta

133
00:06:46,970 --> 00:06:50,070
algoritmo para ejecutarse en el peor de los casos?

134
00:06:50,070 --> 00:06:51,640
Recordemos que representamos esta carrera

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

136
00:06:55,060 --> 00:06:58,650
Con el fin de determinar el elemento unsorted mínimo, se

137
00:06:58,650 --> 00:07:01,880
esencialmente tenían que comparar cada elemento de la lista para

138
00:07:01,880 --> 00:07:04,040
cada otro elemento en la lista.

139
00:07:04,040 --> 00:07:08,430
Intuitivamente, esto suena como una junta de operación n al cuadrado.

140
00:07:08,430 --> 00:07:12,050
En cuanto a nuestro pseudocódigo, también tenemos un bucle anidado dentro

141
00:07:12,050 --> 00:07:14,420
otro bucle, que en realidad suena como una junta

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

143
00:07:16,480 --> 00:07:19,250
Sin embargo, recuerde que no había necesidad de mirar por encima de la

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

145
00:07:23,460 --> 00:07:26,600
Una vez que supimos que el 4 se clasifican, por ejemplo, no nos

146
00:07:26,600 --> 00:07:28,170
necesitamos ver de nuevo.

147
00:07:28,170 --> 00:07:31,020
Lo mismo ocurre con este menor es el tiempo de ejecución?

148
00:07:31,020 --> 00:07:34,510
Para nuestra lista de longitud 6, teníamos que hacer cinco

149
00:07:34,510 --> 00:07:37,990
comparaciones para el primer elemento, cuatro comparaciones para

150
00:07:37,990 --> 00:07:40,750
el segundo elemento, y así sucesivamente.

151
00:07:40,750 --> 00:07:44,690
Eso significa que el número total de pasos es la suma de los

152
00:07:44,690 --> 00:07:49,160
los números enteros de 1 a la longitud de la lista menos 1.

153
00:07:49,160 --> 00:07:51,005
Podemos representar esto con una suma.

154
00:07:57,980 --> 00:07:59,910
No vamos a entrar en sumas aquí.

155
00:07:59,910 --> 00:08:04,900
Pero resulta que esta suma es 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
O de forma equivalente, n al cuadrado sobre 2 menos n sobre 2.

158
00:08:14,220 --> 00:08:18,860
Cuando se habla de tiempo de ejecución asintótico, este término al cuadrado n

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

160
00:08:22,070 --> 00:08:27,850
Así tipo de selección es O de n al cuadrado.

161
00:08:27,850 --> 00:08:31,460
Recordemos que en nuestro ejemplo, clasificar selección sigue siendo necesario para

162
00:08:31,460 --> 00:08:33,850
comprobar si un número que ya se solucionó

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

164
00:08:35,450 --> 00:08:38,929
Así que eso significa que si nos encontramos con una especie de selección sobre ya

165
00:08:38,929 --> 00:08:43,070
lista ordenada, se requeriría el mismo número de pasos como se

166
00:08:43,070 --> 00:08:46,340
lo haría cuando se ejecuta sobre una lista completamente sin clasificar.

167
00:08:46,340 --> 00:08:51,470
Así que tipo de selección tiene un desempeño mejor de los casos cuadrado de n,

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

169
00:08:56,820 --> 00:08:58,600
Y eso es todo por tipo de selección.

170
00:08:58,600 --> 00:09:00,630
Sólo uno de los muchos algoritmos que podamos

171
00:09:00,630 --> 00:09:02,390
utilizar para ordenar una lista.

172
00:09:02,390 --> 00:09:05,910
Mi nombre es Tommy, y esto es CS50.