C++ প্রোগ্রাম: অ্যারেতে ইনভার্শন কাউন্ট করা

ইনভার্শন কাউন্ট মানে একটি অ্যারেকে সোর্টেড করার জন্য কতটুকু সวিচিং বা অদলবদল প্রয়োজন। ইনভার্শন কাউন্ট = 0, যখন অ্যারে সোর্টেড থাকে। ইনভার্শন কাউন্ট = সর্বোচ্চ, যখন অ্যারে রিভার্স অর্ডারে সোর্টেড থাকে।

চলুন অ্যারেতে ইনভার্শন কাউন্ট করার একটি C++ প্রোগ্রাম তৈরি করি।

শুরু
  CountInversionArray ফাংশনের আর্গুমেন্ট: a[], n = এলিমেন্ট সংখ্যা
    কাউন্টার c := 0 ইনিশিয়ালাইজ করুন
    i = 0 থেকে n-1 পর্যন্ত লুপ চালান
      j = (i + 1) থেকে n পর্যন্ত লুপ চালান
        যদি a[i] > a[j] হয়, তবে কাউন্ট 1 বাড়ান
      শেষ
    শেষ
শেষ

#include 
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