Javaマージソートの実装

Question

Javaでマージソートを実装しようとしています。コードは私にとってうまく見えますが、出力として最初のソートされていない配列を返します。私はすべての基本を今学んでいるので、エラーを見つけるのは難しいです。

import java.util.Scanner; 
class Hacker{ 
    int[] input=new int[]{2,4,1,6,8,5,3,7}; 
    int[] left; 
    int[] right; 
    //int size; 
    Scanner scan=new Scanner(System.in); 

    public void mergeSort(int[] input){ 
     if(input.length<2){ 
      return; 
     } 
     int mid=input.length/2; 
     left=new int[mid]; 
     right=new int[input.length-mid]; 
     System.arraycopy(input, 0, left, 0, left.length); 
     System.arraycopy(input, mid, right, 0, right.length); 
     mergeSort(left); 
     mergeSort(right); 
     merge(input,left,right); 
    } 

    public void merge(int[]input,int[]left,int[]right){ 
     int i=0,j=0,k=0; 
     while(i<left.length&&j<right.length){ 
      if(left[i]<right[j]){ 
       input[k++]=left[i++]; 
      } 
      else{ 
       input[k++]=right[j++]; 
      } 
     } 
     while(i<left.length){ 
      input[k++]=left[i++]; 
     } 
     while(j<right.length){ 
      input[k++]=right[j++]; 
     } 
    } 


    public static void main(String args[]){ 
     Hacker h=new Hacker(); 

     h.mergeSort(h.input);   
     for(int i=0;i<h.input.length;i++){ 
      System.out.print(h.input[i]); 
     } 
    } 
} 

出力：

24168537 

Answer 1

あなたの問題は、あなたがインスタンス変数left、再帰的な方法でrightとinputを使用していることです。これは、すべての再帰呼び出しが値を上書きしていることを意味します。再帰には、メソッドから結果を返すローカル変数が必要です。これはまた、メソッドが静的であり、コードをよりクリーンにすることを意味します。

ここでコードを変換してローカル変数を使用し、計算結果を返します。私はまた、いくつかを単純化しました。あなたの参考のために

public class Sorter { 
    public static int[] mergeSort(int[] input) { 
     if (input.length < 2) { 
      return input; 
     } 
     int mid = input.length/2; 
     int[] left = Arrays.copyOfRange(input, 0, mid); 
     int[] right = Arrays.copyOfRange(input, mid, input.length); 
     return merge(mergeSort(left), mergeSort(right)); 
    } 

    public static int[] merge(int[] left, int[] right) { 
     int i = 0, j = 0, k = 0; 
     int[] output = new int[left.length + right.length]; 
     while (i < left.length && j < right.length) { 
      if (left[i] < right[j]) { 
       output[k++] = left[i++]; 
      } else { 
       output[k++] = right[j++]; 
      } 
     } 
     while (i < left.length) { 
      output[k++] = left[i++]; 
     } 
     while (j < right.length) { 
      output[k++] = right[j++]; 
     } 
     return output; 
    } 

    public static void main(String args[]) { 
     int[] input = new int[]{2, 4, 1, 6, 8, 5, 3, 7}; 
     System.out.println(Arrays.toString(Sorter.mergeSort(input))); 
    } 
} 

は、ここでは二つの方法を組み合わせて、新しい配列を作成するのではなく、その場でソートして単純化したバージョンです。個人的に

public void mergeSort(int[] input) { 
    if (input.length >= 2) { 
     int[] left = copyOfRange(input, 0, input.length/2); 
     int[] right = copyOfRange(input, input.length/2, input.length); 
     mergeSort(left); 
     mergeSort(right); 
     for (int i = 0, j = 0, k = 0; i < left.length || j < right.length; k++) { 
      if (i >= left.length || (j < right.length && left[i] > right[j])) 
       input[k] = right[j++]; 
      else 
       input[k] = left[i++]; 
     } 
    } 
} 

Answer 2

むしろI：

private static void mergeSort(double[] arr, int start, int end){ 
    if(start < end){ 
     int mid = (start + end)/2; 
     mergeSort(arr, start, mid); 
     mergeSort(arr, mid + 1, end); 
     Merge(arr, start, mid, end); 
    } 
} 


private static void Merge(double[] arr, int start, int mid, int end){ 

    double[] leftArray = new double[mid - start + 2]; 
    double[] rightArray = new double[end - mid + 1]; 
    for(int i = start; i <= mid; i++) 
     leftArray[i - start] = arr[i]; 
    for (int i = mid + 1; i <= end; i++) 
     rightArray[i - mid - 1] = arr[i]; 

    leftArray[mid - start + 1] = Double.POSITIVE_INFINITY; 
    rightArray[end - mid] = Double.POSITIVE_INFINITY; 

    int leftIndex = 0, rightIndex = 0; 

    for (int k = start; k <= end; k++){ 
     if(leftArray[leftIndex] <= rightArray[rightIndex]) 
      arr[k] = leftArray[leftIndex++]; 
     else 
      arr[k] = rightArray[rightIndex++]; 
    } 
}