Introduzione all'ordinamento per inserzione in Java
Se sei un programmatore, devi aver già sentito parlare molto dell'ordinamento. L'ordinamento consiste essenzialmente nel disporre gli elementi in ordine crescente o decrescente. Ci sono così tanti algoritmi di ordinamento disponibili per ordinare gli elementi e ogni algoritmo ha modi diversi per ordinare, complessità diversa. Quindi dipende dallo scenario specifico e dal numero di elementi su quale algoritmo dovrebbe essere usato. L'inserimento è anche uno degli algoritmi di ordinamento comunemente usati con la complessità di O (n 2) in generale e viene eseguito come se ordinassimo le carte da gioco nelle nostre mani. In questo argomento, impareremo l'ordinamento per inserzione in Java.
Come funziona l'ordinamento per inserzione in Java?
Comprendiamo il funzionamento dell'ordinamento per inserzione usando un esempio. Supponiamo che esista un array con il nome arr con gli elementi di seguito indicati:
10 5 8 20 30 2 9 7
Step # 1 - L'ordinamento di inserzione inizia con il 2 ° elemento dell'array, ovvero 5, considerando il 1 ° elemento dell'array assortito in sé. Ora l'elemento 5 viene confrontato con 10 poiché 5 è inferiore a 10, quindi 10 viene spostato 1 posizione in avanti e 5 viene inserito prima di esso.
Ora l'array risultante è:
5 10 8 20 30 2 9 7
Step # 2 - Ora l'elemento arr (2), ovvero 8 viene confrontato con l'elemento arr (1), ovvero 10. Poiché 8 è più piccolo del suo precedente elemento 10, viene spostato di un passo avanti rispetto alla sua posizione e quindi è rispetto a 5. Poiché 8 è maggiore di 5, quindi viene inserito dopo di esso.
Quindi l'array risultante è:
5 8 10 20 30 2 9 7
Step # 3 - Ora l'elemento 20 viene confrontato con 10 poiché è maggiore di 10, rimane nella sua posizione.
5 8 10 20 30 2 9 7
Passaggio n. 4: l' elemento 30 viene confrontato con 20 e poiché è maggiore di 20, non verranno apportate modifiche e l'array rimarrà così com'è. Ora la matrice sarebbe
5 8 10 20 30 2 9 7
Step # 5 - L' elemento 2 viene confrontato con 30, poiché è inferiore a 30, viene spostato di una posizione in avanti, quindi viene confrontato con 20, 10, 8, 5, uno per uno e tutti gli elementi vengono spostati in 1 posizione in avanti e 2 è inserito prima di 5.
La matrice risultante è:
2 5 8 10 20 30 9 7
Step # 6 - L' elemento 9 viene confrontato con 30 poiché è inferiore a 30, viene confrontato con 20, 10 uno per uno e l'elemento viene spostato di 1 posizione in avanti e 9 viene inserito prima di 10 e dopo 8. L'array risultante è:
2 5 8 9 10 20 30 7
Step # 7 - L' elemento 7 viene confrontato con 30 e poiché è inferiore a 30, viene confrontato con 30, 20, 10, 9, 8 e tutti gli elementi vengono spostati di 1 posizione avanti uno per uno e 7 viene inserito prima di 8 La matrice risultante diventerebbe:
2 5 7 8 9 10 20 30
In questo modo, tutti gli elementi dell'array vengono ordinati utilizzando l'ordinamento di inserimento iniziando il confronto con l'elemento precedente.
Esempi per implementare l'ordinamento per inserzione in Java
Insertion Sort in Java è un semplice algoritmo di ordinamento adatto a tutti i piccoli set di dati.
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);
)
)
Produzione:
12 15 18 21 23 52 61
Spiegazione:
Nel precedente programma Insertion Sort, la funzione insertionSort () viene utilizzata per ordinare gli elementi dell'array originale. L'ordinamento inizia dal secondo elemento poiché il primo elemento considera ordinato in sé. Quindi il ciclo di 'j' inizia dall'indice 1 dell'array. 'i' è la variabile che tiene traccia dell'indice appena prima di 'j' per confrontare il valore. ' chiave "è la variabile che contiene il valore dell'elemento corrente che deve essere disposto in posizione ordinata. mentre il ciclo () viene eseguito se il valore corrente è inferiore al valore più a sinistra in modo che sia possibile elaborare lo spostamento degli elementi e al termine l'inserimento dell'elemento corrente nella posizione corretta. La funzione printArray () viene utilizzata per stampare finalmente l'array ordinato.
1. Caso migliore
Nell'ordinamento per inserzione, il caso migliore sarebbe quando tutti gli elementi dell'array sono già ordinati. Quindi, quando un elemento viene confrontato con il suo elemento più a sinistra, è sempre maggiore e quindi non verranno elaborati spostamenti o inserimenti di elementi. In questo caso, la complessità del caso migliore sarebbe lineare, ovvero O (n).
2. Caso peggiore
Nel codice di ordinamento di inserimento sopra riportato, il caso peggiore sarebbe quando l'array è in ordine inverso, quindi ogni volta che l'elemento viene confrontato con l'elemento più a sinistra, è sempre più piccolo e quindi confrontato con tutti gli elementi che avvengono e si spostano e l'inserimento è fatto. In questo caso, la complessità dell'ordinamento per inserzione è O (n 2).
3. Caso medio
Anche in un caso medio, l'ordinamento per inserzione ha una complessità O (n 2) in cui alcuni elementi non richiedono spostamento mentre alcuni elementi vengono spostati dalle loro posizioni e viene eseguito l'inserimento nella posizione corretta.
4. Migliore utilizzo
L'ordinamento per inserzione è meglio usare quando la dimensione di un array non è molto grande o solo un piccolo numero di elementi deve essere ordinato in cui sono ordinati quasi tutti gli elementi e solo alcune modifiche devono essere fatte. L'ordinamento per inserzione è uno degli algoritmi più veloci per array di piccole dimensioni anche più veloce dell'ordinamento rapido. In effetti, quicksort utilizza l'ordinamento Insertion quando ordina le sue piccole parti dell'array.
Conclusione
La spiegazione sopra mostra chiaramente il funzionamento e l'implementazione di Insertion Sort in Java. Anche in altri linguaggi di programmazione, la logica per eseguire l'ordinamento Insertion rimane invariata solo le modifiche alla Sintassi. Prima di implementare qualsiasi algoritmo di ordinamento, è molto importante eseguire alcune analisi dello scenario in cui è necessario eseguire l'ordinamento poiché non tutti gli algoritmi di ordinamento si adattano a tutti gli scenari.
Articoli consigliati
Questa è una guida per Insertion Sort in Java. Qui discutiamo di come funziona l'ordinamento di inserzione in Java con esempi per implementare l'ordinamento di inserzione in Java. Puoi anche dare un'occhiata ai seguenti articoli per saperne di più -
- Radice quadrata in Java
- BorderLayout in Java
- Numero inverso in Java
- StringBuffer in Java
- Radice quadrata in PHP
- Radice quadrata in JavaScript
- Guida ai primi 6 algoritmi di ordinamento in Python