Ordinamento di inserzione in Java

1. Panoramica

In questo tutorial, discuteremo l'algoritmo di ordinamento di inserzione e daremo uno sguardo alla sua implementazione Java .

L'ordinamento di inserzione è un algoritmo efficiente per ordinare un numero limitato di articoli. Questo metodo si basa sul modo in cui i giocatori di carte ordinano una mano di carte da gioco.

Iniziamo con una mano sinistra vuota e le carte posate sul tavolo. Quindi rimuoviamo una carta alla volta dal tavolo e la inseriamo nella posizione corretta nella mano sinistra. Per trovare la posizione corretta per una nuova carta, la confrontiamo con il set di carte già ordinato nella mano, da destra a sinistra.

Cominciamo con la comprensione dei passaggi dell'algoritmo in forma di pseudocodice.

2. Pseudocodice

Presenteremo il nostro pseudocodice per l'ordinamento per inserzione come una procedura chiamata INSERTION-SORT , prendendo come parametro un array A [1 .. n] di n elementi da ordinare. L'algoritmo ordina la matrice di input sul posto (riorganizzando gli elementi all'interno della matrice A).

Al termine della procedura, l'array di input A contiene una permutazione della sequenza di input ma in ordine ordinato:

INSERTION-SORT(A) for i=2 to A.length key = A[i] j = i - 1 while j > 0 and A[j] > key A[j+1] = A[j] j = j - 1 A[j + 1] = key

Esaminiamo brevemente l'algoritmo sopra.

L'indice i indica la posizione dell'elemento corrente nell'array da elaborare.

Iniziamo dal secondo elemento poiché per definizione un array con un elemento è considerato ordinato. L'elemento all'indice i è chiamato chiave . Una volta ottenuta la chiave, la seconda parte dell'algoritmo si occupa di trovare il suo indice corretto. Se la chiave è inferiore al valore dell'elemento all'indice j , la chiave si sposta di una posizione a sinistra. Il processo continua fino al caso in cui raggiungiamo un elemento più piccolo della chiave.

È importante notare che prima di iniziare l'iterazione per trovare la posizione corretta della chiave all'indice i , l'array A [1 .. j - 1] è già ordinato .

3. Implementazione imperativa

Per il caso imperativo, scriveremo una funzione chiamata insertionSortImperative , prendendo come parametro un array di numeri interi. La funzione inizia l'iterazione sulla matrice dal secondo elemento.

In qualsiasi momento durante l'iterazione, potremmo pensare a questo array come se fosse logicamente diviso in due parti; il lato sinistro è quello ordinato e il lato destro contiene gli elementi non ancora ordinati.

Una nota importante qui è che dopo aver trovato la posizione corretta in cui inseriremo il nuovo elemento, spostiamo (e non scambiamo) gli elementi a destra per liberare uno spazio per esso.

public static void insertionSortImperative(int[] input) { for (int i = 1; i 
    
     = 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; } }
    

Successivamente, creiamo un test per il metodo sopra:

@Test public void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc() { int[] input = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Il test sopra dimostra che l'algoritmo ordina correttamente in ordine crescente l'array di input .

4. Implementazione ricorsiva

La funzione per il caso ricorsivo è chiamata insertionSortR ecursive e accetta come input un array di numeri interi (come per il caso imperativo).

La differenza qui dal caso imperativo (nonostante sia ricorsivo) è che chiama una funzione sovraccaricata con un secondo argomento che è uguale al numero di elementi da ordinare.

Poiché vogliamo ordinare l'array completo, passeremo un numero di elementi uguale alla sua lunghezza:

public static void insertionSortRecursive(int[] input) { insertionSortRecursive(input, input.length); }

Il caso ricorsivo è un po 'più impegnativo. Il caso base si verifica quando tentiamo di ordinare un array con un elemento. In questo caso, non facciamo nulla.

Tutte le successive chiamate ricorsive ordinano una porzione predefinita dell'array di input, a partire dal secondo elemento fino a raggiungere la fine dell'array:

private static void insertionSortRecursive(int[] input, int i) { if (i <= 1) { return; } insertionSortRecursive(input, i - 1); int key = input[i - 1]; int j = i - 2; while (j>= 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; }

E questo è l'aspetto dello stack di chiamate per un array di input di 6 elementi:

insertionSortRecursive(input, 6) insertionSortRecursive(input, 5) and insert the 6th item into the sorted array insertionSortRecursive(input, 4) and insert the 5th item into the sorted array insertionSortRecursive(input, 3) and insert the 4th item into the sorted array insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array insertionSortRecursive(input, 1) and insert the 2nd item into the sorted array

Vediamo anche il test per questo:

@Test public void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc() { int[] input = {6, 4, 5, 2, 3, 1}; InsertionSort.insertionSortRecursive(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Il test sopra dimostra che l'algoritmo ordina correttamente in ordine crescente l'array di input .

5. Complessità temporale e spaziale

Il tempo impiegato dalla procedura INSERTION-SORT per l'esecuzione è O (n ^ 2) . Per ogni nuovo elemento, iteriamo da destra a sinistra sulla parte già ordinata dell'array per trovare la sua posizione corretta. Quindi lo inseriamo spostando gli elementi di una posizione a destra.

L'algoritmo ordina sul posto in modo che la sua complessità spaziale sia O (1) per l'implementazione imperativa e O (n) per l'implementazione ricorsiva.

6. Conclusione

In questo tutorial, abbiamo visto come implementare l'ordinamento per inserzione.

Questo algoritmo è utile per ordinare un piccolo numero di elementi. Diventa inefficiente quando si ordinano sequenze di input con più di 100 elementi.

Tieni presente che, nonostante la sua complessità quadratica, ordina sul posto senza bisogno di spazio ausiliario, come nel caso dell'ordinamento di unione .

L'intero codice può essere trovato su GitHub.