@darpan : storing the +ve and -ve numbers in a separate array and using it later for restoring the array will do the trick.
@bhaskar: if thee numbers are 0 & 1 then no extra space required else you need O(n) extra space. -- 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 Mon, Jul 2, 2012 at 8:35 AM, shiva@Algo <shiv.jays...@gmail.com> wrote: > * > while(A[j]<0&&i<=mid) > swap(A[j],A[i]) > i++ > j++ > > > On Mon, Jul 2, 2012 at 8:34 AM, shiva@Algo <shiv.jays...@gmail.com> wrote: > >> 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 < >> bhaskar.kushwaha2...@gmail.com> 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 <darpan.bav...@gmail.com> 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 <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. >>> > >>> > >>> >>> >>> -- >>> 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.
