Tri par insertion en Java

Si vous êtes programmeur, vous devez déjà avoir beaucoup entendu parler du tri. Le tri consiste essentiellement à organiser les éléments par ordre croissant ou décroissant. Il existe de nombreux algorithmes de tri disponibles pour trier les éléments, et chaque algorithme a différentes manières de trier, une complexité différente. Cela dépend donc du scénario spécifique et du nombre d’éléments quant à l’algorithme à utiliser. L'insertion est également l'un des algorithmes de tri couramment utilisés avec une complexité O(n^2) et est effectuée comme si nous triions les cartes à jouer entre nos mains. Dans cette rubrique, nous allons découvrir le tri par insertion en Java.

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

Comment fonctionne le tri par insertion en Java ?

Comprenons le fonctionnement du tri par insertion à l'aide d'un exemple.

Supposons qu'il existe un tableau portant le nom arr contenant les éléments mentionnés ci-dessous :

10 5 8 20 30 2 9 7

Étape n°1 – Le tri par insertion commence par le 2ème élément du tableau, soit 5, en considérant le 1er élément du tableau assorti en lui-même. Maintenant, l'élément 5 est comparé à 10 puisque 5 est inférieur à 10, donc 10 est avancé d'une position et 5 est inséré avant lui.

Maintenant, le tableau résultant est :

5 10 8 20 30 2 9 7

Étape #2 – Maintenant l'élément arr[2], soit 8 est comparé à l'élément arr[1], soit 10. Comme 8 est plus petit que son élément précédent 10, il est décalé d'un un pas en avant par rapport à sa position, puis il est comparé à 5. Puisque 8 est supérieur à 5, il est donc inséré après lui.

Alors le tableau résultant est :

5 8 10 20 30 2 9 7

Étape #3 – Maintenant que l'élément 20 est comparé à 10 puisqu'il est supérieur à 10, il reste à sa position.

5 8 10 20 30 2 9 7

Étape n°4 – L'élément 30 est comparé à 20, et comme il est supérieur à 20, aucune modification ne serait apportée et le tableau reste tel quel. Maintenant, le tableau serait

5 8 10 20 30 2 9 7

Étape #5 – L'élément 2 est comparé à 30, comme il est plus petit que 30, il est décalé d'une position en avant puis il est comparé à 20,10, 8, 5, un par un et tous les éléments sont décalés d'une position en avant et 2 est inséré avant 5.

Le tableau résultant est :

2 5 8 10 20 30 9 7

Étape #6 – L'élément 9 est comparé à 30 car il est inférieur à 30 ; il est comparé à 20, 10 un par un, et l'élément est décalé d'une position en avant, et 9 est inséré avant 10 et après 8.

Le tableau résultant est :

2 5 8 9 10 20 30 7

Étape #7 – L'élément 7 est comparé à 30, et comme il est plus petit que 30, il est comparé à 30, 20, 10, 9, 8, et tous les éléments sont décalés d'une position avancer un par un, et 7 est inséré avant 8.

Le tableau résultant deviendrait :

2 5 7 8 9 10 20 30

De cette manière, tous les éléments du tableau sont triés selon le tri par insertion, démarrant la comparaison avec l'élément précédent.

Exemples d'implémentation du tri par insertion en Java

Le tri par insertion en Java est un algorithme de tri simple adapté à tous les petits ensembles de données.

Code :

public class InsertionSort {
public static void insertionSort(int arr[]) { for (int j = 1; j < arr.length; j++) { int key = arr[j]; int i = j-1;
while ( (i > -1) && ( arr[i] > key ) ) { arr[i+1] = arr[i]; i--; }
arr[i+1] = key;
}
}
static void printArray(int arr[]) { int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i<len; i++)
System.out.print(arr[i] + " " );
System.out.println();
}
public static void main(String args[]){ int[] arr1 = {21,18,15,23,52,12,61};
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
}
}

Sortie :

12 15 18 21 23 52 61

Explication :

• Dans le programme de tri par insertion ci-dessus, la fonction insertionSort() est utilisée pour trier les éléments du tableau d'origine. Le tri commence à partir du deuxième élément puisque le premier élément considère être trié en lui-même. Ainsi, la boucle de « j » commence à partir de l’index 1 du tableau. 'i' est la variable qui garde la trace de l'index juste avant le 'j' afin de comparer la valeur.'
• key' est la variable contenant la valeur de l'élément actuel qui doit être disposé en position triée. La boucle while() est exécutée si la valeur actuelle est inférieure à la valeur la plus à gauche afin que le décalage des éléments puisse être traité, et à la fin, l'insertion de l'élément actuel à la bonne position peut être effectuée. La fonction printArray() est utilisée pour enfin imprimer le tableau trié.

1. Meilleur cas

Dans le tri par insertion, le meilleur des cas serait lorsque tous les éléments du tableau sont déjà triés. Ainsi, lorsqu'un élément est comparé à son élément le plus à gauche, il est toujours plus grand et donc aucun déplacement ni insertion d'éléments ne sera traité. Dans ce cas, la meilleure complexité serait linéaire, c'est-à-dire O(n).

2. Dans le pire des cas

Dans le code de tri par insertion ci-dessus, le pire des cas serait lorsque le tableau est dans l'ordre inverse, donc chaque fois que l'élément est comparé à son élément le plus à gauche, il est toujours plus petit puis comparé à tous les éléments suivants qui prennent le lieu, le déplacement et l'insertion sont effectués. Dans ce cas, la complexité du tri par insertion est O(n^2).

3. Cas moyen

Même dans un cas moyen, le tri par insertion a une complexité O(n^2) dans laquelle certains éléments ne nécessitent pas de déplacement, alors que certains éléments sont décalés de leur position et l'insertion à la bonne position est effectuée.

4. Meilleure utilisation

Le tri par insertion est préférable à utiliser lorsque la taille d'un tableau n'est pas très grande ou que seul un petit nombre d'éléments doit être trié dans lequel presque tous les éléments sont triés et que seules quelques modifications doivent être apportées. Le tri par insertion est l'un des algorithmes les plus rapides pour les tableaux de petite taille, encore plus rapide que le tri rapide. En fait, le tri rapide utilise le tri par insertion lors du tri de ses petites parties du tableau.

Conclusion

L'explication ci-dessus montre clairement le fonctionnement et l'implémentation du tri par insertion en Java. Dans d'autres langages de programmation également, la logique pour effectuer le tri par insertion reste la même, seule la syntaxe change. Avant de mettre en œuvre un algorithme de tri, il est très important de procéder à une analyse du scénario dans lequel le tri doit être effectué, car tous les algorithmes de tri ne conviennent pas à tous les scénarios.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!