এই টিউটোরিয়ালে, আমরা C++ STL-এ সেট ব্যবহার করে ইনভার্শন গণনা করার একটি প্রোগ্রাম আলোচনা করব।
ইনভার্শন কাউন্ট হলো অ্যারেটি কতটুকু সম্পূর্ণ সোর্টেড সেটির নিকট তা মাপার একটি স্কেল। যদি অ্যারে ইতিমধ্যে সোর্টেড থাকে, তবে ইনভার্শন কাউন্ট হবে ০।
উদাহরণ
#include<bits/stdc++.h> using namespace std; //returning inversion count int get_Icount(int arr[],int n){ multiset<int> set1; set1.insert(arr[0]); int invcount = 0; //initializing result multiset<int>::iterator itset1; for (int i=1; i<n; i++){ set1.insert(arr[i]); itset1 = set1.upper_bound(arr[i]); invcount += distance(itset1, set1.end()); } return invcount; } int main() { int arr[] = {8, 4, 2, 1}; int n = sizeof(arr)/sizeof(int); cout << "Number of inversions count are : "<< get_Icount(arr,n); return 0; }আউটপুট
Number of inversions count are : 6
