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ón ordenación por inserción é outro
algoritmo que podemos utilizar para clasificar unha matriz.

4
00:00:09,370 --> 00:00:12,350
A idea detrás deste algoritmo
é construír a súa matriz clasificada

5
00:00:12,350 --> 00:00:19,670
no lugar, desprazando elementos de
a forma como vai, para facer o cuarto.

6
00:00:19,670 --> 00:00:22,240
Esta é lixeiramente diferente
tipo de selección ou burbulla

7
00:00:22,240 --> 00:00:25,460
tipo, por exemplo, onde
estamos axustando os locais,

8
00:00:25,460 --> 00:00:26,910
onde estamos facendo swaps.

9
00:00:26,910 --> 00:00:29,760
>> Neste caso, o que somos, en realidade,
facendo é elementos de deslizamento

10
00:00:29,760 --> 00:00:31,390
máis, para fóra do camiño.

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

12
00:00:34,030 --> 00:00:37,646
Ben, imos só dicir que o arbitrariamente
primeiro elemento da matriz é clasificada.

13
00:00:37,646 --> 00:00:38,770
Estamos construíndo-lo no lugar.

14
00:00:38,770 --> 00:00:42,660
>> Nós imos ir un elemento de cada vez e
constrúe-lo, e por iso o primeiro que vemos

15
00:00:42,660 --> 00:00:43,890
é unha matriz de un elemento.

16
00:00:43,890 --> 00:00:47,720
E, por definición, un
elemento da matriz está clasificada.

17
00:00:47,720 --> 00:00:50,850
>> Entón nós imos repetir este proceso until--
imos repetir o proceso a seguir

18
00:00:50,850 --> 00:00:52,900
ata que todos os elementos son clasificados.

19
00:00:52,900 --> 00:00:57,770
Olle para o seguinte elemento sen clasificar e
inserir-lo na porción clasificada,

20
00:00:57,770 --> 00:01:01,209
desprazándose o número necesario
de elementos fóra do camiño.

21
00:01:01,209 --> 00:01:03,750
Esperemos que esta visualización
vai axudar a ver o que está

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

23
00:01:05,980 --> 00:01:08,010
>> Entón, de novo, aquí está a nosa
toda matriz non clasificado,

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

25
00:01:10,970 --> 00:01:13,320
E imos seguir o
pasos do noso pseudocódigo.

26
00:01:13,320 --> 00:01:16,970
O primeiro que facemos, é o que chamamos
primeiro elemento da matriz, clasificados.

27
00:01:16,970 --> 00:01:20,920
Entón, nós estamos só vou dicir
cinco, está agora clasificada.

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

29
00:01:24,570 --> 00:01:27,610
e queremos que inserir
na porción clasificados,

30
00:01:27,610 --> 00:01:29,750
desprazando elementos máis.

31
00:01:29,750 --> 00:01:33,470
Entón, dous é a seguinte indiferenciados
elemento da matriz.

32
00:01:33,470 --> 00:01:36,250
Claramente, antes da pertenza
cinco, entón o que nós imos facer

33
00:01:36,250 --> 00:01:41,580
é unha especie de realizar dúas de lado por un segundo,
cambiar ao longo de cinco, e logo insira dous

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

35
00:01:43,210 --> 00:01:45,280
E agora podemos dicir que dous está clasificada.

36
00:01:45,280 --> 00:01:48,400
>> Entón, como podes ver, temos só ata agora
mirou dous elementos do array.

37
00:01:48,400 --> 00:01:50,600
Non mirou para o
descansar en todo, pero nós temos

38
00:01:50,600 --> 00:01:54,582
teño eses dous elementos clasificados por
camiño do mecanismo de cambio.

39
00:01:54,582 --> 00:01:56,410
>> Por iso, repita o proceso de novo.

40
00:01:56,410 --> 00:01:58,850
Olhe a próxima sen clasificar
elemento, que é un.

41
00:01:58,850 --> 00:02:04,010
Imos manter isto de lado por un segundo,
cambiar todo máis, e poñer unha

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

43
00:02:05,570 --> 00:02:08,110
>> De novo, aínda, temos sempre só
mirou para un, dous, e cinco.

44
00:02:08,110 --> 00:02:12,480
Non sabemos o que máis está por vir,
pero temos ordenados eses tres elementos.

45
00:02:12,480 --> 00:02:16,030
>> Preto elemento é sen clasificar
tres, así que imos define-lo de lado.

46
00:02:16,030 --> 00:02:18,200
Nós imos cambiar co que nós
precisa para que, desta vez

47
00:02:18,200 --> 00:02:21,820
non é todo como no precedente
dous casos, é só a cinco.

48
00:02:21,820 --> 00:02:25,440
E entón nós imos estar tres,
entre os dous e os cinco.

49
00:02:25,440 --> 00:02:27,849
>> Seis é o seguinte sen clasificar
elemento para a matriz.

50
00:02:27,849 --> 00:02:31,140
E, de feito, seis é superior a cinco, así
nós nin sequera que facer calquera cambio.

51
00:02:31,140 --> 00:02:35,710
Podemos só alinhavar seis da dereita para
o extremo da porción clasificados.

52
00:02:35,710 --> 00:02:38,270
>> Para rematar, é a catro
último elemento indiferenciado.

53
00:02:38,270 --> 00:02:42,060
Entón, imos define-lo de lado, cambiar ao longo
os elementos que precisa cambiar máis,

54
00:02:42,060 --> 00:02:43,780
e logo poñer catro onde pertence.

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

56
00:02:46,400 --> 00:02:48,150
Observe con inserción
tipo, nós non temos

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

58
00:02:50,240 --> 00:02:54,720
Nós só fomos fronte á matriz
Unha vez máis, e cambiamos as cousas

59
00:02:54,720 --> 00:02:59,870
que xa atopara, a fin
para dar espazo para os novos elementos.

60
00:02:59,870 --> 00:03:02,820
>> Entón, cal é o peor caso
escenario con ordenación por inserción?

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

62
00:03:05,090 --> 00:03:11,180
Ten que cambiar cada un dos elementos n
ata n posicións, cada vez que

63
00:03:11,180 --> 00:03:12,880
facer unha inserción.

64
00:03:12,880 --> 00:03:15,720
Iso é unha chea de cambio.

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

66
00:03:18,014 --> 00:03:20,680
E máis ou menos como o que pasou
con cinco e seis no exemplo,

67
00:03:20,680 --> 00:03:23,779
onde se pode só alinhavar-lo no
sen ter que facer ningún cambio,

68
00:03:23,779 --> 00:03:24,820
teremos esencialmente facelo.

69
00:03:24,820 --> 00:03:27,560
>> Se imaxinar que a nosa
matriz era dun a seis,

70
00:03:27,560 --> 00:03:29,900
nós comezar por
declarando un é clasificado.

71
00:03:29,900 --> 00:03:33,300
Dous vén despois dun para que poidamos só
dicir, OK, así un e dous son clasificadas.

72
00:03:33,300 --> 00:03:36,190
Tres vén despois de dous, así, OK,
un e dous e tres son clasificadas.

73
00:03:36,190 --> 00:03:39,590
>> Non estamos facendo ningún swaps, estamos
só movendo esta liña arbitraria

74
00:03:39,590 --> 00:03:42,460
entre clasificadas e sen clasificar como imos nós.

75
00:03:42,460 --> 00:03:46,646
De forma tan eficaz como fixemos no exemplo,
transformando elementos azul, a medida que proseguimos.

76
00:03:46,646 --> 00:03:48,270
Entón, cal é o peor caso de tempo de execución, entón?

77
00:03:48,270 --> 00:03:51,854
Teña en conta que, se temos que cambiar cada un dos
os n elementos posiblemente n posicións,

78
00:03:51,854 --> 00:03:54,020
espero que lle dá
unha idea que o peor caso

79
00:03:54,020 --> 00:03:57,770
O tempo de execución é grande de n ao cadrado.

80
00:03:57,770 --> 00:04:00,220
>> Se a matriz é perfectamente
clasificadas, todos temos que facer

81
00:04:00,220 --> 00:04:04,480
é mirar para cada elemento
Unha vez máis, e, a continuación, estamos a facer.

82
00:04:04,480 --> 00:04:08,440
Así, no mellor dos casos, é omega de n.

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

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

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