Sort a Binary Array

Posted: February 13, 2011 in Algorithms, data structures

Q. Given a binary array of 0 and 1, you have to sort it such that all 0s lie on left side followed by all 1. The sorting should not use any external data structure.

A. The best approach is to use a quick sort kind of algorithm. Here, its only 0s and 1s hence, sorting will happen in O(n) time as we don’t need to call it recursively.

  • Maintain two pointers left and right.
  • Start traversing left pointer towards right until 1 is encountered.
  • Start right pointer towards left until 0 is encountered.
  • Swap elements at both pointers.
  • Continue doing so until left and right pointer converge.

Since, we have to traverse the array only once, sorting happened in O(n) time.

Advertisements
Comments
  1. kinshuk4 says:

    Hi, very well explained. Here is my link as well:
    http://k2code.blogspot.in/2010/04/sorting-binary-array.html with the same partition logic.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s