Shuffle a sorted array so that left portions contains even indices and right portion contains odd indices numbers

I have been solving the following problem:

Input array: \$[7,4,2,5,1,9,6]\$

Output array: \$[1,4,6,9,7,5,2]\$

I tried to do it in the following way:

• Sort the array. So, Input array becomes \$[1,2,4,5,6,7,9]\$ run time \$O(n \log n)\$

• Numbers in even indices are \$[1,4,6,9]\$ an in odd indices are \$[2,5,7]\$. Move all the even indices into left part of the array. So it becomes \$[1,4,6,9,2,7,5]\$. Runtime \$O(n)\$.

• Now, sort the \$[2,7,5]\$ i.e. the numbers from odd indices in descending order. So, the final array becomes \$[1,4,6,9,7,5,2]\$ Runtime : \$O(n \log n)\$

Can you please review it?

#include 
#include 

void shuffleEvenOdd(std::vector& nums)
{
    std::sort(nums.begin(),nums.end());

    int p1=0;
    int p2=0;

    while(p2 ());
}

void test( std::vector& input, const std::vector& expected, const std::string & testName)
{
    shuffleEvenOdd(input);
    std::couttmp= {2,2,2};
    const std::vectorexpected= {2,2,2};
    const std::string tstName = " Test 1 ";

    test(tmp,expected, tstName);
}

void test2()
{
    std::vectortmp= {2};
    const std::vectorexpected= {2};
    const std::string tstName = " Test 2 ";

    test(tmp,expected, tstName);
}

void test3()
{
    std::vectortmp= {3,3};
    const std::vectorexpected= {3,3};
    const std::string tstName = " Test 3 ";

    test(tmp,expected, tstName);
}

void test4()
{
    std::vectortmp= {1,-8,2,0,5};
    const std::vectorexpected= {-8,1,5,2,0};
    const std::string tstName = " Test 4 ";

    test(tmp,expected, tstName);
}

void test5()
{
    std::vectortmp= {-9,1,-8,2,0,5};
    const std::vectorexpected= {-9,0,2,5,1,-8};
    const std::string tstName = " Test 5 ";

    test(tmp,expected, tstName);
}

int main()
{
    test1();
    test2();
    test3();
    test4();
    test5();

    return 0;
}

Use std::swap rather than writing your own

int p1=0;
    int p2=0;

    while(p2 ());

You'd be better off using std::swap:

std::swap(nums[p1], nums[p2]);

But you don't need to swap

However, we can do it without any swaps nor the final sort.

First, create a new vector:

std::vector output = new std::vector();

Now iterate over the sorted vector with a for loop.

int n = nums.size();
    for ( int i = 0; i < n; i += 2 ) {
        output.push_back(nums[i]);
    }

And again with a second for loop.

for ( int i = (n % 2 == 0) ? n - 1 : n - 2; i >= 1; i -= 2 ) {
        output.push_back(nums[i]);
    }

The initialization for the second for loop is tricky because you want it to start on the last odd number. If there are an even number of elements in the vector, then the last odd index is the last index: n - 1; otherwise, it is one less than that: n - 2.

After that, you just need to copy the new vector over the old:

nums = std::move(output);

This saves you an entire sort and a lot of swapping.

Constant memory

You can do it without the extra vector, but it requires more calculations to get the indexes right.

void shuffleEvenOdd(std::vector& nums) {
    int n = nums.size();
    if ( n <= 1 ) {
        // we need more than one element; one and zero length vectors are already sorted
        return;
    }

    std::sort(nums.begin(), nums.end());

    int middle = (n + 1) / 2;

    // we start by putting the correct element in the last element
    int start_index = n - 1;
    int previous_index = start_index;

    // if there is more than one element in the vector, the element at [1] goes to [n-1]
    // otherwise, we should have exited already
    int index = 1;
    int temp = nums[start_index];

    // while we haven't looped back to the start
    while ( index != start_index ) {
        // move the next element
        nums[previous_index] = nums[index];
        previous_index = index;
        // if index is in the left half of the array,
        // we just move from double the index; e.g. 0 from 0, 1 from 2, 2 from 4, etc.
        // otherwise, we count index spaces back from n-1, double it, and add 1
        // e.g. n-1 from 1, n-2 from 3, n-3 from 5, etc.
        // (n-1 - index) * 2 + 1 == (n - index) * 2 - 1
        index = ( index < middle ) ? 2 * index : (n - index) * 2 - 1;
    }

    nums[previous_index] = temp;
}

This works and uses minimal memory, but it is less readable than making the extra vector. That's why it makes such heavy use of comments.

I also don't have any proof that it will always move all the necessary elements. It does in my testing, but that's not proof.

StackExchange Code Review Q#83591, answer score: 5