shell sort

Shell sort, sviluppato da Donald L. Shell, è un algoritmo di sort di tipo non-stable e in-place. Shell sort migliora l'efficienza dell'insertion sort shiftando più velocemente i valori alla loro destinazione. Il tempo medio di ordinamento è O(n^1.25), mentre nel caso peggiore è O(n^1.5) .
Vari intervalli possono essere usati implementando shell sort. Tipicamente l'array è ordinato con un largo intervallo, poi si riduce l'intervallo e si ordina ancora l'array. Nell'ultimo sort l'intervallo è uno. Benchè shell sort è facile da comprendere, l'analisi formale è difficile. In particolare, i valori di intervallo ideali sfuggono ai teorici. Knuth ha sperimentato molti valori e raccomanda che l'intervallo h per un array di grandezza N sia basato sulla seguente formula:

Così, i valori di h sono calcolati come segue:

                                                            h(1)=1
                                                            h(2)=(3x1)+1=4
                                                            h(3)=(3x4)+1=13
                                                            h(4)=(3x13)+1=40
                                                            h(5)=(3x40)+1=121

Per ordinare 100 elementi prima troviamo h(s) così che h(s)>=100. Per 100 elementi, h(5) è selezionato. Il nostro valore finale [ h(t) ] è due passi più basso, ovvero h(3). Perciò la nostra sequenza di h sarà 13-4-1. Una volta che il valore iniziale di h è stato determinato, i valori seguenti possono essere calcolati usando la formula

Esempio: insertion vs. shell

Esempio di insertion sort. In figura a) estraiamo 1, shiftiamo 3 e 5 giù di uno slot, e allora inseriamo 1, usando 2 shifts. Nel seguente passaggio, due shifts sono richiesti prima che possiamo inserire il 2. Il processo continua fino alll'ultimo passaggio, per un totale di 2+2+1=5 shifts.
 

Esempio di shell sort. In figura b) cominciamo facendo un insertion sort usando un intervallo di due. Nel primo passaggio esaminiamo i numeri 3-1. Estraendo 1, shiftiamo 3 giù di uno slot usando uno shift. Poi esaminiamo i numeri 5-2. Estraimo 2, shiftiamo 5 sotto, e iseriamo il 2. Dopo aver ordinato con un ordinato con un intervallo di due, un passo finale è compiuto con un intervallo di uno. Il conto totale degli shift usando shell sort è 1+1+1=3. Usando un intervallo iniziale più largo di uno, siamo in grado di shiftare più velocemente i valori al loro posto.