Can this algorithm be implemented in O(N) time in C++?

I'm trying to implement a function in C++ that takes an array of integers and returns the same array, sorted as follows (I am a beginner to both C++ and CS in general)

1. All the odd numbers come before all the even numbers
2. The odd numbers will keep their original relative order
3. The even numbers will be placed in a reversed order (relative to their original order).

So if arr = [5, 2, 11, 7, 6, 4], then output would be [5, 11, 7, 4, 6, 2].

Is it possible to sort the array as specified above in O(n) time? If so, a hint would be helpful and I will try and figure it out on my own!

The most efficient solution I could think of was:

if ith element of array is even, then swap with the last even element in the array that has not yet been swapped

if the ith element is odd, swap it with the [i-1]th element in the array until the [i-1]th element is odd or you reach the beginning of the array

move onto the next element in the array

I've coded it up and it works, but this seems to run in O(n^2) time in worst case, since basically you have to traverse the array once to get the evens in the right relative order, and then go back through the array to get all the odds before the evens.

I'm having a hard time thinking of an O(n) implementation, as I can't think of a way in one pass of the list to ensure that all the elements are put into the appropriate position in the array. Basically all algorithms I can think of require a pass through the array and then some type of sort. Is an O(n) algorithm even possible in this case?

Of course you could do it by just creating a new array and copying the elements in the appropriate order and then returning the new array, but that's less interesting and I want to get a better understanding of implementing efficient algorithms

You can use the standard library for this.

First, perform a stable_partition, using a predicate that returns true if a number is odd. This will shift all the odd values to the left-hand side, preserving the relative order of all values.

The function returns an iterator to the beginning of the right-hand side, so at that point you can simply reverse that data.

The stable_partition is O(N.logN) worst-case, and the reverse is O(N). So this solution is at worst O(N.logN) time complexity with O(1) storage complexity.

In fact, it's more likely to be O(N). The documentation is a little unclear about how stable_partition should be implemented, but does indicate that the function allocates memory. In that case, it's O(N), only falling back to O(N.logN) behavior if allocation fails.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

inline bool is_odd(int value)
{
    return value % 2 != 0;
}

void show(const std::vector<int>& values)
{
    std::copy(values.begin(), values.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

int main()
{
    std::vector<int> values{ 5, 2, 11, 7, 6, 4 };
    show(values);

    // Partition the array, placing odd numbers first, then even numbers, preserving order
    auto it = std::stable_partition(values.begin(), values.end(), is_odd);
    show(values);

    // Reverse the even numbers
    std::reverse(it, values.end());
    show(values);
}

Your last paragraph saying "Of course you could do it by just creating a new array and [...]" makes it clear you're looking not just for linear time but also for sublinear space. Your attempt with swaps indicates you're even trying to use only constant space.

Yes, that is possible, see Stable Minimum Space Partitioning in Linear Time. The key idea (in my opinion) is to view the array of length n as a sequence of blocks of size log n, then make each block have either only even numbers or only odd numbers, and then sort the sequence of blocks. That sorting uses an algorithm with O(m log m) comparisons and O(m) moves, where m is the number of elements. In our case, the elements are the blocks and we have m = n / (log n) blocks. So the number of comparisons is O(m log m) = O(n/logn log (n/logn)) ≤ O(n/logn logn) = O(n). And the number of moves is O(m) = O(n/logn) block moves, and since blocks have size logn, that's O(n) moves of your array elements. So overall O(n) time. And all with O(1) space.

If I remember correctly, that paper was relatively easy to understand, but that sorting algorithm used in there is in a rather unaccessible paper that even cstheory's top user called "quite complicated". Maybe there are simpler ways now, this is the only one I'm aware of.

This can certainly be done O(N). Here's a simple approach. This is O(N) and is simpler than a partition sort which will first attempt to allocate a full array. It has a fallback but then gets slow and isn't O(N). I don't think there is anything more efficient as this is a single pass and doesn't require reversal.

#include <vector>
std::vector<int> partition_odd_even(const std::vector<int>& v)
{
    std::vector<int> ret(v.size());
    auto pstart = ret.begin(), pend = ret.end();
    for (auto x : v)
    {
        if (x & 1)
            *pstart++ = x;
        else
            *--pend = x;
    }
    return ret;
}

int main()
{
    std::vector<int> v{ 1,2,3,4,5,6,7 };
    auto vout = partition_odd_even(v);
    // vout is 1,3,5,7,6,4,2
}