Algorithme de tri rapide dans Javascénario

Qu'est-ce que le tri ?

Le tri n’est rien d’autre que l’organisation des éléments dans l’ordre souhaité. Vous avez peut-être rencontré cela à l’école ou au collège. 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 dans Javascénario

Comme mentionné précédemment, JavaLe script a sorte(). Prenons un exemple avec quelques tableaux d'éléments comme [5,3,7,6,2,9] et souhaitons trier les éléments de ce tableau par ordre croissant. Il suffit d'appeler sorte() sur le tableau d'éléments et il trie les éléments du tableau par 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 plutôt que le tri par défaut() dans Javascénario

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. Tri par défaut() dans JavaUtilisations du script tri par insertion by Moteur V8 de Chrome et Tri par fusion by Mozilla Firefox et Safari.

Mais 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 bien comprendre, vous devez savoir comment fonctionne le tri rapide et voyons cela en détail maintenant.

Qu'est-ce que le tri rapide ?

Un tri rapide suit Diviser et conquérir algorithme. Il s'agit de diviser les éléments en parties plus petites en fonction de certaines conditions et d'effectuer les opérations de tri sur ces parties plus petites divisées. Par conséquent, cela fonctionne bien pour les grands ensembles de données. Voici donc les étapes de fonctionnement du tri rapide en termes simples.

1. Sélectionnez d'abord un élément qui doit être appelé comme pivot .
2. Ensuite, comparez tous les éléments du tableau avec l'élément pivot sélectionné et disposez-les de telle manière que les éléments inférieurs à l'élément pivot soient à sa gauche et supérieurs à l'élément pivot à sa droite.
3. 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 le tri rapide

1. Trouvez d'abord le "Pivot" élément dans le tableau.
2. Démarrez le pointeur gauche sur le premier élément du tableau.
3. Démarrez le pointeur droit sur le dernier élément du tableau.
4. 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.
5. 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.
6. Vérifiez si le pointeur gauche est inférieur ou égal au pointeur droit, puis échangez les éléments aux emplacements de ces pointeurs.
7. Incrémentez le pointeur gauche et décrémentez le pointeur droit.
8. Si l’index du pointeur gauche est toujours inférieur à l’index du pointeur droit, répétez le processus ; sinon, renvoie l'index du pointeur gauche.

Voyons donc ces étapes avec un exemple. Considérons le tableau d'éléments que nous devons trier est [5,3,7,6,2,9].

Déterminer l'élément pivot

Mais avant de procéder au 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, cela donne les pires performances dans le tableau trié. Ainsi, il est 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 sont présentées 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 les pointeurs gauche et droit comme premier et dernier éléments du tableau respectivement. Donc le pointeur gauche pointe vers 5 à l'index 0 et le pointeur droit pointe vers 9 à l'indice 5.

ÉTAPE 3: Comparez l'élément situé sur le pointeur gauche avec l'élément pivot. Depuis, 5 < 6 déplace le pointeur gauche vers la droite jusqu'à l'index 1.

ÉTAPE 4: Maintenant, toujours 3 <6, alors déplacez le pointeur gauche vers un index supplémentaire vers la droite. Alors maintenant, 7 > 6 arrête 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. Puisque 9 > 6 déplacez le pointeur droit vers la gauche. Maintenant, comme 2 <6, arrêtez de déplacer le pointeur droit.

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

ÉTAPE 7: Déplacez les deux pointeurs d’un pas supplémentaire.

ÉTAPE 8: Puisque 6 = 6, déplacez les pointeurs d'un pas supplémentaire et arrêtez-vous lorsque le pointeur gauche croise le pointeur droit et renvoyez l'index du pointeur gauche.

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

Code pour échanger deux nombres dans Javascénario

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 element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //swap two elements
            i++;
            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. C’est pourquoi on l’appelle l’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éé au cours du processus.

Donc, nous devons appeler ça cloison() expliqué ci-dessus et sur cette base, nous divisons les 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 partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var 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 element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray); //prints [2,3,5,6,7,9]

NOTE: Le tri rapide s'exécute avec la complexité temporelle de O (nlogn).