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