Introduction au tri par insertion en Java
Si vous êtes programmeur, vous devez avoir déjà entendu parler du tri. Le tri consiste essentiellement à organiser les éléments dans l'ordre croissant ou décroissant. Il y a tellement d'algorithmes de tri disponibles pour trier les éléments et chaque algorithme a différentes façons 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 ayant la complexité de O (n 2) en général et est effectuée comme nous trions les cartes à jouer entre nos mains. Dans cette rubrique, nous allons découvrir le tri par insertion en Java.
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 avec le nom arr ayant les éléments mentionnés ci-dessous:
10 5 8 20 30 2 9 7
Étape # 1 - Le tri par insertion commence par le 2e élément du tableau, c'est-à-dire 5, en considérant le 1er élément du tableau en lui-même. L'élément 5 est maintenant comparé à 10 puisque 5 est inférieur à 10, donc 10 est déplacé de 1 position en avant et 5 est inséré avant.
Maintenant, le tableau résultant est:
5 10 8 20 30 2 9 7
Étape # 2 - Maintenant, l'élément arr (2), c'est-à-dire 8 est comparé à l'élément arr (1), c'est-à-dire 10. Comme 8 est plus petit que son élément précédent 10, il est décalé d'un pas en avant de sa position, puis il est par rapport à 5. Puisque 8 est supérieur à 5, il est donc inséré après.
Ensuite, le tableau résultant est:
5 8 10 20 30 2 9 7
Étape # 3 - Maintenant l'élément 20 est comparé à 10 puisqu'il est supérieur à 10, il reste dans sa position.
5 8 10 20 30 2 9 7
Étape # 4 - L' élément 30 est comparé à 20, et comme il est supérieur à 20, aucune modification ne sera 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, car 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é de 1 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 inférieur à 30, il est comparé à 30, 20, 10, 9, 8 et tous les éléments sont décalés d'une position en avant 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 façon, tous les éléments du tableau sont triés à l'aide du tri par insertion commençant la comparaison avec l'élément précédent.
Exemples pour implémenter le 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.
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 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);
)
)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 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);
)
)
Production:
12 15 18 21 23 52 61
Explication:
Dans le programme ci-dessus de tri par insertion, la fonction insertionSort () est utilisée pour trier les éléments du tableau d'origine. Le tri commence à partir du deuxième élément car 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 gardant la trace de l'indice juste avant le «j» afin de comparer la valeur. » clé 'est la variable contenant la valeur de l'élément courant qui doit être arrangé en position triée. La boucle while () est exécutée si la valeur actuelle est inférieure à la valeur la plus à gauche de sorte que le décalage des éléments peut être traité et à la fin l'insertion de l'élément actuel à la position droite peut être effectuée. La fonction printArray () est utilisée pour finalement imprimer le tableau trié.
1. Meilleur cas
Dans le tri par insertion, le meilleur 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 supérieur et, par conséquent, aucun décalage ni insertion d'éléments ne sera traité. Dans ce cas, la meilleure complexité serait linéaire, c'est-à-dire O (n).
2. Pire cas
Dans le code de tri d'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 qui se produisent et se déplacent. et l'insertion est effectuée. Dans ce cas, la complexité du tri d'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écalage tandis que certains éléments sont décalés de leurs positions 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 seulement un petit nombre d'éléments doit être trié dans lequel presque tous les éléments sont triés et 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, quicksort utilise le tri par insertion lors du tri de ses petites parties du tableau.
Conclusion
L'explication ci-dessus montre clairement le fonctionnement et la mise en œuvre 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 d'implémenter un algorithme de tri, il est très important de faire une analyse du scénario où le tri doit être effectué car tous les algorithmes de tri ne conviennent pas à tous les scénarios.
Articles recommandés
Ceci est un guide pour le tri par insertion en Java. Nous discutons ici comment fonctionne le tri par insertion en java avec des exemples pour implémenter le tri par insertion en Java. Vous pouvez également consulter les articles suivants pour en savoir plus -
- Racine carrée en Java
- BorderLayout en Java
- Numéro inversé en Java
- StringBuffer en Java
- Racine carrée en PHP
- Racine carrée en JavaScript
- Guide des 6 meilleurs algorithmes de tri en Python