Shell sort: differenze tra le versioni

Versione delle 17:17, 6 gen 2010

Versione attuale delle 10:39, 25 mag 2024

(35 versioni intermedie di 27 utenti non mostrate)

Riga 1:

{{Infobox Algoritmo

|classclasse = [[Algoritmo di ordinamento]]

|immagine =Sorting shellsort anim2.gif

|image=

|datastruttura dati = [[Array]]

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

|time=dipende dai dati

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

|best-time=O(''n'')

|average-timetempo medio = dipende dai dati

|spacespazio = O(''n'')

|optimalottimale = 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, benché l'analisi della sua complessità sia leggermente più sofisticata: è semplice comprendere in maniera intuitiva il funzionamento dell'algoritmo, ma è spesso 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.

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.

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

Ad ogni passata i dati diventano sempre più ordinati, finché, durante l'ultima lo diventano del tutto. Comunque, il numero di operazioni di ordinamento necessarie in ciascuna passata è limitato, a causa dell'ordinamento parziale ottenuto nelle passate precedenti.

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 64:

([[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 75 ⟶ 77:

</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 [[sequenza di Fibonacci]] (1, 2, 3, 5, 8, 13, 21, ... ) o il suo quadrato (1, 4, 9, 25, 64, ...).

== Altri progettiNote ==

<references />

{{interprogetto|b=Algoritmi/Shell sort|b_oggetto=implementazioni|b_preposizione=di}}

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

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

== Altri progetti ==

{{interprogetto|b=AlgoritmiImplementazioni_di_algoritmi/Shell sortShell_sort|b_oggetto=implementazioni|b_preposizione=didello|preposizione=sullo}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

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

* {{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ì }}

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

{{Ordinamento}}

[[Categoria:Algoritmi di ordinamento]]

{{Portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]

[[cs:Shell sort]]

[[de:Shellsort]]

[[en:Shell sort]]

[[es:Ordenamiento Shell]]

[[fa:مرتب‌سازی شل]]

[[fr:Tri de Shell]]

[[he:Shell sort]]

[[ja:シェルソート]]

[[ko:셸 정렬]]

[[lt:Šelo rikiavimo algoritmas]]

[[nl:Shellsort]]

[[pl:Sortowanie Shella]]

[[pt:Shell sort]]

[[ru:Сортировка Шелла]]

[[sl:Shellovo urejanje]]

[[tr:Kabuk sıralaması]]

[[uk:Сортування Шелла]]

[[zh:希尔排序]]