CODEWITHSUNDEEP
javaarrayssortingcompareinversion
Josh Susa
Josh Susa

Reputation: 173

How do I find the number of inversions in an array?

Basically I'm trying to write an algorithm in Java to determine the number of pairs in an array that are out of order. So if we take i and j and j is in a higher position in an array than i but A[i] > A[j] then it counts those two numbers as an inversion. Currently this is what I have:

for(int i = 0; i<n-1; i++){
    if (A[i] > A[i+1]){
        k++;

What this does is only compared the pairs that are right next to eachother so now I'm trying to modify this to find any two numbers in the array where the lower position is a higher value than the number in the higher position. I know how to do something like that but I want the run time to be (n+k) where n is the length of the array and k is the number of inversions in the array.

EDIT: Here's my attempt to implement insertion sort:

int k = 0;
int [] A = {5, 4, 3, 2, 1};
int n = A.length;
for(int i = 1; i < n; i++){
    int temp = A[i];
    int j;
    for (j = i - 1; j >=0 && temp < A[j]; j--){
        A[j + 1] = A[j];
    A[j + 1] = A[j];
        k++;

k is supposed to be keep track of how many inversions. For the array 5, 4, 3, 2, 1 the number I get returned is 6. Is that right?

Upvotes: 2

Views: 2546

Answers (2)

Nayuki
Nayuki

Reputation: 18542

The solution is to implement insertion sort, and count the number of times that a pair of adjacent elements were swapped. This works because insertion sort performs a swap for and only for each inversion. In fact its running time is O(n + k), just as you requested.

As for question part two - here is the corrected insertion sort algorithm:

for (int i = 1; i < n; i++) {
    int temp = A[i];
    int j;
    for (j = i - 1; j >= 0 && temp < A[j]; j--) {
        A[j + 1] = A[j];
        k++;  // Number of inversions
    }
    A[j + 1] = temp;
}

Extra note: The efficient way to count array inversions is to modify the merge sort algorithm, which runs in O(n log n) time. However when k is small, O(n + k) is approximately O(n), which is less than O(n log n). Indeed, merge sort's best-case time is still O(n log n), whereas insertion sort's best case is O(n). Therefore, merge sort does not answer the OP's question for an O(n + k) algorithm.

Upvotes: 2

Aditya Vyas-Lakhan
Aditya Vyas-Lakhan

Reputation: 13555

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

For each element, count number of elements which are on right side of it and are smaller than it.

int getInvCount(int arr[], int n)
{
  int inv_count = 0;
  int i, j;

  for(i = 0; i < n - 1; i++)
    for(j = i+1; j < n; j++)
      if(arr[i] > arr[j])
        inv_count++;

  return inv_count;
}

/* Driver progra to test above functions */
int main(int argv, char** args)
{
  int arr[] = {1, 20, 6, 4, 5};
  printf(" Number of inversions are %d \n", getInvCount(arr, 5));
  getchar();
  return 0;
}

Upvotes: 0

Related Questions