[algogeeks] Re: Merge unsorted arrays
how does ur algo produce sorted elements in final array?
On Jul 16, 3:55 pm, Ankur Khurana ankur.kkhur...@gmail.com wrote:
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.
Re: [algogeeks] Re: Merge unsorted arrays
you sort array before merging. and then use merge sort
On Sat, Jul 16, 2011 at 6:53 PM, noobcoder ase.as...@gmail.com wrote:
how does ur algo produce sorted elements in final array?
On Jul 16, 3:55 pm, Ankur Khurana ankur.kkhur...@gmail.com wrote:
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.
--
Ankur Khurana
Computer Science , 4th year
Netaji Subhas Institute Of Technology
Delhi.
--
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.
[algogeeks] Re: Merge unsorted arrays
@Aseem: Combine the arrays and sort the result. O(mn log mn). Dave On Jul 16, 4:13 am, 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.
Re: [algogeeks] Re: Merge unsorted arrays
It depends upon problem if n m, apply insertion sort for sorting m arrays because for smaller sublists insertion sort perform better then merge sort and then merge them all in mnlog(m) otherwise simply combine and apply merge sort or any other standard sorting algorithm On Sat, Jul 16, 2011 at 9:30 PM, Dave dave_and_da...@juno.com wrote: @Aseem: Combine the arrays and sort the result. O(mn log mn). Dave On Jul 16, 4:13 am, 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. -- Sanjay Ahuja, Analyst, Financing Prime Brokerage Nomura Securities India Pvt. Ltd -- 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.
