Rask sorteringstidskompleksitet
Nå er det forskjellige måter å skrive Pivot () og Partition () -funksjonene. Valget av typen pivot () -funksjon og/eller partisjon () -funksjonen bestemmer effektiviteten til hele programmet. Effektivitet er som antall hovedoperasjoner som utføres av programmet.
Tidskompleksitet er den relative kjøretiden til et program. Dette kan sees på som hovedoperasjonen av programmet.
Sortering kan være stigende eller synke. I denne artikkelen stiger sorteringen.
Målet med denne artikkelen er å produsere tidskompleksiteten for et QuickSort -program. Siden Quicksort kan skrives på forskjellige måter, avhengig av valg av pivot () og/eller partisjonen (), har hver hurtig-sort-type sin egen tidskompleksitet. Imidlertid er det en rekke av en rekke operasjoner som de forskjellige typene Quicksort -programmer passer. Denne artikkelen presenterer bare en av de forskjellige typene QuickSort -programmer. Ethvert kodesegment som presenteres er av C -språket.
Heltalldivisjon av to
Quick Sort bruker heltalldivisjon i å dele hovedsettet i mindre sett.
Nå,
11/2 = 5 resten 1
Heltalldivisjon betyr, tar 5 og forlater 1. Det vil si godta hele tallet og ignorere resten.
Også,
10/2 = 5 resten 0
Her er resten null og spiller ingen rolle. Fortsatt tar heltalldivisjonen 5 og forlater 0. Det vil si godta hele antallet og ignorere hva resten er der, selv om det er null. Noen ganger i programmering er det også godt å vite om resten er 0 eller ikke - se senere.
Når du deler en liste i hurtig-sort, er heltalldivisjon det som brukes.
For rask sortering, for å skaffe den nullbaserte mellomindeksen for en liste, gjør heltalldivisjon med to for lengden på listen. Hele tallet er den nullbaserte, mellomindeksen. For å oppnå lengden på listen, begynn å telle fra 1.
Tidskompleksitet relatert til rask sortering
Tenk på følgende kode:
int n = 8;char a [] = 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h';
for (int i = 0; i
printf ("\ n");
Utgangen er:
A B C D E F G HDet vil si at alle åtte elementer er skrevet ut.
Det er åtte elementer identifisert av n. Kroppen til for-loop har et innhold.
printf ("%c", a [i]);Dette er en hovedoperasjon. Så åtte hovedoperasjoner har funnet sted. Tidskompleksiteten for denne koden er skrevet som:
På)
Hvor n er antall hovedoperasjoner. Dette er Big-O-notasjonen. I notasjonen er den første bokstaven O i store bokstaver. Så er det parenteser. Inne i parentesene er antall operasjoner eller maksimalt mulig antall operasjoner.
Vurder nå følgende kodesegment:
for (int i = 0; i<8; i++)for (int i = 0; i
if (i == 2)
gå i stykker;
printf ("\ n");
Utgangen er:
A B CKroppen til for-loop har et innhold.
printf ("%c", a [i]);if (i == 2)
gå i stykker;
Dette regnes fremdeles som en hovedoperasjon i denne situasjonen. Tre elementer er skrevet ut fordi hovedoperasjonen er utført tre ganger.
Nå,
8 = 23
=> 3 = log2(8)
Hvis 8 er n, er 3,
Logg2(n)
Og tidskompleksiteten vil bli gitt som:
O (log2n)
Det er fortsatt et annet kodesegment å vurdere i forhold til QuickSort tidskompleksitet. Det er
for (int i = 0; iprintf ("\ n");
printf ("\ n");
Utgangen er:
A B C D E F G HA B C D E F G H
A B C D E F G H
A B C D E F G H
A B C D E F G H
A B C D E F G H
A B C D E F G H
A B C D E F G H
Antallet tegn som er skrevet ut er 64, fra et innledende antall på 8. Dette betyr at hovedoperasjonen er utført 64 ganger.
64 = 8 x 8 = 82
Hvis 8 er n, ville dette være n2. Tidskompleksiteten for denne koden er:
På2)
Rask sorteringsalgoritme i denne artikkelen
For denne artikkelen er trinnene til algoritmen:
- Se etter medianen (se nedenfor) mellom det første elementet, mellomelementet og det siste elementet på listen.
- Plasser medianen midt på listen.
- Send alle elementene til høyre som er mindre enn medianen, nå i midten, til venstre for medianen, og send alle elementene til venstre som er større enn medianen til høyre for medianen. Dette kalles partisjonering.
- Gjenta de ovennevnte tre trinnene i rekkefølge, for hver underliste, til listen er blitt separert i enkeltelementer.
- Når listen består av separerte enkeltelementer, sorteres listen.
Median
For å få median av de tre elementene,
DROSJEomorganisere de tre elementene i orden, jeg.e.
A B CDet midterste elementet, B, er medianen.
Rask sort illustrasjon
Listen som skal sorteres er:
P V D Q S X T BDet er åtte elementer. Når listen er sortert, ville den være:
B d p q s t v xSå problemet er: Sorter listen:
P V D Q S X T BBruke Quicksort.
Medianen mellom P, Q og B ser etter. Det er s. Dette søket etter medianen involverer tre operasjoner. Så det er totalt tre operasjoner så langt. Å sette median midt på listen gir:
V D Q P S X T BHusk: Indeksen for mellomelementet er resultatet av heltalldivisjonen med to. Det er fire bevegelser her, for P og Q. Det er fire operasjoner. Det gjør totalt syv operasjoner så langt (tre pluss fire). Nå vil B bli sendt til venstre, og V og Q vil bli sendt til høyre for å ha:
D b p v q s x tMerk at P ikke lenger er på den sanne midten. Imidlertid var det tre bevegelser. Dette er tre operasjoner. Så det er ti operasjoner så langt (syv pluss tre). Hver av de to underlistene må deles i tre deler (medianen er en del).
Median for d og b er d. Søket etter medianen er tre operasjoner. Det gjør totalt tretten operasjoner så langt (ti pluss tre). Partisjonering av disse elementene gir:
B dDet var to bevegelser her. Det er to operasjoner. Dette gjør totalt femten operasjoner så langt (tretten pluss to). Deretter må medianen for settet V, Q, S, X, T sees etter, og settet partisjonert.
Median for V, S og T er T. Median søket er tre operasjoner. Så langt har det vært atten operasjoner (femten pluss tre). Å sette T i midten gir:
V q t s xDet er tre bevegelser her. Dette er tre operasjoner. Det totale antallet operasjoner så langt er tjueen (atten pluss tre). Å sende lavere elementer til høyre for T til venstre, og høyere elementer til venstre for T til høyre, gir:
Q s t v xDet er to bevegelser her. Dette er to operasjoner. Så langt er det totalt tjuetre operasjoner (tjueen pluss to). Å sette sammen alle partisjonene så langt gir:
B d p q s t v xLegg merke til at listen allerede er sortert. Imidlertid må algoritmen avslutte. Q, s og v, x må ivaretas. Det vil ikke være noen bevegelse av karakterer mellom disse to. Imidlertid vil medianen deres bli sett på. Jakten på to medianer er seks operasjoner. Dette utfører totalt tjueni-operasjoner for hele programmet (tjuetre pluss seks). Den endelige sorterte listen er:
B d p q s t v xMerk:
24 = 8 x 3
=> 24 = 8xlog28
29 er omtrent lik 24.
Konklusjon
Avhengig av typen funksjon som er valgt for pivot () og typen funksjon som er valgt for partisjon (), vil tidskompleksiteten for Quicksort -programmet være et sted mellom
På.Logg2n)
og
På2)
inklusive. Merk at prikken i o (n.Logg2n) betyr multiplikasjon.