Pages

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