I've been struggling for a few days to come up with code that follows the pseudo-code below to count the number of inversions of an unsorted list of permutation numbers. I need the algorithm to run in O(nlogn) time but I can only think of a solution in O(n^2logn) time.
More specifically I would like to know how to speed up the 2nd step by not using a nested for loop. I know there are other efficient algorithms (ie. merge-sort) that would work but I need to follow the steps of the psuedo-code.
Instance: An array A[1] . . . A[n], a permutation of n numbers 1, . . . , n
Question: Calculate vector B[j] = |{A[i] : j > i and A[i] > A[j]}| (the same as
B[j] = |{i : j > i and A[i] > A[j]}|) B[j] is the number of element
larger than A[j] to the left of A[j] in t the array A. In other words,
the sum of the elements in B is equal to the number of inversions in
the permutation A[1] . . . A[n].
(1) Initialize B[i] to 0.
(2) For each even A[j] find elements with indices smaller than j that are by one larger
than A[j]: increase B[j] by the number of such elements;
(3) Divide each A[i] by 2 (in the integer sense);
(4) Stop when all A[i] are 0.
The following is the code I have came up with so far:
long long numInversions = 0;
// number of elements that are zero in the array
unsigned int zeros = 0;
do {
// solution will need to replace this nested
// for loop so it is O(n) not O(n^2)
for (int i = 0; i < permNumber; i++){
// checks if element is even
if(array[i] % 2 == 0){
for (int j = i; j >= 0; j--){
if (array[j] == array[i] + 1){
numInversions++;
}
}
}
}
// resets value of zeros for each pass
zeros = 0;
for (int k = 0; k < permNumber; k++){
array[k] = array[k] / 2;
if (array[k] == 0)
zeros++;
}
} while(zeros != permNumber);
Note: The algorithm should return the number of inversions in the list, a scalar. The pseudo-code asks for an array, but in the end the elements of the array are summed to compute the inversion count.
Example: Consider a permutation (2, 3, 6, 1, 3, 5) with six inversions. The
above algorithm works as follows:
2 4 6 1 3 5 (no pairs) ÷2
1 2 3 0 1 2 1 = 0: one '1' to left, 2: one 3 to left ÷2
0 1 1 0 0 1 1 = 0: two '1's to left, 0: two '1's to left ÷2
0 0 0 0 0 0 total: 6 pairs
This is a pretty clever algorithm -- in each iteration it counts the inversions that will be removed by the division by two... Although it's unnecessary to use an array for B, since all you do with it is add to the elements and then sum them up. You can just keep a single running sum.
Anyway... In order to speed up step (2) you can use another array C[v] to remember counts for all the odd values in A, like this:
Step 2:
Initialize all C[v] to 0
For i = 1 to n: //0 to n-1 if you're using 0-based arrays
if A[i] is even then:
B[i] += C[A[i]+1]
else:
C[A[i]] += 1