Algoritm QuickSort în JavaScript

Ce este Sortarea rapidă?

Algoritmul de sortare rapidă urmează abordarea Divide și Conquer. Împarte elementele în părți mai mici în funcție de anumite condiții și efectuează operațiile de sortare pe acele părți mai mici împărțite.

Algoritmul de sortare rapidă este unul dintre cei mai utilizați și populari algoritmi în orice limbaj de programare. Dar, dacă sunteți un dezvoltator JavaScript, atunci ați auzit de sort () care este deja disponibil în JavaScript. Apoi, s-ar putea să vă fi gândit care este nevoia acestui algoritm de sortare rapidă. Pentru a înțelege acest lucru, mai întâi avem nevoie de sortare și de sortare implicită în JavaScript.

Ce este Sortarea?

Sortarea nu este altceva decât aranjarea elementelor în ordinea dorită. S-ar putea să fi întâlnit acest lucru în timpul școlii sau al colegiului. La fel ca aranjarea numerelor de la mai mic la mai mare (ascendent) sau de la mai mare la mai mic (descendent) este ceea ce am văzut până acum și se numește sortare.

Sortare implicită în JavaScript

După cum sa menționat anterior, JavaScript are sort () . Să luăm un exemplu cu puține matrice de elemente precum [5,3,7,6,2,9] și dorim să sortăm aceste elemente matrice în ordine crescătoare. Doar apelați sort () pe matricea de articole ș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 care alegeți Sortare rapidă peste Sortare implicită () în JavaScript

Deși sort () oferă rezultatul pe care îl dorim, problema constă în felul în care sortează elementele matrice. Sortarea implicită () în JavaScript utilizează sortarea prin inserție după motorul V8 al Chrome și Merge sortează după Mozilla Firefox și Safari .

Dar, altceva nu este potrivit dacă trebuie să sortați un număr mare de elemente. Deci, soluția este să folosiți Sortare rapidă pentru seturi de date mari.

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

Ce este sortarea rapidă?

Sortarea rapidă urmează algoritmul Divide and Conquer . Împarte elementele în părți mai mici pe baza unei anumite condiții și efectuează operațiuni de sortare pe acele părți mai mici împărțite. Prin urmare, funcționează bine pentru seturi de date mari. Deci, iată pașii în care funcționează sortarea rapidă în cuvinte simple.

Mai întâi selectați un element care urmează să fie numit ca element pivot .
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 să fie la dreapta.
În cele din urmă, efectuați aceleași operații pe elementele laterale stânga și dreapta la elementul pivot.

Deci, acesta este schema 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

Mai întâi găsiți elementul "pivot" în matrice.
Porniți indicatorul stâng la primul element al matricei.
Porniți indicatorul drept la ultimul element al matricei.
Comparați elementul care indică cu indicatorul stâng și dacă este mai mic decât elementul pivot, mutați indicatorul stâng spre dreapta (adăugați 1 la indexul stâng). Continuați acest lucru până când elementul din stânga este mai mare sau egal cu elementul pivot.
Comparați elementul care arată cu indicatorul drept și dacă este mai mare decât elementul pivot, mutați indicatorul drept la stânga (scădeți 1 la indexul drept). Continuați acest lucru până când elementul din dreapta este mai mic sau egal cu elementul pivot.
Verificați dacă indicatorul stâng este mai mic sau egal cu indicatorul drept, apoi ați văzut elementele în locațiile acestor indicatori.
Măriți indicatorul stâng și diminuați indicatorul drept.
Dacă indicele indicatorului stâng este încă mai mic decât indicele indicatorului drept, atunci repetați procesul; altfel returnează indexul indicatorului stâng.

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

Determinați elementul pivot

Dar înainte de a merge mai departe cu sortarea rapidă, selectarea elementului pivot joacă un rol major. Dacă selectați primul element ca element pivot, atunci acesta oferă cea mai slabă performanță în matricea sortată. Deci, este întotdeauna recomandabil să alegeți elementul de mijloc (lungimea matricei împărțit la 2) ca element pivot și procedăm la fel.

Iată pașii pentru efectuarea sortării rapide care este prezentat cu un exemplu [5,3,7,6,2,9].

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

PASUL 2: Începeți indicatorii stânga și dreapta ca prim și ultimul element al matricei. Deci, indicatorul stâng indică 5 la indexul 0, iar indicatorul drept indică 9 la indexul 5.

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

PASUL 4: Acum, încă 3 <6, deci deplasați indicatorul stâng la un alt index spre dreapta. Deci, acum 7> 6 oprește incrementarea indicatorului stâng, iar acum indicatorul stâng este la indexul 2.

PASUL 5: Acum, comparați valoarea indicatorului corect cu elementul pivot. Din moment ce 9> 6 mutați cursorul drept la stânga. Acum, pe măsură ce 2 <6 oprește mișcarea indicatorului drept.

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

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

PASUL 8: De la 6 = 6, mutați indicatoarele la încă un pas și opriți-vă în timp ce indicatorul stâng traversează indicatorul drept și întoarceți indexul indicatorului stâng.

Deci, aici, pe baza abordării de mai sus, trebuie să scriem cod pentru schimbarea elementelor și partiționarea matricei așa cum se menționează în pașii de mai sus.

Cod pentru a schimba două numere în JavaScript:

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 se menționează în pașii de mai sus:

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

Efectuați operația recursivă

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

Deci, Sortarea rapidă se execută până când toate elementele din matricea din stânga și din matrice din dreapta sunt sortate.

Notă: Sortarea rapidă se efectuează pe aceeași matrice și nu sunt create matrici noi în acest proces.

Deci, trebuie să numim această partiție () explicată mai sus și pe baza căreia împărțim matricea în părți. Iată deci codul în care îl folosiț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 result = quickSort(items, 0, items.length - 1);

Completează 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 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]