CODEWITHSUNDEEP
algorithmsortingcomplexity-theory
Deqing
Deqing

Reputation: 14632

Performance of counting sort

AFAIK counting sort is using following algorithm:

// A: input array
// B: output array
// C: counting array
sort(A,B,n,k)
1. for(i:k) C[i]=0;
2. for(i:n) ++C[A[i]];
3. for(i:k) C[i]+=C[i-1];
4. for(i:n-1..0) { B[C[A[i]]-1]=A[i]; --C[A[i]]; }

What about I remove step 3 and 4, and do following?

3. t=0; for(i:k) while(C[A[i]]) { --A[i]; B[t++]=i; }

Full code here, looks like fine, but I don't know which one has better performance.

Questions:

  1. I guess the complexity of these two versions would be the same, is that ture?
  2. In step 3 and step 4 the first version need to iterate n+k times, the second one only need to iterate n times. So does the second one have better performance?

Upvotes: 0

Views: 305

Answers (1)

digital_revenant
digital_revenant

Reputation: 3324

Your code seems to be correct and it will work in case of sorting numbers. But, suppose you had an array of structures that you were sorting according to their keys. Your method will not work in that case because it simply counts the frequency of a number and while it remains positive assigns it to increasing indices in the output array. The classical method however will work for arrays of structures and objects etc. because it calculates the position that each element should go to and then copies data from the initial array to the output array.

To answer your question:

1> Yes, the runtime complexity of your code will be the same because for an array of size n and range 0...k, your inner and outer loop run proportional to f(0)+f(1)+...+f(k), where f denotes frequency of a number. Therefore runtime is O(n).

2> In terms of asymptotic complexity, both the methods have same performance. Due to an extra loop, the constants may be higher. But, that also makes the classical method a stable sort and have the benefits that I pointed out earlier.

Upvotes: 1

Related Questions