4 replies to this topic

[Iceboy]

int a[100],c[101],b[100],i=0,n,j=0,k;

  printf("introdu n=");

  scanf("%d",&n);

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

  {

   printf("a[%d]=",i);

   scanf("%d",&a[i]);

  }

  for(k=1;k>=n;k++)

  c[k]=0;

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

c[a[j]]=c[a[j]]+1;

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

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

  for(j=n;j>1;j--)

{

   b[c[a[j]]]=a[j];

   c[a[j]]=c[a[j]]-1;

}


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

  {

   printf("b[%d]=%d\n",i,b[i]);

   }

Counting sort but its not working i have forgotten something anyway i need it in O(n) so anyone have an idea what is wrong?
And second question is It gives an array of numbers that are in the set of {2,3,4...,n}. Modify the array with an algorithm of complexity O(n) so that when asked: How many numbers are in the interval [a,b] to be in a constant time that means O(1). Can i have some idea on this i don't know any algorithm of complexity 1 ...

[WingedPanther]

Sorting has an optimal complexity of O(n ln(n)). Why are you trying to get O(n)?

Similarly, I think your second complexity isn't going to be better than O(ln(n)), unless you know there are no gaps (which would have an answer of b-a+1).

[Iceboy]

The problem ask me to do it in O(n) otherwise i would do heap sort or quick sort and that would be ... but it ask me O(n) on a set of numbers from {0,1,2,3...n} and the idea is the count sort.

[fayyazlodhi]

O(n lg n) is limit for COMPARISON sort based algorithms. Not others.

Counting sort is a standard known algorithm which runs in O(n). However, it has some limitations in terms of range of numbers it can operate on should be with in array limits etc. So it is not a general algorithm.

Why don't you google a little bit, look at it's standard implementation and try to see where you are going wrong? There are many resources including "Intro to Algorithms by Coreman" describing the algo.

Fayyaz

[kernelcoder]

There are few problems in your code. The main problem is that have not set the value for k. Following is the working code...

int i, j, n, k, data[MAX_DATA_COUNT], count[MAX_DATA_COUNT], output[MAX_DATA_COUNT], c, total = 0, max = -99999;

printf("introdu n=");
scanf("%d",&n);
for(i  =0; i < n; i++) {
printf("data[%d]=", i);
scanf("%d", &data[i]);
if (max < data[i]) max = data[i];
}

k = max + 1;
for (i = 0; i < k; i++) count[i] = 0;
for (i = 0; i < n; i++) count[data[i]] = count[data[i]] + 1;

for(i = 0; i < k; i++) {
c = count[i];
count[i] = total;
total = total + c;
}

for(i = 0; i < n; i++) {
output[count[data[i]]] = data[i];
count[data[i]] = count[data[i]] + 1;
}


for(i=0;i<n;i++)
printf("b[%d]=%d\n",i, output[i]);

Here are some links that will be helpful for you...
http://www.cse.iitk....untingSort.html
http://en.wikipedia....i/Counting_sort