Counting inversions in an array

The problem is to count the number of inversions in an array. Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

For example, the sequence 1, 20, 6, 4, 5 has five inversions (20, 6), (20, 4), (20, 5), (6, 4) and (6, 5).

We can modify the mergesort algorithm to count the number of inversions while sorting. This takes time O(nlogn) for an array of size n.

The algorithm belongs to the class of divide-and-conquer algorithms and has the following steps:

  • Divide: Divide the array of size n into two subarrays of size n/2 each.
  • Conquer: Recursively compute the number of inversions in both subarrays.
  • Combine: Count the number of inversions split across the two subarrays. This can be done in linear time by modifying the merge procedure of mergesort such that when it copies an element from the right subarray to the original array, it adds the number of remaining elements in the left subarray to the count of split inversions.

Take a look at the C++ implementation.

Try your hand at problem INVCNT, which uses this idea.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s