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.