配列をソートするための操作をカウントするC++コード

n個の要素を持つ配列Aがあるとします（nは奇数です）。 Aには、最初のnnatural数の順列が含まれています。関数f（i）があるとします。これは、0からn-2の範囲の単一の引数iを取り、操作を実行します。A[i]> A [i + 1]の場合、A[i]とA[の値を交換します。 i+1]。配列Aを初めてソートするには、反復回数をカウントする必要があります。

したがって、入力がA =[4、5、7、1、3、2、6]の場合、各反復後の配列の状態は[4、5、1、7]のようになるため、出力は5になります。 2、3、6]、[4、1、5、2、7、3、6]、[1、4、2、5、3、7、6]、[1、2、4、3、5 6、7]、[1、2、3、4、5、6、7]。

ステップ

これを解決するには、次の手順に従います-

n := size of A
f := 0
Ans := 0
for initialize Ans := 0, do:
   f := 0
   for initialize j := 0, when j < n - 1, update (increase j by 1), do:
      if A[j] > A[j + 1], then:
         f := 1
      if not f is non-zero, then:
         Come out from the loop
      for initialize j := (Ans AND 1), when j < n - 1, update j := j + 2, do:
         if A[j] > A[j + 1], then:
            swap A[j] and A[j + 1]
         (increase Ans by 1)
return Ans

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
   int n = A.size();
   bool f = 0;
   int Ans = 0;
   for (Ans = 0;;){
      f = 0;
      for (int j = 0; j < n - 1; j++)
      if (A[j] > A[j + 1])
         f = 1;
      if (!f)
         break;
      for (int j = (Ans & 1); j < n - 1; j += 2)
         if (A[j] > A[j + 1])
            swap(A[j], A[j + 1]);
      Ans++;
   }
   return Ans;
}
int main(){
   vector<int> A = { 4, 5, 7, 1, 3, 2, 6 };
   cout << solve(A) << endl;
}

入力

{ 4, 5, 7, 1, 3, 2, 6 }

出力

5