Differenze tra le versioni di "Shell sort"

Inserting SVG image
(Inserting SVG image)
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.
[[File:Shell sorting algorithm color bars.svg|thumb|Shell sort barre di colore algoritmo]]
 
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.
 
17

contributi