How do I change merge sort for calculate distance of an array from sorted array?

Question

NOTE: this problem is different from the count of inversions problem.

the distance of an array from sorted array defined as:

 dist(A)=Sumation(j-i) for any i<j that A[i]>A[j]

. Simply it can calculate in O(n^2). My question is How to change merge sort to calculate distance in O(n log n)? for example:

input: 5 2 3 4 1
output: 16

I don't want to count of inversions! this function is different from inversions.

input: 5 2 3 4 1
dist(A): 16
inversions(A): 7

You need to count inversions. Make a search, there is a lot of similar themes. — MBo, Oct 19 '18 at 07:55
I don't want to count of inversions. please check the function one more! — Karim Pazoki, Oct 19 '18 at 07:57

Yao Yingjie · Answer 1 · 2018-10-19T08:36:53.350

0

If you know how to calculate the number of inversion of an array through merge sort, you will solve this by changing several lines of code.

pay attention to the details.

// struct to store the values
//
struct pa {
    int value, index;
};

// The merge step
// A is the left part, while B is the right part
// a_cnt is the number of elements in A
void merge(pa A[], pa B[], int a_cnt, int b_cnt) {
    int st = 0;
    int tmp_sum = 0;
    for (int i = 0; i < a_cnt; ++i) {
        while (st < b_cnt && B[st].value < A[i].value) {
            tmp_sum += B[st].index;
            st++;
        }
        ans += (tmp_sum - st * A[i].index)
    }

    // origional merge code here
}

edited Oct 19 '18 at 08:36

answered Oct 19 '18 at 07:54

Yao Yingjie

450
1
5
17

I don't want to count of inversions. please check the question one more. – Karim Pazoki Oct 19 '18 at 08:00
Oh, I think you misunderstand me ... I think you can get some idea through calculating inversion with mergesort. – Yao Yingjie Oct 19 '18 at 08:02
Thank you. I know what is the count of inversions problem and think to it. but I have no idea for this new function. – Karim Pazoki Oct 19 '18 at 08:05
You should record each value's index in the original array. While in the merge step, the left part and right part are well sorted. At this time, you can know the pairs in which i in the left and j in the right part, if A[i] > A[j], then you will be able to get a inversion and add (index(j) - index(i)) to your answer. – Yao Yingjie Oct 19 '18 at 08:08
In the merge step, we don't check all the differences. so I don't understand how it can help us? – Karim Pazoki Oct 19 '18 at 08:11
in inversion count when i-th is less than j-th we add `inv_count = inv_count + (mid - i);` and doesn't check others. so what you say doesn't work. – Karim Pazoki Oct 19 '18 at 08:15
Yes, so you need to record each value's index. You just need to change `inv_count = inv_count + (mid - i)` to some other code. – Yao Yingjie Oct 19 '18 at 08:22
Thank you. Exactly my problem is I don't understand how to change it! – Karim Pazoki Oct 19 '18 at 08:25
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/182134/discussion-between-yao-yingjie-and-karim-pazoki). – Yao Yingjie Oct 19 '18 at 08:51

score 0 · Answer 2 · answered Oct 19 '18 at 09:09

You can solve this by inserting the numbers one by one in a sorted sequence and maintaining a suffix sum array. Here's how it works:

For each element in the array, have a pair. One contains the number itself and the other, its index. Now create another array and try to insert it in the sorted sequence.

Eg: [(5, 1), (2, 2), (3, 3), (4, 4), (1, 5)]

Insert 5

[(5, 1)]

Insert 2

[(2, 2), (5, 1)] => contributes (1*2 - 1) = > 1

Insert 3

[(2, 2), (3, 3), (5, 1)] => contributes (1*3 - 1) => 2

Insert 4

[(2, 2), (3, 3), (4, 4), (5, 1)] => contributes (1*4 - 1) => 3

Insert 1

[(1, 5), (2, 2), (3, 3), (4, 4), (5, 1)] => contributes (5 * 4 - (10) ) => 10

Sum all the contributions and you get 16

Time complexity: O(N * log N)

score 0 · Answer 3 · answered Oct 21 '18 at 12:42

This can be easily done with the help of binary search tree. You need to maintain the sum of indices of nodes present in right sub tree and number of nodes present in right sub tree. So whenever you are inserting a new node and it goes towards left of any node then distance will get updated by

 `(no of nodes in right subtree* index of val which is to be inserted) - sum of indices of nodes present in right subtree)`

Lets do a walk through for input 5, 2, 3, 4, 1

first node will be with val 5 and distance till now is 0;

Situation after inserting 2

sizeOfRightSubTree : 1 index: 1 sumOfIndicesOnRight: 0 inserted: 2, distance: 1

After inserting 3

sizeOfRightSubTree : 1 index: 2 sumOfIndicesOnRight: 0 inserted: 3, distance: 3

After inserting 4

sizeOfRightSubTree : 1 index: 3 sumOfIndicesOnRight: 0 inserted: 4, distance: 6

After inserting 1. Notice it has to traverse left twice to reach its final position hence distance is updated twice. sizeOfRightSubTree : 1 index: 4 sumOfIndicesOnRight: 0 sizeOfRightSubTree : 3 index: 4 sumOfIndicesOnRight: 6 inserted: 1, distance: 16

Following is the java code

public class DistanceFromSortedArray
{
 class Node {
    int val;
    Node left;
    Node right;
    int index;
    int sumOfIndicesOnRight;
    int sizeOfRightSubTree;


    Node(int num, int index)
    {
        this.val = num;
        this.index = index;
        sizeOfRightSubTree = 1;
        sumOfIndicesOnRight = index;
    }


    void addIndexToRight(int index)
    {
        sizeOfRightSubTree++;
        sumOfIndicesOnRight += index;
    }


    int distance(int index)
    {
        return sizeOfRightSubTree*index - sumOfIndicesOnRight;
    }
}

private Node head;
private int distance;

public int calculate(int[] nums){
    head = null;
    distance = 0;
    for(int i=0; i<nums.length; i++){
        insert(nums[i], i);
    }
    return distance;
}


private void insert(int num, int index)
{
    Node toInsert = new Node(num, index);
    if(head == null){
        head = toInsert;
        return;
    }

    Node current = head;
    Node previous = null;
    while (current != null){
        previous = current;
        if(current.val > num){
            distance += current.distance(index);
            current = current.left;
        }
        else {
            current.addIndexToRight(index);
            current = current.right;
        }
    }


    if(previous.val > num){
        previous.left = toInsert;
    }
    else {
        previous.right = toInsert;
    }

}
}

Here are few test cases

@Test
public void calculate()
{
    int[] nums = {5, 2, 3, 4, 1};
    assertEquals(16, new DistanceFromSortedArray().calculate(nums));
}


@Test
public void reverseCalculate()
{
    int[] nums = {5, 4, 3, 2, 1};
    assertEquals(20, new DistanceFromSortedArray().calculate(nums));
}

@Test
public void SizeTwoCalculate()
{
    int[] nums = {4, 5};
    assertEquals(0, new DistanceFromSortedArray().calculate(nums));

     int [] nums2 = {5, 4};
    assertEquals(1, new DistanceFromSortedArray().calculate(nums2));
}


@Test
public void twistedCalculate()
{
    int[] nums = {8, 3, 6, 5, 7, 1};
    assertEquals(26, new DistanceFromSortedArray().calculate(nums));
}

@Test
public void AllSameCalculate()
{
    int[] nums = {1, 1, 1, 1, 1, 1};
    assertEquals(0, new DistanceFromSortedArray().calculate(nums));
}

How do I change merge sort for calculate distance of an array from sorted array?

3 Answers3