दिए गए ऐरे को क्रमबद्ध करने के लिए होने वाले इनवर्जन की संख्या को इनवर्जन काउंट (inversion count) के रूप में जाना जाता है। इनवर्जन समस्या एक शास्त्रीय समस्या है जिसे मर्ज सॉर्ट एल्गोरिदम का उपयोग करके हल किया जा सकता है। इस समस्या में हम इसके बाईं ओर उससे बड़े सभी एलिमेंट्स को गिनेंगे और काउंट को आउटपुट में जोड़ेंगे। यह तर्क मर्ज सॉर्ट के मर्ज फ़ंक्शन के अंदर किया जाता है।
विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं। आइए मर्ज प्रक्रिया में शामिल दो सब-ऐरे पर विचार करें -
Input: arr[] = { 1, 9, 6, 4, 5} Output: इनवर्जन काउंट 5 है
व्याख्या
ऐरे का इनवर्जन काउंट
एक ऐरे दिया गया है, इसके इनवर्जन की संख्या ढूंढें। यदि (i < j) और (A[i] > A[j]) तो युग्म (i, j) को ऐरे A का इनवर्जन कहा जाता है। हमें ऐरे में ऐसे सभी युग्मों को गिनना है।
उदाहरण के लिए,
ऐरे में 5 इनवर्जन हैं
(9,6), (9,4), (9,5), (6,4), (6,5)
1. एलिमेंट्स के मानों की तुलना एक-दूसरे से करें।
2. काउंटर बढ़ाएं यदि निचले इंडेक्स पर मान अधिक है।
3. परिणाम प्रदर्शित करें।
उदाहरण
#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) // यदि रन आकार == 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;
}
