Partition array - elements non-negative and negative. Minimal number of replacements of elements
Hint: 

Create a new array $B=[]$ where $B[i]=1$ if  $A[i]&lt;0$ and $2$ elsewhere.
You can prove that sorting $B$ is same as performing said operation on $A$

So now, We have to sort an array which only contains two values.
You can do this by a greedy algorithm, whose proof you can obtain by the principle of Induction.

As an extra hint: Let $B=[1.....1,2.....2,1,........]$. where  C is another segment of the array. You have to do something now.

Trust me this is great help. You can continue from here.

As for why it requires fewer(or equal) than $n/2$. The proof is quite easy, once you've devised the algorithm.