Quicksort : Le tri éclair - explication et implémentation en JavaScript

Plongez dans l’univers de l’algorithmie avec nous chaque vendredi ! Chaque semaine, découvrez une nouvelle facette des algorithmes, ces outils puissants qui façonnent le monde numérique. Que vous soyez un débutant curieux ou un développeur chevronné, nos articles vous guideront à travers des concepts clés, des exemples pratiques et des défis passionnants. Ne ratez pas notre rendez-vous hebdomadaire pour démystifier l’algorithmie et booster votre logique de programmation !

La semaine dernière nous avions exploré l’algorithme de tri par insertion :

Le tri par insertion en JavaScript : Principes et implémentations

Cette semaine, nous partons explorer le tri rapide (Quick sort) en JavaScript.

Photo de Andre Taissin sur Unsplash

Le tri rapide, également connu sous son nom anglais “quicksort”, est l’un des algorithmes de tri les plus utilisés et les plus efficaces en informatique. Inventé par Tony Hoare en 1959, cet algorithme utilise une approche “diviser pour régner” qui lui permet d’atteindre des performances remarquables dans la plupart des cas pratiques.

Dans cet article, nous allons explorer en profondeur le fonctionnement du tri rapide, comprendre ses avantages et ses limites, et voir comment l’implémenter efficacement en JavaScript.

Principe de fonctionnement

Le tri rapide repose sur un concept simple mais puissant : choisir un élément du tableau (appelé “pivot”), puis réorganiser le tableau de sorte que tous les éléments inférieurs au pivot se retrouvent à sa gauche et tous les éléments supérieurs à sa droite. Ce processus est appelé “partitionnement”.

Une fois le partitionnement effectué, le pivot est à sa position définitive dans le tableau trié. Il ne reste plus qu’à appliquer récursivement le même processus aux sous-tableaux situés à gauche et à droite du pivot.

Voici les étapes principales de l’algorithme :

1. Choisir un pivot : Sélectionner un élément du tableau qui servira de point de référence.
2. Partitionner : Réorganiser le tableau de sorte que les éléments inférieurs au pivot soient à sa gauche et les éléments supérieurs à sa droite.
3. Récursion : Appliquer récursivement les étapes 1 et 2 aux sous-tableaux gauche et droit.

Visualisation du processus

1. Tableau initial non trié : [7, 2, 1, 6, 8, 5, 3, 4]
2. Choix du pivot (par exemple, le dernier élément) : Pivot = 4
3. Partitionnement : Éléments plus petits que 4 : [2, 1, 3] Éléments plus grands que 4 : [8, 5, 7, 6] Tableau après partitionnement : [2, 1, 3, 4, 8, 5, 7, 6]
4. Récursion : Appliquer Quicksort à [2, 1, |3|] Appliquer Quicksort à [8, 5, 7, 6]
5. Ce processus se répète jusqu’à ce que tout le tableau soit trié.

L’étape de partitionnement en détail

Voici les étapes détaillées du processus :

1. Nous choisissons le dernier élément comme pivot.
2. Nous utilisons deux indices : i qui marque la frontière entre les éléments plus petits que le pivot (à gauche) et les éléments plus grands (à droite), j qui parcourt le tableau. À l’initialisation, i = début - 1, et j = début . Donc au démarrage, i = -1 et j = 0.
3. À chaque étape, si l’élément à l’indice j est inférieur au pivot, nous avons besoin d’effectuer deux opérations :

• Incrémenter i de 1
• Puis nous échangeons les éléments aux indices i et j. Et si, par contre, l’élément à l’indice j est plus grand que le pivot, alors on ne fait rien, et on passer à l’élément suivant en ajoutant 1 à j.

4. À la fin, nous échangeons le pivot avec l’élément à l’indice i+1, plaçant ainsi le pivot à sa position finale.

Une fois que j a parcouru tout le tableau (moins le pivot), on se retrouve avec la partie à gauche du pivot regroupant tous les éléments plus petit que pivot, et la partie de droite regroupant tous les éléments plus grand que pivot.

La vidéo ci-dessous vous montre les différentes étapes du partitionnement, pas à pas.

[embed]

Avant de passer à l’implémentation en JavaScript, voyons ce que ça donne en pseudo-code.

Pseudo-code de l’algorithme QuickSort

ALGORITHME TriRapide(tableau, debut, fin)
    SI debut < fin ALORS
        indice_pivot ← Partitionner(tableau, debut, fin)
        TriRapide(tableau, debut, indice_pivot - 1)
        TriRapide(tableau, indice_pivot + 1, fin)
    FIN SI
FIN ALGORITHME

ALGORITHME Partitionner(tableau, debut, fin)
    pivot ← tableau[fin]
    i ← debut - 1

    POUR j DE debut À fin - 1 FAIRE
        SI tableau[j] ≤ pivot ALORS
            i ← i + 1
            Échanger tableau[i] et tableau[j]
        FIN SI
    FIN POUR

    Échanger tableau[i + 1] et tableau[fin]
    RETOURNER i + 1
FIN ALGORITHMEp

Ce pseudo-code met en évidence :

• La nature récursive de l’algorithme principal
• La fonction de partitionnement qui réorganise les éléments autour du pivot
• Les conditions d’arrêt de la récursion
• Les opérations d’échange qui permettent le tri en place

Implémentation en JavaScript

Voyons maintenant comment implémenter le tri rapide en JavaScript. Nous allons explorer deux approches : une implémentation classique qui modifie le tableau en place, et une implémentation plus fonctionnelle qui crée de nouveaux tableaux.

Implémentation classique (en place)

/** 
 * Implémentation classique du tri rapide qui modifie le tableau en place
 * @param {Array} arr - Le tableau à trier
 * @param {number} [debut=0] - L'indice de début du segment à trier
 * @param {number} [fin=arr.length-1] - L'indice de fin du segment à trier
 * @returns {Array} - Le tableau trié (même référence que l'entrée)
 */
function triRapide(arr, debut = 0, fin = arr.length - 1) {
    // Cas de base : si le segment a 0 ou 1 élément, il est déjà trié
    if (debut >= fin) {
        return arr;
    }

    // Partitionnement et récupération de l'indice du pivot
    const pivotIndex = partition(arr, debut, fin);

    // Tri récursif des sous-tableaux
    triRapide(arr, debut, pivotIndex - 1);  // Sous-tableau gauche
    triRapide(arr, pivotIndex + 1, fin);    // Sous-tableau droit

    return arr;
}

/** 
 * Fonction de partitionnement pour le tri rapide
 * @param {Array} arr - Le tableau à partitionner
 * @param {number} debut - L'indice de début du segment à partitionner
 * @param {number} fin - L'indice de fin du segment à partitionner
 * @returns {number} - L'indice final du pivot
 */
function partition(arr, debut, fin) {
    // Choisir le dernier élément comme pivot
    const pivot = arr[fin];

    // Index qui marque la frontière entre éléments < pivot et éléments > pivot
    let i = debut - 1;

    // Parcourir tous les éléments sauf le pivot
    for (let j = debut; j < fin; j++) {
        // Si l'élément courant est inférieur au pivot
        if (arr[j] < pivot) {
            // Déplacer la frontière et échanger les éléments
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }

    // Placer le pivot à sa position finale
    [arr[i + 1], arr[fin]] = [arr[fin], arr[i + 1]];

    // Retourner l'indice du pivot
    return i + 1;
}

// Exemple d'utilisation
const tableau = [38, 27, 43, 3, 9, 82, 10];
console.log("Tableau original:", tableau);
triRapide(tableau);
console.log("Tableau trié:", tableau);

Implémentation fonctionnelle

/** 
 * Implémentation fonctionnelle du tri rapide qui crée de nouveaux tableaux
 * @param {Array} arr - Le tableau à trier
 * @returns {Array} - Un nouveau tableau trié 
 */
const triRapideFonctionnel = (arr) => {
    // Cas de base : tableau vide ou avec un seul élément
    if (arr.length <= 1) {
        return arr;
    }

    // Choisir le premier élément comme pivot
    const pivot = arr[0];

    // Partitionner le tableau
    const gauche = arr.slice(1).filter(element => element < pivot);
    const droite = arr.slice(1).filter(element => element >= pivot);

    // Combiner les résultats
    return [
        ...triRapideFonctionnel(gauche),
        pivot,
        ...triRapideFonctionnel(droite)
    ];
};

// Exemple d'utilisation
const tableau = [38, 27, 43, 3, 9, 82, 10];
console.log("Tableau original:", tableau);
const tableauTrie = triRapideFonctionnel(tableau);
console.log("Tableau trié:", tableauTrie);

Avantages

• Code plus lisible : L’intention est plus claire avec les opérations fonctionnelles
• Pas d’effets de bord : Le tableau original n’est jamais modifié
• Plus facile à déboguer : Chaque étape produit un nouveau tableau qu’on peut inspecter
• Facilité de parallélisation : Les opérations étant pures, elles peuvent être parallélisées

Inconvénients

• Consommation mémoire : Création de nombreux tableaux temporaires (complexité spatiale O(n))
• Performances : Moins efficace que la version classique pour de grands tableaux
• Copie des données : Nécessite plus d’opérations de copie que la version en place

Cette implémentation est particulièrement adaptée pour :

• Les petits à moyens tableaux où la lisibilité prime sur les performances
• Les cas où l’immutabilité des données est requise
• L’apprentissage et la compréhension de l’algorithme

Analyse de la récursionm

Le tri rapide est un algorithme récursif, ce qui signifie qu’il se divise en sous-problèmes plus petits. Voici une visualisation de l’arbre de récursion pour notre exemple :

Arbre de récursion

Dans notre schéma, le pivot est indiqué entre pipe : | pivot |.

Chaque nœud contenant un tableau représente un appel récursif à la fonction triRapide. On peut voir comment le tableau initial est progressivement divisé en sous-tableaux plus petits, jusqu’à ce que le tableau initiale soit complètement trié.

Analyse de la complexité

Complexité temporelle

La complexité temporelle du tri rapide dépend fortement du choix du pivot :

• Meilleur cas : O(n log n) — Lorsque le pivot divise toujours le tableau en deux parties égales.
• Cas moyen : O(n log n) — En pratique, avec un choix de pivot aléatoire ou médian.
• Pire cas : O(n²) — Lorsque le pivot est toujours l’élément le plus petit ou le plus grand (par exemple, dans un tableau déjà trié).

Complexité spatiale

• Implémentation classique : O(log n) — Espace utilisé par la pile d’appels récursifs.
• Implémentation fonctionnelle : O(n) — Création de nouveaux tableaux à chaque étape.

Comparaison avec d’autres algorithmes de tri

Voici comment le tri rapide se compare aux algorithmes de tri que nous avons vus précédemment :

Comparaison des performances des algorithmes de tri

On constate que le tri rapide (en bleu) est significativement plus efficace que le tri à bulles et le tri par insertion (en vert) pour les grands tableaux, grâce à sa complexité en O(n log n).

Cas particuliers et optimisations

Cas particuliers

Le tri rapide peut présenter des comportements particuliers dans certaines situations :

Cas particuliers

1. Tableau déjà trié : C’est le pire cas si on choisit le premier ou le dernier élément comme pivot, car chaque partition ne retire qu’un seul élément.
2. Éléments identiques : Peut également poser problème si l’algorithme ne gère pas correctement les éléments égaux au pivot.

Optimisations

Voici quelques optimisations courantes pour le tri rapide :

1. Choix du pivot amélioré

Ici, nous allons utiliser la technique du médian des trois. Nous allons prendre la première valeur, la valeur du milieu et la dernière valeur. Ensuite, nous allons trier ces trois valeurs et prendre celle du milieu, le médian des trois. Si on prend comme exemple : [38, 27, 43, 3, 9, 82, 10], cela voudrait dire que l'on va prendre la valeur 38, 3 et 10. On les trie → [3, 10, 38], et on récupère l'élément médian, ici 10.

function choisirPivot(arr, debut, fin) {
    // Méthode du "médian des trois"
    const milieu = Math.floor((debut + fin) / 2);

    // Trier debut, milieu, fin
    if (arr[debut] > arr[milieu]) {
        [arr[debut], arr[milieu]] = [arr[milieu], arr[debut]];
    }

    if (arr[milieu] > arr[fin]) {
        [arr[milieu], arr[fin]] = [arr[fin], arr[milieu]];
        if (arr[debut] > arr[milieu]) {
            [arr[debut], arr[milieu]] = [arr[milieu], arr[debut]];
        }
    }

    // Utiliser l'élément du milieu comme pivot
    return milieu;
}

Le choix d’un pivot médian présente plusieurs avantages importants :

• Évite le pire cas pour les tableaux triés : En choisissant un élément au milieu plutôt qu’aux extrémités, on évite le cas O(n²) pour les tableaux déjà triés ou inversés.
• Meilleure répartition en moyenne : Un élément du milieu a plus de chances d’être proche de la médiane, ce qui conduit à un partitionnement plus équilibré.
• Stabilité des performances : Cette stratégie offre des performances plus prévisibles car elle est moins sensible à l’ordre initial des données.

Cette approche, combinée avec la méthode du “médian des trois”, est souvent utilisée dans les implémentations professionnelles du tri rapide.

2. Tri par insertion pour les petits tableaux

function triRapideOptimise(arr, debut = 0, fin = arr.length - 1) {
    // Utiliser le tri par insertion pour les petits tableaux
    if (fin - debut < 10) {
        return triInsertion(arr, debut, fin);
    }

    // Sinon, utiliser le tri rapide normal
    const pivotIndex = partition(arr, debut, fin);
    triRapideOptimise(arr, debut, pivotIndex - 1);
    triRapideOptimise(arr, pivotIndex + 1, fin);

    return arr;
}

Avantages du tri par insertion pour les petits tableaux

Le tri par insertion présente plusieurs avantages pour les petits tableaux (généralement moins de 10 éléments) :

• Faible surcharge : Contrairement au tri rapide qui nécessite des appels récursifs et des partitionnements, le tri par insertion a une structure simple avec moins d’opérations de gestion.
• Efficacité sur petits tableaux : Pour de petites séquences, les constantes cachées dans la notation O(n²) du tri par insertion sont plus faibles que les surcharges du tri rapide.
• Performances sur des données presque triées : Le tri par insertion est particulièrement efficace lorsque les données sont déjà partiellement triées, ce qui est souvent le cas pour les sous-tableaux générés par le tri rapide.
• Localité mémoire : Le tri par insertion accède aux éléments de manière séquentielle, ce qui est plus efficace pour la mémoire cache sur les petits tableaux.

C’est pourquoi de nombreuses implémentations optimisées du tri rapide utilisent le tri par insertion comme “fallback” pour les petits sous-tableaux, combinant ainsi les avantages des deux algorithmes.

⬇️ Pour vous rafraîchir la mémoire sur le tri par insertion : ☺️

Le tri par insertion en JavaScript : Principes et implémentations

3. Élimination de la récursion terminale

function triRapideIteratif(arr) {
    // Pile pour stocker les bornes des sous-tableaux
    const pile = [[0, arr.length - 1]];

    while (pile.length > 0) {
        const [debut, fin] = pile.pop();

        if (debut < fin) {
            const pivotIndex = partition(arr, debut, fin);

            // Empiler d'abord le plus grand sous-tableau
            if (pivotIndex - debut < fin - pivotIndex) {
                pile.push([debut, pivotIndex - 1]);
                pile.push([pivotIndex + 1, fin]);
            } else {
                pile.push([pivotIndex + 1, fin]);
                pile.push([debut, pivotIndex - 1]);
            }
        }
    }

    return arr;
}

Au lieu d’utiliser des appels récursifs, cette version utilise une pile pour stocker les bornes des sous-tableaux à traiter. Les avantages de cette approche sont :

• Elle évite le risque de débordement de la pile d’appels qui peut survenir avec la version récursive pour de très grands tableaux
• L’optimisation “Empiler d’abord le plus grand sous-tableau” permet de minimiser l’espace utilisé dans la pile

Le code utilise une boucle while qui continue tant qu’il reste des sous-tableaux à traiter dans la pile. À chaque itération :

• Il récupère les indices de début et de fin du prochain sous-tableau à traiter
• Il effectue le partitionnement
• Il empile les nouvelles bornes pour les sous-tableaux restants à trier

Implémentation complète en ES6+

Voici une implémentation complète et optimisée du tri rapide en JavaScript ES6+ :

/** 
 * Classe utilitaire pour le tri rapide avec différentes variantes 
 */
class TriRapide {
  /**
   * Tri rapide classique qui modifie le tableau en place
   * @param {Array} arr - Le tableau à trier
   * @returns {Array} - Le tableau trié (même référence)
   */
  static trier(arr) {
    this._trierRecursif(arr, 0, arr.length - 1);
    return arr;
  }

  /**
   * Fonction récursive interne pour le tri rapide
   * @private
   */
  static _trierRecursif(arr, debut, fin) {
    if (debut < fin) {
      // Optimisation : tri par insertion pour les petits tableaux
      if (fin - debut < 10) {
        this._triInsertion(arr, debut, fin);
        return;
      }

      // Choisir un meilleur pivot (médian des trois)
      const pivotIndex = this._choisirPivot(arr, debut, fin);
      [arr[pivotIndex], arr[fin]] = [arr[fin], arr[pivotIndex]];

      // Partitionner et trier récursivement
      const p = this._partition(arr, debut, fin);
      this._trierRecursif(arr, debut, p - 1);
      this._trierRecursif(arr, p + 1, fin);
    }
  }

  /**
   * Fonction de partitionnement optimisée
   * @private
   */
  static _partition(arr, debut, fin) {
    const pivot = arr[fin];
    let i = debut - 1;

    for (let j = debut; j < fin; j++) {
      if (arr[j] <= pivot) {
        i++;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }

    [arr[i + 1], arr[fin]] = [arr[fin], arr[i + 1]];
    return i + 1;
  }

  /**
   * Choisit un meilleur pivot en utilisant la méthode du médian des trois
   * @private
   */
  static _choisirPivot(arr, debut, fin) {
    const milieu = Math.floor((debut + fin) / 2);

    // Trier debut, milieu, fin
    if (arr[debut] > arr[milieu]) {
      [arr[debut], arr[milieu]] = [arr[milieu], arr[debut]];
    }

    if (arr[milieu] > arr[fin]) {
      [arr[milieu], arr[fin]] = [arr[fin], arr[milieu]];
      if (arr[debut] > arr[milieu]) {
        [arr[debut], arr[milieu]] = [arr[milieu], arr[debut]];
      }
    }

    return milieu;
  }

  /**
   * Tri par insertion pour les petits tableaux
   * @private
   */
  static _triInsertion(arr, debut, fin) {
    for (let i = debut + 1; i <= fin; i++) {
      const valeur = arr[i];
      let j = i - 1;

      while (j >= debut && arr[j] > valeur) {
        arr[j + 1] = arr[j];
        j--;
      }

      arr[j + 1] = valeur;
    }
  }

  /**
   * Version itérative du tri rapide (sans récursion)
   * @param {Array} arr - Le tableau à trier
   * @returns {Array} - Le tableau trié (même référence)
   */
  static trierIteratif(arr) {
    const pile = [[0, arr.length - 1]];

    while (pile.length > 0) {
      const [debut, fin] = pile.pop();

      if (debut < fin) {
        if (fin - debut < 10) {
          this._triInsertion(arr, debut, fin);
          continue;
        }

        const pivotIndex = this._choisirPivot(arr, debut, fin);
        [arr[pivotIndex], arr[fin]] = [arr[fin], arr[pivotIndex]];
        const p = this._partition(arr, debut, fin);

        // Empiler d'abord le plus grand sous-tableau (optimisation)
        if (p - debut < fin - p) {
          pile.push([p + 1, fin]);
          pile.push([debut, p - 1]);
        } else {
          pile.push([debut, p - 1]);
          pile.push([p + 1, fin]);
        }
      }
    }

    return arr;
  }

  /**
   * Version fonctionnelle du tri rapide (crée de nouveaux tableaux)
   * @param {Array} arr - Le tableau à trier
   * @returns {Array} - Un nouveau tableau trié
   */
  static trierFonctionnel(arr) {
    if (arr.length <= 1) {
      return arr;
    }

    // Choisir un pivot (ici, l'élément du milieu pour éviter le pire cas)
    const pivotIndex = Math.floor(arr.length / 2);
    const pivot = arr[pivotIndex];

    // Partitionner le tableau (en excluant le pivot)
    const gauche = [];
    const droite = [];
    const egaux = [];

    for (let i = 0; i < arr.length; i++) {
      if (arr[i] < pivot) {
        gauche.push(arr[i]);
      } else if (arr[i] > pivot) {
        droite.push(arr[i]);
      } else {
        egaux.push(arr[i]);
      }
    }

    // Combiner les résultats
    return [
      ...this.trierFonctionnel(gauche),
      ...egaux,
      ...this.trierFonctionnel(droite)
    ];
  }
}

// Exemples d'utilisation
const tableau1 = [38, 27, 43, 3, 9, 82, 10];
const tableau2 = [...tableau1];
const tableau3 = [...tableau1];

console.log("Tableau original:", tableau1);
console.log("Tri rapide classique:", TriRapide.trier([...tableau1]));
console.log("Tri rapide itératif:", TriRapide.trierIteratif([...tableau2]));
console.log("Tri rapide fonctionnel:", TriRapide.trierFonctionnel(tableau3));

Applications pratiques

Le tri rapide est utilisé dans de nombreux contextes :

1. Bibliothèques standard : De nombreuses implémentations de la méthode sort() dans les langages de programmation utilisent le tri rapide ou ses variantes.
2. Bases de données : Pour trier efficacement de grandes quantités de données.
3. Traitement d’images : Dans certains algorithmes de traitement d’images qui nécessitent un tri rapide des pixels.
4. Recherche : Comme étape préliminaire pour d’autres algorithmes qui nécessitent des données triées.

Exercice pratique : Tri rapide avec pivot aléatoire

Énoncé : Implémentez une variante du tri rapide qui choisit un pivot aléatoire à chaque étape de partitionnement. Comparez ses performances avec l’implémentation standard sur un tableau déjà trié (qui est le pire cas pour le tri rapide standard).

Solution

/** 
 * Tri rapide avec pivot aléatoire
 * @param {Array} arr - Le tableau à trier
 * @param {number} [debut=0] - L'indice de début
 * @param {number} [fin=arr.length-1] - L'indice de fin
 * @returns {Array} - Le tableau trié (même référence)
 */
function triRapideAleatoire(arr, debut = 0, fin = arr.length - 1) {
  if (debut < fin) {
    // Choisir un pivot aléatoire
    const pivotIndex = debut + Math.floor(Math.random() * (fin - debut + 1));

    // Échanger le pivot avec le dernier élément
    [arr[pivotIndex], arr[fin]] = [arr[fin], arr[pivotIndex]];

    // Partitionner et trier récursivement
    const p = partition(arr, debut, fin);
    triRapideAleatoire(arr, debut, p - 1);
    triRapideAleatoire(arr, p + 1, fin);
  }
  return arr;
}

// Fonction de partitionnement (identique à celle vue précédemment)
function partition(arr, debut, fin) {
  const pivot = arr[fin];
  let i = debut - 1;

  for (let j = debut; j < fin; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[fin]] = [arr[fin], arr[i + 1]];
  return i + 1;
}

// Test de performance
function testerPerformance() {
  // Créer un tableau déjà trié (pire cas pour le tri rapide standard)
  const taille = 10000;
  const tableauTrie = Array.from({ length: taille }, (_, i) => i);

  // Copier le tableau pour les deux algorithmes
  const tableauPourStandard = [...tableauTrie];
  const tableauPourAleatoire = [...tableauTrie];

  // Mesurer le temps pour le tri rapide standard
  console.time("Tri rapide standard");
  triRapide(tableauPourStandard);
  console.timeEnd("Tri rapide standard");

  // Mesurer le temps pour le tri rapide avec pivot aléatoire
  console.time("Tri rapide aléatoire");
  triRapideAleatoire(tableauPourAleatoire);
  console.timeEnd("Tri rapide aléatoire");
}

testerPerformance();

Il se peut que la taille de la pile soit trop petite pour exécuter autant de récursions, ce qui peut provoquer une erreur de type “Maximum call stack size exceeded”. Pour contourner ce problème, vous pouvez lancer votre script JavaScript avec la commande :

> node --stack-size=2048 mon_script.js

Cette commande allouera 2 Mo à la pile, ce qui devrait être suffisant pour exécuter nos tests de performances.

Explication de la solution

Le choix d’un pivot aléatoire permet d’éviter le pire cas du tri rapide standard, qui se produit lorsque le tableau est déjà trié ou presque trié. En choisissant un pivot aléatoire, nous avons une probabilité beaucoup plus faible de tomber systématiquement sur le plus petit ou le plus grand élément.

Sur un tableau déjà trié, le tri rapide standard aura une complexité de O(n²), tandis que le tri rapide avec pivot aléatoire conservera une complexité moyenne de O(n log n), ce qui se traduira par des performances bien meilleures.

Conclusion

Le tri rapide est un algorithme de tri puissant et efficace qui, malgré son pire cas en O(n²), offre d’excellentes performances en pratique grâce à sa complexité moyenne en O(n log n).

Ses principales forces sont :

• Sa rapidité moyenne supérieure à la plupart des autres algorithmes de tri
• Son efficacité en termes d’utilisation de la mémoire (pour la version en place)
• Sa capacité à être optimisé de nombreuses façons

Ses principales faiblesses sont :

• Son pire cas en O(n²) sur des tableaux déjà triés ou avec beaucoup de doublons
• Sa nature récursive qui peut poser problème pour de très grands tableaux

En comprenant bien le fonctionnement du tri rapide et ses variantes, vous disposez d’un outil puissant pour résoudre efficacement de nombreux problèmes algorithmiques impliquant le tri de données.

Dans le prochain article, nous explorerons les algorithmes de parcours d’arbres, notamment le parcours en profondeur (DFS) et le parcours en largeur (BFS), qui sont fondamentaux pour travailler avec des structures de données hiérarchiques.

Références

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Hoare, C. A. R. (1962). Quicksort. The Computer Journal, 5(1), 10–16.
• MDN Web Docs. (2023). Array.prototype.sort(). https://developer.mozilla.org/fr/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
• GeeksforGeeks. (2023). QuickSort. https://www.geeksforgeeks.org/quick-sort/