@atul... can u point out where sorting is not working ? any case ? --
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 12:12 PM, Hassan Monfared <hmonfa...@gmail.com>wrote: > 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. > -- 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.
