1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Ordenar Inserción]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvard University]

3
00:00:04,240 --> 00:00:07,290
[Esta es CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Vamos a echar un vistazo a la ordenación por inserción, un algoritmo para la toma de una lista de números y ordenarlos.

5
00:00:13,060 --> 00:00:18,300
Un algoritmo, recuerde, es simplemente un procedimiento paso a paso para realizar una tarea.

6
00:00:18,300 --> 00:00:23,640
La idea básica detrás de la ordenación por inserción, es dividir la lista en dos partes,

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

8
00:00:26,580 --> 00:00:29,290
>> En cada paso del algoritmo, un número se mueve

9
00:00:29,290 --> 00:00:32,439
desde la parte no seleccionada a la porción ordenados

10
00:00:32,439 --> 00:00:35,680
hasta que finalmente toda la lista está ordenada.

11
00:00:35,680 --> 00:00:43,340
Esta es la lista de seis números no clasificados - 23, 42, 4, 16, 8, y 15.

12
00:00:43,340 --> 00:00:47,680
Dado que estos números no son todo en orden ascendente, están sin ordenar.

13
00:00:47,680 --> 00:00:53,890
Puesto que no hemos empezado clasificación, sin embargo, vamos a considerar los seis elementos de nuestra parte sin clasificar.

14
00:00:53,890 --> 00:00:59,270
>> Una vez que comenzamos la clasificación, vamos a poner estos números ordenados a la izquierda de las mismas.

15
00:00:59,270 --> 00:01:03,600
Por lo tanto, vamos a empezar con 23, el primer elemento de la lista.

16
00:01:03,600 --> 00:01:06,930
No tenemos ningún elemento de nuestra parte ordenados, sin embargo,

17
00:01:06,930 --> 00:01:12,460
así que vamos a considerar sólo 23 al ser el inicio y el final de nuestra parte ordenada.

18
00:01:12,460 --> 00:01:16,510
Ahora, nuestra porción ordenada tiene un número, 23,

19
00:01:16,510 --> 00:01:20,260
y de nuestra parte no seleccionada tiene estos cinco números.

20
00:01:20,260 --> 00:01:27,320
Ahora vamos a insertar el siguiente número de nuestra parte sin clasificar, de 42 años, en la parte ordenada.

21
00:01:27,320 --> 00:01:35,930
>> Para ello, tendremos que comparar la 42 a la 23 - el único elemento en nuestra porción ordenados hasta ahora.

22
00:01:35,930 --> 00:01:41,980
Cuarenta y dos es mayor que 23, por lo que simplemente puede añadir 42 hasta el final

23
00:01:41,980 --> 00:01:45,420
de la parte ordenada de la lista. Great!

24
00:01:45,420 --> 00:01:51,850
Ahora nuestra parte según consta de dos elementos, y nuestra parte no seleccionada tiene cuatro elementos.

25
00:01:51,850 --> 00:01:57,200
Por lo tanto, vamos a pasar ahora a la 4, el siguiente elemento de la parte sin clasificar.

26
00:01:57,200 --> 00:02:00,230
Así, donde debe ser colocado en esta porción de la ordenados?

27
00:02:00,230 --> 00:02:04,220
>> Recuerde, queremos poner este número en forma ordenada

28
00:02:04,220 --> 00:02:08,680
por lo que nuestra porción ordenados permanece correctamente ordenados en todo momento.

29
00:02:08,680 --> 00:02:14,380
Si colocamos la 4 a la derecha de los 42, entonces nuestra lista estará fuera de orden.

30
00:02:14,380 --> 00:02:18,380
Por lo tanto, vamos a continuar moviéndose de derecha a izquierda en nuestra porción de clasificación.

31
00:02:18,380 --> 00:02:23,260
A medida que avanzamos, vamos a pasar por cada número un lugar para hacer espacio para el nuevo número.

32
00:02:25,440 --> 00:02:31,740
Vale, 4 también es inferior a 23, por lo que no se puede colocar aquí tampoco.

33
00:02:31,740 --> 00:02:34,480
Vamos a pasar el 23 a la derecha un solo lugar.

34
00:02:36,500 --> 00:02:43,120
>> Eso significa que nos gustaría poner el 4 en la primera ranura en la parte ordenada.

35
00:02:43,120 --> 00:02:46,300
Observe cómo este espacio en la lista ya estaba vacía,

36
00:02:46,300 --> 00:02:51,120
porque hemos estado moviendo elementos ordenados a medida que los hemos encontrado.

37
00:02:51,120 --> 00:02:52,740
Está bien. Por lo tanto, estamos a mitad de camino.

38
00:02:52,740 --> 00:02:57,990
Vamos a continuar nuestro algoritmo mediante la inserción de la 16 a la parte ordenada.

39
00:02:59,260 --> 00:03:03,820
Dieciséis es menos de 42, así que vamos a pasar el 42 a la derecha.

40
00:03:05,700 --> 00:03:10,190
Dieciséis es también menos de 23, así que vamos a cambiar también ese elemento.

41
00:03:11,790 --> 00:03:20,820
>> Ahora, 16 es mayor que 4. Por lo tanto, parece que nos gustaría insertar la 16 entre el 4 y 23 de la.

42
00:03:20,820 --> 00:03:24,620
Mientras se mueve a través de la porción de la lista ordenada de derecha a izquierda,

43
00:03:24,620 --> 00:03:29,160
4 es el primer número hemos visto que es menor que el número

44
00:03:29,160 --> 00:03:31,540
estamos tratando de insertar.

45
00:03:31,540 --> 00:03:35,820
Por lo tanto, ahora podemos insertar los 16 en esta ranura vacía,

46
00:03:35,820 --> 00:03:40,520
que, recordemos, hemos creado por elementos en movimiento en la parte de tipo más

47
00:03:40,520 --> 00:03:43,340
como los hemos encontrado.

48
00:03:43,340 --> 00:03:47,900
>> Está bien. Ahora, tenemos cuatro elementos ordenados y dos elementos no ordenados.

49
00:03:47,900 --> 00:03:51,600
Por lo tanto, vamos a pasar el 8 en la parte ordenada.

50
00:03:51,600 --> 00:03:55,010
Ocho es inferior a 42.

51
00:03:55,010 --> 00:03:56,940
Ocho es menos de 23.

52
00:03:56,940 --> 00:04:00,230
Y 8 es menor que 16.

53
00:04:00,230 --> 00:04:03,110
Pero 8 es mayor que 4.

54
00:04:03,110 --> 00:04:07,280
Por lo tanto, nos gustaría introducir el 8 entre el 4 y el 16.

55
00:04:09,070 --> 00:04:13,650
Y ahora sólo tenemos un elemento más a la izquierda para ordenar - el 15.

56
00:04:13,950 --> 00:04:16,589
Quince es inferior a 42,

57
00:04:16,589 --> 00:04:19,130
Quince es menos de 23.

58
00:04:19,130 --> 00:04:21,750
Y 15 es menor que 16.

59
00:04:21,750 --> 00:04:24,810
Pero 15 es mayor que 8.

60
00:04:24,810 --> 00:04:27,440
>> Así pues, aquí es donde queremos que nuestra inserción final.

61
00:04:28,770 --> 00:04:30,330
Y hemos terminado.

62
00:04:30,330 --> 00:04:33,540
No tenemos más elementos en la porción sin clasificar,

63
00:04:33,540 --> 00:04:36,670
y nuestra porción ordenados en el orden correcto.

64
00:04:36,670 --> 00:04:40,270
Los números están ordenados de menor a mayor.

65
00:04:40,270 --> 00:04:44,330
Por lo tanto, echemos un vistazo a algunos pseudocódigo que describe los pasos que acabamos de realizar.

66
00:04:46,760 --> 00:04:51,740
>> En la línea 1, podemos ver que vamos a necesitar para iterar sobre cada elemento de la lista

67
00:04:51,740 --> 00:04:57,060
excepto el primero, ya que el primer elemento en la parte no seleccionada se hará simplemente

68
00:04:57,060 --> 00:05:00,220
el primer elemento en la parte ordenados.

69
00:05:00,220 --> 00:05:06,320
En las líneas 2 y 3, estamos manteniendo un seguimiento de nuestra posición actual en la parte sin clasificar.

70
00:05:06,320 --> 00:05:10,450
Elemento representa el número que se está moviendo en la parte de clasificados,

71
00:05:10,450 --> 00:05:15,600
y j representa nuestro índice en la parte sin clasificar.

72
00:05:15,600 --> 00:05:20,980
>> En la línea 4, estamos iterando a través de la porción ordenados de derecha a izquierda.

73
00:05:20,980 --> 00:05:26,010
Queremos dejar de iterar una vez que el elemento a la izquierda de su posición actual

74
00:05:26,010 --> 00:05:30,050
es menor que el elemento que estamos tratando de insertar.

75
00:05:30,050 --> 00:05:35,600
En la línea 5, estamos cambiando cada elemento que encontramos un espacio a la derecha.

76
00:05:35,600 --> 00:05:40,950
De esta manera, vamos a tener un espacio libre para insertar en cuando nos encontramos con el primer elemento

77
00:05:40,950 --> 00:05:44,080
menor que el elemento que se está moviendo.

78
00:05:44,080 --> 00:05:50,800
En la línea 6, estamos actualizando nuestro contador a continuar moviéndose a la izquierda por la parte ordenada.

79
00:05:50,800 --> 00:05:56,860
Por último, en la línea 7, estamos insertar el elemento dentro de la parte de la lista ordenada.

80
00:05:56,860 --> 00:06:00,020
>> Sabemos que está bien para insertar en la posición j,

81
00:06:00,020 --> 00:06:05,360
porque ya hemos movido el elemento que solía estar allí un espacio a la derecha.

82
00:06:05,360 --> 00:06:09,460
Recuerde, nos estamos moviendo a través de la porción ordenados de derecha a izquierda,

83
00:06:09,460 --> 00:06:13,960
pero nos estamos moviendo a través de la parte no seleccionada de izquierda a derecha.

84
00:06:13,960 --> 00:06:19,090
Está bien. Echemos un vistazo a cómo de larga data que se algoritmo.

85
00:06:19,090 --> 00:06:25,300
En primer lugar, voy a hacer la pregunta ¿cuánto tiempo se necesita para que este algoritmo se ejecute en el peor de los casos.

86
00:06:25,300 --> 00:06:29,040
Recordemos que representamos esta vez corriendo con la notación grande O.

87
00:06:32,530 --> 00:06:38,500
Para ordenar la lista, tuvimos que iterar sobre los elementos de la parte sin clasificar,

88
00:06:38,500 --> 00:06:43,430
y para cada uno de esos elementos, potencialmente a través de todos los elementos en la porción ordenados.

89
00:06:43,430 --> 00:06:47,950
Intuitivamente, esto suena como una operación O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> En cuanto a nuestro pseudocódigo, tenemos un bucle anidado dentro de otro bucle,

91
00:06:51,840 --> 00:06:55,290
que, de hecho, suena como una operación O (n ^ 2).

92
00:06:55,290 --> 00:07:01,590
Sin embargo, la parte ordenada de lista no contenía toda la lista hasta el final.

93
00:07:01,590 --> 00:07:06,920
Aún así, podría insertar un nuevo elemento en el comienzo mismo de la porción ordenados

94
00:07:06,920 --> 00:07:09,320
en cada iteración del algoritmo,

95
00:07:09,320 --> 00:07:14,500
lo que significa que tendríamos que mirar cada elemento actualmente en la parte ordenada.

96
00:07:14,500 --> 00:07:20,090
Por lo tanto, esto significa que potencialmente podría hacer una comparación para el segundo elemento,

97
00:07:20,090 --> 00:07:24,660
dos comparaciones para el tercer elemento, y así sucesivamente.

98
00:07:24,660 --> 00:07:32,480
Así, el número total de pasos es la suma de los enteros de 1 a la longitud de la lista menos 1.

99
00:07:32,480 --> 00:07:35,240
Podemos representar esto con una suma.

100
00:07:41,170 --> 00:07:47,270
>> No vamos a entrar en sumas aquí, pero resulta que esta suma es igual a

101
00:07:47,270 --> 00:07:57,900
n (n - 1) sobre 2, que es equivalente n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Cuando se habla de tiempo de ejecución asintótico,

103
00:08:00,800 --> 00:08:05,170
este n ^ 2 plazo va a dominar este término n.

104
00:08:05,170 --> 00:08:11,430
Por lo tanto, la ordenación por inserción es Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
¿Qué pasa si nos quedamos ordenación por inserción en una lista ya ordenada.

106
00:08:16,150 --> 00:08:20,960
En ese caso, simplemente se había acumulación de la porción ordenados de izquierda a derecha.

107
00:08:20,960 --> 00:08:25,050
Así que lo único que necesita del orden de n pasos.

108
00:08:25,050 --> 00:08:29,740
>> Esto significa que la ordenación por inserción tiene un rendimiento mejor de los casos de n,

109
00:08:29,740 --> 00:08:34,130
que representamos con Ω (n).

110
00:08:34,130 --> 00:08:36,190
Y eso es todo por tipo de inserción,

111
00:08:36,190 --> 00:08:40,429
sólo uno de los muchos algoritmos que se pueden utilizar para ordenar una lista.

112
00:08:40,429 --> 00:08:43,210
Mi nombre es Tommy, y esto es CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, no puedes dejar que una vez que se inicie.

115
00:09:01,620 --> 00:09:04,760
Oh, lo hicimos - Boom! >>