[algogeeks] Merge unsorted arrays
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] 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.