l'Algorithmie Avancée en Informatique: Diviser pour Régner: Tri rapide, Tri fusion

Introduction

La technique de "Diviser pour Régner" (Divide and Conquer) est une approche algorithmique qui divise un problème en sous-problèmes plus petits, les résout de manière récursive et combine les solutions pour obtenir le résultat final. Cette technique est particulièrement efficace pour les algorithmes de tri tels que le tri rapide (Quick Sort) et le tri par fusion (Merge Sort).

Tri Rapide (Quick Sort)

Le tri rapide est un algorithme de tri très efficace qui utilise la technique de diviser pour régner pour trier un tableau. Il fonctionne en choisissant un pivot et en réorganisant les éléments du tableau de sorte que les éléments inférieurs au pivot soient à sa gauche et les éléments supérieurs soient à sa droite. Ensuite, il trie récursivement les sous-tableaux.

Étapes de l'algorithme de Tri Rapide :

Diviser : Choisissez un pivot et partitionnez le tableau de sorte que les éléments inférieurs au pivot soient à gauche et les éléments supérieurs soient à droite.
Régner : Appliquez récursivement le tri rapide aux sous-tableaux gauche et droit.
Combiner : Les sous-tableaux sont déjà triés, donc aucune étape de combinaison n'est nécessaire.

Implémentation en JavaScript

function quickSort(arr) {
    // Si le tableau a un seul élément ou est vide, il est déjà trié
    if (arr.length <= 1) {
        return arr;
    }

    // Choisir le pivot (ici, on choisit le dernier élément)
    const pivot = arr[arr.length - 1];
    const left = [];
    const right = [];

    // Partitionner le tableau en deux sous-tableaux
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    // Appliquer récursivement le tri rapide aux sous-tableaux gauche et droit
    return [...quickSort(left), pivot, ...quickSort(right)];
}

// Exemple d'utilisation
const arr = [38, 27, 43, 3, 9, 82, 10];
const sortedArr = quickSort(arr);
console.log(sortedArr); // Output: [3, 9, 10, 27, 38, 43, 82]

Explication du Code

Base Case : Si le tableau a un seul élément ou est vide, il est déjà trié.
Choix du Pivot : Le dernier élément du tableau est choisi comme pivot.
Partition : Les éléments inférieurs au pivot sont placés dans le tableau left, et les éléments supérieurs dans le tableau right.
Appel Récursif : Le tri rapide est appliqué récursivement aux sous-tableaux gauche et droit.
Combinaison : Les sous-tableaux triés et le pivot sont combinés pour former le tableau final trié.

Tri par Fusion (Merge Sort)

Le tri par fusion est un algorithme de tri stable et efficace qui utilise la technique de diviser pour régner pour trier un tableau. Il divise le tableau en deux moitiés, trie chaque moitié de manière récursive et fusionne les deux moitiés triées pour obtenir le tableau final trié.

Étapes de l'algorithme de Tri par Fusion :

Diviser : Divisez le tableau en deux moitiés.
Régner : Appliquez récursivement le tri par fusion aux deux moitiés.
Combiner : Fusionnez les deux moitiés triées pour obtenir le tableau final trié.

Implémentation en JavaScript

function mergeSort(arr) {
    // Si le tableau a un seul élément ou est vide, il est déjà trié
    if (arr.length <= 1) {
        return arr;
    }

    // Diviser le tableau en deux moitiés
    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    // Régner : trier chaque moitié de manière récursive
    const sortedLeft = mergeSort(left);
    const sortedRight = mergeSort(right);

    // Combiner : fusionner les deux moitiés triées
    return merge(sortedLeft, sortedRight);
}

// Fonction pour fusionner deux tableaux triés
function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    // Fusionner les tableaux en comparant les éléments
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // Ajouter les éléments restants
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Exemple d'utilisation
const arr = [38, 27, 43, 3, 9, 82, 10];
const sortedArr = mergeSort(arr);
console.log(sortedArr); // Output: [3, 9, 10, 27, 38, 43, 82]

Explication du Code

Base Case : Si le tableau a un seul élément ou est vide, il est déjà trié.
Division : Le tableau est divisé en deux moitiés, left et right.
Appel Récursif : Le tri par fusion est appliqué récursivement aux deux moitiés.
Fusion : Les deux moitiés triées sont fusionnées pour former le tableau final trié.

Comparaison entre Tri Rapide et Tri par Fusion

Complexité Temporelle

Tri Rapide : O(n log n) en moyenne, mais O(n²) dans le pire des cas (si le pivot est toujours le plus petit ou le plus grand élément).
Tri par Fusion : O(n log n) dans tous les cas.

Complexité Spatiale

Tri Rapide : O(log n) d'espace supplémentaire en moyenne pour la pile de récursion.
Tri par Fusion : O d'espace supplémentaire pour les tableaux temporaires utilisés lors de la fusion.

Stabilité

Tri Rapide : Non stable.
Tri par Fusion : Stable.

Applications

Tri Rapide : Souvent utilisé pour les applications générales de tri en raison de sa simplicité et de sa performance moyenne élevée.
Tri par Fusion : Utilisé lorsqu'une stabilité est requise ou lorsque les données sont très grandes et que la complexité temporelle doit être garantie.

Conclusion

Les algorithmes de tri rapide et de tri par fusion sont deux exemples puissants de la technique de diviser pour régner. Ils décomposent le problème de tri en sous-problèmes plus petits, les résolvent de manière récursive et combinent les résultats pour obtenir la solution finale. En comprenant ces algorithmes et leurs applications, les développeurs peuvent choisir l'approche la plus appropriée pour leurs besoins spécifiques de tri.