^^ true, sort the rows and then a K-way merge.
On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal sanjay.raj...@live.inwrote:
I guess sort the array such that elements are sorted finally in such a way
that if we print them row by row, the result is a sorted array.
K-way merge can be useful.
*
@Shady Rows are already sorted ...
On Wed, Jan 11, 2012 at 1:53 PM, shady sinv...@gmail.com wrote:
^^ true, sort the rows and then a K-way merge.
On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal sanjay.raj...@live.inwrote:
I guess sort the array such that elements are sorted finally in such
But the question says without extra space ? How do we do that without space
?
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Wed, Jan 11, 2012 at 12:24 AM, Ankur
If we use K merge I think the time complexity would be nm lognm
I think we must try doing in O(m*n)
On Wed, Jan 11, 2012 at 1:54 PM, Ankur Garg ankurga...@gmail.com wrote:
@Shady Rows are already sorted ...
On Wed, Jan 11, 2012 at 1:53 PM, shady sinv...@gmail.com wrote:
^^ true, sort the
How can it be mn log mn ?
it will be O(mn) as we elements are sorted, we simply pick minimum at each
iteration of the loop. Since there are mn elements, so complexity will be
O(mn).
Correct me if m wrong.
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of
Where do we store the sorted list ? How do we do it in place ?
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Wed, Jan 11, 2012 at 12:34 AM, Sanjay Rajpal
Question says without extra space how can you sort it using K way merge.
eg:-
input:-
1 3 4 8 9
2 5 18 25 50
6 7 22 45 55
output:-
12 3 45
67 8 9 18
22 25 45 50 55
On Wed, Jan 11, 2012 at 2:05 PM, Sanjay Rajpal sanjay.raj...@live.inwrote:
Where do
@Lucifer : I came up with a similar algorithm as yours but I dont
understand your complexity analysis : sum over all i (1 to M} { i*(M+N-i)
} .
Shouldnt it be M * sum over all i(1 to N) {(M+N-i)} ? M= no of
columns, N= no of rows . Since we always have the min element at the 0th
column of
only reason for considering k way merge was to do it O(n*m) time,
but currently i am having problem merging even two sorted arrays in time
linear to the sum of their size without extra space. any help ?
On Wed, Jan 11, 2012 at 2:30 PM, atul anand atul.87fri...@gmail.com wrote:
Question says
Given 2D array.
The rows are sorted in ascending order and the colums are sorted in
ascending order.
We have to sort the whole matrix in ascending array.
We cannot use extra space.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
sort the whole matrix in ascending array means?
can you please explain ?
On Wed, Jan 11, 2012 at 12:53 PM, atul anand atul.87fri...@gmail.comwrote:
Given 2D array.
The rows are sorted in ascending order and the colums are sorted in
ascending order.
We have to sort the whole matrix in
I guess sort the array such that elements are sorted finally in such a way
that if we print them row by row, the result is a sorted array.
K-way merge can be useful.
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra -
12 matches
Mail list logo
