Lets the array A of size n be given as input (we assume that 0 isnt present as only positive and negative integers are considered)
Swap(x,y) swaps the value of x and y in O(1)
- Set int i to 0
- while(A[i] < 0) i = i+1; // this is to ensure that i is set to first positive number appearing in array
- Set j to i
while(j<n){
if( A[j]<0) {swap(A[i],A[j]); i++;}
else j++;
}
the loop checks if A[j] is less than 0 or not, when negative it swaps and increments the i which moves to next position and if positive i stays while j is incremented.
this runs till the end of array. the whole algo takes order of n.