L'ordinamento degli array è una delle operazioni più comuni che un principiante di Java dovrebbe sapere come eseguire. Sebbene gli array non siano sempre il modo più conveniente per organizzare i dati e questo si applica principalmente a piccoli numeri, il concetto alla base dell'ordinamento degli array ha tonnellate di applicazioni in software complessi e scienza dei dati. In questo post, daremo un'occhiata più da vicino a cosa sia l'ordinamento di inserzione. Abbiamo incluso alcuni esempi e problemi pratici per aiutarti a comprendere appieno questo concetto.
![Ordinamento per inserzione in Java - 1]()
Diamo un'occhiata più da vicino all'input e all'output dell'ordinamento di inserzione:
Cos'è l'ordinamento per inserzione?
Fondamentalmente, l'ordinamento per inserzione è un algoritmo utilizzato dagli sviluppatori per organizzare stringhe di piccoli numeri. Divide tutti i valori in due pile: una ordinata e una non ordinata. Uno per uno, i numeri nella pila "non ordinati" vengono scelti e messi nel giusto ordine.
Diamo un'occhiata più da vicino all'input e all'output dell'ordinamento di inserzione:
- Input: un array A con elementi numerici non ordinati: A[0,1, n, n-2...].
- Output: un array contenente gli stessi numeri ma completamente ordinato. Questo è tipicamente indicato come B: B[0]B[1]...B[n-1].
- Ordinamento numerico (ordine crescente): [1, 2, 3, 4, 5]
- Ordinamento numerico (ordine decrescente): [5, 4, 3, 2, 1]
- Ordinamento alfabetico: [a, b, c, d]
Comprensione della teoria dell'ordinamento per inserzione
Prima di esplorare il codice alla base dell'ordinamento per inserzione, suddividiamo l'algoritmo utilizzando un linguaggio non tecnico. Poiché mostreremo il codice per l'ordinamento in ordine crescente, ha senso spiegare l'algoritmo passo dopo passo in questo post. Passaggio 1. Iterazione traarr[1]e arr[n]dove nè un valore numerico in genere inferiore a 10. Passaggio 2. Confrontare l'elemento scelto (noto come key) con il numero precedente nella sequenza utilizzando il sort()metodo. Passaggio 3. Se tutti gli elementi sono più piccoli dei loro successori, ripetere il confronto finché non si trova un valore maggiore. Passaggio 4. Scambia un valore più grande di una posizione oltre quello più piccolo per creare una sequenza ordinata. Passo 5. Ripeti il processo finché non ottieni una stringa ordinata di caratteri
Ordinamento di array primitivi
Poiché l'algoritmo è una delle operazioni Java più semplici, anche i principianti assoluti non dovrebbero avere molti problemi a implementarlo. Ecco una guida passo passo per ordinare un array1. Dichiarare un array per l'ordinamento
Per cominciare, creiamo una stringa di valori che in seguito mostreremo utilizzando Java. Per utilizzare l'ordinamento per inserzione, è necessario creare un array. Per questo, usaint[]
int[] arrayA = {10, 14, 20, 30};
2. Utilizzare sort_arr per implementare l'algoritmo
Il metodo sort_arr è uno dei modi più comuni per implementare l'ordinamento per inserzione. In pratica, sembra così:
for(int i=0; i< sort_arr.length; ++i){
int j = i;
3. Creare un ciclo e un iteratore
Utilizzando un ciclo nell'algoritmo di ordinamento per inserzione, gli sviluppatori non devono ripetere la logica per ogni elemento. Sebbene la creazione di loop sembri complessa, è abbastanza semplice: ecco un esempio:
for(int i=0; i< sort_arr.length; ++i){
j".
int j = i;
4. Creazione di un "ciclo while"
Quando si tratta di ordinamento per inserzione, un ciclo "while" è essenziale per un nuovo array ordinato. Per configurarlo per un ordinamento di inserzione in ordine crescente, uno sviluppatore deve rispettare due condizioni:- Il valore assegnato a j deve essere maggiore di 0
- Il valore assegnato a
j-1deve essere maggiorejdell'indice
j.
5. Ordinamento dell'array
Dopo aver impostato il ciclo while, i valorije j-1verranno scambiati finché una o entrambe le condizioni nel ciclo while falliscono. Allo stesso modo, l'ordinamento verrà ripetuto per ogni valore nel ciclo for finché anche le condizioni del ciclo for falliscono. Ecco come funziona in pratica il processo di ordinamento per inserzione:
int key = sort_arr[j];
sort_arr[j] = sort_arr[j-1];
sort_arr[j-1] = key;
j = j-1;
Ordinamento di un ArrayList
Sebbene la comprensione della matematica dietro l'ordinamento per inserzione sia importante, quando si tratta di sviluppo di software nella vita reale, ordinerai gli ArrayList molto più delle sequenze negli array primitivi. Ecco una guida dettagliata per ordinare un ArrayList:- Crea una nuova
Elementclasse per gli elementi che appartengono alla raccolta.public class Element { private int id; public Element(int id) { this.id = id; } - All'interno di una raccolta, c'è un
compareTo()metodo: lo useremo per confrontare gli ID di due elementi.public int compareTo(Element element) { int res = 0; if (this.id < element.getId()) { res = -1; } if (this.id > element.getId()) { res = 1; } return res; } } - Applica l'algoritmo e crea alcuni cicli per ordinare gli oggetti in un
ArrayListinvece di confrontarli.public static void insertionSortArrayList(List<element> list) { for (int j = 1; j < list.size(); j++) { Element current = list.get(j); int i = j-1; while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) { list.set(i+1, list.get(i)); i--; } list.set(i+1, current); } } - Puoi
ArrayListanche aggiungere altri elementi, come mostrato di seguito:List<element> list = new ArrayList<>(); // Create elements w/ IDs 0-24 for (int i = 0; i < 25; i++) { list.add(new Element(i)); } // To use insertion sort, shuffle the values Collections.shuffle(list); - Ora è il momento di ordinare:
// This helps print values before sorting list.forEach(e -> System.out.print(e.getId() + ", ")); // Sort the list insertionSortArrayList(list); System.out.println(); // Display a sorted array list.forEach(e -> System.out.print(e.getId() + ", ")); - Ora confrontiamo l'input e l'output per assicurarci di non aver commesso errori. Ecco il confronto della stringa che abbiamo usato come esempio.
4, 2, 6, 7, 0, 5, 9, 1, 8, 3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
GO TO FULL VERSION