C++でO(n)時間・O(1)の追加メモリで正負の数を交互に並べ替える方法

本記事では、正の数と負の数が混在した整数型配列 arr[] を扱います。目標は、この配列を正の数と負の数が交互に配置されるように並べ替えることです。どちらか一方の符号の要素が余った場合は、それらを配列の末尾にまとめて配置します。

ここで重要なのは、計算量を O(n) 時間、追加メモリを O(1)（つまり定数個の補助変数のみ）に抑えた実装を行う点です。

入出力のシナリオ例

入力： int arr[] = {4, 2, -1, -1, 6, -3}

出力： O(n) 時間・O(1) の追加メモリで並べ替えた結果： 2 -1 6 -1 4 -3

説明： サイズ6の整数配列には正と負の要素が混在しています。並べ替え後は、正の要素と負の要素が交互に並び、余分な要素は末尾に移動します。最終結果は「2 -1 6 -1 4 -3」となります。

入力： int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}

出力： O(n) 時間・O(1) の追加メモリで並べ替えた結果： 2 -2 3 -5 5 -3 5 -1 1 3 1 1

説明： サイズ12の整数配列に対して同様の処理を行います。正と負の要素を交互に並べた結果、余った正の要素は配列の末尾に配置され、「2 -2 3 -5 5 -3 5 -1 1 3 1 1」が出力されます。

アルゴリズムの考え方

• 整数型の配列を入力として受け取り、そのサイズを求めます。
• FORループを使って、並べ替え前の配列の内容を出力します。
• 配列とサイズを引数として関数 Rearrangement(arr, size) を呼び出します。
• 関数 Rearrangement(arr, size) の内部では以下の処理を行います。
  • 一時的な整数型変数 temp を -1 で初期化し、positive を temp + 1、negative を 0 として宣言します。
  • i を 0 から配列サイズ未満まで回す FORループを実行します。ループ内で arr[i] が 0 未満の場合は temp を1増やし、C++ STL の組み込み関数 swap(arr[temp], arr[i]) を呼び出して要素を交換します。この処理により、負の数がすべて配列の前半に集まります。
  • 次に、positive が配列サイズ未満 かつ negative が positive 未満 かつ arr[negative] が 0 未満である間、WHILEループを繰り返します。ループ内では swap(arr[negative], arr[positive]) によって要素を交換し、positive を1増やし、negative を 2 増やします。これにより、正負が交互になるように入れ替えが進みます。
• 最後に結果を出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
    int temp = -1;
    for(int i = 0; i < size; i++){
        if (arr[i] < 0){
            temp++;
            swap(arr[temp], arr[i]);
        }
    }
    int positive = temp + 1;
    int negative = 0;
    while(positive < size && negative < positive && arr[negative] < 0){
        swap(arr[negative], arr[positive]);
        positive++;
        negative = negative + 2;
    }
}
int main(){
    int arr[] = {4, 2, -1, -1, 6, -3};
    int size = sizeof(arr)/sizeof(arr[0]);
    //配列を並べ替える関数を呼び出す
    Rearrangement(arr, size);
    //並べ替え後の配列を出力する
    cout<<"Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: ";
    for(int i = 0; i < size; i++){
        cout<< arr[i] << " ";
    }
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3

まとめ

このアルゴリズムは、まずクイックソートのパーティション操作のように負の数を配列の前半へ集め、その後にポインタを進めながら正負を交互に入れ替えるという2段階構成になっています。各要素は高々一度ずつ処理されるため全体の時間計算量は O(n)、追加のデータ構造を使用しないため空間計算量は O(1) となります。ただし、元の要素の相対順序（安定性）は保持されない点に注意してください。