Innsettingssorteringstid kompleksitet

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

Innsettingssortering er en sorteringsalgoritme som brukes til å sortere listen i stigende eller synkende rekkefølge. Denne artikkelen omhandler kun sortering i stigende rekkefølge. Sortering i synkende rekkefølge følger samme logikk gitt i dette dokumentet. Målet med denne artikkelen er å forklare innsettingssorten. Programmering gjøres i følgende eksempel i C. Innsettingssorteringen er forklart her ved bruk av én array.

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 å være sortering på plass. Nullbasert indeksering brukes her. Trinnene er som følger:

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

Innsetting Sorter illustrasjon

Når man håndterer tidskompleksitet, er det verste tilfellet som normalt tas i betraktning. Den verste ordningen for den forrige listen er:

80 70 60 50 40 30 20 10

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

Ved indeks null går skanningen til 80. Dette er én bevegelse. Denne ene bevegelsen er en operasjon. Det er totalt én operasjon så langt (én bevegelse, ingen sammenligning og ingen bytte). Resultatet er:

| 80 70 60 50 40 30 20 10

Ved indeks én er det en bevegelse til 70. 70 sammenlignes med 80. 70 og 80 byttes. Én bevegelse er én operasjon. Én sammenligning er også én operasjon. Én bytte er også én operasjon. Denne delen inneholder 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 sammenlignes med 80, deretter byttes 60 og 80. 60 sammenlignes med 70, deretter byttes 60 og 70. Én bevegelse er én operasjon. To sammenligninger er to operasjoner. To bytter er to operasjoner. Denne delen inneholder 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 sammenlignes med 80, deretter byttes 50 og 80. 50 sammenlignes med 70, deretter byttes 50 og 70. 50 sammenlignes med 60, deretter byttes 50 og 60. Én bevegelse er én operasjon. Tre sammenligninger er tre operasjoner. Tre bytter er tre operasjoner. Denne delen inneholder 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 sammenlignes med 80, deretter byttes 40 og 80. 40 sammenlignes med 70, deretter byttes 40 og 70. 40 sammenlignes med 60, deretter byttes 40 og 60. 40 sammenlignes med 50, deretter byttes 40 og 50. Én bevegelse er én operasjon. Fire sammenligninger er fire operasjoner. Fire bytter er fire operasjoner. Denne delen inneholder 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

Ved indeks fem er det en bevegelse til 30. 30 sammenlignes med 80, deretter byttes 30 og 80. 30 sammenlignes med 70, deretter byttes 30 og 70. 30 sammenlignes med 60, deretter byttes 30 og 60. 30 sammenlignes med 50, deretter byttes 30 og 50. 30 sammenlignes med 40, deretter byttes 30 og 40. Én bevegelse er én operasjon. Fem sammenligninger er fem operasjoner. Fem bytter er fem operasjoner. Denne delen inneholder 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

Ved indeks seks er det en bevegelse til 20. 20 sammenlignes med 80, deretter byttes 20 og 80. 20 sammenlignes med 70, deretter byttes 20 og 70. 20 sammenlignes med 60, deretter byttes 20 og 60. 20 sammenlignes med 50, deretter byttes 20 og 50. 20 sammenlignes med 40, deretter byttes 20 og 40. 20 sammenlignes med 30, deretter byttes 20 og 30. Én bevegelse er én operasjon. Seks sammenligninger er seks operasjoner. Seks bytteavtaler er seks operasjoner. Denne delen inneholder 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

Ved indeks syv er det en bevegelse til 10. 10 sammenlignes med 80, deretter byttes 10 og 80. 10 sammenlignes med 70, deretter byttes 10 og 70. 10 sammenlignes med 60, deretter byttes 10 og 60. 10 sammenlignes med 50, deretter byttes 10 og 50. 10 sammenlignes med 30, deretter byttes 10 og 40. 10 sammenlignes med 30, deretter byttes 10 og 30. 10 sammenlignes med 20, deretter byttes 10 og 20. Én bevegelse er én operasjon. Syv sammenligninger er syv operasjoner. Syv bytteavtaler er syv operasjoner. Denne delen inneholder 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 gjort! 64 operasjoner var involvert.

64 = 8 x 8 = 8 ^to

Tidskompleksitet for innsettingssortering

Hvis det er n elementer å sortere med Insertion Sort, vil det maksimale antallet mulige operasjoner være n2, som vist tidligere. Kompleksiteten for innsettingssorteringstid er:

På ^to )

Dette bruker Big-O-notasjonen. Big-O-notasjonen begynner med O med store bokstaver, etterfulgt av parenteser. Inne i parentesen 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 i hovedsak følgende:

Funksjonsdefinisjonen insertionSort() bruker algoritmen som beskrevet. Legg merke til betingelsene for while-løkken. En passende C-hovedfunksjon for dette programmet er:

Konklusjon

Tidskompleksiteten for innsettingssortering er gitt som:

På ^to )

Leseren har kanskje hørt om en verre-tilfelle-tidskompleksitet, gjennomsnittlig-tilfelle-tidskompleksitet og best-case-tidskompleksitet. Disse variantene av innsettingssorteringstidskompleksiteten diskuteres i neste artikkel på nettstedet vårt.