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

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.

—–


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: