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 wrote:
> Question says without extra space how c
@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
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 wrote:
> Where do we store the sorted
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 wrote:
>
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 Te
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 wrote:
> @Shady Rows are already sorted ...
>
>
> On Wed, Jan 11, 2012 at 1:53 PM, shady wrote:
>
>> ^^ true, sort the rows and then a K-way merge.
>>
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 Gar
@Shady Rows are already sorted ...
On Wed, Jan 11, 2012 at 1:53 PM, shady wrote:
> ^^ true, sort the rows and then a K-way merge.
>
>
> On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal wrote:
>
>> I guess sort the array such that elements are sorted finally in such a
>> way that if we print them r
^^ true, sort the rows and then a K-way merge.
On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal wrote:
> 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
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 - 13611
"sort the whole matrix in ascending array" means?
can you please explain ?
On Wed, Jan 11, 2012 at 12:53 PM, atul anand wrote:
> 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.
>
>
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
12 matches
Mail list logo