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 é CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Imos dar un ollo ao tipo de inserción, un algoritmo para a toma de unha lista de números e clasificándose os.

5
00:00:13,060 --> 00:00:18,300
Un algoritmo, lembre, é simplemente un procedemento paso a paso para a realización dunha tarefa.

6
00:00:18,300 --> 00:00:23,640
A idea básica por tras do tipo de inserción, é dividir nosa lista en dúas partes,

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

8
00:00:26,580 --> 00:00:29,290
>> En cada etapa do algoritmo, un número é movido

9
00:00:29,290 --> 00:00:32,439
a partir da porción non triados para a porción clasificada

10
00:00:32,439 --> 00:00:35,680
ata que finalmente a listaxe e ordenada.

11
00:00:35,680 --> 00:00:43,340
Aquí está a lista de seis números indiferenciados - 23, 42, 4, 16, 8 e 15.

12
00:00:43,340 --> 00:00:47,680
Unha vez que estes números non son todo en orde ascendente, están sen clasificación.

13
00:00:47,680 --> 00:00:53,890
Dende que non comezou aínda a clasificación, imos considerar os seis elementos a nosa parte indiferenciados.

14
00:00:53,890 --> 00:00:59,270
>> Así que comezar a clasificación, imos poñer estes números clasificados para a esquerda destes.

15
00:00:59,270 --> 00:01:03,600
Entón, imos comezar con 23, o primeiro elemento na nosa lista.

16
00:01:03,600 --> 00:01:06,930
Nós non temos todos os elementos da nosa parte clasificada aínda,

17
00:01:06,930 --> 00:01:12,460
entón imos simplemente considerar 23 sexa o inicio eo fin da nosa parte clasificados.

18
00:01:12,460 --> 00:01:16,510
Agora, a nosa parte ordenada ten un número, 23,

19
00:01:16,510 --> 00:01:20,260
ea nosa porción indiferenciados ten eses cinco números.

20
00:01:20,260 --> 00:01:27,320
Imos agora introducir o seguinte número na nosa porción indiferenciados, 42, na porción clasificados.

21
00:01:27,320 --> 00:01:35,930
>> Para iso, imos ter que comparar a 42 para o 23 - o único elemento na nosa parcela clasificada ata agora.

22
00:01:35,930 --> 00:01:41,980
Corenta e dous é maior que 23, entón podemos simplemente engadir 42 ata o final

23
00:01:41,980 --> 00:01:45,420
da porción da lista ordenada. Gran!

24
00:01:45,420 --> 00:01:51,850
Agora a nosa parte ordenada posúe dous elementos, ea nosa porción indiferenciados ten catro elementos.

25
00:01:51,850 --> 00:01:57,200
Entón, imos agora pasar a 4, o elemento seguinte na parte indiferenciados.

26
00:01:57,200 --> 00:02:00,230
Así, onde debe estar ser colocada na parte clasificada?

27
00:02:00,230 --> 00:02:04,220
>> Lembre, queremos poñer este número na orde de clasificación

28
00:02:04,220 --> 00:02:08,680
por iso a nosa parte permanece clasificada correctamente clasificados en todos os momentos.

29
00:02:08,680 --> 00:02:14,380
Se colocarmos a 4 a dereita dos 42, entón a nosa lista vai ser fóra de orde.

30
00:02:14,380 --> 00:02:18,380
Entón, imos continuar a moverse de dereita a esquerda na nosa porción tipo.

31
00:02:18,380 --> 00:02:23,260
A medida que avanzamos, imos cambiar cada número baixo de un lugar para dar espazo para o novo número.

32
00:02:25,440 --> 00:02:31,740
Ok, 4 tamén é menor que 23, por tanto, non podemos colocar-lo aquí tamén.

33
00:02:31,740 --> 00:02:34,480
Imos pasar a 23 nun lugar seguro.

34
00:02:36,500 --> 00:02:43,120
>> Isto significa que nós queremos poñer o 4 no primeiro burato na parte de clasificados.

35
00:02:43,120 --> 00:02:46,300
Observe como ese espazo na lista xa estaba baleiro,

36
00:02:46,300 --> 00:02:51,120
porque estamos movendo elementos clasificados para abaixo como atopamos eles.

37
00:02:51,120 --> 00:02:52,740
Todo ben. Entón, nós estamos no medio do camiño.

38
00:02:52,740 --> 00:02:57,990
Imos continuar o noso algoritmo, inserindo a 16 na porción clasificados.

39
00:02:59,260 --> 00:03:03,820
Dezaseis é menor que 42, entón imos cambiar o 42 para a dereita.

40
00:03:05,700 --> 00:03:10,190
Dezaseis tamén é menor que 23, entón imos tamén cambiar ese elemento.

41
00:03:11,790 --> 00:03:20,820
>> Agora, 16 é maior que 4. Entón, parece que quere inserir a 16 entre o 4 eo 23.

42
00:03:20,820 --> 00:03:24,620
Mentres se move a través da parte clasificada na lista da dereita para a esquerda,

43
00:03:24,620 --> 00:03:29,160
4 é o primeiro número que vimos que é menor que o número

44
00:03:29,160 --> 00:03:31,540
estamos intentando introducir.

45
00:03:31,540 --> 00:03:35,820
Entón, agora podemos inserir o 16 neste slot baleiro,

46
00:03:35,820 --> 00:03:40,520
que, lembre, creamos por elementos móbiles na parte de tipo máis

47
00:03:40,520 --> 00:03:43,340
como atopamos eles.

48
00:03:43,340 --> 00:03:47,900
>> Todo ben. Agora, temos catro elementos clasificados e dous elementos non ordenados.

49
00:03:47,900 --> 00:03:51,600
Entón, imos pasar a 8 na porción clasificados.

50
00:03:51,600 --> 00:03:55,010
Oito é inferior a 42.

51
00:03:55,010 --> 00:03:56,940
Oito é inferior a 23.

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

53
00:04:00,230 --> 00:04:03,110
Pero 8 é maior que 4.

54
00:04:03,110 --> 00:04:07,280
Entón, nós queremos introducir a 8 entre o 4 eo 16.

55
00:04:09,070 --> 00:04:13,650
E agora só temos un elemento cara á esquerda para clasificar - o 15.

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

57
00:04:16,589 --> 00:04:19,130
Quince é inferior a 23.

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

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

60
00:04:24,810 --> 00:04:27,440
>> Entón, aquí é onde queremos facer a nosa inserción final.

61
00:04:28,770 --> 00:04:30,330
E estamos a facer.

62
00:04:30,330 --> 00:04:33,540
Nós non temos máis elementos na parte indiferenciados,

63
00:04:33,540 --> 00:04:36,670
ea nosa parte está clasificada na orde correcta.

64
00:04:36,670 --> 00:04:40,270
Os números son ordenadas de menor a maior.

65
00:04:40,270 --> 00:04:44,330
Entón, imos dar un ollo a algúns pseudocódigo que describe os pasos que acaba de realizar.

66
00:04:46,760 --> 00:04:51,740
>> Na liña 1, podemos ver que imos ter iterar sobre cada elemento da lista

67
00:04:51,740 --> 00:04:57,060
exceptuando o primeiro, unha vez que o primeiro elemento na porción non triados será simplemente

68
00:04:57,060 --> 00:05:00,220
o primeiro elemento na porción clasificada.

69
00:05:00,220 --> 00:05:06,320
Nas liñas 2 e 3, estamos mantendo o control do noso sitio actual na parte indiferenciados.

70
00:05:06,320 --> 00:05:10,450
Elemento representa o número que estamos actualmente a pasar á parte de clasificados,

71
00:05:10,450 --> 00:05:15,600
e j representa o índice para a parte indiferenciados.

72
00:05:15,600 --> 00:05:20,980
>> Na liña 4, estamos interactuar a través da parte ordenada da dereita para a esquerda.

73
00:05:20,980 --> 00:05:26,010
Queremos deixar a iteração xa que o elemento á esquerda da nosa posición actual

74
00:05:26,010 --> 00:05:30,050
é menor que o elemento que estamos intentando introducir.

75
00:05:30,050 --> 00:05:35,600
Na liña 5, nós estamos cambiando cada elemento que atopamos un espazo para a dereita.

76
00:05:35,600 --> 00:05:40,950
Desta forma, imos ter un espazo libre para introducir en cando atopamos o primeiro elemento

77
00:05:40,950 --> 00:05:44,080
menos que o elemento que nos movemos.

78
00:05:44,080 --> 00:05:50,800
Na liña 6, estamos a actualizar o noso contador para continuar a moverse cara á esquerda a través da parte clasificados.

79
00:05:50,800 --> 00:05:56,860
Finalmente, na liña 7, que está introducindo o elemento dentro da porción da lista ordenada.

80
00:05:56,860 --> 00:06:00,020
>> Sabemos que non hai problema en introducir en posición j,

81
00:06:00,020 --> 00:06:05,360
porque xa cambiou o elemento que adoitaba ser hai un espazo para a dereita.

82
00:06:05,360 --> 00:06:09,460
Lembre, estamos movendo a través da parte ordenada da dereita para a esquerda,

83
00:06:09,460 --> 00:06:13,960
pero estamos movendo a través da parte indiferenciados de esquerda a dereita.

84
00:06:13,960 --> 00:06:19,090
Todo ben. Imos agora dar un ollo a como o algoritmo de longa duración que tomou.

85
00:06:19,090 --> 00:06:25,300
Imos primeiro facer a pregunta canto tempo leva para este algoritmo para realizar no peor caso.

86
00:06:25,300 --> 00:06:29,040
Lembre que nós representamos esta vez correndo con notación Big.

87
00:06:32,530 --> 00:06:38,500
Co fin de resolver a nosa lista, tivemos que iterar sobre os elementos na parte indiferenciados,

88
00:06:38,500 --> 00:06:43,430
e para cada un deses elementos, potencialmente máis de todos os elementos na porción clasificada.

89
00:06:43,430 --> 00:06:47,950
Intuitivamente, isto soa como unha operación de O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> Mirando para o noso pseudocódigo, temos un loop aninhado dentro doutro loop,

91
00:06:51,840 --> 00:06:55,290
que, en realidade, soa como unha operación de O (n ^ 2).

92
00:06:55,290 --> 00:07:01,590
Con todo, a parte ordenada de lista non contiña toda a lista ata o final.

93
00:07:01,590 --> 00:07:06,920
Aínda así, poderiamos potencialmente inserir un novo elemento no inicio da porción clasificada

94
00:07:06,920 --> 00:07:09,320
cada iteração do algoritmo,

95
00:07:09,320 --> 00:07:14,500
o que significa que teriamos que mirar para cada elemento actualmente na parte clasificados.

96
00:07:14,500 --> 00:07:20,090
Entón, isto significa que podería, potencialmente, facer unha comparación para o segundo elemento,

97
00:07:20,090 --> 00:07:24,660
dúas comparacións para o terceiro elemento, e así por diante.

98
00:07:24,660 --> 00:07:32,480
Así, o número total de pasos é a suma dos números enteiros de 1 ata a lonxitude da lista menos 1.

99
00:07:32,480 --> 00:07:35,240
Podemos representar iso con un sumatorio.

100
00:07:41,170 --> 00:07:47,270
>> Non imos entrar en somatórios aquí, pero acontece que esta suma é igual a

101
00:07:47,270 --> 00:07:57,900
n (n - 1) ao longo de 2, o que é equivalente n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Cando se fala en tempo de execución assintótico,

103
00:08:00,800 --> 00:08:05,170
iso n ^ 2 termo vai dominar este término n.

104
00:08:05,170 --> 00:08:11,430
Entón, tipo de inserción é Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
E se corremos tipo de inserción nunha lista xa clasificada.

106
00:08:16,150 --> 00:08:20,960
Neste caso, nós simplemente construír a porción ordenadas de esquerda a dereita.

107
00:08:20,960 --> 00:08:25,050
Entón, a xente só precisa da orde de n pasos.

108
00:08:25,050 --> 00:08:29,740
>> Isto significa que este tipo de inserción ten un rendemento mellor caso de n,

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

110
00:08:34,130 --> 00:08:36,190
E é que polo tipo de inserción,

111
00:08:36,190 --> 00:08:40,429
só un dos moitos algoritmos que poden ser usados ​​para clasificar a lista.

112
00:08:40,429 --> 00:08:43,210
O meu nome é Tommy, e este é o CS50.

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

114
00:08:46,110 --> 00:08:49,230
Oh, non pode impedir que unha vez iniciado.

115
00:09:01,620 --> 00:09:04,760
Oh, nós fixemos iso - Boom! >>