Tri par Fusion en Javascript

Tri par Fusion s’exécute en temps O (n log n). C’est très efficace. Tri par Fusion est un algorithme récursif utilisé pour la fusion qui repose sur la technique Diviser pour Régner. Un tableau d’éléments est divisé en deux sous tableaux plus petits. Une fois ces deux tableaux libérés indépendamment, ils sont en mesure de produire le tableau trié. Le processus de fusion peut être effectué de manière récursive jusqu’à ce qu’il n’y ait qu’un seul élément dans le tableau.
 
 

L’algorithme :

sort(tab[], g, d)
Si d > g
   1. Trouvez le milieu pour diviser le tableau en deux moitiés m = (g + d) / 2.
   2. Appelez la méthode sort pour la première moitié.
   3. Appelez la méthode sort pour la seconde moitié.
   4. Fusionnez les deux moitiés triées aux étapes 2 et 3.

Exemple :

L’implémentation de l’algorithme de tri par Fusion en Javascript

function merge(left, right){
	
    var tab = [], l = 0, r = 0;

    while (l < left.length && r < right.length){
        if (left[l] < right[r]){
            tab.push(left[l++]);
        } else {
            tab.push(right[r++]);
        }
    }
    return tab.concat(left.slice(l)).concat(right.slice(r));
}

function sort(tab){

    if (tab.length < 2) {
        return tab;
    }

    var mid = Math.floor(tab.length / 2),
        right = tab.slice(mid),
        left = tab.slice(0, mid),
        p = merge(sort(left), sort(right));
    
    p.unshift(0, tab.length);
    tab.splice.apply(tab, p);
    return tab;
}

var tab = [5, 8, 11, 6, 1, 9, 3];
sort(tab);
console.log(tab);

La sortie :

[1, 3, 5, 6, 8, 9, 11]

La fonction merge() fusionne deux tableaux, « left » et « right ». La variable « l » garde la trace de l’index à comparer pour le tableau « left » alors que la variable « r » fait la même chose pour le tableau « right ». Chaque fois qu’une valeur est ajoutée au tableau, sa variable d’index correspondante est incrémentée. Dès que l’un des tableaux est épuisé, les valeurs restantes sont ajoutées à la fin du tableau « tab » à l’aide de concat() dans la ligne 12.

La fonction merge() est assez simple, mais vous devez combiner les deux tableaux triées. Comme mentionné précédemment, cela se fait en divisant le tableau en plusieurs tableau, puis en les combinant systématiquement. Ceci est facilement fait en utilisant un algorithme récursif comme il est mentionné dans la fonction sort().

La fonction sort() stocke les résultats du tri dans une variable appelée « p ». Le meilleur moyen de remplacer des éléments dans un tableau consiste à utiliser la méthode splice(), qui accepte deux arguments ou plus. Le premier argument est l’indice de la première valeur à remplacer et le deuxième argument est le nombre de valeurs à remplacer. L’argument suivant est la valeur à insérer à cette position. Puisqu’il n’y a aucun moyen de passer un tableau de valeurs dans splice(), vous devez utiliser apply() et transmettre les deux premiers arguments combinés avec le tableau trié.