Comb sort: differenze tra le versioni

Versione delle 23:42, 20 apr 2010

Versione delle 17:30, 2 mag 2010

Riga 5:

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

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

|optimal=?

}}

In [[Informatica]], il '''combComb sort''' è un algoritmo di ordinamento ideatopubblicato per la prima volta da [[Stephen Lacey]] e [[Richard Box]], nell'sul numero di aprile [[1991]] della 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]]<ref>[http://en.wikipedia.org/wiki/Talk:Comb_sort#Brick_sort Credito a Dobosiewicz sulla paternità del Comb sort]</ref>. Il 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 vicinovicini laalla 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 ''gappasso'' (distanza reciproca) pari ad 1. L'idea alla base del comb sort è che il gappossa puòpossa essere anche maggiore. (Ancheanche lo [[Shell sort]] è basato su questa idea, ma esso rappresenta una modifica dell'[[insertion sort]] piuttosto che del bubble sort).

LIl ''passo'', o intervallo didel confronto, cominciaè comeimpostato lainizialmente alla lunghezza dell'[[array]] da ordinare, divisa per il ''fattore shrinkdi riduzione'' (generalmente 1,3), e la lista viene ordinata con tale intervallo (arrotondato per difetto all'intero, se necessario). AlchèTerminato essoil primo passaggio il passo viene diviso nuovamente per il fattore Shrinkdi riduzione (arrotondato all'intero), e la lista viene ordinata con questo nuovo intervallo. Il processo si ripete finché il gappasso è pari a 1. A questo punto, combil Comb sort continua ad usare un gappasso 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 Shrinkdi riduzione==

Il fattore Shrinkdi riduzione ha un grande peso sull'efficienza del combComb 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 l'algoritmo perché si necessitarendono dinecessari 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>.

== Combsort11 Varianti==

=== Combsort11 ===

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

Questo si nota anche 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.

Un'altra ottimizzazione è quella di utilizzare una tabella da cui scegliere il passo da usare ad ogni scorrimento dei dati.

=== Combosort con altri metodi conclusivi ===

Come molti altri algoritmi (tipo il quick sort o il [[merge sort]]), il Comb sort è più efficiente durante i passaggi iniziali che in quelli finali, quando tende ad assomigliare al bubble sort. Il Comb sort può perciò essere reso più efficiente se il metodo di ordinamento viene cambiato non appena i passi raggiungono dei valori sufficientemente piccoli. Ad esempio, non appena il passo raggiunge o passa sotto il valore di 10, si può terminare l'utilizzo del comb sort e finire l'ordinamento utilizzando uno [[gnome sort]] o uno [[shaker sort]] o, meglio ancora, un [[insertion sort]], incrementando l'efficienza complessiva dell'ordinamento.

Un altro vantaggio di questo metodo è dato dal non dover tenere traccia degli scambi durante i vari passaggi per verificare se l'ordinamento si deve fermare oppure no.

== Pseudocodice ==

Implementazione del Comb sort classico:

'''function''' combsort('''array''' input)

gap := input.size <span style="color:green">//inizializza la dimensione del passo</span>

'''loop until''' gap <= 1 '''and''' swaps = 0

<span style="color:green">//aggiorna il valore del passo per il prossimo passaggio</span>

gap := int(gap / 1.25)

<br />

i := 0

swaps := 0 <span style="color:green">//vedi [[bubble sort]] per una spiegazione</span>

<br />

<span style="color:green">//un singolo "comb" sulla lista dei dati</span>

'''loop until''' i + gap >= input.size<span style="color:green"> //vedi [[shell sort]] per un'idea simile</span>

'''if''' input[i] > input[i+gap]

[[Swap (computer science)|swap]](input[i], input[i+gap])

swaps := 1 <span style="color:green">// E' stato eseguito uno scambio, perciò</span>

<span style="color:green">// la lista potrebbe non essere ordinata</span>

'''end if'''

i := i + 1

'''end loop'''

<br />

'''end loop'''

'''end function'''

Implementazione del Combsort11:

'''function''' combsort11('''array''' input)

gap := input.size <span style="color:green">//initialize gap size</span>

Riga 49 ⟶ 83:

'''end loop'''

'''end function'''

==Riferimenti==

<references/>

== Voci correlate ==