Tri par insertion de structure de données et d'algorithmes

Il s'agit d'un algorithme de tri basé sur une comparaison sur place. Ici, une sous-liste est maintenue qui est toujours triée. Par exemple, la partie inférieure d'un tableau est conservée pour être triée. Un élément qui doit être «inséré» dans cette sous-liste triée doit trouver sa place appropriée, puis il doit y être inséré. D'où le nom,insertion sort.

Le tableau est recherché séquentiellement et les éléments non triés sont déplacés et insérés dans la sous-liste triée (dans le même tableau). Cet algorithme ne convient pas aux grands ensembles de données car sa complexité moyenne et dans le pire des cas est de Ο (n 2 ), oùn est le nombre d'éléments.

Comment fonctionne le tri par insertion?

Nous prenons un tableau non trié pour notre exemple.

Le tri par insertion compare les deux premiers éléments.

Il constate que les deux 14 et 33 sont déjà dans l'ordre croissant. Pour l'instant, 14 est dans une sous-liste triée.

Le tri par insertion avance et compare 33 à 27.

Et constate que 33 n'est pas dans la bonne position.

Il échange 33 contre 27. Il vérifie également avec tous les éléments de la sous-liste triée. Ici, nous voyons que la sous-liste triée n'a qu'un seul élément 14, et 27 est supérieur à 14. Par conséquent, la sous-liste triée reste triée après l'échange.

À présent, nous avons 14 et 27 dans la sous-liste triée. Ensuite, il compare 33 à 10.

Ces valeurs ne sont pas triées.

Nous les échangeons donc.

Cependant, l'échange rend 27 et 10 non triés.

Par conséquent, nous les échangeons aussi.

Encore une fois, nous trouvons 14 et 10 dans un ordre non trié.

Nous les échangeons à nouveau. À la fin de la troisième itération, nous avons une sous-liste triée de 4 éléments.

Ce processus se poursuit jusqu'à ce que toutes les valeurs non triées soient couvertes dans une sous-liste triée. Nous allons maintenant voir quelques aspects de programmation du tri par insertion.

Algorithme

Nous avons maintenant une vue d'ensemble du fonctionnement de cette technique de tri, nous pouvons donc en déduire des étapes simples grâce auxquelles nous pouvons réaliser le tri par insertion.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Pseudocode

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
	
   for i = 1 to length(A) inclusive do:
	
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end procedure

Pour connaître l'implémentation du tri par insertion dans le langage de programmation C, veuillez cliquer ici .