WayToLearnX » Java » Java Avancé » Tri par insertion en java

Tri par insertion en java

novembre 13, 2018mars 11, 2020 Thomas 2 Commentaires algorithme, insertion, pdf, tri

Nous pouvons créer un programme Java pour trier les éléments d’un tableau à l’aide du tri par insertion. L’insertion n’est utile que pour les petits éléments, car elle nécessite plus de temps pour trier un grand nombre d’éléments. Voici comment le processus fonctionne :

Exemple:

^{Source: Wikipedia.org}

Exemple d’un programme Java pour trier un tableau à l’aide de l’algorithme de tri par insertion.

public class InsertionSortExample {
     
     public static void tri_insertion(int tab[]) 
     {  
          int taille = tab.length;  
        
          for (int i = 1; i < taille; i++)
          { 
               int index = tab[i];  
               int j = i-1;  
            
               while(j >= 0 && tab[j] > index)  
               {
                    tab[j+1] = tab[j];  
                    j--;  
               }  
               tab[j+1] = index; 
        }  
     }
	
     static void displayTab(int[] tab)
     {	    
          for(int i=0; i < tab.length; i++)
          {  
               System.out.print(tab[i] + " ");  
          } 
          System.out.println();
     }
	
     public static void main(String str[])
     {   
          int[] tab = {1,12,4,5,93,21,8,11};  
        
          System.out.println("Avant le tri par insertion");    
          displayTab(tab);
            
          //trie un tableau en utilisant le tri par insertion
          tri_insertion(tab); 
           
          System.out.println("Apres le tri par insertion");  
          displayTab(tab);   
    } 
}

La sortie

Avant le tri par insertion
1 12 4 5 93 21 8 11 

Apres le tri par insertion
1 4 5 8 11 12 21 93

Complexité temporelle: O(n * 2)

Complexité spatial: O(1)

QCM Java – JDK JRE JVM et JITQCM sur Java avec des réponses pour la préparation des entretiens d’embauche, des tests en ligne, aux examens et aux certifications. Ces questions et réponses…Lire plus

QCMs qui pourraient vous intéresser :

2 réflexions sur “Tri par insertion en java”

Noémie
mars 10, 2020 à 11:47 pm
Permalien

Bonsoir, votre programme n’est pas correcte.
Si la première valeur du tableau n’est pas la plus petite valeur, le programme ne marche plus.
Répondre
- Thomas Clavet
  mars 11, 2020 à 12:09 am
  Permalien
  
  Merci pour cette remarque, c’est corrigé 🙂
  Répondre

Exemple d’un programme Java pour trier un tableau à l’aide de l’algorithme de tri par insertion.

Vous pourrez aussi aimer

HashSet | Java

TreeSet | Java

Redéfinition de méthode en Java

2 réflexions sur “Tri par insertion en java”

Laisser un commentaire Annuler la réponse