একটি বিন্যাসের বিপরীত দিক নির্দেশ করে; অ্যারেটিকে সাজানো ফর্মে রূপান্তর করতে কতগুলি পরিবর্তন প্রয়োজন। যখন একটি অ্যারে ইতিমধ্যে বাছাই করা হয়, তখন এটির 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)
অ্যালগরিদম
একত্রীকরণ (অ্যারে, টেম্পঅ্যারে, বাম, মধ্য, ডান)
ইনপুট - দুটি অ্যারে, যারা একত্রিত হয়েছে, বাম, ডান এবং মধ্য সূচক।
আউটপুট -বাছাই ক্রমে মার্জড অ্যারে৷
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
একত্রিত করুন(অ্যারে, টেম্পঅ্যারে, বাম, ডান)
ইনপুট - দেওয়া অ্যারে এবং অস্থায়ী অ্যারে, অ্যারের বাম এবং ডান সূচক।
আউটপুট - বাছাই করার পরে বিপরীতের সংখ্যা।
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
উদাহরণ
#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 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
