Chương trình C++ đếm số nghịch thế (Inversion) trong mảng

Đếm nghịch thế (Count inversion) nghĩa là số lần hoán đổi cần thiết để làm cho mảng được sắp xếp. Số nghịch thế = 0 khi mảng đã sắp xếp. Số nghịch thế = tối đa khi mảng sắp xếp theo thứ tự ngược.

Hãy phát triển chương trình C++ đếm nghịch thế trong mảng.

Thuật toán

Bắt đầu
  Hàm CountInversionArray có tham số a[], n = số phần tử.
    Khởi tạo bộ đếm c := 0
    với i từ 0 đến n-1, làm:
      với j từ (i + 1) đến n, làm:
        nếu a[i] > a[j], thì
          tăng đếm lên 1
        xong
      xong
Kết thúc.

Mã ví dụ

#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 << "\nNhập số phần tử: ";
    cin >> n;
    int a[n];
    for(i = 0; i < n; i++) {
        cout << "Nhập phần tử " << i+1 << ": ";
        cin >> a[i];
    }
    cout << "\nSố nghịch thế trong mảng: " << CountInversionArray(a, n);
    return 0;
}

Kết quả đầu ra

Nhập số phần tử: 5
Nhập phần tử 1: 3
Nhập phần tử 2: 2
Nhập phần tử 3: 7
Nhập phần tử 4: 6
Nhập phần tử 5: 1
Số nghịch thế trong mảng: 6