@RADHA..ya true...my bad i cudnt think dat way...but as pointed out by Sunny the sorted output cant be brought in O(n)...In order to get the sorted output only my algo took O(n^2)...tell me if I am missing anything...
On 7/8/11, sunny agrawal <[email protected]> wrote: > yes upto the step of swapping the elements it is O(m+n) > but if you need final arrays also sorted (Seems like that from your first > post)....it will go nlgn > > > On Fri, Jul 8, 2011 at 1:25 AM, radha krishnan <[email protected] >> wrote: > >> ok ! i got a O(n lgn) finally >> i don know exact complexity >> Let N = size of first array >> Find the first N smallest elements using one pointer in each array >> now swap the list of elements from index 0 to second-pointer in >> second array to first array >> with first_poiner+1 to N in first Array >> I think this is O(n) >> >> On Thu, Jul 7, 2011 at 12:53 PM, Piyush Sinha <[email protected]> >> wrote: >> > @radha...i have an algo but its complexity is O(n^2)...check the >> > following and see if there is any bug as I havent tested for all >> > cases...also suggestions are welcomed....:) >> > >> > main() >> > { >> > int a[]= {1,3,77,78,88}; >> > int b[]= {2,5,79,80,81,99}; >> > int i=sizeof(a)/sizeof(a[0]) - 1; >> > int j=sizeof(b)/sizeof(b[0]) - 1; >> > int temp,k,m; >> > while(j>=0) >> > { >> > if(a[i]>b[j]) >> > { >> > temp = a[i]; >> > k=m=i; >> > while(b[j]<a[k-1]) k--; >> > while(i-k) >> > { >> > a[i] = a[i-1]; >> > i--; >> > } >> > a[i] = b[j]; >> > b[j] = temp; >> > i = m; >> > } >> > j--; >> > } >> > for(k=0;k<sizeof(a)/sizeof(a[0]);k++) >> > printf("%d ",a[k]); >> > puts("\n"); >> > for(k=0;k<sizeof(b)/sizeof(b[0]);k++) >> > printf("%d ",b[k]); >> > puts("\n"); >> > system("pause"); >> > } >> > >> > >> > On 7/8/11, radha krishnan <[email protected]> wrote: >> >> :Given two sorted arrays a[]={1,3,77,78,90} and b[]={2,5,79,81}. Merge >> >> these two arrays, no extra spaces are allowed. Output has to be >> >> a[]={1,2,3,5,77} and b[]={78,79,81,90}. >> >> >> >> -- >> >> 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. >> >> >> >> >> > >> > >> > -- >> > *Piyush Sinha* >> > *IIIT, Allahabad* >> > *+91-8792136657* >> > *+91-7483122727* >> > *https://www.facebook.com/profile.php?id=100000655377926 * >> > >> > -- >> > 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. >> >> > > > -- > Sunny Aggrawal > B-Tech IV year,CSI > Indian Institute Of Technology,Roorkee > > -- > 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. > > -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=100000655377926 * -- 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.
