À la base, le tri par insertion est un algorithme de tri. Il peut placer divers éléments non triés aux endroits qui leur conviennent le mieux à chaque itération. On peut dire que cet algorithme fonctionne de manière assez similaire à la façon dont les gens trient les cartes dans leur main. Si vous avez déjà joué à des jeux de cartes, vous savez que les joueurs de cartes trient en partant du principe que les premières cartes sont déjà triées, après quoi ils sélectionnent les cartes non triées.
Si la carte non triée s’avère être plus grande que la carte en main du joueur, il doit la placer à droite. Sinon, ils doivent garder la carte sur le côté gauche. De même, vous devez placer le reste des cartes non triées et les conserver à leur place respective. L’approche utilisée par le tri par insertion est assez similaire à celle-ci.
Les bases du fonctionnement du tri par insertion
Les trois étapes mentionnées ci-dessous vous donneront un aperçu du fonctionnement du tri par insertion :
– Dans la première étape, les éléments en question sont comparés avec les éléments adjacents à eux
– Si chaque comparaison montre que l’élément en question peut être utilisé à une position spécifique, alors un espace lui est réservé. Cela se fait en déplaçant la position des autres éléments vers la droite.
– Cette procédure se poursuit jusqu’à ce que chaque élément présent dans le tableau trouve sa place.
Caractéristiques du tri par insertion
Bien que cet algorithme de tri par insertion présente un large éventail de caractéristiques, il en existe trois importantes avec lesquelles chacun doit se familiariser.
- Tout d’abord, l’algorithme de tri par insertion est incroyablement simple. Certains diraient même qu’il s’agit du plus simple en raison de sa mise en œuvre directe.
- Si vous êtes un programmeur qui traite régulièrement de petites valeurs de données, l’utilisation de cet algorithme vous sera très utile.
- La nature de l’algorithme de tri par insertion est assez adaptative, ce qui le rend idéal pour les ensembles de données partiellement triés.
Questions fréquemment posées sur le tri par insertion
Voici une liste de réponses concises aux questions fréquemment posées sur les algorithmes de tri par insertion.
Quels sont les cas limites de l’algorithme de tri par insertion ?
Le tri par insertion nécessite beaucoup de temps lorsqu’il s’agit de trier des éléments qui sont dans un ordre inverse. Cependant, si les éléments sont déjà triés, il ne nécessitera pas beaucoup de temps.
Les algorithmes de tri par insertion sont-ils stables ?
Les algorithmes de tri par insertion sont incroyablement stables, surtout si on les compare à d’autres algorithmes.
Quel est le meilleur moment pour utiliser l’algorithme de tri par insertion ?
Comme indiqué précédemment, le tri par insertion est souvent utilisé lorsque le nombre d’éléments est faible. Cela dit, il peut également s’avérer très utile lorsqu’un tableau d’entrée ne nécessite pas un tri trop important et qu’il ne contient que quelques éléments mal placés.
Quelle est l’approche suivie par le tri par insertion ?
L’approche suivie par l’algorithme de tri par insertion est incrémentielle, c’est pourquoi il est incroyablement populaire parmi les programmeurs qui trient des tableaux.
Le tri par insertion binaire expliqué
Les programmeurs peuvent utiliser la recherche binaire pour réduire le nombre de comparaisons présentes dans le tri par insertion ordinaire. Le tri par insertion binaire utilise la recherche pour trouver l’emplacement idéal pour insérer l’élément choisi à chaque itération. Lorsqu’il s’agit d’insertion régulière, le tri utilise O(i) (à la ième itération) dans le pire des cas.
Nous pouvons utiliser la recherche binaire pour le réduire à ceci : O(logi). Cela dit, l’algorithme a toujours un temps d’exécution d’environ O(n^2) dans le pire des cas. Ceci est dû à la quantité de swaps nécessaires par insertion.
Étapes de l’implémentation du tri par insertion dans les listes chaînées
Les étapes mentionnées ci-dessous montrent comment on peut utiliser l’algorithme de tri par insertion dans une liste chaînée.
- Commencez par créer une liste triée, en vous assurant qu’elle est vide.
- Parcourez la liste que vous avez créée et suivez cette étape pour chaque nœud
- Saisissez le nœud actuel sous forme de résultat ou de liste triée
- Enfin, modifiez la tête de la liste chaînée pour en faire la tête de la liste triée, c’est-à-dire la liste de résultats.
Les principales applications du tri par insertion
- Voici deux des scénarios les plus courants dans lesquels les programmeurs utilisent le tri par insertion.
- Tout d’abord, ils l’utilisent lorsqu’il s’agit d’un tableau contenant quelques éléments.
- Le tri par insertion peut également s’avérer pratique lorsqu’il n’y a qu’un petit nombre d’éléments à trier.
Complexités temporelles du tri par insertion
Voici un aperçu des complexités temporelles que vous pouvez rencontrer dans le tri par insertion.
Complexité dans le pire des cas O (n2)
Imaginez qu’il y a un tableau présent dans un ordre ascendant, que vous voulez trier dans un ordre descendant. Un cas comme celui-ci entraîne une complexité de pire cas. Dans une telle situation, vous devez comparer chaque élément avec d’autres éléments pour qu’il y ait (n-1) comparaisons pour chaque nième élément.
Le nombre total de comparaisons sera de n*(n-1) ~ n2.
Complexité du cas moyen O(n)
Ce type de complexité se produit souvent lorsque les éléments d’un tableau sont mélangés, ce qui signifie qu’ils ne sont ni en ordre décroissant ni en ordre croissant.
Complexité spatiale
La complexité spatiale devient 0(1) chaque fois qu’il y a une implémentation d’une variable supplémentaire.
Complexité dans le meilleur des cas
Lorsqu’un tableau n’a pas besoin d’être trié, le nombre de fois où la boucle externe s’exécute est égal à n. D’autre part, la boucle interne reste inactive et ne s’exécute pas. Cela signifie que le nombre de comparaisons sera de n, ce qui donne une complexité linéaire.
Analyse de la complexité temporelle
On ne peut nier l’efficacité du tri par insertion, mais si l’on fournit un tableau déjà trié au tri par insertion, l’algorithme effectuera encore l’autre pour la boucle. Cela nécessitera n étapes pour trier un tableau des n éléments qui ont déjà été triés au départ, transformant essentiellement la complexité du temps dans le meilleur des cas en une fonction n linéaire.
Un tableau non trié nécessite un élément pour effectuer des comparaisons avec d’autres éléments, ce qui signifie que chaque élément de n est comparé aux n autres éléments. Il serait également utile d’analyser d’autres algorithmes similaires comme le tri rapide, le tri par fusion ou le tri par sélection et d’évaluer leurs complexités respectives.