1.2k views
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.
edited | 1.2k views
+2

Watch it ...

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

See here:

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

edited
+3

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing)."  source GFG

also counting sort needs key values within some range . This assumption is not given in the question !!

But somehow i think O(n+k) is time complexity of correct algorithm .

+1
I think by saying   O(n+k) he means   ...  'k' is the maximum value....  but here already one k is there.. So
counting sort takes O(n+m)....where m is the maximum value.....  but still I do not know whats the answer.
0
As here k is given in question, i finally go with counting sort with O(n+k) time complexity.

As the definition of counting sort says "Counting sort is an algorithm that takes an array A of n elements in the range {1, 2, ..., k} and sorts the array in O(n + k) time " reference MIT slide .

An extra array ( auxiliary array with k elements) maintain by counting sort .
+1
Yes..Now I agree with the answer....but here in qsn k means something else. So should not a different variable be used like m instead of k? @Bikram sir.
+1
@ashwan

No , here k means different kind of elements among n elements . Also counting sort definition says the same "Counting sort is an algorithm that takes an array A of n elements in the range {1, 2, ..., k} " here range means different type of elements like 1,2,3,..,k  ..k different elements .

+2
@bikram sir,  So this is not a possible input sequence here?     5,100,1000,5,100,10000   where k=4 distinct elements but maximum value=10000
+1
@ahwan

Yes, this is possible sequence.

This question indirectly ask about counting sort..see the definition of counting sort an this question, you will understand, you may read that MIT slide..google it
+1
@Bikram sir.I don't agree with the selected answer.Here k is not the range so how can we use counting sort?

If my array is :- 1,2,3,1000.

Now my k=4 as 4 distinct numbers but maximum number is 1000. K can be 1 or it can be n(total elements),so it is a general case ,array can have 1 distinct element or it can have n distinct elements and it has nothing to do with range.So i will suggest answer as quicksort here as it is the most practical used algorithm
0
@rahul

can u chk my ans once
0
@ahwan

1 to k here index number of the array. That may be array element or maynot. That is not told in question
0
So, complexity should be nlogn
+1

Counting sort operate on k empty lists

but in this question asking about only k elements , then how counting sort will be answer?

Ref here

0
counting sort is applicable when we already know the range of the values of those elements which we have to sort but given question is not giving any information related to it . Then how counting sort is applicable here. anyone please explain.
use a hash map with chaining to sort all the numbers in $\mathcal{O}(n)$ time and constant space.
0
What would be the size of hash table...we have not given the value of k
+1
Even if we will use 'n' slots in hashing..... that mod n can send all value to one slot...irrespective of what is the value of k...  So hashing should not be used @Bikram Sir.
0
yes correct. hashing can not be used here.

Size for hash Table is n , it depends upon slots.
O(n) is the answer here .

Here k<= n . worst case k = n possible.
+1
@Bikrm Sir, how it can be done in O(n) ? No comparison based sorting can perform better than O(nlogn)..
Only counting, radix, bucket can do that..
But they are used for special cases .
For example counting can be used when the elements are in small range only.
So answer is O(n+m) where m is the maximum value.
So how it can be done in O(n)?
0
yes,  no comparison based sorting can perform better than O(nlogn).. but here in worst case you have to check all n elements right ? that's why O(n)

and in your answer from where ' m ' comes ? it is not mention in question.

say numbers are in this sequence given 1,3,6,3,6  then n=5 and k =3 so what is 'm 'here ? do you mean m= 6 here ?
0
yes sir, I mean m is the maximum element...
+1 vote

It is a sorted sequence. So we can write code like this

int distinctValue(int a[ ] , int n)
{
int k=0;
for(i=0 ; i<n ; i++)
{
for(j=0;j<n;j++)
{
if(a[i]!=a[j])
flag=1;
else
continue;
}
if(flag==1)
k++;
return k;
}
}


Here we are taking distinct values. i loop will take n values, among which j only taking the values, which have no repeated value. That means j taking the values which are non repeating or last element of input sequence

So, complexity must be $O\left ( n^{2} \right )$

But as every time we neednot compute full j loop. j loop will go until it gets a repeating value

So, i loop will go n iteration and j will iterate any thing less than equal to n iteration each time(say k)

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

edited by
+1
@ sreshta it is not sorted. there is a sequence of n numbers which has only k distinct numbers.

ex: 1,2,1,3,4,2,1,2,3, here n = 9 & k = 4
0
Answer must be O(n+k) as for any k distinct numbers k always < and equal to ( in worst case ) n .

By using counting sort it gives O(n+k)

But elements are not sorted , we need to make a sorted sequence.

1
2