2-color dithering

Question

I have an array of containing a mixture of 0s and 1s. I want to rearrange the contents of the array so that as many even positions in the array contain 0 and odd positions contain 1 as possible, subject to the constraint that the number of 0s and 1s are unchanged. This means that if the number of 0s exceeds the number of 1s or vice versa then there will a block at the end of the rearranged array consisting of all-0s or all-1s. How can I do this in one pass, modifying the array in place?

For example:

Input:  {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
Output: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1}

Answer 1

You can just use the standard two-color sort algorithm for this; just edit the array references to map accesses to the first half of the array to even elements in your actual array, and accesses to the second half of the array to odd elements in your actual array (backwards). Basically, a[i] becomes (assuming size is even):

a[i < size/2 ? i * 2 : (size - i) * 2 - 1]