QuickSort algoritmus be JavaForgatókönyv

Mi az a rendezés?

A rendezés nem más, mint az elemek kívánt sorrendbe rendezése. Lehet, hogy az iskolai vagy főiskolai éveidben találkoztál ezzel. Mint a számok kisebbről nagyobbra (növekvő) vagy nagyobbról kisebbre (csökkenő) rendezése, ezt láttuk eddig, és ezt rendezésnek hívják.

Alapértelmezett rendezés JavaForgatókönyv

Mint korábban említettük, JavaA szkript rendelkezik rendezés (). Vegyünk egy példát néhány elemből álló tömbből, például [5,3,7,6,2,9], és szeretnénk ezt a tömb elemeit növekvő sorrendbe rendezni. Csak hívj rendezés () tételek tömbjén, és növekvő sorrendbe rendezi a tömbelemeket.

Kód:

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

Mi az oka annak, hogy a Gyors rendezést választja az alapértelmezett sort() helyett? JavaForgatókönyv

Bár a sort() a kívánt eredményt adja, a probléma a tömbelemek rendezésének módjával van. Alapértelmezett sort() in JavaScript használ beszúrási rendezés by V8-as Chrome motor és a Egyesítés rendezése by Mozilla Firefox és a Safari.

Ez azonban nem megfelelő, ha nagy számú elemet kell rendeznie. Tehát a megoldás a Gyors rendezés használata nagy adatkészletekhez.

Tehát a teljes megértéshez ismernie kell a Gyors rendezés működését, és most lássuk ezt részletesen.

Mi az a Gyors rendezés?

Gyors rendezés következik Oszd meg és uralkodj algoritmus. Az elemeket valamilyen feltétel alapján kisebb részekre osztja, és azokon a rendezési műveleteket hajtja végre azokon a kisebb részeken. Ezért jól működik nagy adatkészleteknél. Tehát íme, a Gyors rendezés működésének lépései egyszerű szavakkal.

1. Először válasszon ki egy elemet, amelyet így kíván hívni pivot elem.
2. Ezután hasonlítsa össze az összes tömbelemet a kiválasztott pivot elemmel, és rendezze el őket úgy, hogy a pivot elemnél kisebb elemek balra, a pivotnál nagyobb elemek pedig jobbra legyenek.
3. Végül hajtsa végre ugyanazokat a műveleteket a forgóelem bal és jobb oldali elemeivel.

Tehát ez a Gyors rendezés alapvázlata. Itt vannak azok a lépések, amelyeket egyenként kell végrehajtani a gyors rendezés végrehajtásához.

Hogyan működik a QuickSort

1. Először találd meg a "pivot" elem a tömbben.
2. Indítsa el a bal mutatót a tömb első eleménél.
3. Indítsa el a jobb mutatót a tömb utolsó eleménél.
4. Hasonlítsa össze a bal mutatóval mutató elemet, és ha kisebb, mint a pivot elem, mozgassa a bal mutatót jobbra (adjon 1-et a bal indexhez). Folytassa ezt mindaddig, amíg a bal oldali elem nagyobb vagy egyenlő nem lesz, mint a forgóelem.
5. Hasonlítsa össze a jobb oldali mutatóval mutató elemet, és ha nagyobb, mint a pivot elem, akkor mozgassa a jobb oldali mutatót balra (vonjon ki 1-et a jobb indexből). Folytassa ezt mindaddig, amíg a jobb oldali elem kisebb vagy egyenlő nem lesz, mint a forgóelem.
6. Ellenőrizze, hogy a bal mutató kisebb-e, vagy egyenlő-e a jobb oldali mutatóval, majd cserélje fel az elemeket a mutató helyén.
7. Növelje a bal mutatót és csökkentse a jobb mutatót.
8. Ha a bal mutató indexe még mindig kisebb, mint a jobb oldali mutató indexe, ismételje meg a folyamatot; egyébként visszaadja a bal oldali mutató indexét.

Lássuk tehát ezeket a lépéseket egy példán keresztül. Tekintsük a rendezendő elemek tömbjét: [5,3,7,6,2,9].

Határozza meg a Pivot elemet

Mielőtt azonban továbblépne a Gyors rendezésre, a pivot elem kiválasztása fontos szerepet játszik. Ha az első elemet választja ki pivot elemként, akkor ez a legrosszabb teljesítményt nyújtja a rendezett tömbben. Ezért mindig célszerű a középső elemet (a tömb hossza osztva 2-vel) pivot elemnek kiválasztani, és mi is így járunk el.

Az alábbiakban bemutatjuk a gyors rendezés lépéseit, amelyet egy példa mutat be [5,3,7,6,2,9].

STEP 1: Határozza meg a forgópontot középső elemként. Így, 7 a forgóelem.

STEP 2: Indítsa el a bal és jobb mutatót a tömb első és utolsó elemeként. Tehát a bal mutató rámutat 5 a 0 indexnél, és a jobb oldali mutató erre mutat 9 az 5-ös indexen.

STEP 3: Hasonlítsa össze a bal mutató elemét a pivot elemmel. Mivel az 5 < 6 a bal mutatót jobbra tolja az 1 indexhez.

STEP 4: Most még mindig 3 <6, tehát tolja a bal mutatót egy további indexre jobbra. Tehát most 7 > 6 hagyja abba a bal mutató növelését, és most a bal mutató a 2-es indexen áll.

STEP 5: Most hasonlítsa össze a jobb mutató értékét a pivot elemmel. Mivel a 9 > 6 mozgassa a jobb mutatót balra. Most, mint 2 < 6, hagyja abba a jobb mutató mozgatását.

STEP 6: Cserélje fel egymással a bal és jobb mutatóban lévő értékeket.

STEP 7: Mozgassa mindkét mutatót még egy lépéssel.

STEP 8: Mivel 6 = 6, mozgassa a mutatókat egy további lépésre, és álljon meg, amikor a bal mutató keresztezi a jobb mutatót, és adja vissza a bal mutató indexét.

Tehát itt a fenti megközelítés alapján kódot kell írnunk az elemek cseréjéhez és a tömb particionálásához a fenti lépésekben említett módon.

Kód két szám felcseréléséhez JavaForgatókönyv

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

Kód a partíció végrehajtásához a fenti lépésekben leírtak szerint

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

Hajtsa végre a rekurzív műveletet

A fenti lépések végrehajtása után a bal oldali mutató indexe kerül visszaadásra, és ezt kell használnunk a tömb felosztásához és a gyors rendezés végrehajtásához az adott részen. Ezért ezt Oszd meg és uralkodj algoritmusnak hívják.

Tehát a Gyors rendezés mindaddig végrehajtódik, amíg a bal és a jobb oldali tömb összes eleme nincs rendezve.

Jegyzet: A gyors rendezés ugyanazon a tömbön történik, és a folyamat során nem jön létre új tömb.

Szóval ezt kell hívnunk partíció () fentebb kifejtve és ez alapján felosztjuk a sor részekre. Tehát itt van a kód, ahol használod,

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öltse ki a gyors rendezési kódot

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]

JEGYZET: A gyors rendezés az idő összetettségével fut O(nlogn).