C++でソートするために個別にソートできるパーティションの最大数

各パーティションは、その中の要素がソートされないように選択されます。 0からN-1の範囲のN個の数値の場合、ソートされた要素のインデックスは値と等しくなります。 Arr [i]=i。

これを解決するには、各要素をその左側でこれまでに見つかった最大値で比較します。最大値の正しい位置に到達すると、（最大値==i）。左側のすべての要素が少ないため、個別のパーティションを作成できます。その右側のすべてが大きいです。次に、残りの適切な要素に対して同じ手順を実行し、それらをパーティションに分割します。

例を挙げて理解しましょう。

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

出力 −パーティションの最大数− 3

説明 − 0から始めて、max =0 Arr [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）。したがって、2番目のパーティションは[5]

合計3つのパーティション[0,3,2,1][4][5]。それぞれを並べ替えて連結します。

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

出力 −パーティションの最大数− 1

説明 − 0から始めて、max =0 Arr [0]

インデックス0と5の間。5が最大です。インデックスi=5（maxx ==i）に到達したとき。したがって、パーティションのみが[5,4,3,2,1,0]

以下のプログラムで使用されているアプローチは次のとおりです

• 0からNの範囲の数値で初期化された整数配列Num[]を使用します。

• 関数partitions（int arr []、int n）は、配列とその長さをパラメーターとして受け取り、配列全体をソートするために個別にソートできる最大パーティションの数を返します。

• 初期パーティションカウントは0です。初期最大値は、arr[0]としてmaxxにあります。

• 左端の要素から始まるすべての要素。 maxxより大きいかどうかを確認します。

• arr[i]>maxxがtrueの場合。 maxxを更新します。

• 現在のmaxxとindexが同じ場合。 （maxx ==i）次に、iまでのすべての要素が1つのパーティションの一部になります。インクリメントカウント。

• 右側の残りの要素について、これを最後まで行います。

• 結果をカウントとして返します。

例

#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: 18