This is a simple program so let's code it.
#include<stdio.h>
void moveToEnd(int arr[],int n)
{
int pos=0,i=0;
while(i<n)
{
if(arr[i]!=0)
arr[pos++]=arr[i++];
else
i++;
}
while(pos<n)
arr[pos++]=0;
}
int main()
{
int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
int n,i;
n=sizeof(arr)/sizeof(arr[0]);
moveToEnd(arr,n);
for(i=0;i<n;i++)
printf(" %d",arr[i]);
return 0;
}
#include<stdio.h>
void moveToEnd(int arr[],int n)
{
int pos=0,i=0;
while(i<n)
{
if(arr[i]!=0)
arr[pos++]=arr[i++];
else
i++;
}
while(pos<n)
arr[pos++]=0;
}
int main()
{
int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
int n,i;
n=sizeof(arr)/sizeof(arr[0]);
moveToEnd(arr,n);
for(i=0;i<n;i++)
printf(" %d",arr[i]);
return 0;
}
This solution is optimized and it is often hard for newcomers to understand it.
ReplyDeleteYou can reach the same solution by starting with inductive hypothesis that subarray can be kept solved at all time, and then extending the subarray one element at the time and preserving the correct state. Later on, the inductive hypothesis can be relaxed and let the array be brought back into correct state after the whole operation.
You can find the whole explanation and intermediate solutions here: http://www.codinghelmet.com/?path=exercises/moving-zeros-to-end-of-array