A simple Divide and Conquer strategy can work Well
Seg_pos_neg(A,beg,end) //A is the array
->
mid=beg+end/2
if(beg<end)
Seg_pos_neg(A,beg,mid)
Seg_pos_neg(A,mid+1,end)
//if leftsubarray contains +ve no and right subarray -ve array,we
swap them
if(A[mid+1]<0)
j=mid+1
i=beg
while(A[i]<0&&i<=mid)
i++
while(A[j]<0&&i<=mid)
swap(A[j],A[i])
->
Running Time O(nlogn)
O(1) space
Correct me if I'm Wrong.....................
On Mon, Jul 2, 2012 at 7:53 AM, Bhaskar Kushwaha <
[email protected]> wrote:
> @amol u have used O(n) extra space!
> I think it's not possible without using extra space.
>
> On 7/2/12, Darpan Baweja <[email protected]> wrote:
> > @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 <[email protected]>
> > 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 <
> >> [email protected]> 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
> >>> <[email protected]>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
> >>>> <[email protected]>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 <
> >>>>> [email protected]> wrote:
> >>>>>
> >>>>>> @saurabh please provide the link to the post you are mentioning
> >>>>>>
> >>>>>> On Fri, Jun 29, 2012 at 8:38 PM, Bhaskar Kushwaha <
> >>>>>> [email protected]> 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 <
> >>>>>>> [email protected]> wrote:
> >>>>>>>
> >>>>>>>> This is a variant of that one
> >>>>>>>>
> >>>>>>>> ------------------------------
> >>>>>>>> *From:* saurabh singh <[email protected]>
> >>>>>>>> *To:* [email protected]
> >>>>>>>> *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 <
> >>>>>>>> [email protected]> 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 [email protected].
> >>>>>>>> To unsubscribe from this group, send email to
> >>>>>>>> [email protected].
> >>>>>>>> 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 [email protected].
> >>>>>>>> To unsubscribe from this group, send email to
> >>>>>>>> [email protected].
> >>>>>>>> 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 [email protected].
> >>>>>>>> To unsubscribe from this group, send email to
> >>>>>>>> [email protected].
> >>>>>>>> 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 [email protected].
> >>>>>> To unsubscribe from this group, send email to
> >>>>>> [email protected].
> >>>>>> 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 [email protected].
> >>>>> To unsubscribe from this group, send email to
> >>>>> [email protected].
> >>>>> 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 [email protected].
> >>>> To unsubscribe from this group, send email to
> >>>> [email protected].
> >>>> 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 [email protected].
> >>> To unsubscribe from this group, send email to
> >>> [email protected].
> >>> 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 [email protected].
> >> To unsubscribe from this group, send email to
> >> [email protected].
> >> 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 [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
