การนับการผกผันในอาร์เรย์ (Count Inversions)

การผกผัน (Inversion) ในอาร์เรย์แสดงถึงจำนวนการเปลี่ยนแปลงที่จำเป็นเพื่อจัดเรียงอาร์เรย์ให้เป็นลำดับจากน้อยไปมาก หากอาร์เรย์เรียงลำดับแล้ว จะต้องใช้ 0 การผกผัน ในขณะที่อาร์เรย์ที่เรียงจากมากไปน้อยจะมีจำนวนการผกผันสูงสุด

เพื่อแก้ปัญหานี้อย่างมีประสิทธิภาพ เราจะใช้แนวคิดของ Merge Sort ซึ่งเป็นอัลกอริทึมแบบ Divide and Conquer เพื่อลดความซับซ้อนของเวลาลงเหลือ O(n log n)

การรับค่าและแสดงผล

Input: ลำดับตัวเลข (1, 5, 6, 4, 20)
Output: จำนวนการผกผันที่ต้องใช้จัดเรียงเป็นลำดับเพิ่มขึ้น
ผลลัพธ์: 2 การผกผัน
ครั้งที่ 1: (1, 5, 4, 6, 20)
ครั้งที่ 2: (1, 4, 5, 6, 20)

อัลกอริทึม

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

Input: สองอาร์เรย์ที่จะรวมกัน ดัชนี left, right และ mid

Output: อาร์เรย์ที่รวมและเรียงลำดับแล้ว

Begin
  i := left, j := mid, k := left
  count := 0
  while i <= mid - 1 and j <= right do
    if array[i] <= array[j] then
      tempArray[k] := array[i]
      เพิ่ม i และ k ขึ้น 1
    else
      tempArray[k] := array[j]
      เพิ่ม j และ k ขึ้น 1
      count := count + (mid - i)
    end if
  done
  
  while ส่วนซ้ายยังมีข้อมูลเหลือ do
    tempArray[k] := array[i]
    เพิ่ม i และ k ขึ้น 1
  done
  
  while ส่วนขวายังมีข้อมูลเหลือ do
    tempArray[k] := array[j]
    เพิ่ม j และ k ขึ้น 1
  done
  
  return count
End

mergeSort(array, tempArray, left, right)

Input: อาร์เรย์ที่กำหนด อาร์เรย์ชั่วคราว ดัชนี left และ right

Output: จำนวนการผกผันหลังจากจัดเรียงแล้ว

Begin
  count := 0
  if right > left then
    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)
  return count
End

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

int merge(int arr[], int temp[], int left, int mid, int right) {
  int i = left, j = mid, k = left;
  int count = 0;
  
  while ((i <= mid - 1) && (j <= right)) {
    if (arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
      count += (mid - i);
    }
  }
  
  while (i <= mid - 1)
    temp[k++] = arr[i++];
  
  while (j <= right)
    temp[k++] = arr[j++];
  
  for (i = left; i <= right; i++)
    arr[i] = temp[i];
  
  return count;
}

int mergeSort(int arr[], int temp[], int left, int right) {
  int mid, count = 0;
  if (right > left) {
    mid = (right + left) / 2;
    count = mergeSort(arr, temp, left, mid);
    count += mergeSort(arr, temp, mid + 1, right);
    count += merge(arr, temp, left, mid + 1, right);
  }
  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);
}

ผลลัพธ์

Number of inversions are 2