Моя программа не считается правильно Инверсии в массиве MergeSort - PullRequest
Новая
       23

Моя программа не считается правильно Инверсии в массиве MergeSort

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

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

Вопросы:

Программа не правильно считает Инверсии, и я не знаю, в чем проблема?

Я тестирую свой код на этом массиве long [] arrayB = {4, 3, 2, 1, 8, 7, 5, 3, 6}. Он показывает 20 инверсий против 15. 

    BufferedReader reader = new BufferedReader(new FileReader("C:\\Users\\Nick\\Desktop\\ArrayInt.txt"));
    long[] arrayA = new long[100_000];
    int i = 0;
    while (reader.readLine() != (null)) {
        arrayA[i] = Long.parseLong(reader.readLine());
        i++;
    }
    reader.close();
    long[] arrayB = {4, 3, 2, 1,  8, 7, 5, 3, 6 };
    long invb = getMergeSort(arrayB);
    long testInvB = simpleInvCount(arrayB);
    System.out.println(invb);
    System.out.println(testInvB);
    System.out.println( (float) testInvB / invb);

}
public static long simpleInvCount(long [] A){
    long invCount = 0;
    for (int i = 0; i < A.length; i++){
        for (int j = 0; j < i; j++){
            if (A[i] < A[j])
                invCount++;
        }
    }
    return invCount;
}

// Получим от сортированного массива методом Слияния 

public static long getMergeSort(long[] A) {
    long invCount = 0;
    if (A.length == 0 || A.length == 1) return 0;
    else {
        int mid = A.length / 2 ;
        long[] left = Arrays.copyOfRange( A, 0, mid); // Левая часть массива
        long[] right = Arrays.copyOfRange( A, mid, A.length); // Правая часть массива
         invCount += getMergeSort(left);
         invCount += getMergeSort(right);

             invCount += toMerge(left,right);
        return invCount;

    }

}

public static long toMerge(long [] left, long [] right){
    long [] temp = new long [left.length + right.length];
    int i = 0, // индекс массива С
    j = 0, // индекс массива Д
    k=0, // индекс итогового массива temp
    invCount = 0; // количество перестановок

    while (i < left.length && j < right.length){
        if (left[i] < right[j]){
            temp[k++] = left[i++];
        } else
            temp[k++] = right[j++];
            invCount = invCount + (left.length - i);
    }

    while (i < left.length){
        temp[k++] = left[i++];
    }

    while (j < right.length){
        temp[k++] = right[j++];
    }

    return invCount;
}

}

В этом массиве long [] arrayB = {4, 3, 2, 1, 8, 7, 5, 3, 6} Я ожидаю, что выходной сигнал будет 15, но фактический выходной сигнал равен 20.

...