1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Fusionner Trier]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Université de Harvard]

3
00:00:04,000 --> 00:00:07,000
[C'est CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Parlons un peu de tri par fusion.

5
00:00:09,000 --> 00:00:14,000
Jusqu'ici, vous avez vu tri à bulles, tri par insertion, et une sorte de sélection.

6
00:00:14,000 --> 00:00:17,000
Bien que je vais sorte de vague ma main à ce que je veux dire par mieux,

7
00:00:17,000 --> 00:00:21,000
le tri par fusion effectue généralement mieux que n'importe lequel de ces 3 sortes.

8
00:00:22,000 --> 00:00:27,000
>> Mais avant de parler de tri par fusion, nous allons parler de la fusion de 2 listes triées.

9
00:00:27,000 --> 00:00:31,000
Nous allons appeler le processus de prise de 2 listes triées, comme ceux-ci,

10
00:00:31,000 --> 00:00:35,000
et de faire une liste unique triés d'entre eux - la fusion des listes.

11
00:00:35,000 --> 00:00:37,750
Comment pouvons-nous faire cela?

12
00:00:37,750 --> 00:00:41,290
Eh bien, une idée est de simplement coller une liste sur l'extrémité de l'autre liste

13
00:00:41,290 --> 00:00:43,830
et puis trier la liste obtenue.

14
00:00:43,830 --> 00:00:47,220
>> Bien que cela fonctionne, il ya beaucoup de travail inutile.

15
00:00:47,220 --> 00:00:49,900
Nous pouvons le faire plus rapidement qu'un simple tri.

16
00:00:49,900 --> 00:00:54,100
Notez qu'une mauvaise idée est de simplement prendre coupes en alternance dans chacune des listes.

17
00:00:54,100 --> 00:00:56,460
Bien que cela puisse sembler au premier abord que les travaux,

18
00:00:56,460 --> 00:01:05,760
fait que nous nous retrouvons avec 4, 8, 15, 23, 16 - notez que 16 et 23 sont hors de propos.

19
00:01:05,760 --> 00:01:09,380
C'est parce que les 2 éléments qui doivent apparaître consécutive dans la liste fusionnée

20
00:01:09,380 --> 00:01:11,720
sont dans la même liste initiale.

21
00:01:11,720 --> 00:01:14,850
Les deux 15 et 16 sont dans la liste de gauche.

22
00:01:14,850 --> 00:01:19,810
L'astuce consiste à profiter du fait que les deux listes sont déjà triés.

23
00:01:19,810 --> 00:01:23,320
Cela signifie que si nous suffit de regarder les premiers éléments des deux listes -

24
00:01:23,320 --> 00:01:29,580
ici, 4 et 8 - l'un d'eux doit être également le premier élément de la liste fusionnée.

25
00:01:29,580 --> 00:01:31,620
Eh bien, pourquoi est-ce?

26
00:01:31,620 --> 00:01:33,520
Ces deux listes sont déjà triés,

27
00:01:33,520 --> 00:01:38,410
et ainsi de 4 ou 8 doit être le plus petit élément lorsque nous combinons les 2 listes.

28
00:01:38,410 --> 00:01:41,770
Dans ce cas, le plus petit est de 4,

29
00:01:41,770 --> 00:01:46,370
afin que nous puissions prendre les 4 et en faire le premier élément de la liste fusionnée.

30
00:01:46,370 --> 00:01:50,710
Maintenant nous continuons de fusionner les 3 autres éléments de la première liste

31
00:01:50,710 --> 00:01:52,920
et 4 éléments de la deuxième liste.

32
00:01:52,920 --> 00:01:57,150
>> Une fois de plus, nous avons seulement besoin de regarder le premier élément de ces deux listes.

33
00:01:57,150 --> 00:02:01,060
Le plus petit des 2 doit être le deuxième élément de notre liste fusionnée.

34
00:02:01,060 --> 00:02:05,440
Cette fois-ci, entre 8 et 15 le plus petit est de 8, et nous avons donc insérer ce

35
00:02:05,440 --> 00:02:09,240
que le deuxième élément de notre liste triée.

36
00:02:09,240 --> 00:02:12,180
Nous pouvons continuer à comparer les premiers éléments de deux listes

37
00:02:12,180 --> 00:02:14,420
et enlever la plus petite de la 2.

38
00:02:14,420 --> 00:02:19,460
En comparant 15 et 23, 15 est plus petit et donc que c'est notre troisième élément.

39
00:02:21,000 --> 00:02:23,910
Maintenant comparant 16 et 23, 16 est plus petit.

40
00:02:23,910 --> 00:02:26,820
Donc, c'est le quatrième élément.

41
00:02:26,820 --> 00:02:30,390
>> Notez que 2 éléments provenaient de la même liste dans une rangée.

42
00:02:30,390 --> 00:02:34,400
C'est pourquoi la liste fusionnée ne peut pas simplement des éléments de rechange des 2 listes.

43
00:02:34,400 --> 00:02:40,020
En comparant 50 et 23, 23 est plus petit, de sorte que nous choisissons.

44
00:02:40,770 --> 00:02:44,070
Entre 50 et 42, 42 est plus petit.

45
00:02:44,070 --> 00:02:48,290
Entre 50 et 108, 50 est plus petit.

46
00:02:48,290 --> 00:02:52,330
Et, enfin, nous avons juste 108, donc il faut aller au bout de notre liste.

47
00:02:53,750 --> 00:02:56,180
Notez que nous avons une belle liste triée.

48
00:02:56,180 --> 00:02:59,040
Chaque fois que nous avons comparé les 2 premiers éléments des 2 listes

49
00:02:59,040 --> 00:03:02,730
nous avons été en mesure de déterminer l'élément suivant de la liste fusionnée.

50
00:03:02,730 --> 00:03:08,070
Cela signifie que si la liste finale contient les numéros de n, où n est ici 8,

51
00:03:08,070 --> 00:03:12,610
alors nous avons besoin dans la plupart des comparaisons n d'obtenir tous ces chiffres dans le bon endroit.

52
00:03:13,230 --> 00:03:16,230
Un tel algorithme est dit de courir en temps linéaire,

53
00:03:16,230 --> 00:03:18,090
mais ne vous inquiétez pas à ce sujet ici.

54
00:03:18,570 --> 00:03:22,810
>> Grâce à notre algorithme de fusion, nous pouvons faire un algorithme de tri rapide de fusion.

55
00:03:22,810 --> 00:03:25,170
Donc, nous allons remettre nos listes.

56
00:03:35,210 --> 00:03:37,750
Il ya 2 grandes étapes dans le processus de tri par fusion.

57
00:03:37,750 --> 00:03:41,500
Tout d'abord, en permanence diviser la liste en deux moitiés de tasses

58
00:03:41,500 --> 00:03:44,860
jusqu'à ce que nous avons un tas de listes avec juste 1 tasse en eux.

59
00:03:44,860 --> 00:03:47,350
Ne vous inquiétez pas si une liste contient un nombre impair

60
00:03:47,350 --> 00:03:49,880
et vous ne pouvez pas faire une coupe parfaitement propre entre eux.

61
00:03:49,880 --> 00:03:53,750
Juste choisir arbitrairement qui liste pour y inclure la tasse supplémentaire po

62
00:03:53,750 --> 00:03:56,240
Donc, nous allons diviser ces listes.

63
00:03:58,140 --> 00:04:01,310
Maintenant, nous avons 2 listes.

64
00:04:04,120 --> 00:04:06,570
Maintenant, nous avons 4 listes.

65
00:04:10,350 --> 00:04:13,870
>> Et maintenant, nous avons 8 listes avec une tasse unique dans chaque liste.

66
00:04:13,870 --> 00:04:16,630
Donc, c'est tout pour l'étape 1.

67
00:04:16,630 --> 00:04:22,230
Pour l'étape 2, nous avons à plusieurs reprises réunis des paires de listes en utilisant l'algorithme de fusion, nous avons appris avant.

68
00:04:22,230 --> 00:04:29,160
La fusion de 108 et 15, nous nous retrouvons avec la liste des 15, 108.

69
00:04:30,330 --> 00:04:36,250
La fusion de 50 et 4, on se retrouve avec 4, 50.

70
00:04:36,960 --> 00:04:41,400
La fusion de 8 et 42, on se retrouve avec 8, 42.

71
00:04:42,790 --> 00:04:48,130
Et la fusion 23 et 16, nous nous retrouvons avec 16, 23.

72
00:04:49,740 --> 00:04:52,450
Maintenant, tous nos listes sont de taille 2.

73
00:04:53,020 --> 00:04:56,180
Notez que chacun des 4 listes sont triées.

74
00:04:56,180 --> 00:04:59,160
>> Donc, nous pouvons commencer la fusion des paires de listes.

75
00:04:59,160 --> 00:05:03,240
La fusion de 15 et 108 et 4 et 50 -

76
00:05:03,240 --> 00:05:11,170
d'abord prendre le 4, puis le 15, puis le 50, puis le 108.

77
00:05:11,170 --> 00:05:15,120
La fusion de 8, 42 et 16, 23,

78
00:05:15,120 --> 00:05:22,440
nous avons d'abord prendre le 8, puis le 16, puis le 23, puis le 42.

79
00:05:22,440 --> 00:05:27,370
Donc maintenant nous avons seulement 2 listes de taille 4, dont chacune est triée.

80
00:05:27,370 --> 00:05:30,980
Alors maintenant, nous fusionnons ces 2 listes.

81
00:05:30,980 --> 00:05:33,440
Nous prenons d'abord le 4.

82
00:05:33,440 --> 00:05:36,580
Puis nous prenons le 8.

83
00:05:36,580 --> 00:05:50,700
Puis nous prenons le 15 et 16, puis 23, puis 42, puis 50, puis 108.

84
00:05:50,700 --> 00:05:52,220
Et c'est fait.

85
00:05:52,220 --> 00:05:54,900
Nous avons maintenant une liste triée.

86
00:05:54,900 --> 00:05:57,890
Alors, comment était-ce rapide, exactement?

87
00:05:57,890 --> 00:06:02,000
En termes techniques, le tri par fusion est en O (n log n),

88
00:06:02,000 --> 00:06:07,380
alors que toutes tri à bulles, tri par insertion, tri par sélection et sont en O (n ²).

89
00:06:07,380 --> 00:06:11,120
En fait, comme vous l'apprendrez bientôt, vous ne serez pas en mesure d'arriver à une sorte

90
00:06:11,120 --> 00:06:14,820
qui fonctionne mieux que O (n log n) dans le cas général.

91
00:06:14,820 --> 00:06:19,120
Encore une fois, ne vous inquiétez pas à propos de cette notation grand O si vous ne l'avez pas encore vu.

92
00:06:19,120 --> 00:06:23,490
>> Il suffit de savoir ce que cela signifie que si nous voulions trier une liste très gros

93
00:06:23,490 --> 00:06:26,820
tri tri à bulles, tri par insertion, et la sélection pourrait prendre

94
00:06:26,820 --> 00:06:29,500
significativement plus long que le tri par fusion.

95
00:06:29,500 --> 00:06:33,210
Cela ne signifie pas que le tri par fusion sera plus rapide pour toutes les listes

96
00:06:33,210 --> 00:06:36,220
ou même pour une liste unique sous une certaine taille.

97
00:06:36,220 --> 00:06:41,950
Par exemple, le tri par insertion peut être le plus rapide de tri pour toutes les listes de moins de 5 éléments.

98
00:06:41,950 --> 00:06:47,360
Dans la pratique, une sorte de fusion est généralement plus rapide pour les listes aussi petites que 50 éléments.

99
00:06:47,360 --> 00:06:51,120
>> Mais cette vitesse supplémentaire ne vient pas sans un prix.

100
00:06:51,120 --> 00:06:54,770
Contrairement à nos autres sortes, qui prend une liste et modifier la liste en place

101
00:06:54,770 --> 00:06:58,740
jusqu'à ce que nous obtenir une liste triée, tri par fusion besoin d'espace supplémentaire

102
00:06:58,740 --> 00:07:00,900
de fusionner 2 listes en même temps.

103
00:07:00,900 --> 00:07:04,690
Nous ne pouvons pas utiliser immédiatement les listes qui sont fusionnées pour stocker la liste fusionnée

104
00:07:04,690 --> 00:07:08,880
car on pourrait remplacer les éléments qui doivent encore être fusionnés.

105
00:07:08,880 --> 00:07:13,540
Cet espace est un peu d'un prix, mais il n'est généralement pas déraisonnable.

106
00:07:13,540 --> 00:07:15,330
Et c'est tout pour le tri par fusion.

107
00:07:15,330 --> 00:07:18,490
>> Mon nom est Rob Bowden, et c'est CS50.

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

109
00:07:20,500 --> 00:07:24,000
- Et la sélection sorte.

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

111
00:07:25,880 --> 00:07:31,480
Oh, que dois prendre trop parce que je suis passé comment je me la présenter.

112
00:07:31,480 --> 00:07:35,680
Liste sur la gauche. C'était une faute de frappe.

113
00:07:35,680 --> 00:07:39,290
[Lapsus] J'ai foiré -

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

115
00:07:41,190 --> 00:07:44,190
Je ne sais pas ce que -