Đếm số cặp nghịch thế trong mảng

Số cặp nghịch thế của một mảng cho biết cần bao nhiêu thay đổi để chuyển mảng đó về dạng đã sắp xếp. Khi mảng đã được sắp xếp, nó cần 0 nghịch thế, và trong trường hợp ngược lại, số nghịch thế sẽ tối đa nếu mảng bị đảo ngược.

Để giải quyết bài toán này, ta sử dụng phương pháp sắp xếp trộn (Merge Sort) để giảm độ phức tạp thời gian, biến nó thành thuật toán Chia để trị (Divide and Conquer).

Đầu vào và Đầu ra

Đầu vào: Một dãy số. (1, 5, 6, 4, 20).
Đầu ra: Số lượng nghịch thế cần thiết để sắp xếp các số theo thứ tự tăng dần. Ở đây số nghịch thế là 2.
Nghịch thế đầu tiên: (1, 5, 4, 6, 20)
Nghịch thế thứ hai: (1, 4, 5, 6, 20)

Thuật toán

merge(array, tempArray, left, mid, right)

Đầu vào: Hai mảng cần trộn, chỉ số trái, phải và giữa.

Đầu ra: Mảng đã trộn theo thứ tự sắp xếp.

Bắt đầu
  i := left, j := mid, k := right
  count := 0
  trong khi i <= mid - 1 và j <= right, thực hiện
    nếu array[i] <= array[j] thì
      tempArray[k] := array[i]
      tăng i và k lên 1
    ngược lại
      tempArray[k] := array[j]
      tăng j và k lên 1
      count := count + (mid - i)
  kết thúc vòng lặp
  trong khi phần trái còn phần tử thừa, thực hiện
    tempArray[k] := array[i]
    tăng i và k lên 1
  kết thúc
  trong khi phần phải còn phần tử thừa, thực hiện
    tempArray[k] := array[j]
    tăng j và k lên 1
  kết thúc
  trả về count
Kết thúc

mergeSort(array, tempArray, left, right)

Đầu vào: Mảng cho trước, mảng tạm, chỉ số trái và phải của mảng.

Đầu ra: Số lượng nghịch thế sau khi sắp xếp.

Bắt đầu
  count := 0
  nếu right > left thì
    mid := (right + left)/2
    count := mergeSort(array, tempArray, left, mid)
    count := count + mergeSort(array, tempArray, mid+1, right)
    count := count + merge(array, tempArray, left, mid+1, right)
  trả về count
Kết thúc

Ví dụ (C++)

#include <iostream>
using namespace std;

int merge(int arr[], int temp[], int left, int mid, int right) {
  int i, j, k;
  int count = 0;
  i = left; // i để xác định vị trí mảng đầu tiên
  j = mid;  // j để xác định vị trí mảng thứ hai
  k = left; // k để xác định vị trí mảng đã trộn
  
  while ((i <= mid - 1) && (j <= right)) {
    if (arr[i] <= arr[j]) { // khi phần tử trái nhỏ hơn phần tử phải
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
      count += (mid - i); // tìm số lượng chuyển đổi được thực hiện
    }
  }
  
  while (i <= mid - 1) // nếu danh sách đầu còn phần tử, thêm vào
    temp[k++] = arr[i++];
  while (j <= right)   // nếu danh sách thứ hai còn phần tử, thêm vào
    temp[k++] = arr[j++];
  
  for (i = left; i <= right; i++)
    arr[i] = temp[i]; // lưu mảng tạm vào mảng chính
  
  return count;
}

int mergeSort(int arr[], int temp[], int left, int right) {
  int mid, count = 0;
  if (right > left) {
    mid = (right + left)/2; // tìm chỉ số giữa của mảng
    count = mergeSort(arr, temp, left, mid); // sắp xếp trộn mảng con trái
    count += mergeSort(arr, temp, mid+1, right); // sắp xếp trộn mảng con phải
    count += merge(arr, temp, left, mid+1, right); // trộn hai mảng con
  }
  return count;
}

int arrInversion(int arr[], int n) {
  int temp[n];
  return mergeSort(arr, temp, 0, n - 1);
}

int main() {
  int arr[] = {1, 5, 6, 4, 20};
  int n = 5;
  cout << "Number of inversions are " << arrInversion(arr, n);
}

Đầu ra

Number of inversions are 2