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!

• Raphael: This is an elementary exercise. What have you tried and where did you get stuck? Why do regular sorting algorithms not solve your problem?
• David Richerby: In particular, there are some very efficient sorting algorithms when you know that your array can only contain a limited number of different values.
• Embase: Im getting confused due to having to sort the booleans, ive only really thought of sorting integers at this point and its new to 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.

• Embase: thanks alot for this reply, i did not think about solving it this way but this makes alot of sense to me the way that you explained it