# Segregate even and odd numbers in array

The problem is to segregate even and odd numbers in an array. The goal is to rearrange the elements in such a way that all even numbers appear before all odd numbers in the array, while maintaining the relative order of even and odd elements as they appeared in the original array.

## Example

Consider the following array:

``[1, 8, 7, 3, 9, 4, 2, 5, 10]``

After segregating even and odd numbers, the array could be rearranged as:

``[8, 4, 2, 10, 1, 7, 3, 9, 5]``

All even numbers (8, 4, 2, 10) appear first, followed by all odd numbers (1, 7, 3, 9, 5). The relative order of even and odd elements is maintained.

## Idea to Solve the Problem

To segregate even and odd numbers in the array, we can use a two-pointer approach. The idea is to have two pointers, one at the beginning of the array (starting from index 0) and the other at the end of the array (starting from index size - 1).

1. Initialize two pointers, i.e., j = 0 and i = 0.
2. The pointer j will be used to keep track of the next available position for an even number.
3. The pointer i will be used to iterate through the array.
4. If arr[i] is even, swap arr[i] with arr[j] and increment both i and j.
5. If arr[i] is odd, just increment i.
6. Continue this process until i reaches the end of the array.

## Algorithm

1. Initialize two pointers, j = 0 and i = 0.
2. Iterate through the array using pointer i from 0 to size - 1.
3. If arr[i] is even (i.e., arr[i] % 2 == 0), swap arr[i] with arr[j], and increment both i and j.
4. If arr[i] is odd (i.e., arr[i] % 2 != 0), just increment i.
5. Continue until i reaches the end of the array.

## Pseudocode

``````function segregateEvenAndOdd(arr, size):
j = 0
for i from 0 to size - 1:
if arr[i] is even:
swap arr[i] with arr[j]
increment j
increment i
end for
end function``````

## Time Complexity

• The above algorithm has a time complexity of O(N), where N is the number of elements in the array.
• The algorithm processes each element in the array exactly once, so it runs in linear time with respect to the number of elements.

## Resultant Output Explanation

The given program implements the algorithm to segregate even and odd numbers in the given arrays.

In the provided output, the program displays the original array and the array after segregating even and odd numbers.

For the array `[1, 8, 7, 3, 9, 4, 2, 5, 10]`, after segregating even and odd numbers, the array becomes `[8, 4, 2, 10, 1, 7, 3, 9, 5]`. All even numbers appear first, followed by all odd numbers, while maintaining the relative order.

For the array `[9, 8, 2, 7, 6, 2, 4, 9, 7, 4]`, after segregating even and odd numbers, the array becomes `[8, 2, 6, 2, 4, 4, 9, 9, 7, 7]`.

Both outputs correctly segregate the even and odd numbers in the arrays.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.