Merge sort to find the number of inversions

Merge sort

The idea of merge sort

Range resolution

The interval to be sorted recursively splits down into left and right cells, and then merges up into left and right cells. Obviously, recursion is at the end of the interval length is 1, in other words, interval [l, r] does not meet the l < r. — — — — — — — — — — — — — — so, merge sort of trunk code has come out: Check whether the interval is redivisible, that is, if l < r is not redivisible, return(end). If it can be divided again, the left and right intervals are sorted in turn and then merged. — — — — — — — — — — — —

void MergeSort(int l,int r)
{
    if(l<r)
    {
        int m = (l+r)/2;// if you don't understand something, don't change it
        MergeSort(l,m);
        MergeSort(m+1,r); SubMergeSort(l,m,r); }}Copy the code

Interval merging

The following results are sorted from small to large

Use two Pointers to the start of the interval to merge, and compare the values of the two Pointers. Whoever is smaller puts the corresponding value in a temporary array and moves the pointer back one bit. Until one of the Pointers reaches the end of the corresponding interval (i.e., there are no subsequent elements). If there are more elements in the other range, the following elements are added to the temporary array. Finally, the elements of the temporary array are copied into the original array.

const int maxnum=100000; int a[maxnum]; Int tem[maxnum]; Void SubMergeSort(int l,int m,int r) {int I = l; void SubMergeSort(int l,int m,int r); Int j = m+1; // array subscript instead of pointer int k = l; /// note that l is not 1while(i<=m&&j<=r)
    {
        if(a[i]>a[j])
            tem[k++] = a[j++];
        else
            tem[k++] = a[i++];
    }
    while(i<=m) tem[k++] = a[i++];
    while(j<=r) tem[k++] = a[j++]; /* Copy from TEM to a*/for(int i=l; i<=r; i++) a[i] = tem[i]; }Copy the code

Use merge sort to find the inverse number

What is an inverse number

In a permutation, logarithms are said to be in an inverse order if their front and back positions are in reverse order of magnitude, i.e. the number in front is larger than the number behind. The total number of inversions in a permutation is called the number of inversions of that permutation.

How to find the inverse number

According to the concept of the inverse number above, it can be understood that the inverse number of a sequence is the sum of all the inversions of the numbers. And the reverse of each number is equal to the number of elements before and greater than that number.

The following sort refers to the order from smallest to largest.

Obviously, during merge sort, the number of interval inversions after each merge is 0. Also, the number of inversions of the previous two ranges is 0, because they are already sorted. So, we just need to record the number of inversions that each element decreases during interval merging. More specifically: the left interval itself is ordered, so the number of inversions of all elements of the left interval in the merged interval is 0. And the number of inversions of the elements in the right interval is equal to the number of elements larger than the elements in the left interval. This number is the number of elements starting from the current pointer to the end of the left interval. [i,m].size() = m-i+1

Find the number of inversions of each element

#include <iostream>
using namespace std;
const int maxnum=100000;

struct node{
    int val;
    int inv;
};

node a[maxnum];
node tem[maxnum];

/* Merge two closed intervals [l,m] and [m+1,r]*/
void SubMergeSort(int l,int m,int r)
{
    int i = l;
    int j = m+1;
    int k = l;/// note that l is not 1
    while(i<=m&&j<=r)
    {
        if(a[i].val>a[j].val)
        {
            a[j].inv += m-i+1;
            tem[k++] = a[j++];
        }
        else
            tem[k++] = a[i++];
    }
    while(i<=m) tem[k++] = a[i++];
    while(j<=r) tem[k++] = a[j++];
    /* Copy from TEM to a*/
    for(inti=l; i<=r; i++) a[i] = tem[i]; }void MergeSort(int l,int r)
{
    if(l<r)
    {
        int m = (l+r)/2;// if you don't understand something, don't change it
        MergeSort(l,m);
        MergeSort(m+1,r); SubMergeSort(l,m,r); }}int main(a)
{
    int n;
    while(cin>>n)
    {
        for(int i=0; i<n; i++) {cin>>a[i].val;
        }
        MergeSort(0,n- 1);
        for(int i=0; i<n; i++) {cout<<a[i].val<<"";
        }
        cout<<endl;
        for(int i=0; i<n; i++) {cout<<a[i].inv<<"";
        }
        cout<<endl;
    }
    return 0;
}
Copy the code

Find the total number of inversions of the sequence

#include <iostream>
using namespace std;
const int maxnum=100000;

int a[maxnum];
int tem[maxnum];

int ans;

/* Merge two closed intervals [l,m] and [m+1,r]*/
void SubMergeSort(int l,int m,int r)
{
    int i = l;
    int j = m+1;
    int k = l;/// note that l is not 1
    while(i<=m&&j<=r)
    {
        if(a[i]>a[j])
        {
            ans += m-i+1;// Count only the number of inversions
            tem[k++] = a[j++];
        }
        else
            tem[k++] = a[i++];
    }
    while(i<=m) tem[k++] = a[i++];
    while(j<=r) tem[k++] = a[j++];
    /* Copy from TEM to a*/
    for(inti=l; i<=r; i++) a[i] = tem[i]; }void MergeSort(int l,int r)
{
    if(l<r)
    {
        int m = (l+r)/2;// if you don't understand something, don't change it
        MergeSort(l,m);
        MergeSort(m+1,r); SubMergeSort(l,m,r); }}int main(a)
{
    int n;
    while(cin>>n)
    {
        for(int i=0; i<n; i++) {cin>>a[i];
        }
        ans = 0;
        MergeSort(0,n- 1);
        for(int i=0; i<n; i++) {cout<<a[i]<<"\t";
        }
        cout<<endl;
        cout<<ans<<endl;
    }
    return 0;
}
Copy the code