सरणी के इनवर्जन इंगित करते हैं; सरणी को उसके क्रमबद्ध रूप में बदलने के लिए कितने परिवर्तन आवश्यक हैं। जब एक सरणी पहले से क्रमबद्ध होती है, तो इसे 0 इनवर्जन की आवश्यकता होती है, और अन्य मामलों में, इनवर्जन की संख्या अधिकतम होगी, यदि सरणी उलटी है।
इस समस्या को हल करने के लिए, हम समय जटिलता को कम करने के लिए मर्ज सॉर्ट दृष्टिकोण का पालन करेंगे, और इसे विभाजन और विजय एल्गोरिदम में बना देंगे।
इनपुट
A sequence of numbers. (1, 5, 6, 4, 20).
आउटपुट
संख्याओं को आरोही क्रम में व्यवस्थित करने के लिए आवश्यक इनवर्जन की संख्या।
Here the number of inversions are 2. First inversion: (1, 5, 4, 6, 20) Second inversion: (1, 4, 5, 6, 20)
एल्गोरिदम
merge(array, tempArray, left, mid, right)
इनपुट - दो सरणियाँ, जिन्हें मिलाया गया है, बाएं, दाएं और मध्य सूचकांक।
आउटपुट - क्रमबद्ध क्रम में मर्ज की गई सरणी।
Begin i := left, j := mid, k := right count := 0 while i <= mid -1 and j <= right, do if array[i] <= array[j], then tempArray[k] := array[i] increase i and k by 1 else tempArray[k] := array[j] increase j and k by 1 count := count + (mid - i) done while left part of the array has some extra element, do tempArray[k] := array[i] increase i and k by 1 done while right part of the array has some extra element, do tempArray[k] := array[j] increase j and k by 1 done return count End
mergeSort(array, tempArray, left, right)
इनपुट - दी गई सरणी और अस्थायी सरणी, सरणी के बाएं और दाएं सूचकांक।
आउटपुट - क्रमबद्ध करने के बाद इनवर्जन की संख्या।
Begin count := 0 if right > left, then 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 End
उदाहरण
#includeusing namespace std; int merge(int arr[], int temp[], int left, int mid, int right) { int i, j, k; int count = 0; i = left; //i to locate first array location j = mid; //i to locate second array location k = left; //i to locate merged array location while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]){ //when left item is less than right item temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; count += (mid - i); //find how many convertion is performed } } while (i <= mid - 1) //if first list has remaining item, add them in the list temp[k++] = arr[i++]; while (j <= right) //if second list has remaining item, add them in the list temp[k++] = arr[j++]; for (i=left; i <= right; i++) arr[i] = temp[i]; //store temp Array to main array return count; } int mergeSort(int arr[], int temp[], int left, int right){ int mid, count = 0; if (right > left) { mid = (right + left)/2; //find mid index of the array count = mergeSort(arr, temp, left, mid); //merge sort left sub array count += mergeSort(arr, temp, mid+1, right); //merge sort right sub array count += merge(arr, temp, left, mid+1, right); //merge two sub arrays } 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
