Alt hvad du behøver at vide om Quicksort i C ++

Der er en overflod af sorteringsalgoritmer. At finde den rette pasform til din applikation er en opgave, der kræver en kort forståelse af faktorer som ydeevne, tidskompleksitet, længde af kode osv. For en bestemt algoritme. I dette indlæg vil vi se på alle de vigtige begreber, der kræves for at implementere Quicksort i C ++ i følgende rækkefølge:

• Forståelse af Quicksort-algoritmen
• Pseudokode til Quicksort
• Program til Quicksort i C ++
• Time Complexity Quicksort

Forståelse af Quicksort-algoritmen

Ligesom Flet sortering , Følger Quicksort opdelings- og erobringsstrategien. Ved at bruge delings- og erobringsstrategien opdeler vi problemet i mange underproblemer og løser dem rekursivt. Først vil vi forstå hele processen trin for trin, og efter det ved hjælp af et eksempel vil vi udvikle en dyb forståelse af hele processen.

1. Først vil vi bede om det usorterede array fra brugeren.

2. Når vi har vores usorterede array, skal vi vælge en pivotværdi fra arrayet. Vi kan vælge enhver værdi.

   
   
   

3. Når vi først har valgt drejepunktet efter det, er vi nødt til at arrangere de andre elementer i arrayet på en sådan måde, at alle elementer, der er mindre end pivotværdien, skal placeres til højre for pivotværdien, og alle elementerne er større end pivot værdi skal placeres til højre for pivotværdien.

4. Vi udfører trin 3, indtil vi får vores sorterede array.

Lad os nu overveje et eksempel og implementere algoritmen og se, hvordan den fungerer.

matrix af objekter i java eksempel program

Hej [5, 4, 1, 11, 9, 6, 2, 3] til dette eksempel vil vi altid betragte drejningen som det længste element på listen.

Lad os gennemgå hvert trin og forstå den logik, vi brugte til at løse problemet.

• For det første valgte vi '3' som vores omdrejningspunkt og arrangerede alle elementerne mindre end '3' i højre og alle elementerne større end '3' til højre.

• På dette tidspunkt har vi to delproblemer. Lad os først løse underproblemet til højre. Vi valgte en som vores omdrejningspunkt og placerede '2' til højre.

• For at løse det andet delproblem vælger vi '6' som vores omdrejningspunkt og placerer elementerne som vi diskuterede tidligere.

• Vi har yderligere 2 underproblemer. Den første løses ved at vælge 4 som drejetap, og den anden løses ved at vælge 9 som omdrejningspunkt. Endelig har vi vores sorterede matrix med elementerne placeret i understregningsindekset.

Bemærk- Det vigtige punkt at forstå her er, at alle operationer finder sted i samme array. Nye arrays oprettes ikke.

datadrevet ramme i selen

Pseudokode til Quicksort i C ++

QuickSort (array [], start_index, end_index) {if (start_index
 Program til Quicksort i C ++ 
Vi forstod algoritmen og udviklede en dyb forståelse af algoritmens funktion. Lad os implementere Quicksort i C ++ og skrive et program for at sortere en matrix.
# inkludere brug af navneområde std ugyldige swap_elements (int * a, int * b) {int temp = * a * a = * b * b = temp} int partition (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 omkostninger<<'Enter the elements one by one: ' for(i=0i>Hej [i]} quickSort (Hello, 0, NumberofElements-1) printArray (Hello, NumberofElements) return 0}
 Produktion: 
 Tidskompleksitet 
Lad os tale om det vigtigste aspekt af enhver sorteringsalgoritme, dvs. tidskompleksitet. Det fortæller os om algoritmens ydeevne i forskellige scenarier. Disse værdier kan hjælpe os med at beslutte, om vi kan bruge denne algoritme til vores applikation.
 Bedste tilfælde- På)
 Gennemsnitlig sag- (nlogn)
 I værste fald- På2)
Med dette kommer vi til slutningen af ​​denne Quicksort i C ++ - artiklen. Hvis du ønsker at lære mere, skal du tjekke   af Edureka, et pålideligt online læringsfirma. Edurekas Java J2EE- og SOA-uddannelses- og certificeringskursus er designet til at træne dig til både kerne- og avancerede Java-koncepter sammen med forskellige Java-rammer som Hibernate & Spring.
 Har du et spørgsmål til os? Nævn det i kommentarsektionen på denne blog, og vi vender tilbage til dig hurtigst muligt.