Implementazioni di algoritmi/Shell sort

Wikibooks, manuali e libri di testo liberi.

Lo Shell sort (o Shellsort) è uno dei più vecchi algoritmi di ordinamento. È stato ideato nel 1959 da Donald L. Shell^[1]. È 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.

[modifica] Concetto base

Lo Shell sort è una estensione dell'w: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.

[modifica] Implementazioni

[modifica] 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;
        }
    }
}

[modifica] 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.

[modifica] Note

[modifica] Altri progetti

• Wikipedia contiene una voce riguardante questo algoritmo

[modifica] Collegamenti esterni

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