Реализация списка сортировки слиянием TopDown + BottomUp + Abstract MergeSort

Я пытаюсь реализовать сортировку слиянием для статических списков (ArrayLists). У меня есть реализация как TopDown, так и BottomUp. Однако я считаю, что абстрактная сортировка слиянием не работает. Я говорю это, потому что я тестировал обе реализации с одним и тем же неупорядоченным списком, что наводит меня на мысль, что метод слияния - это тот, который не работает. Не могу найти ошибку. Частные методы находятся в разных классах. Я собрал их здесь для облегчения чтения. Вот код. Заранее спасибо.

    public <T> void merge(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int mid, int hi) {
//        // Merge a[lo..mid] with a[mid+1..hi].
        List<T> aux = new ArrayList<>(list);// Copy a[lo..hi] to aux[lo..hi].
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) // Merge back to a[lo..hi].
            if (i > mid)
                list.set(k, aux.get(j++));
            else if (j > hi)
                list.set(k, aux.get(i++));
            else if (comparator.compare(list.get(i), list.get(j)) > 0)
                list.set(k, aux.get(j++));
            else
                list.set(k, aux.get(i++));
    }


    public <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list) {
        sort(comparator, list, 0, list.size() - 1);
    }



    //TopDown
    private <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int hi) {  // Sort a[lo..hi].
         if (hi <= lo) return;
         int mid = lo + (hi - lo)/2;
         sort(comparator, list, lo, mid);       // Sort left half.
         sort(comparator, list, mid+1, hi);     // Sort right half.
         merge(comparator, list, lo, mid, hi);  // Merge results
    }

    //BottomUp
    private <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list) {
        for (int mid = 1; mid < list.size(); mid = mid + mid)
            // mid: subarray size
            for (int lo = 0; lo < list.size() - mid; lo += mid + mid) { // lo: subarray index
                merge(comparator, list, lo, lo + mid - 1, Math.min(lo + mid + mid - 1, list.size() - 1));
            }
    }

java sorting mergesort
person Tomas Piaggio    schedule 05.09.2016    source источник
comment
Что такое абстрактная сортировка слиянием?   -  person rcgldr    schedule 06.09.2016
comment
Используется ли метод слияния для обоих сортировщиков слияния.   -  person Tomas Piaggio    schedule 07.09.2016
comment
И сверху вниз, и снизу вверх можно использовать одну и ту же функцию слияния. При вызове снизу вверх также необходимо проверить, есть ли только копия левой половины: merge (..., min (lo + mid -1, list.size () - 1), ...). Было бы лучше сделать одноразовое выделение вспомогательных данных в функции сортировки верхнего уровня, а затем передать его как параметр для сортировки сверху вниз или снизу вверх. Текущий код выделяет всю копию списка для каждой операции слияния, которая будет медленной и может не хватить места с большим списком.   -  person rcgldr    schedule 07.09.2016
comment
Я учту эти оптимизации. Однако код не работает. Я получаю обратно неупорядоченный список. Вы можете определить проблему?   -  person Tomas Piaggio    schedule 07.09.2016

Ответы (1)


arrow_upward
1
arrow_downward

Код в merge () сравнивает элементы списка вывода (list) вместо элемента списка ввода (aux).

изменение

        else if (comparator.compare(list.get(i), list.get(j)) > 0)

to

        else if (comparator.compare(aux.get(i), aux.get(j)) > 0)

Есть ли причина, по которой merge () не является закрытым и что merge () и sort () не статичны?

person rcgldr    schedule 07.09.2016