Algoritmul QuickSort în JavaScenariu

Ce este Sortarea?

Sortarea nu este altceva decât aranjarea elementelor în ordinea pe care o dorim. S-ar putea să fi întâlnit asta în timpul școlii sau a colegiului. La fel ca aranjarea numerelor de la mai mic la mai mare (crescător) sau de la mai mare la mai mic (descrescător) este ceea ce am văzut până acum și se numește sortare.

Sortare implicită JavaScenariu

Ca menționat mai devreme, JavaScriptul are fel(). Să luăm un exemplu cu câteva matrice de elemente precum [5,3,7,6,2,9] și dorim să sortăm aceste elemente de matrice în ordine crescătoare. Doar sună fel() pe elementele matrice și sortează elementele matricei în ordine crescătoare.

Cod:

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

Care este motivul pentru a alege Sortare rapidă în locul sortării implicite () în JavaScenariu

Deși sort() dă rezultatul dorit, problema constă în felul în care sortează elementele matricei. Sortare implicită () în JavaUtilizări de script sortare inserție by Motor V8 din Chrome și Sortare îmbinare by Mozilla Firefox și Safari.

Dar, altfel, acest lucru nu este potrivit dacă trebuie să sortați un număr mare de elemente. Deci, soluția este să utilizați sortarea rapidă pentru un set de date mare.

Deci, pentru a înțelege complet, trebuie să știți cum funcționează Sortarea rapidă și să vedem asta în detaliu acum.

Ce este sortarea rapidă?

Urmează sortarea rapidă Diviza și cuceri algoritm. Împarte elementele în părți mai mici în funcție de anumite condiții și efectuează operațiunile de sortare pe acele părți mai mici împărțite. Prin urmare, funcționează bine pentru seturi de date mari. Așadar, iată pașii cum funcționează Sortarea rapidă în cuvinte simple.

1. Mai întâi selectați un element care urmează să fie numit ca pivot element.
2. Apoi, comparați toate elementele matricei cu elementul pivot selectat și aranjați-le în așa fel încât elementele mai mici decât elementul pivot să fie la stânga și mai mari decât pivotul în dreapta acestuia.
3. În cele din urmă, efectuați aceleași operații pe elementele din stânga și din dreapta la elementul pivot.

Deci, acesta este schița de bază a sortării rapide. Iată pașii care trebuie urmați unul câte unul pentru a efectua sortarea rapidă.

Cum funcționează QuickSort

1. Mai întâi găsiți "pivot" element din matrice.
2. Porniți indicatorul din stânga la primul element al matricei.
3. Porniți indicatorul din dreapta la ultimul element al matricei.
4. Comparați elementul care indică cu indicatorul din stânga și dacă este mai mic decât elementul pivot, apoi mutați indicatorul din stânga la dreapta (adăugați 1 la indexul din stânga). Continuați acest lucru până când elementul din partea stângă este mai mare sau egal cu elementul pivot.
5. Comparați elementul care indică cu indicatorul din dreapta și dacă este mai mare decât elementul pivot, atunci mutați indicatorul din dreapta la stânga (scădeți 1 din indexul din dreapta). Continuați acest lucru până când elementul din partea dreaptă este mai mic sau egal cu elementul pivot.
6. Verificați dacă indicatorul din stânga este mai mic sau egal cu indicatorul din dreapta, apoi schimbați elementele în locațiile acestor indicatori.
7. Crește indicatorul din stânga și decrementează indicatorul din dreapta.
8. Dacă indexul indicatorului din stânga este încă mai mic decât indicele indicatorului din dreapta, atunci repetați procesul; altfel returnează indexul indicatorului din stânga.

Deci, să vedem acești pași cu un exemplu. Să considerăm o serie de elemente pe care trebuie să le sortăm este [5,3,7,6,2,9].

Determinați elementul Pivot

Dar înainte de a continua cu Sortarea rapidă, selectarea elementului pivot joacă un rol major. Dacă selectați primul element ca element pivot, atunci acesta oferă cea mai proastă performanță în matricea sortată. Deci, este întotdeauna recomandabil să alegem elementul din mijloc (lungimea matricei împărțită la 2) ca element pivot și facem același lucru.

Iată pașii pentru a efectua sortarea rapidă, care este afișat cu un exemplu [5,3,7,6,2,9].

PASUL 1: Determinați pivotul ca element de mijloc. Asa de, 7 este elementul pivot.

PASUL 2: Începeți pointerii stânga și dreapta ca primul și, respectiv, ultimul element al matricei. Deci, indicatorul din stânga indică spre 5 la indexul 0 și indicatorul din dreapta indică spre 9 la indicele 5.

PASUL 3: Comparați elementul din indicatorul din stânga cu elementul pivot. Deoarece, 5 < 6 deplasează indicatorul din stânga la dreapta la indexul 1.

PASUL 4: Acum, încă 3 <6, așa că mutați indicatorul din stânga la încă un index la dreapta. Deci acum 7 > 6 nu mai incrementează indicatorul din stânga și acum indicatorul din stânga este la indicele 2.

PASUL 5: Acum, comparați valoarea de la indicatorul din dreapta cu elementul pivot. Deoarece 9 > 6 mutați indicatorul din dreapta spre stânga. Acum ca 2 < 6 nu mai mișcați indicatorul din dreapta.

PASUL 6: Schimbați ambele valori prezente la indicatorul din stânga și din dreapta.

PASUL 7: Mutați ambele indicatori încă un pas.

PASUL 8: Deoarece 6 = 6, mutați pointerii la încă un pas și opriți-vă când indicatorul din stânga traversează indicatorul din dreapta și returnați indexul indicatorului din stânga.

Deci, aici, pe baza abordării de mai sus, trebuie să scriem cod pentru schimbul de elemente și partiționarea matricei, așa cum s-a menționat în pașii de mai sus.

Cod pentru a schimba două numere JavaScenariu

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

Cod pentru a efectua partiția așa cum s-a menționat în pașii de mai sus

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;
}

Efectuați operația recursivă

Odată ce efectuați pașii de mai sus, va fi returnat indexul indicatorului din stânga și trebuie să îl folosim pentru a împărți matricea și a efectua sortarea rapidă pe acea parte. Prin urmare, se numește algoritmul Divide and Conquer.

Deci, sortarea rapidă este efectuată până când toate elementele din matricea din stânga și din matricea din dreapta sunt sortate.

Notă: Sortarea rapidă este efectuată pe aceeași matrice și nu sunt create matrice noi în acest proces.

Deci, trebuie să numim asta partiție () explicat mai sus și pe baza acestuia împărțim mulțime în părți. Deci, iată codul în care îl utilizaț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 result = quickSort(items, 0, items.length - 1);

Completați codul de sortare rapidă

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]

NOTĂ: Sortare rapidă rulează cu complexitatea timpului de O(nlogn).