Java에서 병합 정렬 구현 질문

Question

나는 알고리즘 과정에 있으며 병합 정렬에 대해 배우고 있습니다. 우리 교수는이 책에 제공된 의사 코드를 구현하도록 권장했습니다. I는 정수 배열을 정렬 센티넬 값 으로는 Integer.MAX_VALUE를 사용하여 정정

1. 오전 (라인 아래 병합 방법의 의사 코드 8 & 9에서 사용)?
2. Merge-Sort 의사 코드 메소드의 2 행에서 Math.ceil()을 사용하여 Java에서 코드를 작성하는 것이 맞습니까? (편집 : 실제로는 바닥이고 이것을 반영하기 위해 코드를 업데이트했습니다.)

다른 실수가 있으면 알려주세요.

다음은 병합 정렬에 사용되는 의사 코드입니다. 나는 자바에서 코딩하는 방법을 여기

그리고는 다음과 같습니다

public void mergeSort(int[] arrNums, int p, int r) { 
    if (p < r) { 
     int q = (p + r)/2; 
     mergeSort(arrNums, p, q); 
     mergeSort(arrNums, q + 1, r); 
     merge(arrNums, p, q, r); 
    } 
} 

public void merge(int[] arrNums, int p, int q, int r) { 
    int nOne = q - p + 1; 
    int nTwo = r - q; 

    int[] arrLeft = new int[nOne + 1]; 
    int[] arrRight = new int[nTwo + 1]; 

    for (int i = 0; i < nOne; i++) { 
     arrLeft[i] = arrNums[p + i - 1]; 
    } 

    for (int j = 0; j < nTwo; j++) { 
     arrRight[j] = arrNums[q + j]; 
    } 

    arrLeft[nOne] = Integer.MAX_VALUE; 
    arrRight[nTwo] = Integer.MAX_VALUE; 

    // Tracks arrLeft index 
    int i = 0; 

    // Tracks arrRight index 
    int j = 0; 

    for (int k = p; k < r; k++) { 
     if (arrLeft[i] <= arrRight[j]) { 
      arrNums[k] = arrLeft[i]; 
      i++; 
     } else { 
      arrNums[k] = arrRight[j]; 
      j++; 
     } 
    } 
} 

Answer 1

당신의 merge 방법의 마지막 for 루프는 k 변수는 p - 1에서 시작해야합니다

for (int k = p - 1; k < r; k++) { 
    if (arrLeft[i] <= arrRight[j]) { 
     arrNums[k] = arrLeft[i]; 
     i++; 
    } else { 
     arrNums[k] = arrRight[j]; 
     j++; 
    } 
} 

많은 교과서의 의사 코드 배열 인덱스를 1부터 시작하기를 원하므로 여기에서 1을 뺍니다.

Answer 2

누군가가 관심을 보이면 며칠 전에 구현했습니다.

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++]; 
    } 
}