@nishant: I think this won't work in all the cases as you said in a
statement: "one or two element won't be at correct positions.." there
might be more in other cases unless you prove it somehow. what if
array is too large and there are too many elements not at correct
position after second pass.
On Sun, May 26, 2013 at 8:55 PM, Ankit Agarwal <ankuagarw...@gmail.com> 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
> <nishant.bits.me...@gmail.com> 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 <bagana.bharatku...@gmail.com>
>> 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 algogeeks+unsubscr...@googlegroups.com.
>>>
>>>
>>
>>
>> --
>> 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 algogeeks+unsubscr...@googlegroups.com.
>>
>>
>
>
>
>
> --
>
> 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 algogeeks+unsubscr...@googlegroups.com.
>
>
--
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 algogeeks+unsubscr...@googlegroups.com.
