Différence entre le tri par insertion et le tri par sélection

Le tri par insertion et le tri par sélection sont des techniques utilisées pour trier les données. Le tri par sélection et le tri par insertion peuvent être différenciés par la méthode utilisée pour trier les données. Le tri par insertion insère les valeurs dans un fichier pré-trié pour trier un ensemble de valeurs. Tandis que, le tri par sélection trouve le nombre minimum dans une liste ou une classe dans un certain ordre.

Le tri est une opération de base dans laquelle les éléments d’un tableau sont disposés dans un ordre spécifique pour améliorer la recherche. En gros, les données sont triées afin qu’elles puissent être facilement recherchées.
 
 

Table de comparaison
Tri par insertion Tri par sélection
Définition Les données sont triées en insérant les données dans un fichier trié existant. Les données sont triées en sélectionnant et en plaçant les éléments consécutifs dans l’emplacement trié.
Processus à suivre Les éléments sont connus à l’avance tandis que l’emplacement pour les placer est recherché. L’emplacement est déjà connu pendant que les éléments sont recherchés.
Données immédiates Le tri par insertion est une technique de tri en direct qui peut traiter des données immédiates. Il ne peut pas traiter des données immédiates, il doit être présent au début.
Complexité O(n) O(n2)

 

Tri par insertion

Le tri par insertion fonctionne en insérant l’ensemble de valeurs dans le fichier trié existant.

Il construit le tableau trié en insérant un seul élément à la fois. Ce processus se poursuit jusqu’à ce que le tableau entier soit trié dans un certain ordre. Le concept principal du tri par insertion consiste à insérer chaque élément à l’endroit approprié dans la liste finale. La méthode de tri par insertion permet d’économiser une quantité efficace de mémoire.
 
Avantages du tri par insertion

  • Facilement mis en œuvre et très efficace lorsqu’il est utilisé avec de petits ensembles de données.
  • L’espace mémoire supplémentaire requis pour le tri par insertion est inférieur (c’est-à-dire O (1)).
  • Il est considéré comme une technique de tri en direct car la liste peut être triée lorsque les nouveaux éléments sont reçus.
  • C’est plus rapide que les autres algorithmes de tri.
Tri par sélection

Le tri par sélection effectue le tri en recherchant la valeur minimum et en le plaçant dans la première ou la dernière position selon l’ordre (croissant ou décroissant). Le processus de recherche de la clé minimum et de placement dans la bonne position est poursuivi jusqu’à ce que tous les éléments soient placés à la bonne position.
QCM-C

Différences clés entre le tri par insertion et le tri par sélection
  • Le tri par insertion effectue généralement l’opération d’insertion. Au contraire, le tri par sélection effectue la sélection et le positionnement des éléments requis.
  • Le tri par insertion est dit stable alors que le tri par sélection n’est pas un algorithme stable.
  • Dans l’algorithme de tri par insertion, les éléments sont déjà connus. En revanche, le tri par sélection contient l’emplacement à l’avance.
  • Le tri par insertion est une technique de tri en direct où les éléments arrivant sont immédiatement triés dans la liste alors que le tri par sélection ne peut pas fonctionner correctement avec les données immédiates.
  • Le tri par insertion a le temps d’exécution O (n) dans le meilleur des cas. Par contre, la meilleure complexité d’exécution du tri par sélection est O (n2).

 

Conclusion

Parmi les deux algorithmes de tri, le tri par insertion est rapide, efficace, stable tandis que le tri par sélection ne fonctionne efficacement que lorsque le petit ensemble d’éléments est impliqué ou que la liste est partiellement triée au préalable. Le nombre de comparaisons faites par tri par sélection est supérieur aux mouvements effectués alors que dans le tri par insertion, le nombre de fois qu’un élément est déplacé ou échangé est supérieur aux comparaisons effectuées.
 
 

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *