Rask sorter i C ++

Å arrangere ting i rekkefølge er en oppgave som vi utfører i dagliglivet, enten det er ordnet i stigende rekkefølge eller synkende rekkefølge. Prosessen med å ordne ting i en riktig sekvens kalles sortering. Stigende øker orden og synker synkende orden. I programmering utfører vi også sortering ved hjelp av forskjellige algoritmer. Men en algoritme gir den raskeste sortering som er "rask sort". Denne sorteringsalgoritmen sorterer matrisen raskere enn de andre algoritmene. Den fungerer på skillet og erobrer regelen, setter først et pivotpunkt og deler matrisen inn i to undergarriser. Sett deretter en pivot for under-arrays og prosessen fortsetter til vi kommer til slutten og den nødvendige matrisen er sortert. Denne artikkelen forklarer en grundig arbeid av en rask sort i C ++ med et praktisk kodingseksempel i stigende rekkefølge.

Hvordan velge en pivot

Før du går nærmere inn i detalj, er det viktig å lære hvordan vi kan velge en pivot for hurtigsorteringsalgoritmen.

• • Første element
  • Siste element
  • Medianelement
  • Tilfeldig element

Det er ingen begrensninger for å velge en pivot. Stort sett setter vi matriserens siste verdi som et pivotpunkt.

Algoritmer:

Den raske sorteringen gjøres ved hjelp av to algoritmer - den ene er å dele opp matrisen i henhold til pivotpunktet og den andre er for å sortere matrisen.

For partisjonering:

• • Ta to variabler som laveste og høyeste.
  • Lagre startindeksen til matrisen i den laveste og lagre deretter den siste indeksen i den høyeste.
  • Definer en annen variabel og initialiser den med den laveste variabelen som "iter".
  • Velg matriserens siste medlem for å fungere som pivoten.
  • Passere gjennom matrisen. Etter det, match hvert element med pivotverdien.
  • Hvis array -elementet er mindre enn svingen, øker du "iter" og bytter sine posisjoner.
  • Øk "jeg" med 1 og gjenta prosessen til matrisens slutt er nådd. Avslutt sløyfen der og returner ITER-1.

Den returnerte verdien gir oss posisjonen til pivotindeksen. Før pivoten er det elementene som er mindre enn svingverdien. Etter pivoten er det elementene som er større enn svingverdien.

For sortering:

Gå nå videre til sortering. Bruk følgende instruksjoner for å sortere en matrise:

• • Velg matrisens siste vare som skal fungere som pivoten.
  • Den returnerte indekspartisjonsalgoritmen er riktig indeks for en pivot.
  • Quicksort -metoden kalles til venstre og høyre underbyrå gjentatte ganger.

Ved hjelp av disse to algoritmene kan vi utføre den raske sorteringen på hvilken som helst matrise. Et eksempel på hurtigsorteringsmetoden blir belyst i følgende:

Rask sorter i stigende rekkefølge

La oss forklare metoden "Quick Sort" for å sortere et heltallsarray i økende rekkefølge.

Kode:

#inkludere
ved hjelp av navneområdet STD;
void swap (int array_0 [], int posisjon_1, int posisjon_2)
int temp_0;
temp_0 = array_0 [posisjon_1];
array_0 [posisjon_1] = array_0 [posisjon_2];
array_0 [posisjon_2] = temp_0;
int partisjon (int array_0 [], int lav, int høy, int pivot)
int i_0 = lav;
int j_0 = lav;
mens (i_0 <= high) if(array_0[i_0] > pivot) i_0 ++;
annet Swap (array_0, i_0, j_0); i_0 ++; J_0 ++;
return J_0-1;

void Quicksort_0 (int array_0 [], int lav, int høy)
hvis (lav < high)
int pivot = array_0 [høy];
int posisjon = partisjon (array_0, lav, høy, pivot);
Quicksort_0 (Array_0, Low, Position-1);
Quicksort_0 (Array_0, Position+1, High);
int main ()

int n [4] = 12,3,8,6;
Quicksort_0 (n, 0, 3);
cout<<"The sorted array is: ";
for (int i = 0; i < 4 ; i++) cout<< n[i]<<"\t";

Start koden ved å importere biblioteket og inkludere standard navneområdet. Etter det, definer en metode som heter “Swap” av TRUID -returtypen. I denne funksjonen, pass tre parametere som har heltallstype. De to argumentene, “Position_1” og “Position_2”, brukes til posisjoner. Den tredje, "temp_0", er en matrise. Metoden bytter posisjonene til matriseelementer. Variabelen som heter “TEMP_0” er erklært å spare verdien midlertidig. Initialiser dessuten denne "temp_0" med matrisens første stilling. Tilordne deretter Array's andre posisjon til en matrise første stilling "Position_1". Og tilordne temp til matrisens andre plassering som er "posisjon_2". Dette fungerer som A = B; B = C; c = a. Denne metoden utfører bare byttet.

I tillegg til dette, definerer du en annen funksjon for partisjon. Denne metoden deler matrisen inn i to deler og deler videre under-arrayene i underarrayer. Denne funksjonen er en metode av returtype, og den returnerer en heltallverdi som inneholder riktig indeks for pivoten. Denne partisjonen () -metoden har fire argumenter for heltallstype. Først er en rekke “Array_0”, den andre er “Lav” som lagrer startindeksen til matrisen, den tredje er “Høy” som inneholder den siste indeksen for matrisen, og den fjerde er “Pivot”. Innenfor denne metoden, initialiser to variabler - “I_0” og “J_0” - med “lav”. Disse to variablene har en "int" datatype. Som vi vet, "lav" inneholder den første indeksen for matrisen. I neste linje, bruk "mens" -løkken for å iterere på matrisen. Først, sett tilstanden til ”'mens” som i_0 <= high. Iterate until we reach the last index of the array. Inside the “while” loop, employ the “if” decision-making statement to check whether the array elements are greater than the pivot or not. If this condition is fulfilled, the body of “if” executes which increments the iterator. Otherwise, the body of “else” is run. In the body of “else”, we callthe swap() method that swaps the array values until they are in ascending order. Outside the “while”, return the “j_0-1” to the function. Because that is incremented in the “else” part.

Definer en annen QuickSort () -metode for tomromstype for å utføre hurtig sortering. Tre argumenter - “Array_0”, “Low” og “High” - med en heltalldata blir gitt til denne funksjonen. Angi dessuten "hvis" -tilstanden. Hvis "lav" er mindre enn "høye", initialiser "pivoten" med matrisens siste indeks "høy". For "posisjon" -variabelen, ring Partition () -metoden. Deretter påkaller rekursivt QuickSort () -funksjonen til høyre og venstre under-gebyr.

I den siste delen av koden, bruk Main () -metoden. Deretter initialiser en "int" -type og ring QuickSort_0 () -metoden. Denne funksjonen inneholder tre argumenter. Den utfører en rask art på den spesifiserte matrisen og sorterer denne matrisen. Skriv inn “Cout<<” command to print the “The sorted array is:” line. To display the sorted array, use a “for” loop and iterate until the end of the array is reached.

Produksjon:

Den sorterte matrisen er: 3 6 8 12

Konklusjon

Rask sort i C ++ er diskutert i denne guiden. I programmering er det nødvendig å ordne matriser i stigende eller synkende rekkefølge. Det er flere sorteringsalgoritmer som boble -sortering, fletting osv. Rask slags er en av dem, men som navnet sier, sorterer det arrayen raskere enn andre. Denne artikkelen forklarer hva en pivot er, hvilket array -element kan være pivoten, som algoritmer brukes til rask sortering, og hvordan de utfører. Denne artikkelen avsluttes med koden til C ++ hvor vi implementerer den raske sorteringen.