C Program to Move All Zeroes to the End of Array

  • Write a program to separate all zero's from all non-zero element of the array.
  • Algorithm to shift all zero's to the end of input array in linear time O(n) and in constant space O(1).

Given an integer array of size N. Move all zero's to the end of array.
For Example :

Input Array : 4 7 3 0 0 -3 7 0 8 0
Output Array : 4 7 3 8 7 -3 0 0 0 0

Let inputArray be an integer array of size N.

Using partition method of Quick Sort
This approach is similar to partition method of quick sort.
  • Initialize left and right to the index of first and last element of inputArray repectively(left = 0, right = N-1).
  • Using left index, traverse inputArray from left to right till we find a zero.
  • Using right index, traverse inputArray from right to left till we find a non-zero element.
  • Swap inputArray[left] and inputArray[right].
  • Continue until left < right.
Time Complexity : O(n)

C program to move all 0's to the end of array

#include <stdio.h>

/*
Separates 0's in an array. First all non-zero elements and then 0's .
This approach is similar to partition step of quick sort 
*/
void seperateZero(int *array, int size){
    int temp, left = 0, right = size-1;
    while(right > left){
    /* traverse from left to right till we find a zero */
     while(array[left] != 0)
         left++;
    /* traverse from right to left till we find a non zero*/
     while(array[right] == 0)
         right--;
     
     if(left < right){
            /* Swap array[left] and array[right] */
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
}

int main(){
    int array[10] = {4, 7, 3, 0, 0, -3, 7, 0, 8, 0}; 
    int i;
    
    seperateZero(array, 10);
    
    for(i = 0; i < 10; i++){
     printf("%d ", array[i]);
    }

    return 0;
}
Output
4 7 3 8 7 -3 0 0 0 0
By shifting all non-zero numbers

C program to segregate zero's and non-zero elements together

Algorithm to segregate all zero's and non-zero elements together in an array.
  • Initialize left and right to -1 and 0 respectively.
  • All the elements before left index are non-zero and all the elements between left and right are 0.
  • Using right index, traverse inputArray from left to right. If current element is non-zero, then swap inputArray[left] and inputArray[right].
  • Increment left(left++);
  • Continue until right < N.
Time Complexity : O(n) 
#include <stdio.h>

void swap(int *array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

/*Seperates 0's in an array. first all 0's and then 
non-zero numbers. */
void seperateZero(int *array, int size){
    int right, left = -1;
    for(right = 0; right < size; right++){
     if(array[right] != 0)
         swap(array, ++left, right);
    }
}

int main(){
    int array[10] = {4, 7, 3, 0, 0, -3, 7, 0, 8, 0}; 
    int i;
    
    seperateZero(array, 10);
    
    for(i = 0; i < 10; i++){
     printf("%d ", array[i]);
    }

    return 0;
}
Output
4 7 3 -3 7 8 0 0 0 0
Posted by
Labels: ,