Suppose we want to arrange n numbers stored in an array such that all negative value occur before the positive ones. What will be the minimum number of exchanges in the worst case ?
You can keep a pointer to the currently first positive value in the list, which initializes to 0. Then scan through the list, when you see a negative value swap it with the positive value, and increment your pointer.
You get O(n) swaps in the worst case.
If the first half is positive and second half is negative, you have to have at least n/2 swaps, as the second half needs to swap places with the first half.
To actually get n/2 swaps, you can first count the # of positive values, and if the positive values are greater, iterate the list in reverse order, and keep a pointer first negative value in the list. You can then stop if you have swapped all the positive or negative values.
For your point we will use Quick sort algorithm but only for one time (one pivot) and for the worst case it will take O(nlogn) as we find solution in the first step.