Ordinamento: Shell Sort

Problema: Data una sequanza di $n$ numeri $A= [a_0,\, \dots\,, a_{n-1}]$, ordinarla in modo crescente.
Soluzione: Iterativa (Shell sort)
Complessità: $O(n^{1.25})$ nel caso peggiore

Insertion sort (si veda [1]) è un metodo tanto più efficiente quanto più ordinati sono gli elementi della sequenza da ordinare. Nella sequenza della figura qui sotto, ad esempio, usando insertion sort l'ultimo elemento è 1 e per raggiungere l'inizio della sequenza si devono spostare di una posizione i sette elementi che lo precedono . Per farlo, però, è necessario un ciclo che effettui 7 iterazioni per scambiare l'1 con tutte le posizioni che lo precedono, un passo alla volta.

Se ci fosse un modo per spostare l'1 (ma vale per qualsiasi altro elemento) per più di una posizione ci vorrebbero meno di 7 iterazioni per portare l'1 all'inizio della sequenza.
Il principio di shell sort è proprio questo. Spostare gli elementi più piccoli di più posizioni verso la parte iniziale della sequenza portando allo stesso tempo gli elementi più grandi nella parte finale. Raggiunto un ordinamento approssimativo da parte degli elementi della sequenza si effettua un normalissimo insertion sort che, a quel punto, non ha un peso gravoso dal punto di vista computazionale. Praticamente è un preordinamento a basso costo computazionale prima dell'insertion sort.

Il funzionamento di shell sort è molto simile a quello di insertion sort. L'unica differenza è che c'è un ciclo esterno in più che diminuisce ad ogni iterazione la variabile gap, che rappresenta il numero di posizioni che un elemento deve saltare quando è minore dell'elemento che lo "precede". Ho usato le virgolette perché Shell sort divide la sequenza principale in sottosequenze di elementi che distano di una numero di posizioni uguale a gap. Quindi l'elemento precedente di un elemento in una sottosequenza potrebbe non coincidere con il suo precedente all'interno della sequenza. All'inizio potrebbe sembrare tutto piuttosto confusionario ma, per fortuna, vedere un esempio concreto corredato da immagini rende le cose molto più semplici.

Data la sequenza vista nell'immagine iniziale, se impostiamo gap = 4, l'algoritmo non confronterà più l'1 con l'8 ma l'1 con il 5, che dista 4 posizioni. Quindi è come se insertion sort stesse lavorando sulla sottosequenza {5, 1} in quel momento. In questo modo, scambiando l'1 e il 5 si otterrà uno spostamento dell'1 di 4 posizioni portandolo verso la parte iniziale della sequenza. Allo stesso tempo il 5 verrà spostato verso la parte finale.
Dividendo quindi la sequenza in sottosequenze di elementi che distano 4 posizioni si ottengono 4 sottosequenze di 2 numeri: {6, 4}, {3, 2}, {7, 8}, {5, 1}.

Eseguendo un normale insertion sort su ogni sottosequenza il risultato è che la sequenza principale diventa {4, 2, 7, 1, 6, 3, 8, 5}. Come si può notare nella immagine sotto, già con un solo passaggio la sequenza ha una minima parvenza di ordinamento, con parecchi elementi piccoli all'inizio ed altrettanti grandi alla fine. Diminuendo gap (ad esempio gap = 2) e ripetendo il procedimento si ottengono le due sottosenquenze di 4 elementi che distano 2 posizioni: {4, 7, 6, 8}, {2, 1, 3, 5}

Eseguendo un normale insertion sort su ogni sottosequenza il risultato è che la sequenza principale diventa

Arrivati a questo punto gap = 1 e l'algoritmo diventa un normale insertion sort che lavora su tutta la sequenza ma adesso il costo computazionale si è ridotto fortemente grazie al preordinamento effettuato nei due passaggi precedenti.

#include <stdio.h>
 
void print_vector(int *m, int n);
void shell_sort(int*, int);
 
int main(int argc, char *argv[], char *envp[])
{
 int a[8] = { 6, 3, 7, 5, 4, 2, 8, 1 };
 int n = sizeof(a) / sizeof(int);
 shell_sort(a, n);
 print_vector(a, n);
 
 return 0;
}
 
void shell_sort(int *a, int n)
{
 // Con register si cerca di evitare accessi inutili alla memoria
 register int gap = 0;
 register int i, j;
 
 // Inizializza gap all'intero maggiore nella serie (1, 4, 13, 40, 121, ...) non più grande di n
 // per i dettagli si veda [4]
 while ((gap = 3 * gap + 1) <= n)
  ;
 
 // Analizza il sottoarray composto da elementi distanti gap tra di loro.
 // Alla fine gap = 1 e diventa un semplice insertion sort.
 // Rispetto ad insertion_sort c'è un ciclo esterno in più che serve a diminuire gap per
 // affinare l'ordinamento.
 // La costante 1 di insertion sort qui naturalmente diventa la variabile gap.
 for (gap /= 3; gap > 0; gap /= 3)
 {
  for (i = gap; i < n; ++i)
  {
   int curr = a[i];
   for (j = i - gap; j >= 0 && a[j] > curr; j -= gap)
   {
    a[j + gap] = a[j];
   }
   a[j + gap] = curr;
  }
 }
}
 
void print_vector(int *m, int n)
{
 for (int i = 0; i < n; ++i)
 {
  printf("%d ", m[i]);
 }
 printf("\n");
}

Riferimenti:
[1] Ordinamento: Insertion Sort
[2] https://www.tutorialspoint.com/data_structures_algorithms/shell_sort_algorithm.htm
[3] Algoritmi in C - Sedgewick
[4] The Art of Computer Programming: Sorting and Searching (Vol. 3) - Knuth
[4] C: A Reference Manual - Harbison, Steele