Sort booleans, O(N) time, O(1) space

Question

For a homework assignment, I am asked to sort an array of bools using a method that uses O(1) space, and O(N) time complexity. Can any hints be offered? I was thinking of something along the pivot method of a quicksort algorithm. -Thanks!

Answer 1

1. Keep an index at the front and back.
2. check the current front index, if it's false increment the front index
3. if it's true swap with the back index and decrement the back index
4. continue with steps 2 and 3 until front and back indices are equal to each other

Answer 2

If you have an array of booleans, you can simply count the true (or false) values. Lets assume this results to k. Then you set the first k elements of the array to true and the remaining false.

This algorithm iterates through the array twice (so it has an O(N) time complexity), and only uses one counter, so the space required is O(1).