Discuter:Tri fusion

Un article de Wikipédia, l'encyclopédie libre.

	Tri fusion fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
Bon début	Cet article a été classé comme d'Avancement BD selon le Tableau d'évaluation du projet. (Voir les statistiques)
Faible	Cet article a été classé comme d'Importance faible selon le Tableau d'évaluation du projet. (Contester?)

[modifier] Suggestion de modification de l'implémentation Haskell

Je propose une version un peu différente de l'implémentation haskell :

tri []  =  []
tri [x] =  [x]
tri xs  =  fusion (tri ys) (tri zs)
    where (ys,zs) =  split xs 

          fusion a [] = a
          fusion [] b = b
          fusion a@(x:xs) b@(y:ys) | x <= y     = x : fusion xs b
                                | otherwise  = y : fusion a ys
          split [] = ([], [])
          split [a] = ([a], [])
          split (a:b:xs) = (a:as, b:bs)
              where (as, bs) = split xs

En gros, j'ai juste explicité le SplitAt, en utilisant un algorithme un peu différent. Je pense qu'elle serait plus instructive (pour savoir comment faire le split sans utiliser une fonction toute faite), et en plus elle me semble potentiellement plus efficace dans l'idée (un seul parcours de la liste au lieu de deux, un pour length et un pour split) (par contre, elle n'est pas récursive terminale pour des raisons de clarté).

Elle me semble donc préférable, mais n'étant pas un codeur haskell moi même j'ai préféré ne pas prendre l'initiative d'alourdir le code.

Bluestorm 2 mars 2007 à 17:55 (CET)

Je pense que l'intérêt de mettre une version Haskell de l'algorithme est d'en proposer une implémentation lisible, vu que le tri-fusion est loin d'être le mieux dans un lanage fonctionnel avec des listes chaînées. Je prèfere donc la version avec splitAt (length xs `div` 2) xs qui montre mieux qu'on prend deux moitiés de tableau pour les fusionner ensuite après les avoir trié. Lunar 2 mars 2007 à 18:25 (CET)