অ্যারেতে ইনভার্শন গণনা (Count Inversions in an Array)

একটি অ্যারেতে ইনভার্শন বোঝায় কতগুলো পরিবর্তন প্রয়োজন তা অ্যারেটিকে সর্ট করা ফর্মে রূপান্তর করতে। যখন একটি অ্যারে ইতিমধ্যে সর্ট করা থাকে, তখন ০ ইনভার্শন প্রয়োজন, আর যখন অ্যারেটি রিভার্সড থাকে, তখন সর্বাধিক ইনভার্শন হয়।

এই সমস্যাটি সমাধান করার জন্য আমরা মার্জ সোর্ট পদ্ধতি ব্যবহার করব যাতে সময় জটিলতা কম যায় এবং এটি একটি ডিভাইড অ্যান্ড কনকর অ্যালগরিদমে পরিণত হয়।

ইনপুট এবং আউটপুট

ইনপুট: সংখ্যার একটি সিকোয়েন্স। (1, 5, 6, 4, 20)
আউটপুট: সংখ্যাগুলোকে आरোহী ক্রমে সাজাতে প্রয়োজনীয় ইনভার্শনের সংখ্যা।
এখানে ইনভার্শন সংখ্যা ২।
প্রথম ইনভার্শন: (1, 5, 4, 6, 20)
দ্বিতীয় ইনভার্শন: (1, 4, 5, 6, 20)

এলগরিদম

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

ইনপুট: দুটি অ্যারে যেগুলো মার্জ হবে, বাম, ডান এবং মিড ইনডেক্স।

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

শুরু
  i := left, j := mid, k := right
  count := 0
  যতক্ষণ i <= mid-1 এবং j <= right, করুন
    যদি array[i] <= array[j], তবে
      tempArray[k] := array[i]
      i এবং k কে ১ বাড়ান
    অন্যথায়
      tempArray[k] := array[j]
      j এবং k কে ১ বাড়ান
      count := count + (mid - i)
  শেষ লুপ
  যতক্ষণ বাম অংশে অতিরিক্ত উপাদান থাকে, করুন
    tempArray[k] := array[i]
    i এবং k কে ১ বাড়ান
  শেষ লুপ
  যতক্ষণ ডান অংশে অতিরিক্ত উপাদান থাকে, করুন
    tempArray[k] := array[j]
    j এবং k কে ১ বাড়ান
  শেষ লুপ
  return count
শেষ

mergeSort(array, tempArray, left, right)

ইনপুট: প্রদত্ত অ্যারে এবং টেম্পোরারি অ্যারে, অ্যারের বাম এবং ডান ইনডেক্স।

আউটপুট: সর্ট করার পর ইনভার্শনের সংখ্যা।

শুরু
  count := 0
  যদি right > left, তবে
    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
শেষ

উদাহরণ (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 প্রথম অ্যারের লোকেশন লোকেট করতে
  j = mid;     // j দ্বিতীয় অ্যারের লোকেশন লোকেট করতে
  k = left;    // k মার্জ করা অ্যারের লোকেশন লোকেট করতে
  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