Comb sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Aggiungo: hu:Fésűs rendezés |
Rimuovo F dimenticato |
||
| (41 versioni intermedie di 28 utenti non mostrate) | |||
Riga 1:
{{Algoritmo
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 cosiddette ''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é generalmente vengono spostati molto velocemente).▼
|classe = [[Algoritmo di ordinamento]]
|immagine = Comb sort demo.gif
|struttura dati = [[Array]]
|tempo = <math>O(n log n)</math>
|spazio = <math>O(n)</math>
|ottimale = ?
|completo =
}}
▲In [[Informatica]]
Nel bubble sort, quando vengono confrontati due elementi, essi hanno sempre un ''
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 fattore
Il valore consigliato come fattore è <math>1/(1-\frac{1}{e^\varphi}) \approx 1.247330950103979</math>.
==
=== Combsort11 ===
Con un fattore di 1,3, ci sono solo tre possibili modi di concludere una lista di
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.
=== Combsort 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">// È 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
'''loop until''' gap = 1 '''and''' swaps = 0
<span style="color:green">//
'''if''' gap > 1
gap
'''if''' gap = 10 '''or''' gap = 9
gap
'''end if'''
'''end if'''
i
swaps
<span style="color:green">//
'''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]]
| |||