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)
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 |
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 :
- 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.
- 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.
- Échangez l'élément pivot avec le premier élément de valeurs supérieures, de sorte que le pivot soit au milieu.
- 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]
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 :
La complexité temporelle du tri rapide varie en fonction de la sélection du pivot :
Meilleur cas (O(n log n)) :
Cas moyen (O(n log n)) :
Pire des cas (O(n²)) :
La complexité spatiale de Quick Sort est O(log n) en raison de :
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; }
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 :
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 :
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!