C ++で配列をソートするために、「前に移動」移動の最小数をカウントします

1からnまでの数の配列が与えられます。ここでの目標は、いいえを見つけることです。指定された配列をソートするために必要な「movetofront」操作の数。配列には繰り返しがありません。 「前に移動」操作は要素を選択し、最初の位置、ここではインデックス0に配置します。

要素が正しい位置にある場合は、配列を最後からトラバースします。それ以外の場合は、移動する必要はありません。 1からnまでの要素の場合、要素arr[i]の配列内の正しい位置はインデックスi+1を上回る必要があります。 arr [0]は1、arr [1]は2、…….arr[n-1]はnである必要があります。

入力

Arr[]= { 4,3,2,1 }

出力

Minimum move-to-front operations: 3

説明

Pull 3, 3,4,2,1 count=1
Pull 2, 2,3,4,1 count=2
Pull 1, 1,2,3,4 count=3

入力

Arr[]= { 6,1,2,5,4,3 }

出力

Minimum move-to-front operations: 5

説明

Pull 5, 5,6,1,2,4,3 count=1
Pull 4, 4,5,6,1,2,3 count=2
Pull 3, ,4,5,6,1,2 count=3
Pull 2, 2,3,4,5,6,1 count=4
Pull 1, 1,2,3,4,5,6 count=5

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

• 整数配列Arr[]は、1からnまでの数値を格納します。

• 整数変数サイズは、配列Arr []

  の長さを格納します

• 関数movetoFront（int arr []、int n）は、配列とその長さを入力として受け取り、その指定された配列をソートするために必要な「前に移動」操作の最小数を返します。

• 配列の順序が減少した場合はすべての要素を移動できるため、カウント変数は配列のサイズで初期化されます。

• 要素の値がカウントと同じである場合（1からnの間でソートされた要素の場合、nが最後、n-1が最後から2番目など）、最後のインデックスからトラバースを開始し、前に移動します。次に、その要素としてカウントをデクリメントします。正しい位置にあります。

• このようにして、ループの最後で、カウントは望ましい結果をもたらします。

例

#include <bits/stdc++.h>
using namespace std;
// Calculate minimum number of moves to arrange array
// in increasing order.
int movetoFront(int arr[], int n){
   //take count as all elements are correctly placed
   int count = n;
   // Traverse array from end
   for (int i=n-1; i >= 0; i--){
      // If current item is at its correct position,
         //decrement the count
      //range is 1 to n so every arr[i] should have value i+1
      //1 at 0 index, 2 at 1 index........
      if (arr[i] == count)
         count--;
   }
   return count;
}
int main(){
   int Arr[] = {5, 3, 4, 7, 2, 6, 1};
   int size = 7;
   cout <<"Minimum 'move-to-front' to sort array:"<< movetoFront(Arr, size);
   return 0;
}

出力

Minimum 'move-to-front' to sort array:6