Probleme mit Inversion-Zählung Algorithmus

Question

Ich schrieb eine Implementierung der Inversion-Zählung. Dies ist eine Aufgabe, die in einem Online-Kurs durchgeführt wird. Aber die Eingabe, die ich bekomme, ist nicht korrekt und entsprechend dem, was ich habe, hat das Programm eine korrekte Syntax. Ich habe nicht nur wissen, war ich ging schief Das folgende Programm ist meine Implementierung

import java.io.*; 

class CountInversions { 
    //Create an array of length 1 and keep expanding as data comes in 

    private int elements[]; 
    private int checker = 0; 

    public CountInversions() { 
     elements = new int[1]; 
     checker = 0; 
    } 

    private boolean isFull() { 
     return checker == elements.length; 
    } 

    public int[] getElements() { 
     return elements; 
    } 

    public void push(int value) { 
     if (isFull()) { 
      int newElements[] = new int[elements.length * 2]; 
      System.arraycopy(elements, 0, newElements, 0, elements.length); 
      elements = newElements; 
     } 
     elements[checker++] = value; 
    } 

    public void readInputElements() throws IOException { 
     //Read input from file and until the very last input 
     try { 
      File f = new File("IntegerArray.txt"); 
      FileReader fReader = new FileReader(f); 
      BufferedReader br = new BufferedReader(fReader); 
      String stringln; 
      while ((stringln = br.readLine()) != null) { 
       push(Integer.parseInt(stringln)); 
      } 
      System.out.println(elements.length); 
      fReader.close(); 
     } catch (Exception e) {//Catch exception if any 
      System.err.println("Error: " + e.getMessage()); 
     } finally { 
//   in.close 
     } 
    } 
     //Perform the count inversion algorithm 
    public int countInversion(int array[],int length){ 
     int x,y,z; 
     int mid = array.length/2 ; 
     int k; 
     if (length == 1){ 
      return 0; 
     }else{ 
      //count Leftinversion and count Rightinversion respectively 
      int left[] = new int[mid]; 
      int right[] = new int[array.length - mid]; 

      for(k = 0; k < left.length;k++){ 
       left[k] = array[k]; 
      } 

      for(k = 0 ;k < right.length;k++){ 
       right[k] = array[mid + k]; 
      } 
      x = countInversion(left, left.length); 
      y = countInversion(right, right.length); 
      int result[] = new int[array.length]; 
      z = mergeAndCount(left,right,result); 

      //count splitInversion 
      return x + y + z; 
     } 
    } 

    private int mergeAndCount(int[] left, int[] right, int[] result) { 
     int count = 0; 
     int i = 0, j = 0, k = 0; 
     int m = left.length, n = right.length; 
     while(i < m && j < n){ 
      if(left[i] < right[j]){ 
       result[k++] = left[i++]; 
      }else{ 
       result[k++] = right[j++]; 
       count += left.length - i; 
      } 
     } 
     if(i < m){ 
      for (int p = i ;p < m ;p++){ 
       result[k++] = left[p]; 
      } 
     } 
     if(j < n){ 
      for (int p = j ;p < n ;p++){ 
       result[k++] = right[p]; 
      } 
     } 
     return count; 
    } 
} 
class MainApp{ 
    public static void main(String args[]){ 
     int count = 0; 
     CountInversions cIn = new CountInversions(); 
     try { 
      cIn.readInputElements(); 
      count = cIn.countInversion(cIn.getElements(),cIn.getElements().length); 
      System.out.println("Number of Inversios: " + count); 

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

    } 
} 

Answer 1

Ihr Code funktioniert, wenn die Array-Länge eine Potenz von 2 (tatsächlich ist, ich bin nicht sicher, ob, wenn der Fall ist, siehe unten zweiten Punkt).

Wenn Sie die Eingabe lesen, verdoppeln Sie die Array-Größe, wenn sie voll ist, aber Sie ändern sie nie auf die Anzahl der tatsächlich gelesenen Elemente, die in checker gespeichert ist. Ihre Array-Länge ist also eine Potenz von 2, und wenn die Anzahl der aus der Datei gelesenen keine Potenz von 2 ist, haben Sie ein zu langes Array mit einigen nachlaufenden 0 -Elementen, die den zugewiesenen, aber nicht befüllten Stellen aus der Datei entsprechen . Da Sie countInversions mit der Länge des Arrays und nicht mit der Anzahl der gelesenen Elemente aufrufen, werden diese 0 s ebenfalls sortiert, was zu einigen falschen Inversionen führt.

nach der Eingabe lesen, zuzuteilen ein neues Array

int[] copy = new int[checker]; 
for(int i = 0; i < checker; ++i) { 
    copy[i] = elements[i]; 
} 
elements = copy; 

die Elemente zu kopieren, und das alte Array mit der falschen Kapazität verwerfen.

Ein weiteres Problem in Ihrem Algorithmus ist, dass Sie nie das ursprüngliche Array ändern, weil Sie ein neues Array für das Merge Ergebnis zuteilen,

int result[] = new int[array.length]; 
z = mergeAndCount(left,right,result); 

so verschmelzen Sie unsortiert Arrays, die auch die Inversionszahl Skew kann. Da Sie die Hälften des Eingangsfeldes zu neuen Arrays für die rekursive Aufrufe kopiert, können Sie ohne Probleme setzen das Merge Ergebnis in der übergebene Array, so ersetzen die beiden oben genannten Linien mit

z = mergeAndCount(left,right,array); 

ein Verfahren zu erhalten Das sortiert das Array und zählt die Inversionen.

Answer 2

Dieser Beitrag ist gegen das Problem der Zählung Inversion mit Java (mit Ausnahme der Datei lesen, die Sie auf OK getan haben) - Counting inversions in an array