CodeGym /Blog Java /France /Tri par insertion en Java
Auteur
Oleksandr Miadelets
Head of Developers Team at CodeGym

Tri par insertion en Java

Publié dans le groupe France
Le tri de tableaux est une des opérations les plus courantes qu'un débutant Java doit savoir faire. Bien que les tableaux ne sont pas toujours le moyen le plus pratique d'organiser les données et qu'ils s'appliquent principalement à de petits nombres, le concept derrière le tri des tableaux a des tonnes d'applications dans les logiciels complexes et la science des données. Dans cet article, nous allons examiner de plus près ce qu'est un algorithme de tri par insertion. Nous avons inclus quelques exemples et problèmes d'entraînement pour t'aider à saisir pleinement le concept.

Qu'est-ce que le tri par insertion ?

Fondamentalement, le tri par insertion algorithmique est ce que les développeurs utilisent pour organiser des chaînes de petits nombres. Il divise toutes les valeurs en deux piles : une triée et une non triée. Un par un, les nombres de la pile « non triée » sont choisis et mis dans le bon ordre.Tri par insertion en Java - 1Examinons de plus près l'entrée et la sortie du tri par insertion :
  • Entrée : un tableau A avec des éléments numériques non triés : A[0,1, n, n-2...].
  • Sortie : un tableau contenant les mêmes nombres, mais tous triés. Celui-ci est généralement appelé B : B[0]B[1]...B[n-1].
Il existe plusieurs façons d'utiliser le tri par insertion. Voici les plus populaires :
  • Tri numérique (ordre croissant) : [1, 2, 3, 4, 5]
  • Tri numérique (ordre décroissant) : [5, 4, 3, 2, 1]
  • Tri alphabétique : [a, b, c, d]
Remarque : si tu as un tableau vide ou un singleton, ceux-ci sont considérés comme triés par défaut.

Comprendre la théorie du tri par insertion

Avant d'explorer le code derrière le tri par insertion, étudions l'algorithme en utilisant un langage non technique. Comme nous allons montrer le code pour le tri dans l'ordre croissant, il est logique d'expliquer l'algorithme étape par étape dans cet article. Étape 1. Itération entre arr[1] et arr[n], où n est une valeur numérique généralement inférieure à 10. Étape 2. Compare l'élément que tu as choisi (la key) au nombre précédent dans la séquence en utilisant la méthode sort(). Étape 3. Si tous les éléments sont plus petits que leurs successeurs, répète la comparaison jusqu'à ce que tu trouves une plus grande valeur. Étape 4. Permute la plus grande valeur une position après la plus petite pour créer une séquence ordonnée. Étape 5. Répète le processus jusqu'à ce que tu obtiennes une chaîne triée de caractères.

Tri des tableaux primitifs

Puisque cet algorithme est une des opérations Java les plus simples, même les débutants complets ne devraient pas avoir trop de mal à le mettre en œuvre. Voici un guide étape par étape pour trier un tableau :

1. Déclarer un tableau pour le tri

Pour commencer, créons une série de valeurs que nous afficherons plus tard à l'aide de Java. Pour utiliser l'insertion par tri, tu dois créer un tableau. Pour cela, utilise int[]

int[] arrayA = {10, 14, 20, 30};

2. Utiliser sort_arr pour implémenter l'algorithme

La méthode sort_arr est l'un des moyens les plus courants de mettre en œuvre le tri par insertion. En pratique, cela ressemblerait à ceci :

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. Créer une boucle et un itérateur

En utilisant une boucle dans l'algorithme de tri par insertion, les développeurs n'ont pas à répéter la logique pour chaque élément. Bien que la création de boucles semble complexe, c'est assez simple. Voici un exemple :

for(int i=0; i< sort_arr.length; ++i){
Maintenant que tu as une boucle fonctionnelle, il est temps de créer un itérateur qui triera tous les éléments dans l'ordre désiré. À partir de maintenant, nous ferons référence à l'itérateur sous le nom « j ».
        int j = i;

4. Créer une « boucle while »

Pour effectuer le tri par insertion, une boucle « while » est essentielle pour créer un nouveau tableau trié. Pour la configurer pour une insertion en ordre croissant, un développeur doit se conformer à deux conditions :
  • La valeur attribuée à j doit être supérieure à 0
  • La valeur attribuée à j-1 doit être supérieure à l'index j
Dès que les deux conditions dans la boucle while sont vraies, la valeur de clé du tableau sera égale à l'index j.

5. Trier le tableau

Après avoir configuré la boucle while, les valeurs j et j-1 sont échangées jusqu'à ce qu'une des conditions (ou les deux) de la boucle while ne soit plus respectée. De même, le tri sera répété pour chaque valeur de la boucle for jusqu'à ce que les conditions de la boucle for ne soient plus respectées. Voici comment le tri par insertion fonctionne dans la pratique :

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

Trier une ArrayList

Bien que la compréhension des mathématiques se cachant derrière le tri par insertion est importante, pour le développement de logiciels dans la vie réelle, tu trieras des ArrayLists bien plus souvent que des séquences dans des tableaux primitifs. Voici un guide étape par étape pour trier une ArrayList :
  1. Crée une nouvelle classe Element pour les objets qui appartiennent à la collection.

    
    public class Element {
        private int id;
    
        public Element(int id) {
            this.id = id;
        }
    

  2. Une collection possède une méthode compareTo(), que nous allons utiliser pour comparer les id de deux éléments.

    
        public int compareTo(Element element) {
            int res = 0;
            if (this.id < element.getId()) {
                res = -1;
            }
            if (this.id > element.getId()) {
                res = 1;
            }
            return res;
        }
    }
    

  3. Applique l'algorithme et crée quelques boucles pour trier les objets dans une ArrayList au lieu de les comparer.

    
    public static void insertionSortArrayList(List<element> list) {
        for (int j = 1; j < list.size(); j++) {
            Element current = list.get(j);
            int i = j-1;
            while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
                list.set(i+1, list.get(i));
                i--;
            }
            list.set(i+1, current);
        }
    }
    

  4. Tu peux également ajouter d'autres éléments à l'ArrayList, comme indiqué ci-dessous :

    
    List<element> list = new ArrayList<>();
    
    // Create elements w/ IDs 0-24
    for (int i = 0; i < 25; i++) {
        list.add(new Element(i));
    }
    
    // To use insertion sort, shuffle the values
    Collections.shuffle(list);
    

  5. Maintenant, il est temps de trier :

    
    // This helps print values before sorting
    list.forEach(e -> System.out.print(e.getId() + ", "));
    
    // Sort the list
    insertionSortArrayList(list);
    
    System.out.println();
    
    // Display a sorted array 
    list.forEach(e -> System.out.print(e.getId() + ", "));
    

  6. Maintenant, comparons l'entrée et la sortie pour nous assurer que nous n'avons pas fait d'erreurs. Voici la comparaison pour la chaîne que nous avons utilisée à titre d'exemple.

    4, 2, 6, 7, 0, 5, 9, 1, 8, 3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Problèmes pratiques de tri par insertion

Maintenant que tu as pris en main cet algorithme de tri, il est temps de mettre tes compétences théoriques et pratiques à l'épreuve. Quiz théorique #1 On te donne un tableau [1, 4, 6, 8] et tu y ajoutes un nouvel élément n = 7. Quel est le nombre de comparaisons que tu devras faire pour obtenir une séquence triée de nombres ? Indique la valeur finale de l'index n dans le tableau. Quiz théorique #2 Lors d'un entretien d'embauche, un chef d'équipe te demande de prouver que le tri par insertion est une méthode inefficace. En prenant une chaîne numérique [0, 3, 6, 8, 9], quel devrait être l'ordre de ta séquence d'entrée pour maximiser le temps d'exécution requis pour le tri ? Problème pratique Trie le tableau [0, 1, 4, 5, 2, 3, 7, 9, 8] en ordre croissant avec l'insertion par tri en Java.

Conclusion

Le plus grand défi dans le tri par insertion est de comprendre comment le processus fonctionne. Une fois que tu as saisi l'essentiel, transformer le modèle en code est une partie de plaisir. Tant que tu t'entraînes et revisites les problèmes pratiques pertinents avec le temps, tu amélioreras rapidement ta vitesse de tri par insertion.
Cet article est également disponible en anglais:
Read the English version of this article to see what insertion sort looks like in Java.
Commentaires
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION