[Powered by Google Translate] [Fusionner Trier] [Rob Bowden - Université de Harvard] [C'est CS50. - CS50.TV] Parlons un peu de tri par fusion. Jusqu'ici, vous avez vu tri à bulles, tri par insertion, et une sorte de sélection. Bien que je vais sorte de vague ma main à ce que je veux dire par mieux, le tri par fusion effectue généralement mieux que n'importe lequel de ces 3 sortes. 

Mais avant de parler de tri par fusion, nous allons parler de la fusion de 2 listes triées. Nous allons appeler le processus de prise de 2 listes triées, comme ceux-ci, et de faire une liste unique triés d'entre eux - la fusion des listes. Comment pouvons-nous faire cela? Eh bien, une idée est de simplement coller une liste sur l'extrémité de l'autre liste et puis trier la liste obtenue. 

Bien que cela fonctionne, il ya beaucoup de travail inutile. Nous pouvons le faire plus rapidement qu'un simple tri. Notez qu'une mauvaise idée est de simplement prendre coupes en alternance dans chacune des listes. Bien que cela puisse sembler au premier abord que les travaux, fait que nous nous retrouvons avec 4, 8, 15, 23, 16 - notez que 16 et 23 sont hors de propos. C'est parce que les 2 éléments qui doivent apparaître consécutive dans la liste fusionnée sont dans la même liste initiale. Les deux 15 et 16 sont dans la liste de gauche. L'astuce consiste à profiter du fait que les deux listes sont déjà triés. Cela signifie que si nous suffit de regarder les premiers éléments des deux listes - ici, 4 et 8 - l'un d'eux doit être également le premier élément de la liste fusionnée. Eh bien, pourquoi est-ce? Ces deux listes sont déjà triés, et ainsi de 4 ou 8 doit être le plus petit élément lorsque nous combinons les 2 listes. Dans ce cas, le plus petit est de 4, afin que nous puissions prendre les 4 et en faire le premier élément de la liste fusionnée. Maintenant nous continuons de fusionner les 3 autres éléments de la première liste et 4 éléments de la deuxième liste. 

Une fois de plus, nous avons seulement besoin de regarder le premier élément de ces deux listes. Le plus petit des 2 doit être le deuxième élément de notre liste fusionnée. Cette fois-ci, entre 8 et 15 le plus petit est de 8, et nous avons donc insérer ce que le deuxième élément de notre liste triée. Nous pouvons continuer à comparer les premiers éléments de deux listes et enlever la plus petite de la 2. En comparant 15 et 23, 15 est plus petit et donc que c'est notre troisième élément. Maintenant comparant 16 et 23, 16 est plus petit. Donc, c'est le quatrième élément. 

Notez que 2 éléments provenaient de la même liste dans une rangée. C'est pourquoi la liste fusionnée ne peut pas simplement des éléments de rechange des 2 listes. En comparant 50 et 23, 23 est plus petit, de sorte que nous choisissons. Entre 50 et 42, 42 est plus petit. Entre 50 et 108, 50 est plus petit. Et, enfin, nous avons juste 108, donc il faut aller au bout de notre liste. Notez que nous avons une belle liste triée. Chaque fois que nous avons comparé les 2 premiers éléments des 2 listes nous avons été en mesure de déterminer l'élément suivant de la liste fusionnée. Cela signifie que si la liste finale contient les numéros de n, où n est ici 8, alors nous avons besoin dans la plupart des comparaisons n d'obtenir tous ces chiffres dans le bon endroit. Un tel algorithme est dit de courir en temps linéaire, mais ne vous inquiétez pas à ce sujet ici. 

Grâce à notre algorithme de fusion, nous pouvons faire un algorithme de tri rapide de fusion. Donc, nous allons remettre nos listes. Il ya 2 grandes étapes dans le processus de tri par fusion. Tout d'abord, en permanence diviser la liste en deux moitiés de tasses jusqu'à ce que nous avons un tas de listes avec juste 1 tasse en eux. Ne vous inquiétez pas si une liste contient un nombre impair et vous ne pouvez pas faire une coupe parfaitement propre entre eux. Juste choisir arbitrairement qui liste pour y inclure la tasse supplémentaire po Donc, nous allons diviser ces listes. Maintenant, nous avons 2 listes. Maintenant, nous avons 4 listes. 

Et maintenant, nous avons 8 listes avec une tasse unique dans chaque liste. Donc, c'est tout pour l'étape 1. Pour l'étape 2, nous avons à plusieurs reprises réunis des paires de listes en utilisant l'algorithme de fusion, nous avons appris avant. La fusion de 108 et 15, nous nous retrouvons avec la liste des 15, 108. La fusion de 50 et 4, on se retrouve avec 4, 50. La fusion de 8 et 42, on se retrouve avec 8, 42. Et la fusion 23 et 16, nous nous retrouvons avec 16, 23. Maintenant, tous nos listes sont de taille 2. Notez que chacun des 4 listes sont triées. 

Donc, nous pouvons commencer la fusion des paires de listes. La fusion de 15 et 108 et 4 et 50 - d'abord prendre le 4, puis le 15, puis le 50, puis le 108. La fusion de 8, 42 et 16, 23, nous avons d'abord prendre le 8, puis le 16, puis le 23, puis le 42. Donc maintenant nous avons seulement 2 listes de taille 4, dont chacune est triée. Alors maintenant, nous fusionnons ces 2 listes. Nous prenons d'abord le 4. Puis nous prenons le 8. Puis nous prenons le 15 et 16, puis 23, puis 42, puis 50, puis 108. Et c'est fait. Nous avons maintenant une liste triée. Alors, comment était-ce rapide, exactement? En termes techniques, le tri par fusion est en O (n log n), alors que toutes tri à bulles, tri par insertion, tri par sélection et sont en O (n ²). En fait, comme vous l'apprendrez bientôt, vous ne serez pas en mesure d'arriver à une sorte qui fonctionne mieux que O (n log n) dans le cas général. Encore une fois, ne vous inquiétez pas à propos de cette notation grand O si vous ne l'avez pas encore vu. 

Il suffit de savoir ce que cela signifie que si nous voulions trier une liste très gros tri tri à bulles, tri par insertion, et la sélection pourrait prendre significativement plus long que le tri par fusion. Cela ne signifie pas que le tri par fusion sera plus rapide pour toutes les listes ou même pour une liste unique sous une certaine taille. Par exemple, le tri par insertion peut être le plus rapide de tri pour toutes les listes de moins de 5 éléments. Dans la pratique, une sorte de fusion est généralement plus rapide pour les listes aussi petites que 50 éléments. 

Mais cette vitesse supplémentaire ne vient pas sans un prix. Contrairement à nos autres sortes, qui prend une liste et modifier la liste en place jusqu'à ce que nous obtenir une liste triée, tri par fusion besoin d'espace supplémentaire de fusionner 2 listes en même temps. Nous ne pouvons pas utiliser immédiatement les listes qui sont fusionnées pour stocker la liste fusionnée car on pourrait remplacer les éléments qui doivent encore être fusionnés. Cet espace est un peu d'un prix, mais il n'est généralement pas déraisonnable. Et c'est tout pour le tri par fusion. 

Mon nom est Rob Bowden, et c'est CS50. [CS50.TV] - Et la sélection sorte. [Rires] Oh, que dois prendre trop parce que je suis passé comment je me la présenter. Liste sur la gauche. C'était une faute de frappe. [Lapsus] J'ai foiré - [Rires] Je ne sais pas ce que -