shell sort

Lo Shell sort (o Shellsort) è uno dei più vecchi algoritmi di ordinamento. È stato ideato nel 1959 da Donald L. Shell [Sh]. È 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.
Lo Shell sort è una estensione dell'insertion sort, tenendo presenti due osservazioni:
L'Insertion sort è efficiente se l'input è già abbastanza ordinato.
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:
sistema la sequenza dei dati in un array bidimensionale(con un numero h di colonne)
ordina i valori presenti all'interno di ciascuna colonna dell'array
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.

tratto da wikipedia.org