Algoritmo di ordinamento Insertion sort in JavaScript
Insertion Sort è un semplice algoritmo di ordinamento che costruisce una lista ordinata uno alla volta, inserendo ogni elemento nella posizione corretta. Questo metodo è efficiente per piccoli dataset o per array quasi ordinati. Esploriamo in dettaglio il funzionamento e l'implementazione di Insertion Sort in JavaScript.
L'idea di base di Insertion Sort è simile all'ordinamento di carte da gioco in mano: si prende un elemento alla volta e lo si inserisce nel posto corretto tra gli elementi già ordinati.
Il processo di ordinamento coinvolge i seguenti passaggi:
- Si inizia considerando il secondo elemento dell'array e lo si confronta con gli elementi precedenti.
- Si sposta l'elemento corrente verso sinistra finché non si trova un elemento minore o fino a raggiungere l'inizio dell'array.
- Si inserisce l'elemento corrente nella posizione corretta tra gli elementi ordinati.
- Si ripete questo processo per ogni elemento nell'array, costruendo gradualmente una sezione ordinata all'inizio dell'array.
Fonte gif: Wikipedia
Implementazione di Insertion Sort in JavaScript
Ecco un'implementazione di base di Insertion Sort in JavaScript:
function insertionSort(arr) {
const len = arr.length;
for (let i = 1; i < len; i++) {
let current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
Questo codice definisce una funzione insertionSort che accetta un array come argomento e lo ordina utilizzando l'algoritmo Insertion Sort.
let array = [64, 34, 25, 12, 22, 11, 90];
console.log(insertionSort(array)); // Output: [11, 12, 22, 25, 34, 64, 90]
Complessità Temporale di Insertion Sort
L'Insertion Sort ha una complessità temporale di O(n2) nel caso peggiore e nel caso medio, rendendolo meno efficiente rispetto ad altri algoritmi come Merge Sort o Quick Sort su dataset di grandi dimensioni. Tuttavia, è efficiente su piccoli dataset o quando l'array è già quasi ordinato.
Insertion Sort è utile in situazioni in cui si lavora con piccoli dataset o dataset parzialmente ordinati. È un buon algoritmo per ordinare un numero limitato di elementi o in situazioni in cui l'array è già parzialmente ordinato.
Conclusione
Insertion Sort è un algoritmo intuitivo e semplice che può essere facilmente implementato in JavaScript per ordinare un array. Sebbene non sia ottimale per grandi dataset a causa della sua complessità O(n2), è una buona scelta per situazioni in cui la quantità di dati è limitata o parzialmente ordinata. Comprendere l'Insertion Sort offre una base solida per esplorare concetti più complessi di algoritmi di ordinamento.