-
AndreaDeDomenico.
User deleted
Questa puntata è speciale, oggi introdurrò il primo algoritmo della serie caratterizzato da una complessità asintotica minore di O(n*logn), in particolare, parlerò del counting sort.
Da un famoso teorema sappiamo come un algoritmo di ordinamento generale non potrà far meglio di algoritmi come il quick-sort od il merge-sort. Un concetto che bisogna aver chiaro fin da subito è che gli algoritmi di ordinamento lineari sono specializzati per funzionare su dei tipi di dati specifici.
In particolar modo, usare il counting-sort ci è utile quando dobbiamo ordinare un array di interi tali che la differenza tra il minimo ed il massimo elemento sia ragionevolmente piccola.CODICEvoid count(int *a, int n)
{
int b[max(a)]; // inizializzato a 0
int i,j;
for(i=0; i<n; ++i) ++b[a[i]];
for(i=0,j=0; j<max(a); ++j)
{
while(b[j])
{
a[i++]=j;
--b[j];
}
}
}
Notate come questo algoritmo si appoggia ad un array ausiliare b, che funziona come un contatore delle frequenze. L'algoritmo è lineare perché in una prima scansione lineare dell'array b viene "popolato" con le occorrenze di ciascun elemento appartenente ad a.
Successivamente viene scansionato l'array b partendo dall'inizio ed inserendo nuovamente gli elementi in a, questa volta però in ordine.
Documentandovi talvolta potreste vedere il counting sort implementato in modo leggermente diverso, la logica sottostante tuttavia è equivalente, ho preferito scriverlo in questo modo perché lo trovo decisamente più intuitivo, anche se non è il modo migliore per farlo (infatti l'array b può essere ottimizzato dal punto di vista spaziale, visto che servono solo max(a)-min(a) posizioni).
La prossima volta vederemo degli algoritmi professionali che spesso vengono implementati nelle librerie standard dei linguaggi di programmazione, stay tuned
.
Algoritmi di ordinamento 7: Complessità lineare! |
Like