Insertion Sort

1. Cos'è l'Insertion Sort?

L'Insertion Sort (ordinamento per inserimento) è un algoritmo elementare che ricalca il metodo intuitivo utilizzato comunemente per ordinare le carte da gioco in mano: si esamina un elemento alla volta e lo si inserisce nella posizione corretta all'interno della sotto-sequenza precedente che risulta già ordinata.

Ad ogni iterazione, l'elemento corrente (chiamato chiave) viene confrontato a ritroso con gli elementi precedenti, spostando questi ultimi verso destra finché non si trova la collocazione adeguata per la chiave.

2. Meccanismo di Funzionamento e Codice C++

L'algoritmo parte considerando il primo elemento del vettore come una sotto-sequenza iniziale già ordinata di lunghezza 1. Successivamente, scorre dal secondo elemento ($i = 1$) fino alla fine.

                // Implementazione dell'Insertion Sort in C++
                #include <vector>
                #include <algorithm>
                #include <iostream>

                void insertionSort(std::vector<int>& v) {
                int n = v.size();

                for (int i = 1; i < n; i++)
                {
                int key = v[i];
                int j = i - 1;

                // Sposta gli elementi maggiori di key verso destra
                while (j >= 0 && v[j] > key) {
                v[j + 1] = v[j];
                j--;
                }
                v[j + 1] = key;
                }
                }
            

3. Analisi della Complessità

Complessità Temporale nel Caso Migliore $\mathcal{O}(N)$: Si verifica quando il vettore di partenza è già ordinato. Il ciclo interno non esegue mai spostamenti e l'algoritmo scorre l'array con un solo passaggio lineare.
Complessità Temporale nel Caso Peggiore $\mathcal{O}(N^2)$: Si verifica quando il vettore è ordinato al contrario, richiedendo il massimo numero di spostamenti e confronti.
Complessità Spaziale $\mathcal{O}(1)$: L'ordinamento avviene in-place senza necessità di strutture dati ausiliarie.

4. Simulatore Interattivo: Esecuzione Insertion Sort

Inserisci una sequenza di numeri interi separati da virgola per testare l'ordinamento per inserimento e verificare i passaggi eseguiti.

insertion-sort@nexus-core:~# Insertion Sort Simulator

Vettore Numerico (separato da virgole):

> Configura il vettore numerico per avviare la simulazione interattiva dell'Insertion Sort.

1. Cos'è l'Insertion Sort?

2. Meccanismo di Funzionamento e Codice C++

3. Analisi della Complessità

4. Simulatore Interattivo: Esecuzione Insertion Sort

Gestione della Privacy e dei Cookie