Separate odd and even numbers in an array.

Question: Given an array arr[], write a function that separates even and odd numbers. The function should print first all the even numbers and then the odd numbers.

Input: 4, 8, 15, 16, 23, 42
Output: 4, 8, 16, 42, 23, 15

The objective of this problem is mainly to segregate the array in two halves. One half contains all the even numbers and one half contains all the negative numbers.

Naive Method:-

The most naive method is to allocate a separate empty array and then we fill it as we scan the original array. But this method will take up a lot of space and hence it is NOT RECOMMENDED

SMART METHOD:-

We can solve this problem just by a single scan of the array in this way:-

• Initialize two index variables left and right. left = 0, and right = n-1. (Here n is the size of the array, and n is the last index)
• Keep incrementing left index, until the number at that index is even. This way the even numbers stay in the beginning.
• Keep decrementing right index until the number at that index is odd. This way the odd numbers stay at the end.
• If (left < right), swap the numbers at left and right.

Here is an implementation of the above algorithm:-

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

int seperateEvenAndOdd(int arr[], int size)
{
	// Initialize left and right indexes
	int left = 0;
	int right = size - 1;
	
	while(left < right)
	{
		// Increment left index till the number is even
		// num%2 == 0, condition to check even number
		while(arr[left]%2 == 0 && left < right)
		{
			left++;
		}
		
		// Decrement right index till the number is odd
		while(arr[right]%2 == 1 && left < right)
		{
			right--;
		}
		
		// Time to swap
		if(left < right)
		{
			swap(&arr[left], &arr[right]);
			left++;
			right--;
		}
	}
}

Time Complexity:- O(n)
Space Complexity:- O(1)