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
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.
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 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).
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).
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.
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.
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!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
