Question

I am working on the divide/conquer algorithm. I am having a trouble with a print for output from reading the file. Here is my work. When you see I put the comment with TODO. that one I am struck with readfile. I wonder if you'd able to help me to fix the readfile to find a single number. Here is the input3.txt (1 12 13 24 35 46 57 58 69). after that, the output should be 0.

int mergeInversion(int arr[], int l, int m, int r) {

// Size of two arrays

int n1 = m - l + 1;

int n2 = r - m;

/* Create temp arrays */

int L[] = new int[n1];

int R[] = new int[n2];

/* Copy data to temp arrays */

for (int i = 0; i < n1; ++i)

L[i] = arr[l + i];

for (int j = 0; j < n2; ++j)

R[j] = arr[m + 1 + j];

// Counting Inversion

int count = 0;

for (int i = 0; i < n1; i++) {

for (int j = 0; j < n2; j++) {

if (L[i] > R[j]) // Condition to check inversion

{

count++;

}

}

}

return count;

}

// Divide Approach for Inversion

int CountInversion(int arr[], int l, int r) {

int countInv = 0;

if (l < r) {

// Find the middle point

int m = (l + r) / 2;

// Sort first and second halves

countInv = countInv + CountInversion(arr, l, m); // Recursively doing Inversion for first sub array

countInv = countInv + CountInversion(arr, m + 1, r); // Recursively doing Inversion for second sub array

// Merge the sorted halves

countInv = countInv + mergeInversion(arr, l, m, r); // Counting Inversion in from first to Second array

}

return countInv;

}

// Driver method

public static void main(String args[]) throws Exception {

CountingInversion ob = new CountingInversion();

// TODO need to constructor for read file

File readFile = new File("input3.txt");

try {

Scanner scanner = new Scanner(readFile);

while (scanner.hasNextLine()) {

String data = scanner.nextLine();

System.out.println(data);

}

scanner.close();

} catch (FileNotFoundException e) {

System.out.println("An error occurred.");

e.printStackTrace();

}

// Enter Array Values Here.

int arr_rev_sor[] = { 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };

int val = ob.CountInversion(arr_rev_sor, 0, arr_rev_sor.length - 1);

System.out.println("\nTotal Number Of Inversion(Reverse Sorted): " + val);

int arr_sor[] = { 21, 59, 98, 23, 1, 5, 97 };

val = ob.CountInversion(arr_sor, 0, arr_sor.length - 1);

System.out.println("\nTotal Number Of Inversion(Sorted): " + val);

// printing the output

System.out.println(); // TODO need to print for a single number.

}

Answer 1

CODE:

import java.io.*;
import java.util.Scanner;
class CountingInversion{
int mergeInversion(int arr[], int l, int m, int r) {
// Size of two arrays
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/* Copy data to temp arrays */
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
// Counting Inversion
int count = 0;
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
if (L[i] > R[j]) // Condition to check inversion
{
count++;
}
}
}
return count;
}
// Divide Approach for Inversion
int CountInversion(int arr[], int l, int r) {
int countInv = 0;
if (l < r) {
// Find the middle point
int m = (l + r) / 2;
// Sort first and second halves
countInv = countInv + CountInversion(arr, l, m); // Recursively doing Inversion for first sub array
countInv = countInv + CountInversion(arr, m + 1, r); // Recursively doing Inversion for second sub array
// Merge the sorted halves
countInv = countInv + mergeInversion(arr, l, m, r); // Counting Inversion in from first to Second array
}
return countInv;
}
// Driver method
public static void main(String args[]) throws Exception {
CountingInversion ob = new CountingInversion();
// TODO need to constructor for read file
File readFile = new File("input3.txt");
//Declaring array to store values from file
int arr[]=new int[9];
try {
Scanner scanner = new Scanner(readFile);
while (scanner.hasNextLine()) {
String data = scanner.nextLine();
// Splitting the data based on space
// and store it in an string array
String[] ar = data.split(" ");
//Loop to store string elements as integer elements in array
for(int i = 0;i<ar.length;i++){
arr[i] = Integer.parseInt(ar[i]);
}
}
scanner.close();
} catch (FileNotFoundException e) {
System.out.println("An error occurred.");
e.printStackTrace();
}
// Enter Array Values Here.
int arr_rev_sor[] = { 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
int val = ob.CountInversion(arr_rev_sor, 0, arr_rev_sor.length - 1);
System.out.println("\nTotal Number Of Inversion(Reverse Sorted): " + val);
int arr_sor[] = { 21, 59, 98, 23, 1, 5, 97 };
val = ob.CountInversion(arr_sor, 0, arr_sor.length - 1);
System.out.println("\nTotal Number Of Inversion(Sorted): " + val);
// Here we use the array which stores the elements in reading file
// printing the output
val = ob.CountInversion(arr, 0, arr.length - 1);
System.out.println("\nTotal Number Of Inversion: " + val); //Here ouptut is 0.
}
}

CODE SCREENSHOTS:

OUTPUT:

Here I highlighted the code in your program that used to read a file and print output.

Please Don't foget to UPVOTE my solution and Comment if you have any Doubts. I will definitely Answer.