Re: [algogeeks] Merge unsorted arrays
Use divide and conquer. take 2 array at a time and .so you are merging two
array at a time.
num_of_list=m;
length of list=n;
while(num_of_list 1)
{
while( (num of list where length = length_of_list) 2)
{
merge two lists of length (length_of_list);
}
if(num_of_list %2==0)
num_of_list/=2;
else
num_of_list/=2+1;
length of list=n;
}
(it is just a general idea , you have to take care of the left over list
every time , the check for that i havent posted)
so time complexity is
2*n* (m/2) + 2* 2n* (m/4) .. log(m) times.
so complexity is n*m*log(m)
On Sat, Jul 16, 2011 at 2:43 PM, aseem garg ase.as...@gmail.com wrote:
Q2. Given m arrays of n size each, give an algorithm to combine these
arrays into a single array with sorted elements. Also tell the time
complexity of your solution.
Aseem
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Merge unsorted arrays
sort all the arrays first O(nlogn)
then use merge sort
On Sat, Jul 16, 2011 at 3:43 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote:
Use divide and conquer. take 2 array at a time and .so you are merging two
array at a time.
num_of_list=m;
length of list=n;
while(num_of_list 1)
{
while( (num of list where length = length_of_list) 2)
{
merge two lists of length (length_of_list);
}
if(num_of_list %2==0)
num_of_list/=2;
else
num_of_list/=2+1;
length of list=n;
}
(it is just a general idea , you have to take care of the left over list
every time , the check for that i havent posted)
so time complexity is
2*n* (m/2) + 2* 2n* (m/4) .. log(m) times.
so complexity is n*m*log(m)
On Sat, Jul 16, 2011 at 2:43 PM, aseem garg ase.as...@gmail.com wrote:
Q2. Given m arrays of n size each, give an algorithm to combine these
arrays into a single array with sorted elements. Also tell the time
complexity of your solution.
Aseem
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Merge unsorted arrays
oops , didnt see the unsorted thing. complexity is mnlog(n) + mn log(m)
On Sat, Jul 16, 2011 at 4:23 PM, sagar pareek sagarpar...@gmail.com wrote:
sort all the arrays first O(nlogn)
then use merge sort
On Sat, Jul 16, 2011 at 3:43 PM, Ankur Khurana
ankur.kkhur...@gmail.comwrote:
Use divide and conquer. take 2 array at a time and .so you are merging two
array at a time.
num_of_list=m;
length of list=n;
while(num_of_list 1)
{
while( (num of list where length = length_of_list) 2)
{
merge two lists of length (length_of_list);
}
if(num_of_list %2==0)
num_of_list/=2;
else
num_of_list/=2+1;
length of list=n;
}
(it is just a general idea , you have to take care of the left over list
every time , the check for that i havent posted)
so time complexity is
2*n* (m/2) + 2* 2n* (m/4) .. log(m) times.
so complexity is n*m*log(m)
On Sat, Jul 16, 2011 at 2:43 PM, aseem garg ase.as...@gmail.com wrote:
Q2. Given m arrays of n size each, give an algorithm to combine these
arrays into a single array with sorted elements. Also tell the time
complexity of your solution.
Aseem
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
