DAA - Tri par insertion

Le tri par insertion est une méthode très simple pour trier les nombres dans un ordre croissant ou décroissant. Cette méthode suit la méthode incrémentielle. Il peut être comparé à la technique de tri des cartes au moment de la partie.

Les nombres, qui doivent être triés, sont appelés keys. Voici l'algorithme de la méthode de tri par insertion.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

Une analyse

Le temps d'exécution de cet algorithme dépend beaucoup de l'entrée donnée.

Si les nombres donnés sont triés, cet algorithme s'exécute dans O(n)temps. Si les nombres donnés sont dans l'ordre inverse, l'algorithme s'exécute enO(n²) temps.

Exemple

Unsorted list:

2 13 5 18 14

1^st iteration:

Clé = a [2] = 13

a [1] = 2 <13

Swap, pas de swap

2 13 5 18 14

2^nd iteration:

Clé = a [3] = 5

a [2] = 13> 5

Swap 5 et 13

2 5 13 18 14

Ensuite, a [1] = 2 <13

Swap, pas de swap

2 5 13 18 14

3^rd iteration:

Clé = a [4] = 18

a [3] = 13 <18,

a [2] = 5 <18,

a [1] = 2 <18

Swap, pas de swap

2 5 13 18 14

4^th iteration:

Clé = a [5] = 14

a [4] = 18> 14

Swap 18 et 14

2 5 13 14 18

Ensuite, a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

Donc, pas de swap

2 5 13 14 18

Finalement,

the sorted list is

2 5 13 14 18