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" <bagana.bharatku...@gmail.com> 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 <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.
>
>
>
--
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.
