# If I have a large random array of 0s and 1s that I want to sort what kind of an algorithm and data structures should I consider?

What are the types of things that need to be considered if I need to sort a large random array of 0s and 1s?

You can assume large array is in the order of million or billions.

I understand there are tons of sorting algorithms out there (quick, merge, radix,.etc.) and there are so many different data structures out there (trees, skip lists, linked lists, etc.)

If somebody asks me to sort this large array, do I simply jump to Quick Sort and say that's the best solution? If not, what am I supposed to be thinking about?

I'm not even sure if I know the right answer to this question, but I would really appreciate it if somebody in the community can give some advise.

Thanks.

-
why can't you just count the number of 1s, and then just write out the 0s and 1s. –  Realz Slaw Dec 9 '12 at 3:25
I guess sometime it is better to think in simple manner. –  AJed Dec 9 '12 at 4:22
In general, it's a good idea to start with whatever is correct, such as Quicksort. Then, think about how you could do better: Quicksort is a general purpose algorithm, but think about the structure of your input. Then you might notice that you only have zeros and ones. This is the kind of structure that sometimes allows one to design faster algorithms. –  Juho Dec 9 '12 at 20:01
Juho - thanks for your comment. I'm starting to see the thought process now. –  user1068636 Dec 10 '12 at 0:55

Use counting sort: run through the array once and count the number of 0's. Then run through the array once more and write in it the counted number of 0's, followed by 1's. In any case, this is a purely academic exercise because nobody would ever need to do such a thing in real life.

-
Hi Andrej - I'm just a little curious, how did you think about Counting Sort? In my question I mentioned quick,merge,radix sorts, but you thought about counting sort. What was it that triggered you to think about counting sort? Sorry if this sounds like a dumb question, but I"m just curious to know your thought pattern. –  user1068636 Dec 9 '12 at 4:07
Let us put it this way. I have been programming since I was 13 years old, so that would be 28 years of experience, and I am a university professor who teaches people like you sorting algorithms. –  Andrej Bauer Dec 9 '12 at 4:47
One intuition that would be useful here is that counting sort has runtime O(n + U), where n is the number of elements and U is the number of possible values. A good way to arrive at counting sort would be to realize that the number of distinct values is extremely small (just two), so an algorithm that depends on the upper bound of the number of distinct values would probably be very appropriate. From there, it's just a matter of remembering that counting sort would be one of the best choices for something in this situation. –  templatetypedef Dec 9 '12 at 19:54

While Andrej Bauer points out that your problem can be solved very efficiently, 0-1 sorting has some interesting and nontrivial aspects. For example, a sorting network is valid if and only if it can sort all sequences of 0s and 1s.

Intuitively, a sorting network is an sorting algorithm that does not change what it does based on previous results. This is not true of, say, quicksort, which recurses differently based on the rank of the chosen pivot (quicksort is clearly not a sorting network for several reasons in its standard form). This is why for sorting networks 0-1 sorting is exactly as difficult as unrestricted sorting--the algorithm can't examine the input to see how to handle it most efficiently. In this case, the most efficient way to handle the 1s and 0s is to not really sort at all but count instead. This option is not available to a sorting network, so instead it performs all operations as usual, costing as much as any other kind of sort.

-

My approach would be this:

ptr1 := start_of_array
ptr2 := end_of_array
while ptr2 > ptr1 :

while arr[ptr1] == 0 : //pass1
ptr1++

while arr[ptr2] == 1 : //pass2
ptr2--

if ptr2 > ptr1 :
swap ptr1, ptr2    //swap


This will work like this :

Input Array : 0 0 0 0 1 1 1 0 1 0 1 1

Pass1 : 0 0 0 0 1 1 1 0 1 0 1 1

Pass2 : 0 0 0 0 1 1 1 0 1 0 1 1

Swap : 0 0 0 0 0 1 1 0 1 1 1 1

Pass1 : 0 0 0 0 0 1 1 0 1 1 1 1

Pass2 : 0 0 0 0 0 1 1 0 1 1 1 1

Swap : 0 0 0 0 0 0 1 1 1 1 1 1

Pass1 : 0 0 0 0 0 0 1 1 1 1 1 1

Pass2 : 0 0 0 0 0 0 1 1 1 1 1 1

Exit from loop

-
That is nice, but you need an Elephant in Cairo or else you fail if the input is all either 0 or 1. And the loop will need to be a bit more complex, I think. Still, potentially better than going through the list twice (although going backward in memory can be less efficient than going forward...). –  markets Apr 24 '13 at 21:27

This really depends on the number of zeroes and ones your dealing with on a per element basis.

If your dealing with 64 or less, just convert it to a number, pop it into an array, and sort the array.

32 or less, make a blank array, convert the entry to a number, and keep track of the number of times the number passed.

ok If this is a pathological case-- lets say a billion entries each a 16kilobits long.. now your into diskland... you split your file into ~100 mb pieces then use the unix split, sort, and >> operators to implement a merge sort. There is a temptation to just let sort do it all in one go, ignore that temptation it leads to the land of frustration (It might have been a memory limitation). (I did an 800GB sort this way via script a few years back)

Best of luck --Storm

-
But every element is precisely either a 0 or a 1. –  Juho Dec 9 '12 at 19:53