किसी सरणी के इनवर्जन दर्शाते हैं कि उस सरणी को उसके क्रमबद्ध रूप में बदलने के लिए कितने परिवर्तनों की आवश्यकता है। जब सरणी पहले से क्रमबद्ध होती है, तो इसे 0 इनवर्जन की आवश्यकता होती है, और दूसरे मामले में, इनवर्जन की संख्या अधिकतम होगी, यदि सरणी उलटी हो।
इस समस्या को हल करने के लिए, हम मर्ज सॉर्ट दृष्टिकोण का पालन करेंगे ताकि समय जटिलता कम हो, और इसे विभाजन और विजय एल्गोरिदम में बनाया जा सके।
इनपुट और आउटपुट
इनपुट: संख्याओं का अनुक्रम। (1, 5, 6, 4, 20)। आउटपुट: संख्याओं को आरोही क्रम में व्यवस्थित करने के लिए आवश्यक इनवर्जन की संख्या। यहाँ इनवर्जन की संख्या 2 है। पहला इनवर्जन: (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 को 1 से बढ़ाएं अन्यथा tempArray[k] := array[j] j और k को 1 से बढ़ाएं count := count + (mid - i) किया जब बाएँ भाग में कुछ अतिरिक्त तत्व हों, करें tempArray[k] := array[i] i और k को 1 से बढ़ाएं किया जब दाएँ भाग में कुछ अतिरिक्त तत्व हों, करें tempArray[k] := array[j] j और k को 1 से बढ़ाएं किया 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) count वापस करें अंत
उदाहरण
#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
