# Shifting even numbers to the left in array: Coding in C++ – 6

February 11, 2011 Leave a comment

Question. We are given an arrays of ints. We are supposed to shift the elements of the array such that no even number occurs to the right of an odd number.

i.e. if input is {1, 2, 3, 4, 5}, we want the output to be {2,4, 1,3,5} [ even {4,2, 3,5,1} is a valid output].

Solution.

We can observe that at the end of our manipulation, we would have an index, call it **divider, **such that elements having indexes in the range 0 to divider are even, and those from divider+1 to n (where n is the length of the input array, A) are odd.

We can proceed as follows: traverse through the array from left to right. Whenever we encounter an odd number, we do nothing, and keep going ahead. Whenever we encounter an even number, we move it to the cluster of even numbers at the beginning of the array.

We maintain the following invariant:

After we have traversed element with index = i, all even numbers (if any) encountered thus far have been placed in indexes in the range 0 to divider, and all odd numbers (if any) encountered have been placed in indexes in the range divider+1 to i.

To maintain the loop invariant, we do the following when we are at index = i : If A[i] is odd, do nothing. Else if A[i] is even, swap A[i] with A[divider + 1], and increment divider by 1.

——

**void (int A[ ], size_t n) **

**{**

**int divider = -1; **

**for ( int i = 0; i < n; i++) **

**{**

**if ( (A [i] % 2) == 0) **

**{**

**// swap A[i] and A[divider+1]. **

**int temp = A[i]; **

**A[i] = A[divider + 1]; **

**A[divider + 1] = temp; **

**//increment divider. **

**divider ++; **

**}**

**}**

**—–**

The above code will run in linear time.

—–