@amol :- i don't think this algo would work here
after sorting how would you replace back the original no.s(as no.s are not
0 and 1 in this case)
On Sun, Jul 1, 2012 at 11:08 PM, Amol Sharma <amolsharm...@gmail.com> wrote:
> i think it has been discussed before....nevertheless here is the required
> linear time solution.
>
> first, count the total number 0's and 1's in the array.
>
> let say, total elements are n and there are x zero's.
>
> take count1=0 and count2=x;
>
> traverse through the array :
> for(i=0;i<n;i++)
> if(arr[i]==0)
> arr[i]=count1++;
> else
> arr[i]=count2++;
>
> let's say array is {1,0,0,0,1,1,1,0,0,1} n=10,x=5
> count1=0;count2=5
>
> after the traversal it becomes a[]={5,0,1,2,6,7,8,3,4,9}
>
> now sort this array in O(n) like this :
>
> for(j=0;j<=1;j++)
> {
> for(i=0;i<n;i++)
> {
> if(arr[i]!=i)
> swap(arr[i],arr[arr[i]]);
> }
> }
>
> after the array is sorted again traverse the array and set the elements
> from index 0 to x-1 to '0' and rest '1'.
>
>
>
>
>
>
>
>
> --
>
>
> Amol Sharma
> Final Year Student
> Computer Science and Engineering
> MNNIT Allahabad
>
> <http://gplus.to/amolsharma99>
> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/><http://facebook.com/amolsharma99>
>
>
>
>
>
>
> On Fri, Jun 29, 2012 at 9:20 PM, Bhaskar Kushwaha <
> bhaskar.kushwaha2...@gmail.com> wrote:
>
>> @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.
>>
>
> --
> 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.
>
--
*DARPAN BAWEJA*
*3rd year, I.T*
*MNNIT 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.
