Shell sort: differenze tra le versioni

Versione delle 20:06, 22 feb 2015

Versione delle 08:44, 1 mag 2015

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.

Riga 25:

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 quest'ultimo giro in un insertion sort puro e semplice.

Riga 50:

7 9 9 7 7 9

8 2 8 9

</pre>

Ora la sequenza è quasi completamente ordinata. Una volta organizzata su una sola colonna durante l'ultima passata, sono solamente un 6, un 8 ed un 9 che devono essere spostati leggermente per arrivare a destinazione.

Riga 56:

== Analisi ==

La correttezza dell'algoritmo viene dal fatto che durante l'ultima passata (cioè per ''h'' = 1) un normale insertion sort viene eseguito sull'intero array.

Ma, visto che i dati vengono preordinati dalle passate precedenti (''h'' = 3, 7, 31, ...), una manciata di operazioni dell'insertion sort sono sufficienti. Il numero esatto dipende dalla sequenza dei valori ''h'' (noti come sequenze ''h''). La sequenza ''h'' sopracitata è solo una delle molte possibili.

Riga 79:

Una sequenza ''h'' facilmente computabile per lo Shell sort è la [[sequenza di Fibonacci]] (1, 2, 3, 5, 8, 13, 21, ... ) o il suo quadrato (1, 4, 9, 25, 64, ...).

== Bibliografia ==

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

* D.E.Knuth: Sorting and Searching, vol. 3 of The Art of Computer Programming. Addison-Wesley (1973)

Riga 88:

== Collegamenti esterni ==

* [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm Analisi dettagliata dello Shell sort (inglese)]

* [http://www.nist.gov/dads/HTML/shellsort.html Dizionario degil Algoritmi e Strutture Dati: Shellsort (inglese)]

{{Ordinamento}}

Riga 95:

[[Categoria:Algoritmi di ordinamento]]

{{Linkcategorie VdQ|plqualità}}