Счет инверсии для 100000 целых чисел, используя чтение сортировки слиянием из текстового файла. Но не в состоянии получить правильный счет инверсии
Ниже приведен код, который я прочитаю из текстового файла 100000 целых чисел и, используя сортировку слиянием, отсортирует числа.
Проблемы:1. Сортированные целые числа отображаются в правильном порядке только в консоли eclipse, но когда я пытаюсь записать его в выходной текстовый файл, порядок меняется.
- Насколько мне известно, значение счетчика инверсий в 100000 целых чисел из данного текстового файла должно быть около 2407905288, но я получаю значение 8096.
Пожалуйста, помогите мне решить эти две проблемы. Огромное спасибо заранее.
package com.inversioncount;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class inversioncount
{
public static int mergeSort(Integer[] arr, int array_size)
{
int temp[] = new int[array_size];
return _mergeSort(arr, temp, 0, array_size - 1);
}
/* An auxiliary recursive method that sorts the input array and
returns the number of inversions in the array. */
public static int _mergeSort(Integer arr[], int[] temp, int left, int right)
{
int mid, count = 0;
if (right > left)
{
/* Divide the array into two parts and call _mergeSortAndCountInv()
for each of the parts */
mid = (right + left)/2;
/* Inversion count will be sum of inversions in left-part, right-part
and number of inversions in merging */
count = _mergeSort(arr, temp, left, mid);
count += _mergeSort(arr, temp, mid+1, right);
/*Merge the two parts*/
count += merge(arr, temp, left, mid+1, right);
}
return count;
}
/* This method merges two sorted arrays and returns inversion count in
the arrays.*/
static int merge(Integer arr[], int temp[], int left, int mid, int right)
{
int x, y, z;
int count = 0;
x = left; /* i is index for left subarray*/
y = mid; /* j is index for right subarray*/
z = left; /* k is index for resultant merged subarray*/
while ((x <= mid - 1) && (y <= right))
{
if (arr[x] <= arr[y])
{
temp[z++] = arr[x++];
}
else
{
temp[z++] = arr[y++];
count = count + (mid - x);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (x <= mid - 1)
temp[z++] = arr[x++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (y <= right)
temp[z++] = arr[y++];
/*Copy back the merged elements to original array*/
for (x=left; x <= right; x++)
arr[x] = temp[x];
return count;
}
// Driver method to test the above function
public static void main(String[] args) throws FileNotFoundException
{
try {
BufferedReader br = new BufferedReader(new FileReader("IntegerArray.txt"));
List<Integer> lines = new ArrayList<Integer>();
String line;
while ((line = br.readLine()) != null) {
lines.add(Integer.parseInt(line));
}
br.close();
Integer[] inputArray = lines.toArray(new Integer[lines.size()]);
inversioncount.mergeSort(inputArray, inputArray.length - 1);
System.out.println("Number of inversions are " + mergeSort(inputArray, inputArray.length));
// BufferedWriter writer = null;
//writer = new BufferedWriter(new FileWriter("OutputLatest.txt"));
for (Integer i : inputArray)
{
System.out.println(i);
//Writing sorted lines into output file
// writer.write(i);
// writer.newLine();
}
}
catch (IOException ie)
{
System.out.print(ie.getMessage());
}
}
}
2 ответа
В вашем коде есть несколько проблем:
- вы используете тип
int
для вычисления количества инверсий. Максимальное значение для типаint
является2147483647
. Вместо этого вы должны использовать типlong
который может обрабатывать значения до9223372036854775807
. ты звонишь
mergeSort
дважды вmain()
метод с конфликтующими размерами массива:inversioncount.mergeSort(inputArray, inputArray.length - 1); System.out.println("Number of inversions are " + mergeSort(inputArray, inputArray.length));
Вместо этого вы должны вызвать его только один раз с правильной длиной:
long inversion_count = mergeSort(inputArray, inputArray.length); System.out.println("Number of inversions is " + inversion_count + "\n");
Непонятно указывать
right
как индекс последнего элемента в срезе. Гораздо более регулярный и идиоматический подход используетright
как индекс первого элемента за концом среза.
Вот исправленная версия:
package com.inversioncount;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class inversioncount {
public static long mergeSort(Integer[] arr, int array_size) {
int temp[] = new int[array_size];
return _mergeSort(arr, temp, 0, array_size);
}
/* An auxiliary recursive method that sorts a slice of the input array and
returns the number of inversions. */
static long _mergeSort(Integer arr[], int[] temp, int left, int right) {
long count = 0;
if (right - left > 1) {
/* Divide the array into two parts and call _mergeSort() for each of the parts */
int mid = (right + left + 1) / 2;
/* Inversion count will be sum of inversions in left-part, right-part
and number of inversions in merging */
count += _mergeSort(arr, temp, left, mid);
count += _mergeSort(arr, temp, mid, right);
/* Merge the two parts */
count += merge(arr, temp, left, mid, right);
}
return count;
}
/* This method merges two sorted slices of the array and returns the inversion count */
static long merge(Integer arr[], int temp[], int left, int mid, int right) {
long count = 0;
int x = left; /* x is index for left subarray */
int y = mid; /* y is index for right subarray */
int z = left; /* z is index for resultant merged subarray */
while (x < mid && y < right) {
if (arr[x] <= arr[y]) {
temp[z++] = arr[x++];
} else {
temp[z++] = arr[y++];
count += mid - x;
}
}
/* Copy the remaining elements of left subarray if any */
while (x < mid)
temp[z++] = arr[x++];
/* Copy the remaining elements of right subarray if any */
while (y < right)
temp[z++] = arr[y++];
/* Copy back the merged elements to original array */
for (x = left; x < right; x++)
arr[x] = temp[x];
return count;
}
// Driver method to test the above function
public static void main(String[] args) throws FileNotFoundException {
try {
BufferedReader br = new BufferedReader(new FileReader("IntegerArray.txt"));
List<Integer> lines = new ArrayList<Integer>();
String line;
while ((line = br.readLine()) != null) {
lines.add(Integer.parseInt(line));
}
br.close();
Integer[] inputArray = lines.toArray(new Integer[lines.size()]);
long inversion_count = mergeSort(inputArray, inputArray.length);
System.out.println("Number of inversions is " + inversion_count + "\n");
//BufferedWriter writer = null;
//writer = new BufferedWriter(new FileWriter("OutputLatest.txt"));
for (Integer i : inputArray) {
System.out.println(i);
// Writing sorted lines into output file
//writer.write(i);
//writer.newLine();
}
} catch (IOException ie) {
System.out.print(ie.getMessage());
}
}
}
Используйте long вместо int для inv_count
. Кроме того, измените тип возвращаемого значения с int на long.
Как и в предыдущем решении, int
переполнен.
Это задание из Hackerrank/ Практика / Учебники / Взлом Интервью по кодированию / Сортировка слиянием: Подсчет инверсий:
static long mergeSort(int[] arr, int l, int r) {
long swaps = 0;
if (l < r) {
int p = (l + r) / 2;
swaps += mergeSort(arr, l, p);
swaps += mergeSort(arr, p + 1, r);
// Merge
int[] la = Arrays.copyOfRange(arr, l, p + 1);
int[] ra = Arrays.copyOfRange(arr, p + 1, r + 1);
int i = l, lai = 0, rai = 0;
while (lai < la.length && rai < ra.length) {
if (ra[rai] < la[lai]) {
arr[i++] = ra[rai++];
swaps += la.length - lai;
} else {
arr[i++] = la[lai++];
}
}
while (lai < la.length) {
arr[i++] = la[lai++];
}
while (rai < ra.length) {
arr[i++] = ra[rai++];
}
}
return swaps;
}
Ваши рекурсивные вызовы слева направо и середина +1 справа, как показано здесь:
count = _mergeSort(arr, temp, left, mid);
count += _mergeSort(arr, temp, mid+1, right);
Поэтому правильный вызов функции слияния должен быть:
count += merge(arr, temp, left, mid, right);
Есть также некоторые ошибки в определении слияния. Позвольте мне указать вам на них:
x
должен отличаться от left
в mid
, у должен отличаться от mid+1
в right
x = left; /* i is index for left subarray*/
y = mid+1; /* j is index for right subarray*/
z = left; /* k is index for resultant merged subarray*/
while ((x <= mid) && (y <= right))
Кроме того, счет инверсии фактически равен count = count + (mid - x) + 1;, Вы можете понять это, взяв небольшой массив из 5 элементов.
Также индексы для температуры всегда начинаются с 0.
Поэтому правильная функция слияния:
static int merge(Integer arr[], int temp[], int left, int mid, int right)
{
int x, y, z ;
int count = 0;
x = left; /* i is index for left subarray*/
y = mid+1; /* j is index for right subarray*/
z = 0; /* k is index for resultant merged subarray*/
while ((x <= mid) && (y <= right))
{
if (arr[x] <= arr[y])
{
temp[z++] = arr[x++];
}
else
{
temp[z++] = arr[y++];
count = count + (mid - x) + 1;
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (x <= mid)
temp[z++] = arr[x++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (y <= right)
temp[z++] = arr[y++];
/*Copy back the merged elements to original array*/
z = 0;
for (x=left; x <= right; x++)
arr[x] = temp[z++];
return count;
}