QuestionQuestion

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 PreviewSolution 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.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats