Tri par Fusion en JavaScript : Une approche efficace pour organiser des données

Le tri par fusion en JavaScript, aussi appelé Merge Sort, est un algorithme fondamental pour comprendre la récursivité, la division d’un problème en sous-problèmes et l’organisation efficace des données. Cette page explique son fonctionnement, son code, sa logique étape par étape et propose un simulateur pour tester différents tableaux.

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const middle = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, middle));
  const right = mergeSort(arr.slice(middle));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

Principe de fonctionnement

L'algorithme de tri par fusion suit un processus récursif pour trier un tableau. Voici les étapes de base de son fonctionnement :

1. Diviser : Diviser récursivement le tableau non trié en deux moitiés jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément.
2. Fusionner : Fusionner les sous-tableaux triés pour produire un tableau trié. Cela implique de comparer les éléments des deux sous-tableaux et de les fusionner dans un ordre trié.

Le processus de division et de fusion se poursuit jusqu'à ce que le tableau soit complètement trié.

Implémentation en JavaScript

Voici une implémentation simple de l'algorithme de tri par fusion en JavaScript :

function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

function mergeSort(array) {
    if (array.length <= 1) {
        return array;
    }

    const middle = Math.floor(array.length / 2);
    const left = array.slice(0, middle);
    const right = array.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

Cette implémentation utilise deux fonctions : merge et mergeSort.

• La fonction merge prend deux tableaux triés left et right et les fusionne en un seul tableau trié.
• La fonction mergeSort utilise la récursivité pour diviser le tableau en deux moitiés, puis appelle la fonction merge pour fusionner les sous-tableaux triés.

Exemple d'utilisation

Voici comment utiliser cette implémentation de tri par fusion sur un tableau :

const array = [5, 3, 8, 4, 2, 7, 1];
console.log("Array avant le tri :", array);
const sortedArray = mergeSort(array);
console.log("Array après le tri :", sortedArray);

Complexité

La complexité temporelle du tri par fusion est de O(n log n) dans tous les cas, ce qui en fait l'un des algorithmes de tri les plus efficaces. La complexité spatiale est de O(n), car l'algorithme nécessite de stocker les sous-tableaux lors de la division.

Voici comment nous pourrions illustrer quelques exemples d'application du tri par fusion en JavaScript à travers du code :

// Exemple 1 : Traitement de données dans les applications web
const userData = ['Alice', 'Bob', 'Charlie', 'David', 'Eve'];
const sortedUserData = mergeSort(userData);
console.log("Données des utilisateurs triées :", sortedUserData);

// Exemple 2 : Algorithmes de recherche et de filtrage
const searchResults = ['Résultat 3', 'Résultat 1', 'Résultat 2', 'Résultat 4'];
const sortedSearchResults = mergeSort(searchResults);
console.log("Résultats de recherche triés :", sortedSearchResults);

// Exemple 3 : Gestion de données dans les applications de commerce électronique
const productPrices = [19.99, 9.99, 29.99, 14.99];
const sortedProductPrices = mergeSort(productPrices);
console.log("Prix des produits triés :", sortedProductPrices);

// Exemple 4 : Visualisation de données
const monthlySales = [1000, 500, 1500, 2000, 800];
const sortedMonthlySales = mergeSort(monthlySales);
console.log("Ventes mensuelles triées :", sortedMonthlySales);

// Exemple 5 : Traitement de données dans les jeux
const playerScores = [1500, 1200, 1800, 900, 2000];
const sortedPlayerScores = mergeSort(playerScores);
console.log("Scores des joueurs triés :", sortedPlayerScores);

Ces exemples démontrent comment le tri par fusion peut être utilisé pour trier différentes structures de données dans des applications JavaScript, améliorant ainsi leur efficacité et leur lisibilité.

Voici quelques cas particuliers à considérer lors de l'implémentation du tri par fusion en JavaScript, avec des exemples de code :

1. Tableau déjà trié ou partiellement trié :

Si le tableau à trier est déjà trié ou partiellement trié, cela peut affecter les performances du tri par fusion. Par exemple, un tableau déjà trié pourrait entraîner une réduction du nombre de comparaisons nécessaires, tandis qu'un tableau partiellement trié pourrait encore nécessiter un temps linéaire pour la fusion.

// Tableau déjà trié
const sortedArray = [1, 2, 3, 4, 5];
console.log("Avant le tri :", sortedArray);
const sortedArrayAfterMergeSort = mergeSort(sortedArray);
console.log("Après le tri :", sortedArrayAfterMergeSort);

2. Taille du tableau :

La taille du tableau peut influencer les performances du tri par fusion. Pour de petits tableaux, le coût supplémentaire de la récursivité peut devenir significatif. En revanche, pour de très grands tableaux, le tri par fusion peut être plus efficace que d'autres méthodes de tri.

// Tableau de taille réduite
const smallArray = [5, 3, 8, 4];
console.log("Avant le tri :", smallArray);
const smallArrayAfterMergeSort = mergeSort(smallArray);
console.log("Après le tri :", smallArrayAfterMergeSort);

// Tableau de grande taille
const largeArray = Array.from({ length: 10000 }, () => Math.floor(Math.random() * 10000));
console.time("mergeSort");
const largeArrayAfterMergeSort = mergeSort(largeArray);
console.timeEnd("mergeSort");

3. Éléments dupliqués :

La présence d'éléments dupliqués dans le tableau peut nécessiter une gestion particulière lors de l'implémentation du tri par fusion, notamment pour éviter les erreurs d'ordre ou les boucles infinies.

const arrayWithDuplicates = [5, 3, 8, 4, 3, 7, 1];
console.log("Avant le tri :", arrayWithDuplicates);
const arrayWithDuplicatesAfterMergeSort = mergeSort(arrayWithDuplicates);
console.log("Après le tri :", arrayWithDuplicatesAfterMergeSort);

En tenant compte de ces cas particuliers lors de l'implémentation du tri par fusion en JavaScript, vous pouvez garantir que votre algorithme de tri fonctionne de manière fiable dans une variété de situations.

Exemples avancés qui démontrent des fonctionnalités plus avancées ou des applications spécifiques du tri par fusion en JavaScript :

1. Tri par fusion générique pour différents types de données :

Vous pouvez rendre votre fonction de tri par fusion générique en acceptant une fonction de comparaison en tant que paramètre. Cela permet de trier des tableaux contenant différents types de données ou de trier des tableaux selon des critères personnalisés.

function mergeSort(array, compareFunction) {
    if (array.length <= 1) {
        return array;
    }

    const middle = Math.floor(array.length / 2);
    const left = array.slice(0, middle);
    const right = array.slice(middle);

    return merge(mergeSort(left, compareFunction), mergeSort(right, compareFunction), compareFunction);
}

function merge(left, right, compareFunction) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (compareFunction(left[leftIndex], right[rightIndex]) < 0) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Exemple d'utilisation avec un tableau de chaînes de caractères triées par longueur
const strings = ['apple', 'banana', 'pear', 'orange', 'grape'];
const sortedStrings = mergeSort(strings, (a, b) => a.length - b.length);
console.log("Chaînes de caractères triées par longueur :", sortedStrings);

2. Tri par fusion asynchrone pour de grandes quantités de données :

Pour traiter de très grands ensembles de données de manière efficace, vous pouvez implémenter une version asynchrone du tri par fusion en utilisant des opérations asynchrones telles que des promesses ou des callbacks. Cela permet de répartir la charge de travail sur plusieurs itérations, améliorant ainsi les performances.

async function asyncMergeSort(array) {
    if (array.length <= 1) {
        return array;
    }

    const middle = Math.floor(array.length / 2);
    const left = array.slice(0, middle);
    const right = array.slice(middle);

    const [sortedLeft, sortedRight] = await Promise.all([
        asyncMergeSort(left),
        asyncMergeSort(right)
    ]);

    return merge(sortedLeft, sortedRight);
}

// Exemple d'utilisation avec un grand tableau de nombres
const bigArray = Array.from({ length: 1000000 }, () => Math.floor(Math.random() * 1000000));
console.time("asyncMergeSort");
asyncMergeSort(bigArray).then(sortedArray => {
    console.timeEnd("asyncMergeSort");
    console.log("Tableau trié :", sortedArray);
});

Ces exemples avancés mettent en évidence la flexibilité et la puissance du tri par fusion en JavaScript, ainsi que sa capacité à être adapté à des besoins spécifiques ou à des contraintes de performance particulières.

Conclusion

Le tri par fusion est un algorithme de tri puissant et efficace qui trouve de nombreuses applications dans le domaine de l'informatique. En JavaScript, son implémentation peut être relativement simple à comprendre et à mettre en œuvre. Que ce soit pour trier de petites ou de grandes quantités de données, le tri par fusion offre des performances fiables et prévisibles, ce qui en fait un choix populaire pour de nombreuses applications. En comprenant son fonctionnement et en utilisant correctement ses implémentations, les développeurs JavaScript peuvent bénéficier d'un moyen efficace de trier leurs données.