Assignment 2 Inversion

1 Programming Assignment
In a sequence 𝑆 = 𝑠1, 𝑠2, … , 𝑠𝑛 of 𝑛 integers, an inversion is a pair of elements 𝑠𝑖 and 𝑠𝑗 where
𝑖 < 𝑗 (that is, 𝑠𝑖 appears before 𝑠𝑗
in the sequence) and 𝑠𝑖 𝑠𝑗
. For example, in the sequence
𝑆 = 2, 1, 5, 3, 4
the pairs (2,1), (5,3) and (5,4) are inversions.
The programming assignment is to implement an algorithm which counts the number of
inversions in an input sequence:
Input: An array 𝐴 of 𝑛 integers in the range 1 − 𝑛.
Output: An integer, corresponding to the number of inversions in 𝐴.
An array with 𝑛 elements may have as many as
(
𝑛
2
) =
𝑛(𝑛 − 1)
2
inversions. When the number of inversions 𝑘 may be any value between 0 and 𝑛(𝑛−1)
2
, the best
algorithm for counting inversions has running time 𝑂(𝑛 log(𝑛)). There also exists a 𝑂(𝑛 + 𝑘)
algorithm for counting inversions, which is 𝑂(𝑛
2
) when 𝑘 ∈ 𝑂(𝑛
2
).
In this assignment, we will assume that the number of inversions is at most 𝑛 (that is, 𝑘 ≤ 𝑛).
When the 𝑂(𝑛 + 𝑘) algorithm is used with such values of 𝑘, its running time is 𝑂(𝑛 + 𝑛) =
𝑂(𝑛). For full marks, your implementation must run in 𝑂(𝑛) time when 𝑘 ≤ 𝑛.
Your task is to write a java program, stored in a file named CountInversions.java that
contains a function CountInversions, which takes an integer array A as its only argument,
and returns an integer value. The main function in your code should help you test your
implementation by getting test data or reading it from a file. It should also handle errors but don’t
worry about running times.
2 Examples
The table below gives the inversion count and a list of the inversions present in several small
input arrays.
Input Array # of Inversions Inversions
1, 2, 3 0 none
1, 2, 3, 5, 4 1 (5, 4)
10, 30, 40, 20, 50 3 (30, 20), (40, 20)
4, 3, 2, 1, 5, 6 6 (4, 3), (4, 2), (4, 1), (3, 2), (3, 1), (2, 1)
5, 1, 2, 3, 4 4 (5, 1), (5, 2), (5, 3), (5, 4)
3 Test Datasets
A set of input files have been uploaded to ConneX, containing arrays of various sizes and
inversion counts. You should test your implementation on the uploaded files before submitting.
Note that an algorithm with a running time which is 𝑂(𝑛 log 𝑛) or better should be able to
process any of the files within a few seconds. The uploaded files may not cover all possible
cases, so you should test your implementation on other inputs as well.
4 Evaluation Criteria
The programming assignment will be marked out of 25, based on a combination of automated
testing (using large test arrays similar to the ones posted on ConneX) and human inspection. All
of the tested input arrays will have an inversion count 𝑘 which is at most 𝑛.
Score (/25) Description
0 - 5 Submission does not compile or does not
conform to the provided template.
5 - 15 The implemented algorithm is 𝑂(𝑛
2
) or is
substantially inaccurate on the tested inputs.
15 - 20 The implemented algorithm is 𝑂(𝑛 log 𝑛) or
contains minor errors.
20 – 25 The implemented algorithm is 𝑂(𝑛 + 𝑘) on an
array with 𝑛 elements and 𝑘 inversions, resulting
in a 𝑂(𝑛) algorithm when 𝑘 ∈ 𝑂(𝑛).
To be properly tested, every submission must compile correctly as submitted. If your submission
does not compile for any reason (even trivial mistakes like typos), it will receive at most 5 out of
25.