C++で配列内のクロスラインをカウントする

• Arr []={1,2,4,3,5}以下に示すように3本の十字線があります

• Arr []={1,2,3,4,5}。配列はすでにソートされているため、クロスラインはありません。

挿入ソートを使用してクロスラインをカウントします。挿入ソートでは、右側の要素が左側の並べ替えられた要素に追加されます。ソートされたパーツに要素が追加されるたびに、正しい位置に移動するたびにカウントが増加します。それは、より大きいすべての要素を交差させることによって通過します。

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

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

出力 −配列内のクロスラインの数− 5

説明 − 4-4行目と3-3行目は、1-1行目と2-2行目と交差しています。合計4本のクロスライン。

4-4と3-3の両方が一度交​​差します。合計4+1=5のクロスライン。

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

出力 −配列内のクロスラインの数− 1

説明 −5-5と3-3の両方が1回交差します。合計1本のクロスライン。

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

• 個別の数値で初期化された整数配列arr[]を使用します。

• 関数insertionSort（int arr []、int n）は、配列とその長さを入力として受け取り、並べ替えた後、結果としてクロスラインの数を返します。

• クロスラインの初期数を0とします。カウント変数が使用されます。

• 最初の要素はすでに並べ替えられているため、2番目の要素から最後まで（i =1からi

• >itemかつj>0の場合、すべての要素を右にシフトします。シフト増分ごとに、これらすべてがアイテムと交差するため、カウントされます。

• whileループの最後に、アイテムをarr [j+1]という正しい位置に配置します。

• すべての要素に対してこれを行い、それらが交差する要素を数えます。

• カウントの値をnoとしてインクリメントします。可能なクロスラインの数。

例

#include <bits/stdc++.h>
using namespace std;
int insertionSort(int arr[], int n){
   int count=0;
   int item;
   int j;
   for (int i = 1; i < n; i++){
      item = arr[i];
      j = i - 1;
      //insert element at correct position in sorted part, no. of elements it passes
      //from right till correct position is count of cross lines.
      while (j >= 0 && arr[j] > item){
         arr[j + 1] = arr[j];
         j = j - 1;
         count++;
      }
      arr[j + 1] = item;
   }
   return count;
}
int main(){
   int arr[] = { 4,5,3,1,2};
   int n = 5;
   cout<<"Number of cross lines: "<<insertionSort(arr, n);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Number of cross lines: 8