I have a list/array containing multiple lists/arrays and I want to get a list/ar

Question

I have a list/array containing multiple lists/arrays and I want to get a list/array containing the number of inversions in each of the individual list/arrays within the main list using an algorithm that is O(nlogn). How can I do this in python?

For example, I read in a list that contains 4 sub lists: [ [1,2,3] , [0,0,0] , [2,3,2,1,5] , [5,4,3,2,1] ]. The algorithm should return one list that contains all of the inversions for each sub list.

For the example shown earlier the list would be [0,0,4,10] for ASCENDING ORDER because [1,2,3] contains 0 inversions, [0,0,0] contains 0 inversions, [2,3,2,1,5] contains 4 inversions, and [5,4,3,2,1] contains 10 inversions.

For the example shown earlier the list would be [3,0,5,0] for DESCENDING ORDER because [1,2,3] contains 3 inversions, [0,0,0] contains 0 inversions, [2,3,2,1,5] contains 5 inversions, and [5,4,3,2,1] contains 0 inversions.

What is the python algorithm in O(nlogn) that can accomplish this for both ascending and descending order?

Explanation / Answer

# 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] = 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

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.