QuickSort-algoritmi sisään JavaKäsikirjoitus

Mitä on lajittelu?

Lajittelu ei ole muuta kuin elementtien järjestämistä haluamaasi järjestykseen. Olet ehkä törmännyt tähän koulu- tai yliopistopäivinäsi. Kuten numeroiden järjestäminen pienemmästä suurempaan (nouseva) tai suuremmasta pienempään (laskeva) on se, mitä olemme nähneet tähän asti, ja sitä kutsutaan lajitteluksi.

Oletuslajittelu JavaKäsikirjoitus

Kuten aiemmin mainittu, JavaKäsikirjoituksessa on järjestellä(). Otetaan esimerkki, jossa on muutama elementtiryhmä, kuten [5,3,7,6,2,9] ja haluamme lajitella tämän taulukon elementit nousevaan järjestykseen. Soita vain järjestellä() kohteita -taulukkoon ja se lajittelee taulukon elementit nousevaan järjestykseen.

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 oletussort() in sijaan JavaKäsikirjoitus

Vaikka sort() antaa haluamamme tuloksen, ongelma on siinä, miten se lajittelee taulukon elementit. Oletus sort() in JavaScript käyttää lisäyslaji by Chromen V8-moottori ja Yhdistä lajittelu by mozilla Firefox ja safari.

Mutta muut tämä ei sovellu, jos sinun on lajiteltava suuri määrä elementtejä. Joten ratkaisu on käyttää nopeaa lajittelua suurille tietojoukoille.

Ymmärtääksesi täysin, sinun on tiedettävä, kuinka Pikalajittelu toimii, ja anna meidän nähdä se nyt yksityiskohtaisesti.

Mikä on nopea lajittelu?

Nopea lajittelu seuraa Jaa ja valloita algoritmi. Se jakaa elementtejä pienempiin osiin jonkin ehdon perusteella ja suorittaa lajittelutoiminnot niille jaetuille pienemmille osille. Siksi se toimii hyvin suurille tietojoukoille. Joten tässä on vaiheet, kuinka nopea lajittelu toimii yksinkertaisin sanoin.

1. Valitse ensin elementti, jota kutsutaan nimellä kääntyä elementti.
2. Seuraavaksi vertaa kaikkia taulukon elementtejä valittuun pivot-elementtiin ja järjestä ne siten, että pivot-elementtiä pienemmät elementit ovat sen vasemmalla ja pivot-elementtiä suuremmat sen oikealla puolella.
3. Suorita lopuksi samat toimenpiteet kääntöelementin vasemmalle ja oikealle puolelle.

Tämä on siis pikalajittelun peruspiirteet. Tässä ovat vaiheet, jotka on suoritettava yksitellen pikalajittelun suorittamiseksi.

Kuinka QuickSort toimii

1. Etsi ensin "pivot" elementti taulukossa.
2. Aloita vasen osoitin taulukon ensimmäisestä elementistä.
3. Aloita oikea osoitin taulukon viimeisestä elementistä.
4. Vertaa elementtiä osoittavaa vasempaan osoittimeen ja jos se on pienempi kuin pivot-elementti, siirrä vasenta osoitinta oikealle (lisää 1 vasempaan indeksiin). Jatka tätä, kunnes vasemman puolen elementti on suurempi tai yhtä suuri kuin kääntöelementti.
5. Vertaa elementtiä osoittavaa oikeaan osoittimeen ja jos se on suurempi kuin pivot-elementti, siirrä oikea osoitin vasemmalle (vähennä 1 oikeaan indeksiin). Jatka tätä, kunnes oikeanpuoleinen elementti on pienempi tai yhtä suuri kuin kääntöelementti.
6. Tarkista, onko vasen osoitin pienempi tai yhtä suuri kuin oikea osoitin, ja vaihda sitten elementit näiden osoittimien paikoissa.
7. Kasvata vasenta osoitinta ja vähennä oikeaa osoitinta.
8. Jos vasemman osoittimen indeksi on edelleen pienempi kuin oikean osoittimen indeksi, toista prosessi; muussa tapauksessa palauttaa vasemman osoittimen indeksin.

Joten katsotaanpa nämä vaiheet esimerkin avulla. Tarkastellaanpa elementtien joukkoa, jotka meidän täytyy lajitella, on [5,3,7,6,2,9].

Määritä Pivot-elementti

Mutta ennen kuin jatkat pikalajittelua, pivot-elementin valitseminen on tärkeä rooli. Jos valitset ensimmäisen elementin pivot-elementiksi, se antaa huonoimman suorituskyvyn lajitetussa taulukossa. Joten on aina suositeltavaa valita keskimmäinen elementti (taulukon pituus jaettuna kahdella) pivot-elementiksi ja teemme samoin.

Tässä ovat vaiheet nopean lajittelun suorittamiseksi, joka näytetään esimerkissä [5,3,7,6,2,9].

STEP 1: Määritä nivel keskielementiksi. Niin, 7 on pivot-elementti.

STEP 2: Aloita vasen ja oikea osoitin taulukon ensimmäisinä ja viimeisinä elementteinä. Joten vasen osoitin osoittaa 5 indeksissä 0 ja oikea osoitin osoittaa 9 indeksillä 5.

STEP 3: Vertaa vasemman osoittimen elementtiä pivot-elementtiin. Koska 5 < 6 siirrä vasenta osoitinta oikealle indeksointiin 1.

STEP 4: Nyt edelleen 3 <6, joten siirrä vasen osoitin yhdelle indeksille lisää oikealle. Joten nyt 7 > 6 lopettaa vasemman osoittimen kasvattamisen ja nyt vasen osoitin on indeksissä 2.

STEP 5: Vertaa nyt oikean osoittimen arvoa pivot-elementtiin. Koska 9 > 6 siirrä oikea osoitin vasemmalle. Nyt 2 < 6 lopeta oikean osoittimen liikuttaminen.

STEP 6: Vaihda vasemman ja oikean osoittimen molemmat arvot keskenään.

STEP 7: Siirrä molempia osoittimia vielä yksi askel.

STEP 8: Koska 6 = 6, siirrä osoittimia vielä yhteen askeleeseen ja lopeta, kun vasen osoitin ylittää oikean osoittimen ja palauttaa vasemman osoittimen indeksin.

Joten tässä yllä olevan lähestymistavan perusteella meidän on kirjoitettava koodi elementtien vaihtamista ja taulukon osiointia varten, kuten yllä olevissa vaiheissa mainittiin.

Koodi kahden numeron vaihtamiseksi JavaKäsikirjoitus

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

Koodi suorittaaksesi osion yllä olevissa vaiheissa mainitulla tavalla

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //swap two elements
            i++;
            j--;
        }
    }
    return i;
}

Suorita rekursiivinen operaatio

Kun olet suorittanut yllä olevat vaiheet, vasemman osoittimen indeksi palautetaan, ja meidän on käytettävä sitä taulukon jakamiseen ja nopean lajittelun suorittamiseen kyseiselle osalle. Siksi sitä kutsutaan Divide and Conquer -algoritmiksi.

Joten pikalajittelu suoritetaan, kunnes kaikki vasemman ja oikean taulukon elementit on lajiteltu.

Huomautus: Nopea lajittelu suoritetaan samalle taulukolle, eikä uusia taulukoita luoda prosessin aikana.

Joten meidän on kutsuttava tämä osio () selitettiin yllä ja jaamme sen perusteella ryhmä osiin. Joten tässä on koodi, jossa käytät sitä,

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var result = quickSort(items, 0, items.length - 1);

Täydellinen nopea lajittelukoodi

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 element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray); //prints [2,3,5,6,7,9]

HUOMAUTUS: Nopea lajittelu suoritetaan Time Complexity -toiminnolla O(nlogn).