Smoothsort: differenze tra le versioni

Versione delle 02:03, 25 mag 2010

Versione delle 05:41, 14 apr 2012

Riga 11:

}}

In [[informatica]] lo '''Smoothsort'''<ref>[http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF ewd796a<!-- Titolo generato automaticamente -->]</ref><ref>[http://www.cs.utexas.edu/~EWD/transcriptions/EWD07xx/EWD796a.html E.W.Dijkstra Archive: Smoothsort, an alternative for sorting in situ (EWD 796a)<!-- Titolo generato automaticamente -->]</ref> (metodo) è un [[algoritmo di ordinamento]] particolarmente indicato per ordinare liste di dati già parzialmente ordinate. Lo Smoothsort è una variante dell'[[Heap sort]] sviluppata da [[Edsger Dijkstra]] nel [[1981]]: come l'Heap sort anche lo Smoothsort presenta il limite computazionale massimo pari a [[O-grande|O]](''n'' log&nbsp;''n''). Lo Smoothsort, però, si avvicina ad un tempo O(''n'') se [[algoritmi di ordinamento adattivi|i dati in ingresso sono già parzialmente ordinati]], mentre l'Heap sort mediamente impiega O(''n'' log&nbsp;''n''), indifferentemente dal livello di ordinamento iniziale.

==Analisi==