Indsættelsessorteringstidskompleksitet

Indsaettelsessorteringstidskompleksitet



Overvej følgende tal:

50 60 30 10 80 70 20 40







Hvis denne liste er sorteret i stigende rækkefølge, ville den være:



10 20 30 40 50 60 70 80



Hvis det er sorteret i faldende rækkefølge, vil det være:





80 70 60 50 40 30 20 10

Indsættelsessortering er en sorteringsalgoritme, der bruges til at sortere listen i stigende eller faldende rækkefølge. Denne artikel omhandler kun sortering i stigende rækkefølge. Sortering i faldende rækkefølge følger den samme logik som angivet i dette dokument. Formålet med denne artikel er at forklare indsættelsessorten. Programmering udføres i det følgende eksempel i C. Indsættelsessorteringen er forklaret her ved hjælp af et array.



Algoritme for indsættelsessortering

Der gives en usorteret liste. Målet er at sortere listen i stigende rækkefølge ved hjælp af den samme liste. Sortering af et usorteret array ved hjælp af det samme array siges at være sortering på stedet. Den nulbaserede indeksering bruges her. Trinene er som følger:

    • Listen scannes fra begyndelsen.
    • Mens scanningen foregår, bliver ethvert tal mindre end forgængeren byttet ud med forgængeren.
    • Dette bytte fortsætter langs listen, indtil det ikke længere er muligt at bytte.
    • Når scanningen når afslutningen, er sorteringen afsluttet.

Indsættelsessortering Illustration

Når man beskæftiger sig med tidskompleksitet, er det det værste tilfælde, der normalt tages i betragtning. Det værste arrangement for den forrige liste er:

80 70 60 50 40 30 20 10

Der er otte elementer med indekser fra nul til 7.

Ved indeks nul går scanningen til 80. Dette er én bevægelse. Denne ene bevægelse er en operation. Der er i alt en operation indtil videre (én bevægelse, ingen sammenligning og ingen swap). Resultatet er:

| 80 70 60 50 40 30 20 10

Ved indeks et er der en bevægelse til 70. 70 sammenlignes med 80. 70 og 80 er byttet. Én bevægelse er én operation. Én sammenligning er også én operation. Ét bytte er også én operation. Dette afsnit indeholder tre operationer. Der er i alt fire operationer indtil videre (1 + 3 = 4). Resultatet er som følger:

70 | 80 60 50 40 30 20 10

Ved indeks to er der en bevægelse til 60. 60 sammenlignes med 80, derefter byttes 60 og 80. 60 sammenlignes med 70, derefter byttes 60 og 70. Én bevægelse er én operation. To sammenligninger er to operationer. To swaps er to operationer. Dette afsnit indeholder fem operationer. Der er i alt ni operationer indtil videre (4 + 5 = 9). Resultatet er som følger:

60 70 | 80 50 40 30 20 10

Ved indeks tre er der en bevægelse til 50. 50 sammenlignes med 80, derefter byttes 50 og 80. 50 sammenlignes med 70, derefter byttes 50 og 70. 50 sammenlignes med 60, derefter byttes 50 og 60. Én bevægelse er én operation. Tre sammenligninger er tre operationer. Tre swaps er tre operationer. Dette afsnit indeholder syv operationer. Der er i alt seksten operationer indtil videre (9 + 7 = 16). Resultatet er som følger:

50 60 70 | 80 40 30 20 10

Ved indeks fire er der en bevægelse til 40. 40 sammenlignes med 80, derefter byttes 40 og 80. 40 sammenlignes med 70, derefter byttes 40 og 70. 40 sammenlignes med 60, derefter byttes 40 og 60. 40 sammenlignes med 50, derefter byttes 40 og 50. Én bevægelse er én operation. Fire sammenligninger er fire operationer. Fire swaps er fire operationer. Dette afsnit indeholder ni operationer. Der er i alt femogtyve operationer indtil videre (16 + 9 = 25). Resultatet er som følger:

40 50 60 70 80 | 30 20 10

Ved indeks fem er der en bevægelse til 30. 30 sammenlignes med 80, derefter byttes 30 og 80. 30 sammenlignes med 70, derefter byttes 30 og 70. 30 sammenlignes med 60, derefter byttes 30 og 60. 30 sammenlignes med 50, derefter byttes 30 og 50. 30 sammenlignes med 40, derefter byttes 30 og 40. Én bevægelse er én operation. Fem sammenligninger er fem operationer. Fem swaps er fem operationer. Dette afsnit indeholder elleve operationer. Der er i alt seksogtredive operationer indtil videre (25 + 11 = 36). Resultatet er som følger:

30 40 50 60 70 80 | 20 10

Ved indeks seks er der en bevægelse til 20. 20 sammenlignes med 80, derefter byttes 20 og 80. 20 sammenlignes med 70, derefter byttes 20 og 70. 20 sammenlignes med 60, derefter byttes 20 og 60. 20 sammenlignes med 50, derefter byttes 20 og 50. 20 sammenlignes med 40, derefter byttes 20 og 40. 20 sammenlignes med 30, derefter byttes 20 og 30. Én bevægelse er én operation. Seks sammenligninger er seks operationer. Seks swaps er seks operationer. Dette afsnit indeholder tretten operationer. Der er i alt niogfyrre operationer indtil videre (36 + 13 = 49). Resultatet er som følger:

20 30 40 50 60 70 80 | 10

Ved indeks syv er der en bevægelse til 10. 10 sammenlignes med 80, derefter byttes 10 og 80. 10 sammenlignes med 70, derefter byttes 10 og 70. 10 sammenlignes med 60, derefter byttes 10 og 60. 10 sammenlignes med 50, derefter byttes 10 og 50. 10 sammenlignes med 30, derefter byttes 10 og 40. 10 sammenlignes med 30, derefter byttes 10 og 30. 10 sammenlignes med 20, derefter byttes 10 og 20. Én bevægelse er én operation. Syv sammenligninger er syv operationer. Syv swaps er syv operationer. Dette afsnit indeholder femten operationer. Der er i alt fireogtres operationer indtil videre (49 + 15 = 64). Resultatet er som følger:

10 20 30 40 50 60 70 80 10 |

Jobbet er udført! 64 operationer var involveret.

64 = 8 x 8 = 8 to

Tidskompleksitet for indsættelsessortering

Hvis der er n elementer at sortere med Insertion Sort, vil det maksimale antal mulige operationer være n2, som vist tidligere. Indsættelsessorteringstidskompleksiteten er:

to )

Dette bruger Big-O notationen. Big-O-notationen begynder med O med store bogstaver efterfulgt af parenteser. Inde i parentesen er udtrykket for det maksimalt mulige antal operationer.

Kodning i C

Allerede i begyndelsen af ​​scanningen kan det første element ikke ændre sin position. Programmet er i bund og grund følgende:

#include

ugyldig indsættelseSort ( int A [ ] , int N ) {
til ( int jeg = 0 ; jeg < N; i++ ) {
int j = i;
mens ( EN [ j ] < EN [ j- 1 ] && j- 1 > = 0 ) {
int temp = A [ j ] ; EN [ j ] = A [ j- 1 ] ; EN [ j- 1 ] = temp; // bytte rundt
j--;
}
}
}


Funktionsdefinitionen insertionSort() bruger algoritmen som beskrevet. Bemærk betingelserne for while-løkken. En passende C-hovedfunktion til dette program er:

int main ( int argc, char ** argv )
{
int n = 8 ;
int A [ ] = { halvtreds , 60 , 30 , 10 , 80 , 70 , tyve , 40 } ;

indsættelseSort ( A, n ) ;

til ( int jeg = 0 ; jeg < n; i++ ) {
printf ( '%i' , A [ jeg ] ) ;
}
printf ( ' \n ' ) ;

Vend tilbage 0 ;
}

Konklusion

Tidskompleksiteten for indsættelsessortering er angivet som:

to )

Læseren har måske hørt om en værre tilfældes tidskompleksitet, gennemsnitlig tidskompleksitet og best-case tidskompleksitet. Disse variationer af Insertion Sort Time Complexity diskuteres i den næste artikel på vores hjemmeside.