내 병합 정렬 프로그램이 Java에서 범위를 벗어난 배열을 보여줍니다. (My merge sort program shows an array out of bound in Java)

문제 설명

내 병합 정렬 프로그램이 Java에서 범위를 벗어난 배열을 보여줍니다. (My merge sort program shows an array out of bound in Java)

저는 Java를 배우고 있고 이 병합 정렬 프로그램을 만들지만 ArrayOutOfBound 예외가 발생합니다. 내 실수는 무엇입니까?

array.length 또는 array.length‑1에서도 이 코드를 사용하지만 두 경우 모두 실패합니다. 내 코드가 배열의 길이를 허용하지 않는 것 같습니다.

// 배열을 나누려면‑‑‑

void divide(int a[], int lb, int ub) {
    if (lb < ub) {
        int mid = (lb + ub) / 2;
        divide(a, lb, mid);
        divide(a, mid + 1, ub);
        merge(a, lb, mid, ub);
    }
}

//실제 배열을 인쇄하려면‑‑‑

static void ActualArray(int a[]) {
    System.out.println("‑‑‑‑!!!Merge Sort!!!‑‑‑‑");
    System.out.println("Your Array is: ");
    for (int i : a) {
        System.out.print(i + " ");
    }
    System.out.println("\n");
}

//어레이 병합용

void merge(int a[], int lb, int mid, int ub) {
    int i = lb;
    int j = mid + 1;
    int k = lb;
    int b[] = {};
    while (i <= mid && j <= ub) {
        if (a[i] < a[j]) {
            b[k] = a[i];
            i++;
        } else {
            b[k] = a[j];
            j++;
        }
        k++;
    }
    if (i > mid) {
        while (j <= ub) {
            b[k] = a[j];
            j++;
            k++;
        }
    } else {
        while (i <= mid) {
            b[k] = a[i];
            i++;
            k++;
        }
    }
    System.out.println("Your Sorted Array is: ");
    for (int ele : b) {
        System.out.print(ele + " ");
    }
}

// 주요 방법

public static void main(String args[]) {
    int arr[] = { 25, 16, 45, 17, 84, 61 };
    ActualArray(arr);

    MergeSort obj = new MergeSort();
    obj.divide(arr, 0, arr.length ‑ 1);
}

참조 솔루션

방법 1:

There are multiple problems in your merge method:

• you do not allocate the temporary array b. You should write int b[] = new int[ub ‑ lb + 1];
• the index k into the temporary array should be initialized to 0, not lb.
• you should copy the contents of the temporary array back to a.
• printing the sorted slice is for debugging only.

Here is a modified version:

void merge(int a[], int lb, int mid, int ub) {
    int b[] = new int[ub ‑ lb + 1];
    int i = lb;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= ub) {
        if (a[i] < a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
        }
    }
    // copy the remaining elements from the left part
    while (i <= mid) {
        b[k++] = a[i++];
    }
    // the remaining elements from the right part are already in the proper place
    // copy back the sorted slice into the original array
    for (i = 0; i < k; i++) {
        a[lb + i] = b[i];
    }
}

(by Ashish Verma、chqrlie)

참조 문서

1. My merge sort program shows an array out of bound in Java (CC BY‑SA 2.5/3.0/4.0)