Separate 0’s and 1’s in a given array

Objec­tive:  Given an array which contains only 0’s and 1’s. write an algorithm to separate 0’s and 1’s.

Example

int [] arrA = {1,0,1,0,1,1,0,0,0,0,1};
Output: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

Approach: Counting

• Count number of 0’s in the array. Say its count.
• Now in array, put 0 in indexes from 0 to count – 1.
• In rest of the array put 1.

Time Complexity: O(n)

Code: Run Code

Output: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

Approach: Swapping Indexes

• Use two indexes, left and right.
• Put left index at the start of array and right at the end of the array.
• Increment left till 1 is not found.
• Decrement right till 0 is not found.
• Swap left and right elements
• Do it till left<right

Time Complexity: O(n)

Code: Run Code

Output:

[0, 0, 0, 1, 1, 1, 1, 1]