Tri par insertion
Le tri par insertion, également généralement appelé tri par insertion directe, est un algorithme efficace pour trier un petit nombre d'éléments.
Le tri par insertion est l'une des méthodes de tri les plus simples. Son idée de base est d'insérer un enregistrement dans une table ordonnée déjà triée, formant ainsi une nouvelle table ordonnée dont le nombre d'enregistrements est augmenté de 1.
Dans son implémentation, une boucle à double couche est utilisée. La boucle externe parcourt tous les éléments sauf le premier, et la boucle interne recherche la position d'insertion dans la table ordonnée avant l'élément courant et effectue le déplacement.

Fonctionnement
L'idée centrale du tri par insertion est de« construire une séquence ordonnée »Il divise logiquement le tableau (ou la liste) à trier en deux parties :
- Partie triéeAu départ, le premier élément du tableau est généralement considéré comme une séquence ordonnée à lui seul.
- Partie non triéeDu deuxième élément au dernier élément.
L'algorithme vainsérer de manière répétée le premier élément de la partie non triée à la position correcte de la partie triée.Jusqu'à ce que la partie non triée devienne vide, le tableau entier devient trié.
Applicabilité
La complexité temporelle moyenne du tri par insertion est égalementO(n^2), et la complexité spatiale est d'ordre constantO(1)La complexité temporelle spécifique est également liée au degré d'ordre du tableau.
Dans le tri par insertion, lorsque le tableau à trier est déjà ordonné, c'est le cas optimal. Il suffit de comparer le nombre actuel avec le nombre précédent, et le nombre total de comparaisons nécessaires à ce moment est deN-1fois, et la complexité temporelle estO(N)Le pire cas est lorsque le tableau à trier est en ordre inverse. À ce moment, le nombre de comparaisons est le plus grand. Le pire cas estO(n^2)。
Diagramme du processus
Supposons que les nombres précédentsn-1(oùn>=2) soient déjà triés. Insérez maintenant lennombre dans la séquence précédemment triée, puis trouvez sa position appropriée, afin que la séquence après l'insertion du n-ième nombre soit également triée.
Le processus consistant à insérer tous les éléments de cette manière jusqu'à ce que la séquence entière soit triée est appelé tri par insertion.
L'ensemble du processus de tri par insertion du plus petit au plus grand est illustré dans la figure :
Première passe :En partant du 6 à la deuxième position, il est plus petit que le 7 devant, donc on échange les positions.

Deuxième passe :Le 9 à la troisième position est plus grand que le 7 à la position précédente, donc aucun échange n'est nécessaire.

Troisième passe :Le 3 à la quatrième position est plus petit que le 9 à la position précédente, donc échangez les positions, et comparez en remontant un par un.

Quatrième passe :Le 1 à la cinquième position est plus petit que le 9 à la position précédente, échangez les positions, puis comparez en remontant un par un.

......
De cette façon, comparez un par un jusqu'au dernier élément.
Exemple de code Java
Téléchargement du paquet de code source :Télécharger
Code partiel :
Code du fichier InsertionSort.java :
/**
* Tri par insertion
*/
public class InsertionSort {
// Code principal --- début
public static void sort(Comparable[] arr){
int n = arr.length;
for (int i = 0; i < n; i++) {
// Trouver la position d'insertion appropriée pour l'élément arr[i]
for( int j = i ; j > 0 ; j -- )
if( arr[j].compareTo( arr[j-1] ) < 0 )
swap( arr, j , j-1 );
else
break;
}
}
// Code principal --- fin
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
int N = 20000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
InsertionSort.sort(arr);
for( int i = 0 ; i < arr.longueur ; i ++ ){
System.out.print(arr[i]);
System.out.print(' ');
}
}
}
Implémentation de l'algorithme et analyse du code
Après avoir compris le principe, examinons l'implémentation concrète du code. Nous fournissons ici des versions dans deux langages courants : Python et Java.
Implémentation Python
Exemple
"""
Implémentation de l'algorithme de tri par insertion (ordre croissant)
:param arr: La liste à trier
:return: La liste triée (modifiée sur place, également renvoyée)
"""
# Parcourir du deuxième élément au dernier élément (indice 1 à n-1)
for i in range(1, len(arr)):
current_value = arr[i] # L'élément actuel à insérer, d'abord « gardé en main »
j = i - 1 # j pointe vers le dernier élément de la séquence triée
# Boucle interne : trouver la position d'insertion pour current_value dans la partie triée arr[0..i-1]
# Condition 1 : j >= 0 garantit qu'on ne sort pas des limites avant le début de la liste
# Condition 2 : arr[j] > current_value signifie que l'élément actuellement comparé est plus grand que celui « gardé » et doit être déplacé vers l'arrière
while j >= 0 and arr[j] > current_value:
arr[j + 1] = arr[j] # Déplacer l'élément plus grand d'une position vers l'arrière pour faire de la place
j -= 1 # Continuer à comparer l'élément suivant vers la gauche
# La boucle se termine, ce qui signifie que la position d'insertion (j+1) est trouvée
# À ce stade, arr[j] <= current_value ou j == -1
arr[j + 1] = current_value # Insérer l'élément "retenu" à la bonne position
return arr
# Code de test
if __name__ == "__main__":
# Données de test
test_data = [64, 34, 25, 12, 22, 11, 90]
print("Avant le tri :", test_data)
sorted_data = insertion_sort(test_data.copy()) # Trier à l'aide d'une copie afin que les données d'origine ne soient pas modifiées
print("Après le tri :", sorted_data)
# Un autre test : données presque triées
nearly_sorted_data = [1, 3, 2, 4, 6, 5, 8, 7]
print("\n"Données presque triées avant le tri :", nearly_sorted_data)
print("Données presque triées après le tri :", insertion_sort(nearly_sorted_data.copy()))
Implémentation Java
Exemple
public static void insertionSort(int[] arr) {
# Parcourir du deuxième élément au dernier élément (indice 1 à n-1)
for (int i = 1; i < arr.longueur; i++) {
int currentValue = arr[i]; # Élément actuel à insérer
int j = i - 1; # j pointe vers le dernier élément de la séquence triée
# Boucle interne : trouver la position d'insertion et déplacer les éléments
while (j >= 0 && arr[j] > currentValue) {
arr[j + 1] = arr[j]; # Décaler l'élément vers la droite
j--;
}
# Insérer l'élément actuel à la bonne position
arr[j + 1] = currentValue;
}
}
# Méthode surchargée, prend en charge le tri d'une partie d'un tableau d'entiers
public static void insertionSort(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int currentValue = arr[i];
int j = i - 1;
while (j >= left && arr[j] > currentValue) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = currentValue;
}
}
public static void main(String[] args) {
# Données de test
int[] testData = {64, 34, 25, 12, 22, 11, 90};
System.out.print("Avant le tri : ");
printArray(testData);
int[] dataToSort = testData.clone(); # Utiliser une copie
insertionSort(dataToSort);
System.out.print("Après tri : ");
printArray(dataToSort);
}
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
Analyse des caractéristiques de l'algorithme
Comprendre les performances et les scénarios d'application d'un algorithme est crucial. Les caractéristiques du tri par insertion peuvent être résumées comme suit :
| Fonctionnalités | Description | Explication |
|---|---|---|
| Complexité temporelle | Cas moyen et pire cas : $O(n^2)$ | Des boucles imbriquées sont nécessaires pour comparer et déplacer des éléments. Pour n éléments, le pire cas (ordre complètement inversé) nécessite environ $\frac{n(n-1)}{2}$ comparaisons et déplacements. |
| Meilleur cas:$O(n)$ | Lorsque le tableau d'entrée est déjà globalement trié, la boucle interne s'exécute rarement ou se termine immédiatement, et seulement n-1 comparaisons sont nécessaires. | |
| Complexité spatiale | $O(1)$ | Ouialgorithme de tri en place, ne nécessitant qu'un espace supplémentaire de niveau constant (tel quecurrent_value, jet d'autres variables). |
| Stabilité | Stable | Lorsque deux éléments sont égaux, leur ordre relatif reste inchangé après le tri. Car l'algorithme ne déplace les éléments que lorsqu'il rencontreune valeur supérieure àla valeur actuelle. |
| Scénarios applicables | 1. Données à petite échelle 2. Les données sont globalement ordonnées 3. Comme sous-programme pour des algorithmes de tri avancés (tels que le tri rapide, le tri fusion) |
Dans ces cas, sa logique simple et son faible surcoût constant peuvent le rendre plus performant que des algorithmes plus complexes $O(n \log n)$. |
Dérivation de la formule de complexité temporelle (pire cas)
Dans le pire des cas (tableau dans l'ordre complètement inversé) :
- Le 1er élément (indice 0) est inséré, comparé 0 fois.
- Le 2e élément (indice 1) est inséré, comparé 1 fois, déplacé 1 fois.
- Le 3e élément (indice 2) est inséré, comparé 2 fois, déplacé 2 fois.
- ...
- Le n-ième élément (indice n-1) est inséré, comparé n-1 fois, déplacé n-1 fois.
Le nombre total de comparaisons et de déplacements est : $0 + 1 + 2 + ... + (n-1) = \frac{n(n-1)}{2}$
Par conséquent, la complexité temporelle est $O(n^2)$.