#include <bits/stdc++.h>
using namespace std;
// Function to sort binary array in linear time
int Partition(int A[], int n)
{
int pivot = 0;
int j = 0;
// each time we encounter a 0, j is incremented and
// 0 is placed before the pivot
for (int i = 0; i < n; i++)
{
if (A[i] > pivot)
{
swap(A[i], A[j]);
j++;
}
}
}
// main function
int main()
{
int A[] = { 1, 0, 0, 0, 1, 0, 1, 1 };
int n = sizeof(A)/sizeof(A[0]);
Partition(A, n);
// print the rearranged array
for (int i = 0 ; i < n; i++)
cout << A[i] << " ";
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBGdW5jdGlvbiB0byBzb3J0IGJpbmFyeSBhcnJheSBpbiBsaW5lYXIgdGltZQppbnQgUGFydGl0aW9uKGludCBBW10sIGludCBuKQp7CiAgICBpbnQgcGl2b3QgPSAwOwogICAgaW50IGogPSAwOwogCiAgICAvLyBlYWNoIHRpbWUgd2UgZW5jb3VudGVyIGEgMCwgaiBpcyBpbmNyZW1lbnRlZCBhbmQKICAgIC8vIDAgaXMgcGxhY2VkIGJlZm9yZSB0aGUgcGl2b3QKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQogICAgewogICAgICAgIGlmIChBW2ldID4gcGl2b3QpCiAgICAgICAgewogICAgICAgICAgICBzd2FwKEFbaV0sIEFbal0pOwogICAgICAgICAgICBqKys7CiAgICAgICAgfQogICAgfQp9CiAKLy8gbWFpbiBmdW5jdGlvbgppbnQgbWFpbigpCnsKICAgIGludCBBW10gPSB7IDEsIDAsIDAsIDAsIDEsIDAsIDEsIDEgfTsKICAgIGludCBuID0gc2l6ZW9mKEEpL3NpemVvZihBWzBdKTsKIAogICAgUGFydGl0aW9uKEEsIG4pOwogCiAgICAvLyBwcmludCB0aGUgcmVhcnJhbmdlZCBhcnJheQogICAgZm9yIChpbnQgaSA9IDAgOyBpIDwgbjsgaSsrKQogICAgICAgIGNvdXQgPDwgQVtpXSA8PCAiICI7CiAKICAgIHJldHVybiAwOwp9