Even numbers at even index and Odd numbers at odd index

You are given an array of positive numbers. You have to rearrange array such that even numbers at even position and odd numbers at odd positions. If suppose odd numbers exceeds the even numbers or vice-versa than keep them untouched. Do this in one pass and without using any extra memory.

input : {2 5 7 8 1 6 9 }
output : {2 5 8 7 6 1 9 }
This is similar to an implementation of partition method of quick sort.We start from the left and keep two index one for even position and other for odd positions. Traverse these index from left. At even position there should be even number and at odd positions, there should be odd number . Whenever there is mismatch , we swap the values at odd and even index.

 


arrangeArray (int a[], int size)
{
	oddInd = 1;
	evenInd = 0;
	while (true)
	{
		while (evenInd < size && a[evenInd]%2 == 0)
			evenInd += 2;
		while (oddInd < size && a[oddInd]%2 == 1)
			oddInd += 2;
		if (evenInd < size && oddInd < size)
			swap (a[evenInd], a[oddInd])
		else
			break;
	}

}

Complexity: O(N)

0 Thoughts on “Even numbers at even index and Odd numbers at odd index

  1. Kaushlendra Rai on November 5, 2014 at 1:04 pm said:

    Your code fails for input:

    {2, 5, 7, 8, 1, 6, 9, 1, 6}

  2. Provided solution is wrong…Here is the corrected one

    arrangeArray (int a[], int size)
    {
    oddInd = 1;
    evenInd = 0;
    while (true)
    {
    while (evenInd < size && a[evenInd]%2 == 1)
    evenInd += 2;
    while (oddInd < size && a[oddInd]%2 == 0)
    oddInd += 2;
    if (evenInd < size && oddInd < size)
    swap (a[evenInd], a[oddInd])
    else
    break;
    }

    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation