Счет инверсии для 100000 целых чисел, используя чтение сортировки слиянием из текстового файла. Но не в состоянии получить правильный счет инверсии - PullRequest
Новая
       18

Счет инверсии для 100000 целых чисел, используя чтение сортировки слиянием из текстового файла. Но не в состоянии получить правильный счет инверсии

0 голосов
/ 29 апреля 2018

Ниже приведен код, который я написал, чтобы прочитать 100000 целых чисел из текстового файла и отсортировать их с помощью сортировки слиянием.

Вопросы:

  1. Сортированные целые числа отображаются в правильном порядке только в консоли eclipse, но когда я пытаюсь записать их в выходной текстовый файл, порядок меняется.

  2. Значение счетчика инверсий 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());
        }
    }
}

Ответы [ 4 ]

0 голосов
/ 22 июня 2019

В вашем коде несколько проблем:

  • вы используете тип 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());
        }
    }
}
0 голосов
/ 03 июня 2018

Это задание из Хакерранк / Практика / Учебные пособия / Взлом интервью Интервью / Сортировка слиянием: Подсчет инверсий : 

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;
}
0 голосов
/ 22 июня 2019

Используйте long вместо int для inv_count. Кроме того, измените тип возвращаемого значения с int на long.

Как и в приведенном выше решении, int переполнен.

0 голосов
/ 03 июня 2018

Ваши рекурсивные вызовы с влево * до середины и в середине + 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;
}
...