[演算法筆記] Counting Inversions

問題描述

  1. input: 一個陣列 A
  2. output: inversions 的數量,也就是滿足陣列索引 i<jA[i] > A[j] 的個數

想法

  1. 採用 divide and conquer 策略
    • divide 成兩個子問題,分別求出陣列左右兩半個別的 inversions 數目(假設我們將之稱作 left inversion 以及 right inversion)
    • 接著我們還需要計算 split inversion 的數目,也就是其中一個元素來自 left subarray,另一個來自 right subarray 的 inversion 個數
  2. 借助 merge sort 的力量,一邊排序一邊計算 inversions 之數目
  3. 假設已有 sorted array B 和 C,merge sort 之 merge 的過程即為不斷選出兩個 array 的最小值,將其 copy 到 output array D
    • 由此可知,每當我們從 sorted array C copy 元素到 ouput array D 且 sorted array B 還有元素沒被 copy 到 array D 時,代表有「array B 剩下還沒被 copy 到 array D 的元素總數」個 split inversions
    • 利用這個概念,我們便可以設計出一個 based on merge sort 的 divide and conquer algorithm

C implementation

int sort_and_count(int a[], int l, int r) {
  if (l == r) {
    return 0; 
  } else {
    int mid = (l+r)/2;
    int first = sort_and_count(a, l, mid);
    int second = sort_and_count(a, mid+1, r);

    int i=l;
    int j=mid+1;
    int k=0;
    int output[r-l+1];
    int inversion=0;

    while (i <= mid && j <= r) {
       if (a[i] <= a[j]) {
         output[k++] = a[i++];
       } else {
         output[k++] = a[j++];
         inversion += (mid-i)+1;
       }
    }
    while (i <= mid) {
       output[k++] = a[i++];
    }
    while (j <= r) {
       output[k++] = a[j++];
    }

    k=0;
    for (int i = l; i <= r; i++) {
      a[i] = output[k++];
    }
    return inversion + first + second;
  }
}

int main(int argc, const char *argv[])
{
  int a[] = {1,3,5,2,4,6};
  int len = sizeof(a)/sizeof(int);
  int in = sort_and_count(a, 0, len-1);
  printf("inversions count: %d\n", in);
  return 0;
}
comments powered by Disqus
分享至 Facebook 分享至 Google +