алгоритм перемещает элементы массива

Question

Не могу разобраться в алгоритме для этой задачи, может быть, у вас есть идея?Задача: переместить массив в массив, в первой половине будут все элементы нечетных строк, а во второй - все элементы пары строк.Простейшим вариантом было бы переместить элементы в другой массив, так как он мог бы создать один, используя временную переменную?

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

Answer 1

Это домашняя работа? Если нет, используйте 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());

Если это домашнее задание, то ваш инструктор, вероятно, ожидает от вас написания алгоритма. Если вам не нужно поддерживать порядок, как во входной последовательности, то вы можете сделать это довольно эффективно:

1. Найдите первый элемент, который не удовлетворяет предикату (то есть нечетный ).
2. Найдите, что последний элемент, который выполняет , удовлетворяет предикату (то есть даже )
3. поменяйте местами два элемента.
4. Повторите, начиная с позиций, которые вы только что нашли, пока эти две позиции не встретятся.
5. Точка, в которой встречаются две позиции, - это середина раздела, где начинаются четные числа и начинаются нечетные числа.

Это примерно как std::partition() работает. Если вам нужно поддерживать относительный порядок во входном массиве, вы все равно можете сделать это на месте, но это будет быстрее, если вы используете временный буфер. Скопируйте элементы, которые не соответствуют предикату, в этот буфер и сожмите на место те, которые делают. Наконец, верните элементы, которые не совпадают, в конце массива по порядку.

Answer 2

/* *********************************************************************** */
/*              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;
}

Answer 3

Я читаю этот вопрос так, что в выходном массиве должны быть элементы с четными индексами, за которыми следуют элементы с нечетными индексами, хотя я могу ошибаться.

Если нет, то я бы так и сделалит.

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
}