Specifi c проблема с реализацией алгоритма сортировки слиянием - PullRequest
Новая
       28

Specifi c проблема с реализацией алгоритма сортировки слиянием

0 голосов
/ 05 мая 2020

Java

Я пытаюсь написать алгоритм сортировки слиянием, чтобы отсортировать список настраиваемых объектов в алфавитном порядке, теперь я смотрю на свой код и псевдокод на пару часов и еще не выяснил, почему он не работает,

Возможно, некоторые fre sh глаза могут помочь,

Мой код выглядит следующим образом ... 

    /**
     * Merge Sort Algorithm
     * @param array array to sort
     * @param i - point to start sorting at
     * @param j - point to end sorting at
     */
    public void MergeSort(Movie[] array, int i, int j) {

        if(i < j){
            int m = (i+j)/2;

            MergeSort(array, i, m);
            MergeSort(array, m+1, j);

            merge(array,m);
        }
    }


    void merge(Movie[] array, int m){
        int p = 0;
        int q = m+1;
        int r = 0;
        int j = array.length-1;

        Movie[] temp = new Movie[array.length];

        while(p <= m && q <= j){
            if(array[p].compareTo(array[q]) == 1){
                temp[r++] = array[p++];
            }else{
                temp[r++] = array[q++];
            }
        }

        while (p <= m){
            temp[r++] = array[p++];
        }
        while (q <= j){
            temp[r++] = array[q++];
        }
        System.arraycopy(temp,0,array,0,temp.length);
    }

При тестировании на случаях «a, b, c, d, e, h, y, z» результат будет следующим ... 

a |
b |
d |
e | 
h |
c |
y |
z |

Очевидно это не в алфавитном порядке, просто не могу понять, почему

1 Ответ

0 голосов
/ 05 мая 2020

Глядя на псевдокод, который вы разместили в комментарии , я могу сказать вам, что вы не реализовали этот псевдокод.

Merge (A [i. ..j], m) функция имеет параметры m , который является mid, массив A и параметры i и j , чтобы определить границы для слияния в этом массиве. На мой взгляд, псевдокод просто не точен и плох.

Параметры i и j используются для инициализации p и г . В вашей текущей реализации вы инициализируете оба параметра 0, что не является тем, что делает псевдокод.

Вашему методу merge нужны эти два параметра i и j для определения границ для слияния .

...