@Ravindra: Since both the array contain m elements, you can assume that all elements lie from index [0] to index [m-1] However, because in your example we can consider 0, as a valid value of the sorted array.
PS: Still, if you are suggesting that we should not consider 0 as a value. Then you can perform an compaction operation on 2nd array. Regards, Sandeep Jain On Wed, Jul 13, 2011 at 10:18 PM, ravindra patel <[email protected]>wrote: > @Bittu, Vaibhav > Can you please illustrate your algo for below arrays. > > Array1 - {1, 3, 5, 7} > Array2 - {0,0,0,2,0,4,6,8} > > > Thanks, > - Ravindra > > > > On Wed, Jul 13, 2011 at 9:47 PM, vaibhav shukla > <[email protected]>wrote: > >> start from the end of both the arrays... and try simple merge process not >> from the start but from where the last element is... and keep inserting the >> greater element at the end of the larger array. >> >> >> On Wed, Jul 13, 2011 at 8:41 PM, bittu <[email protected]>wrote: >> >>> @dumanshu check it >>> >>> Algo is simply start putting elemnt in bigger array by comparing then >>> from last logic is same as merge part of merg sort :) >>> >>> void merge(int[] a, int[] b, int n, int m) >>> { >>> int k = m + n - 1; // Index of last location of array b >>> int i = n - 1; // Index of last element in array b >>> int j = m - 1; // Index of last element in array a >>> >>> // Start comparing from the last element and merge a and b >>> while (i >= 0 && j >= 0) >>> { >>> if (a[i] > b[j]) >>> { >>> a[k--] = a[i--]; >>> } >>> else >>> { >>> a[k--] = b[j--]; >>> } >>> } >>> >>> while (j >= 0) >>> { >>> a[k--] = b[j--]; >>> } >>> >>> //no need to do for a array as its alraedy filled in B array :) >>> >>> } >>> Time O(N) >>> >>> Thanks >>> Shashank Mani Narayan >>> Computer Science & Engg. >>> Birla Institute of Technlogy Mesra >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> best wishes!! >> Vaibhav Shukla >> DU-MCA >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
