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.

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;`.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download