QuickSort-algoritmi sisään JavaSkripti esimerkin kanssa

Mikä on pikalajittelu?

Nopea lajittelu on vertailulajittelualgoritmi, joka noudattaa Jaa ja valloita lähestymistapa. Se valitsee yhden elementin pivot-pisteeksi, jakaa taulukon osaan, joka sisältää pivot-pistettä pienempiä arvoja, ja osaan, joka sisältää suurempia arvoja, ja soveltaa sitten samaa menettelyä kumpaankin osaan, kunnes koko taulukko on järjestetty.

Pikalajittelu on yksi käytetyimmistä lajittelualgoritmeista kaikissa ohjelmointikielissä. Jos kirjoitat JavaKäsikirjoitusolet luultavasti jo käyttänyt sisäänrakennettua järjestellä() menetelmää, joten saatat ihmetellä, miksi erillinen pikalajittelun toteutus kannattaa opetella. Vastataksesi tähän sinun on ensin tiedettävä, mitä lajittelu tarkoittaa ja mikä on oletuslajittelu JavaSkripti todellakin tekee niin.

Kolme ominaisuutta määrittelee pikalajittelun:

• Paikan päällä: se järjestelee alkuperäisen uudelleen ryhmä eikä varaa toista saman kokoista taulukkoa.
• Rekursiivinen: Jokainen osio tuottaa kaksi pienempää aluetta, jotka lajitellaan samalla funktiolla.
• Epävakaa: Kaksi yhtäläisillä avaimilla varustettua elementtiä voi päätyä eri suhteelliseen järjestykseen kuin missä ne alkoivat.

Mitä on lajittelu?

Lajittelu tarkoittaa elementtien järjestämistä määrättyyn järjestykseen. Olet melkein varmasti törmännyt tähän koulussa: lukujen järjestäminen pienimmästä suurimpaan on nouseva järjestyksessä ja laittamalla ne suurimmasta pienimpään on aleneva järjestys. Lajittelu ei rajoitu numeroihin. Merkkijonot voidaan järjestää aakkosjärjestykseen, päivämäärät aikajärjestykseen ja objektit minkä tahansa valitsemasi kentän, kuten hinnan tai pistemäärän, mukaan.

Lajittelulla on merkitystä, koska järjestetty data mahdollistaa nopeammat toiminnot. Binäärihaku suoritetaan O(log n) ajassa, mutta vain lajitellulle syötteelle. Deduplikaatio, välikyselyt, sijoittelu ja yhdistämistoiminnot tulevat kaikki paljon halvemmiksi, kun data on järjestyksessä, minkä vuoksi jokaisessa kielessä on ainakin yksi lajittelurutiini.

Oletuslajittelu JavaKäsikirjoitus

Kuten aiemmin mainittu, JavaSkripti tarjoaa järjestellä()Ota pieni taulukko, kuten [5,3,7,6,2,9], jonka haluat olevan nousevassa järjestyksessä. Kutsutaan järjestellä() taulukossa näyttää tekevän juuri niin.

Yllä olevassa kuvakaappauksessa selainkonsoli tulostaa lajitellun taulukon. Tässä on sama koodi:

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

lähtö:

[ 2, 3, 5, 6, 7, 9 ]

Tulos on oikea, mutta vain vahingossa. Array.prototype.sort() muuntaa jokaisen elementin merkkijonoksi ja vertaa merkkijonoja ellet anna vertailufunktiota. Jokainen tämän taulukon arvo on yksinumeroinen, joten merkkijonojen järjestys sattuu vastaamaan numerojärjestystä. Muuta tietoja ja illuusio rikkoutuu.

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

lähtö:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

Mitä algoritmia sort() käyttää?

Spesifikaatiossa ei nimetä algoritmia, joten jokainen moottori valitsee omansa. Nykyaikaiset moottorit käyttävät kaikki yhdistämiseen perustuvaa algoritmia:

• V8 (Chrome, Edge, Node.js) on käyttänyt TimSort versiosta V8 7.0 lähtien, toimitettu Chrome 70:ssä.
• Hämähäkkiapina (Firefox) käyttää Yhdistä lajittelu.
• JavaScriptCore (Safari) käyttää myös Yhdistä lajittelu.

ES2019:stä lähtien kieli takaa, että sort() is vakaa, mikä sulkee pois pelkän pikalajittelun moottorin sisällä. Yhdistämiseen perustuva lajittelu tarvitsee O(n) apumuistia, ja sen on kutsuttava JavaSkriptivertailija jokaista vertailua varten. Käsin kirjoitettu numeerinen pikalajittelu vertaa numeroita suoraan ja lajittelee paikan päällä, joten se voi voittaa suurissa numeerisissa taulukoissa. 1 000 000 satunnaisen kokonaisluvun lajittelu Node.js 22:ssa kesti noin 100 ms alla olevan pikalajittelun avulla ja suunnilleen 210 ms sort((a, b) => a - b).

Joten Quick Sort on kirjoittamisen arvoinen, kun tarvitset lajittelua suoraan paikan päällä, tarkkaa muistin hallintaa tai yksinkertaisesti vankkaa ymmärrystä lajittelun toiminnasta. Tarkastellaanpa mekaniikkaa yksityiskohtaisesti.

Miten pikalajittelu toimii?

Pikalajittelu toistaa yhtä ydintoimintoa, jota kutsutaan osiointi, yhä pienemmillä alueilla. Tässä ovat vaiheet järjestyksessä:

1. Etsi kääntyä elementti taulukossa.
2. Aloita vasen osoitin alueen ensimmäisestä alkiosta.
3. Aloita oikea osoitin alueen viimeisestä alkiosta.
4. Vertaa vasemman osoittimen osoittamaa alkiota kääntöpisteeseen. Jos se on pienempi kuin kääntöpiste, siirrä vasenta osoitinta yhden askeleen oikealle. Jatka, kunnes vasen alkio on suurempi tai yhtä suuri kuin kääntöpiste.
5. Vertaa oikean osoittimen osoittamaa alkiota kääntöpisteeseen. Jos se on suurempi kuin kääntöpiste, siirrä oikean osoitinta yhden askeleen vasemmalle. Jatka, kunnes oikean osoittimen osoittama alkio on pienempi tai yhtä suuri kuin kääntöpiste.
6. Jos vasen osoitin on edelleen pienempi tai yhtä suuri kuin oikea osoitin, vaihda elementtien paikat.
7. Kasvata vasenta osoitinta ja vähennä oikeaa osoitinta.
8. Jos vasen indeksi on edelleen pienempi tai yhtä suuri kuin oikea indeksi, toista vaiheesta 4. Muussa tapauksessa palauta vasemman osoittimen indeksi.

Yllä oleva kaavio trackuvaa osoittimen liikkeitä esimerkkitaulukossa. Jokainen pivotia pienempi elementti päätyy sen vasemmalle puolelle ja jokainen suurempi elementti sen oikealle puolelle, mikä on täsmälleen se, mitä palautettu indeksi merkitsee. Alla oleva osio käy läpi saman taulukon askel askeleelta.

Pivot-elementin määrittäminen

Pivot-kohdan valitseminen on se yksittäinen päätös, joka erottaa nopean pikalajittelun hitaasta. Jos valitset aina ensimmäinen alkiolla, jo lajiteltu taulukko tuottaa huonoimman mahdollisen jaon: yhden tyhjän sivun ja yhden sivun jokaisella jäljellä olevalla alkiolla. Tämä muuttaa algoritmin muotoon O(n²). Kun otetaan huomioon keskimmäinen elementti (taulukon pituus jaettuna kahdella) välttää kyseisen ansan lajitellulla ja käänteisesti lajitellulla syötteellä, minkä vuoksi alla oleva koodi käyttää sitä.

Yleisiä pivot-strategioita:

• Ensimmäinen vai viimeinen elementti: Yksinkertaisin koodata, mutta O(n²) lajitellulla datalla.
• Keskimmäinen elementti: hyvä oletusarvo, joka käsittelee lajitellut ja käänteisesti lajitellut taulukot muodossa O(n log n).
• Satunnainen elementti: tekee pahimman mahdollisen syötteen konstruoinnin etukäteen mahdottomaksi.
• Kolmen mediaani: ottaa ensimmäisen, keskimmäisen ja viimeisen arvon mediaanin; vakiovalinta tuotantokirjastoissa.

Käy nyt läpi taulukon pikalajittelu [5,3,7,6,2,9].

STEP 1: Keskimmäinen elementti on nivelpiste. Kun vasen = 0 ja oikea = 5, Math.floor((5 + 0) / 2) antaa indeksin 2, joten pivot-arvo on 7.

STEP 2: Aloita osoittimet taulukon päistä. Vasen osoitin on indeksissä 0 (arvo 5) ja oikea osoitin on indeksin 5 kohdalla (arvo 9).

STEP 3: Vertaa vasemmanpuoleista arvoa pivot-pisteeseen. 5 < 7, joten siirry oikealle indeksiin 1. 3 < 7, joten siirry oikealle indeksiin 2. Arvo siellä on 7, joka ei ole pienempi kuin pivot-piste, joten vasen osoitin pysähtyy indeksiin 2.

STEP 4: Vertaa oikeanpuoleista arvoa pivot-pisteeseen. 9 > 7, joten siirry vasemmalle indeksiin 4. Siellä arvo on 2, joka ei ole suurempi kuin pivot-piste, joten oikeanpuoleinen osoitin pysähtyy indeksiin 4.

STEP 5: Vasen indeksi (2) on pienempi tai yhtä suuri kuin oikea indeksi (4), joten vaihda arvot keskenään. Taulukosta tulee [5,3,2,6,7,9].

STEP 6: Siirrä molempia osoittimia yhden askeleen sisäänpäin. Vasen osoitin on nyt indeksin 3 kohdalla ja oikea osoitin indeksin 3 kohdalla.

STEP 7: Toista skannaus. Indeksin 3 arvo on 6 ja 6 < 7, joten vasen osoitin etenee indeksiin 4. Indeksin 3 arvo ei ole suurempi kuin pivot-piste, joten oikea osoitin pysyy indeksissä 3.

STEP 8: Vasen indeksi (4) on nyt suurempi kuin oikea indeksi (3), joten silmukka päättyy ja funktio palauttaa 4Kaikki ennen indeksiä 4 on pienempi tai yhtä suuri kuin pivot-piste, ja kaikki indeksistä 4 eteenpäin on suurempi tai yhtä suuri kuin se.

Tuon läpikäynnin perusteella tarvitset koodia kahdelle toiminnolle: swapping kaksi elementtiä ja alueen jakaminen ositukseen.

Code vaihtaa kaksi Numbers in JavaKäsikirjoitus

Kuten yllä oleva editorin kuvakaappaus osoittaa, swap helper käyttää väliaikaista muuttujaa kahden indeksin arvojen vaihtamiseen. Se muuttaa taulukon suoraan eikä palauta mitään.

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

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

lähtö:

[ 9, 3, 7, 6, 2, 5 ]

Code Suorittaaksesi osion

Yllä olevan kuvakaappauksen koodi muuttaa vaiheet 1–8 funktioksi. Kaksi sisäistä silmukoita vie osoittimia eteenpäin, if lohko suorittaa vaihdon ja funktio palauttaa jakoindeksin.

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

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

lähtö:

[ 5, 3, 2, 6, 7, 9 ]
4

Tuloste vastaa manuaalista läpikäyntiä täsmälleen: yhden osiointikerran jälkeen taulukko on [5,3,2,6,7,9] ja palautettu jakoindeksi on 4.

Suorita rekursiivinen OperaTUKSEN

Kun osiointi palauttaa jakoindeksin, käytä sitä alueen jakamiseen ja suorita pikalajittelu molemmille puoliskoille. Siksi sitä kutsutaan hajoita ja hallitse -algoritmiksi. Rekursio jatkuu, kunnes jokainen alialue sisältää yhden elementin, jolloin koko taulukko lajitellaan.

Huomautus: Pikalajittelu toimii samalla taulukolla koko prosessin ajan. Prosessissa ei luoda uusia taulukoita, minkä vuoksi se on paikkakohtainen algoritmi.

Joten soitat osio () yllä selitetty funktio ja käytä sen paluuarvoa jakaaksesi ryhmä osiin. Tässä on koodi, joka tekee sen:

Huomaa kuvakaappauksessa korostetut kaksi vartijaehtoa. left < index - 1 vahvistaa, että vasemmalla puolella on jäljellä vähintään kaksi elementtiä, ja index < right vahvistaa saman oikealle puolelle. Ilman noita suojia funktio kutsuisi itseään ikuisesti yksialkioisilla arvoalueilla.

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 items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

lähtö:

[ 2, 3, 5, 6, 7, 9 ]

Täydellinen pikalajittelu Code

Yhdistämällä swap-, partition- ja rekursio-osat saadaan täydellinen toteutus:

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

lähtö:

[ 2, 3, 5, 6, 7, 9 ]

Yllä oleva kuvakaappaus näyttää koko ohjelman editorissa sekä lajitellun taulukon konsolissa. Tämä toteutus varmistettiin jo lajiteltua taulukkoa, käänteisesti lajiteltua taulukkoa, kaksoiskappaleita ja identtisiä arvoja sisältäviä taulukoita, negatiivisia lukuja, yhden alkion ja tyhjää taulukkoa vasten, ja se palauttaa oikean tuloksen jokaisessa tapauksessa.

Pikalajittelun aika- ja paikkakompleksisuus

Jokainen osiointikierros koskettaa jokaista välin alkiota kerran, joten yksi kierros maksaa O(n). Kokonaiskustannukset riippuvat siis siitä, kuinka monta kertaa taulukko voidaan jakaa ennen kuin välit muuttuvat triviaaleiksi.

Avaruuden monimutkaisuus on O(log n) tälle paikalliselle versiolle. Toista taulukkoa ei ole allokoitu, joten ainoa ylimääräinen muisti on rekursiopino, ja tasapainotettu jakaminen pitää pinon noin log₂(n) kehystä syvänä. Pahimmassa tapauksessa pino kasvaa O(n) kehykseen, minkä vuoksi erittäin suuret taulukot voivat ylittää kutsupinon.

Kaksi lukua tekee tästä konkreettista. Yllä olevalla koodilla 4 096 satunnaisarvon lajitteluun käytettiin noin 65 000 vertailua teoreettista n·log₂(n):ää vasten, joka oli 49 152. Syvin rekursio saavutti 24 kehystä, kun taas log₂(4,096) on 12. Molemmat luvut ovat O(n log n) -algoritmin odotetun pienen vakiokertoimen sisällä.

Pikalajittelu vs. muu lajittelu Algorithms

Pikalajittelu on harvoin ainoa vaihtoehto. Alla oleva taulukko vertaa sitä muihin algoritmeihin, joihin todennäköisimmin törmäät, jotta voit valita oikean vaihtoehdon tiedoillesi.

Käytännössä nopea lajittelu yleensä toimii parhaiten, koska sen sisäinen silmukka on tiukka ja se toimii välimuistiystävällisillä yhtenäisillä alueilla. Valitse yhdistämislajittelu, kun tarvitset taatun O(n log n) -rajaisen tai vakaan järjestyksen, kekolajittelu, kun muistia on erittäin rajoitetusti, ja lisäyslajittelu erittäin pienille tai lähes lajitelluille taulukoille. Tuotantokirjastot yhdistävät usein näitä: introlajittelu aloittaa nopealla lajittelulla, vaihtaa kekolajitteluun, jos rekursio on liian syvä, ja päättyy lisäyslajitteluun pienillä alueilla.

Objektien ja merkkijonojen nopea lajittelu

Tähän mennessä esitetty toteutus vertaa arvoja < ja >, mikä rajoittaa sen numeroihin. Todellisten sovellusten on lajiteltava esineet ominaisuuden, merkkijonojen aakkosjärjestyksessä tai päivämäärien aikajärjestyksessä mukaan. Korjaus on siirtää vertailu takaisinkutsutoimintoon, täsmälleen samalla tavalla kuin sisäänrakennettu sort() ei.

Komparaattori vastaanottaa kaksi arvoa ja palauttaa negatiivisen luvun, kun ensimmäisen pitäisi tulla ensin, positiivisen luvun, kun toisen pitäisi tulla ensin, ja nollan, kun kaksi ovat yhtäpitäviä. Kahden kiinteästi koodatun vertailun korvaaminen komparaattorikutsuilla saa algoritmin toimimaan minkä tahansa tietotyypin kanssa.

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

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

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

lähtö:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

Kolme yksityiskohtaa on syytä huomata. Rekursiovartija on nyt left >= right, joka on oikein mille tahansa alueelle eikä riipu ulomman taulukon pituudesta. Merkkijonojen vertailussa käytetään localeCompare() jotta aksenttiset merkit ja kirjainkoko käsitellään oikein raakakoodipisteen sijaan. Ja koska pikalajittelu ei ole vakaa, saman palkan omaavat tietueet saattavat vaihtaa paikkoja; lajittele tasapelin ratkaisevalla toisella avaimella, jos alkuperäinen järjestys on sinulle tärkeä.

Oletko valmis jatkamaan? Vahvista perusasiat tällä JavaSkriptin esittely, harjoittele osoittimen mekaniikkaa JavaSkriptisilmukat, työstää enemmän käytännön JavaSkriptikoodiesimerkkejä, vertaile toteutuksia Lisäyslajittelu ja Keon lajittelutai lisää tähän algoritmiin staattisia tyyppejä käyttämällä TypeScript viite.

UKK