C++ Question

How to sort a Boolean array in one iteration of the array(traverse only once through the array)?

I want to sort a boolean array in one iteration. I am trying to do this from C++. I try to do this by initialize a new array then append False values to end of the array and true values to start of the array. But I'm struggling with how to append data without overwriting in C++. Is there any better algorithm to do this please enlighten me.

Answer

I would scan through the array with two pointers: one starting from the beginning, and the other from the end. As each pointer walks toward the middle of the array, check whether the values are out of order, and if they are, swap them. When/where the pointers meet, the values are in order.

Note that unlike swapping most other types of values, in this case there's no need to do a typical swap where you copy values around. Let's assume for the moment that you're sorting so all the true values come first, and all the false values second. In this case, if you have to values out of order, it can only be a false coming before a true, and when they're swapped, it can only be a true coming before a false. Rather than a typical swap, you're just looking for a false on the left and a true on the right, and when you find them, you assign true on the left and false on the right.

If you want the output in a separate array, you can take a slightly simpler approach: walk through the input array from beginning to end. For each true you find, set the next value in the output array to true and advance to the next position. When you reach the end of the input array, set the remainder of the values in the output to false:

// ...
for (bool *b = input; b != input_end; ++b)
    if (*b)
       *out++ = true;
while (out != output_end)
    *out++ = false;

This assumes you want true sorted before false. If you want to reverse that, you change if (*b) to if (! *b) and *out++ = false to *out++ = true;.