Tri par Insertion
Dernière mise à jour
Le tri par insertion construit le tableau trié un élément à la fois. Il prend le prochain élément non trié (la « clé ») et décale d'une case vers la droite chaque élément plus grand de la région triée, puis place la clé dans l'espace libéré. C'est exactement ainsi que la plupart des gens trient une main de cartes à jouer. Appuyez sur lecture ci-dessus pour voir chaque clé s'insérer, ou parcourez les décalages un par un.
Le tri par insertion est très rapide sur des entrées petites ou presque triées - il s'exécute en O(n) lorsque les données sont déjà triées - c'est pourquoi de nombreux tris hybrides s'y replient pour les petits sous-tableaux.
Complexité en temps et en espace
| Cas | Complexité | Notes |
|---|---|---|
| Meilleur cas | O(n) | Déjà trié |
| Cas moyen | O(n²) | Ordre aléatoire |
| Pire cas | O(n²) | Ordre inverse |
| Espace | O(1) | En place |
| Stable | Oui | Les éléments égaux conservent leur ordre relatif |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Traiter le premier élément comme une région triée de taille un. |
| 2 | Prendre l'élément suivant comme clé. |
| 3 | Décaler d'une case vers la droite chaque élément trié plus grand que la clé. |
| 4 | Insérer la clé dans l'espace ouvert. |
| 5 | Répéter jusqu'à ce que tous les éléments aient été insérés. |
Exemple résolu
Tri de [5, 2, 4, 1] :
| Passe | Tableau | Action |
|---|---|---|
| Début | [5, 2, 4, 1] | 5 est la région triée initiale de taille un. |
| 1 | [2, 5, 4, 1] | Clé 2 : décaler 5 vers la droite, insérer 2 au début. |
| 2 | [2, 4, 5, 1] | Clé 4 : décaler 5 vers la droite, 2 est plus petit donc arrêt, insérer 4. |
| 3 | [1, 2, 4, 5] | Clé 1 : décaler 5, 4, 2 vers la droite, insérer 1 au début. |
| Fin | [1, 2, 4, 5] | Tous les éléments insérés ; le tableau est trié. |
Quand utiliser le tri par insertion
| À utiliser quand | À éviter quand |
|---|---|
Le tableau est petit (environ n < 20). | Le tableau est grand et ordonné aléatoirement. |
Les données sont déjà presque triées, donnant le meilleur cas O(n). | Vous avez besoin d'un pire cas garanti en O(n log n). |
Vous avez besoin d'un tri stable, en place, avec un espace supplémentaire O(1). | Déplacer les éléments coûte cher, car il effectue de nombreux décalages. |
| Les données arrivent progressivement et doivent rester triées en ligne. | L'entrée est triée à l'envers, son pire cas O(n²). |
Code de Insertion Sort
Une implémentation propre et exécutable de Insertion Sort en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Insertion Sort en Python
Python
1def insertion_sort(a):2 for i in range(1, len(a)):3 key = a[i]4 j = i - 15 # Shift larger elements one slot to the right6 while j >= 0 and a[j] > key:7 a[j + 1] = a[j]8 j -= 19 a[j + 1] = key10 return a11
12
13nums = [7, 3, 9, 1, 5, 8, 2]14print("Before:", nums)15insertion_sort(nums)16print("After: ", nums)Code de Insertion Sort en JavaScript
JavaScript
1function insertionSort(a) {2 for (let i = 1; i < a.length; i++) {3 const key = a[i];4 let j = i - 1;5 // Shift larger elements right to open a slot for key6 while (j >= 0 && a[j] > key) {7 a[j + 1] = a[j];8 j--;9 }10 a[j + 1] = key;11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", insertionSort([...data]));Code de Insertion Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void insertionSort(int[] arr) {5 for (int i = 1; i < arr.length; i++) {6 int key = arr[i];7 int j = i - 1;8 // Shift larger elements one slot to the right9 while (j >= 0 && arr[j] > key) {10 arr[j + 1] = arr[j];11 j--;12 }13 arr[j + 1] = key;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {7, 3, 9, 1, 5, 8, 2};19 System.out.println("Before: " + Arrays.toString(arr));20 insertionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}Code de Insertion Sort en C++
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void insertionSort(std::vector<int>& a) {10 for (size_t i = 1; i < a.size(); ++i) {11 int key = a[i];12 int j = static_cast<int>(i) - 1;13 // Shift larger elements one slot to the right14 while (j >= 0 && a[j] > key) {15 a[j + 1] = a[j];16 --j;17 }18 a[j + 1] = key;19 }20}21
22int main() {23 std::vector<int> data = {7, 3, 9, 1, 5, 8, 2};24 std::cout << "Before: ";25 printVec(data);26 insertionSort(data);27 std::cout << "After: ";28 printVec(data);29 return 0;30}Code de Insertion Sort en C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void insertionSort(int a[], int n) {9 for (int i = 1; i < n; i++) {10 int key = a[i];11 int j = i - 1;12 // Shift larger elements one slot to the right13 while (j >= 0 && a[j] > key) {14 a[j + 1] = a[j];15 j--;16 }17 a[j + 1] = key;18 }19}20
21int main(void) {22 int data[] = {7, 3, 9, 1, 5, 8, 2};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 insertionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}FAQ sur le tri par insertion
Quelle est la complexité temporelle du tri par insertion ?
Le tri par insertion est en
O(n²) en moyenne et dans le pire cas, mais en O(n) sur un tableau déjà trié ou presque trié. Il utilise un espace supplémentaire O(1).Le tri par insertion est-il stable ?
Oui. Le tri par insertion ne décale que les éléments strictement supérieurs à la clé, de sorte que les éléments égaux ne se croisent jamais et que leur ordre relatif est préservé.
Quand devrais-je utiliser le tri par insertion ?
Utilisez-le pour de petits tableaux ou des données déjà presque triées. En raison de son faible coût et de son meilleur cas adaptatif, des algorithmes hybrides comme Timsort l'utilisent pour de petites plages.
Quelle est la différence entre le tri par insertion et le tri à bulles ?
Les deux sont des tris par comparaison en
O(n²), mais le tri par insertion décale les éléments pour ouvrir un espace pour la clé, tandis que le tri à bulles échange à répétition des paires adjacentes mal ordonnées. Le tri par insertion effectue généralement moins d'écritures et se comporte mieux en pratique, surtout sur des données presque triées où il atteint son meilleur cas O(n).Pourquoi le tri par insertion est-il plus rapide que le tri fusion sur de petits tableaux ?
Le tri par insertion a un coût constant très faible et n'utilise ni récursion ni allocation supplémentaire, donc sur de petites entrées il bat les tris en
O(n log n) malgré sa pire complexité asymptotique. C'est précisément pourquoi les tris hybrides comme Timsort et introsort basculent vers le tri par insertion pour les petits sous-tableaux.Le tri par insertion fonctionne-t-il mieux avec une liste chaînée ou un tableau ?
Le tri par insertion est normalement écrit pour les tableaux, où le décalage des éléments est le coût principal. Sur une liste chaînée, vous évitez le décalage en insérant le nœud à sa place, mais vous perdez l'accès aléatoire rapide, donc trouver le point d'insertion prend toujours un temps linéaire par élément et le coût total reste
O(n²).Ressources associées
Plus de visualisations
