L’Algoritmo che vedremo oggi è lo ShellSort. Un algoritmo di ordinamento molto più efficiente rispetto agli altri algoritmi di inserimento diretti quali SelectionSort, InsertionSort, BubbleSort, LeadSort, ShakeSort già visti e trattati su questo sito.

Lo ShellSort ha complessità computazionale media di: Omega(pn^(1+1/p)).

Il linguaggio usato per la sua implementazione al solito è il C, la funzione corrente è scritta per effettuare l’ordinamento di un array:

void Shellsort(int a[], int n){
int i, j, gap;
 
for(gap = n/2; gap > 0; gap /=2)
    for(i = gap; i < n; i++)
        for(j = i - gap; j >= 0 && a[j] > a[j+gap]; j -= gap)
             Scambia(&a[j],&a[j+gap]);
 
}

Per utilizzare la funzione nel vostro programma basta incollarla sopra la funzione principale main() (ricordatevi di incollare anche la funzione Scambia, che altro non è che una funzione che tramite una variabile d’appoggio scambia il valore di due variabili o due elementi di array dati in input ad essa). Per richiamare la funzione nel vostro programma, all’interno del main scrivete: Shellsort(array, n);

Per capire meglio il funzionamento di questo algoritmo potete dare un’occhiata a questo video: