Comb sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
Nessun oggetto della modifica |
||
Riga 5:
|time=<math>O(n log n)</math>
|space=<math>O(n)</math>
|optimal=?
|Complete=
}}
In [[Informatica]] il '''Comb sort''' è un algoritmo di ordinamento pubblicato per la prima volta da [[Stephen Lacey]] e [[Richard Box]] sul numero di aprile [[1991]] della rivista [[Byte]]. Il Comb sort rielabora le idee che Wlodzimierz Dobosiewicz applicò nel [[1980]] per rendere più efficiente lo [[shell sort]] utilizzando la funzione del [[bubble sort]]<ref>[http://en.wikipedia.org/wiki/Talk:Comb_sort#Brick_sort Credito a Dobosiewicz sulla paternità del Comb sort]</ref>. Il Comb sort migliora l'algoritmo [[bubble sort]] e compete in velocità con algoritmi storicamente veloci come il [[Quicksort]]. L'idea basilare dell'algoritmo è quella di eliminare le cosiddette "''tartarughe''", ovvero valori piccoli vicini alla fine della lista, essendo provato che in un bubble sort questi valori tendono spessissimo a scendere nella loro posizione in modo tremendamente lento. (i "''conigli''", ovvero grandi valori all'inizio della lista, non rappresentano un problema nel bubble sort perché generalmente vengono spostati molto velocemente).
| |||