-->

Move all zeroes to the end of array

Posted by Admin on
Given an array , write a program to move all the zero to the end of array . For example if the given array is { 1, 0, 2, 1, 0, 3, 0, 0, 5 } then it should be changed to { 1, 2, 1, 3, 5, 0, 0, 0, 0 }.

Method 1 (Modified bubble sort )

Algorithm :
1) Traverse each element of array and compare each element with the next element .
2) If current element is zero and next element is non zero then swap two element.
       1) If( a[j]==0 &&  a[j+1]>a[j] )
             swap(a[j],a[j+1])
3)Repeat the process until all the zero move to the end of array.

Implementation :

public class ZeroAtEnd {
       public static void main(String args[]) {
              int a[] = { 1, 0, 2, 1, 0, 3, 0, 0, 5 };

              // calling the function to move the zero at end
              sortZeroAtEnd(a);

              // displaying sorted array(zero at front)
              for (int i = 0; i < a.length; i++) {
                     System.out.print(a[i] + " ");
              }
       }

       // function to move zero at the end
       private static void sortZeroAtEnd(int[] a) {
              int len = a.length;
              for (int i = 0; i < len; i++) {
                     for (int j = 0; j < len - 1 - i; j++) {
              //if a[j] is zero and a[j+1] is not zero then swap two element            
                           if (a[j] == 0 && a[j + 1] > a[j]) {
                                  int temp = a[j + 1];
                                  a[j + 1] = a[j];
                                  a[j] = temp;
                           }
                     }
              }
       }
}

Time Complexity : O(n2) 
Space Complexity : O(1)

Method 2 ( Using another array )

Algorithm :
1) Traverse element of array in linear order and copy the element in temp[] array if the element is non zero.
2) Copy back all the element from the temp[] array to the front of original array [].
3) Now fill the remaining indexes with the zero at the end .

Implementation :

public class ZeroAtEnd {
       public static void main(String args[]) {
              int a[] = { 1, 0, 2, 1, 0, 3, 0, 0, 5 };

              // calling the function to move the zero at end
              sortZeroAtEnd(a);

              // displaying sorted array(zero at front)
              for (int i = 0; i < a.length; i++) {
                     System.out.print(a[i] + " ");
              }
       }

       // function to move zero at the end
       private static void sortZeroAtEnd(int[] a) {
              int len = a.length;
              int temp[] = new int[len];
              int j = 0;
              // storing all the non zero element in temp[] array
              for (int i = 0; i < len; i++) {
                     if (a[i] != 0)
                           temp[j++] = a[i];
              }

              // shifting all the non zero element to the front of array
              for (int i = 0; i < j; i++) {
                     a[i] = temp[i];
              }

              // inserting zero to the end of array
              for (int i = j; i < len; i++) {
                     a[i] = 0;
              }
       }
}

Time Complexity : O(n)
Space Complexity : O(n)
where n is the size of input array

Method 3 ( Modifying method 2 and counting non zero elements )

Algorithm :
1) Traverse the element of input array in linear order.
2) If the encountered element a[i] is non zero then replace the element at index 'count'(a[count]) with this element.
3) Now insert 0 at the place of remaining indexes.

Implementation :

public class ZeroAtEnd {
       public static void main(String args[]) {
              int a[] = { 1, 0, 2, 1, 0, 3, 0, 0, 5 };

              // calling the function to sort zero at front
              sortZeroAtEnd(a);

              // displaying sorted array(zero at front)
              for (int i = 0; i < a.length; i++) {
                     System.out.print(a[i] + " ");
              }
       }

       // function to move zero at the end
       private static void sortZeroAtEnd(int[] a) {
              int len = a.length;
              int count = 0; // for counting non zero element
              for (int i = 0; i < len; i++) {

          // if the encountered element is non zero then insert it at index of count
                    if (a[i] != 0) {
                           a[count] = a[i];
                           count++;
                     }
              }

              // insert zero at the remaining indexes
              while (count < len) {
                     a[count++] = 0;
              }
       }
}

Time Complexity : O(n)
Space Complexity : O(1)

Method 4 (Modified Quick Sort )

Algorithm :
Let suppose firstindex point to first element of input array and lastindex point to the last element if input array. 
1) Repeat the below process until firstindex is less than lastindex.
2) Increment firstindex utlil a[firstindex]>0 and firstindex < lastindex.
3) Decrement lastindex until a[lastindex]==0 and lastindex > firstindex. 
4) If firstindex is less than lastindex then swap a[firstindex] and a[lastindex].   

Implementation :

public class ZeroAtEnd {
       public static void main(String args[]) {
              int a[] = { 1, 0, 2, 1, 0, 3, 0, 0, 5 };

              // calling the function to sort zero at front
              sortZeroAtEnd(a);

              // displaying sorted array(zero at front)
              for (int i = 0; i < a.length; i++) {
                     System.out.print(a[i] + " ");
              }
       }

       // function to move zero at the end
       private static void sortZeroAtEnd(int[] a) {
              int len = a.length;
              len--;
              int i = 0;
              while (i < len) {

                     // increment i until a[i]==0 and i is less than len
                     while (i < len && a[i] > 0) {
                           i++;
                     }

                     // decrement len until a[j]>0 and len is greater than i
                     while (i < len && a[len] == 0) {
                           len--;
                     }

                     // swap the element i and len if i is less than len
                     if (i < len) {
                           int temp = a[i];
                           a[i] = a[len];
                           a[len] = temp;
                     }
              }
       }
}

Time Complexity : O(n)
Space Complexity : O(1)

Please comment if you like the above post or if you find any mistake .


2 comments:

  1. One traverse solution

    #include
    int main(){
    int A[]={1, 0, 2, 1, 0, 3, 0, 0, 5};
    int i=0,j=8;
    while(i<=j){
    if(A[i]!=0){i++;
    if(A[j]==0)j--;}
    else {
    A[i]=A[j];
    A[j]=0;
    i++;j--;
    }
    }

    for(i=0;i<=8;i++){printf("%d \t",A[i]);}
    return 0;}

    ReplyDelete
  2. Basic solution is to establish an inductive hypothesis that the subarray can be kept solved. Then extend the subarray by one element and maintain the hypothesis. In that case there are two branches - if next element is zero, do nothing. If next element is non-zero, swap it with the first zero in the row.

    Anyway, the solution (in C# though) after this idea is optimized looks like this:

    void MoveZeros(int[] a)
    {

    int i = 0;

    for (int j = 0; j < a.Length; j++)
    if (a[j] != 0)
    a[i++] = a[j];

    while (i < a.Length)
    a[i++] = 0;

    }

    There is a bit of thinking that leads to this solution, starting from the inductive solution which can be formally proven correct. If you're interested, the whole analysis is here: http://www.codinghelmet.com/?path=exercises/moving-zeros-to-end-of-array

    ReplyDelete