Comb sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
Rimuovo F dimenticato |
||
| (32 versioni intermedie di 24 utenti non mostrate) | |||
Riga 1:
{{
|
|immagine = Comb sort demo.gif
|
|
|
|
|completo =
}}
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]].<ref name=":0">{{Cita web|url=https://kanasz.blogspot.com/2010/12/comb-sort.html|titolo=Programming blog: Comb Sort|autore=Robert Kanasz|sito=Programming blog|data=2010-12-02|accesso=2024-06-29}}</ref> 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
Nel bubble sort, quando vengono confrontati due elementi, essi hanno sempre un ''passo'' (distanza reciproca) pari ad 1.<ref>{{Cita web|url=https://xlinux.nist.gov/dads/HTML/combSort.html|titolo=comb sort|sito=xlinux.nist.gov|accesso=2024-06-29}}</ref><ref name=":0" /> L'idea alla base del comb sort è che il
Selection sort, Insertion sort|autore=Fabrizio Messina|pp=4-8}}</ref> (anche lo [[Shell sort]] è basato su questa idea, ma esso rappresenta una modifica dell'[[insertion sort]] piuttosto che del bubble sort<ref>{{Cita web|url=https://www.geeksforgeeks.org/shellsort/|titolo=ShellSort|sito=GeeksforGeeks|data=2014-06-16|lingua=en-US|accesso=2024-06-29}}</ref>).
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.
==
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
Il valore consigliato come fattore è <math>1/(1-\frac{1}{e^\varphi}) \approx 1.247330950103979</math>.
Riga 21 ⟶ 22:
==Varianti==
=== Combsort11 ===
Con un fattore di 1,3, ci sono solo tre possibili modi di concludere una lista di passi: (9, 6, 4, 3, 2, 1), (10, 7, 5, 3, 2, 1), oppure (11, 8, 6, 4, 3, 2, 1). Soltanto l'ultima sequenza elimina tutte le "tartarughe" prima che il passo divenga 1. Ragion per cui, si hanno miglioramenti significativi in velocità se l'intervallo viene impostato ad 11 ogni qualvolta esso debba diventare 9 o 10. Questa variazione è chiamata
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.
Riga 27 ⟶ 28:
Un'altra ottimizzazione è quella di utilizzare una tabella da cui scegliere il passo da usare ad ogni scorrimento dei dati.
===
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.
Riga 33 ⟶ 34:
== Pseudocodice ==
Implementazione del Comb sort classico:
'''function''' combsort('''array''' input)
gap
'''loop until''' gap <= 1 '''and''' swaps = 0
<span style="color:green">//aggiorna il valore del passo per il prossimo passaggio</span>
gap
i
swaps
<span style="color:green">//un singolo "comb" sulla lista dei dati</span>
'''loop until''' i + gap >= input.size<span style="color:green"> //vedi
'''if''' input[i] > input[i+gap]
[[Swap (computer science)|swap]](input[i], input[i+gap])
swaps
<span style="color:green">// la lista potrebbe non essere ordinata</span>
'''end if'''
i
'''end loop'''
'''end loop'''
'''end function'''
Riga 61:
Implementazione del Combsort11:
'''function''' combsort11('''array''' input)
gap
'''loop until''' gap = 1 '''and''' swaps = 0
<span style="color:green">//aggiorna il valore del passo per il prossimo passaggio</span>
'''if''' gap > 1
gap
'''if''' gap = 10 '''or''' gap = 9
gap
'''end if'''
'''end if'''
i
swaps
<span style="color:green">//un singolo "comb" sulla lista dei dati</span>
'''loop until''' i + gap >= array.size
'''if''' array[i] > array[i+gap]
[[Swap (computer science)|swap]](array[i], array[i+gap])
swaps
'''end if'''
i
'''end loop'''
'''end loop'''
'''end function'''
==Note==
<references/>
== Voci correlate ==
* [[algoritmo di ordinamento]]
* [[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}}
== Collegamenti esterni ==
*
{{Ordinamento}}
{{portale|informatica}}
[[Categoria:Algoritmi di ordinamento]]▼
▲[[Categoria:Algoritmi di ordinamento]]
| |||