Home » Algorithms

Segregate even and odd numbers in minimum time complexity

Here, we are going to learn how to segregate even and odd numbers in minimum time complexity from an array of integers?
Submitted by Radib Kar, on November 13, 2018

Problem statement:

Given an array of integers. Write a function to segregate the Even and Odd numbers. Put the even numbers first.

Solution:

Algorithm:

1. Set two index variable, left = 0 and right = n-1 (n = array length)
2. Keep increasing the left index until any odd no is found.
3. Keep decreasing the right index until any even no is found.
4. If left < right, swap array[left] and array[right].

Time complexity: O(n) (only one scan )

Space complexity: O(1) (no additional space used)

Comment: The input order can be changed in the output as we are swapping on local observation.

C++ implementation to Segregate even and odd numbers in minimum time complexity

#include <bits/stdc++.h>
using namespace std;

void print(int* a,int n){
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}

void swap(int* a,int* b){
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

void separate(int* a, int n){
	int left=0,right=n-1;
	while(left<right){
		// increment left until any odd no is found 
		while(a[left]%2==0 && left<right) 
			left++;
		// increment right until any even no is found
		while(a[right]%2==1 && left<right) 
			right--;
		if(left<right){
			//swap array[left] & array[left] using pointer to reference
			swap(&a[left],&a[right]); 
			left++;
			right--;
		}
	}
}	

int main(){
	int n;
	// enter array length
	cout<<"enter no of elements\n";
	cin>>n;
	int* a=(int*)(malloc(sizeof(int)*n));
	//fill the array
	cout<<"enter elements...\n";
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	
	cout<<"array before segregating...\n";
	print(a,n);
	cout<<"array after segregating...\n";
	separate(a,n);
	print(a,n);

	return 0;	
}

Output

enter no of elements 
8
enter elements... 
11 
12 
13 
67 
66 
45 
34 
38 
array before segregating...
11 12 13 67 66 45 34 38
array after segregating...
38 12 34 66 67 45 13 11