Algoritam QuickSort u JavaScript

Što je Sortiranje?

Sortiranje nije ništa drugo do slaganje elemenata redoslijedom kojim želimo. Možda ste na ovo naišli u školskim ili fakultetskim danima. Poput sređivanja brojeva od manjeg prema većem (uzlazno) ili od većeg prema manjem (opadajuće) je ono što smo vidjeli do sada i zove se sortiranje.

Zadano sortiranje u JavaScript

Kao što je ranije spomenuto, JavaSkripta ima vrsta(). Uzmimo primjer s nekoliko nizova elemenata kao što je [5,3,7,6,2,9] i želimo poredati te elemente niza uzlaznim redoslijedom. Samo nazovi vrsta() na nizu stavki i razvrstava elemente niza uzlaznim redoslijedom.

Kodirati:

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

Koji je razlog da odaberete Quick sort umjesto default sort() in JavaScript

Iako sort() daje rezultat koji želimo, problem leži u načinu na koji sortira elemente niza. Zadani sort() u JavaUpotreba skripte umetanje sortirati by V8 motor Chrome međutim Spajanje vrsta by Mozilla Firefox međutim safari.

Ali ovo nije prikladno ako trebate sortirati veliki broj elemenata. Dakle, rješenje je koristiti brzo sortiranje za veliki skup podataka.

Dakle, da biste u potpunosti razumjeli, morate znati kako funkcionira brzo sortiranje i da vidimo sada to u detalje.

Što je brzo sortiranje?

Slijedi brzo sortiranje Podijeli i vladaj algoritam. To je dijeljenje elemenata na manje dijelove na temelju nekog uvjeta i izvođenje operacija sortiranja na tim podijeljenim manjim dijelovima. Stoga dobro funkcionira za velike skupove podataka. Dakle, evo koraka kako brzo sortiranje funkcionira jednostavnim riječima.

1. Prvo odaberite element koji će biti pozvan kao stožer element.
2. Zatim usporedite sve elemente niza s odabranim zaokretnim elementom i rasporedite ih na takav način da su elementi manji od zaokretnog elementa s njegove lijeve strane, a veći od zaokretnog elementa s njegove desne strane.
3. Na kraju, izvedite iste operacije na elementima s lijeve i desne strane stožernog elementa.

Dakle, to je osnovni prikaz brzog sortiranja. Evo koraka koje je potrebno slijediti jedan po jedan da biste izvršili brzo sortiranje.

Kako funkcionira QuickSort

1. Prvo pronađite "stožer" element u nizu.
2. Pokrenite lijevi pokazivač na prvom elementu niza.
3. Započnite desni pokazivač na zadnjem elementu niza.
4. Usporedite element koji pokazuje s lijevim pokazivačem i ako je manji od stožernog elementa, pomaknite lijevi pokazivač udesno (dodajte 1 lijevom indeksu). Nastavite s tim dok lijevi bočni element ne bude veći ili jednak zakretnom elementu.
5. Usporedite element koji pokazuje s desnim pokazivačem i ako je veći od stožernog elementa, pomaknite desni pokazivač ulijevo (oduzmite 1 od desnog indeksa). Nastavite s tim sve dok desni bočni element ne bude manji ili jednak zakretnom elementu.
6. Provjerite je li lijevi pokazivač manji ili jednak desnom pokazivaču, a zatim zamijenite elemente na mjestima tih pokazivača.
7. Povećajte lijevi pokazivač i smanjite desni pokazivač.
8. Ako je indeks lijevog pokazivača i dalje manji od indeksa desnog pokazivača, ponovite postupak; inače vraća indeks lijevog pokazivača.

Dakle, pogledajmo ove korake na primjeru. Uzmimo u obzir niz elemenata koje trebamo sortirati [5,3,7,6,2,9].

Odredite Pivot element

Ali prije nego što krenemo s brzim sortiranjem, odabir zaokretnog elementa igra glavnu ulogu. Ako odaberete prvi element kao stožerni element, on daje najlošiju izvedbu u sortiranom nizu. Dakle, uvijek je preporučljivo odabrati srednji element (duljina niza podijeljena s 2) kao stožerni element i učinit ćemo isto.

Evo koraka za izvođenje brzog sortiranja koji su prikazani s primjerom [5,3,7,6,2,9].

KORAK 1: Odredite stožer kao srednji element. Tako, 7 je stožerni element.

KORAK 2: Započnite lijevi i desni pokazivač kao prvi odnosno zadnji element niza. Dakle, lijevi pokazivač pokazuje na 5 na indeksu 0 i desni pokazivač pokazuje na 9 na indeksu 5.

KORAK 3: Usporedi element na lijevom pokazivaču sa zaokretnim elementom. Budući da 5 < 6 pomiče lijevi pokazivač udesno do indeksa 1.

KORAK 4: Sada, još uvijek 3 <6 pa pomaknite lijevi pokazivač na još jedan indeks udesno. Dakle, sada 7 > 6 zaustavlja povećanje lijevog pokazivača i sada je lijevi pokazivač na indeksu 2.

KORAK 5: Sada usporedite vrijednost na desnom pokazivaču s elementom zakretanja. Budući da je 9 > 6, pomaknite desni pokazivač ulijevo. Sada kada je 2 < 6 prestanite pomicati desni pokazivač.

KORAK 6: Zamijenite obje vrijednosti prisutne na lijevom i desnom pokazivaču jedna s drugom.

KORAK 7: Pomaknite oba pokazivača za još jedan korak.

KORAK 8: Budući da je 6 = 6, pomaknite pokazivače na još jedan korak i zaustavite se kada lijevi pokazivač prijeđe desni pokazivač i vratite indeks lijevog pokazivača.

Dakle, ovdje na temelju gornjeg pristupa, moramo napisati kod za zamjenu elemenata i particioniranje niza kao što je spomenuto u gornjim koracima.

Kod za zamjenu dva broja JavaScript

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

Kôd za izvođenje particije kao što je spomenuto u prethodnim koracima

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

Izvršite rekurzivnu operaciju

Nakon što izvršite gornje korake, vratit će se indeks lijevog pokazivača i mi ga trebamo upotrijebiti za dijeljenje niza i izvođenje brzog sortiranja na tom dijelu. Stoga se zove algoritam Podijeli pa vladaj.

Dakle, brzo sortiranje se izvodi sve dok se ne sortiraju svi elementi u lijevom i desnom nizu.

Bilješka: Brzo sortiranje izvodi se na istom polju i pritom se ne stvaraju novi nizovi.

Dakle, moramo ovo nazvati particija() gore objašnjeno i na temelju toga dijelimo poredak u dijelove. Evo koda gdje ga koristite,

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

Dovršite brzi kod sortiranja

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]

NAPOMENA: Brzo sortiranje radi s vremenskom složenošću O(nlogn).