Innsettingssorteringstidskompleksitet

Tenk på følgende tall:

50 60 30 10 80 70 20 40

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

10 20 30 40 50 60 70 80

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

80 70 60 50 40 30 20 10

Innføringssorter er en sorteringsalgoritme som brukes til å sortere listen i stigende rekkefølge eller i synkende rekkefølge. Denne artikkelen omhandler bare sortering i stigende rekkefølge. Sortering i synkende rekkefølge følger den samme logikken gitt i dette dokumentet. Målet med denne artikkelen er å forklare innsettingssorteringen. Programmering gjøres i følgende eksempel i C. Innsettingssorteringen forklares her ved hjelp av en matrise.

Algoritme for innsettingssortering

En usortert liste er gitt. Målet er å sortere listen i stigende rekkefølge ved å bruke samme liste. Sortering av en usortert matrise ved hjelp av samme matrise sies å sortere på stedet. Den nullbaserte indekseringen brukes her. Trinnene er som følger:

• • Listen skannes fra begynnelsen.
  • Mens skanningen pågår, blir et hvilket som helst antall mindre enn forgjengeren byttet med forgjengeren.
  • Denne bytteen fortsetter langs listen, til det ikke lenger er mulig å bytte.
  • Når skanning når slutten, er sorteringen fullført.

Innsettingssort illustrasjon

Når du arbeider med tidskompleksitet, er det det verste tilfellet som normalt blir tatt i betraktning. Den verste ordningen for forrige liste er:

80 70 60 50 40 30 20 10

Det er åtte elementer med indekser fra null til 7.

Hos Index Zero går skanning til 80. Dette er en bevegelse. Denne ene bevegelsen er en operasjon. Det er totalt en operasjon så langt (en bevegelse, ingen sammenligning og ingen bytte). Resultatet er:

| 80 70 60 50 40 30 20 10

På indeks en er det en bevegelse til 70. 70 sammenlignes med 80. 70 og 80 byttes ut. En bevegelse er en operasjon. En sammenligning er også en operasjon. En bytte er også en operasjon. Denne delen gir tre operasjoner. Det er totalt fire operasjoner så langt (1 + 3 = 4). Resultatet er som følger:

70 | 80 60 50 40 30 20 10

Ved indeks to er det en bevegelse til 60. 60 blir sammenlignet med 80, deretter byttes 60 og 80. 60 blir sammenlignet med 70, deretter byttes 60 og 70. En bevegelse er en operasjon. To sammenligninger er to operasjoner. To bytter er to operasjoner. Denne delen gir fem operasjoner. Det er totalt ni operasjoner så langt (4 + 5 = 9). Resultatet er som følger:

60 70 | 80 50 40 30 20 10

Ved indeks tre er det en bevegelse til 50. 50 blir sammenlignet med 80, deretter byttes 50 og 80. 50 blir sammenlignet med 70, deretter byttes 50 og 70. 50 blir sammenlignet med 60, deretter byttes 50 og 60. En bevegelse er en operasjon. Tre sammenligninger er tre operasjoner. Tre bytter er tre operasjoner. Denne delen gir syv operasjoner. Det er totalt seksten operasjoner så langt (9 + 7 = 16). Resultatet er som følger:

50 60 70 | 80 40 30 20 10

Ved indeks fire er det en bevegelse til 40. 40 blir sammenlignet med 80, deretter byttes 40 og 80. 40 blir sammenlignet med 70, deretter byttes 40 og 70. 40 blir sammenlignet med 60, deretter byttes 40 og 60. 40 blir sammenlignet med 50, deretter byttes 40 og 50. En bevegelse er en operasjon. Fire sammenligninger er fire operasjoner. Fire bytter er fire operasjoner. Denne delen gir ni operasjoner. Det er totalt tjuefem operasjoner så langt (16 + 9 = 25). Resultatet er som følger:

40 50 60 70 80 | 30 20 10

På indeks fem er det en bevegelse til 30. 30 blir sammenlignet med 80, deretter byttes 30 og 80. 30 blir sammenlignet med 70, deretter byttes 30 og 70. 30 blir sammenlignet med 60, deretter byttes 30 og 60. 30 blir sammenlignet med 50, deretter byttes 30 og 50. 30 blir sammenlignet med 40, deretter byttes 30 og 40. En bevegelse er en operasjon. Fem sammenligninger er fem operasjoner. Fem bytter er fem operasjoner. Denne delen gir elleve operasjoner. Det er totalt trettiseks operasjoner så langt (25 + 11 = 36). Resultatet er som følger:

30 40 50 60 70 80 | 20 10

Hos Index Six er det en bevegelse til 20. 20 blir sammenlignet med 80, deretter byttes 20 og 80. 20 blir sammenlignet med 70, deretter byttes 20 og 70. 20 blir sammenlignet med 60, deretter byttes 20 og 60. 20 blir sammenlignet med 50, deretter byttes 20 og 50. 20 blir sammenlignet med 40, deretter byttes 20 og 40. 20 blir sammenlignet med 30, deretter byttes 20 og 30. En bevegelse er en operasjon. Seks sammenligninger er seks operasjoner. Seks bytter er seks operasjoner. Denne delen gir tretten operasjoner. Det er totalt førti-ni operasjoner så langt (36 + 13 = 49). Resultatet er som følger:

20 30 40 50 60 70 80 | 10

På indeks syv er det en bevegelse til 10. 10 blir sammenlignet med 80, deretter byttes 10 og 80. 10 blir sammenlignet med 70, deretter byttes 10 og 70. 10 blir sammenlignet med 60, deretter byttes 10 og 60. 10 blir sammenlignet med 50, deretter byttes 10 og 50. 10 blir sammenlignet med 30, deretter byttes 10 og 40. 10 blir sammenlignet med 30, deretter byttes 10 og 30. 10 blir sammenlignet med 20, deretter byttes 10 og 20. En bevegelse er en operasjon. Syv sammenligninger er syv operasjoner. Syv bytter er syv operasjoner. Denne delen gir femten operasjoner. Det er totalt sekstifire operasjoner så langt (49 + 15 = 64). Resultatet er som følger:

10 20 30 40 50 60 70 80 10 |

Jobben er ferdig! 64 operasjoner var involvert.

64 = 8 x 8 = 8²

Tidskompleksitet for innsettingssortering

Hvis det er N -elementer å sortere med innsettingssort, vil det maksimale antallet mulige operasjoner være N2, som demonstrert tidligere. Innsettelsestidskompleksiteten er:

På²)

Dette bruker Big-O-notasjonen. Big-O-notasjonen begynner med O i store bokstaver, etterfulgt av parenteser. Inne i parentesene er uttrykket for maksimalt mulig antall operasjoner.

Koding i c

Helt i begynnelsen av skanningen kan ikke det første elementet endre sin posisjon. Programmet er egentlig følgende:

#inkludere
void insertionsort (int a [], int n)
for (int i = 0; iint j = i;
mens (a [j] < A[j-1] && j-1 >= 0)
int temp = a [j]; A [j] = a [j-1]; A [j-1] = temp; //bytte
j--;

Insertionsort () -funksjonsdefinisjonen bruker algoritmen som beskrevet. Legg merke til forholdene for mens-loop. En passende C hovedfunksjon for dette programmet er:

int main (int argc, char ** argv)

int n = 8;
int a [] = 50, 60, 30, 10, 80, 70, 20, 40;
Insertionsort (a, n);
for (int i = 0; iprintf ("%i", a [i]);

printf ("\ n");
retur 0;

Konklusjon

Tidskompleksiteten for innsettingssort er gitt som:

På²)

Leseren har kanskje hørt om en dårligere tidskompleksitet, gjennomsnittlig tidskompleksitet og best case tidskompleksitet. Disse variantene av innsettingssorterens kompleksitet er diskutert i neste artikkel på nettstedet vårt.