Given a list of elements which only has 0's and 1's in it. We have to sort the array in such a way that 0's comes left side of the array and 1's goes right side of the array.
For example:
If the array is
1 0 0 1 0 1 1
Then the result should be
For example:
If the array is
1 0 0 1 0 1 1
Then the result should be
0 0 0 1 1 1 1
Implementation:
#include <stdio.h>
#include <stdlib.h>
/* Swap function to swap the values by reference */
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
int main(void) {
int *a,i,n,l,r;
/* Get the number of elements of the array */
scanf("%d",&n);
/* Dynamically allocate the memory block for n integers and store the starting address of the block in a */
a=(int*)malloc(sizeof(int)*n);
/* Get the elements of the array */
for(i=0;i<n;i++)
scanf("%d",(a+i));
/* starting index of the array in l */
l=0;
/* Ending index of the array in r */
r=n-1;
/* While start pointer is less than end pointer */
while(l<r)
{
/* If the value in left side is 0, like where it is intended to be, we can skip to next element */
if(*(a+l)==0)
{
l++;
}
/* If the value in right side is 1, like where it is intended to be, we can skip to next element from the last */
else if(*(a+r)==1)
{
r--;
}
/* If both the above cases fail,
i.e., if we found 1 in left side and 0 in right side, swap the values
so that 0 comes left and 1 goes right */
else
{
swap((a+l),(a+r));
/* Increment l value and decrement r value */
l++;
r--;
}
}
/* Print the sorted array which has 0's in the left side and 1's in the right side */
for(i=0;i<n;i++)
printf("%d ",*(a+i));
return 0;
}