นับ Inversion ด้วย Set ใน C++ STL

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมนับ inversion (การกลับค่าคลาดเคลื่อน) โดยใช้ set ใน C++ STL

Inversion count คือตัววัดว่า อาร์เรย์ใกล้เคียงกับการเรียงลำดับสมบูรณ์แค่ไหน ถ้าอาร์เรย์เรียงแล้ว inversion count จะเป็น 0

ตัวอย่างโค้ด

#include <bits/stdc++.h> 
using namespace std; 

// คืนค่า inversion count
int get_Icount(int arr[], int n) {
    multiset<int> set1;
    set1.insert(arr[0]);
    int invcount = 0; // เริ่มต้นผลลัพธ์
    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