QuickSort-algoritme i JavaScript

Hvad er hurtig sortering?

Hurtig sorteringsalgoritme følger Divide and Conquer tilgang. Det opdeler elementer i mindre dele baseret på en vis tilstand og udfører sorteringsoperationer på de opdelte mindre dele.

Hurtig sorteringsalgoritme er en af de mest anvendte og populære algoritmer på ethvert programmeringssprog. Men hvis du er JavaScript-udvikler, så har du måske hørt om sort (), som allerede er tilgængelig i JavaScript. Derefter har du måske tænkt på, hvad behovet for denne Quick Sort-algoritme er. For at forstå dette skal vi først bruge, hvad der er sortering, og hvad der er standardsortering i JavaScript.

Hvad er sortering?

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

Standardsortering i JavaScript

Som tidligere nævnt har JavaScript sorteret () . Lad os tage et eksempel med få matrix af elementer som [5,3,7,6,2,9] og vil sortere disse matrixelementer i stigende rækkefølge. Bare kald sort () på elementarray, og det sorterer arrayelementer 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 standardsortering () i JavaScript

Selvom sortering () giver det ønskede resultat, ligger problemet med den måde, det sorterer arrayelementerne. Standardsortering () i JavaScript bruger indsættelsessortering efter V8 Engine i Chrome og Flet sortering efter Mozilla Firefox og Safari .

Men andet dette er ikke egnet, hvis du har brug for at sortere et stort antal elementer. Så løsningen er at bruge Hurtig sortering til stort datasæt.

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

Hvad er hurtig sortering?

Hurtig sortering følger Divide and Conquer algoritme. Det opdeler elementer i mindre dele baseret på en vis tilstand og udfører sorteringsoperationer på de opdelte mindre dele. Derfor fungerer det godt til store datasæt. Så her er trinene, hvordan hurtig sortering fungerer i enkle ord.

Vælg først et element, der skal kaldes som drejelement .
Dernæst skal du sammenligne alle matrixelementer med det valgte pivotelement og arrangere dem på en sådan måde, at elementer mindre end pivotelementet er til venstre og større end pivot til højre.
Endelig udfør de samme operationer på venstre og højre sideelementer til drejelementet.

Så det er den grundlæggende oversigt over hurtig sortering. Her er de trin, der skal følges en efter en for at udføre hurtig sortering.

Hvordan fungerer QuickSort

Find først "pivot" -elementet i arrayet.
Start den venstre markør ved det første element i arrayet.
Start den rigtige markør ved det sidste element i arrayet.
Sammenlign elementet, der peger med venstre markør, og hvis det er mindre end drejelementet, skal du flytte 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 drejelementet.
Sammenlign elementet, der peger med højre markør, og hvis det er større end drejelementet, skal du flytte højre markør til venstre (træk 1 til det højre indeks). Fortsæt dette indtil højre sideelement er mindre end eller lig med drejelementet.
Kontroller, om venstre markør er mindre end eller lig med højre markør, så så elementerne på placeringen af disse markører.
Forøg den venstre markør og mindsk den højre markør.
Hvis indekset for venstre markør stadig er mindre end indekset for højre markør, skal du gentage processen. Ellers returnerer indekset for den venstre markør.

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

Bestem drejningselement

Men inden du går videre med hurtig sortering, spiller valg af drejelement en vigtig rolle. Hvis du vælger det første element som pivotelementet, giver det den dårligste ydeevne i det sorterede array. Så det tilrådes altid at vælge det midterste element (arrayets længde divideret med 2) som drejelementet, 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 drejning som midterelement. Så 7 er omdrejningselementet.

TRIN 2: Start venstre og højre markør som henholdsvis første og sidste element i arrayet. Så venstre peger 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 drejelementet. Siden skifter 5 <6 venstre markør til højre for 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 inkrementering af venstre markør, og nu er venstre markør ved indeks 2.

TRIN 5: Sammenlign nu værdien ved den rigtige markør med drejelementet. Siden 9> 6 skal du flytte højre markør til venstre. Nu når 2 <6 holder op med at flytte den rigtige markør.

TRIN 6: Skift begge værdier til stede ved venstre og højre pegepind med hinanden.

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

TRIN 8: Siden 6 = 6 skal du flytte markørerne til endnu et trin og stoppe, når venstre markør krydser højre markør og returnerer indekset for venstre markør.

Så her baseret på ovenstående tilgang er vi nødt til at skrive kode til at bytte elementer og opdele arrayet som nævnt i ovenstående trin.

Kode for at bytte to numre i JavaScript:

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

Kode for 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 elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}

Udfør den rekursive operation

Når du har udført ovenstående trin, returneres indekset til 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 denne partition () forklaret ovenfor og baseret på, at vi deler arrayet i 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 partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

Komplet hurtig sorteringskode:

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 elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]