CODEWITHSUNDEEP
c++algorithmsortingcountinversion
Buffalo282
Buffalo282

Reputation: 29

Inversion Count Algorithm without using Merge Sort (c++)

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

Upvotes: 2

Views: 1499

Answers (2)

Saurav Sahu
Saurav Sahu

Reputation: 13934

Without using merge sort, in Java:

public int binarySearch(ArrayList<Integer> A, int s, int e, int elem){
        // finds the position at which elem can be inserted to maintain the sorted order in A
        if (s >= e){
            return elem >= A.get(s) ? s+1 : s;
        }
        int mid = (s+e)/2;
        if (elem == A.get(mid)) return mid+1;

        if (elem < A.get(mid)) return binarySearch(A, s, mid-1, elem); 
        return binarySearch(A, mid+1, e, elem);
    }
    public int binarySearchLast(ArrayList<Integer> A, int s, int e, int elem){
        // finds the index of first element greater than "elem" in list A
        if (s >= e) return elem < A.get(s) ? s : s+1;
        int mid = (s+e)/2;

        if (elem < A.get(mid)) return binarySearchLast(A, s, mid, elem); 
        return binarySearchLast(A, mid+1, e, elem);
    }
    public int countInversions(ArrayList<Integer> A) {
        int cnt = 0;
        ArrayList<Integer> B = new ArrayList<>();
        B.add(A.get(0));
        for (int i = 1; i < A.size(); i++){
            int idx = binarySearch(B, 0, B.size()-1, A.get(i));
            B.add(idx, A.get(i));
            idx = binarySearchLast(B, 0, B.size()-1, A.get(i));
            cnt = cnt + B.size() - idx;
        }
        return cnt;
    }

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59204

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

Upvotes: 2

Related Questions