Реализация Mergesort .. Подсчет количества инверсий в массиве

Question

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

 /**
   * 
  */

 package com.JavaReference;

 import java.io.BufferedReader;
import java.io.FileReader;
 import java.io.IOException;

public class ReadFile {


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


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

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


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

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


}




 public static Integer[] 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[nLines];
for (int i=0; i < nLines; i++) {
    nData[ i ] = Integer.parseInt((textR.readLine()));

    }
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[]){

int countLeft,countRight,countMerge;
int mid=num.length/2,k;


if (num.length<=1){

    return 0;// Number of inversions will be zero for an array of this size.
}

int left[]=new int[mid];
int right[]=new int [num.length-mid];


for (k=0;k<mid;k++){
    left[k]=num[k];
}

for (k=0;k<mid;k++){
    right[k]=num[mid+k];
}

countLeft=countInversions(left);
countRight=countInversions(right);

int[] result=new int[num.length];
countMerge=mergeAndCount(left,right,result);
/*
 * Assign it back to original array.
 */
for (k=0;k<num.length;k++){
    num[k]=result[k];
}

return(countLeft+countRight+countMerge);
}
private static int mergeAndCount(int left[],int right[],int result[]){
int count=0;
int a=0,b=0,i,k=0;
while((a<left.length)&&(b<right.length)){

    if(left[a]<right[b]){
        result[k]=left[a++];// No inversions in this case.

    }
    else{// There are inversions.

        result[k]=right[b++];
        count+=left.length-a;
    }
    k++;

    // When we finish iterating through a.

if(a==left.length){
    for (i=b;i<right.length;i++){
        result[k++]=right[b];

    }

    }
else{
    for (i=a;i<left.length;i++){

    }
}






}


return count;
  }
  }

Я новичок в Java и Алгоритмах, поэтому любые проницательные предложения были бы полезны!

Answer 1

Я нашел две ошибки:

• В countInversions () , когда num разбивается на left и right, вы предполагаете, что right имеет m элементов. Однако, если num.length нечетно, это будет m + 1 элементов. Решение состоит в том, чтобы использовать right.length вместо m.
• В mergeAndCount () обработка бита, в котором один подрешеток пуст, а у другого все еще есть некоторые элементы, выполняется неправильно.

Примечание:
Нет абсолютно никакой причины использовать Integer в вашей программе, кроме метода Integer.parseInt() (который, кстати, возвращает int).

Исправленный код:

/**
*
*/

package com.JavaReference;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class ReadFile {

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

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

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

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

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

    }

    public static Integer[] 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[nLines];
        for (int i=0; i < nLines; i++) {
            nData[ i ] = Integer.parseInt((textR.readLine()));

        }
        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[]){

        int countLeft,countRight,countMerge;
        int mid=num.length/2,k;

        if (num.length<=1){

            return 0;// Number of inversions will be zero for an array of this size.
        }

        int left[]=new int[mid];
        int right[]=new int [num.length-mid];

        for (k=0;k<mid;k++){
            left[k]=num[k];
        }

        // BUG 1: you can't assume right.length == m
        for (k=0;k<right.length;k++){
            right[k]=num[mid+k];
        }

        countLeft=countInversions(left);
        countRight=countInversions(right);

        int[] result=new int[num.length];
        countMerge=mergeAndCount(left,right,result);
        /*
        * Assign it back to original array.
        */
        for (k=0;k<num.length;k++){
            num[k]=result[k];
        }

        return(countLeft+countRight+countMerge);
    }
    private static int mergeAndCount(int left[],int right[],int result[]){
        int count=0;
        int a=0,b=0,i,k=0;
        while((a<left.length)&&(b<right.length)){

            if(left[a]<right[b]){
                result[k]=left[a++];// No inversions in this case.

            }
            else{// There are inversions.

                result[k]=right[b++];
                count+=left.length-a;
            }
            k++;
        }

        // BUG 2: Merging of leftovers should be done like this
        while (a < left.length)
        {
            result[k++] = left[a++];
        }
        while (b < right.length)
        {
            result[k++] = right[b++];
        }

        return count;
    }
}

Answer 2

Я нашел точное решение в книге Роберта Седжвика «Алгоритмы на языке Java»

1. Читайте здесь о слиянии
2. См. Java-код дляотсчет инверсии

Answer 3

На мой взгляд, подсчет количества инверсий в массиве находит способ сортировки массива в порядке возрастания.После этой мысли вот мое решение:

int countInversionArray(int[] A) {
    if(A.length<=1) return 0;
    int solution = 0;

    for(int i=1;i<A.length;i++){
        int j = i;
        while(j+2<A.length && A[j] > A[j+1]){
            invert2(j,j+1,A);
            solution++;
            j++;
        }
        j=i;
        while(j>0 && A[j] < A[j-1]){
            invert2(j,j-1,A);
            solution++;
            j--;
        }
    }

    return solution;
}

private void invert2(int index1, int index2, int[] A){
    int temp = A[index1];
    A[index1] = A[index2];
    A[index2] = temp;
}

Answer 4

Вы можете попробовать эту реализацию Mergesort на месте на Java. Но необходим минимум 1 временный контейнер данных (в данном случае ArrayList). Также считает инверсии.

///

Sorter.java

public interface Sorter {

    public void sort(Object[] data);

    public void sort(Object[] data, int startIndex, int len);

}

Класс реализации MergeSorter (другие, такие как QuickSorter, BubbleSorter или InsertionSorter, могут быть реализованы на интерфейсе Sorter)

MergeSorter.java

import java.util.List;
import java.util.ArrayList;

public class MergeSorter implements Sorter {

    private List<Comparable> dataList;
    int num_inversion;

    public MergeSorter() {
        dataList = new ArrayList<Comparable> (500);
        num_inversion = 0;
    }

    public void sort(Object[] data) {
        sort(data, 0, data.length);
    }

    public int counting() {
        return num_inversion;
    }

    public void sort(Object[] data, int start, int len) {
        if (len <= 1) return;
        else {
            int midlen = len / 2;

            sort(data, start, midlen);
            sort(data, midlen + start, len - midlen);
            merge(data, start, midlen, midlen + start, len - midlen);
        }
    }

    private void merge(Object[] data, int start1, int len1, int start2, int len2) {
        dataList.clear();

        int len = len1 + len2;

        // X is left array pointer
        // Y is right array pointer

        int x = start1, y = start2;
        int end1 = len1 + start1 - 1;
        int end2 = len2 + start2 - 1;

        while (x <= end1 && y <= end2) {

            Comparable obj1 = (Comparable) data[x];
            Comparable obj2 = (Comparable) data[y];

            Comparable<?> smallobject = null;
            if (obj1.compareTo(obj2) < 0) {
                smallobject = obj1;
                x++;
            }
            else {
                smallobject = obj2;
                y++;
                num_inversion += (end1 - x + 1);
            }

            dataList.add(smallobject);
        }

        while (x <= end1) {
            dataList.add((Comparable)data[x++]);
        }
        while (y <= end2) {
            dataList.add((Comparable)data[y++]);
        }

        for (int n = start1, i = 0; n <= end2; n++, i++) {
            data[n] = dataList.get(i);
        }

    }
}

Для тестирования создайте класс драйвера и введите основной метод

public static void main(String[] args) {

    Object[] data = ...............
    Sorter sorter = new MergeSorter();
    sorter.sort(data)

    for (Object x : data) {
        System.out.println(x);
    }
    System.out.println("Counting invertion: " + ((MergeSorter)sorter).counting());
}