Alt du trenger å vite om Quicksort i C ++

Det er en mengde sorteringsalgoritmer. Å finne riktig passform for applikasjonen din er en oppgave som krever en kort forståelse av faktorer som ytelse, tidskompleksitet, lengde på koden osv. Til en bestemt algoritme. I dette innlegget vil vi se på alle viktige konsepter som kreves for å implementere Quicksort i C ++ i følgende rekkefølge:

• Forstå Quicksort-algoritmen
• Pseudokode for Quicksort
• Program for Quicksort i C ++
• Time Complexity Quicksort

Forstå Quicksort-algoritmen

Akkurat som Slå sammen Sorter , Følger Quicksort skillet og erobre strategien. Ved å bruke delings- og erobringsstrategien deler vi problemet opp i mange delproblemer og løser dem rekursivt. Først vil vi forstå hele prosessen trinn for trinn, og etter det, ved hjelp av et eksempel, vil vi utvikle en dyp forståelse av hele prosessen.

1. Først vil vi be om usortert utvalg fra brukeren.

2. Når vi har usortert utvalg, må vi velge en pivotverdi fra matrisen. Vi kan velge hvilken som helst verdi.

   
   
   

   hva er tokens i java

3. Når vi velger dreiepunktet etter det, må vi ordne de andre elementene i matrisen på en slik måte at alle elementene mindre enn dreieverdien skal plasseres til høyre for dreieverdien, og alle elementene større enn dreieverdien verdien skal plasseres til høyre for pivotverdien.

4. Vi utfører trinn 3 til vi får vårt sorterte utvalg.

La oss nå vurdere et eksempel og implementere algoritmen og se hvordan den fungerer.

Hei [5, 4, 1, 11, 9, 6, 2, 3] for dette eksemplet vil vi alltid betrakte pivoten som det lengste elementet i listen.

La oss gå gjennom hvert trinn og forstå logikken vi brukte for å løse problemet.

• Først valgte vi ‘3’ som vår dreiebenke og ordnet alle elementene mindre enn ‘3’ i høyre og alle elementene større enn ‘3’ til høyre.

• På dette punktet har vi to delproblemer. La oss først løse delproblemet til høyre. Vi valgte en som dreiepunkt og plasserte ‘2’ til høyre.

• For å løse det andre delproblemet velger vi ‘6’ som vårt ledd og plasserer elementene som vi diskuterte tidligere.

• Vi har 2 flere underproblemer. Den første løses ved å velge 4 som pivot, og den andre løses ved å velge 9 som pivot. Til slutt har vi vårt sorterte utvalg med elementene plassert i understrekingsindeksen.

Merk- Det viktige poenget å forstå her er at alle operasjonene foregår i samme matrise. Nye matriser opprettes ikke.

Pseudokode for Quicksort i C ++

QuickSort (array [], start_index, end_index) {if (start_index
 Program for Quicksort i C ++ 
Vi forsto algoritmen og utviklet en dyp forståelse av algoritmens virkemåte. La oss implementere Quicksort i C ++ og skrive et program for å sortere en matrise.
# inkludere bruk av navneområdet std ugyldige bytteelementer (int * a, int * b) {int temp = * a * a = * b * b = temp} int partisjon (int array [], int start_index, int end_index) {int pivot = array [end_index] int i = (start_index - 1) for (int j = start_index j<= end_index- 1 j++) { if (array[j] <= pivot) { i++ swap_elements(&array[i], &array[j]) } } swap_elements(&array[i + 1], &array[end_index]) return (i + 1) } void quickSort(int array[], int start_index, int end_index) { if (start_index < end_index) { int partition_index = partition(array, start_index, end_index) quickSort(array, start_index, partition_index - 1) quickSort(array, partition_index + 1, end_index) } } void printArray(int array[], int number) { int i cout<<'Sorted Array: ' for (i = 0 i < number i++) cout << array[i] << ' ' cout << endl } int main() { int Hello[30] int i int NumberofElements cout<>NumberofElements kostnad<<'Enter the elements one by one: ' for(i=0i>Hei [i]} quickSort (Hello, 0, NumberofElements-1) printArray (Hello, NumberofElements) return 0}
 Produksjon: 
 Tidskompleksitet 
La oss snakke om det viktigste ved enhver sorteringsalgoritme, dvs. tidskompleksitet. Den forteller oss om ytelsen til algoritmen i forskjellige scenarier. Disse verdiene kan hjelpe oss med å avgjøre om vi kan bruke denne algoritmen til applikasjonen vår.
 Beste sak- På)
 Gjennomsnittlig sak- (nlogn)
 Verste fall- På2)
Med dette kommer vi til en slutt på denne Quicksort in C ++ -artikkelen. Hvis du ønsker å lære mer, sjekk ut   av Edureka, et pålitelig online læringsfirma. Edurekas Java J2EE- og SOA-opplæring og sertifiseringskurs er designet for å trene deg for både kjerne- og avanserte Java-konsepter sammen med forskjellige Java-rammer som Hibernate & Spring.
 Har du et spørsmål til oss? Vennligst nevn det i kommentarfeltet på denne bloggen, så kommer vi tilbake til deg så snart som mulig.