QuickSort Algoritme ind JavaScript

Hvad er sortering?

Sortering er ikke andet end at arrangere elementer i den rækkefølge, vi ønsker. Du er måske stødt på dette i din skole- eller collegetid. Ligesom at arrangere tal fra mindre til større (stigende) eller fra større til mindre (faldende) er, hvad vi så indtil nu og kaldes sortering.

Standard sortering i JavaScript

Som tidligere nævnt, JavaScript har sortere(). Lad os tage et eksempel med få array af elementer som [5,3,7,6,2,9] og ønsker at sortere disse array-elementer i stigende rækkefølge. Bare ring sortere() på elementer array og det sorterer array elementer i stigende rækkefølge.

Kode:

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

Hvad er grunden til at vælge Hurtig sortering over standard sort() i JavaScript

Selvom sort() giver det resultat, vi ønsker, ligger problemet i den måde, den sorterer array-elementerne på. Standard sort() i JavaScript bruger indsætnings sortering by V8 Engine af Chrome og Flet sortering by Mozilla Firefox og Safari.

Men ellers er dette ikke egnet, hvis du skal sortere et stort antal elementer. Så løsningen er at bruge Hurtig sortering til store datasæt.

Så for at forstå fuldstændigt, skal du vide, hvordan Quick sortering fungerer, og lad os se det i detaljer nu.

Hvad er hurtig sortering?

Hurtig sortering følger Opdele og erobre algoritme. Det opdeler elementer i mindre dele baseret på en eller anden tilstand og udfører sorteringsoperationerne på de opdelte mindre dele. Derfor fungerer det godt til store datasæt. Så her er trinene til, hvordan Hurtig sortering fungerer i enkle ord.

1. Vælg først et element, der skal kaldes som pivot element.
2. Dernæst skal du sammenligne alle array-elementer med det valgte pivotelement og arrangere dem på en sådan måde, at elementer mindre end pivotelementet er til venstre for det og større end pivot er til højre.
3. Til sidst skal du udføre de samme handlinger på venstre og højre sideelementer til pivotelementet.

Så det er den grundlæggende skitse af hurtig sortering. Her er de trin, der skal følges et efter et for at udføre Hurtig sortering.

Hvordan virker QuickSort

1. Find først "omdrejningspunkt" element i arrayet.
2. Start den venstre markør ved det første element i arrayet.
3. Start den højre markør ved det sidste element i arrayet.
4. Sammenlign elementet, der peger med venstre markør, og hvis det er mindre end pivotelementet, så flyt venstre markør til højre (tilføj 1 til venstre indeks). Fortsæt dette, indtil venstre sideelement er større end eller lig med pivotelementet.
5. Sammenlign elementet, der peger med højre pointer, og hvis det er større end pivot-elementet, så flyt højre pointer til venstre (træk 1 fra til højre indeks). Fortsæt dette, indtil højre sideelement er mindre end eller lig med pivotelementet.
6. Tjek, om venstre markør er mindre end eller lig med højre markør, og skift derefter elementerne på placeringen af ​​disse markører.
7. Forøg den venstre markør og formindsk den højre markør.
8. Hvis indekset for venstre markør stadig er mindre end indekset for højre markør, så gentag processen; ellers returnerer indekset for den venstre markør.

Så lad os se disse trin med et eksempel. Lad os overveje rækken af ​​elementer, som vi skal sortere er [5,3,7,6,2,9].

Bestem Pivot-elementet

Men før du går videre med Hurtig sortering, spiller valget af pivotelementet en stor rolle. Hvis du vælger det første element som pivotelement, giver det den dårligste ydeevne i det sorterede array. Så det er altid tilrådeligt at vælge det midterste element (længden af ​​arrayet divideret med 2) som pivotelementet, og vi gør det samme.

Her er trinene til at udføre Hurtig sortering, der vises med et eksempel [5,3,7,6,2,9].

TRIN 1: Bestem pivot som mellemelement. Så, 7 er pivotelementet.

TRIN 2: Start venstre og højre pointere som henholdsvis første og sidste elementer i arrayet. Så venstre pointer peger på 5 ved indeks 0 og højre peger peger på 9 ved indeks 5.

TRIN 3: Sammenlign element ved venstre markør med pivotelementet. Siden 5 < 6 flytter venstre markør til højre til indeks 1.

TRIN 4: Nu, stadig 3 <6, så skift venstre markør til endnu et indeks til højre. Så nu stopper 7 > 6 med at øge den venstre markør og nu er venstre markør på indeks 2.

TRIN 5: Sammenlign nu værdien ved den højre markør med pivotelementet. Da 9 > 6 flytter den højre markør til venstre. Nu som 2 < 6 stop med at flytte den højre markør.

TRIN 6: Skift begge værdier, der findes ved venstre og højre pointer, med hinanden.

TRIN 7: Flyt begge markører et trin mere.

TRIN 8: Da 6 = 6, skal du flytte pegepindene til et trin mere og stoppe, når venstre pegepind krydser højre pegepind og returnere indekset for venstre peger.

Så her, baseret på ovenstående tilgang, skal vi skrive kode til at bytte elementer og partitionere arrayet som nævnt i ovenstående trin.

Kode til at bytte to tal ind i JavaScript

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

Kode til at udføre partitionen som nævnt i ovenstående trin

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

Udfør den rekursive operation

Når du har udført ovenstående trin, returneres indekset for den venstre markør, og vi skal bruge det til at opdele arrayet og udføre Hurtig sortering på den del. Derfor kaldes det Divide and Conquer-algoritme.

Så hurtig sortering udføres, indtil alle elementer i venstre array og højre array er sorteret.

Bemærk: Hurtig sortering udføres på det samme array, og der oprettes ingen nye arrays i processen.

Så vi er nødt til at kalde dette skillevæg() forklaret ovenfor og ud fra det opdeler vi matrix ind til dele. Så her er koden, hvor du bruger den,

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

Komplet hurtigsorteringskode

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]

BEMÆRK VENLIGST: Hurtig sortering kører med tidskompleksiteten på O(nlogn).