inversions_array.cpp

/*
 * Copyright 2010, NagaChaitanya Vellanki
 *
 * Author NagaChaitanya Vellanki
 *
 * Inversion of array, complexity O(n *lg(n))
 * Refer to CLRS 2-4
 */

#include <iostream>
#include <stdint.h>
#include <vector>
#include <algorithm>

using namespace std;

void PrintArray(vector<int32_t> &array)
{
  for (int32_t index = 0; index < array.size(); index++)
  {
    cout << array[index] << " ";
  }
  cout << endl;
}

int32_t MergeInversions(vector<int32_t> &array, int32_t low, int32_t mid,  int32_t high)
{
  int32_t n1 = mid - low + 1;
  int32_t n2 = high -mid;
  int32_t left[n1 + 1];
  int32_t right[n2 + 1];

  for(int32_t i = 0; i < n1; i++) {
    left[i] = array[low + i - 1];
  }

  for(int32_t i = 0; i < n2; i++) {
    right[i] = array[i + mid];
  }

  // sentinels
  left[n1] = 999999;
  right[n2] = 999999;

  int32_t i = 0;
  int32_t j = 0;

  int32_t inversions = 0;
  bool counted = false;
  for(int32_t k = low - 1; k < high; k++) {

    if((counted == false) && (left[i] > right[j] )) {
      inversions += n1 - i;
      counted = true;
    }
    if(left[i] <= right[j]) {
      array[k] = left[i];
      i++;
    } else {
      array[k] = right[j];
      j++;
      counted = false;
    }
  }
  cout << "Step:" << endl;
  PrintArray(array);
  return inversions;
}

int32_t CountInversions(vector<int32_t> &array, int32_t low, int32_t high)
{
  int32_t inversions = 0;
  if (low < high)
  {
    int32_t mid = (low + high) / 2;
    inversions += CountInversions(array, low, mid);
    inversions += CountInversions(array, mid + 1, high);
    inversions += MergeInversions(array, low, mid, high);
  }
  return inversions;
}



int main()
{
  int32_t n = 0;
  int32_t temp = 0;
  vector<int32_t> array;

  cout << "Enter the number of elements" << endl;
  cin >> n;

  // read the elements
  cout << " ** Enter the elements of the array **" << endl;
  for (int32_t index = 0; index < n; index++)
  {
    cin >> temp;
    array.push_back(temp);
  }

  cout << "Number of inversions: " << CountInversions(array, 1, n) << endl;
  return 0;
}