Meny

Rask sortering i C ++ med eksempler

quick sort c with examples

Prøv Instrumentet Vårt For Å Eliminere Problemer

Quicksort i C ++ med illustrasjon.

Quicksort er en mye brukt sorteringsalgoritme som velger et bestemt element kalt 'pivot' og partisjonerer arrayet eller listen som skal sorteres i to deler basert på denne pivot s0 at elementene mindre enn pivot er til venstre for listen og elementene større enn pivoten er til høyre for listen.

Dermed er listen delt inn i to underlister. Det er ikke sikkert at underlistene er nødvendige for samme størrelse. Så kaller Quicksort seg rekursivt for å sortere disse to underlistene.

=> Sjekk ut den perfekte C ++ treningsguiden her.

Rask sortering

Hva du vil lære:

Introduksjon

Quicksort fungerer effektivt så vel som raskere, selv for større matriser eller lister.

I denne opplæringen vil vi utforske mer om hvordan Quicksort fungerer, sammen med noen programmeringseksempler på quicksort-algoritmen.

Som en pivotverdi kan vi velge enten første, siste eller mellomverdien eller hvilken som helst tilfeldig verdi. Den generelle ideen er at til slutt blir pivotverdien plassert i riktig posisjon i matrisen ved å flytte de andre elementene i matrisen til venstre eller høyre.

Generell algoritme

Den generelle algoritmen for Quicksort er gitt nedenfor.

quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low

La oss nå ta en titt på pseudokoden for Quicksort-teknikken.

Pseudo-kode for kviksort

//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

Arbeidet til partisjoneringsalgoritmen er beskrevet nedenfor ved hjelp av et eksempel.

arbeid av partisjoneringsalgoritmen

I denne illustrasjonen tar vi det siste elementet som pivot. Vi kan se at matrisen fortløpende er delt rundt pivotelementet til vi har et enkelt element i matrisen.

Nå presenterer vi en illustrasjon av Quicksort nedenfor for bedre å forstå konseptet.

Illustrasjon

La oss se en illustrasjon av quicksort-algoritmen. Tenk på følgende matrise med det siste elementet som pivot. Dessuten er det første elementet merket lavt og det siste elementet er høyt.

illustrasjon av quicksort-algoritmen

hvordan du spiller SWF-filer på Windows 7

Fra illustrasjonen kan vi se at vi beveger pekerne høyt og lavt i begge endene av matrisen. Når lave punkter til elementet er større enn pivot og high peker mot elementet mindre enn pivot, så bytter vi posisjonene til disse elementene og fremfører lave og høye pekere i deres respektive retninger.

Dette gjøres til lave og høye pekere krysser hverandre. Når de krysser hverandre, blir dreieelementet plassert i riktig posisjon, og matrisen er delt i to. Deretter sorteres begge disse underarrayene uavhengig ved hjelp av kviksort rekursivt.

C ++ Eksempel

Nedenfor er implementeringen av 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<

Produksjon:

Inndata matrise

12 23 3 43 51 35 19 45

Array sortert med kviksort

3 12 19 23 35 43 45 51

Her har vi få rutiner som brukes til å partisjonere matrisen og ringe til quicksort rekursivt for å sortere partisjonen, grunnleggende quicksort-funksjonen og verktøyfunksjonene for å vise arrayinnholdet og bytte de to elementene deretter.

Først kaller vi quicksort-funksjonen med inndataoppstillingen. Inne i quicksort-funksjonen kaller vi partisjonsfunksjonen. I partisjonsfunksjonen bruker vi det siste elementet som pivotelement for matrisen. Når pivoten er bestemt, blir matrisen delt i to deler, og deretter kalles quicksort-funksjonen for å sortere begge underarrayene uavhengig.

Når kviksortsfunksjonen returnerer, blir matrisen sortert slik at pivotelementet er på sin rette plassering og elementene mindre enn pivot er til venstre for pivot og elementene større enn pivot er til høyre for pivot.

Deretter vil vi implementere 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

Produksjon:

Inndata matrise

12 23 3 43 51 35 19 45

Array etter sortering med quickort

3 12 19 23 35 43 45 51

Også i Java-implementeringen har vi brukt den samme logikken som vi brukte i C ++ implementering. Vi har brukt det siste elementet i matrisen ettersom pivot og quickort utføres på arrayet for å plassere pivotelementet i riktig posisjon.

passord cracker programvare gratis nedlasting fullversjon

Kompleksitetsanalyse av Quicksort-algoritmen

Tiden det tar for å sortere en matrise, avhenger av inngangsmatrisen og partisjonsstrategien eller metoden.

Hvis k er antall elementer mindre enn svingpunktet, og n er det totale antallet elementer, kan den generelle tiden det tar av quickort, uttrykkes som følger:

T (n) = T (k) + T (n-k-1) + O (n)

Her er T (k) og T (n-k-1) tiden det tar av rekursive samtaler, og O (n) er tiden det tar av partisjoneringsanrop.

La oss analysere denne tidskompleksiteten for quicksort i detalj.

# 1) Verste tilfelle : Worst case in quicksort-teknikk oppstår hovedsakelig når vi velger det laveste eller høyeste elementet i matrisen som en pivot. (I illustrasjonen ovenfor har vi valgt det høyeste elementet som pivot). I en slik situasjon oppstår verste fall når matrisen som skal sorteres allerede er sortert i stigende eller synkende rekkefølge.

Derfor endres uttrykket ovenfor for samlet tid som:

T (n) = T (0) + T (n-1) + O (n) som løser seg for Påto)

# 2) Beste tilfelle: Det beste tilfellet for quicksort oppstår alltid når det valgte pivotelementet er midt i matrisen.

Dermed er gjentakelsen i beste fall:

hvordan du kjører en .swf-fil

T (n) = 2T (n / 2) + O (n) = O (nlogn)

# 3) Gjennomsnittlig tilfelle: For å analysere gjennomsnittssaken for kviksort, bør vi vurdere alle array-permutasjonene og deretter beregne tiden det tar for hver av disse permutasjonene. I et nøtteskall blir gjennomsnittlig tid for quicksort også O (nlogn).

Nedenfor er de forskjellige kompleksitetene for Quicksort-teknikken:

Kompleksitet i verste fallO (n 2)
stabilitetIkke stabilt, da to elementer med samme verdier ikke blir plassert i samme rekkefølge.Stabil - to elementer med de samme verdiene vises i samme rekkefølge i den sorterte utgangen.
Kompleksitet i beste tilfelleO (n * log n)
Gjennomsnittlig tidskompleksitetO (n * log n)
RomkompleksitetO (n * log n)

Vi kan implementere kviksort på mange forskjellige måter bare ved å endre valget av dreieelementet (midt, første eller siste), men det verste tilfellet forekommer sjelden for kviksort.

3-veis kviksort

I original quicksort-teknikk velger vi vanligvis et pivotelement og deler deretter arrayet i underarrays rundt denne pivot, slik at en sub-array består av elementer mindre enn pivot og en annen består av elementer som er større enn pivot.

Men hva om vi velger et pivotelement, og det er mer enn ett element i matrisen som er lik pivot?

For eksempel, vurder følgende array {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Hvis vi utfører en enkel kviksort på denne matrisen og velger 4 som et pivotelement, vil vi bare fikse en forekomst av element 4, og resten vil bli partisjonert sammen med de andre elementene.

I stedet, hvis vi bruker 3-veis hurtigsortering, vil vi dele matrisen (l… r) i tre underarrayer som følger:

  1. Array (l… i) - Her er i pivot og denne matrisen inneholder elementer mindre enn pivot.
  2. Array (i + 1 ... j-1) - Inneholder elementene som er lik svingpunktet.
  3. Array (j… r) - Inneholder elementer som er større enn pivoten.

Dermed kan 3-veis quicksort brukes når vi har mer enn ett overflødig element i matrisen.

Randomisert Quicksort

Quicksort-teknikken kalles randomisert quicksort-teknikk når vi bruker tilfeldige tall for å velge dreieelementet. I randomisert kviksort kalles det 'sentral pivot' og det deler matrisen på en slik måte at hver side har minst ¼ elementer.

Pseudokoden for randomisert kviksort er gitt 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 procedure

I ovennevnte kode på 'randomQuickSort' velger vi i trinn 2 den sentrale pivoten. I trinn 2 er sannsynligheten for at det valgte elementet er den sentrale pivoten ½. Derfor forventes løkken i trinn 2 å kjøre to ganger. Dermed er tidskompleksiteten for trinn 2 i randomisert kviksort O (n).

Å bruke en sløyfe for å velge den sentrale pivoten er ikke den ideelle måten å implementere randomisert kviksort. I stedet kan vi tilfeldig velge et element og kalle det sentral pivot eller omstille arrayelementene. Den forventede tidskompleksiteten i verste fall for randomisert kviksortsalgoritme er O (nlogn).

Quicksort vs. Merge Sort

I denne delen vil vi diskutere hovedforskjellene mellom hurtig sortering og sammenslåing.

SammenligningsparameterRask sorteringSlå sammen sortering
oppdelingMatrisen er delt rundt et pivotelement og er ikke nødvendigvis alltid i to halvdeler. Den kan deles i hvilket som helst forhold.Matrisen er delt inn i to halvdeler (n / 2).
Verste tilfelle kompleksitetO (n 2) - i verste fall kreves det mange sammenligninger.O (nlogn) - samme som gjennomsnittssaken
Datasett brukKan ikke fungere bra med større datasett.Fungerer bra med alle datasettene uavhengig av størrelse.
Ekstra plassPå stedet - trenger ikke ekstra plass.Ikke på plass - trenger ekstra plass for å lagre hjelpearrangement.
SorteringsmetodeInternt - data blir sortert i hovedminnet.Eksternt - bruker eksternt minne for lagring av dataarriser.
EffektivitetRaskere og effektiv for små størrelseslister.Rask og effektiv for større lister.
Arrays / koblede listerMer foretrukket for arrays.Fungerer bra for koblede lister.

Konklusjon

Som navnet antyder, er quicksort algoritmen som sorterer listen raskt enn noen andre sorteringsalgoritmer. Akkurat som sammenslåing, vedtar hurtig sortering også en splitt og erobringsstrategi.

Som vi allerede har sett, deler vi listen ved å bruke hurtig sortering i underarrayer ved hjelp av pivotelementet. Deretter sorteres disse underarrayene uavhengig. På slutten av algoritmen er hele matrisen fullstendig sortert.

Quicksort er raskere og fungerer effektivt for å sortere datastrukturer. Quicksort er en populær sorteringsalgoritme, og noen ganger er den til og med foretrukket fremfor sammenslåingssorteringsalgoritme.

I vår neste opplæring vil vi diskutere mer om Shell-sortering i detalj.

=> Se opp den enkle C ++ treningsserien her.

Anbefalt lesing

^