นับการผกผันในอาร์เรย์

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

ในการแก้ปัญหานี้ เราจะปฏิบัติตามวิธีการจัดเรียงแบบผสานเพื่อลดความซับซ้อนของเวลา และทำให้เป็นอัลกอริทึมแบบแบ่งและพิชิต

อินพุตและเอาต์พุต

Input:
A sequence of numbers. (1, 5, 6, 4, 20).
Output:
The number of inversions required to arrange the numbers into ascending order.
Here the number of inversions are 2.
First inversion: (1, 5, 4, 6, 20)
Second inversion: (1, 4, 5, 6, 20)

อัลกอริทึม

ผสาน (array, tempArray, ซ้าย, กลาง, ขวา)

อินพุต: สองอาร์เรย์ที่รวมกันแล้ว ดัชนีซ้าย ขวา และกลาง

ผลลัพธ์: อาร์เรย์ที่ผสานในลำดับการจัดเรียง

Begin
   i := left, j := mid, k := right
   count := 0
   while i <= mid -1 and j <= right, do
      if array[i] <= array[j], then
         tempArray[k] := array[i]
         increase i and k by 1
      else
         tempArray[k] := array[j]
         increase j and k by 1
         count := count + (mid - i)
   done

   while left part of the array has some extra element, do
      tempArray[k] := array[i]
      increase i and k by 1
   done

   while right part of the array has some extra element, do
      tempArray[k] := array[j]
      increase j and k by 1
   done

   return count
End

mergeSort(array, tempArray, ซ้าย, ขวา)

อินพุต: กำหนดอาร์เรย์และอาร์เรย์ชั่วคราว ดัชนีซ้ายและขวาของอาร์เรย์

ผลลัพธ์ - จำนวนการผกผันหลังจากการเรียงลำดับ

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

ตัวอย่าง

#include <iostream>
using namespace std;

int merge(intarr[], int temp[], int left, int mid, int right) {
   int i, j, k;
   int count = 0;
   
   i = left;    //i to locate first array location
   j = mid;     //i to locate second array location
   k = left;    //i to locate merged array location

   while ((i <= mid - 1) && (j <= right)) {
      if (arr[i] <= arr[j]) {    //when left item is less than right item
         temp[k++] = arr[i++];
      }else{
         temp[k++] = arr[j++];
         count += (mid - i);    //find how many convertion is performed
      }
   }

    while (i <= mid - 1)    //if first list has remaining item, add them in the list
       temp[k++] = arr[i++];

    while (j <= right)    //if second list has remaining item, add them in the list
       temp[k++] = arr[j++];
   
    for (i=left; i <= right; i++)
       arr[i] = temp[i];    //store temp Array to main array
    return count;
}

intmergeSort(intarr[], int temp[], int left, int right) {
   int mid, count = 0;

   if (right > left) {
      mid = (right + left)/2;    //find mid index of the array
      count  = mergeSort(arr, temp, left, mid);    //merge sort left sub array
      count += mergeSort(arr, temp, mid+1, right);    //merge sort right sub array
         
      count += merge(arr, temp, left, mid+1, right);    //merge two sub arrays
   }
   return count;
}

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

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

ผลลัพธ์

Number of inversions are 2