C++で正の要素を偶数インデックス・負の要素を奇数インデックスに配置する方法（相対的な順序は維持しない）

問題概要

この問題では、整数型の配列が与えられ、すべての正の数を偶数インデックス（0, 2, 4…）に、すべての負の数を奇数インデックス（1, 3, 5…）に配置するように配列を変換することが求められます。

ただし、正の数と負の数の個数が一致しない場合もあります。そのようなケースでは、余分な要素は移動せず元の位置に残します。そのため、変換後も要素間の相対的な順序は維持されません。

具体例を使って問題を確認してみましょう。

入力： {3, 5, -1, 19, -7, -2}

出力： {3, -1, 5, -7, 19, -2}

この問題を解く鍵となるのは、「正しい位置に存在しない要素」を配列の中から見つけ出すことです。そのアプローチは複数考えられますが、本記事では代表的な2つの方法を解説します。

方法1：線形探索とスワップによる解法

この方法では、配列を先頭から順に走査し、正しい位置にない要素（偶数インデックスにある負の数、または奇数インデックスにある正の数）を最初に発見した時点で、適切な位置にある別の要素とスワップします。この処理を配列全体の走査が完了するまで繰り返すのが基本的な流れです。

実装例

上記の解法をC++で実装したプログラムは以下の通りです。

#include<iostream>
using namespace std;
void swapElements(int* a, int i , int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    return ;
}
void printArray(int* a, int n){
    for(int i = 0; i<n; i++)
    cout<<a[i]<<"\t";
    cout<<endl;
    return ;
}
void generateOrderedArray(int arr[], int n){
    for(int i = 0; i <n; i++){
        if(arr[i] >= 0 && i % 2 == 1){
            for(int j = i + 1; j <n; j++){
                if(arr[j] < 0 && j % 2 == 0){
                    swapElements(arr, i, j);
                    break ;
                }
            }
        }
        else if(arr[i] < 0 && i % 2 == 0){
            for(int j = i + 1; j <n; j++){
                if(arr[j] >= 0 && j % 2 == 1){
                    swapElements(arr, i, j);
                    break;
                }
            }
        }
    }
    printArray(arr, n);
}
int main(){
    int arr[] = { 1, -3, 5, 6, -3, 6, 7, -4, 9, 10 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Inital Array is : ";
    printArray(arr, n);
    cout<<"Array with positive numbers at even index and negative numbers at odd index :";
    generateOrderedArray(arr,n);
    return 0;
}

出力結果

Inital Array is : 3 5 -1 19 -7 -2
Array with positive numbers at even index and negative numbers at odd index : 3 -1 5 -7 19 -2

方法2：クイックソート風の双ポインタ手法

2つ目の方法は、クイックソートのパーティション処理に似たテクニックを応用したものです。正の数用と負の数用の2つのポインタを用意し、正の数用ポインタをインデックス0（偶数インデックス）に、負の数用ポインタをインデックス1（奇数インデックス）に初期化します。

その後、各ポインタを2ずつ前進させながら走査します。正の数用ポインタが負の数に到達し、かつ負の数用ポインタが正の数に到達した時点で両者を停止させ、その2つの要素をスワップします。この操作を繰り返し、いずれかのポインタが配列の範囲外に出た時点で処理を終了します。

方法1と比較すると、各要素を一度ずつしか参照しないため、より効率的に動作する点が特徴です。

実装例

上記の解法をC++で実装したプログラムは以下の通りです。

#include <iostream>
using namespace std;
void swapElements(int* a, int i , int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    return ;
}
void printArray(int *a, int n){
    for (int i = 0; i <n; i++)
    cout<<a[i]<<"\t";
    cout<<endl;
}
void generateOrderedArray(int a[], int size){
    int positive = 0, negative = 1;
    while (1) {
        while (positive < size && a[positive] >= 0)
        positive += 2;
        while (negative <size && a[negative] <= 0)
        negative += 2;
        if (positive < size && negative < size)
            swapElements(a, positive, negative);
        else
            break;
    }
}
int main(){
    int arr[] = { 3, 5, -1, 19, -7, -2 };
    int n = (sizeof(arr) / sizeof(arr[0]));
    cout<<"Inital Array is : ";
    printArray(arr, n);
    cout<<"Array with positive numbers at even index and negative numbers at odd index : ";
    generateOrderedArray(arr, n);
    printArray(arr, n);
    return 0;
}

出力結果

Inital Array is : 3 5 -1 19 -7 -2
Array with positive numbers at even index and negative numbers at odd index : 3 -1 5 -7 19 -2

まとめ

本記事では、配列内の正の数を偶数インデックスへ、負の数を奇数インデックスへ配置する2つのアルゴリズムを紹介しました。

• 方法1（線形探索＋スワップ）： 実装がシンプルで直感的ですが、入れ子のループにより最悪計算量はO(n²)になります。
• 方法2（双ポインタ方式）： クイックソート風のアプローチで、各要素を高々1回ずつ処理するためO(n)で動作し、大規模な配列に対して効率的です。

どちらの方法でも余分な要素は移動されないため、相対的な順序は保持されない点に注意してください。用途やデータサイズに応じて適切な手法を選択しましょう。