Count inversion
unknown
plain_text
3 years ago
1.5 kB
4
Indexable
#include <iostream> using namespace std; int merge(int *arr, int s, int e) { int mid= (s+e)/2; int length1= mid-s+1; int length2= e-mid; int count = 0; int *first= new int[length1]; int *second= new int[length2]; int mainArrayIndex=s; for(int i=0; i<length1; i++) { first[i]= arr[mainArrayIndex++]; } mainArrayIndex= mid+1; for(int j=0; j<length2; j++) { second[j]= arr[mainArrayIndex++]; } int index1=0; int index2=0; mainArrayIndex=s; while(index1<length1 && index2<length2) { if(first[index1]<=second[index2]) { arr[mainArrayIndex++]=first[index1++]; } else { arr[mainArrayIndex++]=second[index2++]; count += length1 - index1; } } while(index1<length1) { arr[mainArrayIndex++]=first[index1++]; } while(index2<length2) { arr[mainArrayIndex++]=second[index2++]; } delete []first; delete []second; return count; } int mergeSort(int *arr, int s, int e) { int count = 0; if(s<e) { int mid= (s+e)/2; count += mergeSort(arr, s, mid); count += mergeSort(arr, mid+1, e); count += merge(arr, s, e); } return count; } int main() { int arr[4]= {6,5,4,3}; int n=4; int count = mergeSort(arr, 0, n-1); cout<<count; return 0; }
Editor is loading...