Rekursive Mergesort auf Java

Question

Ich übe Algorithms Frage auf merge sort. Ich baue ein Java-Programm auf merge sort. Ich denke, es gibt einen logischen Fehler in meinem Code.

Das ist mein Ausgang:

Array length = 6 
    value of q 2 
    value of q 1 
    value of q 0 
9 1073741823 left end -----m(0,0,1) 
6 1073741823 right end -----m(0,0,1) 
remaining element left 
6 9 0 0 0 0 ------------------- 
9 6 1073741823 left end -----m(0,1,2) 
5 1073741823 right end -----m(0,1,2) 
remaining element left 
5 9 6 0 0 0 ------------------- 
value of q 4 
value of q 3 
0 1073741823 left end -----m(3,3,4) 
8 1073741823 right end -----m(3,3,4) 
remaining element right 
5 9 6 0 8 0 ------------------- 
0 8 1073741823 left end -----m(3,4,5) 
2 1073741823 right end -----m(3,4,5) 
remaining element left 
5 9 6 0 2 8 ------------------- 
9 6 5 1073741823 left end -----m(0,2,5) 
0 8 2 1073741823 right end -----m(0,2,5 
remaining element left 
0 8 2 9 6 5 ------------------- 
0 8 2 9 6 5 

Dies ist mein Code:

public class MergeSort{ 
    private int[] digits; 
    private static int[] dummy; 
    private int length; 

    public static void main(String[] args) { 
     int [] digits = {9,6,5,0,8,2}; 
     System.out.println("Array length = "+digits.length); 
     MergeSort ms = new MergeSort(); 
     ms.sort(digits); 


     for(int a :dummy){ 
      System.out.print(a+" "); 
     } 
    } 
    void sort(int [] digits){ 
     this.digits=digits; 
     length=digits.length; 
     dummy= new int[length]; 
     mergesort(0,length-1); 
    } 

    void mergesort(int p,int r){ 
     int q; 
     if(p < r){ 
      q = (p + r)/2; 

      System.out.println("value of q "+q); 
      mergesort(p,q); 
      mergesort(q+1,r); 
      merge(p,q,r); 
      System.out.println("-------------------"); 
     } 
    } 

    void merge(int p,int q,int r){ 
     int i,j,k; 
     int n1=q-p+1; 
     int n2 =r-q; 
     int [] left = new int[n1+1]; 
     int [] right = new int[n2+1]; 
     int [] arr=new int[n1+n2]; 
     for(i = 0; i<n1;i++){ 
      left[i]= digits[p+i]; 
      //System.out.print(left[i]+" "); 
     } 

     for(j = 0; j < n2; j++){ 
      right[j]= digits[q+j+1]; 
      //System.out.print(left[j]+" "); 
     } 
     left[n1] = Integer.MAX_VALUE/2; 
     right[n2] = Integer.MAX_VALUE/2; 

     for(i = 0; i < left.length; i++){ 
      System.out.print(left[i] + " "); 
     } 
     System.out.println("left end -----m("+p+","+q+","+r+")"); 
     for(j = 0; j < right.length; j++){ 
      System.out.print(right[j]+" "); 
     } 
     System.out.println("right end -----m("+p+","+q+","+r+")"); 

     i=0; 
     j=0; 
     for(k = p; k < r; k++){ 
     if(left[i]<right[j]){ 
      dummy[k]=left[i]; 
      i++; 
     } 

     else { 
      dummy[k] = right[j]; 
      j++; 
     } 
    } 

    while(i<n1) 
     dummy[k]=left[i]; 
     i++; 
     k++; 
     System.out.println("remaining element left"); 
    } 

    while(j<n2){ 
     dummy[k]=right[j]; 
     j++; 
     k++; 
     System.out.println("remaining element right"); 
    } 

     for(int a: dummy){ 
      System.out.print(a+" "); 
     } 
    } 
} 

Answer 1

Für Mergesort arbeiten, um es Ergebnisse von Vorschauen kleiner Berechnung nehmen muss und sie für die nächste Stufe der Berechnung verwenden Ihre Ergebnisse werden jedoch im Dummy gespeichert, der nie als Quelle für die nächste Berechnung verwendet wird. Ich würde sugest merge zu machen und MergeSort Funktionen Rückgabewert ist es viel besser lesbar und sauberer hier ist meine Version, wenn Sie

public class MergeSort { 

public static void main(String ...args){ 
    int[]array = {9,6,5,0,8,2}; 
    String sortedResultToPrint = Arrays.toString(sort(array)); 
    System.out.println(sortedResultToPrint); 
} 
public static int[] sort(int[] array) { 
    int[] result = mergSort(array, 0, array.length-1); 
    return result; 
} 

private static int[] mergSort(int[] array, int start, int end) { 
    int[] result = null; 
    if (start < end) { 
     int midle = (start + end)/2; 
     int[] left = mergSort(array, start, midle); 
     int[] right = mergSort(array, midle + 1, end); 
     result = merge(left, right); 
    } else { 
     result = new int[]{array[start]}; 
    } 
    return result; 
} 

private static int[] merge(int[] left, int[] right) { 
    int[] result = new int[left.length + right.length]; 

    int leftPtr = 0; 
    int rightPtr = 0; 
    for (int i = 0; i < result.length; i++) { 
     // Copyed all the left part only right remains 
     if (leftPtr >= left.length) { 
      result[i] = right[rightPtr++]; 
     } 

     // Copyed all the right part only left remains 
     else if (rightPtr >= right.length) { 
      result[i] = left[leftPtr++]; 
     } 

     //Right is smaller than left 
     else if (right[rightPtr] < left[leftPtr]) { 
      result[i] = right[rightPtr++]; 
     } 

     // Left is smaller than right 
     else { 
      result[i] = left[leftPtr++]; 
     } 

    } 
    return result; 
} 

}