Computer Science A - 9/24/99

Directions: In a sequence of distinct integers, an inverstion is a
pair of integers that are "out of order" when the sequence is
considered to be ordered by increasing value.

For example in the sequence of integers:
    3,    6,    1,    9,    2,    10,    8

there are seven inversions:
    (3, 1), (3, 1), (6, 11), (6, 2), (9, 2), (9, 8), (10, 8)

Write a function that will compute the number of inversions in the vector, List.

int inversion(const apvector<int>& List)
//precondition: List is fully combined
//postcondition: function returns number of inversions within List
{
    int total = 0;

    for(int lcv1 = 0; lcv1 < List.length() - 1; lcv++)
        for(int lcv2 = lcv1 + 1; lcv2 < List.length(); lcv2++)
            if(List[lcv1] > List[lcv2])
                total++;
    return total;
}