*
while(A[j]<0&&i<=mid)
swap(A[j],A[i])
i++
j++
On Mon, Jul 2, 2012 at 8:34 AM, shiva@Algo <[email protected]> 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 <
> [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.
