C++で定数の追加メモリ(O(1))を使って正数と負数を再配置する方法

問題の概要

正の数と負の数が混在する整数型配列 arr[](サイズは任意)が与えられたとします。この課題では、定数の追加メモリ領域(O(1))のみを使用して、負の数を配列の前半に、正の数と 0 を後半に集めるように配列を並べ替えます。本記事では、C++ による実装方法と、その実行結果の出力までをわかりやすく解説します。

入出力シナリオの例

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

出力 − 定数の追加メモリで正数と負数を再配置した結果:-3 -1 -1 0 6 2 4

説明 − サイズ 7 の整数配列には正と負の両方の要素が含まれています。定数の追加メモリ領域で並べ替えを行うと、負の数(-3、-1、-1)が前半に集められ、最終的な結果は「-3 -1 -1 0 6 2 4」となります。

入力 − int arr[] = {-9, -10, 2, 3, 10, 5, 8, 4}

出力 − 定数の追加メモリで正数と負数を再配置した結果:-9 -10 2 3 10 5 8 4

説明 − サイズ 8 の整数配列には正と負の両方の要素が含まれています。この場合も定数の追加メモリ領域で並べ替えを行い、最終的な結果は「-9 -10 2 3 10 5 8 4」となります。

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

• 整数型要素からなる配列を入力として受け取り、配列のサイズを計算します。

• 並べ替えの前に、FOR ループを使って元の配列の内容を表示します。

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

• 関数 Rearrangement(arr, size) の内部では、以下の処理を行います。

  • 整数型変数として i を 0、j を size - 1 で初期化します。

  • while(true) ループを開始します。ループ内では、まず「arr[i] が 0 未満 かつ i が size 未満」である間、i を 1 ずつ増やします。

  • 次に、「arr[j] が 0 より大きく かつ j が 0 以上」である間、j を 1 ずつ減らします。

  • i が j より小さい場合は、一時変数 temp を使って arr[i] と arr[j] の値を交換します。

  • それ以外の場合は break によってループを終了します。

• 最終的な結果を出力します。

この手法は両側からの二ポインタ(two-pointer)方式と呼ばれ、追加の配列を一切必要としないため、空間計算量 O(1) を実現できます。時間計算量は O(n) となり、非常に効率的な並べ替え方法です。

コード例

#include<iostream>
using namespace std;
void Rearrangement(int arr[], int size){
    int i = 0;
    int j = size - 1;
    while(true){
        // 左側から「負ではない」要素を探す
        while(arr[i] < 0 && i < size){
            i++;
        }
        // 右側から「正である」要素を探す
        while(arr[j] > 0 && j >= 0){
            j--;
        }
        if (i < j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        else{
            break;
        }
    }
}
int main(){
    int arr[] = {4, 2, -1, -1, 6, -3, 0};
    int size = sizeof(arr)/sizeof(arr[0]);
    // 配列を並べ替える関数を呼び出す
    Rearrangement(arr, size);
    // 並べ替え後の配列を表示する
    cout<<"定数の追加メモリで正数と負数を再配置した結果: ";
    for(int i = 0; i < size; i++){
        cout<< arr[i] << " ";
    }
    return 0;
}

出力

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

定数の追加メモリで正数と負数を再配置した結果: -3 -1 -1 0 6 2 4