Implementazioni di algoritmi/Shell sort

Lo Shell sort (o Shellsort) è uno dei più vecchi algoritmi di ordinamento. È stato ideato nel 1959 da Donald L. Shell. È veloce, facile da comprendere e da implementare. Comunque, l'analisi della sua complessità è leggermente più sofisticata. È semplice comprendere in maniera intuitiva il fuzionamento dell'algoritmo, ma è spesso difficile analizzarne il tempo di esecuzione.

Lo Shell sort viene a volte chiamato "Shell-Metzner sort" in onore di Marlene Metzner che ne scrisse una primissima implementazione in FORTRAN. Venne per la prima volta chiamato Shell-Metzner in un articolo su Creative Computing nel 1976, ma Marlene Metzner disse di non volere che l'algoritmo portasse il suo nome.

Concetto base

Lo Shell sort è una estensione dell'insertion sort, tenendo presenti due osservazioni:

1. L'Insertion sort è efficiente se l'input è già abbastanza ordinato.
2. L'Insertion sort è inefficiente, generalmente, in quanto muove i valori di una sola posizione per volta.

Lo Shell sort è simile all'insertion sort, ma funziona spostando i valori di più posizioni per volta man mano che risistema i valori, diminuendo gradualmente la dimensione del passo sino ad arrivare ad uno. Alla fine, lo Shell sort esegue un insertion sort, ma per allora i dati saranno già piuttosto ordinati.

Consideriamo un valore piccolo posizionato inizialmente all'estremità errata di un array dati di lunghezza n. Usando l'insertion sort, ci vorranno circa n confronti e scambi per spostare questo valore lungo tutto l'array fino all'altra estremità. Con lo Shell sort, si muoveranno i valori usando passi di grosse dimensioni, cosicché un valore piccolo andrà velocemente nella sua posizione finale con pochi confronti e scambi.

L'idea dietro lo Shell sort può essere illustrata nel seguente modo:

1. sistema la sequenza dei dati in un array bidimensionale(con un numero h di colonne)
2. ordina i valori presenti all'interno di ciascuna colonna dell'array
3. ripeti dal punto 1 con un diverso numero h (minore del precedente) fino a portare h ad 1

L'effetto finale è che la sequenza dei dati viene parzialmente ordinata. La procedura viene eseguita ripetutamente, ogni volta con un array più piccolo, cioè, con un numero di colonne h più basso. Nell'ultima passata, l'array è composto da una singola colonna(h=1) trasformando di fatto questo ultimo giro in un insertion sort puro e semplice. Ad ogni passata i dati diventano sempre più ordinati, finché, durante l'ultima lo diventano del tutto. Comunque, il numero di operazioni di ordinamento necessarie in ciascuna passata è limitato, a causa dell'ordinamento parziale ottenuto nelle passate precedenti.

Implementazioni

Implementazione in Java

public void ShellSort(int[] data){
   int i,j,k,h,hCnt,tmp;
   int []increments=new int[data.length];
   /* Setta l'array incrementi in base alla relazione 3h+1. Il primo elemento è 1 */
   for(h=1,i=0;h<data.length;i++){
      increments[i]=h;
      h=3*h+1;
   }
   for(i--;i>=0;i--){/* esegue il ciclo per ogni incremento partendo dall'ultimo */
      h=increments[i];
      for(hCnt=h;hCnt<h*2;hCnt++)
         for(j=hCnt;j<data.length;){
            tmp=data[j];/* elemento corrente */
            k=j;
            /* k è un indice fittizio. Serve per puntare alla posizione precedente di h passi da data[k]*/
            while(k-h>=0 && tmp<data[k-h]){
 
               data[k]=data[k-h];
               k-=h;
            }
         /* Abbiamo spostato i precedenti maggiori di data[j] in avanti. Adesso ci  troviamo nella giusta posizione per l'elemento corrente ( tmp ) */
         data[k]=tmp;
         j+=h;/* prossimo valore per il salto corrente */
         }
      }  
   }
}

Utilizzo di una lista di dimensioni

Il seguente programma C ordina un array a dalla posizione 0 fino a n-1. Il numero di colonne usato per organizzare i dati in ciascuna passata è nell'array cols. Quindi, i dati vengono distribuiti in 4,356,424 colonne durante la prima passata e in una sola colonna nell'ultima. È da notare che essenzialmente nulla viene eseguito se il numero di colonne h è maggiore del numero di elementi dati n . Ciascuna colonna viene ordinata usando l'insertion sort. Prima, i dati della seconda riga, cominciando da i = h, vengono portati nella corretta posizione all'interno della loro colonna, poi i dati della terza riga (quando i raggiunge il valore 2h) e così via.

void shellsort (int[] a, int n) {
    int i, j, k, h, v;
    int[] cols= { 4356424, 1355339, 543749, 213331, 84801, 27901,
                    11969, 4711, 1968, 815, 277, 97, 31, 7, 3, 1 };
    for (k=0; k<16; k++) {
        h=cols[k];
        for (i=h; i<n; i++) {
            v=a[i];
            j=i;
            while (j>=h && a[j-h]>v) {
                a[j]=a[j-h];
                j=j-h;
            }
            a[j]=v;
        }
    }
}

Utilizzo dei numeri di Fibonacci

void shellsort (int[] a, int n) {
    int h=1, hh=1;
 
    while(hh<n) {
       // eg, h = 5, hh = 8
       hh=hh+h; // hh = 8 + 5 = 13
       h=hh-h;  // h = 13 - 5 = 8
    }
 
    while(hh > 1) {
        int i, j, v;
        for (i=h; i<n; i++) {
            v=a[i];
            j=i;
            while (j>=h && a[j-h]>v) {
                a[j]=a[j-h];
                j=j-h;
            }
            a[j]=v;
        }
 
        // eg, h = 8, hh = 13
 
        h = hh - h; // h = 13 - 8 = 5
        hh = hh - h; // hh = 13 - 5 = 8
    }
}

I quadrati dei numeri di Fibonacci (1, 4, 9, 25, ...) formano una sequenza ancora migliore. L'implementazione viene lasciata al lettore.

Altri progetti

• Wikipedia

• Wikipedia contiene una voce riguardante questo algoritmo

Collegamenti esterni

• Analisi dettagliata dello Shell sort (inglese)
• Dizionario degil Algoritmi e Strutture Dati: Shellsort (inglese)