1
00:00:00,000 --> 00:00:02,826
>> [REPRODUCCIÓN DE MÚSICA]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Así ordenación por inserción es otro
algoritmo que puede utilizar para ordenar una matriz.

4
00:00:09,370 --> 00:00:12,350
La idea detrás de este algoritmo
es la construcción de su matriz ordenada

5
00:00:12,350 --> 00:00:19,670
en su lugar, los elementos de desplazamiento de
el camino a medida que avanza, para hacer espacio.

6
00:00:19,670 --> 00:00:22,240
Esto es ligeramente diferente
desde la selección del tipo o de la burbuja

7
00:00:22,240 --> 00:00:25,460
Ordena, por ejemplo, donde
estamos ajustando los lugares,

8
00:00:25,460 --> 00:00:26,910
donde estamos haciendo swaps.

9
00:00:26,910 --> 00:00:29,760
>> En este caso lo que somos en realidad
haciendo es elementos deslizantes

10
00:00:29,760 --> 00:00:31,390
otra vez, fuera del camino.

11
00:00:31,390 --> 00:00:34,030
¿Cómo funciona este algoritmo
trabajar en pseudocódigo?

12
00:00:34,030 --> 00:00:37,646
Bueno vamos a decir simplemente que la forma arbitraria
primer elemento de la matriz se ordena.

13
00:00:37,646 --> 00:00:38,770
Estamos construyendo en su lugar.

14
00:00:38,770 --> 00:00:42,660
>> Vamos a ir un elemento a la vez y
construirlo, por lo que la primera cosa que vemos

15
00:00:42,660 --> 00:00:43,890
es una matriz de un elemento.

16
00:00:43,890 --> 00:00:47,720
Y, por definición, una
elemento de la matriz se ordena.

17
00:00:47,720 --> 00:00:50,850
>> Entonces vamos a repetir este proceso until--
vamos a repetir el siguiente proceso

18
00:00:50,850 --> 00:00:52,900
hasta que todos los elementos son ordenados.

19
00:00:52,900 --> 00:00:57,770
Mira el siguiente elemento no seleccionados y
insertarlo en la parte ordenada,

20
00:00:57,770 --> 00:01:01,209
desplazando el número requerido
de elementos fuera del camino.

21
00:01:01,209 --> 00:01:03,750
Esperemos que esta visualización
le ayudará a ver exactamente lo que está

22
00:01:03,750 --> 00:01:05,980
pasando con la ordenación por inserción.

23
00:01:05,980 --> 00:01:08,010
>> Así que de nuevo, aquí está nuestra
toda variedad sin clasificar,

24
00:01:08,010 --> 00:01:10,970
todos los elementos indicados en rojo.

25
00:01:10,970 --> 00:01:13,320
Y vamos a seguir la
pasos de nuestra pseudocódigo.

26
00:01:13,320 --> 00:01:16,970
La primera cosa que hacemos, se nos llama a la
primer elemento de la matriz, ordenados.

27
00:01:16,970 --> 00:01:20,920
Así que sólo vamos a decir
cinco, ahora eres ordenados.

28
00:01:20,920 --> 00:01:24,570
>> Entonces nos fijamos en la siguiente
elemento sin clasificar de la matriz

29
00:01:24,570 --> 00:01:27,610
y queremos insertar ese
en la porción ordenados,

30
00:01:27,610 --> 00:01:29,750
por elementos de desplazamiento sobre.

31
00:01:29,750 --> 00:01:33,470
Así que dos es la siguiente sin clasificar
elemento de la matriz.

32
00:01:33,470 --> 00:01:36,250
Es evidente que pertenece antes de la
cinco, así que lo que vamos a hacer

33
00:01:36,250 --> 00:01:41,580
es una especie de sostener de dos de lado por un segundo,
cambiar de cinco más, y después inserte de dos

34
00:01:41,580 --> 00:01:43,210
antes de las cinco, dónde debe ir.

35
00:01:43,210 --> 00:01:45,280
Y ahora podemos decir que dos se ordena.

36
00:01:45,280 --> 00:01:48,400
>> Así como usted puede ver, sólo hemos hasta ahora
mirado dos elementos de la matriz.

37
00:01:48,400 --> 00:01:50,600
No hemos mirado el
descansamos en absoluto, sino que hemos

38
00:01:50,600 --> 00:01:54,582
consiguieron esos dos elementos ordenados por
camino del mecanismo de cambio.

39
00:01:54,582 --> 00:01:56,410
>> Así que repetimos el proceso de nuevo.

40
00:01:56,410 --> 00:01:58,850
Mira la siguiente sin clasificar
elemento, que es uno.

41
00:01:58,850 --> 00:02:04,010
Vamos a celebrar eso a un lado por un segundo,
cambiar todo lo más, y poner uno

42
00:02:04,010 --> 00:02:05,570
donde debe ir.

43
00:02:05,570 --> 00:02:08,110
>> Una vez más, aún así, sólo he
miró a uno, dos y cinco.

44
00:02:08,110 --> 00:02:12,480
No sabemos qué más está por venir,
pero hemos solucionaron esos tres elementos.

45
00:02:12,480 --> 00:02:16,030
>> Elemento sin clasificar siguiente es
tres, por lo que vamos a establecer a un lado.

46
00:02:16,030 --> 00:02:18,200
Nos desplazamos sobre lo que
necesitará que, esta vez

47
00:02:18,200 --> 00:02:21,820
no lo es todo como en el anterior
dos casos, es sólo el cinco.

48
00:02:21,820 --> 00:02:25,440
Y entonces nos mantendremos tres en,
entre los dos y los cinco.

49
00:02:25,440 --> 00:02:27,849
>> Seis es el siguiente sin clasificar
elemento a la matriz.

50
00:02:27,849 --> 00:02:31,140
Y de hecho seis es superior a cinco, por lo
que ni siquiera necesitamos hacer ningún intercambio.

51
00:02:31,140 --> 00:02:35,710
Sólo podemos virar y seis a la derecha en
el extremo de la porción ordenados.

52
00:02:35,710 --> 00:02:38,270
>> Por último, cuatro es el
último elemento sin clasificar.

53
00:02:38,270 --> 00:02:42,060
Así que vamos a establecer un lado, cambiamos más
los elementos que tienen que cambiar a lo largo,

54
00:02:42,060 --> 00:02:43,780
y luego poner las cuatro que le corresponde.

55
00:02:43,780 --> 00:02:46,400
Y ahora mira, tenemos una especie
de todos los elementos.

56
00:02:46,400 --> 00:02:48,150
Aviso de la inserción
especie, no teníamos

57
00:02:48,150 --> 00:02:50,240
para ir y venir a través de la matriz.

58
00:02:50,240 --> 00:02:54,720
Nosotros sólo fuimos a través de la matriz
una sola vez, y nos cambió las cosas

59
00:02:54,720 --> 00:02:59,870
que ya habíamos encontrado, con el fin
para dar cabida a los nuevos elementos.

60
00:02:59,870 --> 00:03:02,820
>> ¿Cuál es el peor de los casos
escenario con la ordenación por inserción?

61
00:03:02,820 --> 00:03:05,090
En el peor de los casos, la
array es en orden inverso.

62
00:03:05,090 --> 00:03:11,180
Usted tiene que cambiar cada uno de los n elementos
hasta n posiciones, todos tenemos una sola vez

63
00:03:11,180 --> 00:03:12,880
hacer una inserción.

64
00:03:12,880 --> 00:03:15,720
Eso es un montón de cambiar.

65
00:03:15,720 --> 00:03:18,014
>> En el mejor de los casos, la
matriz está perfectamente ordenadas.

66
00:03:18,014 --> 00:03:20,680
Y algo así como lo que pasó
con cinco y seis en el ejemplo,

67
00:03:20,680 --> 00:03:23,779
en el que sólo podíamos virar en
sin tener que hacer ningún cambio,

68
00:03:23,779 --> 00:03:24,820
que esencialmente haríamos eso.

69
00:03:24,820 --> 00:03:27,560
>> Si usted se imagina que nuestro
matriz fue del uno al seis,

70
00:03:27,560 --> 00:03:29,900
nos gustaría empezar por
declarando un solo está ordenada.

71
00:03:29,900 --> 00:03:33,300
Dos viene después de que uno por lo que puede simplemente
dicen, OK, bueno uno y dos son ordenados.

72
00:03:33,300 --> 00:03:36,190
Tres viene después de dos, así, está bien,
uno y dos y tres están ordenados.

73
00:03:36,190 --> 00:03:39,590
>> No estamos haciendo ningún swaps, estamos
sólo mover esta línea arbitraria

74
00:03:39,590 --> 00:03:42,460
entre clasificados y no clasificados a medida que avanzamos.

75
00:03:42,460 --> 00:03:46,646
Como efectivamente como lo hicimos en el ejemplo,
convertir elementos azul, a medida que avancemos.

76
00:03:46,646 --> 00:03:48,270
Entonces, ¿qué es lo peor de ejecución caso, entonces?

77
00:03:48,270 --> 00:03:51,854
Recuerde, si tenemos que cambiar cada uno de
los n elementos posiblemente n posiciones,

78
00:03:51,854 --> 00:03:54,020
espero que te da
una idea de que el peor de los casos

79
00:03:54,020 --> 00:03:57,770
tiempo de ejecución es O grande de n al cuadrado.

80
00:03:57,770 --> 00:04:00,220
>> Si la matriz es perfectamente
ordenado, todo lo que tenemos que hacer

81
00:04:00,220 --> 00:04:04,480
es mirar a cada elemento
una vez, y luego hemos terminado.

82
00:04:04,480 --> 00:04:08,440
Así que en el mejor de los casos, es el omega de n.

83
00:04:08,440 --> 00:04:09,490
>> Soy Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Esto es CS50.

85
00:04:11,760 --> 00:04:13,119