Comb sort: differenze tra le versioni

Versione delle 12:58, 14 set 2014

Versione delle 09:13, 4 gen 2016

Riga 8:

|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 (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]]. Il Comb sort migliora l'algoritmo [[bubble sort]] e compete in velocità con algoritmi storicamente veloci come il [[Merge sort]]. L'idea basilare dell'algoritmo è quella di eliminare le cosiddette "''[[Bubble_sortBubble sort#Conigli_e_tartarugheConigli e tartarughe|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 "''[[Bubble_sortBubble sort#Conigli_e_tartarugheConigli e tartarughe|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 ''passo'' (distanza reciproca) pari ad 1. L'idea alla base del comb sort è che il passo possa essere anche maggiore (anche lo [[Shell sort]] è basato su questa idea, ma esso rappresenta una modifica dell'[[insertion sort]] piuttosto che del bubble sort).

Riga 93:

== Collegamenti esterni ==

*[{{cita web|http://www.sharpdeveloper.net/content/archive/2007/08/14/dot-net-data-structures-and-algorithms.aspx |Implementazione .NET del comb sort]}}

{{Ordinamento}}