Algorithme de tri par insertion dans Java avec exemple de programme

Par : James Hartmann James Hartmann
Hours Le kit de préparation mis à jour

⚡ Résumé intelligent

Tri par insertion dans Java construit une section triée d'un tableau élément par élément, en décalant les valeurs les plus importantes vers la droite jusqu'à ce que chaque clé se retrouve à sa position correcte, ce qui la rend idéale pour les petits ensembles de données.

  • (I.e. Définition: Le tri par insertion retire un élément et l'insère à sa place correcte dans la partie triée.
  • ☑️ Processus: Chaque itération compare la clé avec les valeurs précédentes et décale les plus élevées d'une position vers la droite.
  • ✅ Programme : Le Java L'exemple trie {860, 8, 200, 9} et affiche chaque comparaison et échange.
  • 🧪 Complexité: Le meilleur cas s'exécute en temps O(n), tandis que les cas moyens et les pires atteignent O(n²).
  • ️ Mémoire: Le tri s'effectue sur place, donc l'espace auxiliaire reste à O(1) quelle que soit la taille du tableau.
  • (I.e. Comportement: L'algorithme est stable et adaptatif, de sorte que les tableaux presque triés sont terminés après très peu de décalages.
En savoir plus

Algorithme de tri par insertion dans Java

Qu’est-ce que l’algorithme de tri par insertion ?

Le tri par insertion est un algorithme de tri simple adapté aux petits ensembles de données. Lors de chaque itération, l'algorithme :

  • Supprime un élément d'un tableau.
  • Le compare à la plus grande valeur du tableau.
  • Déplace l'élément à son emplacement correct.

Ce comportement est similaire à la façon dont un joueur de cartes dispose sa main : chaque nouvelle carte est prise et déplacée vers la gauche, au-delà de toutes les cartes plus grandes, jusqu’à trouver sa place. Comme tous les déplacements s’effectuent à l’intérieur du tableau d’origine, le tri par insertion est à la fois sur place et stable.

Il appartient à la même famille de produits adaptés aux débutants. Java routines de tri comme tri à bulles, pourtant, il effectue généralement beaucoup moins d'écritures sur des données déjà partiellement ordonnées.

Processus d'algorithme de tri par insertion

Voici comment fonctionne graphiquement le processus de l’algorithme de tri par insertion :

Animé trace de l'algorithme de tri par insertion réorganisant une liste non triée
Processus d'algorithme de tri par insertion

L'animation répète les mêmes trois étapes. Java Le programme ci-dessous s'exécute. Tableau de simulation traces ces étapes sur le tableau d'exemple {860, 8, 200, 9}, exactement comme le programme les imprime au moment de l'exécution.

Passé Élément clé Des comparaisons ont été effectuées Tableau après le passage
1 8 8 contre 860 8 860 200 9
2 200 200 contre 860 8 200 860 9
3 9 9 contre 860, puis 9 contre 200 8 9 200 860

Remarquez que le passage 3 nécessite deux comparaisons car la clé 9 doit passer devant deux valeurs plus élevées. Le nombre de comparaisons augmente donc en fonction du décalage initial de chaque élément.

Java Exemple de programme pour trier un tableau à l'aide de l'algorithme de tri par insertion :

Le programme ci-dessous trie le tableau {860, 8, 200, 9} et affiche un commentaire continu, permettant de visualiser chaque comparaison et chaque décalage. Enregistrez-le sous le nom suivant : InsertionSortExample.java et compilez-le avec n'importe quelle version de JDK 8 ou ultérieure.

package com.guru99;
 
public class InsertionSortExample {
 
	
    public static void main(String a[])
    {    
        int[] myArray  = {860,8,200,9};  
        
        System.out.println("Before Insertion Sort");  
        
        printArray(myArray);
            
        insertionSort(myArray);//sorting array using insertion sort    
           
        System.out.println("After Insertion Sort");  
        
        printArray(myArray);   
    }    
 public static void insertionSort(int arr[]) 
	{  
        int n = arr.length;  
        
        for (int i = 1; i < n; i++)
        {   System.out.println("Sort Pass Number "+(i));
            int key = arr[i];  
            int j = i-1;  
            
            while ( (j > -1) && ( arr [j] > key ) ) 
            {  
            System.out.println("Comparing "+ key  + " and " + arr [j]); 
                arr [j+1] = arr [j];  
                j--;  
            }  
            arr[j+1] = key; 
            System.out.println("Swapping Elements: New Array After Swap");
            printArray(arr);
        }  
    }
 static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
}

L'exécution de la classe produit le trace est montré ici. Chaque Numéro de tri La ligne marque une itération de la boucle externe, et la ligne imprimée après chaque échange montre le tableau tel qu'il se trouve à ce moment-là.

Code Sortie :

Before Insertion Sort
860 8 200 9 
Sort Pass Number 1
Comparing 8 and 860
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 200 860 9 
Sort Pass Number 3
Comparing 9 and 860
Comparing 9 and 200
Swapping Elements: New Array After Swap
8 9 200 860 
After Insertion Sort
8 9 200 860

ARTICLES LIÉS

Complexité temporelle et spatiale du tri par insertion

Les performances du tri par insertion dépendent fortement du degré d'ordre initial des données d'entrée, ce qui explique pourquoi le meilleur et le pire cas diffèrent d'un ordre de grandeur entier.

Témoignage client condition d'entrée Complexité temporelle
Meilleur Le tableau est déjà trié, donc la boucle while interne ne s'exécute jamais. O (n)
Normale Les éléments arrivent dans un ordre aléatoire O(n²)
pire Le tableau est trié en ordre inverse, donc chaque clé se retrouve en tête. O(n²)

L'utilisation de l'espace est beaucoup plus simple. Seuls les comptoirs i, j, n et key sont créées et le tableau est réorganisé sur place, donc l'espace auxiliaire est O(1) quelle que soit la taille de l'entrée.

Étant donné que la boucle interne s'arrête dès qu'elle rencontre une valeur inférieure, le tri par insertion est qualifié d'adaptatif : plus l'entrée se rapproche de l'ordre trié, plus le temps d'exécution tend vers une valeur linéaire.

Avantages et inconvénients du tri par insertion

Le tri par insertion survit dans les bibliothèques de production malgré son cas de moyenne quadratique, car ses facteurs constants sont minuscules et son comportement est prévisible.

Avantages

  • Simple à écrire et facile à trace à la main, ce qui la rend adaptée à l'enseignement et aux entretiens.
  • Stable, de sorte que les enregistrements qui partagent une clé conservent leur ordre relatif d'origine.
  • Sur place, ne nécessitant que O(1) de mémoire supplémentaire au-delà du tableau d'entrée.
  • Adaptatif, atteignant O(n) sur des données déjà presque triées.
  • En ligne, ce qui signifie qu'il peut trier une liste même lorsque de nouveaux éléments arrivent encore.

Désavantages

  • Le temps d'exécution quadratique sur des entrées aléatoires ou en ordre inverse le rend inadapté aux grands tableaux.
  • Chaque étape de décalage écrit dans le tableau, elle déplace donc plus de données que le tri par sélection.
  • Le tri fusion et le tri rapide le surpassent largement une fois que l'ensemble d'entrée comporte quelques dizaines d'éléments.

Une règle pratique consiste à privilégier le tri par insertion lorsque le tableau est petit, lorsque les données sont presque triées, ou lorsqu'un tri de type diviser pour régner a réduit une partition à une poignée d'éléments.

Tri par insertion vs BubblTri par sélection vs tri par sélection

Ces trois algorithmes sont des tris par comparaison quadratique, mais ils diffèrent par leur stabilité, leur réaction aux entrées ordonnées et le nombre d'écritures qu'ils effectuent.

Critères Tri par insertion Bubble Trier Tri de sélection
Meilleur cas O (n) O(n) avec un indicateur de sortie anticipée O(n²)
Cas moyen et cas le plus défavorable O(n²) O(n²) O(n²)
Espace supplémentaire O (1) O (1) O (1)
Stable Oui Oui Non, dans la version standard du tableau
Politiques Oui Oui, lorsque l'optimisation des indicateurs est utilisée Non
Écrit dans le tableau Beaucoup de changements, peu sur des données ordonnées De nombreux échanges Exactement n-1 échanges

Le tri par sélection est préférable lorsque les écritures sont coûteuses, car il effectue le moins d'échanges. Le tri par insertion l'emporte dans presque tous les autres cas à cette échelle, notamment sur des données partiellement ordonnées, ce qui explique pourquoi les tris de bibliothèque comme celui utilisé par [nom de la bibliothèque/du service] sont privilégiés. commun Java exercices et les composants internes du JDK basculent vers ce mode pour les très petites partitions.

FAQ

Le premier élément à lui seul constitue déjà un sous-tableau trié de longueur un. Commencer à l'indice 1 garantit que la boucle dispose toujours d'un élément à comparer ; la clé à la position i est donc insérée dans le bloc trié situé à sa gauche.

Les assistants IA peuvent commenter une exécution à blanc ligne par ligne, générer des tableaux de test supplémentaires et estimer la complexité asymptotique (notation Big O) à partir du code source. Considérez ces explications comme une aide à l'apprentissage et vérifiez les affirmations concernant la complexité à l'aide d'un manuel avant de les citer.

Oui. Copilote GitHub effectue un tri par insertion standard à partir d'une signature de méthode ou d'un commentaire. RevExaminez vous-même les conditions limites, car les boucles générées utilisent parfois j >= 0 ou j > -1 de manière incohérente avec le code environnant.

Le tri par insertion binaire localise le point d'insertion par une recherche dichotomique au lieu d'un parcours linéaire, réduisant ainsi le nombre de comparaisons par élément de O(n) à O(log n). Le travail de décalage restant inchangé, la complexité temporelle globale demeure O(n²).

Oui. Une version récursive trie les n-1 premiers éléments, puis insère le dernier élément dans ce préfixe trié. Elle a la même complexité temporelle que la version itérative, mais nécessite O(n) d'espace mémoire supplémentaire ; c'est pourquoi la version avec boucle est préférée en pratique.

En partie. L'algorithme de tri rapide à double pivot utilisé pour les types primitifs recourt à un tri par insertion sur les très petites partitions, et TimSort, utilisé pour les objets, trie les séquences courtes par tri binaire par insertion avant de les fusionner.

Les erreurs fréquentes consistent à démarrer la boucle externe à 0, à écrire arr[j] = clé au lieu de arr[j+1] = clé et à omettre la garde j > -1, qui lève une exception ArrayIndexOutOfBoundsException lorsque la clé appartient à la position zéro.

Oui. Remplacez le test « supérieur à » par `compareTo` pour un type `Comparable`, ou par un appel à `Comparator`. La logique de décalage reste inchangée et la stabilité est préservée, ce qui est important lorsque des objets partagent la même clé de tri.

Résumez cet article avec :