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

Question

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:

1. Sort the array. So, Input array becomes \$[1,2,4,5,6,7,9]\$ run time \$O(n \log n)\$
2. 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)\$.
3. 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 <iostream>
#include <algorithm>

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

    int p1=0;
    int p2=0;

    while(p2 < nums.size())
    {
        if(p2 % 2 == 0)
        {
            int tmp = nums.at(p1);
            nums[p1] = nums[p2];
            nums[p2] = tmp;

            p1++;
            p2++;
        }
        else
        {
            p2++;
        }
    }

    std::sort(nums.begin()+p1, nums.end(),std::greater<int>());
}

void test( std::vector<int>& input, const std::vector<int>& expected, const std::string & testName)
{
    shuffleEvenOdd(input);
    std::cout<<"\n\n";

    std::cout<<"\n\n"<<"Test case : "<<testName;

    if(input == expected)
          std::cout<<" correct ";
    else
        std::cout<<"  failed. ";

}

void test1()
{
    std::vector<int>tmp= {2,2,2};
    const std::vector<int>expected= {2,2,2};
    const std::string tstName = " Test 1 ";

    test(tmp,expected, tstName);
}

void test2()
{
    std::vector<int>tmp= {2};
    const std::vector<int>expected= {2};
    const std::string tstName = " Test 2 ";

    test(tmp,expected, tstName);
}

void test3()
{
    std::vector<int>tmp= {3,3};
    const std::vector<int>expected= {3,3};
    const std::string tstName = " Test 3 ";

    test(tmp,expected, tstName);
}

void test4()
{
    std::vector<int>tmp= {1,-8,2,0,5};
    const std::vector<int>expected= {-8,1,5,2,0};
    const std::string tstName = " Test 4 ";

    test(tmp,expected, tstName);
}

void test5()
{
    std::vector<int>tmp= {-9,1,-8,2,0,5};
    const std::vector<int>expected= {-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;
}

Answer 1

Use std::swap rather than writing your own

    int p1=0;
    int p2=0;

    while(p2 < nums.size())
    {
        if(p2 % 2 == 0)
        {
            int tmp = nums.at(p1);
            nums[p1] = nums[p2];
            nums[p2] = tmp;

            p1++;
            p2++;
        }
        else
        {
            p2++;
        }
    }

    std::sort(nums.begin()+p1, nums.end(),std::greater<int>());

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<int>& 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.

Answer 2

Your solution using the native sort on the vector is a good one, and your subsequent relocate-and-sort are relatively fast too. There's no scalability problem here in terms of performance, because they are no worse than the sort, but I can't help but think that there's a better way to do this. Why have the same scalability complexity of the sort, when you can do better....?

The ordering/sorting of the data is a bit of a red herring. Rather, it's not a red-herring, it's a minor complication. The sorting is the first part of a two part process, and the problem should be considered as two parts. You should be able to rearrange the even/odd indices of any input vector, whether it's sorted or not. You should be able to relocate the data regardless of the values, simply based on the index.

To make this obvious, there should be two functions, a 'prepare' function that sets the vector up in the input order, and then the 'real' function which rearranges the values in the even/odd index order, and the second function should be indifferent to the type of data stored in the vector. So, consider a test function that looks like:

void test( std::vector<int>& input, const std::vector<int>& expected, const std::string & testName)
{
    std::cout << "Test case : " << testName << "\n";

    prepareEntries(input);

    shuffleEvenOdd(input);

    ....

In an actual implementation, the prepareEntries will sort the data.

My particular interest is in the second stage of the process, the shuffleEvenOdd. This intrigues me, and is what I have studied, and reduced to an \$O(n)\$ operation.

There's a "simple" function you can apply to each index in the vector, and determine, from that where each value should go. The new location of any index value is given by:

int moveTo(const int index, const int right) {
    const int shift = index >> 1;
    return ((index & 1) == 0) ? shift : (right - shift);
}

The way that works, is that odd numbers are positioned relative to the right-side of the vector, and even values are relative to the left. If the value is even, we put it at the left-index + half the value. If the value is odd, we position at the right-index - half the value.

An odd index 5 in a vector of size 11 (which will have the right-most index of 10), will be at 10 - (5/2), or 8... the resulting positions of each input index:

0  1  2  3  4  5  6  7  8  9 10

will be:

0  2  4  6  8 10  9  7  5  3  1

Note how index 5 ended at position 8.

Using the above function, you can create a 'rotation' in the vector. Take an index in the vector, finc out where that index needs to be relocated, take the value from the target spot and save it in a temp variable, then put the source value in to the new location. Then find the new location of the value we just pulled, and save away the value at that spot, and replace it, and so on, until we get back to where we started.

Once we get around the loop, we stop, and we have 'rotated all the values tghat form a sequence in the input vector.

Note that there may be multiple discrete 'loops' in the vector. For example, in a vector of size 5, there are actually 3 loops:

0, 1, 2, 3, 4

Loop 1 is at index 0. When we apply as the source index to our relocation function, the result is the value 0. It is a single-item loop.

Loop 2 is at index 1. Look at the index 1 sequence:

0, 1, 2, 3, 4
   #        ^

Index 1 belongs at index 4, so we save 4 in a temp value, and put index 1 at index 4:

0, 1, 2, 3, 1   (4)

Now, index 4, in our function, belongs at position 2, so we save away the index 2 value, and put the index 4 value there instead:

0, 1, 4, 3, 1   (2)

The value at index 2 now belongs at index 1, so we do that move (and save 1 away):

0, 2, 4, 3, 1   (1)

At this point, we have looped back to index 1, so we stop this loop.

Note that we have not yet visited index 3, it is also a discrete loop. Index 3 in our function returns itself to index 3.

If you consider that index 0 always forms a discrete loop, then you can skip it.

Still, larger vectors have more complicated multiple loops.

Here is a function that will rotate a single discrete loop inside a vector, starting a specific index:

int moveTo(const int index, const int right) {
    const int shift = index >> 1;
    return ((index & 1) == 0) ? shift : (right - shift);
}

void rotate(std::vector<int>& nums, const int start) {

    const int right = nums.size() - 1;

    int index = start;
    int buffer = nums[index];

    do {
        const int npos = moveTo(index, right);
        const int tmp = nums[npos];
        nums[npos] = buffer;
        buffer = tmp;
        index = npos;
    } while (index != start);
}

The challenge here is to find all the discrete loops inside a vector, and to call the above function just once per loop.... to solve that, I recommend having a 'seen' vector of bool, that allows you to identify which indices have been visited.

Combining the seen vector with the various loop rotations, allows you to iterate the vector twice, once looking for unseen values, and the other doing actual rotations. Since each seen member is visited once, and since each value is rotated just once, the result is that the overall solution is a regular \$O(n)\$ loop.

This reduces the complexity from \$O(n \log(n))\$ that your solution currently has.

Now, here we can prove that the actual values in the vector are not significant any more, and all that's important is the index. We can make the method a template method, and it will work on any vector data:

template<class T>
int rotate(std::vector<T>& values, const int start, std::vector<bool>& seen) {

    ...
    T buffer = nums[index];
    ...
}

template<class T>
void shuffleEvenOdd(std::vector<T>& values) {
    ....
}

I have kept the same variable names as you had, but the verctors are now templates, not <int>....

int moveTo(const int index, const int right) {
    const int shift = index >> 1;
    return ((index & 1) == 0) ? shift : (right - shift);
}

template<class T>
int rotate(std::vector<T>& nums, const int start, std::vector<bool>& seen) {

    const int right = nums.size() - 1;

    int index = start;
    T buffer = nums[index];
    int count = 0;

    do {
        const int npos = moveTo(index, right);
        const T tmp = nums[npos];
        nums[npos] = buffer;
        buffer = tmp;
        index = npos;
        count++;
        seen[npos] = true;
    } while (index != start);

    return count;
}

template<class T>
void shuffleEvenOdd(std::vector<T>& nums) {

    const int sz = nums.size();
    if (sz < 3) {
        return;
    }

    std::vector<bool> seen = std::vector<bool>(sz, false);

    int count = 0;
    for (int i = 0; i < sz && count < sz; i++) {
        if (!seen[i]) {
            count += rotate(nums, i, seen);
        }
    }

}

I have put this, with an additional test, up on Ideone

Answer 3

If you implement your own selection sort you can, instead of modifying the array in place, build the two arrays in step 2 in \$O(n^2)\$. Then you can build the 3rd, final array in \$O(n)\$ by traversing the two arrays in lockstep - one from the front, the second from the back. There might be a better sort than selection sort for this, I'll edit this answer if I find one.

Edit: Heapsort is better (\$O(n \log n\$) worst case) but modify it so that instead of moving the largest value to the end, you move the smallest value out of the array and into the step 2 arrays. Heapsort is harder to implement than selection sort, though.