CODEWITHSUNDEEP
c++arrayssorting
Tharindu Ramesh Ketipearachchi
Tharindu Ramesh Ketipearachchi

Reputation: 3

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.

Upvotes: 0

Views: 1458

Answers (4)

Aniruddha Bera
Aniruddha Bera

Reputation: 415

Counting the number of true/false values always does the trick. Something like this.

int main()
{
int a[]={1,0,1,1,0,1,1,0,1,0,0,1,0};
int size=sizeof(a)/4,count1=0,i;

for(i=0;i<size;i++)
    if(a[i]==1)
        count1++;

for(i=0;i<size;i++)
{
    if(i<count1)
        a[i]=1;
    else
        a[i]=0;

    printf("%d ",a[i]);
}
return 0;
}

Upvotes: 0

Jerry Coffin
Jerry Coffin

Reputation: 490338

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

Upvotes: 2

kamaless
kamaless

Reputation: 1

or just count trues and overwrite the array with trues * count and falses *(size - count) depending on your sorting order

Upvotes: 0

mooiamaduck
mooiamaduck

Reputation: 2156

If you're sorting an array of booleans in-place, all you need to do is to loop through the array and swap out any false values you see with a value from the end of the array (using a decrementing counter) (or swap out the true values, if in your definition true comes after false).

void function sort(const bool *array, int n) {
  int i = 0, j = n - 1;
  while(i <= j) {
    if(array[i] == false) {
      bool temp = array[i];
      array[i] = array[j];
      array[j] = temp;
      --j;
    } else {
      ++i;
    }
  }
}

Upvotes: 0

Related Questions