Insertion sort in Java

L’Insertion Sort è un algoritmo di ordinamento semplice e efficace, noto per il suo approccio intuitivo che ricalca il modo in cui le persone solitamente ordinano un mazzo di carte. Questo algoritmo è particolarmente utile per ordinamenti di piccole dimensioni o per dati già parzialmente ordinati.

Come Funziona l’Insertion Sort

Il funzionamento dell’Insertion Sort è basato su un sistema di inserzione progressiva. Dato un array di n elementi, il processo prevede che vengano effettuate n-1 iterazioni. Durante ogni iterazione i, si considera l’elemento i-esimo e si cerca la sua posizione corretta all’interno della porzione già ordinata del vettore, che va da 0 a i-1. Questo avviene attraverso una serie di scambi:

In questo modo, la porzione del vettore da 0 a i risulterà sempre ordinata, fino a quando, dopo n iterazioni, l’intero vettore sarà completamente ordinato.

Implementazione dell’Insertion Sort in Java

Di seguito è riportata l’implementazione dell’algoritmo Insertion Sort in Java:

public void insertionSort(int [] array) {
    for(int i = 1; i < array.length; i++) {
       int x = i;
       int j = i - 1;
       while (j >= 0 && array[j] > array[x]) {
            // Scambiamo l'elemento in posizione x fino a quando non raggiunge
            // la posizione corretta nel sotto-vettore
            int k = array[x];
            array[x] = array[j];
            array[j] = k;
            x = j; // La sua nuova posizione nel sotto-vettore
            j--; // Procediamo al successivo elemento del sotto-vettore
       }
    }
}

Complessità Temporale

La complessità dell’algoritmo è O(n²) nel caso peggiore e medio, mentre nel caso migliore, quando gli elementi sono già ordinati o quasi ordinati, la complessità è O(n). Questo rende l’Insertion Sort un algoritmo efficiente per array di piccole dimensioni o già parzialmente ordinati.

Quando Utilizzare l’Insertion Sort

L’Insertion Sort è consigliato in diverse situazioni, tra cui:

• Nell’ordinamento di piccole liste o array.
• Quando si lavora con dati già parzialmente ordinati.
• In combinazione con altri algoritmi, come il Merge Sort o il Quick Sort, per ottimizzare le prestazioni in caso di piccole sottoliste.

In conclusione, l’Insertion Sort è un algoritmo fondamentale che, sebbene non sia il più efficiente, ha il suo posto nell’arsenale degli algoritmi di ordinamento, specialmente in contesti specifici e applicazioni pratiche.