Shell sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
+aggiunto portale |
→Collegamenti esterni: Aggiunto il template "Collegamenti esterni" Etichette: Modifica da mobile Modifica da applicazione mobile Modifica da applicazione Android |
||
| (5 versioni intermedie di 3 utenti non mostrate) | |||
Riga 1:
{{Algoritmo
|classe = [[Algoritmo di ordinamento]]
|immagine =Sorting shellsort anim2.gif
|struttura dati = [[Array]]
|tempo = O(''n''<sup>2</sup>)
|tempo migliore = O(''n'' log<sub>2</sub> ''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.
Riga 64:
([[Donald Knuth|Knuth]]) Con la sequenza ''h'' 1, 4, 13, 40, 121, ..., 3''h''<sub>''s''-1</sub> + 1 = (3<sup>''s''</sup> - 1)/2, ... Shellsort esegue O(''n''<sup>3/2</sup>) 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''<sup>4/3</sup>) 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''<sup>4/3</sup>) passi per ordinare una sequenza di lunghezza ''n''.
Line 88 ⟶ 90:
== Altri progetti ==
{{interprogetto|b=Implementazioni_di_algoritmi/Shell_sort|b_oggetto=implementazioni|b_preposizione=
== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{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 degli Algoritmi e Strutture Dati: Shellsort (inglese)}}
| |||