왜 분류 기능이 제대로 병합되지 않습니까?

Question

이 병합 정렬은 어떤 이유로 제대로 작동하지 않습니다. 거의 옳았지 만별로는 아닙니다. 병합 함수는 테스트 한 정렬 된 배열의 모든 집합에서 제대로 작동하며 mergeSort 함수에는 명백한 문제가없는 것 같습니다. 내가 뭘 놓치고 있니?

입력 예 : 7,1,5,6,9,3,8,0,2,1. 정렬 후 0 1 1 1 1 3 1 5 6 1. 각 후

병합 : 1000

1 1 5 6 9 3 8 0 2 1 
1 1 5 6 9 3 8 0 2 1 
1 1 5 6 9 3 8 0 2 1 
1 1 5 6 9 3 8 0 2 1 
1 1 5 6 9 3 8 0 2 1 
1 1 5 6 9 0 3 0 2 1 
1 1 5 6 9 0 3 0 1 1 
1 1 5 6 9 0 1 1 3 1 
0 1 1 1 1 3 1 5 6 1 

은 어레이 크기가 다른 경우가 모두 항상 에러없이 완료되도록 뚜껑과 같은 배열의 단부에 부가된다.

void mergeSort(int arr[], int p, int r){ 
    if(p < r){ 
     int q = Math.floorDiv(p+r, 2); 
     mergeSort(arr,p,q); 
     mergeSort(arr,q+1,r); 
     merge(arr,p,q,r); 
    } 
} 

void merge(int arr[], int p, int q, int r){ 
    int n1 = q-p+1; 
    int n2 = r-q; 

    int merge1[] = new int[n1+1]; 
    int merge2[] = new int[n2+1]; 

    for(int i = 0; i<n1; i++) 
     merge1[i] = arr[p+i]; 
    for(int j = 0; j<n2; j++) 
     merge2[j] = arr[q+j+1]; 

    merge1[n1] = 1000; 
    merge2[n2] = 1000; 

    int i = 0; 
    int j = 0; 

    for(int k = p; k<r; k++){ 
     if(merge1[i] < merge2[j]){ 
      arr[k] = merge1[i]; 
      i++; 
     } else { 
      arr[k] = merge2[j]; 
      j++; 
     } 
    } 
} 

Answer 1

나는 그것을 알아 냈다! merge 함수의 문제 인 for(int k = p; k<r; k++){에 문제가있었습니다.

기본적으로 은 배열의 마지막 색인입니다. 따라서 배열의 마지막 인덱스 이전까지 반복함으로써 매번 마지막 숫자를 놓쳤습니다.

변경은 >=