একটি অ্যারেতে ইনভার্সন গণনা করার জন্য C++ প্রোগ্রাম

কাউন্ট ইনভার্সশন মানে একটি অ্যারে সাজানোর জন্য প্রয়োজনীয় সুইচের সংখ্যা। বিপরীত সংখ্যা =0, যখন অ্যারে সাজানো হয়। বিপরীত সংখ্যা =সর্বাধিক, যখন অ্যারে বিপরীত ক্রমে সাজানো হয়।

আসুন একটি অ্যারেতে ইনভার্সন গণনা করার জন্য একটি C++ প্রোগ্রাম তৈরি করি।

অ্যালগরিদম

Begin
   Function CountInversionArray has arguments a[], n = number of elements.
   initialize counter c := 0
   for i in range 0 to n-1, do
      for j in range (i + 1) to n, do
         if a[i] > a[j], then
            increase the count by 1
         done
      done
End.

উদাহরণ কোড

#include<iostream>
using namespace std;
int CountInversionArray(int a[], int n) {
   int i, j, c = 0;
   for(i = 0; i < n; i++) {
      for(j = i+1; j < n; j++)
         if(a[i] > a[j])
            c++;
   }
   return c;
}
int main() {
   int n, i;
   cout<<"\nEnter the number of elements: ";
   cin>>n;
   int a[n];
   for(i = 0; i < n; i++) {
      cout<<"Enter element "<<i+1<<": ";
      cin>>a[i];
   }
   cout<<"\nThe number of inversion in the array: "<<CountInversionArray(a, n);
   return 0;
}

আউটপুট

Enter the number of elements: 5
Enter element 1: 3
Enter element 2: 2
Enter element 3: 7
Enter element 4: 6
Enter element 5: 1

The number of inversion in the array: 6