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

4
00:00:07,000 --> 00:00:09,000
Parlem de tipus de mescla.

5
00:00:09,000 --> 00:00:14,000
Fins ara hem vist espècie de bombolla, ordenació per inserció, i una mena de selecció.

6
00:00:14,000 --> 00:00:17,000
Encara Vaig tipus d'ona meva mà en el que vull dir millor,

7
00:00:17,000 --> 00:00:21,000
merge sort generalment funciona millor que qualsevol d'aquests tres tipus.

8
00:00:22,000 --> 00:00:27,000
>> Però abans de parlar de tipus de mescla, parlarem de la fusió de dues llistes ordenades.

9
00:00:27,000 --> 00:00:31,000
L'anomenarem el procés de prendre 2 llistes ordenades, com aquests,

10
00:00:31,000 --> 00:00:35,000
i fer una única llista ordenada d'ells - la fusió de les llistes.

11
00:00:35,000 --> 00:00:37,750
Com podem fer això?

12
00:00:37,750 --> 00:00:41,290
Bé, una idea és seguir una sola llista a l'extrem de l'altra llista

13
00:00:41,290 --> 00:00:43,830
i després ordenar la llista de resultats.

14
00:00:43,830 --> 00:00:47,220
>> Si bé això funciona, és una gran quantitat de treball innecessari.

15
00:00:47,220 --> 00:00:49,900
Podem fer-ho més ràpid que un simple classificació.

16
00:00:49,900 --> 00:00:54,100
Tingueu en compte que una idea equivocada consisteix en prendre copes alternats de cada llista.

17
00:00:54,100 --> 00:00:56,460
Si bé això pot semblar que funciona al principi,

18
00:00:56,460 --> 00:01:05,760
fent que ens trobem amb 4, 8, 15, 23, 16 - Anunci que el 16 i 23 estan fora de lloc.

19
00:01:05,760 --> 00:01:09,380
Això es deu a dos elements que han d'aparèixer consecutiu a la llista resultant de la fusió

20
00:01:09,380 --> 00:01:11,720
són a la llista inicial igual.

21
00:01:11,720 --> 00:01:14,850
Tant el 15 i 16 estan en la llista de l'esquerra.

22
00:01:14,850 --> 00:01:19,810
El truc consisteix en aprofitar el fet que les dues llistes ja estan ordenats.

23
00:01:19,810 --> 00:01:23,320
Això vol dir que si ens fixem en els primers elements de les dues llistes -

24
00:01:23,320 --> 00:01:29,580
aquí, 4 i 8 - un d'ells ha de ser també el primer element de la llista combinada.

25
00:01:29,580 --> 00:01:31,620
Bé, per què és això?

26
00:01:31,620 --> 00:01:33,520
Ambdues llistes ja estan ordenats,

27
00:01:33,520 --> 00:01:38,410
i per tant ja sigui de 4 o 8 ha de ser l'element més petit quan combinem les dues llistes.

28
00:01:38,410 --> 00:01:41,770
En aquest cas, el més petit és 4,

29
00:01:41,770 --> 00:01:46,370
pel que podem treure 4 i convertir-lo en el primer element de la llista combinada.

30
00:01:46,370 --> 00:01:50,710
Ara continuem la fusió dels 3 restants elements de la primera llista

31
00:01:50,710 --> 00:01:52,920
i 4 elements de la segona llista.

32
00:01:52,920 --> 00:01:57,150
>> Un cop més, només hem de mirar el primer element de les dues llistes.

33
00:01:57,150 --> 00:02:01,060
El menor dels 2 ha de ser el segon element de la llista combinada.

34
00:02:01,060 --> 00:02:05,440
Aquesta vegada, entre el 8 i el 15 el més petit és de 8, de manera que inserir aquest

35
00:02:05,440 --> 00:02:09,240
com el segon element de la llista ordenada.

36
00:02:09,240 --> 00:02:12,180
Podem seguir comparant els primers elements de les dues llistes

37
00:02:12,180 --> 00:02:14,420
i l'eliminació de la menor de les 2.

38
00:02:14,420 --> 00:02:19,460
Comparant els 15 i 23 15, és més petit i per tant aquest és el nostre tercer element.

39
00:02:21,000 --> 00:02:23,910
Ara comparant 16 i 23, 16 és més petit.

40
00:02:23,910 --> 00:02:26,820
Així que aquest és el quart element.

41
00:02:26,820 --> 00:02:30,390
>> Tingueu en compte que dos elements provenien de la mateixa llista en una fila.

42
00:02:30,390 --> 00:02:34,400
Per això, la llista resultant de la fusió no pot simplement elements alternatius a partir de les 2 llistes.

43
00:02:34,400 --> 00:02:40,020
Comparant els 50 i 23, 23 és més petit, així que triem això.

44
00:02:40,770 --> 00:02:44,070
Entre 50 i 42, 42 és més petit.

45
00:02:44,070 --> 00:02:48,290
Entre 50 i 108, 50 és més petit.

46
00:02:48,290 --> 00:02:52,330
I, finalment, només tenim 108, per la qual cosa ha d'anar al final de la nostra llista.

47
00:02:53,750 --> 00:02:56,180
Recordeu que tenim una bona llista, ordenada.

48
00:02:56,180 --> 00:02:59,040
Cada vegada que es van comparar els primer 2 elements de les llistes 2

49
00:02:59,040 --> 00:03:02,730
hem estat capaços de determinar el següent element de la llista combinada.

50
00:03:02,730 --> 00:03:08,070
Això vol dir que si la llista final conté un nombre n, on n és aquí 8,

51
00:03:08,070 --> 00:03:12,610
llavors tenim que en la majoria de les comparacions n per obtenir tots els nombres en el lloc correcte.

52
00:03:13,230 --> 00:03:16,230
Tal algorisme es diu que s'executen en temps lineal,

53
00:03:16,230 --> 00:03:18,090
però no et preocupis per això aquí.

54
00:03:18,570 --> 00:03:22,810
>> Usant el nostre algorisme per a la fusió, podem fer un ràpid algorisme de combinació tipus.

55
00:03:22,810 --> 00:03:25,170
Per tant, anem a restablir les nostres llistes.

56
00:03:35,210 --> 00:03:37,750
Hi ha 2 grans passos en el procés de l'espècie de barreja.

57
00:03:37,750 --> 00:03:41,500
En primer lloc, contínuament dividir la llista de copes en dues meitats

58
00:03:41,500 --> 00:03:44,860
fins que tinguem un munt de llistes amb només 1 tassa-hi.

59
00:03:44,860 --> 00:03:47,350
No et preocupis si una llista conté un nombre imparell

60
00:03:47,350 --> 00:03:49,880
i no es pot fer un tall perfectament net entre ells.

61
00:03:49,880 --> 00:03:53,750
Només arbitràriament escollir quina voleu incloure la tassa extra cm

62
00:03:53,750 --> 00:03:56,240
Per tant, anem a dividir aquestes llistes.

63
00:03:58,140 --> 00:04:01,310
Ara tenim 2 llistes.

64
00:04:04,120 --> 00:04:06,570
Ara tenim 4 llistes.

65
00:04:10,350 --> 00:04:13,870
>> I ara tenim 8 llistes amb una sola tassa a cada llista.

66
00:04:13,870 --> 00:04:16,630
Així que això és tot pel pas 1.

67
00:04:16,630 --> 00:04:22,230
Per al pas 2, repetidament barreja parells de llistes usant l'algorisme de fusió que hem après abans.

68
00:04:22,230 --> 00:04:29,160
La fusió de 108 i 15, ens trobem amb la llista de 15, 108.

69
00:04:30,330 --> 00:04:36,250
La fusió de 50 i 4, ens trobem amb 4, 50.

70
00:04:36,960 --> 00:04:41,400
La fusió de 8 i 42, vam acabar amb 8, 42.

71
00:04:42,790 --> 00:04:48,130
I la fusió de 23 i 16, vam acabar amb 16, 23.

72
00:04:49,740 --> 00:04:52,450
Ara totes les nostres llistes són de mida 2.

73
00:04:53,020 --> 00:04:56,180
Observeu que cadascuna de les 4 llistes està ordenada.

74
00:04:56,180 --> 00:04:59,160
>> Així que podem començar la fusió de parells de llistes de nou.

75
00:04:59,160 --> 00:05:03,240
La fusió de 15 i 108 i 4 i 50 -

76
00:05:03,240 --> 00:05:11,170
primer prendre la 4, a continuació, la 15, la 50, llavors el 108.

77
00:05:11,170 --> 00:05:15,120
La fusió de 8, 42 i 16, 23,

78
00:05:15,120 --> 00:05:22,440
en primer lloc assumir el 8, el 16, després el 23, després el 42.

79
00:05:22,440 --> 00:05:27,370
Així que ara tenim només 2 llistes de mida 4, cada un dels quals està ordenada.

80
00:05:27,370 --> 00:05:30,980
Així que ara ens fusionem aquestes dues llistes.

81
00:05:30,980 --> 00:05:33,440
En primer lloc, prendre la 4.

82
00:05:33,440 --> 00:05:36,580
Després prenem el 8.

83
00:05:36,580 --> 00:05:50,700
Llavors es pren el 15 i el 16, i després 23, després 42, després 50, després 108.

84
00:05:50,700 --> 00:05:52,220
I hem acabat.

85
00:05:52,220 --> 00:05:54,900
Ara tenim una llista ordenada.

86
00:05:54,900 --> 00:05:57,890
Així ho ràpid que era això, exactament?

87
00:05:57,890 --> 00:06:02,000
En termes tècnics, una espècie de combinació és O (n log n),

88
00:06:02,000 --> 00:06:07,380
mentre que tots els de tipus bombolla, ordenació per inserció, i una mena de selecció són O (n ²).

89
00:06:07,380 --> 00:06:11,120
De fet, com vostè aprendrà aviat, vostè no serà capaç d'arribar a una espècie

90
00:06:11,120 --> 00:06:14,820
que es comporta millor que O (n log n) en el cas general.

91
00:06:14,820 --> 00:06:19,120
Un cop més, no es preocupi per aquesta notació gran O si vostè no ho ha vist encara.

92
00:06:19,120 --> 00:06:23,490
>> Només que sàpigues que això vol dir que si volíem ordenar una llista molt gran

93
00:06:23,490 --> 00:06:26,820
espècie tipus bombolla, ordenació per inserció, i la selecció podria prendre

94
00:06:26,820 --> 00:06:29,500
significativament més llarg que merge sort.

95
00:06:29,500 --> 00:06:33,210
Això no vol dir que aquest tipus de barreja serà més ràpid per a totes les llistes

96
00:06:33,210 --> 00:06:36,220
o fins i tot per a qualsevol llista única sota una certa grandària.

97
00:06:36,220 --> 00:06:41,950
Per exemple, el tipus d'inserció pot ser el més ràpid de classificació de totes les llistes de menors de 5 elements.

98
00:06:41,950 --> 00:06:47,360
A la pràctica, una mena de combinació és generalment més ràpid per les llistes de només 50 elements.

99
00:06:47,360 --> 00:06:51,120
>> No obstant això, aquesta velocitat extra no ve sense un preu.

100
00:06:51,120 --> 00:06:54,770
A diferència dels nostres altres gèneres, que tenen una llista i modificar la llista al seu lloc

101
00:06:54,770 --> 00:06:58,740
fins que tinguem una llista ordenada, una mena de barreja necessita una mica d'espai addicional

102
00:06:58,740 --> 00:07:00,900
per fusionar 2 llistes.

103
00:07:00,900 --> 00:07:04,690
No es pot utilitzar immediatament les llistes que es van fusionar per emmagatzemar la llista resultant de la fusió

104
00:07:04,690 --> 00:07:08,880
ja que poden anul · lar els elements que encara han de ser combinades.

105
00:07:08,880 --> 00:07:13,540
Aquest espai és una mica d'un preu, però en general no és irraonable.

106
00:07:13,540 --> 00:07:15,330
I això és tot per tipus de mescla.

107
00:07:15,330 --> 00:07:18,490
>> El meu nom és Rob Bowden, i això és CS50.

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

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

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

111
00:07:25,880 --> 00:07:31,480
Oh, he de prendre això també perquè em vaig canviar com ho estava presentant.

112
00:07:31,480 --> 00:07:35,680
Llista de l'esquerra. Això va ser un error.

113
00:07:35,680 --> 00:07:39,290
[Equivocar al parlar] Vaig cometre un error -

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

115
00:07:41,190 --> 00:07:44,190
No sé per què -