Ordinamento ShellSort

La funzione che segue è un'algoritmo di Shell Sort per l'ordinamento di un vettore di interi. L'idea di base di questo algoritmo, inventato da D. L. Shell nel 1959, consiste nel confrontare  innanzitutto elementi del vettore molto distanti fra loro, contrariamente a quanto avviene negli algoritmi di ordinamento tradizionali, dove i confronti avvengono tra elementi adiacenti. L'approccio di Shell consente di eliminare velocemente la maggior parte delle condizioni  disordine, in modo che, all'aumentare delle iterazioni, il lavoro da svolgere diminuisca. La distanza fra gli elementi messi a confronto viene gradualmente decrementata di un'unità, fino a che le operazioni di ordinamento non diventano degli scambi fra elementi adiacenti.

----------------------------------------------------------------------------------------------------------------------
/* shellsort: ordina v[0].....v[n-1] in ordine crescente */
void shellsort (int v[], int n )
{
     int gap, i , j, temp;

    for (gap = n/2;  gap>0;  gap /= 2)
           for (i = gap;  i < n;  i++)
                  for (j = i - gap;  j >= 0 && v[j] > v[j+gap]; j -= gap)
                 {
                        temp =  v[j];
                        v[j] =  v[j + gap];
                        v[j + gap] = temp;
                }
}
----------------------------------------------------------------------------------------------------------------

In questa funzione troviamo tre cicli innestati. Il ciclo più esterno controlla la distanza tra i due elementi di volta in volta a confronto, inizializzandola a n/2 e decrementandola di un fattore due fino a che essa non diventa nulla. Il ciclo intermedio scandisce tutti gli elementi. Il ciclo più interno, infine, confronta ogni coppia di elementi separati da gap  posizioni e, se tali elementi sono disordinati, li inverte. Poichè, dopo un certo numero di iterazioni, gap varrà sicuramente uno, tutti gli elementi, al termine dell'algoritmo, risulteranno ordinati correttamente. Notate come la generalità del  for consenta al ciclo più esterno, che non è una progressione aritmetica, di adattarsi comunque alla sintassi di questo costrutto.