Sunday 2 August 2015

Shift all zeros to left and non-zeros to right

Given an Array With random 0s and non zero numbers, shift all the 0s to the beginning and non 0s to the rear.
Eg: 2,19,18,14,0,0,2,7,0,6,0
Out put 0,0,0,0,2,19,18,14,2,7,6

i.e order of numbers not to change. Do it in place
import java.util.Objects;

public class ShiftElements {

 public static void shiftElements(int arr[]) {
  Objects.nonNull(arr);
  if (arr.length <= 1)
   return;

  int i = 0;

  for (i = arr.length - 1; i >= 0; i--)
   if (arr[i] == 0)
    break;

  int zeroPosition = i;

  for (i = zeroPosition - 1; i >= 0; i--) {
   if (arr[i] != 0) {
    int temp = arr[i];
    arr[i] = 0;
    arr[zeroPosition] = temp;
    zeroPosition--;
   }
  }
 }
}


Following is the junit test case for above program.
import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

public class ShiftElementsTest {

 @Test
 public void test1() {
  int arr1[] = { 2, 19, 18, 14, 0, 0, 2, 7, 0, 6, 0 };
  int arr2[] = { 1, 2, 3, 4, 5, 0, 0, 0 };

  int expected1[] = { 0, 0, 0, 0, 2, 19, 18, 14, 2, 7, 6 };
  int expected2[] = { 0, 0, 0, 1, 2, 3, 4, 5 };

  ShiftElements.shiftElements(arr1);
  ShiftElements.shiftElements(arr2);

  assertTrue(Arrays.equals(arr1, expected1));
  assertTrue(Arrays.equals(arr2, expected2));
 }
}



No comments:

Post a Comment