C++ STL에서 Set을 사용하여 반전 계산

이 튜토리얼에서는 C++ STL에서 set을 사용하여 반전을 계산하는 프로그램에 대해 논의할 것입니다.

반전 카운트는 배열이 완전히 정렬되는 정도를 측정한 것입니다. 배열이 이미 정렬된 경우 반전 횟수는 0이 됩니다.

예시

#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