Comb sort: differenze tra le versioni

Versione delle 19:19, 5 gen 2009

Versione delle 20:15, 12 apr 2009

Riga 1:

{{Infobox Algoritmo

|class=[[Algoritmo di ordinamento]]

|image=

|data=[[Array]]

|time=<math>O(n log n)</math>

|space=<math>O(n)</math>

|optimal=?

}}

In [[Informatica]], '''comb sort''' è un algoritmo di ordinamento ideato da [[Stephen Lacey]] e [[Richard Box]], nell' aprile 1991. 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 vicino la 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).