Thursday, July 17, 2008

Sorting a binary array

Quickly - how do you sort this binary array?

00110101

Let's have two pointers as start and end. There are only four possibilities. When start = 1 and end = 0, you actually sort by swapping the bits. Rest is just adjusting the pointers. You can shorten the code at the cost of readability.

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]

2 comments:

  1. Hi Rish, liked your explanation. Here is my code from http://k2code.blogspot.in/2010/04/sorting-binary-array.html:
    low = 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]
    }
    }

    ReplyDelete
    Replies
    1. that works too. i wanted to emphasize bin sorting.

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

      Delete