retagged by
6,564 views
26 votes
26 votes
Give an optimal algorithm in pseudo-code for sorting a sequence of $n$ numbers which has only $k$ distinct numbers ($k$ is not known a Priori). Give a brief analysis for the time-complexity of your algorithm.
retagged by

5 Answers

Best answer
23 votes
23 votes

Answer should be counting sort which will take $O(n+k)$ time.

See here:http://www.geeksforgeeks.org/counting-sort/

edited by
5 votes
5 votes

We cannot do it in O(n+k). We will need O(n+klogk).

Why not O(n+k)?

In worst case, if we have k=n distinct elements, then by O(n+k) we are implying that n distinct elements can be sorted in O(n) – which is impossible (without some other special condition, such as range or anything, and there isn’t any such in this question). Here we don’t have the range given explicitly, so at the worst it can be 1 to m where m is the largest element and m can be larger than n itself (m can be O($n^{2}$) or O($n^{3}$) or even higher). So we cannot use the range 1 to m because a simple O(nlogn) solution would be way better than O(m). 

How in O(n+klogk)?

  1. Create a Hash map of all the distinct k elements (similar to the count array we use in counting sort)
  2. Sort these k elements –  this needs to be done explicitly because we have k distinct elements and not a range of 1 to k. This wasn’t needed in counting sort because we can take an array of size k and the indices will be in sorted order only (1 to k) but here this won’t hold true so sorting the distinct elements is needed  --- O(klogk)
  3. Rest is same as counting sort – we store the count of each distinct element and then print them in sorted manner  --- O(n)

So time complexity will be O(n + klogk)

3 votes
3 votes
use a hash map with chaining to sort all the numbers in $\mathcal{O}(n)$ time and constant space.
1 votes
1 votes

 We can write code like this
 

int distinctValue(int a[ ] , int n)
{
   int k=0,value[100],distinct[100];
   for(i=0 ; i<10 ; i++)
       {
       if(max<value[i])
          max=value[i];
       }
   for(i=0; i<max; i++)
       {
          distinct[value[i]]=value[i]; 
       }
    for(i=0; i<max; i++)
      {
         distinct[i]=distinct[i-1]+distinct[i];
      }
return 0;
}

 

So, complexity will be $O\left ( n \right )$

edited by

Related questions

50 votes
50 votes
3 answers
3
Kathleen asked Sep 12, 2014
8,636 views
The minimum number of comparisons required to sort $5$ elements is ______
43 votes
43 votes
3 answers
4
Kathleen asked Sep 12, 2014
13,807 views
Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph $G$ with $n$ vertices and $m$ edges has the time complexity of:$O(n^{2})$$O(mn)$$O(m+n)$$O(m...