 # Inversion Count for an array indicates – how far (or close) t...

## Question

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order then inversion count is the maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

Project Description: the file “IntegerArray.txt” included in this project folder contains all 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 i-th row of the file indicates the i-th entry of an array. Because of the large size of this array, you should implement a divide-and-conquer algorithm.

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import sys
import time

# increase the maximum recursion depth
sys.setrecursionlimit(10000)

def conquer(array: [], tmp: [], left: int, mid: int, right: int) -> int:
"""
conquer step, collect all result
:param array: array of integer
:param tmp: temporary array
:param left: left index
:param mid: mid index
:param right: right index
:return: number of insertion
"""
count = 0
ll = left
mm = mid
tt = left

# until reaching one of 2 ending
while ll < mid and mm <= right:
# a[i < a[j], no rul is broken
if array[ll] <= array[mm]:
tmp[tt] = array[ll]
tt += 1
ll += 1
pass
else:
# a[i] > a[j] , j > i
tmp[tt] = array[mm]
tt += 1
mm += 1
# sum up the
count += mid - ll
pass
pass

# copy the rest to tmp array
while ll < mid:
tmp[tt] = arr[ll]
tt += 1
ll += 1
pass

# copy the rest to tmp array
while mm <= right:
tmp[tt] = arr[mm]
tt += 1
mm += 1
pass

# copy tmp arry to the array
ll = left
while ll <= right:
array[ll] = tmp[ll]
ll += 1
pass

return count
pass

def divide(array: [], tmp: [], left: int, right: int) -> int:
"""
divide array and collect insertion number
:param array: the array
:param tmp: the temporary array
:param left: left index
:param right: right index
:return:
"""
count = 0
if left < right:
# get mid index
mid = int((left + right) / 2)...

By purchasing this solution you'll be able to access the following files:
Solution1.zip and Solution2.docx.

\$40.50
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.