Algoritem hitrega razvrščanja v JavaScript

Kaj je hitro razvrščanje?

Algoritem hitrega razvrščanja sledi pristopu Divide and Conquer. Elemente deli na manjše dele na podlagi nekega pogoja in izvaja operacije razvrščanja na teh razdeljenih manjših delih.

Algoritem hitrega razvrščanja je eden najpogosteje uporabljenih in priljubljenih algoritmov v katerem koli programskem jeziku. Če pa ste razvijalec JavaScript, boste morda že slišali za sort (), ki je že na voljo v JavaScript. Potem ste morda razmišljali, kaj potrebuje ta algoritem za hitro razvrščanje. Da bi to razumeli, najprej potrebujemo, kaj je razvrščanje in kaj privzeto razvrščanje v JavaScript.

Kaj je razvrščanje?

Razvrščanje ni nič drugega kot razvrščanje elementov v želenem vrstnem redu. Morda ste na to naleteli v šoli ali na fakulteti. Tako kot razvrščanje števil od manjšega do večjega (naraščajoče) ali od večjega do manjšega (padajoče) je tisto, kar smo videli do zdaj, in se imenuje sortiranje.

Privzeto razvrščanje v JavaScript

Kot smo že omenili, ima JavaScript sort () . Vzemimo primer z nekaj vrstami elementov, kot je [5,3,7,6,2,9], in želimo razvrstiti elemente polja v naraščajočem vrstnem redu. Preprosto pokličite sort () na elementu matrike in razvrsti elemente polja v naraščajočem vrstnem redu.

Koda:

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

Kaj je razlog, da v JavaScript izberete Quick sort over default sort ()

Čeprav sort () daje želeni rezultat, je težava v načinu razvrščanja elementov matrike. Privzeto razvrščanje () v JavaScriptu uporablja razvrščanje vstavljanja po V8 Engine v Chromu in združevanje po Mozilla Firefox in Safari .

Vendar to ni primerno, če morate razvrstiti veliko število elementov. Rešitev je torej uporaba hitrega razvrščanja za velike nabore podatkov.

Če želite popolnoma razumeti, morate vedeti, kako deluje hitro razvrščanje, in nam to podrobno ogledati zdaj.

Kaj je hitro razvrščanje?

Hitro razvrščanje sledi algoritmu Divide and Conquer . Razdeljuje elemente na manjše dele glede na neko stanje in izvaja operacije razvrščanja na teh razdeljenih manjših delih. Zato deluje dobro za velike nabore podatkov. Tukaj so koraki, kako hitro razvrščanje deluje s preprostimi besedami.

Najprej izberite element, ki ga želite poklicati kot vrtilni element.
Nato primerjajte vse elemente matrike z izbranim vrtilnim elementom in jih razporedite tako, da so elementi, manjši od vrtilnega elementa, levo od njega in večji od pivota desno.
Na koncu izvedite enake operacije na levem in desnem bočnem elementu do vrtilnega elementa.

Torej, to je osnovni oris hitrega razvrščanja. Tu so koraki, ki jih je treba upoštevati enega za drugim za hitro razvrščanje.

Kako deluje QuickSort

Najprej poiščite element "pivot" v matriki.
Zaženite levi kazalec pri prvem elementu polja.
Zaženite desni kazalec pri zadnjem elementu polja.
Primerjajte kazalec elementa z levim kazalcem in če je manjši od vrtilnega elementa, levi kazalec premaknite v desno (dodajte 1 levemu indeksu). Nadaljujte, dokler levi bočni element ni večji ali enak vrtilnemu elementu.
Primerjajte kazalec elementa z desnim kazalcem in če je ta večji od vrtilnega elementa, nato premaknite desni kazalec na levo (odštejte 1 do desnega indeksa). Nadaljujte, dokler desni bočni element ni manjši ali enak vrtilnemu elementu.
Preverite, ali je levi kazalec manjši ali enak desnemu kazalcu, nato pa elemente zagledajte na mestih teh kazalcev.
Povečajte levi kazalec, desni pa zmanjšajte.
Če je indeks levega kazalca še vedno manjši od indeksa desnega kazalca, ponovite postopek; sicer vrne indeks levega kazalca.

Poglejmo si te korake s primerom. Upoštevajmo vrsto elementov, ki jih moramo razvrstiti, [5,3,7,6,2,9].

Določite vrtilni element

Preden nadaljujemo s hitrim razvrščanjem, ima glavno vlogo izbira vrtilnega elementa. Če izberete prvi element kot vrtilni element, potem ima razvrščeno polje najslabše rezultate. Torej, vedno je priporočljivo, da za vrtilni element izberemo srednji element (dolžina matrike, deljena z 2) in naredimo enako.

Tu so koraki za izvedbo hitrega razvrščanja, ki je prikazan s primerom [5,3,7,6,2,9].

1. KORAK: Določite vrtišče kot srednji element. Torej, 7 je pivot element.

2. KORAK: Začnite levi in desni kazalnik kot prvi oziroma zadnji element polja. Torej, levi kazalec kaže na 5 pri indeksu 0, desni pa na 9 pri indeksu 5.

KORAK 3: Primerjajte element na levem kazalcu z vrtilnim elementom. Ker 5 <6 premakne levi kazalec v desno, da indeksira 1.

KORAK 4: Zdaj je še vedno 3 <6, tako da levi kazalec premaknite na še en kazalec v desno. Torej zdaj 7> 6 nehajte povečevati levi kazalec in zdaj je levi kazalec na indeksu 2.

5. KORAK: Zdaj primerjajte vrednost na desnem kazalcu z vrtilnim elementom. Ker je 9> 6, premaknite desni kazalec v levo. Zdaj, ko 2 <6 nehamo premikati desni kazalec.

6. KORAK: Zamenjajte obe vrednosti, prisotni v levem in desnem kazalcu.

7. KORAK: Premaknite oba kazalca še za en korak.

8. KORAK: Ker je 6 = 6, premaknite kazalce na še en korak in se ustavite, ko levi kazalec prečka desni kazalec in vrnete kazalec levega kazalca.

Torej, tu moramo na podlagi zgornjega pristopa napisati kodo za zamenjavo elementov in particioniranje matrike, kot je omenjeno v zgornjih korakih.

Koda za zamenjavo dveh številk v JavaScript:

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

Koda za izvedbo particije, kot je omenjeno v zgornjih korakih:

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

Izvedite rekurzivno operacijo

Ko izvedete zgornje korake, se vrne indeks levega kazalca, ki ga moramo uporabiti za razdelitev matrike in izvedbo hitrega razvrščanja na tem delu. Zato se imenuje algoritem Divide and Conquer.

Tako se izvede hitro razvrščanje, dokler niso razvrščeni vsi elementi v levem in desnem polju.

Opomba: Hitro razvrščanje se izvede na istem polju in v tem procesu ne nastanejo nobena nova polja.

Torej, to particijo () moramo poklicati zgoraj razloženo in na podlagi tega delimo matriko na dele. Tu je torej koda, kjer jo uporabljate,

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

Izpolnite kodo za hitro razvrščanje:

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]