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.
