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:

1. Si inizia considerando il secondo elemento dell'array e lo si confronta con gli elementi precedenti.

2. Si sposta l'elemento corrente verso sinistra finché non si trova un elemento minore o fino a raggiungere l'inizio dell'array.

3. Si inserisce l'elemento corrente nella posizione corretta tra gli elementi ordinati.

4. 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(n²) 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.

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(n²), è 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.