Comb sort: differenze tra le versioni

Versione delle 08:46, 16 lug 2011

Versione delle 23:40, 18 lug 2011

Riga 14:

Il ''passo'', o intervallo del confronto, è impostato inizialmente alla lunghezza dell'[[array]] da ordinare divisa per il ''fattore di riduzione'' (generalmente 1,3), e la lista viene ordinata con tale intervallo (arrotondato per difetto all'intero, se necessario). Terminato il primo passaggio il passo viene diviso nuovamente per il fattore di riduzione (arrotondato all'intero), e la lista viene ordinata con questo nuovo intervallo. Il processo si ripete finché il passo è pari a 1. A questo punto, il Comb sort continua ad usare un passo di 1 finché non si ha un ordinamento totale. Il passaggio finale dell'algoritmo è quindi equivalente ad un bubble sort, ma in questo modo molte "tartarughe" sono scomparse, ed in tal modo il bubble sort è molto più efficiente.

== Fattore di riduzione==

Il fattore di riduzione ha un grande peso sull'efficienza del Comb sort. Ai tempi della sua creazione, gli autori suggerirono di usare il valore di 1,3 in base a delle prove sperimentali basate sulla casualità. Un valore troppo piccolo degrada le prestazioni dell'algoritmo perché si rendono necessari più confronti, mentre con valore troppo alto non si riuscirebbe ad eliminare un numero di "tartarughe" tale da rendere il comb sort un miglioramento sostanziale del bubble sort.

Riga 88:

* [[Bubble sort]], L'algoritmo base del comb sort

* [[Cocktail sort]], o bubble sort bidirezionale, è una variazione che riesce a disperdere velocemente le tartarughe.

== Altri progetti ==

{{interprogetto|commons=Category:Sort algorithms}}

== Collegamenti esterni ==