Почему этот MergeSort не работает? - PullRequest
Новая
       10

Почему этот MergeSort не работает?

0 голосов
/ 07 мая 2018

Я использовал нисходящий псевдо-код из Википедии при создании этого тестового кода: 

public static void main(String args[]) {
    int[] nums = new int[] { 17, 5, 3, 7, 6, 3, 11, 2 };
    mergeSort(nums);
    for (int i = 0; i < nums.length; i++) {
        System.out.print(nums[i] + " ,");
    }
}

public static void mergeSort(int[] A) {
    int[] B = new int[A.length];
    System.arraycopy(A, 0, B, 0, A.length);
    splitMerge(B, 0, A.length, A); // sort data from B[] into A[]
}

public static void splitMerge(int[] B, int begin, int end, int[] A) {
    if (end - begin < 2)
        return;
    int middle = (end + begin) / 2;
    splitMerge(B, begin, middle, A);
    splitMerge(B, middle, end, A);
    System.out.println("begin: " + begin +  " mid: " + ((end - begin)/2) + " end: " + end + " SIZE: " + (end-begin));
    merge(B, begin, middle, end, A);

}

public static void merge(int[] B, int begin, int middle, int end, int[] A) {
    int i = begin;
    int j = middle;
    for (int k = begin; k < end; k++) {
        if (i < middle && (j >= end || B[i] <= B[j])) {
            A[k] = B[i];
            i = i + 1;
        } else {
            A[k] = B[j];
            j = j + 1;
        }
    }
}

Это должно быть более или менее точно так же, как псевдо-код, так почему он не работает? Вот вывод: 

begin: 0 mid: 1 end: 2 SIZE: 2
begin: 2 mid: 1 end: 4 SIZE: 2
begin: 0 mid: 2 end: 4 SIZE: 4
begin: 4 mid: 1 end: 6 SIZE: 2
begin: 6 mid: 1 end: 8 SIZE: 2
begin: 4 mid: 2 end: 8 SIZE: 4
begin: 0 mid: 4 end: 8 SIZE: 8
6 ,3 ,11 ,2 ,17 ,5 ,3 ,7 ,

1 Ответ

0 голосов
/ 07 мая 2018

Ваш массив B содержит копию исходного массива, и вы никогда не измените его, пока вы изменяете исходный массив A.

Это означает, что метод merge не может работать, так как он объединяет два несортированных массива (два подмассива B, которые остаются несортированными по всему алгоритму).

Для правильного выполнения merge необходимо скопировать элементы с индексами от begin до end из массива A в массив B в начале метода слияния.

Все, что вам нужно сделать, это добавить утверждение 

System.arraycopy(A, begin, B, begin, end - begin);

как первое утверждение вашего merge метода.

то есть:. 

public static void merge(int[] B, int begin, int middle, int end, int[] A) {
    System.arraycopy(A, begin, B, begin, end - begin);
    int i = begin;
    int j = middle;
    for (int k = begin; k < end; k++) {
        if (i < middle && (j >= end || B[i] <= B[j])) {
            A[k] = B[i];
            i = i + 1;
        } else {
            A[k] = B[j];
            j = j + 1;
        }
    }
}

Это даст результат 

2 ,3 ,3 ,5 ,6 ,7 ,11 ,17 ,

для данного ввода.

...