Comb sort: differenze tra le versioni

Versione delle 15:33, 26 apr 2008

Versione delle 18:33, 31 ago 2008

Riga 1:

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

Nel bubble sort, quando vengono confrontati due elementi, essi hanno sempre un ''gap'' (distanza reciproca) pari ad 1. L'idea alla base del comb sort è che il gap può essere anche maggiore. (Anche lo [[Shell sort]] è basato su questa idea, ma esso rappresenta una modifica dell'[[insertion sort]] piuttosto che del bubble sort).