- 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.

## 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.

#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