Rask sorter i C

“Quicksort eller Quick-Sort er en sorteringsalgoritme. Rask sort er en skill-og-erobre-algoritme. La listen over tegn bli sortert etter:

Q w e r t y u i o p

Den sorterte listen er:

E i o p q r t u w y

Dette er slags stigende. I denne artikkelen sorterer forklaringen på Quicksort, stigende, ved hjelp av listen: "q", "w", "e", "r", "t", "y", "u", "i", " O ”,“ P ”, og C -språket.”

Rask sort i teorien

Fra listen, “q”, “w”, “e”, “r”, “t”, “y”, “u”, “i”, “o”, “p”, vil rask sort se for en sentral verdi, kalt pivot. I den sorterte listen,

“E”, “i”, “O”, “P”, “Q”, “R”, “T”, “U”, “W”, “Y”

Pivoten er enten "Q" eller "R" siden listen er til og med i antall. Hvis listen var merkelig i antall, ville pivoten helt klart ha vært mellomverdien. “Q” på indeks 4 er valgt som pivot. Husk at listen som skal sorteres er,

Q w e r t y u i o p

Og ikke den sorterte listen. Det er 10 elementer i denne usorterte listen.

Den første fasen er å se etter pivoten (sentral verdi) i den usorterte listen. Den andre fasen er å plassere pivoten i sin rettmessige posisjon i den usorterte listen (i dette tilfellet indeks 4); og legg alle elementene som er mindre enn sving på venstre og alle elementer som er større enn svingen til høyre. Elementene til venstre for pivoten må ikke nødvendigvis sorteres, og elementene til høyre for pivoten må ikke nødvendigvis også sorteres. Denne fasen er skillet eller partisjonsfasen i skillet og erobrer algoritmen. Det er tre deler for dette stadiet: venstre underliste, høyre underliste og den midterste underlisten. Den midterste underlisten består av bare ett element, som er pivoten. For den ovennevnte listen vil resultatet være:

E i o p q w r t y u

Siden pivoten allerede er på sin endelige posisjon, er den siste fasen, i teorien, å sortere venstre underliste og sortere høyre underliste. Dette er erobrende. Det er tilfeldig at venstre underliste, i dette tilfellet, allerede er sortert. Den rette underlisten, i dette tilfellet, skal fremdeles sorteres. Sortering av venstre og høyre underliste hver for seg, resultatet er:

E i o p q r t u w y

som kreves.

Rask sort i praksis

I praksis gjøres partisjonering med en sortering (bytte) gjentatte ganger på en rekursiv måte. Det vil si at nye mindre og mindre underlister er utviklet med sine egne svinger. Med andre ord, tre-delte mindre og mindre underlister utvikles fra hovedlisten til hele listen er sortert.

Det er et problem når det gjelder å velge pivot. Hele den usorterte listen kan ikke skannes element-for-element for å få riktig sving. Det vil være tidkrevende. Så en intelligent gjetning må gjøres.

Husk at listen som skal sorteres er:

Q w e r t y u i o p

La den intelligente gjetningen være P, det høyre elementet. Deretter, la alle elementene mindre enn P, lese fra venstre, gå til venstre for P, og la alle elementene større enn P, fremdeles lese fra venstre, gå til høyre for P uten bevisst sortering. Dette gir:

E i o p q w r t y u

De tre første underlistene er:

“E”, “i”, “o”, “p”, “q”, “w”, “r”, “t”, “y”, “u”

P er på sin rettmessige posisjon (i praksis kan det ikke nødvendigvis være indeks 4; her, det er indeks 3 på dette stadiet). Neste trinn er en rekursiv samtale for å dele den venstre underlisten i tre underlister; og riktig underliste inn i tre underlister, hver med sin egen pivot, fra en intelligent gjetning.

Deling “e”, “i”, “o”
La dens intelligente pivot gjette være, o, det høyre elementet. Alle elementene som er mindre enn O må gå til venstre, og alle elementene som er større enn O må gå til høyre, og lese for begge tilfeller fra venstre. Dette gir:

“E”, “Jeg”, “o”,

uten element til høyre. Hvis “e”, “Jeg” også er rekursivt delt, vil [“e”, “i”, ] resultere. Og slik er den første venstre underlisten sortert, er:

“E”, “i”, “o”

Deling “Q”, “W”, “R”, “T”, “Y”, “U”
“Q”, “W”, “R”, “T”, “Y”, “U” er den første høyre underlisten. La dens intelligente pivot gjette være deg, det høyre elementet. Alle elementene som er mindre enn du må gå til venstre, og alle elementene som er større enn du må gå til høyre; lesing for begge tilfeller, fra venstre. Dette gir:

“Q”, “r”, “t”, “u”, “w”, “t”

Ved å rekursivt partisjonering “q”, “r”, “t” og “w”, “t” på samme måte, ville den første høyre underlisten være:

“Q”, “r”, “t”, “u”, “w”, “y”

Og den komplette sorterte listen ville være:

E i o p q r t u w y

Merk at hver partisjon sorterer i bred forstand ved å plassere usorterte lavere verdier til venstre og usorterte høyere verdier til høyre.

Legg også merke til at den intelligente gjetningen bare valgte det rette mest elementet i en underliste. Det er ikke den beste intelligente gjetningen. På den annen side er ikke løsningen (for intelligent gjetning) å skanne hele den gitte listen! - Se nedenfor for bedre alternativer.

Rask sorteringskode i C

Selv om den høyre verdien er valgt for hver underliste ovenfor, er det konvensjonelt, det er den venstre verdien som er valgt. Selv når det blir gjort en mer intelligent gjetning, må den gode gjettet verdien plasseres i venstre posisjon; og venstre verdi som var der vil bli plassert i en annen passende posisjon (fremdeles på listen).

Det er fire C -funksjoner med navnene, Swap (), Pivot (), Partition () og QuickSort (). Quicksort (), funksjonen, er kodet på en rekursiv måte, og den kaller de andre funksjonene.

Bytting () -funksjonen
Denne funksjonen bytter to matriseelementer ved å bruke indeksene deres. Det er:

void swap (char a [], int m, int n)
char temp = a [m];
A [m] = a [n];
A [n] = temp;

En enkel pivot () -funksjon
Denne funksjonen velger mellom det venstre elementet og det høyre elementet i den gitte hele listen. Det setter det mindre av enten i venstre posisjon og den større i høyre posisjon. Det er:

void pivot (char a [], int venstre, int høyre)
if (a [til venstre]> a [til høyre])
Swap (a, venstre, høyre);

Dette er bedre enn bare å velge det rette mest elementet for listen og underlistene, som gjort ovenfor. En enda bedre pivot () -funksjon er gitt nedenfor.

En partisjon () -funksjon
Akkurat som Pivot () -funksjonen kan skrives på forskjellige måter, kan partisjonen () -funksjonen skrives på forskjellige måter. Den som er valgt for denne artikkelen er:

int partisjon (char a [], int venstre, int høyre)
int pivot = a [venstre];
int i = venstre;
int j = høyre + 1;
Gjør
gjør ++ i;
mens (en [i] pivot);
hvis jeg < j)
Swap (a, i, j);
mens jeg < j);
Swap (a, j, til venstre);
return j;

Etter å ha plassert pivotelementet i venstre posisjon til listen eller underlisten, etter Pivot () -funksjonen, skanner partisjonsfunksjonen listen eller underlisten fra begge ender, og bytter elementene som ikke er på riktig side av pivoten. Skanning fra venstre enden begynner etter svingen i venstre ende (av enten listen eller underlisten); Fordi pivoten vil bli byttet sist (“do ++ i;” ovenfor).

Returindeksen, J, er den nye (neste) pivotposisjonen.

QuickSort () -funksjonen
Dette er en rekursiv funksjon som kaller de andre funksjonene. Det er:

void Quicksort (char a [], int venstre, int høyre)
hvis (til venstre < right)
pivot (a, venstre, høyre);
int k = partisjon (a, venstre, høyre);
Quicksort (a, venstre, k-1);
Quicksort (a, k+1, til høyre);

Her er k det samme som J returnert ovenfor.

Alle de ovennevnte funksjonene som er kodet sammen, i den beskrevne rekkefølgen, vil danne Quicksort -programmet.

C Hovedfunksjonen

En passende C -hovedfunksjon for å teste programmet er:

int main (int argc, char ** argv)

char a [] = “q”, “w”, “e”, “r”, “t”, “y”, “u”, “i”, “o”, “p”;
int sz = størrelse av (a)/størrelse av (a [0]);
Quicksort (A, 0, SZ-1);
for (int i = 0; iprintf ("%c", a [i]);
printf ("\ n");
retur 0;

QuickSort () -funksjonen kalles fra C hovedfunksjonen, og passerer matrisen som det første argumentet. Det andre argumentet som er igjen er en indeks, 0, av hele listen. Det tredje argumentet, til høyre, er den siste-men-en-indeksen for hele listen.

Median pivot

Hvis tre forskjellige tall er ordnet i stigende rekkefølge, er medianen den midterste (andre) verdien. En bedre måte enn den forrige, for å oppnå pivoten, er å se etter medianen, mellom venstre verdi, mellomverdien på listen eller underlisten, og den høyre verdien. Koden er:

int midindex = (venstre + høyre) / 2; // Hele nummeret tatt
if (a [midindex] < A[left])
Swap (a, venstre, midindex);
if (a [til høyre] < A[left])
Swap (a, venstre, høyre);
if (a [midindex] < A[right])
Swap (a, midindex, til høyre);
char pivot = a [høyre];

Legg merke til at de tre elementene kan ha endret posisjoner. Denne koden er kombinert med ovennevnte Pivot () -funksjon å ha:

void pivot (char a [], int venstre, int høyre)
// å skaffe median
int midindex = (venstre + høyre) / 2; // Hele nummeret tatt
if (a [midindex] < A[left])
Swap (a, venstre, midindex);
if (a [til høyre] < A[left])
Swap (a, venstre, høyre);
if (a [midindex] dreie)
Swap (a, venstre, høyre); // ellers er en [venstre] pivoten

Legg merke til den siste IF-kondisjonen.

Konklusjon

Quick-Sort er et skillelinje og erobrer sorteringsalgoritme. Det fortsetter å dele (partisjonering) listen i tre underlister rekursivt. Den midterste underlisten består alltid av ett element, som er pivoten. Når du gjør pivoten, gjøres sortering i bred forstand i det stadiet. Imidlertid, når rekursjonen fortsetter, oppnås perfekt sortering på slutten av programmet.