Insertion Sort in C, algoritmo di ordinamento insertion sort in C

In questa lezione, esploreremo l’algoritmo di ordinamento insertion sort in linguaggio C.

L’insertion sort, come suggerisce il nome, opera su un principio di inserimento graduale degli elementi nella giusta posizione. È simile al modo in cui una persona ordina le carte in mano: si prende una carta alla volta e la si inserisce nella posizione corretta rispetto alle carte già ordinate.

Una caratteristica importante dell’insertion sort è il suo comportamento “in loco”, il che significa che non richiede memoria aggiuntiva oltre all’array da ordinare. Questo risparmio di memoria può essere un vantaggio significativo in sistemi con risorse limitate.

Tuttavia, nonostante la sua semplicità e la mancanza di overhead di memoria, l’insertion sort non è particolarmente efficiente con grandi insiemi di dati. La sua complessità computazionale è quadratica, il che significa che il tempo di esecuzione aumenta quadraticamente all’aumentare della dimensione dell’input.

L’algoritmo richiede due indici: uno che punti all’elemento da ordinare e l’altro all’elemento immediatamente precedente. Il processo consiste nel confrontare l’elemento corrente con quelli già ordinati e inserirlo nella posizione corretta.

Sviluppo dell’algoritmo Insertion Sort in C

Di seguito ecco l’algoritmo sviluppato in linguaggio C:

#include <stdio.h>

int main() {
    int a[10] = {10, 4, 2, 6, 7, 11, 9, 23, 8, 9};
    int i, j, temp;

    // Stampa l'array originale
    printf("Array originale: ");
    for (i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }

    // Ordinamento con insertion sort
    for (i = 1; i < 10; i++) {
        temp = a[i];
        j = i - 1;
        while (j >= 0 && a[j] > temp) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
    }

    // Stampa l'array ordinato
    printf("\nArray ordinato: ");
    for (i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

Come potete notare l’algoritmo utilizza due indici, i e j, e una variabile temporanea per memorizzare temporaneamente l’elemento durante l’ordinamento.

Prestazioni dell’Insertion Sort in C

L’insertion sort ha prestazioni accettabili per insiemi di dati di piccole dimensioni o già parzialmente ordinati. Tuttavia, con insiemi di dati più grandi, il suo tempo di esecuzione può diventare proibitivo a causa della sua complessità quadratica.

Effettua in media $N^{2}/4$ confronti ed altrettanti spostamenti (mezzi scambi), che possono diventare il doppio nel caso peggiore.

Conclusioni

In questa lezione, abbiamo esaminato l’algoritmo insertion sort in linguaggio C, comprendendone i principi di base e la sua implementazione pratica. Nelle prossime lezioni, esploreremo ulteriori algoritmi di ordinamento e approfondiremo le loro applicazioni e prestazioni. Continuate a seguirmi per ulteriori approfondimenti su argomenti di programmazione e algoritmi. Non esitate a condividere le vostre opinioni e domande nei commenti sottostanti.