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)'