1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Ordenar Inserção]

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
Vamos dar uma olhada no tipo de inserção, um algoritmo para a tomada de uma lista de números e classificando-os.

5
00:00:13,060 --> 00:00:18,300
Um algoritmo, lembre-se, é simplesmente um procedimento passo-a-passo para a realização de uma tarefa.

6
00:00:18,300 --> 00:00:23,640
A idéia básica por trás do tipo de inserção, é dividir nossa lista em duas partes,

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

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

9
00:00:29,290 --> 00:00:32,439
a partir da porção não triados para a porção classificada

10
00:00:32,439 --> 00:00:35,680
até que finalmente toda a lista é ordenada.

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

12
00:00:43,340 --> 00:00:47,680
Uma vez que estes números não são tudo em ordem ascendente, eles estão sem classificação.

13
00:00:47,680 --> 00:00:53,890
Desde que não começou ainda a classificação, vamos considerar todos os seis elementos a nossa parte indiferenciados.

14
00:00:53,890 --> 00:00:59,270
>> Assim que iniciar a classificação, vamos colocar esses números classificados para a esquerda destes.

15
00:00:59,270 --> 00:01:03,600
Então, vamos começar com 23, o primeiro elemento em nossa lista.

16
00:01:03,600 --> 00:01:06,930
Nós não temos todos os elementos de nossa parte classificada ainda,

17
00:01:06,930 --> 00:01:12,460
então vamos simplesmente considerar 23 seja o início eo fim de nossa parte classificados.

18
00:01:12,460 --> 00:01:16,510
Agora, a nossa parte ordenada possui um número, 23,

19
00:01:16,510 --> 00:01:20,260
e nossa porção indiferenciados tem esses cinco números.

20
00:01:20,260 --> 00:01:27,320
Vamos agora inserir o próximo número na nossa porção indiferenciados, 42, na porção classificados.

21
00:01:27,320 --> 00:01:35,930
>> Para isso, vamos precisar de comparar a 42 para o 23 - o único elemento em nossa parcela classificada até agora.

22
00:01:35,930 --> 00:01:41,980
Quarenta e dois é maior do que 23, então podemos simplesmente acrescentar 42 até o fim

23
00:01:41,980 --> 00:01:45,420
da porção da lista ordenada. Ótimo!

24
00:01:45,420 --> 00:01:51,850
Agora a nossa parte ordenada possui dois elementos, e nossa porção indiferenciados tem quatro elementos.

25
00:01:51,850 --> 00:01:57,200
Então, vamos agora passar para a 4, o elemento seguinte na parte indiferenciados.

26
00:01:57,200 --> 00:02:00,230
Assim, onde deve esta ser colocada na parte classificada?

27
00:02:00,230 --> 00:02:04,220
>> Lembre-se, nós queremos colocar esse número na ordem de classificação

28
00:02:04,220 --> 00:02:08,680
por isso a nossa parte permanece classificada corretamente classificados em todos os momentos.

29
00:02:08,680 --> 00:02:14,380
Se colocarmos a 4 para a direita dos 42, então a nossa lista vai ser fora de ordem.

30
00:02:14,380 --> 00:02:18,380
Então, vamos continuar a mover da direita para a esquerda na nossa porção tipo.

31
00:02:18,380 --> 00:02:23,260
À medida que avançamos, vamos mudar cada número abaixo de um lugar para dar espaço para o novo número.

32
00:02:25,440 --> 00:02:31,740
Ok, 4 também é menor que 23, portanto, não podemos colocá-lo aqui também.

33
00:02:31,740 --> 00:02:34,480
Vamos passar a 23 um lugar certo.

34
00:02:36,500 --> 00:02:43,120
>> Isso significa que nós gostaríamos de colocar o 4 no primeiro buraco na parte de classificados.

35
00:02:43,120 --> 00:02:46,300
Observe como esse espaço na lista já estava vazio,

36
00:02:46,300 --> 00:02:51,120
porque estamos movendo elementos classificados para baixo como nós encontramos eles.

37
00:02:51,120 --> 00:02:52,740
Tudo bem. Então, nós estamos no meio do caminho.

38
00:02:52,740 --> 00:02:57,990
Vamos continuar o nosso algoritmo, inserindo a 16 na porção classificados.

39
00:02:59,260 --> 00:03:03,820
Dezesseis é menor do que 42, então vamos mudar o 42 para a direita.

40
00:03:05,700 --> 00:03:10,190
Dezesseis também é menor do que 23, então vamos também mudar esse elemento.

41
00:03:11,790 --> 00:03:20,820
>> Agora, 16 é maior do que 4. Então, parece que gostaria de inserir a 16 entre o 4 eo 23.

42
00:03:20,820 --> 00:03:24,620
Enquanto se move através da parte classificada da lista da direita para a esquerda,

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

44
00:03:29,160 --> 00:03:31,540
estamos tentando inserir.

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

46
00:03:35,820 --> 00:03:40,520
que, lembre-se, nós criamos por elementos móveis na parte de tipo mais

47
00:03:40,520 --> 00:03:43,340
como nós encontramos eles.

48
00:03:43,340 --> 00:03:47,900
>> Tudo bem. Agora, temos quatro elementos classificados e dois elementos não ordenados.

49
00:03:47,900 --> 00:03:51,600
Então, vamos passar a 8 na porção classificados.

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 do que 16.

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

54
00:04:03,110 --> 00:04:07,280
Então, nós gostaríamos de inserir a 8 entre o 4 eo 16.

55
00:04:09,070 --> 00:04:13,650
E agora só temos mais um elemento para a esquerda para classificar - o 15.

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

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

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

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

60
00:04:24,810 --> 00:04:27,440
>> Então, aqui é onde nós queremos fazer a nossa inserção final.

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

62
00:04:30,330 --> 00:04:33,540
Nós não temos mais elementos na parte indiferenciados,

63
00:04:33,540 --> 00:04:36,670
e nossa parte é classificada na ordem correta.

64
00:04:36,670 --> 00:04:40,270
Os números são ordenados do menor para o maior.

65
00:04:40,270 --> 00:04:44,330
Então, vamos dar uma olhada em alguns pseudocódigo que descreve os passos que acabou de realizar.

66
00:04:46,760 --> 00:04:51,740
>> Na linha 1, podemos ver que nós vamos precisar iterar sobre cada elemento da lista

67
00:04:51,740 --> 00:04:57,060
exceptuando o primeiro, uma vez que o primeiro elemento na porção não triados será simplesmente

68
00:04:57,060 --> 00:05:00,220
o primeiro elemento na porção classificada.

69
00:05:00,220 --> 00:05:06,320
Nas linhas 2 e 3, estamos mantendo o controle de nosso lugar atual na parte indiferenciados.

70
00:05:06,320 --> 00:05:10,450
Elemento representa o número que estamos actualmente a passar para a parte de classificados,

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

72
00:05:15,600 --> 00:05:20,980
>> Na linha 4, estamos interagindo através da parte ordenada da direita para a esquerda.

73
00:05:20,980 --> 00:05:26,010
Queremos parar a iteração uma vez que o elemento para a esquerda de nossa posição atual

74
00:05:26,010 --> 00:05:30,050
é menor do que o elemento que estamos tentando inserir.

75
00:05:30,050 --> 00:05:35,600
Na linha 5, nós estamos mudando cada elemento que encontramos um espaço para a direita.

76
00:05:35,600 --> 00:05:40,950
Dessa forma, nós vamos ter um espaço livre para inserir em quando encontramos o primeiro elemento

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

78
00:05:44,080 --> 00:05:50,800
Na linha 6, estamos atualizando nosso contador para continuar a mover para a esquerda através da parte classificados.

79
00:05:50,800 --> 00:05:56,860
Finalmente, na linha 7, que está inserindo o elemento dentro da porção da lista ordenada.

80
00:05:56,860 --> 00:06:00,020
>> Sabemos que não há problema em inserir em posição j,

81
00:06:00,020 --> 00:06:05,360
porque já mudou o elemento que costumava ser há um espaço para a direita.

82
00:06:05,360 --> 00:06:09,460
Lembre-se, estamos nos movendo através da parte ordenada da direita para a esquerda,

83
00:06:09,460 --> 00:06:13,960
mas estamos nos movendo através da parte indiferenciados da esquerda para a direita.

84
00:06:13,960 --> 00:06:19,090
Tudo bem. Vamos agora dar uma olhada em como o algoritmo de longa duração que tomou.

85
00:06:19,090 --> 00:06:25,300
Vamos primeiro fazer a pergunta quanto tempo leva para este algoritmo para executar no pior caso.

86
00:06:25,300 --> 00:06:29,040
Lembre-se que nós representamos desta vez correndo com notação Big.

87
00:06:32,530 --> 00:06:38,500
A fim de resolver a nossa lista, nós tivemos que iterar sobre os elementos na parte indiferenciados,

88
00:06:38,500 --> 00:06:43,430
e para cada um desses elementos, potencialmente mais de todos os elementos na porção classificada.

89
00:06:43,430 --> 00:06:47,950
Intuitivamente, isso soa como uma operação de O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> Olhando para o nosso pseudocódigo, temos um loop aninhado dentro de outro loop,

91
00:06:51,840 --> 00:06:55,290
que, na verdade, soa como uma operação de O (n ^ 2).

92
00:06:55,290 --> 00:07:01,590
No entanto, a parte ordenada de lista não continha toda a lista até o fim.

93
00:07:01,590 --> 00:07:06,920
Ainda assim, poderíamos potencialmente inserir um novo elemento no início da porção classificada

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

95
00:07:09,320 --> 00:07:14,500
o que significa que teríamos de olhar para cada elemento atualmente na parte de classificados.

96
00:07:14,500 --> 00:07:20,090
Então, isso significa que poderia, potencialmente, fazer uma comparação para o segundo elemento,

97
00:07:20,090 --> 00:07:24,660
duas comparações para o terceiro elemento, e assim por diante.

98
00:07:24,660 --> 00:07:32,480
Assim, o número total de passos é a soma dos números inteiros de 1 até o comprimento da lista menos 1.

99
00:07:32,480 --> 00:07:35,240
Podemos representar isso com um somatório.

100
00:07:41,170 --> 00:07:47,270
>> Nós não vamos entrar em somatórios aqui, mas acontece que esta soma é 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
Quando se fala em tempo de execução assintótico,

103
00:08:00,800 --> 00:08:05,170
isso n ^ 2 termo vai dominar este termo n.

104
00:08:05,170 --> 00:08:11,430
Então, tipo de inserção é Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
E se corremos tipo de inserção em uma lista já classificada.

106
00:08:16,150 --> 00:08:20,960
Nesse caso, nós simplesmente construir a porção ordenadas da esquerda para a direita.

107
00:08:20,960 --> 00:08:25,050
Então, a gente só precisa da ordem de n passos.

108
00:08:25,050 --> 00:08:29,740
>> Isso significa que esse tipo de inserção tem um desempenho melhor caso de n,

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

110
00:08:34,130 --> 00:08:36,190
E é isso por tipo de inserção,

111
00:08:36,190 --> 00:08:40,429
apenas um dos muitos algoritmos que podem ser usados ​​para classificar uma lista.

112
00:08:40,429 --> 00:08:43,210
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, você não pode impedir que uma vez iniciado.

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