Menu

Tri par insertion en Java - Algorithme de tri par insertion et exemples

  • Principal
  • Autre
  • Tri par insertion en Java - Algorithme de tri par insertion et exemples

insertion sort java insertion sort algorithm examples

Essayez Notre Instrument Pour Éliminer Les Problèmes

Ce didacticiel explique le tri par insertion en Java, y compris son algorithme, son pseudo-code et des exemples de tableaux de tri, liste à liaison unique et double liaison:

La technique de l'algorithme de tri par insertion est similaire au tri par bulles mais est légèrement plus efficace. Le tri par insertion est plus faisable et efficace lorsqu'un petit nombre d'éléments est impliqué. Lorsque l'ensemble de données est plus volumineux, le tri des données prendra plus de temps.

=> Jetez un œil au guide du débutant Java ici.

test unitaire test d'intégration test du système

Tri par insertion en Java

Ce que vous apprendrez:

Introduction au tri par insertion en Java

Dans la technique de tri par insertion, nous supposons que le premier élément de la liste est déjà trié et nous commençons par le deuxième élément. Le deuxième élément est comparé au premier et échangé s'il n'est pas dans l'ordre. Ce processus est répété pour tous les éléments suivants.

En général, la technique de tri par insertion compare chaque élément avec tous ses éléments précédents et trie l'élément pour le placer dans sa bonne position.

Comme déjà mentionné, la technique de tri par insertion est plus faisable pour un plus petit ensemble de données, et ainsi les tableaux avec un petit nombre d'éléments peuvent être triés en utilisant efficacement le tri par insertion.

Le tri par insertion est particulièrement utile pour trier les structures de données de listes liées. Comme vous le savez, les listes liées ont des pointeurs pointant vers son élément suivant (liste liée à un seul lien) et son élément précédent (liste à double lien). Cela facilite le suivi des éléments précédents et suivants.

Ainsi, il est plus facile d'utiliser le tri par insertion pour trier les listes liées. Cependant, le tri prendra beaucoup de temps si les éléments de données sont plus nombreux.

Dans ce didacticiel, nous aborderons la technique de tri par insertion, y compris son algorithme, son pseudo-code et ses exemples. Nous allons également implémenter des programmes Java pour trier un tableau, une liste à liaison unique et une liste à double liaison à l'aide du tri par insertion.

Algorithme de tri par insertion

L'algorithme de tri par insertion est le suivant.

Étape 1 : Répétez les étapes 2 à 5 pour K = 1 à N-1

Étape 2 : set temp = A (K)

Étape 3 : mettre J = K - 1

Étape 4 :

Répéter pendant que temp<=A(J)
définir A (J + 1) = A (J)
définir J = J - 1
(fin de la boucle intérieure)

Étape 5 :

régler A (J + 1) = temp
(fin de boucle)

Étape 6 : sortir

Comme vous le savez, le tri par insertion commence à partir du deuxième élément en supposant que le premier élément est déjà trié. Les étapes ci-dessus sont répétées pour tous les éléments de la liste à partir du deuxième élément et mis dans les positions souhaitées.

Pseudocode pour le tri par insertion

Le pseudo-code de la technique de tri par insertion est donné ci-dessous.

procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element while freePosition > 0 and array(freePosition -1) > insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedure

Ensuite, voyons une illustration qui montre le tri d'un tableau à l'aide du tri par insertion.

Tri d'un tableau à l'aide du tri par insertion

Prenons un exemple de tri par insertion utilisant un tableau.

Le tableau à trier est le suivant:

tableau à trier

Maintenant, pour chaque passage, nous comparons l'élément actuel à tous ses éléments précédents. Donc dans la première passe, nous commençons par le deuxième élément.

Comparer le 2e élément au 1er élément

passer 2

passer 3

passer 4

passer 5

passer 6

Ainsi, nous avons besoin de N nombre de passes pour trier complètement un tableau contenant N nombre d'éléments.

comment utiliser regex en c ++

L'illustration ci-dessus peut être résumée sous forme de tableau comme indiqué ci-dessous:

PasseListe non triéeComparaisonListe triée
1{10,2,6,15,4,1}{10.2}{2,10, 6,15,4,1}
deux{2,10, 6,15,4,1}{2,10, 6}{2,6,10,15,4,1}
3{2,6,10,15,4,1}{2.6, 10.15}{2,6,10,15,4,1}
4{2,6,10,15,4,1}{2.6, 10.15.4}{2,4,6,10,15,1}
5{2,4,6,10,15,1}{2,4,6,10,15,1}{1, 2, 4, 6, 10, 15}
6{}{}{1, 2, 4, 6, 10, 15}

Comme le montre l'illustration ci-dessus, à la fin de chaque passe, un élément se place à sa place. Par conséquent, en général, pour placer N éléments à leur place, nous avons besoin de N-1 passes.

Implémentation du tri par insertion en Java

Le programme suivant montre l'implémentation du tri par insertion en Java. Ici, nous avons un tableau à trier en utilisant le tri par insertion.

import java.util.*; public class Main { public static void main(String() args) { //declare an array and print the original contents int() numArray = {10,6,15,4,1,45}; System.out.println('Original Array:' + Arrays.toString(numArray)); //apply insertion sort algorithm on the array for(int k=1; k=0 && temp <= numArray(j)) { numArray(j+1) = numArray(j); j = j-1; } numArray(j+1) = temp; } //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(numArray)); } }

Production:

Baie d’origine: (10, 6, 15, 4, 1, 45)
Tableau trié: (1, 4, 6, 10, 15, 45)

Implémentation du tri par insertion - Sortie

Dans l'implémentation ci-dessus, on voit que le tri commence à partir du 2ndélément du tableau (variable de boucle j = 1) puis l'élément courant est comparé à tous ses éléments précédents. L'élément est alors placé dans sa position correcte.

Le tri par insertion fonctionne efficacement pour les tableaux plus petits et pour les tableaux partiellement triés où le tri est effectué en moins de passes.

Le tri par insertion est un tri stable, c'est-à-dire qu'il maintient l'ordre des éléments égaux dans la liste.

Tri d'une liste liée à l'aide du tri par insertion

Le programme Java suivant montre le tri d'une liste liée à l'aide du tri par insertion.

import java.util.*; class Linkedlist_sort { node head; node sorted; //define node of a linked list class node { int val; node next; public node(int val) { this.val = val; } } //add a node to the linked list void add(int val) { //allocate a new node node newNode = new node(val); //link new node to list newNode.next = head; //head points to new node head = newNode; } // sort a singly linked list using insertion sort void insertion_Sort(node headref) { // initially, no nodes in sorted list so its set to null sorted = null; node current = headref; // traverse the linked list and add sorted node to sorted list while (current != null) { // Store current.next in next node next = current.next; // current node goes in sorted list Insert_sorted(current); // now next becomes current current = next; } // update head to point to linked list head = sorted; } //insert a new node in sorted list void Insert_sorted(node newNode) { //for head node if (sorted == null || sorted.val >= newNode.val) { newNode.next = sorted; sorted = newNode; } else { node current = sorted; //find the node and then insert while (current.next != null && current.next.val

Production:

Liste liée d'origine:
1 8 32 2 10
Liste liée triée:
1 2 8 10 32

sortie - Liste liée

Dans le programme ci-dessus, nous avons défini une classe qui crée une liste chaînée, y ajoute des nœuds et la trie. Comme la liste liée individuellement a un pointeur suivant, il est plus facile de garder une trace des nœuds lors du tri de la liste.

Tri d'une liste à double liaison à l'aide du tri par insertion

Le programme suivant trie une liste doublement liée à l'aide du tri par insertion. Notez que comme la liste doublement liée a à la fois des pointeurs précédent et suivant, il est facile de mettre à jour et de relier les pointeurs lors du tri des données.

class Main { // doubly linked list node static class Node { int data; Node prev, next; }; // return a new node in DLL static Node getNode(int data){ //create new node Node newNode = new Node(); // assign data to node newNode.data = data; newNode.prev = newNode.next = null; return newNode; } // insert a node in sorted DLL static Node insert_Sorted(Node head_ref, Node newNode) { Node current; //list is empty if (head_ref == null) head_ref = newNode; // node is inserted at the beginning of the DLL else if ((head_ref).data >= newNode.data) { newNode.next = head_ref; newNode.next.prev = newNode; head_ref = newNode; } else { current = head_ref; // find the node after which new node is to be inserted while (current.next != null && current.next.data prev points to new node / if ((head_ref) != null) (head_ref).prev = newNode; // move the head to point to the new node / (head_ref) = newNode; return head_ref; } public static void main(String args()) { // create empty DLL Node head = null; // add nodes to the DLL head=addNode(head, 5); head=addNode(head, 3); head=addNode(head, 7); head=addNode(head, 2); head=addNode(head, 11); head=addNode(head, 1); System.out.println( 'Original doubly linked list:'); print_DLL(head); head=insertion_Sort(head); System.out.println(' Sorted Doubly Linked List:'); print_DLL(head); } }

Production:

Liste d'origine double chaînée:
1 11 2 7 3 5
Liste triée doublement liée:
1 2 3 5 7 11

quels casques vr fonctionnent avec xbox one

Sortie - Liste doublement liée

Questions fréquemment posées

Q # 1) Qu'est-ce que le tri par insertion en Java?

Répondre: Le tri par insertion est une technique de tri simple en Java, efficace pour un ensemble de données plus petit et en place. On suppose que le premier élément est toujours trié, puis chaque élément suivant est comparé à tous ses éléments précédents et placé dans sa bonne position.

Q # 2) Pourquoi le tri par insertion est-il meilleur?

Répondre: Le tri par insertion est plus rapide pour les petits ensembles de données lorsque les autres techniques telles que le tri rapide ajoutent une surcharge via des appels récursifs. Le tri par insertion est comparativement plus stable que les autres algorithmes de tri et nécessite moins de mémoire. Le tri par insertion fonctionne également plus efficacement lorsque le tableau est presque trié.

Q # 3) À quoi sert le tri par insertion?

Répondre: Le tri par insertion est principalement utilisé dans les applications informatiques qui créent des programmes complexes tels que la recherche de fichiers, la recherche de chemins et la compression de données.

Q # 4)Quelle est l'efficacité du tri par insertion?

Répondre: Le tri par insertion a une performance de cas moyenne de O (n ^ 2). Le meilleur cas pour le tri par insertion est lorsque le tableau est déjà trié et qu'il est O (n). Les pires performances pour le tri par insertion sont à nouveau O (n ^ 2).

Conclusion

Le tri par insertion est une technique de tri simple qui fonctionne sur les tableaux ou les listes liées. C'est utile lorsque l'ensemble de données est plus petit. À mesure que l'ensemble de données s'agrandit, cette technique devient plus lente et inefficace.

Le tri par insertion est également plus stable et en place que les autres techniques de tri. Il n'y a pas de surcharge de mémoire car aucune structure distincte n'est utilisée pour stocker les éléments triés.

Le tri par insertion fonctionne bien sur le tri des listes liées qui sont à la fois des listes à liaison simple et double. Cela est dû au fait que la liste liée est composée de nœuds connectés via des pointeurs. Par conséquent, le tri des nœuds devient plus facile.

Dans notre prochain didacticiel, nous aborderons une autre technique de tri en Java.

=> Lisez la série de formations Easy Java.

lecture recommandée

^