Skip to content
Even Odd Separation O(N) Single Iteration

Even Odd Separation O(N) Single Iteration

Given an array containing a mix of even and odd numbers, and we need to perform Even Odd Separation. In this post we’ll see how to separate even and odd numbers in a single iteration using two pointers.

Example

Input: [1,3,2,5,9,4]
Output:[1 3 5 9 2 4]

Input: [8, 13, 14, 16, 17, 18, 21]
Output:[13 17 21 8 14 16 18]

Solution Approach

Method 1

To separate even-odd elements, we can take an extra array and start filling the even/odd numbers first and then the rest, but this would take a lot of time and space.

Method 2 – Optimized O(N)

Even Odd Separation using pointers.

Separate 0s and 1s in an array, using two pointers.

First, we take two pointers – [always] and [asuwish]. Both of them start from the beginning but the [always] pointer keeps on moving irrespective of even or odd but, the [asuwish] pointer stops once it encounters an even number on the way, and increments only when it encounters an odd number.

And the swapping occurs when,

arr[asuwish]%2==0 && arr[always]%2!=0

I hope you got the logic, if you’re in doubt, look at the code below and perform a dry run using pen and paper. Note: The names of pointers are an example, we can change as we wish.

Even Odd Separation Code

#include<iostream>
using namespace std;

int main()
{
    int arr[]={12,3,5,7,9,2,4,6,8,13,14,16,17,18,21};
    int asuwish, always, noe, temp, index;
    noe=sizeof(arr)/sizeof(arr[0]);
    for(always=0;always<noe;cout<<arr[always++]);
    for(asuwish=0,always=0;always<noe;always++)
    {
        if(arr[asuwish]%2==0&&arr[always]%2!=0)
        {
            temp=arr[always];
            for(index=always;index>=asuwish;index--)
                arr[index]=arr[index-1];
            arr[asuwish]=temp;
        }
        if(arr[asuwish]%2!=0)
            asuwish++;
    }
    cout<<endl;
    for(always=0;always<noe;cout<<arr[always++]<<" ");
    return 0;
}
Output:
12 3 5 7 9 2 4 6 8 13 14 16 17 18 21
3 5 7 9 13 17 21 12 2 4 6 8 14 16 18

Also read, Separate 0s and 1s – O(N) Single Iteration

Conclusion

This post is part of my #30DaysChallenge to write a blog post every day on what I learn every day, All the Best~ Abhiram Reddy.

Tags: