Algoritam brzog sortiranja u JavaScript-u

Što je brzo sortiranje?

Algoritam brzog sortiranja slijedi pristup podijeli i osvoji. Dijeli elemente na manje dijelove na temelju nekog stanja i izvršavajući operacije sortiranja na tim podijeljenim manjim dijelovima.

Algoritam brzog sortiranja jedan je od najčešće korištenih i najpopularnijih algoritama u bilo kojem programskom jeziku. Ali ako ste programer za JavaScript, možda ste čuli za sort () koji je već dostupan u JavaScript-u. Tada ste možda razmišljali koja je potreba ovog algoritma za brzo sortiranje. Da bismo to razumjeli, prvo nam treba što je sortiranje, a što zadano sortiranje u JavaScript-u.

Što je sortiranje?

Sortiranje nije ništa drugo nego slaganje elemenata redoslijedom koji želimo. Možda ste se s tim susreli u školskim ili fakultetskim danima. Poput slaganja brojeva od manjeg do većeg (uzlazno) ili od većeg prema manjem (silazno) ono je što smo do sada vidjeli i naziva se sortiranje.

Zadano sortiranje u JavaScript-u

Kao što je ranije spomenuto, JavaScript ima sort () . Uzmimo primjer s nekoliko polja elemenata poput [5,3,7,6,2,9] i želimo sortirati ove elemente niza u rastućem redoslijedu. Samo pozovite sort () na nizu predmeta i on sortira elemente niza u rastućem redoslijedu.

Kodirati:

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

Koji je razlog da u JavaScript-u odaberete Brzo sortiranje umjesto zadanog sortiranja ()

Iako sort () daje rezultat koji želimo, problem leži u načinu sortiranja elemenata niza. Zadana vrsta () u JavaScriptu koristi za umetanje vrsta po V8 motor Chrome i spoji nekako tako Mozilla Firefox i Safari .

Ali, drugo ovo nije prikladno ako trebate razvrstati velik broj elemenata. Dakle, rješenje je korištenje brzog sortiranja za velike skupove podataka.

Dakle, da biste u potpunosti razumjeli, morate znati kako funkcionira brzo sortiranje i pustiti nas da to sada detaljno vidimo.

Što je brzo sortiranje?

Brzo sortiranje slijedi algoritam Podijeli i osvoji . Dijeli elemente na manje dijelove na temelju nekog stanja i izvodi operacije sortiranja na tim podijeljenim manjim dijelovima. Stoga dobro radi za velike skupove podataka. Evo koraka kako brzo sortiranje djeluje jednostavnim riječima.

Prvo odaberite element koji treba pozvati kao stožerni element.
Dalje, usporedite sve elemente niza s odabranim zakretnim elementom i rasporedite ih na takav način da su elementi manji od pivot elementa slijeva, a veći od pivota desno.
Na kraju, izvedite iste operacije na lijevoj i desnoj bočnoj strani elementa za okretanje.

Dakle, to je osnovni obris brze sorte. Evo koraka koje treba slijediti jedan po jedan za brzo izvršavanje sortiranja.

Kako funkcionira QuickSort

Prvo pronađite element "pivot" u polju.
Pokrenite lijevi pokazivač na prvom elementu niza.
Pokrenite desni pokazivač na posljednjem elementu niza.
Usporedite element koji pokazuje s lijevim pokazivačem i ako je manji od pivot elementa, pomaknite lijevi pokazivač udesno (dodajte 1 lijevom indeksu). Nastavite tako dok lijevi bočni element ne bude veći ili jednak osovinskom elementu.
Usporedite element koji pokazuje s desnim pokazivačem i ako je veći od pivot elementa, pomaknite desni pokazivač ulijevo (oduzmite 1 desnom indeksu). Nastavite tako dok desni bočni element ne bude manji ili jednak osovinskom elementu.
Provjerite je li lijevi pokazivač manji ili jednak desnom pokazivaču, a zatim ugledajte elemente na mjestima tih pokazivača.
Povećajte lijevi pokazivač, a desni smanjite.
Ako je indeks lijevog pokazivača i dalje manji od indeksa desnog pokazivača, ponovite postupak; inače vraća indeks lijevog pokazivača.

Dakle, pogledajmo ove korake na primjeru. Razmotrimo niz elemenata koje moramo razvrstati [5,3,7,6,2,9].

Odredite element zakretanja

Ali prije nego što krenete prema naprijed s brzim sortiranjem, odabir pivot elementa igra glavnu ulogu. Ako prvi element odaberete kao stožerni element, to daje najlošiju izvedbu u sortiranom nizu. Dakle, uvijek je poželjno odabrati srednji element (duljina niza podijeljena s 2) kao pivot element i mi radimo isto.

Evo koraka za izvođenje brzog sortiranja koji je prikazan na primjeru [5,3,7,6,2,9].

KORAK 1: Odredite stožer kao srednji element. Dakle, 7 je pivot element.

KORAK 2: Pokrenite lijevi i desni pokazivač kao prvi, odnosno zadnji element niza. Dakle, lijevi pokazivač pokazuje na 5 na indeksu 0, a desni na 9 na indeksu 5.

KORAK 3: Usporedite element na lijevom pokazivaču s osovinskim elementom. Budući da 5 <6 pomiče lijevi pokazivač udesno za indeksiranje 1.

KORAK 4: Sad, još uvijek 3 <6, pa pomaknite lijevi pokazivač na još jedan indeks udesno. Dakle, sada 7> 6 prestanite povećavati lijevi pokazivač i sada je lijevi pokazivač na indeksu 2.

KORAK 5: Usporedite sada vrijednost na desnom pokazivaču s osovinskim elementom. Budući da je 9> 6 pomaknite desni pokazivač ulijevo. Sada dok 2 <6 prestane pomicati desni pokazivač.

KORAK 6: Zamijenite obje vrijednosti prisutne na lijevom i desnom pokazivaču.

KORAK 7: Pomaknite oba pokazivača još jedan korak.

KORAK 8: Budući da je 6 = 6, pomaknite pokazivače na još jedan korak i zaustavite se dok lijevi pokazivač prelazi desni i vraća indeks lijevog pokazivača.

Dakle, ovdje na temelju gornjeg pristupa, trebamo napisati kod za zamjenu elemenata i particioniranje niza kako je spomenuto u gornjim koracima.

Kôd za zamjenu dva broja u JavaScript-u:

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

Kôd za izvođenje particije kako je spomenuto u gornjim koracima:

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

Izvršite rekurzivnu operaciju

Jednom kada izvršite gornje korake, vratit će se indeks lijevog pokazivača i to trebamo upotrijebiti za dijeljenje niza i brzo sortiranje na tom dijelu. Stoga se naziva algoritam Divide and Conquer.

Dakle, brzo sortiranje se izvodi dok se ne razvrstaju svi elementi na lijevom i desnom nizu.

Napomena: Brzo sortiranje izvodi se na istom nizu i u procesu se ne stvaraju novi nizovi.

Dakle, ovu particiju () moramo nazvati gore objašnjeno i na temelju toga dijelimo niz na dijelove. Dakle, ovdje je kod gdje ga koristite,

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

Kompletni kôd za brzo sortiranje:

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]