Реализация mergeSort для определения количества неработающих инверсий при попытке чтения из файла - PullRequest
2 голосов
/ 20 марта 2012

Я пытаюсь сделать реализацию сортировки слиянием, чтобы найти число инверсий.,Массив, кажется, возвращает правильные результаты для небольшого списка чисел, которые жестко запрограммированы, но возвращает неправильное число, когда я читаю из файла.Я думаю, это как-то связано со сравнением строки-целого, но не могу понять, в чем именно проблема.Любое понимание было бы полезно. Вот (соответствующий) код -

public class ReadFile {


public static void main(String args[]){
    int count=0;
    int n[];


int i=0;
    try{
    n=OpenFile();
    int num[] = new int[n.length];

    for (i=0;i<n.length;i++){
        num[i]=n[i];
    //  System.out.println( "Num"+num[i]);
    }
    count=countInversions(num);


    }
    catch(IOException e){
        e.printStackTrace();
    }

    System.out.println(" The number of inversions"+count);


}




 public static int [] OpenFile()throws IOException{

    FileReader fr=new FileReader("C:/IntegerArray.txt");// to put in file name.

BufferedReader textR= new BufferedReader(fr);
int nLines=readLines();
System.out.println("Number of lines"+nLines);
  //    Integer[] nData=new Integer[5000];
int[] nData=new int[nLines];

    //int nData[]={1,3,5,2,4,6};


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

    nData[ i ] = Integer.parseInt((textR.readLine()));// **Is this causing the problem?**

    }

textR.close();

return nData;


}

 public static int readLines() throws IOException{


FileReader fr=new FileReader("C:/IntegerArray.txt");
BufferedReader br=new BufferedReader(fr);


int numLines=0;
//String aLine;

while(br.readLine()!=null){
    numLines++;
}
System.out.println("Number of lines readLines"+numLines);
return numLines;

}
 public static int countInversions(int num[]){...

}

1 Ответ

2 голосов
/ 20 марта 2012

Вы получаете целочисленное переполнение.Сами числа могут состоять максимум из 5 цифр, но, поскольку у вас есть 100000 элементов, число может достигать ½ × 100000 2 = 5 × 10 9 , что слишком много для int.Измените следующее значение на long с:

  • count (в основном)
  • countLeft, countRight, countMerge (в countInversions)
  • типы возврата countInversionsи mergeAndCount
...