Shell sort: differenze tra le versioni

Versione delle 22:25, 11 apr 2005

Versione attuale delle 10:39, 25 mag 2024

(77 versioni intermedie di 57 utenti non mostrate)

Riga 1:

{{Algoritmo

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

|classe = [[Algoritmo di ordinamento]]

E' veloce, facile da comprendere e da implementare.

|immagine =Sorting shellsort anim2.gif

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

|struttura dati = [[Array]]

E' semplice comprendere in maniera intuitiva il fuzionamento dell'algoritmo, ma è spesso difficile analizzarne il tempo di esecuzione.

|tempo = O(''n''²)

|tempo migliore = O(''n'' log₂ ''n'')<ref>{{Cita web|titolo=Shellsort & Comparisons|url=http://www.cs.wcupa.edu/rkline/ds/shell-comparison.html|accesso=19 aprile 2016|dataarchivio=20 dicembre 2019|urlarchivio=https://web.archive.org/web/20191220040546/https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html|urlmorto=sì}}</ref>

|tempo medio = dipende dai dati

|spazio = O(''n'')

|ottimale = No

|didascalia=Ordinamento di una sequenza numerica tramite lo shell sort}}

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

L'algoritmo è veloce, facile da comprendere e da implementare, ma è difficile analizzarne il tempo di esecuzione.

Lo Shell sort viene a volte chiamato "Shell-Metzner sort" in onore di Marlene Metzner che ne scrisse una primissima implementazione in [[FORTRAN]]. Venne per la prima volta chiamato Shell-Metzner in un articolo su ''[[Creative Computing'']] nel [[1976]], ma Marlene Metzner disse di non volere che l'algoritmo portasse il suo nome.

== 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 eseguendospostando passii valori di più grandiposizioni per volta man manmanomano 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|Algoritmo shell sort con barre di colore]]

Consideriamo un valore piccolo posizionato inizialmente all'estremità errata dell'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:

* # sistema la sequenza dei dati in un array bidimensionale (con un numero ''h'' di colonne)

* # ordina lei valori presenti all'interno di ciascuna colonnecolonna 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 memero più bassonumero di colonne ''h'' più basso. Nell'ultimoultima passopassata, l'array è composto da una singola colonna(''h''=1) trasformando di fatto quest'ultimo giro in un insertion sort puro e semplice.

Ad ogni passopassata i dati diventano sempre più ordinati, finchèfinché, durante l'ultimo passoultima lo diventano del tutto. Comunque, il numero di operazioni di ordinamento necessarie in ciascunciascuna passopassata è limitato, a causa dell'ordinamento parziale ottenuto neinelle passipassate precedenti.

== Esempio ==

Poniamo che

<pre>

Line 34 ⟶ 41:

8 4 2 0 6 1 5 -> 7 4 4 0 6 1 6

7 3 4 9 8 2 8 7 9 9 8 2</pre>

Gli elementi 8 e 9 sono ora arrivati in fondo alla sequenza, ma lì c'è anche un elemento piccolo (2) che non dovrebbe esserci. NelNella prossimoprossima passopassata, la sequenza viene organizzata su tre colonne, che vengono nuovamente ordinate:

<pre>

3 3 2 0 0 1

Line 43 ⟶ 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'ultimoultima passopassata, sono solamente un 6, un 8 ed un 9 che devono essere spostati leggermente per arrivare a destinazione.

In realtà, i dati non vengono inseriti in un array bidimensionale, ma vengono tenuti in un array monodimensionale indirizzato opportunamente. Per esempio, i dati alle posizioni 0, 5, 10, 15, etc. formerebbero la prima colonna di un array a cinque colonne. Le "colonne" ottenute con questo indirizzamento vengono ordinate tramite l'[[Insertion sort]], dal momento che questo metodo è piuttosto veloce con sequenze abbastanza ordinate.

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

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

Ma, visto che i dati vengono preordinati dai passi precedenti (''h'' = 3, 7, 31, ...), una manciata di passate dell'insertion sort sono sufficienti. Il numero esatto dipende dalla sequenza dei valori ''h'' (noti come sequenze ''h''). La sequenze ''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''.

([[Donald Knuth|Knuth]]) Con la sequenza ''h'' 1, 4, 13, 40, 121, ..., 3''h''_''s''-1 + 1 = (3^''s'' - 1)/2, ... Shellsort esegue O(''n''^3/2) passi per ordinare una sequenza di lunghezza ''n''.

(sequenza non definita) con la sequenza h 1, 8, 23, ..., 4i+1 + 3*2i +1, ... Shellsort esegue O (''n''^4/3) passi per ordinare una sequenza di lunghezza n.

([[Robert Sedgewick|Sedgewick]]) Con la sequenza ''h'' 1, 5, 19, 41, 109, 209, ... (descritta qui sotto), Shellsort esegue O(''n''^4/3) passi per ordinare una sequenza di lunghezza ''n''.

Line 63 ⟶ 71:

:<math>

h_s=

\left\begin{cases}

9 \cdot 2^s - 9 \cdot 2^{s/2} + 1 & \mbox{per }s\mbox{ pari} \\

\begin{matrix}

98 \cdot 2^s - 96 \cdot 2^{(s+1)/2} + 1 & \mbox{ifper }s\mbox{ is evendispari} \\

\end{cases}

8 \cdot 2^s - 6 \cdot 2^{(s+1)/2} + 1 & \mbox{if }s\mbox{ is odd} \\

\end{matrix}

\right.

</math>

([[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|Sequenza di Fibonacci]] (1, 2, 3, 5, 8, 13, 21, ... ), che incrementa la dimensione del passo con una progressione naturale.

== Implementazioni ==

=== Utilizzo di una lista di dimensioni ===

Il seguente programma [[Linguaggio di programmazione Java|Java]] ordina un array ''a'' dalla posizione 0 fino a ''n''-1. Il numero di colonne usato for organizzare i dati in ciascuna passata è nell'array ''cols''. Quindi, i dati vengono distribuiti in 4,356,424 colonne durante il primo passo e in una sola colonna nell'ultimo. E' da notare che essenzialmente nulla viene eseguito se il numero di colonne ''h'' è maggiore del numero di elementi dati ''n'' . Ciascuna colonna viene ordinata usando l'insertion sort. Prima, i dati della seconda riga, cominciando da ''i'' = ''h'', vengono portati nella corretta posizione all'interno della loro colonna, poi i dati della terza riga (quando ''i'' raggiunge il valore 2''h'') e così via.

<pre>

void shellsort (int[] a, int n) {

int i, j, k, h, v;

int[] cols= { 4356424, 1355339, 543749, 213331, 84801, 27901,

11969, 4711, 1968, 815, 277, 97, 31, 7, 3, 1 };

for (k=0; k<16; k++) {

h=cols[k];

for (i=h; i<n; i++) {

v=a[i];

j=i;

while (j>=h && a[j-h]>v) {

a[j]=a[j-h];

j=j-h;

}

a[j]=v;

}

}

}</pre>

=== Utilizzo dei numeri di fibonacci ===

<pre>

void shellsort (int[] a, int n) {

int h=1, hh=1;

while(hh<n) {

// eg, h = 5, hh = 8

hh=hh+h; // hh = 8 + 5 = 13

h=hh-h; // h = 13 - 5 = 8

}

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, ...).

while(hh > 1) {

int i, j, v;

for (i=h; i<n; i++) {

v=a[i];

j=i;

while (j>=h && a[j-h]>v) {

a[j]=a[j-h];

j=j-h;

}

a[j]=v;

}

== Note ==

// eg, h = 8, hh = 13

<references />

== Bibliografia ==

h = hh - h; // h = 13 - 8 = 5

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

hh = hh - h; // hh = 13 - 5 = 8

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

}

* R.Sedgewick: Algorithms. Addison-Wesley (1988)

}</pre>

== Altri progetti ==

I quadrati dei numeri di Fibonacci (1, 4, 9, 25, ...) formano una sequenza ancora migliore.

{{interprogetto|b=Implementazioni_di_algoritmi/Shell_sort|b_oggetto=implementazioni|b_preposizione=dello|preposizione=sullo}}

L'implementazione viene lasciata al lettore.

== Collegamenti esterni ==

==Riferimenti==

* {{Collegamenti esterni}}

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

* {{cita web | 1 = http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm | 2 = Analisi dettagliata dello Shell sort (inglese) | accesso = 11 aprile 2005 | dataarchivio = 16 gennaio 2000 | urlarchivio = https://web.archive.org/web/20000116130927/http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm | urlmorto = sì }}

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

* {{cita web|http://www.nist.gov/dads/HTML/shellsort.html|Dizionario degli Algoritmi e Strutture Dati: Shellsort (inglese)}}

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

{{Ordinamento}}

== Link esterni ==

{{Portale|informatica}}

*[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)]

[[Algoritmo_di_ordinamento|Categoria:Algoritmi di ordinamento]]