#include <stdio.h>

#include <stdlib.h>

int main()

{

int i=0,length;

printf("Enter input size\n");

scanf("%d",&length);

int *arr=(int *)malloc(sizeof(int)*length);

printf("Enter %d inputs\n",length);

for(i=0;i<length;i++){

printf("%d: ",i+1);

scanf("%d",(arr+i));

}

printf("\nInput Given: ");

for(i=0;i<length;i++){

printf("%d ",arr[i]);

}

moveAllNegativesAtLeft(arr,length);

printf("\nOutput:");

for(i=0;i<length;i++){

printf("%d ",arr[i]);

}

return 0;

}

void moveAllNegativesAtLeft(int *arr,int length){

int left=0,right=length-1,temp,nofExch=0;

// While Loop Invariants:

//1. If left>0 then, Arr[0] to Arr[left-1] are all negative numbers

//2. If right<length-1 then, Arr[right-1] to Arr[length-1] are all positive numbers.

while(left<right){

for(;left<length;left++){

if(arr[left]>=0)

break;

}

for(;right>=0;right--){

if(arr[right]<0)

break;

}

if(left<right){

temp=arr[left];

arr[left]=arr[right];

arr[right]=temp;

right--;

left++; //After each exchange right variable decreases by one

nofExch++; //and left variable increases by one

//and while loop runs until left<right, hence at max n/2 exchanges are possible

}

}

printf("\nTotal Number of Exchanges: %d",nofExch);

}