I need to separate even numbers from odd numbers this way:

• even numbers must be in the first half of the array.
• odd numbers must be in the second half of the array.

note: I can't use a second array.

I've tried this algorithm:

1. if the first element is odd, then swap this element with the next element.
2. go to the next element.
3. if the second element is odd (and I know this is odd, because it's the element I've swapped), then swap again the same way. and repeat.

the problem is that it doesn't work. I think it's because I should have checked another elements. meaning, let x be the current element, x1 is the next element, and x2 is "x1 1". I need to check if x is odd, if x1 is odd, and if x2 is odd as well. if x2 is even, then I swap x with x2. then I increment counter by 1. repeat.

But I feel this is not an efficient algorithm, because it could be a source of confusion, and a source of errors too. To solve this, I thought of another way.

It consists of going at the middle of the array, and comparing the current element with the first element. if the current element is even and the first element is odd, then swap them together. if it's not the case, don't do anything else and increment counter by 1. repeat until the end of the array is reached (note: it's not a string, hence it's not a zero-terminated array). This could work, but there's still another problem, what have I to do if the first element and the current element are odd? there's a solution, but it'd add an extra layer of complexity. Therefore, I think I should avoid this way.

CodePudding user response：

This problem is similar to partitioning in a quick sort algorithm. One of the easiest solutions (both to understand and to implement) is the Hoare partition scheme, which works as follows:

• Start with an index to the first element of the array (i), and another index to the last element of the array (j).
• Increment i until you find an odd number.
• Decrement j until you find an even number.
• Swap array[i] with array[j].
• Repeat until j <= i.

CodePudding user response：

I would echo the comment from @user3386109 above.

If you were using Python then sorted could be used:

In [1]: x = [5, 3, 8, 0, 2, 7, 4, 6, 9, 1]

In [2]: sorted(x, key=lambda i: i % 2)
Out[2]: [8, 0, 2, 4, 6, 5, 3, 7, 9, 1]

Note:

• i % 2 returns a lower number, zero, for all evens and one for all odds.
• Comparisons are reduced as all evens compare equal as do all odds (due to the key function). Within the two partitions, numbers are not unnecessarily sorted.
• It uses the C-optimised sorted function and would be more readable/maintainable than using explicit Python of dancing pointers over an array with conditions that must be just-so.

P.s. It works for negative ints too:

In [9]: x = random.sample(range(-5, 5), 10)

In [10]: x
Out[10]: [1, 2, 3, -4, -5, 4, -3, -1, 0, -2]

In [11]: sorted(x, key=lambda i: i % 2)
Out[11]: [2, -4, 4, 0, -2, 1, 3, -5, -3, -1]