Rask sorteringstidskompleksitet

Simen Stensrud

Rask sort, også skrevet som Quicksort, er en skillelinje-og-er-sortering algoritme. Når kodet, vil QuickSort -programmet bestå av en bytte () -funksjon, en PIVOT () -funksjon, en partisjon () -funksjon og SELCSORT -funksjonen i seg selv. Både Pivot () og Partition () -funksjonene kaller SWAP () -funksjonen. Selve QuickSort () er kort og kaller Pivot () og Partition () -funksjonene. Det kaller seg rekursivt to steder i kroppen.

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; iprintf ("%c", a [i]);

printf ("\ n");

Utgangen er:

A B C D E F G H

Det 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; iprintf ("%c", a [i]);
if (i == 2)
gå i stykker;

printf ("\ n");

Utgangen er:

A B C

Kroppen 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 = 2³
=> 3 = log₂(8)

Hvis 8 er n, er 3,
Logg₂(n)

Og tidskompleksiteten vil bli gitt som:
O (log₂n)

Det er fortsatt et annet kodesegment å vurdere i forhold til QuickSort tidskompleksitet. Det er

for (int i = 0; ifor (int j = 0; jprintf ("%c", a [j]);

printf ("\ n");

printf ("\ n");

Utgangen er:

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
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 = 8²

Hvis 8 er n, ville dette være n². Tidskompleksiteten for denne koden er:
På²)

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,

DROSJE

omorganisere de tre elementene i orden, jeg.e.

A B C

Det midterste elementet, B, er medianen.

Rask sort illustrasjon

Listen som skal sorteres er:

P V D Q S X T B

Det er åtte elementer. Når listen er sortert, ville den være:

B d p q s t v x

Så problemet er: Sorter listen:

P V D Q S X T B

Bruke 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 B

Husk: 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 t

Merk 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 d

Det 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 x

Det 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 x

Det 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 x

Legg 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 x

Merk:
24 = 8 x 3
=> 24 = 8xlog₂8

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å.Logg₂n)

På²)

inklusive. Merk at prikken i o (n.Logg₂n) betyr multiplikasjon.

PHP

Hvordan bruke Scandir -funksjonen i PHP

Scandir () -funksjonen i PHP skanner en katalog for filer og kataloger. Den returnerer en rekke av a...

Elias Krogh Svendsen

C programmering

Hva er forskjellen mellom = og == operatører i C -programmering?

= Operatøren brukes til å tilordne en verdi til en variabel, mens == operatøren sammenligner to vari...

Elias Aalerud Aasen

C programmering

Hva er filhåndtering i C -programmering?

Filhåndtering er et essensielt aspekt ved C -programmering som lar utviklere jobbe med filer og data...

Lars Solberg