@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].
