1
00:00:00,000 --> 00:00:02,826
>> [Música tocando]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Então ordenação por inserção é outro
algoritmo que podemos usar para classificar uma matriz.

4
00:00:09,370 --> 00:00:12,350
A idéia por trás deste algoritmo
é construir a sua matriz classificada

5
00:00:12,350 --> 00:00:19,670
no lugar, deslocando elementos de
a maneira como você vai, para fazer o quarto.

6
00:00:19,670 --> 00:00:22,240
Esta é ligeiramente diferente
tipo de seleção ou bolha

7
00:00:22,240 --> 00:00:25,460
tipo, por exemplo, onde
nós estamos ajustando os locais,

8
00:00:25,460 --> 00:00:26,910
onde nós estamos fazendo swaps.

9
00:00:26,910 --> 00:00:29,760
>> Neste caso, o que nós somos, na verdade,
fazendo é elementos de deslizamento

10
00:00:29,760 --> 00:00:31,390
mais, para fora do caminho.

11
00:00:31,390 --> 00:00:34,030
Como é que este algoritmo
trabalhar em pseudocódigo?

12
00:00:34,030 --> 00:00:37,646
Bem, vamos apenas dizer que o arbitrariamente
primeiro elemento da matriz é classificada.

13
00:00:37,646 --> 00:00:38,770
Estamos construindo-lo no lugar.

14
00:00:38,770 --> 00:00:42,660
>> Nós vamos ir um elemento de cada vez e
construí-lo, e por isso a primeira coisa que vemos

15
00:00:42,660 --> 00:00:43,890
é uma matriz de um elemento.

16
00:00:43,890 --> 00:00:47,720
E, por definição, um
elemento da matriz está classificada.

17
00:00:47,720 --> 00:00:50,850
>> Então nós vamos repetir esse processo until--
vamos repetir o processo a seguir

18
00:00:50,850 --> 00:00:52,900
até que todos os elementos são classificados.

19
00:00:52,900 --> 00:00:57,770
Olhe para o próximo elemento não triados e
inseri-lo na porção classificada,

20
00:00:57,770 --> 00:01:01,209
deslocando-se o número necessário
de elementos fora do caminho.

21
00:01:01,209 --> 00:01:03,750
Esperemos que esta visualização
vai ajudá-lo a ver exatamente o que está

22
00:01:03,750 --> 00:01:05,980
acontecendo com ordenação por inserção.

23
00:01:05,980 --> 00:01:08,010
>> Então, novamente, aqui está a nossa
toda matriz não classificado,

24
00:01:08,010 --> 00:01:10,970
todos os elementos indicados em vermelho.

25
00:01:10,970 --> 00:01:13,320
E vamos seguir o
passos do nosso pseudocódigo.

26
00:01:13,320 --> 00:01:16,970
A primeira coisa que fazemos, é o que chamamos
primeiro elemento da matriz, classificados.

27
00:01:16,970 --> 00:01:20,920
Então, nós estamos só vou dizer
cinco, você está agora classificada.

28
00:01:20,920 --> 00:01:24,570
>> Então, olhamos para a próxima
indiferenciados elemento da matriz

29
00:01:24,570 --> 00:01:27,610
e nós queremos que inserir
na porção classificados,

30
00:01:27,610 --> 00:01:29,750
deslocando elementos mais.

31
00:01:29,750 --> 00:01:33,470
Então, dois é a próxima indiferenciados
elemento da matriz.

32
00:01:33,470 --> 00:01:36,250
Claramente, antes da pertence
cinco, então o que nós vamos fazer

33
00:01:36,250 --> 00:01:41,580
é uma espécie de realizar duas de lado por um segundo,
mudar ao longo de cinco, e em seguida, insira dois

34
00:01:41,580 --> 00:01:43,210
antes das cinco, para onde deve ir.

35
00:01:43,210 --> 00:01:45,280
E agora podemos dizer que dois está classificada.

36
00:01:45,280 --> 00:01:48,400
>> Então, como você pode ver, nós temos somente até agora
olhou para dois elementos do array.

37
00:01:48,400 --> 00:01:50,600
Nós não olhou para o
descansar em tudo, mas nós temos

38
00:01:50,600 --> 00:01:54,582
tenho esses dois elementos classificados por
caminho do mecanismo de mudança.

39
00:01:54,582 --> 00:01:56,410
>> Por isso, repita o processo novamente.

40
00:01:56,410 --> 00:01:58,850
Olhe para a próxima não triados
elemento, que é um.

41
00:01:58,850 --> 00:02:04,010
Vamos manter isso de lado por um segundo,
mudar tudo mais, e colocar uma

42
00:02:04,010 --> 00:02:05,570
onde ele deve ir.

43
00:02:05,570 --> 00:02:08,110
>> Novamente, ainda, temos sempre apenas
olhou para um, dois, e cinco.

44
00:02:08,110 --> 00:02:12,480
Nós não sabemos o que mais está por vir,
mas temos ordenados esses três elementos.

45
00:02:12,480 --> 00:02:16,030
>> Próximo elemento é não triados
três, por isso vamos defini-lo de lado.

46
00:02:16,030 --> 00:02:18,200
Nós vamos mudar com o que nós
precisa para que, desta vez

47
00:02:18,200 --> 00:02:21,820
não é tudo como no precedente
dois casos, é apenas a cinco.

48
00:02:21,820 --> 00:02:25,440
E então nós vamos ficar três,
entre os dois e os cinco.

49
00:02:25,440 --> 00:02:27,849
>> Seis é o próximo não triados
elemento para a matriz.

50
00:02:27,849 --> 00:02:31,140
E, de facto, seis é superior a cinco, assim
nós nem sequer precisa fazer qualquer troca.

51
00:02:31,140 --> 00:02:35,710
Podemos apenas alinhavar seis à direita para
a extremidade da porção classificados.

52
00:02:35,710 --> 00:02:38,270
>> Por último, é a quatro
último elemento indiferenciado.

53
00:02:38,270 --> 00:02:42,060
Então, vamos defini-lo de lado, mudar ao longo
os elementos que precisa mudar mais,

54
00:02:42,060 --> 00:02:43,780
e em seguida, colocar quatro onde ele pertence.

55
00:02:43,780 --> 00:02:46,400
E agora olha, nós temos sorte
de todos os elementos.

56
00:02:46,400 --> 00:02:48,150
Observe com inserção
tipo, nós não temos

57
00:02:48,150 --> 00:02:50,240
para ir e voltar do outro lado da matriz.

58
00:02:50,240 --> 00:02:54,720
Nós só fomos em frente à matriz
uma vez, e mudamos as coisas

59
00:02:54,720 --> 00:02:59,870
que já tinha encontrado, a fim
para dar espaço para os novos elementos.

60
00:02:59,870 --> 00:03:02,820
>> Então, qual é o pior caso
cenário com ordenação por inserção?

61
00:03:02,820 --> 00:03:05,090
No pior dos casos, o
matriz é na ordem inversa.

62
00:03:05,090 --> 00:03:11,180
Você tem que mudar cada um dos elementos n
até n posições, cada vez que

63
00:03:11,180 --> 00:03:12,880
fazer uma inserção.

64
00:03:12,880 --> 00:03:15,720
Isso é um monte de mudança.

65
00:03:15,720 --> 00:03:18,014
>> No melhor dos casos, o
matriz é perfeitamente ordenadas.

66
00:03:18,014 --> 00:03:20,680
E mais ou menos como o que aconteceu
com cinco e seis no exemplo,

67
00:03:20,680 --> 00:03:23,779
onde se pode apenas alinhavar-lo no
sem ter que fazer qualquer mudança,

68
00:03:23,779 --> 00:03:24,820
teremos essencialmente fazer isso.

69
00:03:24,820 --> 00:03:27,560
>> Se você imaginar que a nossa
matriz era de um a seis,

70
00:03:27,560 --> 00:03:29,900
nós começar por
declarando um é classificado.

71
00:03:29,900 --> 00:03:33,300
Dois vem após um para que possamos apenas
dizer, OK, bem um e dois são classificadas.

72
00:03:33,300 --> 00:03:36,190
Três vem depois de dois, assim, OK,
um e dois e três são classificadas.

73
00:03:36,190 --> 00:03:39,590
>> Nós não estamos fazendo nenhum swaps, estamos
apenas movendo essa linha arbitrária

74
00:03:39,590 --> 00:03:42,460
entre classificadas e não triados como vamos nós.

75
00:03:42,460 --> 00:03:46,646
De forma tão eficaz como fizemos no exemplo,
transformando elementos azul, à medida que prosseguimos.

76
00:03:46,646 --> 00:03:48,270
Então, qual é o pior caso de tempo de execução, então?

77
00:03:48,270 --> 00:03:51,854
Lembre-se, se tivermos que mudar cada um dos
os n elementos possivelmente n posições,

78
00:03:51,854 --> 00:03:54,020
espero que lhe dá
uma idéia que o pior caso

79
00:03:54,020 --> 00:03:57,770
O tempo de execução é grande de n ao quadrado.

80
00:03:57,770 --> 00:04:00,220
>> Se a matriz é perfeitamente
classificadas, todos nós temos que fazer

81
00:04:00,220 --> 00:04:04,480
é olhar para cada elemento
uma vez, e, em seguida, estamos a fazer.

82
00:04:04,480 --> 00:04:08,440
Assim, na melhor das hipóteses, é omega de n.

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

84
00:04:09,490 --> 00:04:11,760
Este é CS50.

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