Sort rapide en javascript
À quel point l'algorithme de tri rapide fonctionne
L'algorithme Quicksort choisit un élément et le considère comme un élément pivot; Maintenant, l'élément pivot est réservé.
Ensuite, nous prendrons les deux pointeurs «P» et «Q».
Le pointeur «P» se déplacera du côté gauche vers le côté droit et il ne s'arrêtera pas tant qu'il ne trouvera plus ou égal à l'élément pivot.
Le deuxième pointeur «Q» se déplacera du côté droit vers le côté gauche et il cessera de rechercher lorsqu'il trouvera un élément inférieur ou égal à l'élément pivot.
Ainsi, «P» triera les plus petits éléments du côté gauche et «Q» trie les plus grands éléments vers le côté droit.
Nous allons maintenant comprendre le fonctionnement de l'algorithme de tri rapide à l'aide d'un exemple:
Supposons que nous ayons un tableau de six éléments et que nous voulons le trier par ordre croissant en utilisant un algorithme Quicksort:
Dans l'étape initiale, nous sélectionnons «36» comme élément pivot (élément moyen):
Dans l'étape suivante, nous sélectionnons nos pointeurs, le pointeur «P» pour se déplacer de gauche à droite et le pointeur «Q» pour se déplacer du côté droit vers le côté gauche:
Maintenant, la valeur du pointeur de gauche «P» sera comparée à la valeur de pivot, car «35» est inférieure à «36», déplacez le pointeur «P» vers l'élément adjacent. D'un autre côté, comparez la valeur du pointeur droit «Q» avec la valeur de pivot, «39» est supérieur à «36», donc le pointeur «Q» se déplacera vers l'élément adjacent gauche:
Maintenant, le pointeur «P» pointe vers «33» et est comparé au pivot «36», la valeur du pointeur «p» est inférieure à la valeur de pivot, donc le pointeur «p» sera déplacé vers l'élément adjacent. Alors que la valeur du pointeur «Q» 32 »est inférieure à la valeur de pivot« 36 », elle s'arrêtera ici:
La valeur du pointeur gauche «37» est supérieure à la valeur du pivot «36», donc elle s'arrêtera également ici. Maintenant, «P» s'arrête à «37» et «Q» s'arrête à «32».
Nous allons maintenant vérifier si le pointeur 'P' traverse le pointeur 'Q' ou non. Dans ce cas, jusqu'à présent, «P» ne traverse pas le pointeur «Q», nous allons donc échanger la valeur du pointeur «p» avec la valeur du pointeur «q»:
Maintenant, «P» et «Q» pointent vers «32» et «37» respectivement, déplacez les pointeurs une fois de plus, maintenant p = q («36» = «36»):
Déplacez les pointeurs une fois de plus, alors que le pointeur 'P' traverse le pointeur 'Q' donc ici, il s'arrêtera et renverra l'index du pointeur 'P'. Jusqu'à présent, l'élément pivot est dans sa position droite et tous les éléments supérieurs à l'élément de pivot sont sur le côté droit du pivot, et tous les éléments moins que les éléments de pivot sont sur le côté gauche du pivot. De cette façon, nous trierons toute la liste.
Maintenant, nous allons implémenter ce concept dans JavaScript. Tout d'abord, le code pour échanger les éléments:
fonction swap_elements (elements, left_index, droite_index)var temp = elements [Left_index];
Elements [Left_Index] = Elements [droite_index];
Elements [droite_index] = temp;
Ensuite, le code pour diviser une liste en sous-listes:
fonction sub_lists (Elements, Left_Pointer, droite_pointer)var pivot = éléments [mathématiques.plancher ((droit_pointer + gauche_pointer) / 2)],
i = Left_pointer,
j = right_pointer;
alors que je <= j)
while (éléments [i] pivot)
J-;
if (i 1)
index = sub_lists (Elements, Left_Pointer, droite_pointer);
if (Left_pointer < index - 1)
Quick_sort (Elements, Left_Pointer, index - 1);
if (index < right_pointer)
Quick_sort (Elements, Index, droite_pointer);
Éléments de retour;
Nous avons créé une fonction qui prend trois paramètres dans la fonction. Nous divisons toute la liste en sous-listes et découvrons le pointeur gauche et le pointeur droit et nous écrivons le code pour incrémenter le pointeur gauche s'il est inférieur à l'élément de pivot et décrément le pointeur droit s'il est supérieur à l'élément de pivot:
Maintenant, nous allons écrire le code pour gérer le comportement récursif du tri rapide. Étant donné que dans l'étape ci-dessus, l'index de Left_pointer est renvoyé et nous l'utiliserons pour diviser la liste en sous-listes et appliquer QuickSort sur ces sous-listes:
fonction Quick_sort (Elements, Left_Pointer, droite_pointer)var index;
si (éléments.longueur> 1)
index = sub_lists (Elements, Left_Pointer, droite_pointer);
if (Left_pointer < index - 1)
Quick_sort (Elements, Left_Pointer, index - 1);
if (index < right_pointer)
Quick_sort (Elements, Index, droite_pointer);
Éléments de retour;
L'extrait de code complet ira comme ceci:
Var Elements = [35,33,37,36,32,39];fonction swap_elements (elements, left_index, droite_index)
var temp = elements [Left_index];
Elements [Left_Index] = Elements [droite_index];
Elements [droite_index] = temp;
fonction sub_lists (Elements, Left_Pointer, droite_pointer)
var pivot = éléments [mathématiques.plancher ((droit_pointer + gauche_pointer) / 2)],
i = Left_pointer,
j = right_pointer;
alors que je <= j)
while (éléments [i] pivot)
J-;
if (i 1)
index = sub_lists (Elements, Left_Pointer, droite_pointer);
if (Left_pointer < index - 1)
Quick_sort (Elements, Left_Pointer, index - 1);
if (index < right_pointer)
Quick_sort (Elements, Index, droite_pointer);
Éléments de retour;
var trid_array = Quick_sort (éléments, 0, éléments.longueur - 1);
console.log ("La liste triée:", trid_array);
Nous avons initialisé le tableau non trié au début du programme et à la fin du programme, nous avons appelé la fonction «Quick_sort ()» pour obtenir le tableau trié final:
Enfin, lorsque nous exécutons ce code, nous obtenons la sortie résultante comme:
Conclusion:
Quicksort est un algorithme de tri qui fonctionne sur la philosophie de division et de conquête et de diviser le problème en sous-problèmes plus petits. Et continuez ce processus jusqu'à ce que vous atteigniez l'objectif résultant. Dans cet article, nous discutons du fonctionnement de Quicksort et mettons en œuvre ce concept en JavaScript pour trier n'importe quel tableau de la manière la plus efficace.