C++で個別にソート可能な配列パーティションの最大数を求めるアルゴリズム

問題の概要

0からN-1の範囲の値を含む、サイズNのソートされていない整数配列が与えられます。この配列を複数の部分（パーティション）に分割し、各部分を個別にソートしたうえで連結したとき、全体がソート済みの長さNの配列になるようにします。このとき実現できる分割数の最大値を求めるのが本記事のテーマです。

各パーティションの中身がソートされていなくても構いません。ただし、N個の要素が0〜N-1の範囲にちょうど1回ずつ現れるため、ソート後の配列では必ず「インデックスと値が一致する」（Arr[i] = i）という性質が成り立ちます。この性質が解法の鍵となります。

解法のアプローチ

各要素を左から順に走査し、それまでに登場した値の最大値（累積最大値）と比較していきます。累積最大値が現在のインデックスと一致した瞬間（maxx == i）が、パーティションの区切り地点です。

その理由は次のとおりです。インデックスiまでの要素はすべてmaxx（= i）以下であり、それより右側の要素はすべてmaxxより大きくなります。したがって、この位置で区切っても左側を独立したパーティションとして切り出せます。この手順を右側の残りの要素に対しても繰り返し、パーティションを順番に確定していきます。

具体例1

入力 − Arr[] = { 0, 3, 2, 1, 4, 5 }

出力 − 最大分割数 = 3

説明

• 先頭から開始し、maxx = Arr[0] = 0 とします。
• インデックス0〜3の間での最大値は3です。i = 3 に達した時点で maxx == i が成立するため、最初のパーティションは [0, 3, 2, 1] となります。
• インデックス4では最大値は4です。i = 4 で maxx == i となるため、2番目のパーティションは [4] です。
• インデックス5では最大値は5です。i = 5 で maxx == i となるため、3番目のパーティションは [5] です。

合計3つのパーティション [0,3,2,1]、[4]、[5] に分けられ、それぞれをソートして連結すれば全体が整列します。

具体例2

入力 − Arr[] = { 5, 4, 3, 2, 1, 0 }

出力 − 最大分割数 = 1

説明 − 累積最大値が5に達するのはインデックス5の位置だけです。つまり maxx == i が初めて成立するのが i = 5 のときであり、配列全体が唯一のパーティション [5, 4, 3, 2, 1, 0] となります。

アルゴリズムの手順

• 0〜N-1の範囲の数値で初期化された整数配列Num[]を用意します。
• 関数partitions(int arr[], int n)は、配列とその長さを受け取り、個別にソートして連結すれば全体がソート済みになるような最大分割数を返します。
• 分割数のカウンタcountを0で、累積最大値maxxをarr[0]で初期化します。
• 左端の要素から順にすべての要素を調べ、arr[i]がmaxxより大きいかどうかを確認します。
• arr[i] > maxx が成立する場合は、maxxをarr[i]に更新します。
• 現在のmaxxとインデックスが一致した場合（maxx == i）、インデックスiまでの要素が1つのパーティションを構成するため、countを1増やします。
• 右側の残りの要素に対しても、末尾に到達するまで同じ処理を繰り返します。
• 最後にcountを結果として返します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int partitions(int arr[], int n){
    int count = 0;
    int maxx = arr[0];
    for (int i = 0; i < n; ++i) {
       if(arr[i] > maxx)
          maxx=arr[i];
       if (maxx == i)
          count++;
    }
    return count;
}
int main(){
    int Num[] = { 2,1,0,4,5,3 };
    int len = 6;
    cout <<"Maximum partitions that can be sorted: "<<partitions(Num, len);
    return 0;
}

出力

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

Maximum partitions that can be sorted: 2

この例では、配列 { 2, 1, 0, 4, 5, 3 } に対して maxx == i が成立するのは i = 2 と i = 5 の2か所なので、パーティションは [2, 1, 0, 4, 5] と [3] の2つに分けられます。それぞれをソートして連結すると [0, 1, 2, 3, 4, 5] となり、正しく全体が整列していることが確認できます。

計算量

配列を先頭から一度だけ走査すればよいため、時間計算量はO(N)、追加で必要な補助メモリはO(1)で収まる、非常に効率的なアルゴリズムです。