Sorting an array of boolean values

Question

im looking for some guidance on how to get started with sorting an array of booleans so that the falses would be in front of the trues.

so if given this: a = {true, true, false, true, false}

it would return: a = {false, false, true, true, true}

here is the exact question: Suppose you have an array of booleans of size n. Give an algorithm that sorts the array so that all false elements come before all true elements.

Thanks for any help you can give me!

Answer 1

With only 2 possible values, you want to use an algorithm such as Counting Sort.

Since you only have 2 possible values, true and false, it's easy to just count how many true/false values you have. But to be more efficient, you can just count how many trues you have (or falses) instead. Because size - numTrue = numFalse.

Answer 2

You can do this in linear time.

Algo:
1. Initialize an another array of same size(n) lets name it A[n].
1a. countF = 1 and countT = 1
2. Loop over elements with i going from 1:n on the original array lets name it B:
2a. If B[i] = false, then A[countF] = false and increment countF
2b. If B[i] = true, then A[n-countT + 1] = true and increment countT
3.END

And in the array A, you have the answer. Here, its done in one scan but with a space overhead of n

Note another way, would to scan over the array and count the number of False and True. And on another run over the array you put False from starting to the count of False in original array and True in the remaining places. This method requires two runs over the array but with no overhead of spaces.