well doing it in O(n) is a research problem... stackoverflow.com/questions/15400585/in-place-sort-an-array-with-2-sorted-sub-arrays
it's not that easy... for given problem quicksort or heapsort would work fine... On May 27, 2013 7:48 PM, "bharat b" <[email protected]> wrote: > @Nishan : > For the given example, the number of elements which are not in order may > be less ..can u prove this ? > And also, how can u place an incorrect positioned number at correct > position ---> takes O(n) for each number .... > > > On Sun, May 26, 2013 at 8:55 PM, Ankit Agarwal <[email protected]>wrote: > >> The first pass is not necessary. We can finding the middle element as >> follows: >> >> N = even, Range [ 0 - (N/2 - 1) ] & [ N/2 - (N - 1) ] >> >> N = odd, >> if (A[N/2] > A[N/2 -1]) Range [ 0 - N/2 ] & [ (N/2 + 1) - >> (N - 1) ] >> >> else if ( A[N/2] < A[N/2 + 1]) Range [ 0 - (N/2 - 1) ] & [ >> N/2 - (N - 1) ] >> >> >> >> >> >> On Sun, May 26, 2013 at 8:28 PM, Nishant Pandey < >> [email protected]> wrote: >> >>> The solution could be given in this way. >>> >>> 1) In one pass get the end index of both array says e1 and e2. >>> 2) now in next pass compare elements at e1 and e2 . >>> a) if a(e1) > a(e2) swap the elements and then decreament e1 and e2 >>> both. >>> b) if a(e1) < a(e2) decreament e2. >>> c) if a(e1) == a(e2) then swap a(e1) with a(e2-1) and then decrement >>> e1 by1 and e2 by 2. >>> >>> After this pass there may be one or two element not at coret position, >>> so their position can be placed just by shifting in elements in another >>> pass. >>> >>> So as a total it would be O(n) but it requires 3 passes. >>> >>> >>> If some one is having something better tan this, please suggest. >>> >>> >>> >>> On Sun, May 26, 2013 at 6:46 PM, bharat b >>> <[email protected]>wrote: >>> >>>> An array is given, first and second half are sorted .. Make the array >>>> sorted inplace... Need an algo better than O(n^2).. >>>> If the length of the array is odd.. middle is either in first half or >>>> second half. >>>> Ex: >>>> 1. Arr[] = {2,3,6,8,-5,-2,3,8} --> output : Arr[]={-5,-2,2,3,3,6,8,8}; >>>> 2. Arr[] = {2,3,6,8,-5,-2,3} --> output : Arr[]={-5,-2,2,3,3,6,8}; >>>> 3. Arr[] ={2,3,6,-5,-2,3,8} --> output : Arr[]={-5,-2,2,3,3,6,8}; >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to [email protected]. >>>> >>>> >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> >>> >>> >> >> >> >> -- >> >> *Ankit Agarwal* >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> >> >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
