# Implementazioni di algoritmi/Shell sort

Implementazioni di algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaImplementazioni di algoritmi/Copertina
* Algoritmo di EuclideImplementazioni di algoritmi/Algoritmo di Euclide
* Elevazione a potenzaImplementazioni di algoritmi/Elevazione a potenza
* Prodotto scalareImplementazioni di algoritmi/Prodotto scalare
* Calcolo della PasquaImplementazioni di algoritmi/Calcolo della Pasqua
* Metodo Monte CarloImplementazioni di algoritmi/Metodo Monte Carlo
* Ricerca
** Ricerca dicotomicaImplementazioni di algoritmi/Ricerca dicotomica
* Numeri primi
** Crivello di EratosteneImplementazioni di algoritmi/Crivello di Eratostene
** Test di primalità
*** Test deterministicoImplementazioni di algoritmi/Test deterministico
*** Test di Miller-RabinImplementazioni di algoritmi/Test di Miller-Rabin
* PRNG
** Mersenne TwisterImplementazioni di algoritmi/Mersenne Twister
** Test Chi QuadratoImplementazioni di algoritmi/Test Chi Quadrato
* Crittografia
** RSAImplementazioni di algoritmi/RSA
** TEAImplementazioni di algoritmi/TEA
* π(Metodi per definire il pi greco)
** Pi grecoImplementazioni di algoritmi/Pi greco
* Algoritmi di ordinamento
** Bubble sortImplementazioni di algoritmi/Bubble sort
** Bucket sortImplementazioni di algoritmi/Bucket sort
** Counting sortImplementazioni di algoritmi/Counting sort
** Gnome sortImplementazioni di algoritmi/Gnome sort
** Insertion sortImplementazioni di algoritmi/Insertion sort
** Merge sortImplementazioni di algoritmi/Merge sort
** QuicksortImplementazioni di algoritmi/Quicksort
** Radix sortImplementazioni di algoritmi/Radix sort
** Selection sortImplementazioni di algoritmi/Selection sort
** Shaker sortImplementazioni di algoritmi/Shaker sort
** Shell sortImplementazioni di algoritmi/Shell sort
Modifica il sommario
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 funzionamento 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:
* 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.

## Implementazioni
### 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.

### Utilizzo dei numeri di Fibonacci

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

## Note

* ↑ D.L. Shell: A high-speed sorting procedure. Communications of the ACM 2 (7), 30-32 (1959)

## Altri progetti

Altri progetti
* Wikipedia
* Wikipedia contiene una voce su questo algoritmo

## Collegamenti esterni

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