Implementacja Mergesorta. Zliczanie liczby inwersji w tablicy

Question

Biorę klasę online na Algorytmy i próbuję wdrożyć implementację mergesort znalezienia liczby przewrotów na liście liczb. Ale nie mogę zrozumieć, co robię źle z moją implementacją, ponieważ liczba odwróconych zwrotów jest znacznie niższa niż liczba, którą uzyskuję, wykonując podejście brutalnej siły. Ive położyłem wdrażania podejścia mergesort poniżej

/** 
    * 
    */ 

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

Jestem początkujący w Javie i algorytmów więc wszelkie wnikliwe sugestie byłoby świetnie!

Answer 1

znalazłem dwa błędy:

• W countInversions(), gdy num jest podzielony na left i right założyć right ma m elementy. Jednak gdy num.length jest nieparzyste, będą to elementy m + 1. Rozwiązaniem jest użycie right.length zamiast m.
• W mergeAndCount(), obsługa bitu, w którym jedna podmara jest pusta, a druga nadal zawiera pewne elementy, nie jest wykonywana poprawnie.

Notatka:
Nie ma absolutnie żadnego powodu, aby użyć Integer w programie, z wyjątkiem metody Integer.parseInt() (który, nawiasem mówiąc, zwraca się int).

Poprawiono kod:

/** 
* 
*/ 

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

Można spróbować tego w miejscu mergesort implementacja na Java. Ale potrzebny jest przynajmniej 1 tymczasowy kontener danych (w tym przypadku ArrayList). Zlicza również inwersje.

///

Sorter.java

public interface Sorter { 

    public void sort(Object[] data); 

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

} 

MergeSorter klasa realizacja (inne jak QuickSorter, BubbleSorter lub InsertionSorter mogą być realizowane na interfejsie 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); 
     } 

    } 
} 

Aby przetestować, utwórz klasę kierowcy i typ główną metodą

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

Tak jak ja to widzę, licząc liczbę inwersji w tablicy jest znalezienie sposobu sortowania tablicy w kolejności rosnącej.W następstwie tej myśli, tu jest moje rozwiązanie:

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

znalazłem rigth rozwiązanie Robert Sedgewick książki "Algorytmy w języku Java"

1. Czytaj here about merge
2. Zobacz java code for counting of inversion