Menu

Ordinamento di inserzione in Java - Algoritmo di ordinamento di inserzione ed esempi

  • Principale
  • Altro
  • Ordinamento di inserzione in Java - Algoritmo di ordinamento di inserzione ed esempi

insertion sort java insertion sort algorithm examples

Prova Il Nostro Strumento Per Eliminare I Problemi

Questo tutorial spiega l'ordinamento di inserimento in Java, inclusi l'algoritmo, lo pseudo-codice e gli esempi di array di ordinamento, elenco collegato singolarmente e doppio:

La tecnica dell'algoritmo di ordinamento di inserimento è simile al Bubble sort ma è leggermente più efficiente. L'ordinamento per inserzione è più fattibile ed efficace quando è coinvolto un piccolo numero di elementi. Quando il set di dati è più grande, sarà necessario più tempo per ordinare i dati.

=> Dai un'occhiata alla guida per principianti di Java qui.

come aprire i file bin in Android

Ordinamento di inserzione in Java

Cosa imparerai:

Introduzione all'ordinamento di inserzione in Java

Nella tecnica di ordinamento per inserimento, assumiamo che il primo elemento nell'elenco sia già ordinato e iniziamo con il secondo elemento. Il secondo elemento viene confrontato con il primo e scambiato se non in ordine. Questo processo viene ripetuto per tutti gli elementi successivi.

In generale, la tecnica di ordinamento Insertion confronta ogni elemento con tutti i suoi elementi precedenti e ordina l'elemento per posizionarlo nella posizione corretta.

Come già accennato, la tecnica di ordinamento per inserimento è più fattibile per un set di dati più piccolo e quindi gli array con un numero ridotto di elementi possono essere ordinati utilizzando in modo efficiente l'ordinamento per inserimento.

L'ordinamento per inserzione è particolarmente utile per ordinare le strutture di dati degli elenchi collegati. Come sai, gli elenchi collegati hanno puntatori che puntano al suo elemento successivo (elenco collegato singolarmente) e all'elemento precedente (elenco collegato doppio). Ciò rende più facile tenere traccia degli elementi precedenti e successivi.

In questo modo è più semplice utilizzare l'ordinamento per inserimento per ordinare gli elenchi collegati. Tuttavia, l'ordinamento richiederà molto tempo se gli elementi di dati sono maggiori.

In questo tutorial, discuteremo la tecnica di ordinamento per inserimento, incluso il suo algoritmo, pseudo-codice ed esempi. Implementeremo anche programmi Java per ordinare un array, un elenco collegato singolarmente e un elenco collegato doppio utilizzando l'ordinamento per inserimento.

Algoritmo di ordinamento degli inserimenti

L'algoritmo di ordinamento per inserzione è il seguente.

Passo 1 : Ripetere i passaggi da 2 a 5 per K = da 1 a N-1

Passo 2 : imposta temp = A (K)

Passaggio 3 : impostare J = K - 1

Passaggio 4 :

Ripeti mentre temp<=A(J)
imposta A (J + 1) = A (J)
impostare J = J - 1
(fine del ciclo interno)

Passaggio 5 :

imposta A (J + 1) = temp
(fine del ciclo)

Passaggio 6 : Uscita

Come sapete, l'ordinamento per inserzione inizia dal secondo elemento assumendo che il primo elemento sia già ordinato. I passaggi precedenti vengono ripetuti per tutti gli elementi nell'elenco a partire dal secondo elemento e inseriti nelle posizioni desiderate.

Pseudocodice per ordinamento a inserzione

Di seguito viene fornito lo pseudo-codice per la tecnica di ordinamento per inserzione.

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

Successivamente, vediamo un'illustrazione che mostra l'ordinamento di un array utilizzando l'ordinamento di inserimento.

Ordinamento di una matrice utilizzando l'ordinamento di inserimento

Prendiamo un esempio di ordinamento per inserimento utilizzando un array.

L'array da ordinare è il seguente:

matrice da ordinare

Ora per ogni passaggio, confrontiamo l'elemento corrente con tutti i suoi elementi precedenti. Quindi, nel primo passaggio, iniziamo con il secondo elemento.

Confronta il 2 ° elemento con il 1 ° elemento

passare 2

passare 3

passare 4

passare 5

passare 6

Pertanto, abbiamo bisogno di N numero di passaggi per ordinare completamente un array contenente N numero di elementi.

app per spiare un altro telefono

L'illustrazione sopra può essere riassunta in forma tabulare come mostrato di seguito:

PassaggioElenco non ordinatoconfrontoElenco ordinato
1{10,2,6,15,4,1}{10.2}{2,10, 6,15,4,1}
Due{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}

Come mostrato nell'illustrazione sopra, alla fine di ogni passaggio, un elemento va nella sua posizione corretta. Quindi in generale, per posizionare N elementi al loro posto, abbiamo bisogno di N-1 passaggi.

Implementazione dell'ordinamento di inserzione in Java

Il seguente programma mostra l'implementazione dell'ordinamento Insertion in Java. Qui, abbiamo un array da ordinare utilizzando l'ordinamento di inserimento.

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)); } }

Produzione:

Array originale: (10, 6, 15, 4, 1, 45)
Array ordinato: (1, 4, 6, 10, 15, 45)

Implementazione dell

Nell'implementazione di cui sopra, si vede che l'ordinamento inizia da 2ndelemento dell'array (variabile di ciclo j = 1) e quindi l'elemento corrente viene confrontato con tutti i suoi elementi precedenti. L'elemento viene quindi posizionato nella posizione corretta.

L'ordinamento per inserzione funziona in modo efficace per array più piccoli e per array parzialmente ordinati in cui l'ordinamento viene completato in meno passaggi.

L'ordinamento di inserzione è un ordinamento stabile, ovvero mantiene l'ordine degli elementi uguali nell'elenco.

Ordinamento di un elenco collegato utilizzando l'ordinamento di inserimento

Il seguente programma Java mostra l'ordinamento di un elenco collegato singolarmente utilizzando l'ordinamento di inserimento.

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

Produzione:

Elenco collegato originale:
1 8 32 2 10
Elenco collegato ordinato:
1 2 8 10 32

output - Elenco collegato

Nel programma sopra, abbiamo definito una classe che crea un elenco collegato e aggiunge nodi ad esso e lo ordina. Poiché l'elenco collegato singolarmente ha un puntatore successivo, è più facile tenere traccia dei nodi durante l'ordinamento dell'elenco.

Ordinamento di un elenco a doppio collegamento utilizzando l'ordinamento di inserimento

Il seguente programma ordina un elenco a doppio collegamento utilizzando l'ordinamento per inserzione. Si noti che poiché l'elenco a doppio collegamento ha puntatori sia precedente che successivo, è facile aggiornare e ricollegare i puntatori durante l'ordinamento dei dati.

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); } }

Produzione:

Lista originale doppiamente collegata:
1 11 2 7 3 5
Elenco ordinato a doppio collegamento:
1 2 3 5 7 11

dichiarare un array di stringhe in java

Output - Elenco doppiamente collegato

Domande frequenti

D # 1) Che cos'è l'ordinamento di inserzione in Java?

Risposta: L'ordinamento per inserzione è una semplice tecnica di ordinamento in Java che è efficiente per un set di dati più piccolo e in posizione. Si presume che il primo elemento sia sempre ordinato e quindi ogni elemento successivo venga confrontato con tutti i suoi elementi precedenti e collocato nella posizione corretta.

Q # 2) Perché l'ordinamento di inserzione è migliore?

Risposta: L'ordinamento per inserzione è più veloce per set di dati più piccoli quando le altre tecniche come l'ordinamento rapido aggiungono overhead tramite chiamate ricorsive. L'ordinamento per inserzione è relativamente più stabile degli altri algoritmi di ordinamento e richiede meno memoria. L'ordinamento per inserzione funziona anche in modo più efficiente quando l'array è quasi ordinato.

Q # 3) A cosa serve l'ordinamento di inserzione?

Risposta: L'ordinamento per inserzione viene utilizzato principalmente nelle applicazioni per computer che creano programmi complessi come la ricerca di file, la ricerca di percorsi e la compressione dei dati.

Q # 4)Qual è l'efficienza di Insertion Sort?

Risposta: L'ordinamento di inserzione ha una prestazione media del caso di O (n ^ 2). Il caso migliore per l'ordinamento per inserzione è quando l'array è già ordinato ed è O (n). Le prestazioni nel caso peggiore per l'ordinamento per inserzione sono ancora O (n ^ 2).

Conclusione

L'ordinamento per inserzione è una semplice tecnica di ordinamento che funziona su array o elenchi collegati. È utile quando il set di dati è più piccolo. Man mano che il set di dati diventa più grande, questa tecnica diventa più lenta e inefficiente.

L'ordinamento di inserimento è anche più stabile e sul posto rispetto alle altre tecniche di ordinamento. Non vi è alcun sovraccarico di memoria poiché non viene utilizzata alcuna struttura separata per la memorizzazione degli elementi ordinati.

L'ordinamento per inserzione funziona bene sull'ordinamento di elenchi collegati che sono sia elenchi collegati singolarmente che doppi. Questo perché l'elenco collegato è costituito da nodi collegati tramite puntatori. Quindi l'ordinamento dei nodi diventa più facile.

Nel nostro prossimo tutorial, discuteremo ancora un'altra tecnica di ordinamento in Java.

=> Leggere attraverso la serie di formazione Easy Java.

Lettura consigliata

^