Comb sort
Da Wikipedia, l'enciclopedia libera.
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).
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é il gap è 1. A questo punto, comb sort continua ad usare un gap di 1 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.
Indice |
[modifica] 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é 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 è 
.
[modifica] Combsort11
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é 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.
[modifica] Pseudocode example of combsort11
function combsort11(array input)
gap := input.size //initialize gap size
loop until gap = 1 and swaps = 0
//update the gap value for a next comb
if gap > 1
gap := gap / 1.3
if gap = 10 or gap = 9
gap := 11
end if
end if
i := 0
swaps := 0 //see bubblesort for an explanation
//a single "comb" over the input list
loop until i + gap >= array.size
if array[i] > array[i+gap]
swap(array[i], array[i+gap])
swaps := swaps + 1
end if
i := i + 1
end loop
end loop
end function
[modifica] Voci correlate
- Bubble sort, L'algoritmo base del comb sort
- Cocktail sort, o bubble sort bidirezionale, è una variazione che riesce a disperdere velocemente le tartarughe.
[modifica] Collegamenti esterni
| Algoritmi di ordinamento | ||
|---|---|---|
| Teoria | Teoria della complessità computazionale | Notazione O Grande | Lista | Stack | Coda |  |
| Algoritmi a scambio | Bubble sort | Cocktail sort | Comb sort | Gnome sort | Quicksort | |
| Algoritmi di selezione | Selection sort | Heapsort | Smoothsort | |
| Algoritmi ad inserimento | Insertion sort | Shell sort | Tree sort | Library sort | Patience sorting | |
| Algoritmi a fusione | Merge sort | |
| Algoritmi non comparativi | Radix sort | Bucket sort | Counting sort | Pigeonhole sort | |
| Altri algoritmi | Stupid sort | |
