Do You Know Your Sorting?

Computer Science Level 1

Let k k be a fixed constant. You are given a set of n n positive integers less than k k , and you are tasked to sort it.

Which of the following is the asymptotic running time of the fastest possible algorithm?

Θ ( n lg ⁡ n ) \Theta(n \lg n) Θ ( n ) \Theta(n) Θ ( 1 ) \Theta(1) Θ ( lg ⁡ n ) \Theta(\lg n)

View wiki
Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

[Partial Solution]

Use Counting Sort .

First, read the stream of the values and generate a histogram. Then use the histogram to determine the value in each position.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

it should be o(n+k)???

A Steven Kusuman - 5 years, 3 months ago

Log in to reply

Yes, I believe the OP should correct the question. https://en.wikipedia.org/wiki/Counting_sort

Isay Katsman - 5 years, 3 months ago

Yes, but k is a constant. So it is insignificant ( falls away ) in time complexity analysis (asymptotically).

Jason Smythe - 4 years, 3 months ago

Log in to reply

A constant in the counting sort if it's significantly greater than n, the sorting will cost you O(n+k). My counter example to your solution to prove it's wrong is the following: k = 100 n = 10 So k it's n^2 and if we have O(n+n^2) = O(n^2) = O(k).

If you want to make this solution O(n) I think you should say that the set of n elements are all less than k BUT n it's the same order of k (but even here you should consider the space required by k).

In conclusion, I would use counting sort for example if n log2(n) > k: for example n = 10 like above 10 log2(10) = 33 if k was 50 than you should consider using other algorithms than counting sort

Bogdan Surel - 3 years ago

O(n+k) is the same as O(n) considering that k is a fixed constant much less than infinity?

Raivat Shah - 2 years, 3 months ago

use index sort. Read the input and put each input number such as i in the index of i of the input array.

0 Helpful 0 Interesting 0 Brilliant 1 Confused

First, declare arrays b and s of size k and n respectively, both containing only zeros.

Next, calculate (a mod(k)) for each element a in the given array. The resulting number will be in the range of 0 to k-1, and will be the index of a in the array b. This takes n operations. After this, traverse b, take each nonzero element, and put it in the sorted array s. This will take at most k operations. So the full algorithm takes n+k operations.

Susmit Islam - 10 months, 3 weeks ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...