Javaで再帰的なmergesortの小さなねじれ

Question

私はmergesortプログラムをJavaで書こうとしています。残念ながら私の実装では、コードの結果としてゼロのリストが返されます。私はすべてが論理的で、私に正しい順序であると思われるので、キンクを見つけることができませんでした。誰かが私にこの不具合を見つけるのを助けることができれば、私は感謝します。次のように

コードは次のとおりです。

package com.company; 

public class Main { 

public static void main(String[] args) { 
    int[] array = {35,43,21,4,23,1,13,44}; 

    System.out.println("initial array is equal to:"); 
    for (int data:array) { 
     System.out.println(data); 
    } 
    mergeSort(array, new int[array.length], 0, array.length-1); 
    System.out.println("Sorted array is equal to: "); 
    for (int s:array) { 
     System.out.println(s); 
    } 
    // arr = {35,43,21,4,23,1,13,44} 
} 

public static void mergeSort(int[] array,int[] secondaryArray,int leftStart, int rightEnd){ 
    if(leftStart >= rightEnd){ 
     return; 
    } 
    int midPoint = (leftStart + rightEnd)/2; 
    //sorting the left array 
    mergeSort(array, secondaryArray, leftStart, midPoint); 
    //sorting the right array 
    mergeSort(array, secondaryArray, midPoint+1, rightEnd); 
    //merging the sorted left and right array 
    mergeHalves(array, secondaryArray,leftStart, rightEnd); 
} 

public static void mergeHalves(int[] array, int[] secondaryArray, int leftStart, int rightEnd){ 

    int leftEnd = (leftStart + rightEnd)/2; 
    int rightStart = leftEnd + 1; 
    int index = 0; 

    while ((leftStart <= leftEnd) && (rightStart <= rightEnd)){ 
     if(array[leftStart] <= array[rightStart]){ 
      secondaryArray[index] = array[leftStart]; 
      leftStart++; 
     }else { 
      secondaryArray[index] = array[rightStart]; 
      rightStart++; 
     } 
     index++; 
    } 

    System.arraycopy(array,rightStart,secondaryArray,index,rightEnd-rightStart+1); 
    System.arraycopy(array,leftStart,secondaryArray,index,leftEnd-leftStart+1); 
    System.arraycopy(secondaryArray,0,array,0,secondaryArray.length); 

} 
} 

Answer 1

あなたはmergeHalvesの小さなbug-を持って、最終的な配列のコピーは

System.arraycopy(secondaryArray,0,array,0,secondaryArray.length); 

です：

System.arraycopy(secondaryArray,0,array,leftStartCopy,rightEnd-leftStartCopy+1); 

問題は、関連するセルだけでなく、secondaryArrayをすべてarrayにコピーしていることです。これが原因で、arrayは0でいっぱいになりました。

public static void mergeHalves(int[] array, int[] secondaryArray, int leftStart, int rightEnd){ 
int leftStartCopy = leftStart; 
int leftEnd = (leftStart + rightEnd)/2; 
int rightStart = leftEnd + 1; 
int index = 0; 

while ((leftStart <= leftEnd) && (rightStart <= rightEnd)){ 
    if(array[leftStart] <= array[rightStart]){ 
     secondaryArray[index] = array[leftStart]; 
     leftStart++; 
    }else { 
     secondaryArray[index] = array[rightStart]; 
     rightStart++; 
    } 
    index++; 
} 

System.arraycopy(array,rightStart,secondaryArray,index,rightEnd-rightStart+1); 
System.arraycopy(array,leftStart,secondaryArray,index,leftEnd-leftStart+1); 
System.arraycopy(secondaryArray,0,array,leftStartCopy,rightEnd-leftStartCopy+1);} 

Answer 2

は、あなたがコントロールし、あなたが得るものを見るサンプル入力で各部分を実行してみてください。たとえば、異なる入力配列でmergeHalvesを実行し、期待どおりの結果を得ているかどうかを確認します。

もう1つのことは、呼び出されるたびにその入力と最終結果を印刷することです。その後、小さなサンプル（空の配列、1要素の配列、2要素の配列など）でmergeSortを呼び出すと、すぐにコードが実際に行っていることを理解できます。 （leftStartCopyがmergeHalves中に変更されていないleftStartのコピーであると仮定）しなければならないとき