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]

No comments:

Post a Comment