Algoritmul QuickSort în JavaScript cu exemplu

Ce este sortarea rapidă?

Sortare rapida este un algoritm de sortare prin comparație care urmează Diviza și cuceri abordare. Selectează un element ca pivot, împarte matricea într-o parte care conține valori mai mici decât pivotul și o parte care conține valori mai mari, apoi aplică aceeași procedură fiecărei părți până când întreaga matrice este ordonată.

Sortarea rapidă este unul dintre cei mai utilizați algoritmi de sortare în fiecare limbaj de programare. Dacă scrieți JavaScenariu, probabil ați folosit deja funcția încorporată fel() metoda, așa că s-ar putea să vă întrebați de ce merită să învățați o implementare separată de sortare rapidă. Pentru a răspunde la această întrebare, trebuie mai întâi să știți ce înseamnă sortarea și care este sortarea implicită în JavaScriptul chiar o face.

Trei proprietăți definesc sortarea rapidă:

• În loc: rearanjează originalul mulțime și nu alocă o a doua matrice de aceeași dimensiune.
• Recursiv: fiecare partiție produce două intervale mai mici care sunt sortate după aceeași funcție.
• Instabil: Două elemente cu chei egale pot ajunge într-o ordine relativă diferită față de cea în care au început.

Ce este Sortarea?

Sortarea înseamnă aranjarea elementelor într-o ordine definită. Aproape sigur ați întâlnit acest lucru la școală: aranjarea numerelor de la cel mai mic la cel mai mare este... ascendent ordine, iar așezarea lor de la cea mai mare la cea mai mică este Descendentă ordine. Sortarea nu se limitează la numere. Șirurile pot fi ordonate alfabetic, datele cronologic, iar obiectele după orice câmp ales, cum ar fi prețul sau scorul.

Sortarea este importantă deoarece datele ordonate permit operațiuni mai rapide. O căutare binară se execută în timp O(log n), dar numai pe date de intrare sortate. Operațiunile de deduplicare, interogările de interval, clasare și îmbinare devin mult mai ieftine odată ce datele sunt în ordine, motiv pentru care fiecare limbaj de programare include cel puțin o rutină de sortare.

Sortare implicită în JavaScenariu

Ca menționat mai devreme, JavaScriptul oferă fel()Luați o matrice mică, cum ar fi [5,3,7,6,2,9], pe care o doriți în ordine crescătoare. Apelarea fel() pe matrice pare să facă exact asta.

Captura de ecran de mai sus arată consola browserului care afișează matricea sortată. Iată același cod:

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

ieșire:

[ 2, 3, 5, 6, 7, 9 ]

Rezultatul este corect, dar numai din întâmplare. Array.prototype.sort() convertește fiecare element într-un șir de caractere și compară șirurile de caractere cu excepția cazului în care furnizați o funcție de comparare. Fiecare valoare din această matrice este o singură cifră, deci ordinea șirurilor se întâmplă să corespundă cu ordinea numerică. Schimbați datele și iluzia se epuizează.

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

ieșire:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

Ce algoritm folosește sort()?

Specificația nu denumește un algoritm, așa că fiecare motor își alege propriul algoritm. Motoarele moderne folosesc toate un algoritm bazat pe îmbinare:

• V8 (Chrome, Edge, Node.js) a folosit TimSort începând cu versiunea V8 7.0, disponibil în Chrome 70.
• Maimuta paianjen (Firefox) utilizează fuzionează sort.
• JavaScriptCore (Safari) folosește și fuzionează sort.

Începând cu ES2019, limba garantează că sort() is stabil, ceea ce exclude o sortare rapidă simplă în interiorul motorului. Sortarea bazată pe îmbinare necesită O(n) memorie auxiliară și trebuie să apeleze JavaComparator de scripturi pentru fiecare comparație. O funcție de sortare rapidă numerică scrisă de mână compară numerele direct și sortează pe loc, astfel încât poate fi eficientă pe tablouri numerice mari. Sortarea a 1,000,000 de numere întregi aleatorii pe Node.js 22 a durat aproximativ 100 ms cu Sortarea rapidă de mai jos și aproximativ 210 ms implementate cu sort((a, b) => a - b).

Așadar, merită să scrieți Quick Sort atunci când aveți nevoie de sortare in situ, control strict asupra memoriei sau pur și simplu o înțelegere solidă a modului în care funcționează sortarea. Să analizăm mecanismele în detaliu.

Cum funcționează sortarea rapidă?

Sortarea rapidă repetă o operație principală, numită partiționare, pe intervale din ce în ce mai mici. Iată pașii în ordine:

1. Găsi pivot element din matrice.
2. Începeți indicatorul din stânga la primul element al intervalului.
3. Începeți indicatorul din dreapta la ultimul element al intervalului.
4. Comparați elementul de la indicatorul din stânga cu pivotul. Dacă este mai mic decât pivotul, mutați indicatorul din stânga cu un pas spre dreapta. Continuați până când elementul din stânga este mai mare sau egal cu pivotul.
5. Comparați elementul de la indicatorul din dreapta cu pivotul. Dacă este mai mare decât pivotul, mutați indicatorul din dreapta cu un pas spre stânga. Continuați până când elementul din dreapta este mai mic sau egal cu pivotul.
6. Dacă indicatorul din stânga este în continuare mai mic sau egal cu indicatorul din dreapta, inversați cele două elemente.
7. Crește indicatorul din stânga și decrementează indicatorul din dreapta.
8. Dacă indicele din stânga este încă mai mic sau egal cu indicele din dreapta, repetați de la pasul 4. În caz contrar, returnați indicele indicatorului din stânga.

Diagrama de mai sus tracacele mișcări ale indicatorului pe o matrice eșantion. Fiecare element mai mic decât pivotul se termină în stânga sa, iar fiecare element mai mare se termină în dreapta sa, exact ceea ce marchează indexul returnat. Secțiunea de mai jos prezintă pas cu pas aceeași matrice.

Cum se determină elementul pivot

Alegerea pivotului este singura decizie care diferențiază o sortare rapidă de una lentă. Dacă luați întotdeauna în considerare primul element, o matrice deja sortată produce cea mai proastă divizare posibilă: o parte goală și o parte cu fiecare element rămas. Aceasta transformă algoritmul în O(n²). Luând de mijloc elementul (lungimea matricei împărțită la doi) evită această capcană pentru intrările sortate și sortate invers, motiv pentru care codul de mai jos îl folosește.

Strategii comune de pivotare:

• Primul sau ultimul element: cel mai simplu de codat, dar O(n²) pe date sortate.
• Elementul din mijloc: o valoare implicită bună care gestionează tablouri sortate și sortate invers în O(n log n).
• Element aleatoriu: face imposibilă construirea în avans a datelor de intrare pentru cel mai defavorabil caz.
• Mediana a trei: ia mediana primei, celei din mijloc și celei de-a doua valori; alegerea standard în bibliotecile de producție.

Acum parcurgeți sortarea rapidă pe matrice [5,3,7,6,2,9].

PASUL 1: Pivotul este elementul din mijloc. Cu stânga = 0 și dreapta = 5, Math.floor((5 + 0) / 2) dă indicele 2, deci valoarea pivot este 7.

PASUL 2: Indicatorii încep la capetele tabloului. Indicatorul din stânga este la indexul 0 (valoare 5) și indicatorul din dreapta este la indicele 5 (valoare 9).

PASUL 3: Comparați valoarea din stânga cu pivotul. 5 < 7, deci mutați la dreapta la indicele 1. 3 < 7, deci mutați la dreapta la indicele 2. Valoarea de acolo este 7, care nu este mai mică decât pivotul, deci indicatorul din stânga se oprește la indicele 2.

PASUL 4: Comparați valoarea din dreapta cu pivotul. 9 > 7, deci mutați la stânga la indicele 4. Valoarea de acolo este 2, care nu este mai mare decât pivotul, deci indicatorul din dreapta se oprește la indicele 4.

PASUL 5: Indicele din stânga (2) este mai mic sau egal cu indicele din dreapta (4), deci inversați cele două valori. Tabloul devine [5,3,2,6,7,9].

PASUL 6: Mutați ambele indicatoare cu un pas spre interior. Indicatorul din stânga se află acum la indicele 3, iar indicatorul din dreapta la indicele 3.

PASUL 7: Repetați scanarea. Valoarea de la indicele 3 este 6, iar 6 < 7, deci indicatorul din stânga avansează la indicele 4. Valoarea de la indicele 3 nu este mai mare decât pivotul, deci indicatorul din dreapta rămâne la indicele 3.

PASUL 8: Indicele din stânga (4) este acum mai mare decât indicele din dreapta (3), deci bucla se termină și funcția returnează 4Tot ce se află înainte de indicele 4 este mai mic sau egal cu pivotul, iar tot ce se află de la indicele 4 încolo este mai mare sau egal cu acesta.

Pe baza acestei soluții, aveți nevoie de cod pentru două operații: swapping două elemente și partiționarea unui interval.

Code a schimba două Numbers in JavaScenariu

După cum se arată în captura de ecran a editorului de mai sus, ajutorul pentru swap folosește o variabilă temporară pentru a schimba valorile la doi indecși. Mută ​​direct matricea și nu returnează nimic.

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

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

ieșire:

[ 9, 3, 7, 6, 2, 5 ]

Code pentru a efectua partiționarea

Codul din captura de ecran de mai sus transformă pașii 1-8 într-o funcție. Cele două funcții interne bucle avansați indicatoarele, if Blocul efectuează schimbarea, iar funcția returnează indexul de divizare.

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

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

ieșire:

[ 5, 3, 2, 6, 7, 9 ]
4

Rezultatul corespunde exact cu ghidul manual: după o singură trecere prin partiție, matricea este [5,3,2,6,7,9], iar indexul de divizare returnat este 4.

Efectuați recursivul OperaTION

Odată ce partiționarea returnează indexul de divizare, acesta se folosește pentru a împărți intervalul și a rula sortarea rapidă pe fiecare jumătate. De aceea se numește algoritmul „Împarte și Constrânge”. Recursivitatea continuă până când fiecare subinterval conține un singur element, moment în care întreaga matrice este sortată.

Notă: Sortarea rapidă funcționează pe aceeași matrice pe tot parcursul procesului. Nu se creează matrice noi în acest proces, ceea ce îl face un algoritm in-site.

Deci, îl suni pe partiție () funcția explicată mai sus și folosiți valoarea sa returnată pentru a diviza mulțime în părți. Iată codul care face acest lucru:

Observați cele două condiții de protecție evidențiate în captură de ecran. left < index - 1 confirmă că cel puțin două elemente rămân în partea stângă și index < right confirmă același lucru și pentru partea dreaptă. Fără aceste gărzi, funcția s-ar apela singură la nesfârșit pe intervalele cu un singur element.

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 items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

ieșire:

[ 2, 3, 5, 6, 7, 9 ]

Sortare rapidă completă Code

Combinând componentele swap, partition și recursivitate, se obține implementarea 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); // swapping 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);

ieșire:

[ 2, 3, 5, 6, 7, 9 ]

Captura de ecran de mai sus prezintă programul complet în editor împreună cu matricea sortată din consolă. Această implementare a fost verificată în raport cu o matrice deja sortată, o matrice sortată invers, matrice care conțin valori duplicate și identice, numere negative, un singur element și o matrice goală și returnează rezultatul corect în fiecare caz.

Complexitatea timpului și spațiului sortării rapide

Fiecare trecere de partiție atinge fiecare element din interval o singură dată, deci o singură trecere costă O(n). Prin urmare, costul total depinde de câte ori poate fi împărțită matricea înainte ca intervalele să devină triviale.

Complexitatea spațială este O(log n) pentru această versiune in-place. Nu este alocat niciun al doilea tablou, așa că singura memorie suplimentară este stiva recursivă, iar divizarea echilibrată menține acea stivă cu o adâncime de aproximativ log₂(n) cadre. În cel mai rău caz degenerat, stiva crește la O(n) cadre, motiv pentru care tablourile foarte mari pot depăși stiva de apeluri.

Două numere concretizează acest lucru. Sortarea a 4,096 de valori aleatorii cu codul de mai sus a folosit aproximativ 65,000 de comparații față de un n·log₂(n) teoretic de 49,152, iar cea mai profundă recursiune a atins 24 de cadre, în timp ce log₂(4096) este 12. Ambele cifre se încadrează în factorul constant mic așteptat de la un algoritm O(n log n).

Sortare rapidă vs. alte sortări Algorithms

Sortarea rapidă este rareori singura opțiune. Tabelul de mai jos o compară cu ceilalți algoritmi pe care îi veți întâlni cel mai probabil, astfel încât să îl puteți alege pe cel potrivit pentru datele dvs.

Sortarea rapidă este de obicei cea mai eficientă în practică, deoarece bucla sa internă este strânsă și funcționează în intervale contigue care acceptă memoria cache. Alegeți sortarea prin îmbinare atunci când aveți nevoie de o legătură O(n log n) garantată sau de o ordonare stabilă, sortarea heap atunci când memoria este extrem de constrânsă și sortarea prin inserție pentru matrice foarte mici sau aproape sortate. Bibliotecile de producție le combină frecvent: introsortarea începe cu sortarea rapidă, trece la sortarea heap dacă recursivitatea devine prea profundă și se termină cu sortarea prin inserție pe intervale mici.

Cum să sortați rapid obiecte și șiruri de caractere

Implementarea prezentată până acum compară valorile cu < și >, ceea ce îl restricționează la numere. Aplicațiile reale trebuie să sorteze obiecte printr-o proprietate, șiruri alfabetice sau date cronologice. Soluția este mutarea comparației într-o funcție de apel invers, exact ca în modul încorporat sort() nu.

Un comparator primește două valori și returnează un număr negativ atunci când prima ar trebui să fie prima, un număr pozitiv atunci când a doua ar trebui să fie prima și zero atunci când cele două sunt echivalente. Înlocuirea celor două comparații hard-coded cu apeluri de comparare face ca algoritmul să funcționeze pe orice tip de date.

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

function partition(items, left, right, compare) {
    var pivot = items[Math.floor((right + left) / 2)],
        i     = left,
        j     = right;
    while (i <= j) {
        while (compare(items[i], pivot) < 0) { i++; }
        while (compare(items[j], pivot) > 0) { j--; }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

ieșire:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

Trei detalii merită menționate. Garda recursivă este acum left >= right, care este corect pentru orice interval și nu depinde de lungimea matricei exterioare. Compararea șirurilor de caractere folosește localeCompare() astfel încât caracterele accentuate și majusculele și minusculele să fie gestionate corect în loc de punct de cod brut. Și deoarece Sortarea rapidă nu este stabilă, înregistrările care au același salariu își pot schimba locurile; sortați după o a doua cheie de departajare dacă ordinea originală este importantă pentru dvs.

Ești gata să continui? Consolidează elementele fundamentale cu JavaIntroducere în scenariu, exersează mecanica indicatorului în JavaBucle de script, lucrează prin mai multe practic JavaExemple de cod de script, comparați implementările în Sortare prin inserție și Sortare în grămadă, sau adăugați tipuri statice la acest algoritm cu TypeScript referinţă.

Întrebări frecvente