Shell sort: differenze tra le versioni

Versione delle 20:30, 19 mar 2008

Versione delle 00:49, 9 mar 2009

Riga 1:

Lo '''Shell sort''' (o '''Shellsort''') è uno dei più vecchi [[Algoritmo di ordinamento|algoritmi di ordinamento]]. È stato ideato nel 1959 da [[D. L. Shell|Donald L. Shell]] <nowiki>[</nowiki>[[#References|Sh]]<nowiki>]</nowiki>.

È veloce, facile da comprendere e da implementare.

Comunque, l'analisi della sua complessità è leggermente più sofisticata.

Riga 7:

== Concetto base ==

Lo Shell sort è una estensione dell'[[insertion sort]], tenendo presenti due osservazioni:

#L'Insertion sort è efficiente se l'input è già abbastanza ordinato.

Line 26 ⟶ 25:

== Esempio ==

Poniamo che

<pre>

Line 50 ⟶ 48:

== 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.

([[Vaughan Pratt|Pratt]]) Con la sequenza ''h'' 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2^''p''3^''q'', ... Shellsort esegue O(''n''·log(''n'')²) passi per ordinare una sequenza di lunghezza ''n''.

([[Thomas Hibbard|Hibbard]]) Con la sequenza ''h'' 1, 3, 7, 15, 31, 63, 127, ..., 2^''k'' - 1, ... Shellsort esegue O(''n''^3/2) passi per ordinare una sequenza di lunghezza ''n''.

Line 72 ⟶ 69:

([[Insertion sort]]) Il caso peggiore dello Shell sort è l'insertion sort base (usando un passo ''h'' = 1), che richiede O(''n''&sup2;) confronti e scambi.

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

== Altri progetti ==

Line 78 ⟶ 75:

==Bibliografia==

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

[Kn] * D.E. Knuth: Sorting and Searching, vol. 3 of The Art of Computer Programming. Addison-Wesley ([[1973]])<br/>

[Se] * R. Sedgewick: Algorithms. Addison-Wesley ([[1988]])<br/>

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

== 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)]

[[Categoria:Algoritmi di ordinamento]]