QuickSorti algoritm sisse JavaScript

Mis on sorteerimine?

Sorteerimine pole muud kui elementide järjestamine soovitud järjekorras. Võib-olla olete sellega oma kooli- või kolledži päevil kokku puutunud. Nagu numbrite järjestamine väiksemast suuremaks (kasvav) või suuremast väiksemaks (kahanev), on see, mida me siiani nägime ja seda nimetatakse sortimiseks.

Vaikimisi sortimine JavaScript

Nagu varem mainitud, JavaSkriptil on sort (). Võtame näite mõne elemendi massiiviga, nagu [5,3,7,6,2,9] ja tahame sortida selle massiivi elemendid kasvavas järjekorras. Lihtsalt helista sort () üksuste massiivi ja 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 valida kiirsortimine vaikimisi sortimise() asemel JavaScript

Kuigi sort() annab soovitud tulemuse, seisneb probleem selles, kuidas see massiivi elemente sorteerib. Vaikimisi sort() sisse JavaSkripti kasutamine sisestamise sort by Chrome'i V8 mootor ja Ühenda sort by Mozilla Firefox ja safari.

Kuid muu see ei sobi, kui peate sorteerima suurt hulka elemente. Seega on lahendus suure andmestiku jaoks kasutada kiirsortimist.

Nii et täielikuks mõistmiseks peate teadma, kuidas kiirsortimine töötab, ja laskma meil seda nüüd üksikasjalikult näha.

Mis on kiirsorteerimine?

Järgneb kiire sorteerimine Jaga ja valluta algoritm. See jagab elemendid mõne tingimuse alusel väiksemateks osadeks ja sooritab sorteerimistoimingud nende jagatud väiksemate osadega. Seetõttu töötab see hästi suurte andmekogumite jaoks. Siin on lihtsate sõnadega kiirsortimise juhised.

1. Esmalt valige element, mida soovite kutsuda pöörlema element.
2. Järgmiseks võrrelge kõiki massiivi elemente valitud pivot-elemendiga ja korraldage need nii, et pivot-elemendist väiksemad elemendid oleksid sellest vasakul ja suuremad kui pivot-elemendid paremal.
3. Lõpuks tehke samad toimingud pöördeelemendi vasaku ja parema külje elementidega.

Niisiis, see on kiirsortimise põhijoon. Siin on sammud, mida tuleb kiirsortimiseks ükshaaval järgida.

Kuidas QuickSort töötab

1. Kõigepealt leidke "pööre" element massiivis.
2. Käivitage vasak kursor massiivi esimesest elemendist.
3. Alustage parempoolset kursorit massiivi viimasest elemendist.
4. Võrrelge vasakpoolse kursoriga osutavat elementi ja kui see on pivot-elemendist väiksem, siis liigutage vasakpoolset kursorit paremale (lisage vasakpoolsesse indeksisse 1). Jätkake seda seni, kuni vasakpoolne element on suurem või võrdne pöördeelemendiga.
5. Võrrelge parempoolse kursoriga osutavat elementi ja kui see on pivot-elemendist suurem, siis liigutage parempoolset kursorit vasakule (lahutage 1 paremale indeksile). Jätkake seda seni, kuni parempoolne element on pöördeelemendist väiksem või sellega võrdne.
6. Kontrollige, kas vasak kursor on väiksem või võrdne parempoolse kursoriga, seejärel vahetage elemendid nende osutite asukohtades.
7. Suurendage vasakut kursorit ja vähendage paremat kursorit.
8. Kui vasaku kursori indeks on ikka väiksem kui parempoolse kursori indeks, siis korrake protsessi; muidu tagastab vasakpoolse kursi indeksi.

Niisiis, vaatame neid samme näitega. Vaatleme sorteerimiseks vajalike elementide massiivi [5,3,7,6,2,9].

Määrake Pivot element

Kuid enne kiirsortimisega jätkamist mängib pivot-elemendi valimine suurt rolli. Kui valite pivot-elemendiks esimese elemendi, annab see sorteeritud massiivi halvima jõudluse. Seega on alati soovitatav valida pöördeelemendiks keskmine element (massiivi pikkus jagatud 2-ga) ja teeme sama.

Siin on sammud kiirsortimiseks, mida näidatakse näitega [5,3,7,6,2,9].

STEP 1: Määrake pöördepunkt keskmiseks elemendiks. Niisiis, 7 on pöördeelement.

STEP 2: Käivitage vasak ja parem osuti massiivi esimese ja viimase elemendina. Niisiis, vasak kursor osutab 5 indeksil 0 ja parempoolne kursor osutab 9 indeksil 5.

STEP 3: Võrrelge vasakpoolse kursori elementi pivot-elemendiga. Kuna 5 < 6 nihutab vasakut kursorit paremale, et indekseerida 1.

STEP 4: Nüüd on endiselt 3 <6, nii et nihutage vasak kursor veel ühe indeksiga paremale. Nii et nüüd 7 > 6 lõpetavad vasakpoolse kursi suurendamise ja nüüd on vasak kursor indeksis 2.

STEP 5: Nüüd võrrelge väärtust parempoolses kursoris pivot-elemendiga. Kuna 9 > 6 liigutage parempoolset kursorit vasakule. Nüüd, kui 2 < 6, lõpetage parempoolse kursori liigutamine.

STEP 6: Vahetage mõlemad vasak- ja parempoolses osuti väärtused üksteisega.

STEP 7: Liigutage mõlemat osutit veel ühe sammu võrra.

STEP 8: Kuna 6 = 6, liigutage kursorit veel ühe sammuni ja peatuge, kuna vasak kursor ristub parema kursoriga, ja tagastab vasakpoolse kursori indeksi.

Seega peame ülaltoodud lähenemisviisi põhjal kirjutama koodi elementide vahetamiseks ja massiivi partitsioonideks, nagu eespool kirjeldatud.

Kood kahe numbri vahetamiseks JavaScript

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

Kood partitsiooni teostamiseks, nagu ülaltoodud sammudes mainitud

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

Tehke rekursiivne toiming

Kui olete ülaltoodud toimingud sooritanud, tagastatakse vasakpoolse kursori indeks ja me peame seda kasutama massiivi jagamiseks ja selle osa kiirsortimiseks. Seetõttu nimetatakse seda jaga ja valluta algoritmiks.

Seega tehakse kiirsortimist seni, kuni kõik vasakpoolse ja parema massiivi elemendid on sorteeritud.

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

Niisiis, me peame sellele helistama partitsioon () eespool selgitatud ja selle põhjal jagame massiivi osadeks. Siin on kood, kus seda kasutate,

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äitke kiire sortimise kood

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]

MÄRKUS: Kiire sortimine töötab aja keerukusega O (nlogn).