Shell sort: differenze tra le versioni

Versione delle 21:53, 30 mar 2016

Versione attuale delle 10:39, 25 mag 2024

(12 versioni intermedie di 10 utenti non mostrate)

Riga 1:

{{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, ma è difficile analizzarne il tempo di esecuzione.

Riga 21:

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|ShellAlgoritmo shell sort con barre di colore algoritmo]]

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.

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 78 ⟶ 80:

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

== Note ==

<references />

== Bibliografia ==

Line 85 ⟶ 90:

== Altri progetti ==

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

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* {{cita web|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}}

{{Portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]