algorithm moves the array elements

Question

I can not figure out an algorithm for this task, maybe you have an idea? Task: Move the array to the array in the first half would be all the elements of the odd lines and the second all elements of the pair of lines. The simplest option would be to move elements to another array, as it could make one using temp variable?

Input data array  = {1,2,3,4,5,6,7,8}
output data array = {2,4,6,8,1,3,5,7}

Answer 1

Is this homework? If not, use std::stable_partition():

struct IsEven {
    template<class T>
    bool operator()(const T& v) const { return v % 2 == 0; }
};

int* arr = {1,2,3,4,5,6,7,8};
int* mid = std::stable_partition(arr, arr+8, IsEven());

If it is a homework, then your instructor probably expects you to write the algorithm. If you don't have to maintain the ordering as in the input sequence then you can do it rather efficiently:

1. Find the first element that doesn't satisfy the predicate (i.e., is odd).
2. Find that last element that does satisfy the predicate (i.e., is even)
3. swap the two elements.
4. Repeat, starting from the positions you just found, until the two positions meet.
5. The point where the two positions meet is the middle of the partition, where even numbers stop and odd numbers begin.

This is roughly how std::partition() works. If you do have to maintain the relative ordering in the input array then you can still do it in-place, but it will be faster if you use a temporary buffer. Copy the elements that don't match the predicate into that buffer, and squeeze in place those that do. Finally bring back in the elements that don't match, at the end of the array, in order.

Answer 2

I'm reading this question such that the output array should have the elements at even indices followed by those at odd indices, though I may be incorrect.

If not, then this is how I would do it.

template<typename T>
void moveValues(const T[] input, T[] output, std::size_t length)
{
    int current outputIndex = 0;
    if (length > 1)  // in case we have a single element array.
    {
        for (int i = 1; i < length; i+=2)
        {
            output[++outputIndex] = input[i];
        }
    }
    for (int j = 0; j < length; j+=2)
    {
        output[++outputIndex] = input[j];
    }
    assert(outputIndex == length);  // should have filled up array
}

Answer 3

/* *********************************************************************** */
/*              Author: Bigyan Shrestha                                    */
/*              Description: C++ source code for arranging even numbers    */
/*                           numbers of an array to one  half and odd      */
/*                           numbers to the other half.                    */
/* *********************************************************************** */

#include <iostream>
using namespace std;

inline bool isEven( int value ){
    if( value % 2 == 0 ) {
        return true;
    }
    else {
        return false;
    }
}

inline void swap( int sourceIndex, int destIndex, int **sourceArray ) {
    int temp;
    temp = (*sourceArray)[sourceIndex];
    (*sourceArray)[sourceIndex] = (*sourceArray)[destIndex];
    (*sourceArray)[destIndex] = temp;
}

void displayArray( int *sourceArray, int size ){
    for( int i = 0; i < size ; i++ ) {
        cout << sourceArray[i] << "  " ;
    }
    cout << endl;

}

int main( void ){

    int size;
    int *input;
    int evenIndex = 0;  // for keeping track of even numbers

    cout << "Enter the size of input array" << endl ;
    cin  >> size;

    input = new int[size];

    for( int i = 0; i < size ; i++ ) {
        cout << "Please enter the input value ( " << size-i << " remaining )" << endl;
        cin >> input[i] ;
    }
    cout << endl;

    cout << "Original Input Array " << endl;
    displayArray( input,size );
    cout << endl;

    for( int i = 0; i <size ; i++ ) {
        if( isEven(input[i]) && i > evenIndex ) {
            for( int j = i ; j > evenIndex; j-- ){
                swap( j, j-1, &input);
            }
            ++evenIndex;
        }
    }

    cout << "Modified Array " << endl;
    displayArray( input,size );
    cout << endl;

    return 0;
}