#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);
}