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