Ordinamento per inserzione in Java

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.

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].

Esistono diversi modi per utilizzare l'ordinamento per inserzione: ecco i più popolari:

• Ordinamento numerico (ordine crescente): [1, 2, 3, 4, 5]
• Ordinamento numerico (ordine decrescente): [5, 4, 3, 2, 1]
• Ordinamento alfabetico: [a, b, c, d]

Nota: se hai un array vuoto o un singleton, questi sono considerati ordinati per impostazione predefinita.

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 tra arr[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 array

1. 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){

Ora che hai un ciclo funzionante, è il momento di creare un iteratore che ordinerà tutti gli elementi nell'ordine desiderato. D'ora in poi, ci riferiremo all'iteratore come " 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 maggiore jdell'indice

Non appena entrambe le condizioni nel ciclo while sono vere, il valore della chiave dell'array sarà uguale all'indice j.

5. Ordinamento dell'array

Dopo aver impostato il ciclo while, i valori je 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:

1. Crea una nuova Elementclasse per gli elementi che appartengono alla raccolta.

   
   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }
   

2. 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;
       }
   }
   

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

4. 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);
   

5. 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() + ", "));
   

6. 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,
   

Problemi pratici di ordinamento per inserzione

Ora che conosci questo algoritmo di ordinamento, è il momento di mettere alla prova le tue abilità teoriche e pratiche. Quiz di teoria n. 1 Ti viene dato un array [1, 4, 6, 8] e stai aggiungendo un nuovo elemento n = 7 ad esso. Qual è il numero di confronti necessari per ottenere una sequenza ordinata di numeri? Indicare il valore finale dell'indice n nell'array. Quiz di teoria n. 2 Durante un colloquio di lavoro, un responsabile del team ti chiede di dimostrare che l'inserimento ordinato è un metodo inefficiente. Data una stringa numerica di [0, 3, 6, 8, 9], quale dovrebbe essere l'ordine della sequenza di input per massimizzare il tempo di esecuzione richiesto per l'ordinamento? Esercizio pratico Ordina l'array [0, 1, 4, 5, 2, 3, 7, 9, 8] in ordine crescente utilizzando l'ordinamento per inserzione per Java.

Conclusione

La sfida più grande nel comprendere l'ordinamento per inserzione è capire come funziona il processo. Una volta capito, trasformare il modello in codice è un gioco da ragazzi. Finché ti eserciterai e rivisiterai i problemi pratici rilevanti nel tempo, migliorerai rapidamente la velocità di smistamento degli inserimenti.