Insättningssorteringstidskomplexitet

Tänk på följande siffror:

50 60 30 10 80 70 20 40

Om den här listan är sorterad i stigande ordning skulle den vara:

10 20 30 40 50 60 70 80

Om det sorteras i fallande ordning skulle det vara:

80 70 60 50 40 30 20 10

Infogningssortering är en sorteringsalgoritm som används för att sortera listan i stigande eller fallande ordning. Den här artikeln handlar endast om sortering i stigande ordning. Sortering i fallande ordning följer samma logik som anges i detta dokument. Syftet med den här artikeln är att förklara insättningssorten. Programmering görs i följande exempel i C. Insättningssorteringen förklaras här med en array.

Algoritm för sortering av infogning

En osorterad lista ges. Syftet är att sortera listan i stigande ordning med samma lista. Att sortera en osorterad array med samma array sägs vara sortering på plats. Den nollbaserade indexeringen används här. Stegen är som följer:

• • Listan skannas från början.
  • Medan skanningen pågår byts valfritt antal mindre än dess föregångare ut med dess föregångare.
  • Detta byte fortsätter längs listan tills det inte längre är möjligt att byta.
  • När skanningen når slutet är sorteringen klar.

Insättning Sortera Illustration

När man hanterar tidskomplexitet är det det värsta fallet som normalt tas i beaktande. Det sämsta arrangemanget för den tidigare listan är:

80 70 60 50 40 30 20 10

Det finns åtta element med index från noll till 7.

Vid index noll går skanningen till 80. Detta är en rörelse. Denna ena rörelse är en operation. Det finns totalt en operation hittills (en rörelse, ingen jämförelse och inget byte). Resultatet är:

| 80 70 60 50 40 30 20 10

Vid index ett sker en rörelse till 70. 70 jämförs med 80. 70 och 80 byts. En rörelse är en operation. En jämförelse är också en operation. Ett byte är också en operation. Detta avsnitt innehåller tre operationer. Det är totalt fyra operationer hittills (1 + 3 = 4). Resultatet är som följer:

70 | 80 60 50 40 30 20 10

Vid index två sker en rörelse till 60. 60 jämförs med 80, sedan byts 60 och 80. 60 jämförs med 70, sedan byts 60 och 70. En rörelse är en operation. Två jämförelser är två operationer. Två byten är två operationer. Detta avsnitt innehåller fem operationer. Det är totalt nio operationer hittills (4 + 5 = 9). Resultatet är som följer:

60 70 | 80 50 40 30 20 10

Vid index tre sker en rörelse till 50. 50 jämförs med 80, sedan byts 50 och 80. 50 jämförs med 70, sedan byts 50 och 70. 50 jämförs med 60, sedan byts 50 och 60. En rörelse är en operation. Tre jämförelser är tre operationer. Tre byten är tre operationer. Detta avsnitt innehåller sju operationer. Det är totalt sexton operationer hittills (9 + 7 = 16). Resultatet är som följer:

50 60 70 | 80 40 30 20 10

Vid index fyra sker en rörelse till 40. 40 jämförs med 80, sedan byts 40 och 80. 40 jämförs med 70, sedan byts 40 och 70. 40 jämförs med 60, sedan byts 40 och 60. 40 jämförs med 50, sedan byts 40 och 50. En rörelse är en operation. Fyra jämförelser är fyra operationer. Fyra byten är fyra operationer. Det här avsnittet innehåller nio operationer. Det finns totalt tjugofem operationer hittills (16 + 9 = 25). Resultatet är som följer:

40 50 60 70 80 | 30 20 10

Vid index fem sker en rörelse till 30. 30 jämförs med 80, sedan byts 30 och 80. 30 jämförs med 70, sedan byts 30 och 70. 30 jämförs med 60, sedan byts 30 och 60. 30 jämförs med 50, sedan byts 30 och 50. 30 jämförs med 40, sedan byts 30 och 40. En rörelse är en operation. Fem jämförelser är fem operationer. Fem byten är fem operationer. Detta avsnitt innehåller elva operationer. Det finns totalt trettiosex operationer hittills (25 + 11 = 36). Resultatet är som följer:

30 40 50 60 70 80 | 20 10

Vid index sex sker en rörelse till 20. 20 jämförs med 80, sedan byts 20 och 80. 20 jämförs med 70, sedan byts 20 och 70. 20 jämförs med 60, sedan byts 20 och 60. 20 jämförs med 50, sedan byts 20 och 50. 20 jämförs med 40, sedan byts 20 och 40. 20 jämförs med 30, sedan byts 20 och 30. En rörelse är en operation. Sex jämförelser är sex operationer. Sex byten är sex operationer. Detta avsnitt innehåller tretton operationer. Det finns totalt fyrtionio operationer hittills (36 + 13 = 49). Resultatet är som följer:

20 30 40 50 60 70 80 | 10

Vid index sju sker en rörelse till 10. 10 jämförs med 80, sedan byts 10 och 80. 10 jämförs med 70, sedan byts 10 och 70. 10 jämförs med 60, sedan byts 10 och 60. 10 jämförs med 50, sedan byts 10 och 50. 10 jämförs med 30, sedan byts 10 och 40. 10 jämförs med 30, sedan byts 10 och 30. 10 jämförs med 20, sedan byts 10 och 20. En rörelse är en operation. Sju jämförelser är sju operationer. Sju byten är sju operationer. Detta avsnitt innehåller femton operationer. Det finns totalt sextiofyra operationer hittills (49 + 15 = 64). Resultatet är som följer:

10 20 30 40 50 60 70 80 10 |

Jobbet är gjort! 64 operationer var inblandade.

64 = 8 x 8 = 8 ^två

Tidskomplexitet för insättningssortering

Om det finns n element att sortera med Insertion Sort, skulle det maximala antalet möjliga operationer vara n2, som visats tidigare. Insättningssorteringstidskomplexiteten är:

På ^två )

Detta använder Big-O-notationen. Big-O-notationen börjar med O i versaler, följt av parenteser. Inom parentesen finns uttrycket för maximalt antal operationer.

Kodning i C

I början av skanningen kan det första elementet inte ändra sin position. Programmet är i huvudsak följande:

Funktionsdefinitionen insertionSort() använder algoritmen som beskrivs. Notera villkoren för while-loopen. En lämplig C-huvudfunktion för detta program är:

Slutsats

Tidskomplexiteten för infogningssortering ges som:

På ^två )

Läsaren kanske har hört talas om tidskomplexitet i värre fallet, tidskomplexitet i genomsnitt och tidskomplexitet i bästa fall. Dessa varianter av insättningssorteringstidskomplexiteten diskuteras i nästa artikel på vår webbplats.