|
# Algorithme de tri par insertion
Vue d'ensemble
Le tri par insertion est un algorithme de tri simple qui fonctionne en insérant chaque élément d'un tableau à sa position correcte dans le tableau. Il commence par un tableau trié vide, puis parcourt le tableau d'entrée, en insérant chaque élément à sa position correcte dans le tableau trié. Ce processus est répété jusqu'à ce que l'ensemble du tableau d'entrée soit trié.
Étapes de l'algorithme
Voici l'algorithme étape par étape pour le tri par insertion :
1. Commencez avec un tableau trié vide.
2. Parcourez le tableau d’entrée.
3. Pour chaque élément du tableau d'entrée, insérez-le à sa position correcte dans le tableau trié.
4. Pour insérer un élément, comparez-le avec chaque élément du tableau trié, en commençant par le premier élément.
5. Si l'élément est inférieur à l'élément actuel dans le tableau trié, insérez-le avant l'élément actuel.
6. Si l'élément est supérieur à l'élément actuel dans le tableau trié, continuez la comparaison avec l'élément suivant dans le tableau trié.
7. Répétez les étapes 4 à 6 jusqu'à ce que l'élément ait été inséré dans sa position correcte dans le tableau trié.
8. Répétez les étapes 2 à 7 pour chaque élément du tableau d'entrée.
Exemple
Considérons le tableau d'entrée suivant :
```
[5, 2, 8, 3, 1]
```
Les étapes suivantes montrent comment l'algorithme de tri par insertion trierait ce tableau :
1. Commencez avec un tableau trié vide.
```
[]
```
2. Parcourez le tableau d’entrée.
```
[5]
```
3. Pour chaque élément du tableau d'entrée, insérez-le à sa position correcte dans le tableau trié.
```
[5]
```
4. Pour insérer l'élément 2, comparez-le avec chaque élément du tableau trié, en commençant par le premier élément.
```
[5, 2]
```
5. Puisque 2 est inférieur à 5, insérez-le avant l'élément actuel.
```
[2, 5]
```
6. Parcourez le tableau d’entrée.
```
[2, 5, 8]
```
7. Pour chaque élément du tableau d'entrée, insérez-le à sa position correcte dans le tableau trié.
```
[2, 5, 8]
```
8. Pour insérer l'élément 3, comparez-le avec chaque élément du tableau trié, en commençant par le premier élément.
```
[2, 3, 5, 8]
```
9. Puisque 3 est inférieur à 5, insérez-le avant l'élément actuel.
```
[2, 3, 5, 8]
```
10. Parcourez le tableau d’entrée.
```
[2, 3, 5, 8, 1]
```
11. Pour chaque élément du tableau d'entrée, insérez-le à sa position correcte dans le tableau trié.
```
[1, 2, 3, 5, 8]
```
12. Pour insérer l'élément 1, comparez-le avec chaque élément du tableau trié, en commençant par le premier élément.
```
[1, 2, 3, 5, 8]
```
13. Puisque 1 est inférieur à 2, insérez-le avant l'élément actuel.
```
[1, 2, 3, 5, 8]
```
14. Le tableau trié est maintenant terminé.
```
[1, 2, 3, 5, 8]
```
Complexité temporelle
La complexité temporelle du tri par insertion est O(n^2), où n est la longueur du tableau d'entrée. Cela signifie que le temps d'exécution du tri par insertion augmente quadratiquement à mesure que la taille du tableau d'entrée augmente. Le tri par insertion fonctionne mieux lorsque le tableau d'entrée est déjà presque trié, auquel cas sa complexité temporelle est O(n).
Complexité spatiale
Le tri par insertion nécessite un espace auxiliaire O(1), car il n'a besoin de stocker qu'une seule variable (l'élément actuel en cours d'insertion) en plus du tableau d'entrée.
Avantages et inconvénients
Le tri par insertion présente quelques avantages et inconvénients :
Avantages :
* Simple à mettre en œuvre
* Efficace pour les petits tableaux ou les tableaux presque triés
* Algorithme de tri stable (maintient l'ordre relatif des éléments égaux)
Inconvénients :
* Pas efficace pour les grands tableaux
* Complexité temporelle quadratique (O(n^2))
* Il ne s'agit pas d'un algorithme de tri sur place (nécessite un espace supplémentaire)
Conclusion
Le tri par insertion est un algorithme de tri simple et efficace qui fonctionne bien pour les petits tableaux ou les tableaux presque triés. Sa simplicité et sa stabilité en font un algorithme utile à des fins pédagogiques et pour des applications spécialisées. Cependant, ce n'est pas l'algorithme de tri le plus efficace pour les grands tableaux, où des algorithmes plus efficaces tels que le tri rapide ou le tri par fusion devraient être utilisés.
|
