Mikä on pikalajittelu?
Pikalajittelu algoritmi noudattaa hajoita ja hallitse lähestymistapa. Se jakaa elementit pienempiin osiin jonkin ehdon perusteella ja suorittaa lajittelutoiminnot jaetuille pienemmille osille.
Quick Sort -algoritmi on yksi käytetyimmistä ja suosituimmista algoritmeista kaikilla ohjelmointikielillä. Mutta jos olet JavaScript-kehittäjä, saatat olla kuullut sort (): sta, joka on jo saatavana JavaScript-muodossa. Sitten saatat ajatella, mikä on tämän pikalajittelualgoritmin tarve. Tämän ymmärtämiseksi tarvitsemme ensin, mikä on lajittelu ja mikä on oletuslajittelu JavaScriptissä.
Mikä on lajittelu?
Lajittelu ei ole muuta kuin elementtien järjestäminen haluamassamme järjestyksessä. Olet ehkä törmännyt tähän koulusi tai yliopistosi päivinä. Aivan kuten numeroiden järjestämistä pienemmistä suurempiin (nouseviin) tai suuremmista pienempiin (laskeviin) on se, mitä näimme tähän asti ja joita kutsutaan lajitteluksi.
Oletuslajittelu JavaScriptissä
Kuten aiemmin mainittiin, JavaScriptillä on lajittelu () . Otetaan esimerkki muutamalla elementtiryhmällä, kuten [5,3,7,6,2,9], ja haluamme lajitella tämän taulukon elementit nousevassa järjestyksessä. Kutsu vain lajittelun () kohteet taulukko ja se lajittelee taulukkoelementit nousevassa järjestyksessä.
Koodi:
var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]
Mikä on syy valita pikalajittelu oletuslajittelun () sijaan JavaScriptiin
Vaikka lajittelu () antaa haluamasi tuloksen, ongelma on siinä, miten se lajittelee taulukkoelementit. Oletuslajittelujärjestys () JavaScript käyttää lisäyslajittelun jonka V8 Chrome ja lomituslajittelu mennessä Mozilla Firefox ja Safari .
Mutta muu tämä ei sovi, jos sinun on lajiteltava suuri määrä elementtejä. Joten ratkaisu on käyttää pikalajittelua suurille tietojoukoille.
Joten, jotta ymmärrät täydellisesti, sinun on tiedettävä, kuinka pikalajittelu toimii, ja anna meidän nähdä se nyt yksityiskohtaisesti.
Mikä on pikalajittelu?
Pikalajittelu seuraa Divide and Conquer -algoritmia. Se jakaa elementit pienempiin osiin jonkin ehdon perusteella ja suorittaa lajittelutoiminnot näille jaetuille pienemmille osille. Siksi se toimii hyvin suurille tietojoukoille. Joten tässä ovat vaiheet, kuinka pika-lajittelu toimii yksinkertaisilla sanoilla.
- Valitse ensin elementti, jota kutsutaan pivot- elementiksi.
- Vertaa seuraavaksi kaikkia taulukkoelementtejä valittuun pivot-elementtiin ja järjestä ne siten, että pivot-elementtiä pienemmät elementit ovat vasemmalla ja suuremmat kuin pivot on oikealla.
- Suorita lopuksi samat toiminnot kääntöelementille vasemmalla ja oikealla puolella.
Joten, tämä on pikalajittelun peruspiirre. Tässä on vaiheet, joita on noudatettava yksi kerrallaan nopean lajittelun suorittamiseksi.
Kuinka QuickSort toimii
- Etsi ensin "pivot" -elementti taulukosta.
- Aloita vasen osoitin taulukon ensimmäisestä osasta.
- Aloita oikea osoitin taulukon viimeisestä osasta.
- Vertaa elementtiä osoittamaan vasempaan osoittimeen ja jos se on pienempi kuin kääntöelementti, siirrä sitten vasen osoitin oikealle (lisää 1 vasempaan hakemistoon). Jatka tätä, kunnes vasemmanpuoleinen elementti on suurempi tai yhtä suuri kuin kääntöelementti.
- Vertaa osoittavaa elementtiä oikeaan osoittimeen ja jos se on suurempi kuin kääntöelementti, siirrä sitten oikea osoitin vasemmalle (vähennä 1 oikealle hakemistolle). Jatka tätä, kunnes oikean sivun elementti on pienempi tai yhtä suuri kuin kääntöelementti.
- Tarkista, onko vasen osoitin pienempi tai yhtä suuri kuin oikea osoitin, ja näki sitten elementit näiden osoittimien sijainneissa.
- Lisää vasenta osoitinta ja vähennä oikeaa osoittinta.
- Jos vasemman osoittimen indeksi on edelleen pienempi kuin oikean osoittimen indeksi, toista prosessi; muuten palauta vasemman osoittimen hakemisto.
Katsotaanpa nämä vaiheet esimerkin avulla. Tarkastellaan joukkoa elementtejä, jotka meidän on lajiteltava [5,3,7,6,2,9].
Määritä kääntöelementti
Mutta ennen pikalajittelun jatkamista pivot-elementin valitsemisella on tärkeä rooli. Jos valitset ensimmäisen elementin kääntöelementiksi, se tuottaa huonon suorituskyvyn lajitellussa taulukossa. Joten on aina suositeltavaa valita keskielementti (taulukon pituus jaettuna 2: lla) kääntöelementtinä ja teemme saman.
Tässä on vaiheet pika-lajittelun suorittamiseksi, joka näytetään esimerkissä [5,3,7,6,2,9].
VAIHE 1: Määritä kääntö keskielementiksi. Joten 7 on kääntöelementti.
VAIHE 2: Aloita vasen ja oikea osoitin taulukon ensimmäisenä ja viimeisenä elementtinä. Joten vasen osoitin osoittaa kohtaan 5 indeksissä 0 ja oikea osoitin kohtaan 9 indeksissä 5.
VAIHE 3: Vertaa vasemman osoittimen elementtiä kääntöelementtiin. Koska 5 <6 siirtää vasenta osoitinta oikealle hakemistoon 1.
VAIHE 4: Nyt vielä 3 <6, joten siirrä vasen osoitin vielä yhteen hakemistoon oikealle. Joten nyt 7> 6 lopettaa vasemman osoittimen lisäämisen ja nyt vasen osoitin on indeksissä 2.
VAIHE 5: Vertaa nyt oikean osoittimen arvoa kääntöelementtiin. Koska 9> 6, siirrä oikeaa osoittinta vasemmalle. Nyt kun 2 <6 lopettaa oikean osoittimen siirtämisen.
VAIHE 6: Vaihda molemmat arvot, jotka ovat vasemmalla ja oikealla osoittimella keskenään.
VAIHE 7: Siirrä molempia osoittimia vielä yksi askel.
VAIHE 8: Koska 6 = 6, siirrä osoittimet vielä yhteen vaiheeseen ja pysähdy, kun vasen osoitin ylittää oikean osoittimen ja palauttaa vasemman osoittimen hakemiston.
Joten tässä yllä olevan lähestymistavan perusteella meidän on kirjoitettava koodi elementtien vaihtamiseksi ja taulukon osioimiseksi, kuten edellä mainituissa vaiheissa mainittiin.
Koodi vaihtaaksesi kaksi numeroa JavaScriptissä:
function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}
Koodi osion suorittamiseksi yllä olevien ohjeiden mukaisesti:
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;}
Suorita rekursiivinen toiminto
Kun olet suorittanut yllä olevat vaiheet, vasemman osoittimen hakemisto palautetaan, ja meidän on käytettävä sitä jakamaan taulukko ja suorittamaan pikalajittelu kyseiselle osalle. Siksi sitä kutsutaan Divide and Conquer -algoritmiksi.
Joten pikalajittelu suoritetaan, kunnes kaikki vasemman ja oikean taulukon elementit on lajiteltu.
Huomaa: Pikalajittelu suoritetaan samalle ryhmälle, eikä uusia taulukoita luoda prosessin aikana.
Joten meidän on kutsuttava tätä osiota (), joka on selitetty edellä, ja sen perusteella jaamme taulukon osiin. Joten tässä on koodi missä käytät sitä,
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äydellinen pikalajittelukoodi:
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]
HUOMAUTUS: Nopea lajittelu suoritetaan O: n aikakompleksisuuden (nlogn) kanssa.