# Number of Inversions in an Unsorted Array: Python Code

This is my solution to the first programming assignment of Tim Roughgarden’s course on Algorithms  that was due 12:30 PM IST today. Here’s the question quoted as it is:

Programming Question-1
Download the text file here. (Right click and save link as) This file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated.

Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.
Because of the large size of this array, you should implement the fast divide-and-conquer algorithm covered in the video lectures. The numeric answer for the given input file should be typed in the space below.
So if your answer is 1198233847, then just type 1198233847 in the space provided without any space / commas / any other punctuation marks. You can make up to 5 attempts, and we’ll use the best one for grading.
(We do not require you to submit your code, so feel free to use any programming language you want — just type the final numeric answer in the following space.)

My Solution

I modified an earlier code I wrote for merge sort to arrive at the solution. It needed just a couple of modifications, and if you look carefully, it turns out that the number of inversions are unearthed each and every time we merge two sorted sub-arrays. So, intuitively, if the merge sort algorithm was O(nlog2 n), it would take almost as many operations for counting inversions. In python, the code to sort and count inversions in an array of 10,000 integers took less than 3 seconds.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # load contents of text file into a list # numList NUMLIST_FILENAME = "IntegerArray.txt" inFile = open(NUMLIST_FILENAME, 'r') with inFile as f: numList = [int(integers.strip()) for integers in f.readlines()] count = 0 def inversionsCount(x): global count midsection = len(x) / 2 leftArray = x[:midsection] rightArray = x[midsection:] if len(x) > 1: # Divid and conquer with recursive calls # to left and right arrays similar to # merge sort algorithm inversionsCount(leftArray) inversionsCount(rightArray) # Merge sorted sub-arrays and keep # count of split inversions i, j = 0, 0 a = leftArray; b = rightArray for k in range(len(a) + len(b) + 1): if a[i] <= b[j]: x[k] = a[i] i += 1 if i == len(a) and j != len(b): while j != len(b): k +=1 x[k] = b[j] j += 1 break elif a[i] > b[j]: x[k] = b[j] count += (len(a) - i) j += 1 if j == len(b) and i != len(a): while i != len(a): k+= 1 x[k] = a[i] i += 1 break return x # call function and output number of inversions inversionsCount(numList) print count

Test my solution here with your own test cases.

## One thought on “Number of Inversions in an Unsorted Array: Python Code”

1. deadredhead2 says:

I keep getting a “not defined” message after “a=leftArray; b=rightArray”

Like