Shell sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Annullate le modifiche di 58.35.249.196 (discussione), riportata alla versione precedente di Sedlex |
|||
Riga 16:
== 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.
| |||