Saturday, December 29, 2012

Sort An Array of 0s and 1s


Given an unsorted array of 0s and 1s, sort the array such that the 0s appear before the 1s.

e.g: A[0,1,1,0] --> A[0,0,1,1].


import java.util.Arrays;

public class SortZerosAndOnes {

 static int[] sortZerosAndOnes(int[] a) {
  if (a.length < 2) {
   return a;
  }
  int len = a.length;
  int sum = 0;

  for(int i = 0 ; i < len ; i++) {
   if(a[i] == 1) {
    sum += a[i]; // The result will be the number of 1s in the array
    a[i] = 0; // Make all the 1s zeros
   }
  }

  // In reverse order place the 1s back into the array
  for(int i = 0 ; i < sum ; i++) {
   a[a.length-i-1] = 1;
  }

  return a;
 }

 public static void main(String[] args) {
  int[] a = {0,1,0,1,0,1,1,0,1,0,0};
  System.out.println(Arrays.toString(sortZerosAndOnes(a)));
  // OUTPUT: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
 }
}


Time Complexity: O(n+m) where:
n - Number of elements in array
m - Number of 1s in the array(assuming the array contains any 1s)

No comments:

Post a Comment