Home Arrays Separate odd and even numbers in an array.

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)

You may also like

May 11, 2017 - 05:19

First, your example output is missing a number from your example input.

Secondly your while loops are described wrong as for the even loop it’ll continue to increment the index while the value %2 (even), meaning it’ll loop until it’s first odd value to move to the right, but you comment it as till the number is even.

While they’re all nicely ordered in example, it’s recognized that isn’t stated as a requirement. But your own solution doesn’t produce your example output for your example input. Clearly your indexes converge at the separation index and it’d be simple enough to sort each partial portion of the array. But without that, your output will never be the own example output for the example input.

May 11, 2017 - 14:55

Hi,

Sorry for the typo. I have corrected it.

The code is perfect. Try to understand the while loop once again. It should loop until the left index is less than right index. Can you give me an example of a input that fails with this code? I will be happy to help you out.

Here is a running example of the input given in the post.
http://ideone.com/EReSp3