দেওয়া অ্যারেটি সোর্ট করতে যে ইনভারশনগুলো হয় সেগুলোর কাউন্টকে ইনভারশন কাউন্ট বলা হয়। ইনভারশন সমস্যা একটি ক্লাসিক্যাল সমস্যা যা মার্জ সর্ট অ্যালগরিদম দিয়ে সমাধান করা যায়। এই সমস্যায় আমরা এর বামে থাকা সেটির চেয়ে বড় সব এলিমেন্ট কাউন্ট করব এবং আউটপুটে যোগ করব। এই লজিক মার্জ সর্টের মার্জ ফাংশনের ভেতরে করা হয়।
বিষয়টি ভালোভাবে বুঝতে একটি উদাহরণ নেই। মার্জ প্রসেসে জড়িত দুটি সাব-অ্যারে বিবেচনা করুন −
Input: arr[] = { 1, 9, 6, 4, 5} Output: Inversion count is 5
ব্যাখ্যা
একটি অ্যারের ইনভারশন কাউন্ট
একটি অ্যারে দেওয়া আছে, এর ইনভারশনের সংখ্যা বের করতে হবে। যদি (i < j) এবং (A[i] > A[j]) হয়, তবে জোড়া (i, j) অ্যারে A-এর একটি ইনভারশন कहलাবে। আমাদের অ্যারেতে এমন সব জোড়া কাউন্ট করতে হবে।
উদাহরণস্বরূপ,
অ্যারেতে ৫টি ইনভারশন আছে:
(9,6), (9,4), (9,5), (6,4), (6,5)
১. এলিমেন্টের ভ্যালুগুলো একে অপরের সাথে তুলনা করা।
২. যদি নিচের ইনডেক্সের ভ্যালু বেশি হয়, তবে কাউন্টার ইনক্রিমেন্ট করা।
৩. ফলাফল দেখানো।
উদাহরণ
#include <stdio.h> int Merge(int arr[], int aux[], int low, int mid, int high) { int k = low, i = low, j = mid + 1; int inversionCount = 0; while (i <= mid && j <= high) { if (arr[i] <= arr[j]) { aux[k++] = arr[i++]; } else { aux[k++] = arr[j++]; inversionCount += (mid - i + 1); // NOTE } } while (i <= mid) aux[k++] = arr[i++]; for (int i = low; i <= high; i++) arr[i] = aux[i]; return inversionCount; } int MergeSort(int arr[], int aux[], int low, int high) { if (high == low) // if run size == 1 return 0; int mid = (low + ((high - low) >> 1)); int inversionCount = 0; inversionCount += MergeSort(arr, aux, low, mid); inversionCount += MergeSort(arr, aux, mid + 1, high); inversionCount += Merge(arr, aux, low, mid, high); return inversionCount; } int main() { int arr[] = { 1, 9, 6, 4, 5 }; int N = 5; int aux[N]; for (int i = 0; i < N; i++) aux[i] = arr[i]; printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1)); return 0; }
