C++でO(1)の追加メモリを使って配列の正と負の要素を交互に並べ替える方法

正の数と負の数が混在する整数型の配列 arr[] が与えられたとき、正の数が負の数に挟まれる形で交互に並ぶように配列を並べ替えるのが本記事の課題です。どちらかの符号の要素が余った場合は、それらは配列の末尾にまとめて配置されます。ここでは、O(1)の追加メモリ（定数個の補助変数のみ）でこの処理を実現する方法を解説します。

入出力シナリオの例

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

出力 − 並べ替え前の配列：-1 -2 -3 1 2 3
O(1)の追加メモリで正負の要素を交互に並べ替えた結果：-1 1 -2 2 -3 3

説明 − サイズ6の整数配列に正と負の要素が含まれています。すべての正の要素が負の要素に挟まれるように並べ替え、余った要素は末尾に配置します。この場合、「-1 1 -2 2 -3 3」が最終的な結果となります。

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

出力 − 並べ替え前の配列：-1 -2 -3 1 2 3 5 5 -5 3 1 1
O(1)の追加メモリで正負の要素を交互に並べ替えた結果：-1 1 -2 2 -3 3 -5 5 5 3 1 1

説明 − サイズ12の整数配列に正と負の要素が含まれています。交互に配置できる範囲では正の要素を負の要素で挟むように並べ替え、残りの余分な要素はそのまま配列の末尾へ移動させます。最終結果は「-1 1 -2 2 -3 3 -5 5 5 3 1 1」となります。

プログラムで使用しているアプローチ

• 整数型の要素からなる配列を入力し、配列のサイズを求めます。

• FORループを使って、並べ替えを行う前の配列の内容を出力します。

• 配列とそのサイズを引数として、Rearrangement(arr, size) 関数を呼び出します。

• Rearrangement(arr, size) 関数の内部

  • 整数型変数 ptr を宣言し、-1 で初期化します。

  • i を 0 から size 未満まで進める FOR ループを開始します。ループ内で ptr が 0 以上の場合、arr[i] が正かつ arr[ptr] が負、または arr[i] が負かつ arr[ptr] が正であるときに move_array(arr, size, ptr, i) を呼び出します。さらに i - ptr が 2 以上なら ptr を ptr + 2 に更新し、そうでなければ ptr を -1 に戻します。

  • ptr が -1 の場合は、arr[i] が正かつ i が偶数、または arr[i] が負かつ i が奇数であるときに ptr を i に設定します。

• move_array(int arr[], int size, int ptr, int temp) 関数の内部

  • 変数 ch を宣言し、arr[temp] の値を保存します。

  • i を temp から開始し、ptr より大きい間、各要素を一つ後ろへずらす FOR ループを実行します（arr[i] = arr[i - 1]）。

  • arr[ptr] に ch を代入することで、対象の要素を目的の位置へ挿入します。

コード例

#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
   char ch = arr[temp];
   for(int i = temp; i > ptr; i--){
      arr[i] = arr[i - 1];
   }
   arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
   int ptr = -1;
   for(int i = 0; i < size; i++){
      if (ptr >= 0){
         if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
            move_array(arr, size, ptr, i);
            if(i - ptr >= 2){
               ptr = ptr + 2;
            }
            else{
               ptr = -1;
            }
         }
      }
      if(ptr == -1){
         if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
            ptr = i;
         }
      }
   }
}
int main(){
   // 配列の入力
   int arr[] = {-1, -2, -3, 1, 2, 3};
   int size = sizeof(arr) / sizeof(arr[0]);
   // 元の配列を出力
   cout<<"Array before Arrangement: ";
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   // 配列を並べ替える関数を呼び出し
   Rearrangement(arr, size);
   // 並べ替え後の配列を出力
   cout<<"\nRearrangement of an array in alternating positive & negative items with O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

出力

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

Array before Arrangement: -1 -2 -3 1 2 3
Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3