mergesort가 올바른 값을 출력하지 않습니다

Question

mergesort 알고리즘을 구현하려고하는데 아래에서 보았던 것을했으나 올바른 결과를 얻지 못하는 것 같습니다. 내 코드를 확인하고 제가 누락 된 부분을 알려주십시오.

package test; 

public class MergeSort { 

    private static void mergesort(int[] arr, int n) { 
     int mid; 
     int[] left; 
     int[] right; 
     if(n<2){return;} 
     mid = n/2; 

     left = new int[mid]; 
     right = new int[n-mid]; 

     for(int i=0;i<mid;i++){ 
      left[i]=arr[i]; 

     } 
     for(int i=mid;i<n;i++){ 
      right[i-mid]=arr[i]; 

     } 

     mergesort(left,mid); 
     mergesort(right,n-mid); 
     merge(arr,left,mid,right,n-mid); 

    } 


private static void merge(int[] arr, int[] left, int leftcount, int[] right, int rightcount) { 
    // TODO Auto-generated method stub 
    int i,j,k; 

    i=0;j=0;k=0; 

    while(i<leftcount && j<rightcount){ 
     if(left[i] <right[i]){ 
      arr[k]=left[i]; 
      k++; 
      i++; 
     } 
     else{ 
      arr[k]=right[j]; 
      k++; 
      j++; 

     } 
    } 

    //copy what left if any 
    while(i<leftcount){ 
     arr[k]=left[i]; 
     k++; 
     i++; 
    } 
    //copy whats left if any 
    while(j<rightcount){ 
     arr[k]=right[j]; 
     k++; 
     j++; 
    } 

} 

public static void main(String[]args){ 

    int[] arr = {2,4,1,7,3}; 
    for(int i = 0;i<arr.length;i++){ 
     System.out.print(arr[i] + " "); 
    } 
    System.out.println(); 
    mergesort(arr,arr.length); 
    for(int i = 0;i<arr.length;i++){ 
     System.out.println(arr[i] +" "); 
    }  
    } 
} 

내 테스트 배열이 정렬로 표시되어 있으므로 {2,4,1,7,3}; 하지만 난 내 정렬 된 배열로 이것을 가지고 {1 3 7 2 4}

Answer 1

귀하의 문제는이 라인에있다 : {2, 4} 및 {1, 3, 7} :

if(left[i] <right[i]){ 

이제 두 부분 집합이 있다고 가정.

i = 0: right[i] < left[i] 당신은 당신이 원하는 {1, 3}보다는 {1, 2} 얻을

i = 1: right[i] < left[i]{1}를 얻을.

문제는 left[]과 right[]과 같은 색인입니다.

해결 방법 :

if(left[i] <right[j]){ 

참고에 행을 변경해 : 게다가, 디버깅 학습, 그것은 매우 중요한 기술이다.