Number of Inversions146 views
function number_of_inversions(list) {
function merge_inversions(lst, beg1, end1, beg2, end2, aux) {
var c = beg1,
// counter for auxiliary array
beg = beg1,
// copy beg and end
end = end2,
count = 0;
while (beg1 <= end1 && beg2 <= end2) {
if (lst[beg1] <= lst[beg2]) {
aux[c++] = lst[beg1++];
} else {
aux[c++] = lst[beg2++];
count += end1 - beg1 + 1;
}
} // copy remaining items if any
while (beg1 <= end1) {
aux[c++] = lst[beg1++];
}
while (beg2 <= end2) {
aux[c++] = lst[beg2++];
} // now copy sorted elements from aux to actual list
while (beg <= end) {
lst[beg] = aux[beg++];
}
return count;
}
function count_inversions(lst, start, end, aux) {
if (end === start) { // we have just one element to sort, so its already sorted
return 0;
} // partition the list portion into two and sort them
// this is first step 1. Divide
var mid = Math.floor((start + end) / 2),
inversions = 0;
inversions += count_inversions(lst, start, mid, aux);
inversions += count_inversions(lst, mid + 1, end, aux); // Now merge the two
// this is second step. 2. Conquer
inversions += merge_inversions(lst, start, mid, mid + 1, end, aux);
return inversions;
}
// merge sort the entire array
// create and auxiliary memory, which is required by merge sort
var i = 0,
aux = [];
while (i < list.length) {
aux[i++] = 0;
}
return count_inversions(list, 0, list.length - 1, aux);
}
Problem Statement: Given a list of numbers count the number of inversions.
Solution:Modified merge sort is used to find invesion in a list of numbers.
this resursive solution can be written as follows
inversions(i,j) = inversions(i,k) + inversions(k+1,j) + merge(i,k,j)
where
inversions routine sort subarray [i,...,j] and returns number of inversions in it.
and k = floor((i+j)/2)
merge procedure can be easily explained as follows.
Let A be a sorted sub array {2,6,7,9}
Let B be a sorted sub array {1,3,4,10}
number of inversion in concatenated array AB i.e {2,6,7,9,1,3,4,10} can be found in linear time.
We merge the two list using same method as used in merge sort and when we pick element from second list we increment
number of inversions by the number of element remaining to be processed in first list. Let current item in first b c1
and current item in second list be c2
if B[c2] is less that A[c1] then all remaining elements in A ( from c1 to end} are larger than B[c2] because A and B are sorted lists
but as B[c2] comes after all remaining elements in A all those elements are inversions of the AB combined list.