Introduction au tri rapide en JavaScript
Un algorithme de tri est l'une des parties importantes de la structure des données. Le tri est la façon d'organiser le groupe d'éléments d'une manière spécifiée. Chaque fois que nous discutons d'algorithmes de tri plus rapides, le tri rapide entre en jeu. Il s'agit de l'une des techniques de tri les plus populaires selon le temps d'exécution concerné. C'est comparativement un meilleur choix de n'importe quel développeur ou codeur en raison de ses performances. Le tri rapide fonctionne sur la règle de division et de conquête. Cela signifie qu'il divise la liste en deux, puis deux listes divisées en 4 récursivement et ainsi de suite. Dans cet article, nous verrons également comment fonctionne le tri rapide avec un exemple de code. En outre, nous verrons comment il est plus rapide par rapport à d'autres algorithmes de tri différents. Nous verrons les différents composants de cet algorithme de tri rapide.
Opérations en tri rapide
Il y a trois opérations principales dans le JavaScript de tri rapide:
- Partitionnement d'une liste: Division ou liste de tableaux à l'aide de la fonction diviser pour régner. C'est la première étape que l'on peut dire dans cette technique de tri. Pour cela, nous avons besoin d'un élément Pivot (élément central ou proche de l'élément central).
- Échange d'éléments: c'est l'objectif principal de tout algorithme de tri pour arriver à la liste de souhaits en tant que sortie. Il s'agit d'un mécanisme pour trier remplacer la valeur de l'un à l'autre. Par exemple, A = 10; B = 20; Si quelqu'un demande à échanger, la valeur de A sera 20 et le B sera 10.
- Opération récursive: Cela joue un grand rôle dans le tri rapide. Comme faire les choses encore et encore, ce n'est pas beaucoup possible et fiable sans avoir la fonction récursive. C'est quelque chose qu'une fonction appelle elle-même (même fonction) pour faire le travail. Cela joue un grand rôle lorsque nous effectuons encore et encore n'importe quelle tâche avec la même approche et dans le même contexte.
Comparaison de l'algorithme de tri
Il existe différents types d'algorithmes de tri. Puisque JavaScript est un langage de programmation, il prend en charge tous les algorithmes de tri avec lui. Chaque algorithme de tri a ses avantages et ses inconvénients. Voici la liste des algorithmes de tri et ses performances et autres matrices:
| Algorithme de tri | Complexité temporelle | ||
| Meilleur cas | Cas moyen | Pire cas | |
| Tri des bulles | Ω (N) | Θ (N 2 ) | O (N 2 ) |
| Tri de sélection | Ω (N 2 ) | Θ (N 2 ) | O (N 2 ) |
| Tri par insertion | Ω (N) | Θ (N 2 ) | O (N 2 ) |
| Tri par fusion | Ω (N log N) | Θ (N log N) | O (N log N) |
| Tri par tas | Ω (N log N) | Θ (N log N) | O (N log N) |
| Tri rapide | Ω (N log N) | Θ (N log N) | O (N 2 ) |
Comme nous pouvons le voir dans la liste, le tri RAPIDE est plus rapide que le tri à bulles, le tri par sélection et le tri par insertion.
Comment fonctionne le tri rapide en JavaScript?
Étape 1 : Pour obtenir l'élément Pivot - Dans n'importe quelle division et conquête, la sélection d'un bon pivot joue un rôle essentiel. Donc, généralement, nous essayons d'obtenir l'élément central du tableau en tant qu'élément Pivot. C'est l'élément à partir duquel nous divisons le tableau unique en paix de deux pour traiter le tri.
Étape 2 : démarrez les pointeurs gauches comme premier élément du tableau d'entrée.
Étape 3 : démarrez les pointeurs de droite comme dernier élément du tableau d'entrée.
Étape 4 : Maintenant, nous comparons les éléments du pointeur gauche avec l'élément pivot sélectionné et nous échangeons la valeur si nécessaire conformément aux exigences de l'entreprise. Ensuite, nous comparons le pointeur droit avec l'élément Pivot.
Étape 5: Déplacez les deux à la suivante. Toutes les étapes ci-dessus suivent encore et encore en utilisant une approche récursive.
Exemple de tri rapide en JavaScript
Il s'agit d'une fonction permettant de prendre en charge le tri rapide en JavaScript. En cela, nous passerons la liste complète du tableau en entrée et obtiendrons le tableau trié en sortie.
Quick Sort in JavaScript
function quick_Sorting(array) (
if (array.length <= 1) (
return array; // if there is only one element then return the same
) else
(
var left = ();
var right = ();
var outputArray = ();
var pivot = array.pop();
var length = array.length;
for (var i = 0; i < length; i++) (
if (array(i) <= pivot) (
left.push(array(i));
) else (
right.push(array(i));
)
)
return outputArray.concat(quick_Sorting(left), pivot, quick_Sorting(right));
)
)
var myList = (3, 10, 2, 5, -5, 4, 7, 1);
alert("Input Array List: " + myList);
var sortedList = quick_Sorting(myList);
alert("Output Array List: " + sortedList);
En raison de ses performances étonnantes, la plupart des codeurs utilisent cette technique de tri pour implémenter la fonctionnalité de tri intégrée. Dans divers langages de programmation, le tri rapide a été utilisé pour sa fonctionnalité de tri intégrée. Il existe plusieurs autres façons d'écrire un programme pour effectuer les opérations de tri rapide et toutes les fonctions se rencontrent jusqu'à un point qui est Diviser et Conquérir. Ainsi, cette division et conquête est une règle de thump à traiter avec le tri rapide dans le JavaScript. Pas seulement en JavaScript mais aussi dans tous les langages de programmation.
Production:
Articles recommandés
Ceci est un guide de tri rapide en JavaScript. Nous discutons ici du fonctionnement du tri rapide en javascript, de ses opérations et de la comparaison de l'algorithme de tri avec l'exemple. Vous pouvez également consulter les articles suivants pour en savoir plus -
- Exemples pour implémenter le tri rapide en Java
- Qu'est-ce que la déclaration de cas en JavaScript?
- Propriétés du tri par fusion en JavaScript
- Types de constructeur en JavaScript
- Tri de tas en Python
- Échange en PHP
- Tri par insertion en JavaScript
- Fonction récursive en C
- Fonction récursive en JavaScript