Complexité du temps de tri de l'insertion

Considérez les numéros suivants:

50 60 30 10 80 70 20 40

Si cette liste est 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 de l'insertion est un algorithme de tri qui est utilisé pour trier la liste par ordre croissant ou dans l'ordre descendant. Cet article ne traite que du tri par ordre croissant. Le tri dans l'ordre descendant suit la même logique donnée dans ce document. Le but de cet article est d'expliquer le type d'insertion. La programmation se fait dans l'exemple suivant en C. Le tri d'insertion est expliqué ici en utilisant un tableau.

Algorithme pour le tri de l'insertion

Une liste non triée est donnée. L'objectif est de trier la liste par ordre croissant en utilisant la même liste. Le tri d'un tableau non trié en utilisant le même tableau est censé trier en place. L'indexation zéro est utilisée ici. Les étapes sont les suivantes:

• • La liste est numérisée depuis le début.
  • Pendant que le balayage se déroule, un nombre inférieur à son prédécesseur est échangé avec son prédécesseur.
  • Cet échange continue 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 insertion

Lorsque vous traitez avec la complexité du temps, c'est le pire des cas qui soit 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.

À Index Zero, 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'index un, il y a un mouvement à 70. 70 est comparé à 80. 70 et 80 sont échangés. Un mouvement est une opération. Une comparaison est également une opération. Un échange est également une opération. Cette section fournit 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

À l'index deux, il y a un mouvement à 60. 60 est comparé à 80, puis 60 et 80 sont échangé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 échanges sont deux opérations. Cette section fournit cinq opérations. Il y a jusqu'à présent un total de neuf opérations (4 + 5 = 9). Le résultat est le suivant:

60 70 | 80 50 40 30 20 10

À l'index trois, il y a un mouvement à 50. 50 est comparé à 80, puis 50 et 80 sont échangé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 échanges sont trois opérations. Cette section fournit sept opérations. Il y a jusqu'à présent un total de seize opérations (9 + 7 = 16). Le résultat est le suivant:

50 60 70 | 80 40 30 20 10

À l'index quatre, il y a un mouvement à 40. 40 est comparé à 80, puis 40 et 80 sont échangé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 jusqu'à présent un total de vingt-cinq opérations (16 + 9 = 25). Le résultat est le suivant:

40 50 60 70 80 | 30 20 10

À l'index cinq, il y a un mouvement à 30. 30 est comparé à 80, puis 30 et 80 sont échangé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 échanges sont cinq opérations. Cette section fournit onze opérations. Il y a jusqu'à présent un total de trente-six opérations (25 + 11 = 36). Le résultat est le suivant:

30 40 50 60 70 80 | 20 10

À l'index six, il y a un mouvement à 20. 20 est comparé à 80, puis 20 et 80 sont échangé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 jusqu'à présent un total de quarante-neuf opérations (36 + 13 = 49). Le résultat est le suivant:

20 30 40 50 60 70 80 | dix

À l'index sept, il y a un mouvement à 10. 10 est comparé à 80, puis 10 et 80 sont échangé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 jusqu'à présent un total de soixante-quatre opérations (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²

Complexité du temps pour le tri de l'insertion

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

Sur²)

Cela utilise la notation Big-O. La notation Big-O commence par O en majuscules, suivie 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 modifier sa position. Le programme est essentiellement les suivants:

#inclure
void insertionsort (int a [], int n)
pour (int i = 0; iint j = i;
tandis que (un [j] < A[j-1] && j-1 >= 0)
int temp = a [j]; A [j] = a [j-1]; A [j-1] = temp; //échanger
J-;

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

int main (int argc, char ** argv)

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

printf ("\ n");
retour 0;

Conclusion

La complexité du temps pour le tri de l'insertion est donnée comme suit:

Sur²)

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