Program to Separate Even and Odd numbers of Array

• Write a program to segregate even and odd numbers in linear time complexity.

Given an array of integers of size N. We have to separate odd and even numbers of an array. First group all even numbers then odd numbers.
For Example :
Input Array : 2 7 4 1 9 5 3 8
Output Array : 2 4 8 7 1 9 5 3

---

Dutch Flag Algorithm
This algorithm is similar to partition algorithm of quick sort.

Let "array" be an integer array of size N.

• Initialize two variables leftIndex and rightIndex to index 0 and N-1.
• Find first odd number by moving leftIndex from left to right.
• Find first even number by moving rightIndex from right to left.
• Swap array[leftIndex] and array[rightIndex].
• Repeat above process till rightIndex > leftIndex.

Time Complexity : O(n)

---

C program to separate even and odd numbers.

#include <stdio.h>

/* Checks whether a is odd or not. Returns 1 
if a is Odd number otherwise 0 */
int isOdd(int a){
   return a%2; 
}

/*Seperates Even and Odd Numbers of an array. first all Even and 
then all Odd numbers. This approach is similar to partition step 
of quick sort */
void seperateOddEven(int *array, int size){
    int temp, left = 0, right = size-1;
    while(right > left){
     /* traverse from left to right till we find a Odd number */
     while(!isOdd(array[left]))
         left++;
     /* traverse from right to left till we find an Even number */
     while(isOdd(array[right]))
         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] = {2, 7, 5, 10, 13, 20, 14, 0, 7, 3}; 
    int i;
    
    seperateOddEven(array, 10);
    
    for(i = 0; i < 10; i++){
     printf("%d ", array[i]);
    }

    return 0;
}

Output

2 0 14 10 20 13 5 7 7 3