00110101

~~sortBinaryArray(binaryArray A):
start = 0
end = A.length() -1
while (start < end):
if (start == 0 && end == 0):
start++
if (start == 0 && end == 1):
start++
end--
if (start == 1 && end == 0):
//swap
A[start] = 0
A[end] = 1
start++
end--
if (start == 1 && end == 1):
end--~~

We can use bin sorting. We count the occurrences of numbers (0, 1 in this case) in a

`bin`

array. Then we just update the input array.
```
sortBinaryArray(binaryArray A):
bin = new int[2] //2 as 0, 1
for (i = 0; i < A.length(); i++):
bin[A[i]]++;
curr = 0
for (i = 0; i < bin.length(); i++):
for (j = 0; j < bin[i]; j++):
A[curr++] = i
```

Time efficiency is O(n) for n bits.

[Hat tip to MA]

Hi Rish, liked your explanation. Here is my code from http://k2code.blogspot.in/2010/04/sorting-binary-array.html:

ReplyDeletelow = 0;

high = arr.length - 1;

while (low < high) {

while (arr[low] == 0) {

low ++;

}

while (arr[high] == 1) {

high --;

}

if (low < low ) {

swap arr[low], arr[high]

}

}

that works too. i wanted to emphasize bin sorting.

Deletei know it is just a typo; your if condition should be 'if (low < high)'