Question

Description

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 that 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).

Requirements:

• Design should be based on divide and conquer.

• Running time should NOT be worse than Θ (n log n).

• Must use recursion to subproblems

Input Specification

Your program should read from an input file, which starts with a line indicating the number of test cases. Each of the following lines indicates a test case, and each test case includes a sequence of numbers (separated by spaces) for which you need to count inversions.

Sample Input

3

2 4 1 3 5

1 2 4 8 9 3 5 6

1 20 6 4 5

Output Specification

For each test case, print one line with a format of The sequence has ? inversions in console.

Sample Output

Below is the correct output for the previous sample input.

The sequence has 3 inversions.

The sequence has 7 inversions.

The sequence has 5 inversions.

Hints:

The design can be based on merge sort.

How to get number of inversions in merge()?

Input file

input.txt

3

2 4 1 3 5

1. 2 4 8 9 3 5 6

1. 20 6 4 5

Please code in C++ thank you for your help and time!!

Answer 1

///////////////////////////////////////////////////////////////////////////////////////////////////////////

CODE:-

//////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

int inver = 0;
int curLin = 0;
int noEl = 0;
int element[100]; // Temporary Holding Array

void inverCal(int ele[]) {
   for (int i = 0; i < noEl; i++) {
       for (int j = i + 1; j < noEl; j++) {
           if (ele[i] > ele[j]) {
               inver++;
           }
       }
   }
}

int main() {

int elements[noEl]; // Array that holds elements in current line.   

   std::ifstream file("test.txt");
   std::string str;

   // Below code reads text file line by line.

   while (std::getline(file, str)) {
       std::istringstream is(str);

       int ele;
       int n = 0;
       while (is >> ele) {
           element[n] = ele;
           if (curLin > 0) {

             // This holds no of elements in the current line.Which will be used to give size to our array "elements".
               noEl++;
           }
           n++;
       }
       n = 0;

       // Code below assigns values from temporary array "element" to the array we will use to find inversions "elements".
       if (curLin > 0) {
           for (int i = 0; i < noEl; i++) {
               elements[i] = element[i];
           }

           // Method below takes integer array as an argument and finds the inversions.
           inverCal(elements);
           std::cout << "The sequence has " << inver << " inversions." << "\n";
           inver = 0;
           noEl = 0;
       }

      // Code below increment the value of current line to 1 to indicate actual values are starting now.
       if (curLin == 0) {
           curLin++;
       }
   }
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////

Input :-

//////////////////////////////////////////////////////////////////////////////////////////////////////////////

3
2 4 1 3 5
1 2 4 8 9 3 5 6
1 20 6 4 5

//////////////////////////////////////////////////////////////////////////////////////////////////////////////

Output :-

//////////////////////////////////////////////////////////////////////////////////////////////////////////////