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)
Your code fails for input:
{2, 5, 7, 8, 1, 6, 9, 1, 6}
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;
}
}
failing for input {2, 5, 7,1, 1, 6, 9, 3, 6}
Here’s my implementation based on tweak of original quick sort’s partition component,
static void OddEvenSort(int[] A) {
int j = -2; // odd pointer
int k = -1; // even pointer
for (int i = 0; i < A.Length; i++) {
// Maintain invariant:
// don't touch even items in even locations; last one pointed by k
// don't touch odd items in odd locations; last one pointed by j
if (i % 2 == 0) {
if (i <= j)
continue;
}
else if (i <= k)
continue;
if (A[i] % 2 == 0 && k + 2 < A.Length) {
k = k + 2;
Swap(A, i, k);
}
else if (A[i] % 2 == 1 && j + 2 < A.Length) {
j = j + 2;
Swap(A, i, j);
}
}
}
Updated source code is here: https://github.com/atiq-cs/Problem-Solving/blob/master/Basics/partition_odd_even.cs