I think O(N) space or O(nlogn) [stable nlogn sort : like stable merge sort
) time is required.
( I provided O(n^2) time and O(1) space before )
On Mon, Jul 2, 2012 at 10:24 AM, atul anand <atul.87fri...@gmail.com> wrote:
> @amol : even if your algo wont work for this...until and unless you use
> extra space...
> but your sorting algo is not working.
>
> 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.
>>
>
> --
> 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.
