/*
 * Solution to Problem 2 (C++)
 * 13th Annual CS Programming Contest
 * WCU Dept of Math and CS
 * Copyright 2002 , All Rights Reserved
 *
 * Problem Statement:
 * Degree of Inversion.
 * Compute the extent to which an array is out of sorted order
 * with sorted order meaning that the smallest index has the
 * smallest value, the second smallest index has the second 
 * smallest value, and so on until the largest index has the largest 
 * value. The metric for computing the degree of inversion is defined 
 * as follows. For each array index determine how many elements at
 * larger indexes have larger values. The degree of inversion
 * is the sum of this value over all indexes. Notice that if the
 * array is sorted, then the degree of inversion is 0.
 *
 * The solution is just two nested loops with the outer loop 
 * stepping through all the indexes and the inner loop counting
 * how many indexes after the current index have a value larger
 * than the value at the current index.
 */

#include <iostream.h>

const int NUM_ELTS = 4;

int main()
{
  int i, j;
  int count;
  int array[NUM_ELTS]; 

  cout << "Please enter the array values: ";
  for (i = 0; i < NUM_ELTS; i++) {
    cin >> array[i];
  } 
  count = 0;
  for (i = 0; i < NUM_ELTS; i++)
    for (j = i; j < NUM_ELTS; j++)
      if (array[i] > array[j])
        count++;
  cout << "The degree of inversion is: " << count << endl;
}