QuickSort algoritmus be JavaSzkript példával

Mi az a Gyors rendezés?

Gyors rendezés egy összehasonlító rendezési algoritmus, amely a következőt követi: Oszd meg és uralkodj megközelítés. Kiválaszt egy elemet pivotként, a tömböt felosztja egy olyan részre, amely a pivotnál kisebb értékeket tartalmaz, és egy olyan részre, amely nagyobb értékeket tartalmaz, majd ugyanazt az eljárást alkalmazza mindkét részre, amíg a teljes tömb rendezett nem lesz.

A gyors rendezés az egyik legszélesebb körben használt rendezési algoritmus minden programozási nyelvben. Ha írsz JavaForgatókönyvvalószínűleg már használtad a beépített rendezés () metódus, így felmerülhet benned a kérdés, hogy miért érdemes egy különálló Gyorsrendezés implementációt megtanulni. A válaszadáshoz először is tudnod kell, mit jelent a rendezés, és mi az alapértelmezett rendezés a JavaA szkript tényleg ezt teszi.

A gyors rendezést három tulajdonság határozza meg:

• Helyben: átrendezi az eredetit sor és nem foglal le egy második, azonos méretű tömböt.
• Rekurzív: minden partíció két kisebb tartományt hoz létre, amelyeket ugyanaz a függvény rendez.
• Instabil: Két azonos kulcsú elem végül eltérő relatív sorrendbe kerülhet, mint ahonnan elkezdődött.

Mi az a rendezés?

A rendezés az elemek meghatározott sorrendbe rendezését jelenti. Ezzel szinte biztosan találkoztál már az iskolában: a számok sorrendbe állítása a legkisebbtől a legnagyobbig... emelkedő sorrendben, és a legnagyobbtól a legkisebbig haladva csökkenő sorrend. A rendezés nem korlátozódik számokra. A karakterláncok betűrendben, a dátumok időrendben, az objektumok pedig bármely választott mező, például ár vagy pontszám szerint rendezhetők.

A rendezés azért fontos, mert a rendezett adatok gyorsabb műveleteket tesznek lehetővé. A bináris keresés O(log n) időt vesz igénybe, de csak rendezett bemeneten. A deduplikáció, a tartománylekérdezések, a rangsorolás és az egyesítési műveletek mind sokkal olcsóbbá válnak, ha az adatok rendezettek, ezért minden nyelv tartalmaz legalább egy rendezési rutint.

Alapértelmezett rendezés JavaForgatókönyv

Mint korábban említettük, JavaA szkript biztosítja rendezés ()Vegyünk egy kis tömböt, például [5,3,7,6,2,9], amelyet növekvő sorrendbe szeretnénk rendezni. Hívás rendezés () a tömbön pontosan ezt teszi.

A fenti képernyőképen a böngésző konzolja látható, amint kinyomtatja a rendezett tömböt. Itt ugyanaz a kód:

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

output:

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

Az eredmény helyes, de csak véletlenül. Az Array.prototype.sort() függvény minden elemet karakterlánccá alakít, és összehasonlítja a karakterláncokat. hacsak nem adsz meg egy összehasonlító függvényt. Ebben a tömbben minden érték egyjegyű, így a karakterláncok sorrendje megegyezik a számok sorrendjével. Az adatok módosításával az illúzió megszűnik.

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

output:

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

Melyik algoritmust használja a sort()?

A specifikáció nem nevez meg algoritmust, így minden motor a sajátját választja. A modern motorok mind egy összevonáson alapuló algoritmust használnak:

• V8 (Chrome, Edge, Node.js) használta TimSort V8 7.0 verzió óta, a Chrome 70-ben szállítva.
• Pók majom (Firefox) használ összevonási rendezés.
• JavaScriptCore (Safari) is használja összevonási rendezés.

Az ES2019 óta a nyelv garantálja, hogy sort() is stabil, ami kizárja a motoron belüli egyszerű gyors rendezést. Az egyesítésen alapuló rendezés O(n) segédmemóriát igényel, és meg kell hívnia a JavaSzkript-összehasonlító minden egyes összehasonlításhoz. Egy kézzel írott numerikus gyorsrendezés közvetlenül összehasonlítja a számokat, és helyben rendez, így nagy numerikus tömbökön is sikeres lehet. 1 000 000 véletlenszerű egész szám rendezése a Node.js 22-ben nagyjából ennyi időt vett igénybe. 100 ms az alábbi gyors rendezéssel és nagyjából 210 ms ahol sort((a, b) => a - b).

Tehát a Gyorsrendezés megírása akkor érdemes, ha helybeni rendezésre, a memória feletti szigorú ellenőrzésre, vagy egyszerűen csak a rendezés működésének alapos megértésére van szükség. Nézzük meg részletesen a mechanikát.

Hogyan működik a gyors rendezés?

A Gyorsrendezés egy alapvető műveletet ismétel, az úgynevezett particionálás, egyre kisebb és kisebb tartományokon. Íme a lépések sorrendben:

1. Keresse meg a pivot elem a tömbben.
2. A bal oldali mutatót a tartomány első eleménél kell indítani.
3. A jobb oldali mutatót a tartomány utolsó eleménél indítsa.
4. Hasonlítsa össze a bal oldali mutatónál lévő elemet a forgásponttal. Ha kisebb, mint a forgáspont, mozgassa a bal oldali mutatót egy lépéssel jobbra. Folytassa addig, amíg a bal oldali elem nagyobb vagy egyenlő nem lesz a forgásponttal.
5. Hasonlítsa össze a jobb mutatónál lévő elemet a forgásponttal. Ha az nagyobb, mint a forgáspont, mozgassa a jobb mutatót egy lépéssel balra. Folytassa addig, amíg a jobb oldali elem kisebb vagy egyenlő nem lesz a forgásponttal.
6. Ha a bal oldali mutató továbbra is kisebb vagy egyenlő a jobb oldali mutatóval, cserélje fel a két elemet.
7. Növelje a bal mutatót és csökkentse a jobb mutatót.
8. Ha a bal oldali index továbbra is kisebb vagy egyenlő a jobb oldali indexszel, ismételje meg a 4. lépéstől. Ellenkező esetben adja vissza a bal oldali mutató indexét.

A fenti ábra tracezeket a mutatómozgásokat egy minta tömbön mutatja. Minden, a pivotnál kisebb elem a bal oldalára, minden nagyobb elem pedig a jobb oldalára kerül sor, ami pontosan az, amit a visszaadott index jelöl. Az alábbi szakasz lépésről lépésre végigvezeti ugyanazon a tömbön.

A pivot elem meghatározása

A pivot kiválasztása az egyetlen döntés, ami megkülönbözteti a gyors rendezést a lassútól. Ha mindig a első elem esetén egy már rendezett tömb a lehető legrosszabb felosztást eredményezi: egy üres oldalt és egy oldalt minden megmaradt elemmel. Ez az algoritmust O(n²)-vé alakítja. középső Az elem (a tömb hossza osztva kettővel) elkerüli ezt a csapdát rendezett és fordított rendezésű bemenet esetén, ezért használja az alábbi kód.

Gyakori pivot stratégiák:

• Első vagy utolsó elem: legegyszerűbb kódolni, de rendezett adatokon O(n²).
• Középső elem: egy jó alapértelmezett érték, amely rendezett és fordított rendezésű tömböket kezel O(n log n) formátumban.
• Véletlenszerű elem: lehetetlenné teszi a legrosszabb eset előzetes kiszámítását.
• Három mediánja: az első, középső és utolsó érték mediánját veszi; ez a standard választás az éles könyvtárakban.

Most menjünk végig a tömb gyors rendezésének folyamatán. [5,3,7,6,2,9].

STEP 1: A pivot a középső elem. Bal = 0 és jobb = 5 esetén Math.floor((5 + 0) / 2) 2-es indexet ad, tehát a pivot érték 7.

STEP 2: A mutatók a tömb végein kezdődjenek. A bal oldali mutató a 0. indexnél van (érték 5), és a jobb mutató az 5. indexnél van (érték 9).

STEP 3: Hasonlítsd össze a bal oldali értéket a pivottal. 5 < 7, tehát mozogj jobbra az 1. indexhez. 3 < 7, tehát mozogj jobbra a 2. indexhez. Az ottani érték 7, ami nem kisebb, mint a pivot, tehát a bal oldali mutató a 2. indexnél áll meg.

STEP 4: Hasonlítsd össze a jobb oldali értéket a pivottal. 9 > 7, tehát lépj balra a 4-es indexre. Az ottani érték 2, ami nem nagyobb, mint a pivot, így a jobb oldali mutató a 4-es indexnél megáll.

STEP 5: A bal oldali index (2) kisebb vagy egyenlő, mint a jobb oldali index (4), ezért cseréljük fel a két értéket. A tömb a következőképpen alakul: [5,3,2,6,7,9].

STEP 6: Mozgasd mindkét mutatót egy lépéssel befelé. A bal oldali mutató most a 3-as indexen, a jobb oldali pedig a 3-as indexen van.

STEP 7: Ismételd meg a keresést. A 3-as indexnél lévő érték 6, és 6 < 7, így a bal oldali mutató a 4-es indexre ugrik. A 3-as indexnél lévő érték nem nagyobb, mint a pivot, így a jobb oldali mutató a 3-as indexen marad.

STEP 8: A bal oldali index (4) most nagyobb, mint a jobb oldali index (3), így a ciklus véget ér, és a függvény visszatérési értéke 4A 4-es index előtti minden kisebb vagy egyenlő a pivot értékével, és a 4-es indextől felfelé minden nagyobb vagy egyenlő vele.

Az útmutató alapján két művelethez kell kód: swapping két elem és egy tartomány particionálása.

Code kettőt cserélni Numbers in JavaForgatókönyv

Ahogy a fenti szerkesztő képernyőképe is mutatja, a swap helper egy ideiglenes változót használ a két index értékeinek cseréjére. Közvetlenül mutálja a tömböt, és semmit sem ad vissza.

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

output:

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

Code a partíció végrehajtásához

A fenti képernyőképen látható kód az 1–8. lépéseket függvénnyé alakítja. A két belső hurkok vigye előre a mutatókat, a if A blokk végrehajtja a cserét, és a függvény visszaadja a felosztási indexet.

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

output:

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

A kimenet pontosan megegyezik a manuális bejárással: egy partíciós menet után a tömb [5,3,2,6,7,9], a visszaadott felosztási index pedig 4.

Végezze el a rekurzív műveletet OperaCIÓ

Miután a particionálás visszaadta a felosztási indexet, használd azt a tartomány felosztására, és futtasd le a gyors rendezést mindkét felén. Ezért nevezik oszd meg és uralkodj algoritmusnak. A rekurzió addig folytatódik, amíg minden résztartomány egyetlen elemet tartalmaz, ekkor az egész tömb rendezett lesz.

Jegyzet: A Gyorsrendezés végig ugyanazon a tömbön dolgozik. A folyamat során nem jönnek létre új tömbök, ami helybeni algoritmussá teszi.

Szóval hívod a partíció () a fent leírt függvényt, és a visszatérési értékét használva ossza fel a sor részekre bontva. Itt a kód, ami ezt csinálja:

Figyeld meg a képernyőképen kiemelt két őrfeltételt. left < index - 1 megerősíti, hogy legalább két elem marad a bal oldalon, és index < right ugyanezt megerősíti a jobb oldalra vonatkozóan. Ezen védőelemek nélkül a függvény örökké hívná magát egyelemű tartományokon.

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

output:

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

Teljes gyorsrendezés Code

A swap, a particionálás és a rekurziós elemek összeillesztése adja a teljes implementációt:

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

output:

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

A fenti képernyőkép a teljes programot mutatja a szerkesztőben, a konzolon található rendezett tömbbel együtt. Ezt a megvalósítást egy már rendezett tömbbel, egy fordítottan rendezett tömbbel, ismétlődő és azonos értékeket tartalmazó tömbökkel, negatív számokkal, egyetlen elemmel és egy üres tömbbel ellenőriztük, és minden esetben a helyes eredményt adja vissza.

A gyors rendezés időbeli és térbeli komplexitása

Minden particionálási menet egyszer érinti a tartomány minden elemét, tehát egyetlen menet O(n)-be kerül. A teljes költség tehát attól függ, hogy hányszor lehet felosztani a tömböt, mielőtt a tartományok triviálissá válnának.

A térbeli komplexitás O(log n) ehhez a helybeni verzióhoz. Nincs lefoglalva második tömb, így az egyetlen extra memória a rekurziós verem, és a kiegyensúlyozott felosztás ezt a veremet körülbelül log₂(n) képkocka mélyen tartja. A legrosszabb esetben a verem O(n) képkockára nő, ezért a nagyon nagy tömbök túlcsordulhatnak a hívási veremben.

Két szám teszi ezt kézzelfoghatóvá. A fenti kóddal 4,096 véletlenszerű érték rendezése nagyjából 65 000 összehasonlítást igényelt egy 49 152-es elméleti n·log₂(n) értékkel szemben, és a legmélyebb rekurzió 24 képkockát ért el, míg a log₂(4096) értéke 12. Mindkét érték az O(n log n) algoritmustól elvárt kis konstans tényezőn belül van.

Gyors rendezés vs. egyéb rendezési módok Algorithms

A gyors rendezés ritkán az egyetlen lehetőség. Az alábbi táblázat összehasonlítja a leggyakrabban előforduló többi algoritmussal, így kiválaszthatja az adataihoz leginkább illőt.

A gyors rendezés általában a gyakorlatban sikeres, mivel a belső ciklusa szűk, és gyorsítótár-barát, összefüggő tartományokban működik. Válasszon egyesítéses rendezést, ha garantáltan O(n log n) korlátú vagy stabil rendezésre van szüksége, halomrendezést, ha a memória rendkívül korlátozott, és beszúrós rendezést nagyon kicsi vagy majdnem rendezett tömbökhöz. Az éles könyvtárak gyakran kombinálják ezeket: az introsort gyors rendezéssel kezdődik, halomrendezésre vált, ha a rekurzió túl mélyre kerül, és beszúrós rendezéssel fejeződik be kis tartományokon.

Objektumok és karakterláncok gyors rendezése

Az eddig bemutatott megvalósítás összehasonlítja az értékeket a következővel: < és a >, ami számokra korlátozza. A valódi alkalmazásoknak rendezniük kell objektumok tulajdonság szerint, karakterláncok betűrendben, vagy dátumok időrendben. A megoldás az összehasonlítás visszahívásba helyezése, pontosan úgy, ahogy a beépített sort() igen.

Egy összehasonlító két értéket fogad, és negatív számot ad vissza, ha az elsőnek kell először lennie, pozitív számot, ha a másodiknak kell először lennie, és nullát, ha a kettő egyenértékű. A két fixen kódolt összehasonlítás összehasonlító hívásokkal való helyettesítése lehetővé teszi, hogy az algoritmus bármilyen adattípuson működjön.

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

output:

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

Három részletet érdemes megjegyezni. A rekurziós őr most már left >= right, ami bármely tartományra helyes, és nem függ a külső tömb hosszától. A karakterlánc-összehasonlítás a következőt használja: localeCompare() így az ékezetes karakterek és a kis- és nagybetűk megfelelően kerülnek kezelésre a nyers kódpontok helyett. Mivel a Gyorsrendezés nem stabil, a fizetéssel megegyező rekordok helyet cserélhetnek; rendezzen egy döntetlent eldöntő második kulcs szerint, ha az eredeti sorrend fontos Önnek.

Készen állsz a folytatásra? Erősítsd meg az alapokat a következővel: JavaSzkriptbevezetés, gyakorold a mutató mechanikáját JavaSzkriptciklusok, dolgozz át többet gyakorlati JavaSzkriptkód példák, hasonlítsa össze a megvalósításokat a Beszúrás rendezése és a Halom rendezés, vagy statikus típusokat adjunk ehhez az algoritmushoz a következővel: TypeScript referencia.

GYIK