I consider following problem:It is given array with numbers, for example $[-2,0,1,-324,213,321,-2]$.The problem is: replace elements such that negative numbers precede the non-negative. For our example: $[-2, -324, -2, 321,0,213,1]$.Additional requirement is that algorithm should do minimal number of replacements.   My approachLet's use partition from qsort algorithm - pivot is always $0$. It does $\lfloor n/2\rfloor $ replacements.I think that it is minimal number. It is because of pesimistic case:$|[1,1,..,1,-1,-1,...-1]|=n$  - in this case we must do at least $\lfloor n/2\rfloor $ replacements.   Can you give me algorithm that do less than $\lfloor n/2\rfloor$ replacements ? 
Partition array - elements non-negative and negative. Minimal number of replacements of elements
algorithms;arrays;lower bounds