Highly optimized algorithm for sorting an array consisting of only 0s n 1s

Question

I need to find an optimized algorithm for sorting an array consisting of only 0s n 1s.

My version of the solution is to count no. zeros (say x) and ones (say y). Once you do, put x zeroes in an array, followed by y 1s. This makes it O (n).

Any algorithm that works better than this? I was asked this question in an interview.

Answer 1

Since you need to study each of the input elements n , you cannot improve O(n) .

Also, since your algorithm requires O(1) memory, you cannot improve this (nothing asymptotically better than O(1) ).

Answer 2

we can't do better than O (n), but it looks like we can do in one go

 low = 0; high = arr.length - 1; while (low < high) { while (arr[low] == 0) { low ++; } while (arr[high] == 1) { high --; } if (low < high) { //swap arr[low], arr[high] } } 

Answer 3

If you are summing an array, you can have the number 1, a little more efficient, but still O (n).

Answer 4

You cannot be more efficient than O (N), because every element needs to be checked.

Answer 5

What array are we talking about? If we were counting bits in a 16-bit unsigned integer, then several O (1) time algorithms were developed: see "Fast Counters" .

This is one of the algorithms presented here; the one they call Nifty Parallel Count:

 #define MASK_01010101 (((unsigned int)(-1))/3) #define MASK_00110011 (((unsigned int)(-1))/5) #define MASK_00001111 (((unsigned int)(-1))/17) int bitcount (unsigned int n) { n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101); n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011); n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111); return n % 255 ; } 

Answer 6

It sounds like a one-time abacus. Now I'm curious who your interviewer was.

http://www.dangermouse.net/esoteric/abacussort.html