Synopsys Question: Sort array which contains only 0 and 1.

Problem: Sort a given array which contains only 0 and 1.

Solution: Take two pointers; one from start and one from end. Move them towards each other until start is pointing to 1 and end is pointing to 0. In this case swap the elements.

Implementation:

void sortArray(int arr[], int len)
{
int l = 0; int r = len - 1;

while(l < r)
{
while(arr[l] == 0 && l < r)
++l;
while(arr[r] == 1 && l < r)
--r;
if(l < r)
{
std::swap(arr[l], arr[r]);
++l;
--r;
}
}
}

Complexity: O(n)