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.
