Comb sort: differenze tra le versioni

Versione delle 16:19, 5 nov 2018

Versione attuale delle 14:39, 1 lug 2024

(8 versioni intermedie di 7 utenti non mostrate)

Riga 8:

|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 name=":0" /> Il Comb sort migliora l'algoritmo [[bubble sort]] e compete in velocità con algoritmi storicamente veloci come il [[Merge sort]]. L'idea basilare dell'algoritmo è quella di eliminare le cosiddette "''[[Bubble sort#Conigli e tartarughe|tartarughe]]''", ovvero valori piccoli vicini alla fine della lista, essendo provato che in un bubble sort questi valori tendono spessissimo a scendere nella loro posizione in modo tremendamente lento. (i "''[[Bubble sort#Conigli e tartarughe|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 ''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 passo possa essere anche maggiore<ref>{{Cita (ancheweb|url=https://www.dmi.unict.it/messina/didat/prog1_23_24/21_ordinamento.pdf|titolo=Algoritmi lodi [[Shellordinamento: Bubble sort]] è basato su questa idea, ma esso rappresenta una modifica dell'[[insertion sort]] piuttosto che del bubble sort).

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.

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 '''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.

Riga 37 ⟶ 38:

'''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>

Riga 46 ⟶ 47:

<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])

Riga 61 ⟶ 62:

'''function''' combsort11('''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>

Riga 83 ⟶ 84:

'''end loop'''

'''end function'''

==Note==

<references/>

== Voci correlate ==

Riga 90 ⟶ 95:

== Altri progetti ==

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

== Collegamenti esterni ==

*{{cita web|url=http://www.sharpdeveloper.net/content/archive/2007/08/14/dot-net-data-structures-and-algorithms.aspx|titolo=Implementazione .NET del comb sort|accesso=20 settembre 2007|urlarchivio=https://web.archive.org/web/20120212173240/http://www.sharpdeveloper.net/content/archive/2007/08/14/dot-net-data-structures-and-algorithms.aspx|urlmorto=sì}}

{{Ordinamento}}

{{portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]