Algorithme QuickSort en JavaScript

Qu'est-ce que le tri rapide?

L' algorithme de tri rapide suit l'approche Divide and Conquer. Il divise les éléments en parties plus petites en fonction de certaines conditions et effectue les opérations de tri sur ces petites parties divisées.

L'algorithme de tri rapide est l'un des algorithmes les plus utilisés et les plus populaires dans tous les langages de programmation. Mais, si vous êtes un développeur JavaScript, vous avez peut-être entendu parler de sort () qui est déjà disponible en JavaScript. Ensuite, vous avez peut-être réfléchi à la nécessité de cet algorithme de tri rapide. Pour comprendre cela, nous avons d'abord besoin de ce qu'est le tri et du tri par défaut en JavaScript.

Qu'est-ce que le tri?

Le tri n'est rien d'autre que la disposition des éléments dans l'ordre que nous voulons. Vous avez peut-être rencontré cela à l'école ou à l'université. Comme organiser les nombres du plus petit au plus grand (croissant) ou du plus grand au plus petit (décroissant), c'est ce que nous avons vu jusqu'à présent et s'appelle le tri.

Tri par défaut en JavaScript

Comme mentionné précédemment, JavaScript a sort () . Prenons un exemple avec peu de tableau d'éléments comme [5,3,7,6,2,9] et voulons trier les éléments de ce tableau par ordre croissant. Appelez simplement sort () sur le tableau des éléments et il trie les éléments du tableau dans l'ordre croissant.

Code:

var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]

Quelle est la raison de choisir le tri rapide sur le tri par défaut () dans JavaScript

Bien que sort () donne le résultat souhaité, le problème réside dans la façon dont il trie les éléments du tableau. Le tri par défaut () dans JavaScript utilise le tri par insertion par moteur V8 de Chrome et le tri par fusion par Mozilla Firefox et Safari .

Mais, à part cela, cela ne convient pas si vous devez trier un grand nombre d'éléments. La solution consiste donc à utiliser le tri rapide pour les grands ensembles de données.

Donc, pour comprendre complètement, vous devez savoir comment fonctionne le tri rapide et voyons cela en détail maintenant.

Qu'est-ce que le tri rapide?

Le tri rapide suit l' algorithme Divide and Conquer . Il divise les éléments en pièces plus petites en fonction de certaines conditions et effectue les opérations de tri sur ces pièces plus petites divisées. Par conséquent, cela fonctionne bien pour les grands ensembles de données. Voici donc les étapes du fonctionnement du tri rapide en termes simples.

Sélectionnez d'abord un élément à appeler comme élément pivot .
Ensuite, comparez tous les éléments du tableau avec l'élément pivot sélectionné et organisez-les de manière à ce que les éléments inférieurs à l'élément pivot soient à sa gauche et supérieurs à pivot à droite.
Enfin, effectuez les mêmes opérations sur les éléments latéraux gauche et droit de l'élément pivot.

Voilà donc les grandes lignes du tri rapide. Voici les étapes à suivre une par une pour effectuer un tri rapide.

Comment fonctionne QuickSort

Trouvez d'abord l' élément "pivot" dans le tableau.
Démarrez le pointeur gauche au premier élément du tableau.
Démarrez le pointeur droit au dernier élément du tableau.
Comparez l'élément pointant avec le pointeur gauche et s'il est inférieur à l'élément pivot, déplacez le pointeur gauche vers la droite (ajoutez 1 à l'index gauche). Continuez ainsi jusqu'à ce que l'élément du côté gauche soit supérieur ou égal à l'élément pivot.
Comparez l'élément pointant avec le pointeur droit et s'il est supérieur à l'élément pivot, déplacez le pointeur droit vers la gauche (soustrayez 1 à l'index droit). Continuez ainsi jusqu'à ce que l'élément du côté droit soit inférieur ou égal à l'élément pivot.
Vérifiez si le pointeur gauche est inférieur ou égal au pointeur droit, puis voyez les éléments aux emplacements de ces pointeurs.
Incrémentez le pointeur gauche et décrémentez le pointeur droit.
Si l'index du pointeur gauche est toujours inférieur à l'index du pointeur droit, répétez le processus; else renvoie l'index du pointeur gauche.

Alors, voyons ces étapes avec un exemple. Considérons le tableau des éléments que nous devons trier est [5,3,7,6,2,9].

Déterminer l'élément Pivot

Mais avant d'aller de l'avant avec le tri rapide, la sélection de l'élément pivot joue un rôle majeur. Si vous sélectionnez le premier élément comme élément pivot, les performances dans le tableau trié sont les moins bonnes. Il est donc toujours conseillé de choisir l'élément du milieu (longueur du tableau divisée par 2) comme élément pivot et nous faisons de même.

Voici les étapes pour effectuer un tri rapide qui est montré avec un exemple [5,3,7,6,2,9].

ÉTAPE 1: Déterminez le pivot comme élément central. Donc, 7 est l'élément pivot.

ÉTAPE 2: Commencez respectivement les pointeurs gauche et droit comme premier et dernier éléments du tableau. Ainsi, le pointeur gauche pointe vers 5 à l'index 0 et le pointeur droit pointe vers 9 à l'index 5.

ÉTAPE 3: Comparez l'élément du pointeur gauche avec l'élément pivot. Depuis, 5 <6 décale le pointeur gauche vers la droite vers l'index 1.

ÉTAPE 4: Maintenant, toujours 3 <6, alors déplacez le pointeur gauche vers un autre index vers la droite. Alors maintenant 7> 6 arrêtez d'incrémenter le pointeur gauche et maintenant le pointeur gauche est à l'index 2.

ÉTAPE 5: Maintenant, comparez la valeur du pointeur droit avec l'élément pivot. Depuis 9> 6, déplacez le pointeur droit vers la gauche. Maintenant que 2 <6 arrêtez de déplacer le pointeur droit.

ÉTAPE 6: permutez les deux valeurs présentes aux pointeurs gauche et droit entre elles.

ÉTAPE 7: Déplacez les deux pointeurs d'un pas de plus.

ÉTAPE 8: Depuis 6 = 6, déplacez les pointeurs sur une étape supplémentaire et arrêtez lorsque le pointeur gauche croise le pointeur droit et renvoyez l'index du pointeur gauche.

Donc, ici, sur la base de l'approche ci-dessus, nous devons écrire du code pour permuter les éléments et partitionner le tableau comme mentionné dans les étapes ci-dessus.

Code pour échanger deux nombres en JavaScript:

function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}

Code pour effectuer la partition comme mentionné dans les étapes ci-dessus:

function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}

Effectuer l'opération récursive

Une fois que vous avez effectué les étapes ci-dessus, l'index du pointeur gauche sera renvoyé et nous devons l'utiliser pour diviser le tableau et effectuer le tri rapide sur cette partie. Par conséquent, il est appelé algorithme Divide and Conquer.

Ainsi, le tri rapide est effectué jusqu'à ce que tous les éléments du tableau de gauche et du tableau de droite soient triés.

Remarque: le tri rapide est effectué sur le même tableau et aucun nouveau tableau n'est créé dans le processus.

Nous devons donc appeler cette partition () expliquée ci-dessus et sur cette base, nous divisons le tableau en parties. Voici donc le code où vous l'utilisez,

function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

Code de tri rapide complet:

var items = [5,3,7,6,2,9];function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]