একটি অ্যারের মধ্যে বিপরীত গণনা

একটি অ্যারের ইনভার্সন নির্দেশ করে; অ্যারেটিকে সাজানো ফর্মে রূপান্তর করতে কতগুলি পরিবর্তন প্রয়োজন। যখন একটি অ্যারে ইতিমধ্যে বাছাই করা হয়, তখন এটির 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)

অ্যালগরিদম

মার্জ (অ্যারে, টেম্পঅ্যারে, বাম, মধ্য, ডান)

ইনপুট: দুটি অ্যারে, যারা একত্রিত হয়েছে, বাম, ডান এবং মধ্য সূচক৷

আউটপুট: সাজানো ক্রমে মার্জ করা অ্যারে।

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, left, right)

ইনপুট:৷ একটি অ্যারে এবং অস্থায়ী অ্যারে দেওয়া হয়েছে, অ্যারের বাম এবং ডান সূচক।

আউটপুট − বাছাই করার পরে বিপরীতের সংখ্যা।

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