Radix sort can solve the problem in O(N) time.
Max. value of input is N^2
so in binary representation, we need d = 2(logN)+1 digits to represent
each number. ( It is O(logN) - thats the key)
Now group logN bits ( say r = logN )
The maximum value in each group is O( 2^r) This is the base in which
There is one way in which we can do O(n).
Convert the numbers in base 'n'. [ O(n) ].
Now, there are 2-digit numbers, each digit ranging from 0 to n-1.
You can call count-sort 2 times (for each digit), so, complexity is O(n
+n) =O(n).
On Jun 27, 12:22 am, Dan dant...@aol.com wrote:
Your question
@radhakrishnan: Counting sort in this case, will be O(n2).. as it
involves traversing the entire array!
On Jun 26, 5:03 pm, L prnk.bhatna...@gmail.com wrote:
Count sort is O(n+k), since k~n^2 here, it will be O(N^2).
Radix sort has complexity O(r.n) which is nearly O(n logn).
Are you sure that
@L: It was asked if we could take advantage of the ranges of the
integers between 1-N^2..
I doubt if its possible.
On Jun 26, 5:33 pm, ross jagadish1...@gmail.com wrote:
@radhakrishnan: Counting sort in this case, will be O(n2).. as it
involves traversing the entire array!
On Jun 26, 5:03 pm,
@ross:
I guess the orignal problem is that there are N numbers which are all in the
range [1, N * N], can you do the sorting in O(N) time complexity?
If this is true, we can firstly do the discretization and then do the
counting sort.
--
You received this message because you are subscribed to
@Rujin Cao: Yea, your formulation of the problem is correct.. my bad,.
missed that there are N numbers.
can u elaborate more on the discretization procedure and how ll u do
counting sort (which might warrant traversing of N^2 elements)
On Jun 26, 5:45 pm, Rujin Cao drizzle...@gmail.com wrote:
@ross:
It seems that after discretization , the time complexity still would be
O(nlogn).
The discretization idea is:
say there are 4 numbers, each of them is in the range[1, 16].
e.g. 12 3 12 15
You can do one time transverse to map each of them to a global increasing
index (hashing is the
Use a radix sort.
Complexity of the radix sort is O(N k) where k is the number of digits used
to represent the number in some base b.
If we use the convenient fiction that both N and N^2 fit into the same 32
bit integer then
k is a constant and we get an O(N) sort. (It's kindof cheating :) ).
@Divye: Good theoretical proof and analysis as well.. As you
mentioned, this one works like charm for uniformly distributed
inputs :)
On Jun 26, 8:36 pm, DK divyekap...@gmail.com wrote:
Use a radix sort.
Complexity of the radix sort is O(N k) where k is the number of digits used
to represent
u can use radix sort
On Sun, Jun 26, 2011 at 9:44 PM, ross jagadish1...@gmail.com wrote:
@Divye: Good theoretical proof and analysis as well.. As you
mentioned, this one works like charm for uniformly distributed
inputs :)
On Jun 26, 8:36 pm, DK divyekap...@gmail.com wrote:
Use a radix
Your question is good for a classroom style discussion/debate.
However, in the real world, there is no simple answer.
There are lots of sorting algorithms. Each one has it's pros cons
and no single sorting algorithm is best, especially when not much is
known about the data to be sorted. In
11 matches
Mail list logo
