1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Merge sort]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Harvard University]

3
00:00:04,000 --> 00:00:07,000
[Esta é CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Imos falar sobre o tipo de mesclagem.

5
00:00:09,000 --> 00:00:14,000
Ata agora xa viu especie de burbulla, tipo de inserción e tipo de selección.

6
00:00:14,000 --> 00:00:17,000
Aínda que eu vou tipo de onda miña man que eu quero dicir con mellor,

7
00:00:17,000 --> 00:00:21,000
merge sort xeralmente ten un rendemento mellor que calquera destes tres tipos.

8
00:00:22,000 --> 00:00:27,000
>> Pero antes de falar merge sort, imos falar sobre a mesclagem de dúas listas ordenadas.

9
00:00:27,000 --> 00:00:31,000
Imos chamar o proceso de tomar dúas listas ordenadas, como estes,

10
00:00:31,000 --> 00:00:35,000
e facer unha única lista ordenada fóra delas - a fusión das listas.

11
00:00:35,000 --> 00:00:37,750
Como podemos facer iso?

12
00:00:37,750 --> 00:00:41,290
Ben, unha idea é se ater só unha lista para o final da lista de outro

13
00:00:41,290 --> 00:00:43,830
e despois ordenar a lista resultante.

14
00:00:43,830 --> 00:00:47,220
>> Mentres tanto funciona, é unha chea de traballo innecesario.

15
00:00:47,220 --> 00:00:49,900
Podemos facelo máis rápido que só a clasificación.

16
00:00:49,900 --> 00:00:54,100
Teña en conta que unha idea errónea é só para tomar vasos alternadas de cada lista.

17
00:00:54,100 --> 00:00:56,460
Aínda que isto poida parecer que funciona nun primeiro momento,

18
00:00:56,460 --> 00:01:05,760
facendo iso acabamos con 4, 8, 15, 23, 16 - aviso de que 16 e 23 están fóra de lugar.

19
00:01:05,760 --> 00:01:09,380
Isto porque dous elementos que deben aparecer consecutivo na lista mesclada

20
00:01:09,380 --> 00:01:11,720
están na mesma lista inicial.

21
00:01:11,720 --> 00:01:14,850
Ambos 15 e 16 están na lista do lado esquerdo.

22
00:01:14,850 --> 00:01:19,810
O truco é aproveitar o feito de que ambas as listas xa están clasificados.

23
00:01:19,810 --> 00:01:23,320
Isto significa que, se só ollar para os primeiros elementos de ambas as listas -

24
00:01:23,320 --> 00:01:29,580
aquí, 4 e 8 - un deles tamén debe ser o primeiro elemento da lista resultante da fusión.

25
00:01:29,580 --> 00:01:31,620
Ben, por que isto?

26
00:01:31,620 --> 00:01:33,520
Ambas as listas xa están clasificados,

27
00:01:33,520 --> 00:01:38,410
e entón ou 4 ou 8 debe ser o elemento máis pequeno cando se combinan as dúas listas.

28
00:01:38,410 --> 00:01:41,770
Neste caso, a máis pequena e 4,

29
00:01:41,770 --> 00:01:46,370
para que poidamos aproveitar 4 e facelo o primeiro elemento da lista mesclada.

30
00:01:46,370 --> 00:01:50,710
Agora imos continuar a fusión das restantes tres elementos da primeira lista

31
00:01:50,710 --> 00:01:52,920
e 4 elementos da segunda rolda.

32
00:01:52,920 --> 00:01:57,150
>> Unha vez máis, nós só necesitamos mirar para o primeiro elemento de ambas as listas.

33
00:01:57,150 --> 00:02:01,060
O menor dos dous debe ser o segundo elemento da lista resultante da fusión.

34
00:02:01,060 --> 00:02:05,440
Esta vez, entre 8 e 15 o máis pequeno é de 8, e entón introducir este

35
00:02:05,440 --> 00:02:09,240
como o segundo elemento da lista de clasificados.

36
00:02:09,240 --> 00:02:12,180
Podemos seguir comparando os primeiros elementos de ambas as listas

37
00:02:12,180 --> 00:02:14,420
e eliminar o menor dos dous.

38
00:02:14,420 --> 00:02:19,460
Comparando 15 e 23, 15 é menor e así é o noso terceiro elemento.

39
00:02:21,000 --> 00:02:23,910
Agora comparar 16 e 23, 16 é menor.

40
00:02:23,910 --> 00:02:26,820
Entón ese é o cuarto elemento.

41
00:02:26,820 --> 00:02:30,390
>> Teña en conta que dous elementos viñeron da mesma lista nunha fileira.

42
00:02:30,390 --> 00:02:34,400
É por iso que a lista resultante da fusión non pode só elementos alternados das dúas listas.

43
00:02:34,400 --> 00:02:40,020
Comparando 50 e 23, 23 é menor, polo tanto, escolla que.

44
00:02:40,770 --> 00:02:44,070
Entre 50 e 42, 42 é menor.

45
00:02:44,070 --> 00:02:48,290
Entre 50 e 108, 50 é menor.

46
00:02:48,290 --> 00:02:52,330
E, finalmente, temos só 108, polo que debe ir ao final da nosa lista.

47
00:02:53,750 --> 00:02:56,180
Teña en conta que temos unha lista, bo ordenado.

48
00:02:56,180 --> 00:02:59,040
Cada vez que se compararon os 2 primeiros elementos das dúas listas

49
00:02:59,040 --> 00:03:02,730
fomos capaces de determinar o elemento seguinte da lista resultante da fusión.

50
00:03:02,730 --> 00:03:08,070
Isto significa que a lista final contén n números, onde n aquí é 8,

51
00:03:08,070 --> 00:03:12,610
entón necesitamos na maioría das comparacións n para obter todos estes números para o lugar seguro.

52
00:03:13,230 --> 00:03:16,230
Tal algoritmo está dito para ser executado en tempo lineal,

53
00:03:16,230 --> 00:03:18,090
pero non se preocupe con iso aquí.

54
00:03:18,570 --> 00:03:22,810
>> Usando o noso algoritmo de fusión, podemos facer un algoritmo de ordenación rápido mesclagem.

55
00:03:22,810 --> 00:03:25,170
Entón, imos recuperar nosas listas.

56
00:03:35,210 --> 00:03:37,750
Existen dous grandes pasos no proceso de merge sort.

57
00:03:37,750 --> 00:03:41,500
En primeiro lugar, de forma continua dividir a lista de vasos en metades

58
00:03:41,500 --> 00:03:44,860
ata que teñamos unha morea de listas con só 1 cunca neles.

59
00:03:44,860 --> 00:03:47,350
Non te preocupes se a lista contén un número impar

60
00:03:47,350 --> 00:03:49,880
e non pode facer un corte perfectamente limpo entre eles.

61
00:03:49,880 --> 00:03:53,750
Só arbitrariamente escoller cal alista para incluír o vaso extra dentro

62
00:03:53,750 --> 00:03:56,240
Entón, imos dividir estas listas.

63
00:03:58,140 --> 00:04:01,310
Agora temos dúas listas.

64
00:04:04,120 --> 00:04:06,570
Agora temos catro listas.

65
00:04:10,350 --> 00:04:13,870
>> E agora temos oito listas con un só vaso de cada lista.

66
00:04:13,870 --> 00:04:16,630
Entón é iso para o paso 1.

67
00:04:16,630 --> 00:04:22,230
Para a etapa 2, nós repetidamente fundir pares de listas usando o algoritmo de unión que aprenden antes.

68
00:04:22,230 --> 00:04:29,160
Mesclando 108 e 15, imos acabar coa lista de 15, 108.

69
00:04:30,330 --> 00:04:36,250
Mesclando 50 e 4, imos acabar con 4, 50.

70
00:04:36,960 --> 00:04:41,400
Mesclando 8 e 42, imos acabar con 8, 42.

71
00:04:42,790 --> 00:04:48,130
E fusión de 23 e 16, imos acabar con 16, 23.

72
00:04:49,740 --> 00:04:52,450
Agora todas as nosas listas son de tamaño 2.

73
00:04:53,020 --> 00:04:56,180
Teña en conta que cada unha das catro listas son clasificados.

74
00:04:56,180 --> 00:04:59,160
>> Así, podemos comezar a fundirse pares de listas de novo.

75
00:04:59,160 --> 00:05:03,240
A fusión 15 e 108 e 4 e 50 -

76
00:05:03,240 --> 00:05:11,170
tira primeiro a 4, a continuación, a 15, a continuación a 50, a continuación a 108.

77
00:05:11,170 --> 00:05:15,120
Mesclando 8, 42 e 16, 23,

78
00:05:15,120 --> 00:05:22,440
que comezou a tomar o 8, a continuación, a 16, a continuación a 23, a continuación a 42.

79
00:05:22,440 --> 00:05:27,370
Polo tanto, agora temos só 2 listas de tamaño 4, cada un dos cales está clasificada.

80
00:05:27,370 --> 00:05:30,980
Entón agora nós mesturar estas dúas listas.

81
00:05:30,980 --> 00:05:33,440
Primeiro tomamos a 4.

82
00:05:33,440 --> 00:05:36,580
Entón tomamos a 8.

83
00:05:36,580 --> 00:05:50,700
A continuación, tomar a 15 e 16, e despois 23, despois 42, despois 50, despois 108.

84
00:05:50,700 --> 00:05:52,220
E estamos a facer.

85
00:05:52,220 --> 00:05:54,900
Temos, agora, unha lista ordenada.

86
00:05:54,900 --> 00:05:57,890
Entón, quão rápido foi iso, exactamente?

87
00:05:57,890 --> 00:06:02,000
En termos técnicos, merge sort é O (n log n),

88
00:06:02,000 --> 00:06:07,380
Considerando que todos especie de burbulla, tipo de inserción e tipo de selección son O (n ²).

89
00:06:07,380 --> 00:06:11,120
En realidade, como vai aprender logo, non será capaz de chegar a unha especie

90
00:06:11,120 --> 00:06:14,820
que ten un rendemento mellor que o (n log n) no caso xeral.

91
00:06:14,820 --> 00:06:19,120
Unha vez máis, non se preocupe con esta notación O gran se non viu aínda.

92
00:06:19,120 --> 00:06:23,490
>> Só sei que isto significa que, se quixésemos Ordenar unha lista moi grande

93
00:06:23,490 --> 00:06:26,820
tipo especie de burbulla, tipo de inserción e selección podería levar

94
00:06:26,820 --> 00:06:29,500
significativamente maior que merge sort.

95
00:06:29,500 --> 00:06:33,210
Iso non significa que a clasificación por intercalação será máis rápida para todas as listas

96
00:06:33,210 --> 00:06:36,220
ou mesmo para calquera lista única nun determinado tamaño.

97
00:06:36,220 --> 00:06:41,950
Por exemplo, tipo de inserción pode ser o máis rápido de clasificación para as listas de menores de 5 elementos.

98
00:06:41,950 --> 00:06:47,360
Na práctica, merge sort é normalmente máis rápido para listas de tan pequenas canto 50 elementos.

99
00:06:47,360 --> 00:06:51,120
>> Pero esa velocidade extra non vén sen un prezo.

100
00:06:51,120 --> 00:06:54,770
Ao contrario dos nosos outros tipos, que levan unha lista e modificar a lista en lugar

101
00:06:54,770 --> 00:06:58,740
ata chegar a unha lista ordenada, merge sort necesita un espazo adicional

102
00:06:58,740 --> 00:07:00,900
fundir dúas listas.

103
00:07:00,900 --> 00:07:04,690
Non podemos usar inmediatamente as listas que están sendo incorporadas para gardar a lista mesclada

104
00:07:04,690 --> 00:07:08,880
unha vez que poden substituír elementos que aínda precisan ser mescladas.

105
00:07:08,880 --> 00:07:13,540
Este espazo é un pouco de prezo, pero, xeralmente, non é razoable.

106
00:07:13,540 --> 00:07:15,330
E iso é todo para merge sort.

107
00:07:15,330 --> 00:07:18,490
>> O meu nome é Rob Bowden, e este é o CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- Selección e ordenación.

110
00:07:24,000 --> 00:07:25,880
[Risas]

111
00:07:25,880 --> 00:07:31,480
Ah, ten que ter iso tamén, porque eu mudei como eu estaba me presentando.

112
00:07:31,480 --> 00:07:35,680
Lista á esquerda. Iso foi un erro de dixitación.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] eu estraguei todo -

114
00:07:39,290 --> 00:07:41,190
[Risas]

115
00:07:41,190 --> 00:07:44,190
Eu non sei o que -