@all :- by segregating 0 and 1 or by taking quicksort approach
we have to swap no.s resulting which array becomes unordered.
my approach is start from right and if a negative no. occurs insert it
into another array temp[]
this will shift all positive no.s to right and in 2nd pass start from left
of original array and insert all the elements of temp.
time comp-O(n), space comp-O(n)
correct me if i am wrong
On Thu, Jun 14, 2012 at 1:53 PM, saurabh singh <saurab...@gmail.com> wrote:
> Order may not be maintained necessarily by this solution
>
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT
> blog:geekinessthecoolway.blogspot.com
>
>
>
> On Thu, Jun 14, 2012 at 1:47 PM, Manikanta Babu <manikantabab...@gmail.com
> > wrote:
>
>> Check this out, it works in O(n);
>>
>> int i = 0;
>> int j = n-1;
>>
>> while((i<n && j>= 0)&&(i<j))
>> {
>> if(a[i]>0 && a[j]<0)
>> {
>> swap(a[i],a[j]);
>> i++; j--;
>> }
>> else
>> {
>> if(a[i]<0)
>> i++;
>> if(a[j]>0)
>> j--;
>> }
>>
>> }
>>
>> Thanks,
>> Mani
>>
>> On Thu, Jun 14, 2012 at 1:05 PM, Mad Coder <imamadco...@gmail.com> wrote:
>>
>>>
>>> As nothing is written about space complexity, I am assuming that we can
>>> take extra space.
>>>
>>> Take a temporary array of length n.
>>>
>>> 1. Maintain a counter for the length of temporary array filled till now.
>>>
>>> 2. Traverse the given array. If value contained is negative insert it in
>>> new array and update counter. After complete traversal all negative values
>>> will be in the temporary array.
>>>
>>> 3. Traverse again the given array. Repeat step 2 but this time for
>>> positive numbers.
>>>
>>> Finally temporary array contains the required answer. If required copy
>>> it into original array.
>>>
>>> As this approach takes max. 3 traversals so its complexity is O(n).
>>>
>>> --
>>> 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.
>>>
>>
>>
>>
>> --
>> Thanks & Regards,
>> Mani
>> http://www.sanidapa.com - The music Search engine
>>
>> --
>> 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.
>
--
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.
