Complexité du temps de tri d'insertion

Complexite Du Temps De Tri D Insertion



Considérez les nombres suivants :

50 60 30 10 80 70 20 40







Si cette liste était triée par ordre croissant, ce serait :



10 20 30 40 50 60 70 80



S'il est trié par ordre décroissant, ce serait :





80 70 60 50 40 30 20 10

Le tri par insertion est un algorithme de tri utilisé pour trier la liste par ordre croissant ou décroissant. Cet article traite uniquement du tri par ordre croissant. Le tri par ordre décroissant suit la même logique donnée dans ce document. Le but de cet article est d'expliquer le tri par insertion. La programmation est faite dans l'exemple suivant en C. Le tri par insertion est expliqué ici en utilisant un tableau.



Algorithme pour le tri par insertion

Une liste non triée est donnée. Le but est de trier la liste par ordre croissant en utilisant la même liste. Le tri d'un tableau non trié à l'aide du même tableau est dit tri sur place. L'indexation à base zéro est utilisée ici. Les étapes sont les suivantes:

    • La liste est scannée depuis le début.
    • Pendant l'analyse, tout nombre inférieur à son prédécesseur est échangé avec son prédécesseur.
    • Cet échange se poursuit le long de la liste, jusqu'à ce qu'il ne soit plus possible d'échanger.
    • Lorsque la numérisation atteint la fin, le tri est terminé.

Illustration de tri d'insertion

Lorsqu'il s'agit de complexité temporelle, c'est le pire des cas qui est normalement pris en considération. Le pire arrangement pour la liste précédente est :

80 70 60 50 40 30 20 10

Il y a huit éléments avec des indices de zéro à 7.

A l'index zéro, le balayage passe à 80. C'est un mouvement. Ce seul mouvement est une opération. Il y a un total d'une opération jusqu'à présent (un mouvement, pas de comparaison et pas d'échange). Le résultat est:

| 80 70 60 50 40 30 20 10

À l'indice un, il y a un mouvement vers 70. 70 est comparé à 80. 70 et 80 sont échangés. Un mouvement est une opération. Une comparaison est aussi une opération. Un swap est aussi une opération. Cette section propose trois opérations. Il y a un total de quatre opérations jusqu'à présent (1 + 3 = 4). Le résultat est le suivant :

70 | 80 60 50 40 30 20 10

A l'indice deux, il y a un mouvement vers 60. 60 est comparé à 80, puis 60 et 80 sont permutés. 60 est comparé à 70, puis 60 et 70 sont échangés. Un mouvement est une opération. Deux comparaisons sont deux opérations. Deux swaps sont deux opérations. Cette section propose cinq opérations. Il y a un total de neuf opérations jusqu'à présent (4 + 5 = 9). Le résultat est le suivant :

60 70 | 80 50 40 30 20 10

A l'indice trois, il y a un mouvement vers 50. 50 est comparé à 80, puis 50 et 80 sont permutés. 50 est comparé à 70, puis 50 et 70 sont échangés. 50 est comparé à 60, puis 50 et 60 sont échangés. Un mouvement est une opération. Trois comparaisons sont trois opérations. Trois swaps sont trois opérations. Cette section propose sept opérations. Il y a un total de seize opérations à ce jour (9 + 7 = 16). Le résultat est le suivant :

50 60 70 | 80 40 30 20 10

A l'indice quatre, il y a un mouvement vers 40. 40 est comparé à 80, puis 40 et 80 sont permutés. 40 est comparé à 70, puis 40 et 70 sont échangés. 40 est comparé à 60, puis 40 et 60 sont échangés. 40 est comparé à 50, puis 40 et 50 sont échangés. Un mouvement est une opération. Quatre comparaisons sont quatre opérations. Quatre swaps sont quatre opérations. Cette section fournit neuf opérations. Il y a un total de vingt-cinq opérations à ce jour (16 + 9 = 25). Le résultat est le suivant :

40 50 60 70 80 | 30 20 10

A l'indice cinq, il y a un mouvement vers 30. 30 est comparé à 80, puis 30 et 80 sont permutés. 30 est comparé à 70, puis 30 et 70 sont échangés. 30 est comparé à 60, puis 30 et 60 sont échangés. 30 est comparé à 50, puis 30 et 50 sont échangés. 30 est comparé à 40, puis 30 et 40 sont échangés. Un mouvement est une opération. Cinq comparaisons sont cinq opérations. Cinq swaps sont cinq opérations. Cette section fournit onze opérations. Il y a un total de trente-six opérations à ce jour (25 + 11 = 36). Le résultat est le suivant :

30 40 50 60 70 80 | 20 10

A l'indice six, il y a un mouvement vers 20. 20 est comparé à 80, puis 20 et 80 sont permutés. 20 est comparé à 70, puis 20 et 70 sont échangés. 20 est comparé à 60, puis 20 et 60 sont échangés. 20 est comparé à 50, puis 20 et 50 sont échangés. 20 est comparé à 40, puis 20 et 40 sont échangés. 20 est comparé à 30, puis 20 et 30 sont échangés. Un mouvement est une opération. Six comparaisons sont six opérations. Six swaps sont six opérations. Cette section fournit treize opérations. Il y a un total de quarante-neuf opérations à ce jour (36 + 13 = 49). Le résultat est le suivant :

20 30 40 50 60 70 80 | dix

A l'indice sept, il y a un mouvement vers 10. 10 est comparé à 80, puis 10 et 80 sont permutés. 10 est comparé à 70, puis 10 et 70 sont échangés. 10 est comparé à 60, puis 10 et 60 sont échangés. 10 est comparé à 50, puis 10 et 50 sont échangés. 10 est comparé à 30, puis 10 et 40 sont échangés. 10 est comparé à 30, puis 10 et 30 sont échangés. 10 est comparé à 20, puis 10 et 20 sont échangés. Un mouvement est une opération. Sept comparaisons sont sept opérations. Sept swaps sont sept opérations. Cette section fournit quinze opérations. Il y a un total de soixante-quatre opérations à ce jour (49 + 15 = 64). Le résultat est le suivant :

10 20 30 40 50 60 70 80 10 |

Le travail est fait ! 64 opérations ont été impliquées.

64 = 8 x 8 = 8 deux

Complexité temporelle pour le tri par insertion

S'il y a n éléments à trier avec le tri par insertion, le nombre maximum d'opérations possibles serait n2, comme démontré précédemment. La complexité du temps de tri d'insertion est :

Sur deux )

Cela utilise la notation Big-O. La notation Big-O commence par O en majuscule, suivi de parenthèses. À l'intérieur des parenthèses se trouve l'expression du nombre maximal possible d'opérations.

Codage en C

Au tout début du scan, le premier élément ne peut pas changer de position. Le programme est essentiellement le suivant :

#include

void insertionTrier ( entier A [ ] , entier N ) {
pour ( entier je = 0 ; je < N; je++ ) {
int j = je ;
tandis que ( UN [ j ] < UN [ j- 1 ] && j- 1 > = 0 ) {
temp int = A [ j ] ; UN [ j ] = UN [ j- 1 ] ; UN [ j- 1 ] = temp ; // échanger
j-- ;
}
}
}


La définition de la fonction insertionSort() utilise l'algorithme tel que décrit. Notez les conditions de la boucle while. Une fonction principale C appropriée pour ce programme est :

int main ( int argc, caractère ** argv )
{
entier n = 8 ;
entier A [ ] = { cinquante , 60 , 30 , dix , 80 , 70 , vingt , 40 } ;

tri par insertion ( Un ) ;

pour ( entier je = 0 ; je < n; je++ ) {
printf ( '%je ' , UN [ je ] ) ;
}
printf ( ' \n ' ) ;

revenir 0 ;
}

Conclusion

La complexité temporelle du tri par insertion est donnée par :

Sur deux )

Le lecteur a peut-être entendu parler d'une complexité temporelle dans le pire des cas, d'une complexité temporelle dans le cas moyen et d'une complexité temporelle dans le meilleur des cas. Ces variations de la complexité du temps de tri d'insertion sont abordées dans le prochain article de notre site Web.