|
Una sequenza ''h'' facilmente computabile per lo Shell sort è la [[Successione_di_Fibonacci|Sequenza di Fibonacci]] (1, 2, 3, 5, 8, 13, 21, ... ), o il suo quadrato (1, 4, 9, 25, 64, ...).
== ImplementazioniAltri progetti ==
{{interprogetto|b=Algoritmi/Shell sort|b_oggetto=implementazioni|b_preposizione=di}}
{{Trasferimento|wb|Implementazioni}}
=== Utilizzo di una lista di dimensioni ===
Il seguente programma [[Linguaggio_C|C]] ordina un array ''a'' dalla posizione 0 fino a ''n''-1. Il numero di colonne usato per organizzare i dati in ciascuna passata è nell'array ''cols''. Quindi, i dati vengono distribuiti in 4,356,424 colonne durante la prima passata e in una sola colonna nell'ultima. È 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
}
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;
}
// eg, h = 8, hh = 13
h = hh - h; // h = 13 - 8 = 5
hh = hh - h; // hh = 13 - 5 = 8
}
}</pre>
I quadrati dei numeri di Fibonacci (1, 4, 9, 25, ...) formano una sequenza ancora migliore.
L'implementazione viene lasciata al lettore.
==Bibliografia==
|
