Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other
// without keep the order
void rearrange(int A[], int N) {
int low = 0, high = N-1;
while(low < high) {
while(low < N && A[low] < 0) low++;
if(low == N) return;
while(high >= 0 && A[high] > 0) high--;
if(high < 0) return;
swap(A[low], A[high]);
low++;
high--;
}
}
// keep the order
void rearrange(int A[], int N) {
int *B = new int[N];
int j=0;
for(int i=0; i<N; i++)
if(A[i] < 0) B[j++] = A[i];
for(int i=0; i<N; i++)
if(A[i] > 0) B[j++] = A[i];
for(int i=0; i<N; i++)
A[i] = B[i];
delete [] B;
}