Counting sort: differenze tra le versioni

Versione delle 12:16, 13 lug 2011

Versione delle 17:48, 23 set 2011

Riga 47:

C[i] ← C[i] - 1

==Codice in Linguaggio C==

<source lang="c">

int* countingSort(int *v,int n) //v = vettore da ordinare, n = lunghezza vettore

{

int *b,*c,i,li,ls; // li & ls = limite inferiore e superiore

ls=li=v[0];

for(i=1;i<n;i++)

{

if(v[i]<li)

li=v[i];

if(v[i]>ls)

ls=v[i];

}

c=(int*)malloc(sizeof(int)*(ls-li+1));

b=(int*)malloc(sizeof(int)*n);

for(i=0;i<=(ls-li);i++)

c[i]=0;

for(i=0;i<n;i++)

c[v[i]]++;

for(i=1;i<=(ls-li);i++)

c[i]+=c[i-1];

for(i=n-1;i>=0;i--)

{

b[c[v[i]]-1]=v[i];

c[v[i]]--;

}

return b;

}

</source>

== Bibliografia ==

* {{cita libro| Thomas | Cormen | Introduction to Algorithms | 1998| The MIT Press | Cambridge, Massachussetts | coautori=Charles E. Leiserson, [[Ronald Rivest]]| capitolo=Sorting in Linear Time | ed=2 | pagine=pp. 175-177}}