Comb sort: differenze tra le versioni

Versione delle 08:33, 20 set 2007

Versione delle 11:28, 4 ott 2007

Riga 1:

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 cosidette ''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è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).

L'intervallo di confronto comincia come la lunghezza dell'array da ordinare, divisa per il ''fattore shrink'' (generalmente 1,3), e la lista viene ordinata con tale intervallo (arrotondato per difetto all'intero, se necessario). Alchè esso viene diviso nuovamente per il fattore Shrink, e la lista viene ordinata con questo nuovo intervallo. Il processo si ripete finchèfinché il gap è 1. A questo punto, comb sort continua ad usare un gap di 1 finchèfinché non si ha 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 Shrink ==

Il fattore Shrink ha un grande peso sull'efficienza del comb sort. Ai tempi della sua creazione, gli autori suggerirono 1.3 in base a delle prove sperimentali basate sulla casualità. Un valore troppo piccolo degrada l'algoritmo perchèperché si necessita di più confronti, mentre un valore troppo alto non riuscirebbe ad eliminare un numero sufficiente di tartarughe per essere un miglioramento sostanziale del bubble sort.

Il valore consigliato come fattore è <math>1/(1-\frac{1}{e^\varphi}) \approx 1.247330950103979</math>.

Riga 13:

Con un fattore di 1,3, ci sono solo tre possibili modi di concludere una lista di intervalli: (9, 6, 4, 3, 2, 1), (10, 7, 5, 3, 2, 1), oppure (11, 8, 6, 4, 3, 2, 1). Soltanto l'ultima sequenza uccide tutte le tartarughe prima che il gap divenga 1. Ragion per cui, si hanno miglioramenti significativi in velocità se l'intervallo viene settato ad 11 ogni qual volta esso debba diventare 9 o 10. Questa variazione è chiamata Combsort11.

Questo si nota anche perchèperché se si arrivasse ad usare un intervallo pari a 9 o a 10, il passo finale con un intervallo pari ad 1 sarebbe più inefficiente in quanto ripetuto due volte. I dati sono ordinati quando non si effettuano scambi tra valori durante tutta la scansione dell'array con intervallo 1.

== Pseudocode example of combsort11 ==