Watch it ...

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+12 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.

+12 votes

+5

" *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.

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 .

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 .

So answer is O(n+k)

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 .

So answer is O(n+k)

+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

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

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

@ahwan

1 to k here index number of the array. That may be array element or maynot. That is not told in question

1 to k here index number of the array. That may be array element or maynot. That is not told in question

+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

+3 votes

+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.

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)?

Please help.

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)?

Please help.

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 ?

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 ?

+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 )$

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 553
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,913 questions

52,293 answers

182,250 comments

67,738 users