Wikibooks

Implementazioni di algoritmi/Shell sort: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
m Bot: inversione accenti
Riga 15:
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è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:
Riga 23:
 
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è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.
 
== Esempio ==
Estratto da "https://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Shell_sort"