quick sort c with examples
Quicksort i C ++ med illustration.
Quicksort er en meget anvendt sorteringsalgoritme, der vælger et specifikt element kaldet 'pivot' og partitionerer arrayet eller listen, der skal sorteres i to dele, baseret på denne pivot s0, at elementerne mindre end pivot er til venstre for listen og elementerne større end omdrejningspunktet er til højre for listen.
Således er listen opdelt i to underlister. Underlisterne er muligvis ikke nødvendige for den samme størrelse. Så kalder Quicksort sig rekursivt for at sortere disse to underlister.
=> Tjek den perfekte C ++ træningsvejledning her.
Hvad du lærer:
- Introduktion
- Generel algoritme
- Pseudokode til Quicksort
- Illustration
- C ++ Eksempel
- Java-eksempel
- Kompleksitetsanalyse af Quicksort-algoritmen
- 3-vejs Quicksort
- Randomiseret Quicksort
- Quicksort vs. Merge Sort
- Konklusion
- Anbefalet læsning
Introduktion
Quicksort fungerer effektivt såvel som hurtigere, selv for større arrays eller lister.
I denne vejledning vil vi udforske mere om Quicksorts funktion sammen med nogle programmeringseksempler på quicksort-algoritmen.
Som en pivotværdi kan vi vælge enten første, sidste eller mellemværdi eller en vilkårlig værdi. Den generelle idé er, at i sidste ende pivotværdien placeres i sin rette position i arrayet ved at flytte de andre elementer i arrayet til venstre eller højre.
Generel algoritme
Den generelle algoritme for Quicksort er angivet nedenfor.
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low Lad os nu se på pseudokoden til Quicksort-teknik.
Pseudokode til Quicksort
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low Funktionen af partitioneringsalgoritmen er beskrevet nedenfor ved hjælp af et eksempel.
I denne illustration tager vi det sidste element som drejning. Vi kan se, at arrayet successivt er opdelt omkring pivotelementet, indtil vi har et enkelt element i arrayet.
Nu præsenterer vi en illustration af Quicksort nedenfor for bedre at forstå konceptet.
Illustration
Lad os se en illustration af quicksort-algoritmen. Overvej følgende array med det sidste element som pivot. Det første element er også mærket lavt og det sidste element er højt.
angularjs interviewspørgsmål og svar til erfaren pdf
Fra illustrationen kan vi se, at vi bevæger markørerne højt og lavt i begge ender af arrayet. Når lavpunkter til elementet er større end omdrejningspunktet og høje punkter til elementet mindre end omdrejningspunktet, udveksler vi disse elementers positioner og fremfører de lave og høje markører i deres respektive retninger.
Dette gøres, indtil de lave og høje markører krydser hinanden. Når de krydser hinanden, placeres drejelementet i sin rette position, og arrayet er opdelt i to. Derefter sorteres begge disse underarrays uafhængigt ved hjælp af quicksort rekursivt.
C ++ Eksempel
Nedenfor er implementeringen af Quicksort-algoritmen i C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int pivot = arr(high); // pivot int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< Produktion:
Input array
12 23 3 43 51 35 19 45
Array sorteret med quicksort
3 12 19 23 35 43 45 51
Her har vi få rutiner, der bruges til at opdele arrayet og kalde quicksort rekursivt for at sortere partitionen, grundlæggende quicksort-funktion og hjælpefunktioner til at vise arrayindholdet og bytte de to elementer i overensstemmelse hermed.
Først kalder vi quicksort-funktionen med input-arrayet. Inde i quicksort-funktionen kalder vi partitionsfunktionen. I partitionsfunktionen bruger vi det sidste element som pivotelementet til arrayet. Når drejningen er bestemt, opdeles arrayet i to dele, og derefter kaldes quicksort-funktionen til at sortere begge underarrays uafhængigt.
Når quicksort-funktionen vender tilbage, sorteres arrayet således, at pivotelementet er på det korrekte sted, og elementerne mindre end pivot er til venstre for pivot, og elementerne større end pivot er til højre for pivot.
Dernæst implementerer vi quicksort-algoritmen i Java.
Java-eksempel
// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr(), int low, int high) { int pivot = arr(high); int i = (low-1); // index of smaller element for (int j=low; j Produktion:
Input array
12 23 3 43 51 35 19 45
Array efter sortering med quicksort
3 12 19 23 35 43 45 51
Også i Java-implementeringen har vi brugt den samme logik, som vi brugte i C ++ implementering. Vi har brugt det sidste element i arrayet, da pivot og quicksort udføres på arrayet for at placere pivotelementet i sin rette position.
Kompleksitetsanalyse af Quicksort-algoritmen
Den tid, det tager af quicksort at sortere en matrix, afhænger af inputmatrixen og partitionsstrategien eller metoden.
Hvis k er antallet af elementer, der er mindre end omdrejningspunktet, og n er det samlede antal elementer, kan den generelle tid, der tages af quicksort, udtrykkes som følger:
T (n) = T (k) + T (n-k-1) + O (n)
Her er T (k) og T (n-k-1) den tid, det tager af rekursive opkald, og O (n) er den tid, det tager af partitioneringsopkald.
Lad os analysere denne tidskompleksitet for quicksort i detaljer.
bedste gratis download af musiksteder til Android-telefoner
# 1) Værste tilfælde : Det værste tilfælde i quicksort-teknik opstår mest, når vi vælger det laveste eller højeste element i arrayet som en drejetap. (I ovenstående illustration har vi valgt det højeste element som omdrejningspunkt). I en sådan situation opstår det værste tilfælde, når det array, der skal sorteres, allerede er sorteret i stigende eller faldende rækkefølge.
Derfor ændres ovenstående udtryk for den samlede tid taget som:
T (n) = T (0) + T (n-1) + O (n) det løser at Påto)
# 2) Bedste tilfælde: Det bedste tilfælde for quicksort opstår altid, når det valgte pivotelement er midten af arrayet.
Således er gentagelsen i bedste fald:
gratis dvd-kopieringssoftware til mac
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Gennemsnitlig sag: For at analysere det gennemsnitlige tilfælde for quicksort skal vi overveje alle array-permutationer og derefter beregne den tid, det tager for hver af disse permutationer. I en nøddeskal bliver den gennemsnitlige tid for quicksort også O (nlogn).
Nedenfor er de forskellige kompleksiteter for Quicksort-teknik:
Værst tilfælde tidskompleksitet O (n 2) stabilitet Ikke stabil, da to elementer med de samme værdier ikke placeres i samme rækkefølge. Stabil - to elementer med de samme værdier vises i samme rækkefølge i det sorterede output. Kompleksitet i bedste tilfælde O (n * log n) Gennemsnitlig tidskompleksitet O (n * log n) Rumkompleksitet O (n * log n)
Vi kan implementere quicksort på mange forskellige måder bare ved at ændre valget af drejelementet (mellem, første eller sidste), men det værste tilfælde forekommer sjældent for quicksort.
3-vejs Quicksort
I original quicksort-teknik vælger vi normalt et pivotelement og deler derefter arrayet i underarrays omkring denne pivot, så et underarray består af elementer mindre end pivot og et andet består af elementer større end pivot.
Men hvad hvis vi vælger et pivotelement, og der er mere end et element i arrayet, der er lig med pivot?
For eksempel, overvej følgende array {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Hvis vi udfører et simpelt kviksort på dette array og vælger 4 som et drejelement, så løser vi kun en forekomst af element 4, og resten vil blive opdelt sammen med de andre elementer.
I stedet for, hvis vi bruger 3-vejs quicksort, vil vi dele array (l… r) i tre underarrays som følger:
- Array (l… i) - Her er i pivot, og denne matrix indeholder elementer mindre end pivot.
- Array (i + 1… j-1) - Indeholder de elementer, der er lig med drejetappen.
- Array (j… r) - Indeholder elementer, der er større end omdrejningspunktet.
Således kan 3-vejs quicksort bruges, når vi har mere end et redundant element i arrayet.
Randomiseret Quicksort
Quicksort-teknikken kaldes randomiseret quicksort-teknik, når vi bruger tilfældige tal til at vælge drejelementet. I randomiseret quicksort kaldes det “central pivot”, og det opdeler arrayet på en sådan måde, at hver side har mindst ¼ elementer.
Pseudokoden for randomiseret quicksort er angivet nedenfor:
// Sorts an array arr(low..high) using randomized quick sort randomQuickSort(array(), low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from (low..high). Let pi be the randomly picked number. (ii) Count elements in array(low..high) that are smaller than array(pi). Let this count be a_low. (iii) Count elements in array(low..high) that are greater than array(pi). Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array(low..high) around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedureI ovenstående kode på “randomQuickSort” vælger vi i trin # 2 den centrale drejning. I trin 2 er sandsynligheden for, at det valgte element er den centrale drejning ½. Derfor forventes løkken i trin 2 at køre 2 gange. Således er tidskompleksiteten for trin 2 i randomiseret quicksort O (n).
Brug af en sløjfe til at vælge den centrale drejning er ikke den ideelle måde at implementere randomiseret quicksort på. I stedet kan vi tilfældigt vælge et element og kalde det central drejning eller ombytte arrayelementerne. Den forventede værst tænkelige tidskompleksitet for randomiseret quicksort-algoritme er O (nlogn).
Quicksort vs. Merge Sort
I dette afsnit vil vi diskutere de vigtigste forskelle mellem hurtig sortering og flet sortering.
Sammenligningsparameter Hurtig sortering Flet sortering partitionering Arrayet er opdelt omkring et pivotelement og er ikke nødvendigvis altid i to halvdele. Det kan opdeles i ethvert forhold. Arrayet er opdelt i to halvdele (n / 2). Værste tilfælde kompleksitet O (n 2) - i værste fald kræves der mange sammenligninger. O (nlogn) - samme som gennemsnittet Brug af datasæt Kan ikke fungere godt med større datasæt. Fungerer godt med alle datasættene uanset størrelse. Ekstra plads På stedet - behøver ikke ekstra plads. Ikke på plads - har brug for ekstra plads til at gemme hjælpearray. Sorteringsmetode Internt - data sorteres i hovedhukommelsen. Ekstern - bruger ekstern hukommelse til lagring af dataarrays. Effektivitet Hurtigere og effektiv til små størrelseslister. Hurtig og effektiv til større lister. Arrays / sammenkædede lister Mere foretrukket til arrays. Fungerer godt til sammenkædede lister.
Konklusion
Som navnet selv antyder, er quicksort den algoritme, der sorterer listen hurtigt end nogen anden sorteringsalgoritme. Ligesom flettsorter, vedtager hurtig sortering også en opdeling og erobringsstrategi.
Som vi allerede har set, deler vi listen ved hjælp af hurtig sortering i underarrays ved hjælp af drejelementet. Derefter sorteres disse underarrays uafhængigt. I slutningen af algoritmen sorteres hele arrayet fuldstændigt.
Quicksort er hurtigere og fungerer effektivt til at sortere datastrukturer. Quicksort er en populær sorteringsalgoritme og undertiden foretrækkes endda frem for flettsorteringsalgoritme.
I vores næste tutorial vil vi diskutere mere om Shell-sortering i detaljer.
=> Hold øje med den enkle C ++ træningsserie her.
Anbefalet læsning
- MongoDB Sort () metode med eksempler
- Unix sorteringskommando med syntaks, indstillinger og eksempler
- Flet sortering i C ++ med eksempler
- Heapsortering i C ++ med eksempler
- Shell Sort In C ++ med eksempler
- Valg af sortering i C ++ med eksempler
- Boblesortering i C ++ med eksempler
- Indsats sortering i C ++ med eksempler
