Décryptage de l'algorithme de tri rapide : de la théorie à la pratique en quelques minutes

Quicksort est l'un des algorithmes de tri les plus rapides. Il prend un tableau de valeurs, choisit l'une des valeurs comme élément « pivot » et déplace les autres valeurs de sorte que les valeurs inférieures soient à gauche de l'élément pivot et les valeurs supérieures à droite de celui-ci.

Quick Sort se présente comme l'un des algorithmes de tri les plus élégants et efficaces dans le monde des algorithmes. Contrairement aux algorithmes plus simples comme le tri à bulles ou le tri par sélection, le tri rapide utilise une stratégie sophistiquée diviser pour régner qui le rend beaucoup plus rapide en pratique. Bien que le tri par fusion utilise également la division diviser pour régner, l'approche de partitionnement unique de Quick Sort conduit souvent à de meilleures performances et à une meilleure utilisation de la mémoire.

Complexité temporelle moyenne : O(n log n)

Complexité temporelle dans le pire des cas : O(n²)

Complexité spatiale : O(log n)

Table des matières

1. Qu'est-ce que l'algorithme de tri rapide
2. Comment fonctionne le tri rapide
   • Complexité temporelle
   • Complexité spatiale
3. Implémentation JavaScript
4. Conclusion

Qu'est-ce que l'algorithme de tri rapide

Quick Sort est un algorithme de tri très efficace qui fonctionne en sélectionnant un élément « pivot » dans le tableau et en partitionnant les autres éléments en deux sous-tableaux selon qu'ils sont inférieurs ou supérieurs au pivot. Contrairement au tri par fusion, qui divise d'abord et combine ensuite, le tri rapide effectue son tri pendant le processus de partitionnement.

Considérez cette comparaison avec d'autres algorithmes de tri :

Algorithm	Time Complexity (Average)	Space Complexity	In-Place?
Quick Sort	O(n log n)	O(log n)	Yes
Merge Sort	O(n log n)	O(n)	No
Bubble Sort	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(1)	Yes
Heap Sort	O(n log n)	O(1)	Yes

Comment fonctionne le tri rapide ?

Avant de plonger dans l'implémentation JavaScript des algorithmes de tri rapide, adoptons une approche étape par étape pour comprendre comment l'algorithme fonctionne en triant manuellement un tableau simple de nombres en seulement quatre étapes simples.

Le tri rapide peut être décomposé en quatre étapes simples :

1. Choisissez un élément pivot dans le tableau. Cet élément peut être le premier, le dernier, le milieu ou même un élément aléatoire de la liste/du tableau.
2. Réorganisez le tableau de manière à ce que tous les éléments inférieurs au pivot soient à gauche et tous les éléments supérieurs à droite.
3. Échangez l'élément pivot avec le premier élément de valeurs supérieures, de sorte que le pivot soit au milieu.
4. Appliquez récursivement les mêmes opérations aux sous-tableaux à gauche et à droite du pivot.

Appliquons ces étapes à un tableau réel. On y va ?

Tableau initial : [3, 6, 2, 7, 1]

Étape 1 : Choisissez un pivot

• Nous choisissons le dernier élément comme pivot pour plus de simplicité.
• Pivot = 1

Étape 2 : Réorganiser le tableau autour du pivot

• Réorganiser de manière à ce que tous les éléments inférieurs au pivot (1) soient à gauche et tous les éléments supérieurs soient à droite.
• Au fur et à mesure que nous passons en revue chaque élément :
  • 3 (supérieur à 1) → reste à droite.
  • 6 (supérieur à 1) → reste à droite.
  • 2 (supérieur à 1) → reste à droite.
  • 7 (supérieur à 1) → reste à droite.
• Tableau réorganisé : [1, 6, 2, 7, 3]

Étape 3 : remettez le pivot dans sa position correcte

• Echangez le pivot (1) avec le premier élément supérieur à lui, qui est 6.
• Tableau après échange : [1, 3, 2, 7, 6]
• Maintenant, 1 est dans la bonne position (indice 0).

Étape 4 : Tri rapide récursif sur les sous-tableaux

• Sous-tableau gauche : [] (aucun élément restant de 1, donc rien à trier ici)
• Sous-tableau droit : [3, 2, 7, 6]

---

Trier le bon sous-tableau [3, 2, 7, 6] de manière récursive

Étape 1 : Choisissez un pivot

• Pivot = 6 (dernier élément)

Étape 2 : Réorganiser le tableau autour du pivot

• Disposer les éléments inférieurs à 6 à gauche et les plus grands à droite :
  • 3 (moins de 6) → reste à gauche.
  • 2 (moins de 6) → reste à gauche.
  • 7 (supérieur à 6) → reste à droite.
• Tableau réorganisé : [3, 2, 6, 7]

Étape 3 : remettez le pivot dans sa position correcte

• 6 est déjà dans la bonne position (index 2).
• Tableau : [1, 3, 2, 6, 7]

Étape 4 : Tri rapide récursif sur les sous-tableaux

• Sous-tableau gauche : [3, 2]
• Sous-tableau droit : [7] (un seul élément, aucun tri nécessaire)

---

Tri du sous-tableau gauche [3, 2]

Étape 1 : Choisissez un pivot

• Pivot = 2 (dernier élément)

Étape 2 : Réorganiser le tableau autour du pivot

• Réorganiser pour que les éléments inférieurs à 2 soient à gauche :
  • 3 (supérieur à 2) → reste à droite.
• Tableau réorganisé : [2, 3]

Étape 3 : remettez le pivot dans sa position correcte

• 2 est déjà dans la bonne position (index 1).
• Tableau : [1, 2, 3, 6, 7]

Étape 4 : Tri rapide récursif sur les sous-tableaux

• Sous-tableau gauche : [] (aucun élément)
• Sous-tableau droit : [3] (un seul élément, aucun tri nécessaire)

---

Tableau trié final

Après avoir trié tous les sous-tableaux, nous obtenons le tableau trié final :

Tableau trié : [1, 2, 3, 6, 7]

Vous trouverez ci-dessous la meilleure illustration de la façon dont cela fonctionne dans la vraie vie :

Complexité temporelle

La complexité temporelle du tri rapide varie en fonction de la sélection du pivot :

• Meilleur cas (O(n log n)) :

  • Se produit lorsque le pivot divise toujours le tableau en moitiés égales
  • Semblable aux performances de Merge Sort

• Cas moyen (O(n log n)) :

  • Scénarios les plus pratiques
  • Mieux que le tri par fusion grâce à une meilleure utilisation du cache

• Pire des cas (O(n²)) :

  • Se produit avec des tableaux déjà triés et une mauvaise sélection de pivot
  • Peut être évité avec de bonnes stratégies de sélection de pivots

Complexité spatiale

La complexité spatiale de Quick Sort est O(log n) en raison de :

• Profondeur de la pile d'appels récursifs
• Partition sur place (contrairement à l'espace supplémentaire O(n) de Merge Sort)
• Meilleure efficacité de la mémoire par rapport au tri par fusion

Implémentation JavaScript

function quickSort(arr) {
  // Base case: arrays with length 0 or 1 are already sorted
  if (arr.length <= 1) return arr;

  // Helper function to swap elements
  const swap = (i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  };

  // Partition function using Lomuto's partition scheme
  function partition(low, high) {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        swap(i, j);
      }
    }
    swap(i + 1, high);
    return i + 1;
  }

  // Main quickSort function implementation
  function quickSortHelper(low, high) {
    if (low < high) {
      const pivotIndex = partition(low, high);
      quickSortHelper(low, pivotIndex - 1); // Sort left side
      quickSortHelper(pivotIndex + 1, high); // Sort right side
    }
  }

  quickSortHelper(0, arr.length - 1);
  return arr;
}

Conclusion

Le tri rapide est un choix populaire en raison de son efficacité et de son tri sur place. Il surpasse les algorithmes plus simples tels que le tri à bulles et le tri par sélection avec ses performances moyennes O(n log n) et sa faible complexité spatiale.

Points clés à retenir :

1. Choisissez soigneusement la stratégie de sélection pivot
2. Tenez compte des caractéristiques d'entrée lorsque vous décidez entre le tri rapide et d'autres algorithmes
3. Utilisez la sélection pivot aléatoire pour de meilleures performances dans les cas moyens

---

---

Restez à jour et connecté

Pour vous assurer de ne manquer aucune partie de cette série et pour me contacter pour plus de détails
discussions sur le Développement Logiciel (Web, Serveur, Mobile ou Scraping/Automatisation), les données
structures et algorithmes, et d'autres sujets technologiques passionnants, suivez-moi sur :

Emmanuel Ayinde Suivez

Ingénieur logiciel | Rédacteur technique | Développeur Backend, Web & Mobile ? | Passionné par la création de solutions logicielles efficaces et évolutives. #connectons-nous ?

• GitHub
• Linkedin
• X (Twitter)

Restez à l'écoute et bon codage ?‍??

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!