QuickSorti algoritm JavaScriptis

Mis on kiire sortimine?

Kiire sortimise algoritm järgib jagamise ja vallutamise lähenemist. See jagab elemendid väiksemateks osadeks, lähtudes mõnest tingimusest ja sooritades nende jagatud väiksemate osade sortimistoiminguid.

Kiire sorteerimise algoritm on üks kõige enam kasutatavaid ja populaarsemaid algoritme mis tahes programmeerimiskeeles. Kuid kui olete JavaScripti arendaja, võite olla kuulnud sort () -ist, mis on juba JavaScriptis saadaval. Siis võisite mõelda, mis on selle kiire sorteerimise algoritmi vajadus. Selle mõistmiseks vajame kõigepealt, mis on sortimine ja mis on JavaScripti vaikesorteerimine.

Mis on sortimine?

Sorteerimine pole muud kui elementide korrastamine soovitud järjekorras. Võib-olla olete sellega kokku puutunud oma kooli või kolledži päevil. Nagu numbrite järjestamine väiksematest suurematesse (kasvavalt) või suurematest väiksematesse (kahanevatesse) on see, mida nägime siiani ja mida nimetatakse sortimiseks.

Vaikimisi sortimine JavaScriptis

Nagu varem mainitud, on JavaScripti sort () . Võtame näite, milles on vähe elementide massiive, näiteks [5,3,7,6,2,9], ja soovime selle massiivi elemendid järjestada kasvavas järjekorras. Lihtsalt helistage üksuste massiivi sort () ja see sorteerib massiivi elemendid kasvavas järjekorras.

Kood:

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

Mis on põhjus, miks JavaScripti vaikesorteerimise () asemel valida kiire sortimine

Kuigi sort () annab soovitud tulemuse, on probleem selles, kuidas ta massiivi elemente sorteerib. Järjekorra () JavaScripti kasutab sisestamise omamoodi poolt V8 Mootori Chrome'i ja Mestimissortimine poolt Mozilla Firefox ja Safari .

Kuid muu see ei sobi, kui peate sortima palju elemente. Niisiis, lahendus on kasutada kiiret sorteerimist suurte andmekogumite jaoks.

Nii et selle täielikuks mõistmiseks peate teadma, kuidas Kiire sortimine töötab, ja andke meile sellest nüüd üksikasjalik ülevaade.

Mis on kiire sortimine?

Kiire sortimine järgib jagamise ja vallutamise algoritmi. See on elementide jagamine väiksemateks osadeks mõne tingimuse alusel ja sortimisoperatsioonide teostamine nende jagatud väiksemate osade jaoks. Seega töötab see hästi suurte andmekogumite puhul. Niisiis, siin on sammud, kuidas kiire sortimine toimib lihtsate sõnadega.

Kõigepealt valige element, mis on võimalik välja kutsuda pivot element.
Järgmisena võrrelge kõiki massiivi elemente valitud pöördelemendiga ja korraldage need nii, et vasakpoolsed elemendid, mis on väiksemad kui pöördelement, jäävad paremale.
Lõpuks tehke samad toimingud pöördelementi vasakule ja paremale küljele.

Nii et see on kiire sortimise põhijoon. Siin on sammud, mida tuleb ükshaaval järgida, et kiiret sortimist teostada.

Kuidas QuickSort töötab

Esmalt leidke massiivist element "pivot" .
Alustage vasakut kursorit massiivi esimesest elemendist.
Alustage parempoolset kursorit massiivi viimasest elemendist.
Võrrelge elementi, mis osutab vasakule ja kui see on väiksem kui pöördelement, siis liigutage vasak kursor paremale (lisage vasakule indeksile 1). Jätkake seda seni, kuni vasakpoolne element on pöördelemendist suurem või sellega võrdne.
Võrrelge elementi, mis osutab parempoolse kursoriga, ja kui see on suurem kui pöördelement, siis liigutage parem kursor vasakule (lahutage 1 paremale indeksile). Jätkake seda seni, kuni parempoolne element on pöördelemendist väiksem või sellega võrdne.
Kontrollige, kas vasak osuti on paremal või paremal, seejärel saagige elemente nende osutite asukohtades.
Suurendage vasakut ja paremat.
Kui vasaku kursori indeks on ikka parema kursori indeksist väiksem, siis korrake protsessi; muul juhul tagastatakse vasaku kursori indeks.

Vaatame neid samme koos näitega. Vaatleme sorteeritavate elementide massiivi [5,3,7,6,2,9].

Määrake Pivoti element

Kuid enne kiirsorteerimisega jätkamist on pivoti elemendi valimisel suur roll. Kui valite pöördelemendiks esimese elemendi, annab see sorteeritud massiivis halvima jõudluse. Niisiis on alati soovitatav valida pöördelemendiks keskmine element (massiivi pikkus jagatuna 2-ga) ja me teeme sama.

Siin on näited [5,3,7,6,2,9] näidatud kiire sortimise toimingud.

1. SAMM: määrake pöördelement keskmise elemendina. Niisiis, 7 on pöördelement.

2. SAMM: alustage vasakut ja paremat osutit vastavalt massiivi esimese ja viimase elemendina. Niisiis, vasak kursor osutab indeksil 0 5 ja parempoolne kursor indeksil 9 9 .

3. SAMM: võrrelge vasakpoolse kursori elementi pöördelemendiga. Alates sellest nihutab 5 <6 vasakut kursorit paremale indeksisse 1.

4. SAMM: nüüd ikka 3 <6, nii et nihutage vasak kursor paremale veel ühele indeksile. Nüüd lõpetab 7> 6 vasaku kursori suurendamise ja nüüd on vasak kursor indeksil 2.

5. SAMM: võrrelge nüüd parempoolse kursori väärtust pöördelemendiga. Kuna 9> 6, liigutage parempoolset kursorit vasakule. Nüüd kui 2 <6 lõpetavad parema kursori liigutamise.

6. SAMM: vahetage mõlemad vasakul ja paremal kursoril olevad väärtused omavahel.

7. SAMM: teisaldage mõlemad näpunäited veel üks samm.

8. SAMM: kuna 6 = 6, liigutage kursorid veel ühele sammule ja peatage, kui vasak osuti ületab parempoolse kursori ja tagastab vasaku kursori indeksi.

Niisiis, siin ülaltoodud lähenemisviisi põhjal peame kirjutama koodi elementide vahetamiseks ja massiivi jaotamiseks, nagu eespool nimetatud sammudes mainitud.

Kood kahe numbri vahetamiseks JavaScriptis:

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

Kood partitsiooni täitmiseks, nagu ülalnimetatud juhistes mainitud:

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

Tehke rekursiivne toiming

Kui olete ülaltoodud toimingud teinud, tagastatakse vasakpoolse kursori indeks ja me peame seda massiivi jagamiseks ja selle osa kiirsorteerimiseks tegema. Seega nimetatakse seda jagamise ja vallutamise algoritmiks.

Niisiis viiakse läbi kiire sortimine, kuni kõik vasakpoolse ja parema massiivi elemendid on sorteeritud.

Märkus: Kiire sortimine toimub samal massiivil ja uusi massiive selle käigus ei looda.

Niisiis, peame kutsuma selle ülalpool selgitatud partitsiooni () ja jagama selle põhjal massiivi osadeks. Nii et siin on kood, kus te seda kasutate,

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

Täielik kiirsorteerimiskood:

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]