Valg sorterer tidskompleksitet

55 65 35 15 85 75 25 45

Hvis denne listen er sortert i stigende rekkefølge, vil den være:

15 25 35 45 55 65 75 85

Hvis listen er sortert i synkende rekkefølge, vil den være:

85 75 65 55 45 35 25 15

I denne artikkelen er det bare å sortere i stigende rekkefølge vurderes. Valgssorter sorterer ved å se etter små elementer og bytte dem med startelementene, som begynner fra det minste elementet, mens de erstattede startelementene blir stigende. En liste skal sorteres i stigende rekkefølge på slutten av denne prosessen.

Artikkelen tar sikte på å bestemme tidskompleksiteten til utvelgelsessorten. Følgende programmering gjøres på C -språket.

Valgssorter algoritme

Trinnene for utvalgssort er som følger:

• Anta at det første elementet er det minste elementet.
• Sammenlign dette elementet med de andre elementene for å kjenne det sanne minste elementet.
• Bytt det minste elementet som finnes med det første elementet.
• Gjenta de tre foregående trinnene i rekkefølge, unntatt det første erstattede elementet.
• Fortsett å gjenta de tre foregående trinnene, unntatt elementene mot venstre (nedre) ende som er erstattet.
• Sortering slutter når det siste elementet er nådd.

Det er to hovedoperasjonstyper her, som er sammenligning og bytte. Å flytte fra det ene elementet til det neste er også en operasjon, men det tar relativt lite tid sammenlignet med sammenligningsoperasjonen eller byttedriften i utvalgssorteringen.

På²) Tidskompleksitet

Tenk på følgende kode:

int resultat = 0;
for (int i = 0; i<8; i++)
for (int j = 0; j<8; j++)
Resultat = resultat + 1;


printf ("%i \ n", resultat);

Det er en ytre og indre sløyfe. Hver sløyfe itererer åtte ganger. Den ene tilleggsoperasjonen for begge løkker er hovedoperasjonen og opererer 64 ganger. 64 = 8 x 8 = 82. Utgangen er 64.

Denne koden anses å ha 82 hovedoperasjoner. Hvis 8 erstattes av N, vil tidskompleksiteten bli gitt som:

O (n2)

Dette bruker Big-O-notasjonen. Notasjonen begynner med O i store bokstaver, etterfulgt av parenteser. Inne i parentesene er antall hovedoperasjoner for koden.

Tenk på følgende kode:

int resultat = 0;
for (int i = 0; i<8; i++)
for (int j = i; j<8; j++)
Resultat = resultat + 1;


printf ("%i \ n", resultat);

Den ytre sløyfen itererer åtte ganger. Den indre sløyfen itererer opp til åttende gang, men begynner fra jeg, som er iterasjonsnummeret til den ytre sløyfen. Utgangen er 36. Den ene tilleggsoperasjonen fungerer 36 ganger og ikke 64 ganger. Vel, dette blir fremdeles betraktet som O (N2) tidskompleksitet. Arbeidet med utvalgssort ligner på denne koden. Med andre ord, utvalgssorteringen anses å ha O (N2) tidskompleksitet.

Koding i c

Utvalgssort vil alltid gi o (n2) tidskompleksitet. Det spiller ingen rolle hvordan elementene i matrisen er ordnet. Dette er fordi alle elementene først blir skannet; Så blir resten av elementene uten den første skannet neste; Skanning av resten av elementene uten de to første følger, og så videre. Skanning må fullføres før du bytter.

Listen for å sortere er:

P o i u y t r e w q

C -programmet sorterer i stigende rekkefølge. I hovedsak begynner programmet med:

#inkludere
void selectiosort (char a [], int n)
for (int i = 0; iint minindx = i;
for (int j = i+1; jif (a [j] < A[minIndx])
minindx = j;

char temp = a [i]; A [i] = a [minindx]; A [minindx] = temp; //bytting

Biblioteket som er ansvarlig for inngang fra tastaturet og utgangen til skjermen er inkludert. Deretter er det definisjonen av valgsortfunksjonen. Denne funksjonen som parametere har matrisen (referanse) med listen og antall elementer i matrisen.

Det er to for-løkker; den ene er nestet inne i den andre. Ytre for-loop itererer over alle elementene som begynner fra den første. Mens den ytre for-loop er i en indeks, itererer den indre for-loopen over resten av elementene, unntatt det foregående elementet. Hovedoperasjonen er sammenligningsoperasjonen i nestede for-loop.

Bytting gjøres for hver iterasjon av den ytre sløyfen like etter at den indre sløyfen er fullført.

En passende C hovedfunksjon for programmet er:

int main (int argc, char ** argv)

int n = 10;
char a [] = 'p', 'o', 'i', 'u', 'y', 't', 'r', 'e', ​​'w', 'q';
Selectiosort (a, n);
for (int i = 0; iprintf ("%c", a [i]);
printf ("\ n");
retur 0;

Utgangen er:

E i o p q r t u w y

sortert.

Det begynner med erklæringen om antall elementer i matrisen. Så er det matrisenklæringen. Det er ti elementer i matrisen. Disse elementene er karakterer. Så, matrise -erklæringen begynner med “Char”. Deretter kalles innsettingssortfunksjonen. Det første argumentet i funksjonssamtalen er array -navnet. Det andre argumentet er antall elementer i matrisen.

En for-loop følger. Denne for-loop skriver ut de sorterte tegnene. Den bruker printf () -funksjonen til STDIO.H bibliotek. Det første argumentet for denne funksjonen er en streng. Denne strengen er en spesiell streng, men har fremdeles tegn som vil bli skrevet ut. Den har også parametere for argumenter. I dette tilfellet er det bare en parameter, %C. Det er også bare ett argument, en [i]. Etter at alle tegnene er skrevet ut på en linje, tar den neste Printf () -funksjonen utdataene til neste linje.

Konklusjon

Denne artikkelen diskuterte trinnene for utvalgssort, som inkluderer forutsatt. I tillegg må en bruker bytte det minste elementet som finnes med det første elementet og gjenta de tre foregående trinnene i rekkefølge, unntatt det første erstattede elementet. De siste trinnene inkluderer å fortsette å gjenta de tre trinnene ovenfor, unntatt elementene mot venstre (nedre) ende som er erstattet; Sortering slutter når det siste elementet er nådd. Tidskompleksiteten for utvalgssort er O (N2).