Mergesort Implementation ..計數陣列中的反轉次數

Question

我正在參加算法的在線類，並嘗試實現在數字列表中查找反轉次數的mergesort實現。但是，我不能確定我的執行過程中我做了什麼錯誤，因爲返回的反轉次數遠遠低於我在執行暴力破解時獲得的次數。伊夫放在下面

/** 
    * 
    */ 

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中，這就地歸併FPGA實現。但是最少需要1個臨時數據容器（在這種情況下是ArrayList）。還計算倒數。

///

Sorter.java

public interface Sorter { 

    public void sort(Object[] data); 

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

} 

MergeSorter實現類

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); 
     } 

    } 
} 

（其他類似QuickSorter，BubbleSorter或InsertionSorter可以分揀機接口上實現）

對於測試，創建一個驅動程序類和類型主要方法

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()); 
} 

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

我發現羅伯特·塞奇威克書

1. 閱讀 「在Java語言算法」 一分辯解決方案here about merge
2. 見java code for counting of inversion