@Hassan I think your algo will take time O(n^2) in worst case which occurs
when all elements are negative except the last one
@everyone Can we solve this problem in linear time?
On Fri, Jun 29, 2012 at 9:10 PM, Hassan Monfared <hmonfa...@gmail.com>wrote:
> Hi,
> this can be done by simple modification in bubble sort :
> void inplace_pos_neg(int pdata[],int sz)
> {
> bool changed=false;
> do
> {
> changed=false;
> for(int i=1;i<sz;i++)
> if(pdata[i-1]>0 && pdata[i]<0)
> {
> swap(pdata[i-1], pdata[i]);
> changed=true;
> }
> }while(changed);
> }
>
> void test_inplace_pos_neg()
> {
> int a[]={-1,-5,10,11,15,-500,200,-10};
>
> copy(a,a+sizeof(a)/sizeof(int),ostream_iterator<int>(cout,","));cout<<endl;
> inplace_pos_neg(a,sizeof(a)/sizeof(int));
>
> copy(a,a+sizeof(a)/sizeof(int),ostream_iterator<int>(cout,","));cout<<endl;
>
> }
>
>
> Regards
>
> On Fri, Jun 29, 2012 at 7:52 PM, utsav sharma <utsav.sharm...@gmail.com>wrote:
>
>> @bhaskar:- please explain stable sorting algorithm you would use(as
>> mainly all of them require extra space)
>> @sourabh:- that previous post discussion does't lead to any correct soln
>>
>> On Fri, Jun 29, 2012 at 8:39 PM, Bhaskar Kushwaha <
>> bhaskar.kushwaha2...@gmail.com> wrote:
>>
>>> @saurabh please provide the link to the post you are mentioning
>>>
>>> On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha <
>>> bhaskar.kushwaha2...@gmail.com> wrote:
>>>
>>>> If the order is important then I think we can use any stable sorting
>>>> algorithm with the following comparison function
>>>>
>>>> int compare (int a ,int b)
>>>> {
>>>> if((a>0&&b>0)||(a<0&&b<0)) return 0;
>>>> else return a<b;
>>>> }
>>>> On Fri, Jun 29, 2012 at 3:37 PM, raghavan M <
>>>> peacelover1987...@yahoo.co.in> wrote:
>>>>
>>>>> This is a variant of that one
>>>>>
>>>>> ------------------------------
>>>>> *From:* saurabh singh <saurab...@gmail.com>
>>>>> *To:* algogeeks@googlegroups.com
>>>>> *Sent:* Friday, 29 June 2012 3:05 PM
>>>>>
>>>>> *Subject:* Re: [algogeeks] MS Question: Segregrate positive and
>>>>> negative nos in array without changing order
>>>>>
>>>>> duplicate of a previous post.Kindly refer to that post.
>>>>> Saurabh Singh
>>>>> B.Tech (Computer Science)
>>>>> MNNIT
>>>>> blog:geekinessthecoolway.blogspot.com
>>>>>
>>>>>
>>>>>
>>>>> On Fri, Jun 29, 2012 at 10:41 AM, raghavan M <
>>>>> peacelover1987...@yahoo.co.in> wrote:
>>>>>
>>>>> Hi
>>>>> Question as in subject
>>>>>
>>>>> *No extra space (can use one extra space)-O(1) max
>>>>> *No order change allowed
>>>>> example:
>>>>>
>>>>> input : 1,-5,2,10,-100,-2
>>>>> output: -5,-10,-100,1,2
>>>>>
>>>>> input : -1,-5,10,11,15,-500,200,-10
>>>>> output : -1,-5,-10,-500,-10,10,11,15
>>>>>
>>>>>
>>>>> Thanks
>>>>> Raghavn
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> regards,
>>>> Bhaskar Kushwaha
>>>> Student
>>>> Final year
>>>> CSE
>>>> M.N.N.I.T. Allahabad
>>>>
>>>>
>>>
>>>
>>> --
>>> regards,
>>> Bhaskar Kushwaha
>>> Student
>>> Final year
>>> CSE
>>> M.N.N.I.T. Allahabad
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Utsav Sharma,
>> NIT Allahabad
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
